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