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