1 /* "Bag-of-pages" garbage collector for the GNU compiler.
2 Copyright (C) 1999 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. */
41 This garbage-collecting allocator allocates objects on one of a set
42 of pages. Each page can allocate objects of a single size only;
43 available sizes are powers of two starting at four bytes. The size
44 of an allocation request is rounded up to the next power of two
45 (`order'), and satisfied from the appropriate page.
47 Each page is recorded in a page-entry, which also maintains an
48 in-use bitmap of object positions on the page. This allows the
49 allocation state of a particular object to be flipped without
50 touching the page itself.
52 Each page-entry also has a context depth, which is used to track
53 pushing and popping of allocation contexts. Only objects allocated
54 in the current (highest-numbered) context may be collected.
56 Page entries are arranged in an array of singly-linked lists. The
57 array is indexed by the allocation size, in bits, of the pages on
58 it; i.e. all pages on a list allocate objects of the same size.
59 Pages are ordered on the list such that all non-full pages precede
60 all full pages, with non-full pages arranged in order of decreasing
63 Empty pages (of all orders) are kept on a single page cache list,
64 and are considered first when new pages are required; they are
65 deallocated at the start of the next collection if they haven't
66 been recycled by then. */
69 /* Define GGC_POISON to poison memory marked unused by the collector. */
72 /* Define GGC_ALWAYS_COLLECT to perform collection every time
73 ggc_collect is invoked. Otherwise, collection is performed only
74 when a significant amount of memory has been allocated since the
76 #undef GGC_ALWAYS_COLLECT
78 /* If ENABLE_CHECKING is defined, enable GGC_POISON and
79 GGC_ALWAYS_COLLECT automatically. */
80 #ifdef ENABLE_CHECKING
82 #define GGC_ALWAYS_COLLECT
85 /* Define GGC_DEBUG_LEVEL to print debugging information.
86 0: No debugging output.
87 1: GC statistics only.
88 2: Page-entry allocations/deallocations as well.
89 3: Object allocations as well.
90 4: Object marks as well. */
91 #define GGC_DEBUG_LEVEL (0)
93 #ifndef HOST_BITS_PER_PTR
94 #define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
97 /* Timing information for collect execution goes into here. */
100 /* The "" allocated string. */
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))
137 /* A page_entry records the status of an allocation page. This
138 structure is dynamically sized to fit the bitmap in_use_p. */
139 typedef struct page_entry
141 /* The next page-entry with objects of the same size, or NULL if
142 this is the last page-entry. */
143 struct page_entry
*next
;
145 /* The number of bytes allocated. (This will always be a multiple
146 of the host system page size.) */
149 /* The address at which the memory is allocated. */
152 /* Saved in-use bit vector for pages that aren't in the topmost
153 context during collection. */
154 unsigned long *save_in_use_p
;
156 /* Context depth of this page. */
157 unsigned char context_depth
;
159 /* The lg of size of objects allocated from this page. */
162 /* The number of free objects remaining on this page. */
163 unsigned short num_free_objects
;
165 /* A likely candidate for the bit position of a free object for the
166 next allocation from this page. */
167 unsigned short next_bit_hint
;
169 /* Saved number of free objects for pages that aren't in the topmost
170 context during colleciton. */
171 unsigned short save_num_free_objects
;
173 /* A bit vector indicating whether or not objects are in use. The
174 Nth bit is one if the Nth object on this page is allocated. This
175 array is dynamically sized. */
176 unsigned long in_use_p
[1];
180 #if HOST_BITS_PER_PTR <= 32
182 /* On 32-bit hosts, we use a two level page table, as pictured above. */
183 typedef page_entry
**page_table
[PAGE_L1_SIZE
];
187 /* On 64-bit hosts, we use the same two level page tables plus a linked
188 list that disambiguates the top 32-bits. There will almost always be
189 exactly one entry in the list. */
190 typedef struct page_table_chain
192 struct page_table_chain
*next
;
194 page_entry
**table
[PAGE_L1_SIZE
];
199 /* The rest of the global variables. */
200 static struct globals
202 /* The Nth element in this array is a page with objects of size 2^N.
203 If there are any pages with free objects, they will be at the
204 head of the list. NULL if there are no page-entries for this
206 page_entry
*pages
[HOST_BITS_PER_PTR
];
208 /* The Nth element in this array is the last page with objects of
209 size 2^N. NULL if there are no page-entries for this object
211 page_entry
*page_tails
[HOST_BITS_PER_PTR
];
213 /* Lookup table for associating allocation pages with object addresses. */
216 /* The system's page size. */
220 /* Bytes currently allocated. */
223 /* Bytes currently allocated at the end of the last collection. */
224 size_t allocated_last_gc
;
226 /* The current depth in the context stack. */
227 unsigned char context_depth
;
229 /* A file descriptor open to /dev/zero for reading. */
230 #if defined (HAVE_MMAP) && !defined(MAP_ANONYMOUS)
234 /* A cache of free system pages. */
235 page_entry
*free_pages
;
237 /* The file descriptor for debugging output. */
242 /* Compute DIVIDEND / DIVISOR, rounded up. */
243 #define DIV_ROUND_UP(Dividend, Divisor) \
244 ((Dividend + Divisor - 1) / Divisor)
246 /* The number of objects per allocation page, for objects of size
248 #define OBJECTS_PER_PAGE(Order) \
249 ((Order) >= G.lg_pagesize ? 1 : G.pagesize / ((size_t)1 << (Order)))
251 /* The size in bytes required to maintain a bitmap for the objects
253 #define BITMAP_SIZE(Num_objects) \
254 (DIV_ROUND_UP ((Num_objects), HOST_BITS_PER_LONG) * sizeof(long))
256 /* Skip garbage collection if the current allocation is not at least
257 this factor times the allocation at the end of the last collection.
258 In other words, total allocation must expand by (this factor minus
259 one) before collection is performed. */
260 #define GGC_MIN_EXPAND_FOR_GC (1.3)
262 /* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
263 test from triggering too often when the heap is small. */
264 #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
267 static int ggc_allocated_p
PROTO ((const void *));
268 static page_entry
*lookup_page_table_entry
PROTO ((const void *));
269 static void set_page_table_entry
PROTO ((void *, page_entry
*));
270 static char *alloc_anon
PROTO ((char *, size_t));
271 static struct page_entry
* alloc_page
PROTO ((unsigned));
272 static void free_page
PROTO ((struct page_entry
*));
273 static void release_pages
PROTO ((void));
274 static void clear_marks
PROTO ((void));
275 static void sweep_pages
PROTO ((void));
278 static void poison
PROTO ((void *, size_t));
279 static void poison_pages
PROTO ((void));
282 void debug_print_page_list
PROTO ((int));
284 /* Returns non-zero if P was allocated in GC'able memory. */
293 #if HOST_BITS_PER_PTR <= 32
296 page_table table
= G
.lookup
;
297 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
302 if (table
->high_bits
== high_bits
)
306 base
= &table
->table
[0];
309 /* Extract the level 1 and 2 indicies. */
313 return base
[L1
] && base
[L1
][L2
];
316 /* Traverse the page table and find the entry for a page.
317 Die (probably) if the object wasn't allocated via GC. */
319 static inline page_entry
*
320 lookup_page_table_entry(p
)
326 #if HOST_BITS_PER_PTR <= 32
329 page_table table
= G
.lookup
;
330 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
331 while (table
->high_bits
!= high_bits
)
333 base
= &table
->table
[0];
336 /* Extract the level 1 and 2 indicies. */
344 /* Set the page table entry for a page. */
346 set_page_table_entry(p
, entry
)
353 #if HOST_BITS_PER_PTR <= 32
357 size_t high_bits
= (size_t) p
& ~ (size_t) 0xffffffff;
358 for (table
= G
.lookup
; table
; table
= table
->next
)
359 if (table
->high_bits
== high_bits
)
362 /* Not found -- allocate a new table. */
363 table
= (page_table
) xcalloc (1, sizeof(*table
));
364 table
->next
= G
.lookup
;
365 table
->high_bits
= high_bits
;
368 base
= &table
->table
[0];
371 /* Extract the level 1 and 2 indicies. */
375 if (base
[L1
] == NULL
)
376 base
[L1
] = (page_entry
**) xcalloc (PAGE_L2_SIZE
, sizeof (page_entry
*));
378 base
[L1
][L2
] = entry
;
382 /* Prints the page-entry for object size ORDER, for debugging. */
384 debug_print_page_list (order
)
388 printf ("Head=%p, Tail=%p:\n", G
.pages
[order
], G
.page_tails
[order
]);
392 printf ("%p(%1d|%3d) -> ", p
, p
->context_depth
, p
->num_free_objects
);
400 /* `Poisons' the region of memory starting at START and extending for
407 memset (start
, 0xa5, len
);
411 /* Allocate SIZE bytes of anonymous memory, preferably near PREF,
414 alloc_anon (pref
, size
)
415 char *pref ATTRIBUTE_UNUSED
;
422 page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
423 MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
425 page
= (char *) mmap (pref
, size
, PROT_READ
| PROT_WRITE
,
426 MAP_PRIVATE
, G
.dev_zero_fd
, 0);
428 if (page
== (char *) MAP_FAILED
)
430 fputs ("Virtual memory exhausted!\n", stderr
);
435 page
= (char *) valloc (size
);
438 fputs ("Virtual memory exhausted!\n", stderr
);
441 #endif /* HAVE_VALLOC */
442 #endif /* HAVE_MMAP */
447 /* Allocate a new page for allocating objects of size 2^ORDER,
448 and return an entry for it. The entry is not added to the
449 appropriate page_table list. */
450 static inline struct page_entry
*
454 struct page_entry
*entry
, *p
, **pp
;
458 size_t page_entry_size
;
461 num_objects
= OBJECTS_PER_PAGE (order
);
462 bitmap_size
= BITMAP_SIZE (num_objects
+ 1);
463 page_entry_size
= sizeof (page_entry
) - sizeof (long) + bitmap_size
;
464 entry_size
= num_objects
* (1 << order
);
469 /* Check the list of free pages for one we can use. */
470 for (pp
= &G
.free_pages
, p
= *pp
; p
; pp
= &p
->next
, p
= *pp
)
471 if (p
->bytes
== entry_size
)
476 /* Recycle the allocated memory from this page ... */
479 /* ... and, if possible, the page entry itself. */
480 if (p
->order
== order
)
483 memset (entry
, 0, page_entry_size
);
490 /* Actually allocate the memory, using mmap. */
491 page
= alloc_anon (NULL
, entry_size
);
495 entry
= (struct page_entry
*) xcalloc (1, page_entry_size
);
497 entry
->bytes
= entry_size
;
499 entry
->context_depth
= G
.context_depth
;
500 entry
->order
= order
;
501 entry
->num_free_objects
= num_objects
;
502 entry
->next_bit_hint
= 1;
504 /* Set the one-past-the-end in-use bit. This acts as a sentry as we
505 increment the hint. */
506 entry
->in_use_p
[num_objects
/ HOST_BITS_PER_LONG
]
507 = (unsigned long) 1 << (num_objects
% HOST_BITS_PER_LONG
);
509 set_page_table_entry (page
, entry
);
511 if (GGC_DEBUG_LEVEL
>= 2)
512 fprintf (G
.debug_file
,
513 "Allocating page at %p, object size=%d, data %p-%p\n", entry
,
514 1 << order
, page
, page
+ entry_size
- 1);
520 /* Free a page when it's no longer needed. */
525 if (GGC_DEBUG_LEVEL
>= 2)
526 fprintf (G
.debug_file
,
527 "Deallocating page at %p, data %p-%p\n", entry
,
528 entry
->page
, entry
->page
+ entry
->bytes
- 1);
530 set_page_table_entry (entry
->page
, NULL
);
532 entry
->next
= G
.free_pages
;
533 G
.free_pages
= entry
;
537 /* Release the page cache to the system. */
542 page_entry
*p
, *next
;
559 /* Gather up adjacent pages so they are unmapped together. */
560 if (p
->page
== start
+ len
)
575 page_entry
*p
, *next
;
577 for (p
= G
.free_pages
; p
; p
= next
)
583 #endif /* HAVE_VALLOC */
584 #endif /* HAVE_MMAP */
590 /* This table provides a fast way to determine ceil(log_2(size)) for
591 allocation requests. The minimum allocation size is four bytes. */
592 static unsigned char const size_lookup
[257] =
594 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
595 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
596 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
597 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
598 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
599 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
600 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
601 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
602 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
603 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
604 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
605 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
606 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
607 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
608 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
609 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
613 /* Allocate a chunk of memory of SIZE bytes. If ZERO is non-zero, the
614 memory is zeroed; otherwise, its contents are undefined. */
616 ggc_alloc_obj (size
, zero
)
620 unsigned order
, word
, bit
, object_offset
;
621 struct page_entry
*entry
;
625 order
= size_lookup
[size
];
629 while (size
> ((size_t) 1 << order
))
633 /* If there are non-full pages for this size allocation, they are at
634 the head of the list. */
635 entry
= G
.pages
[order
];
637 /* If there is no page for this object size, or all pages in this
638 context are full, allocate a new page. */
640 || entry
->num_free_objects
== 0
641 || entry
->context_depth
!= G
.context_depth
)
643 struct page_entry
*new_entry
;
644 new_entry
= alloc_page (order
);
646 /* If this is the only entry, it's also the tail. */
648 G
.page_tails
[order
] = new_entry
;
650 /* Put new pages at the head of the page list. */
651 new_entry
->next
= entry
;
653 G
.pages
[order
] = new_entry
;
655 /* For a new page, we know the word and bit positions (in the
656 in_use bitmap) of the first available object -- they're zero. */
657 new_entry
->next_bit_hint
= 1;
664 /* First try to use the hint left from the previous allocation
665 to locate a clear bit in the in-use bitmap. We've made sure
666 that the one-past-the-end bit is always set, so if the hint
667 has run over, this test will fail. */
668 unsigned hint
= entry
->next_bit_hint
;
669 word
= hint
/ HOST_BITS_PER_LONG
;
670 bit
= hint
% HOST_BITS_PER_LONG
;
672 /* If the hint didn't work, scan the bitmap from the beginning. */
673 if ((entry
->in_use_p
[word
] >> bit
) & 1)
676 while (~entry
->in_use_p
[word
] == 0)
678 while ((entry
->in_use_p
[word
] >> bit
) & 1)
680 hint
= word
* HOST_BITS_PER_LONG
+ bit
;
683 /* Next time, try the next bit. */
684 entry
->next_bit_hint
= hint
+ 1;
686 object_offset
= hint
<< order
;
689 /* Set the in-use bit. */
690 entry
->in_use_p
[word
] |= ((unsigned long) 1 << bit
);
692 /* Keep a running total of the number of free objects. If this page
693 fills up, we may have to move it to the end of the list if the
694 next page isn't full. If the next page is full, all subsequent
695 pages are full, so there's no need to move it. */
696 if (--entry
->num_free_objects
== 0
697 && entry
->next
!= NULL
698 && entry
->next
->num_free_objects
> 0)
700 G
.pages
[order
] = entry
->next
;
702 G
.page_tails
[order
]->next
= entry
;
703 G
.page_tails
[order
] = entry
;
706 /* Calculate the object's address. */
707 result
= entry
->page
+ object_offset
;
710 /* `Poison' the entire allocated object before zeroing the requested area,
711 so that bytes beyond the end, if any, will not necessarily be zero. */
712 poison (result
, 1 << order
);
715 memset (result
, 0, size
);
717 /* Keep track of how many bytes are being allocated. This
718 information is used in deciding when to collect. */
719 G
.allocated
+= (size_t) 1 << order
;
721 if (GGC_DEBUG_LEVEL
>= 3)
722 fprintf (G
.debug_file
,
723 "Allocating object, requested size=%d, actual=%d at %p on %p\n",
724 (int) size
, 1 << order
, result
, entry
);
730 /* If P is not marked, marks it and returns 0. Otherwise returns 1.
731 P must have been allocated by the GC allocator; it mustn't point to
732 static objects, stack variables, or memory allocated with malloc. */
741 /* Look up the page on which the object is alloced. If the object
742 wasn't allocated by the collector, we'll probably die. */
743 entry
= lookup_page_table_entry (p
);
744 #ifdef ENABLE_CHECKING
749 /* Calculate the index of the object on the page; this is its bit
750 position in the in_use_p bitmap. */
751 bit
= (((char *) p
) - entry
->page
) >> entry
->order
;
752 word
= bit
/ HOST_BITS_PER_LONG
;
753 mask
= (unsigned long) 1 << (bit
% HOST_BITS_PER_LONG
);
755 /* If the bit was previously set, skip it. */
756 if (entry
->in_use_p
[word
] & mask
)
759 /* Otherwise set it, and decrement the free object count. */
760 entry
->in_use_p
[word
] |= mask
;
761 entry
->num_free_objects
-= 1;
763 G
.allocated
+= (size_t) 1 << entry
->order
;
765 if (GGC_DEBUG_LEVEL
>= 4)
766 fprintf (G
.debug_file
, "Marking %p\n", p
);
772 ggc_mark_if_gcable (p
)
775 if (p
&& ggc_allocated_p (p
))
779 /* Initialize the ggc-mmap allocator. */
783 G
.pagesize
= getpagesize();
784 G
.lg_pagesize
= exact_log2 (G
.pagesize
);
786 #if defined (HAVE_MMAP) && !defined(MAP_ANONYMOUS)
787 G
.dev_zero_fd
= open ("/dev/zero", O_RDONLY
);
788 if (G
.dev_zero_fd
== -1)
793 G
.debug_file
= fopen ("ggc-mmap.debug", "w");
795 G
.debug_file
= stdout
;
798 G
.allocated_last_gc
= GGC_MIN_LAST_ALLOCATED
;
800 empty_string
= ggc_alloc_string ("", 0);
801 ggc_add_string_root (&empty_string
, 1);
811 if (G
.context_depth
== 0)
819 unsigned order
, depth
;
821 depth
= --G
.context_depth
;
823 /* Any remaining pages in the popped context are lowered to the new
824 current context; i.e. objects allocated in the popped context and
825 left over are imported into the previous context. */
826 for (order
= 2; order
< HOST_BITS_PER_PTR
; order
++)
828 size_t num_objects
= OBJECTS_PER_PAGE (order
);
829 size_t bitmap_size
= BITMAP_SIZE (num_objects
);
833 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
835 if (p
->context_depth
> depth
)
837 p
->context_depth
= depth
;
840 /* If this page is now in the topmost context, and we'd
841 saved its allocation state, restore it. */
842 else if (p
->context_depth
== depth
&& p
->save_in_use_p
)
844 memcpy (p
->in_use_p
, p
->save_in_use_p
, bitmap_size
);
845 free (p
->save_in_use_p
);
846 p
->save_in_use_p
= 0;
847 p
->num_free_objects
= p
->save_num_free_objects
;
858 for (order
= 2; order
< HOST_BITS_PER_PTR
; order
++)
860 size_t num_objects
= OBJECTS_PER_PAGE (order
);
861 size_t bitmap_size
= BITMAP_SIZE (num_objects
);
864 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
866 #ifdef ENABLE_CHECKING
867 /* The data should be page-aligned. */
868 if ((size_t) p
->page
& (G
.pagesize
- 1))
872 /* Pages that aren't in the topmost context are not collected;
873 nevertheless, we need their in-use bit vectors to store GC
874 marks. So, back them up first. */
875 if (p
->context_depth
< G
.context_depth
876 && ! p
->save_in_use_p
)
878 p
->save_in_use_p
= xmalloc (bitmap_size
);
879 memcpy (p
->save_in_use_p
, p
->in_use_p
, bitmap_size
);
880 p
->save_num_free_objects
= p
->num_free_objects
;
883 /* Reset reset the number of free objects and clear the
884 in-use bits. These will be adjusted by mark_obj. */
885 p
->num_free_objects
= num_objects
;
886 memset (p
->in_use_p
, 0, bitmap_size
);
888 /* Make sure the one-past-the-end bit is always set. */
889 p
->in_use_p
[num_objects
/ HOST_BITS_PER_LONG
]
890 = ((unsigned long) 1 << (num_objects
% HOST_BITS_PER_LONG
));
900 for (order
= 2; order
< HOST_BITS_PER_PTR
; order
++)
902 /* The last page-entry to consider, regardless of entries
903 placed at the end of the list. */
904 page_entry
* const last
= G
.page_tails
[order
];
906 size_t num_objects
= OBJECTS_PER_PAGE (order
);
907 page_entry
*p
, *previous
;
917 page_entry
*next
= p
->next
;
919 /* Loop until all entries have been examined. */
922 /* Only objects on pages in the topmost context should get
924 if (p
->context_depth
< G
.context_depth
)
927 /* Remove the page if it's empty. */
928 else if (p
->num_free_objects
== num_objects
)
931 G
.pages
[order
] = next
;
933 previous
->next
= next
;
935 /* Are we removing the last element? */
936 if (p
== G
.page_tails
[order
])
937 G
.page_tails
[order
] = previous
;
942 /* If the page is full, move it to the end. */
943 else if (p
->num_free_objects
== 0)
945 /* Don't move it if it's already at the end. */
946 if (p
!= G
.page_tails
[order
])
948 /* Move p to the end of the list. */
950 G
.page_tails
[order
]->next
= p
;
952 /* Update the tail pointer... */
953 G
.page_tails
[order
] = p
;
955 /* ... and the head pointer, if necessary. */
957 G
.pages
[order
] = next
;
959 previous
->next
= next
;
964 /* If we've fallen through to here, it's a page in the
965 topmost context that is neither full nor empty. Such a
966 page must precede pages at lesser context depth in the
967 list, so move it to the head. */
968 else if (p
!= G
.pages
[order
])
970 previous
->next
= p
->next
;
971 p
->next
= G
.pages
[order
];
973 /* Are we moving the last element? */
974 if (G
.page_tails
[order
] == p
)
975 G
.page_tails
[order
] = previous
;
992 for (order
= 2; order
< HOST_BITS_PER_PTR
; order
++)
994 size_t num_objects
= OBJECTS_PER_PAGE (order
);
995 size_t size
= (size_t) 1 << order
;
998 for (p
= G
.pages
[order
]; p
!= NULL
; p
= p
->next
)
1001 for (i
= 0; i
< num_objects
; i
++)
1004 word
= i
/ HOST_BITS_PER_LONG
;
1005 bit
= i
% HOST_BITS_PER_LONG
;
1006 if (((p
->in_use_p
[word
] >> bit
) & 1) == 0)
1007 poison (p
->page
+ i
* size
, size
);
1019 /* Avoid frequent unnecessary work by skipping collection if the
1020 total allocations haven't expanded much since the last
1022 #ifndef GGC_ALWAYS_COLLECT
1023 if (G
.allocated
< GGC_MIN_EXPAND_FOR_GC
* G
.allocated_last_gc
)
1027 time
= get_run_time ();
1029 fprintf (stderr
, " {GC %luk -> ", (unsigned long)G
.allocated
/ 1024);
1031 /* Zero the total allocated bytes. We'll reaccumulate this while
1035 /* Release the pages we freed the last time we collected, but didn't
1036 reuse in the interim. */
1047 G
.allocated_last_gc
= G
.allocated
;
1048 if (G
.allocated_last_gc
< GGC_MIN_LAST_ALLOCATED
)
1049 G
.allocated_last_gc
= GGC_MIN_LAST_ALLOCATED
;
1051 time
= get_run_time () - time
;
1056 fprintf (stderr
, "%luk in %.3f}",
1057 (unsigned long) G
.allocated
/ 1024, time
* 1e-6);