/* "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"
file open. Prefer either to valloc. */
#ifdef HAVE_MMAP_ANON
# undef HAVE_MMAP_DEV_ZERO
-# undef HAVE_VALLOC
# include <sys/mman.h>
# ifndef MAP_FAILED
#endif
#ifdef HAVE_MMAP_DEV_ZERO
-# undef HAVE_VALLOC
# include <sys/mman.h>
# ifndef MAP_FAILED
#endif
-#ifdef HAVE_VALLOC
-# undef MAP_FAILED
-# define MAP_FAILED 0
+#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 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]))
+#define NUM_EXTRA_ORDERS ARRAY_SIZE (extra_order_size_table)
/* 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*
/* 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
/* 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). The ifdef structure here is intended to cause a
compile error unless exactly one of the HAVE_* is defined. */
char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE, G.dev_zero_fd, 0);
#endif
-#ifdef HAVE_VALLOC
- char *page = (char *) valloc (size);
-#endif
if (page == (char *) MAP_FAILED)
{
- fputs ("Virtual memory exhausted!\n", stderr);
- exit(1);
+ perror ("virtual memory exhausted");
+ exit (FATAL_EXIT_CODE);
}
/* Remember that we allocated this memory. */
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 = 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)
{
int i;
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->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 ()
{
- page_entry *p, *next;
-
#ifdef USING_MMAP
+ page_entry *p, *next;
char *start;
size_t len;
munmap (start, len);
G.bytes_mapped -= len;
}
-#else
- for (p = G.free_pages; p; p = next)
- {
- next = p->next;
- free (p->page);
- G.bytes_mapped -= p->bytes;
- free (p);
- }
-#endif /* USING_MMAP */
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. */
abort ();
}
- /* We have a good page, might as well hold onto it... */
+ /* 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;
/* 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));
OSDN Git Service
