[patch] [2/5] Types reference counting [garbage-collector]

[Jan Kratochvil <jan dot kratochvil at redhat dot com>]

Hi,

a types garbage collector implementation.  This part is directly dependent on
the `base' patch.

The free_all_types calls should be one day moved together with free_all_values
into some general idle function.


Thanks,
Jan


gdb/
2009-04-11  Jan Kratochvil  <jan.kratochvil@redhat.com>
	    Tom Tromey  <tromey@redhat.com>

	Start garbage collecting unused types.
	* gdbtypes.c (main_type_crawl_iter, main_type_crawl, link_group_relabel)
	(type_group_link_check_grouping_markers)
	(type_group_link_check_grouping_iter, type_group_link_check_grouping)
	(check_types_fail_iter, check_types_fail, check_types_assert)
	(type_group_link_check, delete_main_type, delete_type_chain)
	(type_group_link_remove, free_all_types): New.
	* gdbtypes.h (free_all_types): New prototype.
	* mi/mi-main.c (mi_cmd_execute): Call free_all_types when idle.
	* top.c (execute_command): Likewise.

diff --git a/gdb/gdbtypes.c b/gdb/gdbtypes.c
index c866353..63f6cc6 100644
--- a/gdb/gdbtypes.c
+++ b/gdb/gdbtypes.c
@@ -3154,6 +3154,251 @@ copy_type (const struct type *type)
   return new_type;
 }
 
+/* Callback type for main_type_crawl.  */
+typedef int (*main_type_crawl_iter) (struct type *type, void *data);
+
+/* Iterate all main_type structures reachable through any `struct type *' from
+   TYPE.  ITER will be called only for one type of each main_type, use
+   TYPE_CHAIN traversal to find all the type instances.  ITER is being called
+   for each main_type found.  ITER returns non-zero if main_type_crawl should
+   depth-first enter the specific type.  ITER must provide some detection for
+   reentering the same main_type as this function would otherwise endlessly
+   loop.  */
+
+static void
+main_type_crawl (struct type *type, main_type_crawl_iter iter, void *data)
+{
+  struct type *type_iter;
+  int i;
+
+  if (!type)
+    return;
+
+  gdb_assert (TYPE_OBJFILE (type) == NULL);
+
+  /* `struct cplus_struct_type' handling is unsupported by this function.  */
+  gdb_assert ((TYPE_CODE (type) != TYPE_CODE_STRUCT
+	       && TYPE_CODE (type) != TYPE_CODE_UNION)
+	      || !HAVE_CPLUS_STRUCT (type) || !TYPE_CPLUS_SPECIFIC (type));
+
+  if (!(*iter) (type, data))
+    return;
+
+  /* Iterate all the type instances of this main_type.  */
+  type_iter = type;
+  do
+    {
+      gdb_assert (TYPE_MAIN_TYPE (type_iter) == TYPE_MAIN_TYPE (type));
+
+      main_type_crawl (TYPE_POINTER_TYPE (type), iter, data);
+      main_type_crawl (TYPE_REFERENCE_TYPE (type), iter, data);
+
+      type_iter = TYPE_CHAIN (type_iter);
+    }
+  while (type_iter != type);
+
+  for (i = 0; i < TYPE_NFIELDS (type); i++)
+    main_type_crawl (TYPE_FIELD_TYPE (type, i), iter, data);
+
+  main_type_crawl (TYPE_TARGET_TYPE (type), iter, data);
+  main_type_crawl (TYPE_VPTR_BASETYPE (type), iter, data);
+}
+
+/* Unify all the entries associated by type_group FROM with type_group TO.  The
+   new group will belong to type_group TO.  */
+
+static void
+link_group_relabel (struct type_group *to, struct type_group *from)
+{
+  struct type_group_link *iter, *iter_next;
+
+  gdb_assert (to != from);
+
+  to->link_count += from->link_count;
+
+  for (iter = from->link_list; iter; iter = iter_next)
+    {
+      iter_next = iter->group_next;
+
+      /* Relink ITER to the group list of TO.  */
+      iter->group_next = to->link_list;
+      to->link_list = iter;
+
+      iter->group = to;
+    }
+
+  xfree (from);
+}
+
+/* Number of visited type_group_link_table entries during this
+   type_group_link_check pass.  */
+static unsigned type_group_link_check_grouping_markers;
+
+/* Unify type_group of all the type structures found while crawling the
+   type_group_link_table tree from the starting point type.  DATA contains
+   type_group_link reference of the starting point type.  Only during the first
+   callback TYPE will always match type_group_link referenced by DATA.  */
+
+static int
+type_group_link_check_grouping_iter (struct type *type, void *data)
+{
+  /* The starting point referenced in type_group_link_table.  */
+  struct type_group_link *link_start = data;
+  struct type_group_link link_local, *link;
+  int crawl_into = 0;
+
+  link_local.type = type;
+  link = htab_find (type_group_link_table, &link_local);
+  /* A permanent type?  */
+  if (!link)
+    return 0;
+
+  /* Was this LINK already met during the current type_group_link_check pass?  */
+  if (link->age != type_group_age)
+    {
+      link->age = type_group_age;
+      type_group_link_check_grouping_markers++;
+      crawl_into = 1;
+    }
+
+  if (link != link_start && link->group != link_start->group)
+    {
+      /* Keep the time complexity linear by relabeling always the smaller
+	 group.  */
+      if (link->group->link_count < link_start->group->link_count)
+	link_group_relabel (link->group, link_start->group);
+      else
+	link_group_relabel (link_start->group, link->group);
+    }
+
+  return crawl_into;
+}
+
+/* Iterator to unify type_group of all the type structures connected with the
+   one referenced by LINK (therefore *SLOT).  */
+
+static int
+type_group_link_check_grouping (void **slot, void *unused)
+{
+  struct type_group_link *link = *slot;
+
+  main_type_crawl (link->type, type_group_link_check_grouping_iter, link);
+
+  return 1;
+}
+
+/* Helper iterator for check_types_fail.  */
+
+static int
+check_types_fail_iter (void **slot, void *unused)
+{
+  struct type_group_link *link = *slot;
+  struct type *type = link->type;
+
+  fprintf_unfiltered (gdb_stderr, "type %p main_type %p \"%s\" group %p "
+				  "use_count %d link_count %d\n",
+		      type, TYPE_MAIN_TYPE (type),
+		      TYPE_NAME (type) ? TYPE_NAME (type) : "<null>",
+		      link->group, link->group->use_count,
+		      link->group->link_count);
+
+  return 1;
+}
+
+/* Called by check_types_assert to abort GDB execution printing the state of
+   type_group_link_table to make debugging GDB possible.  */
+
+static void
+check_types_fail (const char *file, int line, const char *function)
+{
+  target_terminal_ours ();
+  gdb_flush (gdb_stdout);
+
+  htab_traverse (type_group_link_table, check_types_fail_iter, NULL);
+
+  internal_error (file, line, _("%s: Type groups consistency fail"), function);
+}
+
+/* gdb_assert replacement for conditions being caused by wrong
+   type_group_link_table state.  This function is not intended for catching
+   bugs in these sanity checking functions themselves.  */
+
+#define check_types_assert(expr)					 \
+  ((void) ((expr) ? 0 :							 \
+	   (check_types_fail (__FILE__, __LINE__, ASSERT_FUNCTION), 0)))
+
+/* Unify type_group of all the type structures found while crawling the
+   type_group_link_table tree from every of its type_group_link entries.  This
+   functionality protects free_all_types from freeing a type structure still
+   being referenced by some other type.  */
+
+static void
+type_group_link_check (void)
+{
+  /* Mark a new pass.  As GDB checks all the entries were visited after each
+     pass there cannot be any stale entries already containing the changed
+     value.  */
+  type_group_age ^= 1;
+
+  type_group_link_check_grouping_markers = 0;
+  htab_traverse (type_group_link_table, type_group_link_check_grouping, NULL);
+  check_types_assert (type_group_link_check_grouping_markers
+		      == htab_elements (type_group_link_table));
+}
+
+/* A helper for delete_type which deletes a main_type and the things to which
+   it refers.  TYPE is a type whose main_type we wish to destroy.  */
+
+static void
+delete_main_type (struct type *type)
+{
+  int i;
+
+  gdb_assert (TYPE_OBJFILE (type) == NULL);
+
+  xfree (TYPE_NAME (type));
+  xfree (TYPE_TAG_NAME (type));
+
+  for (i = 0; i < TYPE_NFIELDS (type); ++i)
+    {
+      xfree (TYPE_FIELD_NAME (type, i));
+
+      if (TYPE_FIELD_LOC_KIND (type, i) == FIELD_LOC_KIND_PHYSNAME)
+	xfree (TYPE_FIELD_STATIC_PHYSNAME (type, i));
+    }
+  xfree (TYPE_FIELDS (type));
+
+  /* `struct cplus_struct_type' handling is unsupported by this function.  */
+  gdb_assert ((TYPE_CODE (type) != TYPE_CODE_STRUCT
+	       && TYPE_CODE (type) != TYPE_CODE_UNION)
+	      || !HAVE_CPLUS_STRUCT (type) || !TYPE_CPLUS_SPECIFIC (type));
+
+  xfree (TYPE_MAIN_TYPE (type));
+}
+
+/* Delete all the instances on TYPE_CHAIN of TYPE, including their referenced
+   main_type.  TYPE must be a reclaimable type - neither permanent nor objfile
+   associated.  */
+
+static void
+delete_type_chain (struct type *type)
+{
+  struct type *type_iter, *type_iter_to_free;
+
+  gdb_assert (TYPE_OBJFILE (type) == NULL);
+
+  delete_main_type (type);
+
+  type_iter = type;
+  do
+    {
+      type_iter_to_free = type_iter;
+      type_iter = TYPE_CHAIN (type_iter);
+      xfree (type_iter_to_free);
+    }
+  while (type_iter != type);
+}
+
 /* Hash function for type_group_link_table.  */
 
 static hashval_t
