← blog index

TempleOS programs in Linux user-space, part 2: Anatomy of a kernel

29 Mar 2020, last update 13 Apr 2020

Last time, we discussed why it might be desirable to run TempleOS on Linux in some form other than a full-blown virtual machine, and we teased some possible approaches. In the end, we commited to finding out whether it would be possible to run the standard kernel as a user-space program. Today, we will see what we are up against.

Being at the heart of TempleOS, the kernel, consisting of about 22 000 lines of source code, has several crucial responsibilities:

• Initialization and interfacing with hardware
• Memory management
• I/O services, including file management
• Task management and multi-tasking
• Providing a standard library of functions for compression, date/time handling, maths and string operations

The last bullet point demonstrates how closely TempleOS programs are coupled to the kernel, providing a very coherent experience for the programmer on the one hand, but a very difficult emulation target on the other hand. (Note the contrast with the Linux world for example, where the user space C runtime library interfaces with the kernel through a limited set of system calls. This architecture is what allows Microsoft’s WSL to work without any “real” Linux kernel).

Genesis

Since UEFI booting is not supported, the kernel is always born in 16-bit mode, with only one CPU core up and running. A compact 16-bit bootloader loads the entire binary kernel image at once, which limits its size to 640 KiB (and requires that the image is stored in one continuous block on disk). From there, roughly the following happens, in order:

KStart16.HC

1. VGA graphics is initialized via a BIOS call (if enabled at kernel compile time) [L84]
2. Memory map is discovered, A20 gate configured [L81]
3. PCI buses are enumerated [L147]
4. The load segment of the kernel is determined and stored into MEM_BOOT_BASE [L174]
5. A pointer to the kernel’s patch_table_offset is saved (this will come in handy later) [L181]
6. A minimal page table is set up and the processor is switched to 32-bit protected mode [L186]

KStart32.HC

1. (Boring: 32-bit control & segment registers are initialized for the first time) [L75]
2. The kernel is relocated to ensure that any absolute addresses in the code correspond to the actual kernel load address. [L95]
3. More “boring” x86 initialization (SYS_FIND_PCIBIOS_SERVICE_DIR, SYS_INIT_16MEG_SYS_CODE_BP) [L109+]
4. Finally, we enter 64-bit mode via SYS_ENTER_LONG_MODE

KStart64.HC

1. x87 FPU is enabled [L5]
2. Internal kernel structures are prepared (CPUStruct, Adam HeapCtrl, Adam stack) [L9+]
3. Adam task (aka init process) is established [L34]
4. We jump to KMain

KMain.HC

1. Enter KMain — the first HolyC code to run after boot
2. More internal structures are set up, but more importantly:
3. The kernel symbols are loaded and dynamic linking is performed via LoadKernel. More on this later!
4. Data structures for graphics are constructed
5. The white-on-black boot-time version banner is printed now (not to be confused with the other banner, printed by HomeSys after boot)
6. Hardware timers are configured, memory size is checked against the requirement of 512 MiB
7. Interrupts are enabled [L167+]
8. Block devices (disks, optical drives) are initialized and file systems mounted [L175]
9. The rest of the CPU cores are brought up [L199]. Note that while TempleOS suports a large number of cores, it is not SMP.
10. Keyboard & mouse input is initialized [L203]
11. The HolyC compiler binary is loaded. [L210] The kernel contains direct calls to compiler functions like ExeFile. How? The kernel is built against the Compiler headers, and these calls are only resolved at this point.
12. StartOS.HC is compiled and run just-in-time in context of the Adam task [L216]

StartOS.HC

(Now we are no longer in the AOT-compiled kernel, but for completeness, it is useful to understand the final steps of the start-up)

1. The JIT compilation context starts out as a tabula rasa. No function prototypes or global variables are known, only the basic built-in types.
2. Therefore, kernel headers must be parsed to gain access to its public functions, structures and exported variables. Since Adam is the father of all tasks, this environment will be inherited by all user programs. [L8]
3. The Adam code (MakeAdam.HC) is included. As with the kernel exports, all of these functions will be inherited by new tasks. [L18]
4. We proceed to build up the user space, opening a DolDoc window, starting up the window manager, and applying user customizations via MakeHome.HC
5. The OS is now ready to use. The kernel keeps running behind the scenes — handling interrupts, some timed events, and, of course, function calls from “user space”

Memory map

The virtual memory model model in x86 is super complex. And TempleOS uses none of it! In fact, the memory map is as simple as could ever be: virtual address space and physical address space are identity-mapped. The only things obstructing full access to the computer’s RAM are some BIOS areas and memory-mapped devices.

By default, memory access is cached. For accessing hardware, this is usually undesirable, so an uncached alias is available, which allows access to all of the same memory locations, but bypassing the cache entirely. (Keep in mind that the 64-bit address space is much larger than all the RAM you could ever have, so there is no point in trying to be economical)

Since the use of the uncached alias is so niche, from now on we shall pretend it doesn’t exists.

It is also worth noting that to reduce binary program size, TempleOS decidedly allows code to reside only in the lower 2 GiB of memory. (the technical reason is that this makes it possible to use 32-bit relative jumps everywhere)

There are such concepts as code heap and data heap, and the boundary is not always at 2 GiB, but the details are not terribly important. More details can be found in MemOverview.DD.

Kernel dynamic linking

Interestingly, the kernel is not compiled as a flat binary. The BIN format, which is also used for the AOT-compiled compiler, has a level of complexity comparable to 16-bit Windows Executables.

However, the kernel BIN file is constructed in such a way that the bootloader can jump into it directly and start executing. The first 2 bytes of the BIN header encode a jmp instruction to the first byte of the image (labelled SYS_KERNEL). Dynamic linking used later to fix-up addresses in the code, export functions to JIT code, and even to resolve some of the function calls internal to the kernel.

One way to explore BIN files is a command-line tool called bininfo. It generates a textual dump of the kernel’s headers which can be found here. Towards the bottom, you can see the imported functions (IET_REL_I32 entries). Note that the BIN file doesn’t give any hints about where these symbols actually come from.

We have to do some cross-referencing to find out that SET_GS_BASE is provided by the kernel itself. ExeFile, for example, comes from the compiler. But the rabbit hole goes deeper – certain functions, like DocSave, come from Adam. This means that the corresponding function pointers in the kernel are undefined until “sometime later” when the JIT compiler encounters their implementations through MakeAdam. Might the kernel attempt to call them before that? What would happen? Let us know once you find out!

Fun fact: 32-bit IET_ABS_ADDR relocations are also generated for labels in the 16-bit early initialization code. Of course, these are meaningless, because 16-bit code just uses segment-based addressing, and by the time the kernel relocates itself (and destroys whatever follows these 16-bit operands), we are already in 32-bit land.

Task scheduling

Since everything shares a single address space, TempleOS tasks (aka processes) are quite lightweight and context switching is very fast. Multi-tasking is cooperative — a task runs until it give up the CPU by calling Yield. Running tasks are organized in a doubly-linked list, with flags specifying which tasks are ready to run, and which are blocked, for example, waiting for external input.

Conclusion

There is much more that could be said, but for today, our time’s up. In part 3, we will finally do less talking, and more… doing. See you next month, class!

As a homework, you are invited to AOT-compile a simple TempleOS program and explain what is seen in the resulting BIN file headers.

---

Special thanks to the amazing combo of draw.io, Inkscape & nano!