#include "config.h"
#include "system.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "toplev.h"
#include "flags.h"
#include "ggc.h"
#include "timevar.h"
#include "params.h"
#ifdef ENABLE_VALGRIND_CHECKING
#include <valgrind.h>
#else
#define VALGRIND_DISCARD(x)
#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
#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 OBJECTS_IN_PAGE(P) ((P)->bytes / OBJECT_SIZE ((P)->order))
#define OBJECT_SIZE(ORDER) object_size_table[ORDER]
#define DIV_MULT(ORDER) inverse_table[ORDER].mult
#define DIV_SHIFT(ORDER) inverse_table[ORDER].shift
#define OFFSET_TO_BIT(OFFSET, ORDER) \
(((OFFSET) * DIV_MULT (ORDER)) >> DIV_SHIFT (ORDER))
#define NUM_EXTRA_ORDERS ARRAY_SIZE (extra_order_size_table)
#define RTL_SIZE(NSLOTS) \
(sizeof (struct rtx_def) + ((NSLOTS) - 1) * sizeof (rtunion))
static const size_t extra_order_size_table[] = {
sizeof (struct tree_decl),
sizeof (struct tree_list),
RTL_SIZE (2),
RTL_SIZE (10),
};
#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))
#define ROUND_UP_VALUE(x, f) ((f) - 1 - ((f) - 1 + (x)) % (f))
#define ROUND_UP(x, f) (CEIL (x, f) * (f))
static unsigned objects_per_page_table[NUM_ORDERS];
static size_t object_size_table[NUM_ORDERS];
static struct
{
size_t mult;
unsigned int shift;
}
inverse_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 index_by_depth;
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 long context_depth_allocations;
unsigned long context_depth_collections;
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;
unsigned int depth_in_use;
unsigned int depth_max;
unsigned int *depth;
unsigned int by_depth_in_use;
unsigned int by_depth_max;
page_entry **by_depth;
unsigned long **save_in_use;
} G;
#define BITMAP_SIZE(Num_objects) \
(CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
#define GGC_QUIRE_SIZE 16
#define INITIAL_PTE_COUNT 128
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 *));
static void compute_inverse PARAMS ((unsigned));
static inline void adjust_depth PARAMS ((void));
static void move_ptes_to_front PARAMS ((int, int));
#ifdef ENABLE_GC_CHECKING
static void poison_pages PARAMS ((void));
#endif
void debug_print_page_list PARAMS ((int));
static void push_depth PARAMS ((unsigned int));
static void push_by_depth PARAMS ((page_entry *, unsigned long *));
inline static void
push_depth (i)
unsigned int i;
{
if (G.depth_in_use >= G.depth_max)
{
G.depth_max *= 2;
G.depth = (unsigned int *) xrealloc ((char *) G.depth,
G.depth_max * sizeof (unsigned int));
}
G.depth[G.depth_in_use++] = i;
}
inline static void
push_by_depth (p, s)
page_entry *p;
unsigned long *s;
{
if (G.by_depth_in_use >= G.by_depth_max)
{
G.by_depth_max *= 2;
G.by_depth = (page_entry **) xrealloc ((char *) G.by_depth,
G.by_depth_max * sizeof (page_entry *));
G.save_in_use = (unsigned long **) xrealloc ((char *) G.save_in_use,
G.by_depth_max * sizeof (unsigned long *));
}
G.by_depth[G.by_depth_in_use] = p;
G.save_in_use[G.by_depth_in_use++] = s;
}
#define prefetch(X) ((void) X)
#define save_in_use_p_i(__i) \
(G.save_in_use[__i])
#define save_in_use_p(__p) \
(save_in_use_p_i (__p->index_by_depth))
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) xcalloc (1, sizeof(*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 **) xcalloc (PAGE_L2_SIZE, sizeof (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;
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, 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
free (p);
}
#ifdef USING_MMAP
else if (entry_size == G.pagesize)
{
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 *) xcalloc (1, page_entry_size);
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);
#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 = xmalloc (alloc_size);
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 *) xcalloc (1, page_entry_size);
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 *) xcalloc (1, page_entry_size);
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;
G.context_depth_allocations |= (unsigned long)1 << G.context_depth;
#ifdef USING_MALLOC_PAGE_GROUPS
entry->group = group;
set_page_group_in_use (group, page);
#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=%lu, data %p-%p\n",
(PTR) entry, (unsigned long) OBJECT_SIZE (order), page,
page + entry_size - 1);
return entry;
}
static inline void
adjust_depth ()
{
page_entry *top;
if (G.by_depth_in_use)
{
top = G.by_depth[G.by_depth_in_use-1];
while (G.depth_in_use > (size_t)top->context_depth+1)
--G.depth_in_use;
}
}
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);
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->page, entry->bytes));
set_page_table_entry (entry->page, NULL);
#ifdef USING_MALLOC_PAGE_GROUPS
clear_page_group_in_use (entry->group, entry->page);
#endif
if (G.by_depth_in_use > 1)
{
page_entry *top = G.by_depth[G.by_depth_in_use-1];
if (entry->context_depth == top->context_depth)
{
int i = entry->index_by_depth;
G.by_depth[i] = top;
G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1];
top->index_by_depth = i;
}
else
{
abort ();
}
}
--G.by_depth_in_use;
adjust_depth ();
entry->next = G.free_pages;
G.free_pages = entry;
}
static void
release_pages ()
{
#ifdef USING_MMAP
page_entry *p, *next;
char *start;
size_t len;
p = G.free_pages;
while (p)
{
start = p->page;
next = p->next;
len = p->bytes;
free (p);
p = next;
while (p && p->page == start + len)
{
next = p->next;
len += p->bytes;
free (p);
p = next;
}
munmap (start, len);
G.bytes_mapped -= len;
}
G.free_pages = NULL;
#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;
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;
free (g->allocation);
}
else
gp = &g->next;
#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);
new_entry->index_by_depth = G.by_depth_in_use;
push_by_depth (new_entry, 0);
while (new_entry->context_depth >= G.depth_in_use)
push_depth (G.by_depth_in_use-1);
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 ENABLE_GC_CHECKING
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, OBJECT_SIZE (order)));
memset (result, 0xaf, OBJECT_SIZE (order));
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) result + size,
OBJECT_SIZE (order) - size));
#endif
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
G.allocated += OBJECT_SIZE (order);
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file,
"Allocating object, requested size=%lu, actual=%lu at %p on %p\n",
(unsigned long) size, (unsigned 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 = OFFSET_TO_BIT (((const char *) p) - entry->page, 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 = OFFSET_TO_BIT (((const char *) p) - entry->page, 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);
}
static void
compute_inverse (order)
unsigned order;
{
size_t size, inv;
unsigned int e;
size = OBJECT_SIZE (order);
e = 0;
while (size % 2 == 0)
{
e++;
size >>= 1;
}
inv = size;
while (inv * size != 1)
inv = inv * (2 - inv*size);
DIV_MULT (order) = inv;
DIV_SHIFT (order) = e;
}
void
init_ggc ()
{
unsigned order;
G.pagesize = getpagesize();
G.lg_pagesize = exact_log2 (G.pagesize);
#ifdef HAVE_MMAP_DEV_ZERO
G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
if (G.dev_zero_fd == -1)
abort ();
#endif
#if 0
G.debug_file = fopen ("ggc-mmap.debug", "w");
#else
G.debug_file = stdout;
#endif
#ifdef USING_MMAP
{
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 *) xcalloc (1, sizeof (struct 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 = ROUND_UP (s, 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;
compute_inverse (order);
}
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;
}
G.depth_in_use = 0;
G.depth_max = 10;
G.depth = (unsigned int *) xmalloc (G.depth_max * sizeof (unsigned int));
G.by_depth_in_use = 0;
G.by_depth_max = INITIAL_PTE_COUNT;
G.by_depth = (page_entry **) xmalloc (G.by_depth_max * sizeof (page_entry *));
G.save_in_use = (unsigned long **) xmalloc (G.by_depth_max * sizeof (unsigned long *));
}
void
ggc_push_context ()
{
++G.context_depth;
if (G.context_depth >= HOST_BITS_PER_LONG)
abort ();
}
static void
ggc_recalculate_in_use_p (p)
page_entry *p;
{
unsigned int i;
size_t num_objects;
num_objects = OBJECTS_IN_PAGE (p) + 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] |= save_in_use_p (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 long omask;
unsigned int depth, i, e;
#ifdef ENABLE_CHECKING
unsigned int order;
#endif
depth = --G.context_depth;
omask = (unsigned long)1 << (depth + 1);
if (!((G.context_depth_allocations | G.context_depth_collections) & omask))
return;
G.context_depth_allocations |= (G.context_depth_allocations & omask) >> 1;
G.context_depth_allocations &= omask - 1;
G.context_depth_collections &= omask - 1;
if (depth+1 < G.depth_in_use)
e = G.depth[depth+1];
else
e = G.by_depth_in_use;
if (depth < G.depth_in_use)
{
for (i = G.depth[depth]; i < e; ++i)
{
page_entry *p;
#ifdef ENABLE_CHECKING
p = G.by_depth[i];
if (p->context_depth != depth)
abort ();
if (p->index_by_depth != i)
abort ();
#endif
prefetch (&save_in_use_p_i (i+8));
prefetch (&save_in_use_p_i (i+16));
if (save_in_use_p_i (i))
{
p = G.by_depth[i];
ggc_recalculate_in_use_p (p);
free (save_in_use_p_i (i));
save_in_use_p_i (i) = 0;
}
}
}
for (i = e; i < G.by_depth_in_use; ++i)
{
page_entry *p = G.by_depth[i];
#ifdef ENABLE_CHECKING
if (p->context_depth <= depth)
abort ();
if (p->index_by_depth != i)
abort ();
#endif
p->context_depth = depth;
}
adjust_depth ();
#ifdef ENABLE_CHECKING
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)
abort ();
else if (p->context_depth == depth && save_in_use_p (p))
abort ();
}
}
#endif
}
static inline void
clear_marks ()
{
unsigned order;
for (order = 2; order < NUM_ORDERS; order++)
{
page_entry *p;
for (p = G.pages[order]; p != NULL; p = p->next)
{
size_t num_objects = OBJECTS_IN_PAGE (p);
size_t bitmap_size = BITMAP_SIZE (num_objects + 1);
#ifdef ENABLE_CHECKING
if ((size_t) p->page & (G.pagesize - 1))
abort ();
#endif
if (p->context_depth < G.context_depth)
{
if (! save_in_use_p (p))
save_in_use_p (p) = xmalloc (bitmap_size);
memcpy (save_in_use_p (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;
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);
num_objects = OBJECTS_IN_PAGE (p);
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 ENABLE_GC_CHECKING
static inline void
poison_pages ()
{
unsigned order;
for (order = 2; order < NUM_ORDERS; order++)
{
size_t size = OBJECT_SIZE (order);
page_entry *p;
for (p = G.pages[order]; p != NULL; p = p->next)
{
size_t num_objects;
size_t i;
if (p->context_depth != G.context_depth)
continue;
num_objects = OBJECTS_IN_PAGE (p);
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)
{
char *object = p->page + i * size;
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (object, size));
memset (object, 0xa5, size);
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (object, size));
}
}
}
}
}
#endif
void
ggc_collect ()
{
float allocated_last_gc =
MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
float min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
if (G.allocated < allocated_last_gc + min_expand)
return;
timevar_push (TV_GC);
if (!quiet_flag)
fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
G.allocated = 0;
release_pages ();
G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
clear_marks ();
ggc_mark_roots ();
#ifdef ENABLE_GC_CHECKING
poison_pages ();
#endif
sweep_pages ();
G.allocated_last_gc = G.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_IN_PAGE (p) - p->num_free_objects) * OBJECT_SIZE (i);
overhead += (sizeof (page_entry) - sizeof (long)
+ BITMAP_SIZE (OBJECTS_IN_PAGE (p) + 1));
}
fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
(unsigned long) OBJECT_SIZE (i),
SCALE (allocated), LABEL (allocated),
SCALE (in_use), LABEL (in_use),
SCALE (overhead), LABEL (overhead));
total_overhead += overhead;
}
fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
SCALE (G.bytes_mapped), LABEL (G.bytes_mapped),
SCALE (G.allocated), LABEL(G.allocated),
SCALE (total_overhead), LABEL (total_overhead));
}
struct ggc_pch_data
{
struct ggc_pch_ondisk
{
unsigned totals[NUM_ORDERS];
} d;
size_t base[NUM_ORDERS];
size_t written[NUM_ORDERS];
};
struct ggc_pch_data *
init_ggc_pch ()
{
return xcalloc (sizeof (struct ggc_pch_data), 1);
}
void
ggc_pch_count_object (d, x, size)
struct ggc_pch_data *d;
void *x ATTRIBUTE_UNUSED;
size_t size;
{
unsigned order;
if (size <= 256)
order = size_lookup[size];
else
{
order = 9;
while (size > OBJECT_SIZE (order))
order++;
}
d->d.totals[order]++;
}
size_t
ggc_pch_total_size (d)
struct ggc_pch_data *d;
{
size_t a = 0;
unsigned i;
for (i = 0; i < NUM_ORDERS; i++)
a += ROUND_UP (d->d.totals[i] * OBJECT_SIZE (i), G.pagesize);
return a;
}
void
ggc_pch_this_base (d, base)
struct ggc_pch_data *d;
void *base;
{
size_t a = (size_t) base;
unsigned i;
for (i = 0; i < NUM_ORDERS; i++)
{
d->base[i] = a;
a += ROUND_UP (d->d.totals[i] * OBJECT_SIZE (i), G.pagesize);
}
}
char *
ggc_pch_alloc_object (d, x, size)
struct ggc_pch_data *d;
void *x ATTRIBUTE_UNUSED;
size_t size;
{
unsigned order;
char *result;
if (size <= 256)
order = size_lookup[size];
else
{
order = 9;
while (size > OBJECT_SIZE (order))
order++;
}
result = (char *) d->base[order];
d->base[order] += OBJECT_SIZE (order);
return result;
}
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;
void *x;
void *newx ATTRIBUTE_UNUSED;
size_t size;
{
unsigned order;
if (size <= 256)
order = size_lookup[size];
else
{
order = 9;
while (size > OBJECT_SIZE (order))
order++;
}
if (fwrite (x, size, 1, f) != 1)
fatal_io_error ("can't write PCH file");
if (size != OBJECT_SIZE (order)
&& fseek (f, OBJECT_SIZE (order) - size, SEEK_CUR) != 0)
fatal_io_error ("can't write PCH file");
d->written[order]++;
if (d->written[order] == d->d.totals[order]
&& fseek (f, ROUND_UP_VALUE (d->d.totals[order] * OBJECT_SIZE (order),
G.pagesize),
SEEK_CUR) != 0)
fatal_io_error ("can't write PCH file");
}
void
ggc_pch_finish (d, f)
struct ggc_pch_data * d;
FILE *f;
{
if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
fatal_io_error ("can't write PCH file");
free (d);
}
static void
move_ptes_to_front (count_old_page_tables, count_new_page_tables)
int count_old_page_tables;
int count_new_page_tables;
{
unsigned i;
page_entry **new_by_depth;
unsigned long **new_save_in_use;
new_by_depth = (page_entry **) xmalloc (G.by_depth_max * sizeof (page_entry *));
new_save_in_use = (unsigned long **) xmalloc (G.by_depth_max * sizeof (unsigned long *));
memcpy (&new_by_depth[0],
&G.by_depth[count_old_page_tables],
count_new_page_tables * sizeof (void *));
memcpy (&new_by_depth[count_new_page_tables],
&G.by_depth[0],
count_old_page_tables * sizeof (void *));
memcpy (&new_save_in_use[0],
&G.save_in_use[count_old_page_tables],
count_new_page_tables * sizeof (void *));
memcpy (&new_save_in_use[count_new_page_tables],
&G.save_in_use[0],
count_old_page_tables * sizeof (void *));
free (G.by_depth);
free (G.save_in_use);
G.by_depth = new_by_depth;
G.save_in_use = new_save_in_use;
for (i = G.by_depth_in_use; i > 0; --i)
{
page_entry *p = G.by_depth[i-1];
p->index_by_depth = i-1;
}
if (count_old_page_tables)
push_depth (count_new_page_tables);
}
void
ggc_pch_read (f, addr)
FILE *f;
void *addr;
{
struct ggc_pch_ondisk d;
unsigned i;
char *offs = addr;
unsigned long count_old_page_tables;
unsigned long count_new_page_tables;
count_old_page_tables = G.by_depth_in_use;
clear_marks ();
#ifdef GGC_POISON
poison_pages ();
#endif
if (G.context_depth != 0)
abort ();
G.context_depth = 1;
for (i = 0; i < NUM_ORDERS; i++)
{
page_entry *p;
for (p = G.pages[i]; p != NULL; p = p->next)
p->context_depth = G.context_depth;
}
if (fread (&d, sizeof (d), 1, f) != 1)
fatal_io_error ("can't read PCH file");
for (i = 0; i < NUM_ORDERS; i++)
{
struct page_entry *entry;
char *pte;
size_t bytes;
size_t num_objs;
size_t j;
if (d.totals[i] == 0)
continue;
bytes = ROUND_UP (d.totals[i] * OBJECT_SIZE (i), G.pagesize);
num_objs = bytes / OBJECT_SIZE (i);
entry = xcalloc (1, (sizeof (struct page_entry)
- sizeof (long)
+ BITMAP_SIZE (num_objs + 1)));
entry->bytes = bytes;
entry->page = offs;
entry->context_depth = 0;
offs += bytes;
entry->num_free_objects = 0;
entry->order = i;
for (j = 0;
j + HOST_BITS_PER_LONG <= num_objs + 1;
j += HOST_BITS_PER_LONG)
entry->in_use_p[j / HOST_BITS_PER_LONG] = -1;
for (; j < num_objs + 1; j++)
entry->in_use_p[j / HOST_BITS_PER_LONG]
|= 1L << (j % HOST_BITS_PER_LONG);
for (pte = entry->page;
pte < entry->page + entry->bytes;
pte += G.pagesize)
set_page_table_entry (pte, entry);
if (G.page_tails[i] != NULL)
G.page_tails[i]->next = entry;
else
G.pages[i] = entry;
G.page_tails[i] = entry;
push_by_depth (entry, 0);
}
count_new_page_tables = G.by_depth_in_use - count_old_page_tables;
move_ptes_to_front (count_old_page_tables, count_new_page_tables);
G.allocated = G.allocated_last_gc = offs - (char *)addr;
}