the beginnings of an operating system on aarch64

im not making an operating system because i have a grand idea
about security or interprocess communication. i just want to 
be able to run my programs on a computer and my programs assume 
there will be some greater power available to supply things like 
memory allocation, threads, futexes, a file system, etc. 

what i end up with is perhaps more accuritely called a unikernel. 
its one program with the kernel part and the user part bundled together 
however, the user part is my compiler and the source of all my example programs, 
so it can jit compile the other programs and present something that looks more 
like a general purpose operating system. 
that said, the building blocks you need at the beginning will the same if you're making 
a more classical shape of operating system than this one so this should still be useful. 
the high level ideas carry over to other architectures but this is focused on 
aarch64 because that's what i have more experience with. 

these sections are not a tutorial you can follow in order. 
you'll probably want to do simple versions of things and incrementally 
progress as you get more debugging tools. 

emulators/hypervisors

priveledge levels

system registers

the mrs/msr instructions let you read/write these registers. 
the ones i need to use are backend/arm64/bits.fr/L312-L350

writing to these registers has side effects!

some of them are bit flags that control whether user space can use different instructions. 
- CPACR_EL1 has a bit to enable floating point instructions
- CNTKCTL_EL1 has a bit to enable reading CNTVCT_EL0/CNTFRQ_EL0 system registers to get high precision timers
- SPSel controls whether userspace and kernelspace share a stack pointer register

some are read only information 
- ID_AA64ISAR0_EL1 has a bit that reports if atomic instructions are implemented on this cpu 
- CurrentEL has the current privledge level
- ICC_SRE_EL1 has a bit that tells you if interrupts are configured with system registers or a special memory region

- some hold pointers to data structures the cpu uses: page tables, interrupt vector
- some are just extra registers you can use. TPIDR_EL1 conventionally holds a pointer 
  to the kernel's task data structure so you can tell what's currently running. 

linux boot protocol

the linux kernel has very simple rules for how it expects a flat image 
to be loaded into memory by the bootloader. if you follow that it's 
mostly painless to run in different virtual machines without needing 
to figure out what magic start address the system it's pretending to be wants you to use. 
linux is ubiquitous enough that everyone needs to make it work on their thing.  

see kernel.org spec
and my code for generating it

for more conventional toolchains i assume there's someway to produce that format 
with a linker script, luckily i live in a world where i can just put 
the bytes in the file so that's none-my-business. 

note that this is not an elf file, you don't get to do data relocations 
or have sections spread out in virtual memory. there's a header with some 
extra information and the first 8 bytes are machine code instructions that
need to jump to the actual entry point of your kernel. 
a pointer to the device tree will be in x0 (helpfully the first argument of the standard calling convention). 
don't forget to point sp somewhere good for the kernel's stack before jumping to higher level language code. 

in my code there's a second header that says how big (the kernel code, the user space init 
program, and the initial file system) are, and those are all concatenated together. 
my kernel knows to look for that and pass the info to userspace. that's just an arbitrary 
choice on my part. a more sane startup mechanism for a real system would probably involve a 
seperate disk image with the userspace data, so you don't have to recompile the kernel as much. 
1500 milliseconds every time really starts to add up. 

device tree

the bootloader/hypervisor/whatever gives you information about what io devices exist. 
this lets you have one kernel blob that runs on multiple different hardware configurations. 
there's no need to debug blind, you should have a way to print back the structure you parsed as soon as possible! 
there's a bootstrapping problem that you might need information in the device tree to know how 
to print to the console. good luck with that. 

see my code for parsing the blob and displaying the tree. 
as an example, see my output when running in apple's virtualization framework. 
what your kernel will recieve is a flat binary format. 
don't be fooled by examples with textual (.dts) files.

the fields are big endian so don't forget to byteswap. 
the header has the size and offset to the structs encoding the tree and the blob of string data. 
the structs region is a sequence of nodes, each starting with a tag 
(BEGIN_NODE=1, END_NODE=2, PROP=3, NOP=4, END=9). 
BEGIN_NODE is followed by an offset in strings of a null terminated field name for that node. 
PROP is followed by an offset and a length in strings of the data for that node. 
each node can have more BEGIN_NODEs before its closing END_NODE to represent a nested tree structure. 

the fields i need for the devices i use in later sections are intc,gic,pl011,pci,memory,cpus. 
also qemu's -append cli argument controls the string in chosen.bootargs. 

