2 * GENerational Conservative Garbage Collector for SBCL
6 * This software is part of the SBCL system. See the README file for
9 * This software is derived from the CMU CL system, which was
10 * written at Carnegie Mellon University and released into the
11 * public domain. The software is in the public domain and is
12 * provided with absolutely no warranty. See the COPYING and CREDITS
13 * files for more information.
17 * For a review of garbage collection techniques (e.g. generational
18 * GC) and terminology (e.g. "scavenging") see Paul R. Wilson,
19 * "Uniprocessor Garbage Collection Techniques" available at
20 * <https://www.cs.rice.edu/~javaplt/311/Readings/wilson92uniprocessor.pdf>
22 * <ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps>.
30 #include "genesis/sbcl.h"
35 #include "interrupt.h"
41 #include "pseudo-atomic.h"
43 #include "genesis/gc-tables.h"
44 #include "genesis/vector.h"
45 #include "genesis/weak-pointer.h"
46 #include "genesis/symbol.h"
47 #include "genesis/hash-table.h"
48 #include "genesis/instance.h"
49 #include "hopscotch.h"
50 #include "genesis/cons.h"
51 #include "genesis/brothertree.h"
52 #include "genesis/split-ordered-list.h"
55 /* forward declarations */
56 extern FILE *gc_activitylog();
58 /* Largest allocation seen since last GC. */
59 os_vm_size_t large_allocation
= 0;
67 /* the verbosity level. All non-error messages are disabled at level 0;
68 * and only a few rare messages are printed at level 1. */
69 int gencgc_verbose
= 0;
72 * GC structures and variables
75 /* the total bytes allocated. These are seen by Lisp DYNAMIC-USAGE. */
76 os_vm_size_t bytes_allocated
= 0;
77 os_vm_size_t auto_gc_trigger
= 0;
79 /* the source and destination generations. These are set before a GC starts
81 generation_index_t from_space
;
82 generation_index_t new_space
;
84 /* Set to 1 when in GC */
87 /* should the GC be conservative on stack. If false (only right before
88 * saving a core), don't scan the stack / mark pages pinned. */
89 bool conservative_stack
= 1;
90 int save_lisp_gc_iteration
;
92 /* An array of page structures is allocated on gc initialization.
93 * This helps to quickly map between an address and its page structure.
94 * page_table_pages is set from the size of the dynamic space. */
95 page_index_t page_table_pages
;
96 struct page
*page_table
;
97 unsigned char *gc_page_pins
;
98 unsigned char *gc_card_mark
;
99 // Filtered pins include code but not simple-funs,
100 // and must not include invalid pointers.
101 static lispobj
* gc_filtered_pins
;
102 static int pins_alloc_size
;
103 static int gc_pin_count
;
104 struct hopscotch_table pinned_objects
;
106 /* This is always 0 except during gc_and_save() */
107 lispobj lisp_init_function
;
109 static inline bool boxed_type_p(int type
) { return type
> 1; }
110 static inline bool page_boxed_p(page_index_t page
) {
111 // ignore SINGLE_OBJECT_FLAG and OPEN_REGION_PAGE_FLAG
112 return boxed_type_p(page_table
[page
].type
& PAGE_TYPE_MASK
);
115 #ifndef LISP_FEATURE_SOFT_CARD_MARKS
116 static inline bool protect_page_p(page_index_t page
, generation_index_t generation
) {
117 return (page_boxed_p(page
)
118 && !(page_table
[page
].type
& OPEN_REGION_PAGE_FLAG
)
119 && (page_words_used(page
) != 0)
120 && !gc_page_pins
[page
]
121 && (page_table
[page
].gen
== generation
));
125 /* Calculate the address where the allocation region associated with
126 * the page starts. */
128 page_scan_start(page_index_t page_index
)
130 return page_address(page_index
)-page_scan_start_offset(page_index
);
133 /* We maintain the invariant that pages with FREE_PAGE_FLAG have
134 * scan_start of zero, to optimize page_ends_contiguous_block_p().
135 * Clear all the flags that don't pertain to a free page.
136 * Particularly the 'need_zerofill' bit MUST remain as-is */
137 void reset_page_flags(page_index_t page
) {
138 page_table
[page
].scan_start_offset_
= 0;
139 set_page_type(page_table
[page
], FREE_PAGE_FLAG
);
140 gc_page_pins
[page
] = 0;
141 // Why can't the 'gen' get cleared? It caused failures. THIS MAKES NO SENSE!!!
142 // page_table[page].gen = 0;
143 // Free pages are dirty (MARKED) because MARKED is equivalent
144 // to not-write-protected, which is what you want for allocation.
145 assign_page_card_marks(page
, CARD_MARKED
);
148 #include "genesis/cardmarks.h"
149 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
150 int page_cards_all_marked_nonsticky(page_index_t page
) {
151 return cardseq_all_marked_nonsticky(page_to_card_index(page
));
155 /// External function for calling from Lisp.
156 page_index_t
ext_find_page_index(void *addr
) { return find_page_index(addr
); }
158 /* an array of generation structures. There needs to be one more
159 * generation structure than actual generations as the oldest
160 * generation is temporarily raised then lowered. */
161 struct generation generations
[NUM_GENERATIONS
];
163 /* the oldest generation that is will currently be GCed by default.
164 * Valid values are: 0, 1, ... HIGHEST_NORMAL_GENERATION
166 * The default of HIGHEST_NORMAL_GENERATION enables GC on all generations.
168 * Setting this to 0 effectively disables the generational nature of
169 * the GC. In some applications generational GC may not be useful
170 * because there are no long-lived objects.
172 * An intermediate value could be handy after moving long-lived data
173 * into an older generation so an unnecessary GC of this long-lived
174 * data can be avoided. */
175 generation_index_t gencgc_oldest_gen_to_gc
= HIGHEST_NORMAL_GENERATION
;
177 page_index_t next_free_page
; // upper (exclusive) bound on used page range
179 #ifdef LISP_FEATURE_SB_THREAD
180 /* This lock is to prevent multiple threads from simultaneously
181 * allocating new regions which overlap each other. Note that the
182 * majority of GC is single-threaded, but alloc() may be called from
183 * >1 thread at a time and must be thread-safe. This lock must be
184 * seized before all accesses to generations[] or to parts of
185 * page_table[] that other threads may want to see */
186 #ifdef LISP_FEATURE_WIN32
187 static CRITICAL_SECTION free_pages_lock
;
189 static pthread_mutex_t free_pages_lock
= PTHREAD_MUTEX_INITIALIZER
;
193 void acquire_gc_page_table_lock() { ignore_value(mutex_acquire(&free_pages_lock
)); }
194 void release_gc_page_table_lock() { ignore_value(mutex_release(&free_pages_lock
)); }
196 extern os_vm_size_t gencgc_alloc_granularity
;
197 os_vm_size_t gencgc_alloc_granularity
= GENCGC_ALLOC_GRANULARITY
;
201 * miscellaneous heap functions
204 static void show_pinnedobj_count()
208 int n_pinned_largeobj
= 0;
209 for (page
= 0; page
< next_free_page
; ++page
) {
210 if (page_table
[page
].gen
== from_space
&& gc_page_pins
[page
]
211 && page_single_obj_p(page
)) {
212 nwords
+= page_words_used(page
);
213 if (page_starts_contiguous_block_p(page
))
218 "/pinned objects(g%d): large=%d (%d words), small=%d\n",
219 from_space
, n_pinned_largeobj
, nwords
, pinned_objects
.count
);
222 /* Work through the pages and add up the number of bytes used for the
223 * given generation. */
224 static __attribute__((unused
)) os_vm_size_t
225 count_generation_bytes_allocated (generation_index_t gen
)
228 os_vm_size_t result
= 0;
229 for (i
= 0; i
< next_free_page
; i
++) {
230 if (!page_free_p(i
) && page_table
[i
].gen
== gen
)
231 result
+= page_words_used(i
);
233 return result
*N_WORD_BYTES
;
237 /* The generation currently being allocated to. */
238 static generation_index_t gc_alloc_generation
;
240 __attribute__((unused
)) static const char * const page_type_description
[8] =
241 {0, "unboxed", "boxed", "mixed", "sm_mix", "cons", "?", "code"};
244 * To support quick and inline allocation, regions of memory can be
245 * allocated and then allocated from with just a free pointer and a
246 * check against an end address.
248 * Since objects can be allocated to spaces with different properties
249 * e.g. boxed/unboxed, generation, ages; there may need to be many
250 * allocation regions.
252 * Each allocation region may start within a partly used page. Many
253 * features of memory use are noted on a page wise basis, e.g. the
254 * generation; so if a region starts within an existing allocated page
255 * it must be consistent with this page.
257 * During the scavenging of the newspace, objects will be transported
258 * into an allocation region, and pointers updated to point to this
259 * allocation region. It is possible that these pointers will be
260 * scavenged again before the allocation region is closed, e.g. due to
261 * trans_list which jumps all over the place to cleanup the list. It
262 * is important to be able to determine properties of all objects
263 * pointed to when scavenging, e.g to detect pointers to the oldspace.
264 * Thus it's important that the allocation regions have the correct
265 * properties set when allocated, and not just set when closed. The
266 * region allocation routines return regions with the specified
267 * properties, and grab all the pages, setting their properties
268 * appropriately, except that the amount used is not known.
270 * These regions are used to support quicker allocation using just a
271 * free pointer. The actual space used by the region is not reflected
272 * in the pages tables until it is closed. It can't be scavenged until
275 * When finished with the region it should be closed, which will
276 * update the page tables for the actual space used returning unused
277 * space. Further it may be noted in the new regions which is
278 * necessary when scavenging the newspace.
280 * Large objects may be allocated directly without an allocation
281 * region, the page table is updated immediately.
283 * Unboxed objects don't contain pointers to other objects and so
284 * don't need scavenging. Further they can't contain pointers to
285 * younger generations so WP is not needed. By allocating pages to
286 * unboxed objects the whole page never needs scavenging or
287 * write-protecting. */
289 /* We use five regions for the current newspace generation. */
290 struct alloc_region gc_alloc_region
[6];
293 alloc_start_pages
[8], // one for each value of PAGE_TYPE_x
294 max_alloc_start_page
; // the largest of any array element
295 page_index_t gencgc_alloc_start_page
; // initializer for the preceding array
297 /* Each 'start_page' informs the region-opening logic where it should
298 * attempt to continue allocating after closing a region associated
299 * with a particular page type. We aren't very clever about this -
300 * either the start_page has space remaining or it doesn't, and when it
301 * doesn't, then we should hop over *all* allocated pages regardless of
302 * type that intercede between the page we couldn't use up to next_free_page.
303 * It's kind of dumb that there is one start_page per type,
304 * other than it serves its purpose for picking up where it left off
305 * on a partially full page during GC */
306 #define RESET_ALLOC_START_PAGES() \
307 alloc_start_pages[0] = gencgc_alloc_start_page; \
308 alloc_start_pages[1] = gencgc_alloc_start_page; \
309 alloc_start_pages[2] = gencgc_alloc_start_page; \
310 alloc_start_pages[3] = gencgc_alloc_start_page; \
311 alloc_start_pages[4] = gencgc_alloc_start_page; \
312 alloc_start_pages[5] = gencgc_alloc_start_page; \
313 alloc_start_pages[6] = gencgc_alloc_start_page; \
314 alloc_start_pages[7] = gencgc_alloc_start_page; \
315 max_alloc_start_page = gencgc_alloc_start_page;
318 get_alloc_start_page(unsigned int page_type
)
320 if (page_type
> 7) lose("bad page_type: %d", page_type
);
321 struct thread
* th
= get_sb_vm_thread();
322 page_index_t global_start
= alloc_start_pages
[page_type
];
325 case PAGE_TYPE_MIXED
:
326 if ((hint
= thread_extra_data(th
)->mixed_page_hint
) > 0 && hint
<= global_start
) {
327 thread_extra_data(th
)->mixed_page_hint
= - 1;
332 if ((hint
= thread_extra_data(th
)->cons_page_hint
) > 0 && hint
<= global_start
) {
333 thread_extra_data(th
)->cons_page_hint
= - 1;
342 set_alloc_start_page(unsigned int page_type
, page_index_t page
)
344 if (page_type
> 7) lose("bad page_type: %d", page_type
);
345 if (page
> max_alloc_start_page
) max_alloc_start_page
= page
;
346 alloc_start_pages
[page_type
] = page
;
348 #include "private-cons.inc"
350 /* Find a new region with room for at least the given number of bytes.
352 * It starts looking at the current generation's alloc_start_page. So
353 * may pick up from the previous region if there is enough space. This
354 * keeps the allocation contiguous when scavenging the newspace.
356 * The alloc_region should have been closed by a call to
357 * gc_close_region(), and will thus be in an empty state.
359 * To assist the scavenging functions write-protected pages are not
360 * used. Free pages should not be write-protected.
362 * It is critical to the conservative GC that the start of regions be
363 * known. To help achieve this only small regions are allocated at a
366 * During scavenging, pointers may be found to within the current
367 * region and the page generation must be set so that pointers to the
368 * from space can be recognized. Therefore the generation of pages in
369 * the region are set to gc_alloc_generation. To prevent another
370 * allocation call using the same pages, all the pages in the region
371 * are allocated, although they will initially be empty.
374 #ifdef LISP_FEATURE_ALLOCATOR_METRICS
375 #define INSTRUMENTING(expression, metric) { \
376 struct timespec t0, t1; clock_gettime(CLOCK_REALTIME, &t0); expression; \
377 clock_gettime(CLOCK_REALTIME, &t1); \
378 struct thread* th = get_sb_vm_thread(); \
379 th->metric += (t1.tv_sec - t0.tv_sec)*1000000000 + (t1.tv_nsec - t0.tv_nsec); }
381 #define INSTRUMENTING(expression, metric) expression
384 /* Test whether page 'index' can continue a non-large-object region
385 * having specified 'gen' and 'type' values. It must not be pinned
386 * and must be marked but not referenced from the stack */
388 page_extensible_p(page_index_t index
, generation_index_t gen
, int type
) {
389 #ifdef LISP_FEATURE_BIG_ENDIAN /* TODO: implement this as single comparison */
390 int attributes_match
=
391 page_table
[index
].type
== type
392 && page_table
[index
].gen
== gen
393 && !gc_page_pins
[index
];
395 // FIXME: "warning: dereferencing type-punned pointer will break strict-aliasing rules"
396 int attributes_match
=
397 *(int16_t*)&page_table
[index
].type
== ((gen
<<8)|type
);
399 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
400 return attributes_match
&& page_cards_all_marked_nonsticky(index
);
402 return attributes_match
&& !PAGE_WRITEPROTECTED_P(index
);
406 void gc_heap_exhausted_error_or_lose (sword_t available
, sword_t requested
) never_returns
;
408 /* Find a single page for conses or SMALL_MIXED objects.
409 * CONS differs because:
410 * - not all GENCGC_PAGE_BYTES of the page can be used.
411 * - a region can't be extended from one page to the next
412 * (implied by the preceding restriction).
413 * SMALL_MIXED is similar to cons, but all bytes of the page can be used
414 * for storing objects, subject to the non-card-spaning constraint. */
415 static page_index_t
find_single_page(int page_type
, sword_t nbytes
, generation_index_t gen
)
417 page_index_t page
= alloc_start_pages
[page_type
];;
418 // Compute the max words that could already be used while satisfying the request.
419 page_words_t usage_allowance
;
420 if (page_type
== PAGE_TYPE_CONS
) {
421 gc_assert(nbytes
<= CONS_PAGE_USABLE_BYTES
);
422 usage_allowance
= (CONS_SIZE
*MAX_CONSES_PER_PAGE
) - (nbytes
>>WORD_SHIFT
);
424 gc_assert(page_type
== PAGE_TYPE_SMALL_MIXED
);
425 usage_allowance
= GENCGC_PAGE_BYTES
/N_WORD_BYTES
- (nbytes
>>WORD_SHIFT
);
427 for ( ; page
< page_table_pages
; ++page
) {
428 if (page_words_used(page
) <= usage_allowance
429 && (page_free_p(page
) || page_extensible_p(page
, gen
, page_type
))) return page
;
431 /* Compute the "available" space for the lossage message. This is kept out of the
432 * search loop because it's needless overhead. Any free page would have been returned,
433 * so we just have to find the least full page meeting the gen+type criteria */
434 sword_t min_used
= GENCGC_PAGE_WORDS
;
435 for ( page
= alloc_start_pages
[page_type
]; page
< page_table_pages
; ++page
) {
436 if (page_words_used(page
) < min_used
&& page_extensible_p(page
, gen
, page_type
))
437 min_used
= page_words_used(page
);
440 if (page_type
== PAGE_TYPE_CONS
) {
441 bytes_avail
= CONS_PAGE_USABLE_BYTES
- (min_used
<<WORD_SHIFT
);
442 /* The sentinel value initially in 'least_words_used' exceeds a cons
443 * page's capacity, so clip to 0 instead of showing a negative value
444 * if no page matched on gen+type */
445 if (bytes_avail
< 0) bytes_avail
= 0;
447 bytes_avail
= GENCGC_PAGE_BYTES
- (min_used
<<WORD_SHIFT
);
449 gc_heap_exhausted_error_or_lose(bytes_avail
, nbytes
);
453 bool page_is_zeroed(page_index_t page
)
455 int nwords_per_page
= GENCGC_PAGE_BYTES
/N_WORD_BYTES
;
456 uword_t
*pagebase
= (void*)page_address(page
);
458 for (i
=0; i
<nwords_per_page
; ++i
) if (pagebase
[i
]) return 0;
464 gc_alloc_new_region(sword_t nbytes
, int page_type
, struct alloc_region
*alloc_region
, int unlock
)
466 /* Check that the region is in a reset state. */
467 gc_dcheck(!alloc_region
->start_addr
);
469 if (page_type
== PAGE_TYPE_CONS
|| page_type
== PAGE_TYPE_SMALL_MIXED
) {
470 // No mutex release, because either this is:
471 // - not called from Lisp, as in the SMALL_MIXED case
472 // - called from lisp_alloc() which does its own unlock
475 INSTRUMENTING(page
= find_single_page(page_type
, nbytes
, gc_alloc_generation
),
476 et_find_freeish_page
);
477 if (page
+1 > next_free_page
) next_free_page
= page
+1;
478 page_table
[page
].gen
= gc_alloc_generation
;
479 set_page_type(page_table
[page
], OPEN_REGION_PAGE_FLAG
| page_type
);
480 if (!page_words_used(page
))
481 prepare_pages(1, page
, page
, page_type
, gc_alloc_generation
);
482 // Don't need to set the scan_start_offset because free pages have it 0
483 // (and each of these page types starts a new contiguous block)
484 gc_dcheck(page_table
[page
].scan_start_offset_
== 0);
485 alloc_region
->start_addr
= page_address(page
) + page_bytes_used(page
);
486 if (page_type
== PAGE_TYPE_CONS
) {
487 alloc_region
->end_addr
= page_address(page
) + CONS_PAGE_USABLE_BYTES
;
489 alloc_region
->end_addr
=
490 (char*)ALIGN_DOWN((uword_t
)alloc_region
->start_addr
, GENCGC_CARD_BYTES
) + GENCGC_CARD_BYTES
;
492 alloc_region
->free_pointer
= alloc_region
->start_addr
;
493 gc_assert(find_page_index(alloc_region
->start_addr
) == page
);
494 return alloc_region
->free_pointer
;
497 page_index_t first_page
= get_alloc_start_page(page_type
), last_page
;
500 last_page
= gc_find_freeish_pages(&first_page
, nbytes
,
501 ((nbytes
>= (sword_t
)GENCGC_PAGE_BYTES
) ?
502 SINGLE_OBJECT_FLAG
: 0) | page_type
,
503 gc_alloc_generation
),
504 et_find_freeish_page
);
506 /* Set up the alloc_region. */
507 alloc_region
->start_addr
= page_address(first_page
) + page_bytes_used(first_page
);
508 alloc_region
->free_pointer
= alloc_region
->start_addr
;
509 alloc_region
->end_addr
= page_address(last_page
+1);
510 gc_assert(find_page_index(alloc_region
->start_addr
) == first_page
);
512 /* Set up the pages. */
514 /* The first page may have already been in use. */
515 /* If so, just assert that it's consistent, otherwise, set it up. */
516 if (page_words_used(first_page
)) {
517 gc_assert(page_table
[first_page
].type
== page_type
);
518 gc_assert(page_table
[first_page
].gen
== gc_alloc_generation
);
520 page_table
[first_page
].gen
= gc_alloc_generation
;
522 set_page_type(page_table
[first_page
], OPEN_REGION_PAGE_FLAG
| page_type
);
525 for (i
= first_page
+1; i
<= last_page
; i
++) {
526 set_page_type(page_table
[i
], OPEN_REGION_PAGE_FLAG
| page_type
);
527 page_table
[i
].gen
= gc_alloc_generation
;
528 set_page_scan_start_offset(i
,
529 addr_diff(page_address(i
), alloc_region
->start_addr
));
532 int __attribute__((unused
)) ret
= mutex_release(&free_pages_lock
);
536 if (page_words_used(first_page
)) ++first_page
;
537 if (first_page
<= last_page
)
538 INSTRUMENTING(prepare_pages(1, first_page
, last_page
, page_type
, gc_alloc_generation
),
541 return alloc_region
->free_pointer
;
544 /* The new_object structure holds the page, byte offset, and size of
545 * new regions of objects. Each new area is placed in the array of
546 * these structures pointer to by new_areas. new_areas_index holds the
547 * offset into new_areas.
549 * If new_area overflows NUM_NEW_AREAS then it stops adding them. The
550 * later code must detect this and handle it, probably by doing a full
551 * scavenge of a generation. */
552 #define NUM_NEW_AREAS 512
554 /* 'record_new_regions_below' is the page number (strictly) below which
555 * allocations must be tracked. Choosing the boundary cases with care allows
556 * for all the required modes of operation without an additional control flag:
557 * (1) When allocating from Lisp code, we need not record regions into areas.
558 * In this case 'record_new_regions_below' is 0,
559 * because no page index is less than that value.
560 * (2) When performing a full scavenge of newspace, we record regions below the
561 * highest scavenged page thus far. Pages ahead of (at a higher index than)
562 * the pointer which walks all pages can be ignored, because those pages
563 * will be scavenged in the future regardless of where allocations occur.
564 * (3) When iteratively scavenging newspace, all regions are tracked in areas,
565 * so this variable is set to 1+page_table_pages,
566 * because every page index is less than that sentinel value.
568 static page_index_t record_new_regions_below
;
574 static struct new_area
*new_areas
;
575 static int new_areas_index
;
576 int new_areas_index_hwm
; // high water mark
578 /* Add a new area to new_areas. */
580 add_new_area(page_index_t first_page
, size_t offset
, size_t size
)
582 if (!(first_page
< record_new_regions_below
))
585 /* Ignore if full. */
586 // Technically overflow occurs at 1+ this number, but it's not worth
587 // losing sleep (or splitting hairs) over one potentially wasted array cell.
588 // i.e. overflow did not necessarily happen if we needed _exactly_ this
589 // many areas. But who cares? The limit should not be approached at all.
590 if (new_areas_index
>= NUM_NEW_AREAS
)
593 size_t new_area_start
= npage_bytes(first_page
) + offset
;
596 char* base
= page_address(first_page
) + offset
;
597 fprintf(gc_activitylog(), "enqueue rescan [%p:%p]\n", base
, base
+size
);
599 /* Search backwards for a prior area that this follows from. If
600 found this will save adding a new area. */
601 for (i
= new_areas_index
-1, c
= 0; (i
>= 0) && (c
< 8); i
--, c
++) {
603 npage_bytes(new_areas
[i
].page
) + new_areas
[i
].offset
+ new_areas
[i
].size
;
604 if (new_area_start
== area_end
) {
605 new_areas
[i
].size
+= size
;
610 new_areas
[new_areas_index
].page
= first_page
;
611 new_areas
[new_areas_index
].offset
= offset
;
612 new_areas
[new_areas_index
].size
= size
;
616 /* Update the PTEs for the alloc_region. The region may be added to
619 * When done the alloc_region is set up so that the next quick alloc
620 * will fail safely and thus a new region will be allocated. Further
621 * it is safe to try to re-update the page table of this reset
624 * This is the internal implementation of ensure_region_closed(),
625 * and not to be invoked as the interface to closing a region.
627 * Note that in no case will closing a region alter the need_to_zero bit
628 * on any page in the region. It is legal to set that bit as late as possible,
629 * because we only have to know just-in-time - when changing the page
630 * (at some point later) from FREE to non-free - whether to zeroize it.
631 * Therefore, we can set the need_to_zero bit only when there is otherwise
632 * no way to detect that it ever held nonzero data, namely immediately
633 * before doing reset_page_flags() or setting the words_used to 0.
634 * Reflecting the words_used into that bit each time we update words_used
635 * from a region's free pointer would be redundant (newspace scavenging
636 * can open/close/open/close a region several times on the same page).
639 gc_close_region(struct alloc_region
*alloc_region
, int page_type
)
641 page_index_t first_page
= find_page_index(alloc_region
->start_addr
);
642 int type
= page_table
[first_page
].type
;
643 gc_assert(type
& OPEN_REGION_PAGE_FLAG
);
644 char *page_base
= page_address(first_page
);
646 // page_bytes_used() can be done without holding a lock. Nothing else
647 // affects the usage on the first page of a region owned by this thread.
648 page_bytes_t orig_first_page_bytes_used
= page_bytes_used(first_page
);
649 gc_assert(alloc_region
->start_addr
== page_base
+ orig_first_page_bytes_used
);
650 // Mark the region as closed on its first page.
651 page_table
[first_page
].type
= type
^ OPEN_REGION_PAGE_FLAG
;
653 page_index_t next_page
= first_page
+1;
654 char *free_pointer
= alloc_region
->free_pointer
;
656 if (free_pointer
!= alloc_region
->start_addr
) {
657 /* some bytes were allocated in the region */
659 /* All the pages used need to be updated */
661 /* Update the first page. */
662 if (!orig_first_page_bytes_used
)
663 gc_assert(page_starts_contiguous_block_p(first_page
));
665 gc_assert(page_table
[first_page
].type
== page_type
);
666 gc_assert(page_table
[first_page
].gen
== gc_alloc_generation
);
668 /* Calculate the number of bytes used in this page. This is not
669 * always the number of new bytes, unless it was free. */
670 os_vm_size_t bytes_used
= addr_diff(free_pointer
, page_base
);
672 if ((more
= (bytes_used
> GENCGC_PAGE_BYTES
)))
673 bytes_used
= GENCGC_PAGE_BYTES
;
674 set_page_bytes_used(first_page
, bytes_used
);
676 /* 'region_size' will be the sum of new bytes consumed by the region,
677 * EXCLUDING any part of the first page already in use,
678 * and any unused part of the final used page */
679 os_vm_size_t region_size
= bytes_used
- orig_first_page_bytes_used
;
681 /* All the rest of the pages should be accounted for. */
683 gc_assert(page_table
[next_page
].type
==
684 (OPEN_REGION_PAGE_FLAG
| page_type
));
685 page_table
[next_page
].type
^= OPEN_REGION_PAGE_FLAG
;
686 gc_assert(page_words_used(next_page
) == 0);
687 gc_assert(page_table
[next_page
].gen
== gc_alloc_generation
);
688 page_base
+= GENCGC_PAGE_BYTES
;
689 gc_assert(page_scan_start_offset(next_page
) ==
690 addr_diff(page_base
, alloc_region
->start_addr
));
692 /* Calculate the number of bytes used in this page. */
693 bytes_used
= addr_diff(free_pointer
, page_base
);
694 if ((more
= (bytes_used
> GENCGC_PAGE_BYTES
)))
695 bytes_used
= GENCGC_PAGE_BYTES
;
696 set_page_bytes_used(next_page
, bytes_used
);
697 region_size
+= bytes_used
;
702 // Now 'next_page' is 1 page beyond those fully accounted for.
703 gc_assert(addr_diff(free_pointer
, alloc_region
->start_addr
) == region_size
);
704 // Update the global totals
705 bytes_allocated
+= region_size
;
706 generations
[gc_alloc_generation
].bytes_allocated
+= region_size
;
708 /* Set the alloc restart page to the last page of the region. */
709 set_alloc_start_page(page_type
, next_page
-1);
711 /* Add the region to the new_areas if requested. */
712 if (boxed_type_p(page_type
))
713 add_new_area(first_page
, orig_first_page_bytes_used
, region_size
);
715 } else if (!orig_first_page_bytes_used
) {
716 /* The first page is completely unused. Unallocate it */
717 reset_page_flags(first_page
);
720 /* Unallocate any unused pages. */
721 page_index_t region_last_page
= find_page_index((char*)alloc_region
->end_addr
-1);
722 while (next_page
<= region_last_page
) {
723 gc_assert(page_words_used(next_page
) == 0);
724 reset_page_flags(next_page
);
727 gc_set_region_empty(alloc_region
);
730 /* Allocate a possibly large object. */
731 void *gc_alloc_large(sword_t nbytes
, int page_type
)
733 page_index_t first_page
, last_page
;
734 // Large BOXED would serve no purpose beyond MIXED, and "small large" is illogical.
735 if (page_type
== PAGE_TYPE_BOXED
|| page_type
== PAGE_TYPE_SMALL_MIXED
)
736 page_type
= PAGE_TYPE_MIXED
;
738 int locked
= !gc_active_p
;
740 int __attribute__((unused
)) ret
= mutex_acquire(&free_pages_lock
);
744 first_page
= max_alloc_start_page
;
746 last_page
= gc_find_freeish_pages(&first_page
, nbytes
,
747 SINGLE_OBJECT_FLAG
| page_type
,
748 gc_alloc_generation
),
749 et_find_freeish_page
);
750 // No need to check whether last_page > old max; it's gotta be.
751 max_alloc_start_page
= last_page
;
753 /* Set up the pages. */
755 for (page
= first_page
; page
<= last_page
; ++page
) {
756 /* Large objects don't share pages with other objects. */
757 gc_assert(page_words_used(page
) == 0);
758 set_page_type(page_table
[page
], SINGLE_OBJECT_FLAG
| page_type
);
759 page_table
[page
].gen
= gc_alloc_generation
;
762 #ifdef LISP_FEATURE_WIN32
763 // don't incur access violations
764 os_commit_memory(page_address(first_page
), npage_bytes(1+last_page
-first_page
));
767 // Store a filler so that a linear heap walk does not try to examine
768 // these pages cons-by-cons (or whatever they happen to look like).
769 // A concurrent walk would probably crash anyway, and most certainly
770 // will if it uses the page tables while this allocation is partway
771 // through assigning bytes_used per page.
772 // The fix for that is clear: MAP-OBJECTS-IN-RANGE should acquire
773 // free_pages_lock when computing the extent of a contiguous block.
774 // Anyway it's best if the new page resembles a valid object ASAP.
775 uword_t nwords
= nbytes
>> WORD_SHIFT
;
776 lispobj
* addr
= (lispobj
*)page_address(first_page
);
778 /* The test of whether to use THREAD_JIT_WP here is not based on 'page_type'
779 * but rather how the page _is_mapped_now_. Conservatively do the call
780 * because thning about all 4 combinations of how-it-was-mapped x how-it-will-be-mapped,
781 * here and down below is too confusing */
782 if (locked
) { THREAD_JIT_WP(0); }
783 *addr
= make_filler_header(nwords
);
785 os_vm_size_t scan_start_offset
= 0;
786 for (page
= first_page
; page
< last_page
; ++page
) {
787 set_page_scan_start_offset(page
, scan_start_offset
);
788 set_page_bytes_used(page
, GENCGC_PAGE_BYTES
);
789 scan_start_offset
+= GENCGC_PAGE_BYTES
;
791 page_bytes_t final_bytes_used
= nbytes
- scan_start_offset
;
792 gc_dcheck((nbytes
% GENCGC_PAGE_BYTES
? nbytes
% GENCGC_PAGE_BYTES
793 : GENCGC_PAGE_BYTES
) == final_bytes_used
);
794 set_page_scan_start_offset(last_page
, scan_start_offset
);
795 set_page_bytes_used(last_page
, final_bytes_used
);
796 bytes_allocated
+= nbytes
;
797 generations
[gc_alloc_generation
].bytes_allocated
+= nbytes
;
800 int __attribute__((unused
)) ret
= mutex_release(&free_pages_lock
);
803 INSTRUMENTING(prepare_pages(0, first_page
, last_page
, page_type
, gc_alloc_generation
),
806 /* Add the region to the new_areas if requested. */
807 if (boxed_type_p(page_type
)) add_new_area(first_page
, 0, nbytes
);
809 // page may have not needed zeroing, but first word was stored,
810 // turning the putative object temporarily into a page filler object.
811 // Now turn it back into free space.
813 if (locked
) { THREAD_JIT_WP(1); }
818 /* Search for at least nbytes of space, possibly picking up any
819 * remaining space on the tail of a page that was not fully used.
821 * The found space is guaranteed to be page-aligned if the SINGLE_OBJECT_FLAG
822 * bit is set in page_type.
825 gc_find_freeish_pages(page_index_t
*restart_page_ptr
, sword_t nbytes
,
826 int page_type
, generation_index_t gen
)
828 page_index_t most_bytes_found_from
= 0, most_bytes_found_to
= 0;
829 page_index_t first_page
, last_page
, restart_page
= *restart_page_ptr
;
830 sword_t nbytes_goal
= nbytes
;
831 sword_t bytes_found
= 0;
832 sword_t most_bytes_found
= 0;
833 int multi_object
= !(page_type
& SINGLE_OBJECT_FLAG
);
834 /* FIXME: assert(free_pages_lock is held); */
837 if (nbytes_goal
< (sword_t
)gencgc_alloc_granularity
)
838 nbytes_goal
= gencgc_alloc_granularity
;
839 #if !defined(LISP_FEATURE_64_BIT)
840 // Increase the region size to avoid excessive fragmentation
841 if (page_type
== PAGE_TYPE_CODE
&& nbytes_goal
< 65536)
845 page_type
&= ~SINGLE_OBJECT_FLAG
;
847 gc_assert(nbytes
>=0);
848 first_page
= restart_page
;
849 while (first_page
< page_table_pages
) {
851 if (page_free_p(first_page
)) {
852 gc_dcheck(!page_words_used(first_page
));
853 bytes_found
= GENCGC_PAGE_BYTES
;
854 } else if (multi_object
&&
855 // Never return a range starting with a 100% full page
856 (bytes_found
= GENCGC_PAGE_BYTES
857 - page_bytes_used(first_page
)) > 0 &&
858 // "extensible" means all PTE fields are compatible
859 page_extensible_p(first_page
, gen
, page_type
)) {
860 // TODO: Now that BOXED, CONS, and SMALL_MIXED pages exist, investigate
861 // whether the bias against returning partial pages is still useful.
862 // It probably isn't.
863 if (bytes_found
< nbytes
&& !is_code(page_type
)) {
864 if (bytes_found
> most_bytes_found
)
865 most_bytes_found
= bytes_found
;
873 #ifndef LISP_FEATURE_SOFT_CARD_MARKS
874 gc_dcheck(!PAGE_WRITEPROTECTED_P(first_page
));
876 /* page_free_p() can legally be used at index 'page_table_pages'
877 * because the array dimension is 1+page_table_pages */
878 for (last_page
= first_page
+1;
879 bytes_found
< nbytes_goal
&&
880 page_free_p(last_page
) && last_page
< page_table_pages
;
882 /* page_free_p() implies 0 bytes used, thus GENCGC_PAGE_BYTES available.
883 * It also implies !write_protected, and if the OS's conception were
884 * otherwise, lossage would routinely occur in the fault handler) */
885 bytes_found
+= GENCGC_PAGE_BYTES
;
886 gc_dcheck(!page_words_used(last_page
));
887 #ifndef LISP_FEATURE_SOFT_CARD_MARKS
888 gc_dcheck(!PAGE_WRITEPROTECTED_P(last_page
));
892 if (bytes_found
> most_bytes_found
) {
893 most_bytes_found
= bytes_found
;
894 most_bytes_found_from
= first_page
;
895 most_bytes_found_to
= last_page
;
897 if (bytes_found
>= nbytes_goal
)
900 first_page
= last_page
;
903 bytes_found
= most_bytes_found
;
904 restart_page
= first_page
+ 1;
906 /* Check for a failure */
907 if (bytes_found
< nbytes
) {
908 gc_assert(restart_page
>= page_table_pages
);
909 gc_heap_exhausted_error_or_lose(most_bytes_found
, nbytes
);
912 gc_assert(most_bytes_found_to
);
913 // most_bytes_found_to is the upper exclusive bound on the found range.
914 // next_free_page is the high water mark of most_bytes_found_to.
915 if (most_bytes_found_to
> next_free_page
) next_free_page
= most_bytes_found_to
;
916 *restart_page_ptr
= most_bytes_found_from
;
917 return most_bytes_found_to
-1;
920 /* Allocate bytes. The fast path of gc_general_alloc() calls this
921 * when it can't fit in the open region.
922 * This entry point is only for use within the GC itself.
923 * The Lisp region overflow handler either directly calls gc_alloc_large
924 * or closes and opens a region if the allocation is small.
926 * There are two general approaches to handling SMALL_MIXED allocations:
927 * 1. always open the alloc region as whole page, but hack up gc_general_alloc
928 * to avoid spanning cards in the fast case.
929 * 2. open the region as one card, and alter the slow case to try consuming
930 * the next card on the same page if it can.
931 * Choice 2 is better because choice 1 makes an extra test for page_type
932 * in each call to gc_general_alloc.
934 static void *new_region(struct alloc_region
* region
, sword_t nbytes
, int page_type
)
936 ensure_region_closed(region
, page_type
);
937 void* new_obj
= gc_alloc_new_region(nbytes
, page_type
, region
, 0);
938 region
->free_pointer
= (char*)new_obj
+ nbytes
;
939 gc_assert(region
->free_pointer
<= region
->end_addr
);
942 void *collector_alloc_fallback(struct alloc_region
* region
, sword_t nbytes
, int page_type
)
944 /* If this is a normal GC - as opposed to "final" GC just prior to saving
945 * a core, then we should never copy a large object (not that that's the best
946 * strategy always, because it entirely precludes defragmenting those objects).
947 * But unfortunately we can't assert that only small objects are seen here,
948 * because genesis does not use large-object pages. So cold-init could fail,
949 * depending on whether objects in the cold core are sufficiently large that
950 * they ought to have gone on large object pages if they could have. */
951 if (nbytes
>= LARGE_OBJECT_SIZE
) return gc_alloc_large(nbytes
, page_type
);
953 if (page_type
!= PAGE_TYPE_SMALL_MIXED
) return new_region(region
, nbytes
, page_type
);
955 #define SMALL_MIXED_NWORDS_LIMIT 10
956 #define SMALL_MIXED_NBYTES_LIMIT (SMALL_MIXED_NWORDS_LIMIT * N_WORD_BYTES)
957 /* We're want to try to place mix raw/tagged slot objects such that they don't span cards.
958 * There are essentially three cases:
959 * (1) If the object size exceeds one card, we go straight to the MIXED region.
960 * (2) If the object size is <= SMALL_MIXED_NWORDS_LIMIT, we will _always_ place it
961 * on one card. To do that, just align up to the next card or whole page
962 * if it would span cards based on the current free_pointer.
963 * This wastes at most SMALL_MIXED_NWORDS_LIMIT - 2 words, per card.
964 * (3) If the object is larger than that, we will waste at most the threshold number
965 * of words, but if it would waste more, we use the MIXED region.
966 * So this case opportunistically uses the subcard region if it can */
967 if ((int)nbytes
> (int)GENCGC_CARD_BYTES
)
968 return new_region(mixed_region
, nbytes
, PAGE_TYPE_MIXED
);
969 if (!region
->start_addr
) { // region is not in an open state
970 /* Don't try to request too much, because that might return a brand new page,
971 * when we could have kept going on the same page with small objects.
972 * Better to put the threshold-exceeding object in the MIXED region */
973 int request
= nbytes
> SMALL_MIXED_NBYTES_LIMIT
? SMALL_MIXED_NBYTES_LIMIT
: nbytes
;
974 void* new_obj
= gc_alloc_new_region(request
, page_type
, region
, 0);
975 char* new_freeptr
= (char*)new_obj
+ nbytes
;
976 /* alloc_new_region() ensures that the page it returns has at least 'nbytes' more
977 * but does *not* ensure that there is that much space below the end of the region.
978 * This is a little weird, but doing things this way confines the filler insertion
979 * logic to just here instead of also being also in alloc_new_region.
980 * You could try to put that logic only in alloc_new_region, but doing that has
981 * its own down-side: to call alloc_new_region, you first have to close the region,
982 * which entails extra work in sync'ing the PTE when we don't really need to */
983 if (new_freeptr
<= (char*)region
->end_addr
) {
984 region
->free_pointer
= new_freeptr
;
988 __attribute__((unused
)) page_index_t fpi
= find_page_index(region
->start_addr
);
989 __attribute__((unused
)) page_index_t lpi
= find_page_index((char*)region
->end_addr
-1);
990 gc_assert(fpi
== lpi
);
991 gc_assert(page_table
[fpi
].type
& OPEN_REGION_PAGE_FLAG
);
992 // Region is open, but card at free_pointer lacks sufficient space.
993 // See if there's another card on the same page.
994 char* page_base
= PTR_ALIGN_DOWN(region
->start_addr
, GENCGC_PAGE_BYTES
);
995 char* next_card
= PTR_ALIGN_UP(region
->free_pointer
, GENCGC_CARD_BYTES
);
996 if (next_card
< page_base
+ GENCGC_PAGE_BYTES
) {
997 int fill_nbytes
= next_card
- (char*)region
->free_pointer
;
999 int fill_nwords
= fill_nbytes
>> WORD_SHIFT
;
1000 /* Object size might strictly exceed SMALL_MIXED_NWORDS_LIMIT.
1001 * Never insert that much filler */
1002 if (fill_nwords
>= SMALL_MIXED_NWORDS_LIMIT
)
1003 return new_region(mixed_region
, nbytes
, PAGE_TYPE_MIXED
);
1004 *(lispobj
*)region
->free_pointer
= make_filler_header(fill_nwords
);
1006 region
->end_addr
= next_card
+ GENCGC_CARD_BYTES
;
1007 void* new_obj
= next_card
;
1008 region
->free_pointer
= (char*)new_obj
+ nbytes
;
1009 gc_assert(region
->free_pointer
<= region
->end_addr
);
1012 /* Now be careful not to waste too much at the end of the page in the following situation:
1013 * page has 20 words more, but we need 24 words. Use the MIXED region because the subcard
1014 * region has room for anywhere from 2 to 10 more objects depending on how small */
1015 if (nbytes
> SMALL_MIXED_NBYTES_LIMIT
)
1016 return new_region(mixed_region
, nbytes
, PAGE_TYPE_MIXED
);
1017 /* Consider the following: suppose upon entry to this function, the region was already open,
1018 * and free_pointer was positioned to its page's last card. The request exceeded the
1019 * remaining space. Because the region was open, "if (!region->start_addr)" was skipped, and
1020 * because it lacks more space, "if (next_card < page_base + GENCGC_PAGE_BYTES)" failed.
1021 * So the region gets closed and we grab a new page. Here was a bug: if that new page needs to
1022 * advance to its next card, we fail the assertion in new_region() that the free pointer can
1023 * simply be be bumped up while remaining <= end_addr. But we _do_ know that the new page can
1024 * accommodate the current request without spanning cards. Proof: if the space remaining below
1025 * region->end_addr is < nbytes, but the space on the page is at least nbytes (as implied by
1026 * the fact that the page was selected), then there exists a next card. The next card holds
1027 * GENCGC_CARD_BYTES, which exceeds SMALL_MIXED_NBYTES_LIMIT. Therefore in this final case,
1028 * we need to open a region but check whether to advance to a new card */
1029 ensure_region_closed(region
, page_type
);
1030 void* new_obj
= gc_alloc_new_region(nbytes
, page_type
, region
, 0);
1031 void* new_freeptr
= (char*)new_obj
+ nbytes
;
1032 if (new_freeptr
<= region
->end_addr
) {
1033 region
->free_pointer
= new_freeptr
;
1035 next_card
= PTR_ALIGN_UP(new_obj
, GENCGC_CARD_BYTES
);
1036 page_base
= PTR_ALIGN_DOWN(region
->start_addr
, GENCGC_PAGE_BYTES
);
1037 gc_assert(next_card
< page_base
+ GENCGC_PAGE_BYTES
);
1038 int fill_nbytes
= next_card
- (char*)new_obj
;
1040 int fill_nwords
= fill_nbytes
>> WORD_SHIFT
;
1041 *(lispobj
*)region
->free_pointer
= make_filler_header(fill_nwords
);
1043 region
->end_addr
= next_card
+ GENCGC_CARD_BYTES
;
1044 new_obj
= next_card
;
1045 region
->free_pointer
= (char*)new_obj
+ nbytes
;
1046 gc_assert(region
->free_pointer
<= region
->end_addr
);
1052 /* Free any trailing pages of the object starting at 'first_page'
1053 * that are currently unused due to object shrinkage.
1054 * Possibly assign different 'gen' and 'allocated' values.
1056 * maybe_adjust_large_object() specifies 'from_space' for 'new_gen'
1057 * and copy_potential_large_object() specifies 'new_space'
1059 * Note that creating a large object might not affect the 'need_to_zero'
1060 * flag on any of pages consumed (it would if the page type demands prezeroing
1061 * and wasn't zero), but freeing the unused pages of a shrunken object DOES
1062 * set the need_to_zero bit unconditionally. We have to suppose that the object
1063 * constructor wrote bytes on each of its pages, and we don't know whether the tail
1064 * of the object got zeroed versus bashed into FILLER_WIDETAG + random bits.
1067 static uword_t
adjust_obj_ptes(page_index_t first_page
,
1069 generation_index_t new_gen
,
1072 int old_allocated
= page_table
[first_page
].type
;
1073 sword_t remaining_bytes
= nwords
* N_WORD_BYTES
;
1074 page_index_t n_full_pages
= nwords
/ (GENCGC_PAGE_BYTES
/ N_WORD_BYTES
);
1075 page_bytes_t excess
= remaining_bytes
& (GENCGC_PAGE_BYTES
- 1);
1076 // page number of ending page of this object at its new size
1077 page_index_t final_page
= first_page
+ (n_full_pages
- 1) + (excess
!= 0);
1079 /* Decide whether there is anything to do by checking whether:
1080 * (1) the page at n_full_pages-1 beyond the first is fully used,
1081 * (2) the next fractional page, if any, has correct usage, and
1082 * (3) the page after that is not part of this object.
1083 * If all those conditions are met, this is the easy case,
1084 * though we may still have to change the generation and/or page type. */
1085 if ((!n_full_pages
|| page_words_used(first_page
+(n_full_pages
-1))
1086 == GENCGC_PAGE_WORDS
) &&
1087 (!excess
|| page_bytes_used(final_page
) == excess
) &&
1088 page_starts_contiguous_block_p(1+final_page
)) {
1089 /* The 'if' below has an 'else' which subsumes the 'then' in generality.
1090 * Why? Because usually we only need perform one assignment.
1091 * Moreover, after a further change which makes us not look at the 'gen'
1092 * of the *interior* of a page-spanning object, then the fast case
1093 * reduces to "page_table[first_page].gen = new_gen". And we're done.
1094 * At present, some logic assumes that every page's gen was updated */
1096 if (old_allocated
== new_allocated
) { // Almost always true,
1097 // except when bignums or specialized arrays change from thread-local
1098 // (boxed) allocation to unboxed, for downstream efficiency.
1099 for (page
= first_page
; page
<= final_page
; ++page
)
1100 page_table
[page
].gen
= new_gen
;
1102 for (page
= first_page
; page
<= final_page
; ++page
) {
1103 set_page_type(page_table
[page
], new_allocated
);
1104 page_table
[page
].gen
= new_gen
;
1110 /* The assignments to the page table here affect only one object
1111 * since its pages can't be shared with other objects */
1112 #define CHECK_AND_SET_PTE_FIELDS() \
1113 gc_assert(page_table[page].type == old_allocated); \
1114 gc_assert(page_table[page].gen == from_space); \
1115 gc_assert(page_scan_start_offset(page) == npage_bytes(page-first_page)); \
1116 page_table[page].gen = new_gen; \
1117 set_page_type(page_table[page], new_allocated)
1119 gc_assert(page_starts_contiguous_block_p(first_page
));
1120 page_index_t page
= first_page
;
1121 while (remaining_bytes
> (sword_t
)GENCGC_PAGE_BYTES
) {
1122 gc_assert(page_words_used(page
) == GENCGC_PAGE_WORDS
);
1123 CHECK_AND_SET_PTE_FIELDS();
1124 remaining_bytes
-= GENCGC_PAGE_BYTES
;
1128 /* Now at most one page of data in use by the object remains,
1129 * but there may be more unused pages beyond which will be freed. */
1131 /* This page must have at least as many bytes in use as expected */
1132 gc_assert((sword_t
)page_bytes_used(page
) >= remaining_bytes
);
1133 CHECK_AND_SET_PTE_FIELDS();
1135 /* Adjust the bytes_used. */
1136 page_bytes_t prev_bytes_used
= page_bytes_used(page
);
1137 set_page_bytes_used(page
, remaining_bytes
);
1139 uword_t bytes_freed
= prev_bytes_used
- remaining_bytes
;
1141 /* Free unused pages that were originally allocated to this object. */
1143 while (prev_bytes_used
== GENCGC_PAGE_BYTES
&&
1144 page_table
[page
].gen
== from_space
&&
1145 page_table
[page
].type
== old_allocated
&&
1146 page_scan_start_offset(page
) == npage_bytes(page
- first_page
)) {
1147 // These pages are part of oldspace, which was un-write-protected.
1148 gc_assert(page_cards_all_marked_nonsticky(page
));
1150 /* Zeroing must have been done before shrinking the object.
1151 * (It is strictly necessary for correctness with objects other
1152 * than simple-vector, but pragmatically it reduces accidental
1153 * conservativism when done for simple-vectors as well) */
1155 { lispobj
* words
= (lispobj
*)page_address(page
);
1157 for(i
=0; i
<(int)(GENCGC_PAGE_BYTES
/N_WORD_BYTES
); ++i
)
1159 lose("non-zeroed trailer of shrunken object @ %p",
1160 page_address(first_page
));
1163 /* It checks out OK, free the page. */
1164 prev_bytes_used
= page_bytes_used(page
);
1165 set_page_need_to_zero(page
, 1);
1166 set_page_bytes_used(page
, 0);
1167 reset_page_flags(page
);
1168 bytes_freed
+= prev_bytes_used
;
1172 // If this freed nothing, it ought to have gone through the fast path.
1173 gc_assert(bytes_freed
!= 0);
1177 /* "Copy" a large object. If the object is on large object pages,
1178 * and satisifies the condition to remain where it is,
1179 * it is simply promoted, else it is copied.
1180 * To stay on large-object pages, the object must either be at least
1181 * LARGE_OBJECT_SIZE, or must waste fewer than about 1% of the space
1182 * on its allocated pages. Using 32k pages as a reference point:
1183 * 3 pages - ok if size >= 97552
1184 * 2 pages - ... size >= 65040
1185 * 1 page - ... size >= 32528
1187 * Bignums and vectors may have shrunk. If the object is not copied,
1188 * the slack needs to be reclaimed, and the page_tables corrected.
1190 * Code objects can't shrink, but it's not worth adding an extra test
1191 * for large code just to avoid the loop that performs adjustment, so
1192 * go through the adjustment motions even though nothing happens.
1196 copy_potential_large_object(lispobj object
, sword_t nwords
,
1197 struct alloc_region
* region
, int page_type
)
1199 page_index_t first_page
;
1201 CHECK_COPY_PRECONDITIONS(object
, nwords
);
1203 /* Check whether it's a large object. */
1204 first_page
= find_page_index((void *)object
);
1205 gc_dcheck(first_page
>= 0);
1207 os_vm_size_t nbytes
= nwords
* N_WORD_BYTES
;
1208 os_vm_size_t rounded
= ALIGN_UP(nbytes
, GENCGC_PAGE_BYTES
);
1209 if (page_single_obj_p(first_page
) &&
1210 (nbytes
>= LARGE_OBJECT_SIZE
|| (rounded
- nbytes
< rounded
/ 128))) {
1212 // Large BOXED would serve no purpose beyond MIXED, and "small large" is illogical.
1213 if (page_type
== PAGE_TYPE_BOXED
|| page_type
== PAGE_TYPE_SMALL_MIXED
)
1214 page_type
= PAGE_TYPE_MIXED
;
1215 os_vm_size_t bytes_freed
=
1216 adjust_obj_ptes(first_page
, nwords
, new_space
,
1217 SINGLE_OBJECT_FLAG
| page_type
);
1219 generations
[from_space
].bytes_allocated
-= (bytes_freed
+ nbytes
);
1220 generations
[new_space
].bytes_allocated
+= nbytes
;
1221 bytes_allocated
-= bytes_freed
;
1223 /* Add the region to the new_areas if requested. */
1224 gc_in_situ_live_nwords
+= nbytes
>>WORD_SHIFT
;
1225 if (boxed_type_p(page_type
)) add_new_area(first_page
, 0, nbytes
);
1229 return gc_copy_object(object
, nwords
, region
, page_type
);
1232 /* to copy unboxed objects */
1234 copy_unboxed_object(lispobj object
, sword_t nwords
)
1236 return gc_copy_object(object
, nwords
, unboxed_region
, PAGE_TYPE_UNBOXED
);
1239 /* This WILL NOT reliably work for objects in a currently open allocation region,
1240 * because page_words_used() is not sync'ed to the free pointer until closing.
1241 * However it should work reliably for codeblobs, because if you can hold
1242 * a reference to the codeblob, then either you'll find it in the generation 0
1243 * tree, or else can linearly scan for it in an older generation */
1244 static lispobj dynspace_codeblob_tree_snapshot
; // valid only during GC
1245 lispobj
*search_dynamic_space(void *pointer
)
1247 page_index_t page_index
= find_page_index(pointer
);
1249 /* The address may be invalid, so do some checks.
1250 * page_index -1 is legal, and page_free_p returns true in that case. */
1251 if (page_free_p(page_index
)) return NULL
;
1253 int type
= page_table
[page_index
].type
& PAGE_TYPE_MASK
;
1254 // Generation 0 code is in the tree usually - it isn't for objects
1255 // in generation 0 following a non-promotion cycle.
1256 if (type
== PAGE_TYPE_CODE
&& page_table
[page_index
].gen
== 0) {
1257 lispobj tree
= dynspace_codeblob_tree_snapshot
? dynspace_codeblob_tree_snapshot
:
1258 SYMBOL(DYNSPACE_CODEBLOB_TREE
)->value
;
1259 lispobj node
= brothertree_find_lesseql((uword_t
)pointer
, tree
);
1261 lispobj
*found
= (lispobj
*)((struct binary_node
*)INSTANCE(node
))->uw_key
;
1262 int widetag
= widetag_of(found
);
1263 if (widetag
!= CODE_HEADER_WIDETAG
&& widetag
!= FUNCALLABLE_INSTANCE_WIDETAG
)
1264 lose("header not OK for code page: @ %p = %"OBJ_FMTX
"\n", found
, *found
);
1265 sword_t nwords
= object_size(found
);
1266 lispobj
*upper_bound
= found
+ nwords
;
1267 if (pointer
< (void*)upper_bound
) return found
;
1270 char* limit
= page_address(page_index
) + page_bytes_used(page_index
);
1271 if ((char*)pointer
> limit
) return NULL
;
1272 if (type
== PAGE_TYPE_CONS
) {
1273 return (lispobj
*)ALIGN_DOWN((uword_t
)pointer
, 2*N_WORD_BYTES
);
1276 if (type
== PAGE_TYPE_SMALL_MIXED
) { // find the nearest card boundary below 'pointer'
1277 start
= (lispobj
*)ALIGN_DOWN((uword_t
)pointer
, GENCGC_CARD_BYTES
);
1279 start
= (lispobj
*)page_scan_start(page_index
);
1281 return gc_search_space(start
, pointer
);
1284 /* Return true if and only if everything on the specified page is NOT subject
1285 * to evacuation, i.e. either the page is not in 'from_space', or is entirely
1286 * pinned. "Entirely pinned" is predicated on being marked as pinned,
1287 * and satisfying one of two additional criteria:
1288 * 1. the page is a single-object page
1289 * 2. the page contains only code, and all code objects are pinned.
1291 * A non-large-object page that is marked "pinned" does not suffice
1292 * to be considered entirely pinned if it contains other than code.
1294 int pin_all_dynamic_space_code
;
1295 static inline int immune_set_memberp(page_index_t page
)
1297 return (page_table
[page
].gen
!= from_space
)
1298 || (gc_page_pins
[page
] &&
1299 (page_single_obj_p(page
) ||
1300 (is_code(page_table
[page
].type
) && pin_all_dynamic_space_code
)));
1303 #ifndef LISP_FEATURE_WEAK_VECTOR_READBARRIER
1304 // Only a bignum, code blob, or vector could be on a single-object page.
1305 #define potential_largeobj_p(w) \
1306 (w==BIGNUM_WIDETAG || w==CODE_HEADER_WIDETAG || \
1307 (w>=SIMPLE_VECTOR_WIDETAG && w < COMPLEX_BASE_STRING_WIDETAG))
1309 // also include WEAK_POINTER_WIDETAG because it could be vector-like
1310 #define potential_largeobj_p(w) \
1311 (w==BIGNUM_WIDETAG || w==CODE_HEADER_WIDETAG || w==WEAK_POINTER_WIDETAG || \
1312 (w>=SIMPLE_VECTOR_WIDETAG && w < COMPLEX_BASE_STRING_WIDETAG))
1315 static inline __attribute__((unused
))
1316 int lowtag_ok_for_page_type(__attribute__((unused
)) lispobj ptr
,
1317 __attribute__((unused
)) int page_type
) {
1318 // If the young generation goes to mixed-region, this filter is not valid
1319 #ifdef LISP_FEATURE_USE_CONS_REGION
1320 // This doesn't currently decide on acceptability for code/non-code
1321 if (lowtag_of(ptr
) == LIST_POINTER_LOWTAG
) {
1322 if (page_type
!= PAGE_TYPE_CONS
) return 0;
1324 if (page_type
== PAGE_TYPE_CONS
) return 0;
1331 * We offer many variations on root scanning:
1332 * 1. X86: all refs from them stack are ambiguous, and pin their referent
1333 * if there is one. All refs from registers (interrupt contexts)
1334 * are ambiguous, and similarly pin their referent if there is one.
1335 * Interior pointers are disallowed to anything except code.
1336 * (FIXME: the PC to the jump instruction into an immobile fdefn
1337 * or self-contained trampoline GF - what does it do wrt pinning???)
1339 * 2. ARM64: interior code pointers from the stack are ambiguous
1340 * and pin their referent if there is one,
1341 * Non-code references are unambiguous, and do NOT pin their referent.
1342 * Only the call chain is scanned for code pointers.
1343 * Interrupt context registers are unambiguous, and can get
1346 * 3. PPC64: interior code pointers from the stack are ambiguous roots,
1347 * and pin their referent if there is one.
1348 * Non-code pointers are unambiguous, and do NOT pin
1349 * their referent from the stack.
1350 * Interrupt context registers are unambiguous and DO pin their referent.
1351 * The entire control stack is scanned for code pointers, thus avoiding
1352 * reliance on a correct backtrace. (I doubt the veracity of all claims
1353 * to the backtrace chain being correct in the presence of interrupts)
1355 * 4. All references from the stack are tagged, and precise, and none pin
1357 * Interrupt contexts registers are unambiguous, and do not pin their referent.
1358 * (pertains to any architecture not specifically mentione above)
1360 * A single boolean value for GENCGC_IS_PRECISE is inadequate to express
1361 * the possibilities. Anything except case 1 is considered "precise".
1362 * Because of the variations, there are many other #ifdefs surrounding
1363 * the logic pertaining to stack and interrupt context scanning.
1364 * Anyway, the above is the theory, but in practice, we have to treat
1365 * some unambiguous pointers as ambiguous for lack of information
1366 * in conservative_root_p what the intent is.
1368 #define AMBIGUOUS_POINTER 1
1369 #if !GENCGC_IS_PRECISE
1370 // Return the starting address of the object containing 'addr'
1371 // if and only if the object is one which would be evacuated from 'from_space'
1372 // were it allowed to be either discarded as garbage or moved.
1373 // 'addr_page_index' is the page containing 'addr' and must not be -1.
1374 // Return 0 if there is no such object - that is, if addr is past the
1375 // end of the used bytes, or its pages are not in 'from_space' etc.
1376 static lispobj
conservative_root_p(lispobj addr
, page_index_t addr_page_index
)
1378 /* quick check 1: Address is quite likely to have been invalid. */
1379 struct page
* page
= &page_table
[addr_page_index
];
1380 bool enforce_lowtag
= !is_code(page
->type
);
1382 if ((addr
& (GENCGC_PAGE_BYTES
- 1)) >= page_bytes_used(addr_page_index
) ||
1383 (!is_lisp_pointer(addr
) && enforce_lowtag
) ||
1384 (compacting_p() && immune_set_memberp(addr_page_index
)))
1386 gc_assert(!(page
->type
& OPEN_REGION_PAGE_FLAG
));
1388 /* If this page can hold only one object, the test is very simple.
1389 * Code pages allow random interior pointers, but only a correctly
1390 * tagged pointer to the boxed words. Tagged interior pointers to SIMPLE-FUNs
1391 * are just as good as any untagged instruction pointer. */
1392 if (page_single_obj_p(addr_page_index
)) {
1393 lispobj
* object_start
= page_scan_start(addr_page_index
);
1394 int widetag
= widetag_of(object_start
);
1395 if (instruction_ptr_p((char*)addr
, object_start
) ||
1396 (potential_largeobj_p(widetag
) &&
1397 // Conveniently all potential largeobjs are OTHER_POINTER
1398 make_lispobj(object_start
, OTHER_POINTER_LOWTAG
) == addr
))
1399 return make_lispobj(object_start
, OTHER_POINTER_LOWTAG
);
1403 /* For pages of code:
1404 * - we can't enforce a particular lowtag on the pointer.
1405 * - we have to find the object base, because pinning a code object
1406 * pins its embedded simple-funs and vice-versa.
1407 * I don't know what to think about pointing to filler objects.
1408 * It seems like a bad idea, but what if Lisp code does that?
1409 * Can it crash if we free the page? I'll assume we're fine
1410 * unless someone can show otherwise */
1411 if (is_code(page
->type
)) {
1412 lispobj
* object_start
= search_dynamic_space((void*)addr
);
1413 /* This search must not fail. We've already verified that the
1414 * pointer is within range for its page. */
1415 gc_assert(object_start
);
1416 switch (widetag_of(object_start
)) {
1417 case CODE_HEADER_WIDETAG
:
1418 /* If 'addr' points anywhere beyond the boxed words, it's valid
1419 * (i.e. allow it even if an incorrectly tagged pointer to a simple-fun header)
1420 * FIXME: Do we want to allow pointing at the untagged base address too?
1421 * It'll find a key in the codeblob tree, but why would Lisp have the
1422 * untagged pointer and expect it to be a strong reference? */
1423 if (instruction_ptr_p((void*)addr
, object_start
)
1424 || addr
== make_lispobj(object_start
, OTHER_POINTER_LOWTAG
))
1425 return make_lispobj(object_start
, OTHER_POINTER_LOWTAG
);
1427 #ifdef LISP_FEATURE_X86_64
1428 case FUNCALLABLE_INSTANCE_WIDETAG
:
1429 // Allow any of these to pin a funcallable instance:
1430 // - pointer to embedded machine instructions
1431 // - untagged pointer to trampoline word
1432 // - correctly tagged pointer
1433 if ((addr
>= (uword_t
)(object_start
+2) && addr
< (uword_t
)(object_start
+4))
1434 || addr
== (lispobj
)(object_start
+1)
1435 || addr
== make_lispobj(object_start
, FUN_POINTER_LOWTAG
))
1436 return make_lispobj(object_start
, FUN_POINTER_LOWTAG
);
1443 /* For non-code, the pointer's lowtag and widetag must correspond.
1444 * The putative object header can safely be read even if it turns out
1445 * that the pointer is not valid, because 'addr' was in bounds for the page.
1446 * Note that this can falsely pass if looking at the interior of an unboxed
1447 * array that masquerades as a Lisp object header by random chance. */
1448 if (widetag_of(native_pointer(addr
)) != FILLER_WIDETAG
1449 && lowtag_ok_for_page_type(addr
, page
->type
)
1450 && plausible_tag_p(addr
)) return AMBIGUOUS_POINTER
;
1452 // FIXME: I think there is a window of GC vulnerability regarding FINs
1453 // and FDEFNs containing executable bytes. In either case if the only pointer
1454 // to such an object is the program counter, the object could be considered
1455 // garbage because there is no _tagged_ pointer to it.
1456 // This is an almost impossible situation to arise, but seems worth some study.
1460 #elif defined LISP_FEATURE_MIPS || defined LISP_FEATURE_PPC64
1461 /* Consider interior pointers to code as roots.
1462 * But most other pointers are *unambiguous* conservative roots.
1463 * This is not "less conservative" per se, than the non-precise code,
1464 * because it's actually up to the user of this predicate to decide whehther
1465 * the control stack as a whole is scanned for objects to pin.
1466 * The so-called "precise" code should generally NOT scan the stack,
1467 * and not call this on stack words.
1468 * Anyway, this code isn't as performance-critical as the x86 variant,
1469 * so it's not worth trying to optimize out the search for the object */
1470 static lispobj
conservative_root_p(lispobj addr
, page_index_t addr_page_index
)
1472 struct page
* page
= &page_table
[addr_page_index
];
1474 // quick check: within from_space and within page usage
1475 if ((addr
& (GENCGC_PAGE_BYTES
- 1)) >= page_bytes_used(addr_page_index
) ||
1476 (compacting_p() && immune_set_memberp(addr_page_index
)))
1478 gc_assert(!(page
->type
& OPEN_REGION_PAGE_FLAG
));
1480 /* Find the containing object, if any
1481 * This is slightly less quick than could be: if sticky_preserve_pointer() was
1482 * called on the contents of a boxed register, then we know that the value is
1483 * a properly tagged descriptor, and don't really need to "search" for an object.
1484 * (And in fact we should rule out fixnums up front)
1485 * Unfortunately sticky_preserve_pointer() does not inform conservative_root_p()
1486 * whether the pointer is known good. So we need a slightly different interface
1487 * to achieve that extra bit of efficiency */
1488 lispobj
* object_start
= search_dynamic_space((void*)addr
);
1489 if (!object_start
) return 0;
1491 if (is_code(page
->type
))
1492 return make_lispobj(object_start
, OTHER_POINTER_LOWTAG
);
1494 /* Take special care not to return fillers. A real-world example:
1495 * - a boxed register contains 0x528b4000
1496 * - the object formerly at 0x528b4000 is a filler
1497 * - compute_lispobj(0x528b4000) returns 0x528b4000 because LOWTAG_FOR_WIDETAG
1498 * says that FILLER_WIDTAG has a 0 lowtag.
1499 * compute_lispobj simply ORs in the 0 which gives back the original address
1500 * and that of course satisfies the equality test. */
1502 // Correctly tagged pointer: ok
1503 if (addr
== compute_lispobj(object_start
)
1504 && widetag_of(object_start
) != FILLER_WIDETAG
)
1510 /* Adjust large bignum and vector objects. This will adjust the
1511 * allocated region if the size has shrunk, and change boxed pages
1512 * into unboxed pages. The pages are not promoted here, and the
1513 * object is not added to the new_regions; this is really
1514 * only designed to be called from preserve_pointer(). Shouldn't fail
1515 * if this is missed, just may delay the moving of objects to unboxed
1516 * pages, and the freeing of pages. */
1518 maybe_adjust_large_object(lispobj
* where
, page_index_t first_page
, sword_t nwords
)
1522 /* Check whether it's a vector or bignum object. */
1523 /* There is no difference between MIXED and BOXED for large objects,
1524 * because in any event we'll use the large simple-vector optimization
1525 * for root scavenging if applicable. */
1526 lispobj widetag
= widetag_of(where
);
1527 if (widetag
== SIMPLE_VECTOR_WIDETAG
)
1528 page_type
= SINGLE_OBJECT_FLAG
| PAGE_TYPE_MIXED
;
1529 #ifndef LISP_FEATURE_UBSAN
1530 else if (specialized_vector_widetag_p(widetag
) || widetag
== BIGNUM_WIDETAG
)
1531 page_type
= SINGLE_OBJECT_FLAG
| PAGE_TYPE_UNBOXED
;
1536 os_vm_size_t bytes_freed
=
1537 adjust_obj_ptes(first_page
, nwords
, from_space
, page_type
);
1538 generations
[from_space
].bytes_allocated
-= bytes_freed
;
1539 bytes_allocated
-= bytes_freed
;
1542 /* After scavenging of the roots is done, we go back to the pinned objects
1543 * and look within them for pointers. Additionally we delete any keys
1544 * from the list of pins that were not legal object addresses,
1545 * but passed through all the filters in conservative_root_p.
1547 #define SMALL_MAX_PINS 200
1548 static uword_t small_pins_vector
[SMALL_MAX_PINS
];
1550 uword_t gc_pinned_nwords
;
1551 static void refine_ambiguous_roots()
1553 void gc_heapsort_uwords(uword_t
*, int);
1555 int pre_deletion_count
= pinned_objects
.count
;
1556 gc_pin_count
= pre_deletion_count
;
1557 if (pre_deletion_count
== 0) return;
1559 /* We need a place to sort the keys of pinned_objects. If the key count is small,
1560 * use the small_pins vector; otherwise grab some memory via mmap */
1562 if (pre_deletion_count
< SMALL_MAX_PINS
) { // leave room for sentinel at end
1563 workspace
= small_pins_vector
;
1565 pins_alloc_size
= ALIGN_UP((pre_deletion_count
+1)*N_WORD_BYTES
, BACKEND_PAGE_BYTES
);
1566 workspace
= (lispobj
*)os_allocate(pins_alloc_size
);
1567 gc_assert(workspace
);
1569 gc_filtered_pins
= workspace
; // needed for obliterate_nonpinned_words
1571 int count
= 0, index
;
1572 for_each_hopscotch_key(index
, key
, pinned_objects
) {
1573 gc_assert(is_lisp_pointer(key
));
1574 // Preserve only the object base addresses, including any "false" pointers.
1575 if (listp(key
) || widetag_of(native_pointer(key
)) != SIMPLE_FUN_WIDETAG
)
1576 workspace
[count
++] = key
;
1578 gc_heapsort_uwords(workspace
, count
);
1580 * for each group of keys with the same page_scan_start
1581 * - scan the heap at the indicated start address
1582 * - "intersect" the list of objects visited with the list of
1583 * ambiguous roots (this is easy because the keys are sorted)
1584 * - change any missed key to 0 as we go
1586 lispobj
*where
= 0, // as is tradition
1587 *previous_scan_start
= 0;
1589 for (index
= 0 ; index
< count
; ++index
) {
1590 lispobj
* key
= native_pointer(workspace
[index
]);
1591 lispobj
* scan_start
= page_scan_start(find_page_index(key
));
1592 if (scan_start
!= previous_scan_start
) where
= previous_scan_start
= scan_start
;
1593 /* Scan forward from 'where'. This does not need a termination test based
1594 * on page_bytes_used because we know that 'key' was in-bounds for its page.
1595 * Therefore at least as many bytes are in use on the page as are needed
1596 * to enclose 'where'. If the next object we would visit is beyond it,
1597 * then we're done; the key was not found */
1600 where
+= object_size(where
);
1601 } else if (where
== key
) {
1603 } else { // 'where' went past the key, so the key is bad
1604 workspace
[index
] = 0;
1613 for (index
= 0 ; index
< count
; ++index
) {
1614 key
= workspace
[index
];
1615 if (key
) workspace
[new_index
++] = key
;
1617 gc_assert(new_index
< count
);
1620 gc_pin_count
= count
;
1621 if (!(gencgc_verbose
& 4)) return;
1622 // Print in multiple columns to fit more on a screen
1623 // and sort like 'ls' (down varying fastest)
1624 char description
[24];
1625 fprintf(stderr
, "Sorted pin list (%d):\n", count
);
1626 const int ncolumns
= 4;
1627 int nrows
= ALIGN_UP(count
,ncolumns
) / ncolumns
;
1629 for (row
= 0; row
< nrows
; ++row
) {
1630 for (col
= 0; col
< ncolumns
; ++col
) {
1631 int index
= col
* nrows
+ row
;
1632 if (index
< count
) {
1633 lispobj
* obj
= native_pointer(workspace
[index
]);
1634 lispobj word
= *obj
;
1635 strcpy(description
, "cons");
1636 if (is_header(word
))
1637 snprintf(description
, sizeof description
, "%s,%ldw",
1638 widetag_names
[header_widetag(word
)>>2],
1639 (long)object_size(obj
));
1640 fprintf(stderr
, " %"OBJ_FMTX
": %-24s", (uword_t
)obj
, description
);
1647 /* After scavenging of the roots is done, we go back to the pinned objects
1648 * and look within them for pointers. */
1650 scavenge_pinned_ranges()
1655 for (i
= 0; i
< gc_pin_count
; ++i
) {
1656 key
= gc_filtered_pins
[i
];
1657 gc_assert(is_lisp_pointer(key
));
1658 lispobj
* obj
= native_pointer(key
);
1663 lispobj header
= *obj
;
1664 nwords
+= scavtab
[header_widetag(header
)](obj
, header
);
1667 gc_pinned_nwords
= nwords
;
1670 /* visit_freed_objects() was designed to support post-GC actions such as
1671 * recycling of unused symbol TLS indices. However, I could not make this work
1672 * as claimed at the time that it gets called, so at best this is reserved
1673 * for debugging, and only when you can tolerate some inaccuracy.
1675 * The problem is that oldspace pages which were not pinned should eventually
1676 * be scanned en masse using contiguous blocks as large as possible without
1677 * encroaching on pinned pages. But we need to visit the dead objects on partially
1678 * pinned pages prior to turning those objects into page-filling objects.
1679 * Based on a real-life example, finding a correct approach is difficult.
1680 * Consider three pages all having the same scan_start of 0x1008e78000,
1681 * with the final page and only the final containing a pinned object:
1683 * start: 0x1008e78000 0x1008e80000 0x1008e88000
1685 * ^------------------+------------------|
1686 * There is a page-spanning (SIMPLE-ARRAY (UNSIGNED-BYTE 64) 8192)
1687 * from 0x1008e78000 to 0x1008E88010 (exclusive). The penultimate word
1688 * of that array appears to be a valid widetag:
1690 * 0x1008e88000: 0x0000000000001df1
1691 * 0x1008e88008: 0x0000000000000000
1693 * 0x1008e88010: 0x0000001006c798c7 CONS
1694 * 0x1008e88018: 0x0000001008e88447
1695 * 0x1008e88020: 0x00000000000000ad (SIMPLE-ARRAY (UNSIGNED-BYTE 64) 32)
1696 * 0x1008e88028: 0x0000000000000040
1697 * ... pretty much anything in here ...
1698 * 0x1008e8bec0: any valid pinned object
1700 * Page wiping ignores the pages based at 0x1008e78000 and 0x1008e80000
1701 * and it is only concerned with the range from 0x1008e88000..0x1008e8bec0
1702 * which becomes filler. The question is how to traverse objects in the filled
1703 * range. You can't start scanning dead objects at the page base address
1704 * of the final page because that would parse these objects as:
1706 * 0x1008e88000: 0x0000000000001df1 (complex-vector-nil) ; 30 words
1707 * 0x1008e880f0: any random garbage
1709 * But if you scan from the correct scan start of 0x1008e78000 then how do you
1710 * know to skip that page later (in free_oldspace), as it is entirely in oldspace,
1711 * but partially visited already? This what in malloc/free terms would be
1712 * a "double free", and there is no obvious solution to that.
1714 void visit_freed_objects(char __attribute__((unused
)) *start
,
1715 sword_t
__attribute__((unused
)) nbytes
)
1717 #ifdef TRAVERSE_FREED_OBJECTS
1718 /* At this point we could attempt to recycle unused TLS indices
1719 * as follows: For each now-garbage symbol that had a nonzero index,
1720 * return that index to a "free TLS index" pool, perhaps a linked list
1721 * or bitmap. Then either always try the free pool first (for better
1722 * locality) or if ALLOC-TLS-INDEX detects exhaustion (for speed). */
1723 lispobj
* where
= (lispobj
*)start
;
1724 lispobj
* end
= (lispobj
*)(start
+ nbytes
);
1725 while (where
< end
) {
1726 lispobj word
= *where
;
1727 if (forwarding_pointer_p(where
)) { // live oject
1728 /* CAUTION: This CAN NOT WORK RELIABLY. Due to gc_copy_object_resizing()
1729 * we might compute the wrong size because we take it from the copy.
1730 * Are there other places where we get this wrong??? I sure hope not */
1731 lispobj
* fwd_where
= native_pointer(forwarding_pointer_value(where
));
1732 fprintf(stderr
, "%p: -> %p\n", where
, fwd_where
);
1733 where
+= object_size(fwd_where
);
1734 } else { // dead object
1735 fprintf(stderr
, "%p: %"OBJ_FMTX
" %"OBJ_FMTX
"\n", where
, where
[0], where
[1]);
1736 if (is_header(word
)) {
1737 // Do something interesting
1738 where
+= headerobj_size(where
, word
);
1740 /* Can't do much useful with conses because often we can't distinguish
1741 * filler from data. visit_freed_objects is called on ranges of pages
1742 * without regard to whether each intervening page was completely full.
1743 * (This is not usually the way, but freeing of pages is slightly
1744 * imprecise in that regard).
1745 * And it's probably broken, since we leave detritus on code pages */
1753 /* Deposit a FILLER_WIDETAG object covering one or more dead objects.
1754 * If using more than 1 card per page, scavenge_root_gens() is able to scan
1755 * some pages without aligning to object boundaries. For that to work,
1756 * it must not accidentally see a raw word or leftover garbage.
1757 * Note that while CONS and SMALL_MIXED pages never have card-spanning objects,
1758 * deposit_filler() deals with the "mirror image" of the pinned objects,
1759 * hence it might get a card-spanning filler. It has to do something to ensure
1760 * that no card will see garbage if scanned from its base address.
1761 * To achieve that, an extra filler may be needed at the start of any spanned card.
1762 * The sizes of extra fillers don't have to sum up to the total filler size.
1763 * They serve the vital purpose of getting descriptors_scavenge() to skip a
1764 * portion of the card they're on, but those fillers are never visited in a
1765 * heap walk that steps by object from a page's page_scan_start.
1766 * The final filler must be the correct size, so any algorithm that achieves
1767 * the desired end result is OK */
1768 void deposit_filler(char* from
, char* to
) {
1769 sword_t nbytes
= to
- from
;
1770 if (!nbytes
) return;
1771 gc_assert(nbytes
> 0);
1772 sword_t nwords
= nbytes
>> WORD_SHIFT
;
1773 gc_assert((nwords
- 1) <= 0x7FFFFF);
1774 page_index_t page
= find_page_index(from
);
1775 gc_assert(find_page_index(to
-1) == page
);
1776 *(lispobj
*)from
= make_filler_header(nwords
);
1777 long unsigned last_card
;
1778 switch (page_table
[page
].type
) {
1779 case PAGE_TYPE_BOXED
:
1780 case PAGE_TYPE_CONS
:
1781 case PAGE_TYPE_SMALL_MIXED
:
1782 last_card
= addr_to_card_index(to
-1);
1783 while (addr_to_card_index(from
) != last_card
) {
1784 from
= PTR_ALIGN_DOWN(from
, GENCGC_CARD_BYTES
) + GENCGC_CARD_BYTES
;
1785 nwords
= (to
- from
) >> WORD_SHIFT
;
1786 *(lispobj
*)from
= make_filler_header(nwords
);
1791 /* Deposit filler objects on small object pinned pages.
1792 * Also ensure that no scan_start_offset points to a page in
1793 * oldspace that will be freed.
1795 static void obliterate_nonpinned_words()
1797 if (!gc_pin_count
) return;
1799 #define page_base(x) ALIGN_DOWN(x, GENCGC_PAGE_BYTES)
1800 // This macro asserts that space accounting happens exactly
1801 // once per affected page (a page with any pins, no matter how many)
1802 #define adjust_gen_usage(i) \
1803 gc_assert(page_table[i].gen == from_space); \
1804 bytes_moved += page_bytes_used(i); \
1805 page_table[i].gen = new_space
1807 lispobj
* keys
= gc_filtered_pins
;
1808 int n_pins
= gc_pin_count
;
1809 // Store a sentinel at the end.
1810 // It is safe to write one more word than there are pins.
1811 keys
[n_pins
] = ~(uword_t
)0;
1813 // Each pinned object begets two ranges of bytes to be turned into filler:
1814 // - the range preceding it back to its page start or predecessor object
1815 // - the range after it, up to the lesser of page bytes used or successor object
1818 uword_t fill_from
= page_base(keys
[0]);
1819 os_vm_size_t bytes_moved
= 0; // i.e. virtually moved
1822 for (i
= 0; i
< n_pins
; ++i
) {
1823 lispobj
* obj
= native_pointer(keys
[i
]);
1824 page_index_t begin_page_index
= find_page_index(obj
);
1825 // Create a filler object occupying space from 'fill_from' up to but
1827 deposit_filler((char*)fill_from
, (char*)obj
);
1828 if (fill_from
== page_base((uword_t
)obj
)) {
1829 adjust_gen_usage(begin_page_index
);
1830 // This pinned object started a new page of pins.
1831 // scan_start must not see any page prior to this page,
1832 // as those might be in oldspace and about to be marked free.
1833 set_page_scan_start_offset(begin_page_index
, 0);
1835 // If 'obj' spans pages, move its successive page(s) to newspace and
1836 // ensure that those pages' scan_starts point at the same address
1837 // that this page's scan start does, which could be this page or earlier.
1838 sword_t nwords
= object_size(obj
);
1839 uword_t obj_end
= (uword_t
)(obj
+ nwords
); // non-inclusive address bound
1840 page_index_t end_page_index
= find_page_index((char*)obj_end
- 1); // inclusive bound
1842 if (end_page_index
> begin_page_index
) {
1843 char *scan_start
= page_scan_start(begin_page_index
);
1845 for (index
= begin_page_index
+ 1; index
<= end_page_index
; ++index
) {
1846 set_page_scan_start_offset(index
,
1847 addr_diff(page_address(index
), scan_start
));
1848 adjust_gen_usage(index
);
1851 // Compute page base address of last page touched by this obj.
1852 uword_t obj_end_pageaddr
= page_base(obj_end
- 1);
1853 // See if there's another pinned object on this page.
1854 // There is always a next object, due to the sentinel.
1855 if (keys
[i
+1] < obj_end_pageaddr
+ GENCGC_PAGE_BYTES
) {
1856 // Next object starts within the same page.
1857 fill_from
= obj_end
;
1859 /* Next pinned object does not start on the same page this obj ends on.
1860 * Any bytes following 'obj' up to its page end are garbage.
1861 * The reason we don't merely reduce the page_bytes_used is that decreasing
1862 * the grand total bytes allocated had a tendency to delay triggering the
1863 * next GC. This phenomenon was especially bad if the only pinned objects
1864 * were at the start of a page, as it caused the entire rest of the page to
1865 * be unusable. :SMALLOBJ-AUTO-GC-TRIGGER from rev dfddbc8a tests this */
1866 deposit_filler((char*)obj_end
,
1867 (char*)obj_end_pageaddr
+ page_bytes_used(end_page_index
));
1868 fill_from
= page_base(keys
[i
+1]);
1871 generations
[from_space
].bytes_allocated
-= bytes_moved
;
1872 generations
[new_space
].bytes_allocated
+= bytes_moved
;
1873 #undef adjust_gen_usage
1875 if (pins_alloc_size
) {
1876 os_deallocate((char*)gc_filtered_pins
, pins_alloc_size
);
1877 gc_filtered_pins
= 0;
1879 pins_alloc_size
= 0;
1883 int sb_introspect_pinnedp(lispobj obj
) {
1884 return hopscotch_containsp(&pinned_objects
, obj
);
1887 /* Add 'object' to the hashtable, and if the object is a code component,
1888 * then also add all of the embedded simple-funs.
1889 * It is OK to call this function on an object which is already pinned-
1890 * it will do nothing.
1891 * But it is not OK to call this if the object is not one which merits
1892 * pinning in the first place. i.e. It MUST be an object in from_space
1893 * and moreover must be in the condemned set, which means that it can't
1894 * be a code object if pin_all_dynamic_space_code is 1.
1896 * The rationale for doing some extra work on code components is that without it,
1897 * every call to pinned_p() would entail this logic:
1898 * if the object is a simple-fun then
1900 * if already forwarded then return "no"
1901 * else go backwards to the code header and test pinned_p().
1902 * But we can avoid that by making every embedded function pinned
1903 * whenever the containing object is pinned.
1904 * Experimentation bears out that this is the better technique.
1905 * Also, we wouldn't often expect code components in the collected generation
1906 * so the extra work here is quite minimal, even if it can generally add to
1907 * the number of keys in the hashtable.
1909 #define PAGE_PINNED 0xFF
1910 static void pin_object(lispobj object
)
1912 if (!compacting_p()) {
1913 gc_mark_obj(object
);
1917 lispobj
* object_start
= native_pointer(object
);
1918 page_index_t page
= find_page_index(object_start
);
1920 /* Large object: the 'pinned' bit in the PTE on the first page should be definitive
1921 * for that object. However, all occupied pages have to marked pinned,
1922 * because move_pinned_pages_to_newspace() looks at pages as if they're independent.
1923 * That seems to be the only place that cares how many pages' pinned bits are affected
1924 * here for large objects, though I do wonder why we can't move the object right now
1925 * and be done with it */
1926 if (page_single_obj_p(page
)) {
1927 if (gc_page_pins
[page
]) return;
1928 sword_t nwords
= object_size(object_start
);
1929 maybe_adjust_large_object(object_start
, page
, nwords
);
1930 page_index_t last_page
= find_page_index(object_start
+ nwords
- 1);
1931 while (page
<= last_page
) gc_page_pins
[page
++] = PAGE_PINNED
;
1935 // Multi-object page (the usual case) - presence in the hash table is the pinned criterion.
1936 // The 'pinned' bit is a coarse-grained test of whether to bother looking in the table.
1937 if (hopscotch_containsp(&pinned_objects
, object
)) return;
1939 hopscotch_insert(&pinned_objects
, object
, 1);
1940 unsigned int addr_lowpart
= object
& (GENCGC_PAGE_BYTES
-1);
1941 // Divide the page into 8 parts, mark that part pinned
1942 gc_page_pins
[page
] |= 1 << (addr_lowpart
/ (GENCGC_PAGE_BYTES
/8));
1943 struct code
* maybe_code
= (struct code
*)native_pointer(object
);
1944 // Avoid iterating over embedded simple-funs until the debug info is set.
1945 // Prior to that, the unboxed payload will contain random bytes.
1946 // There can't be references to any of the simple-funs
1947 // until the object is fully constructed.
1948 if (widetag_of(&maybe_code
->header
) == CODE_HEADER_WIDETAG
&& maybe_code
->debug_info
) {
1949 for_each_simple_fun(i
, fun
, maybe_code
, 0, {
1950 hopscotch_insert(&pinned_objects
, make_lispobj(fun
, FUN_POINTER_LOWTAG
), 1);
1951 addr_lowpart
= (uword_t
)fun
& (GENCGC_PAGE_BYTES
-1);
1952 gc_page_pins
[find_page_index(fun
)] |=
1953 1 << (addr_lowpart
/ (GENCGC_PAGE_BYTES
/8));
1958 /* Additional logic for soft marks: any word that is potentially a
1959 * tagged pointer to a page being written must preserve the mark regardless
1960 * of what update_writeprotection() thinks. That's because the mark is set
1961 * prior to storing. If GC occurs in between setting the mark and storing,
1962 * then resetting the mark would be wrong if the subsequent store
1963 * creates an old->young pointer.
1964 * Mark stickiness is checked only once per invocation of collect_garbage(),
1965 * when scanning interrupt contexts for generation 0 but not higher gens.
1966 * There are two cases:
1967 * (1) tagged pointer to a large simple-vector, but we scan card-by-card
1968 * for specifically the marked cards. This has to be checked first
1969 * so as not to fail to see subsequent cards if the first is marked.
1970 * (2) tagged pointer to an object that marks only the page containing
1972 * And note a subtle point: only an already-marked card can acquire sticky
1973 * status. So we can ignore any unmarked (a/k/a WRITEPROTECTED_P) card
1974 * regardless of a context register pointing to it, because if a mark was not
1975 * stored, then the pointer was not stored. Without examining the next few
1976 * instructions, there's no reason even to suppose that a store occurs.
1977 * It seems like the stop-for-GC handler must be enforcing that GC sees things
1978 * stored in the correct order for out-of-order memory models */
1979 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
1980 static void impart_mark_stickiness(lispobj word
)
1982 // This function does not care whether 'word' points to a valid object.
1983 // At worst this will spurisouly mark a card as sticky,
1984 // which can happen only if it was already marked as dirty.
1985 page_index_t page
= find_page_index((void*)word
);
1986 if (page
>= 0 && page_boxed_p(page
) // stores to raw bytes are uninteresting
1987 && (word
& (GENCGC_PAGE_BYTES
- 1)) < page_bytes_used(page
)
1988 && page_table
[page
].gen
!= 0
1989 && lowtag_ok_for_page_type(word
, page_table
[page
].type
)
1990 && plausible_tag_p(word
)) { // "plausible" is good enough
1991 /* if 'word' is the correctly-tagged pointer to the base of a SIMPLE-VECTOR,
1992 * then set the sticky mark on every marked card. The only other large
1993 * objects are CODE (writes to which are pseudo-atomic),
1994 * and BIGNUM (which aren't on boxed pages)
1995 * I'm not sure if it's inadvertent that this first 'if' is taken
1996 * for non-large simple-vectors. It probably can't hurt,
1997 * but I think it's not necessary */
1998 if (lowtag_of(word
) == OTHER_POINTER_LOWTAG
&&
1999 widetag_of(native_pointer(word
)) == SIMPLE_VECTOR_WIDETAG
) {
2000 generation_index_t gen
= page_table
[page
].gen
;
2002 long card
= page_to_card_index(page
);
2004 for(i
=0; i
<CARDS_PER_PAGE
; ++i
)
2005 if (gc_card_mark
[card
+i
]==CARD_MARKED
) gc_card_mark
[card
+i
]=STICKY_MARK
;
2006 if (page_ends_contiguous_block_p(page
, gen
)) return;
2009 } else if (gc_card_mark
[addr_to_card_index((void*)word
)] == CARD_MARKED
) {
2010 gc_card_mark
[addr_to_card_index((void*)word
)] = STICKY_MARK
;
2016 #if !GENCGC_IS_PRECISE || defined LISP_FEATURE_MIPS || defined LISP_FEATURE_PPC64
2017 /* Take a possible pointer to a Lisp object and mark its page in the
2018 * page_table so that it will not be relocated during a GC.
2020 * This involves locating the page it points to, then backing up to
2021 * the start of its region, then marking all pages pinned from there
2022 * up to the first page that's not full or has a different generation
2024 * It is assumed that all the pages' pin flags have been cleared at
2025 * the start of a GC.
2027 * It is also assumed that the current gc_alloc() region has been
2028 * flushed and the tables updated. */
2030 static void NO_SANITIZE_MEMORY
preserve_pointer(os_context_register_t word
, void* arg
)
2032 int contextp
= arg
== (void*)1;
2033 page_index_t page
= find_page_index((void*)word
);
2035 // Though immobile_space_preserve_pointer accepts any pointer,
2036 // there's a benefit to testing immobile_space_p first
2037 // because it's inlined. Either is a no-op if no immobile space.
2038 if (immobile_space_p(word
))
2039 immobile_space_preserve_pointer((void*)word
);
2043 // Special case for untagged instance pointers in registers. This might belong in
2044 // conservative_root_p() but the pointer has to be adjusted here or else the wrong
2045 // value will be inserted into 'pinned_objects' (which demands tagged pointers)
2046 if (contextp
&& lowtag_of(word
) == 0 &&
2047 (page_table
[page
].type
== PAGE_TYPE_MIXED
||
2048 page_table
[page
].type
== PAGE_TYPE_SMALL_MIXED
) &&
2049 widetag_of((lispobj
*)word
) == INSTANCE_WIDETAG
)
2050 word
|= INSTANCE_POINTER_LOWTAG
;
2052 lispobj object
= conservative_root_p(word
, page
);
2053 if (!object
) return;
2054 if (object
!= AMBIGUOUS_POINTER
) {
2058 // It's a non-large non-code ambiguous pointer.
2059 if (compacting_p()) {
2060 if (!hopscotch_containsp(&pinned_objects
, word
)) {
2061 hopscotch_insert(&pinned_objects
, word
, 1);
2062 unsigned int addr_lowpart
= word
& (GENCGC_PAGE_BYTES
-1);
2063 // Divide the page into 8 parts, mark that part pinned
2064 gc_page_pins
[page
] |= 1 << (addr_lowpart
/ (GENCGC_PAGE_BYTES
/8));
2068 // Mark only: search for the object, because fullcgc can't handle random pointers
2069 lispobj
* found
= search_dynamic_space((void*)word
);
2070 if (found
) gc_mark_obj(compute_lispobj(found
));
2072 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2073 static void sticky_preserve_pointer(os_context_register_t register_word
, void* arg
)
2075 // registers can be wider than words. This could accept uword_t as the arg type
2076 // but I like it to be directly callable with os_context_register.
2077 uword_t word
= register_word
;
2078 if (is_lisp_pointer(word
)) impart_mark_stickiness(word
);
2079 preserve_pointer(word
, arg
);
2084 /* Pin an unambiguous descriptor object which may or may not be a pointer.
2085 * Ignore immediate objects, and heuristically skip some objects that are
2086 * known to be pinned without looking in pinned_objects.
2087 * pin_object() will always do the right thing and ignore multiple
2088 * calls with the same object in the same collection pass.
2090 static void pin_exact_root(lispobj obj
)
2092 // These tests are performed in approximate order of quickness to check.
2095 if (!is_lisp_pointer(obj
)) return;
2096 // 2. If not moving, then pinning is irrelevant. 'obj' is a-priori live given
2097 // the reference from *PINNED-OBJECTS*, and obviously it won't move.
2098 if (!compacting_p()) return;
2099 // 3. If the pointer is in immobile space, preserve it.
2100 page_index_t page
= find_page_index((void*)obj
);
2102 if (immobile_space_p(obj
))
2103 immobile_space_preserve_pointer((void*)obj
);
2106 // 4. Ignore if not in the condemned set.
2107 if (immune_set_memberp(page
)) return;
2109 // Never try to pin an interior pointer - always use base pointers.
2110 lispobj
*object_start
= native_pointer(obj
);
2111 switch (widetag_of(object_start
)) {
2112 case SIMPLE_FUN_WIDETAG
:
2113 #ifdef RETURN_PC_WIDETAG
2114 case RETURN_PC_WIDETAG
:
2116 obj
= make_lispobj(fun_code_header((struct simple_fun
*)object_start
),
2117 OTHER_POINTER_LOWTAG
);
2123 /* Return true if 'ptr' is OK to be on a write-protected page
2124 * of an object in 'gen'. That is, if the pointer does not point to a younger object.
2125 * Note: 'ptr' is _sometimes_ an ambiguous pointer - we do not utilize the layout bitmap
2126 * when scanning instances for pointers, so we will occasionally see a raw word for 'ptr'.
2127 * Also, 'ptr might not have a lowtag (such as lockfree list node successor), */
2128 static bool ptr_ok_to_writeprotect(lispobj ptr
, generation_index_t gen
)
2131 lispobj
__attribute__((unused
)) header
;
2133 /* Check that it's in the dynamic space */
2134 if ((index
= find_page_index((void*)ptr
)) != -1) {
2135 int pointee_gen
= page_table
[index
].gen
;
2136 if (/* Does it point to a younger or the temp. generation? */
2137 (pointee_gen
< gen
|| pointee_gen
== SCRATCH_GENERATION
) &&
2138 /* and an in-use part of the page?
2139 * Formerly this examined the bounds of each open region,
2140 * but that is extra work with little benefit. It is faster
2141 * to treat all of any page with an open region as in-use.
2142 * It will self-correct when the region gets closed */
2143 ((page_table
[index
].type
& OPEN_REGION_PAGE_FLAG
)
2144 || (ptr
& (GENCGC_PAGE_BYTES
-1)) < page_bytes_used(index
)))
2147 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2148 else if (immobile_space_p(ptr
) &&
2149 other_immediate_lowtag_p(header
= *native_pointer(ptr
))) {
2150 // This is *possibly* a pointer to an object in immobile space,
2151 // given that above two conditions were satisfied.
2152 // But unlike in the dynamic space case, we need to read a byte
2153 // from the object to determine its generation, which requires care.
2154 // Consider an unboxed word that looks like a pointer to a word that
2155 // looks like simple-fun-widetag. We can't naively back up to the
2156 // underlying code object since the alleged header might not be one.
2157 int pointee_gen
= gen
; // Make comparison fail if we fall through
2158 switch (header_widetag(header
)) {
2159 case SIMPLE_FUN_WIDETAG
:
2160 if (functionp(ptr
)) {
2161 lispobj
* code
= (lispobj
*)fun_code_header(FUNCTION(ptr
));
2162 // This is a heuristic, since we're not actually looking for
2163 // an object boundary. Precise scanning of 'page' would obviate
2164 // the guard conditions here.
2165 if (immobile_space_p((lispobj
)code
)
2166 && widetag_of(code
) == CODE_HEADER_WIDETAG
)
2167 pointee_gen
= immobile_obj_generation(code
);
2171 pointee_gen
= immobile_obj_generation(native_pointer(ptr
));
2173 // A bogus generation number implies a not-really-pointer,
2174 // but it won't cause misbehavior.
2175 if (pointee_gen
< gen
|| pointee_gen
== SCRATCH_GENERATION
) {
2183 #ifndef LISP_FEATURE_SOFT_CARD_MARKS
2184 static inline void protect_page(void* page_addr
)
2186 os_protect((void *)page_addr
, GENCGC_PAGE_BYTES
, OS_VM_PROT_READ
);
2187 gc_card_mark
[addr_to_card_index(page_addr
)] = CARD_UNMARKED
;
2191 #define LOCKFREE_LIST_NEXT(x) ((struct list_node*)x)->_node_next
2193 /* Helper function for update_writeprotection.
2194 * If the [where,limit) contain an old->young pointer, then return
2195 * the address - or approximate address - containing such pointer.
2196 * The return value is used as a boolean, but if debugging, you might
2197 * want to see the address */
2198 static lispobj
* range_dirty_p(lispobj
* where
, lispobj
* limit
, generation_index_t gen
)
2201 for ( ; where
< limit
; where
+= nwords
) {
2202 lispobj word
= *where
;
2203 if (is_cons_half(word
)) {
2204 if (is_lisp_pointer(word
) && !ptr_ok_to_writeprotect(word
, gen
)) return where
;
2206 if (is_lisp_pointer(word
) && !ptr_ok_to_writeprotect(word
, gen
)) return where
;
2210 int widetag
= widetag_of(where
);
2211 gc_dcheck(widetag
!= CODE_HEADER_WIDETAG
); // This can't be called on a code page
2212 nwords
= sizetab
[widetag
](where
);
2213 if (leaf_obj_widetag_p(widetag
)) continue; // Do nothing
2214 #ifdef LISP_FEATURE_COMPACT_INSTANCE_HEADER
2215 if (instanceoid_widetag_p(widetag
)) {
2216 // instance_layout works on funcallable or regular instances
2217 // and we have to specially check it because it's in the upper
2218 // bytes of the 0th word.
2219 lispobj layout
= instance_layout(where
);
2221 if (!ptr_ok_to_writeprotect(layout
, gen
)) return where
;
2222 if (lockfree_list_node_layout_p(LAYOUT(layout
)) &&
2223 !ptr_ok_to_writeprotect(LOCKFREE_LIST_NEXT(where
), gen
))
2228 if (widetag
== INSTANCE_WIDETAG
) {
2229 // instance_layout works only on regular instances,
2230 // we don't have to treat it specially but we do have to
2231 // check for lockfree list nodes.
2232 lispobj layout
= instance_layout(where
);
2233 if (layout
&& lockfree_list_node_layout_p(LAYOUT(layout
)) &&
2234 !ptr_ok_to_writeprotect(LOCKFREE_LIST_NEXT(where
), gen
))
2238 #ifdef LISP_FEATURE_LINKAGE_SPACE
2239 else if (widetag
== SYMBOL_WIDETAG
) {
2240 struct symbol
* s
= (void*)where
;
2241 if (!ptr_ok_to_writeprotect(linkage_cell_function(symbol_linkage_index(s
)), gen
))
2243 // Process the value and info slots normally, and the bit-packed package ID + name
2244 // can't be younger, so that slot's contents are irrelevant
2245 } else if (widetag
== FDEFN_WIDETAG
) {
2246 struct fdefn
* f
= (void*)where
;
2247 if (!ptr_ok_to_writeprotect(linkage_cell_function(fdefn_linkage_index(f
)), gen
))
2251 // Scan all the rest of the words even if some of them are raw bits.
2252 // At worst this overestimates the set of pointer words.
2254 for (index
=1; index
<nwords
; ++index
)
2255 if (is_lisp_pointer(where
[index
]) && !ptr_ok_to_writeprotect(where
[index
], gen
))
2261 /* Given a range of pages at least one of which is not WPed (logically or physically,
2262 * depending on SOFT_CARD_MARKS), scan all those pages for pointers to younger generations.
2263 * If no such pointers are found, then write-protect the range.
2265 * Care is taken to check for pointers to any open allocation regions,
2266 * which by design contain younger objects.
2268 * If we find a word which is a witness for the inability to apply write-protection,
2269 * then return the address of the object containing the witness pointer.
2270 * Otherwise return 0. The word address is just for debugging; there are cases
2271 * where we don't apply write protectection, but nonetheless return 0.
2273 * This function is still buggy, but not in a fatal way.
2274 * The issue is that for any kind of weak object - hash-table vector,
2275 * weak pointer, or weak simple-vector, we skip scavenging the object
2276 * which might leave some pointers to younger generation objects
2277 * which will later be smashed when processing weak objects.
2278 * That is, the referent is non-live. But when we scanned this page range,
2279 * it looks like it still had the pointer to the younger object.
2280 * To get this really right, we would have to wait until after weak objects
2281 * have been processed.
2282 * It may or may not be possible to get verify_range to croak
2283 * about suboptimal application of WP. Possibly not, because of the hack
2284 * for pinned pages without soft card marking (which won't WP).
2286 * See also 'doc/internals-notes/fdefn-gc-safety' for execution schedules
2287 * that lead to invariant loss with FDEFNs. This might not be a problem
2288 * in practice. At least it seems like it never has been.
2291 update_writeprotection(page_index_t first_page
, page_index_t last_page
,
2292 lispobj
* where
, lispobj
* limit
)
2294 /* Shouldn't be a free page. */
2295 gc_dcheck(!page_free_p(first_page
)); // Implied by the next assertion
2296 gc_assert(page_words_used(first_page
) != 0);
2298 if (!ENABLE_PAGE_PROTECTION
) return 0;
2299 if (!page_boxed_p(first_page
)) return 0;
2302 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2303 /* If any page is referenced from the stack (mark byte = 2), then we're
2304 * can not apply protection even if we see no witness, because the
2305 * absence of synchronization between mutator and GC means that the next
2306 * instruction issued when the mutator resumes might create the witness,
2307 * and it thinks it already marked a card */
2308 for (page
= first_page
; page
<= last_page
; ++page
)
2309 if (cardseq_any_sticky_mark(page_to_card_index(page
))) return 0;
2311 /* Skip if any page is pinned.
2312 * The 'pinned' check is sort of bogus but sort of necessary,
2313 * but doesn't completely fix the problem that it tries to, which is
2314 * passing a memory address to the OS for it to write into.
2315 * An object on a never-written protected page would still fail.
2316 * It's probably rare to pass boxed pages to the OS, but it could be
2317 * to read fixnums into a simple-vector. */
2318 for (page
= first_page
; page
<= last_page
; ++page
)
2319 if (gc_page_pins
[page
]) return 0;
2322 /* Now we attempt to find any 1 "witness" that the pages should NOT be protected.
2323 * If such witness is found, then return without doing anything, otherwise
2324 * apply protection to the range. */
2325 lispobj
* witness
= range_dirty_p(where
, limit
, page_table
[first_page
].gen
);
2326 if (witness
) return witness
;
2328 for (page
= first_page
; page
<= last_page
; ++page
) {
2329 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2330 // Don't worry, the cards are all clean - if any card mark was sticky,
2331 // then we would have bailed out as the first thing (way up above).
2332 assign_page_card_marks(page
, CARD_UNMARKED
);
2334 // Try to avoid a system call
2335 if (!PAGE_WRITEPROTECTED_P(page
)) protect_page(page_address(page
));
2341 /* Decide if this single-object page holds a normal simple-vector.
2342 * "Normal" now includes non-weak address-insensitive k/v vectors */
2343 static inline bool large_scannable_vector_p(page_index_t page
) {
2344 lispobj header
= *(lispobj
*)page_address(page
);
2345 if (header_widetag(header
) == SIMPLE_VECTOR_WIDETAG
) {
2346 int mask
= (flag_VectorWeak
| flag_VectorAddrHashing
) << ARRAY_FLAGS_POSITION
;
2347 if (header
& mask
) return 0;
2348 if (vector_flagp(header
, VectorHashing
)) {
2349 lispobj
* data
= ((struct vector
*)page_address(page
))->data
;
2350 // If not very full, use the normal path.
2351 // The exact boundary here doesn't matter too much.
2352 if (KV_PAIRS_HIGH_WATER_MARK(data
) < (int)(GENCGC_PAGE_BYTES
/N_WORD_BYTES
))
2360 /* Attempt to re-protect code from first_page to last_page inclusive.
2361 * The object bounds are 'start' and 'limit', the former being redundant
2362 * with page_address(first_page).
2363 * Immobile space is dealt with in "immobile-space.c"
2366 update_code_writeprotection(page_index_t first_page
, page_index_t last_page
,
2367 lispobj
* start
, lispobj
* limit
)
2369 if (!ENABLE_PAGE_PROTECTION
) return;
2371 for (i
=first_page
; i
<= last_page
; ++i
) {// last_page is inclusive
2372 gc_assert(is_code(page_table
[i
].type
));
2373 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2374 if (cardseq_any_sticky_mark(page_to_card_index(i
))) {
2380 lispobj
* where
= start
;
2381 for (; where
< limit
; where
+= headerobj_size(where
)) {
2382 switch (widetag_of(where
)) {
2383 case CODE_HEADER_WIDETAG
:
2384 if (header_rememberedp(*where
)) return;
2386 case FUNCALLABLE_INSTANCE_WIDETAG
:
2387 if (range_dirty_p(where
, where
+headerobj_size(where
), page_table
[first_page
].gen
))
2392 for (i
= first_page
; i
<= last_page
; i
++) assign_page_card_marks(i
, CARD_UNMARKED
);
2395 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2396 # define card_stickymarked_p(x) (gc_card_mark[x] == STICKY_MARK)
2398 extern int descriptors_scavenge(lispobj
*, lispobj
*, generation_index_t
, int);
2399 int root_boxed_words_scanned
, root_vector_words_scanned
, root_mixed_words_scanned
;
2401 /* Special treatment for strictly boxed pages improves on the general case as follows:
2402 * - It can skip determining the extent of the contiguous block up front,
2403 * instead just blasting through the cards as it sees them.
2404 * - If only a subset of cards in a contiguous block are dirty, the scan
2405 * can be restricted to that subset. We don't need to align at object boundaries.
2406 * - It is not necessary to invoke a scavenge method specific to each object type.
2407 * - new write-protection status can be recomputed as we go.
2408 * This combination of aspects will be especially beneficial if cards are
2409 * are much smaller than they currently are (like 1K)
2411 * We have two choices for object traversal: walk object-by-object,
2412 * or card-by-card just blasting through the words looking for pointers.
2413 * But the latter can fail on a card-spanning object if care is not taken.
2414 * Example: Suppose the card size is 1K, and an instance has 200 slots.
2415 * The instance consumes around 1600 bytes (@ 8 bytes/word), which conceivably
2416 * could use 3 cards: header + 10 slots on the end of the first card,
2417 * 128 slots on the next, and the remainder on the final card. The soft write
2418 * barrier marks only the card with the header, so we don't know exactly
2419 * which card contains a modified pointer. Therefore, in all cases when using
2420 * card-by-card scan that disregards object boundaries, we have to assume
2421 * that 1 card beyond any marked card contains part of a marked object,
2422 * if that next card has the same scan start as its predecessor.
2423 * But where to stop scanning under this assumption? We shouldn't assume
2424 * that any marked card implies scanning an unbounded number of cards.
2425 * Therefore, a big instance should not be put on a purely boxed card.
2426 * (And granted, a massive instance will go on single-object pages.)
2427 * The other purely boxed objects are cons-sized, so they don't have a problem.
2428 * And (SETF SVREF) does mark an exact card, so it's all good.
2429 * Also, the hardware write barrier does not have this concern.
2431 #define WORDS_PER_CARD (GENCGC_CARD_BYTES/N_WORD_BYTES)
2432 static page_index_t
scan_boxed_root_cards_spanning(page_index_t page
, generation_index_t gen
)
2434 __attribute__((unused
)) int prev_marked
= 0;
2436 lispobj
* start
= (void*)page_address(page
);
2437 lispobj
* limit
= start
+ page_words_used(page
);
2438 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2439 long card
= addr_to_card_index(start
);
2440 /* Cards can change from marked to unmarked (just like with physical protection),
2441 * but also unmarked to marked, if transferring the card mark from the object's
2442 * header card to a cell in that object on a later card.
2443 * Lisp is given leeway because marking the header is easier. So the
2444 * algorithm accepts either way on input, but makes its output canonical.
2445 * (similar in spirit to Postel's Law) */
2446 if (prev_marked
|| cardseq_any_marked(card
)) {
2447 if (GC_LOGGING
) fprintf(gc_activitylog(), "scan_roots spanning %p\n", page_address(page
));
2449 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, ++card
, start
+= WORDS_PER_CARD
) {
2450 int marked
= card_dirtyp(card
);
2451 if (marked
|| prev_marked
) {
2452 lispobj
* end
= start
+ WORDS_PER_CARD
;
2453 if (end
> limit
) end
= limit
;
2454 int dirty
= descriptors_scavenge(start
, end
, gen
, card_stickymarked_p(card
));
2455 root_boxed_words_scanned
+= end
- start
;
2456 gc_card_mark
[card
] =
2457 (gc_card_mark
[card
] != STICKY_MARK
) ? (dirty
? CARD_MARKED
: CARD_UNMARKED
) :
2459 prev_marked
= marked
;
2464 if (!PAGE_WRITEPROTECTED_P(page
)) {
2465 int dirty
= descriptors_scavenge(start
, limit
, gen
, 0);
2466 if (ENABLE_PAGE_PROTECTION
&& !dirty
) protect_page(start
);
2470 } while (!page_ends_contiguous_block_p(page
-1, gen
));
2474 /* Large simple-vectors and pages of conses are even easier than strictly boxed root pages
2475 * because individual cons cells can't span cards, and vectors always mark the card of a
2476 * specific element. So there is no looking back 1 card to check for a marked header */
2477 static page_index_t
scan_boxed_root_cards_non_spanning(page_index_t page
, generation_index_t gen
)
2479 #ifndef LISP_FEATURE_SOFT_CARD_MARKS
2480 /* Physical protection doesn't distinguish between card-spanning and non-card-spanning,
2481 * because the write fault always occurs on the page that is getting dirtied by a store,
2482 * unlike soft marks which can mark an object header, but store onto the next card */
2483 return scan_boxed_root_cards_spanning(page
, gen
);
2486 lispobj
* start
= (void*)page_address(page
);
2487 long card
= addr_to_card_index(start
);
2488 if (cardseq_any_marked(card
)) {
2489 if (GC_LOGGING
) fprintf(gc_activitylog(), "scan_roots non-spanning %p\n", page_address(page
));
2490 lispobj
* limit
= start
+ page_words_used(page
);
2492 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, ++card
, start
+= WORDS_PER_CARD
) {
2493 if (card_dirtyp(card
)) {
2494 lispobj
* end
= start
+ WORDS_PER_CARD
;
2495 if (end
> limit
) end
= limit
;
2496 int dirty
= descriptors_scavenge(start
, end
, gen
,
2497 card_stickymarked_p(card
));
2498 root_vector_words_scanned
+= end
- start
;
2499 if (!dirty
) gc_card_mark
[card
] = CARD_UNMARKED
;
2504 } while (!page_ends_contiguous_block_p(page
-1, gen
));
2509 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2510 /* PAGE_TYPE_SMALL_MIXED roots are walked object-by-object to avoid affecting any raw word.
2511 * By construction, objects will never span cards */
2512 static page_index_t
scan_mixed_root_cards(page_index_t page
, generation_index_t gen
)
2515 lispobj
* start
= (void*)page_address(page
);
2516 long card
= addr_to_card_index(start
);
2517 if (cardseq_any_marked(card
)) {
2518 if (GC_LOGGING
) fprintf(gc_activitylog(), "scan_roots subcard mixed %p\n", page_address(page
));
2519 lispobj
* limit
= start
+ page_words_used(page
);
2521 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, ++card
, start
+= WORDS_PER_CARD
) {
2522 if (card_dirtyp(card
)) {
2523 lispobj
* end
= start
+ WORDS_PER_CARD
;
2524 if (end
> limit
) end
= limit
;
2525 // heap_scavenge doesn't take kindly to inverted start+end
2526 if (start
< limit
) {
2527 heap_scavenge(start
, limit
);
2528 if (!card_stickymarked_p(card
) && !range_dirty_p(start
, limit
, gen
))
2529 gc_card_mark
[card
] = CARD_UNMARKED
;
2531 gc_card_mark
[card
] = CARD_UNMARKED
;
2536 } while (!page_ends_contiguous_block_p(page
-1, gen
));
2541 /* Scavenge all generations greater than or equal to FROM.
2543 * Under the current scheme when a generation is GCed, the generations
2544 * younger than it are empty. So, when a generation is being GCed it
2545 * is only necessary to examine generations older than it for pointers.
2547 * Logical or physical write-protection is used to note pages that don't
2548 * contain old->young pointers. But pages can be written without having
2549 * such pointers. After the pages are scavenged here, they are examined
2550 * for old->young pointer, are marked clean (unprotected) if there are none.
2552 * Write-protected pages will not have any pointers to the
2553 * from_space so do not need scavenging, but might be visited
2554 * as part of a contiguous range containing a relevant page.
2558 scavenge_root_gens(generation_index_t from
)
2561 page_index_t limit
= next_free_page
;
2562 gc_dcheck(compacting_p());
2565 generation_index_t generation
= page_table
[i
].gen
;
2566 if (generation
< from
|| generation
== SCRATCH_GENERATION
2567 /* Not sure why word_used is checked. Probably because reset_page_flags()
2568 * does not change the page's gen to an unused number. Perhaps it should */
2569 || !page_boxed_p(i
) || !page_words_used(i
)) {
2574 /* This should be the start of a region */
2575 gc_assert(page_starts_contiguous_block_p(i
));
2577 if (page_table
[i
].type
== PAGE_TYPE_BOXED
) {
2578 i
= scan_boxed_root_cards_spanning(i
, generation
);
2579 } else if ((page_table
[i
].type
== PAGE_TYPE_CONS
) ||
2580 (page_single_obj_p(i
) && large_scannable_vector_p(i
))) {
2581 i
= scan_boxed_root_cards_non_spanning(i
, generation
);
2582 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2583 } else if (page_table
[i
].type
== PAGE_TYPE_SMALL_MIXED
) {
2584 i
= scan_mixed_root_cards(i
, generation
);
2587 page_index_t last_page
;
2589 /* Now work forward until the end of the region */
2590 for (last_page
= i
; ; last_page
++) {
2591 long card_index
= page_to_card_index(last_page
);
2592 marked
= marked
|| cardseq_any_marked(card_index
);
2593 if (page_ends_contiguous_block_p(last_page
, generation
))
2597 lispobj
* start
= (lispobj
*)page_address(i
);
2599 (lispobj
*)page_address(last_page
) + page_words_used(last_page
);
2600 if (GC_LOGGING
) fprintf(gc_activitylog(), "scan_roots mixed %p:%p\n", start
, limit
);
2601 root_mixed_words_scanned
+= limit
- start
;
2602 heap_scavenge(start
, limit
);
2603 /* Now scan the pages and write protect those that
2604 * don't have pointers to younger generations. */
2605 if (is_code(page_table
[i
].type
))
2606 update_code_writeprotection(i
, last_page
, start
, limit
);
2608 update_writeprotection(i
, last_page
, start
, limit
);
2616 /* Scavenge a newspace generation. As it is scavenged new objects may
2617 * be allocated to it; these will also need to be scavenged. This
2618 * repeats until there are no more objects unscavenged in the
2619 * newspace generation.
2621 * To help improve the efficiency, areas written are recorded by
2622 * gc_alloc() and only these scavenged. Sometimes a little more will be
2623 * scavenged, but this causes no harm. An easy check is done that the
2624 * scavenged bytes equals the number allocated in the previous
2627 * Write-protected pages are not scanned except if they are marked
2628 * pinned, in which case they may have been promoted and still have
2629 * pointers to the from space.
2631 * Write-protected pages could potentially be written by alloc however
2632 * to avoid having to handle re-scavenging of write-protected pages
2633 * gc_alloc() does not write to write-protected pages.
2635 * New areas of objects allocated are recorded alternatively in the two
2636 * new_areas arrays below. */
2637 static struct new_area new_areas_1
[NUM_NEW_AREAS
];
2638 static struct new_area new_areas_2
[NUM_NEW_AREAS
];
2640 /* Do one full scan of the new space generation. This is not enough to
2641 * complete the job as new objects may be added to the generation in
2642 * the process which are not scavenged. */
2643 static void newspace_full_scavenge(generation_index_t generation
)
2647 for (i
= 0; i
< next_free_page
; i
++) {
2648 if ((page_table
[i
].gen
== generation
) && page_boxed_p(i
)
2649 && (page_words_used(i
) != 0)
2650 && cardseq_any_marked(page_to_card_index(i
))) {
2651 page_index_t last_page
;
2653 /* The scavenge will start at the scan_start_offset of
2656 * We need to find the full extent of this contiguous
2657 * block in case objects span pages. */
2658 for (last_page
= i
; ;last_page
++) {
2659 /* Check whether this is the last page in this
2660 * contiguous block */
2661 if (page_ends_contiguous_block_p(last_page
, generation
))
2665 record_new_regions_below
= 1 + last_page
;
2666 heap_scavenge(page_scan_start(i
),
2667 (lispobj
*)page_address(last_page
) + page_words_used(last_page
));
2671 /* Enable recording of all new allocation regions */
2672 record_new_regions_below
= 1 + page_table_pages
;
2675 void gc_close_collector_regions(int flag
)
2677 ensure_region_closed(code_region
, flag
|PAGE_TYPE_CODE
);
2678 ensure_region_closed(boxed_region
, PAGE_TYPE_BOXED
);
2679 ensure_region_closed(unboxed_region
, PAGE_TYPE_UNBOXED
);
2680 ensure_region_closed(mixed_region
, PAGE_TYPE_MIXED
);
2681 ensure_region_closed(small_mixed_region
, PAGE_TYPE_SMALL_MIXED
);
2682 ensure_region_closed(cons_region
, PAGE_TYPE_CONS
);
2685 /* Do a complete scavenge of the newspace generation. */
2687 scavenge_newspace(generation_index_t generation
)
2689 /* Flush the current regions updating the page table. */
2690 gc_close_collector_regions(0);
2692 /* Turn on the recording of new areas. */
2693 gc_assert(new_areas_index
== 0);
2694 new_areas
= new_areas_1
;
2696 /* Start with a full scavenge. */
2697 if (GC_LOGGING
) fprintf(gc_activitylog(), "newspace full scav\n");
2698 newspace_full_scavenge(generation
);
2700 /* Flush the current regions updating the page table. */
2701 gc_close_collector_regions(0);
2704 if (GC_LOGGING
) fprintf(gc_activitylog(), "newspace loop\n");
2705 if (!new_areas_index
&& !immobile_scav_queue_count
) { // possible stopping point
2706 if (!test_weak_triggers(0, 0))
2707 break; // no work to do
2708 // testing of triggers can't detect whether any triggering object
2709 // actually entails new work - it only knows which triggers were removed
2710 // from the pending list. So check again if allocations occurred,
2711 // which is only if not all triggers referenced already-live objects.
2712 gc_close_collector_regions(0); // update new_areas from regions
2713 if (!new_areas_index
&& !immobile_scav_queue_count
)
2714 break; // still no work to do
2716 /* Move the current to the previous new areas */
2717 struct new_area
*previous_new_areas
= new_areas
;
2718 int previous_new_areas_index
= new_areas_index
;
2719 /* Note the max new_areas used. */
2720 if (new_areas_index
> new_areas_index_hwm
)
2721 new_areas_index_hwm
= new_areas_index
;
2723 /* Prepare to record new areas. Alternate between using new_areas_1 and 2 */
2724 new_areas
= (new_areas
== new_areas_1
) ? new_areas_2
: new_areas_1
;
2725 new_areas_index
= 0;
2727 scavenge_immobile_newspace();
2728 /* Check whether previous_new_areas had overflowed. */
2729 if (previous_new_areas_index
>= NUM_NEW_AREAS
) {
2731 /* New areas of objects allocated have been lost so need to do a
2732 * full scan to be sure! If this becomes a problem try
2733 * increasing NUM_NEW_AREAS. */
2734 newspace_full_scavenge(generation
);
2739 /* Work through previous_new_areas. */
2740 for (i
= 0; i
< previous_new_areas_index
; i
++) {
2741 page_index_t page
= previous_new_areas
[i
].page
;
2742 size_t offset
= previous_new_areas
[i
].offset
;
2743 size_t size
= previous_new_areas
[i
].size
;
2744 gc_assert(size
% (2*N_WORD_BYTES
) == 0);
2745 lispobj
*start
= (lispobj
*)(page_address(page
) + offset
);
2746 if (GC_LOGGING
) fprintf(gc_activitylog(), "heap_scav %p..%p\n",
2747 start
, (lispobj
*)((char*)start
+ size
));
2748 heap_scavenge(start
, (lispobj
*)((char*)start
+ size
));
2752 /* Flush the current regions updating the page table. */
2753 gc_close_collector_regions(0);
2756 /* Turn off recording of allocation regions. */
2757 record_new_regions_below
= 0;
2759 new_areas_index
= 0;
2762 /* Un-write-protect all the pages in from_space. This is done at the
2763 * start of a GC else there may be many page faults while scavenging
2764 * the newspace (I've seen drive the system time to 99%). These pages
2765 * would need to be unprotected anyway before unmapping in
2766 * free_oldspace; not sure what effect this has on paging..
2768 * Here is a real-life example of what can go wrong if we don't
2769 * unprotect oldspace:
2771 * - gc-with-promotion (raise=1) of gen2 to gen3
2772 * - symbol FOO in gen 3 on page 1000
2773 * - large vector 'v' in gen 2 on page 1300..1305
2774 * - 'v' points only to gen 2 objects (so it is unmarked, or "protected")
2775 * - symbol-value of FOO is 'v'
2776 * - root generations are 4 and higher
2777 * - no roots point to vector 'v' or any of its contents
2779 * - scavenge_newspace_full_scan visits page 1000
2780 * - assigns 'record_new_regions_below' = 1001
2781 * - traces slots of FOO, calls copy_potential_large_object(v)
2782 * - 'v' is promoted into gen3
2783 * - call add_new_area on page 1300..1305
2784 * - 1300 exceeds 1001 so we skip this area
2785 * So because 'v' is ahead of the wavefront, and theoretically page 1300
2786 * will be picked up by the remainder of the full_scan loop, we optimized out
2787 * the addition of the area. But then the scan loop sees that page 1300
2788 * is protected and it decides that it can can skip it even though it was
2789 * originally part of 'from_space' and points to other 'from_space' things.
2790 * The consequence is that everything 'v' pointed to in gen2 becomes freed
2791 * while 'v' holds dangling pointers to all that garbage.
2794 unprotect_oldspace(void)
2798 /* Gen0 never has protection applied, so we can usually skip the un-protect step,
2799 * however, in the final GC, because everything got moved to gen0 by brute force
2800 * adjustment of the page table, we don't know the state of the protection.
2801 * Therefore only skip out if NOT in the final GC */
2802 if (conservative_stack
&& from_space
== 0) return;
2804 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2805 for (i
= 0; i
< next_free_page
; i
++)
2806 /* Why does this even matter? Obviously it did for physical protection
2807 * (storing the forwarding pointers shouldn't fault)
2808 * but there's no physical protection, so ... why bother?
2809 * But I tried removing it and got assertion failures */
2810 if (page_words_used(i
) && page_table
[i
].gen
== from_space
)
2811 assign_page_card_marks(i
, CARD_MARKED
);
2813 char *page_addr
= 0;
2814 char *region_addr
= 0;
2815 uword_t region_bytes
= 0;
2816 for (i
= 0; i
< next_free_page
; i
++) {
2817 if ((page_words_used(i
) != 0)
2818 && (page_table
[i
].gen
== from_space
)) {
2820 /* Remove any write-protection. We should be able to rely
2821 * on the write-protect flag to avoid redundant calls. */
2822 if (PAGE_WRITEPROTECTED_P(i
)) {
2823 SET_PAGE_PROTECTED(i
, 0);
2824 if (protection_mode(i
) == PHYSICAL
) {
2825 page_addr
= page_address(i
);
2828 region_addr
= page_addr
;
2829 region_bytes
= GENCGC_PAGE_BYTES
;
2830 } else if (region_addr
+ region_bytes
== page_addr
) {
2831 /* Region continue. */
2832 region_bytes
+= GENCGC_PAGE_BYTES
;
2834 /* Unprotect previous region. */
2835 os_protect(region_addr
, region_bytes
, OS_VM_PROT_ALL
);
2836 /* First page in new region. */
2837 region_addr
= page_addr
;
2838 region_bytes
= GENCGC_PAGE_BYTES
;
2845 /* Unprotect last region. */
2846 os_protect(region_addr
, region_bytes
, OS_VM_PROT_ALL
);
2851 /* Work through all the pages and free any in from_space.
2852 * Live non-pinned objects will have been copied to new pages.
2853 * Pinned objects are no longer in 'from_space', as the containing
2854 * page is now in a different generation.
2855 * Bytes_allocated and the generation bytes_allocated
2856 * counter are updated. */
2857 static void free_oldspace(void)
2859 uword_t bytes_freed
= 0;
2861 for (page
= 0; page
< next_free_page
; ++page
) {
2862 if (page_table
[page
].gen
== from_space
) {
2863 /* Should already be unprotected by unprotect_oldspace(). */
2864 gc_dcheck(page_cards_all_marked_nonsticky(page
));
2865 /* Free the page. */
2866 int used
= page_words_used(page
);
2867 if (used
) set_page_need_to_zero(page
, 1);
2868 set_page_bytes_used(page
, 0);
2869 reset_page_flags(page
);
2870 bytes_freed
+= used
<< WORD_SHIFT
;
2873 generations
[from_space
].bytes_allocated
-= bytes_freed
;
2874 bytes_allocated
-= bytes_freed
;
2876 void free_large_object(lispobj
* where
, lispobj
* end
)
2878 page_index_t first
= find_page_index(where
);
2879 page_index_t last
= find_page_index((char*)end
- 1);
2880 generation_index_t g
= page_table
[first
].gen
;
2881 gc_assert(page_ends_contiguous_block_p(last
, g
));
2882 uword_t bytes_freed
= 0;
2884 // Perform all assertions before clobbering anything
2885 for (page
= first
; page
<= last
; ++page
) {
2886 gc_assert(page_single_obj_p(page
)); // redundant for the first page
2887 gc_assert(page_table
[page
].gen
== g
); // also redundant
2888 gc_assert(page_scan_start(page
) == where
);
2889 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2890 // FIXME: I've seen this check fail very often if -DDEBUG. Is it just wrong?
2891 // gc_dcheck(page_cards_all_marked_nonsticky(page));
2893 /* Force page to be writable. As much as memory faults should not occur
2894 * during GC, they are allowed, and this step will ensure writability. */
2895 *page_address(page
) = 0;
2898 // Copied from free_oldspace
2899 for (page
= first
; page
<= last
; ++page
) {
2900 int used
= page_words_used(page
);
2901 if (used
) set_page_need_to_zero(page
, 1);
2902 set_page_bytes_used(page
, 0);
2903 reset_page_flags(page
);
2904 bytes_freed
+= used
<< WORD_SHIFT
;
2906 generations
[g
].bytes_allocated
-= bytes_freed
;
2907 bytes_allocated
-= bytes_freed
;
2910 /* Call 'proc' with pairs of addresses demarcating ranges in the
2911 * specified generation.
2912 * Stop if any invocation returns non-zero, and return that value */
2914 walk_generation(uword_t (*proc
)(lispobj
*,lispobj
*,uword_t
),
2915 generation_index_t generation
, uword_t extra
)
2918 int genmask
= generation
>= 0 ? 1 << generation
: ~0;
2920 for (i
= 0; i
< next_free_page
; i
++) {
2921 if ((page_words_used(i
) != 0) && ((1 << page_table
[i
].gen
) & genmask
)) {
2922 page_index_t last_page
;
2924 /* This should be the start of a contiguous block */
2925 gc_assert(page_starts_contiguous_block_p(i
));
2927 /* Need to find the full extent of this contiguous block in case
2928 objects span pages. */
2930 /* Now work forward until the end of this contiguous area is
2932 for (last_page
= i
; ;last_page
++)
2933 /* Check whether this is the last page in this contiguous
2935 if (page_ends_contiguous_block_p(last_page
, page_table
[i
].gen
))
2939 proc((lispobj
*)page_address(i
),
2940 (lispobj
*)page_address(last_page
) + page_words_used(last_page
),
2942 if (result
) return result
;
2951 /* Write-protect all the dynamic boxed pages in the given generation. */
2953 write_protect_generation_pages(generation_index_t generation
)
2955 // Neither 0 nor scratch can be protected. Additionally, protection of
2956 // pseudo-static space is applied only in gc_load_corefile_ptes().
2957 gc_assert(generation
!= 0 && generation
!= SCRATCH_GENERATION
2958 && generation
!= PSEUDO_STATIC_GENERATION
);
2960 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
2962 for (page
= 0; page
< next_free_page
; ++page
) {
2963 if (page_table
[page
].gen
== generation
&& page_boxed_p(page
)
2964 && page_words_used(page
)) {
2965 long card
= page_to_card_index(page
);
2967 // must not touch a card referenced from the control stack
2968 // because the next instruction executed by user code
2969 // might store an old->young pointer.
2970 // There's probably a clever SIMD-in-a-register algorithm for this...
2971 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, card
++)
2972 if (gc_card_mark
[card
] != STICKY_MARK
) gc_card_mark
[card
] = CARD_UNMARKED
;
2976 page_index_t start
= 0, end
;
2977 int n_hw_prot
= 0, n_sw_prot
= 0;
2979 while (start
< next_free_page
) {
2980 if (!protect_page_p(start
, generation
)) {
2984 if (protection_mode(start
) == LOGICAL
) {
2985 SET_PAGE_PROTECTED(start
, 1);
2991 /* Note the page as protected in the page tables. */
2992 SET_PAGE_PROTECTED(start
, 1);
2994 /* Find the extent of pages desiring physical protection */
2995 for (end
= start
+ 1; end
< next_free_page
; end
++) {
2996 if (!protect_page_p(end
, generation
) || protection_mode(end
) == LOGICAL
)
2998 SET_PAGE_PROTECTED(end
, 1);
3001 n_hw_prot
+= end
- start
;
3002 os_protect(page_address(start
), npage_bytes(end
- start
), OS_VM_PROT_READ
);
3007 if (gencgc_verbose
> 1) {
3008 printf("HW protected %d, SW protected %d\n", n_hw_prot
, n_sw_prot
);
3014 move_pinned_pages_to_newspace()
3018 /* scavenge() will evacuate all oldspace pages, but no newspace
3019 * pages. Pinned pages are precisely those pages which must not
3020 * be evacuated, so move them to newspace directly. */
3022 for (i
= 0; i
< next_free_page
; i
++) {
3023 /* 'pinned' is cleared lazily, so test the 'gen' field as well. */
3024 if (gc_page_pins
[i
] == PAGE_PINNED
&&
3025 page_table
[i
].gen
== from_space
&&
3026 (page_single_obj_p(i
) ||
3027 (is_code(page_table
[i
].type
) && pin_all_dynamic_space_code
))) {
3028 page_table
[i
].gen
= new_space
;
3029 /* And since we're moving the pages wholesale, also adjust
3030 * the generation allocation counters. */
3031 page_bytes_t used
= page_bytes_used(i
);
3032 generations
[new_space
].bytes_allocated
+= used
;
3033 generations
[from_space
].bytes_allocated
-= used
;
3038 static void __attribute__((unused
)) maybe_pin_code(lispobj addr
) {
3039 page_index_t page
= find_page_index((char*)addr
);
3042 if (immobile_space_p(addr
))
3043 immobile_space_preserve_pointer((void*)addr
);
3046 if (immune_set_memberp(page
)) return;
3048 struct code
* code
= (struct code
*)dynamic_space_code_from_pc((char *)addr
);
3050 pin_exact_root(make_lispobj(code
, OTHER_POINTER_LOWTAG
));
3055 static void conservative_pin_code_from_return_addresses(struct thread
* th
) {
3056 lispobj
*object_ptr
;
3057 // We need more information to reliably backtrace through a call
3058 // chain, as these backends may generate leaf functions where the
3059 // return address does not get spilled. Therefore, fall back to
3060 // scanning the entire stack for potential interior code pointers.
3061 for (object_ptr
= th
->control_stack_start
;
3062 object_ptr
< access_control_stack_pointer(th
);
3064 maybe_pin_code(*object_ptr
);
3065 int i
= fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3066 // Scan program counters and return registers in interrupted
3067 // frames: They may contain interior code pointers that weren't
3068 // spilled onto the stack, as is the case for leaf functions.
3069 for (i
= i
- 1; i
>= 0; --i
) {
3070 os_context_t
* context
= nth_interrupt_context(i
, th
);
3071 maybe_pin_code(os_context_pc(context
));
3072 maybe_pin_code((lispobj
)*os_context_register_addr(context
, reg_RA
));
3077 #if defined LISP_FEATURE_MIPS || defined LISP_FEATURE_PPC64
3078 static void semiconservative_pin_stack(struct thread
* th
,
3079 generation_index_t gen
) {
3080 /* Stack can only pin code, since it contains return addresses.
3081 * Non-code pointers on stack do *not* pin anything, and may be updated
3083 * Interrupt contexts' boxed registers do pin their referents */
3084 lispobj
*object_ptr
;
3085 for (object_ptr
= th
->control_stack_start
;
3086 object_ptr
< access_control_stack_pointer(th
);
3088 maybe_pin_code(*object_ptr
);
3089 int i
= fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3090 for (i
= i
- 1; i
>= 0; --i
) {
3091 os_context_t
* context
= nth_interrupt_context(i
, th
);
3093 #if defined LISP_FEATURE_MIPS
3094 mcontext_t
*mctx
= &context
->uc_mcontext
;
3095 for(j
=1; j
<32; ++j
) {
3096 // context registers have more significant bits than lispobj.
3097 uword_t word
= mctx
->gregs
[j
];
3098 if (gen
== 0) sticky_preserve_pointer(word
, (void*)1);
3099 else preserve_pointer(word
, (void*)1);
3101 #elif defined LISP_FEATURE_PPC64
3102 static int boxed_registers
[] = BOXED_REGISTERS
;
3103 for (j
= (int)(sizeof boxed_registers
/ sizeof boxed_registers
[0])-1; j
>= 0; --j
) {
3104 lispobj word
= *os_context_register_addr(context
, boxed_registers
[j
]);
3105 if (gen
== 0) sticky_preserve_pointer(word
, (void*)1);
3106 else preserve_pointer(word
, (void*)1);
3108 // What kinds of data do we put in the Count register?
3109 // maybe it's count (raw word), maybe it's a PC. I just don't know.
3110 preserve_pointer(*os_context_lr_addr(context
), (void*)1);
3111 preserve_pointer(*os_context_ctr_addr(context
), (void*)1);
3113 preserve_pointer(os_context_pc(context
), (void*)1);
3118 #if GENCGC_IS_PRECISE && !defined(reg_CODE)
3120 static int boxed_registers
[] = BOXED_REGISTERS
;
3122 /* Pin all (condemned) code objects pointed to by the chain of in-flight calls
3123 * based on scanning from the innermost frame pointer. This relies on an exact backtrace,
3124 * which some of our architectures have trouble obtaining. But it's theoretically
3125 * more efficient to do it this way versus looking at all stack words to see
3126 * whether each points to a code object. */
3127 static void pin_call_chain_and_boxed_registers(struct thread
* th
) {
3128 lispobj
*cfp
= access_control_frame_pointer(th
);
3132 lispobj
* ocfp
= (lispobj
*) cfp
[0];
3133 lispobj lr
= cfp
[1];
3140 int i
= fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3141 for (i
= i
- 1; i
>= 0; --i
) {
3142 os_context_t
* context
= nth_interrupt_context(i
, th
);
3143 maybe_pin_code((lispobj
)*os_context_register_addr(context
, reg_LR
));
3145 for (unsigned i
= 0; i
< (sizeof(boxed_registers
) / sizeof(int)); i
++) {
3146 lispobj word
= *os_context_register_addr(context
, boxed_registers
[i
]);
3147 if (is_lisp_pointer(word
)) {
3148 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
3149 impart_mark_stickiness(word
);
3151 pin_exact_root(word
);
3159 #if !GENCGC_IS_PRECISE
3160 extern void visit_context_registers(void (*proc
)(os_context_register_t
, void*),
3161 os_context_t
*context
, void*);
3162 static void NO_SANITIZE_ADDRESS NO_SANITIZE_MEMORY
3163 conservative_stack_scan(struct thread
* th
,
3164 __attribute__((unused
)) generation_index_t gen
,
3165 // #+sb-safepoint uses os_get_csp() and not this arg
3166 __attribute__((unused
)) lispobj
* cur_thread_approx_stackptr
)
3168 /* there are potentially two stacks for each thread: the main
3169 * stack, which may contain Lisp pointers, and the alternate stack.
3170 * We don't ever run Lisp code on the altstack, but it may
3171 * host a sigcontext with lisp objects in it.
3172 * Actually, STOP_FOR_GC has a signal context on the main stack,
3173 * and the values it in will be *above* the stack-pointer in it
3174 * at the point of interruption, so we would not scan all registers
3175 * unless the context is scanned.
3177 * For the thread which initiates GC there will usually not be a
3178 * sigcontext, though there could, in theory be if it performs
3179 * GC while handling an interruption */
3181 __attribute__((unused
)) void (*context_method
)(os_context_register_t
,void*) =
3182 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
3183 gen
== 0 ? sticky_preserve_pointer
: preserve_pointer
;
3188 void* esp
= (void*)-1;
3189 # if defined(LISP_FEATURE_SB_SAFEPOINT)
3190 /* Conservative collect_garbage is always invoked with a
3191 * foreign C call or an interrupt handler on top of every
3192 * existing thread, so the stored SP in each thread
3193 * structure is valid, no matter which thread we are looking
3194 * at. For threads that were running Lisp code, the pitstop
3195 * and edge functions maintain this value within the
3196 * interrupt or exception handler. */
3197 esp
= os_get_csp(th
);
3198 assert_on_stack(th
, esp
);
3200 /* And on platforms with interrupts: scavenge ctx registers. */
3202 /* Disabled on Windows, because it does not have an explicit
3203 * stack of `interrupt_contexts'. The reported CSP has been
3204 * chosen so that the current context on the stack is
3205 * covered by the stack scan. See also set_csp_from_context(). */
3206 # ifndef LISP_FEATURE_WIN32
3207 if (th
!= get_sb_vm_thread()) {
3208 int k
= fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3210 os_context_t
* context
= nth_interrupt_context(--k
, th
);
3212 visit_context_registers(context_method
, context
, (void*)1);
3216 # elif defined(LISP_FEATURE_SB_THREAD)
3218 /* fprintf(stderr, "Thread %p, ici=%d stack[%p:%p] (%dw)",
3219 th, fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX,th)),
3220 th->control_stack_start, th->control_stack_end,
3221 th->control_stack_end - th->control_stack_start); */
3222 for (i
= fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
))-1; i
>=0; i
--) {
3223 os_context_t
*c
= nth_interrupt_context(i
, th
);
3224 visit_context_registers(context_method
, c
, (void*)1);
3225 lispobj
* esp1
= (lispobj
*) *os_context_register_addr(c
,reg_SP
);
3226 if (esp1
>= th
->control_stack_start
&& esp1
< th
->control_stack_end
&& (void*)esp1
< esp
)
3229 if (th
== get_sb_vm_thread()) {
3230 if ((void*)cur_thread_approx_stackptr
< esp
) esp
= cur_thread_approx_stackptr
;
3233 esp
= cur_thread_approx_stackptr
;
3235 if (!esp
|| esp
== (void*) -1)
3236 UNKNOWN_STACK_POINTER_ERROR("garbage_collect", th
);
3237 /* fprintf(stderr, " SP=%p (%dw)%s\n",
3238 esp, (int)(th->control_stack_end - (lispobj*)esp),
3239 (th == get_sb_vm_thread()) ? " CURRENT":""); */
3241 // Words on the stack which point into the stack are likely
3242 // frame pointers or alien or DX object pointers. In any case
3243 // there's no need to call preserve_pointer on them since
3244 // they definitely don't point to the heap.
3245 // See the picture at alloc_thread_struct() as a reminder.
3246 #ifdef LISP_FEATURE_UNIX
3247 lispobj exclude_from
= (lispobj
)th
->control_stack_start
;
3248 lispobj exclude_to
= (lispobj
)th
+ dynamic_values_bytes
;
3249 #define potential_heap_pointer(word) !(exclude_from <= word && word < exclude_to)
3251 // We can't use the heuristic of excluding words that appear to point into
3252 // 'struct thread' on win32 because ... I don't know why.
3253 // See https://groups.google.com/g/sbcl-devel/c/8s7mrapq56s/m/UaAjYPqKBAAJ
3254 #define potential_heap_pointer(word) 1
3258 for (ptr
= esp
; ptr
< th
->control_stack_end
; ptr
++) {
3259 lispobj word
= *ptr
;
3260 // Also note that we can eliminate small fixnums from consideration
3261 // since there is no memory on the 0th page.
3262 // (most OSes don't let users map memory there, though they used to).
3263 if (word
>= BACKEND_PAGE_BYTES
&& potential_heap_pointer(word
)) {
3264 preserve_pointer(word
, 0);
3270 static void scan_explicit_pins(__attribute__((unused
)) struct thread
* th
)
3272 lispobj pin_list
= read_TLS(PINNED_OBJECTS
, th
);
3273 for ( ; pin_list
!= NIL
; pin_list
= CONS(pin_list
)->cdr
) {
3274 lispobj object
= CONS(pin_list
)->car
;
3275 pin_exact_root(object
);
3276 if (lowtag_of(object
) == INSTANCE_POINTER_LOWTAG
) {
3277 struct instance
* instance
= INSTANCE(object
);
3278 lispobj layout
= instance_layout((lispobj
*)instance
);
3279 // Since we're still in the pinning phase of GC, layouts can't have moved yet,
3280 // so there is no forwarding check needed here.
3281 if (layout
&& lockfree_list_node_layout_p(LAYOUT(layout
))) {
3282 /* A logically-deleted explicitly-pinned lockfree list node pins its
3283 * successor too, since Lisp reconstructs the next node's tagged pointer
3284 * from an untagged pointer currently stored in %NEXT of this node. */
3285 lispobj successor
= ((struct list_node
*)instance
)->_node_next
;
3286 // Be sure to ignore an uninitialized word containing 0.
3287 if (successor
&& fixnump(successor
))
3288 pin_exact_root(successor
| INSTANCE_POINTER_LOWTAG
);
3294 /* Given the slightly asymmetric formulation of page_ends_contiguous_block_p()
3295 * you might think that it could cause the next page's assertion about start_block_p()
3296 * to fail, but it does not seem to. That's really weird! */
3297 __attribute__((unused
)) static void check_contiguity()
3299 page_index_t first
= 0;
3300 while (first
< next_free_page
) {
3301 if (!page_words_used(first
)) { ++first
; continue; }
3302 gc_assert(page_starts_contiguous_block_p(first
));
3303 page_index_t last
= first
;
3304 while (!page_ends_contiguous_block_p(last
, page_table
[first
].gen
)) ++last
;
3309 static void finish_code_metadata();
3310 int show_gc_generation_throughput
= 0;
3311 /* Garbage collect a generation. If raise is 0 then the remains of the
3312 * generation are not raised to the next generation. */
3313 void NO_SANITIZE_ADDRESS NO_SANITIZE_MEMORY
3314 garbage_collect_generation(generation_index_t generation
, int raise
,
3315 void* cur_thread_approx_stackptr
)
3319 if (gencgc_verbose
> 2) fprintf(stderr
, "BEGIN gc_gen(%d,%d)\n", generation
, raise
);
3321 #ifdef COLLECT_GC_STATS
3323 clock_gettime(CLOCK_MONOTONIC
, &t0
);
3324 uword_t gen_usage_at_start
= generations
[generation
].bytes_allocated
;
3325 uword_t higher_gen_usage_at_start
=
3326 raise
? generations
[generation
+1].bytes_allocated
: 0;
3329 gc_assert(generation
<= PSEUDO_STATIC_GENERATION
);
3331 /* The oldest generation can't be raised. */
3332 gc_assert(!raise
|| generation
< HIGHEST_NORMAL_GENERATION
);
3334 /* Check that weak hash tables were processed in the previous GC. */
3335 gc_assert(weak_hash_tables
== NULL
);
3337 /* When a generation is not being raised it is transported to a
3338 * temporary generation (NUM_GENERATIONS), and lowered when
3339 * done. Set up this new generation. There should be no pages
3340 * allocated to it yet. */
3342 gc_assert(generations
[SCRATCH_GENERATION
].bytes_allocated
== 0);
3345 hopscotch_reset(&pinned_objects
);
3347 #ifdef LISP_FEATURE_SB_THREAD
3348 pin_all_dynamic_space_code
= 0;
3349 for_each_thread(th
) {
3350 if (th
->state_word
.state
!= STATE_DEAD
&& \
3351 (read_TLS(GC_PIN_CODE_PAGES
, th
) & make_fixnum(1))) {
3352 pin_all_dynamic_space_code
= 1;
3357 pin_all_dynamic_space_code
= read_TLS(GC_PIN_CODE_PAGES
, 0) & make_fixnum(1);
3360 /* Set the global src and dest. generations */
3361 generation_index_t original_alloc_generation
= gc_alloc_generation
;
3363 if (generation
< PSEUDO_STATIC_GENERATION
) {
3365 from_space
= generation
;
3367 new_space
= generation
+1;
3369 new_space
= SCRATCH_GENERATION
;
3371 /* Change to a new space for allocation, resetting the alloc_start_page */
3372 gc_alloc_generation
= new_space
;
3373 RESET_ALLOC_START_PAGES();
3375 if (pin_all_dynamic_space_code
) {
3376 /* This needs to happen before ambiguous root pinning, as the mechanisms
3377 * overlap in a way that all-code pinning wouldn't do the right thing if flipped.
3378 * FIXME: why would it not? More explanation needed!
3379 * Code objects should never get into the pins table in this case */
3381 for (i
= 0; i
< next_free_page
; i
++) {
3382 if (page_table
[i
].gen
== from_space
3383 && is_code(page_table
[i
].type
) && page_words_used(i
))
3384 gc_page_pins
[i
] = PAGE_PINNED
;
3388 /* Un-write-protect the old-space pages. This is essential for the
3389 * promoted pages as they may contain pointers into the old-space
3390 * which need to be scavenged. It also helps avoid unnecessary page
3391 * faults as forwarding pointers are written into them. They need to
3392 * be un-protected anyway before unmapping later. */
3393 unprotect_oldspace();
3395 } else { // "full" [sic] GC
3397 gc_assert(!pin_all_dynamic_space_code
); // not supported (but could be)
3399 /* This is a full mark-and-sweep of all generations without compacting
3400 * and without returning free space to the allocator. The intent is to
3401 * break chains of objects causing accidental reachability.
3402 * Subsequent GC cycles will compact and reclaims space as usual. */
3403 from_space
= new_space
= -1;
3405 // Allocate pages from dynamic space for the work queue.
3406 extern void prepare_for_full_mark_phase();
3407 prepare_for_full_mark_phase();
3411 /* Possibly pin stack roots and/or *PINNED-OBJECTS*, unless saving a core.
3412 * Scavenging (fixing up pointers) will occur later on */
3414 if (conservative_stack
) {
3415 for_each_thread(th
) {
3416 if (th
->state_word
.state
== STATE_DEAD
) continue;
3417 scan_explicit_pins(th
);
3418 #if !GENCGC_IS_PRECISE
3419 /* Pin everything in fromspace with a stack root, and also set the
3420 * sticky card mark on any page (in any generation)
3421 * referenced from the stack. */
3422 conservative_stack_scan(th
, generation
, cur_thread_approx_stackptr
);
3423 #elif defined LISP_FEATURE_MIPS || defined LISP_FEATURE_PPC64
3424 // Pin code if needed
3425 semiconservative_pin_stack(th
, generation
);
3426 #elif defined REG_RA
3427 conservative_pin_code_from_return_addresses(th
);
3428 #elif !defined(reg_CODE)
3429 pin_call_chain_and_boxed_registers(th
);
3434 // Thread creation optionally no longer synchronizes the creating and
3435 // created thread. When synchronized, the parent thread is responsible
3436 // for pinning the start function for handoff to the created thread.
3437 // When not synchronized, The startup parameters are pinned via this list
3438 // which will always be NIL if the feature is not enabled.
3439 #ifdef STARTING_THREADS
3440 lispobj pin_list
= SYMBOL(STARTING_THREADS
)->value
;
3441 for ( ; pin_list
!= NIL
; pin_list
= CONS(pin_list
)->cdr
) {
3442 lispobj thing
= CONS(pin_list
)->car
;
3443 if (!thing
) continue; // Nothing to worry about when 'thing' is already smashed
3444 // It might be tempting to say that only the SB-THREAD:THREAD instance
3445 // requires pinning - because right after we access it to extract the
3446 // primitive thread, we link into all_threads - but it may be that the code
3447 // emitted by the C compiler in new_thread_trampoline computes untagged pointers
3448 // when accessing the vector and the start function, so those would not be
3449 // seen as valid lisp pointers by the implicit pinning logic.
3450 // And the precisely GC'd platforms would not pin anything from C code.
3451 // The tests in 'threads.impure.lisp' are good at detecting omissions here.
3452 gc_assert(instancep(thing
));
3453 struct thread_instance
*lispthread
= (void*)(thing
- INSTANCE_POINTER_LOWTAG
);
3454 lispobj info
= lispthread
->startup_info
;
3455 // INFO gets set to a fixnum when the thread is exiting. I *think* it won't
3456 // ever be seen in the starting-threads list, but let's be cautious.
3457 if (is_lisp_pointer(info
)) {
3458 gc_assert(simple_vector_p(info
));
3459 gc_assert(vector_len(VECTOR(info
)) >= 1);
3460 lispobj fun
= VECTOR(info
)->data
[0];
3461 gc_assert(functionp(fun
));
3462 pin_exact_root(fun
);
3463 // pin_exact_root is more efficient than preserve_pointer()
3464 // because it does not search for the object.
3465 pin_exact_root(thing
);
3466 pin_exact_root(info
);
3471 /* Remove any key from pinned_objects this does not identify an object.
3472 * This is done more efficiently by delaying until after all keys are
3473 * inserted rather than at each insertion */
3474 refine_ambiguous_roots();
3476 if (gencgc_verbose
> 1) {
3477 extern void dump_marked_objects();
3478 if (compacting_p()) show_pinnedobj_count(); /*else dump_marked_objects();*/
3481 /* Now that all of the pinned pages are known, and
3482 * before we start to scavenge (and thus relocate) objects,
3483 * relocate the pinned pages to newspace, so that the scavenger
3484 * will not attempt to relocate their contents. */
3486 move_pinned_pages_to_newspace();
3488 /* Scavenge all the rest of the roots. */
3490 #if GENCGC_IS_PRECISE
3492 * If not x86, we need to scavenge the interrupt context(s) and the
3493 * control stack, unless in final GC then don't.
3495 if (conservative_stack
) {
3497 for_each_thread(th
) {
3498 #if !defined(LISP_FEATURE_MIPS) && defined(reg_CODE) // interrupt contexts already pinned everything they see
3499 scavenge_interrupt_contexts(th
);
3501 scavenge_control_stack(th
);
3504 # ifdef LISP_FEATURE_SB_SAFEPOINT
3505 /* In this case, scrub all stacks right here from the GCing thread
3506 * instead of doing what the comment below says. Suboptimal, but
3509 scrub_thread_control_stack(th
);
3511 /* Scrub the unscavenged control stack space, so that we can't run
3512 * into any stale pointers in a later GC (this is done by the
3513 * stop-for-gc handler in the other threads). */
3514 scrub_control_stack();
3519 /* Scavenge the Lisp functions of the interrupt handlers */
3520 if (GC_LOGGING
) fprintf(gc_activitylog(), "begin scavenge sighandlers\n");
3522 scavenge(lisp_sig_handlers
, NSIG
);
3524 gc_mark_range(lisp_sig_handlers
, NSIG
);
3526 /* Scavenge the binding stacks. */
3527 if (GC_LOGGING
) fprintf(gc_activitylog(), "begin scavenge thread roots\n");
3530 for_each_thread(th
) {
3531 scav_binding_stack((lispobj
*)th
->binding_stack_start
,
3532 (lispobj
*)get_binding_stack_pointer(th
),
3533 compacting_p() ? 0 : gc_mark_obj
);
3534 /* do the tls as well */
3535 lispobj
* from
= &th
->lisp_thread
;
3536 lispobj
* to
= (lispobj
*)(SymbolValue(FREE_TLS_INDEX
,0) + (char*)th
);
3537 sword_t nwords
= to
- from
;
3539 scavenge(from
, nwords
);
3541 gc_mark_range(from
, nwords
);
3545 if (!compacting_p()) {
3546 #ifdef LISP_FEATURE_PERMGEN
3547 remember_all_permgen();
3549 extern void execute_full_mark_phase();
3550 extern void execute_full_sweep_phase();
3551 execute_full_mark_phase();
3552 execute_full_sweep_phase();
3556 if (GC_LOGGING
) fprintf(gc_activitylog(), "begin scavenge static roots\n");
3557 heap_scavenge((lispobj
*)NIL_SYMBOL_SLOTS_START
, (lispobj
*)NIL_SYMBOL_SLOTS_END
);
3558 heap_scavenge((lispobj
*)STATIC_SPACE_OBJECTS_START
, static_space_free_pointer
);
3559 #ifdef LISP_FEATURE_PERMGEN
3560 // Remembered objects below the core permgen end, and all objects above it, are roots.
3561 heap_scavenge((lispobj
*)permgen_bounds
[1], permgen_space_free_pointer
);
3562 int i
, n
= permgen_remset_count
;
3563 for (i
=0; i
<n
; ++i
) {
3564 lispobj
* o
= native_pointer(permgen_remset
[i
]);
3565 heap_scavenge(o
, object_size(o
)+o
);
3568 #ifdef LISP_FEATURE_LINKAGE_SPACE
3569 extern void scavenge_elf_linkage_space();
3570 scavenge_elf_linkage_space();
3572 #ifndef LISP_FEATURE_IMMOBILE_SPACE
3573 // TODO: use an explicit remembered set of modified objects in this range
3574 if (TEXT_SPACE_START
) heap_scavenge((lispobj
*)TEXT_SPACE_START
, text_space_highwatermark
);
3576 #ifdef LISP_FEATURE_SYSTEM_TLABS
3577 extern void gc_scavenge_arenas();
3578 gc_scavenge_arenas();
3581 /* All generations but the generation being GCed need to be
3582 * scavenged. The new_space generation needs special handling as
3583 * objects may be moved in - it is handled separately below. */
3585 // SCRATCH_GENERATION is scavenged in immobile space
3586 // because pinned objects will already have had their generation
3587 // number reassigned to that generation if applicable.
3588 scavenge_immobile_roots(generation
+1, SCRATCH_GENERATION
);
3590 // When collecting gen0, ordinarily the roots would be gen1 and higher,
3591 // but if gen0 is getting raised to 1 on this cycle, then we skip roots in gen1
3592 // because we'll eventually examine all of gen1 as part of newspace.
3593 // Similarly for higher generations. So if raising, the minimum root gen is
3594 // always the collected generation + 2, otherwise it's the collected + 1.
3595 if (GC_LOGGING
) fprintf(gc_activitylog(), "begin scavenge_root_gens\n");
3596 scavenge_root_gens(generation
+1+raise
);
3597 scavenge_pinned_ranges();
3598 /* The Lisp start function is stored in the core header, not a static
3599 * symbol. It is passed to gc_and_save() in this C variable */
3600 if (lisp_init_function
) scavenge(&lisp_init_function
, 1);
3601 if (lisp_package_vector
) scavenge(&lisp_package_vector
, 1);
3602 if (alloc_profile_data
) scavenge(&alloc_profile_data
, 1);
3604 /* If SB-SPROF was used, enliven all pages of code.
3605 * Note that some objects may have already been transported off the page.
3606 * Despite the extra scan, it is more efficient than scanning all trace buffers
3607 * and potentially updating them and/or invalidating hashes.
3608 * This really wants a better algorithm. Each code blob could have one byte
3609 * indicating whether it is present in any trace buffer; the SIGPROF handler
3610 * can update that byte. */
3611 if (sb_sprof_enabled
) {
3612 page_index_t first
= 0;
3613 while (first
< next_free_page
) {
3614 if (page_table
[first
].gen
!= from_space
3615 || !is_code(page_table
[first
].type
)
3616 || !page_words_used(first
)) {
3620 page_index_t last
= first
;
3621 while (!page_ends_contiguous_block_p(last
, from_space
)) ++last
;
3622 // [first,last] are inclusive bounds on a code range
3623 /* FIXME: should 'where' be initialized to page_scan_start()? I think so,
3624 * because ends_contiguous_block(page-1) does NOT imply
3625 * starts_contiguous_block(page). This is very unfortunate.
3626 * I've seen things such as the following:
3627 * page base: 0x20000 0x21000 0x22000
3629 * ss: 0x20000 0x20000 0x21010
3630 * where the first two pages were opened together and then closed
3631 * after consuming all of the first + 0x10 bytes more, and then the next
3632 * page extends the region (so not to waste the entire rest of the second
3633 * page), pointing its scan_start to the end of the range that was updated
3634 * into the page table. In that scenario, ends_p() is true of the page
3635 * based at 0x21000 but starts_p() is false of the next page,
3636 * because its scan start is an earlier page than itself.
3637 * How does this assertion NOT fail sometimes? Yet, it does not. */
3638 gc_assert(page_starts_contiguous_block_p(first
));
3639 lispobj
* where
= (lispobj
*)page_address(first
);
3640 lispobj
* limit
= (lispobj
*)page_address(last
) + page_words_used(last
);
3641 while (where
< limit
) {
3642 if (forwarding_pointer_p(where
)) {
3643 // The codeblob already survived GC, so we just need to step over it.
3644 lispobj
* copy
= native_pointer(forwarding_pointer_value(where
));
3645 // NOTE: it's OK to size the newspace copy rather than the original
3646 // because code size can't change.
3647 where
+= headerobj_size(copy
);
3649 // Compute 'nwords' before potentially moving the object
3650 // at 'where', because moving it stomps on the header word.
3651 sword_t nwords
= headerobj_size(where
);
3652 // If the object is not a filler and not a trampline, then create
3653 // a pointer to it and eliven the pointee.
3654 if (widetag_of(where
) == CODE_HEADER_WIDETAG
3655 && where
[1] != 0 /* has at least one boxed word */
3656 && code_serialno((struct code
*)where
) != 0) {
3657 lispobj ptr
= make_lispobj(where
, OTHER_POINTER_LOWTAG
);
3667 /* Finally scavenge the new_space generation. Keep going until no
3668 * more objects are moved into the new generation */
3669 scavenge_newspace(new_space
);
3670 if (save_lisp_gc_iteration
== 2) finish_code_metadata();
3672 scan_binding_stack();
3673 smash_weak_pointers();
3674 /* Return private-use pages to the general pool so that Lisp can have them */
3675 gc_dispose_private_pages();
3676 cull_weak_hash_tables(weak_ht_alivep_funs
);
3679 obliterate_nonpinned_words();
3680 // Do this last, because until obliterate_nonpinned_words() happens,
3681 // not all page table entries have the 'gen' value updated,
3682 // which we need to correctly find all old->young pointers.
3683 sweep_immobile_space(raise
);
3685 ASSERT_REGIONS_CLOSED();
3686 hopscotch_log_stats(&pinned_objects
, "pins");
3690 /* If this cycle was not a promotion cycle, change SCRATCH_GENERATION back
3691 * to its correct generation number */
3692 struct generation
* g
= &generations
[generation
];
3695 for (i
= 0; i
< next_free_page
; i
++)
3696 if (page_table
[i
].gen
== SCRATCH_GENERATION
) page_table
[i
].gen
= generation
;
3697 gc_assert(g
->bytes_allocated
== 0);
3698 g
->bytes_allocated
= generations
[SCRATCH_GENERATION
].bytes_allocated
;
3699 generations
[SCRATCH_GENERATION
].bytes_allocated
= 0;
3701 #ifdef COLLECT_GC_STATS
3702 if (show_gc_generation_throughput
) {
3704 clock_gettime(CLOCK_MONOTONIC
, &t1
);
3705 long et_nsec
= (t1
.tv_sec
- t0
.tv_sec
)*1000000000 + (t1
.tv_nsec
- t0
.tv_nsec
);
3706 sword_t bytes_retained
, bytes_freed
;
3708 bytes_retained
= (generations
[generation
+1].bytes_allocated
3709 - higher_gen_usage_at_start
);
3711 bytes_retained
= generations
[generation
].bytes_allocated
;
3713 bytes_freed
= gen_usage_at_start
- bytes_retained
;
3715 double pct_freed
= gen_usage_at_start
? (double)bytes_freed
/ gen_usage_at_start
: 0.0;
3716 double et_sec
= (double)et_nsec
/ 1000000000.0;
3717 double speed
= (double)(gc_copied_nwords
<< WORD_SHIFT
) / 1024 / et_sec
;
3718 char *units
= "KiB";
3719 if (speed
> 1024.0) speed
/= 1024.0, units
= "MiB";
3720 /* The pre-GC bytes allocated should sum to copied + pinned + freed, which it
3721 * more-or-less does, but there can be discrepancies because structure instances
3722 * can be extended with a stable-hash slot (which isn't accounted for at all),
3723 * vectors can be shrunk (part being "freed" and part being "copied", depending
3724 * on the size and partial pinning),and the finalizer hash-table can have cons
3725 * cells allocated to record the list of functions to call.
3726 * In particular, there could be 0 usage before, and some usage after due to
3727 * the finalizer table, which causes "freed" to be negative.
3728 * While those factors could be accounted for in the report, it would be needlessly
3729 * pedantic and confusing, and not really affect the big picture.
3730 * If the MiB per sec is low, it could be that not many bytes were copied.
3731 * Low speed + large count is bad though */
3733 // can't use fprintf() inside GC because of malloc. snprintf() can deadlock too,
3734 // but seems to do so much less often.
3735 int n
= snprintf(buffer
, sizeof buffer
,
3736 "gen%d: %ldw copied in %f sec (%.0f %s/sec), %ldw in-situ,"
3737 " %d pins (%ldw), %ldw freed (%.1f%%)\n",
3738 generation
, gc_copied_nwords
, et_sec
, speed
, units
,
3739 gc_in_situ_live_nwords
,
3740 gc_pin_count
, gc_pinned_nwords
,
3741 bytes_freed
>> WORD_SHIFT
, pct_freed
*100.0);
3742 write(2, buffer
, n
);
3743 n
= snprintf(buffer
, sizeof buffer
,
3744 "root word counts: %d + %d + %d\n", root_boxed_words_scanned
,
3745 root_vector_words_scanned
, root_mixed_words_scanned
);
3746 write(2, buffer
, n
);
3748 gc_copied_nwords
= gc_in_situ_live_nwords
= gc_pinned_nwords
= 0;
3749 root_boxed_words_scanned
= root_vector_words_scanned
= root_mixed_words_scanned
= 0;
3752 /* Reset the alloc_start_page for generation. */
3753 RESET_ALLOC_START_PAGES();
3755 /* Set the new gc trigger for the GCed generation. */
3756 g
->gc_trigger
= g
->bytes_allocated
+ g
->bytes_consed_between_gc
;
3757 g
->num_gc
= raise
? 0 : (1 + g
->num_gc
);
3760 // Have to kill this structure from its root, because any of the nodes would have
3761 // been on pages that got freed by free_oldspace.
3762 dynspace_codeblob_tree_snapshot
= 0;
3763 if (generation
>= verify_gens
)
3764 hexdump_and_verify_heap(cur_thread_approx_stackptr
,
3765 VERIFY_POST_GC
| (generation
<<1) | raise
);
3767 extern int n_unboxed_instances
;
3768 n_unboxed_instances
= 0;
3769 gc_alloc_generation
= original_alloc_generation
;
3773 find_next_free_page(void)
3775 page_index_t last_page
= -1, i
;
3777 for (i
= 0; i
< next_free_page
; i
++)
3778 if (page_words_used(i
) != 0)
3781 /* 1 page beyond the last used page is the next free page */
3782 return last_page
+ 1;
3785 generation_index_t small_generation_limit
= 1;
3787 extern int finalizer_thread_runflag
;
3789 /* GC all generations newer than last_gen, raising the objects in each
3790 * to the next older generation - we finish when all generations below
3791 * last_gen are empty. Then if last_gen is due for a GC, or if
3792 * last_gen==NUM_GENERATIONS (the scratch generation? eh?) we GC that
3793 * too. The valid range for last_gen is: 0,1,...,NUM_GENERATIONS.
3795 * We stop collecting at gencgc_oldest_gen_to_gc, even if this is less than
3796 * last_gen (oh, and note that by default it is NUM_GENERATIONS-1) */
3798 void NO_SANITIZE_ADDRESS NO_SANITIZE_MEMORY
3799 collect_garbage(generation_index_t last_gen
)
3803 generation_index_t gen
= 0, i
;
3804 bool gc_mark_only
= 0;
3805 int raise
, more
= 0;
3807 /* The largest value of next_free_page seen since the time
3808 * remap_free_pages was called. */
3809 static page_index_t high_water_mark
= 0;
3811 #ifdef COLLECT_GC_STATS
3812 struct timespec t_gc_start
;
3813 clock_gettime(CLOCK_MONOTONIC
, &t_gc_start
);
3815 log_generation_stats(gc_logfile
, "=== GC Start ===");
3819 if (last_gen
== 1+PSEUDO_STATIC_GENERATION
) {
3820 // Pseudostatic space undergoes a non-moving collection
3821 last_gen
= PSEUDO_STATIC_GENERATION
;
3823 } else if (last_gen
> 1+PSEUDO_STATIC_GENERATION
) {
3824 // This is a completely non-obvious thing to do, but whatever...
3828 /* Flush the alloc regions updating the page table.
3830 * GC is single-threaded and all memory allocations during a collection
3831 * happen in the GC thread, so it is sufficient to update PTEs for the
3832 * per-thread regions exactly once at the beginning of a collection
3833 * and update only from the GC's regions thereafter during collection.
3835 * The GC's regions are probably empty already, except:
3836 * - The code region is shared across all threads
3837 * - The boxed region is used in lieu of thread-specific regions
3838 * in a unithread build.
3839 * So we need to close them for those two cases.
3842 for_each_thread(th
) {
3843 gc_close_thread_regions(th
, 0);
3844 #ifdef LISP_FEATURE_PERMGEN
3845 // transfer the thread-local remset to the global remset
3846 remset_union(th
->remset
);
3850 #ifdef LISP_FEATURE_PERMGEN
3851 // transfer the remsets from threads that exited
3852 remset_union(remset_transfer_list
);
3853 remset_transfer_list
= 0;
3856 ensure_region_closed(code_region
, PAGE_TYPE_CODE
);
3857 if (gencgc_verbose
> 2) fprintf(stderr
, "[%d] BEGIN gc(%d)\n", n_lisp_gcs
, last_gen
);
3859 #ifdef LISP_FEATURE_IMMOBILE_SPACE
3860 if (ENABLE_PAGE_PROTECTION
) {
3861 // Unprotect the in-use ranges. Any page could be written during scavenge
3862 os_protect((os_vm_address_t
)FIXEDOBJ_SPACE_START
,
3863 (lispobj
)fixedobj_free_pointer
- FIXEDOBJ_SPACE_START
,
3868 lispobj
* cur_thread_approx_stackptr
=
3869 (lispobj
*)ALIGN_DOWN((uword_t
)&last_gen
, N_WORD_BYTES
);
3870 /* Verify the new objects created by Lisp code. */
3871 if (pre_verify_gen_0
)
3872 hexdump_and_verify_heap(cur_thread_approx_stackptr
, VERIFY_PRE_GC
);
3874 if (gencgc_verbose
> 1) {
3875 fprintf(stderr
, "Pre-GC:\n");
3876 print_generation_stats();
3879 /* After a GC, pages of code are safe to linearly scan because
3880 * there won't be random junk on them below page_bytes_used.
3881 * But generation 0 pages are _not_ safe to linearly scan because they aren't
3882 * pre-zeroed. The SIGPROF handler could have a bad time if were to misread
3883 * the header of an object mid-creation. Therefore, codeblobs newly made by Lisp
3884 * are kept in a lock-free and threadsafe datastructure. But we don't want to
3885 * enliven nodes of that structure for Lisp to see (absent any other references)
3886 * because the whole thing becomes garbage after this GC. So capture the tree
3887 * for GC's benefit, and delete the view of it from Lisp.
3888 * Incidentally, immobile text pages have their own tree, for other purposes
3889 * (among them being to find page scan start offsets) which is pruned as
3890 * needed by a finalizer. */
3891 dynspace_codeblob_tree_snapshot
= SYMBOL(DYNSPACE_CODEBLOB_TREE
)->value
;
3892 SYMBOL(DYNSPACE_CODEBLOB_TREE
)->value
= NIL
;
3894 page_index_t initial_nfp
= next_free_page
;
3896 garbage_collect_generation(PSEUDO_STATIC_GENERATION
, 0,
3897 cur_thread_approx_stackptr
);
3902 /* Collect the generation. */
3904 if (more
|| (gen
>= gencgc_oldest_gen_to_gc
)) {
3905 /* Never raise the oldest generation. Never raise the extra generation
3906 * collected due to more-flag. */
3912 || (generations
[gen
].num_gc
>= generations
[gen
].number_of_gcs_before_promotion
);
3913 /* If we would not normally raise this one, but we're
3914 * running low on space in comparison to the object-sizes
3915 * we've been seeing, raise it and collect the next one
3917 if (!raise
&& gen
== last_gen
) {
3918 more
= (2*large_allocation
) >= (dynamic_space_size
- bytes_allocated
);
3923 /* If an older generation is being filled, then update its
3926 generations
[gen
+1].cum_sum_bytes_allocated
+=
3927 generations
[gen
+1].bytes_allocated
;
3930 garbage_collect_generation(gen
, raise
, cur_thread_approx_stackptr
);
3932 /* Reset the memory age cum_sum. */
3933 generations
[gen
].cum_sum_bytes_allocated
= 0;
3935 if (gencgc_verbose
> 1) {
3936 fprintf(stderr
, "Post-GC(gen=%d):\n", gen
);
3937 print_generation_stats();
3941 } while ((gen
<= gencgc_oldest_gen_to_gc
)
3942 && ((gen
< last_gen
)
3945 && (generations
[gen
].bytes_allocated
3946 > generations
[gen
].gc_trigger
)
3947 && (generation_average_age(gen
)
3948 > generations
[gen
].minimum_age_before_gc
))));
3950 /* Now if gen-1 was raised all generations before gen are empty.
3951 * If it wasn't raised then all generations before gen-1 are empty.
3953 * Now objects within this gen's pages cannot point to younger
3954 * generations unless they are written to. This can be exploited
3955 * by write-protecting the pages of gen; then when younger
3956 * generations are GCed only the pages which have been written
3961 gen_to_wp
= gen
- 1;
3963 /* There's not much point in WPing pages in generation 0 as it is
3964 * never scavenged (except promoted pages). */
3965 if ((gen_to_wp
> 0) && ENABLE_PAGE_PROTECTION
) {
3966 /* Check that they are all empty. */
3967 for (i
= 0; i
< gen_to_wp
; i
++) {
3968 if (generations
[i
].bytes_allocated
)
3969 lose("trying to write-protect gen. %d when gen. %d nonempty",
3972 write_protect_generation_pages(gen_to_wp
);
3974 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
3976 // Turn sticky cards marks to the regular mark.
3978 for (page
=0; page
<next_free_page
; ++page
) {
3979 long card
= page_to_card_index(page
);
3981 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, ++card
)
3982 if (gc_card_mark
[card
] == STICKY_MARK
) gc_card_mark
[card
] = CARD_MARKED
;
3987 /* Save the high-water mark before updating next_free_page */
3988 if (next_free_page
> high_water_mark
)
3989 high_water_mark
= next_free_page
;
3991 next_free_page
= find_next_free_page();
3993 /* Update auto_gc_trigger. Make sure we trigger the next GC before
3994 * running out of heap! */
3995 if (bytes_consed_between_gcs
<= (dynamic_space_size
- bytes_allocated
))
3996 auto_gc_trigger
= bytes_allocated
+ bytes_consed_between_gcs
;
3998 auto_gc_trigger
= bytes_allocated
+ (dynamic_space_size
- bytes_allocated
)/2;
4000 if(gencgc_verbose
) {
4001 #define MESSAGE ("Next gc when %"OS_VM_SIZE_FMT" bytes have been consed\n")
4004 // fprintf() can - and does - cause deadlock here.
4005 // snprintf() seems to work fine.
4006 n
= snprintf(buf
, sizeof buf
, MESSAGE
, (uintptr_t)auto_gc_trigger
);
4007 ignore_value(write(2, buf
, n
));
4011 /* If we did a big GC (arbitrarily defined as gen > 1), release memory
4014 if (gen
> small_generation_limit
) {
4015 if (next_free_page
> high_water_mark
)
4016 high_water_mark
= next_free_page
;
4017 // BUG? high_water_mark is the highest value of next_free_page,
4018 // which means that page_table[high_water_mark] was actually NOT ever
4019 // used, because next_free_page is an exclusive bound on the range
4020 // of pages used. But remap_free_pages takes to 'to' as an *inclusive*
4021 // bound. The only reason it's not an array overrun error is that
4022 // the page_table has one more element than there are pages.
4023 remap_free_pages(0, high_water_mark
);
4024 high_water_mark
= 0;
4027 large_allocation
= 0;
4029 write_protect_immobile_space();
4032 #ifdef COLLECT_GC_STATS
4033 struct timespec t_gc_done
;
4034 clock_gettime(CLOCK_MONOTONIC
, &t_gc_done
);
4035 long et_nsec
= (t_gc_done
.tv_sec
- t_gc_start
.tv_sec
)*1000000000
4036 + (t_gc_done
.tv_nsec
- t_gc_start
.tv_nsec
);
4037 tot_gc_nsec
+= et_nsec
;
4040 log_generation_stats(gc_logfile
, "=== GC End ===");
4041 // Increment the finalizer runflag. This acts as a count of the number
4042 // of GCs as well as a notification to wake the finalizer thread.
4043 if (finalizer_thread_runflag
!= 0) {
4044 int newval
= 1 + finalizer_thread_runflag
;
4045 // check if counter wrapped around. Don't store 0 as the new value,
4046 // as that causes the thread to exit.
4047 finalizer_thread_runflag
= newval
? newval
: 1;
4050 // Clear all pin bits for the next GC cycle.
4051 // This could be done in the background somehow maybe.
4052 page_index_t max_nfp
= initial_nfp
> next_free_page
? initial_nfp
: next_free_page
;
4053 memset(gc_page_pins
, 0, max_nfp
);
4054 #ifdef LISP_FEATURE_LINKAGE_SPACE
4055 sweep_linkage_space();
4057 // It's confusing to see 'from_space=5' and such in the next *pre* GC verification
4062 /* Initialization of gencgc metadata is split into two steps:
4063 * 1. gc_init() - allocation of a fixed-address space via mmap(),
4064 * failing which there's no reason to go on. (safepoint only)
4065 * 2. gc_allocate_ptes() - page table entries
4070 hopscotch_create(&pinned_objects
, HOPSCOTCH_HASH_FUN_DEFAULT
, 0 /* hashset */,
4071 32 /* logical bin count */, 0 /* default range */);
4072 #ifdef LISP_FEATURE_WIN32
4073 InitializeCriticalSection(&free_pages_lock
);
4077 int gc_card_table_nbits
;
4078 long gc_card_table_mask
;
4081 /* alloc() and alloc_list() are external interfaces for memory allocation.
4082 * They allocate to generation 0 and are not called from within the garbage
4083 * collector as it is only external uses that need the check for heap
4084 * size (GC trigger) and to disable the interrupts (interrupts are
4085 * always disabled during a GC).
4087 * The vops that allocate assume that the returned space is zero-filled.
4088 * (E.g. the most significant word of a 2-word bignum in MOVE-FROM-UNSIGNED.)
4090 * The check for a GC trigger is only performed when the current
4091 * region is full, so in most cases it's not needed. */
4093 int gencgc_alloc_profiler
;
4094 NO_SANITIZE_MEMORY lispobj
*
4095 lisp_alloc(int flags
, struct alloc_region
*region
, sword_t nbytes
,
4096 int page_type
, struct thread
*thread
)
4098 os_vm_size_t trigger_bytes
= 0;
4100 gc_assert(nbytes
> 0);
4102 /* Check for alignment allocation problems. */
4103 gc_assert((((uword_t
)region
->free_pointer
& LOWTAG_MASK
) == 0)
4104 && ((nbytes
& LOWTAG_MASK
) == 0));
4106 #define SYSTEM_ALLOCATION_FLAG 2
4107 #ifdef LISP_FEATURE_SYSTEM_TLABS
4108 lispobj
* handle_arena_alloc(struct thread
*, struct alloc_region
*, int, sword_t
);
4109 if (page_type
!= PAGE_TYPE_CODE
&& thread
->arena
&& !(flags
& SYSTEM_ALLOCATION_FLAG
))
4110 return handle_arena_alloc(thread
, region
, page_type
, nbytes
);
4113 ++thread
->slow_path_allocs
;
4114 if ((os_vm_size_t
) nbytes
> large_allocation
)
4115 large_allocation
= nbytes
;
4117 /* maybe we can do this quickly ... */
4118 /* I'd really like this "quick" case to be more uniform in terms of whether
4119 * it's allowed to occur at all. Some of the inconsistencies are:
4120 * - 32-bit x86 will (or would, not sure any more) choose to use
4121 * out-of-line allocation if lexical policy favors space.
4122 * - PPC at git rev 28aaa39f4e had a subtle "but-not-wrong" bug at the edge
4123 * where it trapped to C if the new free pointer was ':lge' instead of ':lgt'
4124 * the region end, fixed in rev 05047647.
4125 * - other architectures may have similar issues.
4126 * So because of those reasons, even if we satisfy the allocation
4127 * from the TLAB it might be worth a check of whether to refill
4129 void *new_obj
= region
->free_pointer
;
4130 char *new_free_pointer
= (char*)new_obj
+ nbytes
;
4131 if (new_free_pointer
<= (char*)region
->end_addr
) {
4132 region
->free_pointer
= new_free_pointer
;
4133 #if defined LISP_FEATURE_MIPS || defined LISP_FEATURE_PPC || \
4134 defined LISP_FEATURE_PPC64 || defined LISP_FEATURE_X86_64
4135 /* Most allocations should never get here, but two page types are special.
4136 * - CODE always comes through here.
4137 * - CONS can come through here because when overflow occurs in lisp,
4138 * the fallback logic will call lisp_alloc one or more times,
4139 * obtaining possibly discontiguous pages of conses */
4140 gc_assert(page_type
== PAGE_TYPE_CONS
|| page_type
== PAGE_TYPE_CODE
);
4145 /* We don't want to count nbytes against auto_gc_trigger unless we
4146 * have to: it speeds up the tenuring of objects and slows down
4147 * allocation. However, unless we do so when allocating _very_
4148 * large objects we are in danger of exhausting the heap without
4149 * running sufficient GCs.
4151 if ((os_vm_size_t
) nbytes
>= bytes_consed_between_gcs
)
4152 trigger_bytes
= nbytes
;
4154 /* we have to go the long way around, it seems. Check whether we
4155 * should GC in the near future
4157 if (auto_gc_trigger
&& (bytes_allocated
+trigger_bytes
> auto_gc_trigger
)) {
4158 /* Don't flood the system with interrupts if the need to gc is
4159 * already noted. This can happen for example when SUB-GC
4160 * allocates or after a gc triggered in a WITHOUT-GCING. */
4161 if (read_TLS(GC_PENDING
,thread
) == NIL
) {
4162 /* set things up so that GC happens when we finish the PA
4164 write_TLS(GC_PENDING
, LISP_T
, thread
);
4165 if (read_TLS(GC_INHIBIT
,thread
) == NIL
) {
4166 #ifdef LISP_FEATURE_SB_SAFEPOINT
4167 thread_register_gc_trigger();
4169 set_pseudo_atomic_interrupted(thread
);
4170 maybe_save_gc_mask_and_block_deferrables
4171 # if HAVE_ALLOCATION_TRAP_CONTEXT
4172 (thread_interrupt_data(thread
).allocation_trap_context
);
4181 /* For the architectures which do NOT use a trap instruction for allocation,
4182 * overflow, record a backtrace now if statistical profiling is enabled.
4183 * The ones which use a trap will backtrace from the signal handler.
4184 * Code allocations are ignored, because every code allocation
4185 * comes through lisp_alloc() which makes this not a statistical
4186 * sample. Also the trapping ones don't trap for code.
4187 * #+win32 doesn't seem to work, but neither does CPU profiling */
4188 #if !(defined LISP_FEATURE_PPC || defined LISP_FEATURE_PPC64 \
4189 || defined LISP_FEATURE_SPARC || defined LISP_FEATURE_WIN32)
4190 extern void allocator_record_backtrace(void*, struct thread
*);
4191 if (page_type
!= PAGE_TYPE_CODE
&& gencgc_alloc_profiler
4192 && thread
->state_word
.sprof_enable
)
4193 allocator_record_backtrace(__builtin_frame_address(0), thread
);
4196 if (flags
& 1) return gc_alloc_large(nbytes
, page_type
);
4198 int __attribute__((unused
)) ret
= mutex_acquire(&free_pages_lock
);
4200 ensure_region_closed(region
, page_type
);
4201 // hold the lock after alloc_new_region if a cons page
4202 int release
= page_type
!= PAGE_TYPE_CONS
;
4203 new_obj
= gc_alloc_new_region(nbytes
, page_type
, region
, release
);
4204 region
->free_pointer
= (char*)new_obj
+ nbytes
;
4205 // addr_diff asserts that 'end' >= 'free_pointer'
4206 int remaining
= addr_diff(region
->end_addr
, region
->free_pointer
);
4208 // System TLABs are not important to refill right away (in the nearly-empty case)
4209 // so put a high-enough number in 'remaining' to suppress the grab-another-page test
4210 if (flags
& SYSTEM_ALLOCATION_FLAG
) remaining
= 256;
4212 // Try to avoid the next Lisp -> C -> Lisp round-trip by possibly
4213 // requesting yet another region.
4214 if (page_type
== PAGE_TYPE_CONS
) {
4215 if (remaining
<= CONS_SIZE
* N_WORD_BYTES
) { // Refill now if <= 1 more cons to go
4216 gc_close_region(region
, page_type
);
4217 // Request > 2 words, forcing a new page to be claimed.
4218 gc_alloc_new_region(4 * N_WORD_BYTES
, page_type
, region
, 0); // don't release
4220 ret
= mutex_release(&free_pages_lock
);
4222 } else if (remaining
<= 4 * N_WORD_BYTES
4223 && TryEnterCriticalSection(&free_pages_lock
)) {
4224 gc_close_region(region
, page_type
);
4225 // Request > 4 words, forcing a new page to be claimed.
4226 gc_alloc_new_region(6 * N_WORD_BYTES
, page_type
, region
, 1); // do release
4232 #ifdef LISP_FEATURE_SPARC
4233 void mixed_region_rollback(sword_t size
)
4235 struct alloc_region
*region
= main_thread_mixed_region
;
4236 gc_assert(region
->free_pointer
> region
->end_addr
);
4237 region
->free_pointer
= (char*)region
->free_pointer
- size
;
4238 gc_assert(region
->free_pointer
>= region
->start_addr
4239 && region
->free_pointer
<= region
->end_addr
);
4244 * shared support for the OS-dependent signal handlers which
4245 * catch GENCGC-related write-protect violations
4247 void unhandled_sigmemoryfault(void* addr
);
4249 /* Depending on which OS we're running under, different signals might
4250 * be raised for a violation of write protection in the heap. This
4251 * function factors out the common generational GC magic which needs
4252 * to invoked in this case, and should be called from whatever signal
4253 * handler is appropriate for the OS we're running under.
4255 * Return true if this signal is a normal generational GC thing that
4256 * we were able to handle, or false if it was abnormal and control
4257 * should fall through to the general SIGSEGV/SIGBUS/whatever logic.
4259 * We have two control flags for this: one causes us to ignore faults
4260 * on unprotected pages completely, and the second complains to stderr
4261 * but allows us to continue without losing.
4263 extern bool ignore_memoryfaults_on_unprotected_pages
;
4264 bool ignore_memoryfaults_on_unprotected_pages
= 0;
4266 extern bool continue_after_memoryfault_on_unprotected_pages
;
4267 bool continue_after_memoryfault_on_unprotected_pages
= 0;
4269 int gencgc_handle_wp_violation(__attribute__((unused
)) void* context
, void* fault_addr
)
4271 page_index_t page_index
= find_page_index(fault_addr
);
4273 /* Check whether the fault is within the dynamic space. */
4274 if (page_index
== (-1)) {
4275 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4276 extern int immobile_space_handle_wp_violation(void*);
4277 if (immobile_space_handle_wp_violation(fault_addr
))
4281 /* It can be helpful to be able to put a breakpoint on this
4282 * case to help diagnose low-level problems. */
4283 unhandled_sigmemoryfault(fault_addr
);
4285 /* not within the dynamic space -- not our responsibility */
4289 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
4290 fake_foreign_function_call(context
);
4291 lose("misuse of mprotect() on dynamic space @ %p", fault_addr
);
4293 // Pages of code are never have MMU-based protection, except on darwin,
4294 // where they do, but they are thread-locally-un-protected when creating
4295 // objets on those pages.
4296 gc_assert(!is_code(page_table
[page_index
].type
));
4298 // There can not be an open region. gc_close_region() does not attempt
4299 // to flip that bit atomically. (What does this mean?)
4300 gc_assert(!(page_table
[page_index
].type
& OPEN_REGION_PAGE_FLAG
));
4302 // The collector should almost never incur page faults, but I haven't
4303 // found all the trouble spots. It may or may not be worth doing.
4304 // See git rev 8a0af65bfd24
4305 // if (gc_active_p && compacting_p()) lose("unexpected WP fault @ %p during GC", fault_addr);
4307 // Because this signal handler can not be interrupted by STOP_FOR_GC,
4308 // the only possible state change between reading the mark and deciding how
4309 // to proceed is due to another thread also unprotecting the address.
4310 // That's fine; in fact it's OK to read a stale value here.
4311 // The only harmful case would be where the mark byte says it was
4312 // never protected, and the fault occurred nonetheless. That can't happen.
4313 unsigned char mark
= gc_card_mark
[addr_to_card_index(fault_addr
)];
4316 case WP_CLEARED_AND_MARKED
: // possible data race
4317 unprotect_page(fault_addr
, WP_CLEARED_AND_MARKED
);
4320 if (!ignore_memoryfaults_on_unprotected_pages
) {
4321 void lisp_backtrace(int frames
);
4324 "Fault @ %p, PC=%p, page %"PAGE_INDEX_FMT
" (~WP) mark=%#x gc_active=%d\n"
4325 " mixed_region=%p:%p\n"
4326 " page.scan_start: %p .words_used: %u .type: %d .gen: %d\n",
4327 fault_addr
, (void*)(context
?os_context_pc(context
):(uword_t
)-1), page_index
,
4329 mixed_region
->start_addr
, mixed_region
->end_addr
,
4330 page_scan_start(page_index
),
4331 page_words_used(page_index
),
4332 page_table
[page_index
].type
,
4333 page_table
[page_index
].gen
);
4334 if (!continue_after_memoryfault_on_unprotected_pages
) lose("Feh.");
4338 return 1; // Handled
4340 /* This is to be called when we catch a SIGSEGV/SIGBUS, determine that
4341 * it's not just a case of the program hitting the write barrier, and
4342 * are about to let Lisp deal with it. It's basically just a
4343 * convenient place to set a gdb breakpoint. */
4345 unhandled_sigmemoryfault(void __attribute__((unused
)) *addr
)
4348 void zero_all_free_ranges() /* called only by gc_and_save() */
4351 // gc_and_save() dumps at the granularity of "backend" pages, not GC pages
4352 // so make sure that any extra GC pages are zeroed
4353 #if BACKEND_PAGE_BYTES > GENCGC_PAGE_BYTES
4354 const int gc_pagecount_align
= BACKEND_PAGE_BYTES
/GENCGC_PAGE_BYTES
;
4356 const int gc_pagecount_align
= 1;
4358 page_index_t limit
= ALIGN_UP(next_free_page
, gc_pagecount_align
);
4359 for (i
= 0; i
< limit
; i
++) {
4360 char* start
= page_address(i
);
4361 char* page_end
= start
+ GENCGC_PAGE_BYTES
;
4362 start
+= page_bytes_used(i
);
4363 memset(start
, 0, page_end
-start
);
4365 #ifndef LISP_FEATURE_SB_THREAD
4366 // zero the allocation regions at the start of static-space
4367 // This gets a spurious warning:
4368 // warning: 'memset' offset [0, 71] is out of the bounds [0, 0] [-Warray-bounds]
4369 // which 'volatile' works around.
4370 char * volatile region
= (char*)STATIC_SPACE_START
;
4371 bzero((char*)region
, 3*sizeof (struct alloc_region
));
4375 generation_index_t
gc_gen_of(lispobj obj
, int defaultval
) {
4376 int page
= find_page_index((void*)obj
);
4377 if (page
>= 0) return page_table
[page
].gen
;
4378 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4379 if (immobile_space_p(obj
))
4380 return immobile_obj_generation(base_pointer(obj
));
4385 /* Return 1 if 'a' is strictly younger than 'b'.
4386 * This asserts that 'a' is pinned if in 'from_space' because it is
4387 * specifically a helper function for scav_code_blob(), where this is
4388 * called after scavenging the header. So if something didn't get moved
4389 * out of from_space, then it must have been pinned.
4390 * So don't call this for anything except that use-case. */
4391 static inline bool obj_gen_lessp(lispobj obj
, generation_index_t b
)
4393 generation_index_t a
= gc_gen_of(obj
, ARTIFICIALLY_HIGH_GEN
);
4394 if (a
== from_space
) {
4395 gc_assert(pinned_p(obj
, find_page_index((void*)obj
)));
4398 return ((a
==SCRATCH_GENERATION
) ? from_space
: a
) < b
;
4401 /* Loosely inspired by the code in 'purify' */
4402 #define LATERBLOCKSIZE 50000 // arbitrary
4403 static struct later
{
4405 struct code
*list
[LATERBLOCKSIZE
];
4407 } *later_blocks
= NULL
;
4409 static void delay_code_metadata_scavenge(struct code
* code
)
4411 struct later
* block
= later_blocks
;
4412 if (!block
|| block
->count
== LATERBLOCKSIZE
) {
4413 block
= calloc(1, sizeof (struct later
));
4414 block
->next
= later_blocks
;
4415 later_blocks
= block
;
4417 block
->list
[block
->count
] = code
;
4421 static void finish_code_metadata()
4423 struct later
*block
= later_blocks
;
4425 save_lisp_gc_iteration
= 3; // ensure no more delaying of metadata scavenge
4426 for ( ; block
; block
= block
->next
) {
4427 for (i
= 0; i
< block
->count
; ++i
) {
4428 struct code
*c
= block
->list
[i
];
4429 gc_assert(!forwarding_pointer_p((lispobj
*)c
));
4430 // first two words are non-pointer, then come debug_info and fixups
4431 // in whatever order they were defined in objdef.
4432 scavenge((lispobj
*)c
+ 2, 2);
4433 CLEAR_WRITTEN_FLAG((lispobj
*)c
);
4436 scavenge_newspace(new_space
);
4439 sword_t
scav_code_blob(lispobj
*object
, lispobj header
)
4441 struct code
* code
= (struct code
*)object
;
4442 int nboxed
= code_header_words(code
);
4443 if (!nboxed
) goto done
;
4445 int my_gen
= gc_gen_of((lispobj
)object
, ARTIFICIALLY_HIGH_GEN
);
4446 if (my_gen
< ARTIFICIALLY_HIGH_GEN
&& ((my_gen
& 7) == from_space
)) {
4447 // Since 'from_space' objects are not directly scavenged - they can
4448 // only be scavenged after moving to newspace, then this object
4449 // must be pinned. (It's logically in newspace). Assert that.
4450 gc_assert(pinned_p(make_lispobj(object
, OTHER_POINTER_LOWTAG
),
4451 find_page_index(object
)));
4455 // If the header's 'written' flag is off and it was not copied by GC
4456 // into newspace, then the object should be ignored.
4458 // This test could stand to be tightened up: in a GC promotion cycle
4459 // (e.g. 0 becomes 1), we can't discern objects that got copied to newspace
4460 // from objects that started out there. Of the ones that were already there,
4461 // we need only scavenge those marked as written. All the copied one
4462 // should always be scavenged. So really what we could do is mark anything
4463 // that got copied as written, which would allow dropping the second half
4464 // of the OR condition. As is, we scavenge "too much" of newspace which
4465 // is not an issue of correctness but rather efficiency.
4466 if (header_rememberedp(header
) || (my_gen
== new_space
) ||
4467 #ifndef LISP_FEATURE_IMMOBILE_SPACE
4468 // if NO immobile-space, then text space is equivalent to static space
4469 ((uword_t
)object
>= TEXT_SPACE_START
&& object
< text_space_highwatermark
) ||
4471 ((uword_t
)object
>= STATIC_SPACE_START
&& object
< static_space_free_pointer
)) {
4472 // FIXME: We sometimes scavenge protected pages.
4473 // This assertion fails, but things work nonetheless.
4474 // gc_assert(!card_protected_p(object));
4476 if (save_lisp_gc_iteration
== 2 &&
4477 lowtag_of(code
->debug_info
) == INSTANCE_POINTER_LOWTAG
) {
4478 // Attempt to place debug-info at end of the heap by not scavenging now
4479 scavenge(object
+ 4, nboxed
- 4);
4480 delay_code_metadata_scavenge(code
);
4482 /* Scavenge the boxed section of the code data block. */
4483 scavenge(object
+ 2, nboxed
- 2);
4486 extern void scav_code_linkage_cells(struct code
*);
4487 scav_code_linkage_cells(code
);
4489 // What does this have to do with DARWIN_JIT?
4490 #if defined LISP_FEATURE_64_BIT && !defined LISP_FEATURE_DARWIN_JIT
4491 /* If any function in this code object redirects to a function outside
4492 * the object, then scavenge all entry points. Otherwise there is no need,
4493 * as trans_code() made necessary adjustments to internal entry points.
4494 * This test is just an optimization to avoid some work */
4495 if (((*object
>> 16) & 0xff) == CODE_IS_TRACED
) {
4497 { /* Not enough spare bits in the header to hold random flags.
4498 * Just do the extra work always */
4500 for_each_simple_fun(i
, fun
, code
, 1, {
4501 if (simplefun_is_wrapped(fun
)) {
4502 lispobj target_fun
= fun_taggedptr_from_self(fun
->self
);
4503 lispobj
new = target_fun
;
4505 if (new != target_fun
) fun
->self
= fun_self_from_taggedptr(new);
4510 if (save_lisp_gc_iteration
== 2) goto done
;
4512 /* If my_gen is other than newspace, then scan for old->young
4513 * pointers. If my_gen is newspace, there can be no such pointers
4514 * because newspace is the lowest numbered generation post-GC
4515 * (regardless of whether this is a promotion cycle) */
4516 if (my_gen
!= new_space
) {
4517 lispobj
*where
, *end
= object
+ nboxed
, ptr
;
4518 for (where
= object
+ 2; where
< end
; ++where
)
4519 if (is_lisp_pointer(ptr
= *where
) && obj_gen_lessp(ptr
, my_gen
))
4522 CLEAR_WRITTEN_FLAG(object
);
4525 return code_total_nwords(code
);
4528 void really_note_transporting(lispobj old
,void*new,sword_t nwords
)
4530 page_index_t p
= find_page_index((void*)old
);
4531 __attribute__((unused
)) uword_t page_usage_limit
= (uword_t
)((lispobj
*)page_address(p
) + page_words_used(p
));
4532 gc_assert(old
< (uword_t
)page_usage_limit
); // this helps find bogus pointers
4534 fprintf(gc_activitylog(),
4535 listp(old
)?"t %"OBJ_FMTX
" %"OBJ_FMTX
"\n":
4536 "t %"OBJ_FMTX
" %"OBJ_FMTX
" %x\n",
4537 old
, (uword_t
)new, (int)nwords
);
4540 /** heap invariant checker **/
4542 static bool card_markedp(void* addr
)
4544 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4545 if (immobile_space_p((lispobj
)addr
))
4546 return !immobile_card_protected_p(addr
);
4548 return gc_card_mark
[addr_to_card_index(addr
)] != CARD_UNMARKED
;
4551 // Check a single pointer. Return 1 if we should stop verifying due to too many errors.
4552 // (Otherwise continue showing errors until then)
4553 // NOTE: This function can produces false failure indications,
4554 // usually related to dynamic space pointing to the stack of a
4555 // dead thread, but there may be other reasons as well.
4556 static void note_failure(lispobj thing
, lispobj
*where
, struct verify_state
*state
,
4559 if (state
->flags
& VERIFY_PRINT_HEADER_ON_FAILURE
) {
4560 if (state
->flags
& VERIFY_PRE_GC
) fprintf(stderr
, "pre-GC failure\n");
4561 if (state
->flags
& VERIFY_POST_GC
) fprintf(stderr
, "post-GC failure\n");
4562 state
->flags
&= ~VERIFY_PRINT_HEADER_ON_FAILURE
;
4564 if (state
->object_addr
) {
4565 lispobj obj
= compute_lispobj(state
->object_addr
);
4566 page_index_t pg
= find_page_index(state
->object_addr
);
4567 fprintf(stderr
, "Ptr %p @ %"OBJ_FMTX
" (lispobj %"OBJ_FMTX
",pg%d,h=%"OBJ_FMTX
") sees %s\n",
4568 (void*)thing
, (uword_t
)where
, obj
, (int)pg
, *native_pointer(obj
), str
);
4569 // Record this in state->err_objs if possible
4571 for(i
=0; i
<MAX_ERR_OBJS
; ++i
)
4572 if (!state
->err_objs
[i
]) {
4573 state
->err_objs
[i
] = (uword_t
)state
->object_addr
;
4577 fprintf(stderr
, "Ptr %p @ %"OBJ_FMTX
" sees %s\n", (void*)thing
, (uword_t
)where
, str
);
4582 verify_pointer(lispobj thing
, lispobj
*where
, struct verify_state
*state
)
4584 /* Strict containment: no pointer from a heap space may point
4585 * to anything outside of a heap space. */
4586 // bool strict_containment = state->flags & VERIFY_FINAL;
4588 #define FAIL_IF(cond, why) \
4589 if (cond) { if (++state->nerrors > 25) return 1; note_failure(thing,where,state,why); }
4591 if (!is_lisp_pointer(thing
)) {
4592 FAIL_IF(!is_lisp_immediate(thing
), "strange non-pointer");
4595 // if (strict_containment && !gc_managed_heap_space_p(thing)) GC_WARN("non-Lisp memory");
4596 page_index_t source_page_index
= find_page_index(where
);
4597 page_index_t target_page_index
= find_page_index((void*)thing
);
4598 int source_is_generational
= source_page_index
>= 0 || immobile_space_p((lispobj
)where
);
4599 if (!(target_page_index
>= 0 || immobile_space_p(thing
))) return 0; // can't do much with it
4600 if ((state
->flags
& VERIFY_TAGS
) && target_page_index
>= 0) {
4602 FAIL_IF(!(is_cons_half(CONS(thing
)->car
) && is_cons_half(CONS(thing
)->cdr
)),
4605 FAIL_IF(LOWTAG_FOR_WIDETAG(widetag_of(native_pointer(thing
))) != lowtag_of(thing
),
4606 "incompatible widetag");
4609 generation_index_t to_gen
=
4610 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4611 points_to_asm_code_p((uword_t
)thing
)?
4612 gc_gen_of(make_lispobj((void*)asm_routines_start
,OTHER_POINTER_LOWTAG
),0):
4614 gc_gen_of(thing
, ARTIFICIALLY_HIGH_GEN
);
4615 if (to_gen
< state
->min_pointee_gen
) state
->min_pointee_gen
= to_gen
;
4616 if (state
->flags
& VERIFY_QUICK
) return 0;
4617 if (target_page_index
>= 0) {
4618 // If it's within the dynamic space it should point to a used page.
4619 FAIL_IF(page_free_p(target_page_index
), "free page");
4620 FAIL_IF(!(page_table
[target_page_index
].type
& OPEN_REGION_PAGE_FLAG
)
4621 && (thing
& (GENCGC_PAGE_BYTES
-1)) >= page_bytes_used(target_page_index
),
4622 "unallocated space");
4624 // The object pointed to must not have been discarded as garbage.
4625 FAIL_IF(!other_immediate_lowtag_p(*native_pointer(thing
)), "trashed object");
4627 // Must not point to a forwarding pointer
4628 FAIL_IF(*native_pointer(thing
) == FORWARDING_HEADER
, "forwarding ptr");
4629 // Forbid pointers from R/O space into a GCed space
4630 FAIL_IF((READ_ONLY_SPACE_START
<= (uword_t
)where
&& where
< read_only_space_free_pointer
),
4631 "dynamic space from RO space");
4632 // Card marking invariant check, but only if the source of pointer is a heap object
4633 if (header_widetag(state
->object_header
) == CODE_HEADER_WIDETAG
4634 && ! is_in_static_space(state
->object_addr
)
4635 && to_gen
< state
->object_gen
) {
4636 // two things must be true:
4637 // 1. the card containing the code must be marked
4638 FAIL_IF(!card_markedp(state
->object_addr
), "younger obj from WP'd code header page");
4639 // 2. the object header must be marked as written
4640 if (!header_rememberedp(state
->object_header
))
4641 lose("code @ %p (g%d). word @ %p -> %"OBJ_FMTX
" (g%d)",
4642 state
->object_addr
, state
->object_gen
, where
, thing
, to_gen
);
4643 } else if ((state
->flags
& VERIFYING_GENERATIONAL
) && to_gen
< state
->object_gen
4644 && source_is_generational
) {
4645 /* The WP criteria are:
4646 * - CONS marks the exact card since it can't span cards
4647 * - SIMPLE-VECTOR marks the card containing the cell with the old->young pointer.
4648 * - Everything else marks the object header -OR- the card with the pointer.
4649 * (either/or because Lisp marks the header card,
4650 * but the collector marks the cell's card.) */
4651 int marked
= card_markedp(where
)
4652 #ifdef LISP_FEATURE_SOFT_CARD_MARKS
4653 || (state
->object_header
4654 && header_widetag(state
->object_header
) != SIMPLE_VECTOR_WIDETAG
4655 && card_markedp(state
->object_addr
))
4656 #elif defined LISP_FEATURE_EXECUTABLE_FUNINSTANCES
4657 /* #+(and (not soft-card-marks) executable-funinstances) could find the mark
4658 * for a page-spanning funinstance on the preceding page, because it uses
4659 * logical marking, not physical protection of the page holding the pointer */
4660 || (header_widetag(state
->object_header
) == FUNCALLABLE_INSTANCE_WIDETAG
4661 && card_markedp(state
->object_addr
))
4664 FAIL_IF(!marked
, "younger obj from WP page");
4667 if (state
->flags
& VERIFY_AGGRESSIVE
) // Extreme paranoia mode
4668 valid
= valid_tagged_pointer_p(thing
);
4670 /* Efficiently decide whether 'thing' is plausible.
4671 * This MUST NOT use properly_tagged_descriptor_p() which
4672 * assumes a known good object base address, and would
4673 * "dangerously" scan a code component for embedded funs. */
4674 valid
= plausible_tag_p(thing
);
4676 /* If 'thing' points to a stack, we can only hope that the stack
4677 * frame is ok, or the object at 'where' is unreachable. */
4678 FAIL_IF(!valid
&& !is_in_stack_space(thing
), "junk");
4681 #define CHECK(pointer, where) if (verify_pointer(pointer, where, state)) return 1
4682 #define CHECK_LINKAGE_CELL(index, where) CHECK(linkage_cell_function(index), where)
4684 /* Return 0 if good, 1 if bad.
4685 * Take extra pains to process weak SOLIST nodes - Finalizer list nodes weakly point
4686 * to a referent via an untagged pointer, so the GC doesn't even have to know that
4687 * the reference is weak - it simply is ignored as a non-pointer.
4688 * This makes invariant verification a little tricky. We want to restore the tagged
4689 * pointer, but only if the list is the finalizer list. */
4690 extern bool finalizer_list_node_p(struct instance
*);
4691 static int verify_headered_object(lispobj
* object
, sword_t nwords
,
4692 struct verify_state
*state
)
4695 int widetag
= widetag_of(object
);
4696 if (instanceoid_widetag_p(widetag
)) {
4697 lispobj layout
= layout_of(object
);
4699 CHECK(layout
, object
);
4700 struct bitmap bitmap
= get_layout_bitmap(LAYOUT(layout
));
4701 if (lockfree_list_node_layout_p(LAYOUT(layout
))) {
4702 // These objects might have _two_ untagged references -
4703 // 1) the 'next' slot may or may not have tag bits
4704 // 2) finalizer list node always stores its referent as untagged
4705 struct list_node
* node
= (void*)object
;
4706 lispobj next
= node
->_node_next
;
4707 if (fixnump(next
) && next
)
4708 CHECK(next
| INSTANCE_POINTER_LOWTAG
, &node
->_node_next
);
4709 if (finalizer_node_layout_p(LAYOUT(layout
))) {
4710 struct solist_node
* node
= (void*)object
;
4711 // !fixnump(next) implies that this node is NOT deleted, nor in
4712 // the process of getting deleted by CANCEL-FINALIZATION
4713 if (node
->so_key
&& !fixnump(next
)) {
4714 gc_assert(fixnump(node
->so_key
));
4715 lispobj key
= compute_lispobj((lispobj
*)node
->so_key
);
4716 CHECK(key
, &node
->so_key
);
4720 for (i
=0; i
<(nwords
-1); ++i
)
4721 if (bitmap_logbitp(i
, bitmap
)) CHECK(object
[1+i
], object
+1+i
);
4725 if (widetag
== CODE_HEADER_WIDETAG
) {
4726 struct code
*code
= (struct code
*)object
;
4727 gc_assert(fixnump(object
[1])); // boxed size, needed for code_header_words()
4728 sword_t nheader_words
= code_header_words(code
);
4729 /* Verify the boxed section of the code data block */
4730 state
->min_pointee_gen
= ARTIFICIALLY_HIGH_GEN
;
4731 for (i
=2; i
<nheader_words
; ++i
) CHECK(object
[i
], object
+i
);
4732 #ifndef NDEBUG // avoid "unused" warnings on auto vars of for_each_simple_fun()
4733 // Check the SIMPLE-FUN headers
4734 for_each_simple_fun(i
, fheaderp
, code
, 1, {
4735 #if defined LISP_FEATURE_COMPACT_INSTANCE_HEADER
4736 lispobj
__attribute__((unused
)) layout
= funinstance_layout((lispobj
*)fheaderp
);
4737 gc_assert(!layout
|| layout
== LAYOUT_OF_FUNCTION
);
4738 #elif defined LISP_FEATURE_64_BIT
4739 gc_assert((fheaderp
->header
>> 32) == 0);
4743 #if 0 // this looks redundant. It's checked with each pointer, no?
4744 bool rememberedp
= header_rememberedp(code
->header
);
4745 /* The remembered set invariant is that an object is marked "written"
4746 * if and only if either it points to a younger object or is pointed
4747 * to by a register or stack. (The pointed-to case assumes that the
4748 * very next instruction on return from GC would store an old->young
4749 * pointer into that object). Non-compacting GC does not have the
4750 * "only if" part of that, nor does pre-GC verification because we
4751 * don't test the generation of the newval when storing into code. */
4752 if (is_in_static_space(object
)) { }
4753 else if (compacting_p() && (state
->flags
& VERIFY_POST_GC
) ?
4754 (state
->min_pointee_gen
< state
->object_gen
) != rememberedp
:
4755 (state
->min_pointee_gen
< state
->object_gen
) && !rememberedp
)
4756 lose("object @ %p is gen%d min_pointee=gen%d %s",
4757 (void*)state
->tagged_object
, state
->object_gen
, state
->min_pointee_gen
,
4758 rememberedp
? "written" : "not written");
4762 #if FUN_SELF_FIXNUM_TAGGED
4763 if (widetag
== CLOSURE_WIDETAG
&& object
[1] != 0) {
4764 __attribute__((unused
)) struct simple_fun
* sf
= (void*)(object
[1] - 2*N_WORD_BYTES
);
4765 gc_assert(header_widetag(sf
->header
) == SIMPLE_FUN_WIDETAG
);
4766 gc_assert(header_widetag(fun_code_header(sf
)->header
) == CODE_HEADER_WIDETAG
);
4769 if (widetag
== SYMBOL_WIDETAG
) {
4770 struct symbol
* s
= (void*)object
;
4771 CHECK(s
->value
, &s
->value
);
4772 CHECK(s
->fdefn
, &s
->fdefn
);
4773 CHECK(s
->info
, &s
->info
);
4774 #ifdef LISP_FEATURE_LINKAGE_SPACE
4775 CHECK_LINKAGE_CELL(symbol_linkage_index(s
), &s
->fdefn
);
4777 CHECK(decode_symbol_name(s
->name
), &s
->name
);
4780 if (widetag
== FDEFN_WIDETAG
) {
4781 struct fdefn
* f
= (void*)object
;
4782 CHECK(f
->name
, &f
->name
);
4783 CHECK(f
->fun
, &f
->fun
);
4784 #ifdef LISP_FEATURE_LINKAGE_SPACE
4785 CHECK_LINKAGE_CELL(fdefn_linkage_index(f
), &f
->fun
);
4787 CHECK(decode_fdefn_rawfun(f
), (lispobj
*)&f
->raw_addr
);
4791 for (i
=1; i
<nwords
; ++i
) CHECK(object
[i
], object
+i
);
4795 static __attribute__((unused
)) bool acceptable_filler_cons_p(lispobj
* where
)
4797 if (where
[0] == 0 && where
[1] == 0) return 1;
4798 // These "conses" can result from bignum multiplication-
4799 // trailing insigificant sign bits which get chopped.
4800 if (where
[0] == (uword_t
)-1 && where
[1] == (uword_t
)-1) return 1;
4801 if (where
[0] == (uword_t
)-1 && where
[1] == 0) return 1;
4804 static int verify_range(lispobj
* start
, lispobj
* end
, struct verify_state
* state
)
4806 lispobj
* where
= start
;
4807 if (state
->flags
& VERIFYING_GENERATIONAL
&& find_page_index(start
)>=0) {
4808 page_index_t page
= find_page_index(start
);
4809 if (page_table
[page
].type
== PAGE_TYPE_CONS
)
4810 gc_assert(page_words_used(page
) <= MAX_CONSES_PER_PAGE
*CONS_SIZE
);
4812 if ((state
->flags
& VERIFYING_UNFORMATTED
)) {
4813 while (where
< end
) {
4814 if (*where
!= NO_TLS_VALUE_MARKER
) {
4815 int result
= verify_pointer(*where
, where
, state
);
4816 if (result
) return result
;
4822 while (where
< end
) {
4823 int widetag
= is_header(*where
) ? header_widetag(*where
) : LIST_POINTER_LOWTAG
;
4824 /* Technically we should wait until after performing the widetag validity
4825 * tests before calling the sizer. Otherwise the lossage message would
4826 * not be as good as it could be. I guess that failure doesn't happen much */
4827 sword_t nwords
= object_size(where
);
4828 state
->object_addr
= where
;
4829 state
->object_header
= is_cons_half(*where
) ? 0 : *where
;
4830 if (state
->flags
& VERIFYING_GENERATIONAL
) {
4831 page_index_t pg
= find_page_index(where
);
4832 state
->object_gen
= pg
>= 0 ? page_table
[pg
].gen
:
4833 gc_gen_of((lispobj
)where
, ARTIFICIALLY_HIGH_GEN
);
4834 #ifdef LISP_FEATURE_PPC64
4835 // Cons fillers (two words of all 1s) cause failure of
4836 // the default verification logic, so brute-force skip them
4837 // regardless of whether the page type is PAGE_TYPE_CONS.
4838 if (*where
== (uword_t
)-1 && where
[1] == (uword_t
)-1) {
4843 if (widetag
!= FILLER_WIDETAG
&& pg
>= 0) {
4844 // Assert proper page type
4845 if (state
->object_header
) // is not a cons
4846 gc_assert(page_table
[pg
].type
!= PAGE_TYPE_CONS
);
4847 #ifdef LISP_FEATURE_USE_CONS_REGION
4848 else if (page_table
[pg
].type
!= PAGE_TYPE_CONS
) {
4849 if (is_cons_half(where
[0]))
4850 gc_assert(acceptable_filler_cons_p(where
));
4853 if (widetag
== CODE_HEADER_WIDETAG
) {
4854 if (!is_code(page_table
[pg
].type
))
4855 lose("object @ %p is code on non-code page", where
);
4856 } else if (widetag
== FUNCALLABLE_INSTANCE_WIDETAG
) {
4857 // where these reside depends on the architecture
4859 if (is_code(page_table
[pg
].type
))
4860 lose("object @ %p is non-code on code page", where
);
4864 if (!state
->object_header
) {
4865 if (verify_pointer(where
[0], where
+0, state
) ||
4866 verify_pointer(where
[1], where
+1, state
)) break;
4867 } else if (widetag
== FILLER_WIDETAG
) { // do nothing
4868 } else if (!(other_immediate_lowtag_p(widetag
) && LOWTAG_FOR_WIDETAG(widetag
))) {
4869 lose("Unhandled widetag %"OBJ_FMTX
" @ %p", *where
, where
);
4870 } else if (leaf_obj_widetag_p(widetag
)) {
4871 #ifdef LISP_FEATURE_UBSAN
4872 if (specialized_vector_widetag_p(widetag
)) {
4873 if (is_lisp_pointer(object
[1])) {
4874 struct vector
* bits
= (void*)native_pointer(object
[1]);
4875 if (header_widetag(bits
->header
) != SIMPLE_BIT_VECTOR_WIDETAG
)
4876 lose("bad shadow bits for %p", where
);
4877 gc_assert(header_widetag(bits
->header
) == SIMPLE_BIT_VECTOR_WIDETAG
);
4878 gc_assert(vector_len(bits
) >= vector_len((struct vector
*)object
));
4882 bool strict_containment
= state
->flags
& VERIFY_FINAL
;
4883 if (strict_containment
&& gencgc_verbose
&& widetag
== SAP_WIDETAG
&& where
[1])
4884 fprintf(stderr
, "\nStrange SAP %p -> %p\n", where
, (void*)where
[1]);
4886 if (verify_headered_object(where
, nwords
, state
)) break;
4893 static int verify(lispobj start
, lispobj
* end
, struct verify_state
* state
, int flags
)
4895 int savedflags
= state
->flags
;
4896 state
->flags
|= flags
;
4897 int result
= verify_range((lispobj
*)start
, end
, state
);
4898 state
->flags
= savedflags
;
4902 extern void save_gc_crashdump(char *, lispobj
*);
4903 /* Return the number of verification errors found.
4904 * You might want to use that as a deciding factor for dump the heap
4905 * to a file (which takes time, and generally isn't needed).
4906 * But if a particular verification fails, then do dump it */
4907 int verify_heap(__attribute__((unused
)) lispobj
* cur_thread_approx_stackptr
,
4910 int verbose
= gencgc_verbose
| ((flags
& VERIFY_VERBOSE
) != 0);
4912 struct verify_state state
;
4913 memset(&state
, 0, sizeof state
);
4914 state
.flags
= flags
;
4918 flags
& VERIFY_PRE_GC
? "Verify before GC" :
4919 flags
& VERIFY_POST_GC
? "Verify after GC(%d,%d)" :
4920 "Heap check", // if called at a random time
4921 (flags
>> 1) & 7, // generation number
4922 flags
& 1); // 'raise'
4924 state
.flags
|= VERIFY_PRINT_HEADER_ON_FAILURE
;
4926 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4928 // Try this verification if immobile-space was compiled with extra debugging.
4929 // But weak symbols don't work on macOS.
4930 extern void __attribute__((weak
)) check_text_pages();
4931 if (&check_text_pages
) check_text_pages();
4934 fprintf(stderr
, " [immobile]");
4935 if (verify(FIXEDOBJ_SPACE_START
,
4936 fixedobj_free_pointer
, &state
,
4937 flags
| VERIFYING_GENERATIONAL
)) goto out
;
4938 if (verify(TEXT_SPACE_START
,
4939 text_space_highwatermark
, &state
,
4940 flags
| VERIFYING_GENERATIONAL
)) goto out
;
4944 fprintf(stderr
, " [threads]");
4945 state
.object_addr
= 0;
4946 state
.object_gen
= 0;
4947 for_each_thread(th
) {
4948 if (th
->state_word
.state
== STATE_DEAD
) continue;
4949 if (verify((lispobj
)th
->binding_stack_start
,
4950 (lispobj
*)get_binding_stack_pointer(th
), &state
,
4951 VERIFYING_UNFORMATTED
)) goto out
;
4952 if (verify((lispobj
)&th
->lisp_thread
,
4953 (lispobj
*)(SymbolValue(FREE_TLS_INDEX
,0) + (char*)th
), &state
,
4954 VERIFYING_UNFORMATTED
))
4958 fprintf(stderr
, " [RO]");
4959 if (verify(READ_ONLY_SPACE_START
, read_only_space_free_pointer
, &state
, 0)) goto out
;
4961 fprintf(stderr
, " [static]");
4962 // Just don't worry about NIL, it's seldom the problem
4963 // if (verify(NIL_SYMBOL_SLOTS_START, (lispobj*)NIL_SYMBOL_SLOTS_END, &state, 0)) goto out;
4964 if (verify(STATIC_SPACE_OBJECTS_START
, static_space_free_pointer
, &state
, 0)) goto out
;
4966 fprintf(stderr
, " [permgen]");
4967 if (verify(PERMGEN_SPACE_START
, permgen_space_free_pointer
, &state
,0)) goto out
;
4969 fprintf(stderr
, " [dynamic]");
4970 state
.flags
|= VERIFYING_GENERATIONAL
;
4971 walk_generation((uword_t(*)(lispobj
*,lispobj
*,uword_t
))verify_range
,
4972 -1, (uword_t
)&state
);
4973 if (verbose
&& state
.nerrors
==0) fprintf(stderr
, " passed\n");
4975 if (state
.nerrors
&& !(flags
& VERIFY_DONT_LOSE
)) {
4976 // dump_spaces(&state, "verify failed");
4977 lose("Verify failed: %d errors", state
.nerrors
);
4979 return state
.nerrors
;
4982 void gc_show_pte(lispobj obj
)
4984 char marks
[1+CARDS_PER_PAGE
];
4985 page_index_t page
= find_page_index((void*)obj
);
4987 printf("page %"PAGE_INDEX_FMT
" base %p gen %d type %x ss %p used %x",
4988 page
, page_address(page
), page_table
[page
].gen
, page_table
[page
].type
,
4989 page_scan_start(page
), page_bytes_used(page
));
4990 if (page_starts_contiguous_block_p(page
)) printf(" startsblock");
4991 if (page_ends_contiguous_block_p(page
, page_table
[page
].gen
)) printf(" endsblock");
4992 printf(" (%s)\n", page_card_mark_string(page
, marks
));
4995 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4996 page
= find_text_page_index((void*)obj
);
4998 lispobj
* text_page_scan_start(low_page_index_t page
);
4999 int gens
= text_page_genmask
[page
];
5002 for (i
=0;i
<8;++i
) genstring
[i
] = (gens
& (1<<i
)) ? '0'+i
: '-';
5004 printf("page %d (v) base %p gens %s ss=%p%s\n",
5005 (int)page
, text_page_address(page
), genstring
,
5006 text_page_scan_start(page
),
5007 card_markedp((void*)obj
)?"":" WP");
5010 page
= find_fixedobj_page_index((void*)obj
);
5012 printf("page %d (f) align %d gens %x%s\n", (int)page
,
5013 fixedobj_pages
[page
].attr
.parts
.obj_align
,
5014 fixedobj_pages
[page
].attr
.parts
.gens_
,
5015 card_markedp((void*)obj
)?"": " WP");
5019 printf("not in GC'ed space\n");
5022 static int count_immobile_objects(__attribute__((unused
)) int gen
, int res
[3])
5024 #ifdef LISP_FEATURE_IMMOBILE_SPACE
5025 lispobj
* where
= (lispobj
*)FIXEDOBJ_SPACE_START
;
5026 lispobj
* end
= fixedobj_free_pointer
;
5027 while (where
< end
) {
5028 if (immobile_obj_generation(where
) == gen
) {
5029 switch (widetag_of(where
)) {
5030 case INSTANCE_WIDETAG
: ++res
[0]; break;
5031 case SYMBOL_WIDETAG
: ++res
[1]; break;
5034 where
+= object_size(where
);
5036 where
= (lispobj
*)TEXT_SPACE_START
;
5037 end
= text_space_highwatermark
;
5038 while (where
< end
) {
5039 if (widetag_of(where
) != FILLER_WIDETAG
&& immobile_obj_generation(where
) == gen
)
5041 where
+= object_size(where
);
5044 return (res
[0] | res
[1] | res
[2]) != 0;
5047 /* Count the number of pages in the given generation.
5048 * Additionally, if 'n_dirty' is non-NULL, then assign
5049 * into *n_dirty the count of marked pages.
5052 count_generation_pages(generation_index_t generation
, page_index_t
* n_dirty
)
5054 page_index_t i
, total
= 0, dirty
= 0;
5057 for (i
= 0; i
< next_free_page
; i
++)
5058 if (!page_free_p(i
) && (page_table
[i
].gen
== generation
)) {
5060 long card
= page_to_card_index(i
);
5061 for (j
=0; j
<CARDS_PER_PAGE
; ++j
, ++card
)
5062 if (card_dirtyp(card
)) ++dirty
;
5064 // divide by cards per page rounding up
5065 if (n_dirty
) *n_dirty
= (dirty
+ (CARDS_PER_PAGE
-1)) / CARDS_PER_PAGE
;
5069 // You can call this with 0 and NULL to perform its assertions silently
5070 void gc_gen_report_to_file(int filedes
, FILE *file
)
5072 #ifdef LISP_FEATURE_X86
5073 extern void fpu_save(void *), fpu_restore(void *);
5076 /* Can end up here after calling alloc_tramp which doesn't prepare
5077 * the x87 state, and the C ABI uses a different mode */
5078 fpu_save(fpu_state
);
5081 #define OUTPUT(str, len) \
5082 {if (file) fwrite(str, 1, len, file); if (filedes>=0) ignore_value(write(filedes, str, len));}
5084 /* Print the heap stats. */
5086 " | Immobile Objects |\n";
5087 OUTPUT(header1
, sizeof header1
-1);
5089 " Gen layout symbol code Boxed Cons Raw Code SmMix Mixed LgRaw LgCode LgMix"
5090 " Waste% Alloc Trig Dirty GCs Mem-age\n";
5091 OUTPUT(header2
, sizeof header2
-1);
5093 generation_index_t gen_num
, begin
, end
;
5094 int immobile_matrix
[8][3], have_immobile_obj
= 0;
5095 int immobile_totals
[3];
5096 memset(immobile_matrix
, 0, sizeof immobile_matrix
);
5097 memset(immobile_totals
, 0, sizeof immobile_totals
);
5098 for (gen_num
= 0; gen_num
<= 6; ++gen_num
) {
5099 if (count_immobile_objects(gen_num
, immobile_matrix
[gen_num
]))
5100 have_immobile_obj
|= 1 << gen_num
;
5101 immobile_totals
[0] += immobile_matrix
[gen_num
][0];
5102 immobile_totals
[1] += immobile_matrix
[gen_num
][1];
5103 immobile_totals
[2] += immobile_matrix
[gen_num
][2];
5105 // Print from the lowest gen that has any allocated pages.
5106 for (begin
= 0; begin
<= PSEUDO_STATIC_GENERATION
; ++begin
)
5107 if ((have_immobile_obj
>>begin
)&1 || generations
[begin
].bytes_allocated
) break;
5108 // Print up to and including the highest gen that has any allocated pages.
5109 for (end
= SCRATCH_GENERATION
; end
>= 0; --end
)
5110 if (generations
[end
].bytes_allocated
) break;
5113 page_index_t coltot
[9];
5114 uword_t eden_words_allocated
= 0;
5115 page_index_t eden_pages
= 0;
5116 memset(coltot
, 0, sizeof coltot
);
5117 for (gen_num
= begin
; gen_num
<= end
; gen_num
++) {
5119 page_index_t pagect
[9];
5120 int *objct
= immobile_matrix
[gen_num
];
5121 memset(pagect
, 0, sizeof pagect
);
5122 if (gen_num
== 0) { // Count the eden pages
5123 for (page
= 0; page
< next_free_page
; page
++)
5124 if (page_table
[page
].gen
== 0 && page_table
[page
].type
& THREAD_PAGE_FLAG
) {
5126 switch (page_table
[page
].type
& ~THREAD_PAGE_FLAG
) {
5127 case PAGE_TYPE_BOXED
: column
= 0; break;
5128 case PAGE_TYPE_CONS
: column
= 1; break;
5129 case PAGE_TYPE_CODE
: column
= 3; break;
5130 case PAGE_TYPE_MIXED
: column
= 5; break;
5131 default: lose("Bad eden page subtype: %x\n", page_table
[page
].type
);
5136 eden_words_allocated
+= page_words_used(page
);
5138 uword_t waste
= npage_bytes(eden_pages
) - (eden_words_allocated
<<WORD_SHIFT
);
5139 double pct_waste
= eden_pages
> 0 ?
5140 (double)waste
/ (double)npage_bytes(eden_pages
) * 100 : 0.0;
5143 int linelen
= snprintf(linebuf
, sizeof linebuf
,
5144 " E %6d %6d %6d %6d %7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%14"PAGE_INDEX_FMT
5146 "%28.1f %11"OS_VM_SIZE_FMT
"\n",
5147 objct
[0], objct
[1], objct
[2], objct
[3],
5148 pagect
[0], pagect
[1], pagect
[3], pagect
[5],
5149 pct_waste
, eden_words_allocated
<<WORD_SHIFT
);
5150 OUTPUT(linebuf
, linelen
);
5152 memset(pagect
, 0, sizeof pagect
);
5154 uword_t words_allocated
= 0;
5155 page_index_t tot_pages
= 0;
5156 for (page
= 0; page
< next_free_page
; page
++)
5157 if (!page_free_p(page
) && page_table
[page
].gen
== gen_num
5158 && !(page_table
[page
].type
& THREAD_PAGE_FLAG
)) {
5160 switch (page_table
[page
].type
& (SINGLE_OBJECT_FLAG
|PAGE_TYPE_MASK
)) {
5161 case PAGE_TYPE_BOXED
: column
= 0; break;
5162 case PAGE_TYPE_CONS
: column
= 1; break;
5163 case PAGE_TYPE_UNBOXED
: column
= 2; break;
5164 case PAGE_TYPE_CODE
: column
= 3; break;
5165 case PAGE_TYPE_SMALL_MIXED
: column
= 4; break;
5166 case PAGE_TYPE_MIXED
: column
= 5; break;
5167 case SINGLE_OBJECT_FLAG
|PAGE_TYPE_UNBOXED
: column
= 6; break;
5168 case SINGLE_OBJECT_FLAG
|PAGE_TYPE_CODE
: column
= 7; break;
5169 case SINGLE_OBJECT_FLAG
|PAGE_TYPE_MIXED
: column
= 8; break;
5170 default: lose("Invalid page type %#x (p%"PAGE_INDEX_FMT
")", page_table
[page
].type
, page
);
5175 words_allocated
+= page_words_used(page
);
5177 struct generation
* gen
= &generations
[gen_num
];
5179 gc_assert(gen
->bytes_allocated
==
5180 (words_allocated
+eden_words_allocated
) << WORD_SHIFT
);
5181 /* private-cons.inc doesn't update bytes_allocated */
5184 gc_assert(gen->bytes_allocated == words_allocated << WORD_SHIFT);
5187 page_index_t n_dirty
;
5188 count_generation_pages(gen_num
, &n_dirty
);
5189 uword_t waste
= npage_bytes(tot_pages
) - (words_allocated
<<WORD_SHIFT
);
5190 double pct_waste
= tot_pages
> 0 ?
5191 (double)waste
/ (double)npage_bytes(tot_pages
) * 100 : 0.0;
5193 snprintf(linebuf
, sizeof linebuf
,
5195 "%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
5196 "%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
5197 "%7"PAGE_INDEX_FMT
" %6.1f %11"OS_VM_SIZE_FMT
" %11"OS_VM_SIZE_FMT
,
5198 gen_num
, objct
[0], objct
[1], objct
[2],
5199 pagect
[0], pagect
[1], pagect
[2], pagect
[3], pagect
[4], pagect
[5],
5200 pagect
[6], pagect
[7], pagect
[8],
5201 pct_waste
, words_allocated
<<WORD_SHIFT
,
5202 (uintptr_t)gen
->gc_trigger
);
5203 // gen0 pages are never WPed
5204 linelen
+= snprintf(linebuf
+linelen
, sizeof linebuf
-linelen
,
5205 gen_num
==0?" -" : " %7"PAGE_INDEX_FMT
, n_dirty
);
5206 linelen
+= snprintf(linebuf
+linelen
, sizeof linebuf
-linelen
,
5207 " %3d %7.4f\n", gen
->num_gc
, generation_average_age(gen_num
));
5208 OUTPUT(linebuf
, linelen
);
5210 page_index_t tot_pages
= coltot
[0] + coltot
[1] + coltot
[2] + coltot
[3] + coltot
[4] +
5211 coltot
[5] + coltot
[6] + coltot
[7] + coltot
[8];
5212 uword_t waste
= npage_bytes(tot_pages
) - bytes_allocated
;
5213 double pct_waste
= (double)waste
/ (double)npage_bytes(tot_pages
) * 100;
5214 double heap_use_frac
= 100 * (double)bytes_allocated
/ (double)dynamic_space_size
;
5215 int *objct
= immobile_totals
;
5217 snprintf(linebuf
, sizeof linebuf
,
5219 "%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
5220 "%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
"%7"PAGE_INDEX_FMT
5221 "%7"PAGE_INDEX_FMT
" %6.1f%12"OS_VM_SIZE_FMT
5222 " [%.1f%% of %"OS_VM_SIZE_FMT
" max]\n",
5223 objct
[0], objct
[1], objct
[2],
5224 coltot
[0], coltot
[1], coltot
[2], coltot
[3], coltot
[4], coltot
[5], coltot
[6],
5225 coltot
[7], coltot
[8], pct_waste
,
5226 (uintptr_t)bytes_allocated
, heap_use_frac
, (uintptr_t)dynamic_space_size
);
5227 OUTPUT(linebuf
, linelen
);
5230 #ifdef LISP_FEATURE_X86
5231 fpu_restore(fpu_state
);