vm/free_list.cpp

   1 #include "master.hpp"
   2
   3 namespace factor
   4 {
   5
   6 void free_list::clear_free_list()
   7 {
   8         for(cell i = 0; i < free_list_count; i++)
   9                 small_blocks[i].clear();
  10         large_blocks.clear();
  11         free_block_count = 0;
  12         free_space = 0;
  13 }
  14
  15 void free_list::initial_free_list(cell start, cell end, cell occupied)
  16 {
  17         clear_free_list();
  18         if(occupied != end - start)
  19         {
  20                 free_heap_block *last_block = (free_heap_block *)(start + occupied);
  21                 last_block->make_free(end - (cell)last_block);
  22                 add_to_free_list(last_block);
  23         }
  24 }
  25
  26 void free_list::add_to_free_list(free_heap_block *block)
  27 {
  28         cell size = block->size();
  29
  30         free_block_count++;
  31         free_space += size;
  32
  33         if(size < free_list_count * data_alignment)
  34                 small_blocks[size / data_alignment].push_back(block);
  35         else
  36                 large_blocks.insert(block);
  37 }
  38
  39 free_heap_block *free_list::find_free_block(cell size)
  40 {
  41         /* Check small free lists */
  42         if(size / data_alignment < free_list_count)
  43         {
  44                 std::vector<free_heap_block *> &blocks = small_blocks[size / data_alignment];
  45                 if(blocks.size() == 0)
  46                 {
  47                         /* Round up to a multiple of 'size' */
  48                         cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
  49
  50                         /* Allocate a block this big */
  51                         free_heap_block *large_block = find_free_block(large_block_size);
  52                         if(!large_block) return NULL;
  53
  54                         large_block = split_free_block(large_block,large_block_size);
  55
  56                         /* Split it up into pieces and add each piece back to the free list */
  57                         for(cell offset = 0; offset < large_block_size; offset += size)
  58                         {
  59                                 free_heap_block *small_block = large_block;
  60                                 large_block = (free_heap_block *)((cell)large_block + size);
  61                                 small_block->make_free(size);
  62                                 add_to_free_list(small_block);
  63                         }
  64                 }
  65
  66                 free_heap_block *block = blocks.back();
  67                 blocks.pop_back();
  68
  69                 free_block_count--;
  70                 free_space -= block->size();
  71
  72                 return block;
  73         }
  74         else
  75         {
  76                 /* Check large free list */
  77                 free_heap_block key;
  78                 key.make_free(size);
  79                 large_block_set::iterator iter = large_blocks.lower_bound(&key);
  80                 large_block_set::iterator end = large_blocks.end();
  81
  82                 if(iter != end)
  83                 {
  84                         free_heap_block *block = *iter;
  85                         large_blocks.erase(iter);
  86
  87                         free_block_count--;
  88                         free_space -= block->size();
  89
  90                         return block;
  91                 }
  92
  93                 return NULL;
  94         }
  95 }
  96
  97 free_heap_block *free_list::split_free_block(free_heap_block *block, cell size)
  98 {
  99         if(block->size() != size)
 100         {
 101                 /* split the block in two */
 102                 free_heap_block *split = (free_heap_block *)((cell)block + size);
 103                 split->make_free(block->size() - size);
 104                 block->make_free(size);
 105                 add_to_free_list(split);
 106         }
 107
 108         return block;
 109 }
 110
 111 bool free_list::can_allot_p(cell size)
 112 {
 113         return largest_free_block() >= std::max(size,allocation_page_size);
 114 }
 115
 116 cell free_list::largest_free_block()
 117 {
 118         if(large_blocks.size())
 119         {
 120                 large_block_set::reverse_iterator last = large_blocks.rbegin();
 121                 return (*last)->size();
 122         }
 123         else
 124         {
 125                 for(int i = free_list_count - 1; i >= 0; i--)
 126                 {
 127                         if(small_blocks[i].size())
 128                                 return small_blocks[i].back()->size();
 129                 }
 130
 131                 return 0;
 132         }
 133 }
 134
 135 }