[cfe-dev] 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
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev