#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tree.h"
#include "tm_p.h"
#include "flags.h"
#include "varray.h"
#include "ggc.h"
#include "toplev.h"
#include "timevar.h"
#include "params.h"
#undef GGC_POISON
#undef GGC_BALANCE
#undef GGC_ALWAYS_VERIFY
#ifdef ENABLE_GC_CHECKING
#define GGC_POISON
#define GGC_ALWAYS_VERIFY
#endif
#ifndef HOST_BITS_PER_PTR
#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
#endif
#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_mem
{
struct ggc_mem *sub[2];
unsigned int mark : 1;
unsigned int context : 7;
unsigned int size : 24;
union {
HOST_WIDEST_INT i;
#ifdef HAVE_LONG_DOUBLE
long double d;
#else
double d;
#endif
} u;
};
static struct globals
{
struct ggc_mem *root;
size_t allocated;
size_t objects;
size_t allocated_last_gc;
int context;
} G;
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));
extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
#ifdef GGC_BALANCE
extern void debug_ggc_balance PARAMS ((void));
#endif
static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
static inline void
tree_insert (v)
struct ggc_mem *v;
{
size_t v_key = PTR_KEY (v);
struct ggc_mem *p, **pp;
for (pp = &G.root, p = *pp; p ; p = *pp)
{
size_t p_key = PTR_KEY (p);
pp = &p->sub[v_key < p_key];
}
*pp = v;
}
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)
{
size_t p_key = PTR_KEY (p);
if (p == v)
return 1;
p = p->sub[v_key < p_key];
}
return 0;
}
void *
ggc_alloc (size)
size_t size;
{
struct ggc_mem *x;
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_POISON
memset (&x->u, 0xaf, size);
#endif
tree_insert (x);
G.allocated += size;
G.objects += 1;
return &x->u;
}
int
ggc_set_mark (p)
const void *p;
{
struct ggc_mem *x;
x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
#ifdef GGC_ALWAYS_VERIFY
if (! tree_lookup (x))
abort ();
#endif
if (x->mark)
return 1;
x->mark = 1;
G.allocated += x->size;
G.objects += 1;
return 0;
}
int
ggc_marked_p (p)
const void *p;
{
struct ggc_mem *x;
x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
#ifdef GGC_ALWAYS_VERIFY
if (! tree_lookup (x))
abort ();
#endif
return x->mark;
}
size_t
ggc_get_size (p)
const void *p;
{
struct ggc_mem *x
= (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
return x->size;
}
static void
clear_marks (x)
struct ggc_mem *x;
{
x->mark = 0;
if (x->sub[0])
clear_marks (x->sub[0]);
if (x->sub[1])
clear_marks (x->sub[1]);
}
static void
sweep_objs (root)
struct ggc_mem **root;
{
struct ggc_mem *x = *root;
if (!x)
return;
sweep_objs (&x->sub[0]);
sweep_objs (&x->sub[1]);
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;
}
#ifdef GGC_POISON
memset (&x->u, 0xA5, x->size);
#endif
free (x);
}
}
void
ggc_collect ()
{
size_t allocated_last_gc =
MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
size_t min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
if (G.allocated < allocated_last_gc + min_expand)
return;
#ifdef GGC_BALANCE
debug_ggc_balance ();
#endif
timevar_push (TV_GC);
if (!quiet_flag)
fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
G.allocated = 0;
G.objects = 0;
clear_marks (G.root);
ggc_mark_roots ();
sweep_objs (&G.root);
G.allocated_last_gc = G.allocated;
timevar_pop (TV_GC);
if (!quiet_flag)
fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
#ifdef GGC_BALANCE
debug_ggc_balance ();
#endif
}
void
init_ggc ()
{
}
void
ggc_push_context ()
{
G.context++;
if (G.context >= 128)
abort ();
}
void
ggc_pop_context ()
{
G.context--;
if (G.root)
ggc_pop_context_1 (G.root, G.context);
}
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);
}
void
debug_ggc_tree (p, indent)
struct ggc_mem *p;
int indent;
{
int i;
if (!p)
{
fputs ("(nil)\n", stderr);
return;
}
if (p->sub[0])
debug_ggc_tree (p->sub[0], indent + 1);
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);
}
#ifdef GGC_BALANCE
#include <math.h>
void
debug_ggc_balance ()
{
size_t nleaf, sumdepth;
nleaf = sumdepth = 0;
tally_leaves (G.root, 0, &nleaf, &sumdepth);
fprintf (stderr, " {B %.2f,%.1f,%.1f}",
(float)nleaf / (float)G.objects,
(float)sumdepth / (float)nleaf,
log ((double) G.objects) / M_LN2);
}
#endif
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])
{
*nleaf += 1;
*sumdepth += depth;
}
else
{
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);
}
}
#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'))
void
ggc_print_statistics ()
{
struct ggc_statistics stats;
size_t nleaf = 0, sumdepth = 0;
memset (&stats, 0, sizeof (stats));
G.allocated_last_gc = 0;
ggc_print_common_statistics (stderr, &stats);
tally_leaves (G.root, 0, &nleaf, &sumdepth);
fprintf (stderr, "\n\
Total internal data (bytes)\t%ld%c\n\
Number of leaves in tree\t%lu\n\
Average leaf depth\t\t%.1f\n",
SCALE(G.objects * offsetof (struct ggc_mem, u)),
LABEL(G.objects * offsetof (struct ggc_mem, u)),
(unsigned long)nleaf, (double)sumdepth / (double)nleaf);
fprintf (stderr, "\n\
Total objects allocated\t\t%ld\n\
Total memory in GC arena\t%ld%c\n",
(unsigned long)G.objects,
SCALE(G.allocated), LABEL(G.allocated));
}
struct ggc_pch_data *
init_ggc_pch ()
{
sorry ("Generating PCH files is not supported when using ggc-simple.c");
return NULL;
}
void
ggc_pch_count_object (d, x, size)
struct ggc_pch_data *d ATTRIBUTE_UNUSED;
void *x ATTRIBUTE_UNUSED;
size_t size ATTRIBUTE_UNUSED;
{
}
size_t
ggc_pch_total_size (d)
struct ggc_pch_data *d ATTRIBUTE_UNUSED;
{
return 0;
}
void
ggc_pch_this_base (d, base)
struct ggc_pch_data *d ATTRIBUTE_UNUSED;
void *base ATTRIBUTE_UNUSED;
{
}
char *
ggc_pch_alloc_object (d, x, size)
struct ggc_pch_data *d ATTRIBUTE_UNUSED;
void *x ATTRIBUTE_UNUSED;
size_t size ATTRIBUTE_UNUSED;
{
return NULL;
}
void
ggc_pch_prepare_write (d, f)
struct ggc_pch_data * d ATTRIBUTE_UNUSED;
FILE * f ATTRIBUTE_UNUSED;
{
}
void
ggc_pch_write_object (d, f, x, newx, size)
struct ggc_pch_data * d ATTRIBUTE_UNUSED;
FILE *f ATTRIBUTE_UNUSED;
void *x ATTRIBUTE_UNUSED;
void *newx ATTRIBUTE_UNUSED;
size_t size ATTRIBUTE_UNUSED;
{
}
void
ggc_pch_finish (d, f)
struct ggc_pch_data * d ATTRIBUTE_UNUSED;
FILE *f ATTRIBUTE_UNUSED;
{
}
void
ggc_pch_read (f, addr)
FILE *f ATTRIBUTE_UNUSED;
void *addr ATTRIBUTE_UNUSED;
{
abort ();
}