l4/pkg/l4re-core/l4re/util/include/counting_cap_alloc

   1 // -*- Mode: C++ -*-
   2 // vim:ft=cpp
   3 /**
   4  * \file
   5  * \brief  Reference-counting capability allocator
   6  */
   7 /*
   8  * (c) 2008-2010 Alexander Warg <warg@os.inf.tu-dresden.de>
   9  *     economic rights: Technische Universität Dresden (Germany)
  10  *
  11  * This file is part of TUD:OS and distributed under the terms of the
  12  * GNU General Public License 2.
  13  * Please see the COPYING-GPL-2 file for details.
  14  *
  15  * As a special exception, you may use this file as part of a free software
  16  * library without restriction.  Specifically, if other files instantiate
  17  * templates or use macros or inline functions from this file, or you compile
  18  * this file and link it with other files to produce an executable, this
  19  * file does not by itself cause the resulting executable to be covered by
  20  * the GNU General Public License.  This exception does not however
  21  * invalidate any other reasons why the executable file might be covered by
  22  * the GNU General Public License.
  23  */
  24
  25 #pragma once
  26
  27 #include <l4/sys/task>
  28 #include <l4/sys/assert.h>
  29 #include <l4/re/consts>
  30
  31 namespace L4Re { namespace Util {
  32
  33 template< typename COUNTER = unsigned char >
  34 struct Counter
  35 {
  36   typedef COUNTER Type;
  37   Type _cnt;
  38
  39   static Type nil() { return 0; }
  40
  41   void free() { _cnt = 0; }
  42   bool is_free() const { return _cnt == 0; }
  43   void inc() { ++_cnt; }
  44   Type dec() { return --_cnt; }
  45   void alloc() { _cnt = 1; }
  46 };
  47
  48 /**
  49  * \brief Reference-counting cap allocator
  50  *
  51  * \note The operations in this class are not thread-safe.
  52  *
  53  * \ingroup api_l4re_util
  54  */
  55 template <typename COUNTERTYPE = L4Re::Util::Counter<unsigned char> >
  56 class Counting_cap_alloc
  57 {
  58 private:
  59   void operator = (Counting_cap_alloc const &) { }
  60   typedef COUNTERTYPE Counter;
  61
  62   COUNTERTYPE *_items;
  63   long _free_hint;
  64   long _bias;
  65   long _capacity;
  66
  67
  68 public:
  69
  70   template <unsigned COUNT>
  71   struct Counter_storage
  72   {
  73     COUNTERTYPE _buf[COUNT];
  74     typedef COUNTERTYPE Buf_type[COUNT];
  75     enum { Size = COUNT };
  76   };
  77
  78 protected:
  79
  80   /**
  81    * Create a new, empty allocator.
  82    *
  83    * Needs to be initialized with setup() before it can be used.
  84    */
  85   Counting_cap_alloc() throw()
  86   : _items(0), _free_hint(0), _bias(0), _capacity(0)
  87   {}
  88
  89   /**
  90    * Set up the backing memory for the allocator.
  91    *
  92    * \param m        Pointer to backing memory.
  93    * \param capacity Number of capabilities that can be stored.
  94    * \param bias     First capability id to use by this allocator.
  95    */
  96   void setup(void *m, long capacity, long bias) throw()
  97   {
  98     _items = (Counter*)m;
  99     _capacity = capacity;
 100     _bias = bias;
 101   }
 102
 103 public:
 104   /**
 105    * Allocated a new capability.
 106    *
 107    * \return The newly allocated capability, invalid if the allocator
 108    *         was exhausted.
 109    */
 110   L4::Cap<void> alloc() throw()
 111   {
 112     if (_free_hint >= _capacity)
 113       return L4::Cap_base::Invalid;
 114
 115     for (long i = _free_hint; i < _capacity; ++i)
 116       {
 117         if (_items[i].is_free())
 118           {
 119             _items[i].alloc();
 120             _free_hint = i + 1;
 121
 122             return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
 123           }
 124       }
 125
 126     return L4::Cap<void>::Invalid;
 127   }
 128
 129   /// \copydoc alloc()
 130   template <typename T>
 131   L4::Cap<T> alloc() throw()
 132   {
 133     return L4::cap_cast<T>(alloc());
 134   }
 135
 136
 137   /**
 138    * Increase the reference counter for the capability.
 139    *
 140    * \param cap Capability, whose reference counter should be increased.
 141    *
 142    * If the capability was still free, it will be automatically allocated.
 143    * Silently does nothing if the capability is not
 144    * managed by this allocator.
 145    */
 146   void take(L4::Cap<void> cap) throw()
 147   {
 148     long c = cap.cap() >> L4_CAP_SHIFT;
 149     if (c < _bias)
 150       return;
 151
 152     c -= _bias;
 153     if (c >= _capacity)
 154       return;
 155
 156     _items[c].inc();
 157   }
 158
 159
 160   /**
 161    * Free the capability.
 162    *
 163    * \param cap  Capability to free.
 164    * \param task If set, task to unmap the capability from.
 165    * \param unmap_flags  Flags for unmap, see l4_unmap_flags_t.
 166    *
 167    * \pre The capability has been allocated. Calling free twice results
 168    *      in undefined behaviour.
 169    *
 170    * \return True, if the capability was managed by this allocator.
 171    */
 172   bool free(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
 173             unsigned unmap_flags = L4_FP_ALL_SPACES) throw()
 174   {
 175     long c = cap.cap() >> L4_CAP_SHIFT;
 176     if (c < _bias)
 177       return false;
 178
 179     c -= _bias;
 180
 181     if (c >= _capacity)
 182       return false;
 183
 184     l4_assert(!_items[c].is_free());
 185
 186     if (task != L4_INVALID_CAP)
 187       l4_task_unmap(task, cap.fpage(), unmap_flags);
 188
 189     if (c < _free_hint)
 190       _free_hint = c;
 191
 192     _items[c].free();
 193
 194     return true;
 195   }
 196
 197   /**
 198    * Decrease the reference counter for a capability.
 199    *
 200    * \param cap  Capability to release.
 201    * \param task If set, task to unmap the capability from.
 202    * \param unmap_flags  Flags for unmap, see l4_unmap_flags_t.
 203    *
 204    * \pre The capability has been allocated. Calling release on a free
 205    *      capability results in undefined behaviour.
 206    *
 207    * \return True, if the capability was freed as a result of
 208    *         this operation. If false is returned the capability
 209    *         is either still in use or was already free or invalid.
 210    */
 211   bool release(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
 212                unsigned unmap_flags = L4_FP_ALL_SPACES) throw()
 213   {
 214     long c = cap.cap() >> L4_CAP_SHIFT;
 215     if (c < _bias)
 216       return false;
 217
 218     c -= _bias;
 219
 220     if (c >= _capacity)
 221       return false;
 222
 223     l4_assert(!_items[c].is_free());
 224
 225     if (_items[c].dec() == Counter::nil())
 226       {
 227         if (task != L4_INVALID_CAP)
 228           l4_task_unmap(task, cap.fpage(), unmap_flags);
 229
 230         if (c < _free_hint)
 231           _free_hint = c;
 232
 233         return true;
 234       }
 235     return false;
 236   }
 237
 238
 239   /**
 240    * Return highest capability id managed by this allocator.
 241    */
 242   long last() throw()
 243   {
 244     return _capacity + _bias - 1;
 245   }
 246 };
 247
 248 }}
 249