328 lines · plain
1================2Initializer List3================4This discussion took place in https://reviews.llvm.org/D352165"Escape symbols when creating std::initializer_list".6 7It touches problems of modelling C++ standard library constructs in general,8including modelling implementation-defined fields within C++ standard library9objects, in particular constructing objects into pointers held by such fields,10and separation of responsibilities between analyzer's core and checkers.11 12**Artem:**13 14I've seen a few false positives that appear because we construct15C++11 std::initializer_list objects with brace initializers, and such16construction is not properly modeled. For instance, if a new object is17constructed on the heap only to be put into a brace-initialized STL container,18the object is reported to be leaked.19 20Approach (0): This can be trivially fixed by this patch, which causes pointers21passed into initializer list expressions to immediately escape.22 23This fix is overly conservative though. So i did a bit of investigation as to24how model std::initializer_list better.25 26According to the standard, ``std::initializer_list<T>`` is an object that has27methods ``begin(), end(), and size()``, where ``begin()`` returns a pointer to continuous28array of ``size()`` objects of type T, and end() is equal to begin() plus size().29The standard does hint that it should be possible to implement30``std::initializer_list<T>`` as a pair of pointers, or as a pointer and a size31integer, however specific fields that the object would contain are an32implementation detail.33 34Ideally, we should be able to model the initializer list's methods precisely.35Or, at least, it should be possible to explain to the analyzer that the list36somehow "takes hold" of the values put into it. Initializer lists can also be37copied, which is a separate story that i'm not trying to address here.38 39The obvious approach to modeling ``std::initializer_list`` in a checker would be to40construct a SymbolMetadata for the memory region of the initializer list object,41which would be of type ``T*`` and represent ``begin()``, so we'd trivially model ``begin()``42as a function that returns this symbol. The array pointed to by that symbol43would be ``bindLoc()``ed to contain the list's contents (probably as a ``CompoundVal``44to produce less bindings in the store). Extent of this array would represent45``size()`` and would be equal to the length of the list as written.46 47So this sounds good, however apparently it does nothing to address our false48positives: when the list escapes, our ``RegionStoreManager`` is not magically49guessing that the metadata symbol attached to it, together with its contents,50should also escape. In fact, it's impossible to trigger a pointer escape from51within the checker.52 53Approach (1): If only we enabled ``ProgramState::bindLoc(..., notifyChanges=true)``54to cause pointer escapes (not only region changes) (which sounds like the right55thing to do anyway) such checker would be able to solve the false positives by56triggering escapes when binding list elements to the list. However, it'd be as57conservative as the current patch's solution. Ideally, we do not want escapes to58happen so early. Instead, we'd prefer them to be delayed until the list itself59escapes.60 61So i believe that escaping metadata symbols whenever their base regions escape62would be the right thing to do. Currently we didn't think about that because we63had neither pointer-type metadatas nor non-pointer escapes.64 65Approach (2): We could teach the Store to scan itself for bindings to66metadata-symbolic-based regions during scanReachableSymbols() whenever a region67turns out to be reachable. This requires no work on checker side, but it sounds68performance-heavy.69 70Approach (3): We could let checkers maintain the set of active metadata symbols71in the program state (ideally somewhere in the Store, which sounds weird but72causes the smallest amount of layering violations), so that the core knew what73to escape. This puts a stress on the checkers, but with a smart data map it74wouldn't be a problem.75 76Approach (4): We could allow checkers to trigger pointer escapes in arbitrary77moments. If we allow doing this within ``checkPointerEscape`` callback itself, we78would be able to express facts like "when this region escapes, that metadata79symbol attached to it should also escape". This sounds like an ultimate freedom,80with maximum stress on the checkers - still not too much stress when we have81smart data maps.82 83I'm personally liking the approach (2) - it should be possible to avoid84performance overhead, and clarity seems nice.85 86**Gabor:**87 88At this point, I am a bit wondering about two questions.89 90* When should something belong to a checker and when should something belong to the engine?91 Sometimes we model library aspects in the engine and model language constructs in checkers.92 93* What is the checker programming model that we are aiming for? Maximum freedom or more easy checker development?94 95I think if we aim for maximum freedom, we do not need to worry about the96potential stress on checkers, and we can introduce abstractions to mitigate that97later on.98If we want to simplify the API, then maybe it makes more sense to move language99construct modeling to the engine when the checker API is not sufficient instead100of complicating the API.101 102Right now I have no preference or objections between the alternatives but there103are some random thoughts:104 105* Maybe it would be great to have a guideline how to evolve the analyzer and106 follow it, so it can help us to decide in similar situations107 108* I do care about performance in this case. The reason is that we have a109 limited performance budget. And I think we should not expect most of the checker110 writers to add modeling of language constructs. So, in my opinion, it is ok to111 have less nice/more verbose API for language modeling if we can have better112 performance this way, since it only needs to be done once, and is done by the113 framework developers.114 115**Artem:** These are some great questions, i guess it'd be better to discuss116them more openly. As a quick dump of my current mood:117 118* To me it seems obvious that we need to aim for a checker API that is both119 simple and powerful. This can probably by keeping the API as powerful as120 necessary while providing a layer of simple ready-made solutions on top of it.121 Probably a few reusable components for assembling checkers. And this layer122 should ideally be pleasant enough to work with, so that people would prefer to123 extend it when something is lacking, instead of falling back to the complex124 omnipotent API. I'm thinking of AST matchers vs. AST visitors as a roughly125 similar situation: matchers are not omnipotent, but they're so nice.126 127* Separation between core and checkers is usually quite strange. Once we have128 shared state traits, i generally wouldn't mind having region store or range129 constraint manager as checkers (though it's probably not worth it to transform130 them - just a mood). The main thing to avoid here would be the situation when131 the checker overwrites stuff written by the core because it thinks it has a132 better idea what's going on, so the core should provide a good default behavior.133 134* Yeah, i totally care about performance as well, and if i try to implement135 approach, i'd make sure it's good.136 137**Artem:**138 139> Approach (2): We could teach the Store to scan itself for bindings to140> metadata-symbolic-based regions during scanReachableSymbols() whenever141> a region turns out to be reachable. This requires no work on checker side,142> but it sounds performance-heavy.143 144Nope, this approach is wrong. Metadata symbols may become out-of-date: when the145object changes, metadata symbols attached to it aren't changing (because symbols146simply don't change). The same metadata may have different symbols to denote its147value in different moments of time, but at most one of them represents the148actual metadata value. So we'd be escaping more stuff than necessary.149 150If only we had "ghost fields"151(https://lists.llvm.org/pipermail/cfe-dev/2016-May/049000.html), it would have152been much easier, because the ghost field would only contain the actual153metadata, and the Store would always know about it. This example adds to my154belief that ghost fields are exactly what we need for most C++ checkers.155 156**Devin:**157 158In this case, I would be fine with some sort of159AbstractStorageMemoryRegion that meant "here is a memory region and somewhere160reachable from here exists another region of type T". Or even multiple regions161with different identifiers. This wouldn't specify how the memory is reachable,162but it would allow for transfer functions to get at those regions and it would163allow for invalidation.164 165For ``std::initializer_list`` this reachable region would the region for the backing166array and the transfer functions for begin() and end() yield the beginning and167end element regions for it.168 169In my view this differs from ghost variables in that (1) this storage does170actually exist (it is just a library implementation detail where that storage171lives) and (2) it is perfectly valid for a pointer into that storage to be172returned and for another part of the program to read or write from that storage.173(Well, in this case just read since it is allowed to be read-only memory).174 175What I'm not OK with is modeling abstract analysis state (for example, the count176of a NSMutableArray or the typestate of a file handle) as a value stored in some177ginned up region in the store. This takes an easy problem that the analyzer does178well at (modeling typestate) and turns it into a hard one that the analyzer is179bad at (reasoning about the contents of the heap).180 181I think the key criterion here is: "is the region accessible from outside the182library". That is, does the library expose the region as a pointer that can be183read to or written from in the client program? If so, then it makes sense for184this to be in the store: we are modeling reachable storage as storage. But if185we're just modeling arbitrary analysis facts that need to be invalidated when a186pointer escapes then we shouldn't try to gin up storage for them just to get187invalidation for free.188 189**Artem:**190 191> In this case, I would be fine with some sort of ``AbstractStorageMemoryRegion``192> that meant "here is a memory region and somewhere reachable from here exists193> another region of type T". Or even multiple regions with different194> identifiers. This wouldn't specify how the memory is reachable, but it would195> allow for transfer functions to get at those regions and it would allow for196> invalidation.197 198Yeah, this is what we can easily implement now as a199symbolic-region-based-on-a-metadata-symbol (though we can make a new region200class for that if we eg. want it typed). The problem is that the relation201between such storage region and its parent object region is essentially202immaterial, similarly to the relation between ``SymbolRegionValue`` and its parent203region. Region contents are mutable: today the abstract storage is reachable204from its parent object, tomorrow it's not, and maybe something else becomes205reachable, something that isn't even abstract. So the parent region for the206abstract storage is most of the time at best a "nice to know" thing - we cannot207rely on it to do any actual work. We'd anyway need to rely on the checker to do208the job.209 210> For std::initializer_list this reachable region would the region for the211> backing array and the transfer functions for begin() and end() yield the212> beginning and end element regions for it.213 214So maybe in fact for std::initializer_list it may work fine because you cannot215change the data after the object is constructed - so this region's contents are216essentially immutable. For the future, i feel as if it is a dead end.217 218I'd like to consider another funny example. Suppose we're trying to model219 220.. code-block:: cpp221 222 std::unique_ptr. Consider::223 224 void bar(const std::unique_ptr<int> &x);225 226 void foo(std::unique_ptr<int> &x) {227 int *a = x.get(); // (a, 0, direct): &AbstractStorageRegion228 *a = 1; // (AbstractStorageRegion, 0, direct): 1 S32b229 int *b = new int;230 *b = 2; // (SymRegion{conj_$0<int *>}, 0 ,direct): 2 S32b231 x.reset(b); // Checker map: x -> SymRegion{conj_$0<int *>}232 bar(x); // 'a' doesn't escape (the pointer was unique), 'b' does.233 clang_analyzer_eval(*a == 1); // Making this true is up to the checker.234 clang_analyzer_eval(*b == 2); // Making this unknown is up to the checker.235 }236 237The checker doesn't totally need to ensure that ``*a == 1`` passes - even though the238pointer was unique, it could theoretically have ``.get()``-ed above and the code239could of course break the uniqueness invariant (though we'd probably want it).240The checker can say that "even if ``*a`` did escape, it was not because it was241stuffed directly into bar()".242 243The checker's direct responsibility, however, is to solve the ``*b == 2`` thing244(which is in fact the problem we're dealing with in this patch - escaping the245storage region of the object).246 247So we're talking about one more operation over the program state (scanning248reachable symbols and regions) that cannot work without checker support.249 250We can probably add a new callback "checkReachableSymbols" to solve this. This251is in fact also related to the dead symbols problem (we're scanning for live252symbols in the store and in the checkers separately, but we need to do so253simultaneously with a single worklist). Hmm, in fact this sounds like a good254idea; we can replace checkLiveSymbols with checkReachableSymbols.255 256Or we could just have ghost member variables, and no checker support required at257all. For ghost member variables, the relation with their parent region (which258would be their superregion) is actually useful, the mutability of their contents259is expressed naturally, and the store automagically sees reachable symbols, live260symbols, escapes, invalidations, whatever.261 262> In my view this differs from ghost variables in that (1) this storage does263> actually exist (it is just a library implementation detail where that storage264> lives) and (2) it is perfectly valid for a pointer into that storage to be265> returned and for another part of the program to read or write from that266> storage. (Well, in this case just read since it is allowed to be read-only267> memory).268 269> What I'm not OK with is modeling abstract analysis state (for example, the270> count of a NSMutableArray or the typestate of a file handle) as a value stored271> in some ginned up region in the store.This takes an easy problem that the272> analyzer does well at (modeling typestate) and turns it into a hard one that273> the analyzer is bad at (reasoning about the contents of the heap).274 275Yeah, i tend to agree on that. For simple typestates, this is probably an276overkill, so let's definitely put aside the idea of "ghost symbolic regions"277that i had earlier.278 279But, to summarize a bit, in our current case, however, the typestate we're280looking for is the contents of the heap. And when we try to model such281typestates (complex in this specific manner, i.e. heap-like) in any checker, we282have a choice between re-doing this modeling in every such checker (which is283something analyzer is indeed good at, but at a price of making checkers heavy)284or instead relying on the Store to do exactly what it's designed to do.285 286> I think the key criterion here is: "is the region accessible from outside287> the library". That is, does the library expose the region as a pointer that288> can be read to or written from in the client program? If so, then it makes289> sense for this to be in the store: we are modeling reachable storage as290> storage. But if we're just modeling arbitrary analysis facts that need to be291> invalidated when a pointer escapes then we shouldn't try to gin up storage292> for them just to get invalidation for free.293 294As a metaphor, i'd probably compare it to body farms - the difference between295ghost member variables and metadata symbols seems to me like the difference296between body farms and evalCall. Both are nice to have, and body farms are very297pleasant to work with, even if not omnipotent. I think it's fine for a298FunctionDecl's body in a body farm to have a local variable, even if such299variable doesn't actually exist, even if it cannot be seen from outside the300function call. I'm not seeing immediate practical difference between "it does301actually exist" and "it doesn't actually exist, just a handy abstraction".302Similarly, i think it's fine if we have a ``CXXRecordDecl`` with303implementation-defined contents, and try to farm up a member variable as a handy304abstraction (we don't even need to know its name or offset, only that it's there305somewhere).306 307**Artem:**308 309We've discussed it in person with Devin, and he provided more points to think310about:311 312* If the initializer list consists of non-POD data, constructors of list's313 objects need to take the sub-region of the list's region as this-region In the314 current (v2) version of this patch, these objects are constructed elsewhere and315 then trivial-copied into the list's metadata pointer region, which may be316 incorrect. This is our overall problem with C++ constructors, which manifests in317 this case as well. Additionally, objects would need to be constructed in the318 analyzer's core, which would not be able to predict that it needs to take a319 checker-specific region as this-region, which makes it harder, though it might320 be mitigated by sharing the checker state traits.321 322* Because "ghost variables" are not material to the user, we need to somehow323 make super sure that they don't make it into the diagnostic messages.324 325So, because this needs further digging into overall C++ support and rises too326many questions, i'm delaying a better approach to this problem and will fall327back to the original trivial patch.328