27d26
< #include "varray.h"
30a30,36
> #include "params.h"
> #ifdef ENABLE_VALGRIND_CHECKING
> #include <valgrind.h>
> #else
> /* Avoid #ifdef:s when we can help it. */
> #define VALGRIND_DISCARD(x)
> #endif
62c68
< /* Stategy:
---
> /* Stategy:
77c83
< in the current (highest-numbered) context may be collected.
---
> in the current (highest-numbered) context may be collected.
91,107d96
<
< /* Define GGC_POISON to poison memory marked unused by the collector. */
< #undef GGC_POISON
<
< /* Define GGC_ALWAYS_COLLECT to perform collection every time
< ggc_collect is invoked. Otherwise, collection is performed only
< when a significant amount of memory has been allocated since the
< last collection. */
< #undef GGC_ALWAYS_COLLECT
<
< #ifdef ENABLE_GC_CHECKING
< #define GGC_POISON
< #endif
< #ifdef ENABLE_GC_ALWAYS_COLLECT
< #define GGC_ALWAYS_COLLECT
< #endif
<
136c125
< index values in the lookup table, respectively.
---
> index values in the lookup table, respectively.
160a150,158
> /* For speed, we avoid doing a general integer divide to locate the
> offset in the allocation bitmap, by precalculating numbers M, S
> such that (O * M) >> S == O / Z (modulo 2^32), for any offset O
> within the page which is evenly divisible by the object size Z. */
> #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))
>
164,165c162
< #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)
166a164,166
> #define RTL_SIZE(NSLOTS) \
> (sizeof (struct rtx_def) + ((NSLOTS) - 1) * sizeof (rtunion))
>
173c173,175
< sizeof (struct tree_list)
---
> sizeof (struct tree_list),
> RTL_SIZE (2), /* REG, MEM, PLUS, etc. */
> RTL_SIZE (10), /* INSN, CALL_INSN, JUMP_INSN */
207a210,220
> /* The Ith entry is a pair of numbers (mult, shift) such that
> ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
> for all k evenly divisible by OBJECT_SIZE(I). */
>
> static struct
> {
> unsigned int mult;
> unsigned int shift;
> }
> inverse_table[NUM_ORDERS];
>
210c223
< typedef struct page_entry
---
> typedef struct page_entry
228,230c241,243
< /* Saved in-use bit vector for pages that aren't in the topmost
< context during collection. */
< unsigned long *save_in_use_p;
---
> /* This is the index in the by_depth varray where this page table
> can be found. */
> unsigned long index_by_depth;
318a332,337
> /* Bit N set if any allocations have been done at context depth N. */
> unsigned long context_depth_allocations;
>
> /* Bit N set if any collections have been done at context depth N. */
> unsigned long context_depth_collections;
>
335a355,384
>
> /* Current number of elements in use in depth below. */
> unsigned int depth_in_use;
>
> /* Maximum number of elements that can be used before resizing. */
> unsigned int depth_max;
>
> /* Each element of this arry is an index in by_depth where the given
> depth starts. This structure is indexed by that given depth we
> are interested in. */
> unsigned int *depth;
>
> /* Current number of elements in use in by_depth below. */
> unsigned int by_depth_in_use;
>
> /* Maximum number of elements that can be used before resizing. */
> unsigned int by_depth_max;
>
> /* Each element of this array is a pointer to a page_entry, all
> page_entries can be found in here by increasing depth.
> index_by_depth in the page_entry is the index into this data
> structure where that page_entry can be found. This is used to
> speed up finding all page_entries at a particular depth. */
> page_entry **by_depth;
>
> /* Each element is a pointer to the saved in_use_p bits, if any,
> zero otherwise. We allocate them all together, to enable a
> better runtime data access pattern. */
> unsigned long **save_in_use;
>
343,352d391
< /* Skip garbage collection if the current allocation is not at least
< this factor times the allocation at the end of the last collection.
< In other words, total allocation must expand by (this factor minus
< one) before collection is performed. */
< #define GGC_MIN_EXPAND_FOR_GC (1.3)
<
< /* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
< test from triggering too often when the heap is small. */
< #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
<
357a397,399
>
> /* Initial guess as to how many page table entries we might need. */
> #define INITIAL_PTE_COUNT 128
375a418,419
> static void compute_inverse PARAMS ((unsigned));
> static inline void adjust_depth PARAMS ((void));
377c421
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
381a426,427
> static void push_depth PARAMS ((unsigned int));
> static void push_by_depth PARAMS ((page_entry *, unsigned long *));
383c429
< /* Returns non-zero if P was allocated in GC'able memory. */
---
> /* Push an entry onto G.depth. */
384a431,472
> inline static void
> push_depth (i)
> unsigned int i;
> {
> if (G.depth_in_use >= G.depth_max)
> {
> G.depth_max *= 2;
> G.depth = (unsigned int *) xrealloc ((char *) G.depth,
> G.depth_max * sizeof (unsigned int));
> }
> G.depth[G.depth_in_use++] = i;
> }
>
> /* Push an entry onto G.by_depth and G.save_in_use. */
>
> inline static void
> push_by_depth (p, s)
> page_entry *p;
> unsigned long *s;
> {
> if (G.by_depth_in_use >= G.by_depth_max)
> {
> G.by_depth_max *= 2;
> G.by_depth = (page_entry **) xrealloc ((char *) G.by_depth,
> G.by_depth_max * sizeof (page_entry *));
> G.save_in_use = (unsigned long **) xrealloc ((char *) G.save_in_use,
> G.by_depth_max * sizeof (unsigned long *));
> }
> G.by_depth[G.by_depth_in_use] = p;
> G.save_in_use[G.by_depth_in_use++] = s;
> }
>
> /* For the 3.3 release, we will avoid prefetch, as it isn't tested widely. */
> #define prefetch(X) ((void) X)
>
> #define save_in_use_p_i(__i) \
> (G.save_in_use[__i])
> #define save_in_use_p(__p) \
> (save_in_use_p_i (__p->index_by_depth))
>
> /* Returns nonzero if P was allocated in GC'able memory. */
>
415c503
< /* Traverse the page table and find the entry for a page.
---
> /* Traverse the page table and find the entry for a page.
527a616,620
> /* Pretend we don't have access to the allocated pages. We'll enable
> access to smaller pieces of the area in ggc_alloc. Discard the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, size));
>
721a815,816
> G.context_depth_allocations |= (unsigned long)1 << G.context_depth;
>
735,737c830,832
< fprintf (G.debug_file,
< "Allocating page at %p, object size=%ld, data %p-%p\n",
< (PTR) entry, (long) OBJECT_SIZE (order), page,
---
> fprintf (G.debug_file,
> "Allocating page at %p, object size=%lu, data %p-%p\n",
> (PTR) entry, (unsigned long) OBJECT_SIZE (order), page,
742a838,857
> /* Adjust the size of G.depth so that no index greater than the one
> used by the top of the G.by_depth is used. */
>
> static inline void
> adjust_depth ()
> {
> page_entry *top;
>
> if (G.by_depth_in_use)
> {
> top = G.by_depth[G.by_depth_in_use-1];
>
> /* Peel back indicies in depth that index into by_depth, so that
> as new elements are added to by_depth, we note the indicies
> of those elements, if they are for new context depths. */
> while (G.depth_in_use > (size_t)top->context_depth+1)
> --G.depth_in_use;
> }
> }
>
750c865
< fprintf (G.debug_file,
---
> fprintf (G.debug_file,
753a869,872
> /* Mark the page as inaccessible. Discard the handle to avoid handle
> leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->page, entry->bytes));
>
759a879,902
> if (G.by_depth_in_use > 1)
> {
> page_entry *top = G.by_depth[G.by_depth_in_use-1];
>
> /* If they are at the same depth, put top element into freed
> slot. */
> if (entry->context_depth == top->context_depth)
> {
> int i = entry->index_by_depth;
> G.by_depth[i] = top;
> G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1];
> top->index_by_depth = i;
> }
> else
> {
> /* We cannot free a page from a context deeper than the
> current one. */
> abort ();
> }
> }
> --G.by_depth_in_use;
>
> adjust_depth ();
>
820c963
< G.bytes_mapped -= g->alloc_size;
---
> G.bytes_mapped -= g->alloc_size;
831c974
< static unsigned char size_lookup[257] =
---
> static unsigned char size_lookup[257] =
833,838c976,980
< 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,
---
> 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,
840c982,983
< 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,
852c995
< /* Allocate a chunk of memory of SIZE bytes. If ZERO is non-zero, the
---
> /* Allocate a chunk of memory of SIZE bytes. If ZERO is nonzero, the
882c1025,1033
<
---
>
> new_entry->index_by_depth = G.by_depth_in_use;
> push_by_depth (new_entry, 0);
>
> /* We can skip context depths, if we do, make sure we go all the
> way to the new depth. */
> while (new_entry->context_depth >= G.depth_in_use)
> push_depth (G.by_depth_in_use-1);
>
886c1037
<
---
>
908c1059
<
---
>
946c1097,1103
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
> /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the
> exact same semantics in presence of memory bugs, regardless of
> ENABLE_VALGRIND_CHECKING. We override this request below. Drop the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, OBJECT_SIZE (order)));
>
949a1107,1111
>
> /* Make the bytes after the end of the object unaccessible. Discard the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) result + size,
> OBJECT_SIZE (order) - size));
951a1114,1118
> /* Tell Valgrind that the memory is there, but its content isn't
> defined. The bytes at the end of the object are still marked
> unaccessible. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
>
957,959c1124,1127
< fprintf (G.debug_file,
< "Allocating object, requested size=%ld, actual=%ld at %p on %p\n",
< (long) size, (long) OBJECT_SIZE (order), result, (PTR) entry);
---
> fprintf (G.debug_file,
> "Allocating object, requested size=%lu, actual=%lu at %p on %p\n",
> (unsigned long) size, (unsigned long) OBJECT_SIZE (order), result,
> (PTR) entry);
986c1154
< bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
---
> bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
989c1157
<
---
>
1004c1172
< /* Return 1 if P has been marked, zero otherwise.
---
> /* Return 1 if P has been marked, zero otherwise.
1026c1194
< bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
---
> bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1029c1197
<
---
>
1043c1211,1212
< /* Initialize the ggc-mmap allocator. */
---
> /* Subroutine of init_ggc which computes the pair of numbers used to
> perform division by OBJECT_SIZE (order) and fills in inverse_table[].
1044a1214,1253
> This algorithm is taken from Granlund and Montgomery's paper
> "Division by Invariant Integers using Multiplication"
> (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
> constants). */
>
> static void
> compute_inverse (order)
> unsigned order;
> {
> unsigned size, inv, e;
>
> /* There can be only one object per "page" in a bucket for sizes
> larger than half a machine page; it will always have offset zero. */
> if (OBJECT_SIZE (order) > G.pagesize/2)
> {
> if (OBJECTS_PER_PAGE (order) != 1)
> abort ();
>
> DIV_MULT (order) = 1;
> DIV_SHIFT (order) = 0;
> return;
> }
>
> 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;
> }
>
> /* Initialize the ggc-mmap allocator. */
1056c1265
< abort ();
---
> fatal_io_error ("open /dev/zero");
1065,1066d1273
< G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
<
1107c1314
< /* Initialize the objects-per-page table. */
---
> /* Initialize the objects-per-page and inverse tables. */
1112a1320
> compute_inverse (order);
1127a1336,1344
>
> G.depth_in_use = 0;
> G.depth_max = 10;
> G.depth = (unsigned int *) xmalloc (G.depth_max * sizeof (unsigned int));
>
> G.by_depth_in_use = 0;
> G.by_depth_max = INITIAL_PTE_COUNT;
> G.by_depth = (page_entry **) xmalloc (G.by_depth_max * sizeof (page_entry *));
> G.save_in_use = (unsigned long **) xmalloc (G.by_depth_max * sizeof (unsigned long *));
1139c1356
< if (G.context_depth == 0)
---
> if (G.context_depth >= HOST_BITS_PER_LONG)
1153c1370
< /* Because the past-the-end bit in in_use_p is always set, we
---
> /* Because the past-the-end bit in in_use_p is always set, we
1161c1378
< for (i = 0;
---
> for (i = 0;
1170c1387
< p->in_use_p[i] |= p->save_in_use_p[i];
---
> p->in_use_p[i] |= save_in_use_p (p)[i];
1181c1398
< /* Decrement the `GC context'. All objects allocated since the
---
> /* Decrement the `GC context'. All objects allocated since the
1187c1404,1408
< unsigned order, depth;
---
> unsigned long omask;
> unsigned int depth, i, e;
> #ifdef ENABLE_CHECKING
> unsigned int order;
> #endif
1189a1411
> omask = (unsigned long)1 << (depth + 1);
1191,1193c1413,1479
< /* Any remaining pages in the popped context are lowered to the new
< current context; i.e. objects allocated in the popped context and
< left over are imported into the previous context. */
---
> if (!((G.context_depth_allocations | G.context_depth_collections) & omask))
> return;
>
> G.context_depth_allocations |= (G.context_depth_allocations & omask) >> 1;
> G.context_depth_allocations &= omask - 1;
> G.context_depth_collections &= omask - 1;
>
> /* The G.depth array is shortend so that the last index is the
> context_depth of the top element of by_depth. */
> if (depth+1 < G.depth_in_use)
> e = G.depth[depth+1];
> else
> e = G.by_depth_in_use;
>
> /* We might not have any PTEs of depth depth. */
> if (depth < G.depth_in_use)
> {
>
> /* First we go through all the pages at depth depth to
> recalculate the in use bits. */
> for (i = G.depth[depth]; i < e; ++i)
> {
> page_entry *p;
>
> #ifdef ENABLE_CHECKING
> p = G.by_depth[i];
>
> /* Check that all of the pages really are at the depth that
> we expect. */
> if (p->context_depth != depth)
> abort ();
> if (p->index_by_depth != i)
> abort ();
> #endif
>
> prefetch (&save_in_use_p_i (i+8));
> prefetch (&save_in_use_p_i (i+16));
> if (save_in_use_p_i (i))
> {
> p = G.by_depth[i];
> ggc_recalculate_in_use_p (p);
> free (save_in_use_p_i (i));
> save_in_use_p_i (i) = 0;
> }
> }
> }
>
> /* Then, we reset all page_entries with a depth greater than depth
> to be at depth. */
> for (i = e; i < G.by_depth_in_use; ++i)
> {
> page_entry *p = G.by_depth[i];
>
> /* Check that all of the pages really are at the depth we
> expect. */
> #ifdef ENABLE_CHECKING
> if (p->context_depth <= depth)
> abort ();
> if (p->index_by_depth != i)
> abort ();
> #endif
> p->context_depth = depth;
> }
>
> adjust_depth ();
>
> #ifdef ENABLE_CHECKING
1201,1210c1487,1489
< p->context_depth = depth;
<
< /* If this page is now in the topmost context, and we'd
< saved its allocation state, restore it. */
< else if (p->context_depth == depth && p->save_in_use_p)
< {
< ggc_recalculate_in_use_p (p);
< free (p->save_in_use_p);
< p->save_in_use_p = 0;
< }
---
> abort ();
> else if (p->context_depth == depth && save_in_use_p (p))
> abort ();
1212a1492
> #endif
1241,1243c1521,1523
< if (! p->save_in_use_p)
< p->save_in_use_p = xmalloc (bitmap_size);
< memcpy (p->save_in_use_p, p->in_use_p, bitmap_size);
---
> 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);
1252c1532
< p->in_use_p[num_objects / HOST_BITS_PER_LONG]
---
> p->in_use_p[num_objects / HOST_BITS_PER_LONG]
1276c1556
<
---
>
1354c1634
< }
---
> }
1365c1645
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
1396c1676,1688
< memset (p->page + i * size, 0xa5, size);
---
> {
> char *object = p->page + i * size;
>
> /* Keep poison-by-write when we expect to use Valgrind,
> so the exact same memory semantics is kept, in case
> there are memory errors. We override this request
> below. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (object, size));
> memset (object, 0xa5, size);
>
> /* Drop the handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (object, size));
> }
1411,1412c1703,1708
< #ifndef GGC_ALWAYS_COLLECT
< if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
---
> 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)
1414d1709
< #endif
1424c1719
< /* Release the pages we freed the last time we collected, but didn't
---
> /* Release the pages we freed the last time we collected, but didn't
1427a1723,1725
> /* Indicate that we've seen collections at this context depth. */
> G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
>
1430,1431c1728,1729
<
< #ifdef GGC_POISON
---
>
> #ifdef ENABLE_GC_CHECKING
1438,1439d1735
< if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
< G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
1464c1760
<
---
>
1475c1771
< /* Collect some information about the various sizes of
---
> /* Collect some information about the various sizes of
1498c1794
< in_use +=
---
> in_use +=
1504c1800,1801
< fprintf (stderr, "%-5d %10ld%c %10ld%c %10ld%c\n", OBJECT_SIZE (i),
---
> fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
> (unsigned long) OBJECT_SIZE (i),
1510c1807
< fprintf (stderr, "%-5s %10ld%c %10ld%c %10ld%c\n", "Total",
---
> fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
< #include "varray.h"
30a30,36
> #include "params.h"
> #ifdef ENABLE_VALGRIND_CHECKING
> #include <valgrind.h>
> #else
> /* Avoid #ifdef:s when we can help it. */
> #define VALGRIND_DISCARD(x)
> #endif
62c68
< /* Stategy:
---
> /* Stategy:
77c83
< in the current (highest-numbered) context may be collected.
---
> in the current (highest-numbered) context may be collected.
91,107d96
<
< /* Define GGC_POISON to poison memory marked unused by the collector. */
< #undef GGC_POISON
<
< /* Define GGC_ALWAYS_COLLECT to perform collection every time
< ggc_collect is invoked. Otherwise, collection is performed only
< when a significant amount of memory has been allocated since the
< last collection. */
< #undef GGC_ALWAYS_COLLECT
<
< #ifdef ENABLE_GC_CHECKING
< #define GGC_POISON
< #endif
< #ifdef ENABLE_GC_ALWAYS_COLLECT
< #define GGC_ALWAYS_COLLECT
< #endif
<
136c125
< index values in the lookup table, respectively.
---
> index values in the lookup table, respectively.
160a150,158
> /* For speed, we avoid doing a general integer divide to locate the
> offset in the allocation bitmap, by precalculating numbers M, S
> such that (O * M) >> S == O / Z (modulo 2^32), for any offset O
> within the page which is evenly divisible by the object size Z. */
> #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))
>
164,165c162
< #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)
166a164,166
> #define RTL_SIZE(NSLOTS) \
> (sizeof (struct rtx_def) + ((NSLOTS) - 1) * sizeof (rtunion))
>
173c173,175
< sizeof (struct tree_list)
---
> sizeof (struct tree_list),
> RTL_SIZE (2), /* REG, MEM, PLUS, etc. */
> RTL_SIZE (10), /* INSN, CALL_INSN, JUMP_INSN */
207a210,220
> /* The Ith entry is a pair of numbers (mult, shift) such that
> ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
> for all k evenly divisible by OBJECT_SIZE(I). */
>
> static struct
> {
> unsigned int mult;
> unsigned int shift;
> }
> inverse_table[NUM_ORDERS];
>
210c223
< typedef struct page_entry
---
> typedef struct page_entry
228,230c241,243
< /* Saved in-use bit vector for pages that aren't in the topmost
< context during collection. */
< unsigned long *save_in_use_p;
---
> /* This is the index in the by_depth varray where this page table
> can be found. */
> unsigned long index_by_depth;
318a332,337
> /* Bit N set if any allocations have been done at context depth N. */
> unsigned long context_depth_allocations;
>
> /* Bit N set if any collections have been done at context depth N. */
> unsigned long context_depth_collections;
>
335a355,384
>
> /* Current number of elements in use in depth below. */
> unsigned int depth_in_use;
>
> /* Maximum number of elements that can be used before resizing. */
> unsigned int depth_max;
>
> /* Each element of this arry is an index in by_depth where the given
> depth starts. This structure is indexed by that given depth we
> are interested in. */
> unsigned int *depth;
>
> /* Current number of elements in use in by_depth below. */
> unsigned int by_depth_in_use;
>
> /* Maximum number of elements that can be used before resizing. */
> unsigned int by_depth_max;
>
> /* Each element of this array is a pointer to a page_entry, all
> page_entries can be found in here by increasing depth.
> index_by_depth in the page_entry is the index into this data
> structure where that page_entry can be found. This is used to
> speed up finding all page_entries at a particular depth. */
> page_entry **by_depth;
>
> /* Each element is a pointer to the saved in_use_p bits, if any,
> zero otherwise. We allocate them all together, to enable a
> better runtime data access pattern. */
> unsigned long **save_in_use;
>
343,352d391
< /* Skip garbage collection if the current allocation is not at least
< this factor times the allocation at the end of the last collection.
< In other words, total allocation must expand by (this factor minus
< one) before collection is performed. */
< #define GGC_MIN_EXPAND_FOR_GC (1.3)
<
< /* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
< test from triggering too often when the heap is small. */
< #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
<
357a397,399
>
> /* Initial guess as to how many page table entries we might need. */
> #define INITIAL_PTE_COUNT 128
375a418,419
> static void compute_inverse PARAMS ((unsigned));
> static inline void adjust_depth PARAMS ((void));
377c421
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
381a426,427
> static void push_depth PARAMS ((unsigned int));
> static void push_by_depth PARAMS ((page_entry *, unsigned long *));
383c429
< /* Returns non-zero if P was allocated in GC'able memory. */
---
> /* Push an entry onto G.depth. */
384a431,472
> inline static void
> push_depth (i)
> unsigned int i;
> {
> if (G.depth_in_use >= G.depth_max)
> {
> G.depth_max *= 2;
> G.depth = (unsigned int *) xrealloc ((char *) G.depth,
> G.depth_max * sizeof (unsigned int));
> }
> G.depth[G.depth_in_use++] = i;
> }
>
> /* Push an entry onto G.by_depth and G.save_in_use. */
>
> inline static void
> push_by_depth (p, s)
> page_entry *p;
> unsigned long *s;
> {
> if (G.by_depth_in_use >= G.by_depth_max)
> {
> G.by_depth_max *= 2;
> G.by_depth = (page_entry **) xrealloc ((char *) G.by_depth,
> G.by_depth_max * sizeof (page_entry *));
> G.save_in_use = (unsigned long **) xrealloc ((char *) G.save_in_use,
> G.by_depth_max * sizeof (unsigned long *));
> }
> G.by_depth[G.by_depth_in_use] = p;
> G.save_in_use[G.by_depth_in_use++] = s;
> }
>
> /* For the 3.3 release, we will avoid prefetch, as it isn't tested widely. */
> #define prefetch(X) ((void) X)
>
> #define save_in_use_p_i(__i) \
> (G.save_in_use[__i])
> #define save_in_use_p(__p) \
> (save_in_use_p_i (__p->index_by_depth))
>
> /* Returns nonzero if P was allocated in GC'able memory. */
>
415c503
< /* Traverse the page table and find the entry for a page.
---
> /* Traverse the page table and find the entry for a page.
527a616,620
> /* Pretend we don't have access to the allocated pages. We'll enable
> access to smaller pieces of the area in ggc_alloc. Discard the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, size));
>
721a815,816
> G.context_depth_allocations |= (unsigned long)1 << G.context_depth;
>
735,737c830,832
< fprintf (G.debug_file,
< "Allocating page at %p, object size=%ld, data %p-%p\n",
< (PTR) entry, (long) OBJECT_SIZE (order), page,
---
> fprintf (G.debug_file,
> "Allocating page at %p, object size=%lu, data %p-%p\n",
> (PTR) entry, (unsigned long) OBJECT_SIZE (order), page,
742a838,857
> /* Adjust the size of G.depth so that no index greater than the one
> used by the top of the G.by_depth is used. */
>
> static inline void
> adjust_depth ()
> {
> page_entry *top;
>
> if (G.by_depth_in_use)
> {
> top = G.by_depth[G.by_depth_in_use-1];
>
> /* Peel back indicies in depth that index into by_depth, so that
> as new elements are added to by_depth, we note the indicies
> of those elements, if they are for new context depths. */
> while (G.depth_in_use > (size_t)top->context_depth+1)
> --G.depth_in_use;
> }
> }
>
750c865
< fprintf (G.debug_file,
---
> fprintf (G.debug_file,
753a869,872
> /* Mark the page as inaccessible. Discard the handle to avoid handle
> leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->page, entry->bytes));
>
759a879,902
> if (G.by_depth_in_use > 1)
> {
> page_entry *top = G.by_depth[G.by_depth_in_use-1];
>
> /* If they are at the same depth, put top element into freed
> slot. */
> if (entry->context_depth == top->context_depth)
> {
> int i = entry->index_by_depth;
> G.by_depth[i] = top;
> G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1];
> top->index_by_depth = i;
> }
> else
> {
> /* We cannot free a page from a context deeper than the
> current one. */
> abort ();
> }
> }
> --G.by_depth_in_use;
>
> adjust_depth ();
>
820c963
< G.bytes_mapped -= g->alloc_size;
---
> G.bytes_mapped -= g->alloc_size;
831c974
< static unsigned char size_lookup[257] =
---
> static unsigned char size_lookup[257] =
833,838c976,980
< 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,
---
> 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,
840c982,983
< 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,
852c995
< /* Allocate a chunk of memory of SIZE bytes. If ZERO is non-zero, the
---
> /* Allocate a chunk of memory of SIZE bytes. If ZERO is nonzero, the
882c1025,1033
<
---
>
> new_entry->index_by_depth = G.by_depth_in_use;
> push_by_depth (new_entry, 0);
>
> /* We can skip context depths, if we do, make sure we go all the
> way to the new depth. */
> while (new_entry->context_depth >= G.depth_in_use)
> push_depth (G.by_depth_in_use-1);
>
886c1037
<
---
>
908c1059
<
---
>
946c1097,1103
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
> /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the
> exact same semantics in presence of memory bugs, regardless of
> ENABLE_VALGRIND_CHECKING. We override this request below. Drop the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, OBJECT_SIZE (order)));
>
949a1107,1111
>
> /* Make the bytes after the end of the object unaccessible. Discard the
> handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) result + size,
> OBJECT_SIZE (order) - size));
951a1114,1118
> /* Tell Valgrind that the memory is there, but its content isn't
> defined. The bytes at the end of the object are still marked
> unaccessible. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
>
957,959c1124,1127
< fprintf (G.debug_file,
< "Allocating object, requested size=%ld, actual=%ld at %p on %p\n",
< (long) size, (long) OBJECT_SIZE (order), result, (PTR) entry);
---
> fprintf (G.debug_file,
> "Allocating object, requested size=%lu, actual=%lu at %p on %p\n",
> (unsigned long) size, (unsigned long) OBJECT_SIZE (order), result,
> (PTR) entry);
986c1154
< bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
---
> bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
989c1157
<
---
>
1004c1172
< /* Return 1 if P has been marked, zero otherwise.
---
> /* Return 1 if P has been marked, zero otherwise.
1026c1194
< bit = (((const char *) p) - entry->page) / OBJECT_SIZE (entry->order);
---
> bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1029c1197
<
---
>
1043c1211,1212
< /* Initialize the ggc-mmap allocator. */
---
> /* Subroutine of init_ggc which computes the pair of numbers used to
> perform division by OBJECT_SIZE (order) and fills in inverse_table[].
1044a1214,1253
> This algorithm is taken from Granlund and Montgomery's paper
> "Division by Invariant Integers using Multiplication"
> (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
> constants). */
>
> static void
> compute_inverse (order)
> unsigned order;
> {
> unsigned size, inv, e;
>
> /* There can be only one object per "page" in a bucket for sizes
> larger than half a machine page; it will always have offset zero. */
> if (OBJECT_SIZE (order) > G.pagesize/2)
> {
> if (OBJECTS_PER_PAGE (order) != 1)
> abort ();
>
> DIV_MULT (order) = 1;
> DIV_SHIFT (order) = 0;
> return;
> }
>
> 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;
> }
>
> /* Initialize the ggc-mmap allocator. */
1056c1265
< abort ();
---
> fatal_io_error ("open /dev/zero");
1065,1066d1273
< G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
<
1107c1314
< /* Initialize the objects-per-page table. */
---
> /* Initialize the objects-per-page and inverse tables. */
1112a1320
> compute_inverse (order);
1127a1336,1344
>
> G.depth_in_use = 0;
> G.depth_max = 10;
> G.depth = (unsigned int *) xmalloc (G.depth_max * sizeof (unsigned int));
>
> G.by_depth_in_use = 0;
> G.by_depth_max = INITIAL_PTE_COUNT;
> G.by_depth = (page_entry **) xmalloc (G.by_depth_max * sizeof (page_entry *));
> G.save_in_use = (unsigned long **) xmalloc (G.by_depth_max * sizeof (unsigned long *));
1139c1356
< if (G.context_depth == 0)
---
> if (G.context_depth >= HOST_BITS_PER_LONG)
1153c1370
< /* Because the past-the-end bit in in_use_p is always set, we
---
> /* Because the past-the-end bit in in_use_p is always set, we
1161c1378
< for (i = 0;
---
> for (i = 0;
1170c1387
< p->in_use_p[i] |= p->save_in_use_p[i];
---
> p->in_use_p[i] |= save_in_use_p (p)[i];
1181c1398
< /* Decrement the `GC context'. All objects allocated since the
---
> /* Decrement the `GC context'. All objects allocated since the
1187c1404,1408
< unsigned order, depth;
---
> unsigned long omask;
> unsigned int depth, i, e;
> #ifdef ENABLE_CHECKING
> unsigned int order;
> #endif
1189a1411
> omask = (unsigned long)1 << (depth + 1);
1191,1193c1413,1479
< /* Any remaining pages in the popped context are lowered to the new
< current context; i.e. objects allocated in the popped context and
< left over are imported into the previous context. */
---
> if (!((G.context_depth_allocations | G.context_depth_collections) & omask))
> return;
>
> G.context_depth_allocations |= (G.context_depth_allocations & omask) >> 1;
> G.context_depth_allocations &= omask - 1;
> G.context_depth_collections &= omask - 1;
>
> /* The G.depth array is shortend so that the last index is the
> context_depth of the top element of by_depth. */
> if (depth+1 < G.depth_in_use)
> e = G.depth[depth+1];
> else
> e = G.by_depth_in_use;
>
> /* We might not have any PTEs of depth depth. */
> if (depth < G.depth_in_use)
> {
>
> /* First we go through all the pages at depth depth to
> recalculate the in use bits. */
> for (i = G.depth[depth]; i < e; ++i)
> {
> page_entry *p;
>
> #ifdef ENABLE_CHECKING
> p = G.by_depth[i];
>
> /* Check that all of the pages really are at the depth that
> we expect. */
> if (p->context_depth != depth)
> abort ();
> if (p->index_by_depth != i)
> abort ();
> #endif
>
> prefetch (&save_in_use_p_i (i+8));
> prefetch (&save_in_use_p_i (i+16));
> if (save_in_use_p_i (i))
> {
> p = G.by_depth[i];
> ggc_recalculate_in_use_p (p);
> free (save_in_use_p_i (i));
> save_in_use_p_i (i) = 0;
> }
> }
> }
>
> /* Then, we reset all page_entries with a depth greater than depth
> to be at depth. */
> for (i = e; i < G.by_depth_in_use; ++i)
> {
> page_entry *p = G.by_depth[i];
>
> /* Check that all of the pages really are at the depth we
> expect. */
> #ifdef ENABLE_CHECKING
> if (p->context_depth <= depth)
> abort ();
> if (p->index_by_depth != i)
> abort ();
> #endif
> p->context_depth = depth;
> }
>
> adjust_depth ();
>
> #ifdef ENABLE_CHECKING
1201,1210c1487,1489
< p->context_depth = depth;
<
< /* If this page is now in the topmost context, and we'd
< saved its allocation state, restore it. */
< else if (p->context_depth == depth && p->save_in_use_p)
< {
< ggc_recalculate_in_use_p (p);
< free (p->save_in_use_p);
< p->save_in_use_p = 0;
< }
---
> abort ();
> else if (p->context_depth == depth && save_in_use_p (p))
> abort ();
1212a1492
> #endif
1241,1243c1521,1523
< if (! p->save_in_use_p)
< p->save_in_use_p = xmalloc (bitmap_size);
< memcpy (p->save_in_use_p, p->in_use_p, bitmap_size);
---
> 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);
1252c1532
< p->in_use_p[num_objects / HOST_BITS_PER_LONG]
---
> p->in_use_p[num_objects / HOST_BITS_PER_LONG]
1276c1556
<
---
>
1354c1634
< }
---
> }
1365c1645
< #ifdef GGC_POISON
---
> #ifdef ENABLE_GC_CHECKING
1396c1676,1688
< memset (p->page + i * size, 0xa5, size);
---
> {
> char *object = p->page + i * size;
>
> /* Keep poison-by-write when we expect to use Valgrind,
> so the exact same memory semantics is kept, in case
> there are memory errors. We override this request
> below. */
> VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (object, size));
> memset (object, 0xa5, size);
>
> /* Drop the handle to avoid handle leak. */
> VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (object, size));
> }
1411,1412c1703,1708
< #ifndef GGC_ALWAYS_COLLECT
< if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
---
> 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)
1414d1709
< #endif
1424c1719
< /* Release the pages we freed the last time we collected, but didn't
---
> /* Release the pages we freed the last time we collected, but didn't
1427a1723,1725
> /* Indicate that we've seen collections at this context depth. */
> G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
>
1430,1431c1728,1729
<
< #ifdef GGC_POISON
---
>
> #ifdef ENABLE_GC_CHECKING
1438,1439d1735
< if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
< G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
1464c1760
<
---
>
1475c1771
< /* Collect some information about the various sizes of
---
> /* Collect some information about the various sizes of
1498c1794
< in_use +=
---
> in_use +=
1504c1800,1801
< fprintf (stderr, "%-5d %10ld%c %10ld%c %10ld%c\n", OBJECT_SIZE (i),
---
> fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
> (unsigned long) OBJECT_SIZE (i),
1510c1807
< fprintf (stderr, "%-5s %10ld%c %10ld%c %10ld%c\n", "Total",
---
> fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",