Proposed: change tracking for RegionStore

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Proposed: change tracking for RegionStore

Jordy Rose
In working with C string length tracking, I've found it's hard to track
all the cases when a region might change. One possibility would be to
allow
registering callbacks when /any/ store is made (possibly erasures as
well).
I wasn't so fond of that idea.

Instead, I went with an alternate idea: record a "change marker" in the
store for each region. Whenever a region changes, the marker is cleared, as
well as markers for all its super-regions.

The markers are stored under a new type of binding (BindingKey::Change),
(ab)using UndefinedVal's data slot to contain the marker. The actual value
of the marker is simply a pointer to the store just before the marker was
added.

The downside, of course, is that the marker-clearing happens with every
Add/Remove in the store, most of the time doing nothing. The super-region
hierarchy isn't /that/ deep, but it's still something to consider.

Comments? What needs to be done to make this committable?
RequestChangeMarker is particularly bad, but I'm not sure what the best way
around it is.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

change-markers.patch (8K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek
Hi Jordy,

I'm really concerned about the potential scalability cost this will impugn on RegionStore.  Adding change markers will cause the store to record information that is highly specific to a given path.  In this case, stores would retain memory of the previous store, which transforms them from being memoryless (aside from LazyCompoundVals) to retaining a bunch of extra state that is specific to a given path.  This can cause states not to merge when they are otherwise identical, which could possibly have huge algorithmic implications with how well the analyzer scales, as far fewer paths will get merged.

I think there is a higher-order API problem here as well.  The internal model that a StoreManager uses for managing memory bindings might not be the same as a Checker's view of memory.  Checkers reason about memory using MemoryRegions, but a store could model them using MemRegions+offsets, etc.  Checkers wishing to know about changes to memory would want to know about those changes in terms of how they reason about memory, not how the StoreManager reasons about them.

In your opinion, why is the callback idea not so hot?

On Jul 30, 2010, at 11:27 AM, Jordy Rose wrote:

> In working with C string length tracking, I've found it's hard to track
> all the cases when a region might change. One possibility would be to
> allow
> registering callbacks when /any/ store is made (possibly erasures as
> well).
> I wasn't so fond of that idea.
>
> Instead, I went with an alternate idea: record a "change marker" in the
> store for each region. Whenever a region changes, the marker is cleared, as
> well as markers for all its super-regions.
>
> The markers are stored under a new type of binding (BindingKey::Change),
> (ab)using UndefinedVal's data slot to contain the marker. The actual value
> of the marker is simply a pointer to the store just before the marker was
> added.
>
> The downside, of course, is that the marker-clearing happens with every
> Add/Remove in the store, most of the time doing nothing. The super-region
> hierarchy isn't /that/ deep, but it's still something to consider.
>
> Comments? What needs to be done to make this committable?
> RequestChangeMarker is particularly bad, but I'm not sure what the best way
> around it is.<change-markers.patch>_______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose

On Fri, 30 Jul 2010 11:43:51 -0700, Ted Kremenek <[hidden email]>
wrote:
> Hi Jordy,
>
> I'm really concerned about the potential scalability cost this will
impugn
> on RegionStore.  Adding change markers will cause the store to record
> information that is highly specific to a given path.  In this case,
stores
> would retain memory of the previous store, which transforms them from
being
> memoryless (aside from LazyCompoundVals) to retaining a bunch of extra
> state that is specific to a given path.  This can cause states not to
merge
> when they are otherwise identical, which could possibly have huge
> algorithmic implications with how well the analyzer scales, as far fewer
> paths will get merged.

This is true; I hadn't thought of that. Of course, it's only a problem
when the checkers request that information, but it could be a big deal for
a large function (or function net with IPA) dealing with lots of C strings.


> I think there is a higher-order API problem here as well.  The internal
> model that a StoreManager uses for managing memory bindings might not be
> the same as a Checker's view of memory.  Checkers reason about memory
using
> MemoryRegions, but a store could model them using MemRegions+offsets,
etc.
> Checkers wishing to know about changes to memory would want to know
about
> those changes in terms of how they reason about memory, not how the
> StoreManager reasons about them.

I don't think that's true. If I'm watching a[0][4] of an int[][], and it
get casted to an int[] and the fourth element changes, I still want to
know.


> In your opinion, why is the callback idea not so hot?

It's mainly an API problem as well. A StoreManager may do multiple Add()
or Remove() calls as part of a single action, and between those actions the
store isn't exactly in a reasonable state. For example, the old code for
initializing an array with a string would copy each element of the string
into the array. All that happens here is that change markers get
redundantly cleared, but with callbacks the observer might be able to see
the store with undefined values, or whatever.

(I haven't looked through RegionStore to see if that's actually true.)

Moving the callback up to Bind or Invalidate might work, but then the
stores would have to keep track of every region touched during the call --
annoying, but not impossible. This could still show up during a larger
operation, since the StoreManager doesn't know who's modifying the store.
(It could be part of modeling a function's behavior, for example.)

If we can work out the right API for that, I'd be happy to switch over.
First pass: any call that returns a new Store will call

void RegionWatcher::RegionChanged(Store NewStore, const MemRegion *MR)

for each region, and it's up to the RegionWatcher to traverse
superclasses. This would probably be using the logical view of regions
rather than the internal view, which I'm still not sure is better.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek

On Jul 30, 2010, at 12:56 PM, Jordy Rose wrote:

> It's mainly an API problem as well. A StoreManager may do multiple Add()
> or Remove() calls as part of a single action, and between those actions the
> store isn't exactly in a reasonable state. For example, the old code for
> initializing an array with a string would copy each element of the string
> into the array. All that happens here is that change markers get
> redundantly cleared, but with callbacks the observer might be able to see
> the store with undefined values, or whatever.
>
> (I haven't looked through RegionStore to see if that's actually true.)
>
> Moving the callback up to Bind or Invalidate might work,

This is the level I was thinking of.

> but then the
> stores would have to keep track of every region touched during the call --
> annoying, but not impossible.

Not necessarily.  Instead of tracking all regions that modified, we can have a registered list of subscribers (provides as input to Bind/Invalidate) that want to know when *specific* regions (and/or their subregions) have been touched.  If there are no subscribers, then we record nothing.  If there are subscribers, we only record information for regions that they have said they care about. Most subscribers will only care about regions for which they have checker-specific state, and that set should be small.

> This could still show up during a larger
> operation, since the StoreManager doesn't know who's modifying the store.
> (It could be part of modeling a function's behavior, for example.)

That is true, and we want individual subscribers (which are probably Checkers) to have the ability to interject new analysis state (either via new GRState objects or ExplodedNodes).  Not every call to Bind/Invalidate is structured to work that way, but it could probably be done.

One thing I like about this approach is that it could be a natural extension of the Checker callback interface.

> If we can work out the right API for that, I'd be happy to switch over.
> First pass: any call that returns a new Store will call
>
> void RegionWatcher::RegionChanged(Store NewStore, const MemRegion *MR)
>
> for each region, and it's up to the RegionWatcher to traverse
> superclasses.

Superclasses?

> This would probably be using the logical view of regions
> rather than the internal view, which I'm still not sure is better.


Subscribers/checkers need to be StoreManager agnostic, and in the common cases they will be reasoning (with checker-specific state) about SymbolicRegions and VarRegions (or other "base" regions).  We really don't want checkers to get into the business of directly reasoning about individual array elements, as that could implicitly require discretizing the representation of the contents of the array instead of reasoning about it symbolically.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose

On Fri, 30 Jul 2010 13:29:57 -0700, Ted Kremenek <[hidden email]>
wrote:
> On Jul 30, 2010, at 12:56 PM, Jordy Rose wrote:
>
>> It's mainly an API problem as well. A StoreManager may do multiple
Add()
>> or Remove() calls as part of a single action, and between those actions
>> the
>> store isn't exactly in a reasonable state. For example, the old code
for
>> initializing an array with a string would copy each element of the
string
>> into the array. All that happens here is that change markers get
>> redundantly cleared, but with callbacks the observer might be able to
see

>> the store with undefined values, or whatever.
>>
>> (I haven't looked through RegionStore to see if that's actually true.)
>>
>> Moving the callback up to Bind or Invalidate might work,
>
> This is the level I was thinking of.
>
>> but then the
>> stores would have to keep track of every region touched during the call
>> --
>> annoying, but not impossible.
>
> Not necessarily.  Instead of tracking all regions that modified, we can
> have a registered list of subscribers (provides as input to
> Bind/Invalidate) that want to know when *specific* regions (and/or their
> subregions) have been touched.  If there are no subscribers, then we
record
> nothing.  If there are subscribers, we only record information for
regions
> that they have said they care about. Most subscribers will only care
about
> regions for which they have checker-specific state, and that set should
be
> small.

That's true, but I meant we have to pass a list down from method to method
for any possible modifications. The simplest way would be to add all
regions to the list, but we could also pass a set of interesting regions
and have the methods mark the ones that are touched.

Would it be better to store a region<->listeners map or a listener set
that we then query for a list of regions? I'm leaning towards the former.


>> This could still show up during a larger
>> operation, since the StoreManager doesn't know who's modifying the
store.
>> (It could be part of modeling a function's behavior, for example.)
>
> That is true, and we want individual subscribers (which are probably
> Checkers) to have the ability to interject new analysis state (either
via
> new GRState objects or ExplodedNodes).  Not every call to
Bind/Invalidate
> is structured to work that way, but it could probably be done.
>
> One thing I like about this approach is that it could be a natural
> extension of the Checker callback interface.

If that's the case, what's the best way for checkers to register their
interest in a region? Do they register with the GRExprEngine, the
GRStateManager, or directly with the StoreManager?

And hm. How can we inject new analysis state at the level of Bind or
Invalidate, where only the Store is being changed? Not all store-modifying
code goes through GRState.


>> If we can work out the right API for that, I'd be happy to switch over.
>> First pass: any call that returns a new Store will call
>>
>> void RegionWatcher::RegionChanged(Store NewStore, const MemRegion *MR)
>>
>> for each region, and it's up to the RegionWatcher to traverse
>> superclasses.
>
> Superclasses?

Super-regions, sorry. If we're figuring out which observers to notify
within the store, however, it's going to have to be the store's
responsibility to check super-regions.


>> This would probably be using the logical view of regions
>> rather than the internal view, which I'm still not sure is better.
>
>
> Subscribers/checkers need to be StoreManager agnostic, and in the common
> cases they will be reasoning (with checker-specific state) about
> SymbolicRegions and VarRegions (or other "base" regions).  We really
don't
> want checkers to get into the business of directly reasoning about
> individual array elements, as that could implicitly require discretizing
> the representation of the contents of the array instead of reasoning
about
> it symbolically.

Good point, never mind.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek

On Jul 30, 2010, at 3:33 PM, Jordy Rose wrote:

>> One thing I like about this approach is that it could be a natural
>> extension of the Checker callback interface.
>
> If that's the case, what's the best way for checkers to register their
> interest in a region? Do they register with the GRExprEngine, the
> GRStateManager, or directly with the StoreManager?

Interest in a region is probably something that would go into GRState, but that "registration" of interest can be implicit.  For example, GRExprEngine could query the checkers for the set of "interesting" regions given a GRState*.  After all, a given checker probably knows what regions it cares about because it is already tracking checker-specific state for them.

>
> And hm. How can we inject new analysis state at the level of Bind or
> Invalidate, where only the Store is being changed? Not all store-modifying
> code goes through GRState.


I think Bind and Invalidate would still work as expected, but just return the list of regions that "subscribers" had said they cared about.

Bind and Invalidate, however, are only called at specific places (e.g., in GRExprEngine), and usually when one is reasoning about a GRState or ExplodedNode.  Does it seem plausible to try and do the callbacks after the Bind/Invalidate, possibly generating new ExplodedNodes?  For example, I can see this happening when evaluating a store within GRExprEngine.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose

On Fri, 30 Jul 2010 19:05:35 -0700, Ted Kremenek <[hidden email]>
wrote:
> On Jul 30, 2010, at 3:33 PM, Jordy Rose wrote:
>>
>> And hm. How can we inject new analysis state at the level of Bind or
>> Invalidate, where only the Store is being changed? Not all
>> store-modifying
>> code goes through GRState.
>
>
> I think Bind and Invalidate would still work as expected, but just
return
> the list of regions that "subscribers" had said they cared about.
>
> Bind and Invalidate, however, are only called at specific places (e.g.,
in
> GRExprEngine), and usually when one is reasoning about a GRState or
> ExplodedNode.  Does it seem plausible to try and do the callbacks after
the
> Bind/Invalidate, possibly generating new ExplodedNodes?  For example, I
can
> see this happening when evaluating a store within GRExprEngine.

I'm thinking of modeling functions, though. The only place where this is
used now is MallocChecker's fill value (admittedly, a patch from me, weeks
ago). But memset() is basically Invalidate-then-BindDefault.
OSAtomicChecker is using EvalStore, but it's not as clean as it should be.
There's no EvalFill or EvalInvalidate. Should there be?

I'm inclined to not allow new ExplodedNodes here, only a one-to-one filter
of GRStates. That is, you can change states when getting a region update,
but not bifurcate the state. This limits us to "places that call
GRState::makeWithStore", which are a manageable set. But still not at the
GRExprEngine level. I'm not thrilled with turning every bind* call into
this:

RegionSet RS = C.getEngine().GetInterestingRegions();
tie(state, RS) = state->bindLoc(L, V, RS);
C.getEngine().NoteRegionsChanged(state, RS);

Or this:

state = state->bindLoc(L, V, C.getEngine());

They both seem like they're mixing levels. But having to move these cover
methods for Bind* and friends (eight methods) up to the engine seems a
little silly. Maybe it shouldn't.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Zhongxing Xu
Are we trying to solve the problem that, some checkers want to be
informed when some region bindings are changed?

Can we do this:

GRExprEngine maintains a RegionWatcher, which is basically a map:
      MemRegion *  => list of Checkers who are interested in the MemRegion

Checkers first register themselves with the region they are interested
in to the RegionWatcher.

In StoreManager::bind and other necessary places, call
RegionWatcher::RegionChanged() with the new store and a list of
changed regions. RegionWatcher then inform each Checker that
registered before.

On Sat, Jul 31, 2010 at 1:42 PM, Jordy Rose <[hidden email]> wrote:

>
> On Fri, 30 Jul 2010 19:05:35 -0700, Ted Kremenek <[hidden email]>
> wrote:
>> On Jul 30, 2010, at 3:33 PM, Jordy Rose wrote:
>>>
>>> And hm. How can we inject new analysis state at the level of Bind or
>>> Invalidate, where only the Store is being changed? Not all
>>> store-modifying
>>> code goes through GRState.
>>
>>
>> I think Bind and Invalidate would still work as expected, but just
> return
>> the list of regions that "subscribers" had said they cared about.
>>
>> Bind and Invalidate, however, are only called at specific places (e.g.,
> in
>> GRExprEngine), and usually when one is reasoning about a GRState or
>> ExplodedNode.  Does it seem plausible to try and do the callbacks after
> the
>> Bind/Invalidate, possibly generating new ExplodedNodes?  For example, I
> can
>> see this happening when evaluating a store within GRExprEngine.
>
> I'm thinking of modeling functions, though. The only place where this is
> used now is MallocChecker's fill value (admittedly, a patch from me, weeks
> ago). But memset() is basically Invalidate-then-BindDefault.
> OSAtomicChecker is using EvalStore, but it's not as clean as it should be.
> There's no EvalFill or EvalInvalidate. Should there be?
>
> I'm inclined to not allow new ExplodedNodes here, only a one-to-one filter
> of GRStates. That is, you can change states when getting a region update,
> but not bifurcate the state. This limits us to "places that call
> GRState::makeWithStore", which are a manageable set. But still not at the
> GRExprEngine level. I'm not thrilled with turning every bind* call into
> this:
>
> RegionSet RS = C.getEngine().GetInterestingRegions();
> tie(state, RS) = state->bindLoc(L, V, RS);
> C.getEngine().NoteRegionsChanged(state, RS);
>
> Or this:
>
> state = state->bindLoc(L, V, C.getEngine());
>
> They both seem like they're mixing levels. But having to move these cover
> methods for Bind* and friends (eight methods) up to the engine seems a
> little silly. Maybe it shouldn't.
>

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose

On Sun, 1 Aug 2010 16:23:51 +0800, Zhongxing Xu <[hidden email]>
wrote:
> Are we trying to solve the problem that, some checkers want to be
> informed when some region bindings are changed?
>
> Can we do this:
>
> GRExprEngine maintains a RegionWatcher, which is basically a map:
>       MemRegion *  => list of Checkers who are interested in the
MemRegion
>
> Checkers first register themselves with the region they are interested
> in to the RegionWatcher.
>
> In StoreManager::bind and other necessary places, call
> RegionWatcher::RegionChanged() with the new store and a list of
> changed regions. RegionWatcher then inform each Checker that
> registered before.

That's a good idea. I'd be a little worried transferring from one
GRExprEngine to the next during far inline calls, but I guess that can wait
until there's more support for that. (Plenty of checkers, for example,
assume the ASTContext doesn't change between invocations.) And I assume
these callbacks would happen at the end of the StoreManager public
interface methods.

I'd actually still like to push this up to GRStateManager, since that
would allow checkers to mess with their GDM store as a side effect of a
region change (in the case of CStringChecker, to invalidate any recorded
strlen).
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Zhongxing Xu
On Mon, Aug 2, 2010 at 7:53 AM, Jordy Rose <[hidden email]> wrote:

>
> On Sun, 1 Aug 2010 16:23:51 +0800, Zhongxing Xu <[hidden email]>
> wrote:
>> Are we trying to solve the problem that, some checkers want to be
>> informed when some region bindings are changed?
>>
>> Can we do this:
>>
>> GRExprEngine maintains a RegionWatcher, which is basically a map:
>>       MemRegion *  => list of Checkers who are interested in the
> MemRegion
>>
>> Checkers first register themselves with the region they are interested
>> in to the RegionWatcher.
>>
>> In StoreManager::bind and other necessary places, call
>> RegionWatcher::RegionChanged() with the new store and a list of
>> changed regions. RegionWatcher then inform each Checker that
>> registered before.
>
> That's a good idea. I'd be a little worried transferring from one
> GRExprEngine to the next during far inline calls, but I guess that can wait
> until there's more support for that. (Plenty of checkers, for example,
> assume the ASTContext doesn't change between invocations.) And I assume
> these callbacks would happen at the end of the StoreManager public
> interface methods.

We should try to make more components ASTContext agnostic.

>
> I'd actually still like to push this up to GRStateManager, since that
> would allow checkers to mess with their GDM store as a side effect of a
> region change (in the case of CStringChecker, to invalidate any recorded
> strlen).
>
This makes sense.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek
In reply to this post by Zhongxing Xu
(Just catching up)

This is essentially what we are trying to do.  The problem is whether that map is done as a per-path property or something "global" to the instance of a Checker or GRExprEngine.  If it is per-path, the map has to go in GRState or something similar if that map isn't short-lived.  My suggestion before was that this map is essentially implicitly defined by the Checkers, since they are already tracking checker-specific state on the side.  In this case, representing this map separately in GRState seems a little silly to me, and potentially a performance concern when it comes to state caching.

On Aug 1, 2010, at 1:23 AM, Zhongxing Xu wrote:

> Are we trying to solve the problem that, some checkers want to be
> informed when some region bindings are changed?
>
> Can we do this:
>
> GRExprEngine maintains a RegionWatcher, which is basically a map:
>      MemRegion *  => list of Checkers who are interested in the MemRegion
>
> Checkers first register themselves with the region they are interested
> in to the RegionWatcher.
>
> In StoreManager::bind and other necessary places, call
> RegionWatcher::RegionChanged() with the new store and a list of
> changed regions. RegionWatcher then inform each Checker that
> registered before.
>
> On Sat, Jul 31, 2010 at 1:42 PM, Jordy Rose <[hidden email]> wrote:
>>
>> On Fri, 30 Jul 2010 19:05:35 -0700, Ted Kremenek <[hidden email]>
>> wrote:
>>> On Jul 30, 2010, at 3:33 PM, Jordy Rose wrote:
>>>>
>>>> And hm. How can we inject new analysis state at the level of Bind or
>>>> Invalidate, where only the Store is being changed? Not all
>>>> store-modifying
>>>> code goes through GRState.
>>>
>>>
>>> I think Bind and Invalidate would still work as expected, but just
>> return
>>> the list of regions that "subscribers" had said they cared about.
>>>
>>> Bind and Invalidate, however, are only called at specific places (e.g.,
>> in
>>> GRExprEngine), and usually when one is reasoning about a GRState or
>>> ExplodedNode.  Does it seem plausible to try and do the callbacks after
>> the
>>> Bind/Invalidate, possibly generating new ExplodedNodes?  For example, I
>> can
>>> see this happening when evaluating a store within GRExprEngine.
>>
>> I'm thinking of modeling functions, though. The only place where this is
>> used now is MallocChecker's fill value (admittedly, a patch from me, weeks
>> ago). But memset() is basically Invalidate-then-BindDefault.
>> OSAtomicChecker is using EvalStore, but it's not as clean as it should be.
>> There's no EvalFill or EvalInvalidate. Should there be?
>>
>> I'm inclined to not allow new ExplodedNodes here, only a one-to-one filter
>> of GRStates. That is, you can change states when getting a region update,
>> but not bifurcate the state. This limits us to "places that call
>> GRState::makeWithStore", which are a manageable set. But still not at the
>> GRExprEngine level. I'm not thrilled with turning every bind* call into
>> this:
>>
>> RegionSet RS = C.getEngine().GetInterestingRegions();
>> tie(state, RS) = state->bindLoc(L, V, RS);
>> C.getEngine().NoteRegionsChanged(state, RS);
>>
>> Or this:
>>
>> state = state->bindLoc(L, V, C.getEngine());
>>
>> They both seem like they're mixing levels. But having to move these cover
>> methods for Bind* and friends (eight methods) up to the engine seems a
>> little silly. Maybe it shouldn't.
>>


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek
In reply to this post by Jordy Rose

On Aug 1, 2010, at 4:53 PM, Jordy Rose wrote:

> That's a good idea. I'd be a little worried transferring from one
> GRExprEngine to the next during far inline calls, but I guess that can wait
> until there's more support for that. (Plenty of checkers, for example,
> assume the ASTContext doesn't change between invocations.) And I assume
> these callbacks would happen at the end of the StoreManager public
> interface methods.

Besides the ASTContext changing, we possibly will have different MemRegions as well.  We haven't worked those details out yet.

> I'd actually still like to push this up to GRStateManager, since that
> would allow checkers to mess with their GDM store as a side effect of a
> region change (in the case of CStringChecker, to invalidate any recorded
> strlen).

Yes, this makes sense.  Checkers don't get to manipulate stores directly, and GRState is the only place they can put new state.

The problem with just generating GRStates, as opposed to ExplodedNodes, is that it prevents Checkers from registering an error immediately when the memory "notification" takes place.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek
In reply to this post by Zhongxing Xu
On Aug 1, 2010, at 7:27 PM, Zhongxing Xu wrote:

>> That's a good idea. I'd be a little worried transferring from one
>> GRExprEngine to the next during far inline calls, but I guess that can wait
>> until there's more support for that. (Plenty of checkers, for example,
>> assume the ASTContext doesn't change between invocations.) And I assume
>> these callbacks would happen at the end of the StoreManager public
>> interface methods.
>
> We should try to make more components ASTContext agnostic.

Agreed.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose
In reply to this post by Ted Kremenek

On Mon, 2 Aug 2010 17:33:43 -0700, Ted Kremenek <[hidden email]>
wrote:
> This is essentially what we are trying to do.  The problem is whether
that
> map is done as a per-path property or something "global" to the instance
of
> a Checker or GRExprEngine.  If it is per-path, the map has to go in
GRState
> or something similar if that map isn't short-lived.  My suggestion
before
> was that this map is essentially implicitly defined by the Checkers,
since
> they are already tracking checker-specific state on the side.  In this
> case, representing this map separately in GRState seems a little silly
to
> me, and potentially a performance concern when it comes to state
caching.

Tracking the map in GRState is probably worse than change markers when it
comes to merging state, so I agree that a path-sensitive map wouldn't buy
us much. The difference between having an explicit map and an implicit one
is really just a time/memory/simplicity tradeoff.

These are the options I see:

Explicit map :
- One place to deal with super-regions.
- No virtual calls except for the checkers who actually said they were
interested.
- Backing (proposed): DenseMap<const MemRegion *, vector<Checker *>>

"Interest poll":
- Before each modification, ask checkers if they're interested in the
change.
- After the modification, notify all checkers that said they were
interested.
- If we wanted, this would let us ask checkers about certain /kinds/ of
changes.
- Downside: (up to) twice as many calls.

ProcessRegionChange:
- Like ProcessAssume, does no filtering of checkers. Takes a GRState and
the location that changed (SVal or MemRegion?), returns a new GRState.
- Not too hard to add the same sort of respondsToCallback checking as for
Visit*Stmt, meaning we'd at least only get checkers that /can/ track region
changes.
- Downside: not context-sensitive at all.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek
On Aug 2, 2010, at 6:36 PM, Jordy Rose wrote:

> ProcessRegionChange:
> - Like ProcessAssume, does no filtering of checkers. Takes a GRState and
> the location that changed (SVal or MemRegion?), returns a new GRState.
> - Not too hard to add the same sort of respondsToCallback checking as for
> Visit*Stmt, meaning we'd at least only get checkers that /can/ track region
> changes.

Yup.  It's all very simple too.

> - Downside: not context-sensitive at all.

It's only not context-sensitive from the perspective of when to do the callbacks to the checkers, but ultimately the checkers know what data they care about when they operate on a given GRState.  Since the amount of "interested" regions will likely be small, this is probably not an issue.

I think this is the simplest and cleanest approach we have on the table.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose
OK, here's a first pass at ProcessRegionChange.

The first note is that I didn't choose to call it for every change to the
store.

Included: bindLoc, bindDefault, InvalidateRegions
Excluded: bindCompoundLiteral, bindDecl, bindDeclWithNoInit, unbindLoc,
EnterStackFrame

The reason for this is that the excluded calls only /add/ regions to the
store; they do not change existing bindings. It follows that a checker
cannot already be tracking a region that has not existed until this point.
(Arguably, bindDefault should be here too, since it's currently only used
for new regions.) unbindLoc is a special case since it's not used for
regions at all.

The second note is that it requires a ridiculous cross-indexing sort of
search to be useful: if I'm tracking the strlen of region X, that length is
invalid if any of X's subregions /or/ super-regions change. This results in
the code seen in the attached txt snippet. Is there a better way to set
this up that would make this neater?

Finally, the bind* covers in GRState are getting a little bulky for inline
functions. At what point would we give up on the efficiency gain and move
them to GRState.cpp?
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

ProcessRegionChanges.patch (12K) Download Attachment
EvalRegionChanges.txt (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek

On Aug 4, 2010, at 11:01 PM, Jordy Rose wrote:

> OK, here's a first pass at ProcessRegionChange.
>
> The first note is that I didn't choose to call it for every change to the
> store.
>
> Included: bindLoc, bindDefault, InvalidateRegions

Note that InvalidateRegions touches a lot more than the regions specified.  It computes a transitive closure, including looking at regions whose addresses are bound to other regions.  Should those be included in the callback?

> Excluded: bindCompoundLiteral, bindDecl, bindDeclWithNoInit, unbindLoc,
> EnterStackFrame
>
> The reason for this is that the excluded calls only /add/ regions to the
> store; they do not change existing bindings. It follows that a checker
> cannot already be tracking a region that has not existed until this point.
> (Arguably, bindDefault should be here too, since it's currently only used
> for new regions.) unbindLoc is a special case since it's not used for
> regions at all.

Makes lots of sense.

>
> The second note is that it requires a ridiculous cross-indexing sort of
> search to be useful: if I'm tracking the strlen of region X, that length is
> invalid if any of X's subregions /or/ super-regions change. This results in
> the code seen in the attached txt snippet. Is there a better way to set
> this up that would make this neater?

This looks very similar to the region "cluster" analysis done in RegionStore that is used for InvalidateRegions and RemoveDeadBindings.  When I changed RegionStore to use the cluster analysis it wiped out a ton of old code.  We could expose that algorithm/API at a higher level, and possibly eliminate most of the boilerplate in your code.  Exposing APIs to do this kind of cross-indexing gives us the opportunity to do clever optimizations later that benefits all clients.

One nit: In your code, it's probably good to check that EntryMap is non-empty before building this index (which could be expensive).

>
> Finally, the bind* covers in GRState are getting a little bulky for inline
> functions. At what point would we give up on the efficiency gain and move
> them to GRState.cpp?

Agreed.  I think all of these should be moved out-of-line at this point.  We should keep GRState.h defining a clean, readable interface.  These methods aren't hotspots anyway, so keeping them inline buys us nothing.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose
Second pass. This mainly addresses the fact that InvalidateRegions doesn't
just invalidate the regions it's given -- thanks, Ted -- by recording all
the touched regions in a SmallVector.

I looked at what it would take to re-use the cluster analysis code. Right
now ClusterAnalysis is pretty tightly tied to RegionStore (it maps regions
to BindingKeys). Even if the region-walking part could be extricated,
though, it's really not the same as what the checker needs (which is
basically IsSubOrSuperRegion(MemRegion*, MemRegion*)). I guess it's okay to
leave for now.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

ProcessRegionChanges.patch (27K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Ted Kremenek

On Aug 7, 2010, at 6:42 PM, Jordy Rose wrote:

> Second pass. This mainly addresses the fact that InvalidateRegions doesn't
> just invalidate the regions it's given -- thanks, Ted -- by recording all
> the touched regions in a SmallVector.

Thanks Jordy.  I'm still really leery about the cost of this, but I'm willing to see how CStringChecker makes use of the information so we can see how we can possibly do this better.  Recording the entire set of invalidated regions seems really expensive.  Comments inline:

Index: include/clang/Checker/PathSensitive/Store.h
===================================================================
--- include/clang/Checker/PathSensitive/Store.h (revision 110519)
+++ include/clang/Checker/PathSensitive/Store.h (working copy)
@@ -159,13 +159,15 @@
   virtual Store BindDeclWithNoInit(Store store, const VarRegion *VR) = 0;
 
   typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
+  typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions;
 
   virtual Store InvalidateRegions(Store store,
                                   const MemRegion * const *Begin,
                                   const MemRegion * const *End,
                                   const Expr *E, unsigned Count,
                                   InvalidatedSymbols *IS,
-                                  bool invalidateGlobals) = 0;
+                                  bool invalidateGlobals,
+                                  InvalidatedRegions &Regions) = 0;


Does it make sense to pass in a pointer instead of a reference?  The problem with passing in a reference is that it means we always have to do the work of recording the invalidated MemRegions.


 
   /// EnterStackFrame - Let the StoreManager to do something when execution
   /// engine is about to execute into a callee.
Index: include/clang/Checker/PathSensitive/GRExprEngine.h
===================================================================
--- include/clang/Checker/PathSensitive/GRExprEngine.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRExprEngine.h (working copy)
@@ -78,7 +78,8 @@
   enum CallbackKind {
     PreVisitStmtCallback,
     PostVisitStmtCallback,
-    ProcessAssumeCallback
+    ProcessAssumeCallback,
+    EvalRegionChangesCallback
   };
 
   typedef uint32_t CallbackTag;
@@ -228,6 +229,12 @@
   ///  making assumptions about state values.
   const GRState *ProcessAssume(const GRState *state, SVal cond,bool assumption);
 
+  /// ProcessRegionChanges - Called by GRStateManager whenever a change is made
+  ///  to the store. Used to update checkers that track region values.
+  const GRState* ProcessRegionChanges(const GRState *state,
+                                      const MemRegion * const *Begin,
+                                      const MemRegion * const *End);
+

Looks good.



   virtual GRStateManager& getStateManager() { return StateMgr; }
 
   StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
Index: include/clang/Checker/PathSensitive/Checker.h
===================================================================
--- include/clang/Checker/PathSensitive/Checker.h (revision 110519)
+++ include/clang/Checker/PathSensitive/Checker.h (working copy)
@@ -284,6 +284,14 @@
     return state;
   }
 
