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