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? > 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. Richard. > Thanks, > - Tom >