+  virtual const GRState *EvalRegionChanges(const GRState *state,
+                                           const MemRegion * const *Begin,
+                                           const MemRegion * const *End,
+                                           bool *respondsToCallback) {
+    *respondsToCallback = false;
+    return state;
+  }
+


Looks good, although we should probably just move this out-of-line at this point.


   virtual void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B,
                                 GRExprEngine &Eng) {}
 };
Index: include/clang/Checker/PathSensitive/GRSubEngine.h
===================================================================
--- include/clang/Checker/PathSensitive/GRSubEngine.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRSubEngine.h (working copy)
@@ -17,7 +17,7 @@
 
 namespace clang {
 
-class Stmt;
+class AnalysisManager;
 class CFGBlock;
 class CFGElement;
 class ExplodedNode;
@@ -32,6 +32,8 @@
 class GRCallEnterNodeBuilder;
 class GRCallExitNodeBuilder;
 class LocationContext;
+class MemRegion;
+class Stmt;
 
 class GRSubEngine {
 public:
@@ -75,12 +77,23 @@
 
   // Generate the first post callsite node.
   virtual void ProcessCallExit(GRCallExitNodeBuilder &builder) = 0;
-  
+
   /// Called by ConstraintManager. Used to call checker-specific
   /// logic for handling assumptions on symbolic values.
   virtual const GRState* ProcessAssume(const GRState *state,
                                        SVal cond, bool assumption) = 0;
-  
+
+  /// ProcessRegionChanges - Called by GRStateManager whenever a change is made
+  ///  to the store. Used to update checkers that track region values.
+  virtual const GRState* ProcessRegionChanges(const GRState* state,
+                                              const MemRegion* const *Begin,
+                                              const MemRegion* const *End) = 0;
+
+  inline const GRState* ProcessRegionChange(const GRState* state,
+                                            const MemRegion* MR) {
+    return ProcessRegionChanges(state, &MR, &MR+1);
+  }
+
   /// Called by GRCoreEngine when the analysis worklist is either empty or the
   //  maximum number of analysis steps have been reached.
   virtual void ProcessEndWorklist(bool hasWorkRemaining) = 0;
Index: include/clang/Checker/PathSensitive/GRState.h
===================================================================
--- include/clang/Checker/PathSensitive/GRState.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRState.h (working copy)
@@ -16,6 +16,7 @@
 
 #include "clang/Checker/PathSensitive/ConstraintManager.h"
 #include "clang/Checker/PathSensitive/Environment.h"
+#include "clang/Checker/PathSensitive/GRSubEngine.h"
 #include "clang/Checker/PathSensitive/Store.h"
 #include "clang/Checker/PathSensitive/ValueManager.h"
 #include "llvm/ADT/FoldingSet.h"
@@ -397,6 +398,9 @@
   friend class GRState;
   friend class GRExprEngine; // FIXME: Remove.
 private:
+  /// Eng - The GRSubEngine that owns this state manager.
+  GRSubEngine &Eng;
+
   EnvironmentManager                   EnvMgr;
   llvm::OwningPtr<StoreManager>        StoreMgr;
   llvm::OwningPtr<ConstraintManager>   ConstraintMgr;
@@ -426,7 +430,8 @@
                  ConstraintManagerCreator CreateConstraintManager,
                  llvm::BumpPtrAllocator& alloc,
                  GRSubEngine &subeng)
-    : EnvMgr(alloc),
+    : Eng(subeng),
+      EnvMgr(alloc),
       GDMFactory(alloc),
       ValueMgr(alloc, Ctx, *this),
       Alloc(alloc) {
@@ -469,6 +474,7 @@
 
   StoreManager& getStoreManager() { return *StoreMgr; }
   ConstraintManager& getConstraintManager() { return *ConstraintMgr; }
+  GRSubEngine& getOwningEngine() { return Eng; }
 
   const GRState* RemoveDeadBindings(const GRState* St,
                                     const StackFrameContext *LCtx,
@@ -618,58 +624,10 @@
                            cast<DefinedSVal>(UpperBound), Assumption);
 }
 
-inline const GRState *
-GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL,
-                             const LocationContext *LC, SVal V) const {
-  Store new_store =
-    getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V);
-  return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindDecl(const VarRegion* VR, SVal IVal) const {
-  Store new_store = getStateManager().StoreMgr->BindDecl(St, VR, IVal);
-  return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const {
-  Store new_store = getStateManager().StoreMgr->BindDeclWithNoInit(St, VR);
-  return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindLoc(Loc LV, SVal V) const {
-  Store new_store = getStateManager().StoreMgr->Bind(St, LV, V);
-  return makeWithStore(new_store);
-}
-
 inline const GRState *GRState::bindLoc(SVal LV, SVal V) const {
   return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V);
 }


When moving these methods out-of-line, please commit that change in another patch.  It separates out the functional change being done by your patch from the "cosmetic" one by moving these methods out-of-line.  Keeping it all together makes this patch a little harder to follow.


 
-inline const GRState *GRState::bindDefault(SVal loc, SVal V) const {
-  const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion();
-  Store new_store = getStateManager().StoreMgr->BindDefault(St, R, V);
-  return makeWithStore(new_store);
-}
-
-inline const GRState *
-GRState::InvalidateRegions(const MemRegion * const *Begin,
-                           const MemRegion * const *End,
-                           const Expr *E, unsigned Count,
-                           StoreManager::InvalidatedSymbols *IS,
-                           bool invalidateGlobals) const {
-  Store new_store
-    = getStateManager().StoreMgr->InvalidateRegions(St, Begin, End,
-                                                    E, Count, IS,
-                                                    invalidateGlobals);
-  return makeWithStore(new_store);
-}
-
-inline const GRState *
-GRState::EnterStackFrame(const StackFrameContext *frame) const {
-  Store new_store = getStateManager().StoreMgr->EnterStackFrame(this, frame);
-  return makeWithStore(new_store);
-}
-
 inline Loc GRState::getLValue(const VarDecl* VD,
                                const LocationContext *LC) const {
   return getStateManager().StoreMgr->getLValueVar(VD, LC);
Index: lib/Checker/FlatStore.cpp
===================================================================
--- lib/Checker/FlatStore.cpp (revision 110519)
+++ lib/Checker/FlatStore.cpp (working copy)
@@ -60,7 +60,7 @@
   Store InvalidateRegions(Store store, const MemRegion * const *I,
                           const MemRegion * const *E, const Expr *Ex,
                           unsigned Count, InvalidatedSymbols *IS,
-                          bool invalidateGlobals);
+                          bool invalidateGlobals, InvalidatedRegions &Regions);
 
   void print(Store store, llvm::raw_ostream& Out, const char* nl,
              const char *sep);
@@ -155,11 +155,12 @@
 }
 
 Store FlatStoreManager::InvalidateRegions(Store store,
-                                            const MemRegion * const *I,
-                                            const MemRegion * const *E,
-                                            const Expr *Ex, unsigned Count,
-                                            InvalidatedSymbols *IS,
-                                            bool invalidateGlobals) {
+                                          const MemRegion * const *I,
+                                          const MemRegion * const *E,
+                                          const Expr *Ex, unsigned Count,
+                                          InvalidatedSymbols *IS,
+                                          bool invalidateGlobals,
+                                          InvalidatedRegions &Regions) {
   assert(false && "Not implemented");
   return store;
 }
Index: lib/Checker/GRState.cpp
===================================================================
--- lib/Checker/GRState.cpp (revision 110519)
+++ lib/Checker/GRState.cpp (working copy)
@@ -68,6 +68,29 @@
   return getPersistentState(State);
 }
 
+const GRState * GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL,
+                                             const LocationContext *LC,
+                                             SVal V) const {
+  Store new_store =
+    getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V);
+  return makeWithStore(new_store);
+}
+
+const GRState *GRState::bindDecl(const VarRegion* VR, SVal IVal) const {
+  Store new_store = getStateManager().StoreMgr->BindDecl(St, VR, IVal);
+  return makeWithStore(new_store);
+}
+
+const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const {
+  Store new_store = getStateManager().StoreMgr->BindDeclWithNoInit(St, VR);
+  return makeWithStore(new_store);
+}
+
+const GRState *GRState::EnterStackFrame(const StackFrameContext *frame) const {
+  Store new_store = getStateManager().StoreMgr->EnterStackFrame(this, frame);
+  return makeWithStore(new_store);
+}
+
 const GRState *GRState::unbindLoc(Loc LV) const {
   assert(!isa<loc::MemRegionVal>(LV) && "Use InvalidateRegion instead.");
 
@@ -80,6 +103,46 @@
   return makeWithStore(NewStore);
 }
 
