vm/free_list.cpp

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