[Analyzer] Make referenced SymbolMetadata live even if its region is dead

[a.sidorin]

Summary

If SymbolMetadata is referenced but its region is dead it is removed from GDM entries making referenced information inconsistent. This patch resolves this issue.
This also resolves some FIXMEs in CStringChecker tests.

[jordan_rose]

The intent here was that a metadata symbol represents metadata about a region. That means if the region is dead, and the symbol isn't directly referenceable, we won't be able to recreate it. The advantage of && was that checkers didn't have to track when regions were no longer live.

Of course, the example shows that a symbol doesn't have to be directly referenceable to be used, so it didn't exactly pan out. But making this change without a corresponding change to every checker using metadata symbols (in-tree, just CStringChecker) means that those checkers will now keep the symbols alive forever. (And if we wanted to do that, we wouldn't have to use markInUse; just markLive.)

I think this needs a little more thought.

[a.sidorin]

Thank you for you reply!

This version contains more radical solution. Also, I took an another look at the CStringChecker and its way of handling checkDeadSymbols.

[a.sidorin]

lib/StaticAnalyzer/Core/SymbolManager.cpp

457

Maybe we should just return false here?

[jordan_rose]

So we just throw out the whole notion of "metadata in use"? That can work. There are two things I'd be concerned about changing here:

• What happens when you take a string's length, test it against something, throw it away, then remeasure the string? In this case we'd be okay because CStringChecker still hangs on to the symbol in its map until the region is invalidated.
• Will we keep more symbols alive than we did previously, increasing the analyzer's memory use? I think the answer is "yes", but not by very much: the live/dead checking is two-pass, so we'll mark a metadata symbol live in checkLiveSymbols but then find out we could have dropped it in checkDeadSymbols when the region is found to be dead. It'll get cleaned up the next time around, but I think that sort of conditional liveness is what the old mechanism was trying to accomplish.

Do you have any ideas for how we could make that better? I can think of a complicated case where you use markInUse if the metadata symbol exactly matches the key, but markLive otherwise…but at some point I'm not sure it's worth the complexity cost. (In particular, after this change, I'm not sure metadata symbols behave any differently from regular conjured symbols. This is a good thing.)

(We've also talked about having better REGISTER_MAP_WITH_PROGRAMSTATE that auto-remove any keys for dead symbols or dead regions. I'm sure Anna and Devin would be happy to see someone pick that up.)

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2137–2141

Huh, this is probably an improvement anyway!

[a.sidorin]

• What happens when you take a string's length, test it against something, throw it away, then remeasure the string? In this case we'd be okay because CStringChecker still hangs on to the symbol in its map until the region is invalidated.

We cannot throw out anything related to live region we reference in the checker. While region lives, checker will keep its length alive, so this case seem to be OK.

• Will we keep more symbols alive than we did previously, increasing the analyzer's memory use? I think the answer is "yes", but not by very much: the live/dead checking is two-pass, so we'll mark a metadata symbol live in checkLiveSymbols but then find out we could have dropped it in checkDeadSymbols when the region is found to be dead. It'll get cleaned up the next time around, but I think that sort of conditional liveness is what the old mechanism was trying to accomplish.

Yes, you are right. The lengths of dead regions will be garbage-collected only in the next collection so they will consume some memory.

Do you have any ideas for how we could make that better? I can think of a complicated case where you use markInUse if the metadata symbol exactly matches the key, but markLive otherwise…but at some point I'm not sure it's worth the complexity cost.

As I understand, to make a precise GC, we need to do it in a number of iterations but now we make only one iteration. This does not influence correctness because we are conservative and we don't remove information that is alive (but may keep some dead). However, iterative GC may dramatically decrease analyzer perfomance.

(In particular, after this change, I'm not sure metadata symbols behave any differently from regular conjured symbols. This is a good thing.)

Yes. But we extensively use SymbolMetadata's information in our summary implementation so don't hurry to throw it out :)

(We've also talked about having better REGISTER_MAP_WITH_PROGRAMSTATE that auto-remove any keys for dead symbols or dead regions. I'm sure Anna and Devin would be happy to see someone pick that up.)

I don't think it is a good idea because some checkers handle dead symbols in customizable ways to detect leaks. Some helper for remove all items with dead keys from state working with common collections (in CheckerHelpers, for example) may be useful to to avoid code duplication, but it is an item for another patch.

BTW, what about my comment for line 457? Should we consider a metadata symbol always dead after this patch?

[a.sidorin]

Sorry, I misunderstood your first question. This case is OK because CStringChecker handles invalidation and shouldn't track invalidated regions until their lengths become known. Test strlen_global() (string.c:106) should confirm this.

[a.sidorin]

Ping?

[xazax.hun]

Maybe it would be great to do a profiling before and after this patch?
It looks like this is a hotspot of the analyzer: http://clang-developers.42468.n3.nabble.com/Analyzer-pretty-profiling-pictures-td4052016.html

[a.sidorin]

Gabor: Ok,will do.

include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h

   typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
 
   SymbolMapTy TheLiving;
-  SymbolSetTy MetadataInUse;
   SymbolSetTy TheDead;
 
   RegionSetTy RegionRoots;

   /// environment. Checkers should instead use metadata symbols and markInUse.
   void markLive(SymbolRef sym);
 
-  /// \brief Marks a symbol as important to a checker.
-  ///
-  /// For metadata symbols,
-  /// this will keep the symbol alive as long as its associated region is also
-  /// live. For other symbols, this has no effect; checkers are not permitted
-  /// to influence the life of other symbols. This should be used before any
-  /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
-  void markInUse(SymbolRef sym);
-
   /// \brief If a symbol is known to be live, marks the symbol as live.
   ///
   ///  Otherwise, if the symbol cannot be proven live, it is marked as dead.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

 
     for (SymExpr::symbol_iterator si = Len.symbol_begin(),
                                   se = Len.symbol_end(); si != se; ++si)
-      SR.markInUse(*si);
+      SR.markLive(*si);
   }
 }
 
 void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
                                       CheckerContext &C) const {
-  if (!SR.hasDeadSymbols())
-    return;
-
-  ProgramStateRef state = C.getState();
-  CStringLengthTy Entries = state->get<CStringLength>();
+  auto state = C.getState();
+  auto Entries = state->get<CStringLength>();
   if (Entries.isEmpty())
     return;
 
-  CStringLengthTy::Factory &F = state->get_context<CStringLength>();
-  for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end();
-       I != E; ++I) {
-    SVal Len = I.getData();
-    if (SymbolRef Sym = Len.getAsSymbol()) {
-      if (SR.isDead(Sym))
-        Entries = F.remove(Entries, I.getKey());
-    }
+  auto &F = state->get_context<CStringLength>();
+  for (auto I = Entries.begin(), E = Entries.end(); I != E; ++I) {
+    const MemRegion *MR = I.getKey();
+    if (!SR.isLiveRegion(MR))
+      Entries = F.remove(Entries, MR);
   }
 
   state = state->set<CStringLength>(Entries);

lib/StaticAnalyzer/Core/SymbolManager.cpp

   RegionRoots.insert(region);
 }
 