interrupt handlers
- device interrupt like console input, timer, etc.
- syncronous exceptions: illegal instruction, memory fault, etc.

the interupt table is an array of 16 entries, each are 32 instructions. 
if you need more than 32 instructions or if you want to handle all the 
interrupts in a consistant way you can jump to other code immediatly. 
note that which slot of the table was jumped to gives you information 
about what type of interrupt it was. 
VBAR_EL1 is the system register that holds the address of the table. 
it must be aligned to 2048 bytes (also happens to be the total size of the table).

it's important that you save all the registers before doing anything useful because 
you're going to return to userspace and it will be expecting all its variables to still be intact. 
unlike a normal function call, the user can be interrupted at any time so you can't really 
have a calling convention with caller saved registers that the interrupt handler is allowed to stomp on. 
of course there are exceptions to that rule. 
some system registers (and the condition flags and stack pointer) have seperate versions for user space 
and kernel space so you don't have to worry about stomping them. 

x18 is the "platform register" which the system (in this case that's you) might declare 
is reserved and might be mangled at any time (which happens on macos). 
so if that's the abi you want then that's an extra general purpose register you can use 
right away in the interrupt handler. make sure the toolchain you use for user binaries agrees with your choice.

there's a system register where you read the intid at the beginning (ICC_IAR1_EL1) 
and one where you write intid to acknoledge it when done (ICC_EOIR1_EL1). 
it's important to only read ICC_IAR1_EL1 when the interrupt table entry being called is 
the one for device interrupts. you can't read ICC_IAR1_EL1 all the time to decide 
if you're supposed to be handling an interrupt or you get race conditions where you lose 
syncronous exceptions that happen at the same time as a device interrupt. 

syscalls

syscalls are just like function calls except that the caller is user code 
and the callee is the kernel code. so the userspace needs to set up values in registers 
in whatever calling convention the kernel expects (for sanity purposes, i made this 
the same as it is for user space calls: x0-x7), and then trigger a trap that makes 
the cpu change privledge levels and jump into some handler in the kernel code. 
the kernel needs to save the state of all the registers and remember where it came 
from so it can return back when the syscall is done. then inspect the contents of registers 
and do the action. 

in function calls you choose what function is called by jumping to a different address
in memory. syscalls traditionally only have one entry point and you put a magic number 
in another register that the handler looks at to decide what action will be performed. 
you could imagine writing a normal userspace program with only one function with a giant 
switch statement over its first argument where every function call is a recursive call to 
that one function with a different argument. 

the mechanism for getting to the syscall handler is exactly the same as for other traps 
like illegal instructions or accessing invalid memory. the fact that the isa has an instruction 
called "syscall" doesn't give any extra power. it just makes it easier to read the 
disassembly than if you decided the way you ask for a syscall was to try to jump to some address you know is unmapped. 
the important thing is that both sides agree. 

if you want an easy time you can choose to use the same syscall numbers (and behaviours) as linux. 
then you can compile a statically linked program with someone else's tool chain 
and run it on your own operating system (assuming you write an elf loader). 
obviously if you want to walk your own path you can choose whatever syscall numbers you want. 
linux is unusual in that the syscalls are the stable interface given to third party user programs. 
many operating systems ship with some other user space code that provides a stable 
interface as function calls (that normal programs dynamically link against) 
on top of the kernel's syscalls (on macos and BSDs that's libc). 

signals

sometimes you don't want to deal with an interrupt/exception in the kernel, 
you just want to send it to userspace and let them decide what to do. 
for example, many language runtimes will want to print a nice stack trace on segfaults 
or you might want to allow writing device drivers in userspace. 

careful about handling nested interrupts and when you tell the cpu you're done handling an interrupt. 

generic interrupt controllor

gicd vs gicr.
i use version 3. 
sgi vs ppi vs spi. 
field bit packing. 

timer

the timer is controlled by system registers. 
CNTFRQ_EL0 holds the frequency (how many times the timer ticks per second). 
CNTV_TVAL_EL0 holds how many ticks until a timer interrupt will be sent (as an i32). 
at startup and every time you recive the interrupt, you reset that counter to ask for a new interrupt. 
write 1/0 to CNTV_CTL_EL0 to enable/disable the timer. 
make sure to set the counter before enabling the timer. 
- also set the counter before acknoledging the interrupt

