OSDN Git Service

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