-void SymbolReaper::markInUse(SymbolRef sym) {
-  if (isa<SymbolMetadata>(sym))
-    MetadataInUse.insert(sym);
-}
-
 bool SymbolReaper::maybeDead(SymbolRef sym) {
   if (isLive(sym))
     return false;

     KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
     break;
   case SymExpr::MetadataKind:
-    KnownLive = MetadataInUse.count(sym) &&
-                isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
-    if (KnownLive)
-      MetadataInUse.erase(sym);
+    KnownLive = isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
     break;
   case SymExpr::SymIntKind:
     KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());

test/Analysis/string.c

   clang_analyzer_eval(strlen(dst) >= 4); // expected-warning{{TRUE}}
 }
 
+void strcat_symbolic_src_length(char *src) {
+  char dst[8] = "1234";
+  strcat(dst, src);
+  clang_analyzer_eval(strlen(dst) >= 4); // expected-warning{{TRUE}}
+}
+
 void strcat_symbolic_dst_length_taint(char *dst) {
   scanf("%s", dst); // Taint data.
   strcat(dst, "1234");

   clang_analyzer_eval(strlen(x) > 4); // expected-warning{{UNKNOWN}}
 }
 
+void strncpy_exactly_matching_buffer2(char *y) {
+    if (strlen(y) >= 4)
+        return;
+
+    char x[4];
+    strncpy(x, y, 4); // no-warning
+
+    // This time, we know that y fits in x anyway.
+  clang_analyzer_eval(strlen(x) <= 3); // expected-warning{{TRUE}}
+}
+
 void strncpy_zero(char *src) {
   char dst[] = "123";
   strncpy(dst, src, 0); // no-warning

   // character. For now, we just model the invalidation.
   clang_analyzer_eval(str[1] == 'b'); // expected-warning{{UNKNOWN}}
 }
-
-//===----------------------------------------------------------------------===
-// FIXMEs
-//===----------------------------------------------------------------------===
-
-// The analyzer_eval call below should evaluate to true. We are being too 
-// aggressive in marking the (length of) src symbol dead. The length of dst 
-// depends on src. This could be explicitely specified in the checker or the 
-// logic for handling MetadataSymbol in SymbolManager needs to change.
-void strcat_symbolic_src_length(char *src) {
-  char dst[8] = "1234";
-  strcat(dst, src);
-  clang_analyzer_eval(strlen(dst) >= 4); // expected-warning{{UNKNOWN}}
-}
-
-// The analyzer_eval call below should evaluate to true. Most likely the same
-// issue as the test above.
-void strncpy_exactly_matching_buffer2(char *y) {
-  if (strlen(y) >= 4)
-    return;
-
-  char x[4];
-  strncpy(x, y, 4); // no-warning
-
-  // This time, we know that y fits in x anyway.
-  clang_analyzer_eval(strlen(x) <= 3); // expected-warning{{UNKNOWN}}
-}