CNTV_TVAL_EL0 is a convience over directly accessing CNTVCT_EL0 (a counter that always goes up) 
and CNTV_CVAL_EL0 (a value to compare that counter to for sending a timer interrupt). 
it's not clear to me why they give you a shorter way to write 
CNTV_TVAL_EL0=x instead of CNTV_CVAL_EL0=CNTVCT_EL0+x. 
reading CNTVCT_EL0 directly tells you how long it's been since the core started 
(which can be useful when implementing a sleep syscall). 

the V in those register names stands for virtual, there's also a P (physical) version of them. 
the virtual counters are used for... virtualization... they let a hypervisor efficiently 
lie to you about the time by applying some offset.
the important thing is that you won't be allowed to use the physical ones 
if you're running in vzf or qemu with -accel hvf. 

concurent threads

before you get to real parallelism where you turn on multiple cores that 
can run different code at the same time, you can still provide an interface 
for spawning threads that appear to run at the same time. 

there are two main categories. 
coperative scheduling where the user program has some way of explicitly yielding when 
it wants to wait for another thread to make progress. preemptive scheduling where 
a timer forces a trap that lets another thread run. 
inevitably you want a mix of the two. some amount of preemptivness means a program 
with an infinite loop can't freeze the whole computer. 
some amount of coperativness lets threads efficiently comunicate with each other 
instead of burning cpu time uselessly spinning waiting for something to happen. 

user space will want some way to create threads and some way to join threads. 

futexes

the concerency primitives you want are the ability to sleep a thread and the ability to 
signal another sleeping thread that it should wake up. 
- dumbest: spin loop until a flag changes
- better but racey: sleep/wake syscall. you could give it a time out but that wastes more time than being precise.  
- solution: sleep until the value at a memory location changes. 

different systems have different names for this operation:
on linux it's called futex_wake,futex_wait, on macos it's called ulock_wake,ulock_wait, in webassembly its called atomics.wait,atomics.notify. 

atomics

there are instructions for many simple read-modifiy-write operations. 
the general case is compare-and-swap which does a store that completes 
only if a memory location holds a specific value. so you can load, do an arbitrary computation 
to choose the new value, and only store it if the memory hasn't been modified 
since your original load. the output of the cas instruction tells you if the store succeeded 
so you can do it in a loop until you get your update. this is powerful enough 
to build all the other rmw atomic operations. 

this matters much more with real parallelism but even with peremptive concureny 
you can get preempted in the between when you load a value and when you store 
back a modified one. 

there are also atomic orderings where you give the cpu information about 
who you want to prioratize succeeding when there's contention. 

something to watch out for: atomic instructions are tend to be much more strict about alignment that normal memory accesses. 
many languages require that pointers be well aligned anyway so this doesn't matter. 

note that atomics are all in user space / the cpu, the kernel doesn't get a vote. 

cas+futex lets you implement higher level concerency things like mutex,condvar,lock free queues.

pl011 console
- less universal than the virtio console but much easier to use for early debugging
- doesn't work on apple's vzf (virtio console does tho)

virtio drivers

see virtio spec and my code for creating virt-queues. 
on my system i expose create and poll as syscalls. 

there are two ways to find devices: pci, device tree mmio. 
qemu lets you use either depending on the cli flags. 
vzf only does pci. 

there's a separation between the raw transport mechanism used to implement virt-queues 
and the higher level protocol for each different device that uses the queues. 

its common to have variable sized responses where you put an 
uninitialized buffer on the queue, the device writes to part of it, 
and then responds with how many bytes it wrote. 

readable buffers before writable buffers. 
events get interrupts. 

pci

it still ends up being memory mapped io. aarch64 doesn't have seperate io instructions like amd64 does. 
it's just an extra convoluted way to choose which magic addresses to use. 

virtio console

- console (log text to a terminal and get key presses back)

see my code implementing read/write calls with it

virtio gpu

it has a misleading name, you can use it as a simple framebuffer you can write pixels into. 
see my code for the command structs 
and an example program using them. 

setup call sequence:
- ask for the size of the screen
- create a texture resource with a certain pixel format
- attach a region of memory to that texture
- set the texture as the scanout for the screen
loop each frame:
- write your data into the frame buffer
- transfer the resource to the host
- flush the resource to show it on the screen
- sleep until the next frame


when you create a resource, you pick an aritrary u32 resource id that will be used to 
identify it in future commands.

the command for attaching memory to the texture takes an array of (physical address, byte length) 
tuples so it doesn't need to be contigous in physical memory. 

virtio fs

