1 /* "Bag-of-pages" garbage collector for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
32 #ifdef HAVE_MMAP_ANYWHERE
40 #if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
41 #define MAP_ANONYMOUS MAP_ANON
46 This garbage-collecting allocator allocates objects on one of a set
47 of pages. Each page can allocate objects of a single size only;
48 available sizes are powers of two starting at four bytes. The size
49 of an allocation request is rounded up to the next power of two
50 (`order'), and satisfied from the appropriate page.
52 Each page is recorded in a page-entry, which also maintains an
53 in-use bitmap of object positions on the page. This allows the
54 allocation state of a particular object to be flipped without
55 touching the page itself.
57 Each page-entry also has a context depth, which is used to track
58 pushing and popping of allocation contexts. Only objects allocated
59 in the current (highest-numbered) context may be collected.
61 Page entries are arranged in an array of singly-linked lists. The
62 array is indexed by the allocation size, in bits, of the pages on
63 it; i.e. all pages on a list allocate objects of the same size.
64 Pages are ordered on the list such that all non-full pages precede
65 all full pages, with non-full pages arranged in order of decreasing
68 Empty pages (of all orders) are kept on a single page cache list,
69 and are considered first when new pages are required; they are
70 deallocated at the start of the next collection if they haven't
71 been recycled by then. */
74 /* Define GGC_POISON to poison memory marked unused by the collector. */
77 /* Define GGC_ALWAYS_COLLECT to perform collection every time
78 ggc_collect is invoked. Otherwise, collection is performed only
79 when a significant amount of memory has been allocated since the
81 #undef GGC_ALWAYS_COLLECT
83 #ifdef ENABLE_GC_CHECKING
86 #ifdef ENABLE_GC_ALWAYS_COLLECT
87 #define GGC_ALWAYS_COLLECT
90 /* Define GGC_DEBUG_LEVEL to print debugging information.
91 0: No debugging output.
92 1: GC statistics only.
93 2: Page-entry allocations/deallocations as well.
94 3: Object allocations as well.
95 4: Object marks as well. */
96 #define GGC_DEBUG_LEVEL (0)
98 #ifndef HOST_BITS_PER_PTR
99 #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
103 /* A two-level tree is used to look up the page-entry for a given
104 pointer. Two chunks of the pointer's bits are extracted to index
105 the first and second levels of the tree, as follows:
109 msb +----------------+----+------+------+ lsb
115 The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry
116 pages are aligned on system page boundaries. The next most
117 significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first
118 index values in the lookup table, respectively.
120 For 32-bit architectures and the settings below, there are no
121 leftover bits. For architectures with wider pointers, the lookup
122 tree points to a list of pages, which must be scanned to find the
125 #define PAGE_L1_BITS (8)
126 #define PAGE_L2_BITS (32 - PAGE_L1_BITS - G.lg_pagesize)
127 #define PAGE_L1_SIZE ((size_t) 1 << PAGE_L1_BITS)
128 #define PAGE_L2_SIZE ((size_t) 1 << PAGE_L2_BITS)
130 #define LOOKUP_L1(p) \
131 (((size_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
133 #define LOOKUP_L2(p) \
134 (((size_t) (p) >> G.lg_pagesize) & ((1 << PAGE_L2_BITS) - 1))
136 /* The number of objects per allocation page, for objects on a page of
137 the indicated ORDER. */
138 #define OBJECTS_PER_PAGE(ORDER) objects_per_page_table[ORDER]
140 /* The size of an object on a page of the indicated ORDER. */
141 #define OBJECT_SIZE(ORDER) object_size_table[ORDER]
143 /* The number of extra orders, not corresponding to power-of-two sized
146 #define NUM_EXTRA_ORDERS \
147 (sizeof (extra_order_size_table) / sizeof (extra_order_size_table[0]))
149 /* The Ith entry is the maximum size of an object to be stored in the
150 Ith extra order. Adding a new entry to this array is the *only*
151 thing you need to do to add a new special allocation size. */
153 static const size_t extra_order_size_table
[] = {
154 sizeof (struct tree_decl
),
155 sizeof (struct tree_list
)
158 /* The total number of orders. */
160 #define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS)
162 /* We use this structure to determine the alignment required for
163 allocations. For power-of-two sized allocations, that's not a
164 problem, but it does matter for odd-sized allocations. */
166 struct max_alignment
{
170 #ifdef HAVE_LONG_DOUBLE
178 /* The biggest alignment required. */
180 #define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
182 /* The Ith entry is the number of objects on a page or order I. */
184 static unsigned objects_per_page_table
[NUM_ORDERS
];
186 /* The Ith entry is the size of an object on a page of order I. */
188 static size_t object_size_table
[NUM_ORDERS
];
190 /* A page_entry records the status of an allocation page. This
191 structure is dynamically sized to fit the bitmap in_use_p. */
192 typedef struct page_entry
194 /* The next page-entry with objects of the same size, or NULL if
195 this is the last page-entry. */
196 struct page_entry
*next
;
198 /* The number of bytes allocated. (This will always be a multiple
199 of the host system page size.) */
202 /* The address at which the memory is allocated. */
205 /* Saved in-use bit vector for pages that aren't in the topmost
206 context during collection. */
207 unsigned long *save_in_use_p
;
209 /* Context depth of this page. */
210 unsigned short context_depth
;
212 /* The number of free objects remaining on this page. */
213 unsigned short num_free_objects
;
215 /* A likely candidate for the bit position of a free object for the
216 next allocation from this page. */
217 unsigned short next_bit_hint
;
219 /* The lg of size of objects allocated from this page. */
222 /* A bit vector indicating whether or not objects are in use. The
223 Nth bit is one if the Nth object on this page is allocated. This
224 array is dynamically sized. */
225 unsigned long in_use_p
[1];
229 #if HOST_BITS_PER_PTR <= 32
231 /* On 32-bit hosts, we use a two level page table, as pictured above. */
232 typedef page_entry
**page_table
[PAGE_L1_SIZE
];
236 /* On 64-bit hosts, we use the same two level page tables plus a linked
237 list that disambiguates the top 32-bits. There will almost always be
238 exactly one entry in the list. */
239 typedef struct page_table_chain
241 struct page_table_chain
*next
;
243 page_entry
**table
[PAGE_L1_SIZE
];
248 /* The rest of the global variables. */
249 static struct globals
251 /* The Nth element in this array is a page with objects of size 2^N.
252 If there are any pages with free objects, they will be at the
253 head of the list. NULL if there are no page-entries for this
255 page_entry
*pages
[NUM_ORDERS
];
257 /* The Nth element in this array is the last page with objects of
258 size 2^N. NULL if there are no page-entries for this object
260 page_entry
*page_tails
[NUM_ORDERS
];
262 /* Lookup table for associating allocation pages with object addresses. */
265 /* The system's page size. */
269 /* Bytes currently allocated. */
272 /* Bytes currently allocated at the end of the last collection. */
273 size_t allocated_last_gc
;
275 /* Total amount of memory mapped. */
278 /* The current depth in the context stack. */
279 unsigned short context_depth
;
281 /* A file descriptor open to /dev/zero for reading. */
282 #if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
286 /* A cache of free system pages. */
287 page_entry
*free_pages
;
289 /* The file descriptor for debugging output. */
293 /* The size in bytes required to maintain a bitmap for the objects
295 #define BITMAP_SIZE(Num_objects) \
296 (CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
298 /* Skip garbage collection if the current allocation is not at least
299 this factor times the allocation at the end of the last collection.
300 In other words, total allocation must expand by (this factor minus
301 one) before collection is performed. */
302 #define GGC_MIN_EXPAND_FOR_GC (1.3)
304 /* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
305 test from triggering too often when the heap is small. */
306 #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
308 /* Allocate pages in chunks of this size, to throttle calls to mmap.
309 The first page is used, the rest go onto the free list. */
310 #define GGC_QUIRE_SIZE 16
313 static int ggc_allocated_p
PARAMS ((const void *));
314 static page_entry
*lookup_page_table_entry
PARAMS ((const void *));
315 static void set_page_table_entry
PARAMS ((void *, page_entry
*));
316 static char *alloc_anon
PARAMS ((char *, size_t));
317 static struct page_entry
* alloc_page
PARAMS ((unsigned));
318 static void free_page
PARAMS ((struct page_entry
*));
319 static void release_pages
PARAMS ((void));
320 static void clear_marks
PARAMS ((void));
321 static void sweep_pages
PARAMS ((void));
322 static void ggc_recalculate_in_use_p
PARAMS ((page_entry
*));
325 static void poison_pages
PARAMS ((void));
328 void debug_print_page_list
PARAMS ((int));
330 /* Returns non-zero if P was allocated in GC'able memory. */
339 #if HOST_BITS_PER_PTR <= 32
342 page_table table
= G
.lookup
;
343 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
348 if (table
->high_bits
== high_bits
)
352 base
= &table
->table
[0];
355 /* Extract the level 1 and 2 indicies. */
359 return base
[L1
] && base
[L1
][L2
];
362 /* Traverse the page table and find the entry for a page.
363 Die (probably) if the object wasn't allocated via GC. */
365 static inline page_entry
*
366 lookup_page_table_entry(p
)
372 #if HOST_BITS_PER_PTR <= 32
375 page_table table
= G
.lookup
;
376 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
377 while (table
->high_bits
!= high_bits
)
379 base
= &table
->table
[0];
382 /* Extract the level 1 and 2 indicies. */
389 /* Set the page table entry for a page. */
392 set_page_table_entry(p
, entry
)
399 #if HOST_BITS_PER_PTR <= 32
403 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
404 for (table
= G
.lookup
; table
; table
= table
->next
)
405 if (table
->high_bits
== high_bits
)
408 /* Not found -- allocate a new table. */
409 table
= (page_table
) xcalloc (1, sizeof(*table
));
410 table
->next
= G
.lookup
;
411 table
->high_bits
= high_bits
;
414 base
= &table
->table
[0];
417 /* Extract the level 1 and 2 indicies. */
421 if (base
[L1
] == NULL
)
422 base
[L1
] = (page_entry
**) xcalloc (PAGE_L2_SIZE
, sizeof (page_entry
*));
424 base
[L1
][L2
] = entry
;
427 /* Prints the page-entry for object size ORDER, for debugging. */
430 debug_print_page_list (order
)
434 printf ("Head=%p, Tail=%p:\n", (PTR
) G
.pages
[order
],
435 (PTR
) G
.page_tails
[order
]);
439 printf ("%p(%1d|%3d) -> ", (PTR
) p
, p
->context_depth
,
440 p
->num_free_objects
);
447 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
451 alloc_anon (pref
, size
)
452 char *pref ATTRIBUTE_UNUSED
;
457 #ifdef HAVE_MMAP_ANYWHERE
459 page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
460 MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
462 page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
463 MAP_PRIVATE
, G
.dev_zero_fd
, 0);
465 if (page
== (char *) MAP_FAILED
)
467 fputs ("Virtual memory exhausted!\n", stderr
);
472 page
= (char *) valloc (size
);
475 fputs ("Virtual memory exhausted!\n", stderr
);
478 #endif /* HAVE_VALLOC */
479 #endif /* HAVE_MMAP_ANYWHERE */
481 /* Remember that we allocated this memory. */
482 G
.bytes_mapped
+= size
;
487 /* Allocate a new page for allocating objects of size 2^ORDER,
488 and return an entry for it. The entry is not added to the
489 appropriate page_table list. */
491 static inline struct page_entry
*
495 struct page_entry
*entry
, *p
, **pp
;
499 size_t page_entry_size
;
502 num_objects
= OBJECTS_PER_PAGE (order
);
503 bitmap_size
= BITMAP_SIZE (num_objects
+ 1);
504 page_entry_size
= sizeof (page_entry
) - sizeof (long) + bitmap_size
;
505 entry_size
= num_objects
* OBJECT_SIZE (order
);
510 /* Check the list of free pages for one we can use. */
511 for (pp
= &G
.free_pages
, p
= *pp
; p
; pp
= &p
->next
, p
= *pp
)
512 if (p
->bytes
== entry_size
)
517 /* Recycle the allocated memory from this page ... */
520 /* ... and, if possible, the page entry itself. */
521 if (p
->order
== order
)
524 memset (entry
, 0, page_entry_size
);
529 #ifdef HAVE_MMAP_ANYWHERE
530 else if (entry_size
== G
.pagesize
)
532 /* We want just one page. Allocate a bunch of them and put the
533 extras on the freelist. (Can only do this optimization with
534 mmap for backing store.) */
535 struct page_entry
*e
, *f
= G
.free_pages
;
538 page
= alloc_anon (NULL
, entry_size
* GGC_QUIRE_SIZE
);
539 /* This loop counts down so that the chain will be in ascending
541 for (i
= GGC_QUIRE_SIZE
- 1; i
>= 1; i
--)
543 e
= (struct page_entry
*) xcalloc (1, sizeof (struct page_entry
));
544 e
->bytes
= entry_size
;
545 e
->page
= page
+ i
*entry_size
;
553 page
= alloc_anon (NULL
, entry_size
);
556 entry
= (struct page_entry
*) xcalloc (1, page_entry_size
);
558 entry
->bytes
= entry_size
;
560 entry
->context_depth
= G
.context_depth
;
561 entry
->order
= order
;
562 entry
->num_free_objects
= num_objects
;
563 entry
->next_bit_hint
= 1;
565 /* Set the one-past-the-end in-use bit. This acts as a sentry as we
566 increment the hint. */
567 entry
->in_use_p
[num_objects
/ HOST_BITS_PER_LONG
]
568 = (unsigned long) 1 << (num_objects
% HOST_BITS_PER_LONG
);
570 set_page_table_entry (page
, entry
);
572 if (GGC_DEBUG_LEVEL
>= 2)
573 fprintf (G
.debug_file
,
574 "Allocating page at %p, object size=%d, data %p-%p\n",
575 (PTR
) entry
, OBJECT_SIZE (order
), page
, page
+ entry_size
- 1);
580 /* For a page that is no longer needed, put it on the free page list. */
586 if (GGC_DEBUG_LEVEL
>= 2)
587 fprintf (G
.debug_file
,
588 "Deallocating page at %p, data %p-%p\n", (PTR
) entry
,
589 entry
->page
, entry
->page
+ entry
->bytes
- 1);
591 set_page_table_entry (entry
->page
, NULL
);
593 entry
->next
= G
.free_pages
;
594 G
.free_pages
= entry
;
597 /* Release the free page cache to the system. */
602 page_entry
*p
, *next
;
604 #ifdef HAVE_MMAP_ANYWHERE
608 /* Gather up adjacent pages so they are unmapped together. */
619 while (p
&& p
->page
== start
+ len
)
628 G
.bytes_mapped
-= len
;
633 for (p
= G
.free_pages
; p
; p
= next
)
637 G
.bytes_mapped
-= p
->bytes
;
640 #endif /* HAVE_VALLOC */
641 #endif /* HAVE_MMAP_ANYWHERE */
646 /* This table provides a fast way to determine ceil(log_2(size)) for
647 allocation requests. The minimum allocation size is four bytes. */
649 static unsigned char size_lookup
[257] =
651 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
652 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
653 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
654 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
655 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
656 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
657 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
658 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
659 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
660 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
661 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
662 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
663 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
664 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
665 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
666 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
670 /* Allocate a chunk of memory of SIZE bytes. If ZERO is non-zero, the
671 memory is zeroed; otherwise, its contents are undefined. */
677 unsigned order
, word
, bit
, object_offset
;
678 struct page_entry
*entry
;
682 order
= size_lookup
[size
];
686 while (size
> OBJECT_SIZE (order
))
690 /* If there are non-full pages for this size allocation, they are at
691 the head of the list. */
692 entry
= G
.pages
[order
];
694 /* If there is no page for this object size, or all pages in this
695 context are full, allocate a new page. */
696 if (entry
== NULL
|| entry
->num_free_objects
== 0)
698 struct page_entry
*new_entry
;
699 new_entry
= alloc_page (order
);
701 /* If this is the only entry, it's also the tail. */
703 G
.page_tails
[order
] = new_entry
;
705 /* Put new pages at the head of the page list. */
706 new_entry
->next
= entry
;
708 G
.pages
[order
] = new_entry
;
710 /* For a new page, we know the word and bit positions (in the
711 in_use bitmap) of the first available object -- they're zero. */
712 new_entry
->next_bit_hint
= 1;
719 /* First try to use the hint left from the previous allocation
720 to locate a clear bit in the in-use bitmap. We've made sure
721 that the one-past-the-end bit is always set, so if the hint
722 has run over, this test will fail. */
723 unsigned hint
= entry
->next_bit_hint
;
724 word
= hint
/ HOST_BITS_PER_LONG
;
725 bit
= hint
% HOST_BITS_PER_LONG
;
727 /* If the hint didn't work, scan the bitmap from the beginning. */
728 if ((entry
->in_use_p
[word
] >> bit
) & 1)
731 while (~entry
->in_use_p
[word
] == 0)
733 while ((entry
->in_use_p
[word
] >> bit
) & 1)
735 hint
= word
* HOST_BITS_PER_LONG
+ bit
;
738 /* Next time, try the next bit. */
739 entry
->next_bit_hint
= hint
+ 1;
741 object_offset
= hint
* OBJECT_SIZE (order
);
744 /* Set the in-use bit. */
745 entry
->in_use_p
[word
] |= ((unsigned long) 1 << bit
);
747 /* Keep a running total of the number of free objects. If this page
748 fills up, we may have to move it to the end of the list if the
749 next page isn't full. If the next page is full, all subsequent
750 pages are full, so there's no need to move it. */
751 if (--entry
->num_free_objects
== 0
752 && entry
->next
!= NULL
753 && entry
->next
->num_free_objects
> 0)
755 G
.pages
[order
] = entry
->next
;
757 G
.page_tails
[order
]->next
= entry
;
758 G
.page_tails
[order
] = entry
;
761 /* Calculate the object's address. */
762 result
= entry
->page
+ object_offset
;
765 /* `Poison' the entire allocated object, including any padding at
767 memset (result
, 0xaf, OBJECT_SIZE (order
));
770 /* Keep track of how many bytes are being allocated. This
771 information is used in deciding when to collect. */
772 G
.allocated
+= OBJECT_SIZE (order
);
774 if (GGC_DEBUG_LEVEL
>= 3)
775 fprintf (G
.debug_file
,
776 "Allocating object, requested size=%d, actual=%d at %p on %p\n",
777 (int) size
, OBJECT_SIZE (order
), result
, (PTR
) entry
);
782 /* If P is not marked, marks it and return false. Otherwise return true.
783 P must have been allocated by the GC allocator; it mustn't point to
784 static objects, stack variables, or memory allocated with malloc. */
794 /* Look up the page on which the object is alloced. If the object
795 wasn't allocated by the collector, we'll probably die. */
796 entry
= lookup_page_table_entry (p
);
797 #ifdef ENABLE_CHECKING
802 /* Calculate the index of the object on the page; this is its bit
803 position in the in_use_p bitmap. */
804 bit
= (((const char *) p
) - entry
->page
) / OBJECT_SIZE (entry
->order
);
805 word
= bit
/ HOST_BITS_PER_LONG
;
806 mask
= (unsigned long) 1 << (bit
% HOST_BITS_PER_LONG
);
808 /* If the bit was previously set, skip it. */
809 if (entry
->in_use_p
[word
] & mask
)
812 /* Otherwise set it, and decrement the free object count. */
813 entry
->in_use_p
[word
] |= mask
;
814 entry
->num_free_objects
-= 1;
816 if (GGC_DEBUG_LEVEL
>= 4)
817 fprintf (G
.debug_file
, "Marking %p\n", p
);
822 /* Mark P, but check first that it was allocated by the collector. */
825 ggc_mark_if_gcable (p
)
828 if (p
&& ggc_allocated_p (p
))
832 /* Return the size of the gc-able object P. */
838 page_entry
*pe
= lookup_page_table_entry (p
);
839 return OBJECT_SIZE (pe
->order
);
842 /* Initialize the ggc-mmap allocator. */
849 G
.pagesize
= getpagesize();
850 G
.lg_pagesize
= exact_log2 (G
.pagesize
);
852 #if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
853 G
.dev_zero_fd
= open ("/dev/zero", O_RDONLY
);
854 if (G
.dev_zero_fd
== -1)
859 G
.debug_file
= fopen ("ggc-mmap.debug", "w");
861 G
.debug_file
= stdout
;
864 G
.allocated_last_gc
= GGC_MIN_LAST_ALLOCATED
;
866 #ifdef HAVE_MMAP_ANYWHERE
867 /* StunOS has an amazing off-by-one error for the first mmap allocation
868 after fiddling with RLIMIT_STACK. The result, as hard as it is to
869 believe, is an unaligned page allocation, which would cause us to
870 hork badly if we tried to use it. */
872 char *p
= alloc_anon (NULL
, G
.pagesize
);
873 if ((size_t)p
& (G
.pagesize
- 1))
875 /* How losing. Discard this one and try another. If we still
876 can't get something useful, give up. */
878 p
= alloc_anon (NULL
, G
.pagesize
);
879 if ((size_t)p
& (G
.pagesize
- 1))
882 munmap (p
, G
.pagesize
);
886 /* Initialize the object size table. */
887 for (order
= 0; order
< HOST_BITS_PER_PTR
; ++order
)
888 object_size_table
[order
] = (size_t) 1 << order
;
889 for (order
= HOST_BITS_PER_PTR
; order
< NUM_ORDERS
; ++order
)
891 size_t s
= extra_order_size_table
[order
- HOST_BITS_PER_PTR
];
893 /* If S is not a multiple of the MAX_ALIGNMENT, then round it up
894 so that we're sure of getting aligned memory. */
895 s
= CEIL (s
, MAX_ALIGNMENT
) * MAX_ALIGNMENT
;
896 object_size_table
[order
] = s
;
899 /* Initialize the objects-per-page table. */
900 for (order
= 0; order
< NUM_ORDERS
; ++order
)
902 objects_per_page_table
[order
] = G
.pagesize
/ OBJECT_SIZE (order
);
903 if (objects_per_page_table
[order
] == 0)
904 objects_per_page_table
[order
] = 1;
907 /* Reset the size_lookup array to put appropriately sized objects in
908 the special orders. All objects bigger than the previous power
909 of two, but no greater than the special size, should go in the
911 for (order
= HOST_BITS_PER_PTR
; order
< NUM_ORDERS
; ++order
)
916 o
= size_lookup
[OBJECT_SIZE (order
)];
917 for (i
= OBJECT_SIZE (order
); size_lookup
[i
] == o
; --i
)
918 size_lookup
[i
] = order
;
922 /* Increment the `GC context'. Objects allocated in an outer context
923 are never freed, eliminating the need to register their roots. */
931 if (G
.context_depth
== 0)
935 /* Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P
936 reflects reality. Recalculate NUM_FREE_OBJECTS as well. */
939 ggc_recalculate_in_use_p (p
)
945 /* Because the past-the-end bit in in_use_p is always set, we
946 pretend there is one additional object. */
947 num_objects
= OBJECTS_PER_PAGE (p
->order
) + 1;
949 /* Reset the free object count. */
950 p
->num_free_objects
= num_objects
;
952 /* Combine the IN_USE_P and SAVE_IN_USE_P arrays. */
954 i
< CEIL (BITMAP_SIZE (num_objects
),
955 sizeof (*p
->in_use_p
));
960 /* Something is in use if it is marked, or if it was in use in a
961 context further down the context stack. */
962 p
->in_use_p
[i
] |= p
->save_in_use_p
[i
];
964 /* Decrement the free object count for every object allocated. */
965 for (j
= p
->in_use_p
[i
]; j
; j
>>= 1)
966 p
->num_free_objects
-= (j
& 1);
969 if (p
->num_free_objects
>= num_objects
)
973 /* Decrement the `GC context'. All objects allocated since the
974 previous ggc_push_context are migrated to the outer context. */
979 unsigned order
, depth
;
981 depth
= --G
.context_depth
;
983 /* Any remaining pages in the popped context are lowered to the new
984 current context; i.e. objects allocated in the popped context and
985 left over are imported into the previous context. */
986 for (order
= 2; order
< NUM_ORDERS
; order
++)
990 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
992 if (p
->context_depth
> depth
)
993 p
->context_depth
= depth
;
995 /* If this page is now in the topmost context, and we'd
996 saved its allocation state, restore it. */
997 else if (p
->context_depth
== depth
&& p
->save_in_use_p
)
999 ggc_recalculate_in_use_p (p
);
1000 free (p
->save_in_use_p
);
1001 p
->save_in_use_p
= 0;
1007 /* Unmark all objects. */
1014 for (order
= 2; order
< NUM_ORDERS
; order
++)
1016 size_t num_objects
= OBJECTS_PER_PAGE (order
);
1017 size_t bitmap_size
= BITMAP_SIZE (num_objects
+ 1);
1020 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
1022 #ifdef ENABLE_CHECKING
1023 /* The data should be page-aligned. */
1024 if ((size_t) p
->page
& (G
.pagesize
- 1))
1028 /* Pages that aren't in the topmost context are not collected;
1029 nevertheless, we need their in-use bit vectors to store GC
1030 marks. So, back them up first. */
1031 if (p
->context_depth
< G
.context_depth
)
1033 if (! p
->save_in_use_p
)
1034 p
->save_in_use_p
= xmalloc (bitmap_size
);
1035 memcpy (p
->save_in_use_p
, p
->in_use_p
, bitmap_size
);
1038 /* Reset reset the number of free objects and clear the
1039 in-use bits. These will be adjusted by mark_obj. */
1040 p
->num_free_objects
= num_objects
;
1041 memset (p
->in_use_p
, 0, bitmap_size
);
1043 /* Make sure the one-past-the-end bit is always set. */
1044 p
->in_use_p
[num_objects
/ HOST_BITS_PER_LONG
]
1045 = ((unsigned long) 1 << (num_objects
% HOST_BITS_PER_LONG
));
1050 /* Free all empty pages. Partially empty pages need no attention
1051 because the `mark' bit doubles as an `unused' bit. */
1058 for (order
= 2; order
< NUM_ORDERS
; order
++)
1060 /* The last page-entry to consider, regardless of entries
1061 placed at the end of the list. */
1062 page_entry
* const last
= G
.page_tails
[order
];
1064 size_t num_objects
= OBJECTS_PER_PAGE (order
);
1065 size_t live_objects
;
1066 page_entry
*p
, *previous
;
1076 page_entry
*next
= p
->next
;
1078 /* Loop until all entries have been examined. */
1081 /* Add all live objects on this page to the count of
1082 allocated memory. */
1083 live_objects
= num_objects
- p
->num_free_objects
;
1085 G
.allocated
+= OBJECT_SIZE (order
) * live_objects
;
1087 /* Only objects on pages in the topmost context should get
1089 if (p
->context_depth
< G
.context_depth
)
1092 /* Remove the page if it's empty. */
1093 else if (live_objects
== 0)
1096 G
.pages
[order
] = next
;
1098 previous
->next
= next
;
1100 /* Are we removing the last element? */
1101 if (p
== G
.page_tails
[order
])
1102 G
.page_tails
[order
] = previous
;
1107 /* If the page is full, move it to the end. */
1108 else if (p
->num_free_objects
== 0)
1110 /* Don't move it if it's already at the end. */
1111 if (p
!= G
.page_tails
[order
])
1113 /* Move p to the end of the list. */
1115 G
.page_tails
[order
]->next
= p
;
1117 /* Update the tail pointer... */
1118 G
.page_tails
[order
] = p
;
1120 /* ... and the head pointer, if necessary. */
1122 G
.pages
[order
] = next
;
1124 previous
->next
= next
;
1129 /* If we've fallen through to here, it's a page in the
1130 topmost context that is neither full nor empty. Such a
1131 page must precede pages at lesser context depth in the
1132 list, so move it to the head. */
1133 else if (p
!= G
.pages
[order
])
1135 previous
->next
= p
->next
;
1136 p
->next
= G
.pages
[order
];
1138 /* Are we moving the last element? */
1139 if (G
.page_tails
[order
] == p
)
1140 G
.page_tails
[order
] = previous
;
1149 /* Now, restore the in_use_p vectors for any pages from contexts
1150 other than the current one. */
1151 for (p
= G
.pages
[order
]; p
; p
= p
->next
)
1152 if (p
->context_depth
!= G
.context_depth
)
1153 ggc_recalculate_in_use_p (p
);
1158 /* Clobber all free objects. */
1165 for (order
= 2; order
< NUM_ORDERS
; order
++)
1167 size_t num_objects
= OBJECTS_PER_PAGE (order
);
1168 size_t size
= OBJECT_SIZE (order
);
1171 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
1175 if (p
->context_depth
!= G
.context_depth
)
1176 /* Since we don't do any collection for pages in pushed
1177 contexts, there's no need to do any poisoning. And
1178 besides, the IN_USE_P array isn't valid until we pop
1182 for (i
= 0; i
< num_objects
; i
++)
1185 word
= i
/ HOST_BITS_PER_LONG
;
1186 bit
= i
% HOST_BITS_PER_LONG
;
1187 if (((p
->in_use_p
[word
] >> bit
) & 1) == 0)
1188 memset (p
->page
+ i
* size
, 0xa5, size
);
1195 /* Top level mark-and-sweep routine. */
1200 /* Avoid frequent unnecessary work by skipping collection if the
1201 total allocations haven't expanded much since the last
1203 #ifndef GGC_ALWAYS_COLLECT
1204 if (G
.allocated
< GGC_MIN_EXPAND_FOR_GC
* G
.allocated_last_gc
)
1208 timevar_push (TV_GC
);
1210 fprintf (stderr
, " {GC %luk -> ", (unsigned long) G
.allocated
/ 1024);
1212 /* Zero the total allocated bytes. This will be recalculated in the
1216 /* Release the pages we freed the last time we collected, but didn't
1217 reuse in the interim. */
1229 G
.allocated_last_gc
= G
.allocated
;
1230 if (G
.allocated_last_gc
< GGC_MIN_LAST_ALLOCATED
)
1231 G
.allocated_last_gc
= GGC_MIN_LAST_ALLOCATED
;
1233 timevar_pop (TV_GC
);
1236 fprintf (stderr
, "%luk}", (unsigned long) G
.allocated
/ 1024);
1239 /* Print allocation statistics. */
1240 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
1242 : ((x) < 1024*1024*10 \
1244 : (x) / (1024*1024))))
1245 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
1248 ggc_print_statistics ()
1250 struct ggc_statistics stats
;
1252 size_t total_overhead
= 0;
1254 /* Clear the statistics. */
1255 memset (&stats
, 0, sizeof (stats
));
1257 /* Make sure collection will really occur. */
1258 G
.allocated_last_gc
= 0;
1260 /* Collect and print the statistics common across collectors. */
1261 ggc_print_common_statistics (stderr
, &stats
);
1263 /* Release free pages so that we will not count the bytes allocated
1264 there as part of the total allocated memory. */
1267 /* Collect some information about the various sizes of
1269 fprintf (stderr
, "\n%-5s %10s %10s %10s\n",
1270 "Log", "Allocated", "Used", "Overhead");
1271 for (i
= 0; i
< NUM_ORDERS
; ++i
)
1278 /* Skip empty entries. */
1282 overhead
= allocated
= in_use
= 0;
1284 /* Figure out the total number of bytes allocated for objects of
1285 this size, and how many of them are actually in use. Also figure
1286 out how much memory the page table is using. */
1287 for (p
= G
.pages
[i
]; p
; p
= p
->next
)
1289 allocated
+= p
->bytes
;
1291 (OBJECTS_PER_PAGE (i
) - p
->num_free_objects
) * OBJECT_SIZE (i
);
1293 overhead
+= (sizeof (page_entry
) - sizeof (long)
1294 + BITMAP_SIZE (OBJECTS_PER_PAGE (i
) + 1));
1296 fprintf (stderr
, "%-5d %10ld%c %10ld%c %10ld%c\n", i
,
1297 SCALE (allocated
), LABEL (allocated
),
1298 SCALE (in_use
), LABEL (in_use
),
1299 SCALE (overhead
), LABEL (overhead
));
1300 total_overhead
+= overhead
;
1302 fprintf (stderr
, "%-5s %10ld%c %10ld%c %10ld%c\n", "Total",
1303 SCALE (G
.bytes_mapped
), LABEL (G
.bytes_mapped
),
1304 SCALE (G
.allocated
), LABEL(G
.allocated
),
1305 SCALE (total_overhead
), LABEL (total_overhead
));