1 /*
2 * \brief Slab allocator
3 * \author Norman Feske
4 * \date 2006-04-18
5 */
6
7 /*
8 * Copyright (C) 2006-2013 Genode Labs GmbH
9 *
10 * This file is part of the Genode OS framework, which is distributed
11 * under the terms of the GNU General Public License version 2.
12 */
13
14 #ifndef _INCLUDE__BASE__SLAB_H_
15 #define _INCLUDE__BASE__SLAB_H_
16
17 #include <base/allocator.h>
18 #include <base/stdint.h>
19
20 namespace Genode {
21
22 class Slab;
23 class Slab_block;
24 class Slab_entry;
25 }
26
27
28 /**
29 * A slab block holds an array of slab entries.
30 */
31 class Genode::Slab_block
32 {
33 public:
34
35 Slab_block *next; /* next block */
36 Slab_block *prev; /* previous block */
37
38 private:
39
40 enum { FREE, USED }
41
42 Slab *_slab; /* back reference to slab allocator */
43 size_t _avail; /* free entries of this block */
44
45 /*
46 * Each slab block consists of three areas, a fixed-size header
47 * that contains the member variables declared above, a byte array
48 * called state table that holds the allocation state for each slab
49 * entry, and an area holding the actual slab entries. The number
50 * of state-table elements corresponds to the maximum number of slab
51 * entries per slab block (the `_num_elem` member variable of the
52 * Slab allocator).
53 */
54
55 char _data[]; /* dynamic data (state table and slab entries) */
56
57 /*
58 * Caution! no member variables allowed below this line!
59 */
60
61 /**
62 * Return the allocation state of a slab entry
63 */
64 inline bool state(int idx) { return _data[idx]}
65
66 /**
67 * Set the allocation state of a slab entry
68 */
69 inline void state(int idx, bool state) { _data[idx] = state;}
70
71 /**
72 * Request address of slab entry by its index
73 */
74 Slab_entry *slab_entry(int idx);
75
76 /**
77 * Determine block index of specified slab entry
78 */
79 int slab_entry_idx(Slab_entry *e);
80
81 public:
82
83 /**
84 * Constructor
85 *
86 * Normally, Slab_blocks are constructed by a Slab allocator
87 * that specifies itself as constructor argument.
88 */
89 explicit Slab_block(Slab *s = 0) { if (s)slab(s);}
90
91 /**
92 * Configure block to be managed by the specified slab allocator
93 */
94 void slab(Slab *slab);
95
96 /**
97 * Request number of available entries in block
98 */
99 unsigned avail() const { return _avail}
100
101 /**
102 * Allocate slab entry from block
103 */
104 void *alloc();
105
106 /**
107 * Return a used slab block entry
108 */
109 Slab_entry *first_used_entry();
110
111 /**
112 * These functions are called by Slab_entry.
113 */
114 void inc_avail(Slab_entry *e);
115 void dec_avail();
116
117 /**
118 * Debug and test hooks
119 */
120 void dump();
121 int check_bounds();
122 }
123
124
125 class Genode::Slab_entry
126 {
127 private:
128
129 Slab_block *_sb;
130 char _data[];
131
132 /*
133 * Caution! no member variables allowed below this line!
134 */
135
136 public:
137
138 void init() { _sb = 0;}
139
140 void occupy(Slab_block *sb)
141 {
142 _sb = sb;
143 _sb->dec_avail();
144 }
145
146 void free()
147 {
148 _sb->inc_avail(this);
149 _sb = 0;
150 }
151
152 void *addr() { return _data}
153
154 /**
155 * Lookup Slab_entry by given address
156 *
157 * The specified address is supposed to point to _data[0].
158 */
159 static Slab_entry *slab_entry(void *addr) {
160 return (Slab_entry *)((addr_t)- sizeof(Slab_entry))}
161 }
162
163
164 /**
165 * Slab allocator
166 */
167 class Genode::Slab : public Allocator
168 {
169 private:
170
171 size_t _slab_size; /* size of one slab entry */
172 size_t _block_size; /* size of slab block */
173 size_t _num_elem; /* number of slab entries per block */
174 Slab_block *_first_sb; /* first slab block */
175 Slab_block *_initial_sb; /* initial (static) slab block */
176 bool _alloc_state; /* indicator for `currently in service` */
177
178 Allocator *_backing_store;
179
180 /**
181 * Allocate and initialize new slab block
182 */
183 Slab_block *_new_slab_block();
184
185 public:
186
187 inline size_t slab_size() const { return _slab_size}
188 inline size_t block_size() const { return _block_size}
189 inline size_t num_elem() const { return _num_elem}
190 inline size_t entry_size() const { return sizeof(Slab_entry)+ _slab_size}
191
192 /**
193 * Constructor
194 *
195 * At construction time, there exists one initial slab
196 * block that is used for the first couple of allocations,
197 * especially for the allocation of the second slab
198 * block.
199 */
200 Slab(size_t slab_size, size_t block_size, Slab_block *initial_sb,
201 Allocator *backing_store = 0);
202
203 /**
204 * Destructor
205 */
206 ~Slab();
207
208 /**
209 * Debug function for dumping the current slab block list
210 *
211 * \noapi
212 */
213 void dump_sb_list();
214
215 /**
216 * Remove block from slab block list
217 *
218 * \noapi
219 */
220 void remove_sb(Slab_block *sb);
221
222 /**
223 * Insert block into slab block list
224 *
225 * \noapi
226 */
227 void insert_sb(Slab_block *sb, Slab_block *at = 0);
228
229 /**
230 * Free slab entry
231 */
232 static void free(void *addr);
233
234 /**
235 * Return a used slab element
236 */
237 void *first_used_elem();
238
239 /**
240 * Return true if number of free slab entries is higher than n
241 */
242 bool num_free_entries_higher_than(int n);
243
244 /**
245 * Define/request backing-store allocator
246 *
247 * \noapi
248 */
249 void backing_store(Allocator *bs) { _backing_store = bs;}
250
251 /**
252 * Request backing-store allocator
253 *
254 * \noapi
255 */
256 Allocator *backing_store() { return _backing_store}
257
258 /*************************
259 ** Allocator interface **
260 *************************/
261
262 /**
263 * Allocate slab entry
264 *
265 * The `size` parameter is ignored as only slab entries with
266 * preconfigured slab-entry size are allocated.
267 */
268 bool alloc(size_t size, void **addr) override;
269 void free(void *addr, size_t) override { free(addr);}
270 size_t consumed() const override;
271 size_t overhead(size_t) const override { return _block_size/_num_elem}
272 bool need_size_for_free() const override { return false}
273 }
274
275 #endif /* _INCLUDE__BASE__SLAB_H_ */