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 typedef std::multiset<free_heap_block*, block_size_compare> large_block_set;
  30
  31 struct free_list {
  32   std::vector<free_heap_block*> small_blocks[free_list_count];
  33   large_block_set large_blocks;
  34   cell free_block_count;
  35   cell free_space;
  36
  37   void clear_free_list();
  38   void initial_free_list(cell start, cell end, cell occupied);
  39   void add_to_free_list(free_heap_block* block);
  40   free_heap_block* find_free_block(cell size);
  41   free_heap_block* split_free_block(free_heap_block* block, cell size);
  42   bool can_allot_p(cell size);
  43   cell largest_free_block();
  44 };
  45
  46 struct allocator_room {
  47   cell size;
  48   cell occupied_space;
  49   cell total_free;
  50   cell contiguous_free;
  51   cell free_block_count;
  52 };
  53
  54 template <typename Block> struct free_list_allocator {
  55   cell size;
  56   cell start;
  57   cell end;
  58   free_list free_blocks;
  59   mark_bits state;
  60
  61   free_list_allocator(cell size, cell start);
  62   void initial_free_list(cell occupied);
  63   bool contains_p(Block* block);
  64   bool can_allot_p(cell size);
  65   Block* allot(cell size);
  66   void free(Block* block);
  67   cell occupied_space();
  68   cell free_space();
  69   cell largest_free_block();
  70   cell free_block_count();
  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   template <typename Iterator> void iterate(Iterator& iter);
  78   allocator_room as_allocator_room();
  79 };
  80
  81 template <typename Block>
  82 free_list_allocator<Block>::free_list_allocator(cell size, cell start)
  83     : size(size),
  84       start(start),
  85       end(start + size),
  86       state(mark_bits(size, start)) {
  87   initial_free_list(0);
  88 }
  89
  90 template <typename Block>
  91 void free_list_allocator<Block>::initial_free_list(cell occupied) {
  92   free_blocks.initial_free_list(start, end, occupied);
  93 }
  94
  95 template <typename Block>
  96 bool free_list_allocator<Block>::contains_p(Block* block) {
  97   return ((cell)block - start) < size;
  98 }
  99
 100 template <typename Block>
 101 bool free_list_allocator<Block>::can_allot_p(cell size) {
 102   return free_blocks.can_allot_p(size);
 103 }
 104
 105 template <typename Block> Block* free_list_allocator<Block>::allot(cell size) {
 106   size = align(size, data_alignment);
 107
 108   free_heap_block* block = free_blocks.find_free_block(size);
 109   if (block) {
 110     block = free_blocks.split_free_block(block, size);
 111     return (Block*)block;
 112   }
 113   return NULL;
 114 }
 115
 116 template <typename Block> void free_list_allocator<Block>::free(Block* block) {
 117   free_heap_block* free_block = (free_heap_block*)block;
 118   free_block->make_free(block->size());
 119   free_blocks.add_to_free_list(free_block);
 120 }
 121
 122 template <typename Block> cell free_list_allocator<Block>::free_space() {
 123   return free_blocks.free_space;
 124 }
 125
 126 template <typename Block> cell free_list_allocator<Block>::occupied_space() {
 127   return size - free_blocks.free_space;
 128 }
 129
 130 template <typename Block>
 131 cell free_list_allocator<Block>::largest_free_block() {
 132   return free_blocks.largest_free_block();
 133 }
 134
 135 template <typename Block> cell free_list_allocator<Block>::free_block_count() {
 136   return free_blocks.free_block_count;
 137 }
 138
 139 template <typename Block>
 140 template <typename Iterator>
 141 void free_list_allocator<Block>::sweep(Iterator& iter) {
 142   free_blocks.clear_free_list();
 143
 144   cell start = this->start;
 145   cell end = this->end;
 146
 147   while (start != end) {
 148     // find next unmarked block
 149     start = state.next_unmarked_block_after(start);
 150
 151     if (start != end) {
 152       // find size
 153       cell size = state.unmarked_block_size(start);
 154       FACTOR_ASSERT(size > 0);
 155
 156       free_heap_block* free_block = (free_heap_block*)start;
 157       free_block->make_free(size);
 158       free_blocks.add_to_free_list(free_block);
 159       iter((Block*)start, size);
 160
 161       start = start + size;
 162     }
 163   }
 164 }
 165
 166 template <typename Block> void free_list_allocator<Block>::sweep() {
 167   auto null_sweep = [](Block* free_block, cell size) { };
 168   sweep(null_sweep);
 169 }
 170
 171 // The forwarding map must be computed first by calling
 172 // state.compute_forwarding().
 173 template <typename Block>
 174 template <typename Iterator, typename Fixup>
 175 void free_list_allocator<Block>::compact(Iterator& iter, Fixup fixup,
 176                                          const Block** finger) {
 177   cell dest_addr = start;
 178   auto compact_block_func = [&](Block* block, cell size) {
 179     cell block_addr = (cell)block;
 180     if (!state.marked_p(block_addr))
 181       return;
 182     *finger = (Block*)(block_addr + size);
 183     memmove((Block*)dest_addr, block, size);
 184     iter(block, (Block*)dest_addr, size);
 185     dest_addr += size;
 186   };
 187   iterate(compact_block_func, fixup);
 188
 189   // Now update the free list; there will be a single free block at
 190   // the end
 191   free_blocks.initial_free_list(start, end, dest_addr - start);
 192 }
 193
 194 // During compaction we have to be careful and measure object sizes
 195 // differently
 196 template <typename Block>
 197 template <typename Iterator, typename Fixup>
 198 void free_list_allocator<Block>::iterate(Iterator& iter, Fixup fixup) {
 199   cell scan = this->start;
 200   while (scan != this->end) {
 201     Block* block = (Block*)scan;
 202     cell size = fixup.size(block);
 203     if (!block->free_p())
 204       iter(block, size);
 205     scan += size;
 206   }
 207 }
 208
 209 template <typename Block>
 210 allocator_room free_list_allocator<Block>::as_allocator_room() {
 211   allocator_room room;
 212   room.size = size;
 213   room.occupied_space = occupied_space();
 214   room.total_free = free_space();
 215   room.contiguous_free = largest_free_block();
 216   room.free_block_count = free_block_count();
 217   return room;
 218 }
 219
 220 }