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". As of 20000618, this
20 * had been accepted for _ACM Computing Surveys_ and was available
21 * as a PostScript preprint through
22 * <http://www.cs.utexas.edu/users/oops/papers.html>
24 * <ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps>.
33 #if defined(LISP_FEATURE_WIN32) && defined(LISP_FEATURE_SB_THREAD)
34 #include "pthreads_win32.h"
42 #include "interrupt.h"
47 #include "gc-internal.h"
48 #include "gc-private.h"
49 #include "gencgc-private.h"
51 #include "pseudo-atomic.h"
53 #include "genesis/gc-tables.h"
54 #include "genesis/vector.h"
55 #include "genesis/weak-pointer.h"
56 #include "genesis/fdefn.h"
57 #include "genesis/simple-fun.h"
59 #include "genesis/hash-table.h"
60 #include "genesis/instance.h"
61 #include "genesis/layout.h"
63 #include "hopscotch.h"
64 #include "genesis/cons.h"
65 #include "forwarding-ptr.h"
67 /* forward declarations */
68 page_index_t
gc_find_freeish_pages(page_index_t
*restart_page_ptr
, sword_t nbytes
,
76 /* As usually configured, generations 0-5 are normal collected generations,
77 6 is pseudo-static (the objects in which are never moved nor reclaimed),
78 and 7 is scratch space used when collecting a generation without promotion,
79 wherein it is moved to generation 7 and back again.
82 SCRATCH_GENERATION
= PSEUDO_STATIC_GENERATION
+1,
86 /* Largest allocation seen since last GC. */
87 os_vm_size_t large_allocation
= 0;
94 /* the verbosity level. All non-error messages are disabled at level 0;
95 * and only a few rare messages are printed at level 1. */
97 boolean gencgc_verbose
= 1;
99 boolean gencgc_verbose
= 0;
102 /* FIXME: At some point enable the various error-checking things below
103 * and see what they say. */
105 /* We hunt for pointers to old-space, when GCing generations >= verify_gen.
106 * Set verify_gens to HIGHEST_NORMAL_GENERATION + 2 to disable this kind of
108 generation_index_t verify_gens
= HIGHEST_NORMAL_GENERATION
+ 2;
110 /* Should we do a pre-scan verify of generation 0 before it's GCed? */
111 boolean pre_verify_gen_0
= 0;
113 /* Should we check that newly allocated regions are zero filled? */
114 boolean gencgc_zero_check
= 0;
116 /* Should we check that the free space is zero filled? */
117 /* Don't use this - you'll get more mileage out of READ_PROTECT_FREE_PAGES,
118 * because we zero-fill lazily. This switch should probably be removed. */
119 boolean gencgc_enable_verify_zero_fill
= 0;
121 /* When loading a core, don't do a full scan of the memory for the
122 * memory region boundaries. (Set to true by coreparse.c if the core
123 * contained a pagetable entry).
125 boolean gencgc_partial_pickup
= 0;
127 /* If defined, free pages are read-protected to ensure that nothing
131 /* #define READ_PROTECT_FREE_PAGES */
135 * GC structures and variables
138 /* the total bytes allocated. These are seen by Lisp DYNAMIC-USAGE. */
139 os_vm_size_t bytes_allocated
= 0;
140 os_vm_size_t auto_gc_trigger
= 0;
142 /* the source and destination generations. These are set before a GC starts
144 generation_index_t from_space
;
145 generation_index_t new_space
;
147 /* Set to 1 when in GC */
148 boolean gc_active_p
= 0;
150 /* should the GC be conservative on stack. If false (only right before
151 * saving a core), don't scan the stack / mark pages dont_move. */
152 static boolean conservative_stack
= 1;
154 /* An array of page structures is allocated on gc initialization.
155 * This helps to quickly map between an address and its page structure.
156 * page_table_pages is set from the size of the dynamic space. */
157 page_index_t page_table_pages
;
158 struct page
*page_table
;
159 #ifdef LISP_FEATURE_SB_TRACEROOT
160 lispobj gc_object_watcher
;
161 int gc_traceroot_criterion
;
163 #ifdef PIN_GRANULARITY_LISPOBJ
165 struct hopscotch_table pinned_objects
;
168 /* This is always 0 except during gc_and_save() */
169 lispobj lisp_init_function
;
171 /// Constants defined in gc-internal:
172 /// #define BOXED_PAGE_FLAG 1
173 /// #define UNBOXED_PAGE_FLAG 2
174 /// #define OPEN_REGION_PAGE_FLAG 4
176 /// Return true if 'allocated' bits are: {001, 010, 011}, false if 1zz or 000.
177 static inline boolean
page_allocated_no_region_p(page_index_t page
) {
178 return (page_table
[page
].allocated
^ OPEN_REGION_PAGE_FLAG
) > OPEN_REGION_PAGE_FLAG
;
181 static inline boolean
page_free_p(page_index_t page
) {
182 return (page_table
[page
].allocated
== FREE_PAGE_FLAG
);
185 static inline boolean
page_boxed_p(page_index_t page
) {
186 return (page_table
[page
].allocated
& BOXED_PAGE_FLAG
);
189 /// Return true if 'allocated' bits are: {001, 011}, false otherwise.
190 /// i.e. true of pages which could hold boxed or partially boxed objects.
191 static inline boolean
page_boxed_no_region_p(page_index_t page
) {
192 return (page_table
[page
].allocated
& 5) == BOXED_PAGE_FLAG
;
195 /// Return true if page MUST NOT hold boxed objects (including code).
196 static inline boolean
page_unboxed_p(page_index_t page
) {
197 /* Both flags set == boxed code page */
198 return (page_table
[page
].allocated
& 3) == UNBOXED_PAGE_FLAG
;
201 static inline boolean
protect_page_p(page_index_t page
, generation_index_t generation
) {
202 return (page_boxed_no_region_p(page
)
203 && (page_bytes_used(page
) != 0)
204 && !page_table
[page
].dont_move
205 && (page_table
[page
].gen
== generation
));
208 /* Calculate the start address for the given page number. */
210 page_address(page_index_t page_num
)
212 return (void*)(DYNAMIC_SPACE_START
+ (page_num
* GENCGC_CARD_BYTES
));
215 /* Calculate the address where the allocation region associated with
216 * the page starts. */
218 page_scan_start(page_index_t page_index
)
220 return page_address(page_index
)-page_scan_start_offset(page_index
);
223 /* True if the page starts a contiguous block. */
224 static inline boolean
225 page_starts_contiguous_block_p(page_index_t page_index
)
227 // Don't use the preprocessor macro: 0 means 0.
228 return page_table
[page_index
].scan_start_offset_
== 0;
231 /* True if the page is the last page in a contiguous block. */
232 static inline boolean
233 page_ends_contiguous_block_p(page_index_t page_index
, generation_index_t gen
)
235 // There is *always* a next page in the page table.
236 boolean answer
= page_bytes_used(page_index
) < GENCGC_CARD_BYTES
237 || page_starts_contiguous_block_p(page_index
+1);
239 boolean safe_answer
=
240 (/* page doesn't fill block */
241 (page_bytes_used(page_index
) < GENCGC_CARD_BYTES
)
242 /* page is last allocated page */
243 || ((page_index
+ 1) >= last_free_page
)
244 /* next page contains no data */
245 || !page_bytes_used(page_index
+ 1)
246 /* next page is in different generation */
247 || (page_table
[page_index
+ 1].gen
!= gen
)
248 /* next page starts its own contiguous block */
249 || (page_starts_contiguous_block_p(page_index
+ 1)));
250 gc_assert(answer
== safe_answer
);
255 /* We maintain the invariant that pages with FREE_PAGE_FLAG have
256 * scan_start of zero, to optimize page_ends_contiguous_block_p().
257 * Clear all other flags as well, since they don't mean anything,
258 * and a store is simpler than a bitwise operation */
259 static inline void reset_page_flags(page_index_t page
) {
260 page_table
[page
].scan_start_offset_
= 0;
261 // Any C compiler worth its salt should merge these into one store
262 page_table
[page
].allocated
= page_table
[page
].write_protected
263 = page_table
[page
].write_protected_cleared
264 = page_table
[page
].dont_move
= page_table
[page
].has_pins
265 = page_table
[page
].large_object
= 0;
268 /// External function for calling from Lisp.
269 page_index_t
ext_find_page_index(void *addr
) { return find_page_index(addr
); }
272 npage_bytes(page_index_t npages
)
274 gc_assert(npages
>=0);
275 return ((os_vm_size_t
)npages
)*GENCGC_CARD_BYTES
;
278 /* Check that X is a higher address than Y and return offset from Y to
280 static inline os_vm_size_t
281 addr_diff(void *x
, void *y
)
284 return (uintptr_t)x
- (uintptr_t)y
;
287 /* a structure to hold the state of a generation
289 * CAUTION: If you modify this, make sure to touch up the alien
290 * definition in src/code/gc.lisp accordingly. ...or better yes,
291 * deal with the FIXME there...
296 // A distinct start page per nonzero value of 'page_type_flag'.
297 // The zeroth index is the large object start page.
298 page_index_t alloc_start_page_
[4];
299 #define alloc_large_start_page alloc_start_page_[0]
300 #define alloc_start_page alloc_start_page_[BOXED_PAGE_FLAG]
301 #define alloc_unboxed_start_page alloc_start_page_[UNBOXED_PAGE_FLAG]
303 /* the first page that gc_alloc_large (boxed) considers on its next
304 * call. (Although it always allocates after the boxed_region.) */
305 page_index_t alloc_large_start_page
;
307 /* the first page that gc_alloc() checks on its next call */
308 page_index_t alloc_start_page
;
310 /* the first page that gc_alloc_unboxed() checks on its next call */
311 page_index_t alloc_unboxed_start_page
;
314 /* the bytes allocated to this generation */
315 os_vm_size_t bytes_allocated
;
317 /* the number of bytes at which to trigger a GC */
318 os_vm_size_t gc_trigger
;
320 /* to calculate a new level for gc_trigger */
321 os_vm_size_t bytes_consed_between_gc
;
323 /* the number of GCs since the last raise */
326 /* the number of GCs to run on the generations before raising objects to the
328 int number_of_gcs_before_promotion
;
330 /* the cumulative sum of the bytes allocated to this generation. It is
331 * cleared after a GC on this generations, and update before new
332 * objects are added from a GC of a younger generation. Dividing by
333 * the bytes_allocated will give the average age of the memory in
334 * this generation since its last GC. */
335 os_vm_size_t cum_sum_bytes_allocated
;
337 /* a minimum average memory age before a GC will occur helps
338 * prevent a GC when a large number of new live objects have been
339 * added, in which case a GC could be a waste of time */
340 double minimum_age_before_gc
;
343 /* an array of generation structures. There needs to be one more
344 * generation structure than actual generations as the oldest
345 * generation is temporarily raised then lowered. */
346 struct generation generations
[NUM_GENERATIONS
];
348 /* the oldest generation that is will currently be GCed by default.
349 * Valid values are: 0, 1, ... HIGHEST_NORMAL_GENERATION
351 * The default of HIGHEST_NORMAL_GENERATION enables GC on all generations.
353 * Setting this to 0 effectively disables the generational nature of
354 * the GC. In some applications generational GC may not be useful
355 * because there are no long-lived objects.
357 * An intermediate value could be handy after moving long-lived data
358 * into an older generation so an unnecessary GC of this long-lived
359 * data can be avoided. */
360 generation_index_t gencgc_oldest_gen_to_gc
= HIGHEST_NORMAL_GENERATION
;
362 /* META: Is nobody aside from me bothered by this especially misleading
363 * use of the word "last"? It could mean either "ultimate" or "prior",
364 * but in fact means neither. It is the *FIRST* page that should be grabbed
365 * for more space, so it is min free page, or 1+ the max used page. */
366 /* The maximum free page in the heap is maintained and used to update
367 * ALLOCATION_POINTER which is used by the room function to limit its
368 * search of the heap. XX Gencgc obviously needs to be better
369 * integrated with the Lisp code. */
371 page_index_t last_free_page
;
373 #ifdef LISP_FEATURE_SB_THREAD
374 /* This lock is to prevent multiple threads from simultaneously
375 * allocating new regions which overlap each other. Note that the
376 * majority of GC is single-threaded, but alloc() may be called from
377 * >1 thread at a time and must be thread-safe. This lock must be
378 * seized before all accesses to generations[] or to parts of
379 * page_table[] that other threads may want to see */
380 static pthread_mutex_t free_pages_lock
= PTHREAD_MUTEX_INITIALIZER
;
381 /* This lock is used to protect non-thread-local allocation. */
382 static pthread_mutex_t allocation_lock
= PTHREAD_MUTEX_INITIALIZER
;
385 extern os_vm_size_t gencgc_release_granularity
;
386 os_vm_size_t gencgc_release_granularity
= GENCGC_RELEASE_GRANULARITY
;
388 extern os_vm_size_t gencgc_alloc_granularity
;
389 os_vm_size_t gencgc_alloc_granularity
= GENCGC_ALLOC_GRANULARITY
;
393 * miscellaneous heap functions
396 /* Count the number of pages which are write-protected within the
397 * given generation. */
399 count_write_protect_generation_pages(generation_index_t generation
)
401 page_index_t i
, count
= 0;
403 for (i
= 0; i
< last_free_page
; i
++)
405 && (page_table
[i
].gen
== generation
)
406 && page_table
[i
].write_protected
)
411 /* Count the number of pages within the given generation. */
413 count_generation_pages(generation_index_t generation
)
416 page_index_t count
= 0;
418 for (i
= 0; i
< last_free_page
; i
++)
419 if (!page_free_p(i
) && page_table
[i
].gen
== generation
)
426 count_dont_move_pages(void)
429 page_index_t count
= 0;
430 for (i
= 0; i
< last_free_page
; i
++) {
431 if (!page_free_p(i
) && page_table
[i
].dont_move
) {
439 /* Work through the pages and add up the number of bytes used for the
440 * given generation. */
441 static __attribute__((unused
)) os_vm_size_t
442 count_generation_bytes_allocated (generation_index_t gen
)
445 os_vm_size_t result
= 0;
446 for (i
= 0; i
< last_free_page
; i
++) {
447 if (!page_free_p(i
) && page_table
[i
].gen
== gen
)
448 result
+= page_bytes_used(i
);
453 /* Return the average age of the memory in a generation. */
455 generation_average_age(generation_index_t gen
)
457 if (generations
[gen
].bytes_allocated
== 0)
461 ((double)generations
[gen
].cum_sum_bytes_allocated
)
462 / ((double)generations
[gen
].bytes_allocated
);
465 #ifdef LISP_FEATURE_X86
466 extern void fpu_save(void *);
467 extern void fpu_restore(void *);
470 #define PAGE_INDEX_FMT PRIdPTR
473 write_generation_stats(FILE *file
)
475 generation_index_t i
;
477 #ifdef LISP_FEATURE_X86
480 /* Can end up here after calling alloc_tramp which doesn't prepare
481 * the x87 state, and the C ABI uses a different mode */
485 /* Print the heap stats. */
487 " Gen StaPg UbSta LaSta Boxed Unbox LB LUB !move Alloc Waste Trig WP GCs Mem-age\n");
489 for (i
= 0; i
<= SCRATCH_GENERATION
; i
++) {
491 page_index_t boxed_cnt
= 0;
492 page_index_t unboxed_cnt
= 0;
493 page_index_t large_boxed_cnt
= 0;
494 page_index_t large_unboxed_cnt
= 0;
495 page_index_t pinned_cnt
=0;
497 for (j
= 0; j
< last_free_page
; j
++)
498 if (page_table
[j
].gen
== i
) {
500 /* Count the number of boxed pages within the given
502 if (page_boxed_p(j
)) {
503 if (page_table
[j
].large_object
)
508 if(page_table
[j
].dont_move
) pinned_cnt
++;
509 /* Count the number of unboxed pages within the given
511 if (page_unboxed_p(j
)) {
512 if (page_table
[j
].large_object
)
519 gc_assert(generations
[i
].bytes_allocated
520 == count_generation_bytes_allocated(i
));
522 " %1d: %5ld %5ld %5ld",
524 (long)generations
[i
].alloc_start_page
,
525 (long)generations
[i
].alloc_unboxed_start_page
,
526 (long)generations
[i
].alloc_large_start_page
);
528 " %5"PAGE_INDEX_FMT
" %5"PAGE_INDEX_FMT
" %5"PAGE_INDEX_FMT
529 " %5"PAGE_INDEX_FMT
" %5"PAGE_INDEX_FMT
,
530 boxed_cnt
, unboxed_cnt
, large_boxed_cnt
,
531 large_unboxed_cnt
, pinned_cnt
);
536 " %4"PAGE_INDEX_FMT
" %3d %7.4f\n",
537 generations
[i
].bytes_allocated
,
538 (npage_bytes(count_generation_pages(i
)) - generations
[i
].bytes_allocated
),
539 generations
[i
].gc_trigger
,
540 count_write_protect_generation_pages(i
),
541 generations
[i
].num_gc
,
542 generation_average_age(i
));
544 fprintf(file
," Total bytes allocated = %"OS_VM_SIZE_FMT
"\n", bytes_allocated
);
545 fprintf(file
," Dynamic-space-size bytes = %"OS_VM_SIZE_FMT
"\n", dynamic_space_size
);
547 #ifdef LISP_FEATURE_X86
548 fpu_restore(fpu_state
);
553 write_heap_exhaustion_report(FILE *file
, long available
, long requested
,
554 struct thread
*thread
)
557 "Heap exhausted during %s: %ld bytes available, %ld requested.\n",
558 gc_active_p
? "garbage collection" : "allocation",
561 write_generation_stats(file
);
562 fprintf(file
, "GC control variables:\n");
563 fprintf(file
, " *GC-INHIBIT* = %s\n *GC-PENDING* = %s\n",
564 read_TLS(GC_INHIBIT
,thread
)==NIL
? "false" : "true",
565 (read_TLS(GC_PENDING
, thread
) == T
) ?
566 "true" : ((read_TLS(GC_PENDING
, thread
) == NIL
) ?
567 "false" : "in progress"));
568 #ifdef LISP_FEATURE_SB_THREAD
569 fprintf(file
, " *STOP-FOR-GC-PENDING* = %s\n",
570 read_TLS(STOP_FOR_GC_PENDING
,thread
)==NIL
? "false" : "true");
575 print_generation_stats(void)
577 write_generation_stats(stderr
);
580 extern char* gc_logfile
;
581 char * gc_logfile
= NULL
;
584 log_generation_stats(char *logfile
, char *header
)
587 FILE * log
= fopen(logfile
, "a");
589 fprintf(log
, "%s\n", header
);
590 write_generation_stats(log
);
593 fprintf(stderr
, "Could not open gc logfile: %s\n", logfile
);
600 report_heap_exhaustion(long available
, long requested
, struct thread
*th
)
603 FILE * log
= fopen(gc_logfile
, "a");
605 write_heap_exhaustion_report(log
, available
, requested
, th
);
608 fprintf(stderr
, "Could not open gc logfile: %s\n", gc_logfile
);
612 /* Always to stderr as well. */
613 write_heap_exhaustion_report(stderr
, available
, requested
, th
);
617 #if defined(LISP_FEATURE_X86)
618 void fast_bzero(void*, size_t); /* in <arch>-assem.S */
621 /* Zero the pages from START to END (inclusive), but use mmap/munmap instead
622 * if zeroing it ourselves, i.e. in practice give the memory back to the
623 * OS. Generally done after a large GC.
625 void zero_pages_with_mmap(page_index_t start
, page_index_t end
) {
627 void *addr
= page_address(start
), *new_addr
;
628 os_vm_size_t length
= npage_bytes(1+end
-start
);
633 gc_assert(length
>= gencgc_release_granularity
);
634 gc_assert((length
% gencgc_release_granularity
) == 0);
636 #ifdef LISP_FEATURE_LINUX
637 // We use MADV_DONTNEED only on Linux due to differing semantics from BSD.
638 // Linux treats it as a demand that the memory be 0-filled, or refreshed
639 // from a file that backs the range. BSD takes it as a hint that you don't
640 // care if the memory has to brought in from swap when next accessed,
641 // i.e. it's not a request to make a user-visible alteration to memory.
642 // So in theory this can bring a page in from the core file, if we happen
643 // to hit a page that resides in the portion of memory mapped by coreparse.
644 // In practice this should not happen because objects from a core file can't
645 // become garbage. Except in save-lisp-and-die they can, and we must be
646 // cautious not to resurrect bytes that originally came from the file.
647 if ((os_vm_address_t
)addr
>= anon_dynamic_space_start
) {
648 if (madvise(addr
, length
, MADV_DONTNEED
) != 0)
649 lose("madvise failed\n");
653 os_invalidate(addr
, length
);
654 new_addr
= os_validate(NOT_MOVABLE
, addr
, length
);
655 if (new_addr
== NULL
|| new_addr
!= addr
) {
656 lose("remap_free_pages: page moved, 0x%08x ==> 0x%08x",
661 for (i
= start
; i
<= end
; i
++)
662 set_page_need_to_zero(i
, 0);
665 /* Zero the pages from START to END (inclusive). Generally done just after
666 * a new region has been allocated.
669 zero_pages(page_index_t start
, page_index_t end
) {
673 #if defined(LISP_FEATURE_X86)
674 fast_bzero(page_address(start
), npage_bytes(1+end
-start
));
676 bzero(page_address(start
), npage_bytes(1+end
-start
));
682 zero_and_mark_pages(page_index_t start
, page_index_t end
) {
685 zero_pages(start
, end
);
686 for (i
= start
; i
<= end
; i
++)
687 set_page_need_to_zero(i
, 0);
690 /* Zero the pages from START to END (inclusive), except for those
691 * pages that are known to already zeroed. Mark all pages in the
692 * ranges as non-zeroed.
695 zero_dirty_pages(page_index_t start
, page_index_t end
) {
698 #ifdef READ_PROTECT_FREE_PAGES
699 os_protect(page_address(start
), npage_bytes(1+end
-start
), OS_VM_PROT_ALL
);
701 for (i
= start
; i
<= end
; i
++) {
702 if (!page_need_to_zero(i
)) continue;
703 for (j
= i
+1; (j
<= end
) && page_need_to_zero(j
) ; j
++)
709 for (i
= start
; i
<= end
; i
++) {
710 set_page_need_to_zero(i
, 1);
716 * To support quick and inline allocation, regions of memory can be
717 * allocated and then allocated from with just a free pointer and a
718 * check against an end address.
720 * Since objects can be allocated to spaces with different properties
721 * e.g. boxed/unboxed, generation, ages; there may need to be many
722 * allocation regions.
724 * Each allocation region may start within a partly used page. Many
725 * features of memory use are noted on a page wise basis, e.g. the
726 * generation; so if a region starts within an existing allocated page
727 * it must be consistent with this page.
729 * During the scavenging of the newspace, objects will be transported
730 * into an allocation region, and pointers updated to point to this
731 * allocation region. It is possible that these pointers will be
732 * scavenged again before the allocation region is closed, e.g. due to
733 * trans_list which jumps all over the place to cleanup the list. It
734 * is important to be able to determine properties of all objects
735 * pointed to when scavenging, e.g to detect pointers to the oldspace.
736 * Thus it's important that the allocation regions have the correct
737 * properties set when allocated, and not just set when closed. The
738 * region allocation routines return regions with the specified
739 * properties, and grab all the pages, setting their properties
740 * appropriately, except that the amount used is not known.
742 * These regions are used to support quicker allocation using just a
743 * free pointer. The actual space used by the region is not reflected
744 * in the pages tables until it is closed. It can't be scavenged until
747 * When finished with the region it should be closed, which will
748 * update the page tables for the actual space used returning unused
749 * space. Further it may be noted in the new regions which is
750 * necessary when scavenging the newspace.
752 * Large objects may be allocated directly without an allocation
753 * region, the page tables are updated immediately.
755 * Unboxed objects don't contain pointers to other objects and so
756 * don't need scavenging. Further they can't contain pointers to
757 * younger generations so WP is not needed. By allocating pages to
758 * unboxed objects the whole page never needs scavenging or
759 * write-protecting. */
761 /* We use either two or three regions for the current newspace generation. */
763 struct alloc_region gc_alloc_region
[3];
764 #define boxed_region gc_alloc_region[BOXED_PAGE_FLAG-1]
765 #define unboxed_region gc_alloc_region[UNBOXED_PAGE_FLAG-1]
766 #define code_region gc_alloc_region[CODE_PAGE_FLAG-1]
768 struct alloc_region boxed_region
;
769 struct alloc_region unboxed_region
;
772 /* The generation currently being allocated to. */
773 static generation_index_t gc_alloc_generation
;
775 static inline page_index_t
776 generation_alloc_start_page(generation_index_t generation
, int page_type_flag
, int large
)
778 if (!(page_type_flag
>= 1 && page_type_flag
<= 3))
779 lose("bad page_type_flag: %d", page_type_flag
);
781 return generations
[generation
].alloc_large_start_page
;
783 return generations
[generation
].alloc_start_page_
[page_type_flag
];
785 if (UNBOXED_PAGE_FLAG
== page_type_flag
)
786 return generations
[generation
].alloc_unboxed_start_page
;
787 /* Both code and data. */
788 return generations
[generation
].alloc_start_page
;
793 set_generation_alloc_start_page(generation_index_t generation
, int page_type_flag
, int large
,
796 if (!(page_type_flag
>= 1 && page_type_flag
<= 3))
797 lose("bad page_type_flag: %d", page_type_flag
);
799 generations
[generation
].alloc_large_start_page
= page
;
802 generations
[generation
].alloc_start_page_
[page_type_flag
] = page
;
804 else if (UNBOXED_PAGE_FLAG
== page_type_flag
)
805 generations
[generation
].alloc_unboxed_start_page
= page
;
806 else /* Both code and data. */
807 generations
[generation
].alloc_start_page
= page
;
811 /* Find a new region with room for at least the given number of bytes.
813 * It starts looking at the current generation's alloc_start_page. So
814 * may pick up from the previous region if there is enough space. This
815 * keeps the allocation contiguous when scavenging the newspace.
817 * The alloc_region should have been closed by a call to
818 * gc_alloc_update_page_tables(), and will thus be in an empty state.
820 * To assist the scavenging functions write-protected pages are not
821 * used. Free pages should not be write-protected.
823 * It is critical to the conservative GC that the start of regions be
824 * known. To help achieve this only small regions are allocated at a
827 * During scavenging, pointers may be found to within the current
828 * region and the page generation must be set so that pointers to the
829 * from space can be recognized. Therefore the generation of pages in
830 * the region are set to gc_alloc_generation. To prevent another
831 * allocation call using the same pages, all the pages in the region
832 * are allocated, although they will initially be empty.
835 gc_alloc_new_region(sword_t nbytes
, int page_type_flag
, struct alloc_region
*alloc_region
)
837 page_index_t first_page
;
838 page_index_t last_page
;
844 "/alloc_new_region for %d bytes from gen %d\n",
845 nbytes, gc_alloc_generation));
848 /* Check that the region is in a reset state. */
849 gc_assert((alloc_region
->first_page
== 0)
850 && (alloc_region
->last_page
== -1)
851 && (alloc_region
->free_pointer
== alloc_region
->end_addr
));
852 ret
= thread_mutex_lock(&free_pages_lock
);
854 first_page
= generation_alloc_start_page(gc_alloc_generation
, page_type_flag
, 0);
855 last_page
=gc_find_freeish_pages(&first_page
, nbytes
, page_type_flag
);
857 /* Set up the alloc_region. */
858 alloc_region
->first_page
= first_page
;
859 alloc_region
->last_page
= last_page
;
860 alloc_region
->start_addr
= page_address(first_page
) + page_bytes_used(first_page
);
861 alloc_region
->free_pointer
= alloc_region
->start_addr
;
862 alloc_region
->end_addr
= page_address(last_page
+1);
864 /* Set up the pages. */
866 /* The first page may have already been in use. */
867 /* If so, just assert that it's consistent, otherwise, set it up. */
868 if (page_bytes_used(first_page
)) {
869 gc_assert(page_table
[first_page
].allocated
== page_type_flag
);
870 gc_assert(page_table
[first_page
].gen
== gc_alloc_generation
);
871 gc_dcheck(page_table
[first_page
].large_object
== 0);
873 page_table
[first_page
].allocated
= page_type_flag
;
874 page_table
[first_page
].gen
= gc_alloc_generation
;
876 page_table
[first_page
].allocated
|= OPEN_REGION_PAGE_FLAG
;
878 for (i
= first_page
+1; i
<= last_page
; i
++) {
879 page_table
[i
].allocated
= page_type_flag
;
880 page_table
[i
].gen
= gc_alloc_generation
;
881 set_page_scan_start_offset(i
,
882 addr_diff(page_address(i
), alloc_region
->start_addr
));
883 page_table
[i
].allocated
|= OPEN_REGION_PAGE_FLAG
;
885 /* Bump up last_free_page. */
886 if (last_page
+1 > last_free_page
) {
887 last_free_page
= last_page
+1;
888 /* do we only want to call this on special occasions? like for
890 set_alloc_pointer((lispobj
)page_address(last_free_page
));
892 ret
= thread_mutex_unlock(&free_pages_lock
);
895 /* If the first page was only partial, don't check whether it's
896 * zeroed (it won't be) and don't zero it (since the parts that
897 * we're interested in are guaranteed to be zeroed).
899 if (page_bytes_used(first_page
)) {
903 zero_dirty_pages(first_page
, last_page
);
905 /* we can do this after releasing free_pages_lock */
906 if (gencgc_zero_check
) {
908 for (p
= alloc_region
->start_addr
;
909 (void*)p
< alloc_region
->end_addr
; p
++) {
911 lose("The new region is not zero at %p (start=%p, end=%p).\n",
912 p
, alloc_region
->start_addr
, alloc_region
->end_addr
);
918 /* If the record_new_objects flag is 2 then all new regions created
921 * If it's 1 then then it is only recorded if the first page of the
922 * current region is <= new_areas_ignore_page. This helps avoid
923 * unnecessary recording when doing full scavenge pass.
925 * The new_object structure holds the page, byte offset, and size of
926 * new regions of objects. Each new area is placed in the array of
927 * these structures pointer to by new_areas. new_areas_index holds the
928 * offset into new_areas.
930 * If new_area overflows NUM_NEW_AREAS then it stops adding them. The
931 * later code must detect this and handle it, probably by doing a full
932 * scavenge of a generation. */
933 #define NUM_NEW_AREAS 512
934 static int record_new_objects
= 0;
935 static page_index_t new_areas_ignore_page
;
941 static struct new_area (*new_areas
)[];
942 static size_t new_areas_index
;
943 size_t max_new_areas
;
945 /* Add a new area to new_areas. */
947 add_new_area(page_index_t first_page
, size_t offset
, size_t size
)
949 size_t new_area_start
, c
;
952 /* Ignore if full. */
953 if (new_areas_index
>= NUM_NEW_AREAS
)
956 switch (record_new_objects
) {
960 if (first_page
> new_areas_ignore_page
)
969 new_area_start
= npage_bytes(first_page
) + offset
;
971 /* Search backwards for a prior area that this follows from. If
972 found this will save adding a new area. */
973 for (i
= new_areas_index
-1, c
= 0; (i
>= 0) && (c
< 8); i
--, c
++) {
975 npage_bytes((*new_areas
)[i
].page
)
976 + (*new_areas
)[i
].offset
977 + (*new_areas
)[i
].size
;
979 "/add_new_area S1 %d %d %d %d\n",
980 i, c, new_area_start, area_end));*/
981 if (new_area_start
== area_end
) {
983 "/adding to [%d] %d %d %d with %d %d %d:\n",
985 (*new_areas)[i].page,
986 (*new_areas)[i].offset,
987 (*new_areas)[i].size,
991 (*new_areas
)[i
].size
+= size
;
996 (*new_areas
)[new_areas_index
].page
= first_page
;
997 (*new_areas
)[new_areas_index
].offset
= offset
;
998 (*new_areas
)[new_areas_index
].size
= size
;
1000 "/new_area %d page %d offset %d size %d\n",
1001 new_areas_index, first_page, offset, size));*/
1004 /* Note the max new_areas used. */
1005 if (new_areas_index
> max_new_areas
)
1006 max_new_areas
= new_areas_index
;
1009 /* Update the tables for the alloc_region. The region may be added to
1012 * When done the alloc_region is set up so that the next quick alloc
1013 * will fail safely and thus a new region will be allocated. Further
1014 * it is safe to try to re-update the page table of this reset
1017 gc_alloc_update_page_tables(int page_type_flag
, struct alloc_region
*alloc_region
)
1019 /* Catch an unused alloc_region. */
1020 if (alloc_region
->last_page
== -1)
1023 page_index_t first_page
= alloc_region
->first_page
;
1024 page_index_t next_page
= first_page
+1;
1025 char *page_base
= page_address(first_page
);
1026 char *free_pointer
= alloc_region
->free_pointer
;
1028 // page_bytes_used() can be done without holding a lock. Nothing else
1029 // affects the usage on the first page of a region owned by this thread.
1030 page_bytes_t orig_first_page_bytes_used
= page_bytes_used(first_page
);
1031 gc_assert(alloc_region
->start_addr
== page_base
+ orig_first_page_bytes_used
);
1033 int ret
= thread_mutex_lock(&free_pages_lock
);
1034 gc_assert(ret
== 0);
1036 // Mark the region as closed on its first page.
1037 page_table
[first_page
].allocated
&= ~(OPEN_REGION_PAGE_FLAG
);
1039 if (free_pointer
!= alloc_region
->start_addr
) {
1040 /* some bytes were allocated in the region */
1042 /* All the pages used need to be updated */
1044 /* Update the first page. */
1045 if (!orig_first_page_bytes_used
)
1046 gc_assert(page_starts_contiguous_block_p(first_page
));
1047 page_table
[first_page
].allocated
&= ~(OPEN_REGION_PAGE_FLAG
);
1050 gc_assert(page_table
[first_page
].allocated
== page_type_flag
);
1052 gc_assert(page_table
[first_page
].allocated
& page_type_flag
);
1054 gc_assert(page_table
[first_page
].gen
== gc_alloc_generation
);
1055 gc_assert(page_table
[first_page
].large_object
== 0);
1057 /* Calculate the number of bytes used in this page. This is not
1058 * always the number of new bytes, unless it was free. */
1059 os_vm_size_t bytes_used
= addr_diff(free_pointer
, page_base
);
1061 if ((more
= (bytes_used
> GENCGC_CARD_BYTES
)))
1062 bytes_used
= GENCGC_CARD_BYTES
;
1063 set_page_bytes_used(first_page
, bytes_used
);
1065 /* 'region_size' will be the sum of new bytes consumed by the region,
1066 * EXCLUDING any part of the first page already in use,
1067 * and any unused part of the final used page */
1068 os_vm_size_t region_size
= bytes_used
- orig_first_page_bytes_used
;
1070 /* All the rest of the pages should be accounted for. */
1072 page_table
[next_page
].allocated
&= ~(OPEN_REGION_PAGE_FLAG
);
1074 gc_assert(page_table
[next_page
].allocated
== page_type_flag
);
1076 gc_assert(page_table
[next_page
].allocated
& page_type_flag
);
1078 gc_assert(page_bytes_used(next_page
) == 0);
1079 gc_assert(page_table
[next_page
].gen
== gc_alloc_generation
);
1080 gc_assert(page_table
[next_page
].large_object
== 0);
1081 page_base
+= GENCGC_CARD_BYTES
;
1082 gc_assert(page_scan_start_offset(next_page
) ==
1083 addr_diff(page_base
, alloc_region
->start_addr
));
1085 /* Calculate the number of bytes used in this page. */
1086 bytes_used
= addr_diff(free_pointer
, page_base
);
1087 if ((more
= (bytes_used
> GENCGC_CARD_BYTES
)))
1088 bytes_used
= GENCGC_CARD_BYTES
;
1089 set_page_bytes_used(next_page
, bytes_used
);
1090 region_size
+= bytes_used
;
1095 // Now 'next_page' is 1 page beyond those fully accounted for.
1096 gc_assert(addr_diff(free_pointer
, alloc_region
->start_addr
) == region_size
);
1097 // Update the global totals
1098 bytes_allocated
+= region_size
;
1099 generations
[gc_alloc_generation
].bytes_allocated
+= region_size
;
1101 /* Set the generations alloc restart page to the last page of
1103 set_generation_alloc_start_page(gc_alloc_generation
, page_type_flag
, 0, next_page
-1);
1105 /* Add the region to the new_areas if requested. */
1106 if (BOXED_PAGE_FLAG
& page_type_flag
)
1107 add_new_area(first_page
,orig_first_page_bytes_used
, region_size
);
1109 } else if (!orig_first_page_bytes_used
) {
1110 /* The first page is completely unused. Unallocate it */
1111 reset_page_flags(first_page
);
1114 /* Unallocate any unused pages. */
1115 while (next_page
<= alloc_region
->last_page
) {
1116 gc_assert(page_bytes_used(next_page
) == 0);
1117 reset_page_flags(next_page
);
1120 ret
= thread_mutex_unlock(&free_pages_lock
);
1121 gc_assert(ret
== 0);
1123 /* alloc_region is per-thread, we're ok to do this unlocked */
1124 gc_set_region_empty(alloc_region
);
1127 /* Allocate a possibly large object. */
1129 gc_alloc_large(sword_t nbytes
, int page_type_flag
, struct alloc_region
*alloc_region
)
1132 page_index_t first_page
, next_page
, last_page
;
1133 os_vm_size_t byte_cnt
;
1134 os_vm_size_t bytes_used
;
1137 ret
= thread_mutex_lock(&free_pages_lock
);
1138 gc_assert(ret
== 0);
1140 first_page
= generation_alloc_start_page(gc_alloc_generation
, page_type_flag
, 1);
1141 // FIXME: really we want to try looking for space following the highest of
1142 // the last page of all other small object regions. That's impossible - there's
1143 // not enough information. At best we can skip some work in only the case where
1144 // the supplied region was the one most recently created. To do this right
1145 // would entail a malloc-like allocator at the page granularity.
1146 if (first_page
<= alloc_region
->last_page
) {
1147 first_page
= alloc_region
->last_page
+1;
1150 last_page
=gc_find_freeish_pages(&first_page
,nbytes
, page_type_flag
);
1152 gc_assert(first_page
> alloc_region
->last_page
);
1154 set_generation_alloc_start_page(gc_alloc_generation
, page_type_flag
, 1, last_page
);
1156 /* Large objects don't share pages with other objects. */
1157 gc_assert(page_bytes_used(first_page
) == 0);
1159 /* Set up the pages. */
1160 page_table
[first_page
].allocated
= page_type_flag
;
1161 page_table
[first_page
].gen
= gc_alloc_generation
;
1162 page_table
[first_page
].large_object
= 1;
1166 /* Calc. the number of bytes used in this page. This is not
1167 * always the number of new bytes, unless it was free. */
1169 if ((bytes_used
= nbytes
) > GENCGC_CARD_BYTES
) {
1170 bytes_used
= GENCGC_CARD_BYTES
;
1173 set_page_bytes_used(first_page
, bytes_used
);
1174 byte_cnt
+= bytes_used
;
1176 next_page
= first_page
+1;
1178 /* All the rest of the pages should be free. We need to set their
1179 * scan_start_offset pointer to the start of the region, and set
1180 * the bytes_used. */
1182 gc_assert(page_free_p(next_page
));
1183 gc_assert(page_bytes_used(next_page
) == 0);
1184 page_table
[next_page
].allocated
= page_type_flag
;
1185 page_table
[next_page
].gen
= gc_alloc_generation
;
1186 page_table
[next_page
].large_object
= 1;
1188 set_page_scan_start_offset(next_page
, npage_bytes(next_page
-first_page
));
1190 /* Calculate the number of bytes used in this page. */
1192 bytes_used
= nbytes
- byte_cnt
;
1193 if (bytes_used
> GENCGC_CARD_BYTES
) {
1194 bytes_used
= GENCGC_CARD_BYTES
;
1197 set_page_bytes_used(next_page
, bytes_used
);
1198 byte_cnt
+= bytes_used
;
1202 gc_assert(byte_cnt
== (size_t)nbytes
);
1204 bytes_allocated
+= nbytes
;
1205 generations
[gc_alloc_generation
].bytes_allocated
+= nbytes
;
1207 /* Add the region to the new_areas if requested. */
1208 if (BOXED_PAGE_FLAG
& page_type_flag
)
1209 add_new_area(first_page
, 0, nbytes
);
1211 /* Bump up last_free_page */
1212 if (last_page
+1 > last_free_page
) {
1213 last_free_page
= last_page
+1;
1214 set_alloc_pointer((lispobj
)(page_address(last_free_page
)));
1216 ret
= thread_mutex_unlock(&free_pages_lock
);
1217 gc_assert(ret
== 0);
1219 zero_dirty_pages(first_page
, last_page
);
1221 return page_address(first_page
);
1224 static page_index_t gencgc_alloc_start_page
= -1;
1227 gc_heap_exhausted_error_or_lose (sword_t available
, sword_t requested
)
1229 struct thread
*thread
= arch_os_get_current_thread();
1230 /* Write basic information before doing anything else: if we don't
1231 * call to lisp this is a must, and even if we do there is always
1232 * the danger that we bounce back here before the error has been
1233 * handled, or indeed even printed.
1235 report_heap_exhaustion(available
, requested
, thread
);
1236 if (gc_active_p
|| (available
== 0)) {
1237 /* If we are in GC, or totally out of memory there is no way
1238 * to sanely transfer control to the lisp-side of things.
1240 lose("Heap exhausted, game over.");
1243 /* FIXME: assert free_pages_lock held */
1244 (void)thread_mutex_unlock(&free_pages_lock
);
1245 #if !(defined(LISP_FEATURE_WIN32) && defined(LISP_FEATURE_SB_THREAD))
1246 gc_assert(get_pseudo_atomic_atomic(thread
));
1247 clear_pseudo_atomic_atomic(thread
);
1248 if (get_pseudo_atomic_interrupted(thread
))
1249 do_pending_interrupt();
1251 /* Another issue is that signalling HEAP-EXHAUSTED error leads
1252 * to running user code at arbitrary places, even in a
1253 * WITHOUT-INTERRUPTS which may lead to a deadlock without
1254 * running out of the heap. So at this point all bets are
1256 if (read_TLS(INTERRUPTS_ENABLED
,thread
) == NIL
)
1257 corruption_warning_and_maybe_lose
1258 ("Signalling HEAP-EXHAUSTED in a WITHOUT-INTERRUPTS.");
1259 /* available and requested should be double word aligned, thus
1260 they can passed as fixnums and shifted later. */
1261 funcall2(StaticSymbolFunction(HEAP_EXHAUSTED_ERROR
), available
, requested
);
1262 lose("HEAP-EXHAUSTED-ERROR fell through");
1266 /* Test whether page 'index' can continue a non-large-object region
1267 * having specified 'gen' and 'allocated' values. */
1268 static inline boolean
1269 page_extensible_p(page_index_t index
, generation_index_t gen
, int allocated
) {
1270 #ifdef LISP_FEATURE_BIG_ENDIAN /* TODO: implement the simpler test */
1271 /* Counterintuitively, gcc prefers to see sequential tests of the bitfields,
1272 * versus one test "!(p.large_object | p.write_protected | p.dont_move)".
1273 * When expressed as separate tests, it figures out that this can be optimized
1274 * as an AND. On the other hand, by attempting to *force* it to do that,
1275 * it shifts each field to the right to line them all up at bit index 0 to
1276 * test that 1 bit, which is a literal rendering of the user-written code.
1279 page_table
[index
].allocated
== allocated
1280 && page_table
[index
].gen
== gen
1281 && !page_table
[index
].large_object
1282 && !page_table
[index
].write_protected
1283 && !page_table
[index
].dont_move
;
1286 /* Test all 5 conditions above as a single comparison against a mask.
1287 * (The C compiler doesn't understand how to do that)
1288 * Any bit that has a 1 in this mask must match the desired input.
1289 * The two 0 bits are for "has_pins" and "write_protected_cleared".
1290 * has_pins is irrelevant- it won't be 1 except during gc.
1291 * wp_cleared is probably 0, but needs to be masked out to be sure.
1292 * All other flag bits must be zero to pass the test.
1296 * #b11111111_10101111
1298 * !move / \ allocated
1300 * The flags reside at 1 byte prior to 'gen' in the page structure.
1302 return (*(int16_t*)(&page_table
[index
].gen
-1) & 0xFFAF) == ((gen
<<8)|allocated
);
1306 /* Search for at least nbytes of space, possibly picking up any
1307 * remaining space on the tail of a page that was not fully used.
1309 * Non-small allocations are guaranteed to be page-aligned.
1312 gc_find_freeish_pages(page_index_t
*restart_page_ptr
, sword_t bytes
,
1315 page_index_t most_bytes_found_from
= 0, most_bytes_found_to
= 0;
1316 page_index_t first_page
, last_page
, restart_page
= *restart_page_ptr
;
1317 os_vm_size_t nbytes
= bytes
;
1318 os_vm_size_t nbytes_goal
= nbytes
;
1319 os_vm_size_t bytes_found
= 0;
1320 os_vm_size_t most_bytes_found
= 0;
1321 /* Note that this definition of "small" is not the complement
1322 * of "large" as used in gc_alloc_large(). That's fine.
1323 * The constraint we must respect is that a large object
1324 * MUST NOT share any of its pages with another object.
1325 * It should also be page-aligned, though that's not a restriction
1326 * per se, but a fairly obvious consequence of not sharing.
1328 boolean small_object
= nbytes
< GENCGC_CARD_BYTES
;
1329 /* FIXME: assert(free_pages_lock is held); */
1331 if (nbytes_goal
< gencgc_alloc_granularity
)
1332 nbytes_goal
= gencgc_alloc_granularity
;
1333 #if !defined(LISP_FEATURE_64_BIT) && SEGREGATED_CODE
1334 // Increase the region size to avoid excessive fragmentation
1335 if (page_type_flag
== CODE_PAGE_FLAG
&& nbytes_goal
< 65536)
1336 nbytes_goal
= 65536;
1339 /* Toggled by gc_and_save for heap compaction, normally -1. */
1340 if (gencgc_alloc_start_page
!= -1) {
1341 restart_page
= gencgc_alloc_start_page
;
1344 /* FIXME: This is on bytes instead of nbytes pending cleanup of
1345 * long from the interface. */
1346 gc_assert(bytes
>=0);
1347 first_page
= restart_page
;
1348 while (first_page
< page_table_pages
) {
1350 if (page_free_p(first_page
)) {
1351 gc_dcheck(!page_bytes_used(first_page
));
1352 bytes_found
= GENCGC_CARD_BYTES
;
1353 } else if (small_object
&&
1354 page_extensible_p(first_page
, gc_alloc_generation
, page_type_flag
)) {
1355 bytes_found
= GENCGC_CARD_BYTES
- page_bytes_used(first_page
);
1361 gc_dcheck(!page_table
[first_page
].write_protected
);
1362 /* page_free_p() can legally be used at index 'page_table_pages'
1363 * because the array dimension is 1+page_table_pages */
1364 for (last_page
= first_page
+1;
1365 bytes_found
< nbytes_goal
&&
1366 page_free_p(last_page
) && last_page
< page_table_pages
;
1368 /* page_free_p() implies 0 bytes used, thus GENCGC_CARD_BYTES available.
1369 * It also implies !write_protected, and if the OS's conception were
1370 * otherwise, lossage would routinely occur in the fault handler) */
1371 bytes_found
+= GENCGC_CARD_BYTES
;
1372 gc_dcheck(0 == page_bytes_used(last_page
));
1373 gc_dcheck(!page_table
[last_page
].write_protected
);
1376 if (bytes_found
> most_bytes_found
) {
1377 most_bytes_found
= bytes_found
;
1378 most_bytes_found_from
= first_page
;
1379 most_bytes_found_to
= last_page
;
1381 if (bytes_found
>= nbytes_goal
)
1384 first_page
= last_page
;
1387 bytes_found
= most_bytes_found
;
1388 restart_page
= first_page
+ 1;
1390 /* Check for a failure */
1391 if (bytes_found
< nbytes
) {
1392 gc_assert(restart_page
>= page_table_pages
);
1393 gc_heap_exhausted_error_or_lose(most_bytes_found
, nbytes
);
1396 gc_assert(most_bytes_found_to
);
1397 *restart_page_ptr
= most_bytes_found_from
;
1398 return most_bytes_found_to
-1;
1401 /* Allocate bytes. All the rest of the special-purpose allocation
1402 * functions will eventually call this */
1405 gc_alloc_with_region(sword_t nbytes
,int page_type_flag
, struct alloc_region
*my_region
,
1408 void *new_free_pointer
;
1410 if (nbytes
>=LARGE_OBJECT_SIZE
)
1411 return gc_alloc_large(nbytes
, page_type_flag
, my_region
);
1413 /* Check whether there is room in the current alloc region. */
1414 new_free_pointer
= (char*)my_region
->free_pointer
+ nbytes
;
1416 /* fprintf(stderr, "alloc %d bytes from %p to %p\n", nbytes,
1417 my_region->free_pointer, new_free_pointer); */
1419 if (new_free_pointer
<= my_region
->end_addr
) {
1420 /* If so then allocate from the current alloc region. */
1421 void *new_obj
= my_region
->free_pointer
;
1422 my_region
->free_pointer
= new_free_pointer
;
1424 /* Unless a `quick' alloc was requested, check whether the
1425 alloc region is almost empty. */
1427 addr_diff(my_region
->end_addr
,my_region
->free_pointer
) <= 32) {
1428 /* If so, finished with the current region. */
1429 gc_alloc_update_page_tables(page_type_flag
, my_region
);
1430 /* Set up a new region. */
1431 gc_alloc_new_region(32 /*bytes*/, page_type_flag
, my_region
);
1434 return((void *)new_obj
);
1437 /* Else not enough free space in the current region: retry with a
1440 gc_alloc_update_page_tables(page_type_flag
, my_region
);
1441 gc_alloc_new_region(nbytes
, page_type_flag
, my_region
);
1442 return gc_alloc_with_region(nbytes
, page_type_flag
, my_region
,0);
1445 /* Copy a large object. If the object is on a large object page then
1446 * it is simply promoted, else it is copied.
1448 * Bignums and vectors may have shrunk. If the object is not copied
1449 * the space needs to be reclaimed, and the page_tables corrected.
1451 * Code objects can't shrink, but it's not worth adding an extra test
1452 * for large code just to avoid the loop that performs adjustment, so
1453 * go through the adjustment motions even though nothing happens.
1455 * An object that is on non-large object pages will never move
1456 * to large object pages, thus ensuring that the assignment of
1457 * '.large_object = 0' in prepare_for_final_gc() is meaningful.
1458 * The saved core should have no large object pages.
1461 copy_large_object(lispobj object
, sword_t nwords
, int page_type_flag
)
1464 page_index_t first_page
;
1465 boolean boxedp
= page_type_flag
!= UNBOXED_PAGE_FLAG
;
1467 CHECK_COPY_PRECONDITIONS(object
, nwords
);
1469 if ((nwords
> 1024*1024) && gencgc_verbose
) {
1470 FSHOW((stderr
, "/general_copy_large_object: %d bytes\n",
1471 nwords
*N_WORD_BYTES
));
1474 /* Check whether it's a large object. */
1475 first_page
= find_page_index((void *)object
);
1476 gc_assert(first_page
>= 0);
1478 // An objects that shrank but was allocated on a large-object page
1479 // is a candidate for copying if its current size is non-large.
1480 if (page_table
[first_page
].large_object
1481 && nwords
>= LARGE_OBJECT_SIZE
/ N_WORD_BYTES
) {
1482 /* Promote the object. Note: Unboxed objects may have been
1483 * allocated to a BOXED region so it may be necessary to
1484 * change the region to UNBOXED. */
1485 os_vm_size_t remaining_bytes
;
1486 os_vm_size_t bytes_freed
;
1487 page_index_t next_page
;
1488 page_bytes_t old_bytes_used
;
1490 /* FIXME: This comment is somewhat stale.
1492 * Note: Any page write-protection must be removed, else a
1493 * later scavenge_newspace may incorrectly not scavenge these
1494 * pages. This would not be necessary if they are added to the
1495 * new areas, but let's do it for them all (they'll probably
1496 * be written anyway?). */
1498 gc_assert(page_starts_contiguous_block_p(first_page
));
1499 next_page
= first_page
;
1500 remaining_bytes
= nwords
*N_WORD_BYTES
;
1502 /* FIXME: can we share code with maybe_adjust_large_object ? */
1503 while (remaining_bytes
> GENCGC_CARD_BYTES
) {
1504 gc_assert(page_table
[next_page
].gen
== from_space
);
1505 gc_assert(page_table
[next_page
].large_object
);
1506 gc_assert(page_scan_start_offset(next_page
) ==
1507 npage_bytes(next_page
-first_page
));
1508 gc_assert(page_bytes_used(next_page
) == GENCGC_CARD_BYTES
);
1509 /* Should have been unprotected by unprotect_oldspace()
1510 * for boxed objects, and after promotion unboxed ones
1511 * should not be on protected pages at all. */
1512 gc_assert(!page_table
[next_page
].write_protected
);
1515 gc_assert(page_boxed_p(next_page
));
1517 gc_assert(page_allocated_no_region_p(next_page
));
1518 page_table
[next_page
].allocated
= UNBOXED_PAGE_FLAG
;
1520 page_table
[next_page
].gen
= new_space
;
1522 remaining_bytes
-= GENCGC_CARD_BYTES
;
1526 /* Now only one page remains, but the object may have shrunk so
1527 * there may be more unused pages which will be freed. */
1529 /* Object may have shrunk but shouldn't have grown - check. */
1530 gc_assert(page_bytes_used(next_page
) >= remaining_bytes
);
1532 page_table
[next_page
].gen
= new_space
;
1535 gc_assert(page_boxed_p(next_page
));
1537 page_table
[next_page
].allocated
= UNBOXED_PAGE_FLAG
;
1539 /* Adjust the bytes_used. */
1540 old_bytes_used
= page_bytes_used(next_page
);
1541 set_page_bytes_used(next_page
, remaining_bytes
);
1543 bytes_freed
= old_bytes_used
- remaining_bytes
;
1545 /* Free any remaining pages; needs care. */
1547 while ((old_bytes_used
== GENCGC_CARD_BYTES
) &&
1548 (page_table
[next_page
].gen
== from_space
) &&
1549 /* FIXME: It is not obvious to me why this is necessary
1550 * as a loop condition: it seems to me that the
1551 * scan_start_offset test should be sufficient, but
1552 * experimentally that is not the case. --NS
1555 page_boxed_p(next_page
) :
1556 page_allocated_no_region_p(next_page
)) &&
1557 page_table
[next_page
].large_object
&&
1558 (page_scan_start_offset(next_page
) ==
1559 npage_bytes(next_page
- first_page
))) {
1560 /* Checks out OK, free the page. Don't need to both zeroing
1561 * pages as this should have been done before shrinking the
1562 * object. These pages shouldn't be write-protected, even if
1563 * boxed they should be zero filled. */
1564 gc_assert(!page_table
[next_page
].write_protected
);
1566 old_bytes_used
= page_bytes_used(next_page
);
1567 reset_page_flags(next_page
);
1568 set_page_bytes_used(next_page
, 0);
1569 bytes_freed
+= old_bytes_used
;
1573 if ((bytes_freed
> 0) && gencgc_verbose
) {
1575 "/general_copy_large_object bytes_freed=%"OS_VM_SIZE_FMT
"\n",
1579 generations
[from_space
].bytes_allocated
-= nwords
*N_WORD_BYTES
1581 generations
[new_space
].bytes_allocated
+= nwords
*N_WORD_BYTES
;
1582 bytes_allocated
-= bytes_freed
;
1584 /* Add the region to the new_areas if requested. */
1586 add_new_area(first_page
,0,nwords
*N_WORD_BYTES
);
1591 /* Allocate space. */
1592 new = gc_general_alloc(nwords
*N_WORD_BYTES
, page_type_flag
, ALLOC_QUICK
);
1594 /* Copy the object. */
1595 memcpy(new,native_pointer(object
),nwords
*N_WORD_BYTES
);
1597 /* Return Lisp pointer of new object. */
1598 return make_lispobj(new, lowtag_of(object
));
1602 /* to copy unboxed objects */
1604 copy_unboxed_object(lispobj object
, sword_t nwords
)
1606 return gc_general_copy_object(object
, nwords
, UNBOXED_PAGE_FLAG
);
1614 scav_weak_pointer(lispobj
*where
, lispobj object
)
1616 struct weak_pointer
* wp
= (struct weak_pointer
*)where
;
1618 if (!wp
->next
&& weak_pointer_breakable_p(wp
)) {
1619 /* All weak pointers refer to objects at least as old as themselves,
1620 * because there is no slot setter for WEAK-POINTER-VALUE.
1621 * (i.e. You can't reference an object that didn't already exist,
1622 * assuming that users don't stuff a new value in via low-level hacks)
1623 * A weak pointer is breakable only if it points to an object in the
1624 * condemned generation, which must be as young as, or younger than
1625 * the weak pointer itself. Per the initial claim, it can't be younger.
1626 * So it must be in the same generation. Therefore, if the pointee
1627 * is condemned, the pointer itself must be condemned. Hence it must
1628 * not be on a write-protected page. Assert this, to be sure.
1629 * (This assertion is compiled out in a normal build,
1630 * so even if incorrect, it should be relatively harmless)
1632 gc_dcheck(!page_table
[find_page_index(wp
)].write_protected
);
1633 add_to_weak_pointer_list(wp
);
1636 /* Do not let GC scavenge the value slot of the weak pointer.
1637 * (That is why it is a weak pointer.) */
1639 return WEAK_POINTER_NWORDS
;
1642 /* a faster version for searching the dynamic space. This will work even
1643 * if the object is in a current allocation region. */
1645 search_dynamic_space(void *pointer
)
1647 page_index_t page_index
= find_page_index(pointer
);
1650 /* The address may be invalid, so do some checks. */
1651 if ((page_index
== -1) || page_free_p(page_index
))
1653 start
= (lispobj
*)page_scan_start(page_index
);
1654 return gc_search_space(start
, pointer
);
1657 #if !GENCGC_IS_PRECISE
1658 // Return the starting address of the object containing 'addr'
1659 // if and only if the object is one which would be evacuated from 'from_space'
1660 // were it allowed to be either discarded as garbage or moved.
1661 // 'addr_page_index' is the page containing 'addr' and must not be -1.
1662 // Return 0 if there is no such object - that is, if addr is past the
1663 // end of the used bytes, or its pages are not in 'from_space' etc.
1665 conservative_root_p(void *addr
, page_index_t addr_page_index
)
1667 /* quick check 1: Address is quite likely to have been invalid. */
1668 struct page
* page
= &page_table
[addr_page_index
];
1669 if (((uword_t
)addr
& (GENCGC_CARD_BYTES
- 1)) > page_bytes_used(addr_page_index
) ||
1671 (!is_lisp_pointer((lispobj
)addr
) && page
->allocated
!= CODE_PAGE_FLAG
) ||
1673 (compacting_p() && (page
->gen
!= from_space
||
1674 (page
->large_object
&& page
->dont_move
))))
1676 gc_assert(!(page
->allocated
& OPEN_REGION_PAGE_FLAG
));
1679 /* quick check 2: Unless the page can hold code, the pointer's lowtag must
1680 * correspond to the widetag of the object. The object header can safely
1681 * be read even if it turns out that the pointer is not valid,
1682 * because the pointer was in bounds for the page.
1683 * Note that this can falsely pass if looking at the interior of an unboxed
1684 * array that masquerades as a Lisp object header by pure luck.
1685 * But if this doesn't pass, there's no point in proceeding to the
1686 * definitive test which involves searching for the containing object. */
1688 if (page
->allocated
!= CODE_PAGE_FLAG
) {
1689 lispobj
* obj
= native_pointer((lispobj
)addr
);
1690 if (lowtag_of((lispobj
)addr
) == LIST_POINTER_LOWTAG
) {
1691 if (!is_cons_half(obj
[0]) || !is_cons_half(obj
[1]))
1694 unsigned char widetag
= widetag_of(*obj
);
1695 if (!other_immediate_lowtag_p(widetag
) ||
1696 lowtag_of((lispobj
)addr
) != lowtag_for_widetag
[widetag
>>2])
1702 /* Filter out anything which can't be a pointer to a Lisp object
1703 * (or, as a special case which also requires dont_move, a return
1704 * address referring to something in a CodeObject). This is
1705 * expensive but important, since it vastly reduces the
1706 * probability that random garbage will be bogusly interpreted as
1707 * a pointer which prevents a page from moving. */
1708 lispobj
* object_start
= search_dynamic_space(addr
);
1709 if (!object_start
) return 0;
1711 /* If the containing object is a code object and 'addr' points
1712 * anywhere beyond the boxed words,
1713 * presume it to be a valid unboxed return address. */
1714 if (instruction_ptr_p(addr
, object_start
))
1715 return object_start
;
1717 /* Large object pages only contain ONE object, and it will never
1718 * be a CONS. However, arrays and bignums can be allocated larger
1719 * than necessary and then shrunk to fit, leaving what look like
1720 * (0 . 0) CONSes at the end. These appear valid to
1721 * properly_tagged_descriptor_p(), so pick them off here. */
1722 if (((lowtag_of((lispobj
)addr
) == LIST_POINTER_LOWTAG
) &&
1723 page_table
[addr_page_index
].large_object
)
1724 || !properly_tagged_descriptor_p(addr
, object_start
))
1727 return object_start
;
1731 /* Adjust large bignum and vector objects. This will adjust the
1732 * allocated region if the size has shrunk, and change boxed pages
1733 * into unboxed pages. The pages are not promoted here, and the
1734 * object is not added to the new_regions; this is really
1735 * only designed to be called from preserve_pointer(). Shouldn't fail
1736 * if this is missed, just may delay the moving of objects to unboxed
1737 * pages, and the freeing of pages. */
1739 maybe_adjust_large_object(page_index_t first_page
, sword_t nwords
)
1741 lispobj
* where
= (lispobj
*)page_address(first_page
);
1742 page_index_t next_page
;
1744 uword_t remaining_bytes
;
1745 uword_t bytes_freed
;
1746 uword_t old_bytes_used
;
1750 /* Check whether it's a vector or bignum object. */
1751 lispobj widetag
= widetag_of(where
[0]);
1752 if (widetag
== SIMPLE_VECTOR_WIDETAG
)
1753 page_type_flag
= BOXED_PAGE_FLAG
;
1754 else if (specialized_vector_widetag_p(widetag
) || widetag
== BIGNUM_WIDETAG
)
1755 page_type_flag
= UNBOXED_PAGE_FLAG
;
1759 /* Note: Any page write-protection must be removed, else a later
1760 * scavenge_newspace may incorrectly not scavenge these pages.
1761 * This would not be necessary if they are added to the new areas,
1762 * but lets do it for them all (they'll probably be written
1765 gc_assert(page_starts_contiguous_block_p(first_page
));
1767 next_page
= first_page
;
1768 remaining_bytes
= nwords
*N_WORD_BYTES
;
1769 while (remaining_bytes
> GENCGC_CARD_BYTES
) {
1770 gc_assert(page_table
[next_page
].gen
== from_space
);
1771 // We can't assert that page_table[next_page].allocated is correct,
1772 // because unboxed objects are initially allocated on boxed pages.
1773 gc_assert(page_allocated_no_region_p(next_page
));
1774 gc_assert(page_table
[next_page
].large_object
);
1775 gc_assert(page_scan_start_offset(next_page
) ==
1776 npage_bytes(next_page
-first_page
));
1777 gc_assert(page_bytes_used(next_page
) == GENCGC_CARD_BYTES
);
1779 // This affects only one object, since large objects don't share pages.
1780 page_table
[next_page
].allocated
= page_type_flag
;
1782 /* Shouldn't be write-protected at this stage. Essential that the
1784 gc_assert(!page_table
[next_page
].write_protected
);
1785 remaining_bytes
-= GENCGC_CARD_BYTES
;
1789 /* Now only one page remains, but the object may have shrunk so
1790 * there may be more unused pages which will be freed. */
1792 /* Object may have shrunk but shouldn't have grown - check. */
1793 gc_assert(page_bytes_used(next_page
) >= remaining_bytes
);
1795 page_table
[next_page
].allocated
= page_type_flag
;
1797 /* Adjust the bytes_used. */
1798 old_bytes_used
= page_bytes_used(next_page
);
1799 set_page_bytes_used(next_page
, remaining_bytes
);
1801 bytes_freed
= old_bytes_used
- remaining_bytes
;
1803 /* Free any remaining pages; needs care. */
1805 while ((old_bytes_used
== GENCGC_CARD_BYTES
) &&
1806 (page_table
[next_page
].gen
== from_space
) &&
1807 page_allocated_no_region_p(next_page
) &&
1808 page_table
[next_page
].large_object
&&
1809 (page_scan_start_offset(next_page
) ==
1810 npage_bytes(next_page
- first_page
))) {
1811 /* It checks out OK, free the page. We don't need to bother zeroing
1812 * pages as this should have been done before shrinking the
1813 * object. These pages shouldn't be write protected as they
1814 * should be zero filled. */
1815 gc_assert(!page_table
[next_page
].write_protected
);
1817 old_bytes_used
= page_bytes_used(next_page
);
1818 reset_page_flags(next_page
);
1819 set_page_bytes_used(next_page
, 0);
1820 bytes_freed
+= old_bytes_used
;
1824 if ((bytes_freed
> 0) && gencgc_verbose
) {
1826 "/maybe_adjust_large_object() freed %d\n",
1830 generations
[from_space
].bytes_allocated
-= bytes_freed
;
1831 bytes_allocated
-= bytes_freed
;
1836 #ifdef PIN_GRANULARITY_LISPOBJ
1837 /* After scavenging of the roots is done, we go back to the pinned objects
1838 * and look within them for pointers. While heap_scavenge() could certainly
1839 * do this, it would potentially lead to extra work, since we can't know
1840 * whether any given object has been examined at least once, since there is
1841 * no telltale forwarding-pointer. The easiest thing to do is defer all
1842 * pinned objects to a subsequent pass, as is done here.
1845 scavenge_pinned_ranges()
1849 for_each_hopscotch_key(i
, key
, pinned_objects
) {
1850 lispobj
* obj
= native_pointer(key
);
1851 lispobj header
= *obj
;
1852 // Never invoke scavenger on a simple-fun, just code components.
1853 if (is_cons_half(header
))
1855 else if (widetag_of(header
) != SIMPLE_FUN_WIDETAG
)
1856 scavtab
[widetag_of(header
)](obj
, header
);
1860 /* Deposit filler objects on small object pinned pages
1861 * from the page start to the first pinned object and in between pairs
1862 * of pinned objects. Zero-fill bytes following the last pinned object.
1863 * Also ensure that no scan_start_offset points to a page in
1864 * oldspace that will be freed.
1867 wipe_nonpinned_words()
1869 void gc_heapsort_uwords(uword_t
*, int);
1871 if (!pinned_objects
.count
)
1874 // Loop over the keys in pinned_objects and pack them densely into
1875 // the same array - pinned_objects.keys[] - but skip any simple-funs.
1876 // Admittedly this is abstraction breakage.
1877 int limit
= hopscotch_max_key_index(pinned_objects
);
1879 for (i
= 0; i
<= limit
; ++i
) {
1880 lispobj key
= pinned_objects
.keys
[i
];
1882 lispobj
* obj
= native_pointer(key
);
1883 // No need to check for is_cons_half() - it will be false
1884 // on a simple-fun header, and that's the correct answer.
1885 if (widetag_of(*obj
) != SIMPLE_FUN_WIDETAG
)
1886 pinned_objects
.keys
[n_pins
++] = (uword_t
)obj
;
1889 // Don't touch pinned_objects.count in case the reset function uses it
1890 // to decide how to resize for next use (which it doesn't, but could).
1891 gc_n_stack_pins
= n_pins
;
1892 // Order by ascending address, stopping short of the sentinel.
1893 gc_heapsort_uwords(pinned_objects
.keys
, n_pins
);
1895 fprintf(stderr
, "Sorted pin list:\n");
1896 for (i
= 0; i
< n_pins
; ++i
) {
1897 lispobj
* obj
= (lispobj
*)pinned_objects
.keys
[i
];
1898 lispobj word
= *obj
;
1899 int widetag
= widetag_of(word
);
1900 if (is_cons_half(word
))
1901 fprintf(stderr
, "%p: (cons)\n", obj
);
1903 fprintf(stderr
, "%p: %d words (%s)\n", obj
,
1904 (int)sizetab
[widetag
](obj
), widetag_names
[widetag
>>2]);
1908 #define page_base(x) ALIGN_DOWN(x, GENCGC_CARD_BYTES)
1909 // This macro asserts that space accounting happens exactly
1910 // once per affected page (a page with any pins, no matter how many)
1911 #define adjust_gen_usage(i) \
1912 gc_assert(page_table[i].has_pins); \
1913 page_table[i].has_pins = 0; \
1914 bytes_moved += page_bytes_used(i); \
1915 page_table[i].gen = new_space
1917 // Store a sentinel at the end. Even if n_pins = table capacity (unlikely),
1918 // it is safe to write one more word, because the hops[] array immediately
1919 // follows the keys[] array in memory. At worst, 2 elements of hops[]
1920 // are clobbered, which is irrelevant since the table has already been
1921 // rendered unusable by stealing its key array for a different purpose.
1922 pinned_objects
.keys
[n_pins
] = ~(uword_t
)0;
1924 // Each pinned object begets two ranges of bytes to be turned into filler:
1925 // - the range preceding it back to its page start or predecessor object
1926 // - the range after it, up to the lesser of page bytes used or successor object
1929 uword_t fill_from
= page_base(pinned_objects
.keys
[0]);
1930 os_vm_size_t bytes_moved
= 0; // i.e. virtually moved
1931 os_vm_size_t bytes_freed
= 0; // bytes after last pinned object per page
1933 for (i
= 0; i
< n_pins
; ++i
) {
1934 lispobj
* obj
= (lispobj
*)pinned_objects
.keys
[i
];
1935 page_index_t begin_page_index
= find_page_index(obj
);
1936 // Create a filler object occupying space from 'fill_from' up to but
1937 // excluding 'obj'. If obj directly abuts its predecessor then don't.
1938 if ((uword_t
)obj
> fill_from
) {
1939 lispobj
* filler
= (lispobj
*)fill_from
;
1940 int nwords
= obj
- filler
;
1941 if (page_table
[begin_page_index
].allocated
!= CODE_PAGE_FLAG
) {
1942 // On pages holding non-code, the filler is an array
1943 filler
[0] = SIMPLE_ARRAY_WORD_WIDETAG
;
1944 filler
[1] = make_fixnum(nwords
- 2);
1945 } else if (nwords
> 2) {
1946 // Otherwise try to keep a strict code/non-code distinction
1947 filler
[0] = 2<<N_WIDETAG_BITS
| CODE_HEADER_WIDETAG
;
1948 filler
[1] = make_fixnum((nwords
- 2) * N_WORD_BYTES
);
1952 // But as an exception, use a NIL array for tiny code filler
1953 // (If the ENSURE-CODE/DATA-SEPARATION test fails again,
1954 // it may need to ignore these objects. Hasn't happened yet)
1955 filler
[0] = SIMPLE_ARRAY_NIL_WIDETAG
;
1956 filler
[1] = make_fixnum(0xDEAD);
1959 if (fill_from
== page_base((uword_t
)obj
)) {
1960 adjust_gen_usage(begin_page_index
);
1961 // This pinned object started a new page of pins.
1962 // scan_start must not see any page prior to this page,
1963 // as those might be in oldspace and about to be marked free.
1964 set_page_scan_start_offset(begin_page_index
, 0);
1966 // If 'obj' spans pages, move its successive page(s) to newspace and
1967 // ensure that those pages' scan_starts point at the same address
1968 // that this page's scan start does, which could be this page or earlier.
1969 size_t nwords
= OBJECT_SIZE(*obj
, obj
);
1970 lispobj
* obj_end
= obj
+ nwords
; // non-inclusive address bound
1971 page_index_t end_page_index
= find_page_index(obj_end
- 1); // inclusive bound
1973 if (end_page_index
> begin_page_index
) {
1974 char *scan_start
= page_scan_start(begin_page_index
);
1976 for (index
= begin_page_index
+ 1; index
<= end_page_index
; ++index
) {
1977 set_page_scan_start_offset(index
,
1978 addr_diff(page_address(index
), scan_start
));
1979 adjust_gen_usage(index
);
1982 // Compute page base address of last page touched by this obj.
1983 uword_t obj_end_pageaddr
= page_base((uword_t
)obj_end
- 1);
1984 // See if there's another pinned object on this page.
1985 // There is always a next object, due to the sentinel.
1986 if (pinned_objects
.keys
[i
+1] < obj_end_pageaddr
+ GENCGC_CARD_BYTES
) {
1987 // Next object starts within the same page.
1988 fill_from
= (uword_t
)obj_end
;
1990 // Next pinned object does not start on the same page this obj ends on.
1991 // Any bytes following 'obj' up to its page end are garbage.
1992 uword_t page_end
= obj_end_pageaddr
+ page_bytes_used(end_page_index
);
1993 long nbytes
= page_end
- (uword_t
)obj_end
;
1994 gc_assert(nbytes
>= 0);
1996 // Bytes beyond a page's highest used byte must be zero.
1997 memset(obj_end
, 0, nbytes
);
1998 bytes_freed
+= nbytes
;
1999 set_page_bytes_used(end_page_index
,
2000 (uword_t
)obj_end
- obj_end_pageaddr
);
2002 fill_from
= page_base(pinned_objects
.keys
[i
+1]);
2005 generations
[from_space
].bytes_allocated
-= bytes_moved
;
2006 generations
[new_space
].bytes_allocated
+= bytes_moved
- bytes_freed
;
2007 bytes_allocated
-= bytes_freed
;
2008 #undef adjust_gen_usage
2012 /* Add 'object' to the hashtable, and if the object is a code component,
2013 * then also add all of the embedded simple-funs.
2014 * The rationale for the extra work on code components is that without it,
2015 * every test of pinned_p() on an object would have to check if the pointer
2016 * is to a simple-fun - entailing an extra read of the header - and mapping
2017 * to its code component if so. Since more calls to pinned_p occur than to
2018 * pin_object, the extra burden should be on this function.
2019 * Experimentation bears out that this is the better technique.
2020 * Also, we wouldn't often expect code components in the collected generation
2021 * so the extra work here is quite minimal, even if it can generally add to
2022 * the number of keys in the hashtable.
2025 pin_object(lispobj
* base_addr
)
2027 lispobj object
= compute_lispobj(base_addr
);
2028 if (!hopscotch_containsp(&pinned_objects
, object
)) {
2029 hopscotch_insert(&pinned_objects
, object
, 1);
2030 struct code
* maybe_code
= (struct code
*)native_pointer(object
);
2031 if (widetag_of(maybe_code
->header
) == CODE_HEADER_WIDETAG
) {
2032 for_each_simple_fun(i
, fun
, maybe_code
, 0, {
2033 hopscotch_insert(&pinned_objects
,
2034 make_lispobj(fun
, FUN_POINTER_LOWTAG
),
2041 # define scavenge_pinned_ranges()
2042 # define wipe_nonpinned_words()
2045 /* Take a possible pointer to a Lisp object and mark its page in the
2046 * page_table so that it will not be relocated during a GC.
2048 * This involves locating the page it points to, then backing up to
2049 * the start of its region, then marking all pages dont_move from there
2050 * up to the first page that's not full or has a different generation
2052 * It is assumed that all the page static flags have been cleared at
2053 * the start of a GC.
2055 * It is also assumed that the current gc_alloc() region has been
2056 * flushed and the tables updated. */
2058 // TODO: there's probably a way to be a little more efficient here.
2059 // As things are, we start by finding the object that encloses 'addr',
2060 // then we see if 'addr' was a "valid" Lisp pointer to that object
2061 // - meaning we expect the correct lowtag on the pointer - except
2062 // that for code objects we don't require a correct lowtag
2063 // and we allow a pointer to anywhere in the object.
2065 // It should be possible to avoid calling search_dynamic_space
2066 // more of the time. First, check if the page pointed to might hold code.
2067 // If it does, then we continue regardless of the pointer's lowtag
2068 // (because of the special allowance). If the page definitely does *not*
2069 // hold code, then we require up front that the lowtake make sense,
2070 // by doing the same checks that are in properly_tagged_descriptor_p.
2072 // Problem: when code is allocated from a per-thread region,
2073 // does it ensure that the occupied pages are flagged as having code?
2075 #if defined(__GNUC__) && defined(MEMORY_SANITIZER)
2076 #define NO_SANITIZE_MEMORY __attribute__((no_sanitize_memory))
2078 #define NO_SANITIZE_MEMORY
2081 static void NO_SANITIZE_MEMORY
2082 preserve_pointer(void *addr
)
2084 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2085 /* Immobile space MUST be lower than dynamic space,
2086 or else this test needs to be revised */
2087 if (addr
< (void*)IMMOBILE_SPACE_END
) {
2088 extern void immobile_space_preserve_pointer(void*);
2089 immobile_space_preserve_pointer(addr
);
2093 page_index_t page
= find_page_index(addr
);
2094 lispobj
*object_start
;
2096 #if GENCGC_IS_PRECISE
2097 /* If we're in precise gencgc (non-x86oid as of this writing) then
2098 * we are only called on valid object pointers in the first place,
2099 * so we just have to do a bounds-check against the heap, a
2100 * generation check, and the already-pinned check. */
2102 (compacting_p() && (page_table
[page
].gen
!= from_space
||
2103 (page_table
[page
].large_object
&&
2104 page_table
[page
].dont_move
))))
2106 object_start
= native_pointer((lispobj
)addr
);
2107 switch (widetag_of(*object_start
)) {
2108 case SIMPLE_FUN_WIDETAG
:
2109 #ifdef RETURN_PC_WIDETAG
2110 case RETURN_PC_WIDETAG
:
2112 object_start
= fun_code_header(object_start
);
2115 if (page
< 0 || (object_start
= conservative_root_p(addr
, page
)) == NULL
)
2119 if (!compacting_p()) {
2120 /* Just mark it. No distinction between large and small objects. */
2121 gc_mark_obj(compute_lispobj(object_start
));
2125 page_index_t first_page
= find_page_index(object_start
);
2126 size_t nwords
= OBJECT_SIZE(*object_start
, object_start
);
2127 page_index_t last_page
= find_page_index(object_start
+ nwords
- 1);
2129 for (page
= first_page
; page
<= last_page
; ++page
) {
2130 /* Oldspace pages were unprotected at start of GC.
2131 * Assert this here, because the previous logic used to,
2132 * and page protection bugs are scary */
2133 gc_assert(!page_table
[page
].write_protected
);
2135 /* Mark the page static. */
2136 page_table
[page
].dont_move
= 1;
2137 page_table
[page
].has_pins
= !page_table
[page
].large_object
;
2140 if (page_table
[first_page
].large_object
)
2141 maybe_adjust_large_object(first_page
, nwords
);
2143 pin_object(object_start
);
2147 #define IN_REGION_P(a,kind) (kind##_region.start_addr<=a && a<=kind##_region.free_pointer)
2149 #define IN_BOXED_REGION_P(a) IN_REGION_P(a,boxed)||IN_REGION_P(a,code)
2151 #define IN_BOXED_REGION_P(a) IN_REGION_P(a,boxed)
2154 /* If the given page is not write-protected, then scan it for pointers
2155 * to younger generations or the top temp. generation, if no
2156 * suspicious pointers are found then the page is write-protected.
2158 * Care is taken to check for pointers to the current gc_alloc()
2159 * region if it is a younger generation or the temp. generation. This
2160 * frees the caller from doing a gc_alloc_update_page_tables(). Actually
2161 * the gc_alloc_generation does not need to be checked as this is only
2162 * called from scavenge_generation() when the gc_alloc generation is
2163 * younger, so it just checks if there is a pointer to the current
2166 * We return 1 if the page was write-protected, else 0. */
2168 update_page_write_prot(page_index_t page
)
2170 generation_index_t gen
= page_table
[page
].gen
;
2173 void **page_addr
= (void **)page_address(page
);
2174 sword_t num_words
= page_bytes_used(page
) / N_WORD_BYTES
;
2176 /* Shouldn't be a free page. */
2177 gc_assert(!page_free_p(page
));
2178 gc_assert(page_bytes_used(page
) != 0);
2180 if (!ENABLE_PAGE_PROTECTION
) return 0;
2182 /* Skip if it's already write-protected, pinned, or unboxed */
2183 if (page_table
[page
].write_protected
2184 /* FIXME: What's the reason for not write-protecting pinned pages? */
2185 || page_table
[page
].dont_move
2186 || page_unboxed_p(page
))
2189 /* Scan the page for pointers to younger generations or the
2190 * top temp. generation. */
2192 /* This is conservative: any word satisfying is_lisp_pointer() is
2193 * assumed to be a pointer. To do otherwise would require a family
2194 * of scavenge-like functions. */
2195 for (j
= 0; j
< num_words
; j
++) {
2196 void *ptr
= *(page_addr
+j
);
2198 lispobj
__attribute__((unused
)) header
;
2200 if (!is_lisp_pointer((lispobj
)ptr
))
2202 /* Check that it's in the dynamic space */
2203 if ((index
= find_page_index(ptr
)) != -1) {
2204 if (/* Does it point to a younger or the temp. generation? */
2205 ((page_bytes_used(index
) != 0)
2206 && ((page_table
[index
].gen
< gen
)
2207 || (page_table
[index
].gen
== SCRATCH_GENERATION
)))
2209 /* Or does it point within a current gc_alloc() region? */
2210 || (IN_BOXED_REGION_P(ptr
) || IN_REGION_P(ptr
,unboxed
))) {
2215 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2216 else if ((index
= find_immobile_page_index(ptr
)) >= 0 &&
2217 other_immediate_lowtag_p(header
= *native_pointer((lispobj
)ptr
))) {
2218 // This is *possibly* a pointer to an object in immobile space,
2219 // given that above two conditions were satisfied.
2220 // But unlike in the dynamic space case, we need to read a byte
2221 // from the object to determine its generation, which requires care.
2222 // Consider an unboxed word that looks like a pointer to a word that
2223 // looks like fun-header-widetag. We can't naively back up to the
2224 // underlying code object since the alleged header might not be one.
2225 int obj_gen
= gen
; // Make comparison fail if we fall through
2226 if (lowtag_of((lispobj
)ptr
) == FUN_POINTER_LOWTAG
&&
2227 widetag_of(header
) == SIMPLE_FUN_WIDETAG
) {
2228 lispobj
* code
= fun_code_header((lispobj
)ptr
- FUN_POINTER_LOWTAG
);
2229 // This is a heuristic, since we're not actually looking for
2230 // an object boundary. Precise scanning of 'page' would obviate
2231 // the guard conditions here.
2232 if ((lispobj
)code
>= IMMOBILE_VARYOBJ_SUBSPACE_START
2233 && widetag_of(*code
) == CODE_HEADER_WIDETAG
)
2234 obj_gen
= __immobile_obj_generation(code
);
2236 obj_gen
= __immobile_obj_generation(native_pointer((lispobj
)ptr
));
2238 // A bogus generation number implies a not-really-pointer,
2239 // but it won't cause misbehavior.
2240 if (obj_gen
< gen
|| obj_gen
== SCRATCH_GENERATION
) {
2249 protect_page(page_addr
, page
);
2254 /* Is this page holding a normal (non-hashtable) large-object
2256 static inline boolean
large_simple_vector_p(page_index_t page
) {
2257 if (!page_table
[page
].large_object
)
2259 lispobj header
= *(lispobj
*)page_address(page
);
2260 return widetag_of(header
) == SIMPLE_VECTOR_WIDETAG
&&
2261 is_vector_subtype(header
, VectorNormal
);
2265 /* Scavenge all generations from FROM to TO, inclusive, except for
2266 * new_space which needs special handling, as new objects may be
2267 * added which are not checked here - use scavenge_newspace generation.
2269 * Write-protected pages should not have any pointers to the
2270 * from_space so do need scavenging; thus write-protected pages are
2271 * not always scavenged. There is some code to check that these pages
2272 * are not written; but to check fully the write-protected pages need
2273 * to be scavenged by disabling the code to skip them.
2275 * Under the current scheme when a generation is GCed the younger
2276 * generations will be empty. So, when a generation is being GCed it
2277 * is only necessary to scavenge the older generations for pointers
2278 * not the younger. So a page that does not have pointers to younger
2279 * generations does not need to be scavenged.
2281 * The write-protection can be used to note pages that don't have
2282 * pointers to younger pages. But pages can be written without having
2283 * pointers to younger generations. After the pages are scavenged here
2284 * they can be scanned for pointers to younger generations and if
2285 * there are none the page can be write-protected.
2287 * One complication is when the newspace is the top temp. generation.
2289 * Enabling SC_GEN_CK scavenges the write-protected pages and checks
2290 * that none were written, which they shouldn't be as they should have
2291 * no pointers to younger generations. This breaks down for weak
2292 * pointers as the objects contain a link to the next and are written
2293 * if a weak pointer is scavenged. Still it's a useful check. */
2295 scavenge_generations(generation_index_t from
, generation_index_t to
)
2298 page_index_t num_wp
= 0;
2302 /* Clear the write_protected_cleared flags on all pages. */
2303 for (i
= 0; i
< page_table_pages
; i
++)
2304 page_table
[i
].write_protected_cleared
= 0;
2307 for (i
= 0; i
< last_free_page
; i
++) {
2308 generation_index_t generation
= page_table
[i
].gen
;
2310 && (page_bytes_used(i
) != 0)
2311 && (generation
!= new_space
)
2312 && (generation
>= from
)
2313 && (generation
<= to
)) {
2315 /* This should be the start of a region */
2316 gc_assert(page_starts_contiguous_block_p(i
));
2318 if (large_simple_vector_p(i
)) {
2319 /* Scavenge only the unprotected pages of a
2320 * large-object vector, other large objects could be
2321 * handled as well, but vectors are easier to deal
2322 * with and are more likely to grow to very large
2323 * sizes where avoiding scavenging the whole thing is
2325 if (!page_table
[i
].write_protected
) {
2326 scavenge((lispobj
*)page_address(i
) + 2,
2327 GENCGC_CARD_BYTES
/ N_WORD_BYTES
- 2);
2328 update_page_write_prot(i
);
2330 while (!page_ends_contiguous_block_p(i
, generation
)) {
2332 if (!page_table
[i
].write_protected
) {
2333 scavenge((lispobj
*)page_address(i
),
2334 page_bytes_used(i
) / N_WORD_BYTES
);
2335 update_page_write_prot(i
);
2339 page_index_t last_page
, j
;
2340 boolean write_protected
= 1;
2341 /* Now work forward until the end of the region */
2342 for (last_page
= i
; ; last_page
++) {
2344 write_protected
&& page_table
[last_page
].write_protected
;
2345 if (page_ends_contiguous_block_p(last_page
, generation
))
2348 if (!write_protected
) {
2349 heap_scavenge((lispobj
*)page_address(i
),
2350 (lispobj
*)(page_address(last_page
)
2351 + page_bytes_used(last_page
)));
2353 /* Now scan the pages and write protect those that
2354 * don't have pointers to younger generations. */
2355 if (ENABLE_PAGE_PROTECTION
) {
2356 for (j
= i
; j
<= last_page
; j
++) {
2357 num_wp
+= update_page_write_prot(j
);
2360 if ((gencgc_verbose
> 1) && (num_wp
!= 0)) {
2362 "/write protected %d pages within generation %d\n",
2363 num_wp
, generation
));
2372 /* Check that none of the write_protected pages in this generation
2373 * have been written to. */
2374 for (i
= 0; i
< page_table_pages
; i
++) {
2375 if ((page_bytes_used(i
) != 0)
2376 && (page_table
[i
].gen
== generation
)
2377 && (page_table
[i
].write_protected_cleared
!= 0)) {
2378 FSHOW((stderr
, "/scavenge_generation() %d\n", generation
));
2380 "/page bytes_used=%d scan_start_offset=%lu dont_move=%d\n",
2382 scan_start_offset(page_table
[i
]),
2383 page_table
[i
].dont_move
));
2384 lose("write to protected page %d in scavenge_generation()\n", i
);
2391 /* Scavenge a newspace generation. As it is scavenged new objects may
2392 * be allocated to it; these will also need to be scavenged. This
2393 * repeats until there are no more objects unscavenged in the
2394 * newspace generation.
2396 * To help improve the efficiency, areas written are recorded by
2397 * gc_alloc() and only these scavenged. Sometimes a little more will be
2398 * scavenged, but this causes no harm. An easy check is done that the
2399 * scavenged bytes equals the number allocated in the previous
2402 * Write-protected pages are not scanned except if they are marked
2403 * dont_move in which case they may have been promoted and still have
2404 * pointers to the from space.
2406 * Write-protected pages could potentially be written by alloc however
2407 * to avoid having to handle re-scavenging of write-protected pages
2408 * gc_alloc() does not write to write-protected pages.
2410 * New areas of objects allocated are recorded alternatively in the two
2411 * new_areas arrays below. */
2412 static struct new_area new_areas_1
[NUM_NEW_AREAS
];
2413 static struct new_area new_areas_2
[NUM_NEW_AREAS
];
2415 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2416 extern unsigned int immobile_scav_queue_count
;
2418 update_immobile_nursery_bits(),
2419 scavenge_immobile_roots(generation_index_t
,generation_index_t
),
2420 scavenge_immobile_newspace(),
2421 sweep_immobile_space(int raise
),
2422 write_protect_immobile_space();
2424 #define immobile_scav_queue_count 0
2427 /* Do one full scan of the new space generation. This is not enough to
2428 * complete the job as new objects may be added to the generation in
2429 * the process which are not scavenged. */
2431 scavenge_newspace_generation_one_scan(generation_index_t generation
)
2436 "/starting one full scan of newspace generation %d\n",
2438 for (i
= 0; i
< last_free_page
; i
++) {
2439 /* Note that this skips over open regions when it encounters them. */
2441 && (page_bytes_used(i
) != 0)
2442 && (page_table
[i
].gen
== generation
)
2443 && (!page_table
[i
].write_protected
2444 /* (This may be redundant as write_protected is now
2445 * cleared before promotion.) */
2446 || page_table
[i
].dont_move
)) {
2447 page_index_t last_page
;
2450 /* The scavenge will start at the scan_start_offset of
2453 * We need to find the full extent of this contiguous
2454 * block in case objects span pages.
2456 * Now work forward until the end of this contiguous area
2457 * is found. A small area is preferred as there is a
2458 * better chance of its pages being write-protected. */
2459 for (last_page
= i
; ;last_page
++) {
2460 /* If all pages are write-protected and movable,
2461 * then no need to scavenge */
2462 all_wp
=all_wp
&& page_table
[last_page
].write_protected
&&
2463 !page_table
[last_page
].dont_move
;
2465 /* Check whether this is the last page in this
2466 * contiguous block */
2467 if (page_ends_contiguous_block_p(last_page
, generation
))
2471 /* Do a limited check for write-protected pages. */
2473 new_areas_ignore_page
= last_page
;
2474 heap_scavenge(page_scan_start(i
),
2475 (lispobj
*)(page_address(last_page
)
2476 + page_bytes_used(last_page
)));
2482 "/done with one full scan of newspace generation %d\n",
2486 /* Do a complete scavenge of the newspace generation. */
2488 scavenge_newspace_generation(generation_index_t generation
)
2492 /* the new_areas array currently being written to by gc_alloc() */
2493 struct new_area (*current_new_areas
)[] = &new_areas_1
;
2494 size_t current_new_areas_index
;
2496 /* the new_areas created by the previous scavenge cycle */
2497 struct new_area (*previous_new_areas
)[] = NULL
;
2498 size_t previous_new_areas_index
;
2500 /* Flush the current regions updating the tables. */
2501 gc_alloc_update_all_page_tables(0);
2503 /* Turn on the recording of new areas by gc_alloc(). */
2504 new_areas
= current_new_areas
;
2505 new_areas_index
= 0;
2507 /* Don't need to record new areas that get scavenged anyway during
2508 * scavenge_newspace_generation_one_scan. */
2509 record_new_objects
= 1;
2511 /* Start with a full scavenge. */
2512 scavenge_newspace_generation_one_scan(generation
);
2514 /* Record all new areas now. */
2515 record_new_objects
= 2;
2517 /* Give a chance to weak hash tables to make other objects live.
2518 * FIXME: The algorithm implemented here for weak hash table gcing
2519 * is O(W^2+N) as Bruno Haible warns in
2520 * http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html
2521 * see "Implementation 2". */
2522 scav_weak_hash_tables(weak_ht_alivep_funs
, gc_scav_pair
);
2524 /* Flush the current regions updating the tables. */
2525 gc_alloc_update_all_page_tables(0);
2527 /* Grab new_areas_index. */
2528 current_new_areas_index
= new_areas_index
;
2531 "The first scan is finished; current_new_areas_index=%d.\n",
2532 current_new_areas_index));*/
2534 while (current_new_areas_index
> 0 || immobile_scav_queue_count
) {
2535 /* Move the current to the previous new areas */
2536 previous_new_areas
= current_new_areas
;
2537 previous_new_areas_index
= current_new_areas_index
;
2539 /* Scavenge all the areas in previous new areas. Any new areas
2540 * allocated are saved in current_new_areas. */
2542 /* Allocate an array for current_new_areas; alternating between
2543 * new_areas_1 and 2 */
2544 if (previous_new_areas
== &new_areas_1
)
2545 current_new_areas
= &new_areas_2
;
2547 current_new_areas
= &new_areas_1
;
2549 /* Set up for gc_alloc(). */
2550 new_areas
= current_new_areas
;
2551 new_areas_index
= 0;
2553 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2554 scavenge_immobile_newspace();
2556 /* Check whether previous_new_areas had overflowed. */
2557 if (previous_new_areas_index
>= NUM_NEW_AREAS
) {
2559 /* New areas of objects allocated have been lost so need to do a
2560 * full scan to be sure! If this becomes a problem try
2561 * increasing NUM_NEW_AREAS. */
2562 if (gencgc_verbose
) {
2563 SHOW("new_areas overflow, doing full scavenge");
2566 /* Don't need to record new areas that get scavenged
2567 * anyway during scavenge_newspace_generation_one_scan. */
2568 record_new_objects
= 1;
2570 scavenge_newspace_generation_one_scan(generation
);
2572 /* Record all new areas now. */
2573 record_new_objects
= 2;
2577 /* Work through previous_new_areas. */
2578 for (i
= 0; i
< previous_new_areas_index
; i
++) {
2579 page_index_t page
= (*previous_new_areas
)[i
].page
;
2580 size_t offset
= (*previous_new_areas
)[i
].offset
;
2581 size_t size
= (*previous_new_areas
)[i
].size
;
2582 gc_assert(size
% (2*N_WORD_BYTES
) == 0);
2583 lispobj
*start
= (lispobj
*)(page_address(page
) + offset
);
2584 heap_scavenge(start
, (lispobj
*)((char*)start
+ size
));
2589 scav_weak_hash_tables(weak_ht_alivep_funs
, gc_scav_pair
);
2591 /* Flush the current regions updating the tables. */
2592 gc_alloc_update_all_page_tables(0);
2594 current_new_areas_index
= new_areas_index
;
2597 "The re-scan has finished; current_new_areas_index=%d.\n",
2598 current_new_areas_index));*/
2601 /* Turn off recording of areas allocated by gc_alloc(). */
2602 record_new_objects
= 0;
2607 /* Check that none of the write_protected pages in this generation
2608 * have been written to. */
2609 for (i
= 0; i
< page_table_pages
; i
++) {
2610 if ((page_bytes_used(i
) != 0)
2611 && (page_table
[i
].gen
== generation
)
2612 && (page_table
[i
].write_protected_cleared
!= 0)
2613 && (page_table
[i
].dont_move
== 0)) {
2614 lose("write protected page %d written to in scavenge_newspace_generation\ngeneration=%d dont_move=%d\n",
2615 i
, generation
, page_table
[i
].dont_move
);
2622 /* Un-write-protect all the pages in from_space. This is done at the
2623 * start of a GC else there may be many page faults while scavenging
2624 * the newspace (I've seen drive the system time to 99%). These pages
2625 * would need to be unprotected anyway before unmapping in
2626 * free_oldspace; not sure what effect this has on paging.. */
2628 unprotect_oldspace(void)
2631 char *region_addr
= 0;
2632 char *page_addr
= 0;
2633 uword_t region_bytes
= 0;
2635 for (i
= 0; i
< last_free_page
; i
++) {
2636 if ((page_bytes_used(i
) != 0)
2637 && (page_table
[i
].gen
== from_space
)) {
2639 /* Remove any write-protection. We should be able to rely
2640 * on the write-protect flag to avoid redundant calls. */
2641 if (page_table
[i
].write_protected
) {
2642 page_table
[i
].write_protected
= 0;
2643 page_addr
= page_address(i
);
2646 region_addr
= page_addr
;
2647 region_bytes
= GENCGC_CARD_BYTES
;
2648 } else if (region_addr
+ region_bytes
== page_addr
) {
2649 /* Region continue. */
2650 region_bytes
+= GENCGC_CARD_BYTES
;
2652 /* Unprotect previous region. */
2653 os_protect(region_addr
, region_bytes
, OS_VM_PROT_ALL
);
2654 /* First page in new region. */
2655 region_addr
= page_addr
;
2656 region_bytes
= GENCGC_CARD_BYTES
;
2662 /* Unprotect last region. */
2663 os_protect(region_addr
, region_bytes
, OS_VM_PROT_ALL
);
2667 /* Work through all the pages and free any in from_space. This
2668 * assumes that all objects have been copied or promoted to an older
2669 * generation. Bytes_allocated and the generation bytes_allocated
2670 * counter are updated. The number of bytes freed is returned. */
2674 uword_t bytes_freed
= 0;
2675 page_index_t first_page
, last_page
;
2680 /* Find a first page for the next region of pages. */
2681 while ((first_page
< last_free_page
)
2682 && ((page_bytes_used(first_page
) == 0)
2683 || (page_table
[first_page
].gen
!= from_space
)))
2686 if (first_page
>= last_free_page
)
2689 /* Find the last page of this region. */
2690 last_page
= first_page
;
2693 /* Free the page. */
2694 bytes_freed
+= page_bytes_used(last_page
);
2695 generations
[page_table
[last_page
].gen
].bytes_allocated
-=
2696 page_bytes_used(last_page
);
2697 reset_page_flags(last_page
);
2698 set_page_bytes_used(last_page
, 0);
2699 /* Should already be unprotected by unprotect_oldspace(). */
2700 gc_assert(!page_table
[last_page
].write_protected
);
2703 while ((last_page
< last_free_page
)
2704 && (page_bytes_used(last_page
) != 0)
2705 && (page_table
[last_page
].gen
== from_space
));
2707 #ifdef TRAVERSE_FREED_OBJECTS
2708 /* At this point we could attempt to recycle unused TLS indices
2709 * as follows: For each now-garbage symbol that had a nonzero index,
2710 * return that index to a "free TLS index" pool, perhaps a linked list
2711 * or bitmap. Then either always try the free pool first (for better
2712 * locality) or if ALLOC-TLS-INDEX detects exhaustion (for speed). */
2714 lispobj
* where
= (lispobj
*)page_address(first_page
);
2715 lispobj
* end
= (lispobj
*)page_address(last_page
);
2716 while (where
< end
) {
2717 lispobj word
= *where
;
2718 if (forwarding_pointer_p(where
)) {
2719 word
= *native_pointer(forwarding_pointer_value(where
));
2720 where
+= OBJECT_SIZE(word
,
2721 native_pointer(forwarding_pointer_value(where
)));
2722 } else if (is_cons_half(word
)) {
2723 // Print something maybe
2726 // Print something maybe
2727 where
+= sizetab
[widetag_of(word
)](where
);
2733 #ifdef READ_PROTECT_FREE_PAGES
2734 os_protect(page_address(first_page
),
2735 npage_bytes(last_page
-first_page
),
2738 first_page
= last_page
;
2739 } while (first_page
< last_free_page
);
2741 bytes_allocated
-= bytes_freed
;
2746 /* Print some information about a pointer at the given address. */
2748 print_ptr(lispobj
*addr
)
2750 /* If addr is in the dynamic space then out the page information. */
2751 page_index_t pi1
= find_page_index((void*)addr
);
2754 fprintf(stderr
," %p: page %d alloc %d gen %d bytes_used %d offset %lu dont_move %d\n",
2757 page_table
[pi1
].allocated
,
2758 page_table
[pi1
].gen
,
2759 page_bytes_used(pi1
),
2760 scan_start_offset(page_table
[pi1
]),
2761 page_table
[pi1
].dont_move
);
2762 fprintf(stderr
," %x %x %x %x (%x) %x %x %x %x\n",
2776 is_in_stack_space(lispobj ptr
)
2778 /* For space verification: Pointers can be valid if they point
2779 * to a thread stack space. This would be faster if the thread
2780 * structures had page-table entries as if they were part of
2781 * the heap space. */
2782 /* Actually, no, how would that be faster?
2783 * If you have to examine thread structures, you have to examine
2784 * them all. This demands something like a binary search tree */
2786 for_each_thread(th
) {
2787 if ((th
->control_stack_start
<= (lispobj
*)ptr
) &&
2788 (th
->control_stack_end
>= (lispobj
*)ptr
)) {
2795 struct verify_state
{
2796 lispobj
*object_start
, *object_end
;
2797 lispobj
*virtual_where
;
2800 generation_index_t object_gen
;
2803 #define VERIFY_VERBOSE 1
2804 /* AGGRESSIVE = always call valid_lisp_pointer_p() on pointers.
2805 * Otherwise, do only a quick check that widetag/lowtag correspond */
2806 #define VERIFY_AGGRESSIVE 2
2807 /* VERIFYING_foo indicates internal state, not a caller's option */
2808 #define VERIFYING_HEAP_OBJECTS 8
2810 // NOTE: This function can produces false failure indications,
2811 // usually related to dynamic space pointing to the stack of a
2812 // dead thread, but there may be other reasons as well.
2814 verify_range(lispobj
*where
, sword_t nwords
, struct verify_state
*state
)
2816 extern int valid_lisp_pointer_p(lispobj
);
2817 boolean is_in_readonly_space
=
2818 (READ_ONLY_SPACE_START
<= (uword_t
)where
&&
2819 where
< read_only_space_free_pointer
);
2820 boolean is_in_immobile_space
= 0;
2821 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2822 is_in_immobile_space
=
2823 (IMMOBILE_SPACE_START
<= (uword_t
)where
&&
2824 where
< immobile_space_free_pointer
);
2827 lispobj
*end
= where
+ nwords
;
2829 for ( ; where
< end
; where
+= count
) {
2830 // Keep track of object boundaries, unless verifying a non-heap space.
2831 if (where
> state
->object_end
&& (state
->flags
& VERIFYING_HEAP_OBJECTS
)) {
2832 state
->object_start
= where
;
2833 state
->object_end
= where
+ OBJECT_SIZE(*where
, where
) - 1;
2836 lispobj thing
= *where
;
2839 if (is_lisp_pointer(thing
)) {
2840 page_index_t page_index
= find_page_index((void*)thing
);
2841 boolean to_immobile_space
= 0;
2842 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2844 (IMMOBILE_SPACE_START
<= thing
&&
2845 thing
< (lispobj
)immobile_fixedobj_free_pointer
) ||
2846 (IMMOBILE_VARYOBJ_SUBSPACE_START
<= thing
&&
2847 thing
< (lispobj
)immobile_space_free_pointer
);
2850 /* unlike lose(), fprintf detects format mismatch, hence the casts */
2851 #define FAIL_IF(what, why) if (what) { \
2852 if (++state->errors > 25) lose("Too many errors"); \
2853 else fprintf(stderr, "Ptr %p @ %"OBJ_FMTX" sees %s\n", \
2854 (void*)(uintptr_t)thing, \
2855 (lispobj)(state->virtual_where ? state->virtual_where : where), \
2858 /* Does it point to the dynamic space? */
2859 if (page_index
!= -1) {
2860 /* If it's within the dynamic space it should point to a used page. */
2861 FAIL_IF(page_free_p(page_index
), "free page");
2862 FAIL_IF(!(page_table
[page_index
].allocated
& OPEN_REGION_PAGE_FLAG
)
2863 && (thing
& (GENCGC_CARD_BYTES
-1)) >= page_bytes_used(page_index
),
2864 "unallocated space");
2865 /* Check that it doesn't point to a forwarding pointer! */
2866 FAIL_IF(*native_pointer(thing
) == 0x01, "forwarding ptr");
2867 /* Check that its not in the RO space as it would then be a
2868 * pointer from the RO to the dynamic space. */
2869 FAIL_IF(is_in_readonly_space
, "dynamic space from RO space");
2870 } else if (to_immobile_space
) {
2871 // the object pointed to must not have been discarded as garbage
2872 FAIL_IF(!other_immediate_lowtag_p(*native_pointer(thing
)) ||
2873 immobile_filler_p(native_pointer(thing
)),
2876 /* Any pointer that points to non-static space is examined further.
2877 * You might think this should scan stacks first as a quick out,
2878 * but that would take time proportional to the number of threads. */
2879 if (page_index
>= 0 || to_immobile_space
) {
2881 /* If aggressive, or to/from immobile space, do a full search
2882 * (as entailed by valid_lisp_pointer_p) */
2883 if ((state
->flags
& VERIFY_AGGRESSIVE
)
2884 || (is_in_immobile_space
|| to_immobile_space
))
2885 valid
= valid_lisp_pointer_p(thing
);
2887 /* Efficiently decide whether 'thing' is plausible.
2888 * This MUST NOT use properly_tagged_descriptor_p() which
2889 * assumes a known good object base address, and would
2890 * "dangerously" scan a code component for embedded funs. */
2891 int lowtag
= lowtag_of(thing
);
2892 if (lowtag
== LIST_POINTER_LOWTAG
)
2893 valid
= is_cons_half(CONS(thing
)->car
)
2894 && is_cons_half(CONS(thing
)->cdr
);
2896 lispobj word
= *native_pointer(thing
);
2897 valid
= other_immediate_lowtag_p(word
) &&
2898 lowtag_for_widetag
[widetag_of(word
)>>2] == lowtag
;
2901 /* If 'thing' points to a stack, we can only hope that the frame
2902 * not clobbered, or the object at 'where' is unreachable. */
2903 FAIL_IF(!valid
&& !is_in_stack_space(thing
), "junk");
2907 int widetag
= widetag_of(thing
);
2908 if (is_lisp_immediate(thing
) || widetag
== NO_TLS_VALUE_MARKER_WIDETAG
) {
2909 /* skip immediates */
2910 } else if (!(other_immediate_lowtag_p(widetag
)
2911 && lowtag_for_widetag
[widetag
>>2])) {
2912 lose("Unhandled widetag %p at %p\n", widetag
, where
);
2913 } else if (unboxed_obj_widetag_p(widetag
)) {
2914 count
= sizetab
[widetag
](where
);
2915 } else switch(widetag
) {
2916 /* boxed or partially boxed objects */
2917 // FIXME: x86-64 can have partially unboxed FINs. The raw words
2918 // are at the moment valid fixnums by blind luck.
2919 case INSTANCE_WIDETAG
:
2920 if (instance_layout(where
)) {
2921 sword_t nslots
= instance_length(thing
) | 1;
2922 lispobj bitmap
= LAYOUT(instance_layout(where
))->bitmap
;
2923 gc_assert(fixnump(bitmap
)
2924 || widetag_of(*native_pointer(bitmap
))==BIGNUM_WIDETAG
);
2925 instance_scan((void (*)(lispobj
*, sword_t
, uword_t
))verify_range
,
2926 where
+1, nslots
, bitmap
, (uintptr_t)state
);
2930 case CODE_HEADER_WIDETAG
:
2932 struct code
*code
= (struct code
*) where
;
2933 sword_t nheader_words
= code_header_words(code
->header
);
2934 /* Scavenge the boxed section of the code data block */
2935 verify_range(where
+ 1, nheader_words
- 1, state
);
2937 /* Scavenge the boxed section of each function
2938 * object in the code data block. */
2939 for_each_simple_fun(i
, fheaderp
, code
, 1, {
2940 #if defined(LISP_FEATURE_COMPACT_INSTANCE_HEADER)
2941 lispobj
__attribute__((unused
)) layout
=
2942 function_layout((lispobj
*)fheaderp
);
2943 gc_assert(!layout
|| layout
== SYMBOL(FUNCTION_LAYOUT
)->value
>> 32);
2945 verify_range(SIMPLE_FUN_SCAV_START(fheaderp
),
2946 SIMPLE_FUN_SCAV_NWORDS(fheaderp
),
2948 count
= nheader_words
+ code_instruction_words(code
->code_size
);
2952 verify_range(where
+ 1, 2, state
);
2953 callee
= fdefn_callee_lispobj((struct fdefn
*)where
);
2954 /* For a more intelligible error, don't say that the word that
2955 * contains an errant pointer is in stack space if it isn't. */
2956 state
->virtual_where
= where
+ 3;
2957 verify_range(&callee
, 1, state
);
2958 state
->virtual_where
= 0;
2959 count
= ALIGN_UP(sizeof (struct fdefn
)/sizeof(lispobj
), 2);
2964 static uword_t
verify_space(lispobj start
, lispobj
* end
, uword_t flags
) {
2965 struct verify_state state
;
2966 memset(&state
, 0, sizeof state
);
2967 state
.flags
= flags
;
2968 verify_range((lispobj
*)start
, end
-(lispobj
*)start
, &state
);
2969 if (state
.errors
) lose("verify failed: %d error(s)", state
.errors
);
2972 static uword_t
verify_gen_aux(lispobj start
, lispobj
* end
, struct verify_state
* state
)
2974 verify_range((lispobj
*)start
, end
-(lispobj
*)start
, state
);
2977 static void verify_generation(generation_index_t generation
, uword_t flags
)
2979 struct verify_state state
;
2980 memset(&state
, 0, sizeof state
);
2981 state
.flags
= flags
;
2982 walk_generation((uword_t(*)(lispobj
*,lispobj
*,uword_t
))verify_gen_aux
,
2983 generation
, (uword_t
)&state
);
2984 if (state
.errors
) lose("verify failed: %d error(s)", state
.errors
);
2987 void verify_gc(uword_t flags
)
2989 int verbose
= flags
& VERIFY_VERBOSE
;
2991 flags
|= VERIFYING_HEAP_OBJECTS
;
2993 #ifdef LISP_FEATURE_IMMOBILE_SPACE
2995 // Try this verification if immobile-space was compiled with extra debugging.
2996 // But weak symbols don't work on macOS.
2997 extern void __attribute__((weak
)) check_varyobj_pages();
2998 if (&check_varyobj_pages
) check_varyobj_pages();
3001 printf("Verifying immobile space\n");
3002 verify_space(IMMOBILE_SPACE_START
, immobile_fixedobj_free_pointer
, flags
);
3003 verify_space(IMMOBILE_VARYOBJ_SUBSPACE_START
, immobile_space_free_pointer
, flags
);
3007 printf("Verifying binding stacks\n");
3008 for_each_thread(th
) {
3009 verify_space((lispobj
)th
->binding_stack_start
,
3010 (lispobj
*)get_binding_stack_pointer(th
),
3011 flags
^ VERIFYING_HEAP_OBJECTS
);
3012 #ifdef LISP_FEATURE_SB_THREAD
3013 verify_space((lispobj
)(th
+1),
3014 (lispobj
*)(SymbolValue(FREE_TLS_INDEX
,0)
3015 + (char*)((union per_thread_data
*)th
)->dynamic_values
),
3016 flags
^ VERIFYING_HEAP_OBJECTS
);
3020 printf("Verifying RO space\n");
3021 verify_space(READ_ONLY_SPACE_START
, read_only_space_free_pointer
, flags
);
3023 printf("Verifying static space\n");
3024 verify_space(STATIC_SPACE_START
, static_space_free_pointer
, flags
);
3026 printf("Verifying dynamic space\n");
3027 verify_generation(-1, flags
);
3030 /* Call 'proc' with pairs of addresses demarcating ranges in the
3031 * specified generation.
3032 * Stop if any invocation returns non-zero, and return that value */
3034 walk_generation(uword_t (*proc
)(lispobj
*,lispobj
*,uword_t
),
3035 generation_index_t generation
, uword_t extra
)
3038 int genmask
= generation
>= 0 ? 1 << generation
: ~0;
3040 for (i
= 0; i
< last_free_page
; i
++) {
3041 if ((page_bytes_used(i
) != 0) && ((1 << page_table
[i
].gen
) & genmask
)) {
3042 page_index_t last_page
;
3044 /* This should be the start of a contiguous block */
3045 gc_assert(page_starts_contiguous_block_p(i
));
3047 /* Need to find the full extent of this contiguous block in case
3048 objects span pages. */
3050 /* Now work forward until the end of this contiguous area is
3052 for (last_page
= i
; ;last_page
++)
3053 /* Check whether this is the last page in this contiguous
3055 if (page_ends_contiguous_block_p(last_page
, page_table
[i
].gen
))
3059 proc((lispobj
*)page_address(i
),
3060 (lispobj
*)(page_bytes_used(last_page
) + page_address(last_page
)),
3062 if (result
) return result
;
3070 /* Check that all the free space is zero filled. */
3072 verify_zero_fill(void)
3076 for (page
= 0; page
< last_free_page
; page
++) {
3077 if (page_free_p(page
)) {
3078 /* The whole page should be zero filled. */
3079 sword_t
*start_addr
= (sword_t
*)page_address(page
);
3081 for (i
= 0; i
< (sword_t
)GENCGC_CARD_BYTES
/N_WORD_BYTES
; i
++) {
3082 if (start_addr
[i
] != 0) {
3083 lose("free page not zero at %p\n", start_addr
+ i
);
3087 sword_t free_bytes
= GENCGC_CARD_BYTES
- page_bytes_used(page
);
3088 if (free_bytes
> 0) {
3089 sword_t
*start_addr
=
3090 (sword_t
*)(page_address(page
) + page_bytes_used(page
));
3091 sword_t size
= free_bytes
/ N_WORD_BYTES
;
3093 for (i
= 0; i
< size
; i
++) {
3094 if (start_addr
[i
] != 0) {
3095 lose("free region not zero at %p\n", start_addr
+ i
);
3103 /* External entry point for verify_zero_fill */
3105 gencgc_verify_zero_fill(void)
3107 /* Flush the alloc regions updating the tables. */
3108 gc_alloc_update_all_page_tables(1);
3109 SHOW("verifying zero fill");
3113 /* Write-protect all the dynamic boxed pages in the given generation. */
3115 write_protect_generation_pages(generation_index_t generation
)
3119 gc_assert(generation
< SCRATCH_GENERATION
);
3121 for (start
= 0; start
< last_free_page
; start
++) {
3122 if (protect_page_p(start
, generation
)) {
3126 /* Note the page as protected in the page tables. */
3127 page_table
[start
].write_protected
= 1;
3129 for (last
= start
+ 1; last
< last_free_page
; last
++) {
3130 if (!protect_page_p(last
, generation
))
3132 page_table
[last
].write_protected
= 1;
3135 page_start
= page_address(start
);
3137 os_protect(page_start
,
3138 npage_bytes(last
- start
),
3139 OS_VM_PROT_READ
| OS_VM_PROT_EXECUTE
);
3145 if (gencgc_verbose
> 1) {
3147 "/write protected %d of %d pages in generation %d\n",
3148 count_write_protect_generation_pages(generation
),
3149 count_generation_pages(generation
),
3154 #if !GENCGC_IS_PRECISE
3156 preserve_context_registers (void (*proc
)(os_context_register_t
), os_context_t
*c
)
3158 #ifdef LISP_FEATURE_SB_THREAD
3160 /* On Darwin the signal context isn't a contiguous block of memory,
3161 * so just preserve_pointering its contents won't be sufficient.
3163 #if defined(LISP_FEATURE_DARWIN)||defined(LISP_FEATURE_WIN32)
3164 #if defined LISP_FEATURE_X86
3165 proc(*os_context_register_addr(c
,reg_EAX
));
3166 proc(*os_context_register_addr(c
,reg_ECX
));
3167 proc(*os_context_register_addr(c
,reg_EDX
));
3168 proc(*os_context_register_addr(c
,reg_EBX
));
3169 proc(*os_context_register_addr(c
,reg_ESI
));
3170 proc(*os_context_register_addr(c
,reg_EDI
));
3171 proc(*os_context_pc_addr(c
));
3172 #elif defined LISP_FEATURE_X86_64
3173 proc(*os_context_register_addr(c
,reg_RAX
));
3174 proc(*os_context_register_addr(c
,reg_RCX
));
3175 proc(*os_context_register_addr(c
,reg_RDX
));
3176 proc(*os_context_register_addr(c
,reg_RBX
));
3177 proc(*os_context_register_addr(c
,reg_RSI
));
3178 proc(*os_context_register_addr(c
,reg_RDI
));
3179 proc(*os_context_register_addr(c
,reg_R8
));
3180 proc(*os_context_register_addr(c
,reg_R9
));
3181 proc(*os_context_register_addr(c
,reg_R10
));
3182 proc(*os_context_register_addr(c
,reg_R11
));
3183 proc(*os_context_register_addr(c
,reg_R12
));
3184 proc(*os_context_register_addr(c
,reg_R13
));
3185 proc(*os_context_register_addr(c
,reg_R14
));
3186 proc(*os_context_register_addr(c
,reg_R15
));
3187 proc(*os_context_pc_addr(c
));
3189 #error "preserve_context_registers needs to be tweaked for non-x86 Darwin"
3192 #if !defined(LISP_FEATURE_WIN32)
3193 for(ptr
= ((void **)(c
+1))-1; ptr
>=(void **)c
; ptr
--) {
3194 proc((os_context_register_t
)*ptr
);
3197 #endif // LISP_FEATURE_SB_THREAD
3202 move_pinned_pages_to_newspace()
3206 /* scavenge() will evacuate all oldspace pages, but no newspace
3207 * pages. Pinned pages are precisely those pages which must not
3208 * be evacuated, so move them to newspace directly. */
3210 for (i
= 0; i
< last_free_page
; i
++) {
3211 if (page_table
[i
].dont_move
&&
3212 /* dont_move is cleared lazily, so test the 'gen' field as well. */
3213 page_table
[i
].gen
== from_space
) {
3214 if (page_table
[i
].has_pins
) {
3215 // do not move to newspace after all, this will be word-wiped
3218 page_table
[i
].gen
= new_space
;
3219 /* And since we're moving the pages wholesale, also adjust
3220 * the generation allocation counters. */
3221 int used
= page_bytes_used(i
);
3222 generations
[new_space
].bytes_allocated
+= used
;
3223 generations
[from_space
].bytes_allocated
-= used
;
3228 #if defined(__GNUC__) && defined(ADDRESS_SANITIZER)
3229 #define NO_SANITIZE_ADDRESS __attribute__((no_sanitize_address))
3231 #define NO_SANITIZE_ADDRESS
3234 /* Garbage collect a generation. If raise is 0 then the remains of the
3235 * generation are not raised to the next generation. */
3236 static void NO_SANITIZE_ADDRESS
3237 garbage_collect_generation(generation_index_t generation
, int raise
)
3242 gc_assert(generation
<= PSEUDO_STATIC_GENERATION
);
3244 /* The oldest generation can't be raised. */
3245 gc_assert(!raise
|| generation
< HIGHEST_NORMAL_GENERATION
);
3247 /* Check that weak hash tables were processed in the previous GC. */
3248 gc_assert(weak_hash_tables
== NULL
);
3249 gc_assert(weak_AND_hash_tables
== NULL
);
3251 /* Initialize the weak pointer list. */
3252 weak_pointers
= NULL
;
3254 /* When a generation is not being raised it is transported to a
3255 * temporary generation (NUM_GENERATIONS), and lowered when
3256 * done. Set up this new generation. There should be no pages
3257 * allocated to it yet. */
3259 gc_assert(generations
[SCRATCH_GENERATION
].bytes_allocated
== 0);
3262 /* Set the global src and dest. generations */
3263 if (generation
< PSEUDO_STATIC_GENERATION
) {
3265 from_space
= generation
;
3267 new_space
= generation
+1;
3269 new_space
= SCRATCH_GENERATION
;
3271 /* Change to a new space for allocation, resetting the alloc_start_page */
3272 gc_alloc_generation
= new_space
;
3274 bzero(generations
[new_space
].alloc_start_page_
,
3275 sizeof generations
[new_space
].alloc_start_page_
);
3277 generations
[new_space
].alloc_start_page
= 0;
3278 generations
[new_space
].alloc_unboxed_start_page
= 0;
3279 generations
[new_space
].alloc_large_start_page
= 0;
3282 #ifdef PIN_GRANULARITY_LISPOBJ
3283 hopscotch_reset(&pinned_objects
);
3285 /* Before any pointers are preserved, the dont_move flags on the
3286 * pages need to be cleared. */
3287 /* FIXME: consider moving this bitmap into its own range of words,
3288 * out of the page table. Then we can just bzero() it.
3289 * This will also obviate the extra test at the comment
3290 * "dont_move is cleared lazily" in move_pinned_pages_to_newspace().
3292 for (i
= 0; i
< last_free_page
; i
++)
3293 if(page_table
[i
].gen
==from_space
)
3294 page_table
[i
].dont_move
= 0;
3296 /* Un-write-protect the old-space pages. This is essential for the
3297 * promoted pages as they may contain pointers into the old-space
3298 * which need to be scavenged. It also helps avoid unnecessary page
3299 * faults as forwarding pointers are written into them. They need to
3300 * be un-protected anyway before unmapping later. */
3301 if (ENABLE_PAGE_PROTECTION
)
3302 unprotect_oldspace();
3304 } else { // "full" [sic] GC
3306 /* This is a full mark-and-sweep of all generations without compacting
3307 * and without returning free space to the allocator. The intent is to
3308 * break chains of objects causing accidental reachability.
3309 * Subsequent GC cycles will compact and reclaims space as usual. */
3310 from_space
= new_space
= -1;
3312 // Unprotect the dynamic space but leave page_table bits alone
3313 if (ENABLE_PAGE_PROTECTION
)
3314 os_protect(page_address(0), npage_bytes(last_free_page
),
3317 // Allocate pages from dynamic space for the work queue.
3318 extern void prepare_for_full_mark_phase();
3319 prepare_for_full_mark_phase();
3323 /* Scavenge the stacks' conservative roots. */
3325 /* there are potentially two stacks for each thread: the main
3326 * stack, which may contain Lisp pointers, and the alternate stack.
3327 * We don't ever run Lisp code on the altstack, but it may
3328 * host a sigcontext with lisp objects in it */
3330 /* what we need to do: (1) find the stack pointer for the main
3331 * stack; scavenge it (2) find the interrupt context on the
3332 * alternate stack that might contain lisp values, and scavenge
3335 /* we assume that none of the preceding applies to the thread that
3336 * initiates GC. If you ever call GC from inside an altstack
3337 * handler, you will lose. */
3339 #if !GENCGC_IS_PRECISE
3340 /* And if we're saving a core, there's no point in being conservative. */
3341 if (conservative_stack
) {
3342 for_each_thread(th
) {
3344 void **esp
=(void **)-1;
3345 if (th
->state
== STATE_DEAD
)
3347 # if defined(LISP_FEATURE_SB_SAFEPOINT)
3348 /* Conservative collect_garbage is always invoked with a
3349 * foreign C call or an interrupt handler on top of every
3350 * existing thread, so the stored SP in each thread
3351 * structure is valid, no matter which thread we are looking
3352 * at. For threads that were running Lisp code, the pitstop
3353 * and edge functions maintain this value within the
3354 * interrupt or exception handler. */
3355 esp
= os_get_csp(th
);
3356 assert_on_stack(th
, esp
);
3358 /* In addition to pointers on the stack, also preserve the
3359 * return PC, the only value from the context that we need
3360 * in addition to the SP. The return PC gets saved by the
3361 * foreign call wrapper, and removed from the control stack
3362 * into a register. */
3363 preserve_pointer(th
->pc_around_foreign_call
);
3365 /* And on platforms with interrupts: scavenge ctx registers. */
3367 /* Disabled on Windows, because it does not have an explicit
3368 * stack of `interrupt_contexts'. The reported CSP has been
3369 * chosen so that the current context on the stack is
3370 * covered by the stack scan. See also set_csp_from_context(). */
3371 # ifndef LISP_FEATURE_WIN32
3372 if (th
!= arch_os_get_current_thread()) {
3373 long k
= fixnum_value(
3374 read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3376 preserve_context_registers((void(*)(os_context_register_t
))preserve_pointer
,
3377 th
->interrupt_contexts
[--k
]);
3380 # elif defined(LISP_FEATURE_SB_THREAD)
3382 if(th
==arch_os_get_current_thread()) {
3383 /* Somebody is going to burn in hell for this, but casting
3384 * it in two steps shuts gcc up about strict aliasing. */
3385 esp
= (void **)((void *)&raise
);
3388 free
=fixnum_value(read_TLS(FREE_INTERRUPT_CONTEXT_INDEX
,th
));
3389 for(i
=free
-1;i
>=0;i
--) {
3390 os_context_t
*c
=th
->interrupt_contexts
[i
];
3391 esp1
= (void **) *os_context_register_addr(c
,reg_SP
);
3392 if (esp1
>=(void **)th
->control_stack_start
&&
3393 esp1
<(void **)th
->control_stack_end
) {
3394 if(esp1
<esp
) esp
=esp1
;
3395 preserve_context_registers((void(*)(os_context_register_t
))preserve_pointer
,
3401 esp
= (void **)((void *)&raise
);
3403 if (!esp
|| esp
== (void*) -1)
3404 lose("garbage_collect: no SP known for thread %x (OS %x)",
3406 for (ptr
= ((void **)th
->control_stack_end
)-1; ptr
>= esp
; ptr
--) {
3407 preserve_pointer(*ptr
);
3412 /* Non-x86oid systems don't have "conservative roots" as such, but
3413 * the same mechanism is used for objects pinned for use by alien
3415 for_each_thread(th
) {
3416 lispobj pin_list
= read_TLS(PINNED_OBJECTS
,th
);
3417 while (pin_list
!= NIL
) {
3418 preserve_pointer((void*)(CONS(pin_list
)->car
));
3419 pin_list
= CONS(pin_list
)->cdr
;
3425 if (gencgc_verbose
> 1) {
3426 sword_t num_dont_move_pages
= count_dont_move_pages();
3428 "/non-movable pages due to conservative pointers = %ld (%lu bytes)\n",
3429 num_dont_move_pages
,
3430 npage_bytes(num_dont_move_pages
));
3434 /* Now that all of the pinned (dont_move) pages are known, and
3435 * before we start to scavenge (and thus relocate) objects,
3436 * relocate the pinned pages to newspace, so that the scavenger
3437 * will not attempt to relocate their contents. */
3439 move_pinned_pages_to_newspace();
3441 /* Scavenge all the rest of the roots. */
3443 #if GENCGC_IS_PRECISE
3445 * If not x86, we need to scavenge the interrupt context(s) and the
3450 for_each_thread(th
) {
3451 scavenge_interrupt_contexts(th
);
3452 scavenge_control_stack(th
);
3455 # ifdef LISP_FEATURE_SB_SAFEPOINT
3456 /* In this case, scrub all stacks right here from the GCing thread
3457 * instead of doing what the comment below says. Suboptimal, but
3460 scrub_thread_control_stack(th
);
3462 /* Scrub the unscavenged control stack space, so that we can't run
3463 * into any stale pointers in a later GC (this is done by the
3464 * stop-for-gc handler in the other threads). */
3465 scrub_control_stack();
3470 /* Scavenge the Lisp functions of the interrupt handlers, taking
3471 * care to avoid SIG_DFL and SIG_IGN. */
3472 for (i
= 0; i
< NSIG
; i
++) {
3473 union interrupt_handler handler
= interrupt_handlers
[i
];
3474 if (!ARE_SAME_HANDLER(handler
.c
, SIG_IGN
) &&
3475 !ARE_SAME_HANDLER(handler
.c
, SIG_DFL
) &&
3476 is_lisp_pointer(handler
.lisp
)) {
3478 scavenge((lispobj
*)(interrupt_handlers
+ i
), 1);
3480 gc_mark_obj(handler
.lisp
);
3483 /* Scavenge the binding stacks. */
3486 for_each_thread(th
) {
3487 scav_binding_stack((lispobj
*)th
->binding_stack_start
,
3488 (lispobj
*)get_binding_stack_pointer(th
),
3489 compacting_p() ? 0 : gc_mark_obj
);
3490 #ifdef LISP_FEATURE_SB_THREAD
3491 /* do the tls as well */
3493 len
=(SymbolValue(FREE_TLS_INDEX
,0) >> WORD_SHIFT
) -
3494 (sizeof (struct thread
))/(sizeof (lispobj
));
3496 scavenge((lispobj
*) (th
+1), len
);
3498 gc_mark_range((lispobj
*) (th
+1), len
);
3503 if (!compacting_p()) {
3504 extern void execute_full_mark_phase();
3505 extern void execute_full_sweep_phase();
3506 execute_full_mark_phase();
3507 execute_full_sweep_phase();
3511 /* Scavenge static space. */
3512 if (gencgc_verbose
> 1) {
3514 "/scavenge static space: %d bytes\n",
3515 (uword_t
)static_space_free_pointer
- STATIC_SPACE_START
));
3517 heap_scavenge((lispobj
*)STATIC_SPACE_START
, static_space_free_pointer
);
3519 /* All generations but the generation being GCed need to be
3520 * scavenged. The new_space generation needs special handling as
3521 * objects may be moved in - it is handled separately below. */
3522 #ifdef LISP_FEATURE_IMMOBILE_SPACE
3523 scavenge_immobile_roots(generation
+1, SCRATCH_GENERATION
);
3525 scavenge_generations(generation
+1, PSEUDO_STATIC_GENERATION
);
3527 #ifdef LISP_FEATURE_SB_TRACEROOT
3528 if (gc_object_watcher
) scavenge(&gc_object_watcher
, 1);
3530 scavenge_pinned_ranges();
3531 /* The Lisp start function is stored in the core header, not a static
3532 * symbol. It is passed to gc_and_save() in this C variable */
3533 if (lisp_init_function
) scavenge(&lisp_init_function
, 1);
3535 /* Finally scavenge the new_space generation. Keep going until no
3536 * more objects are moved into the new generation */
3537 scavenge_newspace_generation(new_space
);
3539 /* FIXME: I tried reenabling this check when debugging unrelated
3540 * GC weirdness ca. sbcl-0.6.12.45, and it failed immediately.
3541 * Since the current GC code seems to work well, I'm guessing that
3542 * this debugging code is just stale, but I haven't tried to
3543 * figure it out. It should be figured out and then either made to
3544 * work or just deleted. */
3546 #define RESCAN_CHECK 0
3548 /* As a check re-scavenge the newspace once; no new objects should
3551 os_vm_size_t old_bytes_allocated
= bytes_allocated
;
3552 os_vm_size_t bytes_allocated
;
3554 /* Start with a full scavenge. */
3555 scavenge_newspace_generation_one_scan(new_space
);
3557 /* Flush the current regions, updating the tables. */
3558 gc_alloc_update_all_page_tables(1);
3560 bytes_allocated
= bytes_allocated
- old_bytes_allocated
;
3562 if (bytes_allocated
!= 0) {
3563 lose("Rescan of new_space allocated %d more bytes.\n",
3569 scan_binding_stack();
3570 scan_weak_hash_tables(weak_ht_alivep_funs
);
3571 scan_weak_pointers();
3572 wipe_nonpinned_words();
3573 #ifdef LISP_FEATURE_IMMOBILE_SPACE
3574 // Do this last, because until wipe_nonpinned_words() happens,
3575 // not all page table entries have the 'gen' value updated,
3576 // which we need to correctly find all old->young pointers.
3577 sweep_immobile_space(raise
);
3580 gc_assert(boxed_region
.last_page
< 0);
3581 gc_assert(unboxed_region
.last_page
< 0);
3583 gc_assert(gc_alloc_region
[2].last_page
< 0);
3585 #ifdef PIN_GRANULARITY_LISPOBJ
3586 hopscotch_log_stats(&pinned_objects
, "pins");
3589 /* Free the pages in oldspace, but not those marked dont_move. */
3592 /* If the GC is not raising the age then lower the generation back
3593 * to its normal generation number */
3595 for (i
= 0; i
< last_free_page
; i
++)
3596 if ((page_bytes_used(i
) != 0)
3597 && (page_table
[i
].gen
== SCRATCH_GENERATION
))
3598 page_table
[i
].gen
= generation
;
3599 gc_assert(generations
[generation
].bytes_allocated
== 0);
3600 generations
[generation
].bytes_allocated
=
3601 generations
[SCRATCH_GENERATION
].bytes_allocated
;
3602 generations
[SCRATCH_GENERATION
].bytes_allocated
= 0;
3605 /* Reset the alloc_start_page for generation. */
3607 bzero(generations
[generation
].alloc_start_page_
,
3608 sizeof generations
[generation
].alloc_start_page_
);
3610 generations
[generation
].alloc_start_page
= 0;
3611 generations
[generation
].alloc_unboxed_start_page
= 0;
3612 generations
[generation
].alloc_large_start_page
= 0;
3615 /* Set the new gc trigger for the GCed generation. */
3616 generations
[generation
].gc_trigger
=
3617 generations
[generation
].bytes_allocated
3618 + generations
[generation
].bytes_consed_between_gc
;
3621 generations
[generation
].num_gc
= 0;
3623 ++generations
[generation
].num_gc
;
3626 if (generation
>= verify_gens
) {
3627 if (gencgc_verbose
) {
3635 find_last_free_page(void)
3637 page_index_t last_page
= -1, i
;
3639 for (i
= 0; i
< last_free_page
; i
++)
3640 if (page_bytes_used(i
) != 0)
3643 /* The last free page is actually the first available page */
3644 return last_page
+ 1;
3648 update_dynamic_space_free_pointer(void)
3650 set_alloc_pointer((lispobj
)(page_address(find_last_free_page())));
3654 remap_page_range (page_index_t from
, page_index_t to
)
3656 /* There's a mysterious Solaris/x86 problem with using mmap
3657 * tricks for memory zeroing. See sbcl-devel thread
3658 * "Re: patch: standalone executable redux".
3660 #if defined(LISP_FEATURE_SUNOS)
3661 zero_and_mark_pages(from
, to
);
3664 release_granularity
= gencgc_release_granularity
/GENCGC_CARD_BYTES
,
3665 release_mask
= release_granularity
-1,
3667 aligned_from
= (from
+release_mask
)&~release_mask
,
3668 aligned_end
= (end
&~release_mask
);
3670 if (aligned_from
< aligned_end
) {
3671 zero_pages_with_mmap(aligned_from
, aligned_end
-1);
3672 if (aligned_from
!= from
)
3673 zero_and_mark_pages(from
, aligned_from
-1);
3674 if (aligned_end
!= end
)
3675 zero_and_mark_pages(aligned_end
, end
-1);
3677 zero_and_mark_pages(from
, to
);
3683 remap_free_pages (page_index_t from
, page_index_t to
)
3685 page_index_t first_page
, last_page
;
3687 for (first_page
= from
; first_page
<= to
; first_page
++) {
3688 if (!page_free_p(first_page
) || !page_need_to_zero(first_page
))
3691 last_page
= first_page
+ 1;
3692 while (page_free_p(last_page
) &&
3693 (last_page
<= to
) &&
3694 (page_need_to_zero(last_page
)))
3697 remap_page_range(first_page
, last_page
-1);
3699 first_page
= last_page
;
3703 generation_index_t small_generation_limit
= 1;
3705 /* GC all generations newer than last_gen, raising the objects in each
3706 * to the next older generation - we finish when all generations below
3707 * last_gen are empty. Then if last_gen is due for a GC, or if
3708 * last_gen==NUM_GENERATIONS (the scratch generation? eh?) we GC that
3709 * too. The valid range for last_gen is: 0,1,...,NUM_GENERATIONS.
3711 * We stop collecting at gencgc_oldest_gen_to_gc, even if this is less than
3712 * last_gen (oh, and note that by default it is NUM_GENERATIONS-1) */
3714 collect_garbage(generation_index_t last_gen
)
3716 generation_index_t gen
= 0, i
;
3717 boolean gc_mark_only
= 0;
3718 int raise
, more
= 0;
3720 /* The largest value of last_free_page seen since the time
3721 * remap_free_pages was called. */
3722 static page_index_t high_water_mark
= 0;
3724 FSHOW((stderr
, "/entering collect_garbage(%d)\n", last_gen
));
3725 log_generation_stats(gc_logfile
, "=== GC Start ===");
3729 if (last_gen
== 1+PSEUDO_STATIC_GENERATION
) {
3730 // Pseudostatic space undergoes a non-moving collection
3731 last_gen
= PSEUDO_STATIC_GENERATION
;
3733 } else if (last_gen
> 1+PSEUDO_STATIC_GENERATION
) {
3734 // This is a completely non-obvious thing to do, but whatever...
3736 "/collect_garbage: last_gen = %d, doing a level 0 GC\n",
3741 /* Flush the alloc regions updating the tables. */
3742 gc_alloc_update_all_page_tables(1);
3744 /* Verify the new objects created by Lisp code. */
3745 if (pre_verify_gen_0
) {
3746 FSHOW((stderr
, "pre-checking generation 0\n"));
3747 verify_generation(0, 0);
3750 if (gencgc_verbose
> 1)
3751 print_generation_stats();
3753 #ifdef LISP_FEATURE_IMMOBILE_SPACE
3754 /* Immobile space generation bits are lazily updated for gen0
3755 (not touched on every object allocation) so do it now */
3756 update_immobile_nursery_bits();
3760 garbage_collect_generation(PSEUDO_STATIC_GENERATION
, 0);
3765 /* Collect the generation. */
3767 if (more
|| (gen
>= gencgc_oldest_gen_to_gc
)) {
3768 /* Never raise the oldest generation. Never raise the extra generation
3769 * collected due to more-flag. */
3775 || (generations
[gen
].num_gc
>= generations
[gen
].number_of_gcs_before_promotion
);
3776 /* If we would not normally raise this one, but we're
3777 * running low on space in comparison to the object-sizes
3778 * we've been seeing, raise it and collect the next one
3780 if (!raise
&& gen
== last_gen
) {
3781 more
= (2*large_allocation
) >= (dynamic_space_size
- bytes_allocated
);
3786 if (gencgc_verbose
> 1) {
3788 "starting GC of generation %d with raise=%d alloc=%d trig=%d GCs=%d\n",
3791 generations
[gen
].bytes_allocated
,
3792 generations
[gen
].gc_trigger
,
3793 generations
[gen
].num_gc
));
3796 /* If an older generation is being filled, then update its
3799 generations
[gen
+1].cum_sum_bytes_allocated
+=
3800 generations
[gen
+1].bytes_allocated
;
3803 garbage_collect_generation(gen
, raise
);
3805 /* Reset the memory age cum_sum. */
3806 generations
[gen
].cum_sum_bytes_allocated
= 0;
3808 if (gencgc_verbose
> 1) {
3809 FSHOW((stderr
, "GC of generation %d finished:\n", gen
));
3810 print_generation_stats();
3814 } while ((gen
<= gencgc_oldest_gen_to_gc
)
3815 && ((gen
< last_gen
)
3818 && (generations
[gen
].bytes_allocated
3819 > generations
[gen
].gc_trigger
)
3820 && (generation_average_age(gen
)
3821 > generations
[gen
].minimum_age_before_gc
))));
3823 /* Now if gen-1 was raised all generations before gen are empty.
3824 * If it wasn't raised then all generations before gen-1 are empty.
3826 * Now objects within this gen's pages cannot point to younger
3827 * generations unless they are written to. This can be exploited
3828 * by write-protecting the pages of gen; then when younger
3829 * generations are GCed only the pages which have been written
3834 gen_to_wp
= gen
- 1;
3836 /* There's not much point in WPing pages in generation 0 as it is
3837 * never scavenged (except promoted pages). */
3838 if ((gen_to_wp
> 0) && ENABLE_PAGE_PROTECTION
) {
3839 /* Check that they are all empty. */
3840 for (i
= 0; i
< gen_to_wp
; i
++) {
3841 if (generations
[i
].bytes_allocated
)
3842 lose("trying to write-protect gen. %d when gen. %d nonempty\n",
3845 write_protect_generation_pages(gen_to_wp
);
3848 /* Set gc_alloc() back to generation 0. The current regions should
3849 * be flushed after the above GCs. */
3850 gc_assert(boxed_region
.free_pointer
== boxed_region
.start_addr
);
3851 gc_alloc_generation
= 0;
3853 /* Save the high-water mark before updating last_free_page */
3854 if (last_free_page
> high_water_mark
)
3855 high_water_mark
= last_free_page
;
3857 update_dynamic_space_free_pointer();
3859 /* Update auto_gc_trigger. Make sure we trigger the next GC before
3860 * running out of heap! */
3861 if (bytes_consed_between_gcs
<= (dynamic_space_size
- bytes_allocated
))
3862 auto_gc_trigger
= bytes_allocated
+ bytes_consed_between_gcs
;
3864 auto_gc_trigger
= bytes_allocated
+ (dynamic_space_size
- bytes_allocated
)/2;
3866 if(gencgc_verbose
) {
3867 #define MESSAGE ("Next gc when %"OS_VM_SIZE_FMT" bytes have been consed\n")
3870 // fprintf() can - and does - cause deadlock here.
3871 // snprintf() seems to work fine.
3872 n
= snprintf(buf
, sizeof buf
, MESSAGE
, auto_gc_trigger
);
3873 ignore_value(write(2, buf
, n
));
3877 /* If we did a big GC (arbitrarily defined as gen > 1), release memory
3880 if (gen
> small_generation_limit
) {
3881 if (last_free_page
> high_water_mark
)
3882 high_water_mark
= last_free_page
;
3883 remap_free_pages(0, high_water_mark
);
3884 high_water_mark
= 0;
3887 large_allocation
= 0;
3889 #ifdef LISP_FEATURE_IMMOBILE_SPACE
3890 write_protect_immobile_space();
3894 #ifdef LISP_FEATURE_SB_TRACEROOT
3895 if (gc_object_watcher
) {
3896 extern void gc_prove_liveness(void(*)(), lispobj
, int, uword_t
*, int);
3897 gc_prove_liveness(preserve_context_registers
,
3899 gc_n_stack_pins
, pinned_objects
.keys
,
3900 gc_traceroot_criterion
);
3904 log_generation_stats(gc_logfile
, "=== GC End ===");
3905 SHOW("returning from collect_garbage");
3908 /* Initialization of gencgc metadata is split into three steps:
3909 * 1. gc_init() - allocation of a fixed-address space via mmap(),
3910 * failing which there's no reason to go on. (safepoint only)
3911 * 2. gc_allocate_ptes() - page table entries
3912 * 3. gencgc_pickup_dynamic() - calculation of scan start offsets
3913 * Steps (2) and (3) are combined in self-build because there is
3914 * no PAGE_TABLE_CORE_ENTRY_TYPE_CODE core entry. */
3918 #if defined(LISP_FEATURE_SB_SAFEPOINT)
3923 void gc_allocate_ptes()
3927 /* Compute the number of pages needed for the dynamic space.
3928 * Dynamic space size should be aligned on page size. */
3929 page_table_pages
= dynamic_space_size
/GENCGC_CARD_BYTES
;
3930 gc_assert(dynamic_space_size
== npage_bytes(page_table_pages
));
3932 /* Default nursery size to 5% of the total dynamic space size,
3934 bytes_consed_between_gcs
= dynamic_space_size
/(os_vm_size_t
)20;
3935 if (bytes_consed_between_gcs
< (1024*1024))
3936 bytes_consed_between_gcs
= 1024*1024;
3938 /* The page_table is allocated using "calloc" to zero-initialize it.
3939 * The C library typically implements this efficiently with mmap() if the
3940 * size is large enough. To further avoid touching each page structure
3941 * until first use, FREE_PAGE_FLAG must be 0, statically asserted here:
3944 /* Compile time assertion: If triggered, declares an array
3945 * of dimension -1 forcing a syntax error. The intent of the
3946 * assignment is to avoid an "unused variable" warning. */
3947 char __attribute__((unused
)) assert_free_page_flag_0
[(FREE_PAGE_FLAG
) ? -1 : 1];
3949 /* An extra struct exists as the end as a sentinel. Its 'scan_start_offset'
3950 * and 'bytes_used' must be zero.
3951 * Doing so avoids testing in page_ends_contiguous_block_p() whether the
3952 * next page_index is within bounds, and whether that page contains data.
3954 page_table
= calloc(1+page_table_pages
, sizeof(struct page
));
3955 gc_assert(page_table
);
3958 #ifdef PIN_GRANULARITY_LISPOBJ
3959 hopscotch_create(&pinned_objects
, HOPSCOTCH_HASH_FUN_DEFAULT
, 0 /* hashset */,
3960 32 /* logical bin count */, 0 /* default range */);
3963 scavtab
[WEAK_POINTER_WIDETAG
] = scav_weak_pointer
;
3965 bytes_allocated
= 0;
3967 /* Initialize the generations. */
3968 for (i
= 0; i
< NUM_GENERATIONS
; i
++) {
3969 generations
[i
].alloc_start_page
= 0;
3970 generations
[i
].alloc_unboxed_start_page
= 0;
3971 generations
[i
].alloc_large_start_page
= 0;
3972 generations
[i
].bytes_allocated
= 0;
3973 generations
[i
].gc_trigger
= 2000000;
3974 generations
[i
].num_gc
= 0;
3975 generations
[i
].cum_sum_bytes_allocated
= 0;
3976 /* the tune-able parameters */
3977 generations
[i
].bytes_consed_between_gc
3978 = bytes_consed_between_gcs
/(os_vm_size_t
)HIGHEST_NORMAL_GENERATION
;
3979 generations
[i
].number_of_gcs_before_promotion
= 1;
3980 generations
[i
].minimum_age_before_gc
= 0.75;
3983 /* Initialize gc_alloc. */
3984 gc_alloc_generation
= 0;
3985 gc_set_region_empty(&boxed_region
);
3986 gc_set_region_empty(&unboxed_region
);
3988 gc_set_region_empty(&code_region
);
3994 /* Pick up the dynamic space from after a core load.
3996 * The ALLOCATION_POINTER points to the end of the dynamic space.
4000 gencgc_pickup_dynamic(void)
4002 page_index_t page
= 0;
4003 char *alloc_ptr
= (char *)get_alloc_pointer();
4004 lispobj
*prev
=(lispobj
*)page_address(page
);
4005 generation_index_t gen
= PSEUDO_STATIC_GENERATION
;
4007 bytes_allocated
= 0;
4010 lispobj
*first
,*ptr
= (lispobj
*)page_address(page
);
4012 if (!gencgc_partial_pickup
|| !page_free_p(page
)) {
4013 page_bytes_t bytes_used
= GENCGC_CARD_BYTES
;
4014 /* It is possible, though rare, for the saved page table
4015 * to contain free pages below alloc_ptr. */
4016 page_table
[page
].gen
= gen
;
4017 if (gencgc_partial_pickup
)
4018 bytes_used
= page_bytes_used(page
);
4020 set_page_bytes_used(page
, GENCGC_CARD_BYTES
);
4021 page_table
[page
].large_object
= 0;
4022 page_table
[page
].write_protected
= 0;
4023 page_table
[page
].write_protected_cleared
= 0;
4024 page_table
[page
].dont_move
= 0;
4025 set_page_need_to_zero(page
, 1);
4027 bytes_allocated
+= bytes_used
;
4030 if (!gencgc_partial_pickup
) {
4032 // Make the most general assumption: any page *might* contain code.
4033 page_table
[page
].allocated
= CODE_PAGE_FLAG
;
4035 page_table
[page
].allocated
= BOXED_PAGE_FLAG
;
4037 first
= gc_search_space3(ptr
, prev
, (ptr
+2));
4040 set_page_scan_start_offset(page
, page_address(page
) - (char*)prev
);
4043 } while (page_address(page
) < alloc_ptr
);
4045 last_free_page
= page
;
4047 generations
[gen
].bytes_allocated
= bytes_allocated
;
4049 gc_alloc_update_all_page_tables(1);
4050 if (ENABLE_PAGE_PROTECTION
)
4051 write_protect_generation_pages(gen
);
4055 gc_initialize_pointers(void)
4057 /* !page_table_pages happens once only in self-build and not again */
4058 if (!page_table_pages
)
4060 gencgc_pickup_dynamic();
4064 /* alloc(..) is the external interface for memory allocation. It
4065 * allocates to generation 0. It is not called from within the garbage
4066 * collector as it is only external uses that need the check for heap
4067 * size (GC trigger) and to disable the interrupts (interrupts are
4068 * always disabled during a GC).
4070 * The vops that call alloc(..) assume that the returned space is zero-filled.
4071 * (E.g. the most significant word of a 2-word bignum in MOVE-FROM-UNSIGNED.)
4073 * The check for a GC trigger is only performed when the current
4074 * region is full, so in most cases it's not needed. */
4076 static inline lispobj
*
4077 general_alloc_internal(sword_t nbytes
, int page_type_flag
, struct alloc_region
*region
,
4078 struct thread
*thread
)
4080 #ifndef LISP_FEATURE_WIN32
4081 lispobj alloc_signal
;
4084 void *new_free_pointer
;
4085 os_vm_size_t trigger_bytes
= 0;
4087 gc_assert(nbytes
> 0);
4089 /* Check for alignment allocation problems. */
4090 gc_assert((((uword_t
)region
->free_pointer
& LOWTAG_MASK
) == 0)
4091 && ((nbytes
& LOWTAG_MASK
) == 0));
4093 #if !(defined(LISP_FEATURE_WIN32) && defined(LISP_FEATURE_SB_THREAD))
4094 /* Must be inside a PA section. */
4095 gc_assert(get_pseudo_atomic_atomic(thread
));
4098 if ((os_vm_size_t
) nbytes
> large_allocation
)
4099 large_allocation
= nbytes
;
4101 /* maybe we can do this quickly ... */
4102 new_free_pointer
= (char*)region
->free_pointer
+ nbytes
;
4103 if (new_free_pointer
<= region
->end_addr
) {
4104 new_obj
= (void*)(region
->free_pointer
);
4105 region
->free_pointer
= new_free_pointer
;
4106 return(new_obj
); /* yup */
4109 /* We don't want to count nbytes against auto_gc_trigger unless we
4110 * have to: it speeds up the tenuring of objects and slows down
4111 * allocation. However, unless we do so when allocating _very_
4112 * large objects we are in danger of exhausting the heap without
4113 * running sufficient GCs.
4115 if ((os_vm_size_t
) nbytes
>= bytes_consed_between_gcs
)
4116 trigger_bytes
= nbytes
;
4118 /* we have to go the long way around, it seems. Check whether we
4119 * should GC in the near future
4121 if (auto_gc_trigger
&& (bytes_allocated
+trigger_bytes
> auto_gc_trigger
)) {
4122 /* Don't flood the system with interrupts if the need to gc is
4123 * already noted. This can happen for example when SUB-GC
4124 * allocates or after a gc triggered in a WITHOUT-GCING. */
4125 if (read_TLS(GC_PENDING
,thread
) == NIL
) {
4126 /* set things up so that GC happens when we finish the PA
4128 write_TLS(GC_PENDING
,T
,thread
);
4129 if (read_TLS(GC_INHIBIT
,thread
) == NIL
) {
4130 #ifdef LISP_FEATURE_SB_SAFEPOINT
4131 thread_register_gc_trigger();
4133 set_pseudo_atomic_interrupted(thread
);
4134 #if GENCGC_IS_PRECISE
4135 /* PPC calls alloc() from a trap
4136 * look up the most context if it's from a trap. */
4138 os_context_t
*context
=
4139 thread
->interrupt_data
->allocation_trap_context
;
4140 maybe_save_gc_mask_and_block_deferrables
4141 (context
? os_context_sigmask_addr(context
) : NULL
);
4144 maybe_save_gc_mask_and_block_deferrables(NULL
);
4150 new_obj
= gc_alloc_with_region(nbytes
, page_type_flag
, region
, 0);
4152 #ifndef LISP_FEATURE_WIN32
4153 /* for sb-prof, and not supported on Windows yet */
4154 alloc_signal
= read_TLS(ALLOC_SIGNAL
,thread
);
4155 if ((alloc_signal
& FIXNUM_TAG_MASK
) == 0) {
4156 if ((sword_t
) alloc_signal
<= 0) {
4157 write_TLS(ALLOC_SIGNAL
, T
, thread
);
4160 write_TLS(ALLOC_SIGNAL
,
4161 alloc_signal
- (1 << N_FIXNUM_TAG_BITS
),
4171 general_alloc(sword_t nbytes
, int page_type_flag
)
4173 struct thread
*thread
= arch_os_get_current_thread();
4174 /* Select correct region, and call general_alloc_internal with it.
4175 * For other then boxed allocation we must lock first, since the
4176 * region is shared. */
4178 if (page_type_flag
== BOXED_PAGE_FLAG
) {
4180 if (BOXED_PAGE_FLAG
& page_type_flag
) {
4182 #ifdef LISP_FEATURE_SB_THREAD
4183 struct alloc_region
*region
= (thread
? &(thread
->alloc_region
) : &boxed_region
);
4185 struct alloc_region
*region
= &boxed_region
;
4187 return general_alloc_internal(nbytes
, page_type_flag
, region
, thread
);
4189 } else if (page_type_flag
== UNBOXED_PAGE_FLAG
||
4190 page_type_flag
== CODE_PAGE_FLAG
) {
4191 struct alloc_region
*region
=
4192 page_type_flag
== CODE_PAGE_FLAG
? &code_region
: &unboxed_region
;
4194 } else if (UNBOXED_PAGE_FLAG
== page_type_flag
) {
4195 struct alloc_region
*region
= &unboxed_region
;
4199 result
= thread_mutex_lock(&allocation_lock
);
4201 obj
= general_alloc_internal(nbytes
, page_type_flag
, region
, thread
);
4202 result
= thread_mutex_unlock(&allocation_lock
);
4206 lose("bad page type flag: %d", page_type_flag
);
4210 lispobj AMD64_SYSV_ABI
*
4211 alloc(sword_t nbytes
)
4213 #ifdef LISP_FEATURE_SB_SAFEPOINT_STRICTLY
4214 struct thread
*self
= arch_os_get_current_thread();
4215 int was_pseudo_atomic
= get_pseudo_atomic_atomic(self
);
4216 if (!was_pseudo_atomic
)
4217 set_pseudo_atomic_atomic(self
);
4219 gc_assert(get_pseudo_atomic_atomic(arch_os_get_current_thread()));
4222 lispobj
*result
= general_alloc(nbytes
, BOXED_PAGE_FLAG
);
4224 #ifdef LISP_FEATURE_SB_SAFEPOINT_STRICTLY
4225 if (!was_pseudo_atomic
)
4226 clear_pseudo_atomic_atomic(self
);
4233 * shared support for the OS-dependent signal handlers which
4234 * catch GENCGC-related write-protect violations
4236 void unhandled_sigmemoryfault(void* addr
);
4238 /* Depending on which OS we're running under, different signals might
4239 * be raised for a violation of write protection in the heap. This
4240 * function factors out the common generational GC magic which needs
4241 * to invoked in this case, and should be called from whatever signal
4242 * handler is appropriate for the OS we're running under.
4244 * Return true if this signal is a normal generational GC thing that
4245 * we were able to handle, or false if it was abnormal and control
4246 * should fall through to the general SIGSEGV/SIGBUS/whatever logic.
4248 * We have two control flags for this: one causes us to ignore faults
4249 * on unprotected pages completely, and the second complains to stderr
4250 * but allows us to continue without losing.
4252 extern boolean ignore_memoryfaults_on_unprotected_pages
;
4253 boolean ignore_memoryfaults_on_unprotected_pages
= 0;
4255 extern boolean continue_after_memoryfault_on_unprotected_pages
;
4256 boolean continue_after_memoryfault_on_unprotected_pages
= 0;
4259 gencgc_handle_wp_violation(void* fault_addr
)
4261 page_index_t page_index
= find_page_index(fault_addr
);
4265 "heap WP violation? fault_addr=%p, page_index=%"PAGE_INDEX_FMT
"\n",
4266 fault_addr
, page_index
));
4269 /* Check whether the fault is within the dynamic space. */
4270 if (page_index
== (-1)) {
4271 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4272 extern int immobile_space_handle_wp_violation(void*);
4273 if (immobile_space_handle_wp_violation(fault_addr
))
4277 /* It can be helpful to be able to put a breakpoint on this
4278 * case to help diagnose low-level problems. */
4279 unhandled_sigmemoryfault(fault_addr
);
4281 /* not within the dynamic space -- not our responsibility */
4286 ret
= thread_mutex_lock(&free_pages_lock
);
4287 gc_assert(ret
== 0);
4288 if (page_table
[page_index
].write_protected
) {
4289 unprotect_page_index(page_index
);
4290 } else if (!ignore_memoryfaults_on_unprotected_pages
) {
4291 /* The only acceptable reason for this signal on a heap
4292 * access is that GENCGC write-protected the page.
4293 * However, if two CPUs hit a wp page near-simultaneously,
4294 * we had better not have the second one lose here if it
4295 * does this test after the first one has already set wp=0
4297 if(page_table
[page_index
].write_protected_cleared
!= 1) {
4298 void lisp_backtrace(int frames
);
4301 "Fault @ %p, page %"PAGE_INDEX_FMT
" not marked as write-protected:\n"
4302 " boxed_region.first_page: %"PAGE_INDEX_FMT
","
4303 " boxed_region.last_page %"PAGE_INDEX_FMT
"\n"
4304 " page.scan_start_offset: %"OS_VM_SIZE_FMT
"\n"
4305 " page.bytes_used: %u\n"
4306 " page.allocated: %d\n"
4307 " page.write_protected: %d\n"
4308 " page.write_protected_cleared: %d\n"
4309 " page.generation: %d\n",
4312 boxed_region
.first_page
,
4313 boxed_region
.last_page
,
4314 page_scan_start_offset(page_index
),
4315 page_bytes_used(page_index
),
4316 page_table
[page_index
].allocated
,
4317 page_table
[page_index
].write_protected
,
4318 page_table
[page_index
].write_protected_cleared
,
4319 page_table
[page_index
].gen
);
4320 if (!continue_after_memoryfault_on_unprotected_pages
)
4324 ret
= thread_mutex_unlock(&free_pages_lock
);
4325 gc_assert(ret
== 0);
4326 /* Don't worry, we can handle it. */
4330 /* This is to be called when we catch a SIGSEGV/SIGBUS, determine that
4331 * it's not just a case of the program hitting the write barrier, and
4332 * are about to let Lisp deal with it. It's basically just a
4333 * convenient place to set a gdb breakpoint. */
4335 unhandled_sigmemoryfault(void *addr
)
4339 update_thread_page_tables(struct thread
*th
)
4341 gc_alloc_update_page_tables(BOXED_PAGE_FLAG
, &th
->alloc_region
);
4342 #if defined(LISP_FEATURE_SB_SAFEPOINT_STRICTLY) && !defined(LISP_FEATURE_WIN32)
4343 gc_alloc_update_page_tables(BOXED_PAGE_FLAG
, &th
->sprof_alloc_region
);
4347 /* GC is single-threaded and all memory allocations during a
4348 collection happen in the GC thread, so it is sufficient to update
4349 all the the page tables once at the beginning of a collection and
4350 update only page tables of the GC thread during the collection. */
4351 void gc_alloc_update_all_page_tables(int for_all_threads
)
4353 /* Flush the alloc regions updating the tables. */
4355 if (for_all_threads
) {
4356 for_each_thread(th
) {
4357 update_thread_page_tables(th
);
4361 th
= arch_os_get_current_thread();
4363 update_thread_page_tables(th
);
4367 gc_alloc_update_page_tables(CODE_PAGE_FLAG
, &code_region
);
4369 gc_alloc_update_page_tables(UNBOXED_PAGE_FLAG
, &unboxed_region
);
4370 gc_alloc_update_page_tables(BOXED_PAGE_FLAG
, &boxed_region
);
4374 gc_set_region_empty(struct alloc_region
*region
)
4376 region
->first_page
= 0;
4377 region
->last_page
= -1;
4378 region
->start_addr
= page_address(0);
4379 region
->free_pointer
= page_address(0);
4380 region
->end_addr
= page_address(0);
4384 zero_all_free_pages() /* called only by gc_and_save() */
4388 for (i
= 0; i
< last_free_page
; i
++) {
4389 if (page_free_p(i
)) {
4390 #ifdef READ_PROTECT_FREE_PAGES
4391 os_protect(page_address(i
), GENCGC_CARD_BYTES
, OS_VM_PROT_ALL
);
4398 /* Things to do before doing a final GC before saving a core (without
4401 * + Pages in large_object pages aren't moved by the GC, so we need to
4402 * unset that flag from all pages.
4403 * + The pseudo-static generation isn't normally collected, but it seems
4404 * reasonable to collect it at least when saving a core. So move the
4405 * pages to a normal generation.
4408 prepare_for_final_gc ()
4412 #ifdef LISP_FEATURE_IMMOBILE_SPACE
4413 extern void prepare_immobile_space_for_final_gc();
4414 prepare_immobile_space_for_final_gc ();
4416 for (i
= 0; i
< last_free_page
; i
++) {
4417 page_table
[i
].large_object
= 0;
4418 if (page_table
[i
].gen
== PSEUDO_STATIC_GENERATION
) {
4419 int used
= page_bytes_used(i
);
4420 page_table
[i
].gen
= HIGHEST_NORMAL_GENERATION
;
4421 generations
[PSEUDO_STATIC_GENERATION
].bytes_allocated
-= used
;
4422 generations
[HIGHEST_NORMAL_GENERATION
].bytes_allocated
+= used
;
4425 #ifdef PINNED_OBJECTS
4427 for_each_thread(th
) {
4428 write_TLS(PINNED_OBJECTS
, NIL
, th
);
4433 /* Set this switch to 1 for coalescing of strings dumped to fasl,
4434 * or 2 for coalescing of those,
4435 * plus literal strings in code compiled to memory. */
4436 char gc_coalesce_string_literals
= 0;
4438 /* Do a non-conservative GC, and then save a core with the initial
4439 * function being set to the value of 'lisp_init_function' */
4441 gc_and_save(char *filename
, boolean prepend_runtime
,
4442 boolean save_runtime_options
, boolean compressed
,
4443 int compression_level
, int application_type
)
4446 void *runtime_bytes
= NULL
;
4447 size_t runtime_size
;
4448 extern void coalesce_similar_objects();
4449 extern struct lisp_startup_options lisp_startup_options
;
4450 boolean verbose
= !lisp_startup_options
.noinform
;
4452 file
= prepare_to_save(filename
, prepend_runtime
, &runtime_bytes
,
4457 conservative_stack
= 0;
4459 /* The filename might come from Lisp, and be moved by the now
4460 * non-conservative GC. */
4461 filename
= strdup(filename
);
4463 /* We're committed to process death at this point, and interrupts can not
4464 * possibly be handled in Lisp. Let the installed handler closures become
4465 * garbage, since new ones will be made by ENABLE-INTERRUPT on restart */
4466 #ifndef LISP_FEATURE_WIN32
4469 for (i
=0; i
<NSIG
; ++i
)
4470 if (lowtag_of(interrupt_handlers
[i
].lisp
) == FUN_POINTER_LOWTAG
)
4471 interrupt_handlers
[i
].lisp
= 0;
4475 /* Collect twice: once into relatively high memory, and then back
4476 * into low memory. This compacts the retained data into the lower
4477 * pages, minimizing the size of the core file.
4479 prepare_for_final_gc();
4480 gencgc_alloc_start_page
= last_free_page
;
4481 collect_garbage(HIGHEST_NORMAL_GENERATION
+1);
4483 // We always coalesce copyable numbers. Addional coalescing is done
4484 // only on request, in which case a message is shown (unless verbose=0).
4485 if (gc_coalesce_string_literals
&& verbose
) {
4486 printf("[coalescing similar vectors... ");
4489 coalesce_similar_objects();
4490 if (gc_coalesce_string_literals
&& verbose
)
4493 /* FIXME: now that relocate_heap() works, can we just memmove() everything
4494 * down and perform a relocation instead of a collection? */
4495 prepare_for_final_gc();
4496 gencgc_alloc_start_page
= -1;
4497 collect_garbage(HIGHEST_NORMAL_GENERATION
+1);
4499 if (prepend_runtime
)
4500 save_runtime_to_filehandle(file
, runtime_bytes
, runtime_size
,
4503 /* The dumper doesn't know that pages need to be zeroed before use. */
4504 zero_all_free_pages();
4505 do_destructive_cleanup_before_save(lisp_init_function
);
4507 save_to_filehandle(file
, filename
, lisp_init_function
,
4508 prepend_runtime
, save_runtime_options
,
4509 compressed
? compression_level
: COMPRESSION_LEVEL_NONE
);
4510 /* Oops. Save still managed to fail. Since we've mangled the stack
4511 * beyond hope, there's not much we can do.
4512 * (beyond FUNCALLing lisp_init_function, but I suspect that's
4513 * going to be rather unsatisfactory too... */
4514 lose("Attempt to save core after non-conservative GC failed.\n");
4517 /* Convert corefile ptes to corresponding 'struct page' */
4518 boolean
gc_load_corefile_ptes(char data
[], ssize_t bytes_read
,
4519 page_index_t npages
, page_index_t
* ppage
)
4521 page_index_t page
= *ppage
;
4523 struct corefile_pte pte
;
4525 while (bytes_read
) {
4526 bytes_read
-= sizeof(struct corefile_pte
);
4527 memcpy(&pte
, data
+i
*sizeof (struct corefile_pte
), sizeof pte
);
4528 set_page_bytes_used(page
, pte
.bytes_used
);
4529 // Low 2 bits of the corefile_pte hold the 'allocated' flag.
4530 // The other bits become the scan_start_offset
4531 set_page_scan_start_offset(page
, pte
.sso
& ~0x03);
4532 page_table
[page
].allocated
= pte
.sso
& 0x03;
4533 if (++page
== npages
)
4534 return 0; // No more to go
4538 return 1; // More to go
4541 /* Prepare the array of corefile_ptes for save */
4542 void gc_store_corefile_ptes(struct corefile_pte
*ptes
)
4545 for (i
= 0; i
< last_free_page
; i
++) {
4546 /* Thanks to alignment requirements, the two low bits
4547 * are always zero, so we can use them to store the
4548 * allocation type -- region is always closed, so only
4549 * the two low bits of allocation flags matter. */
4550 uword_t word
= page_scan_start_offset(i
);
4551 gc_assert((word
& 0x03) == 0);
4552 ptes
[i
].sso
= word
| (0x03 & page_table
[i
].allocated
);
4553 ptes
[i
].bytes_used
= page_bytes_used(i
);