L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
counting_cap_alloc
Go to the documentation of this file.
1// vim:set ft=cpp: -*- Mode: C++ -*-
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
37template< typename COUNTER = unsigned char >
38struct Counter
39{
40 typedef COUNTER Type;
41 Type _cnt;
42
43 static Type nil() { return 0; }
44 static Type unused() { return 0; }
45
46 void free() { _cnt = 0; }
47 bool is_free() const { return _cnt == 0; }
48 bool is_saturated() const { return static_cast<Type>(_cnt + 1) == 0; }
49
61 bool inc()
62 {
63 if (is_saturated())
64 return true; // no change and no warning
65 ++_cnt;
66 if (is_saturated())
67 return false; // warn caller that counter is now saturated
68 else
69 return true; // success
70 }
71
78 Type dec()
79 {
80 if (is_saturated())
81 return _cnt; // no change
82 else
83 return --_cnt; // success
84 }
85
86 bool try_alloc()
87 {
88 if (_cnt == 0)
89 {
90 _cnt = 1;
91 return true;
92 }
93 return false;
94 }
95};
96
108template< typename COUNTER = unsigned char >
110{
111 typedef COUNTER Type;
112 Type _cnt;
113
114 static Type nil() { return 0; }
115 static Type unused() { return 1; }
116
117 bool is_free() const { return __atomic_load_n(&_cnt, __ATOMIC_RELAXED) == 0; }
118 static bool is_saturated(Type cnt) { return static_cast<Type>(cnt + 1) == 0; }
119
120 bool try_alloc()
121 {
122 Type expected = nil();
123 // Use "acquire" memory ordering. Any operations tied to the capability slot
124 // must only be observable after the slot has been occupied.
125 return __atomic_compare_exchange_n(&_cnt, &expected, 2, false,
126 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
127 }
128
132 bool inc()
133 {
134 Type old_cnt = __atomic_load_n(&_cnt, __ATOMIC_RELAXED);
135 Type new_cnt;
136 do
137 {
138 if (is_saturated(old_cnt))
139 return true; // no change and no warning
140 new_cnt = old_cnt + 1;
141 }
142 while (!__atomic_compare_exchange_n(&_cnt, &old_cnt, new_cnt, false,
143 __ATOMIC_RELAXED, __ATOMIC_RELAXED));
144 if (is_saturated(new_cnt))
145 return false; // warn caller that counter is now saturated
146 else
147 return true; // success
148 }
149
153 Type dec()
154 {
155 Type old_cnt = __atomic_load_n(&_cnt, __ATOMIC_RELAXED);
156 Type new_cnt;
157 do
158 {
159 if (is_saturated(old_cnt))
160 return old_cnt; // no change
161 new_cnt = old_cnt - 1;
162 }
163 while (!__atomic_compare_exchange_n(&_cnt, &old_cnt, new_cnt, false,
164 __ATOMIC_RELAXED, __ATOMIC_RELAXED));
165 return new_cnt; // success
166 }
167
168 void free()
169 {
170 // Use "release" memory ordering to make sure that any operations tied to
171 // the capability slot are observable by other threads before the slot can
172 // be reused.
173 __atomic_store_n(&_cnt, 0, __ATOMIC_RELEASE);
174 }
175};
176
201template <typename COUNTERTYPE, typename Dbg>
203{
204private:
205 void operator = (Counting_cap_alloc const &) { }
206 typedef COUNTERTYPE Counter;
207
208 COUNTERTYPE *_items;
209 long _free_hint;
210 long _bias;
211 long _capacity;
212 Dbg *_dbg;
213
214public:
215
216 template <unsigned COUNT>
217 struct Storage
218 {
219 COUNTERTYPE _buf[COUNT];
220 typedef COUNTERTYPE Buf_type[COUNT];
221 enum { Size = COUNT };
222 };
223
224protected:
225
232 : _items(0), _free_hint(0), _bias(0), _capacity(0)
233 {}
234
235 Counting_cap_alloc(long capacity, void *m, long bias, Dbg *dbg) noexcept
236 : _items((Counter*)m), _free_hint(0), _bias(bias), _capacity(capacity),
237 _dbg(dbg)
238 {}
239
254 void setup(void *m, long capacity, long bias, Dbg *dbg) noexcept
255 {
256 _items = static_cast<Counter*>(m);
257 _capacity = capacity;
258 _bias = bias;
259 _dbg = dbg;
260 }
261
262public:
270 {
271 long free_hint = __atomic_load_n(&_free_hint, __ATOMIC_RELAXED);
272
273 for (long i = free_hint; i < _capacity; ++i)
274 if (_items[i].try_alloc())
275 {
276 _free_hint = i + 1;
277 return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
278 }
279
280 // _free_hint is not necessarily correct in case of multi-threading! Make
281 // sure we don't miss any potentially free slots.
282 for (long i = 0; i < free_hint && i < _capacity; ++i)
283 if (_items[i].try_alloc())
284 {
285 _free_hint = i + 1;
286 return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
287 }
288
290 }
291
293 template <typename T>
294 L4::Cap<T> alloc() noexcept
295 {
296 return L4::cap_cast<T>(alloc());
297 }
298
299
308 void take(L4::Cap<void> cap) noexcept
309 {
310 long c;
311 if (!range_check_and_get_idx(cap, &c))
312 return;
313
314 if (!L4_UNLIKELY(_items[c].inc()))
315 _dbg->printf("Warning: Reference counter of cap 0x%lx now saturated!\n",
316 cap.cap() >> L4_CAP_SHIFT);
317 }
318
319
334 unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
335 {
336 long c;
337 if (!range_check_and_get_idx(cap, &c))
338 return false;
339
340 l4_assert(!_items[c].is_free());
341
342 if (l4_is_valid_cap(task))
343 l4_task_unmap(task, cap.fpage(), unmap_flags);
344
345 if (c < _free_hint)
346 _free_hint = c;
347
348 _items[c].free();
349
350 return true;
351 }
352
372 unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
373 {
374 long c;
375 if (!range_check_and_get_idx(cap, &c))
376 return false;
377
378 l4_assert(!_items[c].is_free());
379
380 if (_items[c].dec() == Counter::unused())
381 {
382 if (task != L4_INVALID_CAP)
383 l4_task_unmap(task, cap.fpage(), unmap_flags);
384
385 if (c < _free_hint)
386 _free_hint = c;
387
388 // Let others allocate this slot only after the l4_task_unmap() has
389 // finished.
390 _items[c].free();
391
392 return true;
393 }
394 return false;
395 }
396
400 long last() noexcept
401 {
402 return _capacity + _bias - 1;
403 }
404
405private:
406 bool range_check_and_get_idx(L4::Cap<void> cap, long *c)
407 {
408 *c = cap.cap() >> L4_CAP_SHIFT;
409 if (*c < _bias)
410 return false;
411
412 *c -= _bias;
413
414 return *c < _capacity;
415 }
416};
417
418}}
Internal reference-counting cap allocator.
bool release(L4::Cap< void > cap, l4_cap_idx_t task=L4_INVALID_CAP, unsigned unmap_flags=L4_FP_ALL_SPACES) noexcept
Decrease the reference counter for a capability.
void setup(void *m, long capacity, long bias, Dbg *dbg) noexcept
Set up the backing memory for the allocator and the area of managed capability slots.
long last() noexcept
Return highest capability id managed by this allocator.
bool free(L4::Cap< void > cap, l4_cap_idx_t task=L4_INVALID_CAP, unsigned unmap_flags=L4_FP_ALL_SPACES) noexcept
Free the capability.
void take(L4::Cap< void > cap) noexcept
Increase the reference counter for the capability.
L4::Cap< void > alloc() noexcept
Allocate a new capability slot.
L4::Cap< T > alloc() noexcept
Allocate a new capability slot.
Counting_cap_alloc() noexcept
Create a new, empty allocator.
l4_cap_idx_t cap() const noexcept
Return capability selector.
Definition capability.h:49
C++ interface for capabilities.
Definition capability.h:219
unsigned long l4_cap_idx_t
Capability selector type.
Definition types.h:359
unsigned l4_is_valid_cap(l4_cap_idx_t c) L4_NOTHROW
Test if a capability selector is a valid selector.
Definition types.h:416
@ L4_CAP_SHIFT
Capability index shift.
Definition consts.h:157
@ L4_INVALID_CAP
Invalid capability selector.
Definition consts.h:168
l4_msgtag_t l4_task_unmap(l4_cap_idx_t task, l4_fpage_t fpage, l4_umword_t map_mask) L4_NOTHROW
Revoke rights from the task.
Definition task.h:411
@ L4_FP_ALL_SPACES
Flag to tell the unmap operation to revoke permissions from all child mappings including the mapping ...
Definition consts.h:198
#define L4_UNLIKELY(x)
Expression is unlikely to execute.
Definition compiler.h:296
L4Re C++ Interfaces.
Definition l4re.dox:17
Constants.
Thread safe version of counter for Counting_cap_alloc.
Type dec()
Decrement counter if not saturated.
bool inc()
Increment counter if not yet saturated.
Counter for Counting_cap_alloc with variable data width.
Type dec()
Decrement counter if not saturated.
bool inc()
Increment counter if not yet saturated.
Low-level assert implementation.
#define l4_assert(expr)
Low-level assert.
Definition assert.h:43
Common task related definitions.