This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]