+const GRState *GRState::bindLoc(Loc LV, SVal V) const {
+  GRStateManager &Mgr = getStateManager();
+  Store new_store = Mgr.StoreMgr->Bind(St, LV, V);
+  const GRState *new_state = makeWithStore(new_store);
+
+  const MemRegion *MR = LV.getAsRegion();
+  if (MR)
+    return Mgr.getOwningEngine().ProcessRegionChange(new_state, MR);
+
+  return new_state;
+}
+
+const GRState *GRState::bindDefault(SVal loc, SVal V) const {
+  GRStateManager &Mgr = getStateManager();
+  const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion();
+  Store new_store = Mgr.StoreMgr->BindDefault(St, R, V);
+  const GRState *new_state = makeWithStore(new_store);
+  return Mgr.getOwningEngine().ProcessRegionChange(new_state, R);
+}
+
+const GRState *GRState::InvalidateRegions(const MemRegion * const *Begin,
+                                          const MemRegion * const *End,
+                                          const Expr *E, unsigned Count,
+                                          StoreManager::InvalidatedSymbols *IS,
+                                          bool invalidateGlobals) const {
+  StoreManager::InvalidatedRegions Regions;
+
+  GRStateManager &Mgr = getStateManager();
+  Store new_store = Mgr.StoreMgr->InvalidateRegions(St, Begin, End,
+                                                    E, Count, IS,
+                                                    invalidateGlobals,
+                                                    Regions);
+  const GRState *new_state = makeWithStore(new_store);
+
+  GRSubEngine &Eng = Mgr.getOwningEngine();
+  return Eng.ProcessRegionChanges(new_state,
+                                  &Regions.front(),
+                                  &Regions.back()+1);
+}
+
 SVal GRState::getSValAsScalarOrLoc(const MemRegion *R) const {
   // We only want to do fetches from regions that we can actually bind
   // values.  For example, SymbolicRegions of type 'id<...>' cannot
Index: lib/Checker/BasicStore.cpp
===================================================================
--- lib/Checker/BasicStore.cpp (revision 110519)
+++ lib/Checker/BasicStore.cpp (working copy)
@@ -52,7 +52,7 @@
   Store InvalidateRegions(Store store, const MemRegion * const *Begin,
                           const MemRegion * const *End, const Expr *E,
                           unsigned Count, InvalidatedSymbols *IS,
-                          bool invalidateGlobals);
+                          bool invalidateGlobals, InvalidatedRegions &Regions);
 
   Store scanForIvars(Stmt *B, const Decl* SelfDecl,
                      const MemRegion *SelfRegion, Store St);
