Re: PATCH: ggc marking hooks

[Basile STARYNKEVITCH <basile at starynkevitch dot net>]

Hello

In message http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01856.html I (Basile) wrote:

 
> The attached (not very big, about 280 lines) patch is related in
> intention to my committed patch (rev 121077 of trunk) on mark_hook-s
> GTY in gengtype
> http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01534.html
> 
> Remember that the former patch add the (currently still not used
> AFAIK) ability to have a mark hook routine called when markiong some
> specific GGC garbage-collected data.
> 
> If we want to use the mark_hook feature we probably want to have some
> routines called before marking begins and after it has happenned.  As
> Steven Bosscher suggested in
> http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01536.html a possible use
> could be to ease hunting of some memory leaks. Another possible use
> could be to simply count the number of data (of some given
> GTY-declared type). Then it would be helpful to have a small routine
> which clears the counter before every garbage collection (this is a
> pre-marking hook) and another routine (after the marking phase of a
> ggc_collect) would check or dimp this counter (this is a post-marking
> hook). It is best to have these hooks called inside the various
> implementations of ggc_collect. Hence I feel that such hooks are
> useful, otherwise it is not very wise to use the (already committed)
> GTY mark_hook feature.
> 
> Of course, the cost is some small overhead in every (working) call of
> ggc_collect. But I expect that the number of such hooks is rather
> small (a dozen of quickly running routines) - even if this patch does
> not force any artificial bound on the number of hooks. In the current
> state of this patch, no hooks get called yet and I cannot measure the
> small cost of this overhead (which happens only inside ggc_collect,
> which is not called very often). In practice, the overhead is really
> those of the hooks called.
 

I made a slightly improved version (440 lines in this patch) of the patch in
http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01856.html. The improvements are:

* the rank of a hook is now a strictly positive integer, and is also
   used to sort hooks of same priority

* I updated the documentation with a small example, which I *partly*
  reproduce here:

  A simple pre-marking hook just clears a counter:
    static void clear_long(void*d) {
      long *p = d;
      *p = 0;
    }

  A mark_hook (as given with GTY, per my previous patch) increment it
  for every marked structure of some of our type

    static long ptr_counter;
    static void increment_counter(void*d) {
      gcc_assert(d != 0);
      ptr_counter++;
    }

    struct some_struct_st GTY((mark_hook("increment_counter"))) 

 The pre-marking hook is registered (priority 5) with
    int hookrank = ggc_add_premarking_hook(clear_long,(void*)&ptr_counter,5);
 Likewise a post-marking hook can be registered to check (or print) the counter.

this patch, to trunk rev.121106, bootstrapped ok with 
	configure --disable-multilib --enable-languages=c

I also tested the features oprovided by this patch (pre- & post-
marking hooks) by running an example very similar to the one I
documented (mostly by adding fprintf(stderr,..)) in the gty.texi to
make sure the GGC did run, I had to set ggc_force_collect=1 in gdb

I really fill this patch is almost required by my accepted and
committed patch
http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01534.html

Ok for trunk, since it has been bootstrapped on Debian/Sid/AMD64 ie
gnu-linux-x86_64 and separately tested ?

Changelog after my sig.

Regards.
-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359 
8, rue de la Faïencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

############################################## gcc/Changelog
2007-01-24  Basile Starynkevitch  <basile@starynkevitch.net>
	* gcc/doc/gty.texi (Options): Mentions pre&post marking hooks.
	(GGC Hooks): New node explaining pre & post marking hooks with
	example (also for GTY(mark_hook)).

	* gcc/ggc.h: New feature; pre & post marking hooks.
	(ggc_hook_routine_t): new type for signature of hooks.
	(ggc_add_premarking_hook, ggc_remove_premarking_hook, 
	 ggc_add_postmarking_hook, ggc_remove_postmarking_hook, 
	 ggc_run_premarking_hooks, ggc_run_postmarking_hooks): new
	function declarations.

	* gcc/ggc-common.c (ggchook_st, ggchook_ptr_t): new types.
	(premark_hookvec, postmark_hookvec): new static vectors.
	(add_marking_hook, ggc_add_premarking_hook, 
	 ggc_add_postmarking_hook, remove_marking_hook, 
	 ggc_remove_postmarking_hook, hookptr_cmp, run_marking_hooks,
	 ggc_run_premarking_hooks, ggc_run_postmarking_hooks):
	New functions for pre- & post- marking hooks new feature.

	* gcc/ggc-zone.c (ggc_collect): added calls to 
	 ggc_run_premarking_hooks & ggc_run_postmarking_hooks

	* gcc/ggc-page.c (ggc_collect): added calls to 
	 ggc_run_premarking_hooks & ggc_run_postmarking_hooks

	* gcc/Makefile.in (ggc-common.o): added new dependency to vec.h

