#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 "varray.h"
#include "flags.h"
#include "ggc.h"
#include "timevar.h"
#include "params.h"
#include "bitmap.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)
#define VALGRIND_MALLOCLIKE_BLOCK(w,x,y,z)
#define VALGRIND_FREELIKE_BLOCK(x,y)
#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
#error Zone collector requires mmap
#endif
#if (GCC_VERSION < 3001)
#define prefetch(X) ((void) X)
#define prefetchw(X) ((void) X)
#else
#define prefetch(X) __builtin_prefetch (X)
#define prefetchw(X) __builtin_prefetch (X, 1, 3)
#endif
#define GGC_DEBUG_LEVEL (0)
#ifndef HOST_BITS_PER_PTR
#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
#endif
struct alloc_chunk {
struct alloc_chunk *next_free;
unsigned int size;
};
#define PAGE_OVERHEAD (offsetof (struct small_page_entry, alloc_bits))
#define GGC_PAGE_SIZE 4096
#define GGC_PAGE_MASK (GGC_PAGE_SIZE - 1)
#define GGC_PAGE_SHIFT 12
#if 0
#define GGC_PAGE_SIZE G.pagesize
#define GGC_PAGE_MASK G.page_mask
#define GGC_PAGE_SHIFT G.lg_pagesize
#endif
#define SMALL_PAGE_SIZE GGC_PAGE_SIZE
#define NUM_FREE_BINS 64
#define FREE_BIN_DELTA MAX_ALIGNMENT
#define SIZE_BIN_DOWN(SIZE) ((SIZE) / FREE_BIN_DELTA)
#define BYTES_PER_ALLOC_BIT MAX_ALIGNMENT
#define BYTES_PER_MARK_BIT BYTES_PER_ALLOC_BIT
#define BYTES_PER_MARK_WORD (8 * BYTES_PER_MARK_BIT * sizeof (mark_type))
struct max_alignment {
char c;
union {
HOST_WIDEST_INT i;
double d;
} u;
};
#define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
#define ROUND_UP(x, f) (CEIL (x, f) * (f))
typedef unsigned int alloc_type;
typedef unsigned int mark_type;
#define alloc_ffs(x) ffs(x)
typedef struct page_entry
{
char *page;
struct alloc_zone *zone;
#ifdef GATHER_STATISTICS
size_t survived;
#endif
bool large_p;
bool pch_p;
} page_entry;
struct small_page_entry
{
struct page_entry common;
struct small_page_entry *next;
mark_type *mark_bits;
alloc_type alloc_bits[1];
};
struct large_page_entry
{
struct page_entry common;
struct large_page_entry *next;
size_t bytes;
struct large_page_entry *prev;
bool mark_p;
};
#define PAGE_L1_BITS (8)
#define PAGE_L2_BITS (32 - PAGE_L1_BITS - GGC_PAGE_SHIFT)
#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) >> GGC_PAGE_SHIFT) & ((1 << PAGE_L2_BITS) - 1))
#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
{
struct alloc_zone *zones;
page_table lookup;
size_t pagesize;
size_t lg_pagesize;
size_t page_mask;
size_t small_page_overhead;
#if defined (HAVE_MMAP_DEV_ZERO)
int dev_zero_fd;
#endif
size_t quire_size;
FILE *debug_file;
} G;
struct alloc_zone
{
char *cached_free;
size_t cached_free_size;
struct alloc_chunk *free_chunks[NUM_FREE_BINS + 1];
size_t high_free_bin;
size_t allocated;
struct small_page_entry *pages;
struct large_page_entry *large_pages;
mark_type *mark_bits;
const char *name;
size_t n_small_pages;
size_t allocated_last_gc;
size_t bytes_mapped;
struct small_page_entry *free_pages;
struct alloc_zone *next_zone;
bool was_collected;
bool dead;
#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;
} stats;
#endif
} main_zone;
struct alloc_zone rtl_zone;
struct alloc_zone tree_zone;
struct alloc_zone tree_id_zone;
struct pch_zone
{
char *page;
char *end;
size_t bytes;
alloc_type *alloc_bits;
mark_type *mark_bits;
} pch_zone;
#ifdef USING_MMAP
static char *alloc_anon (char *, size_t, struct alloc_zone *);
#endif
static struct small_page_entry * alloc_small_page (struct alloc_zone *);
static struct large_page_entry * alloc_large_page (size_t, struct alloc_zone *);
static void free_chunk (char *, size_t, struct alloc_zone *);
static void free_small_page (struct small_page_entry *);
static void free_large_page (struct large_page_entry *);
static void release_pages (struct alloc_zone *);
static void sweep_pages (struct alloc_zone *);
static bool ggc_collect_1 (struct alloc_zone *, bool);
static void new_ggc_zone_1 (struct alloc_zone *, const char *);
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] = xcalloc (PAGE_L2_SIZE, sizeof (page_entry *));
base[L1][L2] = entry;
}
static inline struct page_entry *
zone_get_object_page (const void *object)
{
return lookup_page_table_entry (object);
}
static inline unsigned int
zone_get_object_alloc_word (const void *object)
{
return (((size_t) object & (GGC_PAGE_SIZE - 1))
/ (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
}
static inline unsigned int
zone_get_object_alloc_bit (const void *object)
{
return (((size_t) object / BYTES_PER_ALLOC_BIT)
% (8 * sizeof (alloc_type)));
}
static inline unsigned int
zone_get_object_mark_word (const void *object)
{
return (((size_t) object & (GGC_PAGE_SIZE - 1))
/ (8 * sizeof (mark_type) * BYTES_PER_MARK_BIT));
}
static inline unsigned int
zone_get_object_mark_bit (const void *object)
{
return (((size_t) object / BYTES_PER_MARK_BIT)
% (8 * sizeof (mark_type)));
}
static inline void
zone_set_object_alloc_bit (const void *object)
{
struct small_page_entry *page
= (struct small_page_entry *) zone_get_object_page (object);
unsigned int start_word = zone_get_object_alloc_word (object);
unsigned int start_bit = zone_get_object_alloc_bit (object);
page->alloc_bits[start_word] |= 1L << start_bit;
}
static inline void
zone_clear_object_alloc_bit (struct small_page_entry *page,
const void *object)
{
unsigned int start_word = zone_get_object_alloc_word (object);
unsigned int start_bit = zone_get_object_alloc_bit (object);
page->alloc_bits[start_word] &= ~(1L << start_bit);
}
static inline size_t
zone_object_size_1 (alloc_type *alloc_bits,
size_t start_word, size_t start_bit,
size_t max_size)
{
size_t size;
alloc_type alloc_word;
int indx;
alloc_word = alloc_bits[start_word++];
if (start_bit)
{
indx = alloc_ffs (alloc_word >> start_bit);
if (indx)
return indx * BYTES_PER_ALLOC_BIT;
size = (sizeof (alloc_type) * 8 - start_bit + 1) * BYTES_PER_ALLOC_BIT;
if (size >= max_size)
return max_size;
alloc_word = alloc_bits[start_word++];
}
else
size = BYTES_PER_ALLOC_BIT;
while (alloc_word == 0)
{
size += sizeof (alloc_type) * 8 * BYTES_PER_ALLOC_BIT;
if (size >= max_size)
return max_size;
alloc_word = alloc_bits[start_word++];
}
indx = alloc_ffs (alloc_word);
return size + (indx - 1) * BYTES_PER_ALLOC_BIT;
}
static inline size_t
zone_find_object_size (struct small_page_entry *page,
const void *object)
{
const char *object_midptr = (const char *) object + BYTES_PER_ALLOC_BIT;
unsigned int start_word = zone_get_object_alloc_word (object_midptr);
unsigned int start_bit = zone_get_object_alloc_bit (object_midptr);
size_t max_size = (page->common.page + SMALL_PAGE_SIZE
- (char *) object);
return zone_object_size_1 (page->alloc_bits, start_word, start_bit,
max_size);
}
static void
zone_allocate_marks (void)
{
struct alloc_zone *zone;
for (zone = G.zones; zone; zone = zone->next_zone)
{
struct small_page_entry *page;
mark_type *cur_marks;
size_t mark_words, mark_words_per_page;
#ifdef ENABLE_CHECKING
size_t n = 0;
#endif
mark_words_per_page
= (GGC_PAGE_SIZE + BYTES_PER_MARK_WORD - 1) / BYTES_PER_MARK_WORD;
mark_words = zone->n_small_pages * mark_words_per_page;
zone->mark_bits = (mark_type *) xcalloc (sizeof (mark_type),
mark_words);
cur_marks = zone->mark_bits;
for (page = zone->pages; page; page = page->next)
{
page->mark_bits = cur_marks;
cur_marks += mark_words_per_page;
#ifdef ENABLE_CHECKING
n++;
#endif
}
#ifdef ENABLE_CHECKING
gcc_assert (n == zone->n_small_pages);
#endif
}
if (pch_zone.bytes)
pch_zone.mark_bits
= (mark_type *) xcalloc (sizeof (mark_type),
CEIL (pch_zone.bytes, BYTES_PER_MARK_WORD));
}
static void
zone_free_marks (void)
{
struct alloc_zone *zone;
for (zone = G.zones; zone; zone = zone->next_zone)
if (zone->mark_bits)
{
free (zone->mark_bits);
zone->mark_bits = NULL;
}
if (pch_zone.bytes)
{
free (pch_zone.mark_bits);
pch_zone.mark_bits = NULL;
}
}
#ifdef USING_MMAP
static inline char *
alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, struct alloc_zone *zone)
{
#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);
}
zone->bytes_mapped += size;
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, size));
return page;
}
#endif
static struct small_page_entry *
alloc_small_page (struct alloc_zone *zone)
{
struct small_page_entry *entry;
entry = zone->free_pages;
if (entry != NULL)
{
zone->free_pages = entry->next;
}
else
{
struct small_page_entry *e, *f = zone->free_pages;
int i;
char *page;
page = alloc_anon (NULL, GGC_PAGE_SIZE * G.quire_size, zone);
for (i = G.quire_size - 1; i >= 1; i--)
{
e = xcalloc (1, G.small_page_overhead);
e->common.page = page + (i << GGC_PAGE_SHIFT);
e->common.zone = zone;
e->next = f;
f = e;
set_page_table_entry (e->common.page, &e->common);
}
zone->free_pages = f;
entry = xcalloc (1, G.small_page_overhead);
entry->common.page = page;
entry->common.zone = zone;
set_page_table_entry (page, &entry->common);
}
zone->n_small_pages++;
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Allocating %s page at %p, data %p-%p\n",
entry->common.zone->name, (PTR) entry, entry->common.page,
entry->common.page + SMALL_PAGE_SIZE - 1);
return entry;
}
static struct large_page_entry *
alloc_large_page (size_t size, struct alloc_zone *zone)
{
struct large_page_entry *entry;
char *page;
size_t needed_size;
needed_size = size + sizeof (struct large_page_entry);
page = xmalloc (needed_size);
entry = (struct large_page_entry *) page;
entry->next = NULL;
entry->common.page = page + sizeof (struct large_page_entry);
entry->common.large_p = true;
entry->common.pch_p = false;
entry->common.zone = zone;
#ifdef GATHER_STATISTICS
entry->common.survived = 0;
#endif
entry->mark_p = false;
entry->bytes = size;
entry->prev = NULL;
set_page_table_entry (entry->common.page, &entry->common);
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Allocating %s large page at %p, data %p-%p\n",
entry->common.zone->name, (PTR) entry, entry->common.page,
entry->common.page + SMALL_PAGE_SIZE - 1);
return entry;
}
static inline void
free_small_page (struct small_page_entry *entry)
{
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Deallocating %s page at %p, data %p-%p\n",
entry->common.zone->name, (PTR) entry,
entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
gcc_assert (!entry->common.large_p);
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->common.page,
SMALL_PAGE_SIZE));
entry->next = entry->common.zone->free_pages;
entry->common.zone->free_pages = entry;
entry->common.zone->n_small_pages--;
}
static inline void
free_large_page (struct large_page_entry *entry)
{
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
"Deallocating %s page at %p, data %p-%p\n",
entry->common.zone->name, (PTR) entry,
entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
gcc_assert (entry->common.large_p);
set_page_table_entry (entry->common.page, NULL);
free (entry);
}
static void
release_pages (struct alloc_zone *zone)
{
#ifdef USING_MMAP
struct small_page_entry *p, *next;
char *start;
size_t len;
p = zone->free_pages;
while (p)
{
start = p->common.page;
next = p->next;
len = SMALL_PAGE_SIZE;
set_page_table_entry (p->common.page, NULL);
p = next;
while (p && p->common.page == start + len)
{
next = p->next;
len += SMALL_PAGE_SIZE;
set_page_table_entry (p->common.page, NULL);
p = next;
}
munmap (start, len);
zone->bytes_mapped -= len;
}
zone->free_pages = NULL;
#endif
}
static inline void
free_chunk (char *ptr, size_t size, struct alloc_zone *zone)
{
struct alloc_chunk *chunk = (struct alloc_chunk *) ptr;
size_t bin = 0;
bin = SIZE_BIN_DOWN (size);
gcc_assert (bin != 0);
if (bin > NUM_FREE_BINS)
{
bin = 0;
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk, sizeof (struct alloc_chunk)));
chunk->size = size;
chunk->next_free = zone->free_chunks[bin];
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (ptr + sizeof (struct alloc_chunk),
size - sizeof (struct alloc_chunk)));
}
else
{
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk, sizeof (struct alloc_chunk *)));
chunk->next_free = zone->free_chunks[bin];
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (ptr + sizeof (struct alloc_chunk *),
size - sizeof (struct alloc_chunk *)));
}
zone->free_chunks[bin] = chunk;
if (bin > zone->high_free_bin)
zone->high_free_bin = bin;
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file, "Deallocating object, chunk=%p\n", (void *)chunk);
}
void *
ggc_alloc_zone_stat (size_t orig_size, struct alloc_zone *zone
MEM_STAT_DECL)
{
size_t bin;
size_t csize;
struct small_page_entry *entry;
struct alloc_chunk *chunk, **pp;
void *result;
size_t size = orig_size;
if (size == 0)
size = MAX_ALIGNMENT;
else
size = (size + MAX_ALIGNMENT - 1) & -MAX_ALIGNMENT;
if (size <= zone->cached_free_size)
{
result = zone->cached_free;
zone->cached_free_size -= size;
if (zone->cached_free_size)
{
zone->cached_free += size;
zone_set_object_alloc_bit (zone->cached_free);
}
goto found;
}
bin = SIZE_BIN_DOWN (size);
if (bin <= NUM_FREE_BINS
&& (chunk = zone->free_chunks[bin]) != NULL)
{
zone->free_chunks[bin] = chunk->next_free;
result = chunk;
goto found;
}
if (zone->high_free_bin > bin)
{
while (zone->high_free_bin > bin
&& zone->free_chunks[zone->high_free_bin] == NULL)
zone->high_free_bin--;
if (zone->high_free_bin > bin)
{
size_t tbin = zone->high_free_bin;
chunk = zone->free_chunks[tbin];
zone->free_chunks[tbin] = chunk->next_free;
result = (char *) chunk;
if (zone->cached_free_size)
free_chunk (zone->cached_free, zone->cached_free_size, zone);
chunk = (struct alloc_chunk *) ((char *) result + size);
zone->cached_free = (char *) chunk;
zone->cached_free_size = (tbin - bin) * FREE_BIN_DELTA;
zone_set_object_alloc_bit (chunk);
goto found;
}
}
pp = &(zone->free_chunks[0]);
chunk = *pp;
while (chunk && chunk->size < size)
{
pp = &chunk->next_free;
chunk = *pp;
}
if (chunk)
{
*pp = chunk->next_free;
result = (char *) chunk;
csize = chunk->size;
if (csize > size)
{
if (zone->cached_free_size)
free_chunk (zone->cached_free, zone->cached_free_size, zone);
chunk = (struct alloc_chunk *) ((char *) result + size);
zone->cached_free = (char *) chunk;
zone->cached_free_size = csize - size;
zone_set_object_alloc_bit (chunk);
}
goto found;
}
if (size > GGC_PAGE_SIZE)
{
struct large_page_entry *entry = alloc_large_page (size, zone);
#ifdef GATHER_STATISTICS
entry->common.survived = 0;
#endif
entry->next = zone->large_pages;
if (zone->large_pages)
zone->large_pages->prev = entry;
zone->large_pages = entry;
result = entry->common.page;
goto found;
}
entry = alloc_small_page (zone);
entry->next = zone->pages;
zone->pages = entry;
entry->alloc_bits[0] = 1;
result = entry->common.page;
if (size < SMALL_PAGE_SIZE)
{
if (zone->cached_free_size)
free_chunk (zone->cached_free, zone->cached_free_size, zone);
zone->cached_free = (char *) result + size;
zone->cached_free_size = SMALL_PAGE_SIZE - size;
zone_set_object_alloc_bit (zone->cached_free);
}
found:
prefetchw (result);
#ifdef ENABLE_GC_CHECKING
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
memset (result, 0xaf, size);
VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (result + orig_size,
size - orig_size));
#endif
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, orig_size));
zone->allocated += size;
timevar_ggc_mem_total += size;
#ifdef GATHER_STATISTICS
ggc_record_overhead (orig_size, size - orig_size, result PASS_MEM_STAT);
{
size_t object_size = size;
size_t overhead = object_size - orig_size;
zone->stats.total_overhead += overhead;
zone->stats.total_allocated += object_size;
if (orig_size <= 32)
{
zone->stats.total_overhead_under32 += overhead;
zone->stats.total_allocated_under32 += object_size;
}
if (orig_size <= 64)
{
zone->stats.total_overhead_under64 += overhead;
zone->stats.total_allocated_under64 += object_size;
}
if (orig_size <= 128)
{
zone->stats.total_overhead_under128 += overhead;
zone->stats.total_allocated_under128 += object_size;
}
}
#endif
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file, "Allocating object, size=%lu at %p\n",
(unsigned long) size, result);
return result;
}
void *
ggc_alloc_typed_stat (enum gt_types_enum gte, size_t size
MEM_STAT_DECL)
{
switch (gte)
{
case gt_ggc_e_14lang_tree_node:
return ggc_alloc_zone_pass_stat (size, &tree_zone);
case gt_ggc_e_7rtx_def:
return ggc_alloc_zone_pass_stat (size, &rtl_zone);
case gt_ggc_e_9rtvec_def:
return ggc_alloc_zone_pass_stat (size, &rtl_zone);
default:
return ggc_alloc_zone_pass_stat (size, &main_zone);
}
}
void *
ggc_alloc_stat (size_t size MEM_STAT_DECL)
{
return ggc_alloc_zone_pass_stat (size, &main_zone);
}
#ifdef ENABLE_GC_CHECKING
#define poison_region(PTR, SIZE) \
memset ((PTR), 0xa5, (SIZE))
#else
#define poison_region(PTR, SIZE)
#endif
void
ggc_free (void *p)
{
struct page_entry *page;
#ifdef GATHER_STATISTICS
ggc_free_overhead (p);
#endif
poison_region (p, ggc_get_size (p));
page = zone_get_object_page (p);
if (page->large_p)
{
struct large_page_entry *large_page
= (struct large_page_entry *) page;
if (large_page->prev)
large_page->prev->next = large_page->next;
else
{
gcc_assert (large_page->common.zone->large_pages == large_page);
large_page->common.zone->large_pages = large_page->next;
}
if (large_page->next)
large_page->next->prev = large_page->prev;
large_page->common.zone->allocated -= large_page->bytes;
free_large_page (large_page);
}
else if (page->pch_p)
;
else
{
size_t size = ggc_get_size (p);
page->zone->allocated -= size;
free_chunk (p, size, page->zone);
}
}
int
ggc_set_mark (const void *p)
{
struct page_entry *page;
const char *ptr = (const char *) p;
page = zone_get_object_page (p);
if (page->pch_p)
{
size_t mark_word, mark_bit, offset;
offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
mark_word = offset / (8 * sizeof (mark_type));
mark_bit = offset % (8 * sizeof (mark_type));
if (pch_zone.mark_bits[mark_word] & (1 << mark_bit))
return 1;
pch_zone.mark_bits[mark_word] |= (1 << mark_bit);
}
else if (page->large_p)
{
struct large_page_entry *large_page
= (struct large_page_entry *) page;
if (large_page->mark_p)
return 1;
large_page->mark_p = true;
}
else
{
struct small_page_entry *small_page
= (struct small_page_entry *) page;
if (small_page->mark_bits[zone_get_object_mark_word (p)]
& (1 << zone_get_object_mark_bit (p)))
return 1;
small_page->mark_bits[zone_get_object_mark_word (p)]
|= (1 << zone_get_object_mark_bit (p));
}
if (GGC_DEBUG_LEVEL >= 4)
fprintf (G.debug_file, "Marking %p\n", p);
return 0;
}
int
ggc_marked_p (const void *p)
{
struct page_entry *page;
const char *ptr = p;
page = zone_get_object_page (p);
if (page->pch_p)
{
size_t mark_word, mark_bit, offset;
offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
mark_word = offset / (8 * sizeof (mark_type));
mark_bit = offset % (8 * sizeof (mark_type));
return (pch_zone.mark_bits[mark_word] & (1 << mark_bit)) != 0;
}
if (page->large_p)
{
struct large_page_entry *large_page
= (struct large_page_entry *) page;
return large_page->mark_p;
}
else
{
struct small_page_entry *small_page
= (struct small_page_entry *) page;
return 0 != (small_page->mark_bits[zone_get_object_mark_word (p)]
& (1 << zone_get_object_mark_bit (p)));
}
}
size_t
ggc_get_size (const void *p)
{
struct page_entry *page;
const char *ptr = (const char *) p;
page = zone_get_object_page (p);
if (page->pch_p)
{
size_t alloc_word, alloc_bit, offset, max_size;
offset = (ptr - pch_zone.page) / BYTES_PER_ALLOC_BIT + 1;
alloc_word = offset / (8 * sizeof (alloc_type));
alloc_bit = offset % (8 * sizeof (alloc_type));
max_size = pch_zone.bytes - (ptr - pch_zone.page);
return zone_object_size_1 (pch_zone.alloc_bits, alloc_word, alloc_bit,
max_size);
}
if (page->large_p)
return ((struct large_page_entry *)page)->bytes;
else
return zone_find_object_size ((struct small_page_entry *) page, p);
}
void
init_ggc (void)
{
gcc_assert (FREE_BIN_DELTA == MAX_ALIGNMENT);
main_zone.name = "Main zone";
G.zones = &main_zone;
new_ggc_zone_1 (&rtl_zone, "RTL zone");
new_ggc_zone_1 (&tree_zone, "Tree zone");
new_ggc_zone_1 (&tree_id_zone, "Tree identifier zone");
G.pagesize = getpagesize();
G.lg_pagesize = exact_log2 (G.pagesize);
G.page_mask = ~(G.pagesize - 1);
gcc_assert ((G.pagesize & (GGC_PAGE_SIZE - 1)) == 0);
G.quire_size = 16 * G.pagesize / GGC_PAGE_SIZE;
G.small_page_overhead
= PAGE_OVERHEAD + (GGC_PAGE_SIZE / BYTES_PER_ALLOC_BIT / 8);
#ifdef HAVE_MMAP_DEV_ZERO
G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
gcc_assert (G.dev_zero_fd != -1);
#endif
#if 0
G.debug_file = fopen ("ggc-mmap.debug", "w");
setlinebuf (G.debug_file);
#else
G.debug_file = stdout;
#endif
#ifdef USING_MMAP
{
char *p = alloc_anon (NULL, G.pagesize, &main_zone);
struct small_page_entry *e;
if ((size_t)p & (G.pagesize - 1))
{
p = alloc_anon (NULL, G.pagesize, &main_zone);
gcc_assert (!((size_t)p & (G.pagesize - 1)));
}
if (GGC_PAGE_SIZE == G.pagesize)
{
e = xcalloc (1, G.small_page_overhead);
e->common.page = p;
e->common.zone = &main_zone;
e->next = main_zone.free_pages;
set_page_table_entry (e->common.page, &e->common);
main_zone.free_pages = e;
}
else
{
munmap (p, G.pagesize);
}
}
#endif
}
static void
new_ggc_zone_1 (struct alloc_zone *new_zone, const char * name)
{
new_zone->name = name;
new_zone->next_zone = G.zones->next_zone;
G.zones->next_zone = new_zone;
}
struct alloc_zone *
new_ggc_zone (const char * name)
{
struct alloc_zone *new_zone = xcalloc (1, sizeof (struct alloc_zone));
new_ggc_zone_1 (new_zone, name);
return new_zone;
}
void
destroy_ggc_zone (struct alloc_zone * dead_zone)
{
struct alloc_zone *z;
for (z = G.zones; z && z->next_zone != dead_zone; z = z->next_zone)
continue;
gcc_assert (z);
z->dead = true;
}
static void
sweep_pages (struct alloc_zone *zone)
{
struct large_page_entry **lpp, *lp, *lnext;
struct small_page_entry **spp, *sp, *snext;
char *last_free;
size_t allocated = 0;
bool nomarksinpage;
memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
zone->high_free_bin = 0;
zone->cached_free = NULL;
zone->cached_free_size = 0;
lpp = &zone->large_pages;
for (lp = zone->large_pages; lp != NULL; lp = lnext)
{
gcc_assert (lp->common.large_p);
lnext = lp->next;
#ifdef GATHER_STATISTICS
lp->common.survived++;
#endif
if (lp->mark_p)
{
lp->mark_p = false;
allocated += lp->bytes;
lpp = &lp->next;
}
else
{
*lpp = lnext;
#ifdef ENABLE_GC_CHECKING
memset (lp->common.page, 0xb5, SMALL_PAGE_SIZE);
#endif
if (lp->prev)
lp->prev->next = lp->next;
if (lp->next)
lp->next->prev = lp->prev;
free_large_page (lp);
}
}
spp = &zone->pages;
for (sp = zone->pages; sp != NULL; sp = snext)
{
char *object, *last_object;
char *end;
alloc_type *alloc_word_p;
mark_type *mark_word_p;
gcc_assert (!sp->common.large_p);
snext = sp->next;
#ifdef GATHER_STATISTICS
sp->common.survived++;
#endif
last_object = object = sp->common.page;
end = sp->common.page + SMALL_PAGE_SIZE;
last_free = NULL;
nomarksinpage = true;
mark_word_p = sp->mark_bits;
alloc_word_p = sp->alloc_bits;
gcc_assert (BYTES_PER_ALLOC_BIT == BYTES_PER_MARK_BIT);
object = sp->common.page;
do
{
unsigned int i, n;
alloc_type alloc_word;
mark_type mark_word;
alloc_word = *alloc_word_p++;
mark_word = *mark_word_p++;
if (mark_word)
nomarksinpage = false;
i = 0;
while ((n = alloc_ffs (alloc_word)) != 0)
{
alloc_word >>= n - 1;
mark_word >>= n - 1;
object += BYTES_PER_MARK_BIT * (n - 1);
if (mark_word & 1)
{
if (last_free)
{
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (last_free,
object
- last_free));
poison_region (last_free, object - last_free);
free_chunk (last_free, object - last_free, zone);
last_free = NULL;
}
else
allocated += object - last_object;
last_object = object;
}
else
{
if (last_free == NULL)
{
last_free = object;
allocated += object - last_object;
}
else
zone_clear_object_alloc_bit (sp, object);
}
alloc_word >>= 1;
mark_word >>= 1;
object += BYTES_PER_MARK_BIT;
i += n;
}
object += BYTES_PER_MARK_BIT * (8 * sizeof (alloc_type) - i);
}
while (object < end);
if (nomarksinpage)
{
*spp = snext;
#ifdef ENABLE_GC_CHECKING
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (sp->common.page, SMALL_PAGE_SIZE));
memset (sp->common.page, 0xb5, SMALL_PAGE_SIZE);
#endif
free_small_page (sp);
continue;
}
else if (last_free)
{
VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (last_free,
object - last_free));
poison_region (last_free, object - last_free);
free_chunk (last_free, object - last_free, zone);
}
else
allocated += object - last_object;
spp = &sp->next;
}
zone->allocated = allocated;
}
static bool
ggc_collect_1 (struct alloc_zone *zone, bool need_marking)
{
#if 0
{
int i;
for (i = 0; i < NUM_FREE_BINS + 1; i++)
{
struct alloc_chunk *chunk;
int n, tot;
n = 0;
tot = 0;
chunk = zone->free_chunks[i];
while (chunk)
{
n++;
tot += chunk->size;
chunk = chunk->next_free;
}
fprintf (stderr, "Bin %d: %d free chunks (%d bytes)\n",
i, n, tot);
}
}
#endif
if (!quiet_flag)
fprintf (stderr, " {%s GC %luk -> ",
zone->name, (unsigned long) zone->allocated / 1024);
zone->allocated = 0;
release_pages (zone);
if (need_marking)
{
zone_allocate_marks ();
ggc_mark_roots ();
#ifdef GATHER_STATISTICS
ggc_prune_overhead_list ();
#endif
}
sweep_pages (zone);
zone->was_collected = true;
zone->allocated_last_gc = zone->allocated;
if (!quiet_flag)
fprintf (stderr, "%luk}", (unsigned long) zone->allocated / 1024);
return true;
}
#ifdef GATHER_STATISTICS
static float
calculate_average_page_survival (struct alloc_zone *zone)
{
float count = 0.0;
float survival = 0.0;
struct small_page_entry *p;
struct large_page_entry *lp;
for (p = zone->pages; p; p = p->next)
{
count += 1.0;
survival += p->common.survived;
}
for (lp = zone->large_pages; lp; lp = lp->next)
{
count += 1.0;
survival += lp->common.survived;
}
return survival/count;
}
#endif
void
ggc_collect (void)
{
struct alloc_zone *zone;
bool marked = false;
timevar_push (TV_GC);
if (!ggc_force_collect)
{
float allocated_last_gc = 0, allocated = 0, min_expand;
for (zone = G.zones; zone; zone = zone->next_zone)
{
allocated_last_gc += zone->allocated_last_gc;
allocated += zone->allocated;
}
allocated_last_gc =
MAX (allocated_last_gc,
(size_t) PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
if (allocated < allocated_last_gc + min_expand)
{
timevar_pop (TV_GC);
return;
}
}
main_zone.was_collected = false;
marked |= ggc_collect_1 (&main_zone, true);
if (main_zone.was_collected)
{
struct alloc_zone *zone;
for (zone = main_zone.next_zone; zone; zone = zone->next_zone)
{
zone->was_collected = false;
marked |= ggc_collect_1 (zone, !marked);
}
}
#ifdef GATHER_STATISTICS
if (GGC_DEBUG_LEVEL >= 2)
{
for (zone = G.zones; zone; zone = zone->next_zone)
{
if (zone->was_collected)
{
float f = calculate_average_page_survival (zone);
printf ("Average page survival in zone `%s' is %f\n",
zone->name, f);
}
}
}
#endif
if (marked)
zone_free_marks ();
for (zone = G.zones; zone && zone->next_zone; zone = zone->next_zone)
{
if (zone->next_zone->dead)
{
struct alloc_zone *dead_zone = zone->next_zone;
printf ("Zone `%s' is dead and will be freed.\n", dead_zone->name);
gcc_assert (!dead_zone->allocated);
zone->next_zone = zone->next_zone->next_zone;
release_pages (dead_zone);
free (dead_zone);
}
}
timevar_pop (TV_GC);
}
#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 (void)
{
struct alloc_zone *zone;
struct ggc_statistics stats;
size_t total_overhead = 0, total_allocated = 0, total_bytes_mapped = 0;
size_t pte_overhead, i;
memset (&stats, 0, sizeof (stats));
ggc_force_collect = true;
ggc_print_common_statistics (stderr, &stats);
ggc_force_collect = false;
for (zone = G.zones; zone; zone = zone->next_zone)
release_pages (zone);
fprintf (stderr,
"Memory still allocated at the end of the compilation process\n");
fprintf (stderr, "%20s %10s %10s %10s\n",
"Zone", "Allocated", "Used", "Overhead");
for (zone = G.zones; zone; zone = zone->next_zone)
{
struct large_page_entry *large_page;
size_t overhead, allocated, in_use;
if (!zone->pages && !zone->large_pages)
continue;
allocated = in_use = 0;
overhead = sizeof (struct alloc_zone);
for (large_page = zone->large_pages; large_page != NULL;
large_page = large_page->next)
{
allocated += large_page->bytes;
in_use += large_page->bytes;
overhead += sizeof (struct large_page_entry);
}
allocated += GGC_PAGE_SIZE * zone->n_small_pages;
in_use += GGC_PAGE_SIZE * zone->n_small_pages;
overhead += G.small_page_overhead * zone->n_small_pages;
for (i = 0; i <= NUM_FREE_BINS; i++)
{
struct alloc_chunk *chunk = zone->free_chunks[i];
while (chunk)
{
in_use -= ggc_get_size (chunk);
chunk = chunk->next_free;
}
}
fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n",
zone->name,
SCALE (allocated), LABEL (allocated),
SCALE (in_use), LABEL (in_use),
SCALE (overhead), LABEL (overhead));
gcc_assert (in_use == zone->allocated);
total_overhead += overhead;
total_allocated += zone->allocated;
total_bytes_mapped += zone->bytes_mapped;
}
#if HOST_BITS_PER_PTR <= 32
pte_overhead = sizeof (G.lookup);
for (i = 0; i < PAGE_L1_SIZE; i++)
if (G.lookup[i])
pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
#else
{
page_table table = G.lookup;
pte_overhead = 0;
while (table)
{
pte_overhead += sizeof (*table);
for (i = 0; i < PAGE_L1_SIZE; i++)
if (table->table[i])
pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
table = table->next;
}
}
#endif
fprintf (stderr, "%20s %11s %11s %10lu%c\n", "Page Table",
"", "", SCALE (pte_overhead), LABEL (pte_overhead));
total_overhead += pte_overhead;
fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n", "Total",
SCALE (total_bytes_mapped), LABEL (total_bytes_mapped),
SCALE (total_allocated), LABEL(total_allocated),
SCALE (total_overhead), LABEL (total_overhead));
#ifdef GATHER_STATISTICS
{
unsigned long long all_overhead = 0, all_allocated = 0;
unsigned long long all_overhead_under32 = 0, all_allocated_under32 = 0;
unsigned long long all_overhead_under64 = 0, all_allocated_under64 = 0;
unsigned long long all_overhead_under128 = 0, all_allocated_under128 = 0;
fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
for (zone = G.zones; zone; zone = zone->next_zone)
{
all_overhead += zone->stats.total_overhead;
all_allocated += zone->stats.total_allocated;
all_allocated_under32 += zone->stats.total_allocated_under32;
all_overhead_under32 += zone->stats.total_overhead_under32;
all_allocated_under64 += zone->stats.total_allocated_under64;
all_overhead_under64 += zone->stats.total_overhead_under64;
all_allocated_under128 += zone->stats.total_allocated_under128;
all_overhead_under128 += zone->stats.total_overhead_under128;
fprintf (stderr, "%20s: %10lld\n",
zone->name, zone->stats.total_allocated);
}
fprintf (stderr, "\n");
fprintf (stderr, "Total Overhead: %10lld\n",
all_overhead);
fprintf (stderr, "Total Allocated: %10lld\n",
all_allocated);
fprintf (stderr, "Total Overhead under 32B: %10lld\n",
all_overhead_under32);
fprintf (stderr, "Total Allocated under 32B: %10lld\n",
all_allocated_under32);
fprintf (stderr, "Total Overhead under 64B: %10lld\n",
all_overhead_under64);
fprintf (stderr, "Total Allocated under 64B: %10lld\n",
all_allocated_under64);
fprintf (stderr, "Total Overhead under 128B: %10lld\n",
all_overhead_under128);
fprintf (stderr, "Total Allocated under 128B: %10lld\n",
all_allocated_under128);
}
#endif
}
#define NUM_PCH_BUCKETS (gt_types_enum_last + 3)
#define OTHER_BUCKET (gt_types_enum_last + 0)
#define IDENTIFIER_BUCKET (gt_types_enum_last + 1)
#define STRING_BUCKET (gt_types_enum_last + 2)
struct ggc_pch_ondisk
{
size_t total;
size_t type_totals[NUM_PCH_BUCKETS];
};
struct ggc_pch_data
{
struct ggc_pch_ondisk d;
size_t base;
size_t orig_base;
size_t alloc_size;
alloc_type *alloc_bits;
size_t type_bases[NUM_PCH_BUCKETS];
size_t start_offset;
};
struct ggc_pch_data *
init_ggc_pch (void)
{
return xcalloc (sizeof (struct ggc_pch_data), 1);
}
static int
pch_bucket (void *x, enum gt_types_enum type,
bool is_string)
{
if (type == gt_ggc_e_14lang_tree_node
&& TREE_CODE ((tree) x) == IDENTIFIER_NODE)
return IDENTIFIER_BUCKET;
else if (type == gt_types_enum_last)
{
if (is_string)
return STRING_BUCKET;
return OTHER_BUCKET;
}
return type;
}
void
ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
size_t size, bool is_string, enum gt_types_enum type)
{
d->d.type_totals[pch_bucket (x, type, is_string)] += size;
}
size_t
ggc_pch_total_size (struct ggc_pch_data *d)
{
enum gt_types_enum i;
size_t alloc_size, total_size;
total_size = 0;
for (i = 0; i < NUM_PCH_BUCKETS; i++)
{
d->d.type_totals[i] = ROUND_UP (d->d.type_totals[i], GGC_PAGE_SIZE);
total_size += d->d.type_totals[i];
}
d->d.total = total_size;
alloc_size = CEIL (d->d.total, BYTES_PER_ALLOC_BIT * 8);
alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
d->alloc_size = alloc_size;
return d->d.total + alloc_size;
}
void
ggc_pch_this_base (struct ggc_pch_data *d, void *base_)
{
int i;
size_t base = (size_t) base_;
d->base = d->orig_base = base;
for (i = 0; i < NUM_PCH_BUCKETS; i++)
{
d->type_bases[i] = base;
base += d->d.type_totals[i];
}
if (d->alloc_bits == NULL)
d->alloc_bits = xcalloc (1, d->alloc_size);
}
char *
ggc_pch_alloc_object (struct ggc_pch_data *d, void *x,
size_t size, bool is_string,
enum gt_types_enum type)
{
size_t alloc_word, alloc_bit;
char *result;
int bucket = pch_bucket (x, type, is_string);
alloc_word = ((d->type_bases[bucket] - d->orig_base)
/ (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
alloc_bit = ((d->type_bases[bucket] - d->orig_base)
/ BYTES_PER_ALLOC_BIT) % (8 * sizeof (alloc_type));
d->alloc_bits[alloc_word] |= 1L << alloc_bit;
result = (char *) d->type_bases[bucket];
d->type_bases[bucket] += size;
return result;
}
void
ggc_pch_prepare_write (struct ggc_pch_data *d,
FILE *f)
{
d->start_offset = ftell (f);
}
void
ggc_pch_write_object (struct ggc_pch_data *d,
FILE *f, void *x, void *newx,
size_t size, bool is_string ATTRIBUTE_UNUSED)
{
if (fseek (f, (size_t) newx - d->orig_base + d->start_offset, SEEK_SET) != 0)
fatal_error ("can't seek PCH file: %m");
if (fwrite (x, size, 1, f) != 1)
fatal_error ("can't write PCH file: %m");
}
void
ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
{
if (fseek (f, d->start_offset + d->d.total, SEEK_SET) != 0)
fatal_error ("can't seek PCH file: %m");
if (fwrite (d->alloc_bits, d->alloc_size, 1, f) != 1)
fatal_error ("can't write PCH fle: %m");
if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
fatal_error ("can't write PCH file: %m");
free (d->alloc_bits);
free (d);
}
void
ggc_pch_read (FILE *f, void *addr)
{
struct ggc_pch_ondisk d;
size_t alloc_size;
struct alloc_zone *zone;
struct page_entry *pch_page;
char *p;
if (fread (&d, sizeof (d), 1, f) != 1)
fatal_error ("can't read PCH file: %m");
alloc_size = CEIL (d.total, BYTES_PER_ALLOC_BIT * 8);
alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
pch_zone.bytes = d.total;
pch_zone.alloc_bits = (alloc_type *) ((char *) addr + pch_zone.bytes);
pch_zone.page = (char *) addr;
pch_zone.end = (char *) pch_zone.alloc_bits;
for (zone = G.zones; zone; zone = zone->next_zone)
{
struct small_page_entry *page, *next_page;
struct large_page_entry *large_page, *next_large_page;
zone->allocated = 0;
memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
zone->high_free_bin = 0;
zone->cached_free = NULL;
zone->cached_free_size = 0;
for (page = zone->pages; page != NULL; page = next_page)
{
next_page = page->next;
memset (page->alloc_bits, 0,
G.small_page_overhead - PAGE_OVERHEAD);
free_small_page (page);
}
for (large_page = zone->large_pages; large_page != NULL;
large_page = next_large_page)
{
next_large_page = large_page->next;
free_large_page (large_page);
}
zone->pages = NULL;
zone->large_pages = NULL;
}
pch_page = xcalloc (1, sizeof (struct page_entry));
pch_page->page = pch_zone.page;
pch_page->pch_p = true;
for (p = pch_zone.page; p < pch_zone.end; p += GGC_PAGE_SIZE)
set_page_table_entry (p, pch_page);
}