#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.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"
#include "tree-flow.h"
#ifdef ENABLE_VALGRIND_CHECKING
# ifdef HAVE_VALGRIND_MEMCHECK_H
# include <valgrind/memcheck.h>
# elif defined HAVE_MEMCHECK_H
# include <memcheck.h>
# else
# include <valgrind.h>
# endif
#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) \
(RTX_HDR_SIZE + (NSLOTS) * sizeof (rtunion))
#define TREE_EXP_SIZE(OPS) \
(sizeof (struct tree_exp) + ((OPS) - 1) * sizeof (tree))
static const size_t extra_order_size_table[] = {
sizeof (struct stmt_ann_d),
sizeof (struct var_ann_d),
sizeof (struct tree_decl_non_common),
sizeof (struct tree_field_decl),
sizeof (struct tree_parm_decl),
sizeof (struct tree_var_decl),
sizeof (struct tree_list),
sizeof (struct tree_ssa_name),
sizeof (struct function),
sizeof (struct basic_block_def),
sizeof (bitmap_element),
sizeof (struct tree_phi_node) + sizeof (struct phi_arg_d) * 3,
TREE_EXP_SIZE (2),
RTL_SIZE (2),
RTL_SIZE (9),
};
#define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
struct max_alignment {
char c;
union {
HOST_WIDEST_INT i;
long double d;
} 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;
struct page_entry *prev;
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;
#ifdef ENABLE_GC_ALWAYS_COLLECT
struct free_object
{
void *object;
struct free_object *next;
} *free_object_list;
#endif
#ifdef GATHER_STATISTICS
struct
{
unsigned long long total_allocated;
unsigned long long total_overhead;
unsigned long long total_allocated_under32;
unsigned long long total_overhead_under32;
unsigned long long total_allocated_under64;
unsigned long long total_overhead_under64;
unsigned long long total_allocated_under128;
unsigned long long total_overhead_under128;
unsigned long long total_allocated_per_order[NUM_ORDERS];
unsigned long long total_overhead_per_order[NUM_ORDERS];
} stats;
#endif
} G;
#define BITMAP_SIZE(Num_objects) \
(CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
#ifndef GGC_QUIRE_SIZE
# ifdef USING_MMAP
# define GGC_QUIRE_SIZE 256
# else
# define GGC_QUIRE_SIZE 16
# endif
#endif
#define INITIAL_PTE_COUNT 128
static int ggc_allocated_p (const void *);
static page_entry *lookup_page_table_entry (const void *);
static void set_page_table_entry (void *, page_entry *);
#ifdef USING_MMAP
static char *alloc_anon (char *, size_t);
#endif
#ifdef USING_MALLOC_PAGE_GROUPS
static size_t page_group_index (char *, char *);
static void set_page_group_in_use (page_group *, char *);
static void clear_page_group_in_use (page_group *, char *);
#endif
static struct page_entry * alloc_page (unsigned);
static void free_page (struct page_entry *);
static void release_pages (void);
static void clear_marks (void);
static void sweep_pages (void);
static void ggc_recalculate_in_use_p (page_entry *);
static void compute_inverse (unsigned);
static inline void adjust_depth (void);
static void move_ptes_to_front (int, int);
void debug_print_page_list (int);
static void push_depth (unsigned int);
static void push_by_depth (page_entry *, unsigned long *);
inline static void
push_depth (unsigned int i)
{
if (G.depth_in_use >= G.depth_max)
{
G.depth_max *= 2;
G.depth = xrealloc (G.depth, G.depth_max * sizeof (unsigned int));
}
G.depth[G.depth_in_use++] = i;
}
inline static void
push_by_depth (page_entry *p, unsigned long *s)
{
if (G.by_depth_in_use >= G.by_depth_max)
{
G.by_depth_max *= 2;
G.by_depth = xrealloc (G.by_depth,
G.by_depth_max * sizeof (page_entry *));
G.save_in_use = xrealloc (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;
}
#if (GCC_VERSION < 3001)
#define prefetch(X) ((void) X)
#else
#define prefetch(X) __builtin_prefetch (X)
#endif
#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 (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 (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 (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 = 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] = XCNEWVEC (page_entry *, PAGE_L2_SIZE);
base[L1][L2] = entry;
}
void
debug_print_page_list (int order)
{
page_entry *p;
printf ("Head=%p, Tail=%p:\n", (void *) G.pages[order],
(void *) G.page_tails[order]);
p = G.pages[order];
while (p != NULL)
{
printf ("%p(%1d|%3d) -> ", (void *) p, p->context_depth,
p->num_free_objects);
p = p->next;
}
printf ("NULL\n");
fflush (stdout);
}
#ifdef USING_MMAP
static inline char *
alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size)
{
#ifdef HAVE_MMAP_ANON
char *page = mmap (pref, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
#ifdef HAVE_MMAP_DEV_ZERO
char *page = 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 (char *allocation, char *page)
{
return (size_t) (page - allocation) >> G.lg_pagesize;
}
static inline void
set_page_group_in_use (page_group *group, char *page)
{
group->in_use |= 1 << page_group_index (group->allocation, page);
}
static inline void
clear_page_group_in_use (page_group *group, char *page)
{
group->in_use &= ~(1 << page_group_index (group->allocation, page));
}
#endif
static inline struct page_entry *
alloc_page (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 = 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;
}
gcc_assert (tail_slop >= sizeof (page_group));
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 = 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 = 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",
(void *) entry, (unsigned long) OBJECT_SIZE (order), page,
page + entry_size - 1);
return entry;
}
static inline void
adjust_depth (void)
{
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 void
free_page (page_entry *entry)
{
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Deallocating page at %p, data %p-%p\n", (void *) 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];
int i = entry->index_by_depth;
gcc_assert (entry->context_depth == top->context_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;
}
--G.by_depth_in_use;
adjust_depth ();
entry->next = G.free_pages;
G.free_pages = entry;
}
static void
release_pages (void)
{
#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
}
#define NUM_SIZE_LOOKUP 512
static unsigned char size_lookup[NUM_SIZE_LOOKUP] =
{
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, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
};
void *
ggc_alloc_typed_stat (enum gt_types_enum type ATTRIBUTE_UNUSED, size_t size
MEM_STAT_DECL)
{
return ggc_alloc_stat (size PASS_MEM_STAT);
}
void *
ggc_alloc_stat (size_t size MEM_STAT_DECL)
{
size_t order, word, bit, object_offset, object_size;
struct page_entry *entry;
void *result;
if (size < NUM_SIZE_LOOKUP)
{
order = size_lookup[size];
object_size = OBJECT_SIZE (order);
}
else
{
order = 10;
while (size > (object_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;
else
entry->prev = new_entry;
new_entry->next = entry;
new_entry->prev = NULL;
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;
#if GCC_VERSION >= 3004
bit = __builtin_ctzl (~entry->in_use_p[word]);
#else
while ((entry->in_use_p[word] >> bit) & 1)
++bit;
#endif
hint = word * HOST_BITS_PER_LONG + bit;
}
entry->next_bit_hint = hint + 1;
object_offset = hint * object_size;
}
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->prev = NULL;
entry->next = NULL;
entry->prev = G.page_tails[order];
G.page_tails[order]->next = entry;
G.page_tails[order] = entry;
}
result = entry->page + object_offset;
#ifdef GATHER_STATISTICS
ggc_record_overhead (OBJECT_SIZE (order), OBJECT_SIZE (order) - size,
result PASS_MEM_STAT);
#endif
#ifdef ENABLE_GC_CHECKING
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, object_size));
memset (result, 0xaf, object_size);
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) result + size,
object_size - size));
#endif
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
G.allocated += object_size;
timevar_ggc_mem_total += object_size;
#ifdef GATHER_STATISTICS
{
size_t overhead = object_size - size;
G.stats.total_overhead += overhead;
G.stats.total_allocated += object_size;
G.stats.total_overhead_per_order[order] += overhead;
G.stats.total_allocated_per_order[order] += object_size;
if (size <= 32)
{
G.stats.total_overhead_under32 += overhead;
G.stats.total_allocated_under32 += object_size;
}
if (size <= 64)
{
G.stats.total_overhead_under64 += overhead;
G.stats.total_allocated_under64 += object_size;
}
if (size <= 128)
{
G.stats.total_overhead_under128 += overhead;
G.stats.total_allocated_under128 += object_size;
}
}
#endif
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, result,
(void *) entry);
return result;
}
int
ggc_set_mark (const void *p)
{
page_entry *entry;
unsigned bit, word;
unsigned long mask;
entry = lookup_page_table_entry (p);
gcc_assert (entry);
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 (const void *p)
{
page_entry *entry;
unsigned bit, word;
unsigned long mask;
entry = lookup_page_table_entry (p);
gcc_assert (entry);
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 (const void *p)
{
page_entry *pe = lookup_page_table_entry (p);
return OBJECT_SIZE (pe->order);
}
void
ggc_free (void *p)
{
page_entry *pe = lookup_page_table_entry (p);
size_t order = pe->order;
size_t size = OBJECT_SIZE (order);
#ifdef GATHER_STATISTICS
ggc_free_overhead (p);
#endif
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file,
"Freeing object, actual size=%lu, at %p on %p\n",
(unsigned long) size, p, (void *) pe);
#ifdef ENABLE_GC_CHECKING
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (p, size));
memset (p, 0xa5, size);
#endif
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (p, size));
#ifdef ENABLE_GC_ALWAYS_COLLECT
{
struct free_object *fo = XNEW (struct free_object);
fo->object = p;
fo->next = G.free_object_list;
G.free_object_list = fo;
}
#else
{
unsigned int bit_offset, word, bit;
G.allocated -= size;
bit_offset = OFFSET_TO_BIT (((const char *) p) - pe->page, order);
word = bit_offset / HOST_BITS_PER_LONG;
bit = bit_offset % HOST_BITS_PER_LONG;
pe->in_use_p[word] &= ~(1UL << bit);
if (pe->num_free_objects++ == 0)
{
page_entry *p, *q;
q = pe->prev;
if (q && q->num_free_objects == 0)
{
p = pe->next;
q->next = p;
if (!p)
G.page_tails[order] = q;
else
p->prev = q;
pe->next = G.pages[order];
pe->prev = NULL;
G.pages[order]->prev = pe;
G.pages[order] = pe;
}
pe->next_bit_hint = bit_offset;
}
}
#endif
}
static void
compute_inverse (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 (void)
{
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)
internal_error ("open /dev/zero: %m");
#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);
gcc_assert (!((size_t)p & (G.pagesize - 1)));
}
e = XCNEW (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;
i = OBJECT_SIZE (order);
if (i >= NUM_SIZE_LOOKUP)
continue;
for (o = size_lookup[i]; o == size_lookup [i]; --i)
size_lookup[i] = order;
}
G.depth_in_use = 0;
G.depth_max = 10;
G.depth = XNEWVEC (unsigned int, G.depth_max);
G.by_depth_in_use = 0;
G.by_depth_max = INITIAL_PTE_COUNT;
G.by_depth = XNEWVEC (page_entry *, G.by_depth_max);
G.save_in_use = XNEWVEC (unsigned long *, G.by_depth_max);
}
struct alloc_zone *
new_ggc_zone (const char *name ATTRIBUTE_UNUSED)
{
return NULL;
}
void
destroy_ggc_zone (struct alloc_zone *zone ATTRIBUTE_UNUSED)
{
}
static void
ggc_recalculate_in_use_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);
}
gcc_assert (p->num_free_objects < num_objects);
}
static void
clear_marks (void)
{
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);
gcc_assert (!((size_t) p->page & (G.pagesize - 1)));
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 void
sweep_pages (void)
{
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 (next)
next->prev = previous;
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;
p->prev = G.page_tails[order];
G.page_tails[order]->next = p;
G.page_tails[order] = p;
if (! previous)
G.pages[order] = next;
else
previous->next = next;
if (next)
next->prev = previous;
p = previous;
}
}
else if (p != G.pages[order])
{
previous->next = p->next;
if (p->next)
p->next->prev = previous;
p->next = G.pages[order];
p->prev = NULL;
G.pages[order]->prev = p;
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 void
poison_pages (void)
{
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));
}
}
}
}
}
#else
#define poison_pages()
#endif
#ifdef ENABLE_GC_ALWAYS_COLLECT
static void
validate_free_objects (void)
{
struct free_object *f, *next, *still_free = NULL;
for (f = G.free_object_list; f ; f = next)
{
page_entry *pe = lookup_page_table_entry (f->object);
size_t bit, word;
bit = OFFSET_TO_BIT ((char *)f->object - pe->page, pe->order);
word = bit / HOST_BITS_PER_LONG;
bit = bit % HOST_BITS_PER_LONG;
next = f->next;
gcc_assert (!(pe->in_use_p[word] & (1UL << bit)));
if (pe->context_depth != G.context_depth)
{
f->next = still_free;
still_free = f;
}
else
free (f);
}
G.free_object_list = still_free;
}
#else
#define validate_free_objects()
#endif
void
ggc_collect (void)
{
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 && !ggc_force_collect)
return;
timevar_push (TV_GC);
if (!quiet_flag)
fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file, "BEGIN COLLECTING\n");
G.allocated = 0;
release_pages ();
G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
clear_marks ();
ggc_mark_roots ();
#ifdef GATHER_STATISTICS
ggc_prune_overhead_list ();
#endif
poison_pages ();
validate_free_objects ();
sweep_pages ();
G.allocated_last_gc = G.allocated;
timevar_pop (TV_GC);
if (!quiet_flag)
fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file, "END COLLECTING\n");
}
#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
? (x) \
: ((x) < 1024*1024*10 \
? (x) / 1024 \
: (x) / (1024*1024))))
#define STAT_LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
void
ggc_print_statistics (void)
{
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,
"Memory still allocated at the end of the compilation process\n");
fprintf (stderr, "%-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), STAT_LABEL (allocated),
SCALE (in_use), STAT_LABEL (in_use),
SCALE (overhead), STAT_LABEL (overhead));
total_overhead += overhead;
}
fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
SCALE (G.bytes_mapped), STAT_LABEL (G.bytes_mapped),
SCALE (G.allocated), STAT_LABEL(G.allocated),
SCALE (total_overhead), STAT_LABEL (total_overhead));
#ifdef GATHER_STATISTICS
{
fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
fprintf (stderr, "Total Overhead: %10lld\n",
G.stats.total_overhead);
fprintf (stderr, "Total Allocated: %10lld\n",
G.stats.total_allocated);
fprintf (stderr, "Total Overhead under 32B: %10lld\n",
G.stats.total_overhead_under32);
fprintf (stderr, "Total Allocated under 32B: %10lld\n",
G.stats.total_allocated_under32);
fprintf (stderr, "Total Overhead under 64B: %10lld\n",
G.stats.total_overhead_under64);
fprintf (stderr, "Total Allocated under 64B: %10lld\n",
G.stats.total_allocated_under64);
fprintf (stderr, "Total Overhead under 128B: %10lld\n",
G.stats.total_overhead_under128);
fprintf (stderr, "Total Allocated under 128B: %10lld\n",
G.stats.total_allocated_under128);
for (i = 0; i < NUM_ORDERS; i++)
if (G.stats.total_allocated_per_order[i])
{
fprintf (stderr, "Total Overhead page size %7d: %10lld\n",
OBJECT_SIZE (i), G.stats.total_overhead_per_order[i]);
fprintf (stderr, "Total Allocated page size %7d: %10lld\n",
OBJECT_SIZE (i), G.stats.total_allocated_per_order[i]);
}
}
#endif
}
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 (void)
{
return XCNEW (struct ggc_pch_data);
}
void
ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
size_t size, bool is_string ATTRIBUTE_UNUSED,
enum gt_types_enum type ATTRIBUTE_UNUSED)
{
unsigned order;
if (size < NUM_SIZE_LOOKUP)
order = size_lookup[size];
else
{
order = 10;
while (size > OBJECT_SIZE (order))
order++;
}
d->d.totals[order]++;
}
size_t
ggc_pch_total_size (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 (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 (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
size_t size, bool is_string ATTRIBUTE_UNUSED,
enum gt_types_enum type ATTRIBUTE_UNUSED)
{
unsigned order;
char *result;
if (size < NUM_SIZE_LOOKUP)
order = size_lookup[size];
else
{
order = 10;
while (size > OBJECT_SIZE (order))
order++;
}
result = (char *) d->base[order];
d->base[order] += OBJECT_SIZE (order);
return result;
}
void
ggc_pch_prepare_write (struct ggc_pch_data *d ATTRIBUTE_UNUSED,
FILE *f ATTRIBUTE_UNUSED)
{
}
void
ggc_pch_write_object (struct ggc_pch_data *d ATTRIBUTE_UNUSED,
FILE *f, void *x, void *newx ATTRIBUTE_UNUSED,
size_t size, bool is_string ATTRIBUTE_UNUSED)
{
unsigned order;
static const char emptyBytes[256];
if (size < NUM_SIZE_LOOKUP)
order = size_lookup[size];
else
{
order = 10;
while (size > OBJECT_SIZE (order))
order++;
}
if (fwrite (x, size, 1, f) != 1)
fatal_error ("can't write PCH file: %m");
if (size != OBJECT_SIZE (order))
{
unsigned padding = OBJECT_SIZE(order) - size;
if (padding <= sizeof(emptyBytes))
{
if (fwrite (emptyBytes, 1, padding, f) != padding)
fatal_error ("can't write PCH file");
}
else
{
if (fseek (f, padding, SEEK_CUR) != 0)
fatal_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_error ("can't write PCH file: %m");
}
void
ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
{
if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
fatal_error ("can't write PCH file: %m");
free (d);
}
static void
move_ptes_to_front (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 = XNEWVEC (page_entry *, G.by_depth_max);
new_save_in_use = XNEWVEC (unsigned long *, G.by_depth_max);
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 (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 ENABLE_GC_CHECKING
poison_pages ();
#endif
gcc_assert (!G.context_depth);
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_error ("can't read PCH file: %m");
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;
}