[patch 6/8] Types GC [the GC itself]

[patch 6/8] Types GC [the GC itself]

[Jan Kratochvil]

Hi,

run the mark-and-sweep garbage collector.  Just without the next patch 7/8
there will be crashes as not all the GDB reclaimable types will be properly
being marked.

obsoletes:
	[patch] [2/5] Types reference counting [garbage-collector]
	http://sourceware.org/ml/gdb-patches/2009-04/msg00201.html


Thanks,
Jan

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

	Start garbage collecting unused types.
	* gdbtypes.c: Include observer.h.
	(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_mark_used, type_group_link_remove, free_all_types): New.
	* gdbtypes.h (type_mark_used, free_all_types): New prototypes.
	* mi-main.c (mi_cmd_execute): Call free_all_types.
	* top.c (execute_command): Likewise.
	* parse.c (exp_types_mark_used_iter, exp_types_mark_used): New.
	* parser-defs.h (exp_types_mark_used): New prototype.

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

	* gdbint.texinfo (Symbol Handling): New menu.
	(Partial Symbol Tables, Object File Formats, Debugging File Formats)
	(Adding a New Symbol Reader to GDB): New nodes from existing sections.
	(Types): New node from existing section.  New anchor `Builtin Types'.
	(Memory Management for Symbol Files): New node from existing section.
	Move types to ...
	(Memory Management for Types): ... here, in a new node.
	* observer.texi (mark_used): New.
---
 gdb/doc/gdbint.texinfo |   63 +++++++++-
 gdb/doc/observer.texi  |    5 +
 gdb/gdbtypes.c         |  314 ++++++++++++++++++++++++++++++++++++++++++++++++
 gdb/gdbtypes.h         |    4 +
 gdb/mi/mi-main.c       |    1 +
 gdb/parse.c            |   19 +++
 gdb/parser-defs.h      |    2 +
 gdb/top.c              |    1 +
 8 files changed, 405 insertions(+), 4 deletions(-)

diff --git a/gdb/doc/gdbint.texinfo b/gdb/doc/gdbint.texinfo
index c25a180..e0fff9a 100644
--- a/gdb/doc/gdbint.texinfo
+++ b/gdb/doc/gdbint.texinfo
@@ -2111,6 +2111,18 @@ time, and so we attempt to handle symbols incrementally.  For instance,
 we create @dfn{partial symbol tables} consisting of only selected
 symbols, and only expand them to full symbol tables when necessary.
 
+@menu
+* Symbol Reading::
+* Partial Symbol Tables::
+* Types::
+* Object File Formats::
+* Debugging File Formats::
+* Adding a New Symbol Reader to GDB::
+* Memory Management for Symbol Files::
+* Memory Management for Types::
+@end menu
+
+@node Symbol Reading
 @section Symbol Reading
 
 @cindex symbol reading
@@ -2203,6 +2215,7 @@ symtab.  Upon return, @code{pst->readin} should have been set to 1, and
 zero if there were no symbols in that part of the symbol file.
 @end table
 
+@node Partial Symbol Tables
 @section Partial Symbol Tables
 
 @value{GDBN} has three types of symbol tables:
@@ -2298,6 +2311,7 @@ and all the psymbols themselves are allocated in a pair of large arrays
 on an obstack, so there is little to be gained by trying to free them
 unless you want to do a lot more work.
 
+@node Types
 @section Types
 
 @unnumberedsubsec Fundamental Types (e.g., @code{FT_VOID}, @code{FT_BOOLEAN}).
@@ -2320,6 +2334,7 @@ types map to one @code{TYPE_CODE_*} type, and are distinguished by
 other members of the type struct, such as whether the type is signed
 or unsigned, and how many bits it uses.
 
+@anchor{Builtin Types}
 @unnumberedsubsec Builtin Types (e.g., @code{builtin_type_void}, @code{builtin_type_char}).
 
 These are instances of type structs that roughly correspond to
@@ -2334,6 +2349,7 @@ only one instance exists, while @file{c-lang.c} builds as many
 @code{TYPE_CODE_INT} types as needed, with each one associated with
 some particular objfile.
 
+@node Object File Formats
 @section Object File Formats
 @cindex object file formats
 
@@ -2419,6 +2435,7 @@ SOM, which is a cross-language ABI).
 
 The SOM reader is in @file{somread.c}.
 
+@node Debugging File Formats
 @section Debugging File Formats
 
 This section describes characteristics of debugging information that
@@ -2490,6 +2507,7 @@ DWARF 3 is an improved version of DWARF 2.
 @cindex SOM debugging info
 Like COFF, the SOM definition includes debugging information.
 
+@node Adding a New Symbol Reader to GDB
 @section Adding a New Symbol Reader to @value{GDBN}
 
 @cindex adding debugging info reader
@@ -2512,6 +2530,7 @@ will only ever be implemented by one object file format may be called
 directly.  This interface should be described in a file
 @file{bfd/lib@var{xyz}.h}, which is included by @value{GDBN}.
 
+@node Memory Management for Symbol Files
 @section Memory Management for Symbol Files
 
 Most memory associated with a loaded symbol file is stored on
@@ -2523,10 +2542,46 @@ released when the objfile is unloaded or reloaded.  Therefore one
 objfile must not reference symbol or type data from another objfile;
 they could be unloaded at different times.
 
-User convenience variables, et cetera, have associated types.  Normally
-these types live in the associated objfile.  However, when the objfile
-is unloaded, those types are deep copied to global memory, so that
-the values of the user variables and history items are not lost.
+@node Memory Management for Types
+@section Memory Management for Types
+@cindex memory management for types
+
+@findex TYPE_OBJFILE
+@code{TYPE_OBJFILE} macro indicates the current memory owner of the type.
+Non-@code{NULL} value indicates it is owned by an objfile (specifically by its
+obstack) and in such case the type remains valid till the objfile is unloaded
+or reloaded.  For such types with an associated objfile no additional memory
+management is being made.
+
+User convenience variables, et cetera, have associated types.  Normally these
+types live in the associated objfile.  However, when the objfile is unloaded,
+those types are deep copied to global memory, so that the values of the user
+variables and history items are not lost.  During the copy they will get their
+@code{TYPE_OBJFILE} set to @code{NULL} and become so-called @dfn{reclaimable}
+types.
+
+Types with null @code{TYPE_OBJFILE} can be either permanent types
+(@pxref{Builtin Types}) or reclaimable types which will be deallocated at the
+first idle @value{GDBN} moment if the last object referencing them is removed.
+Permanent types are allocated by the function @code{alloc_type} (and its
+derivations like @code{init_type}) specifying objfile as @code{NULL}.  The
+reclaimable types are created the same way but moreover they need to have
+@code{type_init_group} called to start their tracking as being possibly
+deallocatable.
+
+@findex free_all_types
+When @value{GDBN} gets idle it always calls the @code{free_all_types} function
+which deallocates any unused types.  All types currently not owned by an
+objfile must be marked as used on each @code{free_all_types} call as they would
+get deallocated as unused otherwise.  Use @code{observer_attach_mark_used} to
+register handler touching all the still used types by @code{type_mark_used}.
+
+@code{free_all_types} automatically checks for any cross-type references such
+as through @code{TYPE_TARGET_TYPE}, @code{TYPE_POINTER_TYPE} etc.@: and
+prevents early deallocation for any such existing references.  Reclaimable
+types may reference any other reclaimable types or even permanent types.  But
+permanent types must not reference reclaimable types (nor an objfile associated
+type).
 
 
 @node Language Support
diff --git a/gdb/doc/observer.texi b/gdb/doc/observer.texi
index 0aecd6d..999812b 100644
--- a/gdb/doc/observer.texi
+++ b/gdb/doc/observer.texi
@@ -215,6 +215,11 @@ Either @value{GDBN} detached from the inferior, or the inferior
 exited.  The argument @var{pid} identifies the inferior.
 @end deftypefun
 
+@deftypefun void mark_used (void)
+Mark any possibly reclaimable objects as used during a mark-and-sweep garbage
+collector pass.  Currently only @code{type_mark_used} marker is supported.
+@end deftypefun
+
  @deftypefun void test_notification (int @var{somearg})
 This observer is used for internal testing.  Do not use.  
 See testsuite/gdb.gdb/observer.exp.
diff --git a/gdb/gdbtypes.c b/gdb/gdbtypes.c
index 45c0538..97e37a0 100644
--- a/gdb/gdbtypes.c
+++ b/gdb/gdbtypes.c
@@ -38,6 +38,7 @@
 #include "cp-abi.h"
 #include "gdb_assert.h"
 #include "hashtab.h"
+#include "observer.h"
 
 /* These variables point to the objects
    representing the predefined C data types.  */
@@ -3204,6 +3205,319 @@ type_group_link_equal (const void *a, const void *b)
   return TYPE_MAIN_TYPE (left->type) == TYPE_MAIN_TYPE (right->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 "
+				  "link_count %d\n",
+		      type, TYPE_MAIN_TYPE (type),
+		      TYPE_NAME (type) ? TYPE_NAME (type) : "<null>",
+		      link->group, 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)
+{
+  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.  The reclaimability is not assertion checked here as it means an
+   expensive type_group_link_table lookup for each MAIN_TYPE being deleted.  */
+
+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);
+}
+
+/* Mark TYPE (and its whole TYPE_GROUP) as used in this free_all_types pass.  */
+
+void
+type_mark_used (struct type *type)
+{
+  struct type_group_link link_local, *link;
+
+  if (type == NULL)
+    return;
+
+  if (TYPE_OBJFILE (type) != NULL)
+    return;
+
+  link_local.type = type;
+  link = htab_find (type_group_link_table, &link_local);
+  /* A permanent type?  */
+  if (!link)
+    return;
+
+  link->group->age = type_group_age;
+}
+
+/* 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->age != type_group_age)
+    {
+      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;
+}
+
+/* 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 only marks those types used by
+   globally tracked objects (with no autovariable references tracking).  */
+
+void
+free_all_types (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 ();
+
+  observer_notify_mark_used ();
+
+  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 fc54acc..fb6f80f 100644
--- a/gdb/gdbtypes.h
+++ b/gdb/gdbtypes.h
@@ -1208,6 +1208,8 @@ extern int get_discrete_bounds (struct type *, LONGEST *, LONGEST *);
 
 extern int is_ancestor (struct type *, struct type *);
 
+extern void type_mark_used (struct type *type);
+
 /* Overload resolution */
 
 #define LENGTH_MATCH(bv) ((bv)->rank[0])
@@ -1276,4 +1278,6 @@ extern struct type *copy_type_recursive (struct objfile *objfile,
 
 extern struct type *copy_type (const 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/parse.c b/gdb/parse.c
index 0157122..3a04e28 100644
--- a/gdb/parse.c
+++ b/gdb/parse.c
@@ -1472,6 +1472,25 @@ exp_uses_objfile (struct expression *exp, struct objfile *objfile)
   return exp_iterate (exp, NULL, exp_uses_objfile_iter, objfile);
 }
 
+/* Helper for exp_types_mark_used.  */
+
+static int
+exp_types_mark_used_iter (struct type *type, void *unused)
+{
+  type_mark_used (type);
+
+  /* Continue the traversal.  */
+  return 0;
+}
+
+/* Call type_mark_used for any TYPE contained in EXP.  */
+
+void
+exp_types_mark_used (struct expression *exp)
+{
+  exp_iterate (exp, exp_types_mark_used_iter, NULL, NULL);
+}
+
 void
 _initialize_parse (void)
 {
diff --git a/gdb/parser-defs.h b/gdb/parser-defs.h
index 3159a21..5a8b3ee 100644
--- a/gdb/parser-defs.h
+++ b/gdb/parser-defs.h
@@ -301,4 +301,6 @@ extern void parser_fprintf (FILE *, const char *, ...) ATTR_FORMAT (printf, 2 ,3
 
 extern int exp_uses_objfile (struct expression *exp, struct objfile *objfile);
 
+extern void exp_types_mark_used (struct expression *exp);
+
 #endif /* PARSER_DEFS_H */
diff --git a/gdb/top.c b/gdb/top.c
index 7a10f7c..2ab854a 100644
--- a/gdb/top.c
+++ b/gdb/top.c
@@ -378,6 +378,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.  */
-- 
1.6.2.2

Re: [patch 6/8] Types GC [the GC itself]

[Eli Zaretskii]

> Date: Mon, 25 May 2009 10:03:23 +0200
> From: Jan Kratochvil <jan.kratochvil@redhat.com>
> 
> gdb/doc/
> 2009-05-25  Jan Kratochvil  <jan.kratochvil@redhat.com>
> 
> 	* gdbint.texinfo (Symbol Handling): New menu.
> 	(Partial Symbol Tables, Object File Formats, Debugging File Formats)
> 	(Adding a New Symbol Reader to GDB): New nodes from existing sections.
> 	(Types): New node from existing section.  New anchor `Builtin Types'.
> 	(Memory Management for Symbol Files): New node from existing section.
> 	Move types to ...
> 	(Memory Management for Types): ... here, in a new node.
> 	* observer.texi (mark_used): New.

