1/*
2 * Copyright 2017, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(DATA61_BSD)
11 */
12
13/**
14 * @file allocman.h
15 *
16 * @brief The allocman is system for resolving dependencies between allocators for different resources
17 *
18 * Allocations need to go via the allocation manager in order to ensure
19 * the correct watermark levels of resources are maintained. While an
20 * individual manager is free to directly give away resources, if it
21 * calls into the allocation manager then that manager may be recursively
22 * invoked. Performing allocations from the allocation manager is also
23 * the only way to allocate the final watermark resources when memory
24 * becomes exhausted.
25 *
26 * It is generally desirable that a free operation does not have any
27 * allocation calls in it. If an allocator does wish to allocate a
28 * resource when performing a free it must accept that its allocation
29 * function could be called as a result. In a similar manner if your
30 * allocation function frees resources your free function may be recursively
31 * called.
32 *
33 * There are (generally) two different types of allocators. Those that are
34 * linked to an allocation manager, and those that are not. Typically the
35 * only sort of manager you would not want linked to an allocation manager
36 * is a cspace manager (if you are managing a clients cspace). Although you
37 * could also create an untyped manager if you do not want to give clients
38 * untypeds directly, but still want to have a fixed untyped pool reserved
39 * for it.
40 *
41 * Possibility exists for much foot shooting with any allocators. A typical
42 * desire might be to create a sub allocator (such as a cspace manager),
43 * use an already existing allocation manager to back all of its allocations,
44 * and then destroy that cspace manager at some point to release all its resources.
45 * There are no guarantees that this will work. If all requests to the sub allocator
46 * use the same allocation manager to perform book keeping requests, and the
47 * sub allocator is told to free using that same allocation manager then all
48 * should work. But this is strictly up to using your allocators correctly,
49 * and knowing how they work.
50 */
51
52#pragma once
53
54#include <assert.h>
55#include <autoconf.h>
56#include <sel4/types.h>
57#include <allocman/util.h>
58#include <allocman/cspace/cspace.h>
59#include <allocman/mspace/mspace.h>
60#include <allocman/utspace/utspace.h>
61#include <vka/cspacepath_t.h>
62#include <sel4platsupport/timer.h>
63
64/**
65 * Describes a reservation chunk for the memory system.
66 * Used by {@link #allocman_configure_mspace_reserve}
67 */
68struct allocman_mspace_chunk {
69    size_t size;
70    size_t count;
71};
72
73/**
74 * Describes a reservation chunk for the untyped system.
75 * Used by {@link #allocman_configure_utspace_reserve}
76 */
77struct allocman_utspace_chunk {
78    size_t size_bits;
79    seL4_Word type;
80    size_t count;
81};
82
83/**
84 * Internal data structure for describing an untyped allocation in
85 * the reservation system
86 */
87struct allocman_utspace_allocation {
88    seL4_Word cookie;
89    cspacepath_t slot;
90};
91
92struct allocman_freed_mspace_chunk {
93    void *ptr;
94    size_t size;
95};
96
97struct allocman_freed_utspace_chunk {
98    size_t size_bits;
99    seL4_Word cookie;
100};
101
102/**
103 * The allocman itself. This is generally the only type you will need to pass around
104 * to deal with allocation. It is declared in full here so that the compiler is able
105 * to calculate its size so it can be allocated on stacks/globals etc as required
106 */
107typedef struct allocman {
108    /* link to our underlying allocators. some are lazily added. the mspace will always be here,
109     * and have_mspace can be used to check if the allocman is initialized at all */
110    int have_mspace;
111    struct mspace_interface mspace;
112    int have_cspace;
113    struct cspace_interface cspace;
114    int have_utspace;
115    struct utspace_interface utspace;
116
117    /* Flag that tracks whether any alloc/free/other function has been entered yet */
118    int in_operation;
119
120    /* Counts that track re-entry into each specific alloc/free function */
121    size_t cspace_alloc_depth;
122    size_t cspace_free_depth;
123    size_t utspace_alloc_depth;
124    size_t utspace_free_depth;
125    size_t mspace_alloc_depth;
126    size_t mspace_free_depth;
127
128    /* Track whether the watermark is currently refilled so we don't recursively do it */
129    int refilling_watermark;
130    /* Has a watermark resource been used. This is just an optimization */
131    int used_watermark;
132
133    /* track resources that we have not yet been able to free due to circular dependencies */
134    size_t desired_freed_slots;
135    size_t num_freed_slots;
136    cspacepath_t *freed_slots;
137
138    size_t desired_freed_mspace_chunks;
139    size_t num_freed_mspace_chunks;
140    struct allocman_freed_mspace_chunk *freed_mspace_chunks;
141
142    size_t desired_freed_utspace_chunks;
143    size_t num_freed_utspace_chunks;
144    struct allocman_freed_utspace_chunk *freed_utspace_chunks;
145
146    /* cspace watermark resources */
147    size_t desired_cspace_slots;
148    size_t num_cspace_slots;
149    cspacepath_t *cspace_slots;
150
151    /* mspace watermark resources */
152    size_t num_mspace_chunks;
153    struct allocman_mspace_chunk *mspace_chunk;
154    size_t *mspace_chunk_count;
155    void ***mspace_chunks;
156
157    /* utspace watermark resources */
158    size_t num_utspace_chunks;
159    struct allocman_utspace_chunk *utspace_chunk;
160    size_t *utspace_chunk_count;
161    struct allocman_utspace_allocation **utspace_chunks;
162} allocman_t;
163
164/**
165 * Allocates 'real' memory from the allocator
166 *
167 * @param alloc Allocman to allocate from
168 * @param bytes Size in bytes to allocate
169 * @param _error (Optional) set to 0 on success
170 *
171 * @return returns pointer to allocated memory
172 */
173void *allocman_mspace_alloc(allocman_t *alloc, size_t bytes, int *_error);
174
175/**
176 * Frees 'real' memory, as previously allocated by {@link #allocman_mspace_alloc}
177 *
178 * @param alloc Allocman to allocate from
179 * @param ptr Allocated memory (as returned by {@link #allocman_mspace_alloc}
180 * @param bytes Size in bytes of the allocation to free. Allocations cannot be partially freed
181 */
182void allocman_mspace_free(allocman_t *alloc, void *ptr, size_t bytes);
183
184/**
185 * Allocates a cslot from the allocator
186 *
187 * @param alloc Allocman to allocate from
188 * @param slot Stores details of the allocated slot
189 *
190 * @return returns 0 on sucess
191 */
192int allocman_cspace_alloc(allocman_t *alloc, cspacepath_t *slot);
193
194/**
195 * Frees a cslot from the allocator, as previously allocated by {@link #allocman_cspace_alloc}.
196 * To avoid the need to keep cspacepath_t's laying around, it is guaruanteed that
197 * (*slot) == allocman_cspace_make_path(alloc, slot->capPtr). So if needed you can simply store
198 * the capPtr and reconstruct the path before calling free.
199 *
200 * @param alloc Allocman to allocate from
201 * @param slot The slot to free.
202 *
203 * @return returns 0 on sucess
204 */
205void allocman_cspace_free(allocman_t *alloc, const cspacepath_t *slot);
206
207/**
208 * Converts a seL4_CPtr into a cspacepath_t using the cspace attached to the allocman.
209 * If the slot is not valid in that cspace then the return path is completely undefined.
210 *
211 * @param alloc Allocman to allocate from
212 * @param slot The slot to convert
213 *
214 * @return cspacepath_t of the given slot
215 */
216static inline cspacepath_t allocman_cspace_make_path(allocman_t *alloc, seL4_CPtr slot) {
217    assert(alloc->have_cspace);
218    return alloc->cspace.make_path(alloc->cspace.cspace, slot);
219}
220
221/**
222 * Allocates a portion of untyped memory, and retypes it into the desired object for you.
223 *
224 * @param alloc Allocman to allocate from
225 * @param size_bits The size in bits of the memory that will be required to store this object.
226    This is different to seL4_Untyped_Retype for allocating seL4_CapTableObjects
227 * @param type The seL4 type of the object being allocated
228 * @param path A path to a location to put the allocated object (this must be a valid empty slot)
229 * @param paddr The desired physical address of the start of this object. A value of '1' indicates do not care
230 *              as '1' can never be a valid object base address
231 * @param canBeDev Whether this allocation can be satisified from a device region, provided that
232 *  region is known to be actual RAM. Objects from device regions are not initialized (i.e. not zeroed)
233 * @param _error (Optional) set to 0 on success
234 *
235 * @return Returns a cookie that can be used in future to free this allocation
236 */
237seL4_Word allocman_utspace_alloc_at(allocman_t *alloc, size_t size_bits, seL4_Word type, const cspacepath_t *path, uintptr_t paddr, bool canBeDev, int *_error);
238
239/**
240 * Allocates a portion of untyped memory, and retypes it into the desired object for you.
241 *
242 * @param alloc Allocman to allocate from
243 * @param size_bits The size in bits of the memory that will be required to store this object.
244    This is different to seL4_Untyped_Retype for allocating seL4_CapTableObjects
245 * @param type The seL4 type of the object being allocated
246 * @param path A path to a location to put the allocated object (this must be a valid empty slot)
247 * @param canBeDev Whether this allocation can be satisified from a device region, provided that
248 *  region is known to be actual RAM. Objects from device regions are not initialized (i.e. not zeroed)
249 * @param _error (Optional) set to 0 on success
250 *
251 * @return Returns a cookie that can be used in future to free this allocation
252 */
253static inline
254seL4_Word allocman_utspace_alloc(allocman_t *alloc, size_t size_bits, seL4_Word type, const cspacepath_t *path, bool canBeDev, int *_error)
255{
256    return allocman_utspace_alloc_at(alloc, size_bits, type, path, ALLOCMAN_NO_PADDR, canBeDev, _error);
257}
258
259/**
260 * Returns a portion of untyped memory back to the allocator. It is assumed that this
261 * memory is now unused, and every capability to this memory has been deleted (including
262 * the one created by {@link allocman_utspace_alloc}
263 *
264 * @param alloc Allocman to allocate from
265 * @param size_bits The size in bits of the memory that was required to store this object.
266    This is different to seL4_Untyped_Retype for seL4_CapTableObjects
267 * @param cookie The cookie representing this allocation (as returned by {@link allocman_utspace_alloc}
268 */
269void allocman_utspace_free(allocman_t *alloc, seL4_Word cookie, size_t size_bits);
270
271/**
272 * Initialize a new allocman. all it requires is a memory allocator, everything will be boot strapped from it
273 *
274 * @param alloc Allocman structure to initialize
275 * @param mspace Memory allocator. This will be permanently linked to this allocator and must keep existing
276 *
277 * @return returns 0 on success
278 */
279int allocman_create(allocman_t *alloc, struct mspace_interface mspace);
280
281/**
282 * Attempts to fill the reserves of the allocator. This can be used if the underlying allocators have been modified,
283 * for instance by having resources added, or as a way to query the health of the allocman
284 *
285 * @param alloc The allocman to fill reserves of
286 *
287 * @return returns 0 if reserves are full
288 */
289int allocman_fill_reserves(allocman_t *alloc);
290
291/**
292 * Attach an untyped allocator to an allocman.
293 *
294 * @param alloc The allocman to attach to
295 * @param utspace untyped allocator to attach. This wil lbe permanently linked to this allocator and must keep existing
296 *
297 * @return returns 0 on success
298 */
299int allocman_attach_utspace(allocman_t *alloc, struct utspace_interface utspace);
300
301/**
302 * Attach a cspace manager to an allocman.
303 *
304 * @param alloc The allocman to attach to
305 * @param cspace The cspace manager to attach. This wil lbe permanently linked to this allocator and must keep existing
306 *
307 * @return returns 0 on success
308 */
309int allocman_attach_cspace(allocman_t *alloc, struct cspace_interface cspace);
310
311/**
312 * Configure the memory reserve for the allocator
313 *
314 * @param alloc The allocman to configure
315 * @param chunk Description of the memory reserve
316 *
317 * @return returns 0 on success
318 */
319int allocman_configure_mspace_reserve(allocman_t *alloc, struct allocman_mspace_chunk chunk);
320
321/**
322 * Configure the untyped reserve for the allocator
323 *
324 * @param alloc The allocman to configure
325 * @param chunk Description of the untyped reserve
326 *
327 * @return returns 0 on success
328 */
329int allocman_configure_utspace_reserve(allocman_t *alloc, struct allocman_utspace_chunk chunk);
330
331/**
332 * Configure the cspace reserve for the allocator
333 *
334 * @param alloc The allocman to configure
335 * @param num Number of cslots to hold in reserve
336 *
337 * @return returns 0 on success
338 */
339int allocman_configure_cspace_reserve(allocman_t *alloc, size_t num);
340
341/**
342 * Configure the maximul number of freed cptrs we can store. This is required for
343 * scenarios where an allocator cannot handle a recursive call, but we would like to not
344 * leak memory
345 *
346 * @param alloc The allocman to configure
347 * @param num Maximum number of slots to handle
348 *
349 * @return returns 0 on success
350 */
351int allocman_configure_max_freed_slots(allocman_t *alloc, size_t num);
352
353/**
354 * Configure the maximul number of freed memory objects we can store. This is required for
355 * scenarios where an allocator cannot handle a recursive call, but we would like to not
356 * leak memory
357 *
358 * @param alloc The allocman to configure
359 * @param num Maxmimum number of chunks to handle
360 *
361 * @return returns 0 on success
362 */
363int allocman_configure_max_freed_memory_chunks(allocman_t *alloc, size_t num);
364
365/**
366 * Configure the maximul number of freed untyped objects we can store. This is required for
367 * scenarios where an allocator cannot handle a recursive call, but we would like to not
368 * leak memory
369 *
370 * @param alloc The allocman to configure
371 * @param num Maxmimum number of chunks to handle
372 *
373 * @return returns 0 on success
374 */
375int allocman_configure_max_freed_untyped_chunks(allocman_t *alloc, size_t num);
376
377/**
378 * Add additional untyped objects to the underlying untyped manager. This allows additional
379 * resources to be injected after the allocman has started
380 *
381 * @param alloc The allocman to add to
382 * @param num Number of untypeds to add
383 * @param uts Path to each of the untyped to add. untyped is assumed to be at depth 32 from this threads cspace_root
384 * @param size_bits Size, in bits, of each of the untypeds
385 * @param paddr Optional parameter specifying the physical address of each of the untypeds
386 * @param utType The type of all untypeds being added. One of (ALLOCMAN_UT_KERNEL, ALLOCMAN_UT_DEV, ALLOCMAN_UT_DEV_MEM)
387 *
388 * @return returns 0 on success
389 */
390static inline int allocman_utspace_add_uts(allocman_t *alloc, size_t num, const cspacepath_t *uts, size_t *size_bits, uintptr_t *paddr, int utType) {
391    int error;
392    assert(alloc->have_utspace);
393    error = alloc->utspace.add_uts(alloc, alloc->utspace.utspace, num, uts, size_bits, paddr, utType);
394    if (error) {
395        return error;
396    }
397    allocman_fill_reserves(alloc);
398    return 0;
399}
400
401/**
402 * Retrieves the physical address for an allocated untyped object
403 *
404 * @param alloc The allocman to query
405 * @param cookie Cookie to the allocated untyped object
406 * @param size_bits Size of the allocated untyped object
407 *
408 * @return Physical address of the object
409 */
410static inline uintptr_t allocman_utspace_paddr(allocman_t *alloc, seL4_Word cookie, size_t size_bits) {
411    assert(alloc->have_utspace);
412    return alloc->utspace.paddr(alloc->utspace.utspace, cookie, size_bits);
413}
414
415/**
416 * Helper function for adding device untypeds from platform specific timer objects
417 *
418 * @param alloc The allocman to query
419 * @param to struct containing untyped metadata
420 *
421 * @return 0 on success, otherwise error.
422 */
423int allocman_add_untypeds_from_timer_objects(allocman_t *alloc, timer_objects_t *to);
424
425