Index: gcc/doc/gty.texi
===================================================================
--- gcc/doc/gty.texi	(revision 121106)
+++ gcc/doc/gty.texi	(working copy)
@@ -69,6 +69,7 @@ These don't need to be marked.
 * GTY Options::		What goes inside a @code{GTY(())}.
 * GGC Roots::		Making global variables GGC roots.
 * Files::		How the generated files work.
+* GGC Hooks::           Adding hooks into the GGC garbage collector.
 @end menu
 
 @node GTY Options
@@ -290,7 +291,9 @@ If provided for a structure or union typ
 routine called when the garbage collector has just marked the data as
 reachable. This routine should not change the data, or call any ggc
 routine. Its only argument is a pointer to the just marked (const)
-structure or union.
+structure or union. GCC developers using such @code{mark_hook}-s may
+also find useful to add ggc collector pre-marking or post-marking
+hooks, see @ref{GGC Hooks}, which also provides a simple example.
 
 @findex maybe_undef
 @item maybe_undef
@@ -444,3 +447,126 @@ source file.  Don't forget to mention th
 For language frontends, there is another file that needs to be included
 somewhere.  It will be called @file{gtype-@var{lang}.h}, where
 @var{lang} is the name of the subdirectory the language is contained in.
+
+
+@node GGC Hooks
+@section Hooks inside the Garbage Collector
+
+The GGC garbage collector is a precise mark and sweep collector. It is
+only explicitly run by calls to @code{ggc_collect}, and handles only
+global or static pointers explicitly annotated with @code{GTY} (it
+ignores any local pointer variables on the call stack of the GCC
+compiler).
+
+GCC Developers may find useful to ask the GGC garbage collector
+(i.e. the @code{ggc_collect} routine) to run some (small and quick)
+code (hooks) inside the garbage collection procedure. Two kinds of
+hooks are available:
+
+@enumerate
+
+@item 
+@cindex pre-marking hooks
+@findex ggc_add_premarking_hook
+@findex ggc_remove_premarking_hook
+@emph{pre-marking hooks} are run inside @code{ggc_collect} before any marking
+begins. They are registered with @code{ggc_add_premarking_hook} and
+removed with @code{ggc_remove_premarking_hook}.
+
+@item
+@cindex post-marking hooks
+@findex ggc_add_postmarking_hook
+@findex ggc_remove_postmarking_hook
+@emph{post-marking hooks} are run inside @code{ggc_collect} after all
+marking and before reclaiming memory. They are registered with
+@code{ggc_add_postmarking_hook} and removed with @code{ggc_remove_postmarking_hook}
+
+@end enumerate
+
+Such hooks are expected to run quickly, and should not alter the GGC
+maanged memory (nor allocate it). 
+
+Hooks have integer priorities, and are executed in order of increasing
+priorities. A hook is registered as a routine (returning @code{void})
+called with a @code{void*} client pointer.
+
+A possible use of such hooks, with the
+@code{GTY((mark_hook("marking-routine")))} marker, is to check that
+every pointer of a given type has been released. To achieve that (in a
+given pass), declare a counter and a @code{mark_hook} incrementing it:
+
+@example
+static long ptr_counter;
+static void increment_counter(void*d) @{
+  gcc_assert(d != 0);
+  ptr_counter++;
+@}
+
+struct some_struct_st GTY((mark_hook("increment_counter"))) 
+@{ @r{/* ... declaration of your structure ... */} 
+@};
+@end example
+
+The counter should be cleared before every marking phase of the GGC
+collector, so we need a pre-marking hook to clear it:
+@example
+static void clear_long(void*d) @{
+  long *p = d;
+  *p = 0;
+@}
+@end example
+
+Notice that this pre-marking hook routine could clear any long passed
+as data (so we would need only one such routine, even if we have
+several counters). We keep the (positive) rank of the registered hook
+in a variable:
+@example
+int clear_long_hook_rank;
+@end example
+And we register the pre-marking hook routine at priority 5 with
+@example
+clear_long_hook_rank = 
+        ggc_add_premarking_hook(clear_long,(void*)&ptr_counter,5);
+@end example
+
+Later on, perhaps in a further pass which is expected to have consumed
+(i.e. released) every instance of our fictuous @code{struct
+some_struct_st}, we register a post-marking hook to check that the
+counter remained at 0, again keeping the rank of the hook in:
+@example
+int check_long_hook_rank;
+@end example
+The hook itself is simply:
+@example
+static void check_zero_long(void*d) @{
+  long *p = d;
+  gcc_assert(*p == 0);
+@}
+@end example
+
+And we register it with:
+@example
+check_long_hook_rank = 
+        ggc_add_postmarking_hook(check_zero_long,(void*)&ptr_counter,2);
+@end example
+
+To check that, as expected, no pointer to @code{struct some_struct_st}
+remains, we have to explicitly call @code{ggc_collect}, and then we
+could remove the hooks with 
+@example
+ggc_remove_premarking_hook(clear_long_hook_rank);
+ggc_remove_postmarking_hook(check_long_hook_rank);
+@end example
+
+It is permitted to add or remove a hook (even itself) from a hook
+routine. The change is taken into account (if called from a hook
+indirectly withing @code{ggc_collect}) at the next garbage
+collection. But @emph{mark hooks} (given with
+@code{GTY((mark_hook("@var{mark-hook-routine}")))}) and @emph{pre- and
+post- marking hooks} (registered with @code{ggc_add_premarking_hook}
+and @code{ggc_add_postmarking_hook}) @emph{cannot alter or allocate
+GGC managed data}.
+
+It is expected that such hooks are not very often used (i.e. dozens,
+but not thousands of hooks), and that they run quickly. Each pass
+should have few hooks (if any).
Index: gcc/ggc.h
===================================================================
--- gcc/ggc.h	(revision 121106)
+++ gcc/ggc.h	(working copy)
@@ -314,4 +314,35 @@ extern void *ggc_alloc_zone_stat (size_t
 
 #endif
 
+
+
+/***
+ * Garbage collection hooks
+ ***/
+
+/* the signature of hooks; these routines cannot do anything ggc
+   related or change ggc managed data */
+typedef void ggc_hook_routine_t(void*data);
+
+/* add a hook to be run before marking; return a positive hook rank
+   (which is used for removing the hook); the hooks are run in order
+   of increasing priority - can be called from a hook but effective
+   only on the next call to ggc_collect */
+int ggc_add_premarking_hook(ggc_hook_routine_t*rout, void*data, int prio);
+/* remove such an added hook - can be called from a hook but effective
+   only on the next call to ggc_collect */
+void ggc_remove_premarking_hook(int rank);
+
+/* add a hook to be run after marking; ; return a positive hook rank
+   (which is used for removing the hook); the hooks are run in order
+   of increasing priority - can be called from a hook but effective
+   only on the next call to ggc_collect */
+int ggc_add_postmarking_hook(ggc_hook_routine_t*rout, void*data, int prio);
+/* remove such an added hook  - can be called from a hook but effective
+   only on the next call to ggc_collect */
+void ggc_remove_postmarking_hook(int rank);
+
+/**** only to be run by ggc implementations ****/
+void ggc_run_premarking_hooks (void);
+void ggc_run_postmarking_hooks (void);
 #endif
Index: gcc/ggc-common.c
===================================================================
--- gcc/ggc-common.c	(revision 121106)
+++ gcc/ggc-common.c	(working copy)
@@ -1,5 +1,5 @@
 /* Simple garbage collection for the GNU compiler.
-   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
    Free Software Foundation, Inc.
 
 This file is part of GCC.
@@ -31,6 +31,7 @@ Software Foundation, 51 Franklin Street,
 #include "params.h"
 #include "hosthooks.h"
 #include "hosthooks-def.h"
+#include "vec.h"
 
 #ifdef HAVE_SYS_RESOURCE_H
 # include <sys/resource.h>
@@ -1021,3 +1022,174 @@ dump_ggc_loc_statistics (bool final ATTR
   fprintf (stderr, "-------------------------------------------------------\n");
 #endif
 }
+
+
+
+/************
+ * garbage collection hook management
+ ************/
+
+struct ggchook_st
+{
+  ggc_hook_routine_t *gh_rout;	/* the hook routine */
+  void *gh_data;		/* its client data */
+  int gh_prio;			/* the priority */
+  int gh_rank;			/* the unique rank in its vector */
+};
+
+typedef struct ggchook_st *ggchook_ptr_t;
+DEF_VEC_P (ggchook_ptr_t);
+DEF_VEC_ALLOC_P (ggchook_ptr_t, heap);
+typedef VEC (ggchook_ptr_t, heap) ggchook_vec_t;
+
+static ggchook_vec_t *premark_hookvec;
+static ggchook_vec_t *postmark_hookvec;
+
+static int
+add_marking_hook (ggchook_vec_t **pvec,
+		  ggc_hook_routine_t *rout, void *data, int prio)
+{
+  static long cnt;
+  struct ggchook_st *newhook = 0;
+  ggchook_vec_t *vec = *pvec;
+  int rk = -1, i = 0, l = 0;
+  gcc_assert (rout != (ggc_hook_routine_t*) 0);
+  if (!vec)
+    vec = VEC_alloc (ggchook_ptr_t, heap, 40);
+  if (VEC_empty(ggchook_ptr_t, vec)) 
+    /* ensure that the vector is not empty hence rank is positive */
+    VEC_safe_push (ggchook_ptr_t, heap, vec, (ggchook_ptr_t)0);
+  newhook = xcalloc (sizeof (struct ggchook_st), 1);
+  cnt++;
+  newhook->gh_rout = rout;
+  newhook->gh_data = data;
+  newhook->gh_prio = prio;
+  newhook->gh_rank = 0 /*updated later*/;
+  l = VEC_length (ggchook_ptr_t, vec);
+  for (i = 1; i < l; i++)
+    {
+      if (!VEC_index (ggchook_ptr_t, vec, i))
+	{
+	  rk = i;
+	  VEC_replace (ggchook_ptr_t, vec, rk, newhook);
+	  newhook->gh_rank = rk;
+	  break;
+	}
+    };
+  if (rk < 0)
+    {
+      rk = l;
+      VEC_safe_push (ggchook_ptr_t, heap, vec, newhook);
+      newhook->gh_rank = rk;
+    };
+  *pvec = vec;
+  return rk;
+}
+
+int
+ggc_add_premarking_hook (ggc_hook_routine_t *rout, void *data, int prio)
+{
+  return add_marking_hook (&premark_hookvec, rout, data, prio);
+}
+
+int
+ggc_add_postmarking_hook (ggc_hook_routine_t *rout, void *data, int prio)
+{
+  return add_marking_hook (&postmark_hookvec, rout, data, prio);
+}
+
+
+static void
+remove_marking_hook (ggchook_vec_t **pvec, int rank)
+{
+  int i = 0, l = 0;
+  ggchook_ptr_t hook = NULL;
+  ggchook_vec_t *vec = *pvec;
+  if (!vec)
+    return;
+  l = VEC_length (ggchook_ptr_t, vec);
+  if (rank <= 0 || rank >= l)
+    return;
+  hook = VEC_replace (ggchook_ptr_t, vec, rank, (struct ggchook_st *) 0);
+  if (!hook)
+    return;
+  gcc_assert(hook->gh_rank == rank);
+  memset (hook, 0, sizeof (*hook));
+  free (hook);
+  /* if this is the highest non empty rank, truncate the vector */
+  for (i = rank + 1; i < l; i++)
+    if (VEC_index (ggchook_ptr_t, vec, i))
+      return;
+  VEC_truncate (ggchook_ptr_t, vec, rank);
+  *pvec = vec;
+}
+
+void
+ggc_remove_premarking_hook (int rank)
+{
+  remove_marking_hook (&premark_hookvec, rank);
+}
+
+void
+ggc_remove_postmarking_hook (int rank)
+{
+  remove_marking_hook (&postmark_hookvec, rank);
+}
+
+/* we sort the hooks by priority or else by their rank */
+static int
+hookptr_cmp (const void *l, const void *r)
+{
+  int dprio;
+  const struct ggchook_st *hl = *(const struct ggchook_st **) l;
+  const struct ggchook_st *hr = *(const struct ggchook_st **) r;
+  gcc_assert(hl != NULL && hr != NULL);
+  dprio = hl->gh_prio - hr->gh_prio;
+  if (dprio == 0)
+    return hl->gh_rank - hr->gh_rank;
+  else
+    return dprio;
+}
+
+/* to run the hooks, we copy them into a calloc-ed array of pointers,
+   sort this array, and run the hooks there; hence adding or removing
+   hooks from other hooks is possible without restriction */
+static void
+run_marking_hooks (ggchook_vec_t * hookvec)
+{
+  struct ggchook_st **hooktab = 0, *hook = 0;
+  int rk = 0, i = 0, l = 0;
+  if (!hookvec)
+    return;
+  l = VEC_length (ggchook_ptr_t, hookvec);
+  /* get the non-empty non-null hooks */
+  hooktab = xcalloc (sizeof (*hooktab), l + 1);
+  for (i = 0; VEC_iterate (ggchook_ptr_t, hookvec, i, hook); i++)
+    {
+      if (!hook || !hook->gh_rout)
+	continue;
+      gcc_assert(hook->gh_rank == i);
+      hooktab[rk++] = hook;
+    }
+  if (rk > 1)
+    qsort (hooktab, rk, sizeof (hook), hookptr_cmp);
+  for (i = 0; i < rk; i++)
+    {
+      hook = hooktab[i];
+      (*hook->gh_rout) (hook->gh_data);
+    }
+  free (hooktab);
+}
+
+void
+ggc_run_premarking_hooks (void)
+{
+  run_marking_hooks (premark_hookvec);
+}
+
+void
+ggc_run_postmarking_hooks (void)
+{
+  run_marking_hooks (postmark_hookvec);
+}
+
Index: gcc/ggc-zone.c
===================================================================
--- gcc/ggc-zone.c	(revision 121106)
+++ gcc/ggc-zone.c	(working copy)
@@ -1883,7 +1883,8 @@ ggc_collect (void)
 	}
     }
 
