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   enum
  58   {
  59     // the number of bits in the bitmap is given by the amount of the smallest
  60     // supported blocks. We need an extra bit in the case that the Max_mem
  61     // is no multiple of Max_size to ensure that buddy() does not access
  62     // beyond the bitmap.
  63     Buddy_bits = (Max_mem + Min_size - 1)/Min_size
  64                  + !!(Max_mem & (Max_size-1))
  65   };
  66   Head *_free[Num_sizes];
  67   Bitmap<Buddy_bits> _free_map;
  68 };
  69
  70
  71 class Buddy_alloc : public Buddy_t_base<10, 8, Config::kernel_mem_max>
  72 {
  73 };
  74
  75
  76 //----------------------------------------------------------------------------
  77 IMPLEMENTATION:
  78
  79 #include <cstdio>
  80 #include <cassert>
  81 #include "kdb_ke.h"
  82 #include "warn.h"
  83
  84 PRIVATE
  85 template<int A, int B, int M>
  86 inline
  87 Buddy_base::Head *
  88 Buddy_t_base<A,B,M>::buddy(void *block, unsigned long index, Head **new_block)
  89 {
  90   //printf("buddy(%p, %ld)\n", block, index);
  91   unsigned long const size = Min_size << index;
  92   unsigned long const n_size = size << 1;
  93   if (index + 1 >= Num_sizes)
  94     return 0;
  95   unsigned long b = (unsigned long)block;
  96   unsigned long _buddy = b & ~(n_size-1);
  97   *new_block = (Head*)_buddy;
  98   if (_buddy == b)
  99     _buddy += size;
 100
 101   Head * const _buddy_h = (Head*)_buddy;
 102
 103   // this test may access one bit behind our maximum, this is safe because
 104   // we allocated an extra bit
 105   if (_free_map[(_buddy - _base)/Min_size] && _buddy_h->index == index)
 106     return _buddy_h;
 107
 108   return 0;
 109 }
 110
 111 PUBLIC
 112 template<int A, int B, int M>
 113 inline
 114 void
 115 Buddy_t_base<A,B,M>::free(void *block, unsigned long size)
 116 {
 117   assert_kdb ((unsigned long)block >= _base);
 118   assert_kdb ((unsigned long)block - _base < Max_mem);
 119   assert_kdb (!_free_map[((unsigned long)block - _base) / Min_size]);
 120   //bool _b = 0;
 121   //if (_debug) printf("Buddy::free(%p, %ld)\n", block, size);
 122   unsigned size_index = 0;
 123   while (((unsigned long)Min_size << size_index) < size)
 124     ++size_index;
 125
 126   if (size != (unsigned long)Min_size << size_index)
 127     WARNX(Info, "Buddy::free: Size mismatch: %lx v %lx\n",
 128           size, (unsigned long)Min_size << size_index);
 129
 130
 131   // no need to look for a buddy if we already have the biggest block size
 132   while (size_index + 1 < Num_sizes)
 133     {
 134       Head *n, *b;
 135       b = buddy(block, size_index, &n);
 136       if (b)
 137         {
 138         //if (!_b && _debug) dump();
 139         //if (_debug) printf("  found buddy %p (n=%p size=%ld)\n", b, n, size_index+1);
 140           b->unlink();
 141           block = n;
 142           ++size_index;
 143           //_b = 1;
 144         }
 145       else
 146         break;
 147     }
 148
 149   //printf("  link free %p\n", block);
 150   Head::link(_free + size_index, block, size_index);
 151   _free_map.set_bit(((unsigned long)block - _base) / Min_size);
 152   //if (_b && _debug) dump();
 153 }
 154
 155
 156 PUBLIC
 157 template<int A, int B, int M>
 158 void
 159 Buddy_t_base<A,B,M>::add_mem(void *b, unsigned long size)
 160 {
 161   unsigned long start = (unsigned long)b;
 162   unsigned long al_start;
 163   al_start = (start + Min_size - 1) & ~(Min_size -1);
 164
 165   //printf("Buddy::add_mem(%p, %lx): al_start=%lx; _base=%lx\n", b, size, al_start, _base);
 166
 167   // _debug = 0;
 168   if (size <= al_start-start)
 169     return;
 170
 171   size -= (al_start-start);
 172   size &= ~(Min_size -1);
 173
 174   while (size)
 175     {
 176       free((void*)al_start, Min_size);
 177       al_start += Min_size;
 178       size -= Min_size;
 179     }
 180   // _debug = 1;
 181   //dump();
 182 }
 183
 184
 185
 186 PRIVATE
 187 template<int A, int B, int M>
 188 inline
 189 void
 190 Buddy_t_base<A,B,M>::split(Head *b, unsigned size_index, unsigned i)
 191 {
 192   //unsigned si = size_index;
 193   //printf("Buddy::split(%p, %d, %d)\n", b, size_index, i);
 194   for (; i > size_index; ++size_index)
 195     {
 196       unsigned long buddy = (unsigned long)b + (Min_size << size_index);
 197       Head::link(_free + size_index, (void*)buddy, size_index);
 198       _free_map.set_bit((buddy - _base) / Min_size);
 199     }
 200
 201   //if (si!=i) dump();
 202 }
 203
 204 PUBLIC
 205 template<int A, int B, int M>
 206 inline
 207 void *
 208 Buddy_t_base<A,B,M>::alloc(unsigned long size)
 209 {
 210   unsigned size_index = 0;
 211   while (((unsigned long)Min_size << size_index) < size)
 212     ++size_index;
 213
 214   if (size != (unsigned long)Min_size << size_index)
 215     WARNX(Info, "Buddy::alloc: Size mismatch: %lx v %lx\n",
 216           size, (unsigned long)Min_size << size_index);
 217
 218   //printf("[%u]: Buddy::alloc(%ld)[ret=%p]: size_index=%d\n", Proc::cpu_id(), size, __builtin_return_address(0), size_index);
 219
 220   for (unsigned i = size_index; i < Num_sizes; ++i)
 221     {
 222       Head *f = _free[i];
 223       if (f)
 224         {
 225           f->unlink();
 226           split(f, size_index, i);
 227           _free_map.clear_bit(((unsigned long)f - _base) / Min_size);
 228           //printf("[%u]: =%p\n", Proc::cpu_id(), f);
 229           return f;
 230         }
 231     }
 232   return 0;
 233 }
 234
 235 PUBLIC
 236 template< int A, int B, int M >
 237 void
 238 Buddy_t_base<A,B,M>::dump() const
 239 {
 240   printf("Buddy_alloc [%d,%d]\n", Min_size, Num_sizes);
 241   for (unsigned i = 0; i < Num_sizes; ++i)
 242     {
 243       unsigned c = 0;
 244       Head *h = _free[i];
 245       printf("  [%d] %p(%ld)", Min_size << i, h, h?h->index:0UL);
 246       while (h)
 247         {
 248           h = h->next;
 249           if (c < 5)
 250             printf(" -> %p(%ld)", h, h?h->index:0UL);
 251           else
 252             {
 253               printf(" ...");
 254               break;
 255             }
 256
 257           ++c;
 258         }
 259       printf("\n");
 260     }
 261 }
 262
 263 PUBLIC
 264 void
 265 Buddy_base::init(unsigned long base)
 266 { _base = base; }
 267
 268 PUBLIC
 269 template< int A, int B, int M >
 270 unsigned long
 271 Buddy_t_base<A,B,M>::avail() const
 272 {
 273   unsigned long a = 0;
 274   for (unsigned i = 0; i < Num_sizes; ++i)
 275     {
 276       Head *h = _free[i];
 277       while (h)
 278         {
 279           a += (Min_size << i);
 280           h = h->next;
 281         }
 282     }
 283   return a;
 284 }
 285