#include "config.h"
#include "system.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "toplev.h"
#include "varray.h"
#include "flags.h"
#include "ggc.h"
#include "timevar.h"
#ifdef PFE
#include "pfe/pfe.h"
#include "pfe/pfe-header.h"
#define DISABLE_PFE_GC
#endif
#ifdef HAVE_MMAP_ANON
# undef HAVE_MMAP_DEV_ZERO
# include <sys/mman.h>
# ifndef MAP_FAILED
# define MAP_FAILED -1
# endif
# if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
# define MAP_ANONYMOUS MAP_ANON
# endif
# define USING_MMAP
#endif
#ifdef HAVE_MMAP_DEV_ZERO
# include <sys/mman.h>
# ifndef MAP_FAILED
# define MAP_FAILED -1
# endif
# define USING_MMAP
#endif
#ifndef USING_MMAP
#define USING_MALLOC_PAGE_GROUPS
#endif
#ifdef PFE
#define USING_MALLOC_PAGE_GROUPS
#define PFE_USING_MMAP 1
#else
#define PFE_USING_MMAP 0
#endif
#undef GGC_POISON
#undef GGC_ALWAYS_COLLECT
#ifdef ENABLE_GC_CHECKING
#define GGC_POISON
#endif
#ifdef ENABLE_GC_ALWAYS_COLLECT
#define GGC_ALWAYS_COLLECT
#endif
#define GGC_DEBUG_LEVEL (0)
#ifndef HOST_BITS_PER_PTR
#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
#endif
#define PAGE_L1_BITS (8)
#define PAGE_L2_BITS (32 - PAGE_L1_BITS - G.lg_pagesize)
#define PAGE_L1_SIZE ((size_t) 1 << PAGE_L1_BITS)
#define PAGE_L2_SIZE ((size_t) 1 << PAGE_L2_BITS)
#define LOOKUP_L1(p) \
(((size_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
#define LOOKUP_L2(p) \
(((size_t) (p) >> G.lg_pagesize) & ((1 << PAGE_L2_BITS) - 1))
#define OBJECTS_PER_PAGE(ORDER) objects_per_page_table[ORDER]
#define OBJECT_SIZE(ORDER) object_size_table[ORDER]
#define NUM_EXTRA_ORDERS \
(sizeof (extra_order_size_table) / sizeof (extra_order_size_table[0]))
static const size_t extra_order_size_table[] = {
sizeof (struct tree_decl),
sizeof (struct tree_list)
};
#define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
struct max_alignment {
char c;
union {
HOST_WIDEST_INT i;
#ifdef HAVE_LONG_DOUBLE
long double d;
#else
double d;
#endif
} u;
};
#define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
static unsigned objects_per_page_table[NUM_ORDERS];
static size_t object_size_table[NUM_ORDERS];
typedef struct page_entry
{
struct page_entry *next;
size_t bytes;
char *page;
#ifdef USING_MALLOC_PAGE_GROUPS
struct page_group *group;
#endif
unsigned long *save_in_use_p;
unsigned short context_depth;
unsigned short num_free_objects;
unsigned short next_bit_hint;
unsigned char order;
unsigned long in_use_p[1];
} page_entry;
#ifdef USING_MALLOC_PAGE_GROUPS
typedef struct page_group
{
struct page_group *next;
char *allocation;
size_t alloc_size;
unsigned int in_use;
} page_group;
#endif
#if HOST_BITS_PER_PTR <= 32
typedef page_entry **page_table[PAGE_L1_SIZE];
#else
typedef struct page_table_chain
{
struct page_table_chain *next;
size_t high_bits;
page_entry **table[PAGE_L1_SIZE];
} *page_table;
#endif
static struct globals
{
page_entry *pages[NUM_ORDERS];
page_entry *page_tails[NUM_ORDERS];
page_table lookup;
size_t pagesize;
size_t lg_pagesize;
size_t allocated;
size_t allocated_last_gc;
size_t bytes_mapped;
unsigned short context_depth;
#if defined (HAVE_MMAP_DEV_ZERO)
int dev_zero_fd;
#endif
page_entry *free_pages;
#ifdef USING_MALLOC_PAGE_GROUPS
page_group *page_groups;
#endif
FILE *debug_file;
} G;
#define BITMAP_SIZE(Num_objects) \
(CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
#define GGC_MIN_EXPAND_FOR_GC (2.0)
#define GGC_MIN_LAST_ALLOCATED (8 * 1024 * 1024)
#define GGC_QUIRE_SIZE 16
static int ggc_allocated_p PARAMS ((const void *));
static page_entry *lookup_page_table_entry PARAMS ((const void *));
static void set_page_table_entry PARAMS ((void *, page_entry *));
#ifdef USING_MMAP
static char *alloc_anon PARAMS ((char *, size_t));
#endif
#ifdef USING_MALLOC_PAGE_GROUPS
static size_t page_group_index PARAMS ((char *, char *));
static void set_page_group_in_use PARAMS ((page_group *, char *));
static void clear_page_group_in_use PARAMS ((page_group *, char *));
#endif
static struct page_entry * alloc_page PARAMS ((unsigned));
static void free_page PARAMS ((struct page_entry *));
static void release_pages PARAMS ((void));
static void clear_marks PARAMS ((void));
static void sweep_pages PARAMS ((void));
static void ggc_recalculate_in_use_p PARAMS ((page_entry *));
#ifdef GGC_POISON
static void poison_pages PARAMS ((void));
#endif
void debug_print_page_list PARAMS ((int));
#ifdef PFE
static void freeze_thaw_page_entry PARAMS ((page_entry *));
static void freeze_thaw_page_group PARAMS ((page_group **));
static void freeze_thaw_page_table1 PARAMS ((page_entry ***));
#if HOST_BITS_PER_PTR > 32
static void freeze_thaw_page_table2 PARAMS ((page_table *));
#endif
#endif
static inline int
ggc_allocated_p (p)
const void *p;
{
page_entry ***base;
size_t L1, L2;
#if HOST_BITS_PER_PTR <= 32
base = &G.lookup[0];
#else
page_table table = G.lookup;
size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
while (1)
{
if (table == NULL)
return 0;
if (table->high_bits == high_bits)
break;
table = table->next;
}
base = &table->table[0];
#endif
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
return base[L1] && base[L1][L2];
}
static inline page_entry *
lookup_page_table_entry(p)
const void *p;
{
page_entry ***base;
size_t L1, L2;
#if HOST_BITS_PER_PTR <= 32
base = &G.lookup[0];
#else
page_table table = G.lookup;
size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
while (table->high_bits != high_bits)
table = table->next;
base = &table->table[0];
#endif
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
return base[L1][L2];
}
static void
set_page_table_entry(p, entry)
void *p;
page_entry *entry;
{
page_entry ***base;
size_t L1, L2;
#if HOST_BITS_PER_PTR <= 32
base = &G.lookup[0];
#else
page_table table;
size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
for (table = G.lookup; table; table = table->next)
if (table->high_bits == high_bits)
goto found;
table = (page_table) PFE_CALLOC (1, sizeof(*table), PFE_ALLOC_GGC_PAGE_TABLE);
table->next = G.lookup;
table->high_bits = high_bits;
G.lookup = table;
found:
base = &table->table[0];
#endif
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
if (base[L1] == NULL)
base[L1] = (page_entry **) PFE_CALLOC (PAGE_L2_SIZE,
sizeof (page_entry *),
PFE_ALLOC_GGC_PAGE_ENTRY);
base[L1][L2] = entry;
}
void
debug_print_page_list (order)
int order;
{
page_entry *p;
printf ("Head=%p, Tail=%p:\n", (PTR) G.pages[order],
(PTR) G.page_tails[order]);
p = G.pages[order];
while (p != NULL)
{
printf ("%p(%1d|%3d) -> ", (PTR) p, p->context_depth,
p->num_free_objects);
p = p->next;
}
printf ("NULL\n");
fflush (stdout);
}
#ifdef USING_MMAP
static inline char *
alloc_anon (pref, size)
char *pref ATTRIBUTE_UNUSED;
size_t size;
{
#ifdef HAVE_MMAP_ANON
char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
#ifdef HAVE_MMAP_DEV_ZERO
char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE, G.dev_zero_fd, 0);
#endif
if (page == (char *) MAP_FAILED)
{
perror ("virtual memory exhausted");
exit (FATAL_EXIT_CODE);
}
G.bytes_mapped += size;
return page;
}
#endif
#ifdef USING_MALLOC_PAGE_GROUPS
static inline size_t
page_group_index (allocation, page)
char *allocation, *page;
{
return (size_t) (page - allocation) >> G.lg_pagesize;
}
static inline void
set_page_group_in_use (group, page)
page_group *group;
char *page;
{
group->in_use |= 1 << page_group_index (group->allocation, page);
}
static inline void
clear_page_group_in_use (group, page)
page_group *group;
char *page;
{
group->in_use &= ~(1 << page_group_index (group->allocation, page));
}
#endif
static inline struct page_entry *
alloc_page (order)
unsigned order;
{
struct page_entry *entry, *p, **pp;
char *page;
size_t num_objects;
size_t bitmap_size;
size_t page_entry_size;
size_t entry_size;
#ifdef USING_MALLOC_PAGE_GROUPS
page_group *group;
#endif
num_objects = OBJECTS_PER_PAGE (order);
bitmap_size = BITMAP_SIZE (num_objects + 1);
page_entry_size = sizeof (page_entry) - sizeof (long) + bitmap_size;
entry_size = num_objects * OBJECT_SIZE (order);
if (entry_size < G.pagesize)
entry_size = G.pagesize;
entry = NULL;
page = NULL;
for (pp = &G.free_pages, p = *pp; p; pp = &p->next, p = *pp)
if (p->bytes == entry_size)
break;
if (p != NULL)
{
*pp = p->next;
page = p->page;
#ifdef USING_MALLOC_PAGE_GROUPS
group = p->group;
#endif
if (p->order == order)
{
entry = p;
memset (entry, 0, page_entry_size);
}
else
PFE_FREE (p);
}
#ifdef USING_MMAP
#ifdef PFE
else if (pfe_operation != PFE_DUMP && pfe_operation != PFE_LOAD)
{
if (entry_size == G.pagesize)
#else
else if (entry_size == G.pagesize)
#endif
{
struct page_entry *e, *f = G.free_pages;
int i;
page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE);
for (i = GGC_QUIRE_SIZE - 1; i >= 1; i--)
{
e = (struct page_entry *) PFE_CALLOC (1, page_entry_size,
PFE_ALLOC_GGC_PAGE_ENTRY);
e->order = order;
e->bytes = G.pagesize;
e->page = page + (i << G.lg_pagesize);
e->next = f;
f = e;
}
G.free_pages = f;
}
else
page = alloc_anon (NULL, entry_size);
#ifdef PFE
}
#endif
#endif
#ifdef USING_MALLOC_PAGE_GROUPS
else
{
char *allocation, *a, *enda;
size_t alloc_size, head_slop, tail_slop;
int multiple_pages = (entry_size == G.pagesize);
if (multiple_pages)
alloc_size = GGC_QUIRE_SIZE * G.pagesize;
else
alloc_size = entry_size + G.pagesize - 1;
allocation = PFE_MALLOC (alloc_size, PFE_ALLOC_GGC_PAGE_GROUP);
page = (char *) (((size_t) allocation + G.pagesize - 1) & -G.pagesize);
head_slop = page - allocation;
if (multiple_pages)
tail_slop = ((size_t) allocation + alloc_size) & (G.pagesize - 1);
else
tail_slop = alloc_size - entry_size - head_slop;
enda = allocation + alloc_size - tail_slop;
if (head_slop >= sizeof (page_group))
group = (page_group *)page - 1;
else
{
if (tail_slop == 0)
{
enda -= G.pagesize;
tail_slop += G.pagesize;
}
if (tail_slop < sizeof (page_group))
abort ();
group = (page_group *)enda;
tail_slop -= sizeof (page_group);
}
group->next = G.page_groups;
group->allocation = allocation;
group->alloc_size = alloc_size;
group->in_use = 0;
G.page_groups = group;
G.bytes_mapped += alloc_size;
if (multiple_pages)
{
struct page_entry *e, *f = G.free_pages;
for (a = enda - G.pagesize; a != page; a -= G.pagesize)
{
e = (struct page_entry *) PFE_CALLOC (1, page_entry_size,
PFE_ALLOC_GGC_PAGE_ENTRY);
e->order = order;
e->bytes = G.pagesize;
e->page = a;
e->group = group;
e->next = f;
f = e;
}
G.free_pages = f;
}
}
#endif
if (entry == NULL)
entry = (struct page_entry *) PFE_CALLOC (1, page_entry_size,
PFE_ALLOC_GGC_PAGE_ENTRY);
entry->bytes = entry_size;
entry->page = page;
entry->context_depth = G.context_depth;
entry->order = order;
entry->num_free_objects = num_objects;
entry->next_bit_hint = 1;
#ifdef USING_MALLOC_PAGE_GROUPS
#ifdef PFE
if (!PFE_USING_MMAP || pfe_operation == PFE_DUMP || pfe_operation == PFE_LOAD)
{
entry->group = group;
set_page_group_in_use (group, page);
}
#else
entry->group = group;
set_page_group_in_use (group, page);
#endif
#endif
entry->in_use_p[num_objects / HOST_BITS_PER_LONG]
= (unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG);
set_page_table_entry (page, entry);
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Allocating page at %p, object size=%ld, data %p-%p\n",
(PTR) entry, (long) OBJECT_SIZE (order), page,
page + entry_size - 1);
return entry;
}
static inline void
free_page (entry)
page_entry *entry;
{
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Deallocating page at %p, data %p-%p\n", (PTR) entry,
entry->page, entry->page + entry->bytes - 1);
set_page_table_entry (entry->page, NULL);
#ifdef USING_MALLOC_PAGE_GROUPS
#ifdef PFE
if (!PFE_USING_MMAP || pfe_operation == PFE_DUMP || pfe_operation == PFE_LOAD)
#endif
clear_page_group_in_use (entry->group, entry->page);
#endif
entry->next = G.free_pages;
G.free_pages = entry;
}
static void
release_pages ()
{
#ifdef USING_MMAP
#ifdef PFE
if (pfe_operation != PFE_DUMP && pfe_operation != PFE_LOAD)
{
#endif
page_entry *p, *next;
char *start;
size_t len;
p = G.free_pages;
while (p)
{
start = p->page;
next = p->next;
len = p->bytes;
PFE_FREE (p);
p = next;
while (p && p->page == start + len)
{
next = p->next;
len += p->bytes;
PFE_FREE (p);
p = next;
}
munmap (start, len);
G.bytes_mapped -= len;
}
G.free_pages = NULL;
#ifdef PFE
} else {
#endif
#endif
#ifdef USING_MALLOC_PAGE_GROUPS
page_entry **pp, *p;
page_group **gp, *g;
pp = &G.free_pages;
while ((p = *pp) != NULL)
if (p->group->in_use == 0)
{
*pp = p->next;
PFE_FREE (p);
}
else
pp = &p->next;
gp = &G.page_groups;
while ((g = *gp) != NULL)
if (g->in_use == 0)
{
*gp = g->next;
G.bytes_mapped -= g->alloc_size;
PFE_FREE (g->allocation);
}
else
gp = &g->next;
#endif
#ifdef USING_MMAP
#ifdef PFE
}
#endif
#endif
}
static unsigned char size_lookup[257] =
{
3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8
};
void *
ggc_alloc (size)
size_t size;
{
unsigned order, word, bit, object_offset;
struct page_entry *entry;
void *result;
if (size <= 256)
order = size_lookup[size];
else
{
order = 9;
while (size > OBJECT_SIZE (order))
order++;
}
entry = G.pages[order];
if (entry == NULL || entry->num_free_objects == 0)
{
struct page_entry *new_entry;
new_entry = alloc_page (order);
if (entry == NULL)
G.page_tails[order] = new_entry;
new_entry->next = entry;
entry = new_entry;
G.pages[order] = new_entry;
new_entry->next_bit_hint = 1;
word = 0;
bit = 0;
object_offset = 0;
}
else
{
unsigned hint = entry->next_bit_hint;
word = hint / HOST_BITS_PER_LONG;
bit = hint % HOST_BITS_PER_LONG;
if ((entry->in_use_p[word] >> bit) & 1)
{
word = bit = 0;
while (~entry->in_use_p[word] == 0)
++word;
while ((entry->in_use_p[word] >> bit) & 1)
++bit;
hint = word * HOST_BITS_PER_LONG + bit;
}
entry->next_bit_hint = hint + 1;
object_offset = hint * OBJECT_SIZE (order);
}
entry->in_use_p[word] |= ((unsigned long) 1 << bit);
if (--entry->num_free_objects == 0
&& entry->next != NULL
&& entry->next->num_free_objects > 0)
{
G.pages[order] = entry->next;
entry->next = NULL;
G.page_tails[order]->next = entry;
G.page_tails[order] = entry;
}
result = entry->page + object_offset;
#ifdef GGC_POISON
memset (result, 0xaf, OBJECT_SIZE (order));
#endif
G.allocated += OBJECT_SIZE (order);
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file,
"Allocating object, requested size=%ld, actual=%ld at %p on %p\n",
(long) size, (long) OBJECT_SIZE (order), result, (PTR) entry);
return result;
}
int
ggc_set_mark (p)
const void *p;
{
page_entry *entry;
unsigned bit, word;
unsigned long mask;
entry = lookup_page_table_entry (p);
#ifdef ENABLE_CHECKING
if (entry == NULL)
abort ();
#endif
bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
word = bit / HOST_BITS_PER_LONG;
mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
if (entry->in_use_p[word] & mask)
return 1;
entry->in_use_p[word] |= mask;
entry->num_free_objects -= 1;
if (GGC_DEBUG_LEVEL >= 4)
fprintf (G.debug_file, "Marking %p\n", p);
return 0;
}
int
ggc_marked_p (p)
const void *p;
{
page_entry *entry;
unsigned bit, word;
unsigned long mask;
entry = lookup_page_table_entry (p);
#ifdef ENABLE_CHECKING
if (entry == NULL)
abort ();
#endif
bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
word = bit / HOST_BITS_PER_LONG;
mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
return (entry->in_use_p[word] & mask) != 0;
}
size_t
ggc_get_size (p)
const void *p;
{
page_entry *pe = lookup_page_table_entry (p);
return OBJECT_SIZE (pe->order);
}
void
init_ggc ()
{
unsigned order;
G.pagesize = getpagesize();
G.lg_pagesize = exact_log2 (G.pagesize);
#ifdef HAVE_MMAP_DEV_ZERO
#ifdef PFE
if (pfe_operation != PFE_DUMP && pfe_operation != PFE_LOAD)
{
G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
if (G.dev_zero_fd == -1)
abort ();
}
#else
G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
if (G.dev_zero_fd == -1)
abort ();
#endif
#endif
#if 0
G.debug_file = fopen ("ggc-mmap.debug", "w");
#else
G.debug_file = stdout;
#endif
G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
#ifdef USING_MMAP
#ifdef PFE
if (pfe_operation == PFE_DUMP)
pfe_compiler_state_ptr->ggc_globals = PFE_MALLOC (sizeof (G),
PFE_ALLOC_GGC_GLOBALS);
else if (pfe_operation != PFE_LOAD)
#endif
{
char *p = alloc_anon (NULL, G.pagesize);
struct page_entry *e;
if ((size_t)p & (G.pagesize - 1))
{
p = alloc_anon (NULL, G.pagesize);
if ((size_t)p & (G.pagesize - 1))
abort ();
}
e = (struct page_entry *) PFE_CALLOC (1, sizeof (struct page_entry),
PFE_ALLOC_GGC_PAGE_ENTRY);
e->bytes = G.pagesize;
e->page = p;
e->next = G.free_pages;
G.free_pages = e;
}
#endif
for (order = 0; order < HOST_BITS_PER_PTR; ++order)
object_size_table[order] = (size_t) 1 << order;
for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
{
size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR];
s = CEIL (s, MAX_ALIGNMENT) * MAX_ALIGNMENT;
object_size_table[order] = s;
}
for (order = 0; order < NUM_ORDERS; ++order)
{
objects_per_page_table[order] = G.pagesize / OBJECT_SIZE (order);
if (objects_per_page_table[order] == 0)
objects_per_page_table[order] = 1;
}
for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
{
int o;
int i;
o = size_lookup[OBJECT_SIZE (order)];
for (i = OBJECT_SIZE (order); size_lookup [i] == o; --i)
size_lookup[i] = order;
}
}
void
ggc_push_context ()
{
++G.context_depth;
if (G.context_depth == 0)
abort ();
}
static void
ggc_recalculate_in_use_p (p)
page_entry *p;
{
unsigned int i;
size_t num_objects;
num_objects = OBJECTS_PER_PAGE (p->order) + 1;
p->num_free_objects = num_objects;
for (i = 0;
i < CEIL (BITMAP_SIZE (num_objects),
sizeof (*p->in_use_p));
++i)
{
unsigned long j;
p->in_use_p[i] |= p->save_in_use_p[i];
for (j = p->in_use_p[i]; j; j >>= 1)
p->num_free_objects -= (j & 1);
}
if (p->num_free_objects >= num_objects)
abort ();
}
void
ggc_pop_context ()
{
unsigned order, depth;
depth = --G.context_depth;
for (order = 2; order < NUM_ORDERS; order++)
{
page_entry *p;
for (p = G.pages[order]; p != NULL; p = p->next)
{
if (p->context_depth > depth)
p->context_depth = depth;
else if (p->context_depth == depth && p->save_in_use_p)
{
ggc_recalculate_in_use_p (p);
PFE_FREE (p->save_in_use_p);
p->save_in_use_p = 0;
}
}
}
}
static inline void
clear_marks ()
{
unsigned order;
for (order = 2; order < NUM_ORDERS; order++)
{
size_t num_objects = OBJECTS_PER_PAGE (order);
size_t bitmap_size = BITMAP_SIZE (num_objects + 1);
page_entry *p;
for (p = G.pages[order]; p != NULL; p = p->next)
{
#ifdef ENABLE_CHECKING
if ((size_t) p->page & (G.pagesize - 1))
abort ();
#endif
if (p->context_depth < G.context_depth)
{
if (! p->save_in_use_p)
p->save_in_use_p = PFE_MALLOC (bitmap_size,
PFE_ALLOC_GGC_BIT_MAP);
memcpy (p->save_in_use_p, p->in_use_p, bitmap_size);
}
p->num_free_objects = num_objects;
memset (p->in_use_p, 0, bitmap_size);
p->in_use_p[num_objects / HOST_BITS_PER_LONG]
= ((unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG));
}
}
}
static inline void
sweep_pages ()
{
unsigned order;
for (order = 2; order < NUM_ORDERS; order++)
{
page_entry * const last = G.page_tails[order];
size_t num_objects = OBJECTS_PER_PAGE (order);
size_t live_objects;
page_entry *p, *previous;
int done;
p = G.pages[order];
if (p == NULL)
continue;
previous = NULL;
do
{
page_entry *next = p->next;
done = (p == last);
live_objects = num_objects - p->num_free_objects;
G.allocated += OBJECT_SIZE (order) * live_objects;
if (p->context_depth < G.context_depth)
;
else if (live_objects == 0)
{
if (! previous)
G.pages[order] = next;
else
previous->next = next;
if (p == G.page_tails[order])
G.page_tails[order] = previous;
free_page (p);
p = previous;
}
else if (p->num_free_objects == 0)
{
if (p != G.page_tails[order])
{
p->next = NULL;
G.page_tails[order]->next = p;
G.page_tails[order] = p;
if (! previous)
G.pages[order] = next;
else
previous->next = next;
p = previous;
}
}
else if (p != G.pages[order])
{
previous->next = p->next;
p->next = G.pages[order];
G.pages[order] = p;
if (G.page_tails[order] == p)
G.page_tails[order] = previous;
p = previous;
}
previous = p;
p = next;
}
while (! done);
for (p = G.pages[order]; p; p = p->next)
if (p->context_depth != G.context_depth)
ggc_recalculate_in_use_p (p);
}
}
#ifdef GGC_POISON
static inline void
poison_pages ()
{
unsigned order;
for (order = 2; order < NUM_ORDERS; order++)
{
size_t num_objects = OBJECTS_PER_PAGE (order);
size_t size = OBJECT_SIZE (order);
page_entry *p;
for (p = G.pages[order]; p != NULL; p = p->next)
{
size_t i;
if (p->context_depth != G.context_depth)
continue;
for (i = 0; i < num_objects; i++)
{
size_t word, bit;
word = i / HOST_BITS_PER_LONG;
bit = i % HOST_BITS_PER_LONG;
if (((p->in_use_p[word] >> bit) & 1) == 0)
memset (p->page + i * size, 0xa5, size);
}
}
}
}
#endif
void
ggc_collect ()
{
#ifndef GGC_ALWAYS_COLLECT
#ifdef DISABLE_PFE_GC
if (pfe_operation == PFE_LOAD || pfe_operation == PFE_DUMP)
return;
#endif
if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
return;
#endif
timevar_push (TV_GC);
if (!quiet_flag)
fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
G.allocated = 0;
release_pages ();
clear_marks ();
ggc_mark_roots ();
#ifdef GGC_POISON
poison_pages ();
#endif
sweep_pages ();
G.allocated_last_gc = G.allocated;
if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
timevar_pop (TV_GC);
if (!quiet_flag)
fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
}
#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;
unsigned int i;
size_t total_overhead = 0;
memset (&stats, 0, sizeof (stats));
G.allocated_last_gc = 0;
ggc_print_common_statistics (stderr, &stats);
release_pages ();
fprintf (stderr, "\n%-5s %10s %10s %10s\n",
"Size", "Allocated", "Used", "Overhead");
for (i = 0; i < NUM_ORDERS; ++i)
{
page_entry *p;
size_t allocated;
size_t in_use;
size_t overhead;
if (!G.pages[i])
continue;
overhead = allocated = in_use = 0;
for (p = G.pages[i]; p; p = p->next)
{
allocated += p->bytes;
in_use +=
(OBJECTS_PER_PAGE (i) - p->num_free_objects) * OBJECT_SIZE (i);
overhead += (sizeof (page_entry) - sizeof (long)
+ BITMAP_SIZE (OBJECTS_PER_PAGE (i) + 1));
}
fprintf (stderr, "%-5d %10ld%c %10ld%c %10ld%c\n", OBJECT_SIZE (i),
SCALE (allocated), LABEL (allocated),
SCALE (in_use), LABEL (in_use),
SCALE (overhead), LABEL (overhead));
total_overhead += overhead;
}
fprintf (stderr, "%-5s %10ld%c %10ld%c %10ld%c\n", "Total",
SCALE (G.bytes_mapped), LABEL (G.bytes_mapped),
SCALE (G.allocated), LABEL(G.allocated),
SCALE (total_overhead), LABEL (total_overhead));
}
#ifdef PFE
void
pfe_freeze_thaw_ggc (pp)
void *pp;
{
struct globals *pG = pfe_freeze_thaw_ptr_fp (pp);
unsigned int i;
#ifdef DISABLE_PFE_GC
return;
#endif
if (PFE_FREEZING)
memcpy (pG, &G, sizeof (G));
for (i = 0; i < NUM_ORDERS; ++i)
{
freeze_thaw_page_entry (pfe_freeze_thaw_ptr ((void *)&pG->pages[i]));
if (pG->page_tails[i])
PFE_FREEZE_THAW_PTR (&pG->page_tails[i]);
}
#if HOST_BITS_PER_PTR <= 32
freeze_thaw_page_table1 (&pG->lookup[0]);
#else
freeze_thaw_page_table2 (&pG->lookup);
#endif
freeze_thaw_page_entry (pfe_freeze_thaw_ptr ((void *)&pG->free_pages));
#ifdef USING_MALLOC_PAGE_GROUPS
freeze_thaw_page_group (&pG->page_groups);
#endif
pG->debug_file = NULL;
if (PFE_THAWING)
memcpy (&G, pG, sizeof (G));
}
static void
freeze_thaw_page_entry (p)
page_entry *p;
{
while (p)
{
if (p->page && !PFE_FREEZE_THAW_PTR (&p->page))
return;
#ifdef USING_MALLOC_PAGE_GROUPS
if (p->group)
{
if ((PFE_FREEZING && PFE_IS_FROZEN (p->group))
|| (PFE_THAWING && !PFE_IS_FROZEN (p->group)))
return;
freeze_thaw_page_group (&p->group);
}
#endif
if (p->save_in_use_p && !PFE_FREEZE_THAW_PTR (&p->save_in_use_p))
return;
p = PFE_FREEZE_THAW_PTR (&p->next);
}
}
static void
freeze_thaw_page_group (groupp)
page_group **groupp;
{
page_group *group = PFE_FREEZE_THAW_PTR (groupp);
while (group)
{
if (group->allocation && !PFE_FREEZE_THAW_PTR (&group->allocation))
return;
group = PFE_FREEZE_THAW_PTR (&group->next);
}
}
static void
freeze_thaw_page_table1 (base)
page_entry ***base;
{
unsigned int i, j;
for (i = 0; i < PAGE_L1_SIZE; ++i)
{
page_entry **p1 = PFE_FREEZE_THAW_PTR (&base[i]);
if (p1)
for (j = 0; j < PAGE_L2_SIZE; ++j)
{
page_entry *p2 = PFE_FREEZE_THAW_PTR (p1 + j);
if (p2)
freeze_thaw_page_entry (p2);
}
}
}
#if HOST_BITS_PER_PTR > 32
static void
freeze_thaw_page_table2 (tablepp)
page_table *tablepp;
{
page_table table = PFE_FREEZE_THAW_PTR (tablepp);
while (table)
{
freeze_thaw_page_table1 (&table->table[0]);
table = PFE_FREEZE_THAW_PTR (&table->next);
}
}
#endif
static void
ggc_debugging(p)
int p;
{
int L1, L2;
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
fprintf (stderr, "L1=%d, L2=%d\n", L1, L2);
}
#if HOST_BITS_PER_PTR <= 32
struct page_table_chain
{
page_entry **table[PAGE_L1_SIZE];
};
#endif
DEFINE_CHECK_STRUCT_FUNCTION (page_entry)
DEFINE_CHECK_STRUCT_FUNCTION (page_group)
DEFINE_CHECK_STRUCT_FUNCTION (page_table_chain)
DEFINE_CHECK_STRUCT_FUNCTION (globals)
#endif