l4/pkg/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 Technische Universität Dresden
   9  * This file is part of TUD:OS and distributed under the terms of the
  10  * GNU General Public License 2.
  11  * Please see the COPYING-GPL-2 file for details.
  12  *
  13  * As a special exception, you may use this file as part of a free software
  14  * library without restriction.  Specifically, if other files instantiate
  15  * templates or use macros or inline functions from this file, or you compile
  16  * this file and link it with other files to produce an executable, this
  17  * file does not by itself cause the resulting executable to be covered by
  18  * the GNU General Public License.  This exception does not however
  19  * invalidate any other reasons why the executable file might be covered by
  20  * the GNU General Public License.
  21  */
  22
  23 #pragma once
  24
  25 #include <l4/sys/task>
  26 #include <l4/re/consts>
  27
  28 namespace L4Re { namespace Util {
  29
  30 template< typename COUNTER = unsigned char >
  31 struct Counter
  32 {
  33   typedef COUNTER Type;
  34   Type _cnt;
  35
  36   static Type nil() { return 0; }
  37
  38   void free() { _cnt = 0; }
  39   bool is_free() const { return _cnt == 0; }
  40   void inc() { ++_cnt; }
  41   Type dec() { return --_cnt; }
  42   void alloc() { _cnt = 1; }
  43 };
  44
  45 /**
  46  * \brief Reference-counting cap allocator
  47  * \ingroup api_l4re_util
  48  */
  49 template <typename COUNTERTYPE = L4Re::Util::Counter<unsigned char> >
  50 class Counting_cap_alloc
  51 {
  52 private:
  53   void operator = (Counting_cap_alloc const &) { }
  54   typedef COUNTERTYPE Counter;
  55
  56   COUNTERTYPE *_items;
  57   long _free_hint;
  58   long _bias;
  59   long _capacity;
  60
  61
  62 public:
  63
  64   template <unsigned COUNT>
  65   struct Counter_storage
  66   {
  67     COUNTERTYPE _buf[COUNT];
  68     typedef COUNTERTYPE Buf_type[COUNT];
  69     enum { Size = COUNT };
  70   };
  71
  72 protected:
  73
  74   Counting_cap_alloc() throw()
  75   : _items(0), _free_hint(0), _bias(0), _capacity(0)
  76   {}
  77
  78   void setup(void *m, long capacity, long bias) throw()
  79   {
  80     _items = (Counter*)m;
  81     _capacity = capacity;
  82     _bias = bias;
  83   }
  84
  85 public:
  86   L4::Cap<void> alloc() throw()
  87   {
  88     if (_free_hint >= _capacity)
  89       return L4::Cap_base::Invalid;
  90
  91     for (long i = _free_hint; i < _capacity; ++i)
  92       {
  93         if (_items[i].is_free())
  94           {
  95             _items[i].alloc();
  96             _free_hint = i + 1;
  97
  98             return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
  99           }
 100       }
 101
 102     return L4::Cap<void>::Invalid;
 103   }
 104
 105   template <typename T>
 106   L4::Cap<T> alloc() throw()
 107   {
 108     return L4::cap_cast<T>(alloc());
 109   }
 110
 111
 112   void take(L4::Cap<void> cap) throw()
 113   {
 114     long c = cap.cap() >> L4_CAP_SHIFT;
 115     if (c < _bias)
 116       return;
 117
 118     c -= _bias;
 119     if (c >= _capacity)
 120       return;
 121
 122     _items[c].inc();
 123   }
 124
 125
 126   bool free(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
 127             unsigned unmap_flags = L4_FP_ALL_SPACES) throw()
 128   {
 129     long c = cap.cap() >> L4_CAP_SHIFT;
 130     if (c < _bias)
 131       return false;
 132
 133     c -= _bias;
 134
 135     if (c >= _capacity)
 136       return false;
 137
 138     if (task != L4_INVALID_CAP)
 139       l4_task_unmap(task, cap.fpage(), unmap_flags);
 140     _free_hint = c;
 141     _items[c].free();
 142
 143     return true;
 144   }
 145
 146   bool release(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
 147                unsigned unmap_flags = L4_FP_ALL_SPACES) throw()
 148   {
 149     long c = cap.cap() >> L4_CAP_SHIFT;
 150     if (c < _bias)
 151       return false;
 152
 153     c -= _bias;
 154
 155     if (c >= _capacity)
 156       return false;
 157
 158     if (_items[c].dec() == Counter::nil())
 159       {
 160         if (task != L4_INVALID_CAP)
 161           l4_task_unmap(task, cap.fpage(), unmap_flags);
 162         _free_hint = c;
 163         return true;
 164       }
 165     return false;
 166   }
 167
 168
 169   long last() throw()
 170   {
 171     return _capacity + _bias - 1;
 172   }
 173 };
 174
 175 }}
 176