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"
34 /* So you need to debug? */
37 #define DEBUG_SPACE_PREDICATES
38 #define DEBUG_SCAVENGE_VERBOSE
39 #define DEBUG_COPY_VERBOSE
44 lispobj *from_space_free_pointer;
47 lispobj *new_space_free_pointer;
49 static void scavenge_newspace(void);
50 static void scavenge_interrupt_contexts(void);
52 extern unsigned long bytes_consed_between_gcs;
55 /* collecting garbage */
59 tv_diff(struct timeval *x, struct timeval *y)
61 return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
62 ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
66 #define BYTES_ZERO_BEFORE_END (1<<12)
68 /* FIXME do we need this? Doesn't it duplicate lisp code in
69 * scrub-control-stack? */
74 lispobj *ptr = current_control_stack_pointer;
80 } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
85 } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
92 gc_general_alloc(long bytes, int unboxed_p, int quick_p) {
93 lispobj *new=new_space_free_pointer;
94 new_space_free_pointer+=(bytes/N_WORD_BYTES);
98 lispobj copy_large_unboxed_object(lispobj object, long nwords) {
99 return copy_object(object,nwords);
101 lispobj copy_unboxed_object(lispobj object, long nwords) {
102 return copy_object(object,nwords);
104 lispobj copy_large_object(lispobj object, long nwords) {
105 return copy_object(object,nwords);
108 /* Note: The generic GC interface we're implementing passes us a
109 * last_generation argument. That's meaningless for us, since we're
110 * not a generational GC. So we ignore it. */
112 collect_garbage(unsigned ignore)
115 struct timeval start_tv, stop_tv;
116 struct rusage start_rusage, stop_rusage;
117 double real_time, system_time, user_time;
118 double percent_retained, gc_rate;
119 unsigned long size_discarded;
121 unsigned long size_retained;
122 lispobj *current_static_space_free_pointer;
123 unsigned long static_space_size;
124 unsigned long control_stack_size, binding_stack_size;
126 struct thread *th=arch_os_get_current_thread();
127 struct interrupt_data *data=th->interrupt_data;
131 printf("[Collecting garbage ... \n");
133 getrusage(RUSAGE_SELF, &start_rusage);
134 gettimeofday(&start_tv, (struct timezone *) 0);
137 /* it's possible that signals are blocked already if this was called
138 * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
140 sigaddset_blockable(&tmp);
141 thread_sigmask(SIG_BLOCK, &tmp, &old);
143 current_static_space_free_pointer =
144 (lispobj *) ((unsigned long)
145 SymbolValue(STATIC_SPACE_FREE_POINTER,0));
148 /* Set up from space and new space pointers. */
150 from_space = current_dynamic_space;
151 from_space_free_pointer = dynamic_space_free_pointer;
154 fprintf(stderr,"from_space = %lx\n",
155 (unsigned long) current_dynamic_space);
157 if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
158 new_space = (lispobj *)DYNAMIC_1_SPACE_START;
159 else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
160 new_space = (lispobj *) DYNAMIC_0_SPACE_START;
162 lose("GC lossage. Current dynamic space is bogus!\n");
164 new_space_free_pointer = new_space;
166 /* Initialize the weak pointer list. */
167 weak_pointers = (struct weak_pointer *) NULL;
170 /* Scavenge all of the roots. */
172 printf("Scavenging interrupt contexts ...\n");
174 scavenge_interrupt_contexts();
177 printf("Scavenging interrupt handlers (%d bytes) ...\n",
178 (int)sizeof(interrupt_handlers));
180 scavenge((lispobj *) data->interrupt_handlers,
181 sizeof(data->interrupt_handlers) / sizeof(lispobj));
183 /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
185 current_control_stack_pointer-
186 (lispobj *)th->control_stack_start;
188 printf("Scavenging the control stack at %p (%ld words) ...\n",
189 ((lispobj *)th->control_stack_start),
192 scavenge(((lispobj *)th->control_stack_start), control_stack_size);
196 current_binding_stack_pointer -
197 (lispobj *)th->binding_stack_start;
199 printf("Scavenging the binding stack %x - %x (%d words) ...\n",
200 th->binding_stack_start,current_binding_stack_pointer,
201 (int)(binding_stack_size));
203 scavenge(((lispobj *)th->binding_stack_start), binding_stack_size);
206 current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
208 printf("Scavenging static space %x - %x (%d words) ...\n",
209 STATIC_SPACE_START,current_static_space_free_pointer,
210 (int)(static_space_size));
212 scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
214 /* Scavenge newspace. */
216 printf("Scavenging new space (%d bytes) ...\n",
217 (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
222 #if defined(DEBUG_PRINT_GARBAGE)
223 print_garbage(from_space, from_space_free_pointer);
226 /* Scan the weak pointers. */
228 printf("Scanning weak pointers ...\n");
230 scan_weak_pointers();
235 printf("Flipping spaces ...\n");
238 /* Maybe FIXME: it's possible that we could significantly reduce
239 * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
240 * similar os-dependent tricks here */
241 os_zero((os_vm_address_t) from_space,
242 (os_vm_size_t) DYNAMIC_SPACE_SIZE);
244 current_dynamic_space = new_space;
245 dynamic_space_free_pointer = new_space_free_pointer;
248 size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
250 size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
252 os_flush_icache((os_vm_address_t)new_space, size_retained);
256 printf("Zeroing empty part of control stack ...\n");
259 set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
260 thread_sigmask(SIG_SETMASK, &old, 0);
264 gettimeofday(&stop_tv, (struct timezone *) 0);
265 getrusage(RUSAGE_SELF, &stop_rusage);
269 percent_retained = (((float) size_retained) /
270 ((float) size_discarded)) * 100.0;
272 printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
273 size_retained, size_discarded, percent_retained);
275 real_time = tv_diff(&stop_tv, &start_tv);
276 user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
277 system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
279 printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
280 real_time, user_time, system_time);
282 gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
284 printf("%10.2f M bytes/sec collected.\n", gc_rate);
292 scavenge_newspace(void)
294 lispobj *here, *next;
297 while (here < new_space_free_pointer) {
298 /* printf("here=%lx, new_space_free_pointer=%lx\n",
299 here,new_space_free_pointer); */
300 next = new_space_free_pointer;
301 scavenge(here, next - here);
304 /* printf("done with newspace\n"); */
307 /* scavenging interrupt contexts */
309 static int boxed_registers[] = BOXED_REGISTERS;
312 scavenge_interrupt_context(os_context_t *context)
317 unsigned long lip_offset;
318 int lip_register_pair;
320 unsigned long pc_code_offset;
321 #ifdef ARCH_HAS_LINK_REGISTER
322 unsigned long lr_code_offset;
324 #ifdef ARCH_HAS_NPC_REGISTER
325 unsigned long npc_code_offset;
327 #ifdef DEBUG_SCAVENGE_VERBOSE
328 fprintf(stderr, "Scavenging interrupt context at 0x%x\n",context);
330 /* Find the LIP's register pair and calculate its offset */
331 /* before we scavenge the context. */
333 lip = *os_context_register_addr(context, reg_LIP);
334 /* 0x7FFFFFFF on 32-bit platforms;
335 0x7FFFFFFFFFFFFFFF on 64-bit platforms */
336 lip_offset = (((unsigned long)1) << (N_WORD_BITS - 1)) - 1;
337 lip_register_pair = -1;
338 for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
343 index = boxed_registers[i];
344 reg = *os_context_register_addr(context, index);
345 /* would be using PTR if not for integer length issues */
346 if ((reg & ~((1L<<N_LOWTAG_BITS)-1)) <= lip) {
348 if (offset < lip_offset) {
350 lip_register_pair = index;
356 /* Compute the PC's offset from the start of the CODE */
359 *os_context_pc_addr(context) -
360 *os_context_register_addr(context, reg_CODE);
361 #ifdef ARCH_HAS_NPC_REGISTER
363 *os_context_npc_addr(context) -
364 *os_context_register_addr(context, reg_CODE);
366 #ifdef ARCH_HAS_LINK_REGISTER
368 *os_context_lr_addr(context) -
369 *os_context_register_addr(context, reg_CODE);
372 /* Scavenge all boxed registers in the context. */
373 for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
377 index = boxed_registers[i];
378 foo = *os_context_register_addr(context,index);
379 scavenge((lispobj *) &foo, 1);
380 *os_context_register_addr(context,index) = foo;
382 /* this is unlikely to work as intended on bigendian
383 * 64 bit platforms */
386 os_context_register_addr(context, index), 1);
391 *os_context_register_addr(context, reg_LIP) =
392 *os_context_register_addr(context, lip_register_pair) + lip_offset;
395 /* Fix the PC if it was in from space */
396 if (from_space_p(*os_context_pc_addr(context)))
397 *os_context_pc_addr(context) =
398 *os_context_register_addr(context, reg_CODE) + pc_code_offset;
399 #ifdef ARCH_HAS_LINK_REGISTER
400 /* Fix the LR ditto; important if we're being called from
401 * an assembly routine that expects to return using blr, otherwise
403 if (from_space_p(*os_context_lr_addr(context)))
404 *os_context_lr_addr(context) =
405 *os_context_register_addr(context, reg_CODE) + lr_code_offset;
408 #ifdef ARCH_HAS_NPC_REGISTER
409 if (from_space_p(*os_context_npc_addr(context)))
410 *os_context_npc_addr(context) =
411 *os_context_register_addr(context, reg_CODE) + npc_code_offset;
415 void scavenge_interrupt_contexts(void)
418 os_context_t *context;
420 struct thread *th=arch_os_get_current_thread();
422 index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX,0));
425 #ifdef DEBUG_SCAVENGE_VERBOSE
426 fprintf(stderr, "%d interrupt contexts to scan\n",index);
428 for (i = 0; i < index; i++) {
429 context = th->interrupt_contexts[i];
430 scavenge_interrupt_context(context);
438 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
441 int total_words_not_copied;
443 printf("Scanning from space ...\n");
445 total_words_not_copied = 0;
447 while (start < from_space_free_pointer) {
449 int forwardp, type, nwords;
453 forwardp = is_lisp_pointer(object) && new_space_p(object);
459 tag = lowtag_of(object);
462 case LIST_POINTER_LOWTAG:
465 case INSTANCE_POINTER_LOWTAG:
466 printf("Don't know about instances yet!\n");
469 case FUN_POINTER_LOWTAG:
472 case OTHER_POINTER_LOWTAG:
473 pointer = (lispobj *) native_pointer(object);
475 type = widetag_of(header);
476 nwords = (sizetab[type])(pointer);
478 default: nwords=1; /* shut yer whinging, gcc */
481 type = widetag_of(object);
482 nwords = (sizetab[type])(start);
483 total_words_not_copied += nwords;
484 printf("%4d words not copied at 0x%16lx; ",
485 nwords, (unsigned long) start);
486 printf("Header word is 0x%08x\n",
487 (unsigned int) object);
491 printf("%d total words not copied.\n", total_words_not_copied);
495 /* vector-like objects */
498 scav_vector(lispobj *where, lispobj object)
500 if (HeaderValue(object) == subtype_VectorValidHashing) {
502 (subtype_VectorMustRehash<<N_WIDETAG_BITS) | SIMPLE_VECTOR_WIDETAG;
511 #define WEAK_POINTER_NWORDS \
512 CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
515 scav_weak_pointer(lispobj *where, lispobj object)
517 /* Do not let GC scavenge the value slot of the weak pointer */
518 /* (that is why it is a weak pointer). Note: we could use */
519 /* the scav_unboxed method here. */
521 return WEAK_POINTER_NWORDS;
525 search_read_only_space(void *pointer)
527 lispobj* start = (lispobj*)READ_ONLY_SPACE_START;
528 lispobj* end = (lispobj*)SymbolValue(READ_ONLY_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_static_space(void *pointer)
539 lispobj* start = (lispobj*)STATIC_SPACE_START;
540 lispobj* end = (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0);
541 if ((pointer < (void *)start) || (pointer >= (void *)end))
543 return (gc_search_space(start,
544 (((lispobj *)pointer)+2)-start,
545 (lispobj *)pointer));
549 search_dynamic_space(void *pointer)
551 lispobj *start = (lispobj *) current_dynamic_space;
552 lispobj *end = (lispobj *) dynamic_space_free_pointer;
553 if ((pointer < (void *)start) || (pointer >= (void *)end))
555 return (gc_search_space(start,
556 (((lispobj *)pointer)+2)-start,
557 (lispobj *)pointer));
560 /* initialization. if gc_init can be moved to after core load, we could
561 * combine these two functions */
567 scavtab[SIMPLE_VECTOR_WIDETAG] = scav_vector;
568 scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
572 gc_initialize_pointers(void)
574 /* FIXME: We do nothing here. We (briefly) misguidedly attempted
575 to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
576 forgetting that (a) actually it could be the other and (b) it's
577 set in coreparse.c anyway. There's a FIXME note left here to
578 note that current_dynamic_space is a violation of OAOO: we can
579 tell which dynamic space we're currently in by looking at
580 dynamic_space_free_pointer. -- CSR, 2002-08-09 */
586 /* noise to manipulate the gc trigger stuff */
588 /* Functions that substantially change the dynamic space free pointer
589 * (collect_garbage, purify) are responsible also for resettting the
591 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
593 os_vm_address_t addr=(os_vm_address_t)current_dynamic_space
595 long length = DYNAMIC_SPACE_SIZE - dynamic_usage;
597 if (addr < (os_vm_address_t)dynamic_space_free_pointer) {
599 "set_auto_gc_trigger: tried to set gc trigger too low! (%ld < 0x%08lx)\n",
600 (unsigned long)dynamic_usage,
601 (unsigned long)((os_vm_address_t)dynamic_space_free_pointer
602 - (os_vm_address_t)current_dynamic_space));
605 else if (length < 0) {
607 "set_auto_gc_trigger: tried to set gc trigger too high! (0x%08lx)\n",
608 (unsigned long)dynamic_usage);
612 addr=os_round_up_to_page(addr);
613 length=os_trunc_size_to_page(length);
615 #if defined(SUNOS) || defined(SOLARIS)
616 os_invalidate(addr,length);
618 os_protect(addr, length, 0);
621 current_auto_gc_trigger = (lispobj *)addr;
624 void clear_auto_gc_trigger(void)
626 if (current_auto_gc_trigger!=NULL){
627 #if defined(SUNOS) || defined(SOLARIS)/* don't want to force whole space into swapping mode... */
628 os_vm_address_t addr=(os_vm_address_t)current_auto_gc_trigger;
630 DYNAMIC_SPACE_SIZE + (os_vm_address_t)current_dynamic_space - addr;
632 os_validate(addr,length);
634 os_protect((os_vm_address_t)current_dynamic_space,
639 current_auto_gc_trigger = NULL;