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"
31 /* So you need to debug? */
34 #define DEBUG_SPACE_PREDICATES
35 #define DEBUG_SCAVENGE_VERBOSE
36 #define DEBUG_COPY_VERBOSE
41 lispobj *from_space_free_pointer;
44 lispobj *new_space_free_pointer;
46 static void scavenge_newspace(void);
47 static void scavenge_interrupt_contexts(void);
50 /* collecting garbage */
54 tv_diff(struct timeval *x, struct timeval *y)
56 return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
57 ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
61 #define BYTES_ZERO_BEFORE_END (1<<12)
63 /* FIXME do we need this? Doesn't it duplicate lisp code in
64 * scrub-control-stack? */
69 u32 *ptr = (u32 *)current_control_stack_pointer;
75 } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
80 } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
87 gc_general_alloc(int bytes, int unboxed_p, int quick_p) {
88 lispobj *new=new_space_free_pointer;
89 new_space_free_pointer+=(bytes/4);
93 lispobj copy_large_unboxed_object(lispobj object, int nwords) {
94 return copy_object(object,nwords);
96 lispobj copy_unboxed_object(lispobj object, int nwords) {
97 return copy_object(object,nwords);
99 lispobj copy_large_object(lispobj object, int nwords) {
100 return copy_object(object,nwords);
103 /* Note: The generic GC interface we're implementing passes us a
104 * last_generation argument. That's meaningless for us, since we're
105 * not a generational GC. So we ignore it. */
107 collect_garbage(unsigned ignore)
110 struct timeval start_tv, stop_tv;
111 struct rusage start_rusage, stop_rusage;
112 double real_time, system_time, user_time;
113 double percent_retained, gc_rate;
114 unsigned long size_discarded;
115 unsigned long size_retained;
117 lispobj *current_static_space_free_pointer;
118 unsigned long static_space_size;
119 unsigned long control_stack_size, binding_stack_size;
123 printf("[Collecting garbage ... \n");
125 getrusage(RUSAGE_SELF, &start_rusage);
126 gettimeofday(&start_tv, (struct timezone *) 0);
130 sigaddset_blockable(&tmp);
131 sigprocmask(SIG_BLOCK, &tmp, &old);
133 current_static_space_free_pointer =
134 (lispobj *) ((unsigned long)
135 SymbolValue(STATIC_SPACE_FREE_POINTER));
138 /* Set up from space and new space pointers. */
140 from_space = current_dynamic_space;
141 from_space_free_pointer = dynamic_space_free_pointer;
144 fprintf(stderr,"from_space = %lx\n",
145 (unsigned long) current_dynamic_space);
147 if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
148 new_space = (lispobj *)DYNAMIC_1_SPACE_START;
149 else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
150 new_space = (lispobj *) DYNAMIC_0_SPACE_START;
152 lose("GC lossage. Current dynamic space is bogus!\n");
154 new_space_free_pointer = new_space;
156 /* Initialize the weak pointer list. */
157 weak_pointers = (struct weak_pointer *) NULL;
160 /* Scavenge all of the roots. */
162 printf("Scavenging interrupt contexts ...\n");
164 scavenge_interrupt_contexts();
167 printf("Scavenging interrupt handlers (%d bytes) ...\n",
168 (int)sizeof(interrupt_handlers));
170 scavenge((lispobj *) interrupt_handlers,
171 sizeof(interrupt_handlers) / sizeof(lispobj));
173 /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
175 current_control_stack_pointer-
176 (lispobj *)CONTROL_STACK_START;
178 printf("Scavenging the control stack at %p (%ld words) ...\n",
179 ((lispobj *)CONTROL_STACK_START),
182 scavenge(((lispobj *)CONTROL_STACK_START), control_stack_size);
186 current_binding_stack_pointer -
187 (lispobj *)BINDING_STACK_START;
189 printf("Scavenging the binding stack %x - %x (%d words) ...\n",
190 BINDING_STACK_START,current_binding_stack_pointer,
191 (int)(binding_stack_size));
193 scavenge(((lispobj *)BINDING_STACK_START), binding_stack_size);
196 current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
198 printf("Scavenging static space %x - %x (%d words) ...\n",
199 STATIC_SPACE_START,current_static_space_free_pointer,
200 (int)(static_space_size));
202 scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
204 /* Scavenge newspace. */
206 printf("Scavenging new space (%d bytes) ...\n",
207 (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
212 #if defined(DEBUG_PRINT_GARBAGE)
213 print_garbage(from_space, from_space_free_pointer);
216 /* Scan the weak pointers. */
218 printf("Scanning weak pointers ...\n");
220 scan_weak_pointers();
225 printf("Flipping spaces ...\n");
228 os_zero((os_vm_address_t) current_dynamic_space,
229 (os_vm_size_t) DYNAMIC_SPACE_SIZE);
231 current_dynamic_space = new_space;
232 dynamic_space_free_pointer = new_space_free_pointer;
235 size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
236 size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
241 printf("Zeroing empty part of control stack ...\n");
245 sigprocmask(SIG_SETMASK, &old, 0);
249 gettimeofday(&stop_tv, (struct timezone *) 0);
250 getrusage(RUSAGE_SELF, &stop_rusage);
254 percent_retained = (((float) size_retained) /
255 ((float) size_discarded)) * 100.0;
257 printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
258 size_retained, size_discarded, percent_retained);
260 real_time = tv_diff(&stop_tv, &start_tv);
261 user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
262 system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
265 printf("Statistics:\n");
266 printf("%10.2f sec of real time\n", real_time);
267 printf("%10.2f sec of user time,\n", user_time);
268 printf("%10.2f sec of system time.\n", system_time);
270 printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
271 real_time, user_time, system_time);
274 gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
276 printf("%10.2f M bytes/sec collected.\n", gc_rate);
278 /* os_flush_icache((os_vm_address_t) 0, sizeof(unsigned long)); */
279 /* Maybe FIXME: it's possible that we could significantly reduce
280 * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
281 * similar os-dependent tricks here */
288 scavenge_newspace(void)
290 lispobj *here, *next;
293 while (here < new_space_free_pointer) {
294 /* printf("here=%lx, new_space_free_pointer=%lx\n",
295 here,new_space_free_pointer); */
296 next = new_space_free_pointer;
297 scavenge(here, next - here);
300 /* printf("done with newspace\n"); */
303 /* scavenging interrupt contexts */
305 static int boxed_registers[] = BOXED_REGISTERS;
308 scavenge_interrupt_context(os_context_t *context)
313 unsigned long lip_offset;
314 int lip_register_pair;
316 unsigned long pc_code_offset;
317 #ifdef ARCH_HAS_LINK_REGISTER
318 unsigned long lr_code_offset;
320 #ifdef ARCH_HAS_NPC_REGISTER
321 unsigned long npc_code_offset;
323 #ifdef DEBUG_SCAVENGE_VERBOSE
324 fprintf(stderr, "Scavenging interrupt context at 0x%x\n",context);
326 /* Find the LIP's register pair and calculate its offset */
327 /* before we scavenge the context. */
329 lip = *os_context_register_addr(context, reg_LIP);
330 /* 0x7FFFFFFF or 0x7FFFFFFFFFFFFFFF ? */
331 lip_offset = 0x7FFFFFFF;
332 lip_register_pair = -1;
333 for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
338 index = boxed_registers[i];
339 reg = *os_context_register_addr(context, index);
340 /* would be using PTR if not for integer length issues */
341 if ((reg & ~((1L<<N_LOWTAG_BITS)-1)) <= lip) {
343 if (offset < lip_offset) {
345 lip_register_pair = index;
351 /* Compute the PC's offset from the start of the CODE */
354 *os_context_pc_addr(context) -
355 *os_context_register_addr(context, reg_CODE);
356 #ifdef ARCH_HAS_NPC_REGISTER
358 *os_context_npc_addr(context) -
359 *os_context_register_addr(context, reg_CODE);
361 #ifdef ARCH_HAS_LINK_REGISTER
363 *os_context_lr_addr(context) -
364 *os_context_register_addr(context, reg_CODE);
367 /* Scavenge all boxed registers in the context. */
368 for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
372 index = boxed_registers[i];
373 foo = *os_context_register_addr(context,index);
374 scavenge((lispobj *) &foo, 1);
375 *os_context_register_addr(context,index) = foo;
377 /* this is unlikely to work as intended on bigendian
378 * 64 bit platforms */
381 os_context_register_addr(context, index), 1);
386 *os_context_register_addr(context, reg_LIP) =
387 *os_context_register_addr(context, lip_register_pair) + lip_offset;
390 /* Fix the PC if it was in from space */
391 if (from_space_p(*os_context_pc_addr(context)))
392 *os_context_pc_addr(context) =
393 *os_context_register_addr(context, reg_CODE) + pc_code_offset;
394 #ifdef ARCH_HAS_LINK_REGISTER
395 /* Fix the LR ditto; important if we're being called from
396 * an assembly routine that expects to return using blr, otherwise
398 if (from_space_p(*os_context_lr_addr(context)))
399 *os_context_lr_addr(context) =
400 *os_context_register_addr(context, reg_CODE) + lr_code_offset;
403 #ifdef ARCH_HAS_NPC_REGISTER
404 if (from_space_p(*os_context_npc_addr(context)))
405 *os_context_npc_addr(context) =
406 *os_context_register_addr(context, reg_CODE) + npc_code_offset;
410 void scavenge_interrupt_contexts(void)
413 os_context_t *context;
415 index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX));
417 #ifdef DEBUG_SCAVENGE_VERBOSE
418 fprintf(stderr, "%d interrupt contexts to scan\n",index);
420 for (i = 0; i < index; i++) {
421 context = lisp_interrupt_contexts[i];
422 scavenge_interrupt_context(context);
430 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
433 int total_words_not_copied;
435 printf("Scanning from space ...\n");
437 total_words_not_copied = 0;
439 while (start < from_space_free_pointer) {
441 int forwardp, type, nwords;
445 forwardp = is_lisp_pointer(object) && new_space_p(object);
451 tag = lowtag_of(object);
454 case LIST_POINTER_LOWTAG:
457 case INSTANCE_POINTER_LOWTAG:
458 printf("Don't know about instances yet!\n");
461 case FUN_POINTER_LOWTAG:
464 case OTHER_POINTER_LOWTAG:
465 pointer = (lispobj *) native_pointer(object);
467 type = widetag_of(header);
468 nwords = (sizetab[type])(pointer);
470 default: nwords=1; /* shut yer whinging, gcc */
473 type = widetag_of(object);
474 nwords = (sizetab[type])(start);
475 total_words_not_copied += nwords;
476 printf("%4d words not copied at 0x%16lx; ",
477 nwords, (unsigned long) start);
478 printf("Header word is 0x%08x\n",
479 (unsigned int) object);
483 printf("%d total words not copied.\n", total_words_not_copied);
487 /* code and code-related objects */
489 /* FIXME (1) this could probably be defined using something like
490 * sizeof(lispobj)*floor(sizeof(struct simple_fun)/sizeof(lispobj))
491 * - FUN_POINTER_LOWTAG
492 * as I'm reasonably sure that simple_fun->code must always be the
493 * last slot in the object
495 * FIXME (2) it also appears in purify.c, and it has a different value
496 * for SPARC users in that bit
499 #define FUN_RAW_ADDR_OFFSET (6*sizeof(lispobj) - FUN_POINTER_LOWTAG)
501 /* Note: on the sparc we don't have to do anything special for fdefns, */
502 /* 'cause the raw-addr has a function lowtag. */
503 #ifndef LISP_FEATURE_SPARC
505 scav_fdefn(lispobj *where, lispobj object)
509 fdefn = (struct fdefn *)where;
511 if ((char *)(fdefn->fun + FUN_RAW_ADDR_OFFSET)
512 == (char *)((unsigned long)(fdefn->raw_addr))) {
513 scavenge(where + 1, sizeof(struct fdefn)/sizeof(lispobj) - 1);
515 (u32) ((char *) LOW_WORD(fdefn->fun)) + FUN_RAW_ADDR_OFFSET;
516 return sizeof(struct fdefn) / sizeof(lispobj);
525 /* vector-like objects */
527 /* #define NWORDS(x,y) (CEILING((x),(y)) / (y)) */
530 scav_vector(lispobj *where, lispobj object)
532 if (HeaderValue(object) == subtype_VectorValidHashing) {
534 (subtype_VectorMustRehash<<N_WIDETAG_BITS) | SIMPLE_VECTOR_WIDETAG;
543 #define WEAK_POINTER_NWORDS \
544 CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
547 scav_weak_pointer(lispobj *where, lispobj object)
549 /* Do not let GC scavenge the value slot of the weak pointer */
550 /* (that is why it is a weak pointer). Note: we could use */
551 /* the scav_unboxed method here. */
553 return WEAK_POINTER_NWORDS;
557 /* initialization. if gc_init can be moved to after core load, we could
558 * combine these two functions */
564 scavtab[SIMPLE_VECTOR_WIDETAG] = scav_vector;
565 scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
569 gc_initialize_pointers(void)
571 /* FIXME: We do nothing here. We (briefly) misguidedly attempted
572 to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
573 forgetting that (a) actually it could be the other and (b) it's
574 set in coreparse.c anyway. There's a FIXME note left here to
575 note that current_dynamic_space is a violation of OAOO: we can
576 tell which dynamic space we're currently in by looking at
577 dynamic_space_free_pointer. -- CSR, 2002-08-09 */
583 /* noise to manipulate the gc trigger stuff */
585 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
587 os_vm_address_t addr=(os_vm_address_t)current_dynamic_space
590 long length = DYNAMIC_SPACE_SIZE - dynamic_usage;
592 if (addr < (os_vm_address_t)dynamic_space_free_pointer) {
594 "set_auto_gc_trigger: tried to set gc trigger too low! (%d < %p)\n",
595 (unsigned int)dynamic_usage,
596 (os_vm_address_t)dynamic_space_free_pointer
597 - (os_vm_address_t)current_dynamic_space);
600 else if (length < 0) {
602 "set_auto_gc_trigger: tried to set gc trigger too high! (%p)\n",
607 addr=os_round_up_to_page(addr);
608 length=os_trunc_size_to_page(length);
610 #if defined(SUNOS) || defined(SOLARIS)
611 os_invalidate(addr,length);
613 os_protect(addr, length, 0);
616 current_auto_gc_trigger = (lispobj *)addr;
619 void clear_auto_gc_trigger(void)
621 if (current_auto_gc_trigger!=NULL){
622 #if defined(SUNOS) || defined(SOLARIS)/* don't want to force whole space into swapping mode... */
623 os_vm_address_t addr=(os_vm_address_t)current_auto_gc_trigger;
625 DYNAMIC_SPACE_SIZE + (os_vm_address_t)current_dynamic_space - addr;
627 os_validate(addr,length);
629 os_protect((os_vm_address_t)current_dynamic_space,
634 current_auto_gc_trigger = NULL;