[patch 5/8] Types GC [type_group framework]

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

Hi,

start tracking which types are reclaimable and tracking how they are
interconnected.  Any utilization of this infrastructure gets implemented by the
patch 6/8 (+7/8).

obsoletes:
	Re: [patch] [1/5] Types reference counting [base]
	http://sourceware.org/ml/gdb-patches/2009-04/msg00215.html


Thanks,
Jan

gdb/
2009-05-25  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* gdbtypes.c (struct type_group, struct type_group_link)
	(type_group_link_table, type_group_age, alloc_type_discardable)
	(alloc_type_as_parent, type_init_group, type_group_link_hash)
	(type_group_link_equal): New.
	(make_pointer_type, make_reference_type): Call alloc_type_as_parent.
	(_initialize_gdbtypes): Initialize `type_group_link_table'.
---
 gdb/gdbtypes.c |  144 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 142 insertions(+), 2 deletions(-)

diff --git a/gdb/gdbtypes.c b/gdb/gdbtypes.c
index f415773..45c0538 100644
--- a/gdb/gdbtypes.c
+++ b/gdb/gdbtypes.c
@@ -146,7 +146,56 @@ static void print_bit_vector (B_TYPE *, int);
 static void print_arg_types (struct field *, int, int);
 static void dump_fn_fieldlists (struct type *, int);
 static void print_cplus_stuff (struct type *, int);
+static void type_init_group (struct type *type);
 
+/* Any type structures which are connected through their `struct type *' are
+   tracked by the same type_group.  Only the discardable (neither permanent
+   types nor types allocated from objfile obstack) type structures get tracked
+   by type_group structures.  */
+
+struct type_group
+{
+  /* Marker this type_group has been visited by the type_mark_used by this
+     pass.  Current pass is represented by TYPE_GROUP_AGE.  */
+  unsigned age : 1;
+
+  /* Number of the type_group_links structures tracked by this type_group.  It
+     matches the length of list `link_list->group_next->...->group_next'.  */
+  int link_count;
+
+  /* Head of an unordered list of all type structures of this type_group.  Next
+     items are linked by `type_group_link->group_next'.  */
+  struct type_group_link *link_list;
+};
+
+/* Linking entry between a type structure and type_group structure.  Only
+   discardable types have such link present.  This link exists only once for
+   each discardable main_type, all type instances for such one main_type should
+   be iterated by `TYPE_CHAIN (type_group_link->type)'.  */
+
+struct type_group_link
+{
+  /* Arbitrary type for main_type being represented by this type_group_link.
+     Each discardable main_type gets its separate type_group_link.  */
+  struct type *type;
+
+  /* Marker this type_group_link has been visited by the type_group_link_check
+     graph traversal by this pass.  Current pass is represented by
+     TYPE_GROUP_AGE.  */
+  unsigned age : 1;
+
+  struct type_group *group;
+
+  /* Next type_group_link belonging to this type_group structure or NULL for
+     the last node of the list.  */
+  struct type_group_link *group_next;
+};
+
+/* The hash table holding all `struct type_group_link *' references.  */
+static htab_t type_group_link_table;
+
+/* Current type_group_link_check pass used for `type_group_link->age'.  */
+static unsigned type_group_age;
 
 /* Alloc a new type structure and fill it with some defaults.  If
    OBJFILE is non-NULL, then allocate the space for the type structure
@@ -183,6 +232,43 @@ alloc_type (struct objfile *objfile)
   return type;
 }
 
+/* Allocate a new type by an alloc_type call but make the new type discardable
+   on next garbage collection by free_all_types.  You must call type_mark_used
+   during each free_all_types to protect TYPE from being deallocated.  */
+
+static struct type *
+alloc_type_discardable (void)
+{
+  struct type *type = alloc_type (NULL);
+
+  type_init_group (type);
+
+  return type;
+}
+
+/* Allocate a new type like alloc_type or alloc_type_discardable copying the
+   discardability state of PARENT_TYPE (its current reference count
+   notwithstanding).  */
+
+static struct type *
+alloc_type_as_parent (struct type *parent_type)
+{
+  struct type *type = alloc_type (TYPE_OBJFILE (parent_type));
+
+  if (TYPE_OBJFILE (parent_type) == NULL)
+    {
+      struct type_group_link link, *found;
+
+      link.type = type;
+      found = htab_find (type_group_link_table, &link);
+      /* Not a permanent type?  */
+      if (found)
+	type_init_group (type);
+    }
+
+  return type;
+}
+
 /* Alloc a new type instance structure, fill it with some defaults,
    and point it at OLDTYPE.  Allocate the new type instance from the
    same place as OLDTYPE.  */
@@ -248,7 +334,7 @@ make_pointer_type (struct type *type, struct type **typeptr)
 
   if (typeptr == 0 || *typeptr == 0)	/* We'll need to allocate one.  */
     {
-      ntype = alloc_type (TYPE_OBJFILE (type));
+      ntype = alloc_type_as_parent (type);
       if (typeptr)
 	*typeptr = ntype;
     }
@@ -328,7 +414,7 @@ make_reference_type (struct type *type, struct type **typeptr)
 
   if (typeptr == 0 || *typeptr == 0)	/* We'll need to allocate one.  */
     {
-      ntype = alloc_type (TYPE_OBJFILE (type));
+      ntype = alloc_type_as_parent (type);
       if (typeptr)
 	*typeptr = ntype;
     }
@@ -3068,6 +3154,56 @@ copy_type (const struct type *type)
   return new_type;
 }
 
+/* Define currently permanent TYPE as being reclaimable during free_all_types.
+   TYPE is required to be now permanent.  */
+
+static void
+type_init_group (struct type *type)
+{
+  void **slot;
+  struct type_group *group;
+  struct type_group_link *link;
+
+  gdb_assert (TYPE_OBJFILE (type) == NULL);
+
+  group = XNEW (struct type_group);
+  link = XNEW (struct type_group_link);
+
+  group->age = type_group_age;
+  group->link_count = 1;
+  group->link_list = link;
+
+  link->type = type;
+  link->age = type_group_age;
+  link->group = group;
+  link->group_next = NULL;
+
+  slot = htab_find_slot (type_group_link_table, link, INSERT);
+  gdb_assert (!*slot);
+  *slot = link;
+}
+
+/* Hash function for type_group_link_table.  */
+
+static hashval_t
+type_group_link_hash (const void *p)
+{
+  const struct type_group_link *link = p;
+
+  return htab_hash_pointer (TYPE_MAIN_TYPE (link->type));
+}
+
+/* Equality function for type_group_link_table.  */
+
+static int
+type_group_link_equal (const void *a, const void *b)
+{
+  const struct type_group_link *left = a;
+  const struct type_group_link *right = b;
+
+  return TYPE_MAIN_TYPE (left->type) == TYPE_MAIN_TYPE (right->type);
+}
+
 static struct type *
 build_flt (int bit, char *name, const struct floatformat **floatformats)
 {
@@ -3276,6 +3412,10 @@ _initialize_gdbtypes (void)
 {
   gdbtypes_data = gdbarch_data_register_post_init (gdbtypes_post_init);
 
+  type_group_link_table = htab_create_alloc (20, type_group_link_hash,
+					     type_group_link_equal, NULL,
+					     xcalloc, xfree);
+
   /* FIXME: The following types are architecture-neutral.  However,
      they contain pointer_type and reference_type fields potentially
      caching pointer or reference types that *are* architecture
-- 
1.6.2.2