Loading...
Searching...
No Matches
slab_alloc
// vi:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
* 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/cxx/std_alloc>
#include <l4/cxx/hlist>
#include <l4/sys/consts.h>
namespace cxx {
template< int Obj_size, int Slab_size = L4_PAGESIZE,
int Max_free = 2, template<typename A> class Alloc = New_allocator >
class Base_slab
{
private:
struct Free_o
{
Free_o *next;
};
protected:
struct Slab_i;
private:
struct Slab_head : public H_list_item
{
unsigned num_free;
Free_o *free;
Base_slab<Obj_size, Slab_size, Max_free, Alloc> *cache;
inline Slab_head() noexcept : num_free(0), free(0), cache(0)
{}
};
// In an empty or partially filled slab, each free object stores a pointer to
// the next free object. Thus, the size of an object needs to be at least the
// size of a pointer.
static_assert(Obj_size >= sizeof(void *),
"Object size must be at least the size of a pointer.");
static_assert(Obj_size <= Slab_size - sizeof(Slab_head),
"Object_size exceeds slab capability.");
public:
enum
{
object_size = Obj_size,
slab_size = Slab_size,
objects_per_slab = (Slab_size - sizeof(Slab_head)) / object_size,
max_free_slabs = Max_free,
};
protected:
struct Slab_store
{
char _o[slab_size - sizeof(Slab_head)];
Free_o *object(unsigned obj) noexcept
{ return reinterpret_cast<Free_o*>(_o + object_size * obj); }
};
struct Slab_i : public Slab_store, public Slab_head
{};
public:
typedef Alloc<Slab_i> Slab_alloc;
typedef void Obj_type;
private:
Slab_alloc _alloc;
unsigned _num_free;
unsigned _num_slabs;
H_list<Slab_i> _full_slabs;
H_list<Slab_i> _partial_slabs;
H_list<Slab_i> _empty_slabs;
void add_slab(Slab_i *s) noexcept
{
s->num_free = objects_per_slab;
s->cache = this;
//L4::cerr << "Slab: " << this << "->add_slab(" << s << ", size="
// << slab_size << "):" << " f=" << s->object(0) << '\n';
// initialize free list
Free_o *f = s->free = s->object(0);
for (unsigned i = 1; i < objects_per_slab; ++i)
{
f->next = s->object(i);
f = f->next;
}
f->next = 0;
// insert slab into cache's list
_empty_slabs.push_front(s);
++_num_slabs;
++_num_free;
}
bool grow() noexcept
{
Slab_i *s = _alloc.alloc();
if (!s)
return false;
new (s, cxx::Nothrow()) Slab_i();
add_slab(s);
return true;
}
void shrink() noexcept
{
if (!_alloc.can_free)
return;
while (!_empty_slabs.empty() && _num_free > max_free_slabs)
{
Slab_i *s = _empty_slabs.front();
_empty_slabs.remove(s);
--_num_free;
--_num_slabs;
_alloc.free(s);
}
}
public:
Base_slab(Slab_alloc const &alloc = Slab_alloc()) noexcept
: _alloc(alloc), _num_free(0), _num_slabs(0), _full_slabs(),
_partial_slabs(), _empty_slabs()
{}
~Base_slab() noexcept
{
while (!_empty_slabs.empty())
{
Slab_i *o = _empty_slabs.front();
_empty_slabs.remove(o);
_alloc.free(o);
}
while (!_partial_slabs.empty())
{
Slab_i *o = _partial_slabs.front();
_partial_slabs.remove(o);
_alloc.free(o);
}
while (!_full_slabs.empty())
{
Slab_i *o = _full_slabs.front();
_full_slabs.remove(o);
_alloc.free(o);
}
}
void *alloc() noexcept
{
H_list<Slab_i> *free = &_partial_slabs;
if (free->empty())
free = &_empty_slabs;
if (free->empty() && !grow())
return 0;
Slab_i *s = free->front();
Free_o *o = s->free;
s->free = o->next;
if (free == &_empty_slabs)
{
_empty_slabs.remove(s);
--_num_free;
}
--(s->num_free);
if (!s->free)
{
_partial_slabs.remove(s);
_full_slabs.push_front(s);
}
else if (free == &_empty_slabs)
_partial_slabs.push_front(s);
//L4::cerr << this << "->alloc(): " << o << ", of " << s << '\n';
return o;
}
void free(void *_o) noexcept
{
if (!_o)
return;
unsigned long addr = reinterpret_cast<unsigned long>(_o);
// find out the slab the object is in
addr = (addr / slab_size) * slab_size;
Slab_i *s = reinterpret_cast<Slab_i*>(addr);
if (s->cache != this)
return;
Free_o *o = reinterpret_cast<Free_o*>(_o);
o->next = s->free;
s->free = o;
bool was_full = false;
if (!s->num_free)
{
_full_slabs.remove(s);
was_full = true;
}
++(s->num_free);
if (s->num_free == objects_per_slab)
{
if (!was_full)
_partial_slabs.remove(s);
_empty_slabs.push_front(s);
++_num_free;
if (_num_free > max_free_slabs)
shrink();
was_full = false;
}
else if (was_full)
_partial_slabs.push_front(s);
//L4::cerr << this << "->free(" << _o << "): of " << s << '\n';
}
unsigned total_objects() const noexcept
{ return _num_slabs * objects_per_slab; }
unsigned free_objects() const noexcept
{
unsigned count = 0;
/* count partial slabs first */
for (typename H_list<Slab_i>::Const_iterator s = _partial_slabs.begin();
s != _partial_slabs.end(); ++s)
count += s->num_free;
/* add empty slabs */
count += _num_free * objects_per_slab;
return count;
}
};
template<typename Type, int Slab_size = L4_PAGESIZE,
int Max_free = 2, template<typename A> class Alloc = New_allocator >
class Slab : public Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>
{
private:
typedef Base_slab<sizeof(Type), Slab_size, Max_free, Alloc> Base_type;
public:
typedef Type Obj_type;
Slab(typename Base_type::Slab_alloc const &alloc
= typename Base_type::Slab_alloc()) noexcept
: Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>(alloc) {}
Type *alloc() noexcept
{
return reinterpret_cast<Type *>(Base_type::alloc());
}
void free(Type *o) noexcept
{ Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>::free(o); }
};
template< int Obj_size, int Slab_size = L4_PAGESIZE,
int Max_free = 2, template<typename A> class Alloc = New_allocator >
class Base_slab_static
{
private:
typedef Base_slab<Obj_size, Slab_size, Max_free, Alloc> _A;
static _A _a;
public:
typedef void Obj_type;
enum
{
object_size = Obj_size,
slab_size = Slab_size,
objects_per_slab = _A::objects_per_slab,
max_free_slabs = Max_free,
};
void *alloc() noexcept { return _a.alloc(); }
void free(void *p) noexcept { _a.free(p); }
unsigned total_objects() const noexcept { return _a.total_objects(); }
unsigned free_objects() const noexcept { return _a.free_objects(); }
};
template< int _O, int _S, int _M, template<typename A> class Alloc >
typename Base_slab_static<_O,_S,_M,Alloc>::_A
Base_slab_static<_O,_S,_M,Alloc>::_a;
template<typename Type, int Slab_size = L4_PAGESIZE,
int Max_free = 2, template<typename A> class Alloc = New_allocator >
class Slab_static
: public Base_slab_static<sizeof(Type), Slab_size, Max_free, Alloc>
{
public:
typedef Type Obj_type;
Type *alloc() noexcept
{
return reinterpret_cast<Type *>(
Base_slab_static<sizeof(Type), Slab_size, Max_free, Alloc>::alloc());
}
};
}
cxx::Base_slab_static
Merged slab allocator (allocators for objects of the same size are merged together).
Definition slab_alloc:389
cxx::Base_slab_static::total_objects
unsigned total_objects() const noexcept
Get the total number of objects managed by the slab allocator.
Definition slab_alloc:430
cxx::Base_slab_static::alloc
void * alloc() noexcept
Allocate an object.
Definition slab_alloc:412
cxx::Base_slab_static::free
void free(void *p) noexcept
Free the given object (p).
Definition slab_alloc:420
cxx::Base_slab_static::max_free_slabs
@ max_free_slabs
Maximum number of free slabs.
Definition slab_alloc:404
cxx::Base_slab_static::slab_size
@ slab_size
Size of a slab.
Definition slab_alloc:400
cxx::Base_slab_static::objects_per_slab
@ objects_per_slab
Number of objects per slab.
Definition slab_alloc:402
cxx::Base_slab_static::object_size
@ object_size
Size of an object.
Definition slab_alloc:398
cxx::Base_slab_static::free_objects
unsigned free_objects() const noexcept
Get the number of free objects in the slab allocator.
Definition slab_alloc:440
cxx::Base_slab
Basic slab allocator.
Definition slab_alloc:32
cxx::Base_slab::free_objects
unsigned free_objects() const noexcept
Get the number of objects which can be allocated before a new empty slab needs to be added to the sla...
Definition slab_alloc:308
cxx::Base_slab::Slab_alloc
Alloc< Slab_i > Slab_alloc
Type of the backend allocator.
Definition slab_alloc:91
cxx::Base_slab< sizeof(Type), Slab_size, Max_free, Alloc >::max_free_slabs
@ max_free_slabs
Definition slab_alloc:74
cxx::Base_slab< sizeof(Type), Slab_size, Max_free, Alloc >::slab_size
@ slab_size
Definition slab_alloc:70
cxx::Base_slab< sizeof(Type), Slab_size, Max_free, Alloc >::object_size
@ object_size
Definition slab_alloc:68
cxx::Base_slab< sizeof(Type), Slab_size, Max_free, Alloc >::objects_per_slab
@ objects_per_slab
Definition slab_alloc:72
cxx::Base_slab::alloc
void * alloc() noexcept
Allocate a new object.
Definition slab_alloc:207
cxx::Base_slab::total_objects
unsigned total_objects() const noexcept
Get the total number of objects managed by the slab allocator.
Definition slab_alloc:299
cxx::Base_slab::free
void free(void *_o) noexcept
Free the given object (_o).
Definition slab_alloc:246
cxx::Bits::Basic_list::empty
bool empty() const
Check if the list is empty.
Definition list_basics.h:126
cxx::Bits::Basic_list::front
Value_type front() const
Return the first element in the list.
Definition list_basics.h:128
cxx::H_list
General double-linked list of unspecified cxx::H_list_item elements.
Definition hlist:70
cxx::H_list::remove
static void remove(T *e)
Remove the given element from its list.
Definition hlist:220
cxx::New_allocator
Standard allocator based on operator new () .
Definition std_alloc:57
cxx::Nothrow
Helper type to distinguish the operator new version that does not throw exceptions.
Definition std_alloc:19
cxx::Slab_static
Merged slab allocator (allocators for objects of the same size are merged together).
Definition slab_alloc:467
cxx::Slab_static::alloc
Type * alloc() noexcept
Allocate an object of type Type.
Definition slab_alloc:478
cxx::Slab::alloc
Type * alloc() noexcept
Allocate an object of type Type.
Definition slab_alloc:355
cxx::Slab::free
void free(Type *o) noexcept
Free the object addressed by o.
Definition slab_alloc:366
L4_PAGESIZE
#define L4_PAGESIZE
Minimal page size (in bytes).
Definition consts.h:391
consts.h
Common constants.
cxx
Our C++ library.
Definition arith:11
cxx::H_list_item
H_list_item_t< void > H_list_item
Untyped list item.
Definition hlist:61
cxx::Base_slab::Slab_i
Type of a slab.
Definition slab_alloc:87