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#include <autoconf.h>
14#include <sel4/sel4.h>
15#include <string.h>
16#include <allocman/allocman.h>
17#include <allocman/cspace/simple1level.h>
18#include <allocman/cspace/two_level.h>
19#include <allocman/mspace/dual_pool.h>
20#include <allocman/utspace/split.h>
21#include <allocman/bootstrap.h>
22#include <allocman/arch/reservation.h>
23#include <stdio.h>
24#include <vka/capops.h>
25#include <vka/object.h>
26#include <sel4utils/api.h>
27#include <sel4utils/mapping.h>
28#include <sel4utils/process.h>
29#include <simple/simple.h>
30#include <simple/simple_helpers.h>
31#include <utils/arith.h>
32#include <sel4platsupport/pmem.h>
33
34/* configure the choice of boot strapping allocators */
35#define UTMAN split
36
37/*do some nasty macro expansion to get the string substitution to happen how we want */
38#define CON2(a, b,c) a##b##c
39#define CON(a, b,c) CON2(a,b,c)
40#define UTMAN_TYPE CON(utspace_, UTMAN,_t)
41#define UTMAN_CREATE CON(utspace_, UTMAN,_create)
42#define UTMAN_MAKE_INTERFACE CON(utspace_, UTMAN,_make_interface)
43#define UTMAN_ADD_UTS CON(_utspace_, UTMAN,_add_uts)
44
45struct bootstrap_info {
46    allocman_t *alloc;
47    int have_boot_cspace;
48    /* a path to the current boot cnode */
49    cspacepath_t boot_cnode;
50    /* this is prefixed with 'maybe' since we are just using it as some preallocated memory
51     * if a temp bootstrapping cspace is needed. it may not actually be used if a more
52     * complicated cspace is passed in directly by the user */
53    cspace_simple1level_t maybe_boot_cspace;
54    cspace_interface_t boot_cspace;
55    /* if we have switched cspaces, a patch to our old root cnode (based in the current cnode) */
56    cspacepath_t old_cnode;
57    /* a path to the page directory cap, we need this to be able to change the cspace root */
58    cspacepath_t pd;
59    cspacepath_t tcb;
60    int uts_in_current_cspace;
61    size_t num_uts;
62    cspacepath_t *uts;
63    size_t *ut_size_bits;
64    uintptr_t *ut_paddr;
65    bool *ut_isDevice;
66    simple_t *simple;
67};
68
69typedef struct add_untypeds_state {
70    int num_regions;
71    bool region_alloc;
72    pmem_region_t *regions;
73    utspace_split_t split_ut;
74    utspace_interface_t ut_interface;
75} add_untypeds_state_t;
76
77static void bootstrap_free_info(bootstrap_info_t *bs) {
78    if (bs->uts) {
79        allocman_mspace_free(bs->alloc, bs->uts, sizeof(cspacepath_t) * bs->num_uts);
80        allocman_mspace_free(bs->alloc, bs->ut_size_bits, sizeof(size_t) * bs->num_uts);
81    }
82    allocman_mspace_free(bs->alloc, bs, sizeof(bootstrap_info_t));
83}
84
85allocman_t *bootstrap_create_allocman(size_t pool_size, void *pool) {
86    uintptr_t cur_pool = (uintptr_t)pool;
87    uintptr_t pool_top = cur_pool + pool_size;
88    mspace_dual_pool_t *mspace;
89    allocman_t *alloc;
90    int error;
91    /* first align the pool */
92    cur_pool = ALIGN_UP(cur_pool, sizeof(size_t));
93    /* carve off some of the pool for the allocman and memory allocator itself */
94    alloc = (allocman_t*)cur_pool;
95    cur_pool += sizeof(*alloc);
96    mspace = (mspace_dual_pool_t*)cur_pool;
97    cur_pool += sizeof(*mspace);
98    if (cur_pool >= pool_top) {
99        LOG_ERROR("Initial memory pool too small");
100        return NULL;
101    }
102    /* create the allocator */
103    mspace_dual_pool_create(mspace, (struct mspace_fixed_pool_config){(void*)cur_pool, pool_top - cur_pool});
104    error = allocman_create(alloc, mspace_dual_pool_make_interface(mspace));
105    if (error) {
106        return NULL;
107    }
108    return alloc;
109}
110
111int bootstrap_set_boot_cspace(bootstrap_info_t *bs, cspace_interface_t cspace, cspacepath_t root_cnode) {
112    bs->boot_cspace = cspace;
113    bs->boot_cnode = root_cnode;
114    bs->have_boot_cspace = 1;
115    return 0;
116}
117
118static int bootstrap_create_temp_bootinfo_cspace_at(bootstrap_info_t *bs, seL4_BootInfo *bi, seL4_CPtr root_cnode) {
119    /* create a cspace to represent the bootinfo cspace. */
120    cspace_simple1level_create(&bs->maybe_boot_cspace, (struct cspace_simple1level_config){
121        .cnode = root_cnode,
122        .cnode_size_bits = bi->initThreadCNodeSizeBits,
123        .cnode_guard_bits = seL4_WordBits - bi->initThreadCNodeSizeBits,
124        .first_slot = bi->empty.start,
125        .end_slot = bi->empty.end - 1
126    });
127    return bootstrap_set_boot_cspace(bs,
128                                     cspace_simple1level_make_interface(
129                                        &bs->maybe_boot_cspace),
130                                        _cspace_simple1level_make_path(&bs->maybe_boot_cspace, root_cnode));
131}
132
133static int bootstrap_create_temp_bootinfo_cspace(bootstrap_info_t *bs, seL4_BootInfo *bi) {
134    return bootstrap_create_temp_bootinfo_cspace_at(bs, bi, seL4_CapInitThreadCNode);
135}
136
137static bootstrap_info_t *_create_info(allocman_t *alloc) {
138    int error;
139    bootstrap_info_t *bs = allocman_mspace_alloc(alloc, sizeof(bootstrap_info_t), &error);
140    if (error) {
141        LOG_ERROR("Failed to allocate bootstrap_info");
142        return NULL;
143    }
144    memset(bs, 0, sizeof(bootstrap_info_t));
145    bs->alloc = alloc;
146    /* currently have no untypeds so this is true */
147    bs->uts_in_current_cspace = 1;
148    return bs;
149}
150
151static int _add_ut(bootstrap_info_t *bs, cspacepath_t slot, size_t size_bits, uintptr_t paddr, bool isDevice) {
152    cspacepath_t *new_uts;
153    size_t *new_size_bits;
154    uintptr_t *new_paddr;
155    bool *new_isDevice;
156    int error;
157    new_uts = allocman_mspace_alloc(bs->alloc, sizeof(cspacepath_t) * (bs->num_uts + 1), &error);
158    if (error) {
159        LOG_ERROR("Failed to allocate space for untypeds (new_uts)");
160        return error;
161    }
162    new_size_bits = allocman_mspace_alloc(bs->alloc, sizeof(size_t) * (bs->num_uts + 1), &error);
163    if (error) {
164        LOG_ERROR("Failed to allocate space for untypeds (new_size_bits)");
165        return error;
166    }
167    new_paddr = allocman_mspace_alloc(bs->alloc, sizeof(uintptr_t) * (bs->num_uts + 1), &error);
168    if (error) {
169        LOG_ERROR("Failed to allocate space for untypeds (new_paddr)");
170        return error;
171    }
172    new_isDevice = allocman_mspace_alloc(bs->alloc, sizeof(bool) * (bs->num_uts + 1), &error);
173    if (error) {
174        ZF_LOGE("Failed to allocate space for untypeds (new_isDevice)");
175        return error;
176    }
177    if (bs->uts) {
178        memcpy(new_uts, bs->uts, sizeof(cspacepath_t) * bs->num_uts);
179        memcpy(new_size_bits, bs->ut_size_bits, sizeof(size_t) * bs->num_uts);
180        memcpy(new_paddr, bs->ut_paddr, sizeof(uintptr_t) * bs->num_uts);
181        memcpy(new_isDevice, bs->ut_isDevice, sizeof(bool) * bs->num_uts);
182        allocman_mspace_free(bs->alloc, bs->uts, sizeof(cspacepath_t) * bs->num_uts);
183        allocman_mspace_free(bs->alloc, bs->ut_size_bits, sizeof(size_t) * bs->num_uts);
184        allocman_mspace_free(bs->alloc, bs->ut_paddr, sizeof(uintptr_t) * bs->num_uts);
185        allocman_mspace_free(bs->alloc, bs->ut_isDevice, sizeof(bool) * bs->num_uts);
186    }
187    new_uts[bs->num_uts] = slot;
188    new_size_bits[bs->num_uts] = size_bits;
189    new_paddr[bs->num_uts] = paddr;
190    new_isDevice[bs->num_uts] = isDevice;
191    bs->uts = new_uts;
192    bs->ut_size_bits = new_size_bits;
193    bs->ut_paddr = new_paddr;
194    bs->ut_isDevice = new_isDevice;
195    bs->num_uts++;
196    return 0;
197}
198
199int bootstrap_add_untypeds(bootstrap_info_t *bs, size_t num, const cspacepath_t *uts, size_t *size_bits, uintptr_t *paddr, bool isDevice) {
200    size_t i;
201    int error;
202    for (i = 0; i < num; i++) {
203        error = _add_ut(bs, uts[i], size_bits[i], paddr ? paddr[i] : ALLOCMAN_NO_PADDR, isDevice);
204        if (error) {
205            return error;
206        }
207    }
208    return 0;
209}
210
211int bootstrap_add_untypeds_from_bootinfo(bootstrap_info_t *bs, seL4_BootInfo *bi) {
212    int error;
213    seL4_CPtr i;
214    /* if we do not have a boot cspace, or we have added some uts that aren't in the
215     * current space then just bail */
216    if (!bs->have_boot_cspace || (bs->uts && !bs->uts_in_current_cspace)) {
217        return 1;
218    }
219    for (i = bi->untyped.start; i < bi->untyped.end; i++) {
220        size_t index = i - bi->untyped.start;
221        cspacepath_t slot = bs->boot_cspace.make_path(bs->boot_cspace.cspace, i);
222        size_t size_bits = bi->untypedList[index].sizeBits;
223        uintptr_t paddr = bi->untypedList[index].paddr;
224        error = _add_ut(bs, slot, size_bits, paddr, bi->untypedList[index].isDevice);
225        if (error) {
226            return error;
227        }
228    }
229    /* we assume this is true here */
230    bs->uts_in_current_cspace = 1;
231    return 0;
232}
233
234static int bootstrap_add_untypeds_from_simple(bootstrap_info_t *bs, simple_t *simple) {
235    int error;
236    int i;
237    /* if we do not have a boot cspace, or we have added some uts that aren't in the
238     * current space then just bail */
239    if (!bs->have_boot_cspace || (bs->uts && !bs->uts_in_current_cspace)) {
240        return 1;
241    }
242    for (i = 0; i < simple_get_untyped_count(simple); i++) {
243        size_t size_bits;
244        uintptr_t paddr;
245        bool device;
246        cspacepath_t slot = bs->boot_cspace.make_path(bs->boot_cspace.cspace,
247                                                      simple_get_nth_untyped(simple, i, &size_bits, &paddr, &device));
248        error = _add_ut(bs, slot, size_bits, paddr, device);
249        if (error) {
250            return error;
251        }
252    }
253    /* we assume this is true here */
254    bs->uts_in_current_cspace = 1;
255    return 0;
256}
257
258static int _remove_ut(bootstrap_info_t *bs, size_t i) {
259    cspacepath_t *new_uts = NULL;
260    size_t *new_size_bits = NULL;
261    uintptr_t *new_paddr = NULL;
262    bool *new_isDevice = NULL;
263    int error;
264    if (bs->num_uts == 0) {
265        /* what? */
266        return 1;
267    }
268    /* if there is only 1 then we will just skip straight to freeing the memory and setting
269     * the arrays to NULL */
270    if (bs->num_uts > 1) {
271        new_uts = allocman_mspace_alloc(bs->alloc, sizeof(cspacepath_t) * (bs->num_uts - 1), &error);
272        if (error) {
273            return error;
274        }
275        new_size_bits = allocman_mspace_alloc(bs->alloc, sizeof(size_t) * (bs->num_uts - 1), & error);
276        if (error) {
277            return error;
278        }
279        new_paddr = allocman_mspace_alloc(bs->alloc, sizeof(uintptr_t) * (bs->num_uts - 1), & error);
280        if (error) {
281            return error;
282        }
283        new_isDevice = allocman_mspace_alloc(bs->alloc, sizeof(bool) * (bs->num_uts - 1), &error);
284        if (error) {
285            return error;
286        }
287        memcpy(&new_uts[0], &bs->uts[0], i * sizeof(cspacepath_t));
288        memcpy(&new_uts[i], &bs->uts[i + 1], (bs->num_uts - i - 1) * sizeof(cspacepath_t));
289        memcpy(&new_size_bits[0], &bs->ut_size_bits[0], i * sizeof(size_t));
290        memcpy(&new_size_bits[i], &bs->ut_size_bits[i + 1], (bs->num_uts - i - 1) * sizeof(size_t));
291        memcpy(&new_paddr[0], &bs->ut_paddr[0], i * sizeof(uintptr_t));
292        memcpy(&new_paddr[i], &bs->ut_paddr[i + 1], (bs->num_uts - i - 1) * sizeof(uintptr_t));
293        memcpy(&new_isDevice[0], &bs->ut_isDevice[0], i * sizeof(bool));
294        memcpy(&new_isDevice[i], &bs->ut_isDevice[i + 1], (bs->num_uts - i - 1) * sizeof(bool));
295    }
296    allocman_mspace_free(bs->alloc, bs->uts, sizeof(cspacepath_t) * (bs->num_uts));
297    allocman_mspace_free(bs->alloc, bs->ut_size_bits, sizeof(size_t) * (bs->num_uts));
298    allocman_mspace_free(bs->alloc, bs->ut_paddr, sizeof(uintptr_t) * (bs->num_uts));
299    allocman_mspace_free(bs->alloc, bs->ut_isDevice, sizeof(bool) * (bs->num_uts));
300    bs->uts = new_uts;
301    bs->ut_size_bits = new_size_bits;
302    bs->ut_paddr = new_paddr;
303    bs->ut_isDevice = new_isDevice;
304    bs->num_uts--;
305    return 0;
306}
307
308static int _split_ut(bootstrap_info_t *bs, cspacepath_t ut, cspacepath_t p1, cspacepath_t p2, size_t size) {
309    int error;
310    error = seL4_Untyped_Retype(ut.capPtr, seL4_UntypedObject, size, p1.root, p1.dest, p1.destDepth, p1.offset, 1);
311    if (error != seL4_NoError) {
312        return 1;
313    }
314    error = seL4_Untyped_Retype(ut.capPtr, seL4_UntypedObject, size, p2.root, p2.dest, p2.destDepth, p2.offset, 1);
315    if (error != seL4_NoError) {
316        return 1;
317    }
318    return 0;
319}
320
321static int _retype_cnode(bootstrap_info_t *bs, cspacepath_t ut, cspacepath_t cnode, seL4_Word sel4_size) {
322    int error;
323    error = seL4_Untyped_Retype(ut.capPtr, seL4_CapTableObject, sel4_size,
324                                cnode.root, cnode.dest, cnode.destDepth, cnode.offset, 1);
325    if (error != seL4_NoError) {
326        return 1;
327    }
328    return 0;
329}
330
331static int bootstrap_allocate_cnode(bootstrap_info_t *bs, size_t size, cspacepath_t *slot) {
332    size_t ut_size;
333    int i;
334    int best = -1;
335    uintptr_t best_paddr;
336    size_t best_size;
337    bool best_isDevice;
338    int error;
339    cspacepath_t best_path;
340    if (!bs->have_boot_cspace) {
341        return 1;
342    }
343    ut_size = size + seL4_SlotBits;
344    /* find the smallest untyped to allocate from */
345    for (i = 0; i < bs->num_uts; i++) {
346        if (bs->ut_size_bits[i] >= ut_size && ( best == -1 || (bs->ut_size_bits[best] > bs->ut_size_bits[i]) ) && !bs->ut_isDevice[i]) {
347            best = i;
348        }
349    }
350    if (best == -1) {
351        return 1;
352    }
353    best_size = bs->ut_size_bits[best];
354    best_path = bs->uts[best];
355    best_paddr = bs->ut_paddr[best];
356    best_isDevice = bs->ut_isDevice[best];
357    /* we searched for a non device one, but make sure here */
358    assert(!best_isDevice);
359    error = _remove_ut(bs, best);
360    if (error) {
361        return error;
362    }
363    while(best_size > ut_size) {
364        /* split the untyped in half */
365        cspacepath_t slot1, slot2;
366        size_t temp_size;
367        error = bs->boot_cspace.alloc(bs->alloc, bs->boot_cspace.cspace, &slot1);
368        if (error) {
369            return error;
370        }
371        error = bs->boot_cspace.alloc(bs->alloc, bs->boot_cspace.cspace, &slot2);
372        if (error) {
373            return error;
374        }
375        error = _split_ut(bs, best_path, slot1, slot2, best_size - 1);
376        if (error) {
377            return error;
378        }
379        /* put one half back in the uts list, and then we keep going with the other one. for the purposes
380         * of book keeping physical addresses it is important to note that we are putting the
381         * FIRST half back in */
382        temp_size = best_size - 1;
383        error = bootstrap_add_untypeds(bs, 1, &slot1, &temp_size, &best_paddr, best_isDevice);
384        if (error) {
385            return error;
386        }
387        best_size--;
388        best_paddr = best_paddr == ALLOCMAN_NO_PADDR ? best_paddr : best_paddr + BIT(best_size);
389        best_path = slot2;
390    }
391    error = bs->boot_cspace.alloc(bs->alloc, bs->boot_cspace.cspace, slot);
392    if (error) {
393        return error;
394    }
395    error = _retype_cnode(bs, best_path, *slot, size);
396    return error;
397}
398
399static int bootstrap_use_current_cspace(bootstrap_info_t *bs, cspace_interface_t cspace) {
400    int error;
401    error = allocman_attach_cspace(bs->alloc, cspace);
402    if (error) {
403        return error;
404    }
405    bs->boot_cspace = cspace;
406    bs->have_boot_cspace = 1;
407    return 0;
408}
409
410static int bootstrap_use_current_1level_cspace(bootstrap_info_t *bs, seL4_CPtr cnode, size_t size_bits, size_t start_free_index, size_t end_free_index) {
411    cspace_single_level_t *cspace;
412    int error;
413    cspace = allocman_mspace_alloc(bs->alloc, sizeof(*cspace), &error);
414    if (error) {
415        LOG_ERROR("Initial memory pool too small to allocate cspace allocator");
416        return error;
417    }
418    error = cspace_single_level_create(bs->alloc, cspace, (struct cspace_single_level_config){
419        .cnode = cnode,
420        .cnode_size_bits = size_bits,
421        .cnode_guard_bits = seL4_WordBits - size_bits,
422        .first_slot = start_free_index,
423        .end_slot = end_free_index
424    });
425    if (error) {
426        LOG_ERROR("Failed to initialize cspace allocator");
427        return error;
428    }
429    error = bootstrap_use_current_cspace(bs, cspace_single_level_make_interface(cspace));
430    if (error) {
431        LOG_ERROR("Failed to bootstrap current cspace");
432    }
433    return error;
434}
435
436static int bootstrap_new_1level_cspace(bootstrap_info_t *bs, int size) {
437    cspacepath_t node;
438    cspace_single_level_t *cspace;
439    int error;
440    /* create the actual cnodes */
441    error = bootstrap_allocate_cnode(bs, size, &node);
442    if (error) {
443        return error;
444    }
445    /* put a cap back to ourselves */
446    seL4_CPtr new_cnode = SEL4UTILS_CNODE_SLOT;
447    error = seL4_CNode_Mint(
448        node.capPtr, new_cnode, size,
449        node.root, node.capPtr, node.capDepth,
450        seL4_AllRights, api_make_guard_skip_word(seL4_WordBits - size));
451    if (error != seL4_NoError) {
452        return 1;
453    }
454    /* put our old cnode into the final slot in our cnode */
455    seL4_CPtr old_cnode_slot = BIT(size) - 1u;
456    error = seL4_CNode_Copy(
457        node.capPtr, old_cnode_slot, size,
458        bs->boot_cnode.root, bs->boot_cnode.capPtr, bs->boot_cnode.capDepth,
459        seL4_AllRights);
460    if (error != seL4_NoError) {
461        return 1;
462    }
463    /* now we can call set space */
464    error = api_tcb_set_space(bs->tcb.capPtr, 0,
465                node.capPtr,
466                api_make_guard_skip_word(seL4_WordBits - size),
467                bs->pd.capPtr, seL4_NilData);
468    if (error != seL4_NoError) {
469        return 1;
470    }
471    /* create the cspace now */
472    cspace = allocman_mspace_alloc(bs->alloc, sizeof(*cspace), &error);
473    if (error) {
474        return error;
475    }
476    error = cspace_single_level_create(bs->alloc, cspace, (struct cspace_single_level_config){
477        .cnode = new_cnode,
478        .cnode_size_bits = size,
479        .cnode_guard_bits = seL4_WordBits - size,
480        .first_slot = simple_last_valid_cap(bs->simple) + 1,
481        .end_slot = BIT(size) - 2u}); // subtract 2 as the last slot is occupied
482    if (error) {
483        return error;
484    }
485    error = allocman_attach_cspace(bs->alloc, cspace_single_level_make_interface(cspace));
486    if (error) {
487        return error;
488    }
489    /* construct path to our old cnode */
490    bs->old_cnode = allocman_cspace_make_path(bs->alloc, old_cnode_slot);
491    /* update where our current booting cnode is */
492    bs->boot_cnode = allocman_cspace_make_path(bs->alloc, new_cnode);
493    /* any untypeds are no longer valid */
494    bs->uts_in_current_cspace = 0;
495    return 0;
496}
497int bootstrap_transfer_caps_simple(bootstrap_info_t *bs, simple_t *simple, int levels) {
498
499    int error;
500    size_t i;
501    size_t cap_count = simple_get_cap_count(simple);
502    seL4_CPtr cnode = simple_get_cnode(simple);
503
504    for(i = 0ul; i < cap_count; i++) {
505        seL4_CPtr pos = simple_get_nth_cap(simple,i);
506
507        /* Because we are going to switch root cnodes don't move the old cnode cap
508         * The cap to the real root cnode is already there.
509         * Also don't move any untyped caps, the untyped allocator is looking
510         * after those now.
511         */
512        if (pos == cnode || simple_is_untyped_cap(simple, pos)) continue;
513
514        cspacepath_t slot;
515        if (levels == 1) {
516            slot = _cspace_single_level_make_path(bs->alloc->cspace.cspace, pos);
517        } else if (levels == 2) {
518            slot = _cspace_two_level_make_path(bs->alloc->cspace.cspace, pos);
519        } else {
520            ZF_LOGE("Too many cspace levels!\n");
521            return 1;
522        }
523
524        if(pos == bs->tcb.capPtr || pos == bs->pd.capPtr) {
525            error = seL4_CNode_Copy(slot.root, pos, slot.capDepth,
526                    bs->old_cnode.capPtr, pos, bs->old_cnode.capDepth,
527                    seL4_AllRights);
528        } else {
529            error = seL4_CNode_Move(
530                    slot.root, pos, slot.capDepth,
531                    bs->old_cnode.capPtr, pos, bs->old_cnode.capDepth);
532        }
533        if (error != seL4_NoError) {
534            return 1;
535        }
536    }
537    return 0;
538}
539
540static int bootstrap_new_2level_cspace(bootstrap_info_t *bs, size_t l1size, size_t l2size, seL4_CPtr cnode, seL4_CPtr old_cnode, size_t total_caps) {
541    cspacepath_t l1node;
542    cspacepath_t l2node;
543    cspace_two_level_t *cspace;
544    int error;
545    size_t i;
546    seL4_CPtr l2nodeforbackpointer = 0;
547    seL4_CPtr last_cap = MAX(cnode, old_cnode);
548    /* create the actual cnodes */
549    error = bootstrap_allocate_cnode(bs, l1size, &l1node);
550    if (error) {
551        return error;
552    }
553    error = bootstrap_allocate_cnode(bs, l2size, &l2node);
554    if (error) {
555        return error;
556    }
557    /* put a cap back to the level 1 in the level 2. That way we have a cap at depth 32 to our cspace */
558    error = seL4_CNode_Mint(
559        l2node.capPtr, cnode, l2size,
560        l1node.root, l1node.capPtr, l1node.capDepth,
561        seL4_AllRights, api_make_guard_skip_word(seL4_WordBits - l1size - l2size));
562    if (error != seL4_NoError) {
563        return 1;
564    }
565
566    for(i = 0; i < (total_caps / BIT(l2size)) + 1; i++) {
567        if(i != 0) {
568            error = bootstrap_allocate_cnode(bs, l2size, &l2node);
569            if(error) {
570                return error;
571            }
572        }
573        /* see if this is the l2 node we will need for installing
574         * the pointer back to our old cnode */
575        if (old_cnode / BIT(l2size) == i) {
576            l2nodeforbackpointer = l2node.capPtr;
577        }
578        /* put the level 2 slot into the level 1 */
579        error = seL4_CNode_Copy(
580            l1node.capPtr, i, l1size,
581            l2node.root, l2node.capPtr, l2node.capDepth,
582            seL4_AllRights);
583        if (error != seL4_NoError) {
584            return 1;
585        }
586
587    }
588    size_t end_existing_index = i;
589    /* put our old cnode into a slot in the level 2 one */
590    error = seL4_CNode_Copy(
591        l2nodeforbackpointer, old_cnode & MASK(l2size), l2size,
592        bs->boot_cnode.root, bs->boot_cnode.capPtr,
593        bs->boot_cnode.capDepth, seL4_AllRights);
594    if (error != seL4_NoError) {
595        return 1;
596    }
597    /* now we can call set space */
598    error = api_tcb_set_space(bs->tcb.capPtr, 0,
599                l1node.capPtr,
600                api_make_guard_skip_word(seL4_WordBits - l1size - l2size),
601                bs->pd.capPtr, seL4_NilData);
602    if (error != seL4_NoError) {
603        return 1;
604    }
605    /* create the cspace now */
606    cspace = allocman_mspace_alloc(bs->alloc, sizeof(*cspace), &error);
607    if (error) {
608        return error;
609    }
610    error = cspace_two_level_create(bs->alloc, cspace, (struct cspace_two_level_config){
611        .cnode = cnode,
612        .cnode_size_bits = l1size,
613        .cnode_guard_bits = seL4_WordBits - l1size - l2size,
614        .first_slot = 0,
615        .end_slot = BIT(l1size),
616        .level_two_bits = l2size,
617        .start_existing_index = 0,
618        .end_existing_index = end_existing_index,
619        .start_existing_slot = 0,
620        .end_existing_slot = last_cap + 1});
621    if (error) {
622        return error;
623    }
624    error = allocman_attach_cspace(bs->alloc, cspace_two_level_make_interface(cspace));
625    if (error) {
626        return error;
627    }
628    /* construct path to our old cnode */
629    bs->old_cnode = _cspace_two_level_make_path(cspace, old_cnode);
630    /* update where our current booting cnode is */
631    bs->boot_cnode = _cspace_two_level_make_path(cspace, cnode);
632    /* any untypeds are no longer valid */
633    bs->uts_in_current_cspace = 0;
634    return 0;
635}
636
637static void bootstrap_update_untypeds(bootstrap_info_t *bs) {
638    int i;
639    for (i = 0; i < bs->num_uts; i++) {
640        bs->uts[i].root = bs->old_cnode.capPtr;
641    }
642}
643
644static void bootstrap_set_pd_tcb_bootinfo(bootstrap_info_t *bs) {
645    bs->pd = bs->boot_cspace.make_path(bs->boot_cspace.cspace, seL4_CapInitThreadPD);
646    bs->tcb = bs->boot_cspace.make_path(bs->boot_cspace.cspace, seL4_CapInitThreadTCB);
647}
648
649static void bootstrap_set_pd_tcb(bootstrap_info_t *bs, cspacepath_t pd, cspacepath_t tcb) {
650    bs->pd = pd;
651    bs->tcb = tcb;
652}
653
654static int bootstrap_move_untypeds(bootstrap_info_t *bs) {
655    int i;
656    int error;
657    for (i = 0; i < bs->num_uts; i++) {
658        cspacepath_t slot;
659        error = allocman_cspace_alloc(bs->alloc, &slot);
660        if (error) {
661            return error;
662        }
663        error = vka_cnode_move(&slot, &bs->uts[i]);
664        if (error != seL4_NoError) {
665            return 1;
666        }
667        bs->uts[i] = slot;
668    }
669    bs->uts_in_current_cspace = 1;
670    return 0;
671}
672
673static int bootstrap_create_utspace(bootstrap_info_t *bs) {
674    int error;
675    int i;
676    UTMAN_TYPE *utspace;
677    utspace = allocman_mspace_alloc(bs->alloc, sizeof(*utspace), &error);
678    if (error) {
679        LOG_ERROR("Initial memory pool too small to allocate untyped allocator");
680        return error;
681    }
682    UTMAN_CREATE(utspace);
683    /* we can shove it in the allocman before we start telling it about its untypeds */
684    error = allocman_attach_utspace(bs->alloc, UTMAN_MAKE_INTERFACE(utspace));
685    if (error) {
686        return error;
687    }
688
689    for (i = 0; i < bs->num_uts; i++) {
690        error = UTMAN_ADD_UTS(bs->alloc, utspace, 1, &bs->uts[i], &bs->ut_size_bits[i], &bs->ut_paddr[i], bs->ut_isDevice[i] ? ALLOCMAN_UT_DEV : ALLOCMAN_UT_KERNEL);
691        if (error) {
692            LOG_ERROR("Failed to add untypeds to untyped allocator");
693            return error;
694        }
695    }
696    return 0;
697}
698
699bootstrap_info_t *bootstrap_create_info(size_t pool_size, void *pool) {
700    allocman_t *alloc;
701    bootstrap_info_t *info;
702    /* bootstrap an allocman from the pool */
703    alloc = bootstrap_create_allocman(pool_size, pool);
704    if (!alloc) {
705        return NULL;
706    }
707    /* create the bootstrapping info */
708    info = _create_info(alloc);
709    if (!info) {
710        return NULL;
711    }
712    return info;
713}
714
715static int _slot_memory_reservations(allocman_t *alloc) {
716    int error;
717    /* these numbers are pulled completely out of my arse (although given I wrote
718     * the allocators my gut feeling should have some weight...) */
719    error = allocman_configure_max_freed_slots(alloc, 10);
720    if (error) {
721        return error;
722    }
723    error = allocman_configure_max_freed_memory_chunks(alloc, 20);
724    if (error) {
725        return error;
726    }
727    error = allocman_configure_max_freed_untyped_chunks(alloc, 10);
728    if (error) {
729        return error;
730    }
731    error = allocman_configure_cspace_reserve(alloc, 30);
732    if (error) {
733        return error;
734    }
735    return 0;
736}
737
738static int _cnode_reservation(allocman_t *alloc, size_t cnode_size) {
739    /* assume one extra level 2 cnode is all we need to keep around */
740    return allocman_configure_utspace_reserve(alloc, (struct allocman_utspace_chunk) {cnode_size + seL4_SlotBits, seL4_CapTableObject, 1});
741}
742
743allocman_t *bootstrap_use_current_1level(seL4_CPtr root_cnode, size_t cnode_size, seL4_CPtr start_slot, seL4_CPtr end_slot, size_t pool_size, void *pool) {
744    allocman_t *alloc;
745    int error;
746    bootstrap_info_t *info;
747    /* create the bootstrapping info */
748    info = bootstrap_create_info(pool_size, pool);
749    if (!info) {
750        LOG_ERROR("Failed to create bootstrap info");
751        return NULL;
752    }
753    /* we will use the current cspace */
754    error = bootstrap_use_current_1level_cspace(info, root_cnode, cnode_size, start_slot, end_slot);
755    if (error) {
756        LOG_ERROR("Failed to boostrap in the current cspace");
757        return NULL;
758    }
759    /* set the pd and tcb */
760    bootstrap_set_pd_tcb_bootinfo(info);
761    /* can now create untyped allocator */
762    error = bootstrap_create_utspace(info);
763    if (error) {
764        LOG_ERROR("Failed to create the untyped allocator");
765        return NULL;
766    }
767    /* add normal slot reservations as well as reservations for memory system. No cnode
768     * reservations since using current cnode */
769    error = _slot_memory_reservations(info->alloc);
770    if (error) {
771        LOG_ERROR("Failed to add slot and memory reservations");
772        return NULL;
773    }
774    /* all done */
775    alloc = info->alloc;
776    bootstrap_free_info(info);
777    return alloc;
778}
779
780static allocman_t *_post_new_cspace_common(bootstrap_info_t *info, cspacepath_t *oldroot) {
781    allocman_t *alloc;
782    int error;
783    /* update any resources */
784    bootstrap_update_untypeds(info);
785    /* move untypeds into new cspace */
786    error = bootstrap_move_untypeds(info);
787    if (error) {
788        return NULL;
789    }
790    /* can now create untyped allocator */
791    error = bootstrap_create_utspace(info);
792    if (error) {
793        return NULL;
794    }
795    /* add normal slot reservations as well as reservations for memory system. We do not
796     * know the cspace geometry, so cannot add cnode reservations */
797    error = _slot_memory_reservations(info->alloc);
798    if (error) {
799        return NULL;
800    }
801    /* give the location of the cap back to the original root cnode */
802    if (oldroot) {
803        *oldroot = info->old_cnode;
804    }
805    /* all done */
806    alloc = info->alloc;
807    return alloc;
808}
809
810/* this does not free the underlying 'info' */
811static allocman_t *_bootstrap_new_level1(bootstrap_info_t *info, size_t cnode_size, cspacepath_t tcb, cspacepath_t pd, cspacepath_t *oldroot) {
812    int error;
813    /* set the pd and tcb */
814    bootstrap_set_pd_tcb(info, pd, tcb);
815    /* create a new one level cspace and switch to it */
816    error = bootstrap_new_1level_cspace(info, cnode_size);
817    if (error) {
818        return NULL;
819    }
820    /* perform post cspace switch tasks (move untypeds and finish creating the allocman) */
821    return _post_new_cspace_common(info, oldroot);
822}
823
824/* this does not free the underlying 'info' */
825static allocman_t *_bootstrap_new_level2(bootstrap_info_t *info, size_t l1size, size_t l2size, cspacepath_t tcb, cspacepath_t pd, cspacepath_t *oldroot) {
826    int error;
827    allocman_t *alloc;
828    /* set the pd and tcb */
829    bootstrap_set_pd_tcb(info, pd, tcb);
830    /* create a new one level cspace and switch to it
831     * place the cap to the root cnode at slot 2 and the cap to the old cnode at slot 1
832     */
833    size_t total_caps = info->num_uts;
834    if(info->have_boot_cspace) {
835        cspacepath_t to_slot;
836        info->boot_cspace.alloc(info->alloc, info->boot_cspace.cspace, &to_slot);
837        total_caps += MAX(2, to_slot.capPtr);
838        error = bootstrap_new_2level_cspace(info, l1size, l2size, 2, to_slot.capPtr, total_caps);
839    } else {
840        total_caps += 2;
841        error = bootstrap_new_2level_cspace(info, l1size, l2size, 2, 1, total_caps);
842    }
843    if (error) {
844        return NULL;
845    }
846    /* perform post cspace switch tasks (move untypeds and finish creating the allocman) */
847    alloc = _post_new_cspace_common(info, oldroot);
848    if (!alloc) {
849        return NULL;
850    }
851    /* add reservations for a second level cnode */
852    error = _cnode_reservation(alloc, l2size);
853    if (error) {
854        return NULL;
855    }
856    return alloc;
857}
858
859allocman_t *bootstrap_new_1level(bootstrap_info_t *info, size_t cnode_size, cspacepath_t tcb, cspacepath_t pd, cspacepath_t *oldroot) {
860    allocman_t *alloc = _bootstrap_new_level1(info, cnode_size, tcb, pd, oldroot);
861    if (!alloc) {
862        return NULL;
863    }
864    bootstrap_free_info(info);
865    return alloc;
866}
867
868allocman_t *bootstrap_new_2level(bootstrap_info_t *info, size_t l1size, size_t l2size, cspacepath_t tcb, cspacepath_t pd, cspacepath_t *oldroot) {
869    allocman_t *alloc = _bootstrap_new_level2(info, l1size, l2size, tcb, pd, oldroot);
870    if (!alloc) {
871        return NULL;
872    }
873    bootstrap_free_info(info);
874    return alloc;
875}
876
877static bootstrap_info_t *_start_new_from_bootinfo(seL4_BootInfo *bi, size_t pool_size, void *pool) {
878    int error;
879    bootstrap_info_t *info;
880    /* create the bootstrapping info */
881    info = bootstrap_create_info(pool_size, pool);
882    if (!info) {
883        return NULL;
884    }
885    /* we will use the current cspace (as descrbied by bootinfo) temporarily for bootstrapping */
886    error = bootstrap_create_temp_bootinfo_cspace(info, bi);
887    if (error) {
888        return NULL;
889    }
890    /* give all the bootinfo untypeds */
891    error = bootstrap_add_untypeds_from_bootinfo(info, bi);
892    if (error) {
893        return NULL;
894    }
895    return info;
896}
897
898static allocman_t *_new_from_bootinfo_common(bootstrap_info_t *info, cspace_simple1level_t **old_cspace) {
899    int error;
900    allocman_t *alloc;
901    /* allocate old cspace if desired */
902    if (old_cspace) {
903        *old_cspace = allocman_mspace_alloc(info->alloc, sizeof(**old_cspace), &error);
904        if (error) {
905            return NULL;
906        }
907        /* we are relying on internal knowledge of this allocator to know that this copy operation is okay */
908        **old_cspace = info->maybe_boot_cspace;
909    }
910    /* all done */
911    alloc = info->alloc;
912    bootstrap_free_info(info);
913    return alloc;
914}
915
916allocman_t *bootstrap_new_1level_bootinfo(seL4_BootInfo *bi, size_t cnode_size, size_t pool_size, void *pool, cspace_simple1level_t **old_cspace) {
917    allocman_t *alloc;
918    bootstrap_info_t *info;
919    /* create the bootstrapping info and fill in as much from bootinfo as we can */
920    info = _start_new_from_bootinfo(bi, pool_size, pool);
921    if (!info) {
922        return NULL;
923    }
924    /* create cspace, switch to it and finish creating the allocman */
925    alloc = _bootstrap_new_level1(info,
926                                  cnode_size,
927                                  info->boot_cspace.make_path(info->boot_cspace.cspace, seL4_CapInitThreadTCB),
928                                  info->boot_cspace.make_path(info->boot_cspace.cspace, seL4_CapInitThreadPD),
929                                  NULL);
930    if (!alloc) {
931        return NULL;
932    }
933    /* do common cleanup */
934    return _new_from_bootinfo_common(info, old_cspace);
935}
936
937allocman_t *bootstrap_new_2level_bootinfo(seL4_BootInfo *bi, size_t l1size, size_t l2size, size_t pool_size, void *pool, cspace_simple1level_t **old_cspace) {
938    allocman_t *alloc;
939    bootstrap_info_t *info;
940    /* create the bootstrapping info and fill in as much from bootinfo as we can */
941    info = _start_new_from_bootinfo(bi, pool_size, pool);
942    if (!info) {
943        return NULL;
944    }
945    /* create cspace, switch to it and finish creating the allocman */
946    alloc = _bootstrap_new_level2(info,
947                                  l1size,
948                                  l2size,
949                                  info->boot_cspace.make_path(info->boot_cspace.cspace, seL4_CapInitThreadTCB),
950                                  info->boot_cspace.make_path(info->boot_cspace.cspace, seL4_CapInitThreadPD),
951                                  NULL);
952    if (!alloc) {
953        return NULL;
954    }
955    /* do common cleanup */
956    return _new_from_bootinfo_common(info, old_cspace);
957}
958
959static size_t get_next_alignment_bits(uintptr_t base, uintptr_t goal, size_t max_alignment) {
960    /* Calculate alignment of our base pointer */
961    uintptr_t alignment = (base == 0) ? max_alignment : MIN(CTZL((long)base), max_alignment);
962
963    /* Our biggest size is either the distance to our goal, or our largest size
964     * based on our current alignment. */
965    uintptr_t next_size = MIN(goal - base, BIT(alignment));
966    ZF_LOGF_IF(next_size == 0, "next_size should not be 0 here.");
967
968    /* The largest untyped we can make is the highest power of 2 component of next_size */
969    size_t next_size_bits = seL4_WordBits - 1 - CLZL((long)next_size);
970
971    ZF_LOGD("goal 0x%zx, base: 0x%zx, next_size: 0x%zx, 0x%zx, 0x%zx, 0x%zx", goal, base, (uintptr_t) BIT(next_size_bits), next_size, CLZL((long)next_size),alignment);
972    return next_size_bits;
973}
974
975/*
976    Helper function that takes a region of device untyped and extracts it
977    from one utspace manager and deposits into a different utspace manager with
978    `untyped_type` type.  It is used for splitting up device untyped caps into ALLOCMAN_UT_DEV_MEM
979    and ALLOCMAN_UT_DEV.
980 */
981static ssize_t perform_sub_allocation(uintptr_t base, uintptr_t goal, allocman_t *alloc,
982                        utspace_interface_t *ut_space, utspace_split_t *token, int untyped_type) {
983    size_t next_size_bits = get_next_alignment_bits(base, goal, seL4_MaxUntypedBits);
984    cspacepath_t path;
985    int error = allocman_cspace_alloc(alloc, &path);
986    ZF_LOGF_IF(error, "allocman_cspace_alloc failed");
987
988    ut_space->alloc(alloc, token, next_size_bits, seL4_UntypedObject, &path, base, true, &error);
989    ZF_LOGF_IF(error, "ut_space.alloc failed");
990
991    error = allocman_utspace_add_uts(alloc, 1, &path, &next_size_bits, &base, untyped_type);
992    ZF_LOGF_IF(error, "allocman_utspace_add_uts failed");
993
994    return BIT(next_size_bits);
995}
996
997/**
998 * Separates device ram memory into separate untyped caps from the cap provided.
999 * Arch specific implementation as on x86 we can use the grup multiboot headers to
1000 * find the address layout.  On arm there is no current implementation, but eventually
1001 * we should be able to take a device tree and extract memory layout from that.
1002 *
1003 * @param  state     handle to device specific state.
1004 * @param  paddr     base paddr of the untyped cap being passed in.
1005 * @param  size_bits size in bits of the untyped cap.
1006 * @param  path      the untyped cap.
1007 * @param  alloc     handle to an already initialised allocman.
1008 * @return           0 for success, otherwise error.
1009 */
1010static int handle_device_untyped_cap(add_untypeds_state_t *state, uintptr_t paddr, size_t size_bits, cspacepath_t *path, allocman_t *alloc ) {
1011    bool cap_tainted = false;
1012    int error;
1013    uintptr_t ut_end = paddr + BIT(size_bits);
1014    int num_regions = 0;
1015    if (state != NULL) {
1016        num_regions = state->num_regions;
1017    }
1018    for (int i = 0; i < num_regions; i++) {
1019        pmem_region_t *region = &state->regions[i];
1020        uint64_t region_end = region->base_addr + region->length;
1021
1022        if (region->type == PMEM_TYPE_RAM && !(paddr >= region_end || ut_end <= region->base_addr)) {
1023            if (!cap_tainted) {
1024                cap_tainted = true;
1025                state->ut_interface.add_uts(alloc, &state->split_ut, 1, path, &size_bits, &paddr, ALLOCMAN_UT_DEV);
1026            }
1027            // We have an untyped that is overlapping with some ram.  Lets break it up into sub parts
1028            ZF_LOGD("basepaddr 0x%zx framesize: %zd", paddr, size_bits);
1029            ZF_LOGD("\tPhysical Memory Region from %"PRIx64" size %"PRIx64" type %d", region->base_addr, region->length, region->type);
1030
1031            uintptr_t top = MIN(region_end, ut_end);
1032            while (paddr < top) {
1033                uintptr_t goal;
1034                int untyped_type;
1035                if (paddr >= region->base_addr) {
1036                    goal = top;
1037                    untyped_type = ALLOCMAN_UT_DEV_MEM;
1038                } else {
1039                    goal = region->base_addr;
1040                    untyped_type = ALLOCMAN_UT_DEV;
1041                }
1042                ssize_t result = perform_sub_allocation(paddr, goal, alloc, &state->ut_interface, &state->split_ut, untyped_type);
1043                ZF_LOGF_IF(result < 0, "perform_sub_allocation failed");
1044                paddr += result;
1045
1046            }
1047        }
1048    }
1049    if (!cap_tainted) {
1050        error = allocman_utspace_add_uts(alloc, 1, path, &size_bits, &paddr, ALLOCMAN_UT_DEV);
1051        ZF_LOGF_IF(error, "allocman_utspace_add_uts failed");
1052    } else if (paddr != ut_end){
1053        // Got to allocate the rest of our untyped as UT_DEV
1054        while (paddr < ut_end) {
1055            ssize_t result = perform_sub_allocation(paddr, ut_end, alloc, &state->ut_interface, &state->split_ut, ALLOCMAN_UT_DEV);
1056            ZF_LOGF_IF(result < 0, "perform_sub_allocation failed");
1057            paddr += result;
1058        }
1059    }
1060    return 0;
1061}
1062
1063static void free_device_untyped_cap_state(allocman_t *alloc, add_untypeds_state_t *state) {
1064    if (state == NULL) {
1065        ZF_LOGE("free_device_untyped_cap_state with NULL state");
1066        return;
1067    }
1068    if (state->region_alloc) {
1069        if (state->regions == NULL) {
1070            ZF_LOGE("free_device_untyped_cap_state with NULL regions");
1071            return;
1072        }
1073        allocman_mspace_free(alloc, state->regions, sizeof(pmem_region_t) * state->num_regions);
1074    }
1075    allocman_mspace_free(alloc, state, sizeof(add_untypeds_state_t));
1076    return;
1077}
1078/**
1079 * Initialise required state for future calls to bootstrap_arch_handle_device_untyped_cap
1080 * @param  alloc           an allocman with a cspace, mspace and utspace inside it.
1081 * @param  simple          a simple interface
1082 * @param  token           For returning a handle to the initialsed state.
1083 * @param  feature_enabled For returning whether bootstrap_arch_handle_device_untyped_cap can be called.
1084 * @param  num_regions     number of regions in region array
1085 * @param  region_list     an array of regions. If NULL this will call sel4platsupport_get_pmem_region_list.
1086 * @return                 0 for success, otherwise error.
1087 */
1088static int prepare_handle_device_untyped_cap(allocman_t *alloc, simple_t *simple, add_untypeds_state_t **token, int num_regions, pmem_region_t *region_list) {
1089    int error;
1090    add_untypeds_state_t *state = allocman_mspace_alloc(alloc, sizeof(add_untypeds_state_t), &error);
1091    ZF_LOGF_IF(error, "Failed to allocate add_untypeds_state_t");
1092
1093    if (num_regions >= 0 && region_list != NULL) {
1094        state->num_regions = num_regions;
1095        state->regions = region_list;
1096        state->region_alloc = false;
1097    } else  {
1098        num_regions = sel4platsupport_get_num_pmem_regions(simple);
1099        if (num_regions == 0 || num_regions == -1) {
1100            free_device_untyped_cap_state(alloc, state);
1101            return 0;
1102        }
1103        state->regions = allocman_mspace_alloc(alloc, sizeof(pmem_region_t) * num_regions, &error);
1104        state->region_alloc = true;
1105        state->num_regions = sel4platsupport_get_pmem_region_list(simple, num_regions, state->regions);
1106        ZF_LOGF_IF(state->num_regions != num_regions, "Couldn't extract region list from simple");
1107    }
1108    utspace_split_create(&state->split_ut);
1109    state->ut_interface = utspace_split_make_interface(&state->split_ut);
1110
1111    *token = state;
1112    return 0;
1113}
1114
1115int allocman_add_simple_untypeds_with_regions(allocman_t *alloc, simple_t *simple, int num_regions, pmem_region_t *region_list) {
1116    add_untypeds_state_t *state = NULL;
1117    int error = prepare_handle_device_untyped_cap(alloc, simple, &state, num_regions, region_list);
1118    ZF_LOGF_IF(error, "bootstrap_prepare_handle_device_untyped_cap Failed");
1119
1120    size_t i;
1121    size_t total_untyped = simple_get_untyped_count(simple);
1122
1123    for(i = 0; i < total_untyped; i++) {
1124        size_t size_bits;
1125        uintptr_t paddr;
1126        bool device;
1127        cspacepath_t path = allocman_cspace_make_path(alloc, simple_get_nth_untyped(simple, i, &size_bits, &paddr, &device));
1128        int dev_type = device ? ALLOCMAN_UT_DEV : ALLOCMAN_UT_KERNEL;
1129        // If it is regular UT memory, then we add cap and move on.
1130        if (dev_type == ALLOCMAN_UT_KERNEL) {
1131            error = allocman_utspace_add_uts(alloc, 1, &path, &size_bits, &paddr, dev_type);
1132            ZF_LOGF_IF(error, "Could not add kernel untyped.");
1133        } else {
1134            // Otherwise we are Device untyped.
1135            error = handle_device_untyped_cap(state, paddr, size_bits, &path, alloc);
1136            ZF_LOGF_IF(error, "bootstrap_arch_handle_device_untyped_cap failed.");
1137        }
1138    }
1139    if (state) {
1140        free_device_untyped_cap_state(alloc, state);
1141    }
1142    return 0;
1143}
1144
1145int allocman_add_simple_untypeds(allocman_t *alloc, simple_t *simple) {
1146    return allocman_add_simple_untypeds_with_regions(alloc, simple, 0, NULL);
1147}
1148
1149allocman_t *bootstrap_use_current_simple(simple_t *simple, size_t pool_size, void *pool) {
1150    allocman_t *allocman;
1151    int error;
1152    /* Initialize inside the current 1 level cspace as defined by simple */
1153    allocman = bootstrap_use_current_1level(simple_get_cnode(simple), simple_get_cnode_size_bits(simple), simple_last_valid_cap(simple) + 1, BIT(simple_get_cnode_size_bits(simple)), pool_size, pool);
1154    if (!allocman) {
1155        LOG_ERROR("Failed to initialize an allocman");
1156        return allocman;
1157    }
1158    error = allocman_add_simple_untypeds(allocman, simple);
1159    if (error) {
1160        /* We have no way to cleanup the allocman we started bootstrapping */
1161        LOG_ERROR("Failed in call to allocman_add_simple_untypeds, cannot cleanup, leaking memory");
1162        return NULL;
1163    }
1164    return allocman;
1165}
1166
1167static allocman_t *bootstrap_new_simple(simple_t *simple, int levels, size_t l1size, size_t l2size, size_t pool_size, void *pool) {
1168    allocman_t *alloc;
1169    int error;
1170
1171    assert(levels == 1 || levels == 2);
1172    assert(l1size > 0);
1173    assert(levels == 1 || l2size > 0);
1174
1175    bootstrap_info_t *bootstrap = bootstrap_create_info(pool_size, pool);
1176    if (bootstrap == NULL) {
1177        return NULL;
1178    }
1179    bootstrap->simple = simple;
1180
1181    cspace_simple1level_create(&bootstrap->maybe_boot_cspace, (struct cspace_simple1level_config){
1182            .cnode = simple_get_cnode(simple),
1183            .cnode_size_bits = simple_get_cnode_size_bits(simple),
1184            .cnode_guard_bits = seL4_WordBits - simple_get_cnode_size_bits(simple),
1185            .first_slot = simple_last_valid_cap(simple) + 1,
1186            .end_slot = BIT(simple_get_cnode_size_bits(simple))
1187    });
1188
1189    cspacepath_t init_cnode_path = _cspace_simple1level_make_path(&bootstrap->maybe_boot_cspace, simple_get_cnode(simple));
1190    bootstrap_set_boot_cspace(bootstrap, cspace_simple1level_make_interface(&bootstrap->maybe_boot_cspace), init_cnode_path);
1191
1192    /* Tell the boostrapping allocator about the untypeds in the system */
1193    bootstrap_add_untypeds_from_simple(bootstrap, simple);
1194
1195    cspacepath_t tcb = _cspace_simple1level_make_path(&bootstrap->maybe_boot_cspace, simple_get_tcb(simple));
1196    cspacepath_t pd = _cspace_simple1level_make_path(&bootstrap->maybe_boot_cspace, simple_get_pd(simple));
1197
1198    if (levels == 1) {
1199        alloc = _bootstrap_new_level1(bootstrap, l1size, tcb, pd, NULL);
1200    } else {
1201        alloc = _bootstrap_new_level2(bootstrap, l1size, l2size, tcb, pd, NULL);
1202    }
1203    if (!alloc) {
1204        return NULL;
1205    }
1206
1207    /* Take all the caps in the boot cnode and put in them in the same location in the new cspace */
1208    error = bootstrap_transfer_caps_simple(bootstrap, simple, levels);
1209    if(error) {
1210        return NULL;
1211    }
1212
1213    /* Cleanup */
1214    bootstrap_free_info(bootstrap);
1215
1216    return alloc;
1217}
1218
1219allocman_t *bootstrap_new_1level_simple(simple_t *simple, size_t l1size, size_t pool_size, void *pool) {
1220    return bootstrap_new_simple(simple, 1, l1size, 0, pool_size, pool);
1221}
1222
1223allocman_t *bootstrap_new_2level_simple(simple_t *simple, size_t l1size, size_t l2size, size_t pool_size, void *pool) {
1224    return bootstrap_new_simple(simple, 2, l1size, l2size, pool_size, pool);
1225}
1226
1227static int allocman_add_bootinfo_untypeds(allocman_t *alloc, seL4_BootInfo *bi) {
1228    seL4_CPtr i;
1229    int error;
1230    for (i = bi->untyped.start; i < bi->untyped.end; i++) {
1231        size_t index = i - bi->untyped.start;
1232        cspacepath_t slot;
1233        size_t size_bits;
1234        uintptr_t paddr;
1235        slot = allocman_cspace_make_path(alloc, i);
1236        size_bits = bi->untypedList[index].sizeBits;
1237        paddr = bi->untypedList[index].paddr;
1238        error = allocman_utspace_add_uts(alloc, 1, &slot, &size_bits, &paddr, bi->untypedList[index].isDevice ? ALLOCMAN_UT_DEV : ALLOCMAN_UT_KERNEL);
1239        if (error) {
1240            return error;
1241        }
1242    }
1243    return 0;
1244}
1245
1246allocman_t *bootstrap_use_bootinfo(seL4_BootInfo *bi, size_t pool_size, void *pool) {
1247    allocman_t *alloc;
1248    int error;
1249    /* use the current single level cspace as described by boot info */
1250    alloc = bootstrap_use_current_1level(seL4_CapInitThreadCNode,
1251                                         bi->initThreadCNodeSizeBits,
1252                                         bi->empty.start,
1253                                         bi->empty.end,
1254                                         pool_size,
1255                                         pool);
1256    if (!alloc) {
1257        return NULL;
1258    }
1259    /* now add all the untypeds described in bootinfo */
1260    error = allocman_add_bootinfo_untypeds(alloc, bi);
1261    if (error) {
1262        return NULL;
1263    }
1264    return alloc;
1265}
1266
1267void bootstrap_configure_virtual_pool(allocman_t *alloc, void *vstart, size_t vsize, seL4_CPtr pd) {
1268    /* configure reservation for the virtual pool */
1269    /* assume we are using 4k pages. maybe this should be a Kconfig option at some point?
1270     * we ignore any errors */
1271    allocman_configure_utspace_reserve(alloc, (struct allocman_utspace_chunk) {vka_get_object_size(seL4_ARCH_4KPage, 0), seL4_ARCH_4KPage, 3});
1272    allocman_configure_utspace_reserve(alloc, (struct allocman_utspace_chunk) {vka_get_object_size(seL4_ARCH_PageTableObject, 0), seL4_ARCH_PageTableObject, 1});
1273    allocman_sel4_arch_configure_reservations(alloc);
1274    mspace_dual_pool_attach_virtual(
1275            (mspace_dual_pool_t*)alloc->mspace.mspace,
1276            (struct mspace_virtual_pool_config){
1277                .vstart = vstart,
1278                .size = vsize,
1279                .pd = pd
1280            }
1281    );
1282}
1283