@@ -521,11 +521,12 @@
 
 
 Store BasicStoreManager::InvalidateRegions(Store store,
-                                      const MemRegion * const *I,
-                                      const MemRegion * const *End,
-                                      const Expr *E, unsigned Count,
-                                      InvalidatedSymbols *IS,
-                                      bool invalidateGlobals) {
+                                           const MemRegion * const *I,
+                                           const MemRegion * const *End,
+                                           const Expr *E, unsigned Count,
+                                           InvalidatedSymbols *IS,
+                                           bool invalidateGlobals,
+                                           InvalidatedRegions &Regions) {
   if (invalidateGlobals) {
     BindingsTy B = GetBindings(store);
     for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
@@ -543,6 +544,7 @@
         continue;
     }
     store = InvalidateRegion(store, *I, E, Count, IS);
+    Regions.push_back(R);
   }


Note that if 'Regions' was a pointer instead of a reference, we could conditionally do this work instead of always paying the cost.


 
   // FIXME: This is copy-and-paste from RegionStore.cpp.
@@ -556,6 +558,7 @@
                                   Count);
 
     store = Bind(store, loc::MemRegionVal(GS), V);
+    Regions.push_back(GS);
   }


Same comment.

 
   return store;
Index: lib/Checker/RegionStore.cpp
===================================================================
--- lib/Checker/RegionStore.cpp (revision 110519)
+++ lib/Checker/RegionStore.cpp (working copy)
@@ -231,7 +231,8 @@
                           const MemRegion * const *End,
                           const Expr *E, unsigned Count,
                           InvalidatedSymbols *IS,