-  /* Start by possibly collecting the main zone.  */
+  /* Start by running pre-marking hooks and possibly collecting the main zone.  */
+  ggc_run_premarking_hooks ();
   main_zone.was_collected = false;
   marked |= ggc_collect_1 (&main_zone, true);
 
@@ -1925,6 +1926,9 @@ ggc_collect (void)
     }
 #endif
 
+  /* run the postmarking hooks before freeing */
+  ggc_run_postmarking_hooks ();
+
   if (marked)
     zone_free_marks ();
 
Index: gcc/ggc-page.c
===================================================================
--- gcc/ggc-page.c	(revision 121106)
+++ gcc/ggc-page.c	(working copy)
@@ -1903,10 +1903,16 @@ ggc_collect (void)
   G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
 
   clear_marks ();
+  /* run the premarking hooks before marking roots*/
+  ggc_run_premarking_hooks ();
   ggc_mark_roots ();
+
 #ifdef GATHER_STATISTICS
   ggc_prune_overhead_list ();
 #endif
+
+  /* run the postmarking hooks before freeing memory */
+  ggc_run_postmarking_hooks ();
   poison_pages ();
   validate_free_objects ();
   sweep_pages ();
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 121106)
+++ gcc/Makefile.in	(working copy)
@@ -1905,7 +1905,7 @@ gtype-desc.o: gtype-desc.c $(CONFIG_H) $
 	$(CGRAPH_H) $(TREE_FLOW_H) reload.h $(CPP_ID_DATA_H)
 
 ggc-common.o: ggc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(GGC_H) \
-	$(HASHTAB_H) toplev.h $(PARAMS_H) hosthooks.h $(HOSTHOOKS_DEF_H)
+	$(HASHTAB_H) toplev.h $(PARAMS_H) hosthooks.h $(HOSTHOOKS_DEF_H) vec.h
 
 ggc-page.o: ggc-page.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
 	$(FLAGS_H) toplev.h $(GGC_H) $(TIMEVAR_H) $(TM_P_H) $(PARAMS_H) $(TREE_FLOW_H)