l4/pkg/cxx/lib/tl/include/slab_alloc

   1 // vi:ft=cpp
   2 /*
   3  * (c) 2008-2009 Technische Universität Dresden
   4  * This file is part of TUD:OS and distributed under the terms of the
   5  * GNU General Public License 2.
   6  * Please see the COPYING-GPL-2 file for details.
   7  *
   8  * As a special exception, you may use this file as part of a free software
   9  * library without restriction.  Specifically, if other files instantiate
  10  * templates or use macros or inline functions from this file, or you compile
  11  * this file and link it with other files to produce an executable, this
  12  * file does not by itself cause the resulting executable to be covered by
  13  * the GNU General Public License.  This exception does not however
  14  * invalidate any other reasons why the executable file might be covered by
  15  * the GNU General Public License.
  16  */
  17
  18 #pragma once
  19
  20 #include <l4/cxx/std_alloc>
  21 #include <l4/cxx/list>
  22 #include <l4/sys/consts.h>
  23
  24 namespace cxx {
  25
  26 /**
  27  * \ingroup cxx_api
  28  * \brief Basic slab allocator.
  29  * \param Obj_size  The size of the objects managed by the allocator (in bytes).
  30  * \param Slab_size The size of a slab cache (in bytes).
  31  * \param Max_free  The maximum number of free slab caches. When this limit is
  32  *                  reached slab caches are freed.
  33  * \param Alloc     The allocator that is used to allocate the slab caches.
  34  */
  35 template< int Obj_size, int Slab_size = L4_PAGESIZE,
  36   int Max_free = 2, template<typename A> class Alloc = New_allocator >
  37 class Base_slab
  38 {
  39 private:
  40   struct Free_o
  41   {
  42     Free_o *next;
  43   };
  44
  45 protected:
  46   struct Slab_i;
  47
  48 private:
  49   struct Slab_head : public List_item
  50   {
  51     unsigned num_free;
  52     Free_o *free;
  53     Base_slab<Obj_size, Slab_size, Max_free, Alloc> *cache;
  54
  55     inline Slab_head() throw() : num_free(0), free(0), cache(0)
  56     {}
  57   };
  58
  59 public:
  60   enum
  61   {
  62     object_size      = Obj_size,   ///< size of an object.
  63     slab_size        = Slab_size,  ///< size of a slab cache.
  64     /// objects per slab cache.
  65     objects_per_slab = (Slab_size - sizeof(Slab_head)) / object_size,
  66     /// maximum number of free slab caches.
  67     max_free_slabs   = Max_free,
  68   };
  69
  70 protected:
  71   struct Slab_store
  72   {
  73     char _o[slab_size - sizeof(Slab_head)];
  74     Free_o *object(unsigned obj) throw()
  75     { return reinterpret_cast<Free_o*>(_o + object_size * obj); }
  76   };
  77
  78   struct Slab_i : public Slab_store, public Slab_head
  79   {};
  80
  81 public:
  82   /// Type of the allocator for the slab caches.
  83   typedef Alloc<Slab_i> Slab_alloc;
  84
  85   typedef void Obj_type;
  86
  87 private:
  88   Slab_alloc _alloc;
  89   unsigned _num_free;
  90   unsigned _num_slabs;
  91   Slab_i *_full_slabs;
  92   Slab_i *_partial_slabs;
  93   Slab_i *_empty_slabs;
  94
  95   /// Add a new slab cache.
  96   void add_slab(Slab_i *s) throw()
  97   {
  98     s->num_free = objects_per_slab;
  99     s->cache = this;
 100
 101     //L4::cerr << "Slab: " << this << "->add_slab(" << s << ", size="
 102     //  << slab_size << "):" << " f=" << s->object(0) << '\n';
 103
 104     // initialize free list
 105     Free_o *f = s->free = s->object(0);
 106     for (unsigned i = 0; i < objects_per_slab; ++i)
 107       {
 108         f->next = s->object(i);
 109         f = f->next;
 110       }
 111     f->next = 0;
 112
 113     // insert slab into cache's list
 114     _empty_slabs = List_item::push_front(_empty_slabs, s);
 115     ++_num_slabs;
 116     ++_num_free;
 117   }
 118
 119   /// Grow the allocator, by adding a new slab cache.
 120   bool grow() throw()
 121   {
 122     Slab_i *s = _alloc.alloc();
 123     if (!s)
 124       return false;
 125
 126     new (s, cxx::Nothrow()) Slab_i();
 127
 128     add_slab(s);
 129     return true;
 130   }
 131
 132   /// Shrink the allocator by freeing free slab caches.
 133   void shrink() throw()
 134   {
 135     if (!_alloc.can_free)
 136       return;
 137
 138     while (_empty_slabs && _num_free > max_free_slabs)
 139       {
 140         Slab_i *s = _empty_slabs;
 141         _empty_slabs = List_item::remove(_empty_slabs, s);
 142         --_num_free;
 143         --_num_slabs;
 144         _alloc.free(s);
 145       }
 146   }
 147
 148 public:
 149   Base_slab(Slab_alloc const &alloc = Slab_alloc()) throw()
 150     : _alloc(alloc), _num_free(0), _num_slabs(0), _full_slabs(0),
 151       _partial_slabs(0), _empty_slabs(0)
 152   {}
 153
 154   ~Base_slab() throw()
 155   {
 156     while (_empty_slabs)
 157       {
 158         Slab_i *o = _empty_slabs;
 159         _empty_slabs = List_item::remove(_empty_slabs, o);
 160         _alloc.free(o);
 161       }
 162     while (_partial_slabs)
 163       {
 164         Slab_i *o = _partial_slabs;
 165         _partial_slabs = List_item::remove(_partial_slabs, o);
 166         _alloc.free(o);
 167       }
 168     while (_full_slabs)
 169       {
 170         Slab_i *o = _full_slabs;
 171         _full_slabs = List_item::remove(_full_slabs, o);
 172         _alloc.free(o);
 173       }
 174   }
 175
 176   void *alloc() throw()
 177   {
 178     Slab_i **free = &_partial_slabs;
 179     if (!(*free))
 180       free = &_empty_slabs;
 181
 182     if (!(*free) && !grow())
 183       return 0;
 184
 185     Slab_i *s = *free;
 186     Free_o *o = s->free;
 187     s->free = o->next;
 188
 189     if (free == &_empty_slabs)
 190       {
 191         _empty_slabs = List_item::remove(_empty_slabs, s);
 192         --_num_free;
 193       }
 194
 195     --(s->num_free);
 196
 197     if (!s->free)
 198       {
 199         _partial_slabs = List_item::remove(_partial_slabs, s);
 200         _full_slabs = List_item::push_front(_full_slabs, s);
 201       }
 202     else if (free == &_empty_slabs)
 203       _partial_slabs = List_item::push_front(_partial_slabs, s);
 204
 205     //L4::cerr << this << "->alloc(): " << o << ", of " << s << '\n';
 206
 207     return o;
 208   }
 209
 210   void free(void *_o) throw()
 211   {
 212     if (!_o)
 213       return;
 214
 215     unsigned long addr = (unsigned long)_o;
 216     addr = (addr / slab_size) * slab_size;
 217     Slab_i *s = (Slab_i*)addr;
 218
 219     if (s->cache != this)
 220       return;
 221
 222     Free_o *o = reinterpret_cast<Free_o*>(_o);
 223
 224     o->next = s->free;
 225     s->free = o;
 226
 227     bool was_full = false;
 228
 229     if (!s->num_free)
 230       {
 231         _full_slabs = List_item::remove(_full_slabs, s);
 232         was_full = true;
 233       }
 234
 235     ++(s->num_free);
 236
 237     if (s->num_free == objects_per_slab)
 238       {
 239         if (!was_full)
 240           _partial_slabs = List_item::remove(_partial_slabs, s);
 241
 242         _empty_slabs = List_item::push_front(_empty_slabs, s);
 243         ++_num_free;
 244         if (_num_free > max_free_slabs)
 245           shrink();
 246
 247         was_full = false;
 248       }
 249
 250     if (was_full)
 251       _partial_slabs = List_item::push_front(_partial_slabs, s);
 252
 253     //L4::cerr << this << "->free(" << _o << "): of " << s << '\n';
 254   }
 255
 256   /**
 257    * \brief Get the total number of objects managed by the slab allocator.
 258    * \return The number of objects managed by the allocator (including the
 259    *         free objects).
 260    */
 261   unsigned total_objects() const throw()
 262   { return _num_slabs * objects_per_slab; }
 263
 264   /**
 265    * \brief Get the total number of objects managed by the slab allocator.
 266    * \return The number of objects managed by the allocator (including the
 267    *         free objects).
 268    */
 269   unsigned free_objects() const throw()
 270   {
 271     unsigned count = 0;
 272
 273     /* count partial slabs first */
 274     List_item::T_iter<Slab_i> s = _partial_slabs;
 275     while (*s)
 276       {
 277         count += s->num_free;
 278         s++;
 279       }
 280
 281     /* add empty slabs */
 282     count += _num_free * objects_per_slab;
 283
 284     return count;
 285   }
 286 };
 287
 288 /**
 289  * \ingroup cxx_api
 290  * \brief Slab allocator for object of type \a Type.
 291  * \param Type the type of the objects to manage.
 292  * \param Slab_size size of a slab cache.
 293  * \param Max_free the maximum number of free slab caches.
 294  * \param Alloc the allocator for the slab caches.
 295  */
 296 template<typename Type, int Slab_size = L4_PAGESIZE,
 297   int Max_free = 2, template<typename A> class Alloc = New_allocator >
 298 class Slab : public Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>
 299 {
 300 private:
 301   typedef Base_slab<sizeof(Type), Slab_size, Max_free, Alloc> Base_type;
 302 public:
 303
 304   typedef Type Obj_type;
 305
 306   Slab(typename Base_type::Slab_alloc const &alloc
 307       = typename Base_type::Slab_alloc()) throw()
 308     : Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>(alloc) {}
 309
 310
 311   /**
 312    * \brief Allocate an object of type \a Type.
 313    * \return A pointer to the object just allocated, or 0 on failure.
 314    */
 315   Type *alloc() throw()
 316   {
 317     return (Type*)Base_slab<sizeof(Type), Slab_size,
 318       Max_free, Alloc>::alloc();
 319   }
 320
 321   /**
 322    * \brief Free the object addressed by \a o.
 323    * \param o The pointer to the object to free.
 324    * \pre The object must have been allocated with this allocator.
 325    */
 326   void free(Type *o) throw()
 327   { Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>::free(o); }
 328 };
 329
 330
 331 /**
 332  * \ingroup cxx_api
 333  * \brief Merged slab allocator (allocators for objects of the same size
 334  *        are merged together).
 335  *
 336  * \param Obj_size   The size of an object managed by the slab allocator.
 337  * \param Slab_size  The size of a slab cache.
 338  * \param Max_free   The maximum number of free slab caches.
 339  * \param Alloc      The allocator for the slab caches.
 340  *
 341  * This slab allocator class is useful for merging slab allocators with the
 342  * same parameters (equal \a Obj_size, \a Slab_size, \a Max_free, and
 343  * \a Alloc parameters) together and share the overhead for the slab caches
 344  * among all equal-sized objects.
 345  *
 346  */
 347 template< int Obj_size, int Slab_size = L4_PAGESIZE,
 348   int Max_free = 2, template<typename A> class Alloc = New_allocator >
 349 class Base_slab_static
 350 {
 351 private:
 352   typedef Base_slab<Obj_size, Slab_size, Max_free, Alloc> _A;
 353   static _A _a;
 354 public:
 355   typedef void Obj_type;
 356   enum
 357   {
 358     object_size      = Obj_size,  ///< size of an object.
 359     slab_size        = Slab_size, ///< size of a slab cache.
 360     /// number of objects per slab cache.
 361     objects_per_slab = _A::objects_per_slab,
 362     max_free_slabs   = Max_free,  ///< maximum number of free slab caches.
 363   };
 364
 365   /** \brief Allocate an object. */
 366   void *alloc() throw() { return _a.alloc(); }
 367   /**
 368    * \brief Free the given object (\a p).
 369    * \param p  The pointer to the object to free.
 370    * \pre \a p must be a pointer to an object allocated by this allocator.
 371    */
 372   void free(void *p) throw() { _a.free(p); }
 373
 374   /**
 375    * \brief Get the total number of objects managed by the slab allocator.
 376    * \return The number of objects managed by the allocator (including the
 377    *         free objects).
 378    * \note The value is the merged value for all equal parameterized
 379    *       Base_slab_static instances.
 380    */
 381   unsigned total_objects() const throw() { return _a.total_objects(); }
 382
 383   /**
 384    * \brief Get the number of free objects in the slab allocator.
 385    * \return The number of free objects in all free and partially used
 386    *         slab caches managed by this allocator.
 387    * \note The value is the merged value for all equal parameterized
 388    *       Base_slab_static instances.
 389    */
 390   unsigned free_objects() const throw() { return _a.free_objects(); }
 391 };
 392
 393
 394 template< int _O, int _S, int _M, template<typename A> class Alloc >
 395 typename Base_slab_static<_O,_S,_M,Alloc>::_A
 396   Base_slab_static<_O,_S,_M,Alloc>::_a;
 397
 398 /**
 399  * \ingroup cxx_api
 400  * \brief Merged slab allocator (allocators for objects of the same size
 401  *        are merged together).
 402  *
 403  * \param Type       The type of the objects to manage.
 404  * \param Slab_size  The size of a slab cache.
 405  * \param Max_free   The maximum number of free slab caches.
 406  * \param Alloc      The allocator for the slab caches.
 407  *
 408  * This slab allocator class is useful for merging slab allocators with the
 409  * same parameters (equal \a sizeof(Type), \a Slab_size, \a Max_free, and
 410  * \a Alloc parameters) together and share the overhead for the slab caches
 411  * among all equal-sized objects.
 412  *
 413  */
 414 template<typename Type, int Slab_size = L4_PAGESIZE,
 415   int Max_free = 2, template<typename A> class Alloc = New_allocator >
 416 class Slab_static
 417 : public Base_slab_static<sizeof(Type), Slab_size, Max_free, Alloc>
 418 {
 419 public:
 420
 421   typedef Type Obj_type;
 422   /**
 423    * \brief Allocate an object of type \a Type.
 424    * \return A pointer to the just allocated object, or 0 of failure.
 425    */
 426   Type *alloc() throw()
 427   {
 428     return (Type*)Base_slab_static<sizeof(Type), Slab_size,
 429       Max_free, Alloc>::alloc();
 430   }
 431 };
 432
 433 }