kernel/fiasco/src/kern/buddy_alloc.cpp

   1 INTERFACE:
   2
   3 #include <cassert>
   4 #include <hlist>
   5 #include "bitmap.h"
   6 #include "config.h"
   7
   8 class Buddy_base
   9 {
  10 protected:
  11   unsigned long _base;
  12
  13   struct Head : cxx::H_list_item
  14   {
  15     unsigned long index;
  16
  17     static void link(cxx::H_list<Head> &h, void *b, unsigned idx)
  18     {
  19       Head *n = (Head*)b;
  20       n->index = idx;
  21       h.add(n);
  22     }
  23   };
  24
  25   typedef cxx::H_list_bss<Head> B_list;
  26 };
  27
  28 template< int MIN_LOG2_SIZE, int NUM_SIZES, int MAX_MEM >
  29 class Buddy_t_base : public Buddy_base
  30 {
  31 public:
  32   enum
  33   {
  34     Min_log2_size = MIN_LOG2_SIZE,
  35     Min_size = 1UL << MIN_LOG2_SIZE,
  36     Num_sizes = NUM_SIZES,
  37     Max_size = Min_size << (NUM_SIZES - 1),
  38     Max_mem = MAX_MEM,
  39   };
  40
  41 private:
  42   enum
  43   {
  44     // the number of bits in the bitmap is given by the amount of the smallest
  45     // supported blocks. We need an extra bit in the case that the Max_mem
  46     // is no multiple of Max_size to ensure that buddy() does not access
  47     // beyond the bitmap.
  48     Buddy_bits = (Max_mem + Min_size - 1)/Min_size
  49                  + !!(Max_mem & (Max_size-1))
  50   };
  51   B_list _free[Num_sizes];
  52   Bitmap<Buddy_bits> _free_map;
  53 };
  54
  55
  56 class Buddy_alloc : public Buddy_t_base<10, 8, Config::kernel_mem_max>
  57 {
  58 };
  59
  60
  61 //----------------------------------------------------------------------------
  62 IMPLEMENTATION:
  63
  64 #include <cstdio>
  65 #include <cassert>
  66 #include "kdb_ke.h"
  67 #include "warn.h"
  68
  69 PRIVATE
  70 template<int A, int B, int M>
  71 inline
  72 Buddy_base::Head *
  73 Buddy_t_base<A,B,M>::buddy(void *block, unsigned long index, Head **new_block)
  74 {
  75   //printf("buddy(%p, %ld)\n", block, index);
  76   unsigned long const size = Min_size << index;
  77   unsigned long const n_size = size << 1;
  78   if (index + 1 >= Num_sizes)
  79     return 0;
  80   unsigned long b = (unsigned long)block;
  81   unsigned long _buddy = b & ~(n_size-1);
  82   *new_block = (Head*)_buddy;
  83   if (_buddy == b)
  84     _buddy += size;
  85
  86   Head * const _buddy_h = (Head*)_buddy;
  87
  88   // this test may access one bit behind our maximum, this is safe because
  89   // we allocated an extra bit
  90   if (_free_map[(_buddy - _base)/Min_size] && _buddy_h->index == index)
  91     return _buddy_h;
  92
  93   return 0;
  94 }
  95
  96 PUBLIC
  97 template<int A, int B, int M>
  98 inline
  99 void
 100 Buddy_t_base<A,B,M>::free(void *block, unsigned long size)
 101 {
 102   assert_kdb ((unsigned long)block >= _base);
 103   assert_kdb ((unsigned long)block - _base < Max_mem);
 104   assert_kdb (!_free_map[((unsigned long)block - _base) / Min_size]);
 105   //bool _b = 0;
 106   //if (_debug) printf("Buddy::free(%p, %ld)\n", block, size);
 107   unsigned size_index = 0;
 108   while (((unsigned long)Min_size << size_index) < size)
 109     ++size_index;
 110
 111   if (size != (unsigned long)Min_size << size_index)
 112     WARNX(Info, "Buddy::free: Size mismatch: %lx v %lx\n",
 113           size, (unsigned long)Min_size << size_index);
 114
 115
 116   // no need to look for a buddy if we already have the biggest block size
 117   while (size_index + 1 < Num_sizes)
 118     {
 119       Head *n, *b;
 120       b = buddy(block, size_index, &n);
 121       if (b)
 122         {
 123         //if (!_b && _debug) dump();
 124         //if (_debug) printf("  found buddy %p (n=%p size=%ld)\n", b, n, size_index+1);
 125           B_list::remove(b);
 126           block = n;
 127           ++size_index;
 128           //_b = 1;
 129         }
 130       else
 131         break;
 132     }
 133
 134   //printf("  link free %p\n", block);
 135   Head::link(_free[size_index], block, size_index);
 136   _free_map.set_bit(((unsigned long)block - _base) / Min_size);
 137   //if (_b && _debug) dump();
 138 }
 139
 140
 141 PUBLIC
 142 template<int A, int B, int M>
 143 void
 144 Buddy_t_base<A,B,M>::add_mem(void *b, unsigned long size)
 145 {
 146   unsigned long start = (unsigned long)b;
 147   unsigned long al_start;
 148   al_start = (start + Min_size - 1) & ~(Min_size -1);
 149
 150   //printf("Buddy::add_mem(%p, %lx): al_start=%lx; _base=%lx\n", b, size, al_start, _base);
 151
 152   // _debug = 0;
 153   if (size <= al_start-start)
 154     return;
 155
 156   size -= (al_start-start);
 157   size &= ~(Min_size -1);
 158
 159   while (size)
 160     {
 161       free((void*)al_start, Min_size);
 162       al_start += Min_size;
 163       size -= Min_size;
 164     }
 165   // _debug = 1;
 166   //dump();
 167 }
 168
 169
 170
 171 PRIVATE
 172 template<int A, int B, int M>
 173 inline
 174 void
 175 Buddy_t_base<A,B,M>::split(Head *b, unsigned size_index, unsigned i)
 176 {
 177   //unsigned si = size_index;
 178   //printf("Buddy::split(%p, %d, %d)\n", b, size_index, i);
 179   for (; i > size_index; ++size_index)
 180     {
 181       unsigned long buddy = (unsigned long)b + (Min_size << size_index);
 182       Head::link(_free[size_index], (void*)buddy, size_index);
 183       _free_map.set_bit((buddy - _base) / Min_size);
 184     }
 185
 186   //if (si!=i) dump();
 187 }
 188
 189 PUBLIC
 190 template<int A, int B, int M>
 191 inline
 192 void *
 193 Buddy_t_base<A,B,M>::alloc(unsigned long size)
 194 {
 195   unsigned size_index = 0;
 196   while (((unsigned long)Min_size << size_index) < size)
 197     ++size_index;
 198
 199   if (size != (unsigned long)Min_size << size_index)
 200     WARNX(Info, "Buddy::alloc: Size mismatch: %lx v %lx\n",
 201           size, (unsigned long)Min_size << size_index);
 202
 203   //printf("[%u]: Buddy::alloc(%ld)[ret=%p]: size_index=%d\n", Proc::cpu_id(), size, __builtin_return_address(0), size_index);
 204
 205   for (unsigned i = size_index; i < Num_sizes; ++i)
 206     {
 207       Head *f = _free[i].front();
 208       if (f)
 209         {
 210           B_list::remove(f);
 211           split(f, size_index, i);
 212           _free_map.clear_bit(((unsigned long)f - _base) / Min_size);
 213           //printf("[%u]: =%p\n", Proc::cpu_id(), f);
 214           return f;
 215         }
 216     }
 217   return 0;
 218 }
 219
 220 PUBLIC
 221 template< int A, int B, int M >
 222 void
 223 Buddy_t_base<A,B,M>::dump() const
 224 {
 225   printf("Buddy_alloc [%d,%d]\n", Min_size, Num_sizes);
 226   for (unsigned i = 0; i < Num_sizes; ++i)
 227     {
 228       unsigned c = 0;
 229       B_list::Const_iterator h = _free[i].begin();
 230       printf("  [%d] %p(%ld)", Min_size << i, *h, h != _free[i].end() ? h->index : 0UL);
 231       while (h != _free[i].end())
 232         {
 233           ++h;
 234           if (c < 5)
 235             printf(" -> %p(%ld)", *h, *h?h->index:0UL);
 236           else
 237             {
 238               printf(" ...");
 239               break;
 240             }
 241
 242           ++c;
 243         }
 244       printf("\n");
 245     }
 246 }
 247
 248 PUBLIC
 249 void
 250 Buddy_base::init(unsigned long base)
 251 { _base = base; }
 252
 253 PUBLIC
 254 template< int A, int B, int M >
 255 unsigned long
 256 Buddy_t_base<A,B,M>::avail() const
 257 {
 258   unsigned long a = 0;
 259   for (unsigned i = 0; i < Num_sizes; ++i)
 260     {
 261       for (B_list::Const_iterator h = _free[i].begin(); h != _free[i].end(); ++h)
 262         a += (Min_size << i);
 263     }
 264   return a;
 265 }
 266