Loading...
Searching...
No Matches
counting_cap_alloc
Go to the documentation of this file.
// vim:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2008-2010 Alexander Warg <warg@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include <l4/sys/task>
#include <l4/sys/assert.h>
#include <l4/re/consts>
namespace L4Re { namespace Util {
template< typename COUNTER = unsigned char >
struct Counter
{
typedef COUNTER Type;
Type _cnt;
static Type nil() { return 0; }
static Type unused() { return 0; }
void free() { _cnt = 0; }
bool is_free() const { return _cnt == 0; }
bool is_saturated() const { return static_cast<Type>(_cnt + 1) == 0; }
bool inc()
{
if (is_saturated())
return true; // no change and no warning
++_cnt;
if (is_saturated())
return false; // warn caller that counter is now saturated
else
return true; // success
}
Type dec()
{
if (is_saturated())
return _cnt; // no change
else
return --_cnt; // success
}
bool try_alloc()
{
if (_cnt == 0)
{
_cnt = 1;
return true;
}
return false;
}
};
template< typename COUNTER = unsigned char >
struct Counter_atomic
{
typedef COUNTER Type;
Type _cnt;
static Type nil() { return 0; }
static Type unused() { return 1; }
bool is_free() const { return __atomic_load_n(&_cnt, __ATOMIC_RELAXED) == 0; }
static bool is_saturated(Type cnt) { return static_cast<Type>(cnt + 1) == 0; }
bool try_alloc()
{
Type expected = nil();
// Use "acquire" memory ordering. Any operations tied to the capability slot
// must only be observable after the slot has been occupied.
return __atomic_compare_exchange_n(&_cnt, &expected, 2, false,
__ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
}
bool inc()
{
Type old_cnt = __atomic_load_n(&_cnt, __ATOMIC_RELAXED);
Type new_cnt;
do
{
if (is_saturated(old_cnt))
return true; // no change and no warning
new_cnt = old_cnt + 1;
}
while (!__atomic_compare_exchange_n(&_cnt, &old_cnt, new_cnt, false,
__ATOMIC_RELAXED, __ATOMIC_RELAXED));
if (is_saturated(new_cnt))
return false; // warn caller that counter is now saturated
else
return true; // success
}
Type dec()
{
Type old_cnt = __atomic_load_n(&_cnt, __ATOMIC_RELAXED);
Type new_cnt;
do
{
if (is_saturated(old_cnt))
return old_cnt; // no change
new_cnt = old_cnt - 1;
}
while (!__atomic_compare_exchange_n(&_cnt, &old_cnt, new_cnt, false,
__ATOMIC_RELAXED, __ATOMIC_RELAXED));
return new_cnt; // success
}
void free()
{
// Use "release" memory ordering to make sure that any operations tied to
// the capability slot are observable by other threads before the slot can
// be reused.
__atomic_store_n(&_cnt, 0, __ATOMIC_RELEASE);
}
};
template <typename COUNTERTYPE, typename Dbg>
class Counting_cap_alloc
{
private:
void operator = (Counting_cap_alloc const &) { }
typedef COUNTERTYPE Counter;
COUNTERTYPE *_items;
long _free_hint;
long _bias;
long _capacity;
Dbg *_dbg;
public:
template <unsigned COUNT>
struct Storage
{
COUNTERTYPE _buf[COUNT];
typedef COUNTERTYPE Buf_type[COUNT];
enum { Size = COUNT };
};
Counting_cap_alloc(long capacity, void *m, long bias, Dbg *dbg) noexcept
: _items((Counter*)m), _free_hint(0), _bias(bias), _capacity(capacity),
_dbg(dbg)
{}
protected:
Counting_cap_alloc() noexcept
: _items(0), _free_hint(0), _bias(0), _capacity(0)
{}
void setup(void *m, long capacity, long bias, Dbg *dbg) noexcept
{
_items = static_cast<Counter*>(m);
_capacity = capacity;
_bias = bias;
_dbg = dbg;
}
public:
L4::Cap<void> alloc() noexcept
{
long free_hint = __atomic_load_n(&_free_hint, __ATOMIC_RELAXED);
for (long i = free_hint; i < _capacity; ++i)
if (_items[i].try_alloc())
{
_free_hint = i + 1;
return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
}
// _free_hint is not necessarily correct in case of multi-threading! Make
// sure we don't miss any potentially free slots.
for (long i = 0; i < free_hint && i < _capacity; ++i)
if (_items[i].try_alloc())
{
_free_hint = i + 1;
return L4::Cap<void>((i + _bias) << L4_CAP_SHIFT);
}
return L4::Cap<void>::Invalid;
}
template <typename T>
L4::Cap<T> alloc() noexcept
{
return L4::cap_cast<T>(alloc());
}
void take(L4::Cap<void> cap) noexcept
{
long c;
if (!range_check_and_get_idx(cap, &c))
return;
if (!L4_UNLIKELY(_items[c].inc()))
_dbg->printf("Warning: Reference counter of cap 0x%lx now saturated!\n",
cap.cap() >> L4_CAP_SHIFT);
}
bool free(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
{
long c;
if (!range_check_and_get_idx(cap, &c))
return false;
l4_assert(!_items[c].is_free());
if (l4_is_valid_cap(task))
l4_task_unmap(task, cap.fpage(), unmap_flags);
if (c < _free_hint)
_free_hint = c;
_items[c].free();
return true;
}
bool release(L4::Cap<void> cap, l4_cap_idx_t task = L4_INVALID_CAP,
unsigned unmap_flags = L4_FP_ALL_SPACES) noexcept
{
long c;
if (!range_check_and_get_idx(cap, &c))
return false;
l4_assert(!_items[c].is_free());
if (_items[c].dec() == Counter::unused())
{
if (task != L4_INVALID_CAP)
l4_task_unmap(task, cap.fpage(), unmap_flags);
if (c < _free_hint)
_free_hint = c;
// Let others allocate this slot only after the l4_task_unmap() has
// finished.
_items[c].free();
return true;
}
return false;
}
long last() noexcept
{
return _capacity + _bias - 1;
}
private:
bool range_check_and_get_idx(L4::Cap<void> cap, long *c)
{
*c = cap.cap() >> L4_CAP_SHIFT;
if (*c < _bias)
return false;
*c -= _bias;
return *c < _capacity;
}
};
}}
L4Re::Util::Counting_cap_alloc::release
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.
Definition counting_cap_alloc:359
L4Re::Util::Counting_cap_alloc::setup
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.
Definition counting_cap_alloc:242
L4Re::Util::Counting_cap_alloc::last
long last() noexcept
Return highest capability id managed by this allocator.
Definition counting_cap_alloc:388
L4Re::Util::Counting_cap_alloc::free
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.
Definition counting_cap_alloc:321
L4Re::Util::Counting_cap_alloc::take
void take(L4::Cap< void > cap) noexcept
Increase the reference counter for the capability.
Definition counting_cap_alloc:296
L4Re::Util::Counting_cap_alloc::alloc
L4::Cap< void > alloc() noexcept
Allocate a new capability slot.
Definition counting_cap_alloc:257
L4Re::Util::Counting_cap_alloc::alloc
L4::Cap< T > alloc() noexcept
Allocate a new capability slot.
Definition counting_cap_alloc:282
L4Re::Util::Counting_cap_alloc::Counting_cap_alloc
Counting_cap_alloc() noexcept
Create a new, empty allocator.
Definition counting_cap_alloc:224
L4::Cap_base::cap
l4_cap_idx_t cap() const noexcept
Return capability selector.
Definition capability.h:49
L4::Cap_base::Invalid
@ Invalid
Invalid capability selector.
Definition capability.h:42
L4::Cap
C++ interface for capabilities.
Definition capability.h:224
l4_cap_idx_t
unsigned long l4_cap_idx_t
Capability selector type.
Definition types.h:336
l4_is_valid_cap
unsigned l4_is_valid_cap(l4_cap_idx_t c) L4_NOTHROW
Test if a capability selector is a valid selector.
Definition types.h:393
L4_CAP_SHIFT
@ L4_CAP_SHIFT
Capability index shift.
Definition consts.h:142
L4_INVALID_CAP
@ L4_INVALID_CAP
Invalid capability selector.
Definition consts.h:153
l4_task_unmap
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:440
L4_FP_ALL_SPACES
@ L4_FP_ALL_SPACES
Flag to tell the unmap operation to revoke permissions from all child mappings including the mapping ...
Definition consts.h:183
L4_UNLIKELY
#define L4_UNLIKELY(x)
Expression is unlikely to execute.
Definition compiler.h:284
L4Re::Util
Documentation of the L4 Runtime Environment utility functionality in C++.
Definition l4re.dox:21
L4Re
L4Re C++ Interfaces.
Definition cmd_control:14
L4::cap_cast
Cap< T > cap_cast(Cap< F > const &c) noexcept
static_cast for capabilities.
Definition capability.h:416
consts
Constants.
L4Re::Util::Counter_atomic
Thread safe version of counter for Counting_cap_alloc.
Definition counting_cap_alloc:99
L4Re::Util::Counter_atomic::dec
Type dec()
Decrement counter if not saturated.
Definition counting_cap_alloc:142
L4Re::Util::Counter_atomic::inc
bool inc()
Increment counter if not yet saturated.
Definition counting_cap_alloc:121
L4Re::Util::Counter
Counter for Counting_cap_alloc with variable data width.
Definition counting_cap_alloc:28
L4Re::Util::Counter::dec
Type dec()
Decrement counter if not saturated.
Definition counting_cap_alloc:67
L4Re::Util::Counter::inc
bool inc()
Increment counter if not yet saturated.
Definition counting_cap_alloc:50
assert.h
Low-level assert implementation.
l4_assert
#define l4_assert(expr)
Low-level assert.
Definition assert.h:32
task
Common task related definitions.