vm/data_gc.h

   1 /* Set by the -S command line argument */
   2 bool secure_gc;
   3
   4 /* set up guard pages to check for under/overflow.
   5 size must be a multiple of the page size */
   6 F_SEGMENT *alloc_segment(CELL size);
   7 void dealloc_segment(F_SEGMENT *block);
   8
   9 CELL untagged_object_size(CELL pointer);
  10 CELL unaligned_object_size(CELL pointer);
  11 CELL object_size(CELL pointer);
  12 CELL binary_payload_start(CELL pointer);
  13 void begin_scan(void);
  14 CELL next_object(void);
  15
  16 void primitive_data_room(void);
  17 void primitive_size(void);
  18 void primitive_begin_scan(void);
  19 void primitive_next_object(void);
  20 void primitive_end_scan(void);
  21
  22 void gc(void);
  23 DLLEXPORT void minor_gc(void);
  24
  25 /* generational copying GC divides memory into zones */
  26 typedef struct {
  27         /* allocation pointer is 'here'; its offset is hardcoded in the
  28         compiler backends, see core/compiler/.../allot.factor */
  29         CELL start;
  30         CELL here;
  31         CELL size;
  32         CELL end;
  33 } F_ZONE;
  34
  35 typedef struct {
  36         F_SEGMENT *segment;
  37
  38         CELL young_size;
  39         CELL aging_size;
  40         CELL tenured_size;
  41
  42         CELL gen_count;
  43
  44         F_ZONE *generations;
  45         F_ZONE* semispaces;
  46
  47         CELL *allot_markers;
  48         CELL *allot_markers_end;
  49
  50         CELL *cards;
  51         CELL *cards_end;
  52
  53         CELL *decks;
  54         CELL *decks_end;
  55 } F_DATA_HEAP;
  56
  57 F_DATA_HEAP *data_heap;
  58
  59 /* card marking write barrier. a card is a byte storing a mark flag,
  60 and the offset (in cells) of the first object in the card.
  61
  62 the mark flag is set by the write barrier when an object in the
  63 card has a slot written to.
  64
  65 the offset of the first object is set by the allocator. */
  66
  67 /* if CARD_POINTS_TO_NURSERY is set, CARD_POINTS_TO_AGING must also be set. */
  68 #define CARD_POINTS_TO_NURSERY 0x80
  69 #define CARD_POINTS_TO_AGING 0x40
  70 #define CARD_MARK_MASK (CARD_POINTS_TO_NURSERY | CARD_POINTS_TO_AGING)
  71 typedef u8 F_CARD;
  72
  73 #define CARD_BITS 8
  74 #define CARD_SIZE (1<<CARD_BITS)
  75 #define ADDR_CARD_MASK (CARD_SIZE-1)
  76
  77 DLLEXPORT CELL cards_offset;
  78
  79 #define ADDR_TO_CARD(a) (F_CARD*)(((CELL)(a) >> CARD_BITS) + cards_offset)
  80 #define CARD_TO_ADDR(c) (CELL*)(((CELL)(c) - cards_offset)<<CARD_BITS)
  81
  82 typedef u8 F_DECK;
  83
  84 #define DECK_BITS (CARD_BITS + 10)
  85 #define DECK_SIZE (1<<DECK_BITS)
  86 #define ADDR_DECK_MASK (DECK_SIZE-1)
  87
  88 DLLEXPORT CELL decks_offset;
  89
  90 #define ADDR_TO_DECK(a) (F_DECK*)(((CELL)(a) >> DECK_BITS) + decks_offset)
  91 #define DECK_TO_ADDR(c) (CELL*)(((CELL)(c) - decks_offset) << DECK_BITS)
  92
  93 #define DECK_TO_CARD(d) (F_CARD*)((((CELL)(d) - decks_offset) << (DECK_BITS - CARD_BITS)) + cards_offset)
  94
  95 #define ADDR_TO_ALLOT_MARKER(a) (F_CARD*)(((CELL)(a) >> CARD_BITS) + allot_markers_offset)
  96 #define CARD_OFFSET(c) (*((c) - (CELL)data_heap->cards + (CELL)data_heap->allot_markers))
  97
  98 #define INVALID_ALLOT_MARKER 0xff
  99
 100 DLLEXPORT CELL allot_markers_offset;
 101
 102 void init_card_decks(void);
 103
 104 /* the write barrier must be called any time we are potentially storing a
 105 pointer from an older generation to a younger one */
 106 INLINE void write_barrier(CELL address)
 107 {
 108         *ADDR_TO_CARD(address) = CARD_MARK_MASK;
 109         *ADDR_TO_DECK(address) = CARD_MARK_MASK;
 110 }
 111
 112 #define SLOT(obj,slot) (UNTAG(obj) + (slot) * CELLS)
 113
 114 INLINE void set_slot(CELL obj, CELL slot, CELL value)
 115 {
 116         put(SLOT(obj,slot),value);
 117         write_barrier(obj);
 118 }
 119
 120 /* we need to remember the first object allocated in the card */
 121 INLINE void allot_barrier(CELL address)
 122 {
 123         F_CARD *ptr = ADDR_TO_ALLOT_MARKER(address);
 124         if(*ptr == INVALID_ALLOT_MARKER)
 125                 *ptr = (address & ADDR_CARD_MASK);
 126 }
 127
 128 void clear_cards(CELL from, CELL to);
 129 void collect_cards(void);
 130
 131 /* the 0th generation is where new objects are allocated. */
 132 #define NURSERY 0
 133 #define HAVE_NURSERY_P (data_heap->gen_count>1)
 134 /* where objects hang around */
 135 #define AGING (data_heap->gen_count-2)
 136 #define HAVE_AGING_P (data_heap->gen_count>2)
 137 /* the oldest generation */
 138 #define TENURED (data_heap->gen_count-1)
 139
 140 #define MIN_GEN_COUNT 1
 141 #define MAX_GEN_COUNT 3
 142
 143 /* used during garbage collection only */
 144 F_ZONE *newspace;
 145
 146 /* new objects are allocated here */
 147 DLLEXPORT F_ZONE nursery;
 148
 149 INLINE bool in_zone(F_ZONE *z, CELL pointer)
 150 {
 151         return pointer >= z->start && pointer < z->end;
 152 }
 153
 154 CELL init_zone(F_ZONE *z, CELL size, CELL base);
 155
 156 void init_data_heap(CELL gens,
 157         CELL young_size,
 158         CELL aging_size,
 159         CELL tenured_size,
 160         bool secure_gc_);
 161
 162 /* statistics */
 163 typedef struct {
 164         CELL collections;
 165         u64 gc_time;
 166         u64 max_gc_time;
 167         CELL object_count;
 168         u64 bytes_copied;
 169 } F_GC_STATS;
 170
 171 F_GC_STATS gc_stats[MAX_GEN_COUNT];
 172 u64 cards_scanned;
 173 u64 decks_scanned;
 174 CELL code_heap_scans;
 175
 176 /* only meaningful during a GC */
 177 bool performing_gc;
 178 CELL collecting_gen;
 179
 180 /* if true, we collecting AGING space for the second time, so if it is still
 181 full, we go on to collect TENURED */
 182 bool collecting_aging_again;
 183
 184 INLINE bool collecting_accumulation_gen_p(void)
 185 {
 186         return ((HAVE_AGING_P
 187                 && collecting_gen == AGING
 188                 && !collecting_aging_again)
 189                 || collecting_gen == TENURED);
 190 }
 191
 192 /* What generation was being collected when collect_literals() was last
 193 called? Until the next call to primitive_add_compiled_block(), future
 194 collections of younger generations don't have to touch the code
 195 heap. */
 196 CELL last_code_heap_scan;
 197
 198 /* sometimes we grow the heap */
 199 bool growing_data_heap;
 200 F_DATA_HEAP *old_data_heap;
 201
 202 /* Every object has a regular representation in the runtime, which makes GC
 203 much simpler. Every slot of the object until binary_payload_start is a pointer
 204 to some other object. */
 205 INLINE void do_slots(CELL obj, void (* iter)(CELL *))
 206 {
 207         CELL scan = obj;
 208         CELL payload_start = binary_payload_start(obj);
 209         CELL end = obj + payload_start;
 210
 211         scan += CELLS;
 212
 213         while(scan < end)
 214         {
 215                 iter((CELL *)scan);
 216                 scan += CELLS;
 217         }
 218 }
 219
 220 /* test if the pointer is in generation being collected, or a younger one. */
 221 INLINE bool should_copy(CELL untagged)
 222 {
 223         if(in_zone(newspace,untagged))
 224                 return false;
 225         if(collecting_gen == TENURED)
 226                 return true;
 227         else if(HAVE_AGING_P && collecting_gen == AGING)
 228                 return !in_zone(&data_heap->generations[TENURED],untagged);
 229         else if(HAVE_NURSERY_P && collecting_gen == NURSERY)
 230                 return in_zone(&nursery,untagged);
 231         else
 232         {
 233                 critical_error("Bug in should_copy",untagged);
 234                 return false;
 235         }
 236 }
 237
 238 void copy_handle(CELL *handle);
 239
 240 /* in case a generation fills up in the middle of a gc, we jump back
 241 up to try collecting the next generation. */
 242 jmp_buf gc_jmp;
 243
 244 /* A heap walk allows useful things to be done, like finding all
 245 references to an object for debugging purposes. */
 246 CELL heap_scan_ptr;
 247
 248 /* GC is off during heap walking */
 249 bool gc_off;
 250
 251 void garbage_collection(volatile CELL gen,
 252         bool growing_data_heap_,
 253         CELL requested_bytes);
 254
 255 /* If a runtime function needs to call another function which potentially
 256 allocates memory, it must store any local variable references to Factor
 257 objects on the root stack */
 258
 259 /* GC locals: stores addresses of pointers to objects. The GC updates these
 260 pointers, so you can do
 261
 262 REGISTER_ROOT(some_local);
 263
 264 ... allocate memory ...
 265
 266 foo(some_local);
 267
 268 ...
 269
 270 UNREGISTER_ROOT(some_local); */
 271 F_SEGMENT *gc_locals_region;
 272 CELL gc_locals;
 273
 274 DEFPUSHPOP(gc_local_,gc_locals)
 275
 276 #define REGISTER_ROOT(obj) gc_local_push((CELL)&obj)
 277 #define UNREGISTER_ROOT(obj) \
 278         { \
 279                 if(gc_local_pop() != (CELL)&obj) \
 280                         critical_error("Mismatched REGISTER_ROOT/UNREGISTER_ROOT",0); \
 281         }
 282
 283 /* Extra roots: stores pointers to objects in the heap. Requires extra work
 284 (you have to unregister before accessing the object) but more flexible. */
 285 F_SEGMENT *extra_roots_region;
 286 CELL extra_roots;
 287
 288 DEFPUSHPOP(root_,extra_roots)
 289
 290 #define REGISTER_UNTAGGED(obj) root_push(obj ? tag_object(obj) : 0)
 291 #define UNREGISTER_UNTAGGED(obj) obj = untag_object(root_pop())
 292
 293 INLINE bool in_data_heap_p(CELL ptr)
 294 {
 295         return (ptr >= data_heap->segment->start
 296                 && ptr <= data_heap->segment->end);
 297 }
 298
 299 /* We ignore strings which point outside the data heap, but we might be given
 300 a char* which points inside the data heap, in which case it is a root, for
 301 example if we call unbox_char_string() the result is placed in a byte array */
 302 INLINE bool root_push_alien(const void *ptr)
 303 {
 304         if(in_data_heap_p((CELL)ptr))
 305         {
 306                 F_BYTE_ARRAY *objptr = ((F_BYTE_ARRAY *)ptr) - 1;
 307                 if(objptr->header == tag_header(BYTE_ARRAY_TYPE))
 308                 {
 309                         root_push(tag_object(objptr));
 310                         return true;
 311                 }
 312         }
 313
 314         return false;
 315 }
 316
 317 #define REGISTER_C_STRING(obj) \
 318         bool obj##_root = root_push_alien(obj)
 319 #define UNREGISTER_C_STRING(obj) \
 320         if(obj##_root) obj = alien_offset(root_pop())
 321
 322 #define REGISTER_BIGNUM(obj) if(obj) root_push(tag_bignum(obj))
 323 #define UNREGISTER_BIGNUM(obj) if(obj) obj = (untag_object(root_pop()))
 324
 325 INLINE void *allot_zone(F_ZONE *z, CELL a)
 326 {
 327         CELL h = z->here;
 328         z->here = h + align8(a);
 329         return (void*)h;
 330 }
 331
 332 /* We leave this many bytes free at the top of the nursery so that inline
 333 allocation (which does not call GC because of possible roots in volatile
 334 registers) does not run out of memory */
 335 #define ALLOT_BUFFER_ZONE 1024
 336
 337 /*
 338  * It is up to the caller to fill in the object's fields in a meaningful
 339  * fashion!
 340  */
 341 INLINE void* allot_object(CELL type, CELL a)
 342 {
 343         CELL *object;
 344
 345         if(HAVE_NURSERY_P && nursery.size - ALLOT_BUFFER_ZONE > a)
 346         {
 347                 /* If there is insufficient room, collect the nursery */
 348                 if(nursery.here + ALLOT_BUFFER_ZONE + a > nursery.end)
 349                         garbage_collection(NURSERY,false,0);
 350
 351                 CELL h = nursery.here;
 352                 nursery.here = h + align8(a);
 353                 object = (void*)h;
 354         }
 355         /* If the object is bigger than the nursery, allocate it in
 356         tenured space */
 357         else
 358         {
 359                 F_ZONE *tenured = &data_heap->generations[TENURED];
 360
 361                 /* If tenured space does not have enough room, collect */
 362                 if(tenured->here + a > tenured->end)
 363                 {
 364                         gc();
 365                         tenured = &data_heap->generations[TENURED];
 366                 }
 367
 368                 /* If it still won't fit, grow the heap */
 369                 if(tenured->here + a > tenured->end)
 370                 {
 371                         garbage_collection(TENURED,true,a);
 372                         tenured = &data_heap->generations[TENURED];
 373                 }
 374
 375                 object = allot_zone(tenured,a);
 376
 377                 /* We have to do this */
 378                 allot_barrier((CELL)object);
 379
 380                 /* Allows initialization code to store old->new pointers
 381                 without hitting the write barrier in the common case of
 382                 a nursery allocation */
 383                 write_barrier((CELL)object);
 384         }
 385
 386         *object = tag_header(type);
 387         return object;
 388 }
 389
 390 void collect_next_loop(CELL scan, CELL *end);
 391
 392 void primitive_gc(void);
 393 void primitive_gc_stats(void);
 394 void primitive_gc_reset(void);
 395 void primitive_become(void);
 396
 397 CELL find_all_words(void);