2 * Extension to GENCGC which provides for pages of objects
3 * that are static in placement but subject to reclamation.
7 * This software is part of the SBCL system. See the README file for
10 * This software is derived from the CMU CL system, which was
11 * written at Carnegie Mellon University and released into the
12 * public domain. The software is in the public domain and is
13 * provided with absolutely no warranty. See the COPYING and CREDITS
14 * files for more information.
19 * 1. Space accounting (GET-BYTES-CONSED etc)
20 * 2. Heuristic for auto-trigger. (Can't yet because no space accounting)
21 * Currently happens with regular GC trigger mechanism.
22 * 3. Specify space size on startup
25 // Work around a bug in some llvm/clang versions affecting the memcpy
26 // call in defrag_immobile_space:
28 // When compiled with _FORTIFY_SOURCE nonzero, as seems to be the
29 // default, memcpy is a macro that expands to
30 // __builtin_memcpy_chk(dst, source, size, __builtin_object_size(...)).
32 // Now usually if the compiler knows that it does not know
33 // __builtin_object_size for the source of the copy, the
34 // __builtin_memcpy_chk call becomes plain old memcpy. But in the
35 // buggy case, the compiler is convinced that it does know the
36 // size. This shows up clearly in the disassembly, where the library
37 // routine receives a source size that was erroneously determined to
38 // be a compile-time constant 0. Thus the assertion failure is that
39 // you are reading from a range with 0 bytes in it.
41 // Defining _FORTIFY_LEVEL 0 disables the above macro and thus works
42 // around the problem. Since it is unclear which clang versions are
43 // affected, only apply the workaround for the known-bad version.
44 #if (defined(__clang__) && (__clang_major__ == 6) && (__clang_minor__ == 0))
45 #define _FORTIFY_SOURCE 0
49 #include "gc-internal.h"
50 #include "genesis/vector.h"
51 #include "forwarding-ptr.h"
57 #define FIRST_VARYOBJ_PAGE (IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE/(int)IMMOBILE_CARD_BYTES)
58 #define WORDS_PER_PAGE ((int)IMMOBILE_CARD_BYTES/N_WORD_BYTES)
59 #define DOUBLEWORDS_PER_PAGE (WORDS_PER_PAGE/2)
61 // In case of problems while debugging, this is selectable.
62 #define DEFRAGMENT_FIXEDOBJ_SUBSPACE 1
65 #undef VERIFY_PAGE_GENS
68 # define dprintf(arg) fprintf arg
74 // Inclusive bounds on highest in-use pages per subspace.
75 low_page_index_t max_used_fixedobj_page
, max_used_varyobj_page
;
77 // This table is for objects fixed in size, as opposed to variable-sized.
78 // (Immobile objects are naturally fixed in placement)
79 struct fixedobj_page
{ // 12 bytes per page
80 union immobile_page_attr
{
84 /* space per object in Lisp words. Can exceed obj_size
85 to align on a larger boundary */
86 unsigned char obj_align
;
87 unsigned char obj_size
; /* in Lisp words, incl. header */
88 /* Which generations have data on this page */
89 unsigned char gens_
; // a bitmap
92 int free_index
; // index is in bytes. 4 bytes
93 short int prior_gc_free_word_index
; // index is in words. 2 bytes
94 /* page index of next page with same attributes */
95 short int page_link
; // 2 bytes
98 unsigned int* immobile_scav_queue
;
99 int immobile_scav_queue_head
;
100 // Number of items enqueued; can exceed QCAPACITY on overflow.
101 // If overflowed, the queue is unusable until reset.
102 unsigned int immobile_scav_queue_count
;
103 #define QCAPACITY (IMMOBILE_CARD_BYTES/sizeof(int))
105 #define gens attr.parts.gens_
107 // These are the high 2 bits of 'flags'
108 #define WRITE_PROTECT 0x80
109 #define WRITE_PROTECT_CLEARED 0x40
111 // Packing and unpacking attributes
112 // the low two flag bits are for write-protect status
113 #define MAKE_ATTR(spacing,size,flags) (((spacing)<<8)|((size)<<16)|flags)
114 #define OBJ_SPACING(attr) ((attr>>8) & 0xFF)
116 // Ignore the write-protect bits and the generations when comparing attributes
117 #define ATTRIBUTES_MATCH_P(page_attr,specified_attr) \
118 ((page_attr & 0xFFFF3F) == specified_attr)
119 #define SET_WP_FLAG(index,flag) \
120 fixedobj_pages[index].attr.parts.flags = (fixedobj_pages[index].attr.parts.flags & 0x3F) | flag
122 #define page_obj_align(i) fixedobj_pages[i].attr.parts.obj_align
123 #define page_obj_size(i) fixedobj_pages[i].attr.parts.obj_size
124 #define set_page_full(i) fixedobj_pages[i].free_index = IMMOBILE_CARD_BYTES
125 #define page_full_p(i) (fixedobj_pages[i].free_index >= (int)IMMOBILE_CARD_BYTES)
126 #define fixedobj_page_wp(i) (fixedobj_pages[i].attr.parts.flags & WRITE_PROTECT)
128 /// Variable-length pages:
130 // Array of inverted write-protect flags, 1 bit per page.
131 unsigned int* varyobj_page_touched_bits
;
132 static int n_bitmap_elts
; // length of array measured in 'int's
134 // Array of offsets backwards in double-lispwords from the page end
135 // to the lowest-addressed object touching the page. This offset can
136 // point to a hole, but we prefer that it not. If the offset is zero,
137 // the page has no object other than possibly a hole resulting
138 // from a freed object.
139 unsigned short* varyobj_page_scan_start_offset
;
141 // Array of page generation masks
142 unsigned char* varyobj_page_header_gens
;
143 // Holes to be stuffed back into the managed free list.
144 lispobj varyobj_holes
;
146 #define VARYOBJ_PAGE_GENS(x) varyobj_page_header_gens[x-FIRST_VARYOBJ_PAGE]
147 #define varyobj_page_touched(x) \
148 ((varyobj_page_touched_bits[(x-FIRST_VARYOBJ_PAGE)/32] >> (x&31)) & 1)
150 #ifdef VERIFY_PAGE_GENS
151 void check_fixedobj_page(low_page_index_t
);
152 void check_varyobj_pages();
155 // Object header: generation byte --| |-- widetag
157 // 0xzzzzzzzz GGzzzzww
158 // arbitrary data -------- ---- length in words
160 // There is a hard constraint on NUM_GENERATIONS, which is currently 8.
161 // (0..5=normal, 6=pseudostatic, 7=scratch)
162 // It could be as high as 16 for 32-bit words (wherein scratch=gen15)
163 // or 32 for 64-bits words (wherein scratch=gen31).
164 // In each case, the VISITED flag bit weight would need to be modified.
165 // Shifting a 1 bit left by the contents of the generation byte
166 // must not overflow a register.
168 #ifdef LISP_FEATURE_LITTLE_ENDIAN
169 static inline void assign_generation(lispobj
* obj
, generation_index_t gen
)
171 ((generation_index_t
*)obj
)[3] = gen
;
173 // Turn a grey node black.
174 static inline void set_visited(lispobj
* obj
)
177 gc_assert(__immobile_obj_gen_bits(obj
) == new_space
);
179 ((generation_index_t
*)obj
)[3] |= IMMOBILE_OBJ_VISITED_FLAG
;
182 #error "Need to define assign_generation() for big-endian"
186 low_page_address(low_page_index_t page_num
)
188 return ((void*)IMMOBILE_SPACE_START
+ (page_num
* IMMOBILE_CARD_BYTES
));
191 //// Variable-length utilities
193 /* Calculate the address where the first object touching this page starts. */
194 static inline lispobj
*
195 varyobj_scan_start(low_page_index_t page_index
)
197 return (lispobj
*)((char*)low_page_address(page_index
+1)
198 - varyobj_page_scan_start_offset
[page_index
- FIRST_VARYOBJ_PAGE
]
199 * (2 * N_WORD_BYTES
));
202 /* Return the generation mask for objects headers on 'page_index'
203 including at most one object that starts before the page but ends on
205 If the scan start is within the page, i.e. less than DOUBLEWORDS_PER_PAGE
206 (note that the scan start is measured relative to the page end) then
207 we don't need to OR in the generation byte from an extra object,
208 as all headers on the page are accounted for in the page generation mask.
209 Also an empty page (where scan start is zero) avoids looking
210 at the next page's first object by accident via the same test. */
211 unsigned char varyobj_page_gens_augmented(low_page_index_t page_index
)
213 return (varyobj_page_scan_start_offset
[page_index
- FIRST_VARYOBJ_PAGE
] <= DOUBLEWORDS_PER_PAGE
214 ? 0 : (1<<__immobile_obj_generation(varyobj_scan_start(page_index
))))
215 | VARYOBJ_PAGE_GENS(page_index
);
218 //// Fixed-length object allocator
220 /* Return the index of an immobile page that is probably not totally full,
221 starting with 'hint_page' and wrapping around.
222 'attributes' determine an eligible page.
223 *IMMOBILE-SPACE-FREE-POINTER* is updated to point beyond the found page
224 if it previously did not. */
226 static int get_freeish_page(int hint_page
, int attributes
)
228 int page
= hint_page
;
229 lispobj new_free_pointer
, old_free_pointer
, actual_old
;
230 struct symbol
* free_pointer_sym
;
231 int page_attr_packed
;
232 unsigned char best_genmask
= 0xff;
235 // Speed of this could be improved by keeping a linked list of pages
236 // with any space available, headed by a field in the page struct.
237 // This is totally lock-free / wait-free though, so it's really not
238 // too shabby, because it never has to deal with a page-table mutex.
240 page_attr_packed
= fixedobj_pages
[page
].attr
.packed
;
241 if (page_attr_packed
== 0)
242 if ((page_attr_packed
=
243 __sync_val_compare_and_swap(&fixedobj_pages
[page
].attr
.packed
,
244 0, attributes
)) == 0) {
245 // Atomically assign MAX(old_free_pointer, new_free_pointer)
246 // into the free pointer.
247 free_pointer_sym
= SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
);
248 new_free_pointer
= (lispobj
)low_page_address(page
+1);
249 old_free_pointer
= free_pointer_sym
->value
;
250 while (new_free_pointer
> old_free_pointer
) {
252 __sync_val_compare_and_swap(&free_pointer_sym
->value
,
255 if (actual_old
== old_free_pointer
)
257 old_free_pointer
= actual_old
;
261 if (ATTRIBUTES_MATCH_P(page_attr_packed
, attributes
)
262 && !page_full_p(page
)) {
263 // Try to avoid new objects on pages with any pseudo-static objects,
264 // because then touching the young object forces scanning the page,
265 // which is unfortunate if most things on it were untouched.
266 if (fixedobj_pages
[page
].gens
< (1<<PSEUDO_STATIC_GENERATION
)) {
269 } else if (fixedobj_pages
[page
].gens
< best_genmask
) {
270 best_genmask
= fixedobj_pages
[page
].gens
;
274 if (++page
>= FIRST_VARYOBJ_PAGE
) page
= 0;
275 } while (page
!= hint_page
);
278 lose("No more immobile pages available");
281 // Unused, but possibly will be for some kind of collision-avoidance scheme
282 // on claiming of new free pages.
283 long immobile_alloc_collisions
;
285 /* Beginning at page index *hint, attempt to find space
286 for an object on a page with page_attributes. Write its header word
287 and return a C (native) pointer. The start page MUST have the proper
288 characteristisc, but might be totally full.
290 Precondition: Lisp has established a pseudo-atomic section. */
292 /* There is a slightly different algorithm that would probably be faster
293 than what is currently implemented:
294 - hint should be the address of a word that you try to claim
295 as an object header; it moves from high-to-low instead of low-to-high.
296 It's easier to compute the page base than the last valid object start
297 if there are some wasted words at the end due to page size not being
298 a perfect multiple of object size.
299 - you do a CAS into that word, and either suceed or fail
300 - if you succeed, subtract the object spacing and compare
301 to the page's base address, which can be computed by
302 masking. if the next address is above or equal to the page start,
303 store it in the hint, otherwise mark the page full */
305 lispobj
alloc_immobile_obj(int page_attributes
, lispobj header
, int* hint
)
309 char * page_data
, * obj_ptr
, * next_obj_ptr
, * limit
, * next_free
;
310 int spacing_in_bytes
= OBJ_SPACING(page_attributes
) << WORD_SHIFT
;
314 gc_assert(low_page_address(page
) < (void*)SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
);
317 page_data
= low_page_address(page
);
318 obj_ptr
= page_data
+ fixedobj_pages
[page
].free_index
;
319 limit
= page_data
+ IMMOBILE_CARD_BYTES
- spacing_in_bytes
;
320 while (obj_ptr
<= limit
) {
321 word
= *(lispobj
*)obj_ptr
;
322 next_obj_ptr
= obj_ptr
+ spacing_in_bytes
;
323 if (fixnump(word
) // a fixnum marks free space
324 && __sync_bool_compare_and_swap((lispobj
*)obj_ptr
,
326 // The value formerly in the header word was the offset to
327 // the next hole. Use it to update the freelist pointer.
329 fixedobj_pages
[page
].free_index
= next_obj_ptr
+ word
- page_data
;
330 return (lispobj
)obj_ptr
;
332 // If some other thread updated the free_index
333 // to a larger value, use that. (See example below)
334 next_free
= page_data
+ fixedobj_pages
[page
].free_index
;
335 obj_ptr
= next_free
> next_obj_ptr
? next_free
: next_obj_ptr
;
338 page
= get_freeish_page(page
+1 >= FIRST_VARYOBJ_PAGE
? 0 : page
+1,
345 Example: Conside the freelist initially pointing to word index 6
346 Threads A, and B, and C each want to claim index 6.
347 - Thread A wins and then is switched out immediately after the CAS.
348 - Thread B fails to claim cell 6, claims cell 12 instead.
349 - Thread C fails to claim a cell and is switched out immediately
351 - Thread B writes the index of the next hole, cell 18 into the
352 page's freelist cell.
353 - Thread A wakes up and writes 12 into the freelist cell.
354 - Thread C wakes up sees 12 for next_offset. 12 is greater than 6,
355 so it sets its next probe location to 12.
356 It fails the fixnump(header) test.
357 - Thread C sees that next_offset is still 12,
358 so it skips by the page's object spacing instead, and will continue
359 to do so until hitting the end of the page.
364 void update_immobile_nursery_bits()
366 low_page_index_t page
;
367 lispobj fixedobj_free_ptr
= SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
;
368 lispobj varyobj_free_ptr
= SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
370 // Find the high water marks for this GC scavenge phase
371 // [avoid passing exactly IMMOBILE_SPACE_END, which has no page index]
372 max_used_fixedobj_page
= find_immobile_page_index((void*)(fixedobj_free_ptr
-1));
373 max_used_varyobj_page
= find_immobile_page_index((void*)(varyobj_free_ptr
-1));
375 immobile_scav_queue
= (unsigned int*)low_page_address(max_used_varyobj_page
+1);
376 gc_assert((IMMOBILE_SPACE_END
- (uword_t
)immobile_scav_queue
) / sizeof(int)
379 // Unprotect the in-use ranges. Any page could be written during scavenge
380 os_protect((os_vm_address_t
)IMMOBILE_SPACE_START
,
381 fixedobj_free_ptr
- IMMOBILE_SPACE_START
,
384 // varyobj_free_ptr is typically not page-aligned - only by random chance
385 // might it be. Additionally we need a page beyond that for the re-scan queue.
386 os_vm_address_t limit
= (char*)immobile_scav_queue
+ IMMOBILE_CARD_BYTES
;
387 os_protect((os_vm_address_t
)(IMMOBILE_VARYOBJ_SUBSPACE_START
),
388 limit
- (os_vm_address_t
)IMMOBILE_VARYOBJ_SUBSPACE_START
,
391 for (page
=0; page
<= max_used_fixedobj_page
; ++page
) {
392 // any page whose free index changed contains nursery objects
393 if (fixedobj_pages
[page
].free_index
>> WORD_SHIFT
!=
394 fixedobj_pages
[page
].prior_gc_free_word_index
)
395 fixedobj_pages
[page
].gens
|= 1;
396 #ifdef VERIFY_PAGE_GENS
397 check_fixedobj_page(page
);
400 #ifdef VERIFY_PAGE_GENS
401 check_varyobj_pages();
405 #ifdef SIMPLE_CHARACTER_STRING_WIDETAG
406 #define MAXIMUM_STRING_WIDETAG SIMPLE_CHARACTER_STRING_WIDETAG
408 #define MAXIMUM_STRING_WIDETAG SIMPLE_BASE_STRING_WIDETAG
411 static inline boolean
unboxed_array_p(int widetag
)
413 // This is not an exhaustive test for unboxed objects,
414 // but it's enough to avoid some unnecessary scavenging.
415 return (widetag
>= SIMPLE_ARRAY_UNSIGNED_BYTE_2_WIDETAG
416 && widetag
<= MAXIMUM_STRING_WIDETAG
417 && widetag
!= SIMPLE_VECTOR_WIDETAG
);
420 /* Turn a white object grey. Also enqueue the object for re-scan if required */
422 promote_immobile_obj(lispobj
*ptr
, int rescan
) // a native pointer
424 if (widetag_of(*ptr
) == SIMPLE_FUN_HEADER_WIDETAG
)
425 ptr
= (lispobj
*)code_obj_from_simple_fun((struct simple_fun
*)ptr
);
426 gc_assert(__immobile_obj_gen_bits(ptr
) == from_space
);
427 int pointerish
= !unboxed_array_p(widetag_of(*ptr
));
428 assign_generation(ptr
, (pointerish
? 0 : IMMOBILE_OBJ_VISITED_FLAG
) | new_space
);
429 low_page_index_t page_index
= find_immobile_page_index(ptr
);
431 if (page_index
>= FIRST_VARYOBJ_PAGE
) {
432 VARYOBJ_PAGE_GENS(page_index
) |= 1<<new_space
;
434 fixedobj_pages
[page_index
].gens
|= 1<<new_space
;
436 // If called from preserve_pointer(), then we haven't scanned immobile
437 // roots yet, so we only need ensure that this object's page's WP bit
438 // is cleared so that the page is not skipped during root scan.
441 if (page_index
>= FIRST_VARYOBJ_PAGE
)
442 varyobj_page_touched_bits
[(page_index
-FIRST_VARYOBJ_PAGE
)/32]
443 |= 1 << (page_index
& 31);
445 SET_WP_FLAG(page_index
, WRITE_PROTECT_CLEARED
);
447 return; // No need to enqueue.
450 // Do nothing if either we don't need to look for pointers in this object,
451 // or the work queue has already overflowed, causing a full scan.
452 if (!pointerish
|| immobile_scav_queue_count
> QCAPACITY
) return;
454 // count is either less than or equal to QCAPACITY.
455 // If equal, just bump the count to signify overflow.
456 if (immobile_scav_queue_count
< QCAPACITY
) {
457 immobile_scav_queue
[immobile_scav_queue_head
] =
458 (uword_t
)ptr
& 0xFFFFFFFF; // Drop the high bits
459 immobile_scav_queue_head
= (immobile_scav_queue_head
+ 1) & (QCAPACITY
- 1);
461 ++immobile_scav_queue_count
;
464 /* If 'addr' points to an immobile object, then make the object
465 live by promotion. But if the object is not in the generation
466 being collected, do nothing */
467 void immobile_space_preserve_pointer(void* addr
)
469 low_page_index_t page_index
= find_immobile_page_index(addr
);
473 lispobj
* header_addr
;
474 if (page_index
>= FIRST_VARYOBJ_PAGE
) {
475 // Restrict addr to lie below IMMOBILE_SPACE_FREE_POINTER.
476 // This way, if the gens byte is nonzero but there is
477 // a final array acting as filler on the remainder of the
478 // final page, we won't accidentally find that.
480 if ((lispobj
)addr
>= SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
481 || !(varyobj_page_gens_augmented(page_index
) & (1<<from_space
))
482 || (start
= varyobj_scan_start(page_index
)) > (lispobj
*)addr
)
484 header_addr
= gc_search_space(start
,
485 native_pointer((lispobj
)addr
)+2 - start
,
488 immobile_filler_p(header_addr
) ||
489 (widetag_of(*header_addr
) != CODE_HEADER_WIDETAG
&&
490 !properly_tagged_descriptor_p((lispobj
)addr
, header_addr
)))
492 } else if (fixedobj_pages
[page_index
].gens
& (1<<from_space
)) {
493 int obj_spacing
= (page_obj_align(page_index
) << WORD_SHIFT
);
494 int obj_index
= ((uword_t
)addr
& (IMMOBILE_CARD_BYTES
-1)) / obj_spacing
;
495 dprintf((logfile
,"Pointer %p is to immobile page %d, object %d\n",
496 addr
, page_index
, obj_index
));
497 char* page_start_addr
= (char*)((uword_t
)addr
& ~(IMMOBILE_CARD_BYTES
-1));
498 header_addr
= (lispobj
*)(page_start_addr
+ obj_index
* obj_spacing
);
499 if (fixnump(*header_addr
) ||
500 (lispobj
*)addr
>= header_addr
+ page_obj_size(page_index
) ||
501 !properly_tagged_descriptor_p((lispobj
)addr
, header_addr
))
506 if (__immobile_obj_gen_bits(header_addr
) == from_space
) {
507 dprintf((logfile
,"immobile obj @ %p (<- %p) is conservatively live\n",
509 promote_immobile_obj(header_addr
, 0);
513 // Loop over the newly-live objects, scavenging them for pointers.
514 // As with the ordinary gencgc algorithm, this uses almost no stack.
515 static void full_scavenge_immobile_newspace()
518 unsigned char bit
= 1<<new_space
;
520 // Fixed-size object pages.
522 for (page
= 0; page
<= max_used_fixedobj_page
; ++page
) {
523 if (!(fixedobj_pages
[page
].gens
& bit
)) continue;
524 // Skip amount within the loop is in bytes.
525 int obj_spacing
= page_obj_align(page
) << WORD_SHIFT
;
526 int n_words
= page_obj_size(page
);
527 lispobj
* obj
= low_page_address(page
);
528 // Use an inclusive, not exclusive, limit. On pages with dense packing
529 // (i.e. non-LAYOUT), if the object size does not evenly divide the page
530 // size, it is wrong to examine memory at an address which could be
531 // an object start, but for the fact that it runs off the page boundary.
532 // On the other hand, unused words hold 0, so it's kind of ok to read them.
533 lispobj
* limit
= (lispobj
*)((char*)obj
+
534 IMMOBILE_CARD_BYTES
- obj_spacing
);
535 for ( ; obj
<= limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
536 if (!fixnump(*obj
) && __immobile_obj_gen_bits(obj
) == new_space
) {
538 scavenge(obj
, n_words
);
543 // Variable-size object pages
545 page
= FIRST_VARYOBJ_PAGE
- 1; // Subtract 1 because of pre-increment
547 // Find the next page with anything in newspace.
549 if (++page
> max_used_varyobj_page
) return;
550 } while ((VARYOBJ_PAGE_GENS(page
) & bit
) == 0);
551 lispobj
* obj
= varyobj_scan_start(page
);
553 lispobj
* limit
= (lispobj
*)low_page_address(page
) + WORDS_PER_PAGE
;
554 int widetag
, n_words
;
555 for ( ; obj
< limit
; obj
+= n_words
) {
556 n_words
= sizetab
[widetag
= widetag_of(*obj
)](obj
);
557 if (__immobile_obj_gen_bits(obj
) == new_space
) {
559 scavenge(obj
, n_words
);
562 page
= find_immobile_page_index(obj
);
563 // Bail out if exact absolute end of immobile space was reached.
564 if (page
< 0) return;
565 // If 'page' should be scanned, then pick up where we left off,
566 // without recomputing 'obj' but setting a higher 'limit'.
567 } while (VARYOBJ_PAGE_GENS(page
) & bit
);
571 /// Repeatedly scavenge immobile newspace work queue until we find no more
572 /// reachable objects within. (They might be in dynamic space though).
573 /// If queue overflow already happened, then a worst-case full scan is needed.
574 /// If it didn't, we try to drain the queue, hoping that overflow does
575 /// not happen while doing so.
576 /// The approach taken is more subtle than just dequeuing each item,
577 /// scavenging, and letting the outer 'while' loop take over.
578 /// That would be ok, but could cause more full scans than necessary.
579 /// Instead, since each entry in the queue is useful information
580 /// in the non-overflow condition, perform all the work indicated thereby,
581 /// rather than considering the queue discardable as soon as overflow happens.
582 /// Essentially we just have to capture the valid span of enqueued items,
583 /// because the queue state is inconsistent when 'count' exceeds 'capacity'.
584 void scavenge_immobile_newspace()
586 while (immobile_scav_queue_count
) {
587 if (immobile_scav_queue_count
> QCAPACITY
) {
588 immobile_scav_queue_count
= 0;
589 full_scavenge_immobile_newspace();
591 int queue_index_from
= (immobile_scav_queue_head
- immobile_scav_queue_count
)
593 int queue_index_to
= immobile_scav_queue_head
;
594 int i
= queue_index_from
;
595 // The termination condition can't be expressed as an inequality,
596 // since the indices might be reversed due to wraparound.
597 // To express as equality entails forcing at least one iteration
598 // since the ending index might be the starting index.
600 lispobj
* obj
= (lispobj
*)(uword_t
)immobile_scav_queue
[i
];
601 i
= (1 + i
) & (QCAPACITY
-1);
602 // Only decrement the count if overflow did not happen.
603 // The first iteration of this loop will decrement for sure,
604 // but subsequent iterations might not.
605 if (immobile_scav_queue_count
<= QCAPACITY
)
606 --immobile_scav_queue_count
;
607 if (!(__immobile_obj_gen_bits(obj
) & IMMOBILE_OBJ_VISITED_FLAG
)) {
609 scavenge(obj
, sizetab
[widetag_of(*obj
)](obj
));
611 } while (i
!= queue_index_to
);
616 // Return a page >= page_index having potential old->young pointers,
617 // or -1 if there isn't one.
618 static int next_varyobj_root_page(unsigned int page_index
,
619 unsigned int end_bitmap_index
,
620 unsigned char genmask
)
622 unsigned int map_index
= (page_index
- FIRST_VARYOBJ_PAGE
) / 32;
623 if (map_index
>= end_bitmap_index
) return -1;
624 int bit_index
= page_index
& 31;
625 // Look only at bits of equal or greater weight than bit_index.
626 unsigned int word
= (0xFFFFFFFFU
<< bit_index
) & varyobj_page_touched_bits
[map_index
];
629 bit_index
= ffs(word
) - 1;
630 page_index
= FIRST_VARYOBJ_PAGE
+ map_index
* 32 + bit_index
;
631 if (varyobj_page_gens_augmented(page_index
) & genmask
)
634 word
^= (1<<bit_index
);
638 if (++map_index
>= end_bitmap_index
) return -1;
639 word
= varyobj_page_touched_bits
[map_index
];
644 scavenge_immobile_roots(generation_index_t min_gen
, generation_index_t max_gen
)
646 // example: scavenging gens 2..6, the mask of root gens is #b1111100
647 int genmask
= ((1 << (max_gen
- min_gen
+ 1)) - 1) << min_gen
;
649 low_page_index_t page
;
650 for (page
= 0; page
<= max_used_fixedobj_page
; ++page
) {
651 if (fixedobj_page_wp(page
) || !(fixedobj_pages
[page
].gens
& genmask
))
653 int obj_spacing
= page_obj_align(page
) << WORD_SHIFT
;
654 int n_words
= page_obj_size(page
);
655 lispobj
* obj
= low_page_address(page
);
656 lispobj
* limit
= (lispobj
*)((char*)obj
+
657 IMMOBILE_CARD_BYTES
- obj_spacing
);
659 // Immobile space can only contain objects with a header word,
660 // no conses, so any fixnum where a header could be is not a live
663 if (!fixnump(*obj
) && (genmask
>> (gen
=__immobile_obj_gen_bits(obj
)) & 1)) {
664 if (gen
== new_space
) { set_visited(obj
); }
665 scavenge(obj
, n_words
);
667 } while ((obj
= (lispobj
*)((char*)obj
+ obj_spacing
)) <= limit
);
670 // Variable-length object pages
671 unsigned n_varyobj_pages
= 1+max_used_varyobj_page
-FIRST_VARYOBJ_PAGE
;
672 unsigned end_bitmap_index
= (n_varyobj_pages
+31)/32;
673 page
= next_varyobj_root_page(FIRST_VARYOBJ_PAGE
, end_bitmap_index
, genmask
);
675 lispobj
* obj
= varyobj_scan_start(page
);
677 lispobj
* limit
= (lispobj
*)low_page_address(page
) + WORDS_PER_PAGE
;
678 int widetag
, n_words
, gen
;
679 for ( ; obj
< limit
; obj
+= n_words
) {
680 n_words
= sizetab
[widetag
= widetag_of(*obj
)](obj
);
681 if (genmask
>> (gen
=__immobile_obj_gen_bits(obj
)) & 1) {
682 if (gen
== new_space
) { set_visited(obj
); }
683 scavenge(obj
, n_words
);
686 page
= find_immobile_page_index(obj
);
688 && (VARYOBJ_PAGE_GENS(page
) & genmask
)
689 && varyobj_page_touched(page
));
690 page
= next_varyobj_root_page(1+page
, end_bitmap_index
, genmask
);
692 scavenge_immobile_newspace();
695 #include "genesis/layout.h"
696 #define LAYOUT_SIZE (sizeof (struct layout)/N_WORD_BYTES)
697 #define LAYOUT_ALIGN 256 /*bytes*/
698 #define LAYOUT_OF_LAYOUT ((IMMOBILE_SPACE_START+2*LAYOUT_ALIGN)|INSTANCE_POINTER_LOWTAG)
699 #define LAYOUT_OF_PACKAGE ((IMMOBILE_SPACE_START+3*LAYOUT_ALIGN)|INSTANCE_POINTER_LOWTAG)
701 // As long as Lisp doesn't have any native allocators (vops and whatnot)
702 // it doesn't need to access these values.
703 int layout_page_hint
, symbol_page_hint
, fdefn_page_hint
;
705 // For the three different page characteristics that we need,
706 // claim a page that works for those characteristics.
707 void set_immobile_space_hints()
709 // The allocator doesn't check whether each 'hint' points to an
710 // expected kind of page, so we have to ensure up front that
711 // allocations start on different pages. i.e. You can point to
712 // a totally full page, but you can't point to a wrong page.
713 // It doesn't work to just assign these to consecutive integers
714 // without also updating the page attributes.
716 // Object sizes must be multiples of 2 because the n_words value we pass
717 // to scavenge() is gotten from the page attributes, and scavenge asserts
718 // that the ending address is aligned to a doubleword boundary as expected.
720 // LAYOUTs are 256-byte-aligned so that the low byte contains no information.
721 // This makes it possible to recover a layout pointer from an instance header
722 // by simply changing the low byte to instance-pointer-lowtag.
723 // As a test of objects using larger-than-required alignment,
724 // the 64-bit implementation uses 256-byte alignment for layouts,
725 // even though the header can store all bits of the layout pointer.
726 // The 32-bit implementation would also need somewhere different to store
727 // the generation byte of each layout, which is a minor annoyance.
728 layout_page_hint
= get_freeish_page(0, MAKE_ATTR(LAYOUT_ALIGN
/ N_WORD_BYTES
, // spacing
729 CEILING(LAYOUT_SIZE
,2),
731 symbol_page_hint
= get_freeish_page(0, MAKE_ATTR(CEILING(SYMBOL_SIZE
,2),
732 CEILING(SYMBOL_SIZE
,2),
734 fdefn_page_hint
= get_freeish_page(0, MAKE_ATTR(CEILING(FDEFN_SIZE
,2),
735 CEILING(FDEFN_SIZE
,2),
739 void write_protect_immobile_space()
741 immobile_scav_queue
= NULL
;
742 immobile_scav_queue_head
= 0;
744 set_immobile_space_hints();
746 // Now find contiguous ranges of pages that are protectable,
747 // minimizing the number of system calls as much as possible.
748 int i
, start
= -1, end
= -1; // inclusive bounds on page indices
749 for (i
= max_used_fixedobj_page
; i
>= 0 ; --i
) {
750 if (fixedobj_page_wp(i
)) {
751 if (end
< 0) end
= i
;
754 if (end
>= 0 && (!fixedobj_page_wp(i
) || i
== 0)) {
755 os_protect(low_page_address(start
),
756 IMMOBILE_CARD_BYTES
* (1 + end
- start
),
757 OS_VM_PROT_READ
|OS_VM_PROT_EXECUTE
);
761 #define varyobj_page_wp(x) !varyobj_page_touched(x)
762 for (i
= max_used_varyobj_page
; i
>= FIRST_VARYOBJ_PAGE
; --i
) {
763 if (varyobj_page_wp(i
)) {
764 if (end
< 0) end
= i
;
767 if (end
>= 0 && (!varyobj_page_wp(i
) || i
== FIRST_VARYOBJ_PAGE
)) {
768 os_protect(low_page_address(start
),
769 IMMOBILE_CARD_BYTES
* (1 + end
- start
),
770 OS_VM_PROT_READ
|OS_VM_PROT_EXECUTE
);
774 #undef varyobj_page_wp
777 // Scan range between start and end (exclusive) for old-to-young pointers.
778 // 'keep_gen' is the value of the generation byte of objects that were
779 // candidates to become garbage, but remain live after this gc.
780 // It will necessarily have the VISITED flag on.
781 // 'new_gen' is the generation number that those objects will have
782 // after collection, which is either the same generation or one higher,
783 // depending on the 'raise' flag for this GC cycle.
785 range_points_to_younger_p(lispobj
* obj
, lispobj
* end
,
786 int gen
, int keep_gen
, int new_gen
)
789 lispobj
* __attribute__((unused
)) saved_obj
= obj
, __attribute__((unused
)) header
= *obj
;
792 lispobj thing
= *obj
;
793 if (is_lisp_pointer(thing
)) {
794 int to_page
= find_page_index((void*)thing
),
796 if (to_page
>= 0) { // points to ordinary dynamic space
797 to_gen
= page_table
[to_page
].gen
;
798 if (to_gen
== PSEUDO_STATIC_GENERATION
+1) // scratch gen
799 to_gen
= new_gen
; // is actually this
800 } else if (immobile_space_p(thing
)) {
801 // Processing the code-entry-points slot of a code component
802 // requires the general variant of immobile_obj_gen_bits
803 // because the pointed-to object is a simple-fun.
804 to_gen
= immobile_obj_gen_bits(native_pointer(thing
));
805 if (to_gen
== keep_gen
) // keep gen
806 to_gen
= new_gen
; // is actually this
809 return 1; // yes, points to younger
812 } while (++obj
< end
);
813 return 0; // no, does not point to younger
816 // Scan a fixed-size object for old-to-young pointers.
817 // Since fixed-size objects are boxed and on known boundaries,
818 // we never start in the middle of random bytes, so the answer is exact.
819 static inline boolean
820 fixedobj_points_to_younger_p(lispobj
* obj
, int n_words
,
821 int gen
, int keep_gen
, int new_gen
)
823 unsigned char widetag
= widetag_of(*obj
);
824 lispobj
__attribute__((unused
)) funobj
[1], layout
[1];
828 #ifdef LISP_FEATURE_IMMOBILE_CODE
830 funobj
[0] = fdefn_raw_referent((struct fdefn
*)obj
);
831 return range_points_to_younger_p(funobj
, funobj
+1, gen
, keep_gen
, new_gen
)
832 || range_points_to_younger_p(obj
+1, obj
+3, gen
, keep_gen
, new_gen
);
834 #ifdef LISP_FEATURE_COMPACT_INSTANCE_HEADER
835 case INSTANCE_HEADER_WIDETAG
:
836 case FUNCALLABLE_INSTANCE_HEADER_WIDETAG
:
837 layout
[0] = instance_layout(obj
);
838 if (range_points_to_younger_p(layout
, layout
+1, gen
, keep_gen
, new_gen
))
840 lbitmap
= ((struct layout
*)native_pointer(layout
[0]))->bitmap
;
841 if (lbitmap
!= make_fixnum(-1)) {
842 gc_assert(fixnump(lbitmap
)); // No bignums (yet)
843 sword_t bitmap
= (sword_t
)lbitmap
>> N_FIXNUM_TAG_BITS
;
844 lispobj
* where
= obj
+ 1;
845 for ( ; --n_words
; ++where
, bitmap
>>= 1 )
846 if ((bitmap
& 1) != 0 &&
847 range_points_to_younger_p(where
, where
+1, gen
, keep_gen
, new_gen
))
851 // FALLTHROUGH_INTENDED
854 return range_points_to_younger_p(obj
+1, obj
+n_words
, gen
, keep_gen
, new_gen
);
858 varyobj_points_to_younger_p(lispobj
* obj
, int gen
, int keep_gen
, int new_gen
,
859 os_vm_address_t page_begin
,
860 os_vm_address_t page_end
) // upper (exclusive) bound
862 lispobj
*begin
, *end
, word
= *obj
;
863 unsigned char widetag
= widetag_of(word
);
864 if (widetag
== CODE_HEADER_WIDETAG
) { // usual case. Like scav_code_header()
865 for_each_simple_fun(i
, function_ptr
, (struct code
*)obj
, 0, {
866 begin
= SIMPLE_FUN_SCAV_START(function_ptr
);
867 end
= begin
+ SIMPLE_FUN_SCAV_NWORDS(function_ptr
);
868 if (page_begin
> (os_vm_address_t
)begin
) begin
= (lispobj
*)page_begin
;
869 if (page_end
< (os_vm_address_t
)end
) end
= (lispobj
*)page_end
;
871 && range_points_to_younger_p(begin
, end
, gen
, keep_gen
, new_gen
))
874 begin
= obj
+ 1; // skip the header
875 end
= obj
+ code_header_words(word
); // exclusive bound on boxed slots
876 } else if (widetag
== SIMPLE_VECTOR_WIDETAG
) {
877 sword_t length
= fixnum_value(((struct vector
*)obj
)->length
);
878 begin
= obj
+ 2; // skip the header and length
879 end
= obj
+ CEILING(length
+ 2, 2);
880 } else if (widetag
>= SIMPLE_ARRAY_UNSIGNED_BYTE_2_WIDETAG
&&
881 widetag
<= MAXIMUM_STRING_WIDETAG
) {
884 lose("Unexpected widetag @ %p", obj
);
886 // Fallthrough: scan words from begin to end
887 if (page_begin
> (os_vm_address_t
)begin
) begin
= (lispobj
*)page_begin
;
888 if (page_end
< (os_vm_address_t
)end
) end
= (lispobj
*)page_end
;
889 if (end
> begin
&& range_points_to_younger_p(begin
, end
, gen
, keep_gen
, new_gen
))
894 /// The next two functions are analogous to 'update_page_write_prot()'
895 /// but they differ in that they are "precise" - random code bytes that look
896 /// like pointers are not accidentally treated as pointers.
898 // If 'page' does not contain any objects that points to an object
899 // younger than themselves, then return true.
900 // This is called on pages that do not themselves contain objects of
901 // the generation being collected, but might contain pointers
902 // to younger generations, which we detect by a cleared WP status bit.
903 // The bit is cleared on any write, though, even of a non-pointer,
904 // so this unfortunately has to be tested much more often than we'd like.
905 static inline boolean
can_wp_fixedobj_page(page_index_t page
, int keep_gen
, int new_gen
)
907 int obj_spacing
= page_obj_align(page
) << WORD_SHIFT
;
908 int obj_size_words
= page_obj_size(page
);
909 lispobj
* obj
= low_page_address(page
);
910 lispobj
* limit
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
- obj_spacing
);
911 for ( ; obj
<= limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) )
912 if (!fixnump(*obj
) && // an object header
913 fixedobj_points_to_younger_p(obj
, obj_size_words
,
914 __immobile_obj_generation(obj
),
920 // To scan _only_ 'page' is impossible in general, but we can act like only
921 // one page was scanned by backing up to the first object whose end is on
922 // or after it, and then restricting points_to_younger within the boundaries.
923 // Doing it this way is probably much better than conservatively assuming
924 // that any word satisfying is_lisp_pointer() is a pointer.
925 static inline boolean
can_wp_varyobj_page(page_index_t page
, int keep_gen
, int new_gen
)
927 lispobj
*begin
= (lispobj
*)low_page_address(page
);
928 lispobj
*end
= begin
+ WORDS_PER_PAGE
;
929 lispobj
*obj
= varyobj_scan_start(page
);
930 for ( ; obj
< end
; obj
+= sizetab
[widetag_of(*obj
)](obj
) ) {
931 gc_assert(other_immediate_lowtag_p(*obj
));
932 if (!immobile_filler_p(obj
) &&
933 varyobj_points_to_younger_p(obj
,
934 __immobile_obj_generation(obj
),
936 (os_vm_address_t
)begin
,
937 (os_vm_address_t
)end
))
944 Sweep immobile space by zeroing the memory of trashed objects
945 and linking them into the freelist.
947 Possible improvements:
948 - If an entire page becomes nothing but holes, we could bzero it
949 instead of object-at-a-time clearing. But it's not known to be
950 so until after the sweep, so it would entail two passes per page,
951 one to mark holes and one to zero them.
952 - And perhaps bzero could be used on ranges of holes, because
953 in that case each hole's pointer to the next hole is zero as well.
956 #define SETUP_GENS() \
957 /* Only care about pages with something in old or new space. */ \
958 int relevant_genmask = (1 << from_space) | (1 << new_space); \
959 /* Objects whose gen byte is 'keep_gen' are alive. */ \
960 int keep_gen = IMMOBILE_OBJ_VISITED_FLAG | new_space; \
961 /* Objects whose gen byte is 'from_space' are trash. */ \
962 int discard_gen = from_space; \
963 /* Moving non-garbage into either 'from_space' or 'from_space+1' */ \
964 generation_index_t new_gen = from_space + (raise!=0)
966 // The new value of the page generation mask is computed as follows:
967 // If 'raise' = 1 then:
968 // Nothing resides in 'from_space', and 'from_space+1' gains new objects
969 // if and only if any objects on the page were retained.
970 // If 'raise' = 0 then:
971 // Nothing resides in the scratch generation, and 'from_space'
972 // has objects if and only if any objects were retained.
973 #define COMPUTE_NEW_MASK(var, old) \
974 int var = old & ~(1<<from_space); \
976 var |= 1<<(from_space+1) & any_kept; \
978 var = (var & ~(1<<new_space)) | (1<<from_space & any_kept)
981 sweep_fixedobj_pages(int raise
)
984 lispobj
*obj
, *limit
, *hole
;
985 // This will be needed for space accounting.
986 // threads might fail to consume all the space on a page.
987 // By storing in the page table the count of holes that really existed
988 // at the start of the prior GC, and subtracting from that the number
989 // that exist now, we know how much usable space was obtained (per page).
995 low_page_index_t page
;
996 for (page
= 0; page
<= max_used_fixedobj_page
; ++page
) {
997 // On pages that won't need manipulation of the freelist,
998 // we try to do less work than for pages that need it.
999 if (!(fixedobj_pages
[page
].gens
& relevant_genmask
)) {
1000 // Scan for old->young pointers, and WP if there are none.
1001 if (!fixedobj_page_wp(page
) && fixedobj_pages
[page
].gens
> 1
1002 && can_wp_fixedobj_page(page
, keep_gen
, new_gen
))
1003 SET_WP_FLAG(page
, WRITE_PROTECT
);
1006 int obj_spacing
= page_obj_align(page
) << WORD_SHIFT
;
1007 int obj_size_words
= page_obj_size(page
);
1008 page_base
= low_page_address(page
);
1009 limit
= (lispobj
*)(page_base
+ IMMOBILE_CARD_BYTES
- obj_spacing
);
1010 obj
= (lispobj
*)page_base
;
1012 int any_kept
= 0; // was anything moved to the kept generation
1015 // wp_it is 1 if we should try to write-protect it now.
1016 // If already write-protected, skip the tests.
1017 int wp_it
= !fixedobj_page_wp(page
);
1019 for ( ; obj
<= limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
1020 if (fixnump(*obj
)) { // was already a hole
1022 // re-link it into the new freelist
1024 // store the displacement from the end of the object
1025 // at prev_hole to the start of this object.
1026 *hole
= (lispobj
)((char*)obj
- ((char*)hole
+ obj_spacing
));
1027 else // this is the first seen hole on the page
1028 // record the byte offset to that hole
1029 fixedobj_pages
[page
].free_index
= (char*)obj
- page_base
;
1032 } else if ((gen
= __immobile_obj_gen_bits(obj
)) == discard_gen
) { // trash
1033 for (word_idx
=obj_size_words
-1 ; word_idx
> 0 ; --word_idx
)
1036 } else if (gen
== keep_gen
) {
1037 assign_generation(obj
, gen
= new_gen
);
1039 gc_assert(!fixedobj_points_to_younger_p(obj
, obj_size_words
,
1040 gen
, keep_gen
, new_gen
));
1043 } else if (wp_it
&& fixedobj_points_to_younger_p(obj
, obj_size_words
,
1044 gen
, keep_gen
, new_gen
))
1047 if ( hole
) // terminate the chain of holes
1048 *hole
= (lispobj
)((char*)obj
- ((char*)hole
+ obj_spacing
));
1049 fixedobj_pages
[page
].prior_gc_free_word_index
=
1050 fixedobj_pages
[page
].free_index
>> WORD_SHIFT
;
1052 COMPUTE_NEW_MASK(mask
, fixedobj_pages
[page
].gens
);
1054 fixedobj_pages
[page
].gens
= mask
;
1056 SET_WP_FLAG(page
, WRITE_PROTECT
);
1057 dprintf((logfile
, "Lowspace: set WP on page %d\n", page
));
1060 dprintf((logfile
,"page %d is all garbage\n", page
));
1061 fixedobj_pages
[page
].attr
.packed
= 0;
1064 check_fixedobj_page(page
);
1066 dprintf((logfile
,"page %d: %d holes\n", page
, n_holes
));
1070 void verify_immobile_page_protection(int,int);
1072 // Scan for freshly trashed objects and turn them into filler.
1073 // Lisp is responsible for consuming the free space
1074 // when it next allocates a variable-size object.
1076 sweep_varyobj_pages(int raise
)
1080 lispobj
* free_pointer
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
1081 low_page_index_t page
;
1082 for (page
= FIRST_VARYOBJ_PAGE
; page
<= max_used_varyobj_page
; ++page
) {
1083 int genmask
= VARYOBJ_PAGE_GENS(page
);
1084 if (!(genmask
& relevant_genmask
)) { // Has nothing in oldspace or newspace.
1085 // Scan for old->young pointers, and WP if there are none.
1086 if (varyobj_page_touched(page
)
1087 && varyobj_page_gens_augmented(page
) > 1
1088 && can_wp_varyobj_page(page
, keep_gen
, new_gen
))
1089 varyobj_page_touched_bits
[(page
- FIRST_VARYOBJ_PAGE
)/32] &= ~(1<<(page
& 31));
1092 lispobj
* page_base
= (lispobj
*)low_page_address(page
);
1093 lispobj
* limit
= page_base
+ WORDS_PER_PAGE
;
1094 if (limit
> free_pointer
) limit
= free_pointer
;
1095 int any_kept
= 0; // was anything moved to the kept generation
1096 // wp_it is 1 if we should try to write-protect it now.
1097 // If already write-protected, skip the tests.
1098 int wp_it
= varyobj_page_touched(page
);
1099 lispobj
* obj
= varyobj_scan_start(page
);
1102 if (obj
< page_base
) {
1103 // An object whose tail is on this page, or which spans this page,
1104 // would have been promoted/kept while dealing with the page with
1105 // the object header. Therefore we don't need to consider that object,
1106 // * except * that we do need to consider whether it is an old object
1107 // pointing to a young object.
1108 if (wp_it
// If we wanted to try write-protecting this page,
1109 // and the object starting before this page is strictly older
1110 // than the generation that we're moving retained objects into
1111 && (gen
= __immobile_obj_gen_bits(obj
)) > new_gen
1112 // and it contains an old->young pointer
1113 && varyobj_points_to_younger_p(obj
, gen
, keep_gen
, new_gen
,
1114 (os_vm_address_t
)page_base
,
1115 (os_vm_address_t
)limit
)) {
1118 // We MUST skip this object in the sweep, because in the case of
1119 // non-promotion (raise=0), we could see an object in from_space
1120 // and believe it to be dead.
1121 obj
+= sizetab
[widetag_of(*obj
)](obj
);
1122 // obj can't hop over this page. If it did, there would be no
1123 // headers on the page, and genmask would have been zero.
1124 gc_assert(obj
< limit
);
1126 for ( ; obj
< limit
; obj
+= size
) {
1127 lispobj word
= *obj
;
1128 size
= sizetab
[widetag_of(word
)](obj
);
1129 if (immobile_filler_p(obj
)) { // do nothing
1130 } else if ((gen
= __immobile_obj_gen_bits(obj
)) == discard_gen
) {
1132 lose("immobile object @ %p too small to free", obj
);
1133 else { // Create a filler object.
1134 struct code
* code
= (struct code
*)obj
;
1135 code
->header
= 2<<N_WIDETAG_BITS
| CODE_HEADER_WIDETAG
;
1136 code
->code_size
= make_fixnum((size
- 2) * N_WORD_BYTES
);
1137 code
->debug_info
= varyobj_holes
;
1138 varyobj_holes
= (lispobj
)code
;
1140 } else if (gen
== keep_gen
) {
1141 assign_generation(obj
, gen
= new_gen
);
1143 gc_assert(!varyobj_points_to_younger_p(obj
, gen
, keep_gen
, new_gen
,
1144 (os_vm_address_t
)page_base
,
1145 (os_vm_address_t
)limit
));
1149 varyobj_points_to_younger_p(obj
, gen
, keep_gen
, new_gen
,
1150 (os_vm_address_t
)page_base
,
1151 (os_vm_address_t
)limit
))
1154 COMPUTE_NEW_MASK(mask
, VARYOBJ_PAGE_GENS(page
));
1155 VARYOBJ_PAGE_GENS(page
) = mask
;
1156 if ( mask
&& wp_it
)
1157 varyobj_page_touched_bits
[(page
- FIRST_VARYOBJ_PAGE
)/32] &= ~(1 << (page
& 31));
1160 verify_immobile_page_protection(keep_gen
, new_gen
);
1164 static void compute_immobile_space_bound()
1167 // find the highest page in use
1168 for (max
= FIRST_VARYOBJ_PAGE
-1 ; max
>= 0 ; --max
)
1169 if (fixedobj_pages
[max
].attr
.parts
.obj_size
)
1171 max_used_fixedobj_page
= max
; // this is a page index, not the number of pages.
1172 SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
=
1173 IMMOBILE_SPACE_START
+ IMMOBILE_CARD_BYTES
*(1+max
);
1175 for (max
= (IMMOBILE_SPACE_SIZE
/IMMOBILE_CARD_BYTES
)-1 ;
1176 max
>= FIRST_VARYOBJ_PAGE
; --max
)
1177 if (varyobj_page_gens_augmented(max
))
1179 max_used_varyobj_page
= max
; // this is a page index, not the number of pages.
1182 // TODO: (Maybe this won't work. Not sure yet.) rather than use the
1183 // same 'raise' concept as in gencgc, each immobile object can store bits
1184 // indicating whether it has survived any GC at its current generation.
1185 // If it has, then it gets promoted next time, rather than all or nothing
1186 // being promoted from the generation getting collected.
1188 sweep_immobile_space(int raise
)
1190 gc_assert(immobile_scav_queue_count
== 0);
1191 sweep_fixedobj_pages(raise
);
1192 sweep_varyobj_pages(raise
);
1193 compute_immobile_space_bound();
1196 void gc_init_immobile()
1201 int n_fixedobj_pages
= FIRST_VARYOBJ_PAGE
;
1202 int n_varyobj_pages
= (IMMOBILE_SPACE_SIZE
- IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE
)
1203 / IMMOBILE_CARD_BYTES
;
1204 fixedobj_pages
= calloc(n_fixedobj_pages
, sizeof(struct fixedobj_page
));
1205 gc_assert(fixedobj_pages
);
1207 n_bitmap_elts
= (n_varyobj_pages
+ 31) / 32;
1208 int request
= n_bitmap_elts
* sizeof (int)
1209 + n_varyobj_pages
* (sizeof (short)+sizeof (char));
1210 char* varyobj_page_tables
= malloc(request
);
1211 gc_assert(varyobj_page_tables
);
1212 memset(varyobj_page_tables
, 0, request
);
1213 varyobj_page_touched_bits
= (unsigned int*)varyobj_page_tables
;
1214 // The conservative value for 'touched' is 1.
1215 memset(varyobj_page_touched_bits
, 0xff, n_bitmap_elts
* sizeof (int));
1216 varyobj_page_scan_start_offset
= (unsigned short*)(varyobj_page_touched_bits
+ n_bitmap_elts
);
1217 varyobj_page_header_gens
= (unsigned char*)(varyobj_page_scan_start_offset
+ n_varyobj_pages
);
1220 /* Because the immobile page table is not dumped into a core image,
1221 we have to reverse-engineer the characteristics of each page,
1222 which means figuring out what the object spacing should be.
1223 This is not difficult, but is a bit of a kludge */
1225 static inline int immobile_obj_spacing(lispobj header_word
, lispobj
*obj
,
1228 if (widetag_of(header_word
) == INSTANCE_HEADER_WIDETAG
&&
1229 instance_layout(obj
) == LAYOUT_OF_LAYOUT
)
1230 return LAYOUT_ALIGN
/ N_WORD_BYTES
;
1232 return actual_size
; // in words
1235 // Set the characteristics of each used page at image startup time.
1236 void immobile_space_coreparse(uword_t address
, uword_t len
)
1238 int n_pages
, word_idx
, page
;
1240 n_pages
= (len
+ IMMOBILE_CARD_BYTES
- 1) / IMMOBILE_CARD_BYTES
;
1241 if (address
== IMMOBILE_SPACE_START
) {
1242 for (page
= 0 ; page
< n_pages
; ++page
) {
1243 lispobj
* page_data
= low_page_address(page
);
1244 for (word_idx
= 0 ; word_idx
< WORDS_PER_PAGE
; ++word_idx
) {
1245 lispobj
* obj
= page_data
+ word_idx
;
1246 lispobj header
= *obj
;
1247 if (!fixnump(header
)) {
1248 gc_assert(other_immediate_lowtag_p(*obj
));
1249 int size
= sizetab
[widetag_of(header
)](obj
);
1250 fixedobj_pages
[page
].attr
.parts
.obj_size
= size
;
1251 fixedobj_pages
[page
].attr
.parts
.obj_align
1252 = immobile_obj_spacing(header
, obj
, size
);
1253 fixedobj_pages
[page
].attr
.parts
.flags
= WRITE_PROTECT
;
1254 fixedobj_pages
[page
].gens
|= 1 << __immobile_obj_gen_bits(obj
);
1259 } else if (address
== IMMOBILE_VARYOBJ_SUBSPACE_START
) {
1260 lispobj
* obj
= (lispobj
*)address
;
1261 lispobj
* limit
= (lispobj
*)(address
+ len
);
1263 low_page_index_t last_page
= 0;
1264 for ( ; obj
< limit
; obj
+= n_words
) {
1265 n_words
= sizetab
[widetag_of(*obj
)](obj
);
1266 if (obj
[1] == 0 && (obj
[0] == INSTANCE_HEADER_WIDETAG
||
1269 // Round up to the next immobile page.
1270 lispobj page_end
= CEILING((lispobj
)obj
, IMMOBILE_CARD_BYTES
);
1271 n_words
= (lispobj
*)page_end
- obj
;
1272 obj
[0] = SIMPLE_ARRAY_FIXNUM_WIDETAG
;
1273 obj
[1] = make_fixnum(n_words
- 2);
1275 // There are trailing zeros to fill the core file page.
1276 // This happens when the next object is exactly aligned
1277 // to an immobile page. There is no padding object.
1278 gc_assert(((lispobj
)obj
& (IMMOBILE_CARD_BYTES
-1)) == 0);
1283 if (immobile_filler_p(obj
)) {
1284 // Holes were chained through the debug_info slot at save.
1285 // Just update the head of the chain.
1286 varyobj_holes
= (lispobj
)obj
;
1289 low_page_index_t first_page
= find_immobile_page_index(obj
);
1290 last_page
= find_immobile_page_index(obj
+n_words
-1);
1291 // Only the page with this object header gets a bit in its gen mask.
1292 VARYOBJ_PAGE_GENS(first_page
) |= 1<<__immobile_obj_gen_bits(obj
);
1293 // For each page touched by this object, set the page's
1294 // scan_start_offset, unless it was already set.
1296 for (page
= first_page
; page
<= last_page
; ++page
) {
1297 if (!varyobj_page_scan_start_offset
[page
- FIRST_VARYOBJ_PAGE
]) {
1298 long offset
= (char*)low_page_address(page
+1) - (char*)obj
;
1299 varyobj_page_scan_start_offset
[page
- FIRST_VARYOBJ_PAGE
]
1300 = offset
>> (WORD_SHIFT
+ 1);
1304 // Write-protect the pages occupied by the core file.
1305 // (There can be no inter-generation pointers.)
1307 for (page
= FIRST_VARYOBJ_PAGE
; page
<= last_page
; ++page
)
1308 varyobj_page_touched_bits
[(page
-FIRST_VARYOBJ_PAGE
)/32] &= ~(1<<(page
& 31));
1309 SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
= (lispobj
)limit
;
1310 compute_immobile_space_bound();
1311 write_protect_immobile_space();
1313 lose("unknown immobile subspace");
1317 // Demote pseudo-static to highest normal generation
1318 // so that all objects become eligible for collection.
1319 void prepare_immobile_space_for_final_gc()
1323 char* page_end
= (char*)SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
;
1325 // The list of holes need not be saved.
1326 SYMBOL(IMMOBILE_FREELIST
)->value
= NIL
;
1328 for (page_base
= (char*)IMMOBILE_SPACE_START
, page
= 0 ;
1329 page_base
< page_end
;
1330 page_base
+= IMMOBILE_CARD_BYTES
, ++page
) {
1331 unsigned char mask
= fixedobj_pages
[page
].gens
;
1332 if (mask
& 1<<PSEUDO_STATIC_GENERATION
) {
1333 int obj_spacing
= page_obj_align(page
) << WORD_SHIFT
;
1334 lispobj
* obj
= (lispobj
*)page_base
;
1335 lispobj
* limit
= (lispobj
*)(page_base
+ IMMOBILE_CARD_BYTES
- obj_spacing
);
1336 for ( ; obj
<= limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
1338 && __immobile_obj_gen_bits(obj
) == PSEUDO_STATIC_GENERATION
)
1339 assign_generation(obj
, HIGHEST_NORMAL_GENERATION
);
1341 fixedobj_pages
[page
].gens
= (mask
& ~(1<<PSEUDO_STATIC_GENERATION
))
1342 | 1<<HIGHEST_NORMAL_GENERATION
;
1346 lispobj
* obj
= (lispobj
*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
1347 lispobj
* limit
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
1348 for ( ; obj
< limit
; obj
+= sizetab
[widetag_of(*obj
)](obj
) ) {
1349 if (__immobile_obj_gen_bits(obj
) == PSEUDO_STATIC_GENERATION
)
1350 assign_generation(obj
, HIGHEST_NORMAL_GENERATION
);
1352 int max_page
= find_immobile_page_index(limit
-1);
1353 for ( page
= FIRST_VARYOBJ_PAGE
; page
<= max_page
; ++page
) {
1354 int mask
= VARYOBJ_PAGE_GENS(page
);
1355 if (mask
& (1<<PSEUDO_STATIC_GENERATION
)) {
1356 VARYOBJ_PAGE_GENS(page
) = (mask
& ~(1<<PSEUDO_STATIC_GENERATION
))
1357 | 1<<HIGHEST_NORMAL_GENERATION
;
1362 // Now once again promote all objects to pseudo-static just prior to save.
1363 // 'coreparse' makes all pages in regular dynamic space pseudo-static.
1364 // But since immobile objects store their generation, it must be done at save,
1365 // or else it would have to be done on image restart
1366 // which would require writing to a lot of pages for no reason.
1367 void prepare_immobile_space_for_save()
1369 // Don't use the page attributes now - defrag doesn't update them.
1370 lispobj
* obj
= (lispobj
*)IMMOBILE_SPACE_START
;
1371 lispobj
* limit
= (lispobj
*)SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
;
1372 while (obj
< limit
) {
1373 if (other_immediate_lowtag_p(*obj
))
1374 assign_generation(obj
, PSEUDO_STATIC_GENERATION
);
1375 obj
+= sizetab
[widetag_of(*obj
)](obj
);
1378 obj
= (lispobj
*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
1379 limit
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
1380 for ( varyobj_holes
= 0 ; obj
< limit
; obj
+= sizetab
[widetag_of(*obj
)](obj
) ) {
1381 if (immobile_filler_p(obj
)) {
1382 struct code
* code
= (struct code
*)obj
;
1383 code
->debug_info
= varyobj_holes
;
1384 varyobj_holes
= (lispobj
)code
;
1385 // 0-fill the unused space.
1386 int nwords
= sizetab
[widetag_of(*obj
)](obj
);
1387 memset(code
->constants
, 0,
1388 (nwords
* N_WORD_BYTES
) - offsetof(struct code
, constants
));
1390 assign_generation(obj
, PSEUDO_STATIC_GENERATION
);
1392 if ((lispobj
)limit
& (IMMOBILE_CARD_BYTES
-1)) { // Last page is partially used.
1393 gc_assert(*limit
== SIMPLE_ARRAY_FIXNUM_WIDETAG
);
1394 // Write an otherwise illegal object at the free pointer.
1395 limit
[0] = INSTANCE_HEADER_WIDETAG
; // 0 payload length
1396 limit
[1] = 0; // no layout
1402 int immobile_space_handle_wp_violation(void* fault_addr
)
1404 low_page_index_t page_index
= find_immobile_page_index(fault_addr
);
1405 if (page_index
< 0) return 0;
1407 os_protect((os_vm_address_t
)((lispobj
)fault_addr
& ~(IMMOBILE_CARD_BYTES
-1)),
1408 IMMOBILE_CARD_BYTES
, OS_VM_PROT_ALL
);
1409 if (page_index
>= FIRST_VARYOBJ_PAGE
) {
1410 // The free pointer can move up or down. Attempting to insist that a WP
1411 // fault not occur above the free pointer (plus some slack) is not
1412 // threadsafe, so allow it anywhere. More strictness could be imparted
1413 // by tracking the max value attained by the free pointer.
1414 __sync_or_and_fetch(&varyobj_page_touched_bits
[(page_index
-FIRST_VARYOBJ_PAGE
)/32],
1415 1 << (page_index
& 31));
1417 // FIXME: a single bitmap of touched bits would make more sense,
1418 // and the _CLEARED flag doesn't achieve much if anything.
1419 if (!(fixedobj_pages
[page_index
].attr
.parts
.flags
1420 & (WRITE_PROTECT
|WRITE_PROTECT_CLEARED
)))
1422 SET_WP_FLAG(page_index
, WRITE_PROTECT_CLEARED
);
1427 // Find the object that encloses pointer.
1428 static int page_attributes_valid
= 1; // For verify_space() after defrag
1430 search_immobile_space(void *pointer
)
1434 if ((lispobj
)pointer
>= IMMOBILE_SPACE_START
1435 && (lispobj
)pointer
< SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
) {
1436 low_page_index_t page_index
= find_immobile_page_index(pointer
);
1437 if ((lispobj
)pointer
>= IMMOBILE_VARYOBJ_SUBSPACE_START
) {
1438 if (page_attributes_valid
) {
1439 start
= (lispobj
*)varyobj_scan_start(page_index
);
1440 if (start
> (lispobj
*)pointer
) return NULL
;
1442 start
= (lispobj
*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
1444 lispobj
* found
= gc_search_space(start
,
1445 (((lispobj
*)pointer
)+2)-start
,
1447 return (found
&& immobile_filler_p(found
)) ? 0 : found
;
1448 } else if ((lispobj
)pointer
< SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
) {
1449 char *page_base
= (char*)((lispobj
)pointer
& ~(IMMOBILE_CARD_BYTES
-1));
1450 if (page_attributes_valid
) {
1451 int spacing
= page_obj_align(page_index
) << WORD_SHIFT
;
1452 int index
= ((char*)pointer
- page_base
) / spacing
;
1453 char *begin
= page_base
+ spacing
* index
;
1454 char *end
= begin
+ (page_obj_size(page_index
) << WORD_SHIFT
);
1455 if ((char*)pointer
< end
) return (lispobj
*)begin
;
1457 start
= (lispobj
*)page_base
;
1458 return (gc_search_space(start
,
1459 (((lispobj
*)pointer
)+2)-start
,
1460 (lispobj
*)pointer
));
1467 // For coalescing holes, we need to scan backwards, which is done by
1468 // looking backwards for a page that contains the start of a
1469 // block of objects one of which must abut 'obj'.
1470 lispobj
* find_preceding_object(lispobj
* obj
)
1472 int page
= find_immobile_page_index(obj
);
1474 int offset
= varyobj_page_scan_start_offset
[page
- FIRST_VARYOBJ_PAGE
];
1475 if (offset
) { // 0 means the page is empty.
1476 lispobj
* start
= varyobj_scan_start(page
);
1477 if (start
< obj
) { // Scan from here forward
1479 lispobj
* end
= start
+ sizetab
[widetag_of(*start
)](start
);
1480 if (end
== obj
) return start
;
1481 gc_assert(end
< obj
);
1486 if (page
== FIRST_VARYOBJ_PAGE
) {
1487 gc_assert(obj
== low_page_address(FIRST_VARYOBJ_PAGE
));
1488 return 0; // Predecessor does not exist
1494 #include "genesis/vector.h"
1495 #include "genesis/instance.h"
1496 lispobj
alloc_layout(lispobj slots
)
1498 struct vector
* v
= (struct vector
*)native_pointer(slots
);
1499 // If INSTANCE_DATA_START is 0, subtract 1 word for the header.
1500 // If 1, subtract 2 words: 1 for the header and 1 for the layout.
1501 if (fixnum_value(v
->length
) != (LAYOUT_SIZE
- INSTANCE_DATA_START
- 1))
1502 lose("bad arguments to alloc_layout");
1503 struct instance
* l
= (struct instance
*)
1504 alloc_immobile_obj(MAKE_ATTR(LAYOUT_ALIGN
/ N_WORD_BYTES
,
1505 CEILING(LAYOUT_SIZE
,2),
1507 #ifdef LISP_FEATURE_COMPACT_INSTANCE_HEADER
1508 (LAYOUT_OF_LAYOUT
<< 32) |
1510 (LAYOUT_SIZE
-1)<<8 | INSTANCE_HEADER_WIDETAG
,
1512 #ifndef LISP_FEATURE_COMPACT_INSTANCE_HEADER
1513 l
->slots
[0] = LAYOUT_OF_LAYOUT
;
1515 memcpy(&l
->slots
[INSTANCE_DATA_START
], v
->data
,
1516 (LAYOUT_SIZE
- INSTANCE_DATA_START
- 1)*N_WORD_BYTES
);
1518 // Possible efficiency win: make the "wasted" bytes after the layout into a
1519 // simple unboxed array so that heap-walking can skip in one step.
1520 // Probably only a performance issue for MAP-ALLOCATED-OBJECTS,
1521 // since scavenging know to skip by the object alignment anyway.
1522 return make_lispobj(l
, INSTANCE_POINTER_LOWTAG
);
1525 #include "genesis/symbol.h"
1526 lispobj
alloc_sym(lispobj name
)
1528 // While there are different "kinds" of symbols in the defragmentation
1529 // logic, we don't distinguish them when allocating,
1530 // on the theory that contiguous allocations are preferable anyway.
1531 struct symbol
* s
= (struct symbol
*)
1532 alloc_immobile_obj(MAKE_ATTR(CEILING(SYMBOL_SIZE
,2), // spacing
1533 CEILING(SYMBOL_SIZE
,2), // size
1535 (SYMBOL_SIZE
-1)<<8 | SYMBOL_HEADER_WIDETAG
,
1537 s
->value
= UNBOUND_MARKER_WIDETAG
;
1542 return make_lispobj(s
, OTHER_POINTER_LOWTAG
);
1545 #include "genesis/fdefn.h"
1546 lispobj
alloc_fdefn(lispobj name
)
1548 struct fdefn
* f
= (struct fdefn
*)
1549 alloc_immobile_obj(MAKE_ATTR(CEILING(FDEFN_SIZE
,2), // spacing
1550 CEILING(FDEFN_SIZE
,2), // size
1552 (FDEFN_SIZE
-1)<<8 | FDEFN_WIDETAG
,
1557 return make_lispobj(f
, OTHER_POINTER_LOWTAG
);
1560 #if defined(LISP_FEATURE_IMMOBILE_CODE) && defined(LISP_FEATURE_COMPACT_INSTANCE_HEADER)
1561 #include "genesis/funcallable-instance.h"
1562 #define GF_SIZE (sizeof(struct funcallable_instance)/sizeof(lispobj)+2) /* = 6 */
1563 lispobj
alloc_generic_function(lispobj slots
)
1565 // GFs have no C header file to represent the layout, which is 6 words:
1566 // header, entry-point, fin-function, slots, raw data (x2)
1567 lispobj
* obj
= (lispobj
*)
1568 alloc_immobile_obj(MAKE_ATTR(CEILING(GF_SIZE
,2), // spacing
1569 CEILING(GF_SIZE
,2), // size
1571 // 5 payload words following the header
1572 ((GF_SIZE
-1)<<8) | FUNCALLABLE_INSTANCE_HEADER_WIDETAG
,
1573 // KLUDGE: same page attributes as symbols,
1574 // so use the same hint.
1576 ((struct funcallable_instance
*)obj
)->info
[0] = slots
;
1577 ((struct funcallable_instance
*)obj
)->trampoline
= (lispobj
)(obj
+ 4);
1578 return make_lispobj(obj
, FUN_POINTER_LOWTAG
);
1582 #ifdef LISP_FEATURE_IMMOBILE_CODE
1583 //// Defragmentation
1588 } fixedobj_tempspace
, varyobj_tempspace
;
1590 // Given an adddress in the target core, return the equivalent
1591 // physical address to read or write during defragmentation
1592 static lispobj
* tempspace_addr(void* address
)
1594 int byte_index
= (char*)address
- (char*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
1595 gc_assert(immobile_space_p((lispobj
)address
));
1596 if (byte_index
< 0) { // fixedobj subspace
1597 if (fixedobj_tempspace
.n_bytes
== 0) return address
;
1598 byte_index
= (char*)address
- (char*)IMMOBILE_SPACE_START
;
1599 gc_assert(byte_index
< fixedobj_tempspace
.n_bytes
);
1600 return (void*)(fixedobj_tempspace
.start
+ byte_index
);
1601 } else { // varyobj subspace
1602 gc_assert(byte_index
< varyobj_tempspace
.n_bytes
);
1603 return (void*)(varyobj_tempspace
.start
+ byte_index
);
1607 static void adjust_words(lispobj
*where
, sword_t n_words
)
1610 for (i
=0;i
<n_words
;++i
) {
1611 lispobj ptr
= where
[i
];
1612 if (is_lisp_pointer(ptr
) && forwarding_pointer_p(native_pointer(ptr
)))
1613 where
[i
] = forwarding_pointer_value(native_pointer(ptr
));
1617 static lispobj
adjust_fun_entrypoint(lispobj raw_entry
)
1619 if (raw_entry
> READ_ONLY_SPACE_END
) {
1620 // if not pointing read-only space, then it's neither closure_tramp
1621 // nor funcallable_instance_tramp.
1622 lispobj simple_fun
= raw_entry
- FUN_RAW_ADDR_OFFSET
;
1623 adjust_words(&simple_fun
, 1);
1624 return simple_fun
+ FUN_RAW_ADDR_OFFSET
;
1626 return raw_entry
; // otherwise it's one of those trampolines
1629 /// Fixup the fdefn at 'where' based on it moving by 'displacement'.
1630 /// 'fdefn_old' is needed for computing the pre-fixup callee if the
1631 /// architecture uses a call-relative instruction.
1632 static void adjust_fdefn_entrypoint(lispobj
* where
, int displacement
,
1633 struct fdefn
* fdefn_old
)
1635 struct fdefn
* fdefn
= (struct fdefn
*)where
;
1636 int callee_adjust
= 0;
1637 // Get the tagged object referred to by the fdefn_raw_addr.
1638 lispobj callee_old
= fdefn_raw_referent(fdefn_old
);
1639 // If it's the undefined function trampoline, or the referent
1640 // did not move, then the callee_adjust stays 0.
1641 // Otherwise we adjust the rel32 field by the change in callee address.
1642 if (callee_old
&& forwarding_pointer_p(native_pointer(callee_old
))) {
1643 lispobj callee_new
= forwarding_pointer_value(native_pointer(callee_old
));
1644 callee_adjust
= callee_new
- callee_old
;
1646 #ifdef LISP_FEATURE_X86_64
1647 *(int*)((char*)&fdefn
->raw_addr
+ 1) += callee_adjust
- displacement
;
1649 #error "Can't adjust fdefn_raw_addr for this architecture"
1653 // Fix the layout of OBJ, and return the layout's address in tempspace.
1654 struct layout
* fix_object_layout(lispobj
* obj
)
1656 // This works on instances, funcallable instances (and/or closures)
1657 // but the latter only if the layout is in the header word.
1658 #ifdef LISP_FEATURE_COMPACT_INSTANCE_HEADER
1659 gc_assert(widetag_of(*obj
) == INSTANCE_HEADER_WIDETAG
1660 || widetag_of(*obj
) == FUNCALLABLE_INSTANCE_HEADER_WIDETAG
1661 || widetag_of(*obj
) == CLOSURE_HEADER_WIDETAG
);
1663 gc_assert(widetag_of(*obj
) == INSTANCE_HEADER_WIDETAG
);
1665 lispobj layout
= instance_layout(obj
);
1666 if (layout
== 0) return 0;
1667 if (forwarding_pointer_p(native_pointer(layout
))) { // usually
1668 layout
= forwarding_pointer_value(native_pointer(layout
));
1669 set_instance_layout(obj
, layout
);
1671 struct layout
* native_layout
= (struct layout
*)
1672 tempspace_addr(native_pointer(layout
));
1673 gc_assert(widetag_of(native_layout
->header
) == INSTANCE_HEADER_WIDETAG
);
1674 gc_assert(instance_layout((lispobj
*)native_layout
) == LAYOUT_OF_LAYOUT
);
1675 return native_layout
;
1678 /// It's tricky to try to use the scavtab[] functions for fixing up moved
1679 /// objects, because scavenger functions might invoke transport functions.
1680 /// The best approach is to do an explicit switch over all object types.
1681 #include "genesis/hash-table.h"
1682 static void fixup_space(lispobj
* where
, size_t n_words
)
1684 lispobj
* end
= where
+ n_words
;
1685 lispobj header_word
;
1688 void fixup_immobile_refs(struct code
*);
1689 int static_space_p
= ((lispobj
)where
== STATIC_SPACE_START
);
1691 while (where
< end
) {
1692 gc_assert(!forwarding_pointer_p(where
));
1693 header_word
= *where
;
1694 if (is_lisp_pointer(header_word
) || is_lisp_immediate(header_word
)) {
1695 adjust_words(where
, 2); // A cons.
1699 widetag
= widetag_of(header_word
);
1700 size
= sizetab
[widetag
](where
);
1703 if (!(widetag
<= COMPLEX_DOUBLE_FLOAT_WIDETAG
1704 || widetag
== SAP_WIDETAG
// Better not point to code!
1705 || widetag
== SIMD_PACK_WIDETAG
1706 || unboxed_array_p(widetag
)))
1707 lose("Unhandled widetag in fixup_space: %p\n", (void*)header_word
);
1709 #ifdef LISP_FEATURE_COMPACT_INSTANCE_HEADER
1710 case FUNCALLABLE_INSTANCE_HEADER_WIDETAG
:
1712 case INSTANCE_HEADER_WIDETAG
:
1713 instance_scan(adjust_words
, where
+1,
1714 instance_length(header_word
) | 1,
1715 fix_object_layout(where
)->bitmap
);
1717 case CODE_HEADER_WIDETAG
:
1718 // Fixup the constant pool.
1719 adjust_words(where
+1, code_header_words(header_word
)-1);
1720 // Fixup all embedded simple-funs
1721 for_each_simple_fun(i
, f
, (struct code
*)where
, 1, {
1722 f
->self
= adjust_fun_entrypoint(f
->self
);
1723 adjust_words(SIMPLE_FUN_SCAV_START(f
), SIMPLE_FUN_SCAV_NWORDS(f
));
1725 if (((struct code
*)where
)->fixups
)
1726 fixup_immobile_refs((struct code
*)where
);
1728 case CLOSURE_HEADER_WIDETAG
:
1729 where
[1] = adjust_fun_entrypoint(where
[1]);
1730 // FALLTHROUGH_INTENDED
1731 #ifndef LISP_FEATURE_COMPACT_INSTANCE_HEADER
1732 case FUNCALLABLE_INSTANCE_HEADER_WIDETAG
:
1734 // skip the trampoline word at where[1]
1735 adjust_words(where
+2, size
-2);
1738 adjust_words(where
+1, 2);
1739 // If fixed-size objects (hence FDEFNs) are movable, then fixing the
1740 // raw address can not be done here, because it is impossible to compute
1741 // the absolute jump target - we don't know what the fdefn's original
1742 // address was to compute a pc-relative address. So we do those while
1743 // permuting the FDEFNs. But because static fdefns do not move,
1744 // we do process their raw address slot here.
1745 #if DEFRAGMENT_FIXEDOBJ_SUBSPACE
1748 adjust_fdefn_entrypoint(where
, 0, (struct fdefn
*)where
);
1751 // Special case because we might need to mark hashtables
1752 // as needing rehash.
1753 case SIMPLE_VECTOR_WIDETAG
:
1754 if ((HeaderValue(header_word
) & 0xFF) == subtype_VectorValidHashing
) {
1755 struct vector
* v
= (struct vector
*)where
;
1756 lispobj
* data
= v
->data
;
1757 gc_assert(v
->length
> 0 &&
1758 lowtag_of(data
[0]) == INSTANCE_POINTER_LOWTAG
&&
1759 !(fixnum_value(v
->length
) & 1)); // length must be even
1760 boolean needs_rehash
= 0;
1762 for (i
= fixnum_value(v
->length
)-1 ; i
>=0 ; --i
) {
1763 lispobj ptr
= data
[i
];
1764 if (is_lisp_pointer(ptr
) && forwarding_pointer_p(native_pointer(ptr
))) {
1765 data
[i
] = forwarding_pointer_value(native_pointer(ptr
));
1770 struct hash_table
*ht
= (struct hash_table
*)native_pointer(v
->data
[0]);
1771 ht
->needs_rehash_p
= T
;
1775 // FALLTHROUGH_INTENDED
1777 // All the other array header widetags.
1778 case SIMPLE_ARRAY_WIDETAG
:
1779 #ifdef COMPLEX_CHARACTER_STRING_WIDETAG
1780 case COMPLEX_CHARACTER_STRING_WIDETAG
:
1782 case COMPLEX_BASE_STRING_WIDETAG
:
1783 case COMPLEX_VECTOR_NIL_WIDETAG
:
1784 case COMPLEX_BIT_VECTOR_WIDETAG
:
1785 case COMPLEX_VECTOR_WIDETAG
:
1786 case COMPLEX_ARRAY_WIDETAG
:
1787 // And the other entirely boxed objects.
1788 case SYMBOL_HEADER_WIDETAG
:
1789 case VALUE_CELL_HEADER_WIDETAG
:
1790 case WEAK_POINTER_WIDETAG
:
1792 case COMPLEX_WIDETAG
:
1793 // Use the sizing functions for generality.
1794 // Symbols can contain strange header bytes,
1795 // and vectors might have a padding word, etc.
1796 adjust_words(where
+1, size
-1);
1804 walk_generation(void (*proc
)(lispobj
*,size_t),
1805 generation_index_t generation
);
1807 int* immobile_space_reloc_index
;
1808 int* immobile_space_relocs
;
1810 static int calc_n_pages(int n_objects
, int words_per_object
)
1812 words_per_object
= CEILING(words_per_object
, 2);
1813 int objects_per_page
= WORDS_PER_PAGE
/ words_per_object
;
1814 return (n_objects
+ objects_per_page
- 1) / objects_per_page
;
1817 // Take and return an untagged pointer, or 0 if the object did not survive GC.
1818 static lispobj
* get_load_address(lispobj
* old
)
1820 if (forwarding_pointer_p(old
))
1821 return native_pointer(forwarding_pointer_value(old
));
1822 gc_assert(immobile_filler_p(old
));
1826 // This does not accept (SIMPLE-ARRAY NIL (*))
1827 // (You'd have a pretty bad time trying making a symbol like that)
1828 static int schar(struct vector
* string
, int index
)
1830 #ifdef LISP_FEATURE_SB_UNICODE
1831 if (widetag_of(string
->header
) == SIMPLE_CHARACTER_STRING_WIDETAG
)
1832 return ((int*)string
->data
)[index
];
1834 return ((char*)string
->data
)[index
];
1837 #include "genesis/package.h"
1838 #define N_SYMBOL_KINDS 4
1840 // Return an integer 0..3 telling which block of symbols to relocate 'sym' into.
1841 // This is the same as the "symbol kind" in the allocator.
1842 // 0 = uninterned, 1 = keyword, 2 = other interned, 3 = special var
1843 static int classify_symbol(lispobj
* obj
)
1845 struct symbol
* symbol
= (struct symbol
*)obj
;
1846 if (symbol
->package
== NIL
) return 0;
1847 struct vector
* package_name
= (struct vector
*)
1848 native_pointer(((struct package
*)native_pointer(symbol
->package
))->_name
);
1849 if (widetag_of(package_name
->header
) == SIMPLE_BASE_STRING_WIDETAG
1850 && !strcmp((char*)package_name
->data
, "KEYWORD"))
1852 struct vector
* symbol_name
= (struct vector
*)native_pointer(symbol
->name
);
1853 if (symbol_name
->length
>= make_fixnum(2) &&
1854 schar(symbol_name
, 0) == '*' &&
1855 schar(symbol_name
, fixnum_value(symbol_name
->length
)-1) == '*')
1860 static char* compute_defrag_start_address()
1862 // For technical reasons, objects on the first few pages created by genesis
1863 // must never move at all. So figure out where the end of that subspace is.
1864 lispobj
* obj
= (lispobj
*)IMMOBILE_SPACE_START
;
1865 gc_assert(widetag_of(*obj
) == INSTANCE_HEADER_WIDETAG
);
1866 while (instance_layout(obj
) != LAYOUT_OF_PACKAGE
) {
1867 obj
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
);
1868 gc_assert(widetag_of(*obj
) == INSTANCE_HEADER_WIDETAG
);
1870 // Now find a page that does NOT have a package.
1872 obj
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
);
1873 } while (widetag_of(*obj
) == INSTANCE_HEADER_WIDETAG
1874 && instance_layout(obj
) == LAYOUT_OF_PACKAGE
);
1878 void defrag_immobile_space(int* components
)
1880 // Find the starting address of fixed-size objects that will undergo defrag.
1881 // Never move the first few pages of LAYOUTs or PACKAGEs created by genesis.
1882 // If codegen becomes smarter, things like layout of FUNCTION and some
1883 // some others can be used as immediate constants in compiled code.
1884 // With initial packages, it's mainly a debugging convenience that they not move.
1885 char* defrag_base
= compute_defrag_start_address();
1886 low_page_index_t page_index
= find_immobile_page_index(defrag_base
);
1890 // Count the number of symbols, fdefns, and layouts that will be relocated
1891 unsigned int obj_type_histo
[64], sym_kind_histo
[4];
1892 bzero(obj_type_histo
, sizeof obj_type_histo
);
1893 bzero(sym_kind_histo
, sizeof sym_kind_histo
);
1895 #if DEFRAGMENT_FIXEDOBJ_SUBSPACE
1896 for ( ; page_index
<= max_used_fixedobj_page
; ++page_index
) {
1897 int obj_spacing
= page_obj_align(page_index
) << WORD_SHIFT
;
1899 lispobj
* obj
= low_page_address(page_index
);
1900 lispobj
* limit
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
);
1901 for ( ; obj
< limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
1902 lispobj word
= *obj
;
1903 if (!fixnump(word
)) {
1904 if (widetag_of(word
) == SYMBOL_HEADER_WIDETAG
)
1905 ++sym_kind_histo
[classify_symbol(obj
)];
1907 ++obj_type_histo
[widetag_of(word
)/4];
1912 gc_assert(obj_type_histo
[INSTANCE_HEADER_WIDETAG
/4]);
1914 // Calculate space needed for fixedobj pages after defrag.
1915 // page order is: layouts, fdefns, GFs, symbols
1916 int n_layout_pages
= calc_n_pages(obj_type_histo
[INSTANCE_HEADER_WIDETAG
/4],
1917 LAYOUT_ALIGN
/ N_WORD_BYTES
);
1918 int n_fdefn_pages
= calc_n_pages(obj_type_histo
[FDEFN_WIDETAG
/4], FDEFN_SIZE
);
1919 int n_fin_pages
= calc_n_pages(obj_type_histo
[FUNCALLABLE_INSTANCE_HEADER_WIDETAG
/4],
1921 #if !(defined(LISP_FEATURE_IMMOBILE_CODE) && defined(LISP_FEATURE_COMPACT_INSTANCE_HEADER))
1922 gc_assert(n_fin_pages
== 0);
1924 char* layout_alloc_ptr
= defrag_base
;
1925 char* fdefn_alloc_ptr
= layout_alloc_ptr
+ n_layout_pages
* IMMOBILE_CARD_BYTES
;
1926 char* fin_alloc_ptr
= fdefn_alloc_ptr
+ n_fdefn_pages
* IMMOBILE_CARD_BYTES
;
1927 char* symbol_alloc_ptr
[N_SYMBOL_KINDS
+1];
1928 symbol_alloc_ptr
[0] = fin_alloc_ptr
+ n_fin_pages
* IMMOBILE_CARD_BYTES
;
1929 for (i
=0; i
<N_SYMBOL_KINDS
; ++i
)
1930 symbol_alloc_ptr
[i
+1] = symbol_alloc_ptr
[i
]
1931 + calc_n_pages(sym_kind_histo
[i
], SYMBOL_SIZE
) * IMMOBILE_CARD_BYTES
;
1932 char* ending_alloc_ptr
= symbol_alloc_ptr
[N_SYMBOL_KINDS
];
1934 fixedobj_tempspace
.n_bytes
= ending_alloc_ptr
- (char*)IMMOBILE_SPACE_START
;
1935 fixedobj_tempspace
.start
= calloc(fixedobj_tempspace
.n_bytes
, 1);
1936 // Copy the first few pages (the permanent pages) from immobile space
1937 // into the temporary copy, so that tempspace_addr()
1938 // does not have to return the unadjusted addr if below defrag_base.
1939 memcpy(fixedobj_tempspace
.start
, (char*)IMMOBILE_SPACE_START
,
1940 (lispobj
)defrag_base
- IMMOBILE_SPACE_START
);
1943 // Compute where each code component will be moved to.
1944 int n_code_components
= 0;
1945 for (i
=0 ; components
[i
*2] ; ++i
) {
1946 addr
= (lispobj
*)(long)components
[i
*2];
1947 gc_assert(lowtag_of((lispobj
)addr
) == OTHER_POINTER_LOWTAG
);
1948 addr
= native_pointer((lispobj
)addr
);
1949 int widetag
= widetag_of(*addr
);
1950 lispobj new_vaddr
= 0;
1951 // FIXME: generalize
1952 gc_assert(widetag
== CODE_HEADER_WIDETAG
);
1953 if (!immobile_filler_p(addr
)) {
1954 ++n_code_components
;
1955 new_vaddr
= IMMOBILE_VARYOBJ_SUBSPACE_START
+ varyobj_tempspace
.n_bytes
;
1956 varyobj_tempspace
.n_bytes
+= sizetab
[widetag
](addr
) << WORD_SHIFT
;
1958 components
[i
*2+1] = new_vaddr
;
1960 varyobj_tempspace
.start
= calloc(varyobj_tempspace
.n_bytes
, 1);
1962 printf("%d+%d+%d+%d objects... ",
1963 obj_type_histo
[INSTANCE_HEADER_WIDETAG
/4],
1964 obj_type_histo
[FDEFN_WIDETAG
/4],
1965 (sym_kind_histo
[0]+sym_kind_histo
[1]+
1966 sym_kind_histo
[2]+sym_kind_histo
[3]),
1969 // Permute varyobj space into tempspace and deposit forwarding pointers.
1971 for (i
=0 ; components
[i
*2] ; ++i
) {
1972 if ((new_vaddr
= components
[i
*2+1]) != 0) {
1973 addr
= native_pointer(components
[i
*2]);
1974 memcpy(tempspace_addr((void*)new_vaddr
), addr
,
1975 sizetab
[widetag_of(*addr
)](addr
) << WORD_SHIFT
);
1976 int displacement
= new_vaddr
- (lispobj
)addr
;
1977 switch (widetag_of(*addr
)) {
1978 case CODE_HEADER_WIDETAG
:
1979 for_each_simple_fun(index
, fun
, (struct code
*)addr
, 1, {
1980 set_forwarding_pointer((lispobj
*)fun
,
1981 make_lispobj((char*)fun
+ displacement
,
1982 FUN_POINTER_LOWTAG
));
1986 set_forwarding_pointer(addr
,
1987 make_lispobj((void*)new_vaddr
,
1988 OTHER_POINTER_LOWTAG
));
1992 #if DEFRAGMENT_FIXEDOBJ_SUBSPACE
1993 // Permute fixed-sized object pages and deposit forwarding pointers.
1994 for ( page_index
= find_immobile_page_index(defrag_base
) ;
1995 page_index
<= max_used_fixedobj_page
; ++page_index
) {
1996 int obj_spacing
= page_obj_align(page_index
) << WORD_SHIFT
;
1997 if (!obj_spacing
) continue;
1998 lispobj
* obj
= low_page_address(page_index
);
1999 lispobj
* limit
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
);
2000 for ( ; obj
< limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
2001 lispobj word
= *obj
;
2002 if (fixnump(word
)) continue;
2004 int lowtag
= OTHER_POINTER_LOWTAG
;
2005 int widetag
= widetag_of(word
);
2007 case INSTANCE_HEADER_WIDETAG
:
2008 alloc_ptr
= &layout_alloc_ptr
;
2009 lowtag
= INSTANCE_POINTER_LOWTAG
;
2011 case FUNCALLABLE_INSTANCE_HEADER_WIDETAG
:
2012 alloc_ptr
= &fin_alloc_ptr
;
2013 lowtag
= FUN_POINTER_LOWTAG
;
2016 alloc_ptr
= &fdefn_alloc_ptr
;
2018 case SYMBOL_HEADER_WIDETAG
:
2019 alloc_ptr
= &symbol_alloc_ptr
[classify_symbol(obj
)];
2022 lose("Unexpected widetag");
2024 lispobj
* new = (lispobj
*)*alloc_ptr
;
2025 lispobj end
= (lispobj
)new + obj_spacing
;
2026 #define ALIGN_MASK (IMMOBILE_CARD_BYTES - 1)
2027 if ((end
& ALIGN_MASK
) < ((lispobj
)new & ALIGN_MASK
) // wrapped
2028 && (end
& ALIGN_MASK
) != 0) // ok if exactly on the boundary
2029 new = (lispobj
*)(end
& ~ALIGN_MASK
); // snap to page
2031 memcpy(tempspace_addr(new), obj
, sizetab
[widetag
](obj
) << WORD_SHIFT
);
2032 set_forwarding_pointer(obj
, make_lispobj(new, lowtag
));
2033 *alloc_ptr
= (char*)new + obj_spacing
;
2036 #ifdef LISP_FEATURE_X86_64
2037 // Fixup JMP offset in fdefns, and self pointers in funcallable instances.
2038 // The former can not be done in the same pass as space permutation,
2039 // because we don't know the order in which a generic function and its
2040 // related fdefn will be reached. Were this attempted in a single pass,
2041 // it could miss a GF that will be moved after the fdefn is moved.
2042 // And it can't be done in fixup_space() because that does not know the
2043 // original address of each fdefn, so can't compute the absolute callee.
2044 for ( page_index
= find_immobile_page_index(defrag_base
) ;
2045 page_index
<= max_used_fixedobj_page
; ++page_index
) {
2046 int obj_spacing
= page_obj_align(page_index
) << WORD_SHIFT
;
2047 if (!obj_spacing
) continue;
2048 lispobj
* obj
= low_page_address(page_index
);
2049 lispobj
* limit
= (lispobj
*)((char*)obj
+ IMMOBILE_CARD_BYTES
);
2050 for ( ; obj
< limit
; obj
= (lispobj
*)((char*)obj
+ obj_spacing
) ) {
2051 if (fixnump(*obj
)) continue;
2052 gc_assert(forwarding_pointer_p(obj
));
2053 lispobj
* new = native_pointer(forwarding_pointer_value(obj
));
2054 switch (widetag_of(*tempspace_addr(new))) {
2056 // Fix displacement in JMP or CALL instruction.
2057 adjust_fdefn_entrypoint(tempspace_addr(new),
2058 (char*)new - (char*)obj
,
2059 (struct fdefn
*)obj
);
2061 case FUNCALLABLE_INSTANCE_HEADER_WIDETAG
:
2062 tempspace_addr(new)[1] = (lispobj
)(new + 4);
2067 #endif /* LISP_FEATURE_X86_64 */
2068 #endif /* DEFRAGMENT_FIXEDOBJ_SUBSPACE */
2070 #ifdef LISP_FEATURE_X86_64
2071 // Fix displacements in JMP and CALL instructions in code objects.
2072 // There are 2 arrays in use:
2073 // - the relocs[] array contains the address of any machine instruction
2074 // that needs to be altered on account of space relocation.
2075 // - the reloc_index[] array identifes the code component each reloc belongs to.
2076 // It is an array of pairs:
2077 // comp_ptr1, index1, comp_ptr2, index2 ... comp_ptrN, indexN, 0, index_max
2078 // The index following a component specifies the starting index within the
2079 // relocs[] array of the first reloc belonging to the respective component.
2080 // The ending reloc can be deduced from the next component's first reloc.
2081 for (i
= 0 ; immobile_space_reloc_index
[i
*2] ; ++i
) {
2082 lispobj code
= immobile_space_reloc_index
[i
*2] - OTHER_POINTER_LOWTAG
;
2084 if (code
>= READ_ONLY_SPACE_START
&& code
< READ_ONLY_SPACE_END
)
2085 load_addr
= code
; // This code can not be moved or GCed.
2087 load_addr
= (lispobj
)get_load_address((lispobj
*)code
);
2088 if (!load_addr
) continue; // Skip code that was dropped by GC
2089 int reloc_index
= immobile_space_reloc_index
[i
*2+1];
2090 int end_reloc_index
= immobile_space_reloc_index
[i
*2+3];
2091 for ( ; reloc_index
< end_reloc_index
; ++reloc_index
) {
2092 unsigned char* inst_addr
= (unsigned char*)(long)immobile_space_relocs
[reloc_index
];
2093 gc_assert(*inst_addr
== 0xE8 || *inst_addr
== 0xE9);
2094 unsigned int target_addr
= (int)(long)inst_addr
+ 5 + *(int*)(inst_addr
+1);
2095 int target_adjust
= 0;
2096 // Both this code and the jumped-to code can move.
2097 // For this component, adjust by the displacement by (old - new).
2098 // If the jump target moved, also adjust by its (new - old).
2099 // The target address can be either a JMP or CALL instruction
2100 // which resides in an fdefn, or a simple-fun. They can easily
2101 // be told apart by the first byte.
2102 if (immobile_space_p(target_addr
)) {
2104 unsigned char expect_widetag
;
2105 // KLUDGE: It would be more proper to search for the Lisp object
2106 // being called, rather than checking for a byte pattern.
2107 // Problem: though gc_search_space() understands FPs, it doesn't
2108 // work here, because objects aren't physically where the FP points.
2109 if ((*(char*)(long)target_addr
& 0xFE) == 0xE8) { // JMP or CALL
2110 // must be jumping into an fdefn
2111 gc_assert(target_addr
< IMMOBILE_SPACE_START
+IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE
);
2112 old_obj
= (lispobj
*)(target_addr
- offsetof(struct fdefn
, raw_addr
));
2113 expect_widetag
= FDEFN_WIDETAG
;
2114 } else if (*(unsigned long*)(unsigned long)target_addr
2115 == 0xFFFFFFFFE9058B48) {
2116 // "MOV RAX, [RIP-23]" (plus a byte of the next instruction)
2117 // indicates a funcallable instance with a self-contained trampoline.
2118 gc_assert(target_addr
< IMMOBILE_SPACE_START
+IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE
);
2119 old_obj
= (lispobj
*)(long)(target_addr
- (4*N_WORD_BYTES
));
2120 expect_widetag
= FUNCALLABLE_INSTANCE_HEADER_WIDETAG
;
2122 old_obj
= (lispobj
*)(target_addr
- offsetof(struct simple_fun
, code
));
2123 expect_widetag
= SIMPLE_FUN_HEADER_WIDETAG
;
2125 lispobj
* new_obj
= !forwarding_pointer_p(old_obj
) ? old_obj
:
2126 native_pointer(forwarding_pointer_value(old_obj
));
2127 gc_assert(widetag_of(*tempspace_addr(new_obj
)) == expect_widetag
);
2128 target_adjust
= (int)((char*)new_obj
- (char*)old_obj
);
2130 // If the instruction to fix has moved, then adjust for
2131 // its new address, and perform the fixup in tempspace.
2132 // Otherwise perform the fixup where the instruction is now.
2133 char* fixup_loc
= (immobile_space_p((lispobj
)inst_addr
) ?
2134 (char*)tempspace_addr(inst_addr
- code
+ load_addr
) :
2135 (char*)inst_addr
) + 1;
2136 *(int*)fixup_loc
+= target_adjust
+ (code
- load_addr
);
2140 free(immobile_space_relocs
);
2141 free(immobile_space_reloc_index
);
2143 // Fix Lisp pointers in static, immobile, and dynamic spaces
2144 fixup_space((lispobj
*)STATIC_SPACE_START
,
2145 (SYMBOL(STATIC_SPACE_FREE_POINTER
)->value
2146 - STATIC_SPACE_START
) >> WORD_SHIFT
);
2148 // Objects in immobile space are physically at 'tempspace',
2149 // but logically at their natural address. Perform fixups
2150 // at their current physical address.
2151 #if DEFRAGMENT_FIXEDOBJ_SUBSPACE
2152 fixup_space((lispobj
*)fixedobj_tempspace
.start
,
2153 fixedobj_tempspace
.n_bytes
>> WORD_SHIFT
);
2155 fixup_space((lispobj
*)IMMOBILE_SPACE_START
,
2156 IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE
>> WORD_SHIFT
);
2158 fixup_space((lispobj
*)varyobj_tempspace
.start
,
2159 varyobj_tempspace
.n_bytes
>> WORD_SHIFT
);
2162 // We can safely ignore allocation region boundaries.
2163 fixup_space((lispobj
*)DYNAMIC_SPACE_START
,
2166 dynamic_space_free_pointer
2168 SymbolValue(ALLOCATION_POINTER
,0)
2170 - DYNAMIC_SPACE_START
) >> WORD_SHIFT
);
2172 // Copy the spaces back where they belong.
2174 // Fixed-size objects: don't copy below the defrag_base - the first few
2175 // pages are totally static in regard to both lifetime and placement.
2176 // (It would "work" to copy them back - since they were copied into
2177 // the temp space, but it's just wasting time to do so)
2178 lispobj old_free_ptr
;
2180 #if DEFRAGMENT_FIXEDOBJ_SUBSPACE
2181 int n_static_bytes
= ((lispobj
)defrag_base
- IMMOBILE_SPACE_START
);
2182 memcpy((char*)defrag_base
,
2183 fixedobj_tempspace
.start
+ n_static_bytes
,
2184 fixedobj_tempspace
.n_bytes
- n_static_bytes
);
2185 // Zero-fill the unused remainder
2186 old_free_ptr
= SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
;
2187 free_ptr
= IMMOBILE_SPACE_START
+ fixedobj_tempspace
.n_bytes
;
2188 bzero((char*)free_ptr
, old_free_ptr
- free_ptr
);
2189 SYMBOL(IMMOBILE_FIXEDOBJ_FREE_POINTER
)->value
= free_ptr
;
2192 // Variable-size object pages.
2193 memcpy((char*)IMMOBILE_VARYOBJ_SUBSPACE_START
,
2194 varyobj_tempspace
.start
, varyobj_tempspace
.n_bytes
);
2195 // Zero-fill the unused remainder
2196 old_free_ptr
= SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
2197 free_ptr
= IMMOBILE_VARYOBJ_SUBSPACE_START
+ varyobj_tempspace
.n_bytes
;
2198 bzero((char*)free_ptr
, old_free_ptr
- free_ptr
);
2199 SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
= free_ptr
;
2200 if (free_ptr
& (IMMOBILE_CARD_BYTES
-1)) { // unless page-aligned
2201 int remainder
= IMMOBILE_CARD_BYTES
- (free_ptr
& (IMMOBILE_CARD_BYTES
-1));
2202 ((lispobj
*)free_ptr
)[0] = SIMPLE_ARRAY_FIXNUM_WIDETAG
;
2203 ((lispobj
*)free_ptr
)[1] = make_fixnum((remainder
>> WORD_SHIFT
) - 2);
2208 // It's easy to mess things up, so assert correctness before saving a core.
2209 printf("verifying defrag\n");
2210 page_attributes_valid
= 0;
2212 printf("verify passed\n");
2214 free(fixedobj_tempspace
.start
);
2215 free(varyobj_tempspace
.start
);
2219 void verify_immobile_page_protection(int keep_gen
, int new_gen
)
2221 low_page_index_t page
;
2222 lispobj
* end
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
2223 low_page_index_t end_page
= find_immobile_page_index((char*)end
-1);
2226 for (page
= FIRST_VARYOBJ_PAGE
; page
<= end_page
; ++page
) {
2227 if (!varyobj_page_touched(page
)) {
2228 lispobj
* page_begin
= low_page_address(page
);
2229 lispobj
* page_end
= page_begin
+ WORDS_PER_PAGE
;
2230 // Assert that there are no old->young pointers.
2231 obj
= varyobj_scan_start(page
);
2232 // Never scan past the free pointer.
2233 // FIXME: It is is supposed to work to scan past the free pointer
2234 // on the last page, but the allocator needs to plop an array header there,
2235 // and sometimes it doesn't.
2236 lispobj
* varyobj_free_ptr
= (lispobj
*)(SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
);
2237 if (page_end
> varyobj_free_ptr
) page_end
= varyobj_free_ptr
;
2238 for ( ; obj
< page_end
; obj
+= sizetab
[widetag_of(*obj
)](obj
) ) {
2239 if (!immobile_filler_p(obj
)
2240 && varyobj_points_to_younger_p(obj
, __immobile_obj_gen_bits(obj
),
2242 (char*)page_begin
, (char*)page_end
))
2243 lose("page WP bit on page %d is wrong\n", page
);
2249 // Fixup immediate values that encode Lisp object addresses
2250 // in immobile space.
2251 #include "forwarding-ptr.h"
2252 #ifdef LISP_FEATURE_X86_64
2253 void fixup_immobile_refs(struct code
* code
)
2255 struct varint_unpacker fixups
;
2256 varint_unpacker_init(&fixups
, code
->fixups
);
2257 char* instructions
= (char*)((lispobj
*)code
+ code_header_words(code
->header
));
2258 int prev_loc
= 0, loc
;
2259 while (varint_unpack(&fixups
, &loc
) && loc
!= 0) {
2260 // For extra compactness, each loc is relative to the prior,
2261 // so that the magnitudes are smaller.
2264 int* fixup_where
= (int*)(instructions
+ loc
);
2265 lispobj ptr
= (lispobj
)(*fixup_where
);
2266 if (is_lisp_pointer(ptr
)) {
2267 if (forwarding_pointer_p(native_pointer(ptr
)))
2268 *fixup_where
= (int)
2269 forwarding_pointer_value(native_pointer(ptr
));
2271 gc_assert(IMMOBILE_SPACE_START
<= ptr
&&
2272 ptr
< (IMMOBILE_SPACE_START
+IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE
));
2273 // It's an absolute interior pointer. search_immobile_space() works
2274 // at this point, because the page attributes on the pointee's page are valid
2275 lispobj
* obj
= search_immobile_space((void*)ptr
);
2276 if (forwarding_pointer_p(obj
)) {
2277 lispobj fpval
= forwarding_pointer_value(obj
);
2278 *fixup_where
= (int)(long)native_pointer(fpval
) + (ptr
- (lispobj
)obj
);
2285 #ifdef VERIFY_PAGE_GENS
2286 void check_fixedobj_page(int page
)
2288 // Every page should have a 'gens' mask which exactly reflects
2289 // the aggregate over all objects on that page. Verify that invariant,
2290 // checking all pages, not just the ones below the free pointer.
2291 int genmask
, obj_size
, obj_spacing
, i
, all_ok
= 1;
2292 lispobj
*obj
, *limit
, header
;
2293 int sees_younger
= 0;
2295 obj_size
= page_obj_size(page
);
2296 obj_spacing
= page_obj_align(page
);
2297 obj
= low_page_address(page
);
2298 limit
= obj
+ WORDS_PER_PAGE
- obj_spacing
;
2300 if (obj_size
== 0) {
2301 for (i
=0; i
<WORDS_PER_PAGE
; ++i
)
2302 gc_assert(obj
[i
]==0);
2303 gc_assert(fixedobj_pages
[page
].gens
==0);
2306 for ( ; obj
<= limit
; obj
+= obj_spacing
) {
2308 if (!fixnump(header
)) {
2309 int gen
= __immobile_obj_gen_bits(obj
);
2310 gc_assert(0 <= gen
&& gen
<= PSEUDO_STATIC_GENERATION
);
2312 if (fixedobj_points_to_younger_p(obj
, obj_size
, gen
, 0xff, 0xff))
2316 // It's not wrong if the gen0 bit is set spuriously, but it should only
2317 // happen at most once, on the first GC after image startup.
2318 // At all other times, the invariant should hold that if the freelist
2319 // indicated that space was available, and the new pointer differs,
2320 // then some gen0 object exists on the page.
2321 // The converse is true because of pseudo-atomicity of the allocator:
2322 // if some thread claimed a hole, then it also updated the freelist.
2323 // If it died before doing the latter, then the object allegedly created
2324 // was never really live, so won't contain any pointers.
2325 if (fixedobj_pages
[page
].gens
!= genmask
2326 && fixedobj_pages
[page
].gens
!= (genmask
|1)) {
2327 fprintf(stderr
, "Page #x%x @ %p: stored mask=%x actual=%x\n",
2328 page
, low_page_address(page
),
2329 fixedobj_pages
[page
].gens
, genmask
);
2332 if (fixedobj_page_wp(page
) && sees_younger
) {
2333 fprintf(stderr
, "Page #x%x @ %p: WP is wrong\n",
2334 page
, low_page_address(page
));
2340 int n_immobile_objects
;
2341 int *immobile_objects
, *immobile_objects_limit
;
2343 int comparator_eq(const void* a
, const void* b
) {
2344 return *(int*)a
- *(int*)b
;
2347 // Find the largest item less than or equal.
2348 // (useful for finding the object that contains a given pointer)
2349 int comparator_le(const void* a
, const void* b
) {
2350 int diff
= *(int*)a
- *(int*)b
;
2351 if (diff
<= 0) return diff
;
2352 // If looking to the right would see an item strictly greater
2353 // than the sought key, or there is nothing to the right,
2354 // then deem this an exact match.
2355 if (b
== (void*)immobile_objects_limit
|| ((int*)b
)[1] > *(int*)a
) return 0;
2359 // Find the smallest item greater than or equal.
2360 // useful for finding the lowest item at or after a page base address.
2361 int comparator_ge(const void* a
, const void* b
) {
2362 int diff
= *(int*)a
- *(int*)b
;
2363 if (diff
>= 0) return diff
;
2364 // If looking to the left would see an item strictly less
2365 // than the sought key, or there is nothing to the left
2366 // then deem this an exact match.
2367 if (b
== (void*)immobile_objects
|| ((int*)b
)[-1] < *(int*)a
) return 0;
2371 void check_varyobj_pages()
2373 // 1. Check that a linear scan sees only valid object headers,
2374 // and that it terminates exactly at IMMOBILE_CODE_FREE_POINTER.
2375 lispobj
* obj
= (lispobj
*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
2376 lispobj
* end
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
2377 low_page_index_t end_page
= find_immobile_page_index((char*)end
-1);
2379 n_immobile_objects
= 0;
2381 lispobj word
= *obj
;
2382 gc_assert(other_immediate_lowtag_p(word
));
2383 int n_words
= sizetab
[widetag_of(word
)](obj
);
2385 ++n_immobile_objects
;
2387 gc_assert(obj
== end
);
2389 // 2. Check that all scan_start_offsets are plausible.
2390 // Begin by collecting all object header locations into an array;
2391 immobile_objects
= calloc(n_immobile_objects
, sizeof (lispobj
));
2392 immobile_objects_limit
= immobile_objects
+ n_immobile_objects
- 1;
2393 obj
= (lispobj
*)IMMOBILE_VARYOBJ_SUBSPACE_START
;
2396 immobile_objects
[i
++] = (lispobj
)obj
;
2397 lispobj word
= *obj
;
2398 int n_words
= sizetab
[widetag_of(word
)](obj
);
2401 // Check that each page's scan start is a known immobile object
2402 // and that it is the right object.
2403 low_page_index_t page
;
2404 for (page
= FIRST_VARYOBJ_PAGE
; page
<= end_page
; ++page
) {
2405 lispobj page_addr
= (lispobj
)low_page_address(page
);
2406 int* found_below
= bsearch(&page_addr
, immobile_objects
, n_immobile_objects
,
2407 sizeof (int), comparator_le
);
2408 int* found_above
= bsearch(&page_addr
, immobile_objects
, n_immobile_objects
,
2409 sizeof (int), comparator_ge
);
2410 int stored_scan_start
= (int)(long)varyobj_scan_start(page
);
2411 lispobj
* scan_start_obj
= (lispobj
*)(long)*found_below
;
2412 if (scan_start_obj
!= (lispobj
*)(long)stored_scan_start
) {
2413 //printf("page %d: found-below=%p stored=%p\n", page, scan_start_obj, stored_scan_start);
2414 while (immobile_filler_p(scan_start_obj
)) {
2415 int nwords
= sizetab
[widetag_of(*scan_start_obj
)](scan_start_obj
);
2416 // printf("skipping %d words to %p\n", nwords, scan_start_obj + nwords);
2417 scan_start_obj
+= nwords
;
2418 // the stored scan start does not guarantee that it points
2419 // to a non-hole; we only assert that it *probably* does not.
2420 // As such, when computing the "correct" value, we allow
2421 // any value in between the legal bounding values for it.
2422 if ((int)(long)scan_start_obj
== stored_scan_start
)
2424 // If you hit the free pointer, or run off the page,
2425 // then the page is completely empty.
2426 if (scan_start_obj
== (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
2427 || scan_start_obj
>= (lispobj
*)low_page_address(page
+1)) {
2428 scan_start_obj
= low_page_address(page
+1);
2433 if (scan_start_obj
!= (lispobj
*)(long)stored_scan_start
)
2434 lose("page %d: stored_scan_start=%p does not match found %p\n",
2435 page
, stored_scan_start
, *found_below
);
2436 if (found_below
!= found_above
) {
2437 // the object below must touch this page.
2438 // if it didn't, there should be a higher object below.
2439 lispobj
* below
= (lispobj
*)(long)*found_below
;
2440 int n_words
= sizetab
[widetag_of(*below
)](below
);
2441 lispobj
* end
= below
+ n_words
;
2442 gc_assert(end
> (lispobj
*)page_addr
);
2445 free(immobile_objects
);
2447 // 3. The generation mask for each page is exactly the union
2448 // of generation numbers of object headers on the page.
2449 for (page
= FIRST_VARYOBJ_PAGE
; page
<= end_page
; ++page
) {
2450 if (!varyobj_page_scan_start_offset
[page
- FIRST_VARYOBJ_PAGE
])
2451 continue; // page is all holes or never used
2452 obj
= varyobj_scan_start(page
);
2453 lispobj word
= *obj
;
2454 int n_words
= sizetab
[widetag_of(word
)](obj
);
2455 // Skip the first object if it doesn't start on this page.
2456 if (obj
< (lispobj
*)low_page_address(page
)) obj
+= n_words
;
2457 lispobj
* limit
= (lispobj
*)low_page_address(page
) + WORDS_PER_PAGE
;
2458 lispobj
* freeptr
= (lispobj
*)SYMBOL(IMMOBILE_SPACE_FREE_POINTER
)->value
;
2459 if (limit
> freeptr
) limit
= freeptr
;
2461 for ( ; obj
< limit
; obj
+= sizetab
[widetag_of(*obj
)](obj
) ) {
2462 int gen
= __immobile_obj_gen_bits(obj
);
2463 if (immobile_filler_p(obj
)) {
2464 gc_assert(gen
== 0);
2466 gc_assert(0 <= gen
&& gen
<= PSEUDO_STATIC_GENERATION
);
2470 gc_assert(mask
== VARYOBJ_PAGE_GENS(page
));