Re: [RFC] two-phase marking in gt_cleare_cache

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

On 07/07/15 16:00, Michael Matz wrote:
> Hi,
>
> On Mon, 6 Jul 2015, Richard Biener wrote:
>
> > > > 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).
> >
> > Hmm, and don't we rather want to first mark and _then_ clear?  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 don't think such use has ever worked with the caching hash tables.  Even
> the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A
> became life from outside, but it itself kept an entry B live in the hash
> table (with no other references to B) then this never worked (or only by
> luck), because the slot was always cleared if !ggc_marked_p, so if B was
> visited before A it was removed from the hash-table (and in particular B's
> gt_ggc_mx routine was never called, so whatever B needed wasn't even
> marked).
>
> Given this I think the call to gt_ggc_mx is superfluous because it
> wouldn't work relyably for multi-step dependencies anyway.  Hence a
> situation that works with that call in place, and breaking without it is
> actually a bug waiting to be uncovered.

Attached patch tries to get multi-step dependencies right, without using 
iteration-till-fixed-point.

During the marking phase, we do recursive marking of the cache entries, 
while skipping the marking of:
- the cache entry itself, and
- the key component of the cache entry.
This marking is done for all non-empty cache entries independent of the 
current value of keep_cache_entry. So we make a conservative choice 
here, and by doing so avoid having to iterate-till-fixed-point.

During the cache-clear phase, for each cache entry we either 
non-recursively mark it live, or remove it.

AFAIU, this scheme reliably handles multi-step dependencies and does not 
increase runtime.

Passes a minimal c build, and it fixes the ICE of PR66714 (although 
there still might be a root cause to address, I'm not sure).

Thanks,
- Tom

Use conservative non-iterative strategy for caches

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

	PR libgomp/66714
	* hash-table.h (gt_cleare_cache): Don't recurse cache entries, just
	mark.
	* trans-mem.c (struct tm_wrapper_hasher::ggc_mx (tree_map *&m)): New
	function.
	* tree.c (struct tree_vec_map_cache_hasher::ggc_mx (tree_vec_map *&m):
	Same.
	* tree.h
	(struct tree_decl_map_cache_hasher::ggc_mx (tree_decl_map *&m)): Same.
	* ubsan.c
	(struct tree_type_map_cache_hasher::ggc_mx (tree_type_map *&m)): Same.
	* varasm.c (struct tm_clone_hasher::ggc_mx (tree_map *&m)): Same.

	* testsuite/libgomp.c/pr66714.c: New test.
---
 gcc/hash-table.h                      | 28 +++++++++++++++++++++++++++-
 gcc/trans-mem.c                       |  4 ++++
 gcc/tree.c                            |  7 +++++++
 gcc/tree.h                            |  6 ++++++
 gcc/ubsan.c                           |  4 ++++
 gcc/varasm.c                          |  4 ++++
 libgomp/testsuite/libgomp.c/pr66714.c | 17 +++++++++++++++++
 7 files changed, 69 insertions(+), 1 deletion(-)
 create mode 100644 libgomp/testsuite/libgomp.c/pr66714.c

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 12e0c96..ce899bd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -1046,6 +1046,32 @@ gt_cleare_cache (hash_table<H> *h)
   if (!h)
     return;
 
+  /* Say we have a cache entry E with key 'from' and non-key 'to'.
+
+     The marking of non-key 'to' should be done in ggc_mx () during the marking
+     phase.  We mark the non-key 'to' conservatively, that is, regardless of
+     whether the key 'from' is live or not.
+
+     The marking of key 'from' has already been done or not during the marking
+     phase, and determines whether we keep entry E live during the clear-cache
+     phase.
+     If key 'from' is alive, we mark entry E as such.
+     If key 'from' is not alive:
+     - we remove the entry E from the cache, and
+     - entry E will be ggc-freed, and
+     - key 'from' will be ggc-freed.
+     - non-key 'to' will not be freed, since we conservatively marked it.  But
+       next ggc invocation, entry E will be gone and no longer cause 'to' to be
+       marked.  So 'to' may be gcc-freed the next ggc invocation.
+
+     Background: A more optimal marking strategy would be to mark the non-key
+     'to' only if key 'from' is live.  But in order to get to the transitive
+     closure of that marking, we'd need an iterate-till-fixed-point loop around
+     the traversing of all cache tables and their entries.
+     So instead we mark conservatively.  The drawback of this strategy
+     is that cache cycles are not freed.  Also, it can take several ggc
+     invocations for the effects to fully propagate.  */
+
   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
       {
@@ -1053,7 +1079,7 @@ gt_cleare_cache (hash_table<H> *h)
 	if (res == 0)
 	  h->clear_slot (&*iter);
 	else if (res != -1)
-	  gt_ggc_mx (*iter);
+	  ggc_set_mark (*iter);
       }
 }
 
diff --git a/gcc/trans-mem.c b/gcc/trans-mem.c
index c809a2e..748a2b6 100644
--- a/gcc/trans-mem.c
+++ b/gcc/trans-mem.c
@@ -478,6 +478,10 @@ struct tm_wrapper_hasher : ggc_cache_ptr_hash<tree_map>
     return a->base.from == b->base.from;
   }
 
