|
150
|
1 ================
|
|
|
2 Initializer List
|
|
|
3 ================
|
|
|
4 This discussion took place in https://reviews.llvm.org/D35216
|
|
|
5 "Escape symbols when creating std::initializer_list".
|
|
|
6
|
|
|
7 It touches problems of modelling C++ standard library constructs in general,
|
|
|
8 including modelling implementation-defined fields within C++ standard library
|
|
|
9 objects, in particular constructing objects into pointers held by such fields,
|
|
|
10 and separation of responsibilities between analyzer's core and checkers.
|
|
|
11
|
|
|
12 **Artem:**
|
|
|
13
|
|
|
14 I've seen a few false positives that appear because we construct
|
|
|
15 C++11 std::initializer_list objects with brace initializers, and such
|
|
|
16 construction is not properly modeled. For instance, if a new object is
|
|
|
17 constructed on the heap only to be put into a brace-initialized STL container,
|
|
|
18 the object is reported to be leaked.
|
|
|
19
|
|
|
20 Approach (0): This can be trivially fixed by this patch, which causes pointers
|
|
|
21 passed into initializer list expressions to immediately escape.
|
|
|
22
|
|
|
23 This fix is overly conservative though. So i did a bit of investigation as to
|
|
|
24 how model std::initializer_list better.
|
|
|
25
|
|
|
26 According to the standard, ``std::initializer_list<T>`` is an object that has
|
|
|
27 methods ``begin(), end(), and size()``, where ``begin()`` returns a pointer to continuous
|
|
|
28 array of ``size()`` objects of type T, and end() is equal to begin() plus size().
|
|
|
29 The standard does hint that it should be possible to implement
|
|
|
30 ``std::initializer_list<T>`` as a pair of pointers, or as a pointer and a size
|
|
|
31 integer, however specific fields that the object would contain are an
|
|
|
32 implementation detail.
|
|
|
33
|
|
|
34 Ideally, we should be able to model the initializer list's methods precisely.
|
|
|
35 Or, at least, it should be possible to explain to the analyzer that the list
|
|
|
36 somehow "takes hold" of the values put into it. Initializer lists can also be
|
|
|
37 copied, which is a separate story that i'm not trying to address here.
|
|
|
38
|
|
|
39 The obvious approach to modeling ``std::initializer_list`` in a checker would be to
|
|
|
40 construct a SymbolMetadata for the memory region of the initializer list object,
|
|
|
41 which would be of type ``T*`` and represent ``begin()``, so we'd trivially model ``begin()``
|
|
|
42 as a function that returns this symbol. The array pointed to by that symbol
|
|
|
43 would be ``bindLoc()``ed to contain the list's contents (probably as a ``CompoundVal``
|
|
|
44 to produce less bindings in the store). Extent of this array would represent
|
|
|
45 ``size()`` and would be equal to the length of the list as written.
|
|
|
46
|
|
|
47 So this sounds good, however apparently it does nothing to address our false
|
|
|
48 positives: when the list escapes, our ``RegionStoreManager`` is not magically
|
|
|
49 guessing that the metadata symbol attached to it, together with its contents,
|
|
|
50 should also escape. In fact, it's impossible to trigger a pointer escape from
|
|
|
51 within the checker.
|
|
|
52
|
|
|
53 Approach (1): If only we enabled ``ProgramState::bindLoc(..., notifyChanges=true)``
|
|
|
54 to cause pointer escapes (not only region changes) (which sounds like the right
|
|
|
55 thing to do anyway) such checker would be able to solve the false positives by
|
|
|
56 triggering escapes when binding list elements to the list. However, it'd be as
|
|
|
57 conservative as the current patch's solution. Ideally, we do not want escapes to
|
|
|
58 happen so early. Instead, we'd prefer them to be delayed until the list itself
|
|
|
59 escapes.
|
|
|
60
|
|
|
61 So i believe that escaping metadata symbols whenever their base regions escape
|
|
|
62 would be the right thing to do. Currently we didn't think about that because we
|
|
|
63 had neither pointer-type metadatas nor non-pointer escapes.
|
|
|
64
|
|
|
65 Approach (2): We could teach the Store to scan itself for bindings to
|
|
|
66 metadata-symbolic-based regions during scanReachableSymbols() whenever a region
|
|
|
67 turns out to be reachable. This requires no work on checker side, but it sounds
|
|
|
68 performance-heavy.
|
|
|
69
|
|
|
70 Approach (3): We could let checkers maintain the set of active metadata symbols
|
|
|
71 in the program state (ideally somewhere in the Store, which sounds weird but
|
|
|
72 causes the smallest amount of layering violations), so that the core knew what
|
|
|
73 to escape. This puts a stress on the checkers, but with a smart data map it
|
|
|
74 wouldn't be a problem.
|
|
|
75
|
|
|
76 Approach (4): We could allow checkers to trigger pointer escapes in arbitrary
|
|
|
77 moments. If we allow doing this within ``checkPointerEscape`` callback itself, we
|
|
|
78 would be able to express facts like "when this region escapes, that metadata
|
|
|
79 symbol attached to it should also escape". This sounds like an ultimate freedom,
|
|
|
80 with maximum stress on the checkers - still not too much stress when we have
|
|
|
81 smart data maps.
|
|
|
82
|
|
|
83 I'm personally liking the approach (2) - it should be possible to avoid
|
|
|
84 performance overhead, and clarity seems nice.
|
|
|
85
|
|
|
86 **Gabor:**
|
|
|
87
|
|
|
88 At 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
|
|
|
95 I think if we aim for maximum freedom, we do not need to worry about the
|
|
|
96 potential stress on checkers, and we can introduce abstractions to mitigate that
|
|
|
97 later on.
|
|
|
98 If we want to simplify the API, then maybe it makes more sense to move language
|
|
|
99 construct modeling to the engine when the checker API is not sufficient instead
|
|
|
100 of complicating the API.
|
|
|
101
|
|
|
102 Right now I have no preference or objections between the alternatives but there
|
|
|
103 are some random thoughts:
|
|
|
104
|
|
|
105 * Maybe it would be great to have a guideline how to evolve the analyzer and
|
|
|
106 follow it, so it can help us to decide in similar situations
|
|
|
107
|
|
|
108 * I do care about performance in this case. The reason is that we have a
|
|
|
109 limited performance budget. And I think we should not expect most of the checker
|
|
|
110 writers to add modeling of language constructs. So, in my opinion, it is ok to
|
|
|
111 have less nice/more verbose API for language modeling if we can have better
|
|
|
112 performance this way, since it only needs to be done once, and is done by the
|
|
|
113 framework developers.
|
|
|
114
|
|
|
115 **Artem:** These are some great questions, i guess it'd be better to discuss
|
|
|
116 them 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 both
|
|
|
119 simple and powerful. This can probably by keeping the API as powerful as
|
|
|
120 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 layer
|
|
|
122 should ideally be pleasant enough to work with, so that people would prefer to
|
|
|
123 extend it when something is lacking, instead of falling back to the complex
|
|
|
124 omnipotent API. I'm thinking of AST matchers vs. AST visitors as a roughly
|
|
|
125 similar situation: matchers are not omnipotent, but they're so nice.
|
|
|
126
|
|
|
127 * Separation between core and checkers is usually quite strange. Once we have
|
|
|
128 shared state traits, i generally wouldn't mind having region store or range
|
|
|
129 constraint manager as checkers (though it's probably not worth it to transform
|
|
|
130 them - just a mood). The main thing to avoid here would be the situation when
|
|
|
131 the checker overwrites stuff written by the core because it thinks it has a
|
|
|
132 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 implement
|
|
|
135 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 to
|
|
|
140 > metadata-symbolic-based regions during scanReachableSymbols() whenever
|
|
|
141 > a region turns out to be reachable. This requires no work on checker side,
|
|
|
142 > but it sounds performance-heavy.
|
|
|
143
|
|
|
144 Nope, this approach is wrong. Metadata symbols may become out-of-date: when the
|
|
|
145 object changes, metadata symbols attached to it aren't changing (because symbols
|
|
|
146 simply don't change). The same metadata may have different symbols to denote its
|
|
|
147 value in different moments of time, but at most one of them represents the
|
|
|
148 actual metadata value. So we'd be escaping more stuff than necessary.
|
|
|
149
|
|
|
150 If only we had "ghost fields"
|
|
|
151 (https://lists.llvm.org/pipermail/cfe-dev/2016-May/049000.html), it would have
|
|
|
152 been much easier, because the ghost field would only contain the actual
|
|
|
153 metadata, and the Store would always know about it. This example adds to my
|
|
|
154 belief that ghost fields are exactly what we need for most C++ checkers.
|
|
|
155
|
|
|
156 **Devin:**
|
|
|
157
|
|
|
158 In this case, I would be fine with some sort of
|
|
|
159 AbstractStorageMemoryRegion that meant "here is a memory region and somewhere
|
|
|
160 reachable from here exists another region of type T". Or even multiple regions
|
|
|
161 with different identifiers. This wouldn't specify how the memory is reachable,
|
|
|
162 but it would allow for transfer functions to get at those regions and it would
|
|
|
163 allow for invalidation.
|
|
|
164
|
|
|
165 For ``std::initializer_list`` this reachable region would the region for the backing
|
|
|
166 array and the transfer functions for begin() and end() yield the beginning and
|
|
|
167 end element regions for it.
|
|
|
168
|
|
|
169 In my view this differs from ghost variables in that (1) this storage does
|
|
|
170 actually exist (it is just a library implementation detail where that storage
|
|
|
171 lives) and (2) it is perfectly valid for a pointer into that storage to be
|
|
|
172 returned 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
|
|
|
175 What I'm not OK with is modeling abstract analysis state (for example, the count
|
|
|
176 of a NSMutableArray or the typestate of a file handle) as a value stored in some
|
|
|
177 ginned up region in the store. This takes an easy problem that the analyzer does
|
|
|
178 well at (modeling typestate) and turns it into a hard one that the analyzer is
|
|
|
179 bad at (reasoning about the contents of the heap).
|
|
|
180
|
|
|
181 I think the key criterion here is: "is the region accessible from outside the
|
|
|
182 library". That is, does the library expose the region as a pointer that can be
|
|
|
183 read to or written from in the client program? If so, then it makes sense for
|
|
|
184 this to be in the store: we are modeling reachable storage as storage. But if
|
|
|
185 we're just modeling arbitrary analysis facts that need to be invalidated when a
|
|
|
186 pointer escapes then we shouldn't try to gin up storage for them just to get
|
|
|
187 invalidation 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 exists
|
|
|
193 > another region of type T". Or even multiple regions with different
|
|
|
194 > identifiers. This wouldn't specify how the memory is reachable, but it would
|
|
|
195 > allow for transfer functions to get at those regions and it would allow for
|
|
|
196 > invalidation.
|
|
|
197
|
|
|
198 Yeah, this is what we can easily implement now as a
|
|
|
199 symbolic-region-based-on-a-metadata-symbol (though we can make a new region
|
|
|
200 class for that if we eg. want it typed). The problem is that the relation
|
|
|
201 between such storage region and its parent object region is essentially
|
|
|
202 immaterial, similarly to the relation between ``SymbolRegionValue`` and its parent
|
|
|
203 region. Region contents are mutable: today the abstract storage is reachable
|
|
|
204 from its parent object, tomorrow it's not, and maybe something else becomes
|
|
|
205 reachable, something that isn't even abstract. So the parent region for the
|
|
|
206 abstract storage is most of the time at best a "nice to know" thing - we cannot
|
|
|
207 rely on it to do any actual work. We'd anyway need to rely on the checker to do
|
|
|
208 the job.
|
|
|
209
|
|
|
210 > For std::initializer_list this reachable region would the region for the
|
|
|
211 > backing array and the transfer functions for begin() and end() yield the
|
|
|
212 > beginning and end element regions for it.
|
|
|
213
|
|
|
214 So maybe in fact for std::initializer_list it may work fine because you cannot
|
|
|
215 change the data after the object is constructed - so this region's contents are
|
|
|
216 essentially immutable. For the future, i feel as if it is a dead end.
|
|
|
217
|
|
|
218 I'd like to consider another funny example. Suppose we're trying to model
|
|
|
219
|
|
|
220 .. code-block:: cpp
|
|
|
221
|
|
|
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): &AbstractStorageRegion
|
|
|
228 *a = 1; // (AbstractStorageRegion, 0, direct): 1 S32b
|
|
|
229 int *b = new int;
|
|
|
230 *b = 2; // (SymRegion{conj_$0<int *>}, 0 ,direct): 2 S32b
|
|
|
231 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
|
|
|
237 The checker doesn't totally need to ensure that ``*a == 1`` passes - even though the
|
|
|
238 pointer was unique, it could theoretically have ``.get()``-ed above and the code
|
|
|
239 could of course break the uniqueness invariant (though we'd probably want it).
|
|
|
240 The checker can say that "even if ``*a`` did escape, it was not because it was
|
|
|
241 stuffed directly into bar()".
|
|
|
242
|
|
|
243 The checker's direct responsibility, however, is to solve the ``*b == 2`` thing
|
|
|
244 (which is in fact the problem we're dealing with in this patch - escaping the
|
|
|
245 storage region of the object).
|
|
|
246
|
|
|
247 So we're talking about one more operation over the program state (scanning
|
|
|
248 reachable symbols and regions) that cannot work without checker support.
|
|
|
249
|
|
|
250 We can probably add a new callback "checkReachableSymbols" to solve this. This
|
|
|
251 is in fact also related to the dead symbols problem (we're scanning for live
|
|
|
252 symbols in the store and in the checkers separately, but we need to do so
|
|
|
253 simultaneously with a single worklist). Hmm, in fact this sounds like a good
|
|
|
254 idea; we can replace checkLiveSymbols with checkReachableSymbols.
|
|
|
255
|
|
|
256 Or we could just have ghost member variables, and no checker support required at
|
|
|
257 all. For ghost member variables, the relation with their parent region (which
|
|
|
258 would be their superregion) is actually useful, the mutability of their contents
|
|
|
259 is expressed naturally, and the store automagically sees reachable symbols, live
|
|
|
260 symbols, escapes, invalidations, whatever.
|
|
|
261
|
|
|
262 > In my view this differs from ghost variables in that (1) this storage does
|
|
|
263 > actually exist (it is just a library implementation detail where that storage
|
|
|
264 > lives) and (2) it is perfectly valid for a pointer into that storage to be
|
|
|
265 > returned and for another part of the program to read or write from that
|
|
|
266 > storage. (Well, in this case just read since it is allowed to be read-only
|
|
|
267 > memory).
|
|
|
268
|
|
|
269 > What I'm not OK with is modeling abstract analysis state (for example, the
|
|
|
270 > count of a NSMutableArray or the typestate of a file handle) as a value stored
|
|
|
271 > in some ginned up region in the store.This takes an easy problem that the
|
|
|
272 > analyzer does well at (modeling typestate) and turns it into a hard one that
|
|
|
273 > the analyzer is bad at (reasoning about the contents of the heap).
|
|
|
274
|
|
|
275 Yeah, i tend to agree on that. For simple typestates, this is probably an
|
|
|
276 overkill, so let's definitely put aside the idea of "ghost symbolic regions"
|
|
|
277 that i had earlier.
|
|
|
278
|
|
|
279 But, to summarize a bit, in our current case, however, the typestate we're
|
|
|
280 looking for is the contents of the heap. And when we try to model such
|
|
|
281 typestates (complex in this specific manner, i.e. heap-like) in any checker, we
|
|
|
282 have a choice between re-doing this modeling in every such checker (which is
|
|
|
283 something analyzer is indeed good at, but at a price of making checkers heavy)
|
|
|
284 or 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 outside
|
|
|
287 > the library". That is, does the library expose the region as a pointer that
|
|
|
288 > can be read to or written from in the client program? If so, then it makes
|
|
|
289 > sense for this to be in the store: we are modeling reachable storage as
|
|
|
290 > storage. But if we're just modeling arbitrary analysis facts that need to be
|
|
|
291 > invalidated when a pointer escapes then we shouldn't try to gin up storage
|
|
|
292 > for them just to get invalidation for free.
|
|
|
293
|
|
|
294 As a metaphor, i'd probably compare it to body farms - the difference between
|
|
|
295 ghost member variables and metadata symbols seems to me like the difference
|
|
|
296 between body farms and evalCall. Both are nice to have, and body farms are very
|
|
|
297 pleasant to work with, even if not omnipotent. I think it's fine for a
|
|
|
298 FunctionDecl's body in a body farm to have a local variable, even if such
|
|
|
299 variable doesn't actually exist, even if it cannot be seen from outside the
|
|
|
300 function call. I'm not seeing immediate practical difference between "it does
|
|
|
301 actually exist" and "it doesn't actually exist, just a handy abstraction".
|
|
|
302 Similarly, i think it's fine if we have a ``CXXRecordDecl`` with
|
|
|
303 implementation-defined contents, and try to farm up a member variable as a handy
|
|
|
304 abstraction (we don't even need to know its name or offset, only that it's there
|
|
|
305 somewhere).
|
|
|
306
|
|
|
307 **Artem:**
|
|
|
308
|
|
|
309 We've discussed it in person with Devin, and he provided more points to think
|
|
|
310 about:
|
|
|
311
|
|
|
312 * If the initializer list consists of non-POD data, constructors of list's
|
|
|
313 objects need to take the sub-region of the list's region as this-region In the
|
|
|
314 current (v2) version of this patch, these objects are constructed elsewhere and
|
|
|
315 then trivial-copied into the list's metadata pointer region, which may be
|
|
|
316 incorrect. This is our overall problem with C++ constructors, which manifests in
|
|
|
317 this case as well. Additionally, objects would need to be constructed in the
|
|
|
318 analyzer's core, which would not be able to predict that it needs to take a
|
|
|
319 checker-specific region as this-region, which makes it harder, though it might
|
|
|
320 be mitigated by sharing the checker state traits.
|
|
|
321
|
|
|
322 * Because "ghost variables" are not material to the user, we need to somehow
|
|
|
323 make super sure that they don't make it into the diagnostic messages.
|
|
|
324
|
|
|
325 So, because this needs further digging into overall C++ support and rises too
|
|
|
326 many questions, i'm delaying a better approach to this problem and will fall
|
|
|
327 back to the original trivial patch.
|
