[RFC] two-phase marking in gt_cleare_cache

[Richard Biener]

On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 06/07/15 15:29, Richard Biener wrote:
>>
>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>>
>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries <Tom_deVries@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
>