* gcc.dg/store-motion-fgcse-sm.c (dg-final): Cleanup
[official-gcc.git] / gcc / ggc-page.c
blobf55c4e9c6fb2796ce6f2c8619af099fc8b8be248
1 /* "Bag-of-pages" garbage collector for the GNU compiler.
2 Copyright (C) 1999-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "diagnostic-core.h"
28 #include "flags.h"
29 #include "ggc.h"
30 #include "ggc-internal.h"
31 #include "timevar.h"
32 #include "params.h"
33 #include "hash-map.h"
34 #include "is-a.h"
35 #include "plugin-api.h"
36 #include "vec.h"
37 #include "hashtab.h"
38 #include "hash-set.h"
39 #include "machmode.h"
40 #include "hard-reg-set.h"
41 #include "input.h"
42 #include "function.h"
43 #include "ipa-ref.h"
44 #include "cgraph.h"
45 #include "cfgloop.h"
46 #include "plugin.h"
47 #include "basic-block.h"
49 /* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
50 file open. Prefer either to valloc. */
51 #ifdef HAVE_MMAP_ANON
52 # undef HAVE_MMAP_DEV_ZERO
53 # define USING_MMAP
54 #endif
56 #ifdef HAVE_MMAP_DEV_ZERO
57 # define USING_MMAP
58 #endif
60 #ifndef USING_MMAP
61 #define USING_MALLOC_PAGE_GROUPS
62 #endif
64 #if defined(HAVE_MADVISE) && HAVE_DECL_MADVISE && defined(MADV_DONTNEED) \
65 && defined(USING_MMAP)
66 # define USING_MADVISE
67 #endif
69 /* Strategy:
71 This garbage-collecting allocator allocates objects on one of a set
72 of pages. Each page can allocate objects of a single size only;
73 available sizes are powers of two starting at four bytes. The size
74 of an allocation request is rounded up to the next power of two
75 (`order'), and satisfied from the appropriate page.
77 Each page is recorded in a page-entry, which also maintains an
78 in-use bitmap of object positions on the page. This allows the
79 allocation state of a particular object to be flipped without
80 touching the page itself.
82 Each page-entry also has a context depth, which is used to track
83 pushing and popping of allocation contexts. Only objects allocated
84 in the current (highest-numbered) context may be collected.
86 Page entries are arranged in an array of singly-linked lists. The
87 array is indexed by the allocation size, in bits, of the pages on
88 it; i.e. all pages on a list allocate objects of the same size.
89 Pages are ordered on the list such that all non-full pages precede
90 all full pages, with non-full pages arranged in order of decreasing
91 context depth.
93 Empty pages (of all orders) are kept on a single page cache list,
94 and are considered first when new pages are required; they are
95 deallocated at the start of the next collection if they haven't
96 been recycled by then. */
98 /* Define GGC_DEBUG_LEVEL to print debugging information.
99 0: No debugging output.
100 1: GC statistics only.
101 2: Page-entry allocations/deallocations as well.
102 3: Object allocations as well.
103 4: Object marks as well. */
104 #define GGC_DEBUG_LEVEL (0)
106 #ifndef HOST_BITS_PER_PTR
107 #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
108 #endif
111 /* A two-level tree is used to look up the page-entry for a given
112 pointer. Two chunks of the pointer's bits are extracted to index
113 the first and second levels of the tree, as follows:
115 HOST_PAGE_SIZE_BITS
116 32 | |
117 msb +----------------+----+------+------+ lsb
118 | | |
119 PAGE_L1_BITS |
121 PAGE_L2_BITS
123 The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry
124 pages are aligned on system page boundaries. The next most
125 significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first
126 index values in the lookup table, respectively.
128 For 32-bit architectures and the settings below, there are no
129 leftover bits. For architectures with wider pointers, the lookup
130 tree points to a list of pages, which must be scanned to find the
131 correct one. */
133 #define PAGE_L1_BITS (8)
134 #define PAGE_L2_BITS (32 - PAGE_L1_BITS - G.lg_pagesize)
135 #define PAGE_L1_SIZE ((uintptr_t) 1 << PAGE_L1_BITS)
136 #define PAGE_L2_SIZE ((uintptr_t) 1 << PAGE_L2_BITS)
138 #define LOOKUP_L1(p) \
139 (((uintptr_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
141 #define LOOKUP_L2(p) \
142 (((uintptr_t) (p) >> G.lg_pagesize) & ((1 << PAGE_L2_BITS) - 1))
144 /* The number of objects per allocation page, for objects on a page of
145 the indicated ORDER. */
146 #define OBJECTS_PER_PAGE(ORDER) objects_per_page_table[ORDER]
148 /* The number of objects in P. */
149 #define OBJECTS_IN_PAGE(P) ((P)->bytes / OBJECT_SIZE ((P)->order))
151 /* The size of an object on a page of the indicated ORDER. */
152 #define OBJECT_SIZE(ORDER) object_size_table[ORDER]
154 /* For speed, we avoid doing a general integer divide to locate the
155 offset in the allocation bitmap, by precalculating numbers M, S
156 such that (O * M) >> S == O / Z (modulo 2^32), for any offset O
157 within the page which is evenly divisible by the object size Z. */
158 #define DIV_MULT(ORDER) inverse_table[ORDER].mult
159 #define DIV_SHIFT(ORDER) inverse_table[ORDER].shift
160 #define OFFSET_TO_BIT(OFFSET, ORDER) \
161 (((OFFSET) * DIV_MULT (ORDER)) >> DIV_SHIFT (ORDER))
163 /* We use this structure to determine the alignment required for
164 allocations. For power-of-two sized allocations, that's not a
165 problem, but it does matter for odd-sized allocations.
166 We do not care about alignment for floating-point types. */
168 struct max_alignment {
169 char c;
170 union {
171 int64_t i;
172 void *p;
173 } u;
176 /* The biggest alignment required. */
178 #define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
181 /* The number of extra orders, not corresponding to power-of-two sized
182 objects. */
184 #define NUM_EXTRA_ORDERS ARRAY_SIZE (extra_order_size_table)
186 #define RTL_SIZE(NSLOTS) \
187 (RTX_HDR_SIZE + (NSLOTS) * sizeof (rtunion))
189 #define TREE_EXP_SIZE(OPS) \
190 (sizeof (struct tree_exp) + ((OPS) - 1) * sizeof (tree))
192 /* The Ith entry is the maximum size of an object to be stored in the
193 Ith extra order. Adding a new entry to this array is the *only*
194 thing you need to do to add a new special allocation size. */
196 static const size_t extra_order_size_table[] = {
197 /* Extra orders for small non-power-of-two multiples of MAX_ALIGNMENT.
198 There are a lot of structures with these sizes and explicitly
199 listing them risks orders being dropped because they changed size. */
200 MAX_ALIGNMENT * 3,
201 MAX_ALIGNMENT * 5,
202 MAX_ALIGNMENT * 6,
203 MAX_ALIGNMENT * 7,
204 MAX_ALIGNMENT * 9,
205 MAX_ALIGNMENT * 10,
206 MAX_ALIGNMENT * 11,
207 MAX_ALIGNMENT * 12,
208 MAX_ALIGNMENT * 13,
209 MAX_ALIGNMENT * 14,
210 MAX_ALIGNMENT * 15,
211 sizeof (struct tree_decl_non_common),
212 sizeof (struct tree_field_decl),
213 sizeof (struct tree_parm_decl),
214 sizeof (struct tree_var_decl),
215 sizeof (struct tree_type_non_common),
216 sizeof (struct function),
217 sizeof (struct basic_block_def),
218 sizeof (struct cgraph_node),
219 sizeof (struct loop),
222 /* The total number of orders. */
224 #define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
226 /* Compute the smallest nonnegative number which when added to X gives
227 a multiple of F. */
229 #define ROUND_UP_VALUE(x, f) ((f) - 1 - ((f) - 1 + (x)) % (f))
231 /* Compute the smallest multiple of F that is >= X. */
233 #define ROUND_UP(x, f) (CEIL (x, f) * (f))
235 /* Round X to next multiple of the page size */
237 #define PAGE_ALIGN(x) (((x) + G.pagesize - 1) & ~(G.pagesize - 1))
239 /* The Ith entry is the number of objects on a page or order I. */
241 static unsigned objects_per_page_table[NUM_ORDERS];
243 /* The Ith entry is the size of an object on a page of order I. */
245 static size_t object_size_table[NUM_ORDERS];
247 /* The Ith entry is a pair of numbers (mult, shift) such that
248 ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
249 for all k evenly divisible by OBJECT_SIZE(I). */
251 static struct
253 size_t mult;
254 unsigned int shift;
256 inverse_table[NUM_ORDERS];
258 /* A page_entry records the status of an allocation page. This
259 structure is dynamically sized to fit the bitmap in_use_p. */
260 typedef struct page_entry
262 /* The next page-entry with objects of the same size, or NULL if
263 this is the last page-entry. */
264 struct page_entry *next;
266 /* The previous page-entry with objects of the same size, or NULL if
267 this is the first page-entry. The PREV pointer exists solely to
268 keep the cost of ggc_free manageable. */
269 struct page_entry *prev;
271 /* The number of bytes allocated. (This will always be a multiple
272 of the host system page size.) */
273 size_t bytes;
275 /* The address at which the memory is allocated. */
276 char *page;
278 #ifdef USING_MALLOC_PAGE_GROUPS
279 /* Back pointer to the page group this page came from. */
280 struct page_group *group;
281 #endif
283 /* This is the index in the by_depth varray where this page table
284 can be found. */
285 unsigned long index_by_depth;
287 /* Context depth of this page. */
288 unsigned short context_depth;
290 /* The number of free objects remaining on this page. */
291 unsigned short num_free_objects;
293 /* A likely candidate for the bit position of a free object for the
294 next allocation from this page. */
295 unsigned short next_bit_hint;
297 /* The lg of size of objects allocated from this page. */
298 unsigned char order;
300 /* Discarded page? */
301 bool discarded;
303 /* A bit vector indicating whether or not objects are in use. The
304 Nth bit is one if the Nth object on this page is allocated. This
305 array is dynamically sized. */
306 unsigned long in_use_p[1];
307 } page_entry;
309 #ifdef USING_MALLOC_PAGE_GROUPS
310 /* A page_group describes a large allocation from malloc, from which
311 we parcel out aligned pages. */
312 typedef struct page_group
314 /* A linked list of all extant page groups. */
315 struct page_group *next;
317 /* The address we received from malloc. */
318 char *allocation;
320 /* The size of the block. */
321 size_t alloc_size;
323 /* A bitmask of pages in use. */
324 unsigned int in_use;
325 } page_group;
326 #endif
328 #if HOST_BITS_PER_PTR <= 32
330 /* On 32-bit hosts, we use a two level page table, as pictured above. */
331 typedef page_entry **page_table[PAGE_L1_SIZE];
333 #else
335 /* On 64-bit hosts, we use the same two level page tables plus a linked
336 list that disambiguates the top 32-bits. There will almost always be
337 exactly one entry in the list. */
338 typedef struct page_table_chain
340 struct page_table_chain *next;
341 size_t high_bits;
342 page_entry **table[PAGE_L1_SIZE];
343 } *page_table;
345 #endif
347 class finalizer
349 public:
350 finalizer (void *addr, void (*f)(void *)) : m_addr (addr), m_function (f) {}
352 void *addr () const { return m_addr; }
354 void call () const { m_function (m_addr); }
356 private:
357 void *m_addr;
358 void (*m_function)(void *);
361 class vec_finalizer
363 public:
364 vec_finalizer (uintptr_t addr, void (*f)(void *), size_t s, size_t n) :
365 m_addr (addr), m_function (f), m_object_size (s), m_n_objects (n) {}
367 void call () const
369 for (size_t i = 0; i < m_n_objects; i++)
370 m_function (reinterpret_cast<void *> (m_addr + (i * m_object_size)));
373 void *addr () const { return reinterpret_cast<void *> (m_addr); }
375 private:
376 uintptr_t m_addr;
377 void (*m_function)(void *);
378 size_t m_object_size;
379 size_t m_n_objects;
382 #ifdef ENABLE_GC_ALWAYS_COLLECT
383 /* List of free objects to be verified as actually free on the
384 next collection. */
385 struct free_object
387 void *object;
388 struct free_object *next;
390 #endif
392 /* The rest of the global variables. */
393 static struct ggc_globals
395 /* The Nth element in this array is a page with objects of size 2^N.
396 If there are any pages with free objects, they will be at the
397 head of the list. NULL if there are no page-entries for this
398 object size. */
399 page_entry *pages[NUM_ORDERS];
401 /* The Nth element in this array is the last page with objects of
402 size 2^N. NULL if there are no page-entries for this object
403 size. */
404 page_entry *page_tails[NUM_ORDERS];
406 /* Lookup table for associating allocation pages with object addresses. */
407 page_table lookup;
409 /* The system's page size. */
410 size_t pagesize;
411 size_t lg_pagesize;
413 /* Bytes currently allocated. */
414 size_t allocated;
416 /* Bytes currently allocated at the end of the last collection. */
417 size_t allocated_last_gc;
419 /* Total amount of memory mapped. */
420 size_t bytes_mapped;
422 /* Bit N set if any allocations have been done at context depth N. */
423 unsigned long context_depth_allocations;
425 /* Bit N set if any collections have been done at context depth N. */
426 unsigned long context_depth_collections;
428 /* The current depth in the context stack. */
429 unsigned short context_depth;
431 /* A file descriptor open to /dev/zero for reading. */
432 #if defined (HAVE_MMAP_DEV_ZERO)
433 int dev_zero_fd;
434 #endif
436 /* A cache of free system pages. */
437 page_entry *free_pages;
439 #ifdef USING_MALLOC_PAGE_GROUPS
440 page_group *page_groups;
441 #endif
443 /* The file descriptor for debugging output. */
444 FILE *debug_file;
446 /* Current number of elements in use in depth below. */
447 unsigned int depth_in_use;
449 /* Maximum number of elements that can be used before resizing. */
450 unsigned int depth_max;
452 /* Each element of this array is an index in by_depth where the given
453 depth starts. This structure is indexed by that given depth we
454 are interested in. */
455 unsigned int *depth;
457 /* Current number of elements in use in by_depth below. */
458 unsigned int by_depth_in_use;
460 /* Maximum number of elements that can be used before resizing. */
461 unsigned int by_depth_max;
463 /* Each element of this array is a pointer to a page_entry, all
464 page_entries can be found in here by increasing depth.
465 index_by_depth in the page_entry is the index into this data
466 structure where that page_entry can be found. This is used to
467 speed up finding all page_entries at a particular depth. */
468 page_entry **by_depth;
470 /* Each element is a pointer to the saved in_use_p bits, if any,
471 zero otherwise. We allocate them all together, to enable a
472 better runtime data access pattern. */
473 unsigned long **save_in_use;
475 /* Finalizers for single objects. */
476 vec<finalizer> finalizers;
478 /* Finalizers for vectors of objects. */
479 vec<vec_finalizer> vec_finalizers;
481 #ifdef ENABLE_GC_ALWAYS_COLLECT
482 /* List of free objects to be verified as actually free on the
483 next collection. */
484 struct free_object *free_object_list;
485 #endif
487 struct
489 /* Total GC-allocated memory. */
490 unsigned long long total_allocated;
491 /* Total overhead for GC-allocated memory. */
492 unsigned long long total_overhead;
494 /* Total allocations and overhead for sizes less than 32, 64 and 128.
495 These sizes are interesting because they are typical cache line
496 sizes. */
498 unsigned long long total_allocated_under32;
499 unsigned long long total_overhead_under32;
501 unsigned long long total_allocated_under64;
502 unsigned long long total_overhead_under64;
504 unsigned long long total_allocated_under128;
505 unsigned long long total_overhead_under128;
507 /* The allocations for each of the allocation orders. */
508 unsigned long long total_allocated_per_order[NUM_ORDERS];
510 /* The overhead for each of the allocation orders. */
511 unsigned long long total_overhead_per_order[NUM_ORDERS];
512 } stats;
513 } G;
515 /* True if a gc is currently taking place. */
517 static bool in_gc = false;
519 /* The size in bytes required to maintain a bitmap for the objects
520 on a page-entry. */
521 #define BITMAP_SIZE(Num_objects) \
522 (CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof (long))
524 /* Allocate pages in chunks of this size, to throttle calls to memory
525 allocation routines. The first page is used, the rest go onto the
526 free list. This cannot be larger than HOST_BITS_PER_INT for the
527 in_use bitmask for page_group. Hosts that need a different value
528 can override this by defining GGC_QUIRE_SIZE explicitly. */
529 #ifndef GGC_QUIRE_SIZE
530 # ifdef USING_MMAP
531 # define GGC_QUIRE_SIZE 512 /* 2MB for 4K pages */
532 # else
533 # define GGC_QUIRE_SIZE 16
534 # endif
535 #endif
537 /* Initial guess as to how many page table entries we might need. */
538 #define INITIAL_PTE_COUNT 128
540 static int ggc_allocated_p (const void *);
541 static page_entry *lookup_page_table_entry (const void *);
542 static void set_page_table_entry (void *, page_entry *);
543 #ifdef USING_MMAP
544 static char *alloc_anon (char *, size_t, bool check);
545 #endif
546 #ifdef USING_MALLOC_PAGE_GROUPS
547 static size_t page_group_index (char *, char *);
548 static void set_page_group_in_use (page_group *, char *);
549 static void clear_page_group_in_use (page_group *, char *);
550 #endif
551 static struct page_entry * alloc_page (unsigned);
552 static void free_page (struct page_entry *);
553 static void release_pages (void);
554 static void clear_marks (void);
555 static void sweep_pages (void);
556 static void ggc_recalculate_in_use_p (page_entry *);
557 static void compute_inverse (unsigned);
558 static inline void adjust_depth (void);
559 static void move_ptes_to_front (int, int);
561 void debug_print_page_list (int);
562 static void push_depth (unsigned int);
563 static void push_by_depth (page_entry *, unsigned long *);
565 /* Push an entry onto G.depth. */
567 inline static void
568 push_depth (unsigned int i)
570 if (G.depth_in_use >= G.depth_max)
572 G.depth_max *= 2;
573 G.depth = XRESIZEVEC (unsigned int, G.depth, G.depth_max);
575 G.depth[G.depth_in_use++] = i;
578 /* Push an entry onto G.by_depth and G.save_in_use. */
580 inline static void
581 push_by_depth (page_entry *p, unsigned long *s)
583 if (G.by_depth_in_use >= G.by_depth_max)
585 G.by_depth_max *= 2;
586 G.by_depth = XRESIZEVEC (page_entry *, G.by_depth, G.by_depth_max);
587 G.save_in_use = XRESIZEVEC (unsigned long *, G.save_in_use,
588 G.by_depth_max);
590 G.by_depth[G.by_depth_in_use] = p;
591 G.save_in_use[G.by_depth_in_use++] = s;
594 #if (GCC_VERSION < 3001)
595 #define prefetch(X) ((void) X)
596 #else
597 #define prefetch(X) __builtin_prefetch (X)
598 #endif
600 #define save_in_use_p_i(__i) \
601 (G.save_in_use[__i])
602 #define save_in_use_p(__p) \
603 (save_in_use_p_i (__p->index_by_depth))
605 /* Returns nonzero if P was allocated in GC'able memory. */
607 static inline int
608 ggc_allocated_p (const void *p)
610 page_entry ***base;
611 size_t L1, L2;
613 #if HOST_BITS_PER_PTR <= 32
614 base = &G.lookup[0];
615 #else
616 page_table table = G.lookup;
617 uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff;
618 while (1)
620 if (table == NULL)
621 return 0;
622 if (table->high_bits == high_bits)
623 break;
624 table = table->next;
626 base = &table->table[0];
627 #endif
629 /* Extract the level 1 and 2 indices. */
630 L1 = LOOKUP_L1 (p);
631 L2 = LOOKUP_L2 (p);
633 return base[L1] && base[L1][L2];
636 /* Traverse the page table and find the entry for a page.
637 Die (probably) if the object wasn't allocated via GC. */
639 static inline page_entry *
640 lookup_page_table_entry (const void *p)
642 page_entry ***base;
643 size_t L1, L2;
645 #if HOST_BITS_PER_PTR <= 32
646 base = &G.lookup[0];
647 #else
648 page_table table = G.lookup;
649 uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff;
650 while (table->high_bits != high_bits)
651 table = table->next;
652 base = &table->table[0];
653 #endif
655 /* Extract the level 1 and 2 indices. */
656 L1 = LOOKUP_L1 (p);
657 L2 = LOOKUP_L2 (p);
659 return base[L1][L2];
662 /* Set the page table entry for a page. */
664 static void
665 set_page_table_entry (void *p, page_entry *entry)
667 page_entry ***base;
668 size_t L1, L2;
670 #if HOST_BITS_PER_PTR <= 32
671 base = &G.lookup[0];
672 #else
673 page_table table;
674 uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff;
675 for (table = G.lookup; table; table = table->next)
676 if (table->high_bits == high_bits)
677 goto found;
679 /* Not found -- allocate a new table. */
680 table = XCNEW (struct page_table_chain);
681 table->next = G.lookup;
682 table->high_bits = high_bits;
683 G.lookup = table;
684 found:
685 base = &table->table[0];
686 #endif
688 /* Extract the level 1 and 2 indices. */
689 L1 = LOOKUP_L1 (p);
690 L2 = LOOKUP_L2 (p);
692 if (base[L1] == NULL)
693 base[L1] = XCNEWVEC (page_entry *, PAGE_L2_SIZE);
695 base[L1][L2] = entry;
698 /* Prints the page-entry for object size ORDER, for debugging. */
700 DEBUG_FUNCTION void
701 debug_print_page_list (int order)
703 page_entry *p;
704 printf ("Head=%p, Tail=%p:\n", (void *) G.pages[order],
705 (void *) G.page_tails[order]);
706 p = G.pages[order];
707 while (p != NULL)
709 printf ("%p(%1d|%3d) -> ", (void *) p, p->context_depth,
710 p->num_free_objects);
711 p = p->next;
713 printf ("NULL\n");
714 fflush (stdout);
717 #ifdef USING_MMAP
718 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
719 (if non-null). The ifdef structure here is intended to cause a
720 compile error unless exactly one of the HAVE_* is defined. */
722 static inline char *
723 alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, bool check)
725 #ifdef HAVE_MMAP_ANON
726 char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
727 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
728 #endif
729 #ifdef HAVE_MMAP_DEV_ZERO
730 char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
731 MAP_PRIVATE, G.dev_zero_fd, 0);
732 #endif
734 if (page == (char *) MAP_FAILED)
736 if (!check)
737 return NULL;
738 perror ("virtual memory exhausted");
739 exit (FATAL_EXIT_CODE);
742 /* Remember that we allocated this memory. */
743 G.bytes_mapped += size;
745 /* Pretend we don't have access to the allocated pages. We'll enable
746 access to smaller pieces of the area in ggc_internal_alloc. Discard the
747 handle to avoid handle leak. */
748 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (page, size));
750 return page;
752 #endif
753 #ifdef USING_MALLOC_PAGE_GROUPS
754 /* Compute the index for this page into the page group. */
756 static inline size_t
757 page_group_index (char *allocation, char *page)
759 return (size_t) (page - allocation) >> G.lg_pagesize;
762 /* Set and clear the in_use bit for this page in the page group. */
764 static inline void
765 set_page_group_in_use (page_group *group, char *page)
767 group->in_use |= 1 << page_group_index (group->allocation, page);
770 static inline void
771 clear_page_group_in_use (page_group *group, char *page)
773 group->in_use &= ~(1 << page_group_index (group->allocation, page));
775 #endif
777 /* Allocate a new page for allocating objects of size 2^ORDER,
778 and return an entry for it. The entry is not added to the
779 appropriate page_table list. */
781 static inline struct page_entry *
782 alloc_page (unsigned order)
784 struct page_entry *entry, *p, **pp;
785 char *page;
786 size_t num_objects;
787 size_t bitmap_size;
788 size_t page_entry_size;
789 size_t entry_size;
790 #ifdef USING_MALLOC_PAGE_GROUPS
791 page_group *group;
792 #endif
794 num_objects = OBJECTS_PER_PAGE (order);
795 bitmap_size = BITMAP_SIZE (num_objects + 1);
796 page_entry_size = sizeof (page_entry) - sizeof (long) + bitmap_size;
797 entry_size = num_objects * OBJECT_SIZE (order);
798 if (entry_size < G.pagesize)
799 entry_size = G.pagesize;
800 entry_size = PAGE_ALIGN (entry_size);
802 entry = NULL;
803 page = NULL;
805 /* Check the list of free pages for one we can use. */
806 for (pp = &G.free_pages, p = *pp; p; pp = &p->next, p = *pp)
807 if (p->bytes == entry_size)
808 break;
810 if (p != NULL)
812 if (p->discarded)
813 G.bytes_mapped += p->bytes;
814 p->discarded = false;
816 /* Recycle the allocated memory from this page ... */
817 *pp = p->next;
818 page = p->page;
820 #ifdef USING_MALLOC_PAGE_GROUPS
821 group = p->group;
822 #endif
824 /* ... and, if possible, the page entry itself. */
825 if (p->order == order)
827 entry = p;
828 memset (entry, 0, page_entry_size);
830 else
831 free (p);
833 #ifdef USING_MMAP
834 else if (entry_size == G.pagesize)
836 /* We want just one page. Allocate a bunch of them and put the
837 extras on the freelist. (Can only do this optimization with
838 mmap for backing store.) */
839 struct page_entry *e, *f = G.free_pages;
840 int i, entries = GGC_QUIRE_SIZE;
842 page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE, false);
843 if (page == NULL)
845 page = alloc_anon (NULL, G.pagesize, true);
846 entries = 1;
849 /* This loop counts down so that the chain will be in ascending
850 memory order. */
851 for (i = entries - 1; i >= 1; i--)
853 e = XCNEWVAR (struct page_entry, page_entry_size);
854 e->order = order;
855 e->bytes = G.pagesize;
856 e->page = page + (i << G.lg_pagesize);
857 e->next = f;
858 f = e;
861 G.free_pages = f;
863 else
864 page = alloc_anon (NULL, entry_size, true);
865 #endif
866 #ifdef USING_MALLOC_PAGE_GROUPS
867 else
869 /* Allocate a large block of memory and serve out the aligned
870 pages therein. This results in much less memory wastage
871 than the traditional implementation of valloc. */
873 char *allocation, *a, *enda;
874 size_t alloc_size, head_slop, tail_slop;
875 int multiple_pages = (entry_size == G.pagesize);
877 if (multiple_pages)
878 alloc_size = GGC_QUIRE_SIZE * G.pagesize;
879 else
880 alloc_size = entry_size + G.pagesize - 1;
881 allocation = XNEWVEC (char, alloc_size);
883 page = (char *) (((uintptr_t) allocation + G.pagesize - 1) & -G.pagesize);
884 head_slop = page - allocation;
885 if (multiple_pages)
886 tail_slop = ((size_t) allocation + alloc_size) & (G.pagesize - 1);
887 else
888 tail_slop = alloc_size - entry_size - head_slop;
889 enda = allocation + alloc_size - tail_slop;
891 /* We allocated N pages, which are likely not aligned, leaving
892 us with N-1 usable pages. We plan to place the page_group
893 structure somewhere in the slop. */
894 if (head_slop >= sizeof (page_group))
895 group = (page_group *)page - 1;
896 else
898 /* We magically got an aligned allocation. Too bad, we have
899 to waste a page anyway. */
900 if (tail_slop == 0)
902 enda -= G.pagesize;
903 tail_slop += G.pagesize;
905 gcc_assert (tail_slop >= sizeof (page_group));
906 group = (page_group *)enda;
907 tail_slop -= sizeof (page_group);
910 /* Remember that we allocated this memory. */
911 group->next = G.page_groups;
912 group->allocation = allocation;
913 group->alloc_size = alloc_size;
914 group->in_use = 0;
915 G.page_groups = group;
916 G.bytes_mapped += alloc_size;
918 /* If we allocated multiple pages, put the rest on the free list. */
919 if (multiple_pages)
921 struct page_entry *e, *f = G.free_pages;
922 for (a = enda - G.pagesize; a != page; a -= G.pagesize)
924 e = XCNEWVAR (struct page_entry, page_entry_size);
925 e->order = order;
926 e->bytes = G.pagesize;
927 e->page = a;
928 e->group = group;
929 e->next = f;
930 f = e;
932 G.free_pages = f;
935 #endif
937 if (entry == NULL)
938 entry = XCNEWVAR (struct page_entry, page_entry_size);
940 entry->bytes = entry_size;
941 entry->page = page;
942 entry->context_depth = G.context_depth;
943 entry->order = order;
944 entry->num_free_objects = num_objects;
945 entry->next_bit_hint = 1;
947 G.context_depth_allocations |= (unsigned long)1 << G.context_depth;
949 #ifdef USING_MALLOC_PAGE_GROUPS
950 entry->group = group;
951 set_page_group_in_use (group, page);
952 #endif
954 /* Set the one-past-the-end in-use bit. This acts as a sentry as we
955 increment the hint. */
956 entry->in_use_p[num_objects / HOST_BITS_PER_LONG]
957 = (unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG);
959 set_page_table_entry (page, entry);
961 if (GGC_DEBUG_LEVEL >= 2)
962 fprintf (G.debug_file,
963 "Allocating page at %p, object size=%lu, data %p-%p\n",
964 (void *) entry, (unsigned long) OBJECT_SIZE (order), page,
965 page + entry_size - 1);
967 return entry;
970 /* Adjust the size of G.depth so that no index greater than the one
971 used by the top of the G.by_depth is used. */
973 static inline void
974 adjust_depth (void)
976 page_entry *top;
978 if (G.by_depth_in_use)
980 top = G.by_depth[G.by_depth_in_use-1];
982 /* Peel back indices in depth that index into by_depth, so that
983 as new elements are added to by_depth, we note the indices
984 of those elements, if they are for new context depths. */
985 while (G.depth_in_use > (size_t)top->context_depth+1)
986 --G.depth_in_use;
990 /* For a page that is no longer needed, put it on the free page list. */
992 static void
993 free_page (page_entry *entry)
995 if (GGC_DEBUG_LEVEL >= 2)
996 fprintf (G.debug_file,
997 "Deallocating page at %p, data %p-%p\n", (void *) entry,
998 entry->page, entry->page + entry->bytes - 1);
1000 /* Mark the page as inaccessible. Discard the handle to avoid handle
1001 leak. */
1002 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (entry->page, entry->bytes));
1004 set_page_table_entry (entry->page, NULL);
1006 #ifdef USING_MALLOC_PAGE_GROUPS
1007 clear_page_group_in_use (entry->group, entry->page);
1008 #endif
1010 if (G.by_depth_in_use > 1)
1012 page_entry *top = G.by_depth[G.by_depth_in_use-1];
1013 int i = entry->index_by_depth;
1015 /* We cannot free a page from a context deeper than the current
1016 one. */
1017 gcc_assert (entry->context_depth == top->context_depth);
1019 /* Put top element into freed slot. */
1020 G.by_depth[i] = top;
1021 G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1];
1022 top->index_by_depth = i;
1024 --G.by_depth_in_use;
1026 adjust_depth ();
1028 entry->next = G.free_pages;
1029 G.free_pages = entry;
1032 /* Release the free page cache to the system. */
1034 static void
1035 release_pages (void)
1037 #ifdef USING_MADVISE
1038 page_entry *p, *start_p;
1039 char *start;
1040 size_t len;
1041 size_t mapped_len;
1042 page_entry *next, *prev, *newprev;
1043 size_t free_unit = (GGC_QUIRE_SIZE/2) * G.pagesize;
1045 /* First free larger continuous areas to the OS.
1046 This allows other allocators to grab these areas if needed.
1047 This is only done on larger chunks to avoid fragmentation.
1048 This does not always work because the free_pages list is only
1049 approximately sorted. */
1051 p = G.free_pages;
1052 prev = NULL;
1053 while (p)
1055 start = p->page;
1056 start_p = p;
1057 len = 0;
1058 mapped_len = 0;
1059 newprev = prev;
1060 while (p && p->page == start + len)
1062 len += p->bytes;
1063 if (!p->discarded)
1064 mapped_len += p->bytes;
1065 newprev = p;
1066 p = p->next;
1068 if (len >= free_unit)
1070 while (start_p != p)
1072 next = start_p->next;
1073 free (start_p);
1074 start_p = next;
1076 munmap (start, len);
1077 if (prev)
1078 prev->next = p;
1079 else
1080 G.free_pages = p;
1081 G.bytes_mapped -= mapped_len;
1082 continue;
1084 prev = newprev;
1087 /* Now give back the fragmented pages to the OS, but keep the address
1088 space to reuse it next time. */
1090 for (p = G.free_pages; p; )
1092 if (p->discarded)
1094 p = p->next;
1095 continue;
1097 start = p->page;
1098 len = p->bytes;
1099 start_p = p;
1100 p = p->next;
1101 while (p && p->page == start + len)
1103 len += p->bytes;
1104 p = p->next;
1106 /* Give the page back to the kernel, but don't free the mapping.
1107 This avoids fragmentation in the virtual memory map of the
1108 process. Next time we can reuse it by just touching it. */
1109 madvise (start, len, MADV_DONTNEED);
1110 /* Don't count those pages as mapped to not touch the garbage collector
1111 unnecessarily. */
1112 G.bytes_mapped -= len;
1113 while (start_p != p)
1115 start_p->discarded = true;
1116 start_p = start_p->next;
1119 #endif
1120 #if defined(USING_MMAP) && !defined(USING_MADVISE)
1121 page_entry *p, *next;
1122 char *start;
1123 size_t len;
1125 /* Gather up adjacent pages so they are unmapped together. */
1126 p = G.free_pages;
1128 while (p)
1130 start = p->page;
1131 next = p->next;
1132 len = p->bytes;
1133 free (p);
1134 p = next;
1136 while (p && p->page == start + len)
1138 next = p->next;
1139 len += p->bytes;
1140 free (p);
1141 p = next;
1144 munmap (start, len);
1145 G.bytes_mapped -= len;
1148 G.free_pages = NULL;
1149 #endif
1150 #ifdef USING_MALLOC_PAGE_GROUPS
1151 page_entry **pp, *p;
1152 page_group **gp, *g;
1154 /* Remove all pages from free page groups from the list. */
1155 pp = &G.free_pages;
1156 while ((p = *pp) != NULL)
1157 if (p->group->in_use == 0)
1159 *pp = p->next;
1160 free (p);
1162 else
1163 pp = &p->next;
1165 /* Remove all free page groups, and release the storage. */
1166 gp = &G.page_groups;
1167 while ((g = *gp) != NULL)
1168 if (g->in_use == 0)
1170 *gp = g->next;
1171 G.bytes_mapped -= g->alloc_size;
1172 free (g->allocation);
1174 else
1175 gp = &g->next;
1176 #endif
1179 /* This table provides a fast way to determine ceil(log_2(size)) for
1180 allocation requests. The minimum allocation size is eight bytes. */
1181 #define NUM_SIZE_LOOKUP 512
1182 static unsigned char size_lookup[NUM_SIZE_LOOKUP] =
1184 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
1185 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1186 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1187 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1188 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1189 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1190 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1191 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1192 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1193 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1194 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1195 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1196 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1197 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1198 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1199 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1200 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1201 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1202 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1203 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1204 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1205 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1206 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1207 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1208 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1209 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1210 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1211 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1212 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1213 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1214 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
1215 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
1218 /* For a given size of memory requested for allocation, return the
1219 actual size that is going to be allocated, as well as the size
1220 order. */
1222 static void
1223 ggc_round_alloc_size_1 (size_t requested_size,
1224 size_t *size_order,
1225 size_t *alloced_size)
1227 size_t order, object_size;
1229 if (requested_size < NUM_SIZE_LOOKUP)
1231 order = size_lookup[requested_size];
1232 object_size = OBJECT_SIZE (order);
1234 else
1236 order = 10;
1237 while (requested_size > (object_size = OBJECT_SIZE (order)))
1238 order++;
1241 if (size_order)
1242 *size_order = order;
1243 if (alloced_size)
1244 *alloced_size = object_size;
1247 /* For a given size of memory requested for allocation, return the
1248 actual size that is going to be allocated. */
1250 size_t
1251 ggc_round_alloc_size (size_t requested_size)
1253 size_t size = 0;
1255 ggc_round_alloc_size_1 (requested_size, NULL, &size);
1256 return size;
1259 /* Allocate a chunk of memory of SIZE bytes. Its contents are undefined. */
1261 void *
1262 ggc_internal_alloc (size_t size, void (*f)(void *), size_t s, size_t n
1263 MEM_STAT_DECL)
1265 size_t order, word, bit, object_offset, object_size;
1266 struct page_entry *entry;
1267 void *result;
1269 ggc_round_alloc_size_1 (size, &order, &object_size);
1271 /* If there are non-full pages for this size allocation, they are at
1272 the head of the list. */
1273 entry = G.pages[order];
1275 /* If there is no page for this object size, or all pages in this
1276 context are full, allocate a new page. */
1277 if (entry == NULL || entry->num_free_objects == 0)
1279 struct page_entry *new_entry;
1280 new_entry = alloc_page (order);
1282 new_entry->index_by_depth = G.by_depth_in_use;
1283 push_by_depth (new_entry, 0);
1285 /* We can skip context depths, if we do, make sure we go all the
1286 way to the new depth. */
1287 while (new_entry->context_depth >= G.depth_in_use)
1288 push_depth (G.by_depth_in_use-1);
1290 /* If this is the only entry, it's also the tail. If it is not
1291 the only entry, then we must update the PREV pointer of the
1292 ENTRY (G.pages[order]) to point to our new page entry. */
1293 if (entry == NULL)
1294 G.page_tails[order] = new_entry;
1295 else
1296 entry->prev = new_entry;
1298 /* Put new pages at the head of the page list. By definition the
1299 entry at the head of the list always has a NULL pointer. */
1300 new_entry->next = entry;
1301 new_entry->prev = NULL;
1302 entry = new_entry;
1303 G.pages[order] = new_entry;
1305 /* For a new page, we know the word and bit positions (in the
1306 in_use bitmap) of the first available object -- they're zero. */
1307 new_entry->next_bit_hint = 1;
1308 word = 0;
1309 bit = 0;
1310 object_offset = 0;
1312 else
1314 /* First try to use the hint left from the previous allocation
1315 to locate a clear bit in the in-use bitmap. We've made sure
1316 that the one-past-the-end bit is always set, so if the hint
1317 has run over, this test will fail. */
1318 unsigned hint = entry->next_bit_hint;
1319 word = hint / HOST_BITS_PER_LONG;
1320 bit = hint % HOST_BITS_PER_LONG;
1322 /* If the hint didn't work, scan the bitmap from the beginning. */
1323 if ((entry->in_use_p[word] >> bit) & 1)
1325 word = bit = 0;
1326 while (~entry->in_use_p[word] == 0)
1327 ++word;
1329 #if GCC_VERSION >= 3004
1330 bit = __builtin_ctzl (~entry->in_use_p[word]);
1331 #else
1332 while ((entry->in_use_p[word] >> bit) & 1)
1333 ++bit;
1334 #endif
1336 hint = word * HOST_BITS_PER_LONG + bit;
1339 /* Next time, try the next bit. */
1340 entry->next_bit_hint = hint + 1;
1342 object_offset = hint * object_size;
1345 /* Set the in-use bit. */
1346 entry->in_use_p[word] |= ((unsigned long) 1 << bit);
1348 /* Keep a running total of the number of free objects. If this page
1349 fills up, we may have to move it to the end of the list if the
1350 next page isn't full. If the next page is full, all subsequent
1351 pages are full, so there's no need to move it. */
1352 if (--entry->num_free_objects == 0
1353 && entry->next != NULL
1354 && entry->next->num_free_objects > 0)
1356 /* We have a new head for the list. */
1357 G.pages[order] = entry->next;
1359 /* We are moving ENTRY to the end of the page table list.
1360 The new page at the head of the list will have NULL in
1361 its PREV field and ENTRY will have NULL in its NEXT field. */
1362 entry->next->prev = NULL;
1363 entry->next = NULL;
1365 /* Append ENTRY to the tail of the list. */
1366 entry->prev = G.page_tails[order];
1367 G.page_tails[order]->next = entry;
1368 G.page_tails[order] = entry;
1371 /* Calculate the object's address. */
1372 result = entry->page + object_offset;
1373 if (GATHER_STATISTICS)
1374 ggc_record_overhead (OBJECT_SIZE (order), OBJECT_SIZE (order) - size,
1375 result FINAL_PASS_MEM_STAT);
1377 #ifdef ENABLE_GC_CHECKING
1378 /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the
1379 exact same semantics in presence of memory bugs, regardless of
1380 ENABLE_VALGRIND_CHECKING. We override this request below. Drop the
1381 handle to avoid handle leak. */
1382 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, object_size));
1384 /* `Poison' the entire allocated object, including any padding at
1385 the end. */
1386 memset (result, 0xaf, object_size);
1388 /* Make the bytes after the end of the object unaccessible. Discard the
1389 handle to avoid handle leak. */
1390 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS ((char *) result + size,
1391 object_size - size));
1392 #endif
1394 /* Tell Valgrind that the memory is there, but its content isn't
1395 defined. The bytes at the end of the object are still marked
1396 unaccessible. */
1397 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, size));
1399 /* Keep track of how many bytes are being allocated. This
1400 information is used in deciding when to collect. */
1401 G.allocated += object_size;
1403 /* For timevar statistics. */
1404 timevar_ggc_mem_total += object_size;
1406 if (f && n == 1)
1407 G.finalizers.safe_push (finalizer (result, f));
1408 else if (f)
1409 G.vec_finalizers.safe_push
1410 (vec_finalizer (reinterpret_cast<uintptr_t> (result), f, s, n));
1412 if (GATHER_STATISTICS)
1414 size_t overhead = object_size - size;
1416 G.stats.total_overhead += overhead;
1417 G.stats.total_allocated += object_size;
1418 G.stats.total_overhead_per_order[order] += overhead;
1419 G.stats.total_allocated_per_order[order] += object_size;
1421 if (size <= 32)
1423 G.stats.total_overhead_under32 += overhead;
1424 G.stats.total_allocated_under32 += object_size;
1426 if (size <= 64)
1428 G.stats.total_overhead_under64 += overhead;
1429 G.stats.total_allocated_under64 += object_size;
1431 if (size <= 128)
1433 G.stats.total_overhead_under128 += overhead;
1434 G.stats.total_allocated_under128 += object_size;
1438 if (GGC_DEBUG_LEVEL >= 3)
1439 fprintf (G.debug_file,
1440 "Allocating object, requested size=%lu, actual=%lu at %p on %p\n",
1441 (unsigned long) size, (unsigned long) object_size, result,
1442 (void *) entry);
1444 return result;
1447 /* Mark function for strings. */
1449 void
1450 gt_ggc_m_S (const void *p)
1452 page_entry *entry;
1453 unsigned bit, word;
1454 unsigned long mask;
1455 unsigned long offset;
1457 if (!p || !ggc_allocated_p (p))
1458 return;
1460 /* Look up the page on which the object is alloced. . */
1461 entry = lookup_page_table_entry (p);
1462 gcc_assert (entry);
1464 /* Calculate the index of the object on the page; this is its bit
1465 position in the in_use_p bitmap. Note that because a char* might
1466 point to the middle of an object, we need special code here to
1467 make sure P points to the start of an object. */
1468 offset = ((const char *) p - entry->page) % object_size_table[entry->order];
1469 if (offset)
1471 /* Here we've seen a char* which does not point to the beginning
1472 of an allocated object. We assume it points to the middle of
1473 a STRING_CST. */
1474 gcc_assert (offset == offsetof (struct tree_string, str));
1475 p = ((const char *) p) - offset;
1476 gt_ggc_mx_lang_tree_node (CONST_CAST (void *, p));
1477 return;
1480 bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1481 word = bit / HOST_BITS_PER_LONG;
1482 mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
1484 /* If the bit was previously set, skip it. */
1485 if (entry->in_use_p[word] & mask)
1486 return;
1488 /* Otherwise set it, and decrement the free object count. */
1489 entry->in_use_p[word] |= mask;
1490 entry->num_free_objects -= 1;
1492 if (GGC_DEBUG_LEVEL >= 4)
1493 fprintf (G.debug_file, "Marking %p\n", p);
1495 return;
1499 /* User-callable entry points for marking string X. */
1501 void
1502 gt_ggc_mx (const char *& x)
1504 gt_ggc_m_S (x);
1507 void
1508 gt_ggc_mx (unsigned char *& x)
1510 gt_ggc_m_S (x);
1513 void
1514 gt_ggc_mx (unsigned char& x ATTRIBUTE_UNUSED)
1518 /* If P is not marked, marks it and return false. Otherwise return true.
1519 P must have been allocated by the GC allocator; it mustn't point to
1520 static objects, stack variables, or memory allocated with malloc. */
1523 ggc_set_mark (const void *p)
1525 page_entry *entry;
1526 unsigned bit, word;
1527 unsigned long mask;
1529 /* Look up the page on which the object is alloced. If the object
1530 wasn't allocated by the collector, we'll probably die. */
1531 entry = lookup_page_table_entry (p);
1532 gcc_assert (entry);
1534 /* Calculate the index of the object on the page; this is its bit
1535 position in the in_use_p bitmap. */
1536 bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1537 word = bit / HOST_BITS_PER_LONG;
1538 mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
1540 /* If the bit was previously set, skip it. */
1541 if (entry->in_use_p[word] & mask)
1542 return 1;
1544 /* Otherwise set it, and decrement the free object count. */
1545 entry->in_use_p[word] |= mask;
1546 entry->num_free_objects -= 1;
1548 if (GGC_DEBUG_LEVEL >= 4)
1549 fprintf (G.debug_file, "Marking %p\n", p);
1551 return 0;
1554 /* Return 1 if P has been marked, zero otherwise.
1555 P must have been allocated by the GC allocator; it mustn't point to
1556 static objects, stack variables, or memory allocated with malloc. */
1559 ggc_marked_p (const void *p)
1561 page_entry *entry;
1562 unsigned bit, word;
1563 unsigned long mask;
1565 /* Look up the page on which the object is alloced. If the object
1566 wasn't allocated by the collector, we'll probably die. */
1567 entry = lookup_page_table_entry (p);
1568 gcc_assert (entry);
1570 /* Calculate the index of the object on the page; this is its bit
1571 position in the in_use_p bitmap. */
1572 bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order);
1573 word = bit / HOST_BITS_PER_LONG;
1574 mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG);
1576 return (entry->in_use_p[word] & mask) != 0;
1579 /* Return the size of the gc-able object P. */
1581 size_t
1582 ggc_get_size (const void *p)
1584 page_entry *pe = lookup_page_table_entry (p);
1585 return OBJECT_SIZE (pe->order);
1588 /* Release the memory for object P. */
1590 void
1591 ggc_free (void *p)
1593 if (in_gc)
1594 return;
1596 page_entry *pe = lookup_page_table_entry (p);
1597 size_t order = pe->order;
1598 size_t size = OBJECT_SIZE (order);
1600 if (GATHER_STATISTICS)
1601 ggc_free_overhead (p);
1603 if (GGC_DEBUG_LEVEL >= 3)
1604 fprintf (G.debug_file,
1605 "Freeing object, actual size=%lu, at %p on %p\n",
1606 (unsigned long) size, p, (void *) pe);
1608 #ifdef ENABLE_GC_CHECKING
1609 /* Poison the data, to indicate the data is garbage. */
1610 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, size));
1611 memset (p, 0xa5, size);
1612 #endif
1613 /* Let valgrind know the object is free. */
1614 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, size));
1616 #ifdef ENABLE_GC_ALWAYS_COLLECT
1617 /* In the completely-anal-checking mode, we do *not* immediately free
1618 the data, but instead verify that the data is *actually* not
1619 reachable the next time we collect. */
1621 struct free_object *fo = XNEW (struct free_object);
1622 fo->object = p;
1623 fo->next = G.free_object_list;
1624 G.free_object_list = fo;
1626 #else
1628 unsigned int bit_offset, word, bit;
1630 G.allocated -= size;
1632 /* Mark the object not-in-use. */
1633 bit_offset = OFFSET_TO_BIT (((const char *) p) - pe->page, order);
1634 word = bit_offset / HOST_BITS_PER_LONG;
1635 bit = bit_offset % HOST_BITS_PER_LONG;
1636 pe->in_use_p[word] &= ~(1UL << bit);
1638 if (pe->num_free_objects++ == 0)
1640 page_entry *p, *q;
1642 /* If the page is completely full, then it's supposed to
1643 be after all pages that aren't. Since we've freed one
1644 object from a page that was full, we need to move the
1645 page to the head of the list.
1647 PE is the node we want to move. Q is the previous node
1648 and P is the next node in the list. */
1649 q = pe->prev;
1650 if (q && q->num_free_objects == 0)
1652 p = pe->next;
1654 q->next = p;
1656 /* If PE was at the end of the list, then Q becomes the
1657 new end of the list. If PE was not the end of the
1658 list, then we need to update the PREV field for P. */
1659 if (!p)
1660 G.page_tails[order] = q;
1661 else
1662 p->prev = q;
1664 /* Move PE to the head of the list. */
1665 pe->next = G.pages[order];
1666 pe->prev = NULL;
1667 G.pages[order]->prev = pe;
1668 G.pages[order] = pe;
1671 /* Reset the hint bit to point to the only free object. */
1672 pe->next_bit_hint = bit_offset;
1675 #endif
1678 /* Subroutine of init_ggc which computes the pair of numbers used to
1679 perform division by OBJECT_SIZE (order) and fills in inverse_table[].
1681 This algorithm is taken from Granlund and Montgomery's paper
1682 "Division by Invariant Integers using Multiplication"
1683 (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
1684 constants). */
1686 static void
1687 compute_inverse (unsigned order)
1689 size_t size, inv;
1690 unsigned int e;
1692 size = OBJECT_SIZE (order);
1693 e = 0;
1694 while (size % 2 == 0)
1696 e++;
1697 size >>= 1;
1700 inv = size;
1701 while (inv * size != 1)
1702 inv = inv * (2 - inv*size);
1704 DIV_MULT (order) = inv;
1705 DIV_SHIFT (order) = e;
1708 /* Initialize the ggc-mmap allocator. */
1709 void
1710 init_ggc (void)
1712 static bool init_p = false;
1713 unsigned order;
1715 if (init_p)
1716 return;
1717 init_p = true;
1719 G.pagesize = getpagesize ();
1720 G.lg_pagesize = exact_log2 (G.pagesize);
1722 #ifdef HAVE_MMAP_DEV_ZERO
1723 G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
1724 if (G.dev_zero_fd == -1)
1725 internal_error ("open /dev/zero: %m");
1726 #endif
1728 #if 0
1729 G.debug_file = fopen ("ggc-mmap.debug", "w");
1730 #else
1731 G.debug_file = stdout;
1732 #endif
1734 #ifdef USING_MMAP
1735 /* StunOS has an amazing off-by-one error for the first mmap allocation
1736 after fiddling with RLIMIT_STACK. The result, as hard as it is to
1737 believe, is an unaligned page allocation, which would cause us to
1738 hork badly if we tried to use it. */
1740 char *p = alloc_anon (NULL, G.pagesize, true);
1741 struct page_entry *e;
1742 if ((uintptr_t)p & (G.pagesize - 1))
1744 /* How losing. Discard this one and try another. If we still
1745 can't get something useful, give up. */
1747 p = alloc_anon (NULL, G.pagesize, true);
1748 gcc_assert (!((uintptr_t)p & (G.pagesize - 1)));
1751 /* We have a good page, might as well hold onto it... */
1752 e = XCNEW (struct page_entry);
1753 e->bytes = G.pagesize;
1754 e->page = p;
1755 e->next = G.free_pages;
1756 G.free_pages = e;
1758 #endif
1760 /* Initialize the object size table. */
1761 for (order = 0; order < HOST_BITS_PER_PTR; ++order)
1762 object_size_table[order] = (size_t) 1 << order;
1763 for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
1765 size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR];
1767 /* If S is not a multiple of the MAX_ALIGNMENT, then round it up
1768 so that we're sure of getting aligned memory. */
1769 s = ROUND_UP (s, MAX_ALIGNMENT);
1770 object_size_table[order] = s;
1773 /* Initialize the objects-per-page and inverse tables. */
1774 for (order = 0; order < NUM_ORDERS; ++order)
1776 objects_per_page_table[order] = G.pagesize / OBJECT_SIZE (order);
1777 if (objects_per_page_table[order] == 0)
1778 objects_per_page_table[order] = 1;
1779 compute_inverse (order);
1782 /* Reset the size_lookup array to put appropriately sized objects in
1783 the special orders. All objects bigger than the previous power
1784 of two, but no greater than the special size, should go in the
1785 new order. */
1786 for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
1788 int o;
1789 int i;
1791 i = OBJECT_SIZE (order);
1792 if (i >= NUM_SIZE_LOOKUP)
1793 continue;
1795 for (o = size_lookup[i]; o == size_lookup [i]; --i)
1796 size_lookup[i] = order;
1799 G.depth_in_use = 0;
1800 G.depth_max = 10;
1801 G.depth = XNEWVEC (unsigned int, G.depth_max);
1803 G.by_depth_in_use = 0;
1804 G.by_depth_max = INITIAL_PTE_COUNT;
1805 G.by_depth = XNEWVEC (page_entry *, G.by_depth_max);
1806 G.save_in_use = XNEWVEC (unsigned long *, G.by_depth_max);
1809 /* Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P
1810 reflects reality. Recalculate NUM_FREE_OBJECTS as well. */
1812 static void
1813 ggc_recalculate_in_use_p (page_entry *p)
1815 unsigned int i;
1816 size_t num_objects;
1818 /* Because the past-the-end bit in in_use_p is always set, we
1819 pretend there is one additional object. */
1820 num_objects = OBJECTS_IN_PAGE (p) + 1;
1822 /* Reset the free object count. */
1823 p->num_free_objects = num_objects;
1825 /* Combine the IN_USE_P and SAVE_IN_USE_P arrays. */
1826 for (i = 0;
1827 i < CEIL (BITMAP_SIZE (num_objects),
1828 sizeof (*p->in_use_p));
1829 ++i)
1831 unsigned long j;
1833 /* Something is in use if it is marked, or if it was in use in a
1834 context further down the context stack. */
1835 p->in_use_p[i] |= save_in_use_p (p)[i];
1837 /* Decrement the free object count for every object allocated. */
1838 for (j = p->in_use_p[i]; j; j >>= 1)
1839 p->num_free_objects -= (j & 1);
1842 gcc_assert (p->num_free_objects < num_objects);
1845 /* Unmark all objects. */
1847 static void
1848 clear_marks (void)
1850 unsigned order;
1852 for (order = 2; order < NUM_ORDERS; order++)
1854 page_entry *p;
1856 for (p = G.pages[order]; p != NULL; p = p->next)
1858 size_t num_objects = OBJECTS_IN_PAGE (p);
1859 size_t bitmap_size = BITMAP_SIZE (num_objects + 1);
1861 /* The data should be page-aligned. */
1862 gcc_assert (!((uintptr_t) p->page & (G.pagesize - 1)));
1864 /* Pages that aren't in the topmost context are not collected;
1865 nevertheless, we need their in-use bit vectors to store GC
1866 marks. So, back them up first. */
1867 if (p->context_depth < G.context_depth)
1869 if (! save_in_use_p (p))
1870 save_in_use_p (p) = XNEWVAR (unsigned long, bitmap_size);
1871 memcpy (save_in_use_p (p), p->in_use_p, bitmap_size);
1874 /* Reset reset the number of free objects and clear the
1875 in-use bits. These will be adjusted by mark_obj. */
1876 p->num_free_objects = num_objects;
1877 memset (p->in_use_p, 0, bitmap_size);
1879 /* Make sure the one-past-the-end bit is always set. */
1880 p->in_use_p[num_objects / HOST_BITS_PER_LONG]
1881 = ((unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG));
1886 /* Check if any blocks with a registered finalizer have become unmarked. If so
1887 run the finalizer and unregister it because the block is about to be freed.
1888 Note that no garantee is made about what order finalizers will run in so
1889 touching other objects in gc memory is extremely unwise. */
1891 static void
1892 ggc_handle_finalizers ()
1894 if (G.context_depth != 0)
1895 return;
1897 unsigned length = G.finalizers.length ();
1898 for (unsigned int i = 0; i < length;)
1900 finalizer &f = G.finalizers[i];
1901 if (!ggc_marked_p (f.addr ()))
1903 f.call ();
1904 G.finalizers.unordered_remove (i);
1905 length--;
1907 else
1908 i++;
1912 length = G.vec_finalizers.length ();
1913 for (unsigned int i = 0; i < length;)
1915 vec_finalizer &f = G.vec_finalizers[i];
1916 if (!ggc_marked_p (f.addr ()))
1918 f.call ();
1919 G.vec_finalizers.unordered_remove (i);
1920 length--;
1922 else
1923 i++;
1927 /* Free all empty pages. Partially empty pages need no attention
1928 because the `mark' bit doubles as an `unused' bit. */
1930 static void
1931 sweep_pages (void)
1933 unsigned order;
1935 for (order = 2; order < NUM_ORDERS; order++)
1937 /* The last page-entry to consider, regardless of entries
1938 placed at the end of the list. */
1939 page_entry * const last = G.page_tails[order];
1941 size_t num_objects;
1942 size_t live_objects;
1943 page_entry *p, *previous;
1944 int done;
1946 p = G.pages[order];
1947 if (p == NULL)
1948 continue;
1950 previous = NULL;
1953 page_entry *next = p->next;
1955 /* Loop until all entries have been examined. */
1956 done = (p == last);
1958 num_objects = OBJECTS_IN_PAGE (p);
1960 /* Add all live objects on this page to the count of
1961 allocated memory. */
1962 live_objects = num_objects - p->num_free_objects;
1964 G.allocated += OBJECT_SIZE (order) * live_objects;
1966 /* Only objects on pages in the topmost context should get
1967 collected. */
1968 if (p->context_depth < G.context_depth)
1971 /* Remove the page if it's empty. */
1972 else if (live_objects == 0)
1974 /* If P was the first page in the list, then NEXT
1975 becomes the new first page in the list, otherwise
1976 splice P out of the forward pointers. */
1977 if (! previous)
1978 G.pages[order] = next;
1979 else
1980 previous->next = next;
1982 /* Splice P out of the back pointers too. */
1983 if (next)
1984 next->prev = previous;
1986 /* Are we removing the last element? */
1987 if (p == G.page_tails[order])
1988 G.page_tails[order] = previous;
1989 free_page (p);
1990 p = previous;
1993 /* If the page is full, move it to the end. */
1994 else if (p->num_free_objects == 0)
1996 /* Don't move it if it's already at the end. */
1997 if (p != G.page_tails[order])
1999 /* Move p to the end of the list. */
2000 p->next = NULL;
2001 p->prev = G.page_tails[order];
2002 G.page_tails[order]->next = p;
2004 /* Update the tail pointer... */
2005 G.page_tails[order] = p;
2007 /* ... and the head pointer, if necessary. */
2008 if (! previous)
2009 G.pages[order] = next;
2010 else
2011 previous->next = next;
2013 /* And update the backpointer in NEXT if necessary. */
2014 if (next)
2015 next->prev = previous;
2017 p = previous;
2021 /* If we've fallen through to here, it's a page in the
2022 topmost context that is neither full nor empty. Such a
2023 page must precede pages at lesser context depth in the
2024 list, so move it to the head. */
2025 else if (p != G.pages[order])
2027 previous->next = p->next;
2029 /* Update the backchain in the next node if it exists. */
2030 if (p->next)
2031 p->next->prev = previous;
2033 /* Move P to the head of the list. */
2034 p->next = G.pages[order];
2035 p->prev = NULL;
2036 G.pages[order]->prev = p;
2038 /* Update the head pointer. */
2039 G.pages[order] = p;
2041 /* Are we moving the last element? */
2042 if (G.page_tails[order] == p)
2043 G.page_tails[order] = previous;
2044 p = previous;
2047 previous = p;
2048 p = next;
2050 while (! done);
2052 /* Now, restore the in_use_p vectors for any pages from contexts
2053 other than the current one. */
2054 for (p = G.pages[order]; p; p = p->next)
2055 if (p->context_depth != G.context_depth)
2056 ggc_recalculate_in_use_p (p);
2060 #ifdef ENABLE_GC_CHECKING
2061 /* Clobber all free objects. */
2063 static void
2064 poison_pages (void)
2066 unsigned order;
2068 for (order = 2; order < NUM_ORDERS; order++)
2070 size_t size = OBJECT_SIZE (order);
2071 page_entry *p;
2073 for (p = G.pages[order]; p != NULL; p = p->next)
2075 size_t num_objects;
2076 size_t i;
2078 if (p->context_depth != G.context_depth)
2079 /* Since we don't do any collection for pages in pushed
2080 contexts, there's no need to do any poisoning. And
2081 besides, the IN_USE_P array isn't valid until we pop
2082 contexts. */
2083 continue;
2085 num_objects = OBJECTS_IN_PAGE (p);
2086 for (i = 0; i < num_objects; i++)
2088 size_t word, bit;
2089 word = i / HOST_BITS_PER_LONG;
2090 bit = i % HOST_BITS_PER_LONG;
2091 if (((p->in_use_p[word] >> bit) & 1) == 0)
2093 char *object = p->page + i * size;
2095 /* Keep poison-by-write when we expect to use Valgrind,
2096 so the exact same memory semantics is kept, in case
2097 there are memory errors. We override this request
2098 below. */
2099 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (object,
2100 size));
2101 memset (object, 0xa5, size);
2103 /* Drop the handle to avoid handle leak. */
2104 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
2110 #else
2111 #define poison_pages()
2112 #endif
2114 #ifdef ENABLE_GC_ALWAYS_COLLECT
2115 /* Validate that the reportedly free objects actually are. */
2117 static void
2118 validate_free_objects (void)
2120 struct free_object *f, *next, *still_free = NULL;
2122 for (f = G.free_object_list; f ; f = next)
2124 page_entry *pe = lookup_page_table_entry (f->object);
2125 size_t bit, word;
2127 bit = OFFSET_TO_BIT ((char *)f->object - pe->page, pe->order);
2128 word = bit / HOST_BITS_PER_LONG;
2129 bit = bit % HOST_BITS_PER_LONG;
2130 next = f->next;
2132 /* Make certain it isn't visible from any root. Notice that we
2133 do this check before sweep_pages merges save_in_use_p. */
2134 gcc_assert (!(pe->in_use_p[word] & (1UL << bit)));
2136 /* If the object comes from an outer context, then retain the
2137 free_object entry, so that we can verify that the address
2138 isn't live on the stack in some outer context. */
2139 if (pe->context_depth != G.context_depth)
2141 f->next = still_free;
2142 still_free = f;
2144 else
2145 free (f);
2148 G.free_object_list = still_free;
2150 #else
2151 #define validate_free_objects()
2152 #endif
2154 /* Top level mark-and-sweep routine. */
2156 void
2157 ggc_collect (void)
2159 /* Avoid frequent unnecessary work by skipping collection if the
2160 total allocations haven't expanded much since the last
2161 collection. */
2162 float allocated_last_gc =
2163 MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
2165 float min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
2166 if (G.allocated < allocated_last_gc + min_expand && !ggc_force_collect)
2167 return;
2169 timevar_push (TV_GC);
2170 if (!quiet_flag)
2171 fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
2172 if (GGC_DEBUG_LEVEL >= 2)
2173 fprintf (G.debug_file, "BEGIN COLLECTING\n");
2175 /* Zero the total allocated bytes. This will be recalculated in the
2176 sweep phase. */
2177 G.allocated = 0;
2179 /* Release the pages we freed the last time we collected, but didn't
2180 reuse in the interim. */
2181 release_pages ();
2183 /* Indicate that we've seen collections at this context depth. */
2184 G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1;
2186 invoke_plugin_callbacks (PLUGIN_GGC_START, NULL);
2188 in_gc = true;
2189 clear_marks ();
2190 ggc_mark_roots ();
2191 ggc_handle_finalizers ();
2193 if (GATHER_STATISTICS)
2194 ggc_prune_overhead_list ();
2196 poison_pages ();
2197 validate_free_objects ();
2198 sweep_pages ();
2200 in_gc = false;
2201 G.allocated_last_gc = G.allocated;
2203 invoke_plugin_callbacks (PLUGIN_GGC_END, NULL);
2205 timevar_pop (TV_GC);
2207 if (!quiet_flag)
2208 fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
2209 if (GGC_DEBUG_LEVEL >= 2)
2210 fprintf (G.debug_file, "END COLLECTING\n");
2213 /* Assume that all GGC memory is reachable and grow the limits for next collection.
2214 With checking, trigger GGC so -Q compilation outputs how much of memory really is
2215 reachable. */
2217 void
2218 ggc_grow (void)
2220 #ifndef ENABLE_CHECKING
2221 G.allocated_last_gc = MAX (G.allocated_last_gc,
2222 G.allocated);
2223 #else
2224 ggc_collect ();
2225 #endif
2226 if (!quiet_flag)
2227 fprintf (stderr, " {GC start %luk} ", (unsigned long) G.allocated / 1024);
2230 /* Print allocation statistics. */
2231 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
2232 ? (x) \
2233 : ((x) < 1024*1024*10 \
2234 ? (x) / 1024 \
2235 : (x) / (1024*1024))))
2236 #define STAT_LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
2238 void
2239 ggc_print_statistics (void)
2241 struct ggc_statistics stats;
2242 unsigned int i;
2243 size_t total_overhead = 0;
2245 /* Clear the statistics. */
2246 memset (&stats, 0, sizeof (stats));
2248 /* Make sure collection will really occur. */
2249 G.allocated_last_gc = 0;
2251 /* Collect and print the statistics common across collectors. */
2252 ggc_print_common_statistics (stderr, &stats);
2254 /* Release free pages so that we will not count the bytes allocated
2255 there as part of the total allocated memory. */
2256 release_pages ();
2258 /* Collect some information about the various sizes of
2259 allocation. */
2260 fprintf (stderr,
2261 "Memory still allocated at the end of the compilation process\n");
2262 fprintf (stderr, "%-5s %10s %10s %10s\n",
2263 "Size", "Allocated", "Used", "Overhead");
2264 for (i = 0; i < NUM_ORDERS; ++i)
2266 page_entry *p;
2267 size_t allocated;
2268 size_t in_use;
2269 size_t overhead;
2271 /* Skip empty entries. */
2272 if (!G.pages[i])
2273 continue;
2275 overhead = allocated = in_use = 0;
2277 /* Figure out the total number of bytes allocated for objects of
2278 this size, and how many of them are actually in use. Also figure
2279 out how much memory the page table is using. */
2280 for (p = G.pages[i]; p; p = p->next)
2282 allocated += p->bytes;
2283 in_use +=
2284 (OBJECTS_IN_PAGE (p) - p->num_free_objects) * OBJECT_SIZE (i);
2286 overhead += (sizeof (page_entry) - sizeof (long)
2287 + BITMAP_SIZE (OBJECTS_IN_PAGE (p) + 1));
2289 fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
2290 (unsigned long) OBJECT_SIZE (i),
2291 SCALE (allocated), STAT_LABEL (allocated),
2292 SCALE (in_use), STAT_LABEL (in_use),
2293 SCALE (overhead), STAT_LABEL (overhead));
2294 total_overhead += overhead;
2296 fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
2297 SCALE (G.bytes_mapped), STAT_LABEL (G.bytes_mapped),
2298 SCALE (G.allocated), STAT_LABEL (G.allocated),
2299 SCALE (total_overhead), STAT_LABEL (total_overhead));
2301 if (GATHER_STATISTICS)
2303 fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
2305 fprintf (stderr, "Total Overhead: %10" HOST_LONG_LONG_FORMAT "d\n",
2306 G.stats.total_overhead);
2307 fprintf (stderr, "Total Allocated: %10" HOST_LONG_LONG_FORMAT "d\n",
2308 G.stats.total_allocated);
2310 fprintf (stderr, "Total Overhead under 32B: %10" HOST_LONG_LONG_FORMAT "d\n",
2311 G.stats.total_overhead_under32);
2312 fprintf (stderr, "Total Allocated under 32B: %10" HOST_LONG_LONG_FORMAT "d\n",
2313 G.stats.total_allocated_under32);
2314 fprintf (stderr, "Total Overhead under 64B: %10" HOST_LONG_LONG_FORMAT "d\n",
2315 G.stats.total_overhead_under64);
2316 fprintf (stderr, "Total Allocated under 64B: %10" HOST_LONG_LONG_FORMAT "d\n",
2317 G.stats.total_allocated_under64);
2318 fprintf (stderr, "Total Overhead under 128B: %10" HOST_LONG_LONG_FORMAT "d\n",
2319 G.stats.total_overhead_under128);
2320 fprintf (stderr, "Total Allocated under 128B: %10" HOST_LONG_LONG_FORMAT "d\n",
2321 G.stats.total_allocated_under128);
2323 for (i = 0; i < NUM_ORDERS; i++)
2324 if (G.stats.total_allocated_per_order[i])
2326 fprintf (stderr, "Total Overhead page size %7lu: %10" HOST_LONG_LONG_FORMAT "d\n",
2327 (unsigned long) OBJECT_SIZE (i),
2328 G.stats.total_overhead_per_order[i]);
2329 fprintf (stderr, "Total Allocated page size %7lu: %10" HOST_LONG_LONG_FORMAT "d\n",
2330 (unsigned long) OBJECT_SIZE (i),
2331 G.stats.total_allocated_per_order[i]);
2336 struct ggc_pch_ondisk
2338 unsigned totals[NUM_ORDERS];
2341 struct ggc_pch_data
2343 struct ggc_pch_ondisk d;
2344 uintptr_t base[NUM_ORDERS];
2345 size_t written[NUM_ORDERS];
2348 struct ggc_pch_data *
2349 init_ggc_pch (void)
2351 return XCNEW (struct ggc_pch_data);
2354 void
2355 ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2356 size_t size, bool is_string ATTRIBUTE_UNUSED)
2358 unsigned order;
2360 if (size < NUM_SIZE_LOOKUP)
2361 order = size_lookup[size];
2362 else
2364 order = 10;
2365 while (size > OBJECT_SIZE (order))
2366 order++;
2369 d->d.totals[order]++;
2372 size_t
2373 ggc_pch_total_size (struct ggc_pch_data *d)
2375 size_t a = 0;
2376 unsigned i;
2378 for (i = 0; i < NUM_ORDERS; i++)
2379 a += PAGE_ALIGN (d->d.totals[i] * OBJECT_SIZE (i));
2380 return a;
2383 void
2384 ggc_pch_this_base (struct ggc_pch_data *d, void *base)
2386 uintptr_t a = (uintptr_t) base;
2387 unsigned i;
2389 for (i = 0; i < NUM_ORDERS; i++)
2391 d->base[i] = a;
2392 a += PAGE_ALIGN (d->d.totals[i] * OBJECT_SIZE (i));
2397 char *
2398 ggc_pch_alloc_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2399 size_t size, bool is_string ATTRIBUTE_UNUSED)
2401 unsigned order;
2402 char *result;
2404 if (size < NUM_SIZE_LOOKUP)
2405 order = size_lookup[size];
2406 else
2408 order = 10;
2409 while (size > OBJECT_SIZE (order))
2410 order++;
2413 result = (char *) d->base[order];
2414 d->base[order] += OBJECT_SIZE (order);
2415 return result;
2418 void
2419 ggc_pch_prepare_write (struct ggc_pch_data *d ATTRIBUTE_UNUSED,
2420 FILE *f ATTRIBUTE_UNUSED)
2422 /* Nothing to do. */
2425 void
2426 ggc_pch_write_object (struct ggc_pch_data *d,
2427 FILE *f, void *x, void *newx ATTRIBUTE_UNUSED,
2428 size_t size, bool is_string ATTRIBUTE_UNUSED)
2430 unsigned order;
2431 static const char emptyBytes[256] = { 0 };
2433 if (size < NUM_SIZE_LOOKUP)
2434 order = size_lookup[size];
2435 else
2437 order = 10;
2438 while (size > OBJECT_SIZE (order))
2439 order++;
2442 if (fwrite (x, size, 1, f) != 1)
2443 fatal_error ("can%'t write PCH file: %m");
2445 /* If SIZE is not the same as OBJECT_SIZE(order), then we need to pad the
2446 object out to OBJECT_SIZE(order). This happens for strings. */
2448 if (size != OBJECT_SIZE (order))
2450 unsigned padding = OBJECT_SIZE (order) - size;
2452 /* To speed small writes, we use a nulled-out array that's larger
2453 than most padding requests as the source for our null bytes. This
2454 permits us to do the padding with fwrite() rather than fseek(), and
2455 limits the chance the OS may try to flush any outstanding writes. */
2456 if (padding <= sizeof (emptyBytes))
2458 if (fwrite (emptyBytes, 1, padding, f) != padding)
2459 fatal_error ("can%'t write PCH file");
2461 else
2463 /* Larger than our buffer? Just default to fseek. */
2464 if (fseek (f, padding, SEEK_CUR) != 0)
2465 fatal_error ("can%'t write PCH file");
2469 d->written[order]++;
2470 if (d->written[order] == d->d.totals[order]
2471 && fseek (f, ROUND_UP_VALUE (d->d.totals[order] * OBJECT_SIZE (order),
2472 G.pagesize),
2473 SEEK_CUR) != 0)
2474 fatal_error ("can%'t write PCH file: %m");
2477 void
2478 ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
2480 if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
2481 fatal_error ("can%'t write PCH file: %m");
2482 free (d);
2485 /* Move the PCH PTE entries just added to the end of by_depth, to the
2486 front. */
2488 static void
2489 move_ptes_to_front (int count_old_page_tables, int count_new_page_tables)
2491 unsigned i;
2493 /* First, we swap the new entries to the front of the varrays. */
2494 page_entry **new_by_depth;
2495 unsigned long **new_save_in_use;
2497 new_by_depth = XNEWVEC (page_entry *, G.by_depth_max);
2498 new_save_in_use = XNEWVEC (unsigned long *, G.by_depth_max);
2500 memcpy (&new_by_depth[0],
2501 &G.by_depth[count_old_page_tables],
2502 count_new_page_tables * sizeof (void *));
2503 memcpy (&new_by_depth[count_new_page_tables],
2504 &G.by_depth[0],
2505 count_old_page_tables * sizeof (void *));
2506 memcpy (&new_save_in_use[0],
2507 &G.save_in_use[count_old_page_tables],
2508 count_new_page_tables * sizeof (void *));
2509 memcpy (&new_save_in_use[count_new_page_tables],
2510 &G.save_in_use[0],
2511 count_old_page_tables * sizeof (void *));
2513 free (G.by_depth);
2514 free (G.save_in_use);
2516 G.by_depth = new_by_depth;
2517 G.save_in_use = new_save_in_use;
2519 /* Now update all the index_by_depth fields. */
2520 for (i = G.by_depth_in_use; i > 0; --i)
2522 page_entry *p = G.by_depth[i-1];
2523 p->index_by_depth = i-1;
2526 /* And last, we update the depth pointers in G.depth. The first
2527 entry is already 0, and context 0 entries always start at index
2528 0, so there is nothing to update in the first slot. We need a
2529 second slot, only if we have old ptes, and if we do, they start
2530 at index count_new_page_tables. */
2531 if (count_old_page_tables)
2532 push_depth (count_new_page_tables);
2535 void
2536 ggc_pch_read (FILE *f, void *addr)
2538 struct ggc_pch_ondisk d;
2539 unsigned i;
2540 char *offs = (char *) addr;
2541 unsigned long count_old_page_tables;
2542 unsigned long count_new_page_tables;
2544 count_old_page_tables = G.by_depth_in_use;
2546 /* We've just read in a PCH file. So, every object that used to be
2547 allocated is now free. */
2548 clear_marks ();
2549 #ifdef ENABLE_GC_CHECKING
2550 poison_pages ();
2551 #endif
2552 /* Since we free all the allocated objects, the free list becomes
2553 useless. Validate it now, which will also clear it. */
2554 validate_free_objects ();
2556 /* No object read from a PCH file should ever be freed. So, set the
2557 context depth to 1, and set the depth of all the currently-allocated
2558 pages to be 1 too. PCH pages will have depth 0. */
2559 gcc_assert (!G.context_depth);
2560 G.context_depth = 1;
2561 for (i = 0; i < NUM_ORDERS; i++)
2563 page_entry *p;
2564 for (p = G.pages[i]; p != NULL; p = p->next)
2565 p->context_depth = G.context_depth;
2568 /* Allocate the appropriate page-table entries for the pages read from
2569 the PCH file. */
2570 if (fread (&d, sizeof (d), 1, f) != 1)
2571 fatal_error ("can%'t read PCH file: %m");
2573 for (i = 0; i < NUM_ORDERS; i++)
2575 struct page_entry *entry;
2576 char *pte;
2577 size_t bytes;
2578 size_t num_objs;
2579 size_t j;
2581 if (d.totals[i] == 0)
2582 continue;
2584 bytes = PAGE_ALIGN (d.totals[i] * OBJECT_SIZE (i));
2585 num_objs = bytes / OBJECT_SIZE (i);
2586 entry = XCNEWVAR (struct page_entry, (sizeof (struct page_entry)
2587 - sizeof (long)
2588 + BITMAP_SIZE (num_objs + 1)));
2589 entry->bytes = bytes;
2590 entry->page = offs;
2591 entry->context_depth = 0;
2592 offs += bytes;
2593 entry->num_free_objects = 0;
2594 entry->order = i;
2596 for (j = 0;
2597 j + HOST_BITS_PER_LONG <= num_objs + 1;
2598 j += HOST_BITS_PER_LONG)
2599 entry->in_use_p[j / HOST_BITS_PER_LONG] = -1;
2600 for (; j < num_objs + 1; j++)
2601 entry->in_use_p[j / HOST_BITS_PER_LONG]
2602 |= 1L << (j % HOST_BITS_PER_LONG);
2604 for (pte = entry->page;
2605 pte < entry->page + entry->bytes;
2606 pte += G.pagesize)
2607 set_page_table_entry (pte, entry);
2609 if (G.page_tails[i] != NULL)
2610 G.page_tails[i]->next = entry;
2611 else
2612 G.pages[i] = entry;
2613 G.page_tails[i] = entry;
2615 /* We start off by just adding all the new information to the
2616 end of the varrays, later, we will move the new information
2617 to the front of the varrays, as the PCH page tables are at
2618 context 0. */
2619 push_by_depth (entry, 0);
2622 /* Now, we update the various data structures that speed page table
2623 handling. */
2624 count_new_page_tables = G.by_depth_in_use - count_old_page_tables;
2626 move_ptes_to_front (count_old_page_tables, count_new_page_tables);
2628 /* Update the statistics. */
2629 G.allocated = G.allocated_last_gc = offs - (char *)addr;