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
30namespace L4Re { namespace Util {
31
32/**
33 * Counter for Counting_cap_alloc with variable data width
34 */
35template< typename COUNTER = unsigned char >
36struct 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 */
74template <typename COUNTERTYPE = L4Re::Util::Counter<unsigned char> >
75class Counting_cap_alloc
76{
77private:
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
87public:
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
97protected:
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() noexcept
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) noexcept
122  {
123    _items = (Counter*)m;
124    _capacity = capacity;
125    _bias = bias;
126  }
127
128public:
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() noexcept
136  {
137    for (long i = _free_hint; i < _capacity; ++i)
138      {
139	if (_items[i].is_free())
140	  {
141	    _items[i].alloc();
142	    _free_hint = i + 1;
143
144	    return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
145	  }
146      }
147
148    return L4::Cap<void>::Invalid;
149  }
150
151  /// \copydoc alloc()
152  template <typename T>
153  L4::Cap<T> alloc() noexcept
154  {
155    return L4::cap_cast<T>(alloc());
156  }
157
158
159  /**
160   * Increase the reference counter for the capability.
161   *
162   * \param cap Capability, whose reference counter should be increased.
163   *
164   * If the capability was still free, it will be automatically allocated.
165   * Silently does nothing if the capability is not
166   * managed by this allocator.
167   */
168  void take(L4::Cap<void> cap) noexcept
169  {
170    long c = cap.cap() >> L4_CAP_SHIFT;
171    if (c < _bias)
172      return;
173
174    c -= _bias;
175    if (c >= _capacity)
176      return;
177
178    _items[c].inc();
179  }
180
181
182  /**
183   * Free the capability.
184   *
185   * \param cap  Capability to free.
186   * \param task If set, task to unmap the capability from.
187   * \param unmap_flags  Flags for unmap, see l4_unmap_flags_t.
188   *
189   * \pre The capability has been allocated. Calling free twice on a
190   *      capability managed by this allocator results in undefined
191   *      behaviour.
192   *
193   * \return True, if the capability was managed by this allocator.
194   */
195  bool free(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
196            unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
197  {
198    long c = cap.cap() >> L4_CAP_SHIFT;
199    if (c < _bias)
200      return false;
201
202    c -= _bias;
203
204    if (c >= _capacity)
205      return false;
206
207    l4_assert(!_items[c].is_free());
208
209    if (l4_is_valid_cap(task))
210      l4_task_unmap(task, cap.fpage(), unmap_flags);
211
212    if (c < _free_hint)
213      _free_hint = c;
214
215    _items[c].free();
216
217    return true;
218  }
219
220  /**
221   * Decrease the reference counter for a capability.
222   *
223   * \param cap  Capability to release.
224   * \param task If set, task to unmap the capability from.
225   * \param unmap_flags  Flags for unmap, see l4_unmap_flags_t.
226   *
227   * \pre The capability has been allocated. Calling release on a free
228   *      capability results in undefined behaviour.
229   *
230   * \return True, if the capability was freed as a result of
231   *         this operation. If false is returned the capability
232   *         is either still in use or is not managed by this
233   *         allocator.
234   *
235   * Does nothing apart from returning false if the capability is not
236   * managed by this allocator.
237   */
238  bool release(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
239               unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
240  {
241    long c = cap.cap() >> L4_CAP_SHIFT;
242    if (c < _bias)
243      return false;
244
245    c -= _bias;
246
247    if (c >= _capacity)
248      return false;
249
250    l4_assert(!_items[c].is_free());
251
252    if (_items[c].dec() == Counter::nil())
253      {
254	if (task != L4_INVALID_CAP)
255	  l4_task_unmap(task, cap.fpage(), unmap_flags);
256
257	if (c < _free_hint)
258	  _free_hint = c;
259
260	return true;
261      }
262    return false;
263  }
264
265
266  /**
267   * Return highest capability id managed by this allocator.
268   */
269  long last() noexcept
270  {
271    return _capacity + _bias - 1;
272  }
273};
274
275}}
276
277