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