/* Simple garbage collection for the GNU compiler.
- Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
- This file is part of GNU CC.
+ This file is part of GCC.
- GNU CC is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
- GNU CC is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ License for more details.
You should have received a copy of the GNU General Public License
- along with GNU CC; see the file COPYING. If not, write to
- the Free Software Foundation, 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA. */
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tree.h"
-#include "ggc.h"
+#include "tm_p.h"
#include "flags.h"
#include "varray.h"
-#include "hash.h"
+#include "ggc.h"
+#include "timevar.h"
/* Debugging flags. */
/* Zap memory before freeing to catch dangling pointers. */
#define GGC_POISON
-/* Log alloc and release. Don't enable this unless you want a
- really really lot of data. */
-#undef GGC_DUMP
+/* Collect statistics on how bushy the search tree is. */
+#undef GGC_BALANCE
-/* Some magic tags for strings and anonymous memory, hoping to catch
- certain errors wrt marking memory. */
+/* Perform collection every time ggc_collect is invoked. Otherwise,
+ collection is performed only when a significant amount of memory
+ has been allocated since the last collection. */
+#undef GGC_ALWAYS_COLLECT
-#define IS_MARKED(X) ((X) & 1)
-#define IGNORE_MARK(X) ((X) & -2)
+/* Always verify that the to-be-marked memory is collectable. */
+#undef GGC_ALWAYS_VERIFY
-#define GGC_STRING_MAGIC ((unsigned int)0xa1b2c3d4)
-#define GGC_STRING_MAGIC_MARK ((unsigned int)0xa1b2c3d4 | 1)
+#ifdef ENABLE_GC_CHECKING
+#define GGC_POISON
+#define GGC_ALWAYS_VERIFY
+#endif
+#ifdef ENABLE_GC_ALWAYS_COLLECT
+#define GGC_ALWAYS_COLLECT
+#endif
-#define GGC_ANY_MAGIC ((unsigned int)0xa9bacbdc)
-#define GGC_ANY_MAGIC_MARK ((unsigned int)0xa9bacbdc | 1)
+#ifndef HOST_BITS_PER_PTR
+#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
+#endif
-/* Global lists of roots, rtxs, and trees. */
+/* We'd like a balanced tree, but we don't really want to pay for the
+ cost of keeping the tree balanced. We'll settle for the next best
+ thing -- nearly balanced.
-struct ggc_rtx
-{
- struct ggc_rtx *chain;
- struct rtx_def rtx;
-};
+ In this context, the most natural key is the node pointer itself,
+ but due to the way memory managers work, we'd be virtually certain
+ to wind up with a completely degenerate straight line. What's needed
+ is to make something more variable, and yet predictable, be more
+ significant in the comparison.
-struct ggc_rtvec
-{
- struct ggc_rtvec *chain;
- struct rtvec_def vec;
-};
+ The handiest source of variability is the low bits of the pointer
+ value itself. Any sort of bit/byte swap would do, but such machine
+ specific operations are not handy, and we don't want to put that much
+ effort into it. */
-struct ggc_tree
-{
- struct ggc_tree *chain;
- union tree_node tree;
-};
+#define PTR_KEY(p) ((size_t)p << (HOST_BITS_PER_PTR - 8) \
+ | ((size_t)p & 0xff00) << (HOST_BITS_PER_PTR - 24) \
+ | (size_t)p >> 16)
-struct ggc_string
-{
- struct ggc_string *chain;
- unsigned int magic_mark;
- char string[1];
-};
-
-/* A generic allocation, with an external mark bit. */
+/* GC'able memory; a node in a binary search tree. */
-struct ggc_any
+struct ggc_mem
{
- struct ggc_any *chain;
- unsigned int magic_mark;
+ /* A combination of the standard left/right nodes, indexable by `<'. */
+ struct ggc_mem *sub[2];
+
+ unsigned int mark : 1;
+ unsigned int context : 7;
+ unsigned int size : 24;
/* Make sure the data is reasonably aligned. */
union {
- char c;
- HOST_WIDE_INT i;
+ HOST_WIDEST_INT i;
+#ifdef HAVE_LONG_DOUBLE
long double d;
+#else
+ double d;
+#endif
} u;
};
-struct ggc_status
+static struct globals
{
- struct ggc_status *next;
- struct ggc_rtx *rtxs;
- struct ggc_rtvec *vecs;
- struct ggc_tree *trees;
- struct ggc_string *strings;
- struct ggc_any *anys;
- size_t bytes_alloced_since_gc;
-};
+ /* Root of the object tree. */
+ struct ggc_mem *root;
-/* A chain of GGC contexts. The currently active context is at the
- front of the chain. */
-static struct ggc_status *ggc_chain;
+ /* Data bytes currently allocated. */
+ size_t allocated;
-/* Some statistics. */
+ /* Data objects currently allocated. */
+ size_t objects;
-static int n_rtxs_collected;
-static int n_vecs_collected;
-static int n_trees_collected;
-static int n_strings_collected;
-static int n_anys_collected;
-extern int gc_time;
+ /* Data bytes allocated at time of last GC. */
+ size_t allocated_last_gc;
-#ifdef GGC_DUMP
-static FILE *dump;
-#endif
+ /* Current context level. */
+ int context;
+} G;
-/* Local function prototypes. */
+/* Skip garbage collection if the current allocation is not at least
+ this factor times the allocation at the end of the last collection.
+ In other words, total allocation must expand by (this factor minus
+ one) before collection is performed. */
+#define GGC_MIN_EXPAND_FOR_GC (1.3)
-static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
-static void ggc_free_rtvec PROTO ((struct ggc_rtvec *v));
-static void ggc_free_tree PROTO ((struct ggc_tree *t));
-static void ggc_free_string PROTO ((struct ggc_string *s));
-static void ggc_free_any PROTO ((struct ggc_any *a));
+/* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
+ test from triggering too often when the heap is small. */
+#define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
-/* Called once to initialize the garbage collector. */
-
-void
-init_ggc PROTO ((void))
-{
- /* Initialize the global context. */
- ggc_push_context ();
+/* Local function prototypes. */
-#ifdef GGC_DUMP
- dump = fopen ("zgcdump", "w");
- setlinebuf (dump);
-#endif
-}
+static void tree_insert PARAMS ((struct ggc_mem *));
+static int tree_lookup PARAMS ((struct ggc_mem *));
+static void clear_marks PARAMS ((struct ggc_mem *));
+static void sweep_objs PARAMS ((struct ggc_mem **));
+static void ggc_pop_context_1 PARAMS ((struct ggc_mem *, int));
-/* Start a new GGC context. Memory allocated in previous contexts
- will not be collected while the new context is active. */
+/* For use from debugger. */
+extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
-void
-ggc_push_context PROTO ((void))
-{
- struct ggc_status *gs = (struct ggc_status *) xcalloc (1, sizeof (*gs));
- gs->next = ggc_chain;
- ggc_chain = gs;
-}
+#ifdef GGC_BALANCE
+extern void debug_ggc_balance PARAMS ((void));
+#endif
+static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
-/* Finish a GC context. Any uncollected memory in the new context
- will be merged with the old context. */
+/* Insert V into the search tree. */
-void
-ggc_pop_context PROTO ((void))
+static inline void
+tree_insert (v)
+ struct ggc_mem *v;
{
- struct ggc_rtx *r;
- struct ggc_rtvec *v;
- struct ggc_tree *t;
- struct ggc_string *s;
- struct ggc_status *gs;
-
- gs = ggc_chain;
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p, **pp;
- r = gs->rtxs;
- if (r)
+ for (pp = &G.root, p = *pp; p ; p = *pp)
{
- while (r->chain)
- r = r->chain;
- r->chain = gs->next->rtxs;
- gs->next->rtxs = gs->rtxs;
- }
-
- v = gs->vecs;
- if (v)
- {
- while (v->chain)
- v = v->chain;
- v->chain = gs->next->vecs;
- gs->next->vecs = gs->vecs;
+ size_t p_key = PTR_KEY (p);
+ pp = &p->sub[v_key < p_key];
}
+ *pp = v;
+}
- t = gs->trees;
- if (t)
- {
- while (t->chain)
- t = t->chain;
- t->chain = gs->next->trees;
- gs->next->trees = gs->trees;
- }
+/* Return true if V is in the tree. */
- s = gs->strings;
- if (s)
+static inline int
+tree_lookup (v)
+ struct ggc_mem *v;
+{
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p = G.root;
+
+ while (p)
{
- while (s->chain)
- s = s->chain;
- s->chain = gs->next->strings;
- gs->next->strings = gs->strings;
+ size_t p_key = PTR_KEY (p);
+ if (p == v)
+ return 1;
+ p = p->sub[v_key < p_key];
}
- gs->next->bytes_alloced_since_gc += gs->bytes_alloced_since_gc;
-
- ggc_chain = gs->next;
- free (gs);
+ return 0;
}
-/* These allocators are dreadfully simple, with no caching whatsoever so
- that Purify-like tools that do allocation versioning can catch errors.
- This collector is never going to go fast anyway. */
+/* Alloc SIZE bytes of GC'able memory. If ZERO, clear the memory. */
-rtx
-ggc_alloc_rtx (nslots)
- int nslots;
+void *
+ggc_alloc (size)
+ size_t size;
{
- struct ggc_rtx *n;
- int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
+ struct ggc_mem *x;
- n = (struct ggc_rtx *) xcalloc (1, size);
- n->chain = ggc_chain->rtxs;
- ggc_chain->rtxs = n;
+ x = (struct ggc_mem *) xmalloc (offsetof (struct ggc_mem, u) + size);
+ x->sub[0] = NULL;
+ x->sub[1] = NULL;
+ x->mark = 0;
+ x->context = G.context;
+ x->size = size;
-#ifdef GGC_DUMP
- fprintf (dump, "alloc rtx %p\n", &n->rtx);
+#ifdef GGC_POISON
+ memset (&x->u, 0xaf, size);
#endif
- ggc_chain->bytes_alloced_since_gc += size;
+ tree_insert (x);
+ G.allocated += size;
+ G.objects += 1;
- return &n->rtx;
+ return &x->u;
}
-rtvec
-ggc_alloc_rtvec (nelt)
- int nelt;
-{
- struct ggc_rtvec *v;
- int size = sizeof (*v) + (nelt - 1) * sizeof (rtx);
-
- v = (struct ggc_rtvec *) xcalloc (1, size);
- v->chain = ggc_chain->vecs;
- ggc_chain->vecs = v;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc vec %p\n", &v->vec);
-#endif
-
- ggc_chain->bytes_alloced_since_gc += size;
-
- return &v->vec;
-}
+/* Mark a node. */
-tree
-ggc_alloc_tree (length)
- int length;
+int
+ggc_set_mark (p)
+ const void *p;
{
- struct ggc_tree *n;
- int size = sizeof(*n) - sizeof(n->tree) + length;
-
- n = (struct ggc_tree *) xcalloc (1, size);
- n->chain = ggc_chain->trees;
- ggc_chain->trees = n;
+ struct ggc_mem *x;
-#ifdef GGC_DUMP
- fprintf(dump, "alloc tree %p\n", &n->tree);
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
#endif
- ggc_chain->bytes_alloced_since_gc += size;
-
- return &n->tree;
-}
+ if (x->mark)
+ return 1;
-char *
-ggc_alloc_string (contents, length)
- const char *contents;
- int length;
-{
- struct ggc_string *s;
- int size;
+ x->mark = 1;
+ G.allocated += x->size;
+ G.objects += 1;
- if (length < 0)
- {
- if (contents == NULL)
- return NULL;
- length = strlen (contents);
- }
+ return 0;
+}
- size = (s->string - (char *)s) + length + 1;
- s = (struct ggc_string *) xmalloc (size);
- s->chain = ggc_chain->strings;
- s->magic_mark = GGC_STRING_MAGIC;
- ggc_chain->strings = s;
+/* Return 1 if P has been marked, zero otherwise. */
- if (contents)
- memcpy (s->string, contents, length);
- s->string[length] = 0;
+int
+ggc_marked_p (p)
+ const void *p;
+{
+ struct ggc_mem *x;
-#ifdef GGC_DUMP
- fprintf(dump, "alloc string %p\n", &s->string);
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
#endif
- ggc_chain->bytes_alloced_since_gc += size;
-
- return s->string;
+ return x->mark;
}
-/* Like xmalloc, but allocates GC-able memory. */
+/* Return the size of the gc-able object P. */
-void *
-ggc_alloc (bytes)
- size_t bytes;
+size_t
+ggc_get_size (p)
+ const void *p;
{
- struct ggc_any *a;
-
- if (bytes == 0)
- bytes = 1;
- bytes += (&((struct ggc_any *) 0)->u.c - (char *) 0);
-
- a = (struct ggc_any *) xmalloc (bytes);
- a->chain = ggc_chain->anys;
- a->magic_mark = GGC_ANY_MAGIC;
- ggc_chain->anys = a;
-
- ggc_chain->bytes_alloced_since_gc += bytes;
-
- return &a->u;
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ return x->size;
}
-/* Freeing a bit of rtl is as simple as calling free. */
+/* Unmark all objects. */
-static inline void
-ggc_free_rtx (r)
- struct ggc_rtx *r;
+static void
+clear_marks (x)
+ struct ggc_mem *x;
{
-#ifdef GGC_DUMP
- fprintf (dump, "collect rtx %p\n", &r->rtx);
-#endif
-#ifdef GGC_POISON
- memset (r, 0xAA, sizeof(*r) + ((GET_RTX_LENGTH (r->rtx.code) -1)
- * sizeof(rtunion)));
-#endif
-
- free (r);
+ x->mark = 0;
+ if (x->sub[0])
+ clear_marks (x->sub[0]);
+ if (x->sub[1])
+ clear_marks (x->sub[1]);
}
-/* Freeing an rtvec is as simple as calling free. */
+/* Free all objects in the current context that are not marked. */
-static inline void
-ggc_free_rtvec (v)
- struct ggc_rtvec *v;
+static void
+sweep_objs (root)
+ struct ggc_mem **root;
{
-#ifdef GGC_DUMP
- fprintf(dump, "collect vec %p\n", &v->vec);
-#endif
-#ifdef GGC_POISON
- memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
- * sizeof (rtunion)));
-#endif
+ struct ggc_mem *x = *root;
+ if (!x)
+ return;
- free (v);
-}
+ sweep_objs (&x->sub[0]);
+ sweep_objs (&x->sub[1]);
-/* Freeing a tree node is almost, but not quite, as simple as calling free.
- Mostly we need to let the language clean up its lang_specific bits. */
+ if (! x->mark && x->context >= G.context)
+ {
+ struct ggc_mem *l, *r;
+
+ l = x->sub[0];
+ r = x->sub[1];
+ if (!l)
+ *root = r;
+ else if (!r)
+ *root = l;
+ else if (!l->sub[1])
+ {
+ *root = l;
+ l->sub[1] = r;
+ }
+ else if (!r->sub[0])
+ {
+ *root = r;
+ r->sub[0] = l;
+ }
+ else
+ {
+ *root = l;
+ do {
+ root = &l->sub[1];
+ } while ((l = *root) != NULL);
+ *root = r;
+ }
-static inline void
-ggc_free_tree (t)
- struct ggc_tree *t;
-{
-#ifdef GGC_DUMP
- fprintf (dump, "collect tree %p\n", &t->tree);
-#endif
#ifdef GGC_POISON
- memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
+ memset (&x->u, 0xA5, x->size);
#endif
- free (t);
+ free (x);
+ }
}
-/* Freeing a string is as simple as calling free. */
+/* The top level mark-and-sweep routine. */
-static inline void
-ggc_free_string (s)
- struct ggc_string *s;
+void
+ggc_collect ()
{
-#ifdef GGC_DUMP
- fprintf(dump, "collect string %p\n", s->string);
+#ifndef GGC_ALWAYS_COLLECT
+ if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
+ return;
#endif
-#ifdef GGC_POISON
- s->magic_mark = 0xDDDDDDDD;
- s->string[0] = 0xDD;
+
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
#endif
- free (s);
-}
+ timevar_push (TV_GC);
+ if (!quiet_flag)
+ fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
-/* Freeing anonymous memory is as simple as calling free. */
+ G.allocated = 0;
+ G.objects = 0;
-static inline void
-ggc_free_any (a)
- struct ggc_any *a;
-{
-#ifdef GGC_DUMP
- fprintf(dump, "collect mem %p\n", &a->u);
-#endif
-#ifdef GGC_POISON
- a->magic_mark = 0xEEEEEEEE;
-#endif
+ clear_marks (G.root);
+ ggc_mark_roots ();
+ sweep_objs (&G.root);
- free (a);
-}
+ G.allocated_last_gc = G.allocated;
+ if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
+ G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
-/* Mark a node. */
+ timevar_pop (TV_GC);
-int
-ggc_set_mark_rtx (r)
- rtx r;
-{
- int marked = r->gc_mark;
- if (! marked)
- r->gc_mark = 1;
- return marked;
-}
+ if (!quiet_flag)
+ fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
-int
-ggc_set_mark_rtvec (v)
- rtvec v;
-{
- int marked = v->gc_mark;
- if (! marked)
- v->gc_mark = 1;
- return marked;
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
+#endif
}
-int
-ggc_set_mark_tree (t)
- tree t;
-{
- int marked = t->common.gc_mark;
- if (! marked)
- t->common.gc_mark = 1;
- return marked;
-}
+/* Called once to initialize the garbage collector. */
-void
-ggc_mark_string (s)
- char *s;
+void
+init_ggc ()
{
- const ptrdiff_t d = (((struct ggc_string *) 0)->string - (char *) 0);
- struct ggc_string *gs;
-
- if (s == NULL)
- return;
-
- gs = (struct ggc_string *)(s - d);
- if (IGNORE_MARK (gs->magic_mark) != GGC_STRING_MAGIC)
- return; /* abort? */
- gs->magic_mark = GGC_STRING_MAGIC_MARK;
+ G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
}
-/* Mark P, allocated with ggc_alloc. */
+/* Start a new GGC context. Memory allocated in previous contexts
+ will not be collected while the new context is active. */
void
-ggc_mark (p)
- void *p;
+ggc_push_context ()
{
- const ptrdiff_t d = (&((struct ggc_any *) 0)->u.c - (char *) 0);
- struct ggc_any *a;
-
- if (p == NULL)
- return;
+ G.context++;
- a = (struct ggc_any *) (((char*) p) - d);
- if (IGNORE_MARK (a->magic_mark) != GGC_ANY_MAGIC)
+ /* We only allocated 7 bits in the node for the context. This
+ should be more than enough. */
+ if (G.context >= 128)
abort ();
- a->magic_mark = GGC_ANY_MAGIC_MARK;
}
-/* The top level mark-and-sweep routine. */
+/* Finish a GC context. Any uncollected memory in the new context
+ will be merged with the old context. */
-void
-ggc_collect ()
+void
+ggc_pop_context ()
{
- struct ggc_rtx *r, **rp;
- struct ggc_rtvec *v, **vp;
- struct ggc_tree *t, **tp;
- struct ggc_string *s, **sp;
- struct ggc_root *x;
- struct ggc_status *gs;
- struct ggc_any *a, **ap;
- int time, n_rtxs, n_trees, n_vecs, n_strings, n_anys;
-
-#if !defined(ENABLE_CHECKING)
- /* See if it's even worth our while. */
- if (ggc_chain->bytes_alloced_since_gc < 4*1024*1024)
- return;
-#endif
-
- if (!quiet_flag)
- fputs (" {GC ", stderr);
-
- time = get_run_time ();
-
- /* Clean out all of the GC marks. */
- for (gs = ggc_chain; gs; gs = gs->next)
- {
- for (r = gs->rtxs; r != NULL; r = r->chain)
- r->rtx.gc_mark = 0;
- for (v = gs->vecs; v != NULL; v = v->chain)
- v->vec.gc_mark = 0;
- for (t = gs->trees; t != NULL; t = t->chain)
- t->tree.common.gc_mark = 0;
- for (s = gs->strings; s != NULL; s = s->chain)
- s->magic_mark = GGC_STRING_MAGIC;
- for (a = gs->anys; a != NULL; a = a->chain)
- a->magic_mark = GGC_ANY_MAGIC;
- }
-
- /* Mark through all the roots. */
- for (x = roots; x != NULL; x = x->next)
- {
- char *elt = x->base;
- int s = x->size, n = x->nelt;
- void (*cb) PROTO ((void *)) = x->cb;
- int i;
+ G.context--;
+ if (G.root)
+ ggc_pop_context_1 (G.root, G.context);
+}
- for (i = 0; i < n; ++i, elt += s)
- (*cb)(elt);
- }
+static void
+ggc_pop_context_1 (x, c)
+ struct ggc_mem *x;
+ int c;
+{
+ if (x->context > c)
+ x->context = c;
+ if (x->sub[0])
+ ggc_pop_context_1 (x->sub[0], c);
+ if (x->sub[1])
+ ggc_pop_context_1 (x->sub[1], c);
+}
- /* Sweep the resulting dead nodes. */
+/* Dump a tree. */
- /* The RTXs. */
+void
+debug_ggc_tree (p, indent)
+ struct ggc_mem *p;
+ int indent;
+{
+ int i;
- rp = &ggc_chain->rtxs;
- r = ggc_chain->rtxs;
- n_rtxs = 0;
- while (r != NULL)
+ if (!p)
{
- struct ggc_rtx *chain = r->chain;
- if (!r->rtx.gc_mark)
- {
- ggc_free_rtx (r);
- *rp = chain;
- n_rtxs++;
- }
- else
- rp = &r->chain;
- r = chain;
+ fputs ("(nil)\n", stderr);
+ return;
}
- *rp = NULL;
- n_rtxs_collected += n_rtxs;
- /* The vectors. */
+ if (p->sub[0])
+ debug_ggc_tree (p->sub[0], indent + 1);
- vp = &ggc_chain->vecs;
- v = ggc_chain->vecs;
- n_vecs = 0;
- while (v != NULL)
- {
- struct ggc_rtvec *chain = v->chain;
- if (!v->vec.gc_mark)
- {
- ggc_free_rtvec (v);
- *vp = chain;
- n_vecs++;
- }
- else
- vp = &v->chain;
- v = chain;
- }
- *vp = NULL;
- n_vecs_collected += n_vecs;
+ for (i = 0; i < indent; ++i)
+ putc (' ', stderr);
+ fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p);
+
+ if (p->sub[1])
+ debug_ggc_tree (p->sub[1], indent + 1);
+}
- /* The trees. */
+#ifdef GGC_BALANCE
+/* Collect tree balance metrics */
- tp = &ggc_chain->trees;
- t = ggc_chain->trees;
- n_trees = 0;
- while (t != NULL)
- {
- struct ggc_tree *chain = t->chain;
- if (!t->tree.common.gc_mark)
- {
- ggc_free_tree (t);
- *tp = chain;
- n_trees++;
- }
- else
- tp = &t->chain;
- t = chain;
- }
- *tp = NULL;
- n_trees_collected += n_trees;
+#include <math.h>
- /* The strings. */
+void
+debug_ggc_balance ()
+{
+ size_t nleaf, sumdepth;
- sp = &ggc_chain->strings;
- s = ggc_chain->strings;
- n_strings = 0;
- while (s != NULL)
- {
- struct ggc_string *chain = s->chain;
- if (! IS_MARKED (s->magic_mark))
- {
- ggc_free_string (s);
- *sp = chain;
- n_strings++;
- }
- else
- sp = &s->chain;
- s = chain;
- }
- *sp = NULL;
- n_strings_collected += n_strings;
+ nleaf = sumdepth = 0;
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
- /* The generic data. */
+ fprintf (stderr, " {B %.2f,%.1f,%.1f}",
+ /* In a balanced tree, leaf/node should approach 1/2. */
+ (float)nleaf / (float)G.objects,
+ /* In a balanced tree, average leaf depth should approach lg(n). */
+ (float)sumdepth / (float)nleaf,
+ log ((double) G.objects) / M_LN2);
+}
+#endif
- ap = &ggc_chain->anys;
- a = ggc_chain->anys;
- n_anys = 0;
- while (a != NULL)
+/* Used by debug_ggc_balance, and also by ggc_print_statistics. */
+static void
+tally_leaves (x, depth, nleaf, sumdepth)
+ struct ggc_mem *x;
+ int depth;
+ size_t *nleaf;
+ size_t *sumdepth;
+{
+ if (! x->sub[0] && !x->sub[1])
{
- struct ggc_any *chain = a->chain;
- if (! IS_MARKED (a->magic_mark))
- {
- ggc_free_any (a);
- *ap = chain;
- n_anys++;
- }
- else
- ap = &a->chain;
- a = chain;
+ *nleaf += 1;
+ *sumdepth += depth;
}
- n_anys_collected += n_anys;
-
- ggc_chain->bytes_alloced_since_gc = 0;
-
- time = get_run_time () - time;
- gc_time += time;
-
- if (!quiet_flag)
+ else
{
- time = (time + 500) / 1000;
- fprintf (stderr, "%dr,%dv,%dt,%ds,%da %d.%03d}", n_rtxs, n_vecs,
- n_trees, n_strings, n_anys, time / 1000, time % 1000);
+ if (x->sub[0])
+ tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
+ if (x->sub[1])
+ tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
}
}
-#if 0
-/* GDB really should have a memory search function. Since this is just
- for initial debugging, I won't even pretend to get the __data_start
- to work on any but alpha-dec-linux-gnu. */
-static void **
-search_data(void **start, void *target)
-{
- extern void *__data_start[];
- void **_end = (void **)sbrk(0);
+#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
+ ? (x) \
+ : ((x) < 1024*1024*10 \
+ ? (x) / 1024 \
+ : (x) / (1024*1024))))
+#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
- if (start == NULL)
- start = __data_start;
- while (start < _end)
- {
- if (*start == target)
- return start;
- start++;
- }
- return NULL;
+/* Report on GC memory usage. */
+void
+ggc_print_statistics ()
+{
+ struct ggc_statistics stats;
+ size_t nleaf = 0, sumdepth = 0;
+
+ /* Clear the statistics. */
+ memset (&stats, 0, sizeof (stats));
+
+ /* Make sure collection will really occur. */
+ G.allocated_last_gc = 0;
+
+ /* Collect and print the statistics common across collectors. */
+ ggc_print_common_statistics (stderr, &stats);
+
+ /* Report on tree balancing. */
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
+
+ fprintf (stderr, "\n\
+Total internal data (bytes)\t%ld%c\n\
+Number of leaves in tree\t%d\n\
+Average leaf depth\t\t%.1f\n",
+ SCALE(G.objects * offsetof (struct ggc_mem, u)),
+ LABEL(G.objects * offsetof (struct ggc_mem, u)),
+ nleaf, (double)sumdepth / (double)nleaf);
+
+ /* Report overall memory usage. */
+ fprintf (stderr, "\n\
+Total objects allocated\t\t%d\n\
+Total memory in GC arena\t%ld%c\n",
+ G.objects,
+ SCALE(G.allocated), LABEL(G.allocated));
}
-#endif
OSDN Git Service
