lib-src/memory/buddysys.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <assert.h>
  26 #include <stddef.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <AD/memory/buddy.h>     // Fibonacci buddy system
  30 #include <AD/generic/tables.h>   // Fibonacci numbers table
  31
  32 static const long * fib = fibonacci + 2;  // 1, 2, 3, 5, 8, ...
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //  Constructor
  36 //////////////////////////////////////////////////////////////////////////////
  37 Buddy::Buddy(void * pool, size_t poolSize) : Mem("Buddy")
  38 {  init_pool(pool, poolSize); }
  39
  40 //////////////////////////////////////////////////////////////////////////////
  41 //  Destructor.  Nothing to do
  42 //////////////////////////////////////////////////////////////////////////////
  43 Buddy::~Buddy() {}
  44
  45 //////////////////////////////////////////////////////////////////////////////
  46 // Method to initialize the pools
  47 //////////////////////////////////////////////////////////////////////////////
  48 void Buddy::init_pool(void * pool, size_t poolSize)
  49 {
  50    my_pool      = pool;
  51    my_pool_size = poolSize;
  52
  53    assert(sizeof(Block *) * levels <= poolSize);
  54    free_lists = (Block**)pool;
  55    pool = (Byte*)pool + sizeof(Block*) * levels;
  56    poolSize -= sizeof(Block*) * levels;
  57
  58    register size_t elements = (poolSize + sizeof(Block) - 1) / sizeof(Block);
  59    register Block * block = (Block *)pool;
  60    register int i;
  61
  62    //
  63    // Initialize free lists to empty
  64    //
  65    for (i = 0; i < levels; i++) free_lists[i] = NULL;
  66
  67    //
  68    // Find the maximum |i| such that |fib[i] < elements|
  69    //
  70    for (i = 0; (size_t)fib[i] <= elements; i++);
  71    i--;
  72
  73    begin = block;
  74    end = block + elements;
  75    //
  76    // Split block into chunks and append them onto the free lists.
  77    //
  78    while (elements > 0) {
  79       while (elements < (size_t)fib[i]) i--;
  80       register int size = fib[i];
  81       block->fib_number = i;
  82       block->right_buddies = 0;
  83       block->allocated = false;
  84       block->next = free_lists[i];
  85       if (block->next) block->next->last = block;
  86       free_lists[i] = block;
  87       block += size;
  88       elements -= size;
  89    }
  90 }
  91
  92 //////////////////////////////////////////////////////////////////////////////
  93 // Allocate some memory and initialize it to zeros
  94 //////////////////////////////////////////////////////////////////////////////
  95 void * Buddy::c_alloc(size_t size)
  96 {  void * core = m_alloc(size);
  97    memset(core,0,size);
  98    return core;
  99 }
 100
 101 //////////////////////////////////////////////////////////////////////////////
 102 // Method to allocate memory
 103 //////////////////////////////////////////////////////////////////////////////
 104 void * Buddy::m_alloc(size_t size)
 105 {  register int i, j;
 106    register size_t elements =
 107       (size + sizeof(Block) + offsetof(Block,next) - 1) / sizeof(Block);
 108
 109    //
 110    // Locate the smallest index |i| such that |fib[i] >= elements|
 111    // with a binary search.
 112    //
 113    {  register int low, high;
 114       for (low = 0, high = levels-1; low < high; ) {
 115           i = (low + high)/2;
 116           if ((size_t)fib[i] < elements) low = i+1;
 117           else if ((size_t)fib[i] == elements) break;
 118           else high = i-1;
 119       }
 120    }
 121
 122    //
 123    // Now, locate a non-empty free list with a sequential search.
 124    //
 125    while ((size_t)fib[i] < elements) i++;
 126    for (j = i; j < levels && ! free_lists[j]; j++);
 127    if (j >= levels) return NULL;
 128
 129    //
 130    // Unlink the free block from the free list.
 131    //
 132    register Block * block = free_lists[j];
 133    free_lists[j] = block->next;
 134    if (block->next) block->next->last = NULL;
 135
 136    //
 137    // Split block into smaller chunks if |j > i|.
 138    // The size of the left buddy is the larger one.
 139    //
 140    for ( ;j > i && j > 1; j--) {
 141       register Block * right_buddy = block + fib[j-1];
 142       right_buddy->fib_number    = j-2;
 143       right_buddy->right_buddies = 0;
 144       right_buddy->next = free_lists[j-2];
 145       right_buddy->allocated = false;
 146       if (right_buddy->next) right_buddy->next->last = right_buddy;
 147       free_lists[j-2] = right_buddy;
 148       block->fib_number = j-1;
 149       block->right_buddies++;
 150    }
 151
 152    //
 153    // Mark the block to be allocated
 154    //
 155    block->allocated = true;
 156    return &(block->next);
 157 }
 158
 159 //////////////////////////////////////////////////////////////////////////////
 160 //  Frees memory
 161 //////////////////////////////////////////////////////////////////////////////
 162 void Buddy::free(void * core)
 163 {  register Block * block =
 164       (Block *)(((char *)core) - offsetof(Block,next));
 165    register int n;         // fibonacci number of current block
 166    assert(block->allocated);
 167
 168    block->allocated = false;   // Mark block as unallocated first.
 169
 170    //
 171    // Keep merging with neighbors until done.
 172    //
 173    for (;;) {
 174       register Block * buddy; // potential buddy
 175       n = block->fib_number;
 176       if (block->right_buddies == 0) {  // Are we a right buddy??
 177          buddy = block - fib [ n + 1 ];
 178          if (buddy >= begin && buddy->right_buddies > 0 &&
 179              ! buddy->allocated && buddy->fib_number == n+1) {
 180             //
 181             // Merge with left buddy
 182             //
 183             if (buddy == free_lists[ n+1 ]) free_lists[ n+1 ] = buddy->next;
 184             if (buddy->last) buddy->last->next = buddy->next;
 185             if (buddy->next) buddy->next->last = buddy->last;
 186             block = buddy;
 187             block->fib_number++;
 188             block->right_buddies--;
 189          } else break;
 190       } else {  // No, we are a left buddy
 191          buddy = block + fib [ n ];
 192          if (buddy + fib[n-1] < end && buddy->right_buddies == 0 &&
 193              ! buddy->allocated && buddy->fib_number == n-1) {
 194             //
 195             // Merge with right buddy
 196             //
 197             if (buddy == free_lists[ n-1 ]) free_lists[ n-1 ] = buddy->next;
 198             if (buddy->last) buddy->last->next = buddy->next;
 199             if (buddy->next) buddy->next->last = buddy->last;
 200             block->fib_number++;
 201             block->right_buddies--;
 202          } else break;
 203       }
 204    }
 205
 206    //
 207    // Link block back to the free list
 208    //
 209    n = block->fib_number;
 210    block->next = free_lists[n];
 211    if (block->next) block->next->last = block;
 212    free_lists[n] = block;
 213 }
 214
 215 //////////////////////////////////////////////////////////////////////////////
 216 // Additional Mem protocol
 217 //////////////////////////////////////////////////////////////////////////////
 218 void   Buddy::clear   ()  { init_pool(my_pool, my_pool_size); }
 219
 220 //////////////////////////////////////////////////////////////////////////////
 221 // Returns the size of a block
 222 //////////////////////////////////////////////////////////////////////////////
 223 size_t Buddy::size(const void * core) const
 224 {  register const Block * block =
 225       (const Block *)(((char *)core) - offsetof(Block,next));
 226    assert(block->allocated);
 227    return fib[block->fib_number] * sizeof(Block);
 228 }
 229