On Tue, Jul 7, 2015 at 11:39 AM, Tom de Vries <tom_devr...@mentor.com> wrote: > On 07/07/15 10:42, Richard Biener wrote: >> >> On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries <tom_devr...@mentor.com> >> wrote: >>> >>> On 06/07/15 15:29, Richard Biener wrote: >>>> >>>> >>>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener >>>> <richard.guent...@gmail.com> wrote: >>>>> >>>>> >>>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <tom_devr...@mentor.com> >>>>> wrote: >>>>>> >>>>>> >>>>>> Hi, >>>>>> >>>>>> Using attached untested patch, I managed to minimize a test-case >>>>>> failure >>>>>> for >>>>>> PR 66714. >>>>>> >>>>>> The patch introduces two-phase marking in gt_cleare_cache: >>>>>> - first phase, it loops over all the hash table entries and removes >>>>>> those which are dead >>>>>> - second phase, it runs over all the live hash table entries and marks >>>>>> live items that are reachable from those live entries >>>>>> >>>>>> By doing so, we make the behaviour of gt_cleare_cache independent of >>>>>> the >>>>>> order in which the entries are visited, turning: >>>>>> - hard-to-trigger bugs which trigger for one visiting order but not >>>>>> for >>>>>> another, into >>>>>> - more easily triggered bugs which trigger for any visiting order. >>>>>> >>>>>> Any comments? >>>>> >>>>> >>>>> >>>>> I think it is only half-way correct in your proposed change. You only >>>>> fix the issue for hashes of the same kind. To truly fix the issue >>>>> you'd >>>>> have to change generated code for gt_clear_caches () and provide >>>>> a clearing-only implementation (or pass a operation mode bool to >>>>> the core worker in hash-table.h). >>>> >>>> >>>> >>> >>> [ Btw, we have been discussing a similar issue before: >>> https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ] >>> >>> True, the problem exists at the scope of all variables marked with >>> 'cache', >>> and this patch addresses the problem only within a single variable. >>> >>>> Hmm, and don't we rather want to first mark and _then_ clear? >>> >>> >>> >>> I. In favor of first clear and then mark: >>> >>> It allows for: >>> - a lazy one phase implementation for !ENABLE_CHECKING where >>> you do a single clear-or-mark phase (so the clear is lazy). >>> - an eager two phase implementation for ENABLE_CHECKING (where the >>> clear is eager) >>> The approach of first a marking phase and then a clearing phase means you >>> always have to do these two phases (you can't do the marking lazily). >> >> >> True. >> >>> First mark and then clear means the marking should be done iteratively. >>> Each >>> time you mark something live, another entry in another hash table could >>> become live. Marking iteratively could become quite costly. >> >> >> I don't see this - marking is done recursively so if one entry makes >> another >> live and that makes another live the usual GC marking recursion will deal >> with this? >> > > That is not my understanding. Marking an item live doesn't mean that the > associated cache entries become live. For that, we have to iterate again > over all hash tables and all entries to find those entries. > And by marking those, we may find new items which are live. And the process > starts over again, until fixed point.
All "used" predicates are basically ggc_marked_p () AFAIK. So when sth was not marked previosuly GC will recurse to marking it. GC only considers the reference from the cache special not references from entries in the cache. But maybe I am missing something here. > [ If we maintain a per-item list of cache entries the item is the key for, > then we can do this recursively, rather than iteratively. > >>> II. In favor of first mark and then clear: >>> >>> The users of garbage collection will need to be less precise. >>> >>>> Because >>>> if entry B in the hash is live and would keep A live then A _is_ kept in >>>> the >>>> end but you'll remove it from the hash, possibly no longer using a still >>>> live copy. >>>> >>> >>> I'm not sure I understand the scenario you're concerned about, but ... >>> say >>> we have >>> - entry B: item B -> item A >>> - entry A: item A -> item Z >>> >>> If you do clear first and mark second, and you start out with item B live >>> and item A dead: >>> - during the clearing phase you clear entry A and keep entry B, and >>> - during the marking phase you mark item A live. >>> >>> So we no longer have entry A, but item A is kept and entry B is kept. >> >> >> Yes. This makes the cache weaker in that after this GC operation >> a lookup of A no longer succeeds but it still is there. >> >> The whole point of your patch was to make the behavior more predictable >> and in some way it succeeds (within a cache). As it is supposed to >> put more stress on the cache logic (it's ENABLE_CHECKING only) >> it makes sense to clear optimistically (after all it's a cache and not >> guaranteed to find a still live entry). It would be still nice to cover >> all caches together because as I remember we've mostly seen issues >> of caches interacting. >> > > Attached patch (completed no-bootstrap c-only build) implements that. Looks good to me. Thanks, Richard. > Thanks, > - Tom >
