1 /* "Bag-of-pages" zone garbage collector for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3 Contributed by Richard Henderson (rth@redhat.com) and Daniel Berlin
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
39 #ifdef ENABLE_VALGRIND_CHECKING
40 # ifdef HAVE_VALGRIND_MEMCHECK_H
41 # include <valgrind/memcheck.h>
42 # elif defined HAVE_MEMCHECK_H
43 # include <memcheck.h>
45 # include <valgrind.h>
48 /* Avoid #ifdef:s when we can help it. */
49 #define VALGRIND_DISCARD(x)
50 #define VALGRIND_MALLOCLIKE_BLOCK(w,x,y,z)
51 #define VALGRIND_FREELIKE_BLOCK(x,y)
53 /* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
54 file open. Prefer either to valloc. */
56 # undef HAVE_MMAP_DEV_ZERO
58 # include <sys/mman.h>
60 # define MAP_FAILED -1
62 # if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
63 # define MAP_ANONYMOUS MAP_ANON
69 #ifdef HAVE_MMAP_DEV_ZERO
71 # include <sys/mman.h>
73 # define MAP_FAILED -1
80 #error "Zone collector requires mmap"
83 #if (GCC_VERSION < 3001)
84 #define prefetch(X) ((void) X)
86 #define prefetch(X) __builtin_prefetch (X)
90 If we track inter-zone pointers, we can mark single zones at a
92 If we have a zone where we guarantee no inter-zone pointers, we
93 could mark that zone separately.
94 The garbage zone should not be marked, and we should return 1 in
95 ggc_set_mark for any object in the garbage zone, which cuts off
99 This garbage-collecting allocator segregates objects into zones.
100 It also segregates objects into "large" and "small" bins. Large
101 objects are greater or equal to page size.
103 Pages for small objects are broken up into chunks, each of which
104 are described by a struct alloc_chunk. One can walk over all
105 chunks on the page by adding the chunk size to the chunk's data
106 address. The free space for a page exists in the free chunk bins.
108 Each page-entry also has a context depth, which is used to track
109 pushing and popping of allocation contexts. Only objects allocated
110 in the current (highest-numbered) context may be collected.
112 Empty pages (of all sizes) are kept on a single page cache list,
113 and are considered first when new pages are required; they are
114 deallocated at the start of the next collection if they haven't
115 been recycled by then. */
117 /* Define GGC_DEBUG_LEVEL to print debugging information.
118 0: No debugging output.
119 1: GC statistics only.
120 2: Page-entry allocations/deallocations as well.
121 3: Object allocations as well.
122 4: Object marks as well. */
123 #define GGC_DEBUG_LEVEL (0)
125 #ifndef HOST_BITS_PER_PTR
126 #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
128 #ifdef COOKIE_CHECKING
129 #define CHUNK_MAGIC 0x95321123
130 #define DEADCHUNK_MAGIC 0x12817317
133 /* This structure manages small chunks. When the chunk is free, it's
134 linked with other chunks via free_next. When the chunk is allocated,
135 the data starts at u. Large chunks are allocated one at a time to
136 their own page, and so don't come in here.
138 The "type" field is a placeholder for a future change to do
139 generational collection. At present it is 0 when free and
140 and 1 when allocated. */
143 #ifdef COOKIE_CHECKING
147 unsigned int typecode
:14;
148 unsigned int large
:1;
149 unsigned int size
:15;
152 struct alloc_chunk
*next_free
;
155 /* Make sure the data is sufficiently aligned. */
156 HOST_WIDEST_INT align_i
;
157 #ifdef HAVE_LONG_DOUBLE
163 } __attribute__ ((packed
));
165 #define CHUNK_OVERHEAD (offsetof (struct alloc_chunk, u))
167 /* We maintain several bins of free lists for chunks for very small
168 objects. We never exhaustively search other bins -- if we don't
169 find one of the proper size, we allocate from the "larger" bin. */
171 /* Decreasing the number of free bins increases the time it takes to allocate.
172 Similar with increasing max_free_bin_size without increasing num_free_bins.
174 After much histogramming of allocation sizes and time spent on gc,
175 on a PowerPC G4 7450 - 667 mhz, and a Pentium 4 - 2.8ghz,
176 these were determined to be the optimal values. */
177 #define NUM_FREE_BINS 64
178 #define MAX_FREE_BIN_SIZE 256
179 #define FREE_BIN_DELTA (MAX_FREE_BIN_SIZE / NUM_FREE_BINS)
180 #define SIZE_BIN_UP(SIZE) (((SIZE) + FREE_BIN_DELTA - 1) / FREE_BIN_DELTA)
181 #define SIZE_BIN_DOWN(SIZE) ((SIZE) / FREE_BIN_DELTA)
183 /* Marker used as chunk->size for a large object. Should correspond
184 to the size of the bitfield above. */
185 #define LARGE_OBJECT_SIZE 0x7fff
187 /* We use this structure to determine the alignment required for
188 allocations. For power-of-two sized allocations, that's not a
189 problem, but it does matter for odd-sized allocations. */
191 struct max_alignment
{
195 #ifdef HAVE_LONG_DOUBLE
203 /* The biggest alignment required. */
205 #define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
207 /* Compute the smallest nonnegative number which when added to X gives
210 #define ROUND_UP_VALUE(x, f) ((f) - 1 - ((f) - 1 + (x)) % (f))
212 /* Compute the smallest multiple of F that is >= X. */
214 #define ROUND_UP(x, f) (CEIL (x, f) * (f))
217 /* A page_entry records the status of an allocation page. */
218 typedef struct page_entry
220 /* The next page-entry with objects of the same size, or NULL if
221 this is the last page-entry. */
222 struct page_entry
*next
;
224 /* The number of bytes allocated. (This will always be a multiple
225 of the host system page size.) */
228 /* How many collections we've survived. */
231 /* The address at which the memory is allocated. */
234 /* Context depth of this page. */
235 unsigned short context_depth
;
237 /* Does this page contain small objects, or one large object? */
240 /* The zone that this page entry belongs to. */
241 struct alloc_zone
*zone
;
245 /* The global variables. */
246 static struct globals
248 /* The linked list of zones. */
249 struct alloc_zone
*zones
;
251 /* The system's page size. */
255 /* A file descriptor open to /dev/zero for reading. */
256 #if defined (HAVE_MMAP_DEV_ZERO)
260 /* The file descriptor for debugging output. */
264 /* The zone allocation structure. */
267 /* Name of the zone. */
270 /* Linked list of pages in a zone. */
273 /* Linked lists of free storage. Slots 1 ... NUM_FREE_BINS have chunks of size
274 FREE_BIN_DELTA. All other chunks are in slot 0. */
275 struct alloc_chunk
*free_chunks
[NUM_FREE_BINS
+ 1];
277 /* Bytes currently allocated. */
280 /* Bytes currently allocated at the end of the last collection. */
281 size_t allocated_last_gc
;
283 /* Total amount of memory mapped. */
286 /* Bit N set if any allocations have been done at context depth N. */
287 unsigned long context_depth_allocations
;
289 /* Bit N set if any collections have been done at context depth N. */
290 unsigned long context_depth_collections
;
292 /* The current depth in the context stack. */
293 unsigned short context_depth
;
295 /* A cache of free system pages. */
296 page_entry
*free_pages
;
298 /* Next zone in the linked list of zones. */
299 struct alloc_zone
*next_zone
;
301 /* True if this zone was collected during this collection. */
304 /* True if this zone should be destroyed after the next collection. */
308 struct alloc_zone
*rtl_zone
;
309 struct alloc_zone
*garbage_zone
;
310 struct alloc_zone
*tree_zone
;
312 /* Allocate pages in chunks of this size, to throttle calls to memory
313 allocation routines. The first page is used, the rest go onto the
314 free list. This cannot be larger than HOST_BITS_PER_INT for the
315 in_use bitmask for page_group. */
316 #define GGC_QUIRE_SIZE 16
318 static int ggc_allocated_p (const void *);
320 static char *alloc_anon (char *, size_t, struct alloc_zone
*);
322 static struct page_entry
* alloc_small_page ( struct alloc_zone
*);
323 static struct page_entry
* alloc_large_page (size_t, struct alloc_zone
*);
324 static void free_chunk (struct alloc_chunk
*, size_t, struct alloc_zone
*);
325 static void free_page (struct page_entry
*);
326 static void release_pages (struct alloc_zone
*);
327 static void sweep_pages (struct alloc_zone
*);
328 static void * ggc_alloc_zone_1 (size_t, struct alloc_zone
*, short);
329 static bool ggc_collect_1 (struct alloc_zone
*, bool);
330 static void check_cookies (void);
333 /* Returns nonzero if P was allocated in GC'able memory. */
336 ggc_allocated_p (const void *p
)
338 struct alloc_chunk
*chunk
;
339 chunk
= (struct alloc_chunk
*) ((char *)p
- CHUNK_OVERHEAD
);
340 #ifdef COOKIE_CHECKING
341 if (chunk
->magic
!= CHUNK_MAGIC
)
344 if (chunk
->type
== 1)
351 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
352 (if non-null). The ifdef structure here is intended to cause a
353 compile error unless exactly one of the HAVE_* is defined. */
356 alloc_anon (char *pref ATTRIBUTE_UNUSED
, size_t size
, struct alloc_zone
*zone
)
358 #ifdef HAVE_MMAP_ANON
359 char *page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
360 MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
362 #ifdef HAVE_MMAP_DEV_ZERO
363 char *page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
364 MAP_PRIVATE
, G
.dev_zero_fd
, 0);
366 VALGRIND_MALLOCLIKE_BLOCK(page
, size
, 0, 0);
368 if (page
== (char *) MAP_FAILED
)
370 perror ("virtual memory exhausted");
371 exit (FATAL_EXIT_CODE
);
374 /* Remember that we allocated this memory. */
375 zone
->bytes_mapped
+= size
;
376 /* Pretend we don't have access to the allocated pages. We'll enable
377 access to smaller pieces of the area in ggc_alloc. Discard the
378 handle to avoid handle leak. */
379 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (page
, size
));
384 /* Allocate a new page for allocating objects of size 2^ORDER,
385 and return an entry for it. */
387 static inline struct page_entry
*
388 alloc_small_page (struct alloc_zone
*zone
)
390 struct page_entry
*entry
;
395 /* Check the list of free pages for one we can use. */
396 entry
= zone
->free_pages
;
399 /* Recycle the allocated memory from this page ... */
400 zone
->free_pages
= entry
->next
;
408 /* We want just one page. Allocate a bunch of them and put the
409 extras on the freelist. (Can only do this optimization with
410 mmap for backing store.) */
411 struct page_entry
*e
, *f
= zone
->free_pages
;
414 page
= alloc_anon (NULL
, G
.pagesize
* GGC_QUIRE_SIZE
, zone
);
416 /* This loop counts down so that the chain will be in ascending
418 for (i
= GGC_QUIRE_SIZE
- 1; i
>= 1; i
--)
420 e
= (struct page_entry
*) xmalloc (sizeof (struct page_entry
));
421 e
->bytes
= G
.pagesize
;
422 e
->page
= page
+ (i
<< G
.lg_pagesize
);
427 zone
->free_pages
= f
;
431 entry
= (struct page_entry
*) xmalloc (sizeof (struct page_entry
));
434 entry
->bytes
= G
.pagesize
;
436 entry
->context_depth
= zone
->context_depth
;
437 entry
->large_p
= false;
439 zone
->context_depth_allocations
|= (unsigned long)1 << zone
->context_depth
;
441 if (GGC_DEBUG_LEVEL
>= 2)
442 fprintf (G
.debug_file
,
443 "Allocating %s page at %p, data %p-%p\n", entry
->zone
->name
,
444 (PTR
) entry
, page
, page
+ G
.pagesize
- 1);
448 /* Compute the smallest multiple of F that is >= X. */
450 #define ROUND_UP(x, f) (CEIL (x, f) * (f))
452 /* Allocate a large page of size SIZE in ZONE. */
454 static inline struct page_entry
*
455 alloc_large_page (size_t size
, struct alloc_zone
*zone
)
457 struct page_entry
*entry
;
459 size
= ROUND_UP (size
, 1024);
460 page
= (char *) xmalloc (size
+ CHUNK_OVERHEAD
+ sizeof (struct page_entry
));
461 entry
= (struct page_entry
*) (page
+ size
+ CHUNK_OVERHEAD
);
466 entry
->context_depth
= zone
->context_depth
;
467 entry
->large_p
= true;
469 zone
->context_depth_allocations
|= (unsigned long)1 << zone
->context_depth
;
471 if (GGC_DEBUG_LEVEL
>= 2)
472 fprintf (G
.debug_file
,
473 "Allocating %s large page at %p, data %p-%p\n", entry
->zone
->name
,
474 (PTR
) entry
, page
, page
+ size
- 1);
480 /* For a page that is no longer needed, put it on the free page list. */
483 free_page (page_entry
*entry
)
485 if (GGC_DEBUG_LEVEL
>= 2)
486 fprintf (G
.debug_file
,
487 "Deallocating %s page at %p, data %p-%p\n", entry
->zone
->name
, (PTR
) entry
,
488 entry
->page
, entry
->page
+ entry
->bytes
- 1);
493 VALGRIND_FREELIKE_BLOCK (entry
->page
, entry
->bytes
);
497 /* Mark the page as inaccessible. Discard the handle to
498 avoid handle leak. */
499 VALGRIND_DISCARD (VALGRIND_MAKE_NOACCESS (entry
->page
, entry
->bytes
));
501 entry
->next
= entry
->zone
->free_pages
;
502 entry
->zone
->free_pages
= entry
;
506 /* Release the free page cache to the system. */
509 release_pages (struct alloc_zone
*zone
)
512 page_entry
*p
, *next
;
516 /* Gather up adjacent pages so they are unmapped together. */
517 p
= zone
->free_pages
;
527 while (p
&& p
->page
== start
+ len
)
536 zone
->bytes_mapped
-= len
;
539 zone
->free_pages
= NULL
;
543 /* Place CHUNK of size SIZE on the free list for ZONE. */
546 free_chunk (struct alloc_chunk
*chunk
, size_t size
, struct alloc_zone
*zone
)
550 bin
= SIZE_BIN_DOWN (size
);
553 if (bin
> NUM_FREE_BINS
)
555 #ifdef COOKIE_CHECKING
556 if (chunk
->magic
!= CHUNK_MAGIC
&& chunk
->magic
!= DEADCHUNK_MAGIC
)
558 chunk
->magic
= DEADCHUNK_MAGIC
;
560 chunk
->u
.next_free
= zone
->free_chunks
[bin
];
561 zone
->free_chunks
[bin
] = chunk
;
562 if (GGC_DEBUG_LEVEL
>= 3)
563 fprintf (G
.debug_file
, "Deallocating object, chunk=%p\n", (void *)chunk
);
564 VALGRIND_DISCARD (VALGRIND_MAKE_READABLE (chunk
, sizeof (struct alloc_chunk
)));
567 /* Allocate a chunk of memory of SIZE bytes. */
570 ggc_alloc_zone_1 (size_t size
, struct alloc_zone
*zone
, short type
)
574 struct page_entry
*entry
;
575 struct alloc_chunk
*chunk
, *lchunk
, **pp
;
578 /* Align size, so that we're assured of aligned allocations. */
579 if (size
< FREE_BIN_DELTA
)
580 size
= FREE_BIN_DELTA
;
581 size
= (size
+ MAX_ALIGNMENT
- 1) & -MAX_ALIGNMENT
;
583 /* Large objects are handled specially. */
584 if (size
>= G
.pagesize
- 2*CHUNK_OVERHEAD
- FREE_BIN_DELTA
)
586 size
= ROUND_UP (size
, 1024);
587 entry
= alloc_large_page (size
, zone
);
589 entry
->next
= entry
->zone
->pages
;
590 entry
->zone
->pages
= entry
;
592 chunk
= (struct alloc_chunk
*) entry
->page
;
593 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk
, sizeof (struct alloc_chunk
)));
595 chunk
->size
= CEIL (size
, 1024);
600 /* First look for a tiny object already segregated into its own
602 bin
= SIZE_BIN_UP (size
);
603 if (bin
<= NUM_FREE_BINS
)
605 chunk
= zone
->free_chunks
[bin
];
608 zone
->free_chunks
[bin
] = chunk
->u
.next_free
;
609 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk
, sizeof (struct alloc_chunk
)));
614 /* Failing that, look through the "other" bucket for a chunk
615 that is large enough. */
616 pp
= &(zone
->free_chunks
[0]);
618 while (chunk
&& chunk
->size
< size
)
620 pp
= &chunk
->u
.next_free
;
624 /* Failing that, allocate new storage. */
627 entry
= alloc_small_page (zone
);
628 entry
->next
= entry
->zone
->pages
;
629 entry
->zone
->pages
= entry
;
631 chunk
= (struct alloc_chunk
*) entry
->page
;
632 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk
, sizeof (struct alloc_chunk
)));
633 chunk
->size
= G
.pagesize
- CHUNK_OVERHEAD
;
638 *pp
= chunk
->u
.next_free
;
639 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk
, sizeof (struct alloc_chunk
)));
642 /* Release extra memory from a chunk that's too big. */
643 lsize
= chunk
->size
- size
;
644 if (lsize
>= CHUNK_OVERHEAD
+ FREE_BIN_DELTA
)
646 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (chunk
, sizeof (struct alloc_chunk
)));
649 lsize
-= CHUNK_OVERHEAD
;
650 lchunk
= (struct alloc_chunk
*)(chunk
->u
.data
+ size
);
651 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (lchunk
, sizeof (struct alloc_chunk
)));
652 #ifdef COOKIE_CHECKING
653 lchunk
->magic
= CHUNK_MAGIC
;
657 lchunk
->size
= lsize
;
659 free_chunk (lchunk
, lsize
, zone
);
661 /* Calculate the object's address. */
663 #ifdef COOKIE_CHECKING
664 chunk
->magic
= CHUNK_MAGIC
;
668 chunk
->typecode
= type
;
669 result
= chunk
->u
.data
;
671 #ifdef ENABLE_GC_CHECKING
672 /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the
673 exact same semantics in presence of memory bugs, regardless of
674 ENABLE_VALGRIND_CHECKING. We override this request below. Drop the
675 handle to avoid handle leak. */
676 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result
, size
));
678 /* `Poison' the entire allocated object. */
679 memset (result
, 0xaf, size
);
682 /* Tell Valgrind that the memory is there, but its content isn't
683 defined. The bytes at the end of the object are still marked
685 VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (result
, size
));
687 /* Keep track of how many bytes are being allocated. This
688 information is used in deciding when to collect. */
689 zone
->allocated
+= size
+ CHUNK_OVERHEAD
;
691 if (GGC_DEBUG_LEVEL
>= 3)
692 fprintf (G
.debug_file
, "Allocating object, chunk=%p size=%lu at %p\n",
693 (void *)chunk
, (unsigned long) size
, result
);
698 /* Allocate a SIZE of chunk memory of GTE type, into an appropriate zone
702 ggc_alloc_typed (enum gt_types_enum gte
, size_t size
)
706 case gt_ggc_e_14lang_tree_node
:
707 return ggc_alloc_zone_1 (size
, tree_zone
, gte
);
709 case gt_ggc_e_7rtx_def
:
710 return ggc_alloc_zone_1 (size
, rtl_zone
, gte
);
712 case gt_ggc_e_9rtvec_def
:
713 return ggc_alloc_zone_1 (size
, rtl_zone
, gte
);
716 return ggc_alloc_zone_1 (size
, &main_zone
, gte
);
720 /* Normal ggc_alloc simply allocates into the main zone. */
723 ggc_alloc (size_t size
)
725 return ggc_alloc_zone_1 (size
, &main_zone
, -1);
728 /* Zone allocation allocates into the specified zone. */
731 ggc_alloc_zone (size_t size
, struct alloc_zone
*zone
)
733 return ggc_alloc_zone_1 (size
, zone
, -1);
736 /* If P is not marked, mark it and return false. Otherwise return true.
737 P must have been allocated by the GC allocator; it mustn't point to
738 static objects, stack variables, or memory allocated with malloc. */
741 ggc_set_mark (const void *p
)
743 struct alloc_chunk
*chunk
;
745 chunk
= (struct alloc_chunk
*) ((char *)p
- CHUNK_OVERHEAD
);
746 #ifdef COOKIE_CHECKING
747 if (chunk
->magic
!= CHUNK_MAGIC
)
754 if (GGC_DEBUG_LEVEL
>= 4)
755 fprintf (G
.debug_file
, "Marking %p\n", p
);
760 /* Return 1 if P has been marked, zero otherwise.
761 P must have been allocated by the GC allocator; it mustn't point to
762 static objects, stack variables, or memory allocated with malloc. */
765 ggc_marked_p (const void *p
)
767 struct alloc_chunk
*chunk
;
769 chunk
= (struct alloc_chunk
*) ((char *)p
- CHUNK_OVERHEAD
);
770 #ifdef COOKIE_CHECKING
771 if (chunk
->magic
!= CHUNK_MAGIC
)
777 /* Return the size of the gc-able object P. */
780 ggc_get_size (const void *p
)
782 struct alloc_chunk
*chunk
;
784 chunk
= (struct alloc_chunk
*) ((char *)p
- CHUNK_OVERHEAD
);
785 #ifdef COOKIE_CHECKING
786 if (chunk
->magic
!= CHUNK_MAGIC
)
790 return chunk
->size
* 1024;
795 /* Initialize the ggc-zone-mmap allocator. */
799 /* Set up the main zone by hand. */
800 main_zone
.name
= "Main zone";
801 G
.zones
= &main_zone
;
803 /* Allocate the default zones. */
804 rtl_zone
= new_ggc_zone ("RTL zone");
805 tree_zone
= new_ggc_zone ("Tree zone");
806 garbage_zone
= new_ggc_zone ("Garbage zone");
808 G
.pagesize
= getpagesize();
809 G
.lg_pagesize
= exact_log2 (G
.pagesize
);
810 #ifdef HAVE_MMAP_DEV_ZERO
811 G
.dev_zero_fd
= open ("/dev/zero", O_RDONLY
);
812 if (G
.dev_zero_fd
== -1)
817 G
.debug_file
= fopen ("ggc-mmap.debug", "w");
818 setlinebuf (G
.debug_file
);
820 G
.debug_file
= stdout
;
824 /* StunOS has an amazing off-by-one error for the first mmap allocation
825 after fiddling with RLIMIT_STACK. The result, as hard as it is to
826 believe, is an unaligned page allocation, which would cause us to
827 hork badly if we tried to use it. */
829 char *p
= alloc_anon (NULL
, G
.pagesize
, &main_zone
);
830 struct page_entry
*e
;
831 if ((size_t)p
& (G
.pagesize
- 1))
833 /* How losing. Discard this one and try another. If we still
834 can't get something useful, give up. */
836 p
= alloc_anon (NULL
, G
.pagesize
, &main_zone
);
837 if ((size_t)p
& (G
.pagesize
- 1))
841 /* We have a good page, might as well hold onto it... */
842 e
= (struct page_entry
*) xmalloc (sizeof (struct page_entry
));
843 e
->bytes
= G
.pagesize
;
845 e
->next
= main_zone
.free_pages
;
846 main_zone
.free_pages
= e
;
851 /* Start a new GGC zone. */
854 new_ggc_zone (const char * name
)
856 struct alloc_zone
*new_zone
= xcalloc (1, sizeof (struct alloc_zone
));
857 new_zone
->name
= name
;
858 new_zone
->next_zone
= G
.zones
->next_zone
;
859 G
.zones
->next_zone
= new_zone
;
863 /* Destroy a GGC zone. */
865 destroy_ggc_zone (struct alloc_zone
* dead_zone
)
867 struct alloc_zone
*z
;
869 for (z
= G
.zones
; z
&& z
->next_zone
!= dead_zone
; z
= z
->next_zone
)
870 /* Just find that zone. */ ;
872 #ifdef ENABLE_CHECKING
873 /* We should have found the zone in the list. Anything else is fatal. */
878 /* z is dead, baby. z is dead. */
882 /* Increment the `GC context'. Objects allocated in an outer context
883 are never freed, eliminating the need to register their roots. */
886 ggc_push_context (void)
888 struct alloc_zone
*zone
;
889 for (zone
= G
.zones
; zone
; zone
= zone
->next_zone
)
890 ++(zone
->context_depth
);
892 if (main_zone
.context_depth
>= HOST_BITS_PER_LONG
)
896 /* Decrement the `GC context'. All objects allocated since the
897 previous ggc_push_context are migrated to the outer context. */
900 ggc_pop_context_1 (struct alloc_zone
*zone
)
906 depth
= --(zone
->context_depth
);
907 omask
= (unsigned long)1 << (depth
+ 1);
909 if (!((zone
->context_depth_allocations
| zone
->context_depth_collections
) & omask
))
912 zone
->context_depth_allocations
|= (zone
->context_depth_allocations
& omask
) >> 1;
913 zone
->context_depth_allocations
&= omask
- 1;
914 zone
->context_depth_collections
&= omask
- 1;
916 /* Any remaining pages in the popped context are lowered to the new
917 current context; i.e. objects allocated in the popped context and
918 left over are imported into the previous context. */
919 for (p
= zone
->pages
; p
!= NULL
; p
= p
->next
)
920 if (p
->context_depth
> depth
)
921 p
->context_depth
= depth
;
924 /* Pop all the zone contexts. */
927 ggc_pop_context (void)
929 struct alloc_zone
*zone
;
930 for (zone
= G
.zones
; zone
; zone
= zone
->next_zone
)
931 ggc_pop_context_1 (zone
);
933 /* Poison the chunk. */
934 #ifdef ENABLE_GC_CHECKING
935 #define poison_chunk(CHUNK, SIZE) \
936 memset ((CHUNK)->u.data, 0xa5, (SIZE))
938 #define poison_chunk(CHUNK, SIZE)
941 /* Free all empty pages and objects within a page for a given zone */
944 sweep_pages (struct alloc_zone
*zone
)
946 page_entry
**pp
, *p
, *next
;
947 struct alloc_chunk
*chunk
, *last_free
, *end
;
948 size_t last_free_size
, allocated
= 0;
950 /* First, reset the free_chunks lists, since we are going to
951 re-free free chunks in hopes of coalescing them into large chunks. */
952 memset (zone
->free_chunks
, 0, sizeof (zone
->free_chunks
));
954 for (p
= zone
->pages
; p
; p
= next
)
957 /* Large pages are all or none affairs. Either they are
958 completely empty, or they are completely full.
960 XXX: Should we bother to increment allocated. */
963 if (((struct alloc_chunk
*)p
->page
)->mark
== 1)
965 ((struct alloc_chunk
*)p
->page
)->mark
= 0;
970 #ifdef ENABLE_GC_CHECKING
971 /* Poison the page. */
972 memset (p
->page
, 0xb5, p
->bytes
);
979 /* This page has now survived another collection. */
982 /* Which leaves full and partial pages. Step through all chunks,
983 consolidate those that are free and insert them into the free
984 lists. Note that consolidation slows down collection
987 chunk
= (struct alloc_chunk
*)p
->page
;
988 end
= (struct alloc_chunk
*)(p
->page
+ G
.pagesize
);
991 nomarksinpage
= true;
994 prefetch ((struct alloc_chunk
*)(chunk
->u
.data
+ chunk
->size
));
995 if (chunk
->mark
|| p
->context_depth
< zone
->context_depth
)
997 nomarksinpage
= false;
1000 last_free
->type
= 0;
1001 last_free
->size
= last_free_size
;
1002 last_free
->mark
= 0;
1003 poison_chunk (last_free
, last_free_size
);
1004 free_chunk (last_free
, last_free_size
, zone
);
1009 allocated
+= chunk
->size
+ CHUNK_OVERHEAD
;
1017 last_free_size
+= CHUNK_OVERHEAD
+ chunk
->size
;
1022 last_free_size
= chunk
->size
;
1026 chunk
= (struct alloc_chunk
*)(chunk
->u
.data
+ chunk
->size
);
1028 while (chunk
< end
);
1033 #ifdef ENABLE_GC_CHECKING
1034 /* Poison the page. */
1035 memset (p
->page
, 0xb5, p
->bytes
);
1042 last_free
->type
= 0;
1043 last_free
->size
= last_free_size
;
1044 last_free
->mark
= 0;
1045 poison_chunk (last_free
, last_free_size
);
1046 free_chunk (last_free
, last_free_size
, zone
);
1051 zone
->allocated
= allocated
;
1054 /* mark-and-sweep routine for collecting a single zone. NEED_MARKING
1055 is true if we need to mark before sweeping, false if some other
1056 zone collection has already performed marking for us. Returns true
1057 if we collected, false otherwise. */
1060 ggc_collect_1 (struct alloc_zone
*zone
, bool need_marking
)
1064 /* Avoid frequent unnecessary work by skipping collection if the
1065 total allocations haven't expanded much since the last
1067 float allocated_last_gc
=
1068 MAX (zone
->allocated_last_gc
,
1069 (size_t) PARAM_VALUE (GGC_MIN_HEAPSIZE
) * 1024);
1071 float min_expand
= allocated_last_gc
* PARAM_VALUE (GGC_MIN_EXPAND
) / 100;
1073 if (zone
->allocated
< allocated_last_gc
+ min_expand
)
1078 fprintf (stderr
, " {%s GC %luk -> ",
1079 zone
->name
, (unsigned long) zone
->allocated
/ 1024);
1081 /* Zero the total allocated bytes. This will be recalculated in the
1083 zone
->allocated
= 0;
1085 /* Release the pages we freed the last time we collected, but didn't
1086 reuse in the interim. */
1087 release_pages (zone
);
1089 /* Indicate that we've seen collections at this context depth. */
1090 zone
->context_depth_collections
1091 = ((unsigned long)1 << (zone
->context_depth
+ 1)) - 1;
1095 zone
->was_collected
= true;
1096 zone
->allocated_last_gc
= zone
->allocated
;
1099 fprintf (stderr
, "%luk}", (unsigned long) zone
->allocated
/ 1024);
1103 /* Calculate the average page survival rate in terms of number of
1107 calculate_average_page_survival (struct alloc_zone
*zone
)
1110 float survival
= 0.0;
1112 for (p
= zone
->pages
; p
; p
= p
->next
)
1115 survival
+= p
->survived
;
1117 return survival
/count
;
1120 /* Check the magic cookies all of the chunks contain, to make sure we
1121 aren't doing anything stupid, like stomping on alloc_chunk
1125 check_cookies (void)
1127 #ifdef COOKIE_CHECKING
1129 struct alloc_zone
*zone
;
1131 for (zone
= G
.zones
; zone
; zone
= zone
->next_zone
)
1133 for (p
= zone
->pages
; p
; p
= p
->next
)
1137 struct alloc_chunk
*chunk
= (struct alloc_chunk
*)p
->page
;
1138 struct alloc_chunk
*end
= (struct alloc_chunk
*)(p
->page
+ G
.pagesize
);
1141 if (chunk
->magic
!= CHUNK_MAGIC
&& chunk
->magic
!= DEADCHUNK_MAGIC
)
1143 chunk
= (struct alloc_chunk
*)(chunk
->u
.data
+ chunk
->size
);
1145 while (chunk
< end
);
1151 /* Top level collection routine. */
1156 struct alloc_zone
*zone
;
1157 bool marked
= false;
1160 timevar_push (TV_GC
);
1162 /* Start by possibly collecting the main zone. */
1163 main_zone
.was_collected
= false;
1164 marked
|= ggc_collect_1 (&main_zone
, true);
1166 /* In order to keep the number of collections down, we don't
1167 collect other zones unless we are collecting the main zone. This
1168 gives us roughly the same number of collections as we used to
1169 have with the old gc. The number of collection is important
1170 because our main slowdown (according to profiling) is now in
1171 marking. So if we mark twice as often as we used to, we'll be
1172 twice as slow. Hopefully we'll avoid this cost when we mark
1175 if (main_zone
.was_collected
)
1177 struct alloc_zone
*zone
;
1179 for (zone
= main_zone
.next_zone
; zone
; zone
= zone
->next_zone
)
1182 zone
->was_collected
= false;
1183 marked
|= ggc_collect_1 (zone
, !marked
);
1187 /* Print page survival stats, if someone wants them. */
1188 if (GGC_DEBUG_LEVEL
>= 2)
1190 for (zone
= G
.zones
; zone
; zone
= zone
->next_zone
)
1192 if (zone
->was_collected
)
1194 f
= calculate_average_page_survival (zone
);
1195 printf ("Average page survival in zone `%s' is %f\n",
1201 /* Since we don't mark zone at a time right now, marking in any
1202 zone means marking in every zone. So we have to clear all the
1203 marks in all the zones that weren't collected already. */
1207 for (zone
= G
.zones
; zone
; zone
= zone
->next_zone
)
1209 if (zone
->was_collected
)
1211 for (p
= zone
->pages
; p
; p
= p
->next
)
1215 struct alloc_chunk
*chunk
= (struct alloc_chunk
*)p
->page
;
1216 struct alloc_chunk
*end
= (struct alloc_chunk
*)(p
->page
+ G
.pagesize
);
1219 prefetch ((struct alloc_chunk
*)(chunk
->u
.data
+ chunk
->size
));
1220 if (chunk
->mark
|| p
->context_depth
< zone
->context_depth
)
1224 chunk
= (struct alloc_chunk
*)(chunk
->u
.data
+ chunk
->size
);
1226 while (chunk
< end
);
1230 ((struct alloc_chunk
*)p
->page
)->mark
= 0;
1236 /* Free dead zones. */
1237 for (zone
= G
.zones
; zone
&& zone
->next_zone
; zone
= zone
->next_zone
)
1239 if (zone
->next_zone
->dead
)
1241 struct alloc_zone
*dead_zone
= zone
->next_zone
;
1243 printf ("Zone `%s' is dead and will be freed.\n", dead_zone
->name
);
1245 /* The zone must be empty. */
1246 if (dead_zone
->allocated
!= 0)
1249 /* Unchain the dead zone, release all its pages and free it. */
1250 zone
->next_zone
= zone
->next_zone
->next_zone
;
1251 release_pages (dead_zone
);
1256 timevar_pop (TV_GC
);
1259 /* Print allocation statistics. */
1262 ggc_print_statistics (void)
1268 struct ggc_pch_ondisk
1276 /* Initialize the PCH datastructure. */
1278 struct ggc_pch_data
*
1281 return xcalloc (sizeof (struct ggc_pch_data
), 1);
1284 /* Add the size of object X to the size of the PCH data. */
1287 ggc_pch_count_object (struct ggc_pch_data
*d
, void *x ATTRIBUTE_UNUSED
,
1288 size_t size
, bool is_string
)
1292 d
->d
.total
+= size
+ CHUNK_OVERHEAD
;
1298 /* Return the total size of the PCH data. */
1301 ggc_pch_total_size (struct ggc_pch_data
*d
)
1306 /* Set the base address for the objects in the PCH file. */
1309 ggc_pch_this_base (struct ggc_pch_data
*d
, void *base
)
1311 d
->base
= (size_t) base
;
1314 /* Allocate a place for object X of size SIZE in the PCH file. */
1317 ggc_pch_alloc_object (struct ggc_pch_data
*d
, void *x
,
1318 size_t size
, bool is_string
)
1321 result
= (char *)d
->base
;
1324 struct alloc_chunk
*chunk
= (struct alloc_chunk
*) ((char *)x
- CHUNK_OVERHEAD
);
1326 d
->base
+= ggc_get_size (x
) + CHUNK_OVERHEAD
;
1328 d
->base
+= chunk
->size
+ CHUNK_OVERHEAD
;
1329 return result
+ CHUNK_OVERHEAD
;
1339 /* Prepare to write out the PCH data to file F. */
1342 ggc_pch_prepare_write (struct ggc_pch_data
*d ATTRIBUTE_UNUSED
,
1343 FILE *f ATTRIBUTE_UNUSED
)
1345 /* Nothing to do. */
1348 /* Write out object X of SIZE to file F. */
1351 ggc_pch_write_object (struct ggc_pch_data
*d ATTRIBUTE_UNUSED
,
1352 FILE *f
, void *x
, void *newx ATTRIBUTE_UNUSED
,
1353 size_t size
, bool is_string
)
1357 struct alloc_chunk
*chunk
= (struct alloc_chunk
*) ((char *)x
- CHUNK_OVERHEAD
);
1358 size
= ggc_get_size (x
);
1359 if (fwrite (chunk
, size
+ CHUNK_OVERHEAD
, 1, f
) != 1)
1360 fatal_error ("can't write PCH file: %m");
1361 d
->written
+= size
+ CHUNK_OVERHEAD
;
1365 if (fwrite (x
, size
, 1, f
) != 1)
1366 fatal_error ("can't write PCH file: %m");
1369 if (d
->written
== d
->d
.total
1370 && fseek (f
, ROUND_UP_VALUE (d
->d
.total
, G
.pagesize
), SEEK_CUR
) != 0)
1371 fatal_error ("can't write PCH file: %m");
1375 ggc_pch_finish (struct ggc_pch_data
*d
, FILE *f
)
1377 if (fwrite (&d
->d
, sizeof (d
->d
), 1, f
) != 1)
1378 fatal_error ("can't write PCH file: %m");
1382 ggc_pch_read (FILE *f
, void *addr
)
1384 struct ggc_pch_ondisk d
;
1385 struct page_entry
*entry
;
1386 struct alloc_zone
*pch_zone
;
1387 if (fread (&d
, sizeof (d
), 1, f
) != 1)
1388 fatal_error ("can't read PCH file: %m");
1389 entry
= xcalloc (1, sizeof (struct page_entry
));
1390 entry
->bytes
= d
.total
;
1392 entry
->context_depth
= 0;
1393 pch_zone
= new_ggc_zone ("PCH zone");
1394 entry
->zone
= pch_zone
;
1395 entry
->next
= entry
->zone
->pages
;
1396 entry
->zone
->pages
= entry
;