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   void *unused_block = 0;
 256   void *ret;
 257     {
 258       Lock_guard<Lock> guard(&lock);
 259
 260       if (EXPECT_FALSE(!_first_available_slab))
 261         {
 262           guard.release();
 263
 264           char *m = (char*)block_alloc(_slab_size, _slab_size);
 265           if (!m)
 266             return 0;
 267
 268           slab *s = new (m + _slab_size - sizeof(slab)) slab(this, m);
 269
 270           guard.lock(&lock);
 271
 272           if (EXPECT_TRUE(!_first_available_slab))
 273             {
 274               _first_available_slab = s;
 275
 276               if (_last_slab)
 277                 {
 278                   assert(_last_slab->is_full());
 279
 280                   _first_available_slab->enqueue(_last_slab);
 281                   _last_slab = _first_available_slab;
 282                 }
 283               else                      // this was the first slab we allocated
 284                 _first_slab = _last_slab = _first_available_slab;
 285             }
 286           else
 287             unused_block = m;
 288         }
 289
 290       assert(_first_available_slab && ! _first_available_slab->is_full());
 291       assert(! _first_available_slab->prev() || _first_available_slab->prev()->is_full());
 292
 293       ret = _first_available_slab->alloc();
 294       assert(ret);
 295
 296       if (_first_available_slab->is_full())
 297         _first_available_slab = _first_available_slab->next();
 298     }
 299
 300   if (unused_block)
 301     block_free(unused_block, _slab_size);
 302
 303   return ret;
 304 }
 305
 306 PUBLIC template< typename Q >
 307 inline
 308 void *
 309 slab_cache_anon::q_alloc(Q *quota)
 310 {
 311   if (EXPECT_FALSE(!quota->alloc(_entry_size)))
 312     return 0;
 313
 314   void *r;
 315   if (EXPECT_FALSE(!(r=alloc())))
 316     {
 317       quota->free(_entry_size);
 318       return 0;
 319     }
 320
 321   return r;
 322 }
 323
 324 PUBLIC
 325 virtual void
 326 slab_cache_anon::free(void *cache_entry) // return initialized member to cache
 327 {
 328   Lock_guard<Lock> guard(&lock);
 329
 330   slab *s = reinterpret_cast<slab*>
 331     ((reinterpret_cast<unsigned long>(cache_entry) & ~(_slab_size - 1)) + _slab_size - sizeof(slab));
 332
 333   bool was_full = s->is_full();
 334
 335   s->free(cache_entry);
 336
 337   if (was_full)
 338     {
 339       if (s->next() == 0)       // have no right neighbor?
 340         {
 341           assert(! _first_available_slab);
 342         }
 343       else if (s->next()->is_full()) // right neigbor full?
 344         {
 345           // We requeue to become the first non-full slab in the queue
 346           // so that all full slabs are at the beginning of the queue.
 347
 348           if (s == _first_slab)
 349             _first_slab = s->next();
 350           // don't care about _first_available_slab, _last_slab --
 351           // they cannot point to s because we were full and have a
 352           // right neighbor
 353
 354           s->dequeue();
 355
 356           if (_first_available_slab)
 357             {
 358               // _first_available_slab->prev() is defined because we
 359               // had a right neighbor which is full, that is,
 360               // _first_available_slab wasn't our right neighbor and
 361               // now isn't the first slab in the queue
 362               assert(_first_available_slab->prev()->is_full());
 363               s->enqueue(_first_available_slab->prev());
 364             }
 365           else
 366             {
 367               // all slabs were full
 368               assert(_last_slab->is_full());
 369               s->enqueue(_last_slab);
 370               _last_slab = s;
 371             }
 372         }
 373
 374       _first_available_slab = s;
 375
 376     }
 377   else if (s->is_empty())
 378     {
 379       if (s->next() && (! s->next()->is_empty())) // right neighbor not empty?
 380         {
 381           // Move to tail of list
 382
 383           if (s == _first_slab)
 384             _first_slab = s->next();
 385           if (s == _first_available_slab)
 386             _first_available_slab = s->next();
 387           // don't care about _last_slab because we know we have a
 388           // right neighbor
 389
 390           s->dequeue();
 391
 392           s->enqueue(_last_slab);
 393           _last_slab = s;
 394         }
 395     }
 396   else
 397     {
 398       // We weren't either full or empty; we already had free
 399       // elements.  This changes nothing in the queue, and there
 400       // already must have been a _first_available_slab.
 401     }
 402
 403   assert(_first_available_slab);
 404 }
 405
 406 PUBLIC template< typename Q >
 407 inline
 408 void
 409 slab_cache_anon::q_free(Q *quota, void *obj)
 410 {
 411   free(obj);
 412   quota->free(_entry_size);
 413 }
 414
 415 PUBLIC
 416 virtual unsigned long
 417 slab_cache_anon::reap()         // request that cache returns memory to system
 418 {
 419   Lock_guard<Lock> guard(&lock);
 420
 421   if (! _first_slab)
 422     return 0;                   // haven't allocated anything yet
 423
 424   // never delete first slab, even if it is empty
 425   if (_last_slab == _first_slab
 426       || (! _last_slab->is_empty()))
 427     return 0;
 428
 429   slab *s = _last_slab;
 430
 431   if (_first_available_slab == s)
 432     _first_available_slab = 0;
 433
 434   _last_slab = s->prev();
 435   s->dequeue();
 436
 437   // explicitly call destructor to delete s;
 438   s->~slab();
 439   block_free(s, _slab_size);
 440
 441   return _slab_size;
 442 }
 443
 444 // Debugging output
 445
 446 #include <cstdio>
 447
 448 PUBLIC
 449 virtual void
 450 slab_cache_anon::debug_dump()
 451 {
 452   printf ("%s: %lu-KB slabs (elems per slab=%d ",
 453           _name, _slab_size / 1024, _elem_num);
 454
 455   unsigned count, total = 0, total_elems = 0;
 456   slab* s = _first_slab;
 457
 458   for (count = 0;
 459        s && s->is_full();
 460        s = s->next())
 461     {
 462       count++;
 463       total_elems += s->in_use();
 464     }
 465
 466   total += count;
 467
 468   printf ("%u full, ", count);
 469
 470   for (count = 0;
 471        s && ! s->is_empty();
 472        s = s->next())
 473     {
 474       if (s->is_full())
 475         printf ("\n*** wrongly-enqueued full slab found\n");
 476       count++;
 477       total_elems += s->in_use();
 478     }
 479
 480   total += count;
 481
 482   printf ("%u used, ", count);
 483
 484   for (count = 0;
 485        s;
 486        s = s->next())
 487     {
 488       if (! s->is_empty())
 489         printf ("\n*** wrongly-enqueued nonempty slab found\n");
 490       count++;
 491       total_elems += s->in_use();
 492     }
 493
 494   unsigned total_used = total;
 495   total += count;
 496
 497   printf ("%u empty = %u total) = %lu KB,\n  %u elems (size=%u)",
 498           count, total, total * _slab_size / 1024,
 499           total_elems, _entry_size);
 500
 501   if (total_elems)
 502     printf (", overhead = %lu B (%lu B)  = %lu%% (%lu%%) \n",
 503             total * _slab_size - total_elems * _entry_size,
 504             total_used * _slab_size - total_elems * _entry_size,
 505             100 - total_elems * _entry_size * 100 / (total * _slab_size),
 506             100 - total_elems * _entry_size * 100 / (total_used * _slab_size));
 507   else
 508     printf ("\n");
 509 }