2 * stop and copy GC based on Cheney's algorithm
6 * This software is part of the SBCL system. See the README file for
9 * This software is derived from the CMU CL system, which was
10 * written at Carnegie Mellon University and released into the
11 * public domain. The software is in the public domain and is
12 * provided with absolutely no warranty. See the COPYING and CREDITS
13 * files for more information.
18 #include <sys/resource.h>
24 #include "gc-internal.h"
26 #include "interrupt.h"
30 #include "genesis/static-symbols.h"
31 #include "genesis/primitive-objects.h"
35 /* So you need to debug? */
38 #define DEBUG_SPACE_PREDICATES
39 #define DEBUG_SCAVENGE_VERBOSE
40 #define DEBUG_COPY_VERBOSE
45 lispobj
*from_space_free_pointer
;
48 lispobj
*new_space_free_pointer
;
50 static void scavenge_newspace(void);
53 /* collecting garbage */
57 tv_diff(struct timeval
*x
, struct timeval
*y
)
59 return (((double) x
->tv_sec
+ (double) x
->tv_usec
* 1.0e-6) -
60 ((double) y
->tv_sec
+ (double) y
->tv_usec
* 1.0e-6));
64 #define BYTES_ZERO_BEFORE_END (1<<12)
66 /* FIXME do we need this? Doesn't it duplicate lisp code in
67 * scrub-control-stack? */
72 lispobj
*ptr
= current_control_stack_pointer
;
78 } while (((unsigned long)ptr
) & (BYTES_ZERO_BEFORE_END
-1));
83 } while (((unsigned long)ptr
) & (BYTES_ZERO_BEFORE_END
-1));
90 gc_general_alloc(long bytes
, int page_type_flag
, int quick_p
) {
91 lispobj
*new=new_space_free_pointer
;
92 new_space_free_pointer
+=(bytes
/N_WORD_BYTES
);
96 lispobj
copy_large_unboxed_object(lispobj object
, long nwords
) {
97 return copy_object(object
,nwords
);
99 lispobj
copy_unboxed_object(lispobj object
, long nwords
) {
100 return copy_object(object
,nwords
);
102 lispobj
copy_large_object(lispobj object
, long nwords
) {
103 return copy_object(object
,nwords
);
106 /* Note: The generic GC interface we're implementing passes us a
107 * last_generation argument. That's meaningless for us, since we're
108 * not a generational GC. So we ignore it. */
110 collect_garbage(generation_index_t ignore
)
113 struct timeval start_tv
, stop_tv
;
114 struct rusage start_rusage
, stop_rusage
;
115 double real_time
, system_time
, user_time
;
116 double percent_retained
, gc_rate
;
117 unsigned long size_discarded
;
119 unsigned long size_retained
;
120 lispobj
*current_static_space_free_pointer
;
121 unsigned long static_space_size
;
122 unsigned long control_stack_size
, binding_stack_size
;
124 struct thread
*th
=arch_os_get_current_thread();
127 printf("[Collecting garbage ... \n");
129 getrusage(RUSAGE_SELF
, &start_rusage
);
130 gettimeofday(&start_tv
, (struct timezone
*) 0);
133 /* it's possible that signals are blocked already if this was called
134 * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
136 sigaddset_blockable(&tmp
);
137 thread_sigmask(SIG_BLOCK
, &tmp
, &old
);
139 current_static_space_free_pointer
=
140 (lispobj
*) ((unsigned long)
141 SymbolValue(STATIC_SPACE_FREE_POINTER
,0));
144 /* Set up from space and new space pointers. */
146 from_space
= current_dynamic_space
;
147 from_space_free_pointer
= dynamic_space_free_pointer
;
150 fprintf(stderr
,"from_space = %lx\n",
151 (unsigned long) current_dynamic_space
);
153 if (current_dynamic_space
== (lispobj
*) DYNAMIC_0_SPACE_START
)
154 new_space
= (lispobj
*)DYNAMIC_1_SPACE_START
;
155 else if (current_dynamic_space
== (lispobj
*) DYNAMIC_1_SPACE_START
)
156 new_space
= (lispobj
*) DYNAMIC_0_SPACE_START
;
158 lose("GC lossage. Current dynamic space is bogus!\n");
160 new_space_free_pointer
= new_space
;
162 /* Initialize the weak pointer list. */
163 weak_pointers
= (struct weak_pointer
*) NULL
;
166 /* Scavenge all of the roots. */
168 printf("Scavenging interrupt contexts ...\n");
170 scavenge_interrupt_contexts();
173 printf("Scavenging interrupt handlers (%d bytes) ...\n",
174 (int)sizeof(interrupt_handlers
));
176 scavenge((lispobj
*) interrupt_handlers
,
177 sizeof(interrupt_handlers
) / sizeof(lispobj
));
179 /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
181 current_control_stack_pointer
-
182 (lispobj
*)th
->control_stack_start
;
184 printf("Scavenging the control stack at %p (%ld words) ...\n",
185 ((lispobj
*)th
->control_stack_start
),
188 scavenge(((lispobj
*)th
->control_stack_start
), control_stack_size
);
192 current_binding_stack_pointer
-
193 (lispobj
*)th
->binding_stack_start
;
195 printf("Scavenging the binding stack %x - %x (%d words) ...\n",
196 th
->binding_stack_start
,current_binding_stack_pointer
,
197 (int)(binding_stack_size
));
199 scavenge(((lispobj
*)th
->binding_stack_start
), binding_stack_size
);
202 current_static_space_free_pointer
- (lispobj
*) STATIC_SPACE_START
;
204 printf("Scavenging static space %x - %x (%d words) ...\n",
205 STATIC_SPACE_START
,current_static_space_free_pointer
,
206 (int)(static_space_size
));
208 scavenge(((lispobj
*)STATIC_SPACE_START
), static_space_size
);
210 /* Scavenge newspace. */
212 printf("Scavenging new space (%d bytes) ...\n",
213 (int)((new_space_free_pointer
- new_space
) * sizeof(lispobj
)));
218 #if defined(DEBUG_PRINT_GARBAGE)
219 print_garbage(from_space
, from_space_free_pointer
);
222 /* Scan the weak pointers. */
224 printf("Scanning weak hash tables ...\n");
226 scan_weak_hash_tables();
228 /* Scan the weak pointers. */
230 printf("Scanning weak pointers ...\n");
232 scan_weak_pointers();
236 printf("Flipping spaces ...\n");
239 /* Maybe FIXME: it's possible that we could significantly reduce
240 * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
241 * similar os-dependent tricks here */
242 os_zero((os_vm_address_t
) from_space
,
243 (os_vm_size_t
) dynamic_space_size
);
245 current_dynamic_space
= new_space
;
246 dynamic_space_free_pointer
= new_space_free_pointer
;
249 size_discarded
= (from_space_free_pointer
- from_space
) * sizeof(lispobj
);
251 size_retained
= (new_space_free_pointer
- new_space
) * sizeof(lispobj
);
253 os_flush_icache((os_vm_address_t
)new_space
, size_retained
);
257 printf("Zeroing empty part of control stack ...\n");
260 set_auto_gc_trigger(size_retained
+bytes_consed_between_gcs
);
261 thread_sigmask(SIG_SETMASK
, &old
, 0);
265 gettimeofday(&stop_tv
, (struct timezone
*) 0);
266 getrusage(RUSAGE_SELF
, &stop_rusage
);
270 percent_retained
= (((float) size_retained
) /
271 ((float) size_discarded
)) * 100.0;
273 printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
274 size_retained
, size_discarded
, percent_retained
);
276 real_time
= tv_diff(&stop_tv
, &start_tv
);
277 user_time
= tv_diff(&stop_rusage
.ru_utime
, &start_rusage
.ru_utime
);
278 system_time
= tv_diff(&stop_rusage
.ru_stime
, &start_rusage
.ru_stime
);
280 printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
281 real_time
, user_time
, system_time
);
283 gc_rate
= ((float) size_retained
/ (float) (1<<20)) / real_time
;
285 printf("%10.2f M bytes/sec collected.\n", gc_rate
);
293 scavenge_newspace(void)
295 lispobj
*here
, *next
;
298 while (here
< new_space_free_pointer
) {
299 /* printf("here=%lx, new_space_free_pointer=%lx\n",
300 here,new_space_free_pointer); */
301 next
= new_space_free_pointer
;
302 scavenge(here
, next
- here
);
303 scav_weak_hash_tables();
306 /* printf("done with newspace\n"); */
309 /* scavenging interrupt contexts */
311 static int boxed_registers
[] = BOXED_REGISTERS
;
314 scavenge_interrupt_context(os_context_t
*context
)
319 unsigned long lip_offset
;
320 int lip_register_pair
;
322 unsigned long pc_code_offset
;
323 #ifdef ARCH_HAS_LINK_REGISTER
324 unsigned long lr_code_offset
;
326 #ifdef ARCH_HAS_NPC_REGISTER
327 unsigned long npc_code_offset
;
329 #ifdef DEBUG_SCAVENGE_VERBOSE
330 fprintf(stderr
, "Scavenging interrupt context at 0x%x\n",context
);
332 /* Find the LIP's register pair and calculate its offset */
333 /* before we scavenge the context. */
335 lip
= *os_context_register_addr(context
, reg_LIP
);
336 /* 0x7FFFFFFF on 32-bit platforms;
337 0x7FFFFFFFFFFFFFFF on 64-bit platforms */
338 lip_offset
= (((unsigned long)1) << (N_WORD_BITS
- 1)) - 1;
339 lip_register_pair
= -1;
340 for (i
= 0; i
< (int)(sizeof(boxed_registers
) / sizeof(int)); i
++) {
342 unsigned long offset
;
345 index
= boxed_registers
[i
];
346 reg
= *os_context_register_addr(context
, index
);
347 /* would be using PTR if not for integer length issues */
348 if ((reg
& ~((1L<<N_LOWTAG_BITS
)-1)) <= lip
) {
350 if (offset
< lip_offset
) {
352 lip_register_pair
= index
;
358 /* Compute the PC's offset from the start of the CODE */
361 *os_context_pc_addr(context
) -
362 *os_context_register_addr(context
, reg_CODE
);
363 #ifdef ARCH_HAS_NPC_REGISTER
365 *os_context_npc_addr(context
) -
366 *os_context_register_addr(context
, reg_CODE
);
368 #ifdef ARCH_HAS_LINK_REGISTER
370 *os_context_lr_addr(context
) -
371 *os_context_register_addr(context
, reg_CODE
);
374 /* Scavenge all boxed registers in the context. */
375 for (i
= 0; i
< (int)(sizeof(boxed_registers
) / sizeof(int)); i
++) {
379 index
= boxed_registers
[i
];
380 foo
= *os_context_register_addr(context
,index
);
381 scavenge((lispobj
*) &foo
, 1);
382 *os_context_register_addr(context
,index
) = foo
;
384 /* this is unlikely to work as intended on bigendian
385 * 64 bit platforms */
388 os_context_register_addr(context
, index
), 1);
393 *os_context_register_addr(context
, reg_LIP
) =
394 *os_context_register_addr(context
, lip_register_pair
) + lip_offset
;
397 /* Fix the PC if it was in from space */
398 if (from_space_p(*os_context_pc_addr(context
)))
399 *os_context_pc_addr(context
) =
400 *os_context_register_addr(context
, reg_CODE
) + pc_code_offset
;
401 #ifdef ARCH_HAS_LINK_REGISTER
402 /* Fix the LR ditto; important if we're being called from
403 * an assembly routine that expects to return using blr, otherwise
405 if (from_space_p(*os_context_lr_addr(context
)))
406 *os_context_lr_addr(context
) =
407 *os_context_register_addr(context
, reg_CODE
) + lr_code_offset
;
410 #ifdef ARCH_HAS_NPC_REGISTER
411 if (from_space_p(*os_context_npc_addr(context
)))
412 *os_context_npc_addr(context
) =
413 *os_context_register_addr(context
, reg_CODE
) + npc_code_offset
;
417 void scavenge_interrupt_contexts(void)
420 os_context_t
*context
;
422 struct thread
*th
=arch_os_get_current_thread();
424 index
= fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX
,0));
427 #ifdef DEBUG_SCAVENGE_VERBOSE
428 fprintf(stderr
, "%d interrupt contexts to scan\n",index
);
430 for (i
= 0; i
< index
; i
++) {
431 context
= th
->interrupt_contexts
[i
];
432 scavenge_interrupt_context(context
);
440 print_garbage(lispobj
*from_space
, lispobj
*from_space_free_pointer
)
443 int total_words_not_copied
;
445 printf("Scanning from space ...\n");
447 total_words_not_copied
= 0;
449 while (start
< from_space_free_pointer
) {
451 int forwardp
, type
, nwords
;
455 forwardp
= is_lisp_pointer(object
) && new_space_p(object
);
461 tag
= lowtag_of(object
);
464 case LIST_POINTER_LOWTAG
:
467 case INSTANCE_POINTER_LOWTAG
:
468 printf("Don't know about instances yet!\n");
471 case FUN_POINTER_LOWTAG
:
474 case OTHER_POINTER_LOWTAG
:
475 pointer
= (lispobj
*) native_pointer(object
);
477 type
= widetag_of(header
);
478 nwords
= (sizetab
[type
])(pointer
);
480 default: nwords
=1; /* shut yer whinging, gcc */
483 type
= widetag_of(object
);
484 nwords
= (sizetab
[type
])(start
);
485 total_words_not_copied
+= nwords
;
486 printf("%4d words not copied at 0x%16lx; ",
487 nwords
, (unsigned long) start
);
488 printf("Header word is 0x%08x\n",
489 (unsigned int) object
);
493 printf("%d total words not copied.\n", total_words_not_copied
);
499 #define WEAK_POINTER_NWORDS \
500 CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
503 scav_weak_pointer(lispobj
*where
, lispobj object
)
505 /* Do not let GC scavenge the value slot of the weak pointer */
506 /* (that is why it is a weak pointer). Note: we could use */
507 /* the scav_unboxed method here. */
509 return WEAK_POINTER_NWORDS
;
513 search_read_only_space(void *pointer
)
515 lispobj
* start
= (lispobj
*)READ_ONLY_SPACE_START
;
516 lispobj
* end
= (lispobj
*)SymbolValue(READ_ONLY_SPACE_FREE_POINTER
,0);
517 if ((pointer
< (void *)start
) || (pointer
>= (void *)end
))
519 return (gc_search_space(start
,
520 (((lispobj
*)pointer
)+2)-start
,
521 (lispobj
*)pointer
));
525 search_static_space(void *pointer
)
527 lispobj
* start
= (lispobj
*)STATIC_SPACE_START
;
528 lispobj
* end
= (lispobj
*)SymbolValue(STATIC_SPACE_FREE_POINTER
,0);
529 if ((pointer
< (void *)start
) || (pointer
>= (void *)end
))
531 return (gc_search_space(start
,
532 (((lispobj
*)pointer
)+2)-start
,
533 (lispobj
*)pointer
));
537 search_dynamic_space(void *pointer
)
539 lispobj
*start
= (lispobj
*) current_dynamic_space
;
540 lispobj
*end
= (lispobj
*) dynamic_space_free_pointer
;
541 if ((pointer
< (void *)start
) || (pointer
>= (void *)end
))
543 return (gc_search_space(start
,
544 (((lispobj
*)pointer
)+2)-start
,
545 (lispobj
*)pointer
));
548 /* initialization. if gc_init can be moved to after core load, we could
549 * combine these two functions */
555 scavtab
[WEAK_POINTER_WIDETAG
] = scav_weak_pointer
;
559 gc_initialize_pointers(void)
561 /* FIXME: We do nothing here. We (briefly) misguidedly attempted
562 to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
563 forgetting that (a) actually it could be the other and (b) it's
564 set in coreparse.c anyway. There's a FIXME note left here to
565 note that current_dynamic_space is a violation of OAOO: we can
566 tell which dynamic space we're currently in by looking at
567 dynamic_space_free_pointer. -- CSR, 2002-08-09 */
573 /* noise to manipulate the gc trigger stuff */
575 /* Functions that substantially change the dynamic space free pointer
576 * (collect_garbage, purify) are responsible also for resetting the
578 void set_auto_gc_trigger(os_vm_size_t dynamic_usage
)
580 os_vm_address_t addr
;
583 addr
= os_round_up_to_page((os_vm_address_t
)current_dynamic_space
585 if (addr
< (os_vm_address_t
)dynamic_space_free_pointer
)
586 lose("set_auto_gc_trigger: tried to set gc trigger too low! (%ld < 0x%08lx)\n",
587 (unsigned long)dynamic_usage
,
588 (unsigned long)((os_vm_address_t
)dynamic_space_free_pointer
589 - (os_vm_address_t
)current_dynamic_space
));
591 length
= os_trunc_size_to_page(dynamic_space_size
- dynamic_usage
);
593 lose("set_auto_gc_trigger: tried to set gc trigger too high! (0x%08lx)\n",
594 (unsigned long)dynamic_usage
);
596 #if defined(SUNOS) || defined(SOLARIS)
597 os_invalidate(addr
, length
);
599 os_protect(addr
, length
, 0);
602 current_auto_gc_trigger
= (lispobj
*)addr
;
605 void clear_auto_gc_trigger(void)
607 os_vm_address_t addr
;
610 if (current_auto_gc_trigger
== NULL
)
613 addr
= (os_vm_address_t
)current_auto_gc_trigger
;
614 length
= dynamic_space_size
+ (os_vm_address_t
)current_dynamic_space
- addr
;
616 #if defined(SUNOS) || defined(SOLARIS)
617 /* don't want to force whole space into swapping mode... */
618 os_validate(addr
, length
);
620 os_protect(addr
, length
, OS_VM_PROT_ALL
);
623 current_auto_gc_trigger
= NULL
;
627 gc_trigger_hit(void *addr
)
629 if (current_auto_gc_trigger
== NULL
)
632 return (addr
>= (void *)current_auto_gc_trigger
&&
633 addr
<((void *)current_dynamic_space
+ dynamic_space_size
));
638 cheneygc_handle_wp_violation(os_context_t
*context
, void *addr
)
640 if(!foreign_function_call_active
&& gc_trigger_hit(addr
)){
641 struct thread
*thread
=arch_os_get_current_thread();
642 clear_auto_gc_trigger();
643 /* Don't flood the system with interrupts if the need to gc is
644 * already noted. This can happen for example when SUB-GC
645 * allocates or after a gc triggered in a WITHOUT-GCING. */
646 if (SymbolValue(GC_PENDING
,thread
) == NIL
) {
647 if (SymbolValue(GC_INHIBIT
,thread
) == NIL
) {
648 if (arch_pseudo_atomic_atomic(context
)) {
649 /* set things up so that GC happens when we finish
651 SetSymbolValue(GC_PENDING
,T
,thread
);
652 arch_set_pseudo_atomic_interrupted(context
);
657 SetSymbolValue(GC_PENDING
,T
,thread
);