vm/data_heap.cpp

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