allows you to share directories with the host when running in a vm. 
it uses the same FUSE interface as user space file systems on linux. 
except that instead of writing the commands as bytes through a pipe, 
they're sent as messages over a virt-queue. 
see my code for fuse command structs and
code implementing virtual file system operations with it

most of the commands corrisopond directly to linux syscalls that interact with the file system 
(stat, mkdir, rename, open, read, write). 
in contrast to the virtio-gpu commands, the fs commands never contain pointers. 
the ones with variable sized payloads (for a file's contents or name) have the data inlined in the 
queue after the command header. 

each command has a common header (with a tag saying which command to use), followed by the command 
specific struct, followed by any variable sized data. each response has the same shape (with different structs). 

when you read from a directory you get back dirent structs. 
each dirent is followed by its name, padded to 8 byte alignment. 
directories must be opened with the opendir command instead of open. 

an open file is represented by a (file handle, node id) pair. 

virtual memory

why
- without the mmu on you can't do unaligned memory accesses
- memory doesn't need to be contigous so less fragmentation
- you can isolate different threads/processes so they can't stomp on each other's memory 
  and you can give memory different read/write/execute permissions so mistakes are less confusing. 
  each "process" can have its own page table. 
- you can overcommit
- more fine control over caching. the default state is that the cpu needs to assume 
  any memory address could be for memory mapped io which will be slower than if you 
  promise it will behave like normal memory that reads back the last thing written to it 
  so its allowed to be cached in a handwavey way. 

how
- enable the mmu
- page tables

extra rules
- you're not allowed memory that's executable in el1 and writable in el0 at the same time. 
  if you care about secuirity that's not something you want anyway but even for 
  debugging while bringing up your operating system the cpu won't allow it at all. 

page table size depends on page size. 
different bits in pointer index different levels of page table. 
each page table entry is 64 bits and either points to the next level of page table or a physical page to be used at the last level. 
page table addresses need to be aligned so extra flags can be stored in the low bits of the page table entry. 

see my code

you'll need an allocator that splits up contigous physical memory into pages to hand out when user space requests some. 
careful that you know which region isn't taken up by your kernel or the device tree blob or memory mapped io. 
the device tree's memory.reg field has the start address and length of physical memory (not accounting for the kernel/devicetree blobs). 
recall that you can't do 8 byte loads of those fields before turning on the mmu because they might not be aligned. 

Symetric MultiProcessing

fancy word for parallelism where the cores are mostly the same. 

- device tree tells you how many cores
- hypervizer call 0xC4000003
- MPIDR_EL1 is the system register that holds the index of the current core in the low byte. 
- note that each core has its own version of the system registers so you have to 
  
see my code for waking all cores. 

idle task

you want something to do when all the threads are waiting for input/timers/whatever. 

wfi instruction so you don't just burn cpu spinning.

power off
- hypervizer call 0x84000008

userspace

the user space part is where you have more interesting choices than endlessly 
going down the list in the architecture manual of all the little features needed. 

a convenient starting point is doing a boring unix-ish thing where you just look at 
a list of functions in libc and implement them somehow. this makes it much easier to 
port other programs to the new system. 
for example the version of doom i use 
in the demo video at the start of this page 
is unmodified from one that runs on linux's framebuffer. 
it wants to call open(/dev/fb0) to get a file descriptor, pass that to ioctal() 
to query the size and colour layout to the screen and then call write to draw pixels on the screen. 
so to make that work, my program loader can "just" make its libc imports resolve to 
functions that hackily remap those calls on to the virtio-gpu frame buffer. 
for style points, the only files the system starts with are the source. 
when you exec the doom program, it jit compiles 
my c compiler and uses that to jit compile doom. 

in my program i took the easy way out on many design decisions because i just wanted 
to explore what it takes to make a program run. my virtual file system is entirely in userspace memory, 
the initial files (source of example programs) are baked into the kernel. 
the concept of thread groups ("processes") and the posix_spawnp function are in userspace 
and all my threads share an address space. i use virtual memory for convience not isolation. 
the virtio-gpu driver is in user space and since you need to give it physical addresses 
for where the frame buffer lives, there's a syscall for address translation (which indirectly 
lets you write to any physical address). 
this is all clearly a terrible idea if you're running programs you don't trust.

elf loader

if you want to use other people's compilers you probably want to write 

an elf loader. the part you actually need to support to get something working is fairly simple. 



if you notice a mistake here please tell me about it! i want to learn information! 
you can email anything@lukegrahamlandry.ca