src/runtime/gc-internal.h

   1 /*
   2  * garbage collection - shared definitions for modules "inside" the GC system
   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 #ifndef _GC_INTERNAL_H_
  17 #define _GC_INTERNAL_H_
  18
  19 #include "genesis/code.h"
  20 #include "genesis/simple-fun.h"
  21 #include "thread.h"
  22 #include "interr.h"
  23
  24 #ifdef LISP_FEATURE_GENCGC
  25 #include "gencgc-internal.h"
  26 #else
  27 #include "cheneygc-internal.h"
  28 #endif
  29
  30 /// Enable extra debug-only checks if DEBUG
  31 #ifdef DEBUG
  32 # define gc_dcheck(ex) gc_assert(ex)
  33 #else
  34 # define gc_dcheck(ex) ((void)0)
  35 #endif
  36
  37 /// Disable all assertions if NDEBUG
  38 #ifdef NDEBUG
  39 # define gc_assert(ex) ((void)0)
  40 # define gc_assert_verbose(ex, fmt, ...) ((void)0)
  41 #else
  42 # define gc_assert(ex)                                                 \
  43 do {                                                                   \
  44     if (!(ex)) gc_abort();                                             \
  45 } while (0)
  46 # define gc_assert_verbose(ex, fmt, ...)                               \
  47 do {                                                                   \
  48     if (!(ex)) {                                                       \
  49         fprintf(stderr, fmt, ## __VA_ARGS__);                          \
  50         gc_abort();                                                    \
  51     }                                                                  \
  52 } while (0)
  53 #endif
  54
  55 #define gc_abort()                                                     \
  56   lose("GC invariant lost, file \"%s\", line %d\n", __FILE__, __LINE__)
  57
  58 #define CEILING(x,y) (((x) + ((y) - 1)) & (~((y) - 1)))
  59
  60 static inline uword_t
  61 NWORDS(uword_t x, uword_t n_bits)
  62 {
  63     /* A good compiler should be able to constant-fold this whole thing,
  64        even with the conditional. */
  65     if(n_bits <= N_WORD_BITS) {
  66         uword_t elements_per_word = N_WORD_BITS/n_bits;
  67
  68         return CEILING(x, elements_per_word)/elements_per_word;
  69     }
  70     else {
  71         /* FIXME: should have some sort of assertion that N_WORD_BITS
  72            evenly divides n_bits */
  73         return x * (n_bits/N_WORD_BITS);
  74     }
  75 }
  76
  77 /* FIXME: Shouldn't this be defined in sbcl.h? */
  78
  79 #if defined(LISP_FEATURE_SPARC) || defined(LISP_FEATURE_ARM)
  80 #define FUN_RAW_ADDR_OFFSET 0
  81 #else
  82 #define FUN_RAW_ADDR_OFFSET (offsetof(struct simple_fun, code) - FUN_POINTER_LOWTAG)
  83 #endif
  84
  85 static inline unsigned short
  86 #ifdef LISP_FEATURE_64_BIT
  87 code_n_funs(struct code* code) { return ((code)->header >> 32) & 0x7FFF; }
  88 #define FIRST_SIMPLE_FUN_OFFSET(code) ((code)->header >> 48)
  89 #else
  90 code_n_funs(struct code* code) { return fixnum_value((code)->n_entries) & 0x3FFF; }
  91 #define FIRST_SIMPLE_FUN_OFFSET(code) ((code)->n_entries >> 16)
  92 #endif
  93
  94 // Iterate over the native pointers to each function in 'code_var'
  95 // offsets are stored as the number of bytes into the instructions
  96 // portion of the code object at which the simple-fun object resides.
  97 // We use bytes, not words, because that's what the COMPUTE-FUN vop expects.
  98 // But the offsets could be compressed further if we chose to use words,
  99 // which might allow storing them as (unsigned-byte 16),
 100 // as long as provision is made for ultra huge simple-funs. (~ .5MB)
 101 //
 102 // Note that the second assignment to _offset_ is OK: while it technically
 103 // oversteps the bounds of the indices of the fun offsets, it can not
 104 // run off the end of the code.
 105 #define for_each_simple_fun(index_var,fun_var,code_var,assertp,guts)        \
 106   { int _nfuns_ = code_n_funs(code_var);                                    \
 107     if (_nfuns_ > 0) {                                                      \
 108       char *_insts_ = (char*)(code_var) +                                   \
 109         (code_header_words((code_var)->header)<<WORD_SHIFT);                \
 110       int index_var = 0;                                                    \
 111       int _offset_ = FIRST_SIMPLE_FUN_OFFSET(code_var);                     \
 112       do {                                                                  \
 113        struct simple_fun* fun_var = (struct simple_fun*)(_insts_+_offset_); \
 114        if (assertp)                                                         \
 115          gc_assert(widetag_of(fun_var->header)==SIMPLE_FUN_HEADER_WIDETAG); \
 116        guts ;                                                               \
 117        _offset_ = ((unsigned int*)_insts_)[index_var];                      \
 118       } while (++index_var < _nfuns_);                                      \
 119   }}
 120
 121 #define SIMPLE_FUN_SCAV_START(fun_ptr) &fun_ptr->name
 122 #define SIMPLE_FUN_SCAV_NWORDS(fun_ptr) ((lispobj*)fun_ptr->code - &fun_ptr->name)
 123
 124 #define WEAK_POINTER_NWORDS \
 125         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
 126
 127 /* values for the *_alloc_* parameters, also see the commentary for
 128  * struct page in gencgc-internal.h.  FIXME: Perhaps these constants
 129  * should be there, or at least defined on gencgc only? */
 130 #define FREE_PAGE_FLAG 0
 131 #define BOXED_PAGE_FLAG 1
 132 #define UNBOXED_PAGE_FLAG 2
 133 #define OPEN_REGION_PAGE_FLAG 4
 134 #define CODE_PAGE_FLAG        (BOXED_PAGE_FLAG|UNBOXED_PAGE_FLAG)
 135
 136 #define ALLOC_BOXED 0
 137 #define ALLOC_UNBOXED 1
 138 #define ALLOC_QUICK 1
 139
 140 #ifdef LISP_FEATURE_GENCGC
 141 #include "gencgc-alloc-region.h"
 142 void *
 143 gc_alloc_with_region(sword_t nbytes,int page_type_flag, struct alloc_region *my_region,
 144                      int quick_p);
 145 static inline void *
 146 gc_general_alloc(sword_t nbytes, int page_type_flag, int quick_p)
 147 {
 148     struct alloc_region *my_region;
 149     if (UNBOXED_PAGE_FLAG == page_type_flag) {
 150         my_region = &unboxed_region;
 151     } else if (BOXED_PAGE_FLAG & page_type_flag) {
 152         my_region = &boxed_region;
 153     } else {
 154         lose("bad page type flag: %d", page_type_flag);
 155     }
 156     return gc_alloc_with_region(nbytes, page_type_flag, my_region, quick_p);
 157 }
 158 #else
 159 extern void *gc_general_alloc(word_t nbytes,int page_type_flag,int quick_p);
 160 #endif
 161
 162 #define CHECK_COPY_PRECONDITIONS(object, nwords) \
 163     gc_dcheck(is_lisp_pointer(object)); \
 164     gc_dcheck(from_space_p(object)); \
 165     gc_dcheck((nwords & 0x01) == 0)
 166
 167 #define CHECK_COPY_POSTCONDITIONS(copy, lowtag) \
 168     gc_dcheck(lowtag_of(copy) == lowtag); \
 169     gc_dcheck(!from_space_p(copy));
 170
 171 static inline lispobj
 172 gc_general_copy_object(lispobj object, long nwords, int page_type_flag)
 173 {
 174     lispobj *new;
 175
 176     CHECK_COPY_PRECONDITIONS(object, nwords);
 177
 178     /* Allocate space. */
 179     new = gc_general_alloc(nwords*N_WORD_BYTES, page_type_flag, ALLOC_QUICK);
 180
 181     /* Copy the object. */
 182     memcpy(new,native_pointer(object),nwords*N_WORD_BYTES);
 183
 184     return make_lispobj(new, lowtag_of(object));
 185 }
 186
 187 extern sword_t (*scavtab[256])(lispobj *where, lispobj object);
 188 extern lispobj (*transother[256])(lispobj object);
 189 extern sword_t (*sizetab[256])(lispobj *where);
 190
 191 extern struct weak_pointer *weak_pointers; /* in gc-common.c */
 192 extern struct hash_table *weak_hash_tables; /* in gc-common.c */
 193
 194 extern void scavenge(lispobj *start, sword_t n_words);
 195 extern void scavenge_interrupt_contexts(struct thread *thread);
 196 extern void scav_weak_hash_tables(void);
 197 extern void scan_weak_hash_tables(void);
 198 extern void scan_weak_pointers(void);
 199
 200 lispobj  copy_large_unboxed_object(lispobj object, sword_t nwords);
 201 lispobj  copy_unboxed_object(lispobj object, sword_t nwords);
 202 lispobj  copy_large_object(lispobj object, sword_t nwords);
 203 lispobj  copy_object(lispobj object, sword_t nwords);
 204 lispobj  copy_code_object(lispobj object, sword_t nwords);
 205 struct simple_fun *code_fun_addr(struct code*, int);
 206
 207 lispobj *search_read_only_space(void *pointer);
 208 lispobj *search_static_space(void *pointer);
 209 lispobj *search_immobile_space(void *pointer);
 210 lispobj *search_dynamic_space(void *pointer);
 211
 212 lispobj *gc_search_space3(void *pointer, lispobj *start, void *limit);
 213 static inline lispobj *gc_search_space(lispobj *start, void *pointer) {
 214     return gc_search_space3(pointer,
 215                             start,
 216                             (void*)(1+((lispobj)pointer | LOWTAG_MASK)));
 217 }
 218 struct vector *symbol_name(lispobj*);
 219
 220 static inline int instruction_ptr_p(void *pointer, lispobj *start_addr)
 221 {
 222     return widetag_of(*start_addr) == CODE_HEADER_WIDETAG &&
 223         pointer >= (void*)(start_addr + code_header_words(*start_addr));
 224 }
 225 extern int properly_tagged_descriptor_p(void *pointer, lispobj *start_addr);
 226
 227 extern void scavenge_control_stack(struct thread *th);
 228 extern void scrub_control_stack(void);
 229 extern void scrub_thread_control_stack(struct thread *);
 230
 231 #include "fixnump.h"
 232
 233 #ifdef LISP_FEATURE_GENCGC
 234 #include "gencgc-internal.h"
 235 #else
 236 #include "cheneygc-internal.h"
 237 #endif
 238
 239 #if N_WORD_BITS == 32
 240 # define SIMPLE_ARRAY_WORD_WIDETAG SIMPLE_ARRAY_UNSIGNED_BYTE_32_WIDETAG
 241 #elif N_WORD_BITS == 64
 242 # define SIMPLE_ARRAY_WORD_WIDETAG SIMPLE_ARRAY_UNSIGNED_BYTE_64_WIDETAG
 243 #endif
 244
 245 extern void
 246 instance_scan(void (*proc)(), lispobj *instance_ptr, sword_t n_words, lispobj bitmap);
 247
 248 #include "genesis/bignum.h"
 249 extern boolean positive_bignum_logbitp(int,struct bignum*);
 250
 251 // Generalization of instance_scan
 252 #define BIT_SCAN_INVERT 1
 253 #define BIT_SCAN_CLEAR  2
 254 typedef uword_t in_use_marker_t;
 255 extern void
 256 bitmap_scan(in_use_marker_t* bitmap, int n_bitmap_words, int flags,
 257             void (*proc)(void*, int, int), void* arg);
 258
 259 #ifdef LISP_FEATURE_IMMOBILE_SPACE
 260
 261 extern lispobj fdefn_raw_referent(struct fdefn *fdefn);
 262
 263 static inline boolean immobile_space_p(lispobj obj)
 264 {
 265   return IMMOBILE_SPACE_START <= obj && obj < IMMOBILE_SPACE_END;
 266 }
 267
 268 typedef int low_page_index_t;
 269 static inline low_page_index_t find_immobile_page_index(void *addr)
 270 {
 271   if (addr >= (void*)IMMOBILE_SPACE_START) {
 272       // Must use full register size here to avoid truncation of quotient
 273       // and bogus result!
 274       page_index_t index =
 275           ((pointer_sized_uint_t)addr -
 276            (pointer_sized_uint_t)IMMOBILE_SPACE_START) / IMMOBILE_CARD_BYTES;
 277       if (index < (int)(IMMOBILE_SPACE_SIZE/IMMOBILE_CARD_BYTES))
 278           return index;
 279   }
 280   return -1;
 281 }
 282 int immobile_obj_younger_p(lispobj,generation_index_t);
 283 void promote_immobile_obj(lispobj*,int);
 284
 285 // Maximum number of boxed words in a code component
 286 #define CODE_HEADER_COUNT_MASK 0xFFFFFF
 287
 288 #define IMMOBILE_OBJ_VISITED_FLAG    0x10
 289 #define IMMOBILE_OBJ_GENERATION_MASK 0x0f // mask off the VISITED flag
 290
 291 #define IMMOBILE_VARYOBJ_SUBSPACE_START (IMMOBILE_SPACE_START+IMMOBILE_FIXEDOBJ_SUBSPACE_SIZE)
 292
 293 // Note: this does not work on a SIMPLE-FUN
 294 // because a simple-fun header does not contain a generation.
 295 #define __immobile_obj_generation(x) (__immobile_obj_gen_bits(x) & IMMOBILE_OBJ_GENERATION_MASK)
 296
 297 static inline struct code *code_obj_from_simple_fun(struct simple_fun *fun)
 298 {
 299   // The upper 4 bytes of any function header will point to its layout,
 300   // so mask those bytes off.
 301   uword_t offset = (HeaderValue(fun->header) & CODE_HEADER_COUNT_MASK)
 302                    * N_WORD_BYTES;
 303   return (struct code *)((uword_t)fun - offset);
 304 }
 305
 306 #ifdef LISP_FEATURE_LITTLE_ENDIAN
 307 static inline int immobile_obj_gen_bits(lispobj* pointer) // native pointer
 308 {
 309   if (widetag_of(*pointer) == SIMPLE_FUN_HEADER_WIDETAG)
 310     pointer = (lispobj*)code_obj_from_simple_fun((struct simple_fun*)pointer);
 311   return ((generation_index_t*)pointer)[3];
 312 }
 313 // Faster way when we know that the object can't be a simple-fun,
 314 // such as when walking the immobile space.
 315 static inline int __immobile_obj_gen_bits(lispobj* pointer) // native pointer
 316 {
 317   return ((generation_index_t*)pointer)[3];
 318 }
 319 #else
 320 #error "Need to define immobile_obj_gen_bits() for big-endian"
 321 #endif /* little-endian */
 322
 323 static inline boolean immobile_filler_p(lispobj* obj) {
 324   return *(int*)obj == (2<<N_WIDETAG_BITS | CODE_HEADER_WIDETAG);
 325 }
 326
 327 #define set_instance_layout(instance_ptr,layout) \
 328   instance_ptr[0] = (layout << 32) | (instance_ptr[0] & 0xFFFFFFFF)
 329
 330 #endif /* immobile space */
 331
 332 #endif /* _GC_INTERNAL_H_ */