kernel/fiasco/src/kern/buddy_alloc.cpp

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