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)
 *
 * This file is part of TUD:OS and distributed under the terms of the
 * GNU General Public License 2.
 * Please see the COPYING-GPL-2 file for details.
 *
 * As a special exception, you may use this file as part of a free software
 * library without restriction.  Specifically, if other files instantiate
 * templates or use macros or inline functions from this file, or you compile
 * this file and link it with other files to produce an executable, this
 * file does not by itself cause the resulting executable to be covered by
 * the GNU General Public License.  This exception does not however
 * invalidate any other reasons why the executable file might be covered by
 * the GNU General Public License.
 */
 
#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 };
  };
 
protected:
 
  Counting_cap_alloc() noexcept
  : _items(0), _free_hint(0), _bias(0), _capacity(0)
  {}
 
  Counting_cap_alloc(long capacity, void *m, long bias, Dbg *dbg) noexcept
  : _items((Counter*)m), _free_hint(0), _bias(bias), _capacity(capacity),
    _dbg(dbg)
  {}
 
  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;
  }
};
 
}}