63383f5e8d26a724bd45e3c631b498224a62dd33
[sbcl.git] / src / runtime / cheneygc.c
1 /*
2  * stop and copy GC based on Cheney's algorithm
3  */
4
5 /*
6  * This software is part of the SBCL system. See the README file for
7  * more information.
8  *
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.
14  */
15
16 #include <stdio.h>
17 #include <sys/time.h>
18 #include <sys/resource.h>
19 #include <signal.h>
20 #include "sbcl.h"
21 #include "runtime.h"
22 #include "os.h"
23 #include "gc.h"
24 #include "gc-internal.h"
25 #include "globals.h"
26 #include "interrupt.h"
27 #include "validate.h"
28 #include "lispregs.h"
29 #include "interr.h"
30 #include "genesis/static-symbols.h"
31 #include "genesis/primitive-objects.h"
32 #include "thread.h"
33
34 /* So you need to debug? */
35 #if 0
36 #define PRINTNOISE
37 #define DEBUG_SPACE_PREDICATES
38 #define DEBUG_SCAVENGE_VERBOSE
39 #define DEBUG_COPY_VERBOSE
40 #define DEBUG_CODE_GC
41 #endif
42
43 lispobj *from_space;
44 lispobj *from_space_free_pointer;
45
46 lispobj *new_space;
47 lispobj *new_space_free_pointer;
48
49 static void scavenge_newspace(void);
50 static void scavenge_interrupt_contexts(void);
51 extern struct interrupt_data * global_interrupt_data;
52
53 extern unsigned long bytes_consed_between_gcs;
54
55 \f
56 /* collecting garbage */
57
58 #ifdef PRINTNOISE
59 static double
60 tv_diff(struct timeval *x, struct timeval *y)
61 {
62     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
63             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
64 }
65 #endif
66
67 #define BYTES_ZERO_BEFORE_END (1<<12)
68
69 /* FIXME do we need this?  Doesn't it duplicate lisp code in 
70  * scrub-control-stack? */
71
72 static void
73 zero_stack(void)
74 {
75     lispobj *ptr = current_control_stack_pointer;
76  search:
77     do {
78         if (*ptr)
79             goto fill;
80         ptr++;
81     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
82     return;
83  fill:
84     do {
85         *ptr++ = 0;
86     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
87
88     goto search;
89 }
90
91
92 void *
93 gc_general_alloc(int bytes, int unboxed_p, int quick_p) {
94     lispobj *new=new_space_free_pointer;
95     new_space_free_pointer+=(bytes/N_WORD_BYTES);
96     return new;
97 }
98
99 lispobj  copy_large_unboxed_object(lispobj object, int nwords) {
100     return copy_object(object,nwords);
101 }
102 lispobj  copy_unboxed_object(lispobj object, int nwords) {
103     return copy_object(object,nwords);
104 }
105 lispobj  copy_large_object(lispobj object, int nwords) {
106     return copy_object(object,nwords);
107 }
108
109 /* Note: The generic GC interface we're implementing passes us a
110  * last_generation argument. That's meaningless for us, since we're
111  * not a generational GC. So we ignore it. */
112 void
113 collect_garbage(unsigned ignore)
114 {
115 #ifdef PRINTNOISE
116     struct timeval start_tv, stop_tv;
117     struct rusage start_rusage, stop_rusage;
118     double real_time, system_time, user_time;
119     double percent_retained, gc_rate;
120     unsigned long size_discarded;
121 #endif
122     unsigned long size_retained;
123     lispobj *current_static_space_free_pointer;
124     unsigned long static_space_size; 
125     unsigned long control_stack_size, binding_stack_size; 
126     sigset_t tmp, old;
127     struct thread *th=arch_os_get_current_thread();
128     struct interrupt_data *data=
129         th ? th->interrupt_data : global_interrupt_data;
130
131
132 #ifdef PRINTNOISE
133     printf("[Collecting garbage ... \n");
134         
135     getrusage(RUSAGE_SELF, &start_rusage);
136     gettimeofday(&start_tv, (struct timezone *) 0);
137 #endif
138         
139     /* it's possible that signals are blocked already if this was called 
140      * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
141     sigemptyset(&tmp);
142     sigaddset_blockable(&tmp);
143     sigprocmask(SIG_BLOCK, &tmp, &old);
144
145     current_static_space_free_pointer =
146         (lispobj *) ((unsigned long)
147                      SymbolValue(STATIC_SPACE_FREE_POINTER,0));
148
149
150     /* Set up from space and new space pointers. */
151
152     from_space = current_dynamic_space;
153     from_space_free_pointer = dynamic_space_free_pointer;
154
155 #ifdef PRINTNOISE
156     fprintf(stderr,"from_space = %lx\n",
157             (unsigned long) current_dynamic_space);
158 #endif
159     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
160         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
161     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
162         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
163     else {
164         lose("GC lossage.  Current dynamic space is bogus!\n");
165     }
166     new_space_free_pointer = new_space;
167
168     /* Initialize the weak pointer list. */
169     weak_pointers = (struct weak_pointer *) NULL;
170
171
172     /* Scavenge all of the roots. */
173 #ifdef PRINTNOISE
174     printf("Scavenging interrupt contexts ...\n");
175 #endif
176     scavenge_interrupt_contexts();
177
178 #ifdef PRINTNOISE
179     printf("Scavenging interrupt handlers (%d bytes) ...\n",
180            (int)sizeof(interrupt_handlers));
181 #endif
182     scavenge((lispobj *) data->interrupt_handlers,
183              sizeof(data->interrupt_handlers) / sizeof(lispobj));
184         
185     /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
186     control_stack_size = 
187         current_control_stack_pointer-
188         (lispobj *)th->control_stack_start;
189 #ifdef PRINTNOISE
190     printf("Scavenging the control stack at %p (%ld words) ...\n",
191            ((lispobj *)th->control_stack_start), 
192            control_stack_size);
193 #endif
194     scavenge(((lispobj *)th->control_stack_start), control_stack_size);
195                  
196
197     binding_stack_size = 
198         current_binding_stack_pointer - 
199         (lispobj *)th->binding_stack_start;
200 #ifdef PRINTNOISE
201     printf("Scavenging the binding stack %x - %x (%d words) ...\n",
202            th->binding_stack_start,current_binding_stack_pointer,
203            (int)(binding_stack_size));
204 #endif
205     scavenge(((lispobj *)th->binding_stack_start), binding_stack_size);
206                  
207     static_space_size = 
208         current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
209 #ifdef PRINTNOISE
210     printf("Scavenging static space %x - %x (%d words) ...\n",
211            STATIC_SPACE_START,current_static_space_free_pointer,
212            (int)(static_space_size));
213 #endif
214     scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
215
216     /* Scavenge newspace. */
217 #ifdef PRINTNOISE
218     printf("Scavenging new space (%d bytes) ...\n",
219            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
220 #endif
221     scavenge_newspace();
222
223
224 #if defined(DEBUG_PRINT_GARBAGE)
225     print_garbage(from_space, from_space_free_pointer);
226 #endif
227
228     /* Scan the weak pointers. */
229 #ifdef PRINTNOISE
230     printf("Scanning weak pointers ...\n");
231 #endif
232     scan_weak_pointers();
233
234
235     /* Flip spaces. */
236 #ifdef PRINTNOISE
237     printf("Flipping spaces ...\n");
238 #endif
239
240     os_zero((os_vm_address_t) current_dynamic_space,
241             (os_vm_size_t) DYNAMIC_SPACE_SIZE);
242
243     current_dynamic_space = new_space;
244     dynamic_space_free_pointer = new_space_free_pointer;
245
246 #ifdef PRINTNOISE
247     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
248 #endif
249     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
250
251     /* Zero stack. */
252 #ifdef PRINTNOISE
253     printf("Zeroing empty part of control stack ...\n");
254 #endif
255     zero_stack();
256     set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
257     sigprocmask(SIG_SETMASK, &old, 0);
258
259
260 #ifdef PRINTNOISE
261     gettimeofday(&stop_tv, (struct timezone *) 0);
262     getrusage(RUSAGE_SELF, &stop_rusage);
263
264     printf("done.]\n");
265         
266     percent_retained = (((float) size_retained) /
267                         ((float) size_discarded)) * 100.0;
268
269     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
270            size_retained, size_discarded, percent_retained);
271
272     real_time = tv_diff(&stop_tv, &start_tv);
273     user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
274     system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
275
276     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
277            real_time, user_time, system_time);
278
279     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
280         
281     printf("%10.2f M bytes/sec collected.\n", gc_rate);
282 #endif
283     /* os_flush_icache((os_vm_address_t) 0, sizeof(unsigned long)); */
284     /* Maybe FIXME: it's possible that we could significantly reduce 
285      * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or 
286      * similar os-dependent tricks here */
287 }
288
289 \f
290 /* scavenging */
291
292 static void
293 scavenge_newspace(void)
294 {
295     lispobj *here, *next;
296
297     here = new_space;
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         here = next;
304     }
305     /* printf("done with newspace\n"); */
306 }
307 \f
308 /* scavenging interrupt contexts */
309
310 static int boxed_registers[] = BOXED_REGISTERS;
311
312 static void
313 scavenge_interrupt_context(os_context_t *context)
314 {
315     int i;
316 #ifdef reg_LIP
317     unsigned long lip;
318     unsigned long lip_offset;
319     int lip_register_pair;
320 #endif
321     unsigned long pc_code_offset;
322 #ifdef ARCH_HAS_LINK_REGISTER
323     unsigned long lr_code_offset;
324 #endif
325 #ifdef ARCH_HAS_NPC_REGISTER
326     unsigned long npc_code_offset;
327 #endif
328 #ifdef DEBUG_SCAVENGE_VERBOSE
329     fprintf(stderr, "Scavenging interrupt context at 0x%x\n",context);
330 #endif
331     /* Find the LIP's register pair and calculate its offset */
332     /* before we scavenge the context. */
333 #ifdef reg_LIP
334     lip = *os_context_register_addr(context, reg_LIP);
335     /* 0x7FFFFFFF on 32-bit platforms;
336        0x7FFFFFFFFFFFFFFF on 64-bit platforms */
337     lip_offset = (((unsigned long)1) << (N_WORD_BITS - 1)) - 1;
338     lip_register_pair = -1;
339     for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
340         unsigned long reg;
341         long offset;
342         int index;
343
344         index = boxed_registers[i];
345         reg = *os_context_register_addr(context, index);
346         /* would be using PTR if not for integer length issues */
347         if ((reg & ~((1L<<N_LOWTAG_BITS)-1)) <= lip) {
348             offset = lip - reg;
349             if (offset < lip_offset) {
350                 lip_offset = offset;
351                 lip_register_pair = index;
352             }
353         }
354     }
355 #endif /* reg_LIP */
356
357     /* Compute the PC's offset from the start of the CODE */
358     /* register. */
359     pc_code_offset =
360         *os_context_pc_addr(context) - 
361         *os_context_register_addr(context, reg_CODE);
362 #ifdef ARCH_HAS_NPC_REGISTER
363     npc_code_offset =
364         *os_context_npc_addr(context) - 
365         *os_context_register_addr(context, reg_CODE);
366 #endif 
367 #ifdef ARCH_HAS_LINK_REGISTER
368     lr_code_offset =
369         *os_context_lr_addr(context) - 
370         *os_context_register_addr(context, reg_CODE);
371 #endif
372                
373     /* Scavenge all boxed registers in the context. */
374     for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
375         int index;
376         lispobj foo;
377                 
378         index = boxed_registers[i];
379         foo = *os_context_register_addr(context,index);
380         scavenge((lispobj *) &foo, 1);
381         *os_context_register_addr(context,index) = foo;
382
383         /* this is unlikely to work as intended on bigendian
384          * 64 bit platforms */
385
386         scavenge((lispobj *)
387                  os_context_register_addr(context, index), 1);
388     }
389
390 #ifdef reg_LIP
391     /* Fix the LIP */
392     *os_context_register_addr(context, reg_LIP) =
393         *os_context_register_addr(context, lip_register_pair) + lip_offset;
394 #endif /* reg_LIP */
395         
396     /* Fix the PC if it was in from space */
397     if (from_space_p(*os_context_pc_addr(context)))
398         *os_context_pc_addr(context) = 
399             *os_context_register_addr(context, reg_CODE) + pc_code_offset;
400 #ifdef ARCH_HAS_LINK_REGISTER
401     /* Fix the LR ditto; important if we're being called from 
402      * an assembly routine that expects to return using blr, otherwise
403      * harmless */
404     if (from_space_p(*os_context_lr_addr(context)))
405         *os_context_lr_addr(context) = 
406             *os_context_register_addr(context, reg_CODE) + lr_code_offset;
407 #endif
408
409 #ifdef ARCH_HAS_NPC_REGISTER
410     if (from_space_p(*os_context_npc_addr(context)))
411         *os_context_npc_addr(context) = 
412             *os_context_register_addr(context, reg_CODE) + npc_code_offset;
413 #endif
414 }
415
416 void scavenge_interrupt_contexts(void)
417 {
418     int i, index;
419     os_context_t *context;
420
421     struct thread *th=arch_os_get_current_thread();
422     struct interrupt_data *data=
423         th ? th->interrupt_data : global_interrupt_data;
424
425     index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX,0));
426
427
428 #ifdef DEBUG_SCAVENGE_VERBOSE
429     fprintf(stderr, "%d interrupt contexts to scan\n",index);
430 #endif
431     for (i = 0; i < index; i++) {
432         context = th->interrupt_contexts[i];
433         scavenge_interrupt_context(context); 
434     }
435 }
436
437 \f
438 /* debugging code */
439
440 void
441 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
442 {
443     lispobj *start;
444     int total_words_not_copied;
445
446     printf("Scanning from space ...\n");
447
448     total_words_not_copied = 0;
449     start = from_space;
450     while (start < from_space_free_pointer) {
451         lispobj object;
452         int forwardp, type, nwords;
453         lispobj header;
454
455         object = *start;
456         forwardp = is_lisp_pointer(object) && new_space_p(object);
457
458         if (forwardp) {
459             int tag;
460             lispobj *pointer;
461
462             tag = lowtag_of(object);
463
464             switch (tag) {
465             case LIST_POINTER_LOWTAG:
466                 nwords = 2;
467                 break;
468             case INSTANCE_POINTER_LOWTAG:
469                 printf("Don't know about instances yet!\n");
470                 nwords = 1;
471                 break;
472             case FUN_POINTER_LOWTAG:
473                 nwords = 1;
474                 break;
475             case OTHER_POINTER_LOWTAG:
476                 pointer = (lispobj *) native_pointer(object);
477                 header = *pointer;
478                 type = widetag_of(header);
479                 nwords = (sizetab[type])(pointer);
480                 break;
481             default: nwords=1;  /* shut yer whinging, gcc */
482             }
483         } else {
484             type = widetag_of(object);
485             nwords = (sizetab[type])(start);
486             total_words_not_copied += nwords;
487             printf("%4d words not copied at 0x%16lx; ",
488                    nwords, (unsigned long) start);
489             printf("Header word is 0x%08x\n", 
490                    (unsigned int) object);
491         }
492         start += nwords;
493     }
494     printf("%d total words not copied.\n", total_words_not_copied);
495 }
496
497 \f
498 /* code and code-related objects */
499
500 /* FIXME (1) this could probably be defined using something like
501  *  sizeof(lispobj)*floor(sizeof(struct simple_fun)/sizeof(lispobj))
502  *    -  FUN_POINTER_LOWTAG
503  * as I'm reasonably sure that simple_fun->code must always be the 
504  * last slot in the object 
505
506  * FIXME (2) it also appears in purify.c, and it has a different value
507  * for SPARC users in that bit
508  */
509
510 #define FUN_RAW_ADDR_OFFSET (6*sizeof(lispobj) - FUN_POINTER_LOWTAG)
511
512 /* Note: on the sparc we don't have to do anything special for fdefns, */
513 /* 'cause the raw-addr has a function lowtag. */
514 #ifndef LISP_FEATURE_SPARC
515 static int
516 scav_fdefn(lispobj *where, lispobj object)
517 {
518     struct fdefn *fdefn;
519
520     fdefn = (struct fdefn *)where;
521     
522     if ((char *)(fdefn->fun + FUN_RAW_ADDR_OFFSET) 
523         == (char *)((unsigned long)(fdefn->raw_addr))) {
524         scavenge(where + 1, sizeof(struct fdefn)/sizeof(lispobj) - 1);
525         fdefn->raw_addr =
526             (u32) ((char *) LOW_WORD(fdefn->fun)) + FUN_RAW_ADDR_OFFSET;
527         return sizeof(struct fdefn) / sizeof(lispobj);
528     }
529     else
530         return 1;
531 }
532 #endif
533
534
535 \f
536 /* vector-like objects */
537
538 static int
539 scav_vector(lispobj *where, lispobj object)
540 {
541     if (HeaderValue(object) == subtype_VectorValidHashing) {
542         *where =
543             (subtype_VectorMustRehash<<N_WIDETAG_BITS) | SIMPLE_VECTOR_WIDETAG;
544     }
545
546     return 1;
547 }
548
549 \f
550 /* weak pointers */
551
552 #define WEAK_POINTER_NWORDS \
553         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
554
555 static int
556 scav_weak_pointer(lispobj *where, lispobj object)
557 {
558     /* Do not let GC scavenge the value slot of the weak pointer */
559     /* (that is why it is a weak pointer).  Note:  we could use */
560     /* the scav_unboxed method here. */
561
562     return WEAK_POINTER_NWORDS;
563 }
564 \f
565 lispobj *
566 search_read_only_space(void *pointer)
567 {
568     lispobj* start = (lispobj*)READ_ONLY_SPACE_START;
569     lispobj* end = (lispobj*)SymbolValue(READ_ONLY_SPACE_FREE_POINTER,0);
570     if ((pointer < (void *)start) || (pointer >= (void *)end))
571         return NULL;
572     return (search_space(start, 
573                          (((lispobj *)pointer)+2)-start, 
574                          (lispobj *)pointer));
575 }
576
577 lispobj *
578 search_static_space(void *pointer)
579 {
580     lispobj* start = (lispobj*)STATIC_SPACE_START;
581     lispobj* end = (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0);
582     if ((pointer < (void *)start) || (pointer >= (void *)end))
583         return NULL;
584     return (search_space(start, 
585                          (((lispobj *)pointer)+2)-start, 
586                          (lispobj *)pointer));
587 }
588
589 lispobj *
590 search_dynamic_space(void *pointer)
591 {
592     lispobj *start = (lispobj *) current_dynamic_space;
593     lispobj *end = (lispobj *) dynamic_space_free_pointer;
594     if ((pointer < (void *)start) || (pointer >= (void *)end))
595         return NULL;
596     return (search_space(start, 
597                          (((lispobj *)pointer)+2)-start, 
598                          (lispobj *)pointer));
599 }
600 \f
601 /* initialization.  if gc_init can be moved to after core load, we could
602  * combine these two functions */
603
604 void
605 gc_init(void)
606 {
607     gc_init_tables();
608     scavtab[SIMPLE_VECTOR_WIDETAG] = scav_vector;
609     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
610 }
611
612 void
613 gc_initialize_pointers(void)
614 {
615     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
616        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
617        forgetting that (a) actually it could be the other and (b) it's
618        set in coreparse.c anyway.  There's a FIXME note left here to
619        note that current_dynamic_space is a violation of OAOO: we can
620        tell which dynamic space we're currently in by looking at
621        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
622 }
623
624
625
626 \f
627 /* noise to manipulate the gc trigger stuff */
628
629 /* Functions that substantially change the dynamic space free pointer
630  * (collect_garbage, purify) are responsible also for resettting the
631  * auto_gc_trigger */
632 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
633 {
634     os_vm_address_t addr=(os_vm_address_t)current_dynamic_space 
635         + dynamic_usage;
636     long length = DYNAMIC_SPACE_SIZE - dynamic_usage;
637
638     if (addr < (os_vm_address_t)dynamic_space_free_pointer) {
639         fprintf(stderr,
640            "set_auto_gc_trigger: tried to set gc trigger too low! (%d < %p)\n",
641                 (unsigned int)dynamic_usage,
642                 (os_vm_address_t)dynamic_space_free_pointer
643                 - (os_vm_address_t)current_dynamic_space);
644         lose("lost");
645     }
646     else if (length < 0) {
647         fprintf(stderr,
648                 "set_auto_gc_trigger: tried to set gc trigger too high! (%p)\n",
649                 dynamic_usage);
650         lose("lost");
651     }
652
653     addr=os_round_up_to_page(addr);
654     length=os_trunc_size_to_page(length);
655
656 #if defined(SUNOS) || defined(SOLARIS)
657     os_invalidate(addr,length);
658 #else
659     os_protect(addr, length, 0);
660 #endif
661
662     current_auto_gc_trigger = (lispobj *)addr;
663 }
664
665 void clear_auto_gc_trigger(void)
666 {
667     if (current_auto_gc_trigger!=NULL){
668 #if defined(SUNOS) || defined(SOLARIS)/* don't want to force whole space into swapping mode... */
669         os_vm_address_t addr=(os_vm_address_t)current_auto_gc_trigger;
670         os_vm_size_t length=
671             DYNAMIC_SPACE_SIZE + (os_vm_address_t)current_dynamic_space - addr;
672
673         os_validate(addr,length);
674 #else
675         os_protect((os_vm_address_t)current_dynamic_space,
676                    DYNAMIC_SPACE_SIZE,
677                    OS_VM_PROT_ALL);
678 #endif
679
680         current_auto_gc_trigger = NULL;
681     }
682 }