-                          bool invalidateGlobals);
+                          bool invalidateGlobals,
+                          InvalidatedRegions &Regions);
 
 public:   // Made public for helper classes.
 
@@ -572,14 +573,16 @@
   const Expr *Ex;
   unsigned Count;
   StoreManager::InvalidatedSymbols *IS;
+  StoreManager::InvalidatedRegions &Regions;
 public:
   InvalidateRegionsWorker(RegionStoreManager &rm,
                           GRStateManager &stateMgr,
                           RegionBindings b,
                           const Expr *ex, unsigned count,
-                          StoreManager::InvalidatedSymbols *is)
+                          StoreManager::InvalidatedSymbols *is,
+                          StoreManager::InvalidatedRegions &r)
     : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b),
-      Ex(ex), Count(count), IS(is) {}
+      Ex(ex), Count(count), IS(is), Regions(r) {}
 
   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
   void VisitBaseRegion(const MemRegion *baseR);
@@ -650,6 +653,9 @@
     return;
   }
 
+  // Otherwise, we have a normal data region. Record that we touched the region.
+  Regions.push_back(baseR);
+
   if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
     // Invalidate the region by setting its default value to
     // conjured symbol. The type of the symbol is irrelavant.
@@ -700,10 +706,11 @@
                                             const MemRegion * const *E,
                                             const Expr *Ex, unsigned Count,
                                             InvalidatedSymbols *IS,
