OSDN Git Service

2005-07-08 Daniel Berlin <dberlin@dberlin.org>
[pf3gnuchains/gcc-fork.git] / gcc / ggc-page.c
1 /* "Bag-of-pages" garbage collector for the GNU compiler.
2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "toplev.h"
30 #include "flags.h"
31 #include "ggc.h"
32 #include "timevar.h"
33 #include "params.h"
34 #include "tree-flow.h"
35 #ifdef ENABLE_VALGRIND_CHECKING
36 # ifdef HAVE_VALGRIND_MEMCHECK_H
37 #  include <valgrind/memcheck.h>
38 # elif defined HAVE_MEMCHECK_H
39 #  include <memcheck.h>
40 # else
41 #  include <valgrind.h>
42 # endif
43 #else
44 /* Avoid #ifdef:s when we can help it.  */
45 #define VALGRIND_DISCARD(x)
46 #endif
47
48 /* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
49    file open.  Prefer either to valloc.  */
50 #ifdef HAVE_MMAP_ANON
51 # undef HAVE_MMAP_DEV_ZERO
52
53 # include <sys/mman.h>
54 # ifndef MAP_FAILED
55 #  define MAP_FAILED -1
56 # endif
57 # if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
58 #  define MAP_ANONYMOUS MAP_ANON
59 # endif
60 # define USING_MMAP
61
62 #endif
63
64 #ifdef HAVE_MMAP_DEV_ZERO
65
66 # include <sys/mman.h>
67 # ifndef MAP_FAILED
68 #  define MAP_FAILED -1
69 # endif
70 # define USING_MMAP
71
72 #endif
73
74 #ifndef USING_MMAP
75 #define USING_MALLOC_PAGE_GROUPS
76 #endif
77
78 /* Strategy:
79
80    This garbage-collecting allocator allocates objects on one of a set
81    of pages.  Each page can allocate objects of a single size only;
82    available sizes are powers of two starting at four bytes.  The size
83    of an allocation request is rounded up to the next power of two
84    (`order'), and satisfied from the appropriate page.
85
86    Each page is recorded in a page-entry, which also maintains an
87    in-use bitmap of object positions on the page.  This allows the
88    allocation state of a particular object to be flipped without
89    touching the page itself.
90
91    Each page-entry also has a context depth, which is used to track
92    pushing and popping of allocation contexts.  Only objects allocated
93    in the current (highest-numbered) context may be collected.
94
95    Page entries are arranged in an array of singly-linked lists.  The
96    array is indexed by the allocation size, in bits, of the pages on
97    it; i.e. all pages on a list allocate objects of the same size.
98    Pages are ordered on the list such that all non-full pages precede
99    all full pages, with non-full pages arranged in order of decreasing
100    context depth.
101
102    Empty pages (of all orders) are kept on a single page cache list,
103    and are considered first when new pages are required; they are
104    deallocated at the start of the next collection if they haven't
105    been recycled by then.  */
106
107 /* Define GGC_DEBUG_LEVEL to print debugging information.
108      0: No debugging output.
109      1: GC statistics only.
110      2: Page-entry allocations/deallocations as well.
111      3: Object allocations as well.
112      4: Object marks as well.  */
113 #define GGC_DEBUG_LEVEL (0)
114 \f
115 #ifndef HOST_BITS_PER_PTR
116 #define HOST_BITS_PER_PTR  HOST_BITS_PER_LONG
117 #endif
118
119 \f
120 /* A two-level tree is used to look up the page-entry for a given
121    pointer.  Two chunks of the pointer's bits are extracted to index
122    the first and second levels of the tree, as follows:
123
124                                    HOST_PAGE_SIZE_BITS
125                            32           |      |
126        msb +----------------+----+------+------+ lsb
127                             |    |      |
128                          PAGE_L1_BITS   |
129                                  |      |
130                                PAGE_L2_BITS
131
132    The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry
133    pages are aligned on system page boundaries.  The next most
134    significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first
135    index values in the lookup table, respectively.
136
137    For 32-bit architectures and the settings below, there are no
138    leftover bits.  For architectures with wider pointers, the lookup
139    tree points to a list of pages, which must be scanned to find the
140    correct one.  */
141
142 #define PAGE_L1_BITS    (8)
143 #define PAGE_L2_BITS    (32 - PAGE_L1_BITS - G.lg_pagesize)
144 #define PAGE_L1_SIZE    ((size_t) 1 << PAGE_L1_BITS)
145 #define PAGE_L2_SIZE    ((size_t) 1 << PAGE_L2_BITS)
146
147 #define LOOKUP_L1(p) \
148   (((size_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
149
150 #define LOOKUP_L2(p) \
151   (((size_t) (p) >> G.lg_pagesize) & ((1 << PAGE_L2_BITS) - 1))
152
153 /* The number of objects per allocation page, for objects on a page of
154    the indicated ORDER.  */
155 #define OBJECTS_PER_PAGE(ORDER) objects_per_page_table[ORDER]
156
157 /* The number of objects in P.  */
158 #define OBJECTS_IN_PAGE(P) ((P)->bytes / OBJECT_SIZE ((P)->order))
159
160 /* The size of an object on a page of the indicated ORDER.  */
161 #define OBJECT_SIZE(ORDER) object_size_table[ORDER]
162
163 /* For speed, we avoid doing a general integer divide to locate the
164    offset in the allocation bitmap, by precalculating numbers M, S
165    such that (O * M) >> S == O / Z (modulo 2^32), for any offset O
166    within the page which is evenly divisible by the object size Z.  */
167 #define DIV_MULT(ORDER) inverse_table[ORDER].mult
168 #define DIV_SHIFT(ORDER) inverse_table[ORDER].shift
169 #define OFFSET_TO_BIT(OFFSET, ORDER) \
170   (((OFFSET) * DIV_MULT (ORDER)) >> DIV_SHIFT (ORDER))
171
172 /* The number of extra orders, not corresponding to power-of-two sized
173    objects.  */
174
175 #define NUM_EXTRA_ORDERS ARRAY_SIZE (extra_order_size_table)
176
177 #define RTL_SIZE(NSLOTS) \
178   (RTX_HDR_SIZE + (NSLOTS) * sizeof (rtunion))
179
180 #define TREE_EXP_SIZE(OPS) \
181   (sizeof (struct tree_exp) + ((OPS) - 1) * sizeof (tree))
182
183 /* The Ith entry is the maximum size of an object to be stored in the
184    Ith extra order.  Adding a new entry to this array is the *only*
185    thing you need to do to add a new special allocation size.  */
186
187 static const size_t extra_order_size_table[] = {
188   sizeof (struct stmt_ann_d),
189   sizeof (struct tree_decl_non_common),
190   sizeof (struct tree_field_decl),
191   sizeof (struct tree_parm_decl),
192   sizeof (struct tree_var_decl),
193   sizeof (struct tree_list),
194   TREE_EXP_SIZE (2),
195   RTL_SIZE (2),                 /* MEM, PLUS, etc.  */
196   RTL_SIZE (9),                 /* INSN */
197 };
198
199 /* The total number of orders.  */
200
201 #define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
202
203 /* We use this structure to determine the alignment required for
204    allocations.  For power-of-two sized allocations, that's not a
205    problem, but it does matter for odd-sized allocations.  */
206
207 struct max_alignment {
208   char c;
209   union {
210     HOST_WIDEST_INT i;
211     long double d;
212   } u;
213 };
214
215 /* The biggest alignment required.  */
216
217 #define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
218
219 /* Compute the smallest nonnegative number which when added to X gives
220    a multiple of F.  */
221
222 #define ROUND_UP_VALUE(x, f) ((f) - 1 - ((f) - 1 + (x)) % (f))
223
224 /* Compute the smallest multiple of F that is >= X.  */
225
226 #define ROUND_UP(x, f) (CEIL (x, f) * (f))
227
228 /* The Ith entry is the number of objects on a page or order I.  */
229
230 static unsigned objects_per_page_table[NUM_ORDERS];
231
232 /* The Ith entry is the size of an object on a page of order I.  */
233
234 static size_t object_size_table[NUM_ORDERS];
235
236 /* The Ith entry is a pair of numbers (mult, shift) such that
237    ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
238    for all k evenly divisible by OBJECT_SIZE(I).  */
239
240 static struct
241 {
242   size_t mult;
243   unsigned int shift;
244 }
245 inverse_table[NUM_ORDERS];
246
247 /* A page_entry records the status of an allocation page.  This
248    structure is dynamically sized to fit the bitmap in_use_p.  */
249 typedef struct page_entry
250 {
251   /* The next page-entry with objects of the same size, or NULL if
252      this is the last page-entry.  */
253   struct page_entry *next;
254
255   /* The previous page-entry with objects of the same size, or NULL if
256      this is the first page-entry.   The PREV pointer exists solely to
257      keep the cost of ggc_free manageable.  */
258   struct page_entry *prev;
259
260   /* The number of bytes allocated.  (This will always be a multiple
261      of the host system page size.)  */
262   size_t bytes;
263
264   /* The address at which the memory is allocated.  */
265   char *page;
266
267 #ifdef USING_MALLOC_PAGE_GROUPS
268   /* Back pointer to the page group this page came from.  */
269   struct page_group *group;
270 #endif
271
272   /* This is the index in the by_depth varray where this page table
273      can be found.  */
274   unsigned long index_by_depth;
275
276   /* Context depth of this page.  */
277   unsigned short context_depth;
278
279   /* The number of free objects remaining on this page.  */
280   unsigned short num_free_objects;
281
282   /* A likely candidate for the bit position of a free object for the
283      next allocation from this page.  */
284   unsigned short next_bit_hint;
285
286   /* The lg of size of objects allocated from this page.  */
287   unsigned char order;
288
289   /* A bit vector indicating whether or not objects are in use.  The
290      Nth bit is one if the Nth object on this page is allocated.  This
291      array is dynamically sized.  */
292   unsigned long in_use_p[1];
293 } page_entry;
294
295 #ifdef USING_MALLOC_PAGE_GROUPS
296 /* A page_group describes a large allocation from malloc, from which
297    we parcel out aligned pages.  */
298 typedef struct page_group
299 {
300   /* A linked list of all extant page groups.  */
301   struct page_group *next;
302
303   /* The address we received from malloc.  */
304   char *allocation;
305
306   /* The size of the block.  */
307   size_t alloc_size;
308
309   /* A bitmask of pages in use.  */
310   unsigned int in_use;
311 } page_group;
312 #endif
313
314 #if HOST_BITS_PER_PTR <= 32
315
316 /* On 32-bit hosts, we use a two level page table, as pictured above.  */
317 typedef page_entry **page_table[PAGE_L1_SIZE];
318
319 #else
320
321 /* On 64-bit hosts, we use the same two level page tables plus a linked
322    list that disambiguates the top 32-bits.  There will almost always be
323    exactly one entry in the list.  */
324 typedef struct page_table_chain
325 {
326   struct page_table_chain *next;
327   size_t high_bits;
328   page_entry **table[PAGE_L1_SIZE];
329 } *page_table;
330
331 #endif
332
333 /* The rest of the global variables.  */
334 static struct globals
335 {
336   /* The Nth element in this array is a page with objects of size 2^N.
337      If there are any pages with free objects, they will be at the
338      head of the list.  NULL if there are no page-entries for this
339      object size.  */
340   page_entry *pages[NUM_ORDERS];
341
342   /* The Nth element in this array is the last page with objects of
343      size 2^N.  NULL if there are no page-entries for this object
344      size.  */
345   page_entry *page_tails[NUM_ORDERS];
346
347   /* Lookup table for associating allocation pages with object addresses.  */
348   page_table lookup;
349
350   /* The system's page size.  */
351   size_t pagesize;
352   size_t lg_pagesize;
353
354   /* Bytes currently allocated.  */
355   size_t allocated;
356
357   /* Bytes currently allocated at the end of the last collection.  */
358   size_t allocated_last_gc;
359
360   /* Total amount of memory mapped.  */
361   size_t bytes_mapped;
362
363   /* Bit N set if any allocations have been done at context depth N.  */
364   unsigned long context_depth_allocations;
365
366   /* Bit N set if any collections have been done at context depth N.  */
367   unsigned long context_depth_collections;
368
369   /* The current depth in the context stack.  */
370   unsigned short context_depth;
371
372   /* A file descriptor open to /dev/zero for reading.  */
373 #if defined (HAVE_MMAP_DEV_ZERO)
374   int dev_zero_fd;
375 #endif
376
377   /* A cache of free system pages.  */
378   page_entry *free_pages;
379
380 #ifdef USING_MALLOC_PAGE_GROUPS
381   page_group *page_groups;
382 #endif
383
384   /* The file descriptor for debugging output.  */
385   FILE *debug_file;
386
387   /* Current number of elements in use in depth below.  */
388   unsigned int depth_in_use;
389
390   /* Maximum number of elements that can be used before resizing.  */
391   unsigned int depth_max;
392
393   /* Each element of this arry is an index in by_depth where the given
394      depth starts.  This structure is indexed by that given depth we
395      are interested in.  */
396   unsigned int *depth;
397
398   /* Current number of elements in use in by_depth below.  */
399   unsigned int by_depth_in_use;
400
401   /* Maximum number of elements that can be used before resizing.  */
402   unsigned int by_depth_max;
403
404   /* Each element of this array is a pointer to a page_entry, all
405      page_entries can be found in here by increasing depth.
406      index_by_depth in the page_entry is the index into this data
407      structure where that page_entry can be found.  This is used to
408      speed up finding all page_entries at a particular depth.  */
409   page_entry **by_depth;
410
411   /* Each element is a pointer to the saved in_use_p bits, if any,
412      zero otherwise.  We allocate them all together, to enable a
413      better runtime data access pattern.  */
414   unsigned long **save_in_use;
415
416 #ifdef ENABLE_GC_ALWAYS_COLLECT
417   /* List of free objects to be verified as actually free on the
418      next collection.  */
419   struct free_object
420   {
421     void *object;
422     struct free_object *next;
423   } *free_object_list;
424 #endif
425
426 #ifdef GATHER_STATISTICS
427   struct
428   {
429     /* Total memory allocated with ggc_alloc.  */
430     unsigned long long total_allocated;
431     /* Total overhead for memory to be allocated with ggc_alloc.  */
432     unsigned long long total_overhead;
433
434     /* Total allocations and overhead for sizes less than 32, 64 and 128.
435        These sizes are interesting because they are typical cache line
436        sizes.  */
437    
438     unsigned long long total_allocated_under32;
439     unsigned long long total_overhead_under32;
440   
441     unsigned long long total_allocated_under64;
442     unsigned long long total_overhead_under64;
443   
444     unsigned long long total_allocated_under128;
445     unsigned long long total_overhead_under128;
446   
447     /* The allocations for each of the allocation orders.  */
448     unsigned long long total_allocated_per_order[NUM_ORDERS];
449
450     /* The overhead for each of the allocation orders.  */
451     unsigned long long total_overhead_per_order[NUM_ORDERS];
452   } stats;
453 #endif
454 } G;
455
456 /* The size in bytes required to maintain a bitmap for the objects
457    on a page-entry.  */
458 #define BITMAP_SIZE(Num_objects) \
459   (CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
460
461 /* Allocate pages in chunks of this size, to throttle calls to memory
462    allocation routines.  The first page is used, the rest go onto the
463    free list.  This cannot be larger than HOST_BITS_PER_INT for the
464    in_use bitmask for page_group.  Hosts that need a different value
465    can override this by defining GGC_QUIRE_SIZE explicitly.  */
466 #ifndef GGC_QUIRE_SIZE
467 # ifdef USING_MMAP
468 #  define GGC_QUIRE_SIZE 256
469 # else
470 #  define GGC_QUIRE_SIZE 16
471 # endif
472 #endif
473
474 /* Initial guess as to how many page table entries we might need.  */
475 #define INITIAL_PTE_COUNT 128
476 \f
477 static int ggc_allocated_p (const void *);
478 static page_entry *lookup_page_table_entry (const void *);
479 static void set_page_table_entry (void *, page_entry *);
480 #ifdef USING_MMAP
481 static char *alloc_anon (char *, size_t);
482 #endif
483 #ifdef USING_MALLOC_PAGE_GROUPS
484 static size_t page_group_index (char *, char *);
485 static void set_page_group_in_use (page_group *, char *);
486 static void clear_page_group_in_use (page_group *, char *);
487 #endif
488 static struct page_entry * alloc_page (unsigned);
489 static void free_page (struct page_entry *);
490 static void release_pages (void);
491 static void clear_marks (void);
492 static void sweep_pages (void);
493 static void ggc_recalculate_in_use_p (page_entry *);
494 static void compute_inverse (unsigned);
495 static inline void adjust_depth (void);
496 static void move_ptes_to_front (int, int);
497
498 void debug_print_page_list (int);
499 static void push_depth (unsigned int);
500 static void push_by_depth (page_entry *, unsigned long *);
501
502 /* Push an entry onto G.depth.  */
503
504 inline static void
505 push_depth (unsigned int i)
506 {
507   if (G.depth_in_use >= G.depth_max)
508     {
509       G.depth_max *= 2;
510       G.depth = xrealloc (G.depth, G.depth_max * sizeof (unsigned int));
511     }
512   G.depth[G.depth_in_use++] = i;
513 }
514
515 /* Push an entry onto G.by_depth and G.save_in_use.  */
516
517 inline static void
518 push_by_depth (page_entry *p, unsigned long *s)
519 {
520   if (G.by_depth_in_use >= G.by_depth_max)
521     {
522       G.by_depth_max *= 2;
523       G.by_depth = xrealloc (G.by_depth,
524                              G.by_depth_max * sizeof (page_entry *));
525       G.save_in_use = xrealloc (G.save_in_use,
526                                 G.by_depth_max * sizeof (unsigned long *));
527     }
528   G.by_depth[G.by_depth_in_use] = p;
529   G.save_in_use[G.by_depth_in_use++] = s;
530 }
531
532 #if (GCC_VERSION < 3001)
533 #define prefetch(X) ((void) X)
534 #else
535 #define prefetch(X) __builtin_prefetch (X)
536 #endif
537
538 #define save_in_use_p_i(__i) \
539   (G.save_in_use[__i])
540 #define save_in_use_p(__p) \
541   (save_in_use_p_i (__p->index_by_depth))
542
543 /* Returns nonzero if P was allocated in GC'able memory.  */
544
545 static inline int
546 ggc_allocated_p (const void *p)
547 {
548   page_entry ***base;
549   size_t L1, L2;
550
551 #if HOST_BITS_PER_PTR <= 32
552   base = &G.lookup[0];
553 #else
554   page_table table = G.lookup;
555   size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
556   while (1)
557     {
558       if (table == NULL)
559         return 0;
560       if (table->high_bits == high_bits)
561         break;
562       table = table->next;
563     }
564   base = &table->table[0];
565 #endif
566
567   /* Extract the level 1 and 2 indices.  */
568   L1 = LOOKUP_L1 (p);
569   L2 = LOOKUP_L2 (p);
570
571   return base[L1] && base[L1][L2];
572 }
573
574 /* Traverse the page table and find the entry for a page.
575    Die (probably) if the object wasn't allocated via GC.  */
576
577 static inline page_entry *
578 lookup_page_table_entry (const void *p)
579 {
580   page_entry ***base;
581   size_t L1, L2;
582
583 #if HOST_BITS_PER_PTR <= 32
584   base = &G.lookup[0];
585 #else
586   page_table table = G.lookup;
587   size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
588   while (table->high_bits != high_bits)
589     table = table->next;
590   base = &table->table[0];
591 #endif
592
593   /* Extract the level 1 and 2 indices.  */
594   L1 = LOOKUP_L1 (p);
595   L2 = LOOKUP_L2 (p);
596
597   return base[L1][L2];
598 }
599
600 /* Set the page table entry for a page.  */
601
602 static void
603 set_page_table_entry (void *p, page_entry *entry)
604 {
605   page_entry ***base;
606   size_t L1, L2;
607
608 #if HOST_BITS_PER_PTR <= 32
609   base = &G.lookup[0];
610 #else
611   page_table table;
612   size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
613   for (table = G.lookup; table; table = table->next)
614     if (table->high_bits == high_bits)
615       goto found;
616
617   /* Not found -- allocate a new table.  */
618   table = xcalloc (1, sizeof(*table));
619   table->next = G.lookup;
620   table->high_bits = high_bits;
621   G.lookup = table;
622 found:
623   base = &table->table[0];
624 #endif
625
626   /* Extract the level 1 and 2 indices.  */
627   L1 = LOOKUP_L1 (p);
628   L2 = LOOKUP_L2 (p);
629
630   if (base[L1] == NULL)
631     base[L1] = xcalloc (PAGE_L2_SIZE, sizeof (page_entry *));
632
633   base[L1][L2] = entry;
634 }
635
636 /* Prints the page-entry for object size ORDER, for debugging.  */
637
638 void
639 debug_print_page_list (int order)
640 {
641   page_entry *p;
642   printf ("Head=%p, Tail=%p:\n", (void *) G.pages[order],
643           (void *) G.page_tails[order]);
644   p = G.pages[order];
645   while (p != NULL)
646     {
647       printf ("%p(%1d|%3d) -> ", (void *) p, p->context_depth,
648               p->num_free_objects);
649       p = p->next;
650     }
651   printf ("NULL\n");
652   fflush (stdout);
653 }
654
655 #ifdef USING_MMAP
656 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
657    (if non-null).  The ifdef structure here is intended to cause a
658    compile error unless exactly one of the HAVE_* is defined.  */
659
660 static inline char *
661 alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size)
662 {
663 #ifdef HAVE_MMAP_ANON
664   char *page = mmap (pref, size, PROT_READ | PROT_WRITE,
665                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
666 #endif
667 #ifdef HAVE_MMAP_DEV_ZERO
668   char *page = mmap (pref, size, PROT_READ | PROT_WRITE,
669                      MAP_PRIVATE, G.dev_zero_fd, 0);
670 #endif
671
672   if (page == (char *) MAP_FAILED)
673     {
674       perror ("virtual memory exhausted");
675       exit (FATAL_EXIT_CODE);
676     }
677
678   /* Remember that we allocated this memory.  */
679   G.bytes_mapped += size;
680
681   /* Pretend we don't have access to the allocated pages.  We'll enable
682      access to smaller pieces of the area in ggc_alloc.  Discard the
683      handle to avoid handle leak.  */
684   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, size));
685
686   return page;
687 }
688 #endif
689 #ifdef USING_MALLOC_PAGE_GROUPS
690 /* Compute the index for this page into the page group.  */
691
692 static inline size_t
693 page_group_index (char *allocation, char *page)
694 {
695   return (size_t) (page - allocation) >> G.lg_pagesize;
696 }
697
698 /* Set and clear the in_use bit for this page in the page group.  */
699
700 static inline void
701 set_page_group_in_use (page_group *group, char *page)
702 {
703   group->in_use |= 1 << page_group_index (group->allocation, page);
704 }
705
706 static inline void
707 clear_page_group_in_use (page_group *group, char *page)
708 {
709   group->in_use &= ~(1 << page_group_index (group->allocation, page));
710 }
711 #endif
712
713 /* Allocate a new page for allocating objects of size 2^ORDER,
714    and return an entry for it.  The entry is not added to the
715    appropriate page_table list.  */
716
717 static inline struct page_entry *
718 alloc_page (unsigned order)
719 {
720   struct page_entry *entry, *p, **pp;
721   char *page;
722   size_t num_objects;
723   size_t bitmap_size;
724   size_t page_entry_size;
725   size_t entry_size;
726 #ifdef USING_MALLOC_PAGE_GROUPS
727   page_group *group;
728 #endif
729
730   num_objects = OBJECTS_PER_PAGE (order);
731   bitmap_size = BITMAP_SIZE (num_objects + 1);
732   page_entry_size = sizeof (page_entry) - sizeof (long) + bitmap_size;
733   entry_size = num_objects * OBJECT_SIZE (order);
734   if (entry_size < G.pagesize)
735     entry_size = G.pagesize;
736
737   entry = NULL;
738   page = NULL;
739
740   /* Check the list of free pages for one we can use.  */
741   for (pp = &G.free_pages, p = *pp; p; pp = &p->next, p = *pp)
742     if (p->bytes == entry_size)
743       break;
744
745   if (p != NULL)
746     {
747       /* Recycle the allocated memory from this page ...  */
748       *pp = p->next;
749       page = p->page;
750
751 #ifdef USING_MALLOC_PAGE_GROUPS
752       group = p->group;
753 #endif
754
755       /* ... and, if possible, the page entry itself.  */
756       if (p->order == order)
757         {
758           entry = p;
759           memset (entry, 0, page_entry_size);
760         }
761       else
762         free (p);
763     }
764 #ifdef USING_MMAP
765   else if (entry_size == G.pagesize)
766     {
767       /* We want just one page.  Allocate a bunch of them and put the
768          extras on the freelist.  (Can only do this optimization with
769          mmap for backing store.)  */
770       struct page_entry *e, *f = G.free_pages;
771       int i;
772
773       page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE);
774
775       /* This loop counts down so that the chain will be in ascending
776          memory order.  */
777       for (i = GGC_QUIRE_SIZE - 1; i >= 1; i--)
778         {
779           e = xcalloc (1, page_entry_size);
780           e->order = order;
781           e->bytes = G.pagesize;
782           e->page = page + (i << G.lg_pagesize);
783           e->next = f;
784           f = e;
785         }
786
787       G.free_pages = f;
788     }
789   else
790     page = alloc_anon (NULL, entry_size);
791 #endif
792 #ifdef USING_MALLOC_PAGE_GROUPS
793   else
794     {
795       /* Allocate a large block of memory and serve out the aligned
796          pages therein.  This results in much less memory wastage
797          than the traditional implementation of valloc.  */
798
799       char *allocation, *a, *enda;
800       size_t alloc_size, head_slop, tail_slop;
801       int multiple_pages = (entry_size == G.pagesize);
802
803       if (multiple_pages)
804         alloc_size = GGC_QUIRE_SIZE * G.pagesize;
805       else
806         alloc_size = entry_size + G.pagesize - 1;
807       allocation = xmalloc (alloc_size);
808
809       page = (char *) (((size_t) allocation + G.pagesize - 1) & -G.pagesize);
810       head_slop = page - allocation;
811       if (multiple_pages)
812         tail_slop = ((size_t) allocation + alloc_size) & (G.pagesize - 1);
813       else
814         tail_slop = alloc_size - entry_size - head_slop;
815       enda = allocation + alloc_size - tail_slop;
816
817       /* We allocated N pages, which are likely not aligned, leaving
818          us with N-1 usable pages.  We plan to place the page_group
819          structure somewhere in the slop.  */
820       if (head_slop >= sizeof (page_group))
821         group = (page_group *)page - 1;
822       else
823         {
824           /* We magically got an aligned allocation.  Too bad, we have
825              to waste a page anyway.  */
826           if (tail_slop == 0)
827             {
828               enda -= G.pagesize;
829               tail_slop += G.pagesize;
830             }
831           gcc_assert (tail_slop >= sizeof (page_group));
832           group = (page_group *)enda;
833           tail_slop -= sizeof (page_group);
834         }
835
836       /* Remember that we allocated this memory.  */
837       group->next = G.page_groups;
838       group->allocation = allocation;
839       group->alloc_size = alloc_size;
840       group->in_use = 0;
841       G.page_groups = group;
842       G.bytes_mapped += alloc_size;
843
844       /* If we allocated multiple pages, put the rest on the free list.  */
845       if (multiple_pages)
846         {
847           struct page_entry *e, *f = G.free_pages;
848           for (a = enda - G.pagesize; a != page; a -= G.pagesize)
849             {
850               e = xcalloc (1, page_entry_size);
851               e->order = order;
852               e->bytes = G.pagesize;
853               e->page = a;
854               e->group = group;
855               e->next = f;
856               f = e;
857             }
858           G.free_pages = f;
859         }
860     }
861 #endif
862
863   if (entry == NULL)
864     entry = xcalloc (1, page_entry_size);
865
866   entry->bytes = entry_size;
867   entry->page = page;
868   entry->context_depth = G.context_depth;
869   entry->order = order;
870   entry->num_free_objects = num_objects;
871   entry->next_bit_hint = 1;
872
873   G.context_depth_allocations |= (unsigned long)1 << G.context_depth;
874
875 #ifdef USING_MALLOC_PAGE_GROUPS
876   entry->group = group;
877   set_page_group_in_use (group, page);
878 #endif
879
880   /* Set the one-past-the-end in-use bit.  This acts as a sentry as we
881      increment the hint.  */
882   entry->in_use_p[num_objects / HOST_BITS_PER_LONG]
883     = (unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG);
884
885   set_page_table_entry (page, entry);
886
887   if (GGC_DEBUG_LEVEL >= 2)
888     fprintf (G.debug_file,
889              "Allocating page at %p, object size=%lu, data %p-%p\n",
890              (void *) entry, (unsigned long) OBJECT_SIZE (order), page,
891              page + entry_size - 1);
892
893   return entry;
894 }
895
896 /* Adjust the size of G.depth so that no index greater than the one
897    used by the top of the G.by_depth is used.  */
898
899 static inline void
900 adjust_depth (void)
901 {
902   page_entry *top;
903
904   if (G.by_depth_in_use)
905     {
906       top = G.by_depth[G.by_depth_in_use-1];
907
908       /* Peel back indices in depth that index into by_depth, so that
909          as new elements are added to by_depth, we note the indices
910          of those elements, if they are for new context depths.  */
911       while (G.depth_in_use > (size_t)top->context_depth+1)
912         --G.depth_in_use;
913     }
914 }
915
916 /* For a page that is no longer needed, put it on the free page list.  */
917
918 static void
919 free_page (page_entry *entry)
920 {
921   if (GGC_DEBUG_LEVEL >= 2)
922     fprintf (G.debug_file,
923              "Deallocating page at %p, data %p-%p\n", (void *) entry,
924              entry->page, entry->page + entry->bytes - 1);
925
926   /* Mark the page as inaccessible.  Discard the handle to avoid handle
927      leak.  */
928   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->page, entry->bytes));
929
930   set_page_table_entry (entry->page, NULL);
931
932 #ifdef USING_MALLOC_PAGE_GROUPS
933   clear_page_group_in_use (entry->group, entry->page);
934 #endif
935
936   if (G.by_depth_in_use > 1)
937     {
938       page_entry *top = G.by_depth[G.by_depth_in_use-1];
939       int i = entry->index_by_depth;
940
941       /* We cannot free a page from a context deeper than the current
942          one.  */
943       gcc_assert (entry->context_depth == top->context_depth);
944       
945       /* Put top element into freed slot.  */
946       G.by_depth[i] = top;
947       G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1];
948       top->index_by_depth = i;
949     }
950   --G.by_depth_in_use;
951
952   adjust_depth ();
953
954   entry->next = G.free_pages;
955   G.free_pages = entry;
956 }
957
958 /* Release the free page cache to the system.  */
959
960 static void
961 release_pages (void)
962 {
963 #ifdef USING_MMAP
964   page_entry *p, *next;
965   char *start;
966   size_t len;
967
968   /* Gather up adjacent pages so they are unmapped together.  */
969   p = G.free_pages;
970
971   while (p)
972     {
973       start = p->page;
974       next = p->next;
975       len = p->bytes;
976       free (p);
977       p = next;
978
979       while (p && p->page == start + len)
980         {
981           next = p->next;
982           len += p->bytes;
983           free (p);
984           p = next;
985         }
986
987       munmap (start, len);
988       G.bytes_mapped -= len;
989     }
990
991   G.free_pages = NULL;
992 #endif
993 #ifdef USING_MALLOC_PAGE_GROUPS
994   page_entry **pp, *p;
995   page_group **gp, *g;
996
997   /* Remove all pages from free page groups from the list.  */
998   pp = &G.free_pages;
999   while ((p = *pp) != NULL)
1000     if (p->group->in_use == 0)
1001       {
1002         *pp = p->next;
1003         free (p);
1004       }
1005     else
1006       pp = &p->next;
1007
1008   /* Remove all free page groups, and release the storage.  */
1009   gp = &G.page_groups;
1010   while ((g = *gp) != NULL)
1011     if (g->in_use == 0)
1012       {
1013         *gp = g->next;
1014         G.bytes_mapped -= g->alloc_size;
1015         free (g->allocation);
1016       }
1017     else
1018       gp = &g->next;
1019 #endif
1020 }
1021
1022 /* This table provides a fast way to determine ceil(log_2(size)) for
1023    allocation requests.  The minimum allocation size is eight bytes.  */
1024
1025 static unsigned char size_lookup[257] =
1026 {
1027   3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
1028   4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1029   5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1030   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1031   6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1032   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1033   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1034   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1035   7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1036   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1037   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1038   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1039   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1040   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1041   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1042   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1043   8
1044 };
1045
1046 /* Typed allocation function.  Does nothing special in this collector.  */
1047
1048 void *
1049 ggc_alloc_typed_stat (enum gt_types_enum type ATTRIBUTE_UNUSED, size_t size
1050                       MEM_STAT_DECL)
1051 {
1052   return ggc_alloc_stat (size PASS_MEM_STAT);
1053 }
1054
1055 /* Allocate a chunk of memory of SIZE bytes.  Its contents are undefined.  */
1056
1057 void *
1058 ggc_alloc_stat (size_t size MEM_STAT_DECL)
1059 {
1060   size_t order, word, bit, object_offset, object_size;
1061   struct page_entry *entry;
1062   void *result;
1063
1064   if (size <= 256)
1065     {
1066       order = size_lookup[size];
1067       object_size = OBJECT_SIZE (order);
1068     }
1069   else
1070     {
1071       order = 9;
1072       while (size > (object_size = OBJECT_SIZE (order)))
1073         order++;
1074     }
1075
1076   /* If there are non-full pages for this size allocation, they are at
1077      the head of the list.  */
1078   entry = G.pages[order];
1079
1080   /* If there is no page for this object size, or all pages in this
1081      context are full, allocate a new page.  */
1082   if (entry == NULL || entry->num_free_objects == 0)
1083     {
1084       struct page_entry *new_entry;
1085       new_entry = alloc_page (order);
1086
1087       new_entry->index_by_depth = G.by_depth_in_use;
1088       push_by_depth (new_entry, 0);
1089
1090       /* We can skip context depths, if we do, make sure we go all the
1091          way to the new depth.  */
1092       while (new_entry->context_depth >= G.depth_in_use)
1093         push_depth (G.by_depth_in_use-1);
1094
1095       /* If this is the only entry, it's also the tail.  If it is not
1096          the only entry, then we must update the PREV pointer of the
1097          ENTRY (G.pages[order]) to point to our new page entry.  */
1098       if (entry == NULL)
1099         G.page_tails[order] = new_entry;
1100       else
1101         entry->prev = new_entry;
1102
1103       /* Put new pages at the head of the page list.  By definition the
1104          entry at the head of the list always has a NULL pointer.  */
1105       new_entry->next = entry;
1106       new_entry->prev = NULL;
1107       entry = new_entry;
1108       G.pages[order] = new_entry;
1109
1110       /* For a new page, we know the word and bit positions (in the
1111          in_use bitmap) of the first available object -- they're zero.  */
1112       new_entry->next_bit_hint = 1;
1113       word = 0;
1114       bit = 0;
1115       object_offset = 0;
1116     }
1117   else
1118     {
1119       /* First try to use the hint left from the previous allocation
1120          to locate a clear bit in the in-use bitmap.  We've made sure
1121          that the one-past-the-end bit is always set, so if the hint
1122          has run over, this test will fail.  */
1123       unsigned hint = entry->next_bit_hint;
1124       word = hint / HOST_BITS_PER_LONG;
1125       bit = hint % HOST_BITS_PER_LONG;
1126
1127       /* If the hint didn't work, scan the bitmap from the beginning.  */
1128       if ((entry->in_use_p[word] >> bit) & 1)
1129         {
1130           word = bit = 0;
1131           while (~entry->in_use_p[word] == 0)
1132             ++word;
1133
1134 #if GCC_VERSION >= 3004
1135           bit = __builtin_ctzl (~entry->in_use_p[word]);
1136 #else
1137           while ((entry->in_use_p[word] >> bit) & 1)
1138             ++bit;
1139 #endif
1140
1141           hint = word * HOST_BITS_PER_LONG + bit;
1142         }
1143
1144       /* Next time, try the next bit.  */
1145       entry->next_bit_hint = hint + 1;
1146
1147       object_offset = hint * object_size;
1148     }
1149
1150   /* Set the in-use bit.  */
1151   entry->in_use_p[word] |= ((unsigned long) 1 << bit);
1152
1153   /* Keep a running total of the number of free objects.  If this page
1154      fills up, we may have to move it to the end of the list if the
1155      next page isn't full.  If the next page is full, all subsequent
1156      pages are full, so there's no need to move it.  */
1157   if (--entry->num_free_objects == 0
1158       && entry->next != NULL
1159       && entry->next->num_free_objects > 0)
1160     {
1161       /* We have a new head for the list.  */
1162       G.pages[order] = entry->next;
1163
1164       /* We are moving ENTRY to the end of the page table list.
1165          The new page at the head of the list will have NULL in
1166          its PREV field and ENTRY will have NULL in its NEXT field.  */
1167       entry->next->prev = NULL;
1168       entry->next = NULL;
1169
1170       /* Append ENTRY to the tail of the list.  */
1171       entry->prev = G.page_tails[order];
1172       G.page_tails[order]->next = entry;
1173       G.page_tails[order] = entry;
1174     }
1175
1176   /* Calculate the object's address.  */
1177   result = entry->page + object_offset;
1178 #ifdef GATHER_STATISTICS
1179   ggc_record_overhead (OBJECT_SIZE (order), OBJECT_SIZE (order) - size,
1180                        result PASS_MEM_STAT);
1181 #endif
1182
1183 #ifdef ENABLE_GC_CHECKING
1184   /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the
1185      exact same semantics in presence of memory bugs, regardless of
1186      ENABLE_VALGRIND_CHECKING.  We override this request below.  Drop the
1187      handle to avoid handle leak.  */
1188   VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, object_size));
1189
1190   /* `Poison' the entire allocated object, including any padding at
1191      the end.  */
1192   memset (result, 0xaf, object_size);
1193
1194   /* Make the bytes after the end of the object unaccessible.  Discard the
1195      handle to avoid handle leak.  */
1196   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS ((char *) result + size,
1197                                             object_size - size));
1198 #endif
1199
1200   /* Tell Valgrind that the memory is there, but its content isn't
1201      defined.  The bytes at the end of the object are still marked
1202      unaccessible.  */
1203   VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
1204
1205   /* Keep track of how many bytes are being allocated.  This
1206      information is used in deciding when to collect.  */
1207   G.allocated += object_size;
1208
1209   /* For timevar statistics.  */
1210   timevar_ggc_mem_total += object_size;
1211
1212 #ifdef GATHER_STATISTICS
1213   {
1214     size_t overhead = object_size - size;
1215
1216     G.stats.total_overhead += overhead;
1217     G.stats.total_allocated += object_size;
1218     G.stats.total_overhead_per_order[order] += overhead;
1219     G.stats.total_allocated_per_order[order] += object_size;
1220
1221     if (size <= 32)
1222       {
1223         G.stats.total_overhead_under32 += overhead;
1224         G.stats.total_allocated_under32 += object_size;
1225       }
1226     if (size <= 64)
1227       {
1228         G.stats.total_overhead_under64 += overhead;
1229         G.stats.total_allocated_under64 += object_size;
1230       }
1231     if (size <= 128)
1232       {
1233         G.stats.total_overhead_under128 += overhead;
1234         G.stats.total_allocated_under128 += object_size;
1235       }
1236   }
1237 #endif
1238
1239   if (GGC_DEBUG_LEVEL >= 3)
1240     fprintf (G.debug_file,
1241              "Allocating object, requested size=%lu, actual=%lu at %p on %p\n",
1242              (unsigned long) size, (unsigned long) object_size, result,
1243              (void *) entry);
1244
1245   return result;
1246 }
1247
1248 /* If P is not marked, marks it and return false.  Otherwise return true.
1249    P must have been allocated by the GC allocator; it mustn't point to
1250    static objects, stack variables, or memory allocated with malloc.  */
1251
1252 int
1253 ggc_set_mark (const void *p)
1254 {
1255   page_entry *entry;
1256   unsigned bit, word;
1257   unsigned long mask;
1258
1259   /* Look up the page on which the object is alloced.  If the object
1260      wasn't allocated by the collector, we'll probably die.  */
1261   entry = lookup_page_table_entry (p);
1262   gcc_assert (entry);
1263
1264   /* Calculate the index of the object on the page; this is its bit
1265      position in the in_use_p bitmap.  */
1266   bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1267   word = bit / HOST_BITS_PER_LONG;
1268   mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
1269
1270   /* If the bit was previously set, skip it.  */
1271   if (entry->in_use_p[word] & mask)
1272     return 1;
1273
1274   /* Otherwise set it, and decrement the free object count.  */
1275   entry->in_use_p[word] |= mask;
1276   entry->num_free_objects -= 1;
1277
1278   if (GGC_DEBUG_LEVEL >= 4)
1279     fprintf (G.debug_file, "Marking %p\n", p);
1280
1281   return 0;
1282 }
1283
1284 /* Return 1 if P has been marked, zero otherwise.
1285    P must have been allocated by the GC allocator; it mustn't point to
1286    static objects, stack variables, or memory allocated with malloc.  */
1287
1288 int
1289 ggc_marked_p (const void *p)
1290 {
1291   page_entry *entry;
1292   unsigned bit, word;
1293   unsigned long mask;
1294
1295   /* Look up the page on which the object is alloced.  If the object
1296      wasn't allocated by the collector, we'll probably die.  */
1297   entry = lookup_page_table_entry (p);
1298   gcc_assert (entry);
1299
1300   /* Calculate the index of the object on the page; this is its bit
1301      position in the in_use_p bitmap.  */
1302   bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1303   word = bit / HOST_BITS_PER_LONG;
1304   mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
1305
1306   return (entry->in_use_p[word] & mask) != 0;
1307 }
1308
1309 /* Return the size of the gc-able object P.  */
1310
1311 size_t
1312 ggc_get_size (const void *p)
1313 {
1314   page_entry *pe = lookup_page_table_entry (p);
1315   return OBJECT_SIZE (pe->order);
1316 }
1317
1318 /* Release the memory for object P.  */
1319
1320 void
1321 ggc_free (void *p)
1322 {
1323   page_entry *pe = lookup_page_table_entry (p);
1324   size_t order = pe->order;
1325   size_t size = OBJECT_SIZE (order);
1326
1327 #ifdef GATHER_STATISTICS
1328   ggc_free_overhead (p);
1329 #endif
1330
1331   if (GGC_DEBUG_LEVEL >= 3)
1332     fprintf (G.debug_file,
1333              "Freeing object, actual size=%lu, at %p on %p\n",
1334              (unsigned long) size, p, (void *) pe);
1335
1336 #ifdef ENABLE_GC_CHECKING
1337   /* Poison the data, to indicate the data is garbage.  */
1338   VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (p, size));
1339   memset (p, 0xa5, size);
1340 #endif
1341   /* Let valgrind know the object is free.  */
1342   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (p, size));
1343
1344 #ifdef ENABLE_GC_ALWAYS_COLLECT
1345   /* In the completely-anal-checking mode, we do *not* immediately free
1346      the data, but instead verify that the data is *actually* not 
1347      reachable the next time we collect.  */
1348   {
1349     struct free_object *fo = xmalloc (sizeof (struct free_object));
1350     fo->object = p;
1351     fo->next = G.free_object_list;
1352     G.free_object_list = fo;
1353   }
1354 #else
1355   {
1356     unsigned int bit_offset, word, bit;
1357
1358     G.allocated -= size;
1359
1360     /* Mark the object not-in-use.  */
1361     bit_offset = OFFSET_TO_BIT (((const char *) p) - pe->page, order);
1362     word = bit_offset / HOST_BITS_PER_LONG;
1363     bit = bit_offset % HOST_BITS_PER_LONG;
1364     pe->in_use_p[word] &= ~(1UL << bit);
1365
1366     if (pe->num_free_objects++ == 0)
1367       {
1368         page_entry *p, *q;
1369
1370         /* If the page is completely full, then it's supposed to
1371            be after all pages that aren't.  Since we've freed one
1372            object from a page that was full, we need to move the
1373            page to the head of the list. 
1374
1375            PE is the node we want to move.  Q is the previous node
1376            and P is the next node in the list.  */
1377         q = pe->prev;
1378         if (q && q->num_free_objects == 0)
1379           {
1380             p = pe->next;
1381
1382             q->next = p;
1383
1384             /* If PE was at the end of the list, then Q becomes the
1385                new end of the list.  If PE was not the end of the
1386                list, then we need to update the PREV field for P.  */
1387             if (!p)
1388               G.page_tails[order] = q;
1389             else
1390               p->prev = q;
1391
1392             /* Move PE to the head of the list.  */
1393             pe->next = G.pages[order];
1394             pe->prev = NULL;
1395             G.pages[order]->prev = pe;
1396             G.pages[order] = pe;
1397           }
1398
1399         /* Reset the hint bit to point to the only free object.  */
1400         pe->next_bit_hint = bit_offset;
1401       }
1402   }
1403 #endif
1404 }
1405 \f
1406 /* Subroutine of init_ggc which computes the pair of numbers used to
1407    perform division by OBJECT_SIZE (order) and fills in inverse_table[].
1408
1409    This algorithm is taken from Granlund and Montgomery's paper
1410    "Division by Invariant Integers using Multiplication"
1411    (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
1412    constants).  */
1413
1414 static void
1415 compute_inverse (unsigned order)
1416 {
1417   size_t size, inv; 
1418   unsigned int e;
1419
1420   size = OBJECT_SIZE (order);
1421   e = 0;
1422   while (size % 2 == 0)
1423     {
1424       e++;
1425       size >>= 1;
1426     }
1427
1428   inv = size;
1429   while (inv * size != 1)
1430     inv = inv * (2 - inv*size);
1431
1432   DIV_MULT (order) = inv;
1433   DIV_SHIFT (order) = e;
1434 }
1435
1436 /* Initialize the ggc-mmap allocator.  */
1437 void
1438 init_ggc (void)
1439 {
1440   unsigned order;
1441
1442   G.pagesize = getpagesize();
1443   G.lg_pagesize = exact_log2 (G.pagesize);
1444
1445 #ifdef HAVE_MMAP_DEV_ZERO
1446   G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
1447   if (G.dev_zero_fd == -1)
1448     internal_error ("open /dev/zero: %m");
1449 #endif
1450
1451 #if 0
1452   G.debug_file = fopen ("ggc-mmap.debug", "w");
1453 #else
1454   G.debug_file = stdout;
1455 #endif
1456
1457 #ifdef USING_MMAP
1458   /* StunOS has an amazing off-by-one error for the first mmap allocation
1459      after fiddling with RLIMIT_STACK.  The result, as hard as it is to
1460      believe, is an unaligned page allocation, which would cause us to
1461      hork badly if we tried to use it.  */
1462   {
1463     char *p = alloc_anon (NULL, G.pagesize);
1464     struct page_entry *e;
1465     if ((size_t)p & (G.pagesize - 1))
1466       {
1467         /* How losing.  Discard this one and try another.  If we still
1468            can't get something useful, give up.  */
1469
1470         p = alloc_anon (NULL, G.pagesize);
1471         gcc_assert (!((size_t)p & (G.pagesize - 1)));
1472       }
1473
1474     /* We have a good page, might as well hold onto it...  */
1475     e = xcalloc (1, sizeof (struct page_entry));
1476     e->bytes = G.pagesize;
1477     e->page = p;
1478     e->next = G.free_pages;
1479     G.free_pages = e;
1480   }
1481 #endif
1482
1483   /* Initialize the object size table.  */
1484   for (order = 0; order < HOST_BITS_PER_PTR; ++order)
1485     object_size_table[order] = (size_t) 1 << order;
1486   for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
1487     {
1488       size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR];
1489
1490       /* If S is not a multiple of the MAX_ALIGNMENT, then round it up
1491          so that we're sure of getting aligned memory.  */
1492       s = ROUND_UP (s, MAX_ALIGNMENT);
1493       object_size_table[order] = s;
1494     }
1495
1496   /* Initialize the objects-per-page and inverse tables.  */
1497   for (order = 0; order < NUM_ORDERS; ++order)
1498     {
1499       objects_per_page_table[order] = G.pagesize / OBJECT_SIZE (order);
1500       if (objects_per_page_table[order] == 0)
1501         objects_per_page_table[order] = 1;
1502       compute_inverse (order);
1503     }
1504
1505   /* Reset the size_lookup array to put appropriately sized objects in
1506      the special orders.  All objects bigger than the previous power
1507      of two, but no greater than the special size, should go in the
1508      new order.  */
1509   for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
1510     {
1511       int o;
1512       int i;
1513
1514       o = size_lookup[OBJECT_SIZE (order)];
1515       for (i = OBJECT_SIZE (order); size_lookup [i] == o; --i)
1516         size_lookup[i] = order;
1517     }
1518
1519   G.depth_in_use = 0;
1520   G.depth_max = 10;
1521   G.depth = xmalloc (G.depth_max * sizeof (unsigned int));
1522
1523   G.by_depth_in_use = 0;
1524   G.by_depth_max = INITIAL_PTE_COUNT;
1525   G.by_depth = xmalloc (G.by_depth_max * sizeof (page_entry *));
1526   G.save_in_use = xmalloc (G.by_depth_max * sizeof (unsigned long *));
1527 }
1528
1529 /* Start a new GGC zone.  */
1530
1531 struct alloc_zone *
1532 new_ggc_zone (const char *name ATTRIBUTE_UNUSED)
1533 {
1534   return NULL;
1535 }
1536
1537 /* Destroy a GGC zone.  */
1538 void
1539 destroy_ggc_zone (struct alloc_zone *zone ATTRIBUTE_UNUSED)
1540 {
1541 }
1542
1543 /* Increment the `GC context'.  Objects allocated in an outer context
1544    are never freed, eliminating the need to register their roots.  */
1545
1546 void
1547 ggc_push_context (void)
1548 {
1549   ++G.context_depth;
1550
1551   /* Die on wrap.  */
1552   gcc_assert (G.context_depth < HOST_BITS_PER_LONG);
1553 }
1554
1555 /* Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P
1556    reflects reality.  Recalculate NUM_FREE_OBJECTS as well.  */
1557
1558 static void
1559 ggc_recalculate_in_use_p (page_entry *p)
1560 {
1561   unsigned int i;
1562   size_t num_objects;
1563
1564   /* Because the past-the-end bit in in_use_p is always set, we
1565      pretend there is one additional object.  */
1566   num_objects = OBJECTS_IN_PAGE (p) + 1;
1567
1568   /* Reset the free object count.  */
1569   p->num_free_objects = num_objects;
1570
1571   /* Combine the IN_USE_P and SAVE_IN_USE_P arrays.  */
1572   for (i = 0;
1573        i < CEIL (BITMAP_SIZE (num_objects),
1574                  sizeof (*p->in_use_p));
1575        ++i)
1576     {
1577       unsigned long j;
1578
1579       /* Something is in use if it is marked, or if it was in use in a
1580          context further down the context stack.  */
1581       p->in_use_p[i] |= save_in_use_p (p)[i];
1582
1583       /* Decrement the free object count for every object allocated.  */
1584       for (j = p->in_use_p[i]; j; j >>= 1)
1585         p->num_free_objects -= (j & 1);
1586     }
1587
1588   gcc_assert (p->num_free_objects < num_objects);
1589 }
1590
1591 /* Decrement the `GC context'.  All objects allocated since the
1592    previous ggc_push_context are migrated to the outer context.  */
1593
1594 void
1595 ggc_pop_context (void)
1596 {
1597   unsigned long omask;
1598   unsigned int depth, i, e;
1599 #ifdef ENABLE_CHECKING
1600   unsigned int order;
1601 #endif
1602
1603   depth = --G.context_depth;
1604   omask = (unsigned long)1 << (depth + 1);
1605
1606   if (!((G.context_depth_allocations | G.context_depth_collections) & omask))
1607     return;
1608
1609   G.context_depth_allocations |= (G.context_depth_allocations & omask) >> 1;
1610   G.context_depth_allocations &= omask - 1;
1611   G.context_depth_collections &= omask - 1;
1612
1613   /* The G.depth array is shortened so that the last index is the
1614      context_depth of the top element of by_depth.  */
1615   if (depth+1 < G.depth_in_use)
1616     e = G.depth[depth+1];
1617   else
1618     e = G.by_depth_in_use;
1619
1620   /* We might not have any PTEs of depth depth.  */
1621   if (depth < G.depth_in_use)
1622     {
1623
1624       /* First we go through all the pages at depth depth to
1625          recalculate the in use bits.  */
1626       for (i = G.depth[depth]; i < e; ++i)
1627         {
1628           page_entry *p = G.by_depth[i];
1629
1630           /* Check that all of the pages really are at the depth that
1631              we expect.  */
1632           gcc_assert (p->context_depth == depth);
1633           gcc_assert (p->index_by_depth == i);
1634
1635           prefetch (&save_in_use_p_i (i+8));
1636           prefetch (&save_in_use_p_i (i+16));
1637           if (save_in_use_p_i (i))
1638             {
1639               p = G.by_depth[i];
1640               ggc_recalculate_in_use_p (p);
1641               free (save_in_use_p_i (i));
1642               save_in_use_p_i (i) = 0;
1643             }
1644         }
1645     }
1646
1647   /* Then, we reset all page_entries with a depth greater than depth
1648      to be at depth.  */
1649   for (i = e; i < G.by_depth_in_use; ++i)
1650     {
1651       page_entry *p = G.by_depth[i];
1652
1653       /* Check that all of the pages really are at the depth we
1654          expect.  */
1655       gcc_assert (p->context_depth > depth);
1656       gcc_assert (p->index_by_depth == i);
1657       p->context_depth = depth;
1658     }
1659
1660   adjust_depth ();
1661
1662 #ifdef ENABLE_CHECKING
1663   for (order = 2; order < NUM_ORDERS; order++)
1664     {
1665       page_entry *p;
1666
1667       for (p = G.pages[order]; p != NULL; p = p->next)
1668         gcc_assert (p->context_depth < depth ||
1669                     (p->context_depth == depth && !save_in_use_p (p)));
1670     }
1671 #endif
1672 }
1673 \f
1674 /* Unmark all objects.  */
1675
1676 static void
1677 clear_marks (void)
1678 {
1679   unsigned order;
1680
1681   for (order = 2; order < NUM_ORDERS; order++)
1682     {
1683       page_entry *p;
1684
1685       for (p = G.pages[order]; p != NULL; p = p->next)
1686         {
1687           size_t num_objects = OBJECTS_IN_PAGE (p);
1688           size_t bitmap_size = BITMAP_SIZE (num_objects + 1);
1689
1690           /* The data should be page-aligned.  */
1691           gcc_assert (!((size_t) p->page & (G.pagesize - 1)));
1692
1693           /* Pages that aren't in the topmost context are not collected;
1694              nevertheless, we need their in-use bit vectors to store GC
1695              marks.  So, back them up first.  */
1696           if (p->context_depth < G.context_depth)
1697             {
1698               if (! save_in_use_p (p))
1699                 save_in_use_p (p) = xmalloc (bitmap_size);
1700               memcpy (save_in_use_p (p), p->in_use_p, bitmap_size);
1701             }
1702
1703           /* Reset reset the number of free objects and clear the
1704              in-use bits.  These will be adjusted by mark_obj.  */
1705           p->num_free_objects = num_objects;
1706           memset (p->in_use_p, 0, bitmap_size);
1707
1708           /* Make sure the one-past-the-end bit is always set.  */
1709           p->in_use_p[num_objects / HOST_BITS_PER_LONG]
1710             = ((unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG));
1711         }
1712     }
1713 }
1714
1715 /* Free all empty pages.  Partially empty pages need no attention
1716    because the `mark' bit doubles as an `unused' bit.  */
1717
1718 static void
1719 sweep_pages (void)
1720 {
1721   unsigned order;
1722
1723   for (order = 2; order < NUM_ORDERS; order++)
1724     {
1725       /* The last page-entry to consider, regardless of entries
1726          placed at the end of the list.  */
1727       page_entry * const last = G.page_tails[order];
1728
1729       size_t num_objects;
1730       size_t live_objects;
1731       page_entry *p, *previous;
1732       int done;
1733
1734       p = G.pages[order];
1735       if (p == NULL)
1736         continue;
1737
1738       previous = NULL;
1739       do
1740         {
1741           page_entry *next = p->next;
1742
1743           /* Loop until all entries have been examined.  */
1744           done = (p == last);
1745
1746           num_objects = OBJECTS_IN_PAGE (p);
1747
1748           /* Add all live objects on this page to the count of
1749              allocated memory.  */
1750           live_objects = num_objects - p->num_free_objects;
1751
1752           G.allocated += OBJECT_SIZE (order) * live_objects;
1753
1754           /* Only objects on pages in the topmost context should get
1755              collected.  */
1756           if (p->context_depth < G.context_depth)
1757             ;
1758
1759           /* Remove the page if it's empty.  */
1760           else if (live_objects == 0)
1761             {
1762               /* If P was the first page in the list, then NEXT
1763                  becomes the new first page in the list, otherwise
1764                  splice P out of the forward pointers.  */
1765               if (! previous)
1766                 G.pages[order] = next;
1767               else
1768                 previous->next = next;
1769             
1770               /* Splice P out of the back pointers too.  */
1771               if (next)
1772                 next->prev = previous;
1773
1774               /* Are we removing the last element?  */
1775               if (p == G.page_tails[order])
1776                 G.page_tails[order] = previous;
1777               free_page (p);
1778               p = previous;
1779             }
1780
1781           /* If the page is full, move it to the end.  */
1782           else if (p->num_free_objects == 0)
1783             {
1784               /* Don't move it if it's already at the end.  */
1785               if (p != G.page_tails[order])
1786                 {
1787                   /* Move p to the end of the list.  */
1788                   p->next = NULL;
1789                   p->prev = G.page_tails[order];
1790                   G.page_tails[order]->next = p;
1791
1792                   /* Update the tail pointer...  */
1793                   G.page_tails[order] = p;
1794
1795                   /* ... and the head pointer, if necessary.  */
1796                   if (! previous)
1797                     G.pages[order] = next;
1798                   else
1799                     previous->next = next;
1800
1801                   /* And update the backpointer in NEXT if necessary.  */
1802                   if (next)
1803                     next->prev = previous;
1804
1805                   p = previous;
1806                 }
1807             }
1808
1809           /* If we've fallen through to here, it's a page in the
1810              topmost context that is neither full nor empty.  Such a
1811              page must precede pages at lesser context depth in the
1812              list, so move it to the head.  */
1813           else if (p != G.pages[order])
1814             {
1815               previous->next = p->next;
1816
1817               /* Update the backchain in the next node if it exists.  */
1818               if (p->next)
1819                 p->next->prev = previous;
1820
1821               /* Move P to the head of the list.  */
1822               p->next = G.pages[order];
1823               p->prev = NULL;
1824               G.pages[order]->prev = p;
1825
1826               /* Update the head pointer.  */
1827               G.pages[order] = p;
1828
1829               /* Are we moving the last element?  */
1830               if (G.page_tails[order] == p)
1831                 G.page_tails[order] = previous;
1832               p = previous;
1833             }
1834
1835           previous = p;
1836           p = next;
1837         }
1838       while (! done);
1839
1840       /* Now, restore the in_use_p vectors for any pages from contexts
1841          other than the current one.  */
1842       for (p = G.pages[order]; p; p = p->next)
1843         if (p->context_depth != G.context_depth)
1844           ggc_recalculate_in_use_p (p);
1845     }
1846 }
1847
1848 #ifdef ENABLE_GC_CHECKING
1849 /* Clobber all free objects.  */
1850
1851 static void
1852 poison_pages (void)
1853 {
1854   unsigned order;
1855
1856   for (order = 2; order < NUM_ORDERS; order++)
1857     {
1858       size_t size = OBJECT_SIZE (order);
1859       page_entry *p;
1860
1861       for (p = G.pages[order]; p != NULL; p = p->next)
1862         {
1863           size_t num_objects;
1864           size_t i;
1865
1866           if (p->context_depth != G.context_depth)
1867             /* Since we don't do any collection for pages in pushed
1868                contexts, there's no need to do any poisoning.  And
1869                besides, the IN_USE_P array isn't valid until we pop
1870                contexts.  */
1871             continue;
1872
1873           num_objects = OBJECTS_IN_PAGE (p);
1874           for (i = 0; i < num_objects; i++)
1875             {
1876               size_t word, bit;
1877               word = i / HOST_BITS_PER_LONG;
1878               bit = i % HOST_BITS_PER_LONG;
1879               if (((p->in_use_p[word] >> bit) & 1) == 0)
1880                 {
1881                   char *object = p->page + i * size;
1882
1883                   /* Keep poison-by-write when we expect to use Valgrind,
1884                      so the exact same memory semantics is kept, in case
1885                      there are memory errors.  We override this request
1886                      below.  */
1887                   VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (object, size));
1888                   memset (object, 0xa5, size);
1889
1890                   /* Drop the handle to avoid handle leak.  */
1891                   VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (object, size));
1892                 }
1893             }
1894         }
1895     }
1896 }
1897 #else
1898 #define poison_pages()
1899 #endif
1900
1901 #ifdef ENABLE_GC_ALWAYS_COLLECT
1902 /* Validate that the reportedly free objects actually are.  */
1903
1904 static void
1905 validate_free_objects (void)
1906 {
1907   struct free_object *f, *next, *still_free = NULL;
1908
1909   for (f = G.free_object_list; f ; f = next)
1910     {
1911       page_entry *pe = lookup_page_table_entry (f->object);
1912       size_t bit, word;
1913
1914       bit = OFFSET_TO_BIT ((char *)f->object - pe->page, pe->order);
1915       word = bit / HOST_BITS_PER_LONG;
1916       bit = bit % HOST_BITS_PER_LONG;
1917       next = f->next;
1918
1919       /* Make certain it isn't visible from any root.  Notice that we
1920          do this check before sweep_pages merges save_in_use_p.  */
1921       gcc_assert (!(pe->in_use_p[word] & (1UL << bit)));
1922
1923       /* If the object comes from an outer context, then retain the
1924          free_object entry, so that we can verify that the address
1925          isn't live on the stack in some outer context.  */
1926       if (pe->context_depth != G.context_depth)
1927         {
1928           f->next = still_free;
1929           still_free = f;
1930         }
1931       else
1932         free (f);
1933     }
1934
1935   G.free_object_list = still_free;
1936 }
1937 #else
1938 #define validate_free_objects()
1939 #endif
1940
1941 /* Top level mark-and-sweep routine.  */
1942
1943 void
1944 ggc_collect (void)
1945 {
1946   /* Avoid frequent unnecessary work by skipping collection if the
1947      total allocations haven't expanded much since the last
1948      collection.  */
1949   float allocated_last_gc =
1950     MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
1951
1952   float min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
1953
1954   if (G.allocated < allocated_last_gc + min_expand && !ggc_force_collect)
1955     return;
1956
1957   timevar_push (TV_GC);
1958   if (!quiet_flag)
1959     fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
1960   if (GGC_DEBUG_LEVEL >= 2)
1961     fprintf (G.debug_file, "BEGIN COLLECTING\n");
1962
1963   /* Zero the total allocated bytes.  This will be recalculated in the
1964      sweep phase.  */
1965   G.allocated = 0;
1966
1967   /* Release the pages we freed the last time we collected, but didn't
1968      reuse in the interim.  */
1969   release_pages ();
1970
1971   /* Indicate that we've seen collections at this context depth.  */
1972   G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
1973
1974   clear_marks ();
1975   ggc_mark_roots ();
1976 #ifdef GATHER_STATISTICS
1977   ggc_prune_overhead_list ();
1978 #endif
1979   poison_pages ();
1980   validate_free_objects ();
1981   sweep_pages ();
1982
1983   G.allocated_last_gc = G.allocated;
1984
1985   timevar_pop (TV_GC);
1986
1987   if (!quiet_flag)
1988     fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
1989   if (GGC_DEBUG_LEVEL >= 2)
1990     fprintf (G.debug_file, "END COLLECTING\n");
1991 }
1992
1993 /* Print allocation statistics.  */
1994 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
1995                   ? (x) \
1996                   : ((x) < 1024*1024*10 \
1997                      ? (x) / 1024 \
1998                      : (x) / (1024*1024))))
1999 #define STAT_LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
2000
2001 void
2002 ggc_print_statistics (void)
2003 {
2004   struct ggc_statistics stats;
2005   unsigned int i;
2006   size_t total_overhead = 0;
2007
2008   /* Clear the statistics.  */
2009   memset (&stats, 0, sizeof (stats));
2010
2011   /* Make sure collection will really occur.  */
2012   G.allocated_last_gc = 0;
2013
2014   /* Collect and print the statistics common across collectors.  */
2015   ggc_print_common_statistics (stderr, &stats);
2016
2017   /* Release free pages so that we will not count the bytes allocated
2018      there as part of the total allocated memory.  */
2019   release_pages ();
2020
2021   /* Collect some information about the various sizes of
2022      allocation.  */
2023   fprintf (stderr,
2024            "Memory still allocated at the end of the compilation process\n");
2025   fprintf (stderr, "%-5s %10s  %10s  %10s\n",
2026            "Size", "Allocated", "Used", "Overhead");
2027   for (i = 0; i < NUM_ORDERS; ++i)
2028     {
2029       page_entry *p;
2030       size_t allocated;
2031       size_t in_use;
2032       size_t overhead;
2033
2034       /* Skip empty entries.  */
2035       if (!G.pages[i])
2036         continue;
2037
2038       overhead = allocated = in_use = 0;
2039
2040       /* Figure out the total number of bytes allocated for objects of
2041          this size, and how many of them are actually in use.  Also figure
2042          out how much memory the page table is using.  */
2043       for (p = G.pages[i]; p; p = p->next)
2044         {
2045           allocated += p->bytes;
2046           in_use +=
2047             (OBJECTS_IN_PAGE (p) - p->num_free_objects) * OBJECT_SIZE (i);
2048
2049           overhead += (sizeof (page_entry) - sizeof (long)
2050                        + BITMAP_SIZE (OBJECTS_IN_PAGE (p) + 1));
2051         }
2052       fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
2053                (unsigned long) OBJECT_SIZE (i),
2054                SCALE (allocated), STAT_LABEL (allocated),
2055                SCALE (in_use), STAT_LABEL (in_use),
2056                SCALE (overhead), STAT_LABEL (overhead));
2057       total_overhead += overhead;
2058     }
2059   fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
2060            SCALE (G.bytes_mapped), STAT_LABEL (G.bytes_mapped),
2061            SCALE (G.allocated), STAT_LABEL(G.allocated),
2062            SCALE (total_overhead), STAT_LABEL (total_overhead));
2063
2064 #ifdef GATHER_STATISTICS  
2065   {
2066     fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
2067
2068     fprintf (stderr, "Total Overhead:                        %10lld\n",
2069              G.stats.total_overhead);
2070     fprintf (stderr, "Total Allocated:                       %10lld\n",
2071              G.stats.total_allocated);
2072
2073     fprintf (stderr, "Total Overhead  under  32B:            %10lld\n",
2074              G.stats.total_overhead_under32);
2075     fprintf (stderr, "Total Allocated under  32B:            %10lld\n",
2076              G.stats.total_allocated_under32);
2077     fprintf (stderr, "Total Overhead  under  64B:            %10lld\n",
2078              G.stats.total_overhead_under64);
2079     fprintf (stderr, "Total Allocated under  64B:            %10lld\n",
2080              G.stats.total_allocated_under64);
2081     fprintf (stderr, "Total Overhead  under 128B:            %10lld\n",
2082              G.stats.total_overhead_under128);
2083     fprintf (stderr, "Total Allocated under 128B:            %10lld\n",
2084              G.stats.total_allocated_under128);
2085    
2086     for (i = 0; i < NUM_ORDERS; i++)
2087       if (G.stats.total_allocated_per_order[i])
2088         {
2089           fprintf (stderr, "Total Overhead  page size %7d:     %10lld\n",
2090                    OBJECT_SIZE (i), G.stats.total_overhead_per_order[i]);
2091           fprintf (stderr, "Total Allocated page size %7d:     %10lld\n",
2092                    OBJECT_SIZE (i), G.stats.total_allocated_per_order[i]);
2093         }
2094   }
2095 #endif
2096 }
2097 \f
2098 struct ggc_pch_data
2099 {
2100   struct ggc_pch_ondisk
2101   {
2102     unsigned totals[NUM_ORDERS];
2103   } d;
2104   size_t base[NUM_ORDERS];
2105   size_t written[NUM_ORDERS];
2106 };
2107
2108 struct ggc_pch_data *
2109 init_ggc_pch (void)
2110 {
2111   return xcalloc (sizeof (struct ggc_pch_data), 1);
2112 }
2113
2114 void
2115 ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2116                       size_t size, bool is_string ATTRIBUTE_UNUSED,
2117                       enum gt_types_enum type ATTRIBUTE_UNUSED)
2118 {
2119   unsigned order;
2120
2121   if (size <= 256)
2122     order = size_lookup[size];
2123   else
2124     {
2125       order = 9;
2126       while (size > OBJECT_SIZE (order))
2127         order++;
2128     }
2129
2130   d->d.totals[order]++;
2131 }
2132
2133 size_t
2134 ggc_pch_total_size (struct ggc_pch_data *d)
2135 {
2136   size_t a = 0;
2137   unsigned i;
2138
2139   for (i = 0; i < NUM_ORDERS; i++)
2140     a += ROUND_UP (d->d.totals[i] * OBJECT_SIZE (i), G.pagesize);
2141   return a;
2142 }
2143
2144 void
2145 ggc_pch_this_base (struct ggc_pch_data *d, void *base)
2146 {
2147   size_t a = (size_t) base;
2148   unsigned i;
2149
2150   for (i = 0; i < NUM_ORDERS; i++)
2151     {
2152       d->base[i] = a;
2153       a += ROUND_UP (d->d.totals[i] * OBJECT_SIZE (i), G.pagesize);
2154     }
2155 }
2156
2157
2158 char *
2159 ggc_pch_alloc_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2160                       size_t size, bool is_string ATTRIBUTE_UNUSED,
2161                       enum gt_types_enum type ATTRIBUTE_UNUSED)
2162 {
2163   unsigned order;
2164   char *result;
2165
2166   if (size <= 256)
2167     order = size_lookup[size];
2168   else
2169     {
2170       order = 9;
2171       while (size > OBJECT_SIZE (order))
2172         order++;
2173     }
2174
2175   result = (char *) d->base[order];
2176   d->base[order] += OBJECT_SIZE (order);
2177   return result;
2178 }
2179
2180 void
2181 ggc_pch_prepare_write (struct ggc_pch_data *d ATTRIBUTE_UNUSED,
2182                        FILE *f ATTRIBUTE_UNUSED)
2183 {
2184   /* Nothing to do.  */
2185 }
2186
2187 void
2188 ggc_pch_write_object (struct ggc_pch_data *d ATTRIBUTE_UNUSED,
2189                       FILE *f, void *x, void *newx ATTRIBUTE_UNUSED,
2190                       size_t size, bool is_string ATTRIBUTE_UNUSED)
2191 {
2192   unsigned order;
2193   static const char emptyBytes[256];
2194
2195   if (size <= 256)
2196     order = size_lookup[size];
2197   else
2198     {
2199       order = 9;
2200       while (size > OBJECT_SIZE (order))
2201         order++;
2202     }
2203
2204   if (fwrite (x, size, 1, f) != 1)
2205     fatal_error ("can't write PCH file: %m");
2206
2207   /* If SIZE is not the same as OBJECT_SIZE(order), then we need to pad the
2208      object out to OBJECT_SIZE(order).  This happens for strings.  */
2209
2210   if (size != OBJECT_SIZE (order))
2211     {
2212       unsigned padding = OBJECT_SIZE(order) - size;
2213
2214       /* To speed small writes, we use a nulled-out array that's larger
2215          than most padding requests as the source for our null bytes.  This
2216          permits us to do the padding with fwrite() rather than fseek(), and
2217          limits the chance the OS may try to flush any outstanding writes.  */
2218       if (padding <= sizeof(emptyBytes))
2219         {
2220           if (fwrite (emptyBytes, 1, padding, f) != padding)
2221             fatal_error ("can't write PCH file");
2222         }
2223       else
2224         {
2225           /* Larger than our buffer?  Just default to fseek.  */
2226           if (fseek (f, padding, SEEK_CUR) != 0)
2227             fatal_error ("can't write PCH file");
2228         }
2229     }
2230
2231   d->written[order]++;
2232   if (d->written[order] == d->d.totals[order]
2233       && fseek (f, ROUND_UP_VALUE (d->d.totals[order] * OBJECT_SIZE (order),
2234                                    G.pagesize),
2235                 SEEK_CUR) != 0)
2236     fatal_error ("can't write PCH file: %m");
2237 }
2238
2239 void
2240 ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
2241 {
2242   if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
2243     fatal_error ("can't write PCH file: %m");
2244   free (d);
2245 }
2246
2247 /* Move the PCH PTE entries just added to the end of by_depth, to the
2248    front.  */
2249
2250 static void
2251 move_ptes_to_front (int count_old_page_tables, int count_new_page_tables)
2252 {
2253   unsigned i;
2254
2255   /* First, we swap the new entries to the front of the varrays.  */
2256   page_entry **new_by_depth;
2257   unsigned long **new_save_in_use;
2258
2259   new_by_depth = xmalloc (G.by_depth_max * sizeof (page_entry *));
2260   new_save_in_use = xmalloc (G.by_depth_max * sizeof (unsigned long *));
2261
2262   memcpy (&new_by_depth[0],
2263           &G.by_depth[count_old_page_tables],
2264           count_new_page_tables * sizeof (void *));
2265   memcpy (&new_by_depth[count_new_page_tables],
2266           &G.by_depth[0],
2267           count_old_page_tables * sizeof (void *));
2268   memcpy (&new_save_in_use[0],
2269           &G.save_in_use[count_old_page_tables],
2270           count_new_page_tables * sizeof (void *));
2271   memcpy (&new_save_in_use[count_new_page_tables],
2272           &G.save_in_use[0],
2273           count_old_page_tables * sizeof (void *));
2274
2275   free (G.by_depth);
2276   free (G.save_in_use);
2277
2278   G.by_depth = new_by_depth;
2279   G.save_in_use = new_save_in_use;
2280
2281   /* Now update all the index_by_depth fields.  */
2282   for (i = G.by_depth_in_use; i > 0; --i)
2283     {
2284       page_entry *p = G.by_depth[i-1];
2285       p->index_by_depth = i-1;
2286     }
2287
2288   /* And last, we update the depth pointers in G.depth.  The first
2289      entry is already 0, and context 0 entries always start at index
2290      0, so there is nothing to update in the first slot.  We need a
2291      second slot, only if we have old ptes, and if we do, they start
2292      at index count_new_page_tables.  */
2293   if (count_old_page_tables)
2294     push_depth (count_new_page_tables);
2295 }
2296
2297 void
2298 ggc_pch_read (FILE *f, void *addr)
2299 {
2300   struct ggc_pch_ondisk d;
2301   unsigned i;
2302   char *offs = addr;
2303   unsigned long count_old_page_tables;
2304   unsigned long count_new_page_tables;
2305
2306   count_old_page_tables = G.by_depth_in_use;
2307
2308   /* We've just read in a PCH file.  So, every object that used to be
2309      allocated is now free.  */
2310   clear_marks ();
2311 #ifdef ENABLE_GC_CHECKING
2312   poison_pages ();
2313 #endif
2314
2315   /* No object read from a PCH file should ever be freed.  So, set the
2316      context depth to 1, and set the depth of all the currently-allocated
2317      pages to be 1 too.  PCH pages will have depth 0.  */
2318   gcc_assert (!G.context_depth);
2319   G.context_depth = 1;
2320   for (i = 0; i < NUM_ORDERS; i++)
2321     {
2322       page_entry *p;
2323       for (p = G.pages[i]; p != NULL; p = p->next)
2324         p->context_depth = G.context_depth;
2325     }
2326
2327   /* Allocate the appropriate page-table entries for the pages read from
2328      the PCH file.  */
2329   if (fread (&d, sizeof (d), 1, f) != 1)
2330     fatal_error ("can't read PCH file: %m");
2331
2332   for (i = 0; i < NUM_ORDERS; i++)
2333     {
2334       struct page_entry *entry;
2335       char *pte;
2336       size_t bytes;
2337       size_t num_objs;
2338       size_t j;
2339
2340       if (d.totals[i] == 0)
2341         continue;
2342
2343       bytes = ROUND_UP (d.totals[i] * OBJECT_SIZE (i), G.pagesize);
2344       num_objs = bytes / OBJECT_SIZE (i);
2345       entry = xcalloc (1, (sizeof (struct page_entry)
2346                            - sizeof (long)
2347                            + BITMAP_SIZE (num_objs + 1)));
2348       entry->bytes = bytes;
2349       entry->page = offs;
2350       entry->context_depth = 0;
2351       offs += bytes;
2352       entry->num_free_objects = 0;
2353       entry->order = i;
2354
2355       for (j = 0;
2356            j + HOST_BITS_PER_LONG <= num_objs + 1;
2357            j += HOST_BITS_PER_LONG)
2358         entry->in_use_p[j / HOST_BITS_PER_LONG] = -1;
2359       for (; j < num_objs + 1; j++)
2360         entry->in_use_p[j / HOST_BITS_PER_LONG]
2361           |= 1L << (j % HOST_BITS_PER_LONG);
2362
2363       for (pte = entry->page;
2364            pte < entry->page + entry->bytes;
2365            pte += G.pagesize)
2366         set_page_table_entry (pte, entry);
2367
2368       if (G.page_tails[i] != NULL)
2369         G.page_tails[i]->next = entry;
2370       else
2371         G.pages[i] = entry;
2372       G.page_tails[i] = entry;
2373
2374       /* We start off by just adding all the new information to the
2375          end of the varrays, later, we will move the new information
2376          to the front of the varrays, as the PCH page tables are at
2377          context 0.  */
2378       push_by_depth (entry, 0);
2379     }
2380
2381   /* Now, we update the various data structures that speed page table
2382      handling.  */
2383   count_new_page_tables = G.by_depth_in_use - count_old_page_tables;
2384
2385   move_ptes_to_front (count_old_page_tables, count_new_page_tables);
2386
2387   /* Update the statistics.  */
2388   G.allocated = G.allocated_last_gc = offs - (char *)addr;
2389 }