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 void inc() { ++_cnt; }
49 Type dec() { return --_cnt; }
50 bool try_alloc()
51 {
52 if (_cnt == 0)
53 {
54 _cnt = 1;
55 return true;
56 }
57 return false;
58 }
59};
60
72template< typename COUNTER = unsigned char >
74{
75 typedef COUNTER Type;
76 Type _cnt;
77
78 static Type nil() { return 0; }
79 static Type unused() { return 1; }
80
81 bool is_free() const { return __atomic_load_n(&_cnt, __ATOMIC_RELAXED) == 0; }
82
83 bool try_alloc()
84 {
85 Type expected = nil();
86 // Use "aquire" memory ordering. Any operations tied to the capability slot
87 // must only be observable after the slot has been occupied.
88 return __atomic_compare_exchange_n(&_cnt, &expected, 2, false,
89 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
90 }
91
92 void inc() { __atomic_add_fetch(&_cnt, 1, __ATOMIC_RELAXED); }
93 Type dec() { return __atomic_sub_fetch(&_cnt, 1, __ATOMIC_RELAXED); }
94
95 void free()
96 {
97 // Use "release" memory ordering to make sure that any operations tied to
98 // the capability slot are observable by other threads before the slot can
99 // be reused.
100 __atomic_store_n(&_cnt, 0, __ATOMIC_RELEASE);
101 }
102};
103
128template <typename COUNTERTYPE>
130{
131private:
132 void operator = (Counting_cap_alloc const &) { }
133 typedef COUNTERTYPE Counter;
134
135 COUNTERTYPE *_items;
136 long _free_hint;
137 long _bias;
138 long _capacity;
139
140
141public:
142
143 template <unsigned COUNT>
144 struct Counter_storage
145 {
146 COUNTERTYPE _buf[COUNT];
147 typedef COUNTERTYPE Buf_type[COUNT];
148 enum { Size = COUNT };
149 };
150
151protected:
152
159 : _items(0), _free_hint(0), _bias(0), _capacity(0)
160 {}
161
175 void setup(void *m, long capacity, long bias) noexcept
176 {
177 _items = (Counter*)m;
178 _capacity = capacity;
179 _bias = bias;
180 }
181
182public:
190 {
191 long free_hint = __atomic_load_n(&_free_hint, __ATOMIC_RELAXED);
192
193 for (long i = free_hint; i < _capacity; ++i)
194 if (_items[i].try_alloc())
195 {
196 _free_hint = i + 1;
197 return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
198 }
199
200 // _free_hint is not necessarily correct in case of multi-threading! Make
201 // sure we don't miss any potentially free slots.
202 for (long i = 0; i < free_hint && i < _capacity; ++i)
203 if (_items[i].try_alloc())
204 {
205 _free_hint = i + 1;
206 return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
207 }
208
210 }
211
213 template <typename T>
214 L4::Cap<T> alloc() noexcept
215 {
216 return L4::cap_cast<T>(alloc());
217 }
218
219
229 void take(L4::Cap<void> cap) noexcept
230 {
231 long c;
232 if (!range_check_and_get_idx(cap, &c))
233 return;
234
235 _items[c].inc();
236 }
237
238
253 unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
254 {
255 long c;
256 if (!range_check_and_get_idx(cap, &c))
257 return false;
258
259 l4_assert(!_items[c].is_free());
260
261 if (l4_is_valid_cap(task))
262 l4_task_unmap(task, cap.fpage(), unmap_flags);
263
264 if (c < _free_hint)
265 _free_hint = c;
266
267 _items[c].free();
268
269 return true;
270 }
271
291 unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
292 {
293 long c;
294 if (!range_check_and_get_idx(cap, &c))
295 return false;
296
297 l4_assert(!_items[c].is_free());
298
299 if (_items[c].dec() == Counter::unused())
300 {
301 if (task != L4_INVALID_CAP)
302 l4_task_unmap(task, cap.fpage(), unmap_flags);
303
304 if (c < _free_hint)
305 _free_hint = c;
306
307 // Let others allocate this slot only after the l4_task_unmap() has
308 // finished.
309 _items[c].free();
310
311 return true;
312 }
313 return false;
314 }
315
319 long last() noexcept
320 {
321 return _capacity + _bias - 1;
322 }
323
324private:
325 bool range_check_and_get_idx(L4::Cap<void> cap, long *c)
326 {
327 *c = cap.cap() >> L4_CAP_SHIFT;
328 if (*c < _bias)
329 return false;
330
331 *c -= _bias;
332
333 return *c < _capacity;
334 }
335};
336
337}}
338
Internal reference-counting cap allocator.
void take(L4::Cap< void > cap) noexcept
Increase the reference counter for the capability.
L4::Cap< void > alloc() noexcept
Allocate a new capability slot.
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 setup(void *m, long capacity, long bias) noexcept
Set up the backing memory for the allocator and the area of managed capability slots.
Counting_cap_alloc() noexcept
Create a new, empty allocator.
long last() noexcept
Return highest capability id managed by this 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.
L4::Cap< T > alloc() noexcept
Allocate a new capability slot.
l4_cap_idx_t cap() const noexcept
Return capability selector.
Definition capability.h:52
C++ interface for capabilities.
Definition capability.h:222
unsigned long l4_cap_idx_t
Capability selector type.
Definition types.h:358
unsigned l4_is_valid_cap(l4_cap_idx_t c) L4_NOTHROW
Test if a capability selector is a valid selector.
Definition types.h:415
@ 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:402
@ L4_FP_ALL_SPACES
Flag to tell the unmap operation to revoke permissions from all child mappings including the mapping ...
Definition consts.h:198
L4Re C++ Interfaces.
Definition cmd_control:15
Constants.
Thread safe version of counter for Counting_cap_alloc.
Counter for Counting_cap_alloc with variable data width.
Low-level assert implementation.
#define l4_assert(expr)
Low-level assert.
Definition assert.h:43
Common task related definitions.