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

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