vm/free_list_allocator.hpp

   1 namespace factor
   2 {
   3
   4 template<typename Block> struct free_list_allocator {
   5         cell size;
   6         cell start;
   7         cell end;
   8         free_list free_blocks;
   9         mark_bits<Block> state;
  10
  11         explicit free_list_allocator(cell size, cell start);
  12         void initial_free_list(cell occupied);
  13         bool contains_p(Block *block);
  14         Block *first_block();
  15         Block *last_block();
  16         Block *next_block_after(Block *block);
  17         Block *next_allocated_block_after(Block *block);
  18         bool can_allot_p(cell size);
  19         Block *allot(cell size);
  20         void free(Block *block);
  21         cell occupied_space();
  22         cell free_space();
  23         cell largest_free_block();
  24         cell free_block_count();
  25         void sweep();
  26         template<typename Iterator> void sweep(Iterator &iter);
  27         template<typename Iterator, typename Fixup> void compact(Iterator &iter, Fixup fixup, const Block **finger);
  28         template<typename Iterator, typename Fixup> void iterate(Iterator &iter, Fixup fixup);
  29         template<typename Iterator> void iterate(Iterator &iter);
  30 };
  31
  32 template<typename Block>
  33 free_list_allocator<Block>::free_list_allocator(cell size_, cell start_) :
  34         size(size_),
  35         start(start_),
  36         end(start_ + size_),
  37         state(mark_bits<Block>(size_,start_))
  38 {
  39         initial_free_list(0);
  40 }
  41
  42 template<typename Block> void free_list_allocator<Block>::initial_free_list(cell occupied)
  43 {
  44         free_blocks.initial_free_list(start,end,occupied);
  45 }
  46
  47 template<typename Block> bool free_list_allocator<Block>::contains_p(Block *block)
  48 {
  49         return ((cell)block - start) < size;
  50 }
  51
  52 template<typename Block> Block *free_list_allocator<Block>::first_block()
  53 {
  54         return (Block *)start;
  55 }
  56
  57 template<typename Block> Block *free_list_allocator<Block>::last_block()
  58 {
  59         return (Block *)end;
  60 }
  61
  62 template<typename Block> Block *free_list_allocator<Block>::next_block_after(Block *block)
  63 {
  64         return (Block *)((cell)block + block->size());
  65 }
  66
  67 template<typename Block> Block *free_list_allocator<Block>::next_allocated_block_after(Block *block)
  68 {
  69         while(block != this->last_block() && block->free_p())
  70         {
  71                 free_heap_block *free_block = (free_heap_block *)block;
  72                 block = (object *)((cell)free_block + free_block->size());
  73         }
  74
  75         if(block == this->last_block())
  76                 return NULL;
  77         else
  78                 return block;
  79 }
  80
  81 template<typename Block> bool free_list_allocator<Block>::can_allot_p(cell size)
  82 {
  83         return free_blocks.can_allot_p(size);
  84 }
  85
  86 template<typename Block> Block *free_list_allocator<Block>::allot(cell size)
  87 {
  88         size = align(size,data_alignment);
  89
  90         free_heap_block *block = free_blocks.find_free_block(size);
  91         if(block)
  92         {
  93                 block = free_blocks.split_free_block(block,size);
  94                 return (Block *)block;
  95         }
  96         else
  97                 return NULL;
  98 }
  99
 100 template<typename Block> void free_list_allocator<Block>::free(Block *block)
 101 {
 102         free_heap_block *free_block = (free_heap_block *)block;
 103         free_block->make_free(block->size());
 104         free_blocks.add_to_free_list(free_block);
 105 }
 106
 107 template<typename Block> cell free_list_allocator<Block>::free_space()
 108 {
 109         return free_blocks.free_space;
 110 }
 111
 112 template<typename Block> cell free_list_allocator<Block>::occupied_space()
 113 {
 114         return size - free_blocks.free_space;
 115 }
 116
 117 template<typename Block> cell free_list_allocator<Block>::largest_free_block()
 118 {
 119         return free_blocks.largest_free_block();
 120 }
 121
 122 template<typename Block> cell free_list_allocator<Block>::free_block_count()
 123 {
 124         return free_blocks.free_block_count;
 125 }
 126
 127 template<typename Block>
 128 template<typename Iterator>
 129 void free_list_allocator<Block>::sweep(Iterator &iter)
 130 {
 131         free_blocks.clear_free_list();
 132
 133         Block *start = this->first_block();
 134         Block *end = this->last_block();
 135
 136         while(start != end)
 137         {
 138                 /* find next unmarked block */
 139                 start = state.next_unmarked_block_after(start);
 140
 141                 if(start != end)
 142                 {
 143                         /* find size */
 144                         cell size = state.unmarked_block_size(start);
 145                         FACTOR_ASSERT(size > 0);
 146
 147                         free_heap_block *free_block = (free_heap_block *)start;
 148                         free_block->make_free(size);
 149                         free_blocks.add_to_free_list(free_block);
 150                         iter(start, size);
 151
 152                         start = (Block *)((char *)start + size);
 153                 }
 154         }
 155 }
 156
 157 template<typename Block>
 158 struct null_sweep_iterator
 159 {
 160         void operator()(Block *free_block, cell size) {}
 161 };
 162
 163 template<typename Block>
 164 void free_list_allocator<Block>::sweep()
 165 {
 166         null_sweep_iterator<Block> none;
 167         sweep(none);
 168 }
 169
 170 template<typename Block, typename Iterator> struct heap_compactor {
 171         mark_bits<Block> *state;
 172         char *address;
 173         Iterator &iter;
 174         const Block **finger;
 175
 176         explicit heap_compactor(mark_bits<Block> *state_, Block *address_, Iterator &iter_, const Block **finger_) :
 177                 state(state_), address((char *)address_), iter(iter_), finger(finger_) {}
 178
 179         void operator()(Block *block, cell size)
 180         {
 181                 if(this->state->marked_p(block))
 182                 {
 183                         *finger = (Block *)((char *)block + size);
 184                         memmove((Block *)address,block,size);
 185                         iter(block,(Block *)address,size);
 186                         address += size;
 187                 }
 188         }
 189 };
 190
 191 /* The forwarding map must be computed first by calling
 192 state.compute_forwarding(). */
 193 template<typename Block>
 194 template<typename Iterator, typename Fixup>
 195 void free_list_allocator<Block>::compact(Iterator &iter, Fixup fixup, const Block **finger)
 196 {
 197         heap_compactor<Block,Iterator> compactor(&state,first_block(),iter,finger);
 198         iterate(compactor,fixup);
 199
 200         /* Now update the free list; there will be a single free block at
 201         the end */
 202         free_blocks.initial_free_list(start,end,(cell)compactor.address - start);
 203 }
 204
 205 /* During compaction we have to be careful and measure object sizes differently */
 206 template<typename Block>
 207 template<typename Iterator, typename Fixup>
 208 void free_list_allocator<Block>::iterate(Iterator &iter, Fixup fixup)
 209 {
 210         Block *scan = first_block();
 211         Block *end = last_block();
 212
 213         while(scan != end)
 214         {
 215                 cell size = fixup.size(scan);
 216                 Block *next = (Block *)((cell)scan + size);
 217                 if(!scan->free_p()) iter(scan,size);
 218                 scan = next;
 219         }
 220 }
 221
 222 template<typename Block>
 223 template<typename Iterator>
 224 void free_list_allocator<Block>::iterate(Iterator &iter)
 225 {
 226         iterate(iter,no_fixup());
 227 }
 228
 229 }