vm/free_list.hpp

   1 namespace factor {
   2
   3 static const cell free_list_count = 32;
   4 static const cell allocation_page_size = 1024;
   5
   6 struct free_heap_block {
   7   cell header;
   8
   9   bool free_p() const { return (header & 1) == 1; }
  10
  11   cell size() const {
  12     cell size = header & ~7;
  13     FACTOR_ASSERT(size > 0);
  14     return size;
  15   }
  16
  17   void make_free(cell size) {
  18     FACTOR_ASSERT(size > 0);
  19     header = size | 1;
  20   }
  21 };
  22
  23 struct block_size_compare {
  24   bool operator()(free_heap_block* a, free_heap_block* b) const {
  25     return a->size() < b->size();
  26   }
  27 };
  28
  29 struct allocator_room {
  30   cell size;
  31   cell occupied_space;
  32   cell total_free;
  33   cell contiguous_free;
  34   cell free_block_count;
  35 };
  36
  37 template <typename Block> struct free_list_allocator {
  38   // Region of memory managed by this free list allocator.
  39   cell start;
  40   cell end;
  41   cell size;
  42
  43   // Stores the free blocks
  44   std::vector<free_heap_block*> small_blocks[free_list_count];
  45   std::multiset<free_heap_block*, block_size_compare> large_blocks;
  46   cell free_block_count;
  47   cell free_space;
  48
  49   mark_bits state;
  50
  51   // Initializing & freeing
  52   free_list_allocator(cell size, cell start);
  53   void initial_free_list(cell occupied);
  54   void clear_free_list();
  55   void add_to_free_list(free_heap_block* block);
  56   void free(Block* block);
  57
  58   // Allocating
  59   free_heap_block* find_free_block(cell size);
  60   free_heap_block* split_free_block(free_heap_block* block, cell size);
  61   Block* allot(cell size);
  62
  63   // Data
  64   bool contains_p(Block* block);
  65   bool can_allot_p(cell size);
  66   cell occupied_space();
  67   cell largest_free_block();
  68   allocator_room as_allocator_room();
  69
  70   // Iteration
  71   void sweep();
  72   template <typename Iterator> void sweep(Iterator& iter);
  73   template <typename Iterator, typename Fixup>
  74   void compact(Iterator& iter, Fixup fixup, const Block** finger);
  75   template <typename Iterator, typename Fixup>
  76   void iterate(Iterator& iter, Fixup fixup);
  77 };
  78
  79 template <typename Block>
  80 void free_list_allocator<Block>::clear_free_list() {
  81   for (cell i = 0; i < free_list_count; i++)
  82     small_blocks[i].clear();
  83   large_blocks.clear();
  84   free_block_count = 0;
  85   free_space = 0;
  86 }
  87
  88 template <typename Block>
  89 void free_list_allocator<Block>::add_to_free_list(free_heap_block* block) {
  90   cell size = block->size();
  91
  92   free_block_count++;
  93   free_space += size;
  94
  95   if (size < free_list_count * data_alignment)
  96     small_blocks[size / data_alignment].push_back(block);
  97   else
  98     large_blocks.insert(block);
  99 }
 100
 101 template <typename Block>
 102 void free_list_allocator<Block>::initial_free_list(cell occupied) {
 103   clear_free_list();
 104   if (occupied != end - start) {
 105     free_heap_block* last_block = (free_heap_block*)(start + occupied);
 106     last_block->make_free(end - (cell)last_block);
 107     add_to_free_list(last_block);
 108   }
 109 }
 110
 111 template <typename Block>
 112 free_list_allocator<Block>::free_list_allocator(cell size, cell start)
 113     : start(start),
 114       end(start + size),
 115       size(size),
 116       state(mark_bits(size, start)) {
 117   initial_free_list(0);
 118 }
 119
 120 template <typename Block>
 121 bool free_list_allocator<Block>::contains_p(Block* block) {
 122   return ((cell)block - start) < size;
 123 }
 124
 125 template <typename Block>
 126 bool free_list_allocator<Block>::can_allot_p(cell size) {
 127   return largest_free_block() >= std::max(size, allocation_page_size);
 128 }
 129
 130 template <typename Block>
 131 free_heap_block* free_list_allocator<Block>::split_free_block(
 132     free_heap_block* block,
 133     cell size) {
 134   if (block->size() != size) {
 135     // split the block in two
 136     free_heap_block* split = (free_heap_block*)((cell)block + size);
 137     split->make_free(block->size() - size);
 138     block->make_free(size);
 139     add_to_free_list(split);
 140   }
 141
 142   return block;
 143 }
 144
 145 template <typename Block>
 146 free_heap_block* free_list_allocator<Block>::find_free_block(cell size) {
 147   // Check small free lists
 148   cell bucket = size / data_alignment;
 149   if (bucket < free_list_count) {
 150     std::vector<free_heap_block*>& blocks = small_blocks[bucket];
 151     if (blocks.size() == 0) {
 152       // Round up to a multiple of 'size'
 153       cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
 154
 155       // Allocate a block this big
 156       free_heap_block* large_block = find_free_block(large_block_size);
 157       if (!large_block)
 158         return NULL;
 159
 160       large_block = split_free_block(large_block, large_block_size);
 161
 162       // Split it up into pieces and add each piece back to the free list
 163       for (cell offset = 0; offset < large_block_size; offset += size) {
 164         free_heap_block* small_block = large_block;
 165         large_block = (free_heap_block*)((cell)large_block + size);
 166         small_block->make_free(size);
 167         add_to_free_list(small_block);
 168       }
 169     }
 170
 171     free_heap_block* block = blocks.back();
 172     blocks.pop_back();
 173
 174     free_block_count--;
 175     free_space -= block->size();
 176
 177     return block;
 178   } else {
 179     // Check large free list
 180     free_heap_block key;
 181     key.make_free(size);
 182     auto iter = large_blocks.lower_bound(&key);
 183     auto end = large_blocks.end();
 184
 185     if (iter != end) {
 186       free_heap_block* block = *iter;
 187       large_blocks.erase(iter);
 188
 189       free_block_count--;
 190       free_space -= block->size();
 191
 192       return block;
 193     }
 194
 195     return NULL;
 196   }
 197 }
 198
 199
 200 template <typename Block>
 201 Block* free_list_allocator<Block>::allot(cell size) {
 202   size = align(size, data_alignment);
 203
 204   free_heap_block* block = find_free_block(size);
 205   if (block) {
 206     block = split_free_block(block, size);
 207     return (Block*)block;
 208   }
 209   return NULL;
 210 }
 211
 212 template <typename Block>
 213 void free_list_allocator<Block>::free(Block* block) {
 214   free_heap_block* free_block = (free_heap_block*)block;
 215   free_block->make_free(block->size());
 216   add_to_free_list(free_block);
 217 }
 218
 219 template <typename Block>
 220 cell free_list_allocator<Block>::occupied_space() {
 221   return size - free_space;
 222 }
 223
 224 template <typename Block>
 225 cell free_list_allocator<Block>::largest_free_block() {
 226   if (large_blocks.size()) {
 227     auto last = large_blocks.rbegin();
 228     return (*last)->size();
 229   } else {
 230     for (int i = free_list_count - 1; i >= 0; i--) {
 231       if (small_blocks[i].size())
 232         return small_blocks[i].back()->size();
 233     }
 234     return 0;
 235   }
 236 }
 237
 238 template <typename Block>
 239 template <typename Iterator>
 240 void free_list_allocator<Block>::sweep(Iterator& iter) {
 241   clear_free_list();
 242
 243   cell start = this->start;
 244   cell end = this->end;
 245
 246   while (start != end) {
 247     // find next unmarked block
 248     start = state.next_unmarked_block_after(start);
 249
 250     if (start != end) {
 251       // find size
 252       cell size = state.unmarked_block_size(start);
 253       FACTOR_ASSERT(size > 0);
 254
 255       free_heap_block* free_block = (free_heap_block*)start;
 256       free_block->make_free(size);
 257       add_to_free_list(free_block);
 258       iter((Block*)start, size);
 259
 260       start = start + size;
 261     }
 262   }
 263 }
 264
 265 template <typename Block> void free_list_allocator<Block>::sweep() {
 266   auto null_sweep = [](Block* free_block, cell size) { (void)free_block; (void)size; };
 267   sweep(null_sweep);
 268 }
 269
 270 // The forwarding map must be computed first by calling
 271 // state.compute_forwarding().
 272 template <typename Block>
 273 template <typename Iterator, typename Fixup>
 274 void free_list_allocator<Block>::compact(Iterator& iter, Fixup fixup,
 275                                          const Block** finger) {
 276   cell dest_addr = start;
 277   auto compact_block_func = [&](Block* block, cell size) {
 278     cell block_addr = (cell)block;
 279     if (!state.marked_p(block_addr))
 280       return;
 281     *finger = (Block*)(block_addr + size);
 282     if (dest_addr != (cell)block) {
 283       memmove((Block*)dest_addr, block, size);
 284     }
 285     iter(block, (Block*)dest_addr, size);
 286     dest_addr += size;
 287   };
 288   iterate(compact_block_func, fixup);
 289
 290   // Now update the free list; there will be a single free block at
 291   // the end
 292   initial_free_list(dest_addr - start);
 293 }
 294
 295 // During compaction we have to be careful and measure object sizes
 296 // differently
 297 template <typename Block>
 298 template <typename Iterator, typename Fixup>
 299 void free_list_allocator<Block>::iterate(Iterator& iter, Fixup fixup) {
 300   cell scan = this->start;
 301   while (scan != this->end) {
 302     Block* block = (Block*)scan;
 303     cell size = fixup.size(block);
 304     if (!block->free_p())
 305       iter(block, size);
 306     scan += size;
 307   }
 308 }
 309
 310 template <typename Block>
 311 allocator_room free_list_allocator<Block>::as_allocator_room() {
 312   allocator_room room;
 313   room.size = size;
 314   room.occupied_space = occupied_space();
 315   room.total_free = free_space;
 316   room.contiguous_free = largest_free_block();
 317   room.free_block_count = free_block_count;
 318   return room;
 319 }
 320
 321 }