1/*
2 * Copyright 2014, General Dynamics C4 Systems
3 *
4 * This software may be distributed and modified according to the terms of
5 * the GNU General Public License version 2. Note that NO WARRANTY is provided.
6 * See "LICENSE_GPLv2.txt" for details.
7 *
8 * @TAG(GD_GPL)
9 */
10
11#include <assert.h>
12#include <kernel/boot.h>
13#include <kernel/thread.h>
14#include <machine/io.h>
15#include <machine/registerset.h>
16#include <model/statedata.h>
17#include <arch/machine.h>
18#include <arch/kernel/boot.h>
19#include <arch/kernel/vspace.h>
20#include <linker.h>
21#include <plat/machine/hardware.h>
22#include <util.h>
23
24/* (node-local) state accessed only during bootstrapping */
25
26ndks_boot_t ndks_boot BOOT_DATA;
27
28BOOT_CODE bool_t
29insert_region(region_t reg)
30{
31    word_t i;
32
33    assert(reg.start <= reg.end);
34    if (is_reg_empty(reg)) {
35        return true;
36    }
37    for (i = 0; i < MAX_NUM_FREEMEM_REG; i++) {
38        if (is_reg_empty(ndks_boot.freemem[i])) {
39            ndks_boot.freemem[i] = reg;
40            return true;
41        }
42    }
43    return false;
44}
45
46BOOT_CODE static inline word_t
47reg_size(region_t reg)
48{
49    return reg.end - reg.start;
50}
51
52BOOT_CODE pptr_t
53alloc_region(word_t size_bits)
54{
55    word_t i;
56    word_t reg_index = 0; /* gcc cannot work out that this will not be used uninitialized */
57    region_t reg = REG_EMPTY;
58    region_t rem_small = REG_EMPTY;
59    region_t rem_large = REG_EMPTY;
60    region_t new_reg;
61    region_t new_rem_small;
62    region_t new_rem_large;
63
64    /* Search for a freemem region that will be the best fit for an allocation. We favour allocations
65     * that are aligned to either end of the region. If an allocation must split a region we favour
66     * an unbalanced split. In both cases we attempt to use the smallest region possible. In general
67     * this means we aim to make the size of the smallest remaining region smaller (ideally zero)
68     * followed by making the size of the largest remaining region smaller */
69
70    for (i = 0; i < MAX_NUM_FREEMEM_REG; i++) {
71        /* Determine whether placing the region at the start or the end will create a bigger left over region */
72        if (ROUND_UP(ndks_boot.freemem[i].start, size_bits) - ndks_boot.freemem[i].start <
73                ndks_boot.freemem[i].end - ROUND_DOWN(ndks_boot.freemem[i].end, size_bits)) {
74            new_reg.start = ROUND_UP(ndks_boot.freemem[i].start, size_bits);
75            new_reg.end = new_reg.start + BIT(size_bits);
76        } else {
77            new_reg.end = ROUND_DOWN(ndks_boot.freemem[i].end, size_bits);
78            new_reg.start = new_reg.end - BIT(size_bits);
79        }
80        if (new_reg.end > new_reg.start &&
81                new_reg.start >= ndks_boot.freemem[i].start &&
82                new_reg.end <= ndks_boot.freemem[i].end) {
83            if (new_reg.start - ndks_boot.freemem[i].start < ndks_boot.freemem[i].end - new_reg.end) {
84                new_rem_small.start = ndks_boot.freemem[i].start;
85                new_rem_small.end = new_reg.start;
86                new_rem_large.start = new_reg.end;
87                new_rem_large.end = ndks_boot.freemem[i].end;
88            } else {
89                new_rem_large.start = ndks_boot.freemem[i].start;
90                new_rem_large.end = new_reg.start;
91                new_rem_small.start = new_reg.end;
92                new_rem_small.end = ndks_boot.freemem[i].end;
93            }
94            if ( is_reg_empty(reg) ||
95                    (reg_size(new_rem_small) < reg_size(rem_small)) ||
96                    (reg_size(new_rem_small) == reg_size(rem_small) && reg_size(new_rem_large) < reg_size(rem_large)) ) {
97                reg = new_reg;
98                rem_small = new_rem_small;
99                rem_large = new_rem_large;
100                reg_index = i;
101            }
102        }
103    }
104    if (is_reg_empty(reg)) {
105        printf("Kernel init failing: not enough memory\n");
106        return 0;
107    }
108    /* Remove the region in question */
109    ndks_boot.freemem[reg_index] = REG_EMPTY;
110    /* Add the remaining regions in largest to smallest order */
111    insert_region(rem_large);
112    if (!insert_region(rem_small)) {
113        printf("alloc_region(): wasted 0x%lx bytes due to alignment, try to increase MAX_NUM_FREEMEM_REG\n",
114               (word_t)(rem_small.end - rem_small.start));
115    }
116    return reg.start;
117}
118
119BOOT_CODE void
120write_slot(slot_ptr_t slot_ptr, cap_t cap)
121{
122    slot_ptr->cap = cap;
123
124    slot_ptr->cteMDBNode = nullMDBNode;
125    mdb_node_ptr_set_mdbRevocable  (&slot_ptr->cteMDBNode, true);
126    mdb_node_ptr_set_mdbFirstBadged(&slot_ptr->cteMDBNode, true);
127}
128
129/* Our root CNode needs to be able to fit all the initial caps and not
130 * cover all of memory.
131 */
132compile_assert(root_cnode_size_valid,
133               CONFIG_ROOT_CNODE_SIZE_BITS < 32 - seL4_SlotBits &&
134               (1U << CONFIG_ROOT_CNODE_SIZE_BITS) >= seL4_NumInitialCaps)
135
136BOOT_CODE cap_t
137create_root_cnode(void)
138{
139    pptr_t  pptr;
140    cap_t   cap;
141
142    /* write the number of root CNode slots to global state */
143    ndks_boot.slot_pos_max = BIT(CONFIG_ROOT_CNODE_SIZE_BITS);
144
145    /* create an empty root CNode */
146    pptr = alloc_region(CONFIG_ROOT_CNODE_SIZE_BITS + seL4_SlotBits);
147    if (!pptr) {
148        printf("Kernel init failing: could not create root cnode\n");
149        return cap_null_cap_new();
150    }
151    memzero(CTE_PTR(pptr), 1U << (CONFIG_ROOT_CNODE_SIZE_BITS + seL4_SlotBits));
152    cap =
153        cap_cnode_cap_new(
154            CONFIG_ROOT_CNODE_SIZE_BITS,      /* radix      */
155            wordBits - CONFIG_ROOT_CNODE_SIZE_BITS, /* guard size */
156            0,                                /* guard      */
157            pptr                              /* pptr       */
158        );
159
160    /* write the root CNode cap into the root CNode */
161    write_slot(SLOT_PTR(pptr, seL4_CapInitThreadCNode), cap);
162
163    return cap;
164}
165
166compile_assert(irq_cnode_size, BIT(IRQ_CNODE_BITS - seL4_SlotBits) > maxIRQ)
167
168BOOT_CODE bool_t
169create_irq_cnode(void)
170{
171    pptr_t pptr;
172    /* create an empty IRQ CNode */
173    pptr = alloc_region(IRQ_CNODE_BITS);
174    if (!pptr) {
175        printf("Kernel init failing: could not create irq cnode\n");
176        return false;
177    }
178    memzero((void*)pptr, 1 << IRQ_CNODE_BITS);
179    intStateIRQNode = (cte_t*)pptr;
180    return true;
181}
182
183/* Check domain scheduler assumptions. */
184compile_assert(num_domains_valid,
185               CONFIG_NUM_DOMAINS >= 1 && CONFIG_NUM_DOMAINS <= 256)
186compile_assert(num_priorities_valid,
187               CONFIG_NUM_PRIORITIES >= 1 && CONFIG_NUM_PRIORITIES <= 256)
188
189BOOT_CODE void
190create_domain_cap(cap_t root_cnode_cap)
191{
192    cap_t cap;
193    word_t i;
194
195    /* Check domain scheduler assumptions. */
196    assert(ksDomScheduleLength > 0);
197    for (i = 0; i < ksDomScheduleLength; i++) {
198        assert(ksDomSchedule[i].domain < CONFIG_NUM_DOMAINS);
199        assert(ksDomSchedule[i].length > 0);
200    }
201
202    cap = cap_domain_cap_new();
203    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapDomain), cap);
204}
205
206
207BOOT_CODE cap_t
208create_ipcbuf_frame(cap_t root_cnode_cap, cap_t pd_cap, vptr_t vptr)
209{
210    cap_t cap;
211    pptr_t pptr;
212
213    /* allocate the IPC buffer frame */
214    pptr = alloc_region(PAGE_BITS);
215    if (!pptr) {
216        printf("Kernel init failing: could not create ipc buffer frame\n");
217        return cap_null_cap_new();
218    }
219    clearMemory((void*)pptr, PAGE_BITS);
220
221    /* create a cap of it and write it into the root CNode */
222    cap = create_mapped_it_frame_cap(pd_cap, pptr, vptr, IT_ASID, false, false);
223    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadIPCBuffer), cap);
224
225    return cap;
226}
227
228BOOT_CODE void
229create_bi_frame_cap(
230    cap_t      root_cnode_cap,
231    cap_t      pd_cap,
232    pptr_t     pptr,
233    vptr_t     vptr
234)
235{
236    cap_t cap;
237
238    /* create a cap of it and write it into the root CNode */
239    cap = create_mapped_it_frame_cap(pd_cap, pptr, vptr, IT_ASID, false, false);
240    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapBootInfoFrame), cap);
241}
242
243BOOT_CODE region_t
244allocate_extra_bi_region(word_t extra_size)
245{
246    /* determine power of 2 size of this region. avoid calling clzl on 0 though */
247    if (extra_size == 0) {
248        /* return any valid address to correspond to the zero allocation */
249        return (region_t) {
250            0x1000, 0x1000
251        };
252    }
253    word_t size_bits = seL4_WordBits - 1 - clzl(ROUND_UP(extra_size, seL4_PageBits));
254    pptr_t pptr = alloc_region(size_bits);
255    if (!pptr) {
256        printf("Kernel init failed: could not allocate extra bootinfo region size bits %lu\n", size_bits);
257        return REG_EMPTY;
258    }
259
260    clearMemory((void*)pptr, size_bits);
261    ndks_boot.bi_frame->extraLen = BIT(size_bits);
262
263    return (region_t) {
264        pptr, pptr + BIT(size_bits)
265    };
266}
267
268BOOT_CODE pptr_t
269allocate_bi_frame(
270    node_id_t  node_id,
271    word_t   num_nodes,
272    vptr_t ipcbuf_vptr
273)
274{
275    pptr_t pptr;
276
277    /* create the bootinfo frame object */
278    pptr = alloc_region(BI_FRAME_SIZE_BITS);
279    if (!pptr) {
280        printf("Kernel init failed: could not allocate bootinfo frame\n");
281        return 0;
282    }
283    clearMemory((void*)pptr, BI_FRAME_SIZE_BITS);
284
285    /* initialise bootinfo-related global state */
286    ndks_boot.bi_frame = BI_PTR(pptr);
287    ndks_boot.slot_pos_cur = seL4_NumInitialCaps;
288
289    BI_PTR(pptr)->nodeID = node_id;
290    BI_PTR(pptr)->numNodes = num_nodes;
291    BI_PTR(pptr)->numIOPTLevels = 0;
292    BI_PTR(pptr)->ipcBuffer = (seL4_IPCBuffer *) ipcbuf_vptr;
293    BI_PTR(pptr)->initThreadCNodeSizeBits = CONFIG_ROOT_CNODE_SIZE_BITS;
294    BI_PTR(pptr)->initThreadDomain = ksDomSchedule[ksDomScheduleIdx].domain;
295    BI_PTR(pptr)->extraLen = 0;
296    BI_PTR(pptr)->extraBIPages.start = 0;
297    BI_PTR(pptr)->extraBIPages.end = 0;
298
299    return pptr;
300}
301
302BOOT_CODE bool_t
303provide_cap(cap_t root_cnode_cap, cap_t cap)
304{
305    if (ndks_boot.slot_pos_cur >= ndks_boot.slot_pos_max) {
306        printf("Kernel init failed: ran out of cap slots\n");
307        return false;
308    }
309    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), ndks_boot.slot_pos_cur), cap);
310    ndks_boot.slot_pos_cur++;
311    return true;
312}
313
314BOOT_CODE create_frames_of_region_ret_t
315create_frames_of_region(
316    cap_t    root_cnode_cap,
317    cap_t    pd_cap,
318    region_t reg,
319    bool_t   do_map,
320    sword_t  pv_offset
321)
322{
323    pptr_t     f;
324    cap_t      frame_cap;
325    seL4_SlotPos slot_pos_before;
326    seL4_SlotPos slot_pos_after;
327
328    slot_pos_before = ndks_boot.slot_pos_cur;
329
330    for (f = reg.start; f < reg.end; f += BIT(PAGE_BITS)) {
331        if (do_map) {
332            frame_cap = create_mapped_it_frame_cap(pd_cap, f, pptr_to_paddr((void*)(f - pv_offset)), IT_ASID, false, true);
333        } else {
334            frame_cap = create_unmapped_it_frame_cap(f, false);
335        }
336        if (!provide_cap(root_cnode_cap, frame_cap))
337            return (create_frames_of_region_ret_t) {
338            S_REG_EMPTY, false
339        };
340    }
341
342    slot_pos_after = ndks_boot.slot_pos_cur;
343
344    return (create_frames_of_region_ret_t) {
345        (seL4_SlotRegion) { slot_pos_before, slot_pos_after }, true
346    };
347}
348
349BOOT_CODE cap_t
350create_it_asid_pool(cap_t root_cnode_cap)
351{
352    pptr_t ap_pptr;
353    cap_t  ap_cap;
354
355    /* create ASID pool */
356    ap_pptr = alloc_region(seL4_ASIDPoolBits);
357    if (!ap_pptr) {
358        printf("Kernel init failed: failed to create initial thread asid pool\n");
359        return cap_null_cap_new();
360    }
361    memzero(ASID_POOL_PTR(ap_pptr), 1 << seL4_ASIDPoolBits);
362    ap_cap = cap_asid_pool_cap_new(IT_ASID >> asidLowBits, ap_pptr);
363    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadASIDPool), ap_cap);
364
365    /* create ASID control cap */
366    write_slot(
367        SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapASIDControl),
368        cap_asid_control_cap_new()
369    );
370
371    return ap_cap;
372}
373
374BOOT_CODE bool_t
375create_idle_thread(void)
376{
377    pptr_t pptr;
378
379#ifdef ENABLE_SMP_SUPPORT
380    for (int i = 0; i < CONFIG_MAX_NUM_NODES; i++) {
381#endif /* ENABLE_SMP_SUPPORT */
382        pptr = alloc_region(seL4_TCBBits);
383        if (!pptr) {
384            printf("Kernel init failed: Unable to allocate tcb for idle thread\n");
385            return false;
386        }
387        memzero((void *)pptr, 1 << seL4_TCBBits);
388        NODE_STATE_ON_CORE(ksIdleThread, i) = TCB_PTR(pptr + TCB_OFFSET);
389        configureIdleThread(NODE_STATE_ON_CORE(ksIdleThread, i));
390#ifdef CONFIG_DEBUG_BUILD
391        setThreadName(NODE_STATE_ON_CORE(ksIdleThread, i), "idle_thread");
392#endif
393        SMP_COND_STATEMENT(NODE_STATE_ON_CORE(ksIdleThread, i)->tcbAffinity = i);
394#ifdef ENABLE_SMP_SUPPORT
395    }
396#endif /* ENABLE_SMP_SUPPORT */
397    return true;
398}
399
400BOOT_CODE tcb_t *
401create_initial_thread(
402    cap_t  root_cnode_cap,
403    cap_t  it_pd_cap,
404    vptr_t ui_v_entry,
405    vptr_t bi_frame_vptr,
406    vptr_t ipcbuf_vptr,
407    cap_t  ipcbuf_cap
408)
409{
410    pptr_t pptr;
411    cap_t  cap;
412    tcb_t* tcb;
413    deriveCap_ret_t dc_ret;
414
415    /* allocate TCB */
416    pptr = alloc_region(seL4_TCBBits);
417    if (!pptr) {
418        printf("Kernel init failed: Unable to allocate tcb for initial thread\n");
419        return NULL;
420    }
421    memzero((void*)pptr, 1 << seL4_TCBBits);
422    tcb = TCB_PTR(pptr + TCB_OFFSET);
423    tcb->tcbTimeSlice = CONFIG_TIME_SLICE;
424    Arch_initContext(&tcb->tcbArch.tcbContext);
425
426    /* derive a copy of the IPC buffer cap for inserting */
427    dc_ret = deriveCap(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadIPCBuffer), ipcbuf_cap);
428    if (dc_ret.status != EXCEPTION_NONE) {
429        printf("Failed to derive copy of IPC Buffer\n");
430        return NULL;
431    }
432
433    /* initialise TCB (corresponds directly to abstract specification) */
434    cteInsert(
435        root_cnode_cap,
436        SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadCNode),
437        SLOT_PTR(pptr, tcbCTable)
438    );
439    cteInsert(
440        it_pd_cap,
441        SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadVSpace),
442        SLOT_PTR(pptr, tcbVTable)
443    );
444    cteInsert(
445        dc_ret.cap,
446        SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadIPCBuffer),
447        SLOT_PTR(pptr, tcbBuffer)
448    );
449    tcb->tcbIPCBuffer = ipcbuf_vptr;
450
451    /* Set the root thread's IPC buffer */
452    Arch_setTCBIPCBuffer(tcb, ipcbuf_vptr);
453
454    setRegister(tcb, capRegister, bi_frame_vptr);
455    setNextPC(tcb, ui_v_entry);
456
457    /* initialise TCB */
458    tcb->tcbPriority = seL4_MaxPrio;
459    tcb->tcbMCP = seL4_MaxPrio;
460    setupReplyMaster(tcb);
461    setThreadState(tcb, ThreadState_Running);
462
463    ksCurDomain = ksDomSchedule[ksDomScheduleIdx].domain;
464    ksDomainTime = ksDomSchedule[ksDomScheduleIdx].length;
465    assert(ksCurDomain < CONFIG_NUM_DOMAINS && ksDomainTime > 0);
466
467    SMP_COND_STATEMENT(tcb->tcbAffinity = 0);
468
469    /* create initial thread's TCB cap */
470    cap = cap_thread_cap_new(TCB_REF(tcb));
471    write_slot(SLOT_PTR(pptr_of_cap(root_cnode_cap), seL4_CapInitThreadTCB), cap);
472
473#ifdef CONFIG_DEBUG_BUILD
474    setThreadName(tcb, "rootserver");
475#endif
476
477    return tcb;
478}
479
480BOOT_CODE void
481init_core_state(tcb_t *scheduler_action)
482{
483#ifdef CONFIG_HAVE_FPU
484    NODE_STATE(ksActiveFPUState) = NULL;
485#endif
486#ifdef CONFIG_DEBUG_BUILD
487    /* add initial threads to the debug queue */
488    NODE_STATE(ksDebugTCBs) = NULL;
489    if (scheduler_action != SchedulerAction_ResumeCurrentThread &&
490            scheduler_action != SchedulerAction_ChooseNewThread) {
491        tcbDebugAppend(scheduler_action);
492    }
493    tcbDebugAppend(NODE_STATE(ksIdleThread));
494#endif
495    NODE_STATE(ksSchedulerAction) = scheduler_action;
496    NODE_STATE(ksCurThread) = NODE_STATE(ksIdleThread);
497}
498
499BOOT_CODE static bool_t
500provide_untyped_cap(
501    cap_t      root_cnode_cap,
502    bool_t     device_memory,
503    pptr_t     pptr,
504    word_t     size_bits,
505    seL4_SlotPos first_untyped_slot
506)
507{
508    bool_t ret;
509    cap_t ut_cap;
510    word_t i = ndks_boot.slot_pos_cur - first_untyped_slot;
511    if (i < CONFIG_MAX_NUM_BOOTINFO_UNTYPED_CAPS) {
512        ndks_boot.bi_frame->untypedList[i] = (seL4_UntypedDesc) {
513            pptr_to_paddr((void*)pptr), 0, 0, size_bits, device_memory
514        };
515        ut_cap = cap_untyped_cap_new(MAX_FREE_INDEX(size_bits),
516                                     device_memory, size_bits, pptr);
517        ret = provide_cap(root_cnode_cap, ut_cap);
518    } else {
519        printf("Kernel init: Too many untyped regions for boot info\n");
520        ret = true;
521    }
522    return ret;
523}
524
525BOOT_CODE bool_t
526create_untypeds_for_region(
527    cap_t      root_cnode_cap,
528    bool_t     device_memory,
529    region_t   reg,
530    seL4_SlotPos first_untyped_slot
531)
532{
533    word_t align_bits;
534    word_t size_bits;
535
536    while (!is_reg_empty(reg)) {
537        /* Determine the maximum size of the region */
538        size_bits = seL4_WordBits - 1 - clzl(reg.end - reg.start);
539
540        /* Determine the alignment of the region */
541        if (reg.start != 0) {
542            align_bits = ctzl(reg.start);
543        } else {
544            align_bits = size_bits;
545        }
546        /* Reduce size bits to align if needed */
547        if (align_bits < size_bits) {
548            size_bits = align_bits;
549        }
550        if (size_bits > seL4_MaxUntypedBits) {
551            size_bits = seL4_MaxUntypedBits;
552        }
553
554        if (size_bits >= seL4_MinUntypedBits) {
555            if (!provide_untyped_cap(root_cnode_cap, device_memory, reg.start, size_bits, first_untyped_slot)) {
556                return false;
557            }
558        }
559        reg.start += BIT(size_bits);
560    }
561    return true;
562}
563
564BOOT_CODE bool_t
565create_kernel_untypeds(cap_t root_cnode_cap, region_t boot_mem_reuse_reg, seL4_SlotPos first_untyped_slot)
566{
567    word_t     i;
568    region_t   reg;
569
570    /* if boot_mem_reuse_reg is not empty, we can create UT objs from boot code/data frames */
571    if (!create_untypeds_for_region(root_cnode_cap, false, boot_mem_reuse_reg, first_untyped_slot)) {
572        return false;
573    }
574
575    /* convert remaining freemem into UT objects and provide the caps */
576    for (i = 0; i < MAX_NUM_FREEMEM_REG; i++) {
577        reg = ndks_boot.freemem[i];
578        ndks_boot.freemem[i] = REG_EMPTY;
579        if (!create_untypeds_for_region(root_cnode_cap, false, reg, first_untyped_slot)) {
580            return false;
581        }
582    }
583
584    return true;
585}
586
587BOOT_CODE void
588bi_finalise(void)
589{
590    seL4_SlotPos slot_pos_start = ndks_boot.slot_pos_cur;
591    seL4_SlotPos slot_pos_end = ndks_boot.slot_pos_max;
592    ndks_boot.bi_frame->empty = (seL4_SlotRegion) {
593        slot_pos_start, slot_pos_end
594    };
595}
596