+  static void ggc_mx (tree_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_map *&m)
   {
diff --git a/gcc/tree.c b/gcc/tree.c
index 6628a38..16afae5 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -261,6 +261,13 @@ struct tree_vec_map_cache_hasher : ggc_cache_ptr_hash<tree_vec_map>
     return a->base.from == b->base.from;
   }
 
+  static void ggc_mx (tree_vec_map *&m) {
+    /* gt_ggc_mx (vec<T, va_gc> *v) from vec.h does not do
+       ggc_test_and_set_mark, so do it here.  */
+    if (ggc_test_and_set_mark (m->to))
+      gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_vec_map *&m)
   {
diff --git a/gcc/tree.h b/gcc/tree.h
index 250f99d..ae48a80 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4626,6 +4626,8 @@ extern unsigned int tree_map_hash (const void *);
 extern unsigned int tree_decl_map_hash (const void *);
 #define tree_decl_map_marked_p tree_map_base_marked_p
 
+extern void gt_ggc_mx (tree&);
+
 struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash<tree_decl_map>
 {
   static hashval_t hash (tree_decl_map *m) { return tree_decl_map_hash (m); }
@@ -4635,6 +4637,10 @@ struct tree_decl_map_cache_hasher : ggc_cache_ptr_hash<tree_decl_map>
     return tree_decl_map_eq (a, b);
   }
 
+  static void ggc_mx (tree_decl_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_decl_map *&m)
   {
diff --git a/gcc/ubsan.c b/gcc/ubsan.c
index 19eafab..6ea5be8 100644
--- a/gcc/ubsan.c
+++ b/gcc/ubsan.c
@@ -95,6 +95,10 @@ struct tree_type_map_cache_hasher : ggc_cache_ptr_hash<tree_type_map>
     return a->type.from == b->type.from;
   }
 
+  static void ggc_mx (tree_type_map *&m) {
+    gt_ggc_mx (m->decl);
+  }
+
   static int
   keep_cache_entry (tree_type_map *&m)
   {
diff --git a/gcc/varasm.c b/gcc/varasm.c
index 3e76032..ff20941 100644
--- a/gcc/varasm.c
+++ b/gcc/varasm.c
@@ -5793,6 +5793,10 @@ struct tm_clone_hasher : ggc_cache_ptr_hash<tree_map>
   static hashval_t hash (tree_map *m) { return tree_map_hash (m); }
   static bool equal (tree_map *a, tree_map *b) { return tree_map_eq (a, b); }
 
+  static void ggc_mx (tree_map *&m) {
+    gt_ggc_mx (m->to);
+  }
+
   static int
   keep_cache_entry (tree_map *&e)
   {
diff --git a/libgomp/testsuite/libgomp.c/pr66714.c b/libgomp/testsuite/libgomp.c/pr66714.c
new file mode 100644
index 0000000..b60c74d
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr66714.c
@@ -0,0 +1,17 @@
+/* { dg-do "compile" } */
+/* { dg-additional-options "--param ggc-min-expand=0" } */
+/* { dg-additional-options "--param ggc-min-heapsize=0" } */
+/* { dg-additional-options "-g" } */
+
+/* Minimized from on target-2.c.  */
+
+void
+fn3 (int x)
+{
+  double b[3 * x];
+  int i;
+  #pragma omp target
+    #pragma omp parallel for
+      for (i = 0; i < x; i++)
+	b[i] += 1;
+}
-- 
1.9.1