/* "Bag-of-pages" garbage collector for the GNU compiler.
- Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
#include "config.h"
#include "system.h"
#include "ggc.h"
#include "timevar.h"
-#ifdef HAVE_MMAP_ANYWHERE
-#include <sys/mman.h>
+/* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
+ file open. Prefer either to valloc. */
+#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
-#ifndef MAP_FAILED
-#define MAP_FAILED -1
+#ifdef HAVE_MMAP_DEV_ZERO
+
+# include <sys/mman.h>
+# ifndef MAP_FAILED
+# define MAP_FAILED -1
+# endif
+# define USING_MMAP
+
#endif
-#if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
-#define MAP_ANONYMOUS MAP_ANON
+#ifndef USING_MMAP
+#define USING_MALLOC_PAGE_GROUPS
#endif
/* Stategy:
1: GC statistics only.
2: Page-entry allocations/deallocations as well.
3: Object allocations as well.
- 4: Object marks as well. */
+ 4: Object marks as well. */
#define GGC_DEBUG_LEVEL (0)
\f
#ifndef HOST_BITS_PER_PTR
/* The size of an object on a page of the indicated ORDER. */
#define OBJECT_SIZE(ORDER) object_size_table[ORDER]
-#ifdef NO_ALIGNMENT_PROBLEM
-
/* The number of extra orders, not corresponding to power-of-two sized
objects. */
#define NUM_EXTRA_ORDERS \
(sizeof (extra_order_size_table) / sizeof (extra_order_size_table[0]))
-#else /* !defined(NO_ALIGNMENT_PROBLEM) */
-
-/* For now, we can't use this code because we don't ensure that the
- objects returned are appropriately aligned. The problem is that
- some tree_list sized things, for example, use */
-#define NUM_EXTRA_ORDERS 0
-
-#endif /* !defined(NO_ALIGNMENT_PROBLEM) */
-
/* The Ith entry is the maximum size of an object to be stored in the
Ith extra order. Adding a new entry to this array is the *only*
thing you need to do to add a new special allocation size. */
#define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
+/* We use this structure to determine the alignment required for
+ allocations. For power-of-two sized allocations, that's not a
+ problem, but it does matter for odd-sized allocations. */
+
+struct max_alignment {
+ char c;
+ union {
+ HOST_WIDEST_INT i;
+#ifdef HAVE_LONG_DOUBLE
+ long double d;
+#else
+ double d;
+#endif
+ } u;
+};
+
+/* The biggest alignment required. */
+
+#define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
+
/* The Ith entry is the number of objects on a page or order I. */
static unsigned objects_per_page_table[NUM_ORDERS];
/* The address at which the memory is allocated. */
char *page;
+#ifdef USING_MALLOC_PAGE_GROUPS
+ /* Back pointer to the page group this page came from. */
+ struct page_group *group;
+#endif
+
/* Saved in-use bit vector for pages that aren't in the topmost
context during collection. */
unsigned long *save_in_use_p;
unsigned long in_use_p[1];
} page_entry;
+#ifdef USING_MALLOC_PAGE_GROUPS
+/* A page_group describes a large allocation from malloc, from which
+ we parcel out aligned pages. */
+typedef struct page_group
+{
+ /* A linked list of all extant page groups. */
+ struct page_group *next;
+
+ /* The address we received from malloc. */
+ char *allocation;
+
+ /* The size of the block. */
+ size_t alloc_size;
+
+ /* A bitmask of pages in use. */
+ unsigned int in_use;
+} page_group;
+#endif
#if HOST_BITS_PER_PTR <= 32
unsigned short context_depth;
/* A file descriptor open to /dev/zero for reading. */
-#if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
+#if defined (HAVE_MMAP_DEV_ZERO)
int dev_zero_fd;
#endif
/* A cache of free system pages. */
page_entry *free_pages;
+#ifdef USING_MALLOC_PAGE_GROUPS
+ page_group *page_groups;
+#endif
+
/* The file descriptor for debugging output. */
FILE *debug_file;
} G;
test from triggering too often when the heap is small. */
#define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
-/* Allocate pages in chunks of this size, to throttle calls to mmap.
- The first page is used, the rest go onto the free list. */
+/* Allocate pages in chunks of this size, to throttle calls to memory
+ allocation routines. The first page is used, the rest go onto the
+ free list. This cannot be larger than HOST_BITS_PER_INT for the
+ in_use bitmask for page_group. */
#define GGC_QUIRE_SIZE 16
-
\f
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));
base = &table->table[0];
#endif
- /* Extract the level 1 and 2 indicies. */
+ /* Extract the level 1 and 2 indices. */
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
base = &table->table[0];
#endif
- /* Extract the level 1 and 2 indicies. */
+ /* Extract the level 1 and 2 indices. */
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
base = &table->table[0];
#endif
- /* Extract the level 1 and 2 indicies. */
+ /* Extract the level 1 and 2 indices. */
L1 = LOOKUP_L1 (p);
L2 = LOOKUP_L2 (p);
fflush (stdout);
}
+#ifdef USING_MMAP
/* Allocate SIZE bytes of anonymous memory, preferably near PREF,
- (if non-null). */
+ (if non-null). The ifdef structure here is intended to cause a
+ compile error unless exactly one of the HAVE_* is defined. */
static inline char *
alloc_anon (pref, size)
char *pref ATTRIBUTE_UNUSED;
size_t size;
{
- char *page;
-
-#ifdef HAVE_MMAP_ANYWHERE
-#ifdef MAP_ANONYMOUS
- page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
- MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
-#else
- page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
- MAP_PRIVATE, G.dev_zero_fd, 0);
+#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)
{
- fputs ("Virtual memory exhausted!\n", stderr);
- exit(1);
- }
-#else
-#ifdef HAVE_VALLOC
- page = (char *) valloc (size);
- if (!page)
- {
- fputs ("Virtual memory exhausted!\n", stderr);
- exit(1);
+ perror ("virtual memory exhausted");
+ exit (FATAL_EXIT_CODE);
}
-#endif /* HAVE_VALLOC */
-#endif /* HAVE_MMAP_ANYWHERE */
/* Remember that we allocated this memory. */
G.bytes_mapped += size;
return page;
}
+#endif
+#ifdef USING_MALLOC_PAGE_GROUPS
+/* Compute the index for this page into the page group. */
+
+static inline size_t
+page_group_index (allocation, page)
+ char *allocation, *page;
+{
+ return (size_t) (page - allocation) >> G.lg_pagesize;
+}
+
+/* Set and clear the in_use bit for this page in the page group. */
+
+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
/* Allocate a new page for allocating objects of size 2^ORDER,
and return an entry for it. The entry is not added to the
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;
/* Check the list of free pages for one we can use. */
- for (pp = &G.free_pages, p = *pp; p ; pp = &p->next, p = *pp)
+ for (pp = &G.free_pages, p = *pp; p; pp = &p->next, p = *pp)
if (p->bytes == entry_size)
break;
if (p != NULL)
{
- /* Recycle the allocated memory from this page ... */
+ /* Recycle the allocated memory from this page ... */
*pp = p->next;
page = p->page;
+
+#ifdef USING_MALLOC_PAGE_GROUPS
+ group = p->group;
+#endif
+
/* ... and, if possible, the page entry itself. */
if (p->order == order)
{
else
free (p);
}
-#ifdef HAVE_MMAP_ANYWHERE
+#ifdef USING_MMAP
else if (entry_size == G.pagesize)
{
/* We want just one page. Allocate a bunch of them and put the
struct page_entry *e, *f = G.free_pages;
int i;
- page = alloc_anon (NULL, entry_size * GGC_QUIRE_SIZE);
+ page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE);
+
/* This loop counts down so that the chain will be in ascending
memory order. */
for (i = GGC_QUIRE_SIZE - 1; i >= 1; i--)
{
- e = (struct page_entry *) xcalloc (1, sizeof (struct page_entry));
- e->bytes = entry_size;
- e->page = page + i*entry_size;
+ 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;
}
-#endif
else
page = alloc_anon (NULL, entry_size);
+#endif
+#ifdef USING_MALLOC_PAGE_GROUPS
+ else
+ {
+ /* Allocate a large block of memory and serve out the aligned
+ pages therein. This results in much less memory wastage
+ than the traditional implementation of valloc. */
+
+ 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;
+
+ /* We allocated N pages, which are likely not aligned, leaving
+ us with N-1 usable pages. We plan to place the page_group
+ structure somewhere in the slop. */
+ if (head_slop >= sizeof (page_group))
+ group = (page_group *)page - 1;
+ else
+ {
+ /* We magically got an aligned allocation. Too bad, we have
+ to waste a page anyway. */
+ 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);
+ }
+
+ /* Remember that we allocated this memory. */
+ 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 we allocated multiple pages, put the rest on the free list. */
+ 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->num_free_objects = num_objects;
entry->next_bit_hint = 1;
+#ifdef USING_MALLOC_PAGE_GROUPS
+ entry->group = group;
+ set_page_group_in_use (group, page);
+#endif
+
/* Set the one-past-the-end in-use bit. This acts as a sentry as we
increment the hint. */
entry->in_use_p[num_objects / HOST_BITS_PER_LONG]
if (GGC_DEBUG_LEVEL >= 2)
fprintf (G.debug_file,
- "Allocating page at %p, object size=%d, data %p-%p\n",
- (PTR) entry, OBJECT_SIZE (order), page, page + entry_size - 1);
+ "Allocating page at %p, object size=%ld, data %p-%p\n",
+ (PTR) entry, (long) OBJECT_SIZE (order), page,
+ page + entry_size - 1);
return entry;
}
set_page_table_entry (entry->page, NULL);
+#ifdef USING_MALLOC_PAGE_GROUPS
+ clear_page_group_in_use (entry->group, entry->page);
+#endif
+
entry->next = G.free_pages;
G.free_pages = entry;
}
static void
release_pages ()
{
+#ifdef USING_MMAP
page_entry *p, *next;
-
-#ifdef HAVE_MMAP_ANYWHERE
char *start;
size_t len;
munmap (start, len);
G.bytes_mapped -= len;
}
-#else
-#ifdef HAVE_VALLOC
-
- for (p = G.free_pages; p; p = next)
- {
- next = p->next;
- free (p->page);
- G.bytes_mapped -= p->bytes;
- free (p);
- }
-#endif /* HAVE_VALLOC */
-#endif /* HAVE_MMAP_ANYWHERE */
G.free_pages = NULL;
+#endif
+#ifdef USING_MALLOC_PAGE_GROUPS
+ page_entry **pp, *p;
+ page_group **gp, *g;
+
+ /* Remove all pages from free page groups from the list. */
+ pp = &G.free_pages;
+ while ((p = *pp) != NULL)
+ if (p->group->in_use == 0)
+ {
+ *pp = p->next;
+ free (p);
+ }
+ else
+ pp = &p->next;
+
+ /* Remove all free page groups, and release the storage. */
+ 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
}
/* This table provides a fast way to determine ceil(log_2(size)) for
- allocation requests. The minimum allocation size is four bytes. */
+ allocation requests. The minimum allocation size is eight bytes. */
static unsigned char size_lookup[257] =
-{
- 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
+{
+ 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,
if (GGC_DEBUG_LEVEL >= 3)
fprintf (G.debug_file,
- "Allocating object, requested size=%d, actual=%d at %p on %p\n",
- (int) size, OBJECT_SIZE (order), result, (PTR) entry);
+ "Allocating object, requested size=%ld, actual=%ld at %p on %p\n",
+ (long) size, (long) OBJECT_SIZE (order), result, (PTR) entry);
return result;
}
word = bit / HOST_BITS_PER_LONG;
mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
- /* If the bit was previously set, skip it. */
+ /* If the bit was previously set, skip it. */
if (entry->in_use_p[word] & mask)
return 1;
return 0;
}
-/* Mark P, but check first that it was allocated by the collector. */
+/* Return 1 if P has been marked, zero otherwise.
+ P must have been allocated by the GC allocator; it mustn't point to
+ static objects, stack variables, or memory allocated with malloc. */
-void
-ggc_mark_if_gcable (p)
+int
+ggc_marked_p (p)
const void *p;
{
- if (p && ggc_allocated_p (p))
- ggc_set_mark (p);
+ page_entry *entry;
+ unsigned bit, word;
+ unsigned long mask;
+
+ /* Look up the page on which the object is alloced. If the object
+ wasn't allocated by the collector, we'll probably die. */
+ entry = lookup_page_table_entry (p);
+#ifdef ENABLE_CHECKING
+ if (entry == NULL)
+ abort ();
+#endif
+
+ /* Calculate the index of the object on the page; this is its bit
+ position in the in_use_p bitmap. */
+ bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
+ word = bit / HOST_BITS_PER_LONG;
+ mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
+
+ return (entry->in_use_p[word] & mask) != 0;
}
/* Return the size of the gc-able object P. */
G.pagesize = getpagesize();
G.lg_pagesize = exact_log2 (G.pagesize);
-#if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
+#ifdef HAVE_MMAP_DEV_ZERO
G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
if (G.dev_zero_fd == -1)
abort ();
G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
-#ifdef HAVE_MMAP_ANYWHERE
+#ifdef USING_MMAP
/* StunOS has an amazing off-by-one error for the first mmap allocation
after fiddling with RLIMIT_STACK. The result, as hard as it is to
believe, is an unaligned page allocation, which would cause us to
hork badly if we tried to use it. */
{
char *p = alloc_anon (NULL, G.pagesize);
+ struct page_entry *e;
if ((size_t)p & (G.pagesize - 1))
{
/* How losing. Discard this one and try another. If we still
if ((size_t)p & (G.pagesize - 1))
abort ();
}
- munmap (p, G.pagesize);
+
+ /* We have a good page, might as well hold onto it... */
+ 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)
- object_size_table[order] =
- extra_order_size_table[order - HOST_BITS_PER_PTR];
+ {
+ size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR];
+
+ /* If S is not a multiple of the MAX_ALIGNMENT, then round it up
+ so that we're sure of getting aligned memory. */
+ s = CEIL (s, MAX_ALIGNMENT) * MAX_ALIGNMENT;
+ object_size_table[order] = s;
+ }
/* Initialize the objects-per-page table. */
for (order = 0; order < NUM_ORDERS; ++order)
/* Collect some information about the various sizes of
allocation. */
fprintf (stderr, "\n%-5s %10s %10s %10s\n",
- "Log", "Allocated", "Used", "Overhead");
+ "Size", "Allocated", "Used", "Overhead");
for (i = 0; i < NUM_ORDERS; ++i)
{
page_entry *p;
overhead += (sizeof (page_entry) - sizeof (long)
+ BITMAP_SIZE (OBJECTS_PER_PAGE (i) + 1));
}
- fprintf (stderr, "%-5d %10ld%c %10ld%c %10ld%c\n", i,
+ fprintf (stderr, "%-5d %10ld%c %10ld%c %10ld%c\n", OBJECT_SIZE (i),
SCALE (allocated), LABEL (allocated),
SCALE (in_use), LABEL (in_use),
SCALE (overhead), LABEL (overhead));