@@ -3225,6 +3470,35 @@ type_incref (struct type *type)
   found->group->use_count++;
 }
 
+/* A traverse callback for type_group_link_table which removes any
+   type_group_link whose reference count is now zero (unused link).  */
+
+static int
+type_group_link_remove (void **slot, void *unused)
+{
+  struct type_group_link *link = *slot;
+
+  if (link->group->use_count == 0)
+    {
+      struct type_group *group = link->group;
+
+      delete_type_chain (link->type);
+
+      /* The list `type_group->link_list' is left inconsistent during the
+	 traversal.  After free_all_types finishes the whole group will be
+	 deleted anyway.  */
+
+      gdb_assert (group->link_count > 0);
+      if (!--group->link_count)
+	xfree (group);
+
+      xfree (link);
+      htab_clear_slot (type_group_link_table, slot);
+    }
+
+  return 1;
+}
+
 /* Decrement the reference count for TYPE.  For permanent or objfile associated
    types nothing happens.  
 
@@ -3250,6 +3524,21 @@ type_decref (struct type *type)
   found->group->use_count--;
 }
 
+/* Free all the reclaimable types that have been allocated and that have
+   currently zero reference counter.
+
+   This function is called after each command, successful or not.  Use this
+   cleanup only in the GDB idle state as GDB code does not necessarily use
+   type_incref / type_decref during temporary use of types.  */
+
+void
+free_all_types (void)
+{
+  type_group_link_check ();
+
+  htab_traverse (type_group_link_table, type_group_link_remove, NULL);
+}
+
 static struct type *
 build_flt (int bit, char *name, const struct floatformat **floatformats)
 {
diff --git a/gdb/gdbtypes.h b/gdb/gdbtypes.h
index 41cd7a3..c698fce 100644
--- a/gdb/gdbtypes.h
+++ b/gdb/gdbtypes.h
@@ -1279,4 +1279,6 @@ extern void type_incref (struct type *type);
 
 extern void type_decref (struct type *type);
 
+extern void free_all_types (void);
+
 #endif /* GDBTYPES_H */
diff --git a/gdb/mi/mi-main.c b/gdb/mi/mi-main.c
index 74e8ab9..cf3127b 100644
--- a/gdb/mi/mi-main.c
+++ b/gdb/mi/mi-main.c
@@ -1332,6 +1332,7 @@ mi_cmd_execute (struct mi_parse *parse)
   int i;
 
   free_all_values ();
+  free_all_types ();
   cleanup = make_cleanup (null_cleanup, NULL);
 
   if (parse->frame != -1 && parse->thread == -1)
diff --git a/gdb/top.c b/gdb/top.c
index 3aff25f..fa9e9ab 100644
--- a/gdb/top.c
+++ b/gdb/top.c
@@ -377,6 +377,7 @@ execute_command (char *p, int from_tty)
     }
   
   free_all_values ();
+  free_all_types ();
 
   /* Force cleanup of any alloca areas if using C alloca instead of
      a builtin alloca.  */