Re: [RFC] two-phase marking in gt_cleare_cache

[Tom de Vries <Tom_deVries at mentor dot com>]

On 07/07/15 10:42, Richard Biener wrote:
> 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?

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.

[ 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.

Thanks,
- Tom

Add clear-phase/mark-phase cache clearing

2015-07-07  Tom de Vries  <tom@codesourcery.com>

	* gengtype.c (finish_cache_funcs): Add phase param to
	gt_clear_caches_<file> and gt_clear_caches.
	(write_roots): Add phase param to gt_clear_caches_<file>, and use.
	* ggc-common.c (ggc_mark_roots): Add arg to call to gt_clear_caches.
	Call gt_clear_caches twice for ENABLE_CHECKING.
	* ggc.h (gt_clear_caches): Add phase param to declaration.
	* hash-table.h (gt_cleare_cache): Add and handle phase param.
---
 gcc/gengtype.c   | 11 ++++++-----
 gcc/ggc-common.c | 11 ++++++++++-
 gcc/ggc.h        |  2 +-
 gcc/hash-table.h | 55 ++++++++++++++++++++++++++++++++++++++++++++-----------
 4 files changed, 61 insertions(+), 18 deletions(-)

diff --git a/gcc/gengtype.c b/gcc/gengtype.c
index 137e0ff..e138fd8 100644
--- a/gcc/gengtype.c
+++ b/gcc/gengtype.c
@@ -4211,12 +4211,13 @@ finish_cache_funcs (flist *flp)
 	    {
 	      oprintf (base_files[fnum], "extern void gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (unsigned int);\n");
 	    }
       }
 
   for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++)
-    oprintf (base_files[fnum], "void\ngt_clear_caches ()\n{\n");
+    oprintf (base_files[fnum],
+	     "void\ngt_clear_caches (unsigned int phase)\n{\n");
 
   for (fli2 = flp; fli2; fli2 = fli2->next)
     if (fli2->started_p)
@@ -4231,7 +4232,7 @@ finish_cache_funcs (flist *flp)
 	    {
 	      oprintf (base_files[fnum], "  gt_clear_caches_");
 	      put_mangled_filename (base_files[fnum], fli2->file);
-	      oprintf (base_files[fnum], " ();\n");
+	      oprintf (base_files[fnum], " (phase);\n");
 	    }
       }
 
@@ -4660,10 +4661,10 @@ write_roots (pair_p variables, bool emit_pch)
 
 	  oprintf (f, "void\ngt_clear_caches_");
 	  put_mangled_filename (f, v->line.file);
-	  oprintf (f, " ()\n{\n");
+	  oprintf (f, " (unsigned int phase)\n{\n");
 	}
 
-      oprintf (f, "  gt_cleare_cache (%s);\n", v->name);
+      oprintf (f, "  gt_cleare_cache (%s, phase);\n", v->name);
     }
 
   finish_cache_funcs (flp);
diff --git a/gcc/ggc-common.c b/gcc/ggc-common.c
index 5096837..4f7e383 100644
--- a/gcc/ggc-common.c
+++ b/gcc/ggc-common.c
@@ -100,7 +100,16 @@ ggc_mark_roots (void)
   if (ggc_protect_identifiers)
     ggc_mark_stringpool ();
 
-  gt_clear_caches ();
+#ifdef ENABLE_CHECKING
+  /* Phase 1: Clear.  */
+  gt_clear_caches (1);
+
+  /* Phase 2: Mark.  */
+  gt_clear_caches (2);
+#else
+  /* Phase 0: Mark or Clear.  */
+  gt_clear_caches (0);
+#endif
 
   if (! ggc_protect_identifiers)
     ggc_purge_stringpool ();
diff --git a/gcc/ggc.h b/gcc/ggc.h
index ebc6a5d..0f6ff85 100644
--- a/gcc/ggc.h
+++ b/gcc/ggc.h
@@ -54,7 +54,7 @@ extern int gt_pch_note_object (void *, void *, gt_note_pointers);
 extern void gt_pch_note_reorder (void *, void *, gt_handle_reorder);
 
 /* generated function to clear caches in gc memory.  */
-extern void gt_clear_caches ();
+extern void gt_clear_caches (unsigned int);
 
 /* Mark the object in the first parameter and anything it points to.  */
 typedef void (*gt_pointer_walker) (void *);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..380e90f 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -491,7 +491,8 @@ private:
   template<typename T> friend void gt_pch_nx (hash_table<T> *,
 					      gt_pointer_operator, void *);
 
-  template<typename T> friend void gt_cleare_cache (hash_table<T> *);
+  template<typename T> friend void gt_cleare_cache (hash_table<T> *,
+						    unsigned int phase);
 
   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
   value_type *find_empty_slot_for_expand (hashval_t);
@@ -1039,22 +1040,54 @@ gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
 
 template<typename H>
 inline void
-gt_cleare_cache (hash_table<H> *h)
+gt_cleare_cache (hash_table<H> *h, unsigned int phase)
 {
   extern void gt_ggc_mx (typename H::value_type &t);
   typedef hash_table<H> table;
   if (!h)
     return;
 
-  for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
-    if (!table::is_empty (*iter) && !table::is_deleted (*iter))
-      {
-	int res = H::keep_cache_entry (*iter);
-	if (res == 0)
-	  h->clear_slot (&*iter);
-	else if (res != -1)
-	  gt_ggc_mx (*iter);
-      }
+  typename table::iterator iter;
+  switch (phase)
+    {
+    case 0:
+      /* Phase 0: Mark or Clear.  */
+      for (iter = h->begin (); iter != h->end (); ++iter)
+	if (!table::is_empty (*iter) && !table::is_deleted (*iter))
+	  {
+	    int res = H::keep_cache_entry (*iter);
+	    if (res == 0)
+	      h->clear_slot (&*iter);
+	    else if (res != -1)
+	      gt_ggc_mx (*iter);
+	  }
+      break;
+
+    case 1:
+      /* Phase 1: Clear.  */
+      for (iter = h->begin (); iter != h->end (); ++iter)
+	if (!table::is_empty (*iter) && !table::is_deleted (*iter))
+	  {
+	    int res = H::keep_cache_entry (*iter);
+	    if (res == 0)
+	      h->clear_slot (&*iter);
+	  }
+      break;
+
+    case 2:
+      /* Phase 2: Mark.  */
+      for (iter = h->begin (); iter != h->end (); ++iter)
+	if (!table::is_empty (*iter) && !table::is_deleted (*iter))
+	  {
+	    int res = H::keep_cache_entry (*iter);
+	    if (res == 1)
+	      gt_ggc_mx (*iter);
+	  }
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
 }
 
 #endif /* TYPED_HASHTAB_H */
-- 
1.9.1