L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
slab_alloc
1// vi:set ft=cpp: -*- Mode: C++ -*-
2/*
3 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
4 * Alexander Warg <warg@os.inf.tu-dresden.de>
5 * economic rights: Technische Universität Dresden (Germany)
6 *
7 * This file is part of TUD:OS and distributed under the terms of the
8 * GNU General Public License 2.
9 * Please see the COPYING-GPL-2 file for details.
10 *
11 * As a special exception, you may use this file as part of a free software
12 * library without restriction. Specifically, if other files instantiate
13 * templates or use macros or inline functions from this file, or you compile
14 * this file and link it with other files to produce an executable, this
15 * file does not by itself cause the resulting executable to be covered by
16 * the GNU General Public License. This exception does not however
17 * invalidate any other reasons why the executable file might be covered by
18 * the GNU General Public License.
19 */
20
21#pragma once
22
23#include <l4/cxx/std_alloc>
24#include <l4/cxx/hlist>
25#include <l4/sys/consts.h>
26
27namespace cxx {
28
40template< int Obj_size, int Slab_size = L4_PAGESIZE,
41 int Max_free = 2, template<typename A> class Alloc = New_allocator >
43{
44private:
45 struct Free_o
46 {
47 Free_o *next;
48 };
49
50protected:
51 struct Slab_i;
52
53private:
54 struct Slab_head : public H_list_item
55 {
57 unsigned num_free;
59 Free_o *free;
62
63 inline Slab_head() noexcept : num_free(0), free(0), cache(0)
64 {}
65 };
66
67 // In an empty or partially filled slab, each free object stores a pointer to
68 // the next free object. Thus, the size of an object needs to be at least the
69 // size of a pointer.
70 static_assert(Obj_size >= sizeof(void *),
71 "Object size must be at least the size of a pointer.");
72 static_assert(Obj_size <= Slab_size - sizeof(Slab_head),
73 "Object_size exceeds slab capability.");
74
75public:
76 enum
77 {
79 object_size = Obj_size,
81 slab_size = Slab_size,
83 objects_per_slab = (Slab_size - sizeof(Slab_head)) / object_size,
85 max_free_slabs = Max_free,
86 };
87
88protected:
89 struct Slab_store
90 {
91 char _o[slab_size - sizeof(Slab_head)];
92 Free_o *object(unsigned obj) noexcept
93 { return reinterpret_cast<Free_o*>(_o + object_size * obj); }
94 };
95
97 struct Slab_i : public Slab_store, public Slab_head
98 {};
99
100public:
102 typedef Alloc<Slab_i> Slab_alloc;
103
104 typedef void Obj_type;
105
106private:
108 Slab_alloc _alloc;
110 unsigned _num_free;
112 unsigned _num_slabs;
114 H_list<Slab_i> _full_slabs;
116 H_list<Slab_i> _partial_slabs;
118 H_list<Slab_i> _empty_slabs;
119
121 void add_slab(Slab_i *s) noexcept
122 {
123 s->num_free = objects_per_slab;
124 s->cache = this;
125
126 //L4::cerr << "Slab: " << this << "->add_slab(" << s << ", size="
127 // << slab_size << "):" << " f=" << s->object(0) << '\n';
128
129 // initialize free list
130 Free_o *f = s->free = s->object(0);
131 for (unsigned i = 1; i < objects_per_slab; ++i)
132 {
133 f->next = s->object(i);
134 f = f->next;
135 }
136 f->next = 0;
137
138 // insert slab into cache's list
139 _empty_slabs.push_front(s);
140 ++_num_slabs;
141 ++_num_free;
142 }
143
145 bool grow() noexcept
146 {
147 Slab_i *s = _alloc.alloc();
148 if (!s)
149 return false;
150
151 new (s, cxx::Nothrow()) Slab_i();
152
153 add_slab(s);
154 return true;
155 }
156
166 void shrink() noexcept
167 {
168 if (!_alloc.can_free)
169 return;
170
171 while (!_empty_slabs.empty() && _num_free > max_free_slabs)
172 {
173 Slab_i *s = _empty_slabs.front();
174 _empty_slabs.remove(s);
175 --_num_free;
176 --_num_slabs;
177 _alloc.free(s);
178 }
179 }
180
181public:
182 Base_slab(Slab_alloc const &alloc = Slab_alloc()) noexcept
183 : _alloc(alloc), _num_free(0), _num_slabs(0), _full_slabs(),
184 _partial_slabs(), _empty_slabs()
185 {}
186
187 ~Base_slab() noexcept
188 {
189 while (!_empty_slabs.empty())
190 {
191 Slab_i *o = _empty_slabs.front();
192 _empty_slabs.remove(o);
193 _alloc.free(o);
194 }
195 while (!_partial_slabs.empty())
196 {
197 Slab_i *o = _partial_slabs.front();
198 _partial_slabs.remove(o);
199 _alloc.free(o);
200 }
201 while (!_full_slabs.empty())
202 {
203 Slab_i *o = _full_slabs.front();
204 _full_slabs.remove(o);
205 _alloc.free(o);
206 }
207 }
208
218 void *alloc() noexcept
219 {
220 H_list<Slab_i> *free = &_partial_slabs;
221 if (free->empty())
222 free = &_empty_slabs;
223
224 if (free->empty() && !grow())
225 return 0;
226
227 Slab_i *s = free->front();
228 Free_o *o = s->free;
229 s->free = o->next;
230
231 if (free == &_empty_slabs)
232 {
233 _empty_slabs.remove(s);
234 --_num_free;
235 }
236
237 --(s->num_free);
238
239 if (!s->free)
240 {
241 _partial_slabs.remove(s);
242 _full_slabs.push_front(s);
243 }
244 else if (free == &_empty_slabs)
245 _partial_slabs.push_front(s);
246
247 //L4::cerr << this << "->alloc(): " << o << ", of " << s << '\n';
248
249 return o;
250 }
251
257 void free(void *_o) noexcept
258 {
259 if (!_o)
260 return;
261
262 unsigned long addr = reinterpret_cast<unsigned long>(_o);
263
264 // find out the slab the object is in
265 addr = (addr / slab_size) * slab_size;
266 Slab_i *s = reinterpret_cast<Slab_i*>(addr);
267
268 if (s->cache != this)
269 return;
270
271 Free_o *o = reinterpret_cast<Free_o*>(_o);
272
273 o->next = s->free;
274 s->free = o;
275
276 bool was_full = false;
277
278 if (!s->num_free)
279 {
280 _full_slabs.remove(s);
281 was_full = true;
282 }
283
284 ++(s->num_free);
285
286 if (s->num_free == objects_per_slab)
287 {
288 if (!was_full)
289 _partial_slabs.remove(s);
290
291 _empty_slabs.push_front(s);
292 ++_num_free;
293 if (_num_free > max_free_slabs)
294 shrink();
295
296 was_full = false;
297 }
298 else if (was_full)
299 _partial_slabs.push_front(s);
300
301 //L4::cerr << this << "->free(" << _o << "): of " << s << '\n';
302 }
303
310 unsigned total_objects() const noexcept
311 { return _num_slabs * objects_per_slab; }
312
319 unsigned free_objects() const noexcept
320 {
321 unsigned count = 0;
322
323 /* count partial slabs first */
324 for (typename H_list<Slab_i>::Const_iterator s = _partial_slabs.begin();
325 s != _partial_slabs.end(); ++s)
326 count += s->num_free;
327
328 /* add empty slabs */
329 count += _num_free * objects_per_slab;
330
331 return count;
332 }
333};
334
344template<typename Type, int Slab_size = L4_PAGESIZE,
345 int Max_free = 2, template<typename A> class Alloc = New_allocator >
346class Slab : public Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>
347{
348private:
349 typedef Base_slab<sizeof(Type), Slab_size, Max_free, Alloc> Base_type;
350public:
351
352 typedef Type Obj_type;
353
354 Slab(typename Base_type::Slab_alloc const &alloc
355 = typename Base_type::Slab_alloc()) noexcept
357
358
366 Type *alloc() noexcept
367 {
368 return reinterpret_cast<Type *>(Base_type::alloc());
369 }
370
377 void free(Type *o) noexcept
378 { Base_slab<sizeof(Type), Slab_size, Max_free, Alloc>::free(o); }
379};
380
381
397template< int Obj_size, int Slab_size = L4_PAGESIZE,
398 int Max_free = 2, template<typename A> class Alloc = New_allocator >
400{
401private:
403 static _A _a;
404public:
405 typedef void Obj_type;
406 enum
407 {
409 object_size = Obj_size,
411 slab_size = Slab_size,
415 max_free_slabs = Max_free,
416 };
417
423 void *alloc() noexcept { return _a.alloc(); }
424
431 void free(void *p) noexcept { _a.free(p); }
432
441 unsigned total_objects() const noexcept { return _a.total_objects(); }
442
451 unsigned free_objects() const noexcept { return _a.free_objects(); }
452};
453
454
455template< int _O, int _S, int _M, template<typename A> class Alloc >
456typename Base_slab_static<_O,_S,_M,Alloc>::_A
457 Base_slab_static<_O,_S,_M,Alloc>::_a;
458
474template<typename Type, int Slab_size = L4_PAGESIZE,
475 int Max_free = 2, template<typename A> class Alloc = New_allocator >
477: public Base_slab_static<sizeof(Type), Slab_size, Max_free, Alloc>
478{
479public:
480
481 typedef Type Obj_type;
489 Type *alloc() noexcept
490 {
491 return reinterpret_cast<Type *>(
492 Base_slab_static<sizeof(Type), Slab_size, Max_free, Alloc>::alloc());
493 }
494};
495
496}
Merged slab allocator (allocators for objects of the same size are merged together).
Definition slab_alloc:400
@ max_free_slabs
Maximum number of free slabs.
Definition slab_alloc:415
@ slab_size
Size of a slab.
Definition slab_alloc:411
@ objects_per_slab
Number of objects per slab.
Definition slab_alloc:413
@ object_size
Size of an object.
Definition slab_alloc:409
unsigned total_objects() const noexcept
Get the total number of objects managed by the slab allocator.
Definition slab_alloc:441
void * alloc() noexcept
Allocate an object.
Definition slab_alloc:423
void free(void *p) noexcept
Free the given object (p).
Definition slab_alloc:431
unsigned free_objects() const noexcept
Get the number of free objects in the slab allocator.
Definition slab_alloc:451
Basic slab allocator.
Definition slab_alloc:43
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:319
Alloc< Slab_i > Slab_alloc
Type of the backend allocator.
Definition slab_alloc:102
void * alloc() noexcept
Allocate a new object.
Definition slab_alloc:218
@ max_free_slabs
Maximum number of free slabs.
Definition slab_alloc:85
@ slab_size
Size of a slab.
Definition slab_alloc:81
@ object_size
Size of an object.
Definition slab_alloc:79
@ objects_per_slab
Objects per slab.
Definition slab_alloc:83
unsigned total_objects() const noexcept
Get the total number of objects managed by the slab allocator.
Definition slab_alloc:310
void free(void *_o) noexcept
Free the given object (_o).
Definition slab_alloc:257
Const_iterator end() const
Return a const iterator to the end of the list.
bool empty() const
Check if the list is empty.
Iterator begin()
Return an iterator to the beginning of the list.
Value_type front() const
Return the first element in the list.
Basic element type for a double-linked H_list.
Definition hlist:34
General double-linked list of unspecified cxx::H_list_item elements.
Definition hlist:81
static void remove(T *e)
Remove the given element from its list.
Definition hlist:231
void push_front(T *e)
Add element to the front of the list.
Definition hlist:120
Helper type to distinguish the oeprator new version that does not throw exceptions.
Definition std_alloc:30
Merged slab allocator (allocators for objects of the same size are merged together).
Definition slab_alloc:478
Type * alloc() noexcept
Allocate an object of type Type.
Definition slab_alloc:489
Slab allocator for object of type Type.
Definition slab_alloc:347
Type * alloc() noexcept
Allocate an object of type Type.
Definition slab_alloc:366
void free(Type *o) noexcept
Free the object addressed by o.
Definition slab_alloc:377
#define L4_PAGESIZE
Minimal page size (in bytes).
Definition consts.h:380
Our C++ library.
Definition arith:22
Type of a slab.
Definition slab_alloc:98