kernel/fiasco/src/lib/libk/slab_cache_anon.cpp

   1 INTERFACE:
   2
   3 #include <spin_lock.h>
   4
   5 // The anonymous slab allocator.  You can specialize this allocator by
   6 // providing your own initialization functions and your own low-level
   7 // allocation functions.
   8
   9 class slab_cache_anon;
  10
  11 class slab
  12 {
  13 private:
  14   slab(const slab&);    // copy constructors remain undefined
  15
  16   struct slab_entry
  17   {
  18     slab_entry *_next_free;
  19   };
  20
  21   slab_cache_anon *_cache;
  22   slab_entry *_first_free;
  23   slab *_next, *_prev;
  24   unsigned short _in_use;
  25 };
  26
  27 class slab_cache_anon
  28 {
  29 protected:
  30   friend class slab;
  31
  32   // Low-level allocator functions:
  33
  34   // Allocate/free a block.  "size" is always a multiple of PAGE_SIZE.
  35   virtual void *block_alloc(unsigned long size, unsigned long alignment) = 0;
  36   virtual void block_free(void *block, unsigned long size) = 0;
  37
  38 private:
  39   slab_cache_anon();
  40   slab_cache_anon(const slab_cache_anon&); // default constructor is undefined
  41
  42   //
  43   // data declaration follows
  44   //
  45
  46   // The slabs of this cache are held in a partially-sorted
  47   // doubly-linked list.  First come the fully-active slabs (all
  48   // elements in use), then the partially active slabs, then empty
  49   // slabs.
  50   slab *_first_slab, *_first_available_slab, *_last_slab;
  51   unsigned long _slab_size;
  52   unsigned _entry_size, _elem_num;
  53   typedef Spin_lock<> Lock;
  54   Lock lock;
  55   char const *_name;
  56 };
  57
  58 IMPLEMENTATION:
  59
  60 #include <cassert>
  61 #include <cstddef>
  62 #include <cstdlib>
  63 #include <lock_guard.h>
  64
  65 // default deallocator must not be called -- must use explicit destruction
  66 inline NOEXPORT
  67 void
  68 slab::operator delete(void* /*block*/)
  69 {
  70   assert (!"slab::operator delete called");
  71 }
  72
  73 PUBLIC
  74 slab::slab(slab_cache_anon *cache, void *mem)
  75 : _cache(cache), _next(0), _prev(0), _in_use(0)
  76 {
  77   // Compute pointer to first data element, now taking into account
  78   // the latest colorization offset
  79   char *data = reinterpret_cast<char*>(mem);
  80
  81   // Initialize the cache elements
  82   slab_entry *e = 0, *e_prev = 0;
  83
  84   for (unsigned i = 0; i < cache->_elem_num; i++)
  85     {
  86       e = reinterpret_cast<slab_entry *>(data);
  87
  88       e->_next_free = e_prev;
  89       data += cache->_entry_size;
  90       e_prev = e;
  91     }
  92
  93   _first_free = e;
  94 }
  95
  96 PUBLIC
  97 void *
  98 slab::alloc()
  99 {
 100   slab_entry *e = _first_free;
 101
 102   if (! e)
 103     return 0;
 104
 105   _first_free = e->_next_free;
 106   ++_in_use;
 107
 108   return e;
 109 }
 110
 111 PUBLIC
 112 void
 113 slab::free(void *entry)
 114 {
 115   slab_entry *e = reinterpret_cast<slab_entry *>(entry);
 116   e->_next_free = _first_free;
 117   _first_free = e;
 118
 119   assert(_in_use);
 120   --_in_use;
 121 }
 122
 123 PUBLIC
 124 inline bool
 125 slab::is_empty() const
 126 {
 127   return _in_use == 0;
 128 }
 129
 130 PUBLIC
 131 inline bool
 132 slab::is_full() const
 133 {
 134   return _in_use == _cache->_elem_num;
 135 }
 136
 137 PUBLIC
 138 inline unsigned
 139 slab::in_use() const
 140 {
 141   return _in_use;
 142 }
 143
 144 PUBLIC
 145 void
 146 slab::enqueue(slab *prev)
 147 {
 148   assert(prev);
 149
 150   if ((_next = prev->_next))
 151     _next->_prev = this;
 152   _prev = prev;
 153   _prev->_next = this;
 154 }
 155
 156 PUBLIC
 157 void
 158 slab::dequeue()
 159 {
 160   if (_prev)
 161     _prev->_next = _next;
 162   if (_next)
 163     _next->_prev = _prev;
 164
 165   _prev = _next = 0;
 166 }
 167
 168 PUBLIC
 169 inline slab *
 170 slab::prev() const
 171 {
 172   return _prev;
 173 }
 174
 175 PUBLIC
 176 inline slab *
 177 slab::next() const
 178 {
 179   return _next;
 180 }
 181
 182 PUBLIC
 183 inline void *
 184 slab::operator new(size_t, void *block) throw()
 185 {
 186   // slabs must be size-aligned so that we can compute their addresses
 187   // from element addresses
 188   return block;
 189 }
 190
 191
 192 PUBLIC static inline
 193 unsigned
 194 slab_cache_anon::entry_size(unsigned elem_size, unsigned alignment)
 195 { return (elem_size + alignment - 1) & ~(alignment - 1); }
 196
 197 //
 198 // slab_cache_anon
 199 //
 200 PUBLIC inline NEEDS[slab_cache_anon::entry_size]
 201 slab_cache_anon::slab_cache_anon(unsigned elem_size,
 202                                  unsigned alignment,
 203                                  char const * name,
 204                                  unsigned long min_size,
 205                                  unsigned long max_size)
 206   : _first_slab(0), _first_available_slab(0), _last_slab(0),
 207     _entry_size(entry_size(elem_size, alignment)),
 208     _name (name)
 209 {
 210   lock.init();
 211
 212   for (
 213       _slab_size = min_size;
 214       (_slab_size - sizeof(slab)) / _entry_size < 8
 215         && _slab_size < max_size;
 216       _slab_size <<= 1) ;
 217
 218   _elem_num = (_slab_size - sizeof(slab)) / _entry_size;
 219 }
 220
 221 //
 222 // slab_cache_anon
 223 //
 224 PUBLIC inline
 225 slab_cache_anon::slab_cache_anon(unsigned long slab_size,
 226                                  unsigned elem_size,
 227                                  unsigned alignment,
 228                                  char const * name)
 229   : _first_slab(0), _first_available_slab(0), _last_slab(0),
 230     _slab_size(slab_size), _entry_size(entry_size(elem_size, alignment)),
 231     _name (name)
 232 {
 233   lock.init();
 234   _elem_num = (_slab_size - sizeof(slab)) / _entry_size;
 235 }
 236
 237 PUBLIC
 238 virtual
 239 slab_cache_anon::~slab_cache_anon()
 240 {
 241   // the derived class should call destroy() before deleting us.
 242   // assert(_first_slab == 0);
 243 }
 244
 245 PROTECTED inline
 246 void
 247 slab_cache_anon::destroy()      // descendant should call this in destructor
 248 {
 249 }
 250
 251 PUBLIC
 252 virtual void *
 253 slab_cache_anon::alloc()        // request initialized member from cache
 254 {
 255   Lock_guard<Lock> guard(&lock);
 256
 257   if (! _first_available_slab)
 258     {
 259       char *m = (char*)block_alloc(_slab_size, _slab_size);
 260       if (!m)
 261         return 0;
 262
 263       slab *s = new (m + _slab_size - sizeof(slab)) slab(this, m);
 264
 265       _first_available_slab = s;
 266
 267       if (_last_slab)
 268         {
 269           assert(_last_slab->is_full());
 270
 271           _first_available_slab->enqueue(_last_slab);
 272           _last_slab = _first_available_slab;
 273         }
 274       else                      // this was the first slab we allocated
 275         _first_slab = _last_slab = _first_available_slab;
 276     }
 277
 278   assert(_first_available_slab
 279          && ! _first_available_slab->is_full());
 280   assert(! _first_available_slab->prev()
 281          || _first_available_slab->prev()->is_full());
 282
 283   void *ret = _first_available_slab->alloc();
 284   assert(ret);
 285
 286   if (_first_available_slab->is_full())
 287     _first_available_slab = _first_available_slab->next();
 288
 289   return ret;
 290 }
 291
 292 PUBLIC template< typename Q >
 293 inline
 294 void *
 295 slab_cache_anon::q_alloc(Q *quota)
 296 {
 297   if (EXPECT_FALSE(!quota->alloc(_entry_size)))
 298     return 0;
 299
 300   void *r;
 301   if (EXPECT_FALSE(!(r=alloc())))
 302     {
 303       quota->free(_entry_size);
 304       return 0;
 305     }
 306
 307   return r;
 308 }
 309
 310 PUBLIC
 311 virtual void
 312 slab_cache_anon::free(void *cache_entry) // return initialized member to cache
 313 {
 314   Lock_guard<Lock> guard(&lock);
 315
 316   slab *s = reinterpret_cast<slab*>
 317     ((reinterpret_cast<unsigned long>(cache_entry) & ~(_slab_size - 1)) + _slab_size - sizeof(slab));
 318
 319   bool was_full = s->is_full();
 320
 321   s->free(cache_entry);
 322
 323   if (was_full)
 324     {
 325       if (s->next() == 0)       // have no right neighbor?
 326         {
 327           assert(! _first_available_slab);
 328         }
 329       else if (s->next()->is_full()) // right neigbor full?
 330         {
 331           // We requeue to become the first non-full slab in the queue
 332           // so that all full slabs are at the beginning of the queue.
 333
 334           if (s == _first_slab)
 335             _first_slab = s->next();
 336           // don't care about _first_available_slab, _last_slab --
 337           // they cannot point to s because we were full and have a
 338           // right neighbor
 339
 340           s->dequeue();
 341
 342           if (_first_available_slab)
 343             {
 344               // _first_available_slab->prev() is defined because we
 345               // had a right neighbor which is full, that is,
 346               // _first_available_slab wasn't our right neighbor and
 347               // now isn't the first slab in the queue
 348               assert(_first_available_slab->prev()->is_full());
 349               s->enqueue(_first_available_slab->prev());
 350             }
 351           else
 352             {
 353               // all slabs were full
 354               assert(_last_slab->is_full());
 355               s->enqueue(_last_slab);
 356               _last_slab = s;
 357             }
 358         }
 359
 360       _first_available_slab = s;
 361
 362     }
 363   else if (s->is_empty())
 364     {
 365       if (s->next() && (! s->next()->is_empty())) // right neighbor not empty?
 366         {
 367           // Move to tail of list
 368
 369           if (s == _first_slab)
 370             _first_slab = s->next();
 371           if (s == _first_available_slab)
 372             _first_available_slab = s->next();
 373           // don't care about _last_slab because we know we have a
 374           // right neighbor
 375
 376           s->dequeue();
 377
 378           s->enqueue(_last_slab);
 379           _last_slab = s;
 380         }
 381     }
 382   else
 383     {
 384       // We weren't either full or empty; we already had free
 385       // elements.  This changes nothing in the queue, and there
 386       // already must have been a _first_available_slab.
 387     }
 388
 389   assert(_first_available_slab);
 390 }
 391
 392 PUBLIC template< typename Q >
 393 inline
 394 void
 395 slab_cache_anon::q_free(Q *quota, void *obj)
 396 {
 397   free(obj);
 398   quota->free(_entry_size);
 399 }
 400
 401 PUBLIC
 402 virtual unsigned long
 403 slab_cache_anon::reap()         // request that cache returns memory to system
 404 {
 405   Lock_guard<Lock> guard(&lock);
 406
 407   if (! _first_slab)
 408     return 0;                   // haven't allocated anything yet
 409
 410   // never delete first slab, even if it is empty
 411   if (_last_slab == _first_slab
 412       || (! _last_slab->is_empty()))
 413     return 0;
 414
 415   slab *s = _last_slab;
 416
 417   if (_first_available_slab == s)
 418     _first_available_slab = 0;
 419
 420   _last_slab = s->prev();
 421   s->dequeue();
 422
 423   // explicitly call destructor to delete s;
 424   s->~slab();
 425   block_free(s, _slab_size);
 426
 427   return _slab_size;
 428 }
 429
 430 // Debugging output
 431
 432 #include <cstdio>
 433
 434 PUBLIC
 435 virtual void
 436 slab_cache_anon::debug_dump()
 437 {
 438   printf ("%s: %lu-KB slabs (elems per slab=%d ",
 439           _name, _slab_size / 1024, _elem_num);
 440
 441   unsigned count, total = 0, total_elems = 0;
 442   slab* s = _first_slab;
 443
 444   for (count = 0;
 445        s && s->is_full();
 446        s = s->next())
 447     {
 448       count++;
 449       total_elems += s->in_use();
 450     }
 451
 452   total += count;
 453
 454   printf ("%u full, ", count);
 455
 456   for (count = 0;
 457        s && ! s->is_empty();
 458        s = s->next())
 459     {
 460       if (s->is_full())
 461         printf ("\n*** wrongly-enqueued full slab found\n");
 462       count++;
 463       total_elems += s->in_use();
 464     }
 465
 466   total += count;
 467
 468   printf ("%u used, ", count);
 469
 470   for (count = 0;
 471        s;
 472        s = s->next())
 473     {
 474       if (! s->is_empty())
 475         printf ("\n*** wrongly-enqueued nonempty slab found\n");
 476       count++;
 477       total_elems += s->in_use();
 478     }
 479
 480   unsigned total_used = total;
 481   total += count;
 482
 483   printf ("%u empty = %u total) = %lu KB,\n  %u elems (size=%u)",
 484           count, total, total * _slab_size / 1024,
 485           total_elems, _entry_size);
 486
 487   if (total_elems)
 488     printf (", overhead = %lu B (%lu B)  = %lu%% (%lu%%) \n",
 489             total * _slab_size - total_elems * _entry_size,
 490             total_used * _slab_size - total_elems * _entry_size,
 491             100 - total_elems * _entry_size * 100 / (total * _slab_size),
 492             100 - total_elems * _entry_size * 100 / (total_used * _slab_size));
 493   else
 494     printf ("\n");
 495 }