1.0.5.25:
[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
51 \f
52 /* collecting garbage */
53
54 #ifdef PRINTNOISE
55 static double
56 tv_diff(struct timeval *x, struct timeval *y)
57 {
58     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
59             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
60 }
61 #endif
62
63 #define BYTES_ZERO_BEFORE_END (1<<12)
64
65 /* FIXME do we need this?  Doesn't it duplicate lisp code in
66  * scrub-control-stack? */
67
68 static void
69 zero_stack(void)
70 {
71     lispobj *ptr = current_control_stack_pointer;
72  search:
73     do {
74         if (*ptr)
75             goto fill;
76         ptr++;
77     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
78     return;
79  fill:
80     do {
81         *ptr++ = 0;
82     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
83
84     goto search;
85 }
86
87
88 void *
89 gc_general_alloc(long bytes, int unboxed_p, int quick_p) {
90     lispobj *new=new_space_free_pointer;
91     new_space_free_pointer+=(bytes/N_WORD_BYTES);
92     return new;
93 }
94
95 lispobj  copy_large_unboxed_object(lispobj object, long nwords) {
96     return copy_object(object,nwords);
97 }
98 lispobj  copy_unboxed_object(lispobj object, long nwords) {
99     return copy_object(object,nwords);
100 }
101 lispobj  copy_large_object(lispobj object, long nwords) {
102     return copy_object(object,nwords);
103 }
104
105 /* Note: The generic GC interface we're implementing passes us a
106  * last_generation argument. That's meaningless for us, since we're
107  * not a generational GC. So we ignore it. */
108 void
109 collect_garbage(generation_index_t ignore)
110 {
111 #ifdef PRINTNOISE
112     struct timeval start_tv, stop_tv;
113     struct rusage start_rusage, stop_rusage;
114     double real_time, system_time, user_time;
115     double percent_retained, gc_rate;
116     unsigned long size_discarded;
117 #endif
118     unsigned long size_retained;
119     lispobj *current_static_space_free_pointer;
120     unsigned long static_space_size;
121     unsigned long control_stack_size, binding_stack_size;
122     sigset_t tmp, old;
123     struct thread *th=arch_os_get_current_thread();
124
125 #ifdef PRINTNOISE
126     printf("[Collecting garbage ... \n");
127
128     getrusage(RUSAGE_SELF, &start_rusage);
129     gettimeofday(&start_tv, (struct timezone *) 0);
130 #endif
131
132     /* it's possible that signals are blocked already if this was called
133      * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
134     sigemptyset(&tmp);
135     sigaddset_blockable(&tmp);
136     thread_sigmask(SIG_BLOCK, &tmp, &old);
137
138     current_static_space_free_pointer =
139         (lispobj *) ((unsigned long)
140                      SymbolValue(STATIC_SPACE_FREE_POINTER,0));
141
142
143     /* Set up from space and new space pointers. */
144
145     from_space = current_dynamic_space;
146     from_space_free_pointer = dynamic_space_free_pointer;
147
148 #ifdef PRINTNOISE
149     fprintf(stderr,"from_space = %lx\n",
150             (unsigned long) current_dynamic_space);
151 #endif
152     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
153         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
154     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
155         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
156     else {
157         lose("GC lossage.  Current dynamic space is bogus!\n");
158     }
159     new_space_free_pointer = new_space;
160
161     /* Initialize the weak pointer list. */
162     weak_pointers = (struct weak_pointer *) NULL;
163
164
165     /* Scavenge all of the roots. */
166 #ifdef PRINTNOISE
167     printf("Scavenging interrupt contexts ...\n");
168 #endif
169     scavenge_interrupt_contexts();
170
171 #ifdef PRINTNOISE
172     printf("Scavenging interrupt handlers (%d bytes) ...\n",
173            (int)sizeof(interrupt_handlers));
174 #endif
175     scavenge((lispobj *) interrupt_handlers,
176              sizeof(interrupt_handlers) / sizeof(lispobj));
177
178     /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
179     control_stack_size =
180         current_control_stack_pointer-
181         (lispobj *)th->control_stack_start;
182 #ifdef PRINTNOISE
183     printf("Scavenging the control stack at %p (%ld words) ...\n",
184            ((lispobj *)th->control_stack_start),
185            control_stack_size);
186 #endif
187     scavenge(((lispobj *)th->control_stack_start), control_stack_size);
188
189
190     binding_stack_size =
191         current_binding_stack_pointer -
192         (lispobj *)th->binding_stack_start;
193 #ifdef PRINTNOISE
194     printf("Scavenging the binding stack %x - %x (%d words) ...\n",
195            th->binding_stack_start,current_binding_stack_pointer,
196            (int)(binding_stack_size));
197 #endif
198     scavenge(((lispobj *)th->binding_stack_start), binding_stack_size);
199
200     static_space_size =
201         current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
202 #ifdef PRINTNOISE
203     printf("Scavenging static space %x - %x (%d words) ...\n",
204            STATIC_SPACE_START,current_static_space_free_pointer,
205            (int)(static_space_size));
206 #endif
207     scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
208
209     /* Scavenge newspace. */
210 #ifdef PRINTNOISE
211     printf("Scavenging new space (%d bytes) ...\n",
212            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
213 #endif
214     scavenge_newspace();
215
216
217 #if defined(DEBUG_PRINT_GARBAGE)
218     print_garbage(from_space, from_space_free_pointer);
219 #endif
220
221     /* Scan the weak pointers. */
222 #ifdef PRINTNOISE
223     printf("Scanning weak hash tables ...\n");
224 #endif
225     scan_weak_hash_tables();
226
227     /* Scan the weak pointers. */
228 #ifdef PRINTNOISE
229     printf("Scanning weak pointers ...\n");
230 #endif
231     scan_weak_pointers();
232
233     /* Flip spaces. */
234 #ifdef PRINTNOISE
235     printf("Flipping spaces ...\n");
236 #endif
237
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);
243
244     current_dynamic_space = new_space;
245     dynamic_space_free_pointer = new_space_free_pointer;
246
247 #ifdef PRINTNOISE
248     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
249 #endif
250     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
251
252     os_flush_icache((os_vm_address_t)new_space, size_retained);
253
254     /* Zero stack. */
255 #ifdef PRINTNOISE
256     printf("Zeroing empty part of control stack ...\n");
257 #endif
258     zero_stack();
259     set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
260     thread_sigmask(SIG_SETMASK, &old, 0);
261
262
263 #ifdef PRINTNOISE
264     gettimeofday(&stop_tv, (struct timezone *) 0);
265     getrusage(RUSAGE_SELF, &stop_rusage);
266
267     printf("done.]\n");
268
269     percent_retained = (((float) size_retained) /
270                         ((float) size_discarded)) * 100.0;
271
272     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
273            size_retained, size_discarded, percent_retained);
274
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);
278
279     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
280            real_time, user_time, system_time);
281
282     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
283
284     printf("%10.2f M bytes/sec collected.\n", gc_rate);
285 #endif
286 }
287
288 \f
289 /* scavenging */
290
291 static void
292 scavenge_newspace(void)
293 {
294     lispobj *here, *next;
295
296     here = new_space;
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);
302         scav_weak_hash_tables();
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
423     index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX,0));
424
425
426 #ifdef DEBUG_SCAVENGE_VERBOSE
427     fprintf(stderr, "%d interrupt contexts to scan\n",index);
428 #endif
429     for (i = 0; i < index; i++) {
430         context = th->interrupt_contexts[i];
431         scavenge_interrupt_context(context);
432     }
433 }
434
435 \f
436 /* debugging code */
437
438 void
439 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
440 {
441     lispobj *start;
442     int total_words_not_copied;
443
444     printf("Scanning from space ...\n");
445
446     total_words_not_copied = 0;
447     start = from_space;
448     while (start < from_space_free_pointer) {
449         lispobj object;
450         int forwardp, type, nwords;
451         lispobj header;
452
453         object = *start;
454         forwardp = is_lisp_pointer(object) && new_space_p(object);
455
456         if (forwardp) {
457             int tag;
458             lispobj *pointer;
459
460             tag = lowtag_of(object);
461
462             switch (tag) {
463             case LIST_POINTER_LOWTAG:
464                 nwords = 2;
465                 break;
466             case INSTANCE_POINTER_LOWTAG:
467                 printf("Don't know about instances yet!\n");
468                 nwords = 1;
469                 break;
470             case FUN_POINTER_LOWTAG:
471                 nwords = 1;
472                 break;
473             case OTHER_POINTER_LOWTAG:
474                 pointer = (lispobj *) native_pointer(object);
475                 header = *pointer;
476                 type = widetag_of(header);
477                 nwords = (sizetab[type])(pointer);
478                 break;
479             default: nwords=1;  /* shut yer whinging, gcc */
480             }
481         } else {
482             type = widetag_of(object);
483             nwords = (sizetab[type])(start);
484             total_words_not_copied += nwords;
485             printf("%4d words not copied at 0x%16lx; ",
486                    nwords, (unsigned long) start);
487             printf("Header word is 0x%08x\n",
488                    (unsigned int) object);
489         }
490         start += nwords;
491     }
492     printf("%d total words not copied.\n", total_words_not_copied);
493 }
494
495 \f
496 /* weak pointers */
497
498 #define WEAK_POINTER_NWORDS \
499         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
500
501 static long
502 scav_weak_pointer(lispobj *where, lispobj object)
503 {
504     /* Do not let GC scavenge the value slot of the weak pointer */
505     /* (that is why it is a weak pointer).  Note:  we could use */
506     /* the scav_unboxed method here. */
507
508     return WEAK_POINTER_NWORDS;
509 }
510 \f
511 lispobj *
512 search_read_only_space(void *pointer)
513 {
514     lispobj* start = (lispobj*)READ_ONLY_SPACE_START;
515     lispobj* end = (lispobj*)SymbolValue(READ_ONLY_SPACE_FREE_POINTER,0);
516     if ((pointer < (void *)start) || (pointer >= (void *)end))
517         return NULL;
518     return (gc_search_space(start,
519                             (((lispobj *)pointer)+2)-start,
520                             (lispobj *)pointer));
521 }
522
523 lispobj *
524 search_static_space(void *pointer)
525 {
526     lispobj* start = (lispobj*)STATIC_SPACE_START;
527     lispobj* end = (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0);
528     if ((pointer < (void *)start) || (pointer >= (void *)end))
529         return NULL;
530     return (gc_search_space(start,
531                             (((lispobj *)pointer)+2)-start,
532                             (lispobj *)pointer));
533 }
534
535 lispobj *
536 search_dynamic_space(void *pointer)
537 {
538     lispobj *start = (lispobj *) current_dynamic_space;
539     lispobj *end = (lispobj *) dynamic_space_free_pointer;
540     if ((pointer < (void *)start) || (pointer >= (void *)end))
541         return NULL;
542     return (gc_search_space(start,
543                             (((lispobj *)pointer)+2)-start,
544                             (lispobj *)pointer));
545 }
546 \f
547 /* initialization.  if gc_init can be moved to after core load, we could
548  * combine these two functions */
549
550 void
551 gc_init(void)
552 {
553     gc_init_tables();
554     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
555 }
556
557 void
558 gc_initialize_pointers(void)
559 {
560     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
561        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
562        forgetting that (a) actually it could be the other and (b) it's
563        set in coreparse.c anyway.  There's a FIXME note left here to
564        note that current_dynamic_space is a violation of OAOO: we can
565        tell which dynamic space we're currently in by looking at
566        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
567 }
568
569
570
571 \f
572 /* noise to manipulate the gc trigger stuff */
573
574 /* Functions that substantially change the dynamic space free pointer
575  * (collect_garbage, purify) are responsible also for resetting the
576  * auto_gc_trigger */
577 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
578 {
579     os_vm_address_t addr;
580     os_vm_size_t length;
581
582     addr = os_round_up_to_page((os_vm_address_t)current_dynamic_space
583                                + dynamic_usage);
584     if (addr < (os_vm_address_t)dynamic_space_free_pointer)
585         lose("set_auto_gc_trigger: tried to set gc trigger too low! (%ld < 0x%08lx)\n",
586              (unsigned long)dynamic_usage,
587              (unsigned long)((os_vm_address_t)dynamic_space_free_pointer
588                              - (os_vm_address_t)current_dynamic_space));
589
590     length = os_trunc_size_to_page(dynamic_space_size - dynamic_usage);
591     if (length < 0)
592         lose("set_auto_gc_trigger: tried to set gc trigger too high! (0x%08lx)\n",
593              (unsigned long)dynamic_usage);
594
595 #if defined(SUNOS) || defined(SOLARIS)
596     os_invalidate(addr, length);
597 #else
598     os_protect(addr, length, 0);
599 #endif
600
601     current_auto_gc_trigger = (lispobj *)addr;
602 }
603
604 void clear_auto_gc_trigger(void)
605 {
606     os_vm_address_t addr;
607     os_vm_size_t length;
608
609     if (current_auto_gc_trigger == NULL)
610         return;
611
612     addr = (os_vm_address_t)current_auto_gc_trigger;
613     length = dynamic_space_size + (os_vm_address_t)current_dynamic_space - addr;
614
615 #if defined(SUNOS) || defined(SOLARIS)
616     /* don't want to force whole space into swapping mode... */
617     os_validate(addr, length);
618 #else
619     os_protect(addr, length, OS_VM_PROT_ALL);
620 #endif
621
622     current_auto_gc_trigger = NULL;
623 }
624
625 static boolean
626 gc_trigger_hit(void *addr)
627 {
628     if (current_auto_gc_trigger == NULL)
629         return 0;
630     else{
631         return (addr >= (void *)current_auto_gc_trigger &&
632                 addr <((void *)current_dynamic_space + dynamic_space_size));
633     }
634 }
635
636 boolean
637 cheneygc_handle_wp_violation(os_context_t *context, void *addr)
638 {
639     if(!foreign_function_call_active && gc_trigger_hit(addr)){
640         struct thread *thread=arch_os_get_current_thread();
641         clear_auto_gc_trigger();
642         /* Don't flood the system with interrupts if the need to gc is
643          * already noted. This can happen for example when SUB-GC
644          * allocates or after a gc triggered in a WITHOUT-GCING. */
645         if (SymbolValue(GC_PENDING,thread) == NIL) {
646             if (SymbolValue(GC_INHIBIT,thread) == NIL) {
647                 if (arch_pseudo_atomic_atomic(context)) {
648                     /* set things up so that GC happens when we finish
649                      * the PA section */
650                     SetSymbolValue(GC_PENDING,T,thread);
651                     arch_set_pseudo_atomic_interrupted(context);
652                 } else {
653                     maybe_gc(context);
654                 }
655             } else {
656                 SetSymbolValue(GC_PENDING,T,thread);
657             }
658         }
659         return 1;
660     }
661     return 0;
662 }