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