* gimplify.c (find_single_pointer_decl_1): New static function.
[official-gcc.git] / gcc / ggc-zone.c
blob1d6edfb707ec6cdd4979da1d44c21e59634d7212
1 /* "Bag-of-pages" zone garbage collector for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
5 Contributed by Richard Henderson (rth@redhat.com) and Daniel Berlin
6 (dberlin@dberlin.org). Rewritten by Daniel Jacobowitz
7 <dan@codesourcery.com>.
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 2, or (at your option) any later
14 version.
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 for more details.
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301, USA. */
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "tree.h"
31 #include "rtl.h"
32 #include "tm_p.h"
33 #include "toplev.h"
34 #include "varray.h"
35 #include "flags.h"
36 #include "ggc.h"
37 #include "timevar.h"
38 #include "params.h"
39 #include "bitmap.h"
41 #ifdef ENABLE_VALGRIND_CHECKING
42 # ifdef HAVE_VALGRIND_MEMCHECK_H
43 # include <valgrind/memcheck.h>
44 # elif defined HAVE_MEMCHECK_H
45 # include <memcheck.h>
46 # else
47 # include <valgrind.h>
48 # endif
49 #else
50 /* Avoid #ifdef:s when we can help it. */
51 #define VALGRIND_DISCARD(x)
52 #define VALGRIND_MALLOCLIKE_BLOCK(w,x,y,z)
53 #define VALGRIND_FREELIKE_BLOCK(x,y)
54 #endif
56 /* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
57 file open. Prefer either to valloc. */
58 #ifdef HAVE_MMAP_ANON
59 # undef HAVE_MMAP_DEV_ZERO
61 # include <sys/mman.h>
62 # ifndef MAP_FAILED
63 # define MAP_FAILED -1
64 # endif
65 # if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
66 # define MAP_ANONYMOUS MAP_ANON
67 # endif
68 # define USING_MMAP
69 #endif
71 #ifdef HAVE_MMAP_DEV_ZERO
72 # include <sys/mman.h>
73 # ifndef MAP_FAILED
74 # define MAP_FAILED -1
75 # endif
76 # define USING_MMAP
77 #endif
79 #ifndef USING_MMAP
80 #error Zone collector requires mmap
81 #endif
83 #if (GCC_VERSION < 3001)
84 #define prefetch(X) ((void) X)
85 #define prefetchw(X) ((void) X)
86 #else
87 #define prefetch(X) __builtin_prefetch (X)
88 #define prefetchw(X) __builtin_prefetch (X, 1, 3)
89 #endif
91 /* FUTURE NOTES:
93 If we track inter-zone pointers, we can mark single zones at a
94 time.
96 If we have a zone where we guarantee no inter-zone pointers, we
97 could mark that zone separately.
99 The garbage zone should not be marked, and we should return 1 in
100 ggc_set_mark for any object in the garbage zone, which cuts off
101 marking quickly. */
103 /* Strategy:
105 This garbage-collecting allocator segregates objects into zones.
106 It also segregates objects into "large" and "small" bins. Large
107 objects are greater than page size.
109 Pages for small objects are broken up into chunks. The page has
110 a bitmap which marks the start position of each chunk (whether
111 allocated or free). Free chunks are on one of the zone's free
112 lists and contain a pointer to the next free chunk. Chunks in
113 most of the free lists have a fixed size determined by the
114 free list. Chunks in the "other" sized free list have their size
115 stored right after their chain pointer.
117 Empty pages (of all sizes) are kept on a single page cache list,
118 and are considered first when new pages are required; they are
119 deallocated at the start of the next collection if they haven't
120 been recycled by then. The free page list is currently per-zone. */
122 /* Define GGC_DEBUG_LEVEL to print debugging information.
123 0: No debugging output.
124 1: GC statistics only.
125 2: Page-entry allocations/deallocations as well.
126 3: Object allocations as well.
127 4: Object marks as well. */
128 #define GGC_DEBUG_LEVEL (0)
130 #ifndef HOST_BITS_PER_PTR
131 #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
132 #endif
134 /* This structure manages small free chunks. The SIZE field is only
135 initialized if the chunk is in the "other" sized free list. Large
136 chunks are allocated one at a time to their own page, and so don't
137 come in here. */
139 struct alloc_chunk {
140 struct alloc_chunk *next_free;
141 unsigned int size;
144 /* The size of the fixed-size portion of a small page descriptor. */
145 #define PAGE_OVERHEAD (offsetof (struct small_page_entry, alloc_bits))
147 /* The collector's idea of the page size. This must be a power of two
148 no larger than the system page size, because pages must be aligned
149 to this amount and are tracked at this granularity in the page
150 table. We choose a size at compile time for efficiency.
152 We could make a better guess at compile time if PAGE_SIZE is a
153 constant in system headers, and PAGE_SHIFT is defined... */
154 #define GGC_PAGE_SIZE 4096
155 #define GGC_PAGE_MASK (GGC_PAGE_SIZE - 1)
156 #define GGC_PAGE_SHIFT 12
158 #if 0
159 /* Alternative definitions which use the runtime page size. */
160 #define GGC_PAGE_SIZE G.pagesize
161 #define GGC_PAGE_MASK G.page_mask
162 #define GGC_PAGE_SHIFT G.lg_pagesize
163 #endif
165 /* The size of a small page managed by the garbage collector. This
166 must currently be GGC_PAGE_SIZE, but with a few changes could
167 be any multiple of it to reduce certain kinds of overhead. */
168 #define SMALL_PAGE_SIZE GGC_PAGE_SIZE
170 /* Free bin information. These numbers may be in need of re-tuning.
171 In general, decreasing the number of free bins would seem to
172 increase the time it takes to allocate... */
174 /* FIXME: We can't use anything but MAX_ALIGNMENT for the bin size
175 today. */
177 #define NUM_FREE_BINS 64
178 #define FREE_BIN_DELTA MAX_ALIGNMENT
179 #define SIZE_BIN_DOWN(SIZE) ((SIZE) / FREE_BIN_DELTA)
181 /* Allocation and marking parameters. */
183 /* The smallest allocatable unit to keep track of. */
184 #define BYTES_PER_ALLOC_BIT MAX_ALIGNMENT
186 /* The smallest markable unit. If we require each allocated object
187 to contain at least two allocatable units, we can use half as many
188 bits for the mark bitmap. But this adds considerable complexity
189 to sweeping. */
190 #define BYTES_PER_MARK_BIT BYTES_PER_ALLOC_BIT
192 #define BYTES_PER_MARK_WORD (8 * BYTES_PER_MARK_BIT * sizeof (mark_type))
194 /* We use this structure to determine the alignment required for
195 allocations.
197 There are several things wrong with this estimation of alignment.
199 The maximum alignment for a structure is often less than the
200 maximum alignment for a basic data type; for instance, on some
201 targets long long must be aligned to sizeof (int) in a structure
202 and sizeof (long long) in a variable. i386-linux is one example;
203 Darwin is another (sometimes, depending on the compiler in use).
205 Also, long double is not included. Nothing in GCC uses long
206 double, so we assume that this is OK. On powerpc-darwin, adding
207 long double would bring the maximum alignment up to 16 bytes,
208 and until we need long double (or to vectorize compiler operations)
209 that's painfully wasteful. This will need to change, some day. */
211 struct max_alignment {
212 char c;
213 union {
214 HOST_WIDEST_INT i;
215 double d;
216 } u;
219 /* The biggest alignment required. */
221 #define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
223 /* Compute the smallest multiple of F that is >= X. */
225 #define ROUND_UP(x, f) (CEIL (x, f) * (f))
227 /* Types to use for the allocation and mark bitmaps. It might be
228 a good idea to add ffsl to libiberty and use unsigned long
229 instead; that could speed us up where long is wider than int. */
231 typedef unsigned int alloc_type;
232 typedef unsigned int mark_type;
233 #define alloc_ffs(x) ffs(x)
235 /* A page_entry records the status of an allocation page. This is the
236 common data between all three kinds of pages - small, large, and
237 PCH. */
238 typedef struct page_entry
240 /* The address at which the memory is allocated. */
241 char *page;
243 /* The zone that this page entry belongs to. */
244 struct alloc_zone *zone;
246 #ifdef GATHER_STATISTICS
247 /* How many collections we've survived. */
248 size_t survived;
249 #endif
251 /* Does this page contain small objects, or one large object? */
252 bool large_p;
254 /* Is this page part of the loaded PCH? */
255 bool pch_p;
256 } page_entry;
258 /* Additional data needed for small pages. */
259 struct small_page_entry
261 struct page_entry common;
263 /* The next small page entry, or NULL if this is the last. */
264 struct small_page_entry *next;
266 /* If currently marking this zone, a pointer to the mark bits
267 for this page. If we aren't currently marking this zone,
268 this pointer may be stale (pointing to freed memory). */
269 mark_type *mark_bits;
271 /* The allocation bitmap. This array extends far enough to have
272 one bit for every BYTES_PER_ALLOC_BIT bytes in the page. */
273 alloc_type alloc_bits[1];
276 /* Additional data needed for large pages. */
277 struct large_page_entry
279 struct page_entry common;
281 /* The next large page entry, or NULL if this is the last. */
282 struct large_page_entry *next;
284 /* The number of bytes allocated, not including the page entry. */
285 size_t bytes;
287 /* The previous page in the list, so that we can unlink this one. */
288 struct large_page_entry *prev;
290 /* During marking, is this object marked? */
291 bool mark_p;
294 /* A two-level tree is used to look up the page-entry for a given
295 pointer. Two chunks of the pointer's bits are extracted to index
296 the first and second levels of the tree, as follows:
298 HOST_PAGE_SIZE_BITS
299 32 | |
300 msb +----------------+----+------+------+ lsb
301 | | |
302 PAGE_L1_BITS |
304 PAGE_L2_BITS
306 The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry
307 pages are aligned on system page boundaries. The next most
308 significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first
309 index values in the lookup table, respectively.
311 For 32-bit architectures and the settings below, there are no
312 leftover bits. For architectures with wider pointers, the lookup
313 tree points to a list of pages, which must be scanned to find the
314 correct one. */
316 #define PAGE_L1_BITS (8)
317 #define PAGE_L2_BITS (32 - PAGE_L1_BITS - GGC_PAGE_SHIFT)
318 #define PAGE_L1_SIZE ((size_t) 1 << PAGE_L1_BITS)
319 #define PAGE_L2_SIZE ((size_t) 1 << PAGE_L2_BITS)
321 #define LOOKUP_L1(p) \
322 (((size_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
324 #define LOOKUP_L2(p) \
325 (((size_t) (p) >> GGC_PAGE_SHIFT) & ((1 << PAGE_L2_BITS) - 1))
327 #if HOST_BITS_PER_PTR <= 32
329 /* On 32-bit hosts, we use a two level page table, as pictured above. */
330 typedef page_entry **page_table[PAGE_L1_SIZE];
332 #else
334 /* On 64-bit hosts, we use the same two level page tables plus a linked
335 list that disambiguates the top 32-bits. There will almost always be
336 exactly one entry in the list. */
337 typedef struct page_table_chain
339 struct page_table_chain *next;
340 size_t high_bits;
341 page_entry **table[PAGE_L1_SIZE];
342 } *page_table;
344 #endif
346 /* The global variables. */
347 static struct globals
349 /* The linked list of zones. */
350 struct alloc_zone *zones;
352 /* Lookup table for associating allocation pages with object addresses. */
353 page_table lookup;
355 /* The system's page size, and related constants. */
356 size_t pagesize;
357 size_t lg_pagesize;
358 size_t page_mask;
360 /* The size to allocate for a small page entry. This includes
361 the size of the structure and the size of the allocation
362 bitmap. */
363 size_t small_page_overhead;
365 #if defined (HAVE_MMAP_DEV_ZERO)
366 /* A file descriptor open to /dev/zero for reading. */
367 int dev_zero_fd;
368 #endif
370 /* Allocate pages in chunks of this size, to throttle calls to memory
371 allocation routines. The first page is used, the rest go onto the
372 free list. */
373 size_t quire_size;
375 /* The file descriptor for debugging output. */
376 FILE *debug_file;
377 } G;
379 /* A zone allocation structure. There is one of these for every
380 distinct allocation zone. */
381 struct alloc_zone
383 /* The most recent free chunk is saved here, instead of in the linked
384 free list, to decrease list manipulation. It is most likely that we
385 will want this one. */
386 char *cached_free;
387 size_t cached_free_size;
389 /* Linked lists of free storage. Slots 1 ... NUM_FREE_BINS have chunks of size
390 FREE_BIN_DELTA. All other chunks are in slot 0. */
391 struct alloc_chunk *free_chunks[NUM_FREE_BINS + 1];
393 /* The highest bin index which might be non-empty. It may turn out
394 to be empty, in which case we have to search downwards. */
395 size_t high_free_bin;
397 /* Bytes currently allocated in this zone. */
398 size_t allocated;
400 /* Linked list of the small pages in this zone. */
401 struct small_page_entry *pages;
403 /* Doubly linked list of large pages in this zone. */
404 struct large_page_entry *large_pages;
406 /* If we are currently marking this zone, a pointer to the mark bits. */
407 mark_type *mark_bits;
409 /* Name of the zone. */
410 const char *name;
412 /* The number of small pages currently allocated in this zone. */
413 size_t n_small_pages;
415 /* Bytes allocated at the end of the last collection. */
416 size_t allocated_last_gc;
418 /* Total amount of memory mapped. */
419 size_t bytes_mapped;
421 /* A cache of free system pages. */
422 struct small_page_entry *free_pages;
424 /* Next zone in the linked list of zones. */
425 struct alloc_zone *next_zone;
427 /* True if this zone was collected during this collection. */
428 bool was_collected;
430 /* True if this zone should be destroyed after the next collection. */
431 bool dead;
433 #ifdef GATHER_STATISTICS
434 struct
436 /* Total memory allocated with ggc_alloc. */
437 unsigned long long total_allocated;
438 /* Total overhead for memory to be allocated with ggc_alloc. */
439 unsigned long long total_overhead;
441 /* Total allocations and overhead for sizes less than 32, 64 and 128.
442 These sizes are interesting because they are typical cache line
443 sizes. */
445 unsigned long long total_allocated_under32;
446 unsigned long long total_overhead_under32;
448 unsigned long long total_allocated_under64;
449 unsigned long long total_overhead_under64;
451 unsigned long long total_allocated_under128;
452 unsigned long long total_overhead_under128;
453 } stats;
454 #endif
455 } main_zone;
457 /* Some default zones. */
458 struct alloc_zone rtl_zone;
459 struct alloc_zone tree_zone;
460 struct alloc_zone tree_id_zone;
462 /* The PCH zone does not need a normal zone structure, and it does
463 not live on the linked list of zones. */
464 struct pch_zone
466 /* The start of the PCH zone. NULL if there is none. */
467 char *page;
469 /* The end of the PCH zone. NULL if there is none. */
470 char *end;
472 /* The size of the PCH zone. 0 if there is none. */
473 size_t bytes;
475 /* The allocation bitmap for the PCH zone. */
476 alloc_type *alloc_bits;
478 /* If we are currently marking, the mark bitmap for the PCH zone.
479 When it is first read in, we could avoid marking the PCH,
480 because it will not contain any pointers to GC memory outside
481 of the PCH; however, the PCH is currently mapped as writable,
482 so we must mark it in case new pointers are added. */
483 mark_type *mark_bits;
484 } pch_zone;
486 #ifdef USING_MMAP
487 static char *alloc_anon (char *, size_t, struct alloc_zone *);
488 #endif
489 static struct small_page_entry * alloc_small_page (struct alloc_zone *);
490 static struct large_page_entry * alloc_large_page (size_t, struct alloc_zone *);
491 static void free_chunk (char *, size_t, struct alloc_zone *);
492 static void free_small_page (struct small_page_entry *);
493 static void free_large_page (struct large_page_entry *);
494 static void release_pages (struct alloc_zone *);
495 static void sweep_pages (struct alloc_zone *);
496 static bool ggc_collect_1 (struct alloc_zone *, bool);
497 static void new_ggc_zone_1 (struct alloc_zone *, const char *);
499 /* Traverse the page table and find the entry for a page.
500 Die (probably) if the object wasn't allocated via GC. */
502 static inline page_entry *
503 lookup_page_table_entry (const void *p)
505 page_entry ***base;
506 size_t L1, L2;
508 #if HOST_BITS_PER_PTR <= 32
509 base = &G.lookup[0];
510 #else
511 page_table table = G.lookup;
512 size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
513 while (table->high_bits != high_bits)
514 table = table->next;
515 base = &table->table[0];
516 #endif
518 /* Extract the level 1 and 2 indices. */
519 L1 = LOOKUP_L1 (p);
520 L2 = LOOKUP_L2 (p);
522 return base[L1][L2];
525 /* Set the page table entry for the page that starts at P. If ENTRY
526 is NULL, clear the entry. */
528 static void
529 set_page_table_entry (void *p, page_entry *entry)
531 page_entry ***base;
532 size_t L1, L2;
534 #if HOST_BITS_PER_PTR <= 32
535 base = &G.lookup[0];
536 #else
537 page_table table;
538 size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
539 for (table = G.lookup; table; table = table->next)
540 if (table->high_bits == high_bits)
541 goto found;
543 /* Not found -- allocate a new table. */
544 table = xcalloc (1, sizeof(*table));
545 table->next = G.lookup;
546 table->high_bits = high_bits;
547 G.lookup = table;
548 found:
549 base = &table->table[0];
550 #endif
552 /* Extract the level 1 and 2 indices. */
553 L1 = LOOKUP_L1 (p);
554 L2 = LOOKUP_L2 (p);
556 if (base[L1] == NULL)
557 base[L1] = xcalloc (PAGE_L2_SIZE, sizeof (page_entry *));
559 base[L1][L2] = entry;
562 /* Find the page table entry associated with OBJECT. */
564 static inline struct page_entry *
565 zone_get_object_page (const void *object)
567 return lookup_page_table_entry (object);
570 /* Find which element of the alloc_bits array OBJECT should be
571 recorded in. */
572 static inline unsigned int
573 zone_get_object_alloc_word (const void *object)
575 return (((size_t) object & (GGC_PAGE_SIZE - 1))
576 / (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
579 /* Find which bit of the appropriate word in the alloc_bits array
580 OBJECT should be recorded in. */
581 static inline unsigned int
582 zone_get_object_alloc_bit (const void *object)
584 return (((size_t) object / BYTES_PER_ALLOC_BIT)
585 % (8 * sizeof (alloc_type)));
588 /* Find which element of the mark_bits array OBJECT should be recorded
589 in. */
590 static inline unsigned int
591 zone_get_object_mark_word (const void *object)
593 return (((size_t) object & (GGC_PAGE_SIZE - 1))
594 / (8 * sizeof (mark_type) * BYTES_PER_MARK_BIT));
597 /* Find which bit of the appropriate word in the mark_bits array
598 OBJECT should be recorded in. */
599 static inline unsigned int
600 zone_get_object_mark_bit (const void *object)
602 return (((size_t) object / BYTES_PER_MARK_BIT)
603 % (8 * sizeof (mark_type)));
606 /* Set the allocation bit corresponding to OBJECT in its page's
607 bitmap. Used to split this object from the preceding one. */
608 static inline void
609 zone_set_object_alloc_bit (const void *object)
611 struct small_page_entry *page
612 = (struct small_page_entry *) zone_get_object_page (object);
613 unsigned int start_word = zone_get_object_alloc_word (object);
614 unsigned int start_bit = zone_get_object_alloc_bit (object);
616 page->alloc_bits[start_word] |= 1L << start_bit;
619 /* Clear the allocation bit corresponding to OBJECT in PAGE's
620 bitmap. Used to coalesce this object with the preceding
621 one. */
622 static inline void
623 zone_clear_object_alloc_bit (struct small_page_entry *page,
624 const void *object)
626 unsigned int start_word = zone_get_object_alloc_word (object);
627 unsigned int start_bit = zone_get_object_alloc_bit (object);
629 /* Would xor be quicker? */
630 page->alloc_bits[start_word] &= ~(1L << start_bit);
633 /* Find the size of the object which starts at START_WORD and
634 START_BIT in ALLOC_BITS, which is at most MAX_SIZE bytes.
635 Helper function for ggc_get_size and zone_find_object_size. */
637 static inline size_t
638 zone_object_size_1 (alloc_type *alloc_bits,
639 size_t start_word, size_t start_bit,
640 size_t max_size)
642 size_t size;
643 alloc_type alloc_word;
644 int indx;
646 /* Load the first word. */
647 alloc_word = alloc_bits[start_word++];
649 /* If that was the last bit in this word, we'll want to continue
650 with the next word. Otherwise, handle the rest of this word. */
651 if (start_bit)
653 indx = alloc_ffs (alloc_word >> start_bit);
654 if (indx)
655 /* indx is 1-based. We started at the bit after the object's
656 start, but we also ended at the bit after the object's end.
657 It cancels out. */
658 return indx * BYTES_PER_ALLOC_BIT;
660 /* The extra 1 accounts for the starting unit, before start_bit. */
661 size = (sizeof (alloc_type) * 8 - start_bit + 1) * BYTES_PER_ALLOC_BIT;
663 if (size >= max_size)
664 return max_size;
666 alloc_word = alloc_bits[start_word++];
668 else
669 size = BYTES_PER_ALLOC_BIT;
671 while (alloc_word == 0)
673 size += sizeof (alloc_type) * 8 * BYTES_PER_ALLOC_BIT;
674 if (size >= max_size)
675 return max_size;
676 alloc_word = alloc_bits[start_word++];
679 indx = alloc_ffs (alloc_word);
680 return size + (indx - 1) * BYTES_PER_ALLOC_BIT;
683 /* Find the size of OBJECT on small page PAGE. */
685 static inline size_t
686 zone_find_object_size (struct small_page_entry *page,
687 const void *object)
689 const char *object_midptr = (const char *) object + BYTES_PER_ALLOC_BIT;
690 unsigned int start_word = zone_get_object_alloc_word (object_midptr);
691 unsigned int start_bit = zone_get_object_alloc_bit (object_midptr);
692 size_t max_size = (page->common.page + SMALL_PAGE_SIZE
693 - (char *) object);
695 return zone_object_size_1 (page->alloc_bits, start_word, start_bit,
696 max_size);
699 /* Allocate the mark bits for every zone, and set the pointers on each
700 page. */
701 static void
702 zone_allocate_marks (void)
704 struct alloc_zone *zone;
706 for (zone = G.zones; zone; zone = zone->next_zone)
708 struct small_page_entry *page;
709 mark_type *cur_marks;
710 size_t mark_words, mark_words_per_page;
711 #ifdef ENABLE_CHECKING
712 size_t n = 0;
713 #endif
715 mark_words_per_page
716 = (GGC_PAGE_SIZE + BYTES_PER_MARK_WORD - 1) / BYTES_PER_MARK_WORD;
717 mark_words = zone->n_small_pages * mark_words_per_page;
718 zone->mark_bits = (mark_type *) xcalloc (sizeof (mark_type),
719 mark_words);
720 cur_marks = zone->mark_bits;
721 for (page = zone->pages; page; page = page->next)
723 page->mark_bits = cur_marks;
724 cur_marks += mark_words_per_page;
725 #ifdef ENABLE_CHECKING
726 n++;
727 #endif
729 #ifdef ENABLE_CHECKING
730 gcc_assert (n == zone->n_small_pages);
731 #endif
734 /* We don't collect the PCH zone, but we do have to mark it
735 (for now). */
736 if (pch_zone.bytes)
737 pch_zone.mark_bits
738 = (mark_type *) xcalloc (sizeof (mark_type),
739 CEIL (pch_zone.bytes, BYTES_PER_MARK_WORD));
742 /* After marking and sweeping, release the memory used for mark bits. */
743 static void
744 zone_free_marks (void)
746 struct alloc_zone *zone;
748 for (zone = G.zones; zone; zone = zone->next_zone)
749 if (zone->mark_bits)
751 free (zone->mark_bits);
752 zone->mark_bits = NULL;
755 if (pch_zone.bytes)
757 free (pch_zone.mark_bits);
758 pch_zone.mark_bits = NULL;
762 #ifdef USING_MMAP
763 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
764 (if non-null). The ifdef structure here is intended to cause a
765 compile error unless exactly one of the HAVE_* is defined. */
767 static inline char *
768 alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, struct alloc_zone *zone)
770 #ifdef HAVE_MMAP_ANON
771 char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
772 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
773 #endif
774 #ifdef HAVE_MMAP_DEV_ZERO
775 char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
776 MAP_PRIVATE, G.dev_zero_fd, 0);
777 #endif
779 if (page == (char *) MAP_FAILED)
781 perror ("virtual memory exhausted");
782 exit (FATAL_EXIT_CODE);
785 /* Remember that we allocated this memory. */
786 zone->bytes_mapped += size;
788 /* Pretend we don't have access to the allocated pages. We'll enable
789 access to smaller pieces of the area in ggc_alloc. Discard the
790 handle to avoid handle leak. */
791 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page, size));
793 return page;
795 #endif
797 /* Allocate a new page for allocating small objects in ZONE, and
798 return an entry for it. */
800 static struct small_page_entry *
801 alloc_small_page (struct alloc_zone *zone)
803 struct small_page_entry *entry;
805 /* Check the list of free pages for one we can use. */
806 entry = zone->free_pages;
807 if (entry != NULL)
809 /* Recycle the allocated memory from this page ... */
810 zone->free_pages = entry->next;
812 else
814 /* We want just one page. Allocate a bunch of them and put the
815 extras on the freelist. (Can only do this optimization with
816 mmap for backing store.) */
817 struct small_page_entry *e, *f = zone->free_pages;
818 int i;
819 char *page;
821 page = alloc_anon (NULL, GGC_PAGE_SIZE * G.quire_size, zone);
823 /* This loop counts down so that the chain will be in ascending
824 memory order. */
825 for (i = G.quire_size - 1; i >= 1; i--)
827 e = xcalloc (1, G.small_page_overhead);
828 e->common.page = page + (i << GGC_PAGE_SHIFT);
829 e->common.zone = zone;
830 e->next = f;
831 f = e;
832 set_page_table_entry (e->common.page, &e->common);
835 zone->free_pages = f;
837 entry = xcalloc (1, G.small_page_overhead);
838 entry->common.page = page;
839 entry->common.zone = zone;
840 set_page_table_entry (page, &entry->common);
843 zone->n_small_pages++;
845 if (GGC_DEBUG_LEVEL >= 2)
846 fprintf (G.debug_file,
847 "Allocating %s page at %p, data %p-%p\n",
848 entry->common.zone->name, (PTR) entry, entry->common.page,
849 entry->common.page + SMALL_PAGE_SIZE - 1);
851 return entry;
854 /* Allocate a large page of size SIZE in ZONE. */
856 static struct large_page_entry *
857 alloc_large_page (size_t size, struct alloc_zone *zone)
859 struct large_page_entry *entry;
860 char *page;
861 size_t needed_size;
863 needed_size = size + sizeof (struct large_page_entry);
864 page = xmalloc (needed_size);
866 entry = (struct large_page_entry *) page;
868 entry->next = NULL;
869 entry->common.page = page + sizeof (struct large_page_entry);
870 entry->common.large_p = true;
871 entry->common.pch_p = false;
872 entry->common.zone = zone;
873 #ifdef GATHER_STATISTICS
874 entry->common.survived = 0;
875 #endif
876 entry->mark_p = false;
877 entry->bytes = size;
878 entry->prev = NULL;
880 set_page_table_entry (entry->common.page, &entry->common);
882 if (GGC_DEBUG_LEVEL >= 2)
883 fprintf (G.debug_file,
884 "Allocating %s large page at %p, data %p-%p\n",
885 entry->common.zone->name, (PTR) entry, entry->common.page,
886 entry->common.page + SMALL_PAGE_SIZE - 1);
888 return entry;
892 /* For a page that is no longer needed, put it on the free page list. */
894 static inline void
895 free_small_page (struct small_page_entry *entry)
897 if (GGC_DEBUG_LEVEL >= 2)
898 fprintf (G.debug_file,
899 "Deallocating %s page at %p, data %p-%p\n",
900 entry->common.zone->name, (PTR) entry,
901 entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
903 gcc_assert (!entry->common.large_p);
905 /* Mark the page as inaccessible. Discard the handle to
906 avoid handle leak. */
907 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry->common.page,
908 SMALL_PAGE_SIZE));
910 entry->next = entry->common.zone->free_pages;
911 entry->common.zone->free_pages = entry;
912 entry->common.zone->n_small_pages--;
915 /* Release a large page that is no longer needed. */
917 static inline void
918 free_large_page (struct large_page_entry *entry)
920 if (GGC_DEBUG_LEVEL >= 2)
921 fprintf (G.debug_file,
922 "Deallocating %s page at %p, data %p-%p\n",
923 entry->common.zone->name, (PTR) entry,
924 entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
926 gcc_assert (entry->common.large_p);
928 set_page_table_entry (entry->common.page, NULL);
929 free (entry);
932 /* Release the free page cache to the system. */
934 static void
935 release_pages (struct alloc_zone *zone)
937 #ifdef USING_MMAP
938 struct small_page_entry *p, *next;
939 char *start;
940 size_t len;
942 /* Gather up adjacent pages so they are unmapped together. */
943 p = zone->free_pages;
945 while (p)
947 start = p->common.page;
948 next = p->next;
949 len = SMALL_PAGE_SIZE;
950 set_page_table_entry (p->common.page, NULL);
951 p = next;
953 while (p && p->common.page == start + len)
955 next = p->next;
956 len += SMALL_PAGE_SIZE;
957 set_page_table_entry (p->common.page, NULL);
958 p = next;
961 munmap (start, len);
962 zone->bytes_mapped -= len;
965 zone->free_pages = NULL;
966 #endif
969 /* Place the block at PTR of size SIZE on the free list for ZONE. */
971 static inline void
972 free_chunk (char *ptr, size_t size, struct alloc_zone *zone)
974 struct alloc_chunk *chunk = (struct alloc_chunk *) ptr;
975 size_t bin = 0;
977 bin = SIZE_BIN_DOWN (size);
978 gcc_assert (bin != 0);
979 if (bin > NUM_FREE_BINS)
981 bin = 0;
982 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk, sizeof (struct alloc_chunk)));
983 chunk->size = size;
984 chunk->next_free = zone->free_chunks[bin];
985 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (ptr + sizeof (struct alloc_chunk),
986 size - sizeof (struct alloc_chunk)));
988 else
990 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk, sizeof (struct alloc_chunk *)));
991 chunk->next_free = zone->free_chunks[bin];
992 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (ptr + sizeof (struct alloc_chunk *),
993 size - sizeof (struct alloc_chunk *)));
996 zone->free_chunks[bin] = chunk;
997 if (bin > zone->high_free_bin)
998 zone->high_free_bin = bin;
999 if (GGC_DEBUG_LEVEL >= 3)
1000 fprintf (G.debug_file, "Deallocating object, chunk=%p\n", (void *)chunk);
1003 /* Allocate a chunk of memory of at least ORIG_SIZE bytes, in ZONE. */
1005 void *
1006 ggc_alloc_zone_stat (size_t orig_size, struct alloc_zone *zone
1007 MEM_STAT_DECL)
1009 size_t bin;
1010 size_t csize;
1011 struct small_page_entry *entry;
1012 struct alloc_chunk *chunk, **pp;
1013 void *result;
1014 size_t size = orig_size;
1016 /* Make sure that zero-sized allocations get a unique and freeable
1017 pointer. */
1018 if (size == 0)
1019 size = MAX_ALIGNMENT;
1020 else
1021 size = (size + MAX_ALIGNMENT - 1) & -MAX_ALIGNMENT;
1023 /* Try to allocate the object from several different sources. Each
1024 of these cases is responsible for setting RESULT and SIZE to
1025 describe the allocated block, before jumping to FOUND. If a
1026 chunk is split, the allocate bit for the new chunk should also be
1027 set.
1029 Large objects are handled specially. However, they'll just fail
1030 the next couple of conditions, so we can wait to check for them
1031 below. The large object case is relatively rare (< 1%), so this
1032 is a win. */
1034 /* First try to split the last chunk we allocated. For best
1035 fragmentation behavior it would be better to look for a
1036 free bin of the appropriate size for a small object. However,
1037 we're unlikely (1% - 7%) to find one, and this gives better
1038 locality behavior anyway. This case handles the lion's share
1039 of all calls to this function. */
1040 if (size <= zone->cached_free_size)
1042 result = zone->cached_free;
1044 zone->cached_free_size -= size;
1045 if (zone->cached_free_size)
1047 zone->cached_free += size;
1048 zone_set_object_alloc_bit (zone->cached_free);
1051 goto found;
1054 /* Next, try to find a free bin of the exactly correct size. */
1056 /* We want to round SIZE up, rather than down, but we know it's
1057 already aligned to at least FREE_BIN_DELTA, so we can just
1058 shift. */
1059 bin = SIZE_BIN_DOWN (size);
1061 if (bin <= NUM_FREE_BINS
1062 && (chunk = zone->free_chunks[bin]) != NULL)
1064 /* We have a chunk of the right size. Pull it off the free list
1065 and use it. */
1067 zone->free_chunks[bin] = chunk->next_free;
1069 /* NOTE: SIZE is only guaranteed to be right if MAX_ALIGNMENT
1070 == FREE_BIN_DELTA. */
1071 result = chunk;
1073 /* The allocation bits are already set correctly. HIGH_FREE_BIN
1074 may now be wrong, if this was the last chunk in the high bin.
1075 Rather than fixing it up now, wait until we need to search
1076 the free bins. */
1078 goto found;
1081 /* Next, if there wasn't a chunk of the ideal size, look for a chunk
1082 to split. We can find one in the too-big bin, or in the largest
1083 sized bin with a chunk in it. Try the largest normal-sized bin
1084 first. */
1086 if (zone->high_free_bin > bin)
1088 /* Find the highest numbered free bin. It will be at or below
1089 the watermark. */
1090 while (zone->high_free_bin > bin
1091 && zone->free_chunks[zone->high_free_bin] == NULL)
1092 zone->high_free_bin--;
1094 if (zone->high_free_bin > bin)
1096 size_t tbin = zone->high_free_bin;
1097 chunk = zone->free_chunks[tbin];
1099 /* Remove the chunk from its previous bin. */
1100 zone->free_chunks[tbin] = chunk->next_free;
1102 result = (char *) chunk;
1104 /* Save the rest of the chunk for future allocation. */
1105 if (zone->cached_free_size)
1106 free_chunk (zone->cached_free, zone->cached_free_size, zone);
1108 chunk = (struct alloc_chunk *) ((char *) result + size);
1109 zone->cached_free = (char *) chunk;
1110 zone->cached_free_size = (tbin - bin) * FREE_BIN_DELTA;
1112 /* Mark the new free chunk as an object, so that we can
1113 find the size of the newly allocated object. */
1114 zone_set_object_alloc_bit (chunk);
1116 /* HIGH_FREE_BIN may now be wrong, if this was the last
1117 chunk in the high bin. Rather than fixing it up now,
1118 wait until we need to search the free bins. */
1120 goto found;
1124 /* Failing that, look through the "other" bucket for a chunk
1125 that is large enough. */
1126 pp = &(zone->free_chunks[0]);
1127 chunk = *pp;
1128 while (chunk && chunk->size < size)
1130 pp = &chunk->next_free;
1131 chunk = *pp;
1134 if (chunk)
1136 /* Remove the chunk from its previous bin. */
1137 *pp = chunk->next_free;
1139 result = (char *) chunk;
1141 /* Save the rest of the chunk for future allocation, if there's any
1142 left over. */
1143 csize = chunk->size;
1144 if (csize > size)
1146 if (zone->cached_free_size)
1147 free_chunk (zone->cached_free, zone->cached_free_size, zone);
1149 chunk = (struct alloc_chunk *) ((char *) result + size);
1150 zone->cached_free = (char *) chunk;
1151 zone->cached_free_size = csize - size;
1153 /* Mark the new free chunk as an object. */
1154 zone_set_object_alloc_bit (chunk);
1157 goto found;
1160 /* Handle large allocations. We could choose any threshold between
1161 GGC_PAGE_SIZE - sizeof (struct large_page_entry) and
1162 GGC_PAGE_SIZE. It can't be smaller, because then it wouldn't
1163 be guaranteed to have a unique entry in the lookup table. Large
1164 allocations will always fall through to here. */
1165 if (size > GGC_PAGE_SIZE)
1167 struct large_page_entry *entry = alloc_large_page (size, zone);
1169 #ifdef GATHER_STATISTICS
1170 entry->common.survived = 0;
1171 #endif
1173 entry->next = zone->large_pages;
1174 if (zone->large_pages)
1175 zone->large_pages->prev = entry;
1176 zone->large_pages = entry;
1178 result = entry->common.page;
1180 goto found;
1183 /* Failing everything above, allocate a new small page. */
1185 entry = alloc_small_page (zone);
1186 entry->next = zone->pages;
1187 zone->pages = entry;
1189 /* Mark the first chunk in the new page. */
1190 entry->alloc_bits[0] = 1;
1192 result = entry->common.page;
1193 if (size < SMALL_PAGE_SIZE)
1195 if (zone->cached_free_size)
1196 free_chunk (zone->cached_free, zone->cached_free_size, zone);
1198 zone->cached_free = (char *) result + size;
1199 zone->cached_free_size = SMALL_PAGE_SIZE - size;
1201 /* Mark the new free chunk as an object. */
1202 zone_set_object_alloc_bit (zone->cached_free);
1205 found:
1207 /* We could save TYPE in the chunk, but we don't use that for
1208 anything yet. If we wanted to, we could do it by adding it
1209 either before the beginning of the chunk or after its end,
1210 and adjusting the size and pointer appropriately. */
1212 /* We'll probably write to this after we return. */
1213 prefetchw (result);
1215 #ifdef ENABLE_GC_CHECKING
1216 /* `Poison' the entire allocated object. */
1217 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, size));
1218 memset (result, 0xaf, size);
1219 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (result + orig_size,
1220 size - orig_size));
1221 #endif
1223 /* Tell Valgrind that the memory is there, but its content isn't
1224 defined. The bytes at the end of the object are still marked
1225 unaccessible. */
1226 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result, orig_size));
1228 /* Keep track of how many bytes are being allocated. This
1229 information is used in deciding when to collect. */
1230 zone->allocated += size;
1232 timevar_ggc_mem_total += size;
1234 #ifdef GATHER_STATISTICS
1235 ggc_record_overhead (orig_size, size - orig_size, result PASS_MEM_STAT);
1238 size_t object_size = size;
1239 size_t overhead = object_size - orig_size;
1241 zone->stats.total_overhead += overhead;
1242 zone->stats.total_allocated += object_size;
1244 if (orig_size <= 32)
1246 zone->stats.total_overhead_under32 += overhead;
1247 zone->stats.total_allocated_under32 += object_size;
1249 if (orig_size <= 64)
1251 zone->stats.total_overhead_under64 += overhead;
1252 zone->stats.total_allocated_under64 += object_size;
1254 if (orig_size <= 128)
1256 zone->stats.total_overhead_under128 += overhead;
1257 zone->stats.total_allocated_under128 += object_size;
1260 #endif
1262 if (GGC_DEBUG_LEVEL >= 3)
1263 fprintf (G.debug_file, "Allocating object, size=%lu at %p\n",
1264 (unsigned long) size, result);
1266 return result;
1269 /* Allocate a SIZE of chunk memory of GTE type, into an appropriate zone
1270 for that type. */
1272 void *
1273 ggc_alloc_typed_stat (enum gt_types_enum gte, size_t size
1274 MEM_STAT_DECL)
1276 switch (gte)
1278 case gt_ggc_e_14lang_tree_node:
1279 return ggc_alloc_zone_pass_stat (size, &tree_zone);
1281 case gt_ggc_e_7rtx_def:
1282 return ggc_alloc_zone_pass_stat (size, &rtl_zone);
1284 case gt_ggc_e_9rtvec_def:
1285 return ggc_alloc_zone_pass_stat (size, &rtl_zone);
1287 default:
1288 return ggc_alloc_zone_pass_stat (size, &main_zone);
1292 /* Normal ggc_alloc simply allocates into the main zone. */
1294 void *
1295 ggc_alloc_stat (size_t size MEM_STAT_DECL)
1297 return ggc_alloc_zone_pass_stat (size, &main_zone);
1300 /* Poison the chunk. */
1301 #ifdef ENABLE_GC_CHECKING
1302 #define poison_region(PTR, SIZE) \
1303 memset ((PTR), 0xa5, (SIZE))
1304 #else
1305 #define poison_region(PTR, SIZE)
1306 #endif
1308 /* Free the object at P. */
1310 void
1311 ggc_free (void *p)
1313 struct page_entry *page;
1315 #ifdef GATHER_STATISTICS
1316 ggc_free_overhead (p);
1317 #endif
1319 poison_region (p, ggc_get_size (p));
1321 page = zone_get_object_page (p);
1323 if (page->large_p)
1325 struct large_page_entry *large_page
1326 = (struct large_page_entry *) page;
1328 /* Remove the page from the linked list. */
1329 if (large_page->prev)
1330 large_page->prev->next = large_page->next;
1331 else
1333 gcc_assert (large_page->common.zone->large_pages == large_page);
1334 large_page->common.zone->large_pages = large_page->next;
1336 if (large_page->next)
1337 large_page->next->prev = large_page->prev;
1339 large_page->common.zone->allocated -= large_page->bytes;
1341 /* Release the memory associated with this object. */
1342 free_large_page (large_page);
1344 else if (page->pch_p)
1345 /* Don't do anything. We won't allocate a new object from the
1346 PCH zone so there's no point in releasing anything. */
1348 else
1350 size_t size = ggc_get_size (p);
1352 page->zone->allocated -= size;
1354 /* Add the chunk to the free list. We don't bother with coalescing,
1355 since we are likely to want a chunk of this size again. */
1356 free_chunk (p, size, page->zone);
1360 /* If P is not marked, mark it and return false. Otherwise return true.
1361 P must have been allocated by the GC allocator; it mustn't point to
1362 static objects, stack variables, or memory allocated with malloc. */
1365 ggc_set_mark (const void *p)
1367 struct page_entry *page;
1368 const char *ptr = (const char *) p;
1370 page = zone_get_object_page (p);
1372 if (page->pch_p)
1374 size_t mark_word, mark_bit, offset;
1375 offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
1376 mark_word = offset / (8 * sizeof (mark_type));
1377 mark_bit = offset % (8 * sizeof (mark_type));
1379 if (pch_zone.mark_bits[mark_word] & (1 << mark_bit))
1380 return 1;
1381 pch_zone.mark_bits[mark_word] |= (1 << mark_bit);
1383 else if (page->large_p)
1385 struct large_page_entry *large_page
1386 = (struct large_page_entry *) page;
1388 if (large_page->mark_p)
1389 return 1;
1390 large_page->mark_p = true;
1392 else
1394 struct small_page_entry *small_page
1395 = (struct small_page_entry *) page;
1397 if (small_page->mark_bits[zone_get_object_mark_word (p)]
1398 & (1 << zone_get_object_mark_bit (p)))
1399 return 1;
1400 small_page->mark_bits[zone_get_object_mark_word (p)]
1401 |= (1 << zone_get_object_mark_bit (p));
1404 if (GGC_DEBUG_LEVEL >= 4)
1405 fprintf (G.debug_file, "Marking %p\n", p);
1407 return 0;
1410 /* Return 1 if P has been marked, zero otherwise.
1411 P must have been allocated by the GC allocator; it mustn't point to
1412 static objects, stack variables, or memory allocated with malloc. */
1415 ggc_marked_p (const void *p)
1417 struct page_entry *page;
1418 const char *ptr = p;
1420 page = zone_get_object_page (p);
1422 if (page->pch_p)
1424 size_t mark_word, mark_bit, offset;
1425 offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
1426 mark_word = offset / (8 * sizeof (mark_type));
1427 mark_bit = offset % (8 * sizeof (mark_type));
1429 return (pch_zone.mark_bits[mark_word] & (1 << mark_bit)) != 0;
1432 if (page->large_p)
1434 struct large_page_entry *large_page
1435 = (struct large_page_entry *) page;
1437 return large_page->mark_p;
1439 else
1441 struct small_page_entry *small_page
1442 = (struct small_page_entry *) page;
1444 return 0 != (small_page->mark_bits[zone_get_object_mark_word (p)]
1445 & (1 << zone_get_object_mark_bit (p)));
1449 /* Return the size of the gc-able object P. */
1451 size_t
1452 ggc_get_size (const void *p)
1454 struct page_entry *page;
1455 const char *ptr = (const char *) p;
1457 page = zone_get_object_page (p);
1459 if (page->pch_p)
1461 size_t alloc_word, alloc_bit, offset, max_size;
1462 offset = (ptr - pch_zone.page) / BYTES_PER_ALLOC_BIT + 1;
1463 alloc_word = offset / (8 * sizeof (alloc_type));
1464 alloc_bit = offset % (8 * sizeof (alloc_type));
1465 max_size = pch_zone.bytes - (ptr - pch_zone.page);
1466 return zone_object_size_1 (pch_zone.alloc_bits, alloc_word, alloc_bit,
1467 max_size);
1470 if (page->large_p)
1471 return ((struct large_page_entry *)page)->bytes;
1472 else
1473 return zone_find_object_size ((struct small_page_entry *) page, p);
1476 /* Initialize the ggc-zone-mmap allocator. */
1477 void
1478 init_ggc (void)
1480 /* The allocation size must be greater than BYTES_PER_MARK_BIT, and
1481 a multiple of both BYTES_PER_ALLOC_BIT and FREE_BIN_DELTA, for
1482 the current assumptions to hold. */
1484 gcc_assert (FREE_BIN_DELTA == MAX_ALIGNMENT);
1486 /* Set up the main zone by hand. */
1487 main_zone.name = "Main zone";
1488 G.zones = &main_zone;
1490 /* Allocate the default zones. */
1491 new_ggc_zone_1 (&rtl_zone, "RTL zone");
1492 new_ggc_zone_1 (&tree_zone, "Tree zone");
1493 new_ggc_zone_1 (&tree_id_zone, "Tree identifier zone");
1495 G.pagesize = getpagesize();
1496 G.lg_pagesize = exact_log2 (G.pagesize);
1497 G.page_mask = ~(G.pagesize - 1);
1499 /* Require the system page size to be a multiple of GGC_PAGE_SIZE. */
1500 gcc_assert ((G.pagesize & (GGC_PAGE_SIZE - 1)) == 0);
1502 /* Allocate 16 system pages at a time. */
1503 G.quire_size = 16 * G.pagesize / GGC_PAGE_SIZE;
1505 /* Calculate the size of the allocation bitmap and other overhead. */
1506 /* Right now we allocate bits for the page header and bitmap. These
1507 are wasted, but a little tricky to eliminate. */
1508 G.small_page_overhead
1509 = PAGE_OVERHEAD + (GGC_PAGE_SIZE / BYTES_PER_ALLOC_BIT / 8);
1510 /* G.small_page_overhead = ROUND_UP (G.small_page_overhead, MAX_ALIGNMENT); */
1512 #ifdef HAVE_MMAP_DEV_ZERO
1513 G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
1514 gcc_assert (G.dev_zero_fd != -1);
1515 #endif
1517 #if 0
1518 G.debug_file = fopen ("ggc-mmap.debug", "w");
1519 setlinebuf (G.debug_file);
1520 #else
1521 G.debug_file = stdout;
1522 #endif
1524 #ifdef USING_MMAP
1525 /* StunOS has an amazing off-by-one error for the first mmap allocation
1526 after fiddling with RLIMIT_STACK. The result, as hard as it is to
1527 believe, is an unaligned page allocation, which would cause us to
1528 hork badly if we tried to use it. */
1530 char *p = alloc_anon (NULL, G.pagesize, &main_zone);
1531 struct small_page_entry *e;
1532 if ((size_t)p & (G.pagesize - 1))
1534 /* How losing. Discard this one and try another. If we still
1535 can't get something useful, give up. */
1537 p = alloc_anon (NULL, G.pagesize, &main_zone);
1538 gcc_assert (!((size_t)p & (G.pagesize - 1)));
1541 if (GGC_PAGE_SIZE == G.pagesize)
1543 /* We have a good page, might as well hold onto it... */
1544 e = xcalloc (1, G.small_page_overhead);
1545 e->common.page = p;
1546 e->common.zone = &main_zone;
1547 e->next = main_zone.free_pages;
1548 set_page_table_entry (e->common.page, &e->common);
1549 main_zone.free_pages = e;
1551 else
1553 munmap (p, G.pagesize);
1556 #endif
1559 /* Start a new GGC zone. */
1561 static void
1562 new_ggc_zone_1 (struct alloc_zone *new_zone, const char * name)
1564 new_zone->name = name;
1565 new_zone->next_zone = G.zones->next_zone;
1566 G.zones->next_zone = new_zone;
1569 struct alloc_zone *
1570 new_ggc_zone (const char * name)
1572 struct alloc_zone *new_zone = xcalloc (1, sizeof (struct alloc_zone));
1573 new_ggc_zone_1 (new_zone, name);
1574 return new_zone;
1577 /* Destroy a GGC zone. */
1578 void
1579 destroy_ggc_zone (struct alloc_zone * dead_zone)
1581 struct alloc_zone *z;
1583 for (z = G.zones; z && z->next_zone != dead_zone; z = z->next_zone)
1584 /* Just find that zone. */
1585 continue;
1587 /* We should have found the zone in the list. Anything else is fatal. */
1588 gcc_assert (z);
1590 /* z is dead, baby. z is dead. */
1591 z->dead = true;
1594 /* Free all empty pages and objects within a page for a given zone */
1596 static void
1597 sweep_pages (struct alloc_zone *zone)
1599 struct large_page_entry **lpp, *lp, *lnext;
1600 struct small_page_entry **spp, *sp, *snext;
1601 char *last_free;
1602 size_t allocated = 0;
1603 bool nomarksinpage;
1605 /* First, reset the free_chunks lists, since we are going to
1606 re-free free chunks in hopes of coalescing them into large chunks. */
1607 memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
1608 zone->high_free_bin = 0;
1609 zone->cached_free = NULL;
1610 zone->cached_free_size = 0;
1612 /* Large pages are all or none affairs. Either they are completely
1613 empty, or they are completely full. */
1614 lpp = &zone->large_pages;
1615 for (lp = zone->large_pages; lp != NULL; lp = lnext)
1617 gcc_assert (lp->common.large_p);
1619 lnext = lp->next;
1621 #ifdef GATHER_STATISTICS
1622 /* This page has now survived another collection. */
1623 lp->common.survived++;
1624 #endif
1626 if (lp->mark_p)
1628 lp->mark_p = false;
1629 allocated += lp->bytes;
1630 lpp = &lp->next;
1632 else
1634 *lpp = lnext;
1635 #ifdef ENABLE_GC_CHECKING
1636 /* Poison the page. */
1637 memset (lp->common.page, 0xb5, SMALL_PAGE_SIZE);
1638 #endif
1639 if (lp->prev)
1640 lp->prev->next = lp->next;
1641 if (lp->next)
1642 lp->next->prev = lp->prev;
1643 free_large_page (lp);
1647 spp = &zone->pages;
1648 for (sp = zone->pages; sp != NULL; sp = snext)
1650 char *object, *last_object;
1651 char *end;
1652 alloc_type *alloc_word_p;
1653 mark_type *mark_word_p;
1655 gcc_assert (!sp->common.large_p);
1657 snext = sp->next;
1659 #ifdef GATHER_STATISTICS
1660 /* This page has now survived another collection. */
1661 sp->common.survived++;
1662 #endif
1664 /* Step through all chunks, consolidate those that are free and
1665 insert them into the free lists. Note that consolidation
1666 slows down collection slightly. */
1668 last_object = object = sp->common.page;
1669 end = sp->common.page + SMALL_PAGE_SIZE;
1670 last_free = NULL;
1671 nomarksinpage = true;
1672 mark_word_p = sp->mark_bits;
1673 alloc_word_p = sp->alloc_bits;
1675 gcc_assert (BYTES_PER_ALLOC_BIT == BYTES_PER_MARK_BIT);
1677 object = sp->common.page;
1680 unsigned int i, n;
1681 alloc_type alloc_word;
1682 mark_type mark_word;
1684 alloc_word = *alloc_word_p++;
1685 mark_word = *mark_word_p++;
1687 if (mark_word)
1688 nomarksinpage = false;
1690 /* There ought to be some way to do this without looping... */
1691 i = 0;
1692 while ((n = alloc_ffs (alloc_word)) != 0)
1694 /* Extend the current state for n - 1 bits. We can't
1695 shift alloc_word by n, even though it isn't used in the
1696 loop, in case only the highest bit was set. */
1697 alloc_word >>= n - 1;
1698 mark_word >>= n - 1;
1699 object += BYTES_PER_MARK_BIT * (n - 1);
1701 if (mark_word & 1)
1703 if (last_free)
1705 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (last_free,
1706 object
1707 - last_free));
1708 poison_region (last_free, object - last_free);
1709 free_chunk (last_free, object - last_free, zone);
1710 last_free = NULL;
1712 else
1713 allocated += object - last_object;
1714 last_object = object;
1716 else
1718 if (last_free == NULL)
1720 last_free = object;
1721 allocated += object - last_object;
1723 else
1724 zone_clear_object_alloc_bit (sp, object);
1727 /* Shift to just after the alloc bit we handled. */
1728 alloc_word >>= 1;
1729 mark_word >>= 1;
1730 object += BYTES_PER_MARK_BIT;
1732 i += n;
1735 object += BYTES_PER_MARK_BIT * (8 * sizeof (alloc_type) - i);
1737 while (object < end);
1739 if (nomarksinpage)
1741 *spp = snext;
1742 #ifdef ENABLE_GC_CHECKING
1743 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (sp->common.page, SMALL_PAGE_SIZE));
1744 /* Poison the page. */
1745 memset (sp->common.page, 0xb5, SMALL_PAGE_SIZE);
1746 #endif
1747 free_small_page (sp);
1748 continue;
1750 else if (last_free)
1752 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (last_free,
1753 object - last_free));
1754 poison_region (last_free, object - last_free);
1755 free_chunk (last_free, object - last_free, zone);
1757 else
1758 allocated += object - last_object;
1760 spp = &sp->next;
1763 zone->allocated = allocated;
1766 /* mark-and-sweep routine for collecting a single zone. NEED_MARKING
1767 is true if we need to mark before sweeping, false if some other
1768 zone collection has already performed marking for us. Returns true
1769 if we collected, false otherwise. */
1771 static bool
1772 ggc_collect_1 (struct alloc_zone *zone, bool need_marking)
1774 #if 0
1775 /* */
1777 int i;
1778 for (i = 0; i < NUM_FREE_BINS + 1; i++)
1780 struct alloc_chunk *chunk;
1781 int n, tot;
1783 n = 0;
1784 tot = 0;
1785 chunk = zone->free_chunks[i];
1786 while (chunk)
1788 n++;
1789 tot += chunk->size;
1790 chunk = chunk->next_free;
1792 fprintf (stderr, "Bin %d: %d free chunks (%d bytes)\n",
1793 i, n, tot);
1796 /* */
1797 #endif
1799 if (!quiet_flag)
1800 fprintf (stderr, " {%s GC %luk -> ",
1801 zone->name, (unsigned long) zone->allocated / 1024);
1803 /* Zero the total allocated bytes. This will be recalculated in the
1804 sweep phase. */
1805 zone->allocated = 0;
1807 /* Release the pages we freed the last time we collected, but didn't
1808 reuse in the interim. */
1809 release_pages (zone);
1811 if (need_marking)
1813 zone_allocate_marks ();
1814 ggc_mark_roots ();
1815 #ifdef GATHER_STATISTICS
1816 ggc_prune_overhead_list ();
1817 #endif
1820 sweep_pages (zone);
1821 zone->was_collected = true;
1822 zone->allocated_last_gc = zone->allocated;
1824 if (!quiet_flag)
1825 fprintf (stderr, "%luk}", (unsigned long) zone->allocated / 1024);
1826 return true;
1829 #ifdef GATHER_STATISTICS
1830 /* Calculate the average page survival rate in terms of number of
1831 collections. */
1833 static float
1834 calculate_average_page_survival (struct alloc_zone *zone)
1836 float count = 0.0;
1837 float survival = 0.0;
1838 struct small_page_entry *p;
1839 struct large_page_entry *lp;
1840 for (p = zone->pages; p; p = p->next)
1842 count += 1.0;
1843 survival += p->common.survived;
1845 for (lp = zone->large_pages; lp; lp = lp->next)
1847 count += 1.0;
1848 survival += lp->common.survived;
1850 return survival/count;
1852 #endif
1854 /* Top level collection routine. */
1856 void
1857 ggc_collect (void)
1859 struct alloc_zone *zone;
1860 bool marked = false;
1862 timevar_push (TV_GC);
1864 if (!ggc_force_collect)
1866 float allocated_last_gc = 0, allocated = 0, min_expand;
1868 for (zone = G.zones; zone; zone = zone->next_zone)
1870 allocated_last_gc += zone->allocated_last_gc;
1871 allocated += zone->allocated;
1874 allocated_last_gc =
1875 MAX (allocated_last_gc,
1876 (size_t) PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
1877 min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
1879 if (allocated < allocated_last_gc + min_expand)
1881 timevar_pop (TV_GC);
1882 return;
1886 /* Start by possibly collecting the main zone. */
1887 main_zone.was_collected = false;
1888 marked |= ggc_collect_1 (&main_zone, true);
1890 /* In order to keep the number of collections down, we don't
1891 collect other zones unless we are collecting the main zone. This
1892 gives us roughly the same number of collections as we used to
1893 have with the old gc. The number of collection is important
1894 because our main slowdown (according to profiling) is now in
1895 marking. So if we mark twice as often as we used to, we'll be
1896 twice as slow. Hopefully we'll avoid this cost when we mark
1897 zone-at-a-time. */
1898 /* NOTE drow/2004-07-28: We now always collect the main zone, but
1899 keep this code in case the heuristics are further refined. */
1901 if (main_zone.was_collected)
1903 struct alloc_zone *zone;
1905 for (zone = main_zone.next_zone; zone; zone = zone->next_zone)
1907 zone->was_collected = false;
1908 marked |= ggc_collect_1 (zone, !marked);
1912 #ifdef GATHER_STATISTICS
1913 /* Print page survival stats, if someone wants them. */
1914 if (GGC_DEBUG_LEVEL >= 2)
1916 for (zone = G.zones; zone; zone = zone->next_zone)
1918 if (zone->was_collected)
1920 float f = calculate_average_page_survival (zone);
1921 printf ("Average page survival in zone `%s' is %f\n",
1922 zone->name, f);
1926 #endif
1928 if (marked)
1929 zone_free_marks ();
1931 /* Free dead zones. */
1932 for (zone = G.zones; zone && zone->next_zone; zone = zone->next_zone)
1934 if (zone->next_zone->dead)
1936 struct alloc_zone *dead_zone = zone->next_zone;
1938 printf ("Zone `%s' is dead and will be freed.\n", dead_zone->name);
1940 /* The zone must be empty. */
1941 gcc_assert (!dead_zone->allocated);
1943 /* Unchain the dead zone, release all its pages and free it. */
1944 zone->next_zone = zone->next_zone->next_zone;
1945 release_pages (dead_zone);
1946 free (dead_zone);
1950 timevar_pop (TV_GC);
1953 /* Print allocation statistics. */
1954 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
1955 ? (x) \
1956 : ((x) < 1024*1024*10 \
1957 ? (x) / 1024 \
1958 : (x) / (1024*1024))))
1959 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
1961 void
1962 ggc_print_statistics (void)
1964 struct alloc_zone *zone;
1965 struct ggc_statistics stats;
1966 size_t total_overhead = 0, total_allocated = 0, total_bytes_mapped = 0;
1967 size_t pte_overhead, i;
1969 /* Clear the statistics. */
1970 memset (&stats, 0, sizeof (stats));
1972 /* Make sure collection will really occur. */
1973 ggc_force_collect = true;
1975 /* Collect and print the statistics common across collectors. */
1976 ggc_print_common_statistics (stderr, &stats);
1978 ggc_force_collect = false;
1980 /* Release free pages so that we will not count the bytes allocated
1981 there as part of the total allocated memory. */
1982 for (zone = G.zones; zone; zone = zone->next_zone)
1983 release_pages (zone);
1985 /* Collect some information about the various sizes of
1986 allocation. */
1987 fprintf (stderr,
1988 "Memory still allocated at the end of the compilation process\n");
1990 fprintf (stderr, "%20s %10s %10s %10s\n",
1991 "Zone", "Allocated", "Used", "Overhead");
1992 for (zone = G.zones; zone; zone = zone->next_zone)
1994 struct large_page_entry *large_page;
1995 size_t overhead, allocated, in_use;
1997 /* Skip empty zones. */
1998 if (!zone->pages && !zone->large_pages)
1999 continue;
2001 allocated = in_use = 0;
2003 overhead = sizeof (struct alloc_zone);
2005 for (large_page = zone->large_pages; large_page != NULL;
2006 large_page = large_page->next)
2008 allocated += large_page->bytes;
2009 in_use += large_page->bytes;
2010 overhead += sizeof (struct large_page_entry);
2013 /* There's no easy way to walk through the small pages finding
2014 used and unused objects. Instead, add all the pages, and
2015 subtract out the free list. */
2017 allocated += GGC_PAGE_SIZE * zone->n_small_pages;
2018 in_use += GGC_PAGE_SIZE * zone->n_small_pages;
2019 overhead += G.small_page_overhead * zone->n_small_pages;
2021 for (i = 0; i <= NUM_FREE_BINS; i++)
2023 struct alloc_chunk *chunk = zone->free_chunks[i];
2024 while (chunk)
2026 in_use -= ggc_get_size (chunk);
2027 chunk = chunk->next_free;
2031 fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n",
2032 zone->name,
2033 SCALE (allocated), LABEL (allocated),
2034 SCALE (in_use), LABEL (in_use),
2035 SCALE (overhead), LABEL (overhead));
2037 gcc_assert (in_use == zone->allocated);
2039 total_overhead += overhead;
2040 total_allocated += zone->allocated;
2041 total_bytes_mapped += zone->bytes_mapped;
2044 /* Count the size of the page table as best we can. */
2045 #if HOST_BITS_PER_PTR <= 32
2046 pte_overhead = sizeof (G.lookup);
2047 for (i = 0; i < PAGE_L1_SIZE; i++)
2048 if (G.lookup[i])
2049 pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
2050 #else
2052 page_table table = G.lookup;
2053 pte_overhead = 0;
2054 while (table)
2056 pte_overhead += sizeof (*table);
2057 for (i = 0; i < PAGE_L1_SIZE; i++)
2058 if (table->table[i])
2059 pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
2060 table = table->next;
2063 #endif
2064 fprintf (stderr, "%20s %11s %11s %10lu%c\n", "Page Table",
2065 "", "", SCALE (pte_overhead), LABEL (pte_overhead));
2066 total_overhead += pte_overhead;
2068 fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n", "Total",
2069 SCALE (total_bytes_mapped), LABEL (total_bytes_mapped),
2070 SCALE (total_allocated), LABEL(total_allocated),
2071 SCALE (total_overhead), LABEL (total_overhead));
2073 #ifdef GATHER_STATISTICS
2075 unsigned long long all_overhead = 0, all_allocated = 0;
2076 unsigned long long all_overhead_under32 = 0, all_allocated_under32 = 0;
2077 unsigned long long all_overhead_under64 = 0, all_allocated_under64 = 0;
2078 unsigned long long all_overhead_under128 = 0, all_allocated_under128 = 0;
2080 fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
2082 for (zone = G.zones; zone; zone = zone->next_zone)
2084 all_overhead += zone->stats.total_overhead;
2085 all_allocated += zone->stats.total_allocated;
2087 all_allocated_under32 += zone->stats.total_allocated_under32;
2088 all_overhead_under32 += zone->stats.total_overhead_under32;
2090 all_allocated_under64 += zone->stats.total_allocated_under64;
2091 all_overhead_under64 += zone->stats.total_overhead_under64;
2093 all_allocated_under128 += zone->stats.total_allocated_under128;
2094 all_overhead_under128 += zone->stats.total_overhead_under128;
2096 fprintf (stderr, "%20s: %10lld\n",
2097 zone->name, zone->stats.total_allocated);
2100 fprintf (stderr, "\n");
2102 fprintf (stderr, "Total Overhead: %10lld\n",
2103 all_overhead);
2104 fprintf (stderr, "Total Allocated: %10lld\n",
2105 all_allocated);
2107 fprintf (stderr, "Total Overhead under 32B: %10lld\n",
2108 all_overhead_under32);
2109 fprintf (stderr, "Total Allocated under 32B: %10lld\n",
2110 all_allocated_under32);
2111 fprintf (stderr, "Total Overhead under 64B: %10lld\n",
2112 all_overhead_under64);
2113 fprintf (stderr, "Total Allocated under 64B: %10lld\n",
2114 all_allocated_under64);
2115 fprintf (stderr, "Total Overhead under 128B: %10lld\n",
2116 all_overhead_under128);
2117 fprintf (stderr, "Total Allocated under 128B: %10lld\n",
2118 all_allocated_under128);
2120 #endif
2123 /* Precompiled header support. */
2125 /* For precompiled headers, we sort objects based on their type. We
2126 also sort various objects into their own buckets; currently this
2127 covers strings and IDENTIFIER_NODE trees. The choices of how
2128 to sort buckets have not yet been tuned. */
2130 #define NUM_PCH_BUCKETS (gt_types_enum_last + 3)
2132 #define OTHER_BUCKET (gt_types_enum_last + 0)
2133 #define IDENTIFIER_BUCKET (gt_types_enum_last + 1)
2134 #define STRING_BUCKET (gt_types_enum_last + 2)
2136 struct ggc_pch_ondisk
2138 size_t total;
2139 size_t type_totals[NUM_PCH_BUCKETS];
2142 struct ggc_pch_data
2144 struct ggc_pch_ondisk d;
2145 size_t base;
2146 size_t orig_base;
2147 size_t alloc_size;
2148 alloc_type *alloc_bits;
2149 size_t type_bases[NUM_PCH_BUCKETS];
2150 size_t start_offset;
2153 /* Initialize the PCH data structure. */
2155 struct ggc_pch_data *
2156 init_ggc_pch (void)
2158 return xcalloc (sizeof (struct ggc_pch_data), 1);
2161 /* Return which of the page-aligned buckets the object at X, with type
2162 TYPE, should be sorted into in the PCH. Strings will have
2163 IS_STRING set and TYPE will be gt_types_enum_last. Other objects
2164 of unknown type will also have TYPE equal to gt_types_enum_last. */
2166 static int
2167 pch_bucket (void *x, enum gt_types_enum type,
2168 bool is_string)
2170 /* Sort identifiers into their own bucket, to improve locality
2171 when searching the identifier hash table. */
2172 if (type == gt_ggc_e_14lang_tree_node
2173 && TREE_CODE ((tree) x) == IDENTIFIER_NODE)
2174 return IDENTIFIER_BUCKET;
2175 else if (type == gt_types_enum_last)
2177 if (is_string)
2178 return STRING_BUCKET;
2179 return OTHER_BUCKET;
2181 return type;
2184 /* Add the size of object X to the size of the PCH data. */
2186 void
2187 ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2188 size_t size, bool is_string, enum gt_types_enum type)
2190 /* NOTE: Right now we don't need to align up the size of any objects.
2191 Strings can be unaligned, and everything else is allocated to a
2192 MAX_ALIGNMENT boundary already. */
2194 d->d.type_totals[pch_bucket (x, type, is_string)] += size;
2197 /* Return the total size of the PCH data. */
2199 size_t
2200 ggc_pch_total_size (struct ggc_pch_data *d)
2202 enum gt_types_enum i;
2203 size_t alloc_size, total_size;
2205 total_size = 0;
2206 for (i = 0; i < NUM_PCH_BUCKETS; i++)
2208 d->d.type_totals[i] = ROUND_UP (d->d.type_totals[i], GGC_PAGE_SIZE);
2209 total_size += d->d.type_totals[i];
2211 d->d.total = total_size;
2213 /* Include the size of the allocation bitmap. */
2214 alloc_size = CEIL (d->d.total, BYTES_PER_ALLOC_BIT * 8);
2215 alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
2216 d->alloc_size = alloc_size;
2218 return d->d.total + alloc_size;
2221 /* Set the base address for the objects in the PCH file. */
2223 void
2224 ggc_pch_this_base (struct ggc_pch_data *d, void *base_)
2226 int i;
2227 size_t base = (size_t) base_;
2229 d->base = d->orig_base = base;
2230 for (i = 0; i < NUM_PCH_BUCKETS; i++)
2232 d->type_bases[i] = base;
2233 base += d->d.type_totals[i];
2236 if (d->alloc_bits == NULL)
2237 d->alloc_bits = xcalloc (1, d->alloc_size);
2240 /* Allocate a place for object X of size SIZE in the PCH file. */
2242 char *
2243 ggc_pch_alloc_object (struct ggc_pch_data *d, void *x,
2244 size_t size, bool is_string,
2245 enum gt_types_enum type)
2247 size_t alloc_word, alloc_bit;
2248 char *result;
2249 int bucket = pch_bucket (x, type, is_string);
2251 /* Record the start of the object in the allocation bitmap. We
2252 can't assert that the allocation bit is previously clear, because
2253 strings may violate the invariant that they are at least
2254 BYTES_PER_ALLOC_BIT long. This is harmless - ggc_get_size
2255 should not be called for strings. */
2256 alloc_word = ((d->type_bases[bucket] - d->orig_base)
2257 / (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
2258 alloc_bit = ((d->type_bases[bucket] - d->orig_base)
2259 / BYTES_PER_ALLOC_BIT) % (8 * sizeof (alloc_type));
2260 d->alloc_bits[alloc_word] |= 1L << alloc_bit;
2262 /* Place the object at the current pointer for this bucket. */
2263 result = (char *) d->type_bases[bucket];
2264 d->type_bases[bucket] += size;
2265 return result;
2268 /* Prepare to write out the PCH data to file F. */
2270 void
2271 ggc_pch_prepare_write (struct ggc_pch_data *d,
2272 FILE *f)
2274 /* We seek around a lot while writing. Record where the end
2275 of the padding in the PCH file is, so that we can
2276 locate each object's offset. */
2277 d->start_offset = ftell (f);
2280 /* Write out object X of SIZE to file F. */
2282 void
2283 ggc_pch_write_object (struct ggc_pch_data *d,
2284 FILE *f, void *x, void *newx,
2285 size_t size, bool is_string ATTRIBUTE_UNUSED)
2287 if (fseek (f, (size_t) newx - d->orig_base + d->start_offset, SEEK_SET) != 0)
2288 fatal_error ("can't seek PCH file: %m");
2290 if (fwrite (x, size, 1, f) != 1)
2291 fatal_error ("can't write PCH file: %m");
2294 void
2295 ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
2297 /* Write out the allocation bitmap. */
2298 if (fseek (f, d->start_offset + d->d.total, SEEK_SET) != 0)
2299 fatal_error ("can't seek PCH file: %m");
2301 if (fwrite (d->alloc_bits, d->alloc_size, 1, f) != 1)
2302 fatal_error ("can't write PCH fle: %m");
2304 /* Done with the PCH, so write out our footer. */
2305 if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
2306 fatal_error ("can't write PCH file: %m");
2308 free (d->alloc_bits);
2309 free (d);
2312 /* The PCH file from F has been mapped at ADDR. Read in any
2313 additional data from the file and set up the GC state. */
2315 void
2316 ggc_pch_read (FILE *f, void *addr)
2318 struct ggc_pch_ondisk d;
2319 size_t alloc_size;
2320 struct alloc_zone *zone;
2321 struct page_entry *pch_page;
2322 char *p;
2324 if (fread (&d, sizeof (d), 1, f) != 1)
2325 fatal_error ("can't read PCH file: %m");
2327 alloc_size = CEIL (d.total, BYTES_PER_ALLOC_BIT * 8);
2328 alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
2330 pch_zone.bytes = d.total;
2331 pch_zone.alloc_bits = (alloc_type *) ((char *) addr + pch_zone.bytes);
2332 pch_zone.page = (char *) addr;
2333 pch_zone.end = (char *) pch_zone.alloc_bits;
2335 /* We've just read in a PCH file. So, every object that used to be
2336 allocated is now free. */
2337 for (zone = G.zones; zone; zone = zone->next_zone)
2339 struct small_page_entry *page, *next_page;
2340 struct large_page_entry *large_page, *next_large_page;
2342 zone->allocated = 0;
2344 /* Clear the zone's free chunk list. */
2345 memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
2346 zone->high_free_bin = 0;
2347 zone->cached_free = NULL;
2348 zone->cached_free_size = 0;
2350 /* Move all the small pages onto the free list. */
2351 for (page = zone->pages; page != NULL; page = next_page)
2353 next_page = page->next;
2354 memset (page->alloc_bits, 0,
2355 G.small_page_overhead - PAGE_OVERHEAD);
2356 free_small_page (page);
2359 /* Discard all the large pages. */
2360 for (large_page = zone->large_pages; large_page != NULL;
2361 large_page = next_large_page)
2363 next_large_page = large_page->next;
2364 free_large_page (large_page);
2367 zone->pages = NULL;
2368 zone->large_pages = NULL;
2371 /* Allocate the dummy page entry for the PCH, and set all pages
2372 mapped into the PCH to reference it. */
2373 pch_page = xcalloc (1, sizeof (struct page_entry));
2374 pch_page->page = pch_zone.page;
2375 pch_page->pch_p = true;
2377 for (p = pch_zone.page; p < pch_zone.end; p += GGC_PAGE_SIZE)
2378 set_page_table_entry (p, pch_page);