-                                            bool invalidateGlobals) {
+                                            bool invalidateGlobals,
+                                            InvalidatedRegions &Regions) {
   InvalidateRegionsWorker W(*this, StateMgr,
                             RegionStoreManager::GetRegionBindings(store),
-                            Ex, Count, IS);
+                            Ex, Count, IS, Regions);
 
   // Scan the bindings and generate the clusters.
   W.GenerateClusters(invalidateGlobals);
@@ -726,6 +733,10 @@
                                   /* symbol type, doesn't matter */ Ctx.IntTy,
                                   Count);
     B = Add(B, BindingKey::Make(GS, BindingKey::Default), V);
+
+    // Even if there are no bindings in the global scope, we still need to
+    // record that we touched it.
+    Regions.push_back(GS);
   }
 

Same comment.  Make 'Region's a pointer that can be null.


   return B.getRoot();
Index: lib/Checker/GRExprEngine.cpp
===================================================================
--- lib/Checker/GRExprEngine.cpp (revision 110519)
+++ lib/Checker/GRExprEngine.cpp (working copy)
@@ -558,6 +558,59 @@
   return TF->EvalAssume(state, cond, assumption);
 }
 
+const GRState *
+GRExprEngine::ProcessRegionChanges(const GRState *state,
+                                   const MemRegion * const *Begin,
+                                   const MemRegion * const *End) {
+  // Determine if we already have a cached 'CheckersOrdered' vector
+  // specifically tailored for processing assumptions.  This
+  // can reduce the number of checkers actually called.
+  CheckersOrdered *CO = &Checkers;
+  llvm::OwningPtr<CheckersOrdered> NewCO;
+
+  CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
+  CheckersOrdered *& CO_Ref = COCache[K];
+
+  if (!CO_Ref) {
+    // If we have no previously cached CheckersOrdered vector for this
+    // statement kind, then create one.
+    NewCO.reset(new CheckersOrdered);
+  }
+  else {
+    // Use the already cached set.
+    CO = CO_Ref;
+  }
+
+  // If there are no checkers, just return the state as is.
+  if (CO->empty())
+    return state;
+
+  for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
+        I != E; ++I) {
+
+    // If any checker declares the state infeasible (or if it starts that way),
+    // bail out.
+    if (!state)
+      return NULL;
+
+    Checker *C = I->second;
+    bool respondsToCallback = true;
+
+    state = C->EvalRegionChanges(state, Begin, End, &respondsToCallback);
+
+    // See if we're building a cache of checkers that care about region changes.
+    if (NewCO.get() && respondsToCallback)
+      NewCO->push_back(*I);
+  }
+
+  // If we got through all the checkers, and we built a list of those that
+  // care about region changes, save it.
+  if (NewCO.get())
+    CO_Ref = NewCO.take();
+
+  return state;
+}
+


This is more copy-paste.  We should be able to refactor this (in a later patch).


 void GRExprEngine::ProcessEndWorklist(bool hasWorkRemaining) {
   for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
        I != E; ++I) {


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Proposed: change tracking for RegionStore

Jordy Rose
On Mon, 9 Aug 2010 13:45:50 -0700, Ted Kremenek <[hidden email]>
wrote:
> On Aug 7, 2010, at 6:42 PM, Jordy Rose wrote:
>
>> Second pass. This mainly addresses the fact that InvalidateRegions
>> doesn't
>> just invalidate the regions it's given -- thanks, Ted -- by recording
all
>> the touched regions in a SmallVector.
>
> Thanks Jordy.  I'm still really leery about the cost of this, but I'm
> willing to see how CStringChecker makes use of the information so we can
> see how we can possibly do this better.  Recording the entire set of
> invalidated regions seems really expensive.

I know. Probably in most cases, the set won't be very big, but any work to
pare out regions (such as only storing base regions) seems like it'd be
more expensive, and also prone to miss cases where a region without a store
binding is invalidated. (This should still make it back to checkers.)

I've attached my local version of CStringChecker, so you can see how I'm
using all of this. Much of it is very simple usage and can probably be
cleaned up to be more efficient.

As for this:

>    virtual Store InvalidateRegions(Store store,
>                                    const MemRegion * const *Begin,
>                                    const MemRegion * const *End,
>                                    const Expr *E, unsigned Count,
>                                    InvalidatedSymbols *IS,
> -                                  bool invalidateGlobals) = 0;
> +                                  bool invalidateGlobals,
> +                                  InvalidatedRegions &Regions) = 0;
>
>
> Does it make sense to pass in a pointer instead of a reference?  The
> problem with passing in a reference is that it means we always have to
do
> the work of recording the invalidated MemRegions.

Right. I was uneasy about this, but I think it actually ought to stay.
Why? Any region invalidation should be picked up by the checkers
eventually, or we have a correctness problem. (It's /because/ invalidating
a set of regions might touch other regions that this is necessary -- even
an internal use has no guarantee of a controlled invalidation.)

If you think it's necessary, I'll change it, but I think it may actually
be needed now.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

CStringChecker.cpp (40K) Download Attachment
12