Thanks.  I have a few comments about this part.

> +@code{TYPE_OBJFILE} macro indicates the current memory owner of the type.

 "The @code{TYPE_OBJFILE} macro ..."

> +Non-@code{NULL} value indicates it is owned by an objfile (specifically by its

 "A non-@code{NULL} value indicates ..."

> +User convenience variables, et cetera, have associated types.  Normally these

Can you spell out what is behind the "et cetera" here?  If the full
list is too long, naming just the most frequently used ones would be
good enough.

> +Types with null @code{TYPE_OBJFILE} can be either permanent types
> +(@pxref{Builtin Types}) or reclaimable types which will be deallocated at the
> +first idle @value{GDBN} moment if the last object referencing them is removed
.

I think "the first idle GDB moment after the last object ... is
removed" is more accurate.  "After" instead of "if".

> +Permanent types are allocated by the function @code{alloc_type} (and its
> +derivations like @code{init_type}) specifying objfile as @code{NULL}.  The
> +reclaimable types are created the same way but moreover they need to have
                                                  ^^^^^^^^
I think "in addition" is better here.

> +register handler touching all the still used types by @code{type_mark_used}.

 "to register a handler that will touch all the types still in use
 with a call to @code{type_mark_used}."

OK with those changes.

Re: [patch 6/8] Types GC [the GC itself]

[Jan Kratochvil]

On Mon, 25 May 2009 22:56:02 +0200, Eli Zaretskii wrote:
> I have a few comments about this part.

Updated according to your review.


> > +User convenience variables, et cetera, have associated types.  Normally these
> 
> Can you spell out what is behind the "et cetera" here?  If the full
> list is too long, naming just the most frequently used ones would be
> good enough.

Those cases are (fortunately) caught by:
	[patch 7/8] Types GC [GC markers]
	http://sourceware.org/ml/gdb-patches/2009-05/msg00550.html
plus varobjs in the patch 8/8. 

Named some of these in the new text:
+User convenience variables, inferior symbols or breakpoint conditions have
+associated types.  [...]


No code part was changed.


Thanks,
Jan


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

	Start garbage collecting unused types.
	* gdbtypes.c: Include observer.h.
	(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_mark_used, type_group_link_remove, free_all_types): New.
	* gdbtypes.h (type_mark_used, free_all_types): New prototypes.
	* mi-main.c (mi_cmd_execute): Call free_all_types.
	* top.c (execute_command): Likewise.
	* parse.c (exp_types_mark_used_iter, exp_types_mark_used): New.
	* parser-defs.h (exp_types_mark_used): New prototype.

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

	* gdbint.texinfo (Symbol Handling): New menu.
	(Partial Symbol Tables, Object File Formats, Debugging File Formats)
	(Adding a New Symbol Reader to GDB): New nodes from existing sections.
	(Types): New node from existing section.  New anchor `Builtin Types'.
	(Memory Management for Symbol Files): New node from existing section.
	Move types to ...
	(Memory Management for Types): ... here, in a new node.
	* observer.texi (mark_used): New.

diff --git a/gdb/doc/gdbint.texinfo b/gdb/doc/gdbint.texinfo
index c25a180..3daf650 100644
--- a/gdb/doc/gdbint.texinfo
+++ b/gdb/doc/gdbint.texinfo
@@ -2111,6 +2111,18 @@ time, and so we attempt to handle symbols incrementally.  For instance,
 we create @dfn{partial symbol tables} consisting of only selected
 symbols, and only expand them to full symbol tables when necessary.
 
+@menu
+* Symbol Reading::
+* Partial Symbol Tables::
+* Types::
+* Object File Formats::
+* Debugging File Formats::
+* Adding a New Symbol Reader to GDB::
+* Memory Management for Symbol Files::
+* Memory Management for Types::
+@end menu
+
+@node Symbol Reading
 @section Symbol Reading
 
 @cindex symbol reading
@@ -2203,6 +2215,7 @@ symtab.  Upon return, @code{pst->readin} should have been set to 1, and
 zero if there were no symbols in that part of the symbol file.
 @end table
 
+@node Partial Symbol Tables
 @section Partial Symbol Tables
 
 @value{GDBN} has three types of symbol tables:
@@ -2298,6 +2311,7 @@ and all the psymbols themselves are allocated in a pair of large arrays
 on an obstack, so there is little to be gained by trying to free them
 unless you want to do a lot more work.
 
+@node Types
 @section Types
 
 @unnumberedsubsec Fundamental Types (e.g., @code{FT_VOID}, @code{FT_BOOLEAN}).
@@ -2320,6 +2334,7 @@ types map to one @code{TYPE_CODE_*} type, and are distinguished by
 other members of the type struct, such as whether the type is signed
 or unsigned, and how many bits it uses.
 
+@anchor{Builtin Types}
 @unnumberedsubsec Builtin Types (e.g., @code{builtin_type_void}, @code{builtin_type_char}).
 
 These are instances of type structs that roughly correspond to
@@ -2334,6 +2349,7 @@ only one instance exists, while @file{c-lang.c} builds as many
 @code{TYPE_CODE_INT} types as needed, with each one associated with
 some particular objfile.
 
+@node Object File Formats
 @section Object File Formats
 @cindex object file formats
 
@@ -2419,6 +2435,7 @@ SOM, which is a cross-language ABI).
 
 The SOM reader is in @file{somread.c}.
 
+@node Debugging File Formats
 @section Debugging File Formats
 
 This section describes characteristics of debugging information that
@@ -2490,6 +2507,7 @@ DWARF 3 is an improved version of DWARF 2.
 @cindex SOM debugging info
 Like COFF, the SOM definition includes debugging information.
 
+@node Adding a New Symbol Reader to GDB
 @section Adding a New Symbol Reader to @value{GDBN}
 
 @cindex adding debugging info reader
@@ -2512,6 +2530,7 @@ will only ever be implemented by one object file format may be called
 directly.  This interface should be described in a file
 @file{bfd/lib@var{xyz}.h}, which is included by @value{GDBN}.
 
+@node Memory Management for Symbol Files
 @section Memory Management for Symbol Files
 
 Most memory associated with a loaded symbol file is stored on
@@ -2523,10 +2542,47 @@ released when the objfile is unloaded or reloaded.  Therefore one
 objfile must not reference symbol or type data from another objfile;
 they could be unloaded at different times.
 
-User convenience variables, et cetera, have associated types.  Normally
-these types live in the associated objfile.  However, when the objfile
-is unloaded, those types are deep copied to global memory, so that
-the values of the user variables and history items are not lost.
+@node Memory Management for Types
+@section Memory Management for Types
+@cindex memory management for types
+
+@findex TYPE_OBJFILE
+The @code{TYPE_OBJFILE} macro indicates the current memory owner of the type.
+A non-@code{NULL} value indicates it is owned by an objfile (specifically by
+its obstack) and in such case the type remains valid till the objfile is
+unloaded or reloaded.  For such types with an associated objfile no additional
+memory management is being made.
+
+User convenience variables, inferior symbols or breakpoint conditions have
+associated types.  Normally these types live in the associated objfile.
+However, when the objfile is unloaded, those types are deep copied to global
+memory, so that the values of the user variables and history items are not
+lost.  During the copy they will get their @code{TYPE_OBJFILE} set to
+@code{NULL} and become so-called @dfn{reclaimable} types.
+
+Types with null @code{TYPE_OBJFILE} can be either permanent types
+(@pxref{Builtin Types}) or reclaimable types which will be deallocated at the
+first idle @value{GDBN} moment after the last object referencing them is
+removed.  Permanent types are allocated by the function @code{alloc_type} (and
+its derivations like @code{init_type}) specifying objfile as @code{NULL}.
+The reclaimable types are created the same way but in addition they need to
+have @code{type_init_group} called to start their tracking as being possibly
+deallocatable.
+
+@findex free_all_types
+When @value{GDBN} gets idle it always calls the @code{free_all_types} function
+which deallocates any unused types.  All types currently not owned by an
+objfile must be marked as used on each @code{free_all_types} call as they would
+get deallocated as unused otherwise.  Use @code{observer_attach_mark_used} to
+register a handler that will touch all the types still in use with a call to
+@code{type_mark_used}.
+
+@code{free_all_types} automatically checks for any cross-type references such
+as through @code{TYPE_TARGET_TYPE}, @code{TYPE_POINTER_TYPE} etc.@: and
+prevents early deallocation for any such existing references.  Reclaimable
+types may reference any other reclaimable types or even permanent types.  But
+permanent types must not reference reclaimable types (nor an objfile associated
+type).
 
 
 @node Language Support
diff --git a/gdb/doc/observer.texi b/gdb/doc/observer.texi
index 0aecd6d..999812b 100644
--- a/gdb/doc/observer.texi
+++ b/gdb/doc/observer.texi
@@ -215,6 +215,11 @@ Either @value{GDBN} detached from the inferior, or the inferior
 exited.  The argument @var{pid} identifies the inferior.
 @end deftypefun
 
+@deftypefun void mark_used (void)
+Mark any possibly reclaimable objects as used during a mark-and-sweep garbage
+collector pass.  Currently only @code{type_mark_used} marker is supported.
+@end deftypefun
+
  @deftypefun void test_notification (int @var{somearg})
 This observer is used for internal testing.  Do not use.  
 See testsuite/gdb.gdb/observer.exp.
diff --git a/gdb/gdbtypes.c b/gdb/gdbtypes.c
index 45c0538..97e37a0 100644
--- a/gdb/gdbtypes.c
+++ b/gdb/gdbtypes.c
@@ -38,6 +38,7 @@
 #include "cp-abi.h"
 #include "gdb_assert.h"
 #include "hashtab.h"
+#include "observer.h"
 
 /* These variables point to the objects
    representing the predefined C data types.  */
@@ -3204,6 +3205,319 @@ type_group_link_equal (const void *a, const void *b)
   return TYPE_MAIN_TYPE (left->type) == TYPE_MAIN_TYPE (right->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 "
+				  "link_count %d\n",
+		      type, TYPE_MAIN_TYPE (type),
+		      TYPE_NAME (type) ? TYPE_NAME (type) : "<null>",
+		      link->group, 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)
+{
+  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.  The reclaimability is not assertion checked here as it means an
+   expensive type_group_link_table lookup for each MAIN_TYPE being deleted.  */
+
+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);
+}
+
+/* Mark TYPE (and its whole TYPE_GROUP) as used in this free_all_types pass.  */
+
+void
+type_mark_used (struct type *type)
+{
+  struct type_group_link link_local, *link;
+
+  if (type == NULL)
+    return;
+
+  if (TYPE_OBJFILE (type) != NULL)
+    return;
+
+  link_local.type = type;
+  link = htab_find (type_group_link_table, &link_local);
+  /* A permanent type?  */
+  if (!link)
+    return;
+
+  link->group->age = type_group_age;
+}
+
+/* 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->age != type_group_age)
+    {
+      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;
+}
+
+/* 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 only marks those types used by
+   globally tracked objects (with no autovariable references tracking).  */
+
+void
+free_all_types (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 ();
+
+  observer_notify_mark_used ();
+
+  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 fc54acc..fb6f80f 100644
--- a/gdb/gdbtypes.h
+++ b/gdb/gdbtypes.h
@@ -1208,6 +1208,8 @@ extern int get_discrete_bounds (struct type *, LONGEST *, LONGEST *);
 
 extern int is_ancestor (struct type *, struct type *);
 
+extern void type_mark_used (struct type *type);
+
 /* Overload resolution */
 
 #define LENGTH_MATCH(bv) ((bv)->rank[0])
@@ -1276,4 +1278,6 @@ extern struct type *copy_type_recursive (struct objfile *objfile,
 
 extern struct type *copy_type (const 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/parse.c b/gdb/parse.c
index 0157122..3a04e28 100644
--- a/gdb/parse.c
+++ b/gdb/parse.c
@@ -1472,6 +1472,25 @@ exp_uses_objfile (struct expression *exp, struct objfile *objfile)
   return exp_iterate (exp, NULL, exp_uses_objfile_iter, objfile);
 }
 
+/* Helper for exp_types_mark_used.  */
+
+static int
+exp_types_mark_used_iter (struct type *type, void *unused)
+{
+  type_mark_used (type);
+
+  /* Continue the traversal.  */
+  return 0;
+}
+
+/* Call type_mark_used for any TYPE contained in EXP.  */
+
+void
+exp_types_mark_used (struct expression *exp)
+{
+  exp_iterate (exp, exp_types_mark_used_iter, NULL, NULL);
+}
+
 void
 _initialize_parse (void)
 {
diff --git a/gdb/parser-defs.h b/gdb/parser-defs.h
index 3159a21..5a8b3ee 100644
--- a/gdb/parser-defs.h
+++ b/gdb/parser-defs.h
@@ -301,4 +301,6 @@ extern void parser_fprintf (FILE *, const char *, ...) ATTR_FORMAT (printf, 2 ,3
 
 extern int exp_uses_objfile (struct expression *exp, struct objfile *objfile);
 
+extern void exp_types_mark_used (struct expression *exp);
+
 #endif /* PARSER_DEFS_H */
diff --git a/gdb/top.c b/gdb/top.c
index 7a10f7c..2ab854a 100644
--- a/gdb/top.c
+++ b/gdb/top.c
@@ -378,6 +378,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.  */

Re: [patch 6/8] Types GC [the GC itself]

[Eli Zaretskii]

> Date: Tue, 26 May 2009 20:15:08 +0200
> From: Jan Kratochvil <jan.kratochvil@redhat.com>
> Cc: gdb-patches@sourceware.org
> 
> On Mon, 25 May 2009 22:56:02 +0200, Eli Zaretskii wrote:
> > I have a few comments about this part.
> 
> Updated according to your review.

Thanks, I'm happy now.

Re: [patch 6/8] Types GC [the GC itself]

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Jan> run the mark-and-sweep garbage collector.  Just without the next
Jan> patch 7/8 there will be crashes as not all the GDB reclaimable
Jan> types will be properly being marked.

This seems reasonable to me.  I have a couple nits though.

Jan> +/* A traverse callback for type_group_link_table which removes any
Jan> +   type_group_link whose reference count is now zero (unused link).  */

Why bother with reference counts?

Jan> +void
Jan> +exp_types_mark_used (struct expression *exp)
Jan> +{
Jan> +  exp_iterate (exp, exp_types_mark_used_iter, NULL, NULL);
Jan> +}

This is not called anywhere with this patch.  I didn't check later
patches yet, so just ignore this if it is called later.

Tom