1 /*
2 * \brief Generic allocator interface
3 * \author Norman Feske
4 * \date 2006-04-16
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__ALLOCATOR_H_
15 #define _INCLUDE__BASE__ALLOCATOR_H_
16
17 #include <base/stdint.h>
18 #include <base/exception.h>
19
20 namespace Genode {
21
22 struct Deallocator;
23 struct Allocator;
24 struct Range_allocator;
25
26 template <typename T, typename DEALLOC>void destroy(DEALLOC && dealloc, T *obj);
27 }
28
29
30 /**
31 * Deallocator interface
32 */
33 struct Genode::Deallocator
34 {
35 /**
36 * Free block a previously allocated block
37 */
38 virtual void free(void *addr, size_t size) = 0
39
40 /**
41 * Return true if the size argument of `free` is required
42 *
43 * The generic `Allocator` interface requires the caller of `free`
44 * to supply a valid size argument but not all implementations make
45 * use of this argument. If this method returns false, it is safe
46 * to call `free` with an invalid size.
47 *
48 * Allocators that rely on the size argument must not be used for
49 * constructing objects whose constructors may throw exceptions.
50 * See the documentation of `operator delete(void *, Allocator *)`
51 * below for more details.
52 */
53 virtual bool need_size_for_free() const = 0
54 }
55
56
57 struct Genode::Allocator : Deallocator
58 {
59 /**
60 * Exception type
61 */
62 class Out_of_memory : public Exception{ }
63
64 /**
65 * Destructor
66 */
67 virtual ~Allocator() { }
68
69 /**
70 * Allocate block
71 *
72 * \param size block size to allocate
73 * \param out_addr resulting pointer to the new block,
74 * undefined in the error case
75 * \return true on success
76 */
77 virtual bool alloc(size_t size, void **out_addr) = 0
78
79 /**
80 * Allocate typed block
81 *
82 * This template allocates a typed block returned as a pointer to
83 * a non-void type. By providing this method, we prevent the
84 * compiler from warning us about "dereferencing type-punned
85 * pointer will break strict-aliasing rules".
86 */
87 template <typename T>bool alloc(size_t size, T **out_addr)
88 {
89 void *addr = 0;
90 bool ret = alloc(size, &addr);
91 *out_addr = (T *)
92 return ret
93 }
94
95 /**
96 * Return total amount of backing store consumed by the allocator
97 */
98 virtual size_t consumed() const { return 0}
99
100 /**
101 * Return meta-data overhead per block
102 */
103 virtual size_t overhead(size_t size) const = 0
104
105 /**
106 * Allocate block and signal error as an exception
107 *
108 * \param size block size to allocate
109 * \return pointer to the new block
110 * \throw Out_of_memory
111 */
112 void *alloc(size_t size)
113 {
114 void *result = 0;
115 if (!alloc(size, &result))
116 throw Out_of_memory();
117
118 return result
119 }
120 }
121
122
123 struct Genode::Range_allocator : Allocator
124 {
125 /**
126 * Destructor
127 */
128 virtual ~Range_allocator() { }
129
130 /**
131 * Add free address range to allocator
132 */
133 virtual int add_range(addr_t base, size_t size) = 0
134
135 /**
136 * Remove address range from allocator
137 */
138 virtual int remove_range(addr_t base, size_t size) = 0
139
140 /**
141 * Return value of allocation functons
142 *
143 * `OK` on success, or
144 * `OUT_OF_METADATA` if meta-data allocation failed, or
145 * `RANGE_CONFLICT` if no fitting address range is found
146 */
147 struct Alloc_return
148 {
149 enum Value { OK = 0, OUT_OF_METADATA = -1, RANGE_CONFLICT = -2 }
150 Value const value;
151 Alloc_return(Value value) : value(value){ }
152
153 bool is_ok() const { return value == OK}
154 bool is_error() const { return !is_ok()}
155 }
156
157 /**
158 * Allocate block
159 *
160 * \param size size of new block
161 * \param out_addr start address of new block,
162 * undefined in the error case
163 * \param align alignment of new block specified
164 * as the power of two
165 */
166 virtual Alloc_return alloc_aligned(size_t size, void **out_addr, int align = 0, addr_t from=0, addr_t to = ~0UL) = 0
167
168 /**
169 * Allocate block at address
170 *
171 * \param size size of new block
172 * \param addr desired address of block
173 *
174 * \return `ALLOC_OK` on success, or
175 * `OUT_OF_METADATA` if meta-data allocation failed, or
176 * `RANGE_CONFLICT` if specified range is occupied
177 */
178 virtual Alloc_return alloc_addr(size_t size, addr_t addr) = 0
179
180 /**
181 * Free a previously allocated block
182 *
183 * NOTE: We have to declare the `Allocator::free(void *)` method
184 * here as well to make the compiler happy. Otherwise the C++
185 * overload resolution would not find `Allocator::free(void *)`.
186 */
187 virtual void free(void *addr) = 0
188 virtual void free(void *addr, size_t size) = 0
189
190 /**
191 * Return the sum of available memory
192 *
193 * Note that the returned value is not neccessarily allocatable
194 * because the memory may be fragmented.
195 */
196 virtual size_t avail() const = 0
197
198 /**
199 * Check if address is inside an allocated block
200 *
201 * \param addr address to check
202 *
203 * \return true if address is inside an allocated block, false
204 * otherwise
205 */
206 virtual bool valid_addr(addr_t addr) const = 0
207 }
208
209
210 void *operator new(Genode::size_t, Genode::Allocator *)
211 void *operator new [] (Genode::size_t, Genode::Allocator *)
212
213 void *operator new(Genode::size_t, Genode::Allocator &)
214 void *operator new [] (Genode::size_t, Genode::Allocator &)
215
216
217 /**
218 * Delete operator invoked when an exception occurs during the construction of
219 * a dynamically allocated object
220 *
221 * When an exception occurs during the construction of a dynamically allocated
222 * object, the C++ standard devises the automatic invocation of the global
223 * operator delete. When passing an allocator as argument to the new operator
224 * (the typical case for Genode), the compiler magically calls the operator
225 * delete taking the allocator type as second argument. This is how we end up
226 * here.
227 *
228 * There is one problem though: We get the pointer of the to-be-deleted object
229 * but not its size. But Genode`s `Allocator` interface requires the object
230 * size to be passed as argument to `Allocator::free()`.
231 *
232 * Even though in the general case, we cannot assume all `Allocator`
233 * implementations to remember the size of each allocated object, the commonly
234 * used `Heap`, `Sliced_heap`, `Allocator_avl`, and `Slab` do so and ignore the
235 * size argument. When using either of those allocators, we are fine. Otherwise
236 * we print a warning and pass the zero size argument anyway.
237 *
238 * :Warning: Never use an allocator that depends on the size argument of the
239 * `free()` method for the allocation of objects that may throw exceptions
240 * at their construction time!
241 */
242 void operator delete(void *, Genode::Deallocator *)
243 void operator delete(void *, Genode::Deallocator &)
244
245
246 /**
247 * Destroy object
248 *
249 * For destroying an object, we need to specify the allocator that was used
250 * by the object. Because we cannot pass the allocator directly to the
251 * delete expression, we mimic the expression by using this template
252 * function. The function explicitly calls the object destructor and
253 * operator delete afterwards.
254 *
255 * For details see https://github.com/genodelabs/genode/issues/1030.
256 *
257 * \param T implicit object type
258 *
259 * \param dealloc reference or pointer to allocator from which the object
260 * was allocated
261 * \param obj object to destroy
262 */
263 template <typename T, typename DEALLOC>
264 void Genode::destroy(DEALLOC && dealloc, T *obj)
265 {
266 if (!obj)
267 return
268
269 /* call destructors */
270 obj->~T();
271
272 /*
273 * Free memory at the allocator
274 *
275 * We have to use the delete operator instead of just calling
276 * `dealloc.free` because the `obj` pointer might not always point to the
277 * begin of the allocated block:
278 *
279 * If `T` is the base class of another class `A`, `obj` may refer
280 * to an instance of `A`. In particular when `A` used multiple inheritance
281 * with `T` not being the first inhertited class, the pointer to the actual
282 * object differs from `obj`.
283 *
284 * Given the pointer to the base class `T`, however, the delete operator is
285 * magically (by the means of the information found in the vtable of `T`)
286 * able to determine the actual pointer to the instance of `A` and passes
287 * this pointer to `free`.
288 */
289 operator delete (obj, dealloc);
290 }
291
292 #endif /* _INCLUDE__BASE__ALLOCATOR_H_ */