vm/data_heap.cpp

   1 #include "master.hpp"
   2
   3 factor::zone nursery;
   4
   5 namespace factor
   6 {
   7
   8 /* Set by the -securegc command line argument */
   9 bool secure_gc;
  10
  11 /* new objects are allocated here */
  12 VM_C_API zone nursery;
  13
  14 /* GC is off during heap walking */
  15 bool gc_off;
  16
  17 data_heap *data;
  18
  19 cell init_zone(zone *z, cell size, cell start)
  20 {
  21         z->size = size;
  22         z->start = z->here = start;
  23         z->end = start + size;
  24         return z->end;
  25 }
  26
  27 void init_card_decks()
  28 {
  29         cell start = align(data->seg->start,deck_size);
  30         allot_markers_offset = (cell)data->allot_markers - (start >> card_bits);
  31         cards_offset = (cell)data->cards - (start >> card_bits);
  32         decks_offset = (cell)data->decks - (start >> deck_bits);
  33 }
  34
  35 data_heap *alloc_data_heap(cell gens,
  36         cell young_size,
  37         cell aging_size,
  38         cell tenured_size)
  39 {
  40         young_size = align(young_size,deck_size);
  41         aging_size = align(aging_size,deck_size);
  42         tenured_size = align(tenured_size,deck_size);
  43
  44         data_heap *data = (data_heap *)safe_malloc(sizeof(data_heap));
  45         data->young_size = young_size;
  46         data->aging_size = aging_size;
  47         data->tenured_size = tenured_size;
  48         data->gen_count = gens;
  49
  50         cell total_size;
  51         if(data->gen_count == 2)
  52                 total_size = young_size + 2 * tenured_size;
  53         else if(data->gen_count == 3)
  54                 total_size = young_size + 2 * aging_size + 2 * tenured_size;
  55         else
  56         {
  57                 fatal_error("Invalid number of generations",data->gen_count);
  58                 return NULL; /* can't happen */
  59         }
  60
  61         total_size += deck_size;
  62
  63         data->seg = alloc_segment(total_size);
  64
  65         data->generations = (zone *)safe_malloc(sizeof(zone) * data->gen_count);
  66         data->semispaces = (zone *)safe_malloc(sizeof(zone) * data->gen_count);
  67
  68         cell cards_size = total_size >> card_bits;
  69         data->allot_markers = (cell *)safe_malloc(cards_size);
  70         data->allot_markers_end = data->allot_markers + cards_size;
  71
  72         data->cards = (cell *)safe_malloc(cards_size);
  73         data->cards_end = data->cards + cards_size;
  74
  75         cell decks_size = total_size >> deck_bits;
  76         data->decks = (cell *)safe_malloc(decks_size);
  77         data->decks_end = data->decks + decks_size;
  78
  79         cell alloter = align(data->seg->start,deck_size);
  80
  81         alloter = init_zone(&data->generations[data->tenured()],tenured_size,alloter);
  82         alloter = init_zone(&data->semispaces[data->tenured()],tenured_size,alloter);
  83
  84         if(data->gen_count == 3)
  85         {
  86                 alloter = init_zone(&data->generations[data->aging()],aging_size,alloter);
  87                 alloter = init_zone(&data->semispaces[data->aging()],aging_size,alloter);
  88         }
  89
  90         if(data->gen_count >= 2)
  91         {
  92                 alloter = init_zone(&data->generations[data->nursery()],young_size,alloter);
  93                 alloter = init_zone(&data->semispaces[data->nursery()],0,alloter);
  94         }
  95
  96         if(data->seg->end - alloter > deck_size)
  97                 critical_error("Bug in alloc_data_heap",alloter);
  98
  99         return data;
 100 }
 101
 102 data_heap *grow_data_heap(data_heap *data, cell requested_bytes)
 103 {
 104         cell new_tenured_size = (data->tenured_size * 2) + requested_bytes;
 105
 106         return alloc_data_heap(data->gen_count,
 107                 data->young_size,
 108                 data->aging_size,
 109                 new_tenured_size);
 110 }
 111
 112 void dealloc_data_heap(data_heap *data)
 113 {
 114         dealloc_segment(data->seg);
 115         free(data->generations);
 116         free(data->semispaces);
 117         free(data->allot_markers);
 118         free(data->cards);
 119         free(data->decks);
 120         free(data);
 121 }
 122
 123 void clear_cards(cell from, cell to)
 124 {
 125         /* NOTE: reverse order due to heap layout. */
 126         card *first_card = addr_to_card(data->generations[to].start);
 127         card *last_card = addr_to_card(data->generations[from].end);
 128         memset(first_card,0,last_card - first_card);
 129 }
 130
 131 void clear_decks(cell from, cell to)
 132 {
 133         /* NOTE: reverse order due to heap layout. */
 134         card_deck *first_deck = addr_to_deck(data->generations[to].start);
 135         card_deck *last_deck = addr_to_deck(data->generations[from].end);
 136         memset(first_deck,0,last_deck - first_deck);
 137 }
 138
 139 void clear_allot_markers(cell from, cell to)
 140 {
 141         /* NOTE: reverse order due to heap layout. */
 142         card *first_card = addr_to_allot_marker((object *)data->generations[to].start);
 143         card *last_card = addr_to_allot_marker((object *)data->generations[from].end);
 144         memset(first_card,invalid_allot_marker,last_card - first_card);
 145 }
 146
 147 void reset_generation(cell i)
 148 {
 149         zone *z = (i == data->nursery() ? &nursery : &data->generations[i]);
 150
 151         z->here = z->start;
 152         if(secure_gc)
 153                 memset((void*)z->start,69,z->size);
 154 }
 155
 156 /* After garbage collection, any generations which are now empty need to have
 157 their allocation pointers and cards reset. */
 158 void reset_generations(cell from, cell to)
 159 {
 160         cell i;
 161         for(i = from; i <= to; i++)
 162                 reset_generation(i);
 163
 164         clear_cards(from,to);
 165         clear_decks(from,to);
 166         clear_allot_markers(from,to);
 167 }
 168
 169 void set_data_heap(data_heap *data_)
 170 {
 171         data = data_;
 172         nursery = data->generations[data->nursery()];
 173         init_card_decks();
 174         clear_cards(data->nursery(),data->tenured());
 175         clear_decks(data->nursery(),data->tenured());
 176         clear_allot_markers(data->nursery(),data->tenured());
 177 }
 178
 179 void init_data_heap(cell gens,
 180         cell young_size,
 181         cell aging_size,
 182         cell tenured_size,
 183         bool secure_gc_)
 184 {
 185         set_data_heap(alloc_data_heap(gens,young_size,aging_size,tenured_size));
 186
 187         gc_locals_region = alloc_segment(getpagesize());
 188         gc_locals = gc_locals_region->start - sizeof(cell);
 189
 190         gc_bignums_region = alloc_segment(getpagesize());
 191         gc_bignums = gc_bignums_region->start - sizeof(cell);
 192
 193         secure_gc = secure_gc_;
 194
 195         init_data_gc();
 196 }
 197
 198 /* Size of the object pointed to by a tagged pointer */
 199 cell object_size(cell tagged)
 200 {
 201         if(immediate_p(tagged))
 202                 return 0;
 203         else
 204                 return untagged_object_size(untag<object>(tagged));
 205 }
 206
 207 /* Size of the object pointed to by an untagged pointer */
 208 cell untagged_object_size(object *pointer)
 209 {
 210         return align8(unaligned_object_size(pointer));
 211 }
 212
 213 /* Size of the data area of an object pointed to by an untagged pointer */
 214 cell unaligned_object_size(object *pointer)
 215 {
 216         switch(pointer->h.hi_tag())
 217         {
 218         case ARRAY_TYPE:
 219                 return array_size((array*)pointer);
 220         case BIGNUM_TYPE:
 221                 return array_size((bignum*)pointer);
 222         case BYTE_ARRAY_TYPE:
 223                 return array_size((byte_array*)pointer);
 224         case STRING_TYPE:
 225                 return string_size(string_capacity((string*)pointer));
 226         case TUPLE_TYPE:
 227                 return tuple_size(untag<tuple_layout>(((tuple *)pointer)->layout));
 228         case QUOTATION_TYPE:
 229                 return sizeof(quotation);
 230         case WORD_TYPE:
 231                 return sizeof(word);
 232         case FLOAT_TYPE:
 233                 return sizeof(boxed_float);
 234         case DLL_TYPE:
 235                 return sizeof(dll);
 236         case ALIEN_TYPE:
 237                 return sizeof(alien);
 238         case WRAPPER_TYPE:
 239                 return sizeof(wrapper);
 240         case CALLSTACK_TYPE:
 241                 return callstack_size(untag_fixnum(((callstack *)pointer)->length));
 242         default:
 243                 critical_error("Invalid header",(cell)pointer);
 244                 return 0; /* can't happen */
 245         }
 246 }
 247
 248 PRIMITIVE(size)
 249 {
 250         box_unsigned_cell(object_size(dpop()));
 251 }
 252
 253 /* The number of cells from the start of the object which should be scanned by
 254 the GC. Some types have a binary payload at the end (string, word, DLL) which
 255 we ignore. */
 256 cell binary_payload_start(object *pointer)
 257 {
 258         switch(pointer->h.hi_tag())
 259         {
 260         /* these objects do not refer to other objects at all */
 261         case FLOAT_TYPE:
 262         case BYTE_ARRAY_TYPE:
 263         case BIGNUM_TYPE:
 264         case CALLSTACK_TYPE:
 265                 return 0;
 266         /* these objects have some binary data at the end */
 267         case WORD_TYPE:
 268                 return sizeof(word) - sizeof(cell) * 3;
 269         case ALIEN_TYPE:
 270                 return sizeof(cell) * 3;
 271         case DLL_TYPE:
 272                 return sizeof(cell) * 2;
 273         case QUOTATION_TYPE:
 274                 return sizeof(quotation) - sizeof(cell) * 2;
 275         case STRING_TYPE:
 276                 return sizeof(string);
 277         /* everything else consists entirely of pointers */
 278         case ARRAY_TYPE:
 279                 return array_size<array>(array_capacity((array*)pointer));
 280         case TUPLE_TYPE:
 281                 return tuple_size(untag<tuple_layout>(((tuple *)pointer)->layout));
 282         case WRAPPER_TYPE:
 283                 return sizeof(wrapper);
 284         default:
 285                 critical_error("Invalid header",(cell)pointer);
 286                 return 0; /* can't happen */
 287         }
 288 }
 289
 290 /* Push memory usage statistics in data heap */
 291 PRIMITIVE(data_room)
 292 {
 293         dpush(tag_fixnum((data->cards_end - data->cards) >> 10));
 294         dpush(tag_fixnum((data->decks_end - data->decks) >> 10));
 295
 296         growable_array a;
 297
 298         cell gen;
 299         for(gen = 0; gen < data->gen_count; gen++)
 300         {
 301                 zone *z = (gen == data->nursery() ? &nursery : &data->generations[gen]);
 302                 a.add(tag_fixnum((z->end - z->here) >> 10));
 303                 a.add(tag_fixnum((z->size) >> 10));
 304         }
 305
 306         a.trim();
 307         dpush(a.elements.value());
 308 }
 309
 310 /* A heap walk allows useful things to be done, like finding all
 311 references to an object for debugging purposes. */
 312 cell heap_scan_ptr;
 313
 314 /* Disables GC and activates next-object ( -- obj ) primitive */
 315 void begin_scan()
 316 {
 317         heap_scan_ptr = data->generations[data->tenured()].start;
 318         gc_off = true;
 319 }
 320
 321 void end_scan()
 322 {
 323         gc_off = false;
 324 }
 325
 326 PRIMITIVE(begin_scan)
 327 {
 328         begin_scan();
 329 }
 330
 331 cell next_object()
 332 {
 333         if(!gc_off)
 334                 general_error(ERROR_HEAP_SCAN,F,F,NULL);
 335
 336         if(heap_scan_ptr >= data->generations[data->tenured()].here)
 337                 return F;
 338
 339         object *obj = (object *)heap_scan_ptr;
 340         heap_scan_ptr += untagged_object_size(obj);
 341         return tag_dynamic(obj);
 342 }
 343
 344 /* Push object at heap scan cursor and advance; pushes f when done */
 345 PRIMITIVE(next_object)
 346 {
 347         dpush(next_object());
 348 }
 349
 350 /* Re-enables GC */
 351 PRIMITIVE(end_scan)
 352 {
 353         gc_off = false;
 354 }
 355
 356 template<typename T> void each_object(T &functor)
 357 {
 358         begin_scan();
 359         cell obj;
 360         while((obj = next_object()) != F)
 361                 functor(tagged<object>(obj));
 362         end_scan();
 363 }
 364
 365 namespace
 366 {
 367
 368 struct word_counter {
 369         cell count;
 370         word_counter() : count(0) {}
 371         void operator()(tagged<object> obj) { if(obj.type_p(WORD_TYPE)) count++; }
 372 };
 373
 374 struct word_accumulator {
 375         growable_array words;
 376         word_accumulator(int count) : words(count) {}
 377         void operator()(tagged<object> obj) { if(obj.type_p(WORD_TYPE)) words.add(obj.value()); }
 378 };
 379
 380 }
 381
 382 cell find_all_words()
 383 {
 384         word_counter counter;
 385         each_object(counter);
 386         word_accumulator accum(counter.count);
 387         each_object(accum);
 388         accum.words.trim();
 389         return accum.words.elements.value();
 390 }
 391
 392 }