Vex

Vex is a hobby operating system kernel written in C (gnu2x) and built with Meson. Limine boots it over UEFI. amd64 is the only implemented architecture: the Meson build knows the riscv64 and aarch64 names, but there is no kernel/arch/ code for them yet.

This book is the architecture guide. It explains how the kernel is put together and why each part is done the way it is. It is not an API reference: the declarations in kernel/include/ carry their own /// documentation, and clangd shows it on hover.

Where to start

• Build the kernel and the test image.
• Run it in QEMU.
• Source map to find where something lives.
• Overview for the whole picture.

How this book is organised

• Getting started covers the build, the test image and the source tree.
• Architecture describes the kernel-wide mechanisms: boot, memory, processes, system calls, the VFS, the device model.
• Drivers, Filesystems and Buses hold one page per implementation. A page exists when the implementation makes a decision worth explaining.
• Reference holds tables: syscalls, the ABI, capabilities, device names.
• Development covers testing and how to update this book.

Status

The getting-started pages are complete. Most architecture pages are still stubs. Until they are complete, docs/kernel/architecture.md describes the kernel-wide mechanisms, and CONTRIBUTING.md holds the full style rules.

Build

Meson and Ninja build Vex. Every build is a cross build: the kernel runs on amd64, and the host that builds it is some other machine. Meson stops with an error when the setup has no cross file.

Requirements

• Kconfiglib sits in contrib/kconfiglib. Python needs no extra packages.
• The build runs on Linux and on WSL. Native Windows is not supported.
• The test image tools and QEMU are only needed for the test image and for running.

Compilers

cross/amd64-clang.ini is the tested cross file. It uses clang, ld.lld and llvm-ar, and it adds -Wdocumentation, so a broken /// block fails the build.

cross/amd64-gcc.ini uses an x86_64-elf-* toolchain. The vex-os/bootstrap repository builds the kernel with it. Do not expect it to work without that toolchain.

The kernel link does not use the linker from the cross file. It calls ld from PATH directly, because Clang has no bare-metal driver for amd64. Install GNU ld, or make ld name LLD. Both understand the link script.

Configure

meson setup build --cross-file cross/amd64-clang.ini

The screenshot comes from a kernel checkout inside the vex-os/bootstrap repository, so its paths differ from yours.

The output names the cross file, the compiler, the host and the target, the generated files and the number of build targets. Meson reads x86_64 from the cross file and the build maps it to the amd64 arch name.

The setup options are:

To change an option after the setup, run meson configure build -D<option> and then ninja -C build. Meson reconfigures on its own when a Kconfig file changes.

Build

ninja -C build

The build writes the kernel to build/kernel/vexsys.elf. With the test layer enabled, the same command also builds the test programs.

The project sets werror=true and warning_level=2. A new warning fails the build. For a local experiment only, add -Dwerror=false at setup.

Configuration

Vex uses Kconfig, the configuration language that Linux uses. Kconfiglib is vendored, so the configuration works without a Linux source tree.

The model

The configuration is a tree of symbols. Each symbol has a type, a prompt, a default and help text. The types are:

• bool, on or off
• int and hex, a number with an optional range
• string, free text
• choice, one symbol out of a group

A symbol can depend on another symbol through depends on. It then exists only when that symbol is set. select forces another symbol on. This is how ARCH_AMD64 selects ARCH_HAS_SMP: the arch code offers SMP, and the generic code tests for it.

Each directory has its own Kconfig file. The file holds the help text for its options, so the description of an option sits next to the code that reads it. The menu shows that text.

The menu

ninja -C build menuconfig

The top level groups the options by subsystem. The entries follow kernel/Kconfig, which sources one file per directory.

The help pane shows the text from the Kconfig file, then the type, the default, the dependencies and the location in the tree.

A choice offers one value out of a list. The framebuffer font is one: the list holds every font that kernel/fbcons/Kconfig declares, and the chosen symbol names the file that the build converts.

The config file

The configuration lives in build/.config. At configure time, scripts/kconfig/sync_config.py does this:

• If build/.config exists, load it.
• If it does not exist, copy the defconfig into it.

The defconfig holds only the values that differ from the Kconfig defaults. configs/amd64_defconfig is empty for that reason: every option is at its default.

The defconfig is a seed, not a mirror. A change to the defconfig does nothing to a build tree that already has a .config. Delete build/.config, or run ninja -C build defconfig, to seed the tree again.

To change the defaults, run ninja -C build savedefconfig and copy build/defconfig over configs/<arch>_defconfig.

In the code

At build time, scripts/kconfig/gen_config_h.py turns .config into build/kernel/generated.config.h:

• an enabled bool becomes #define CONFIG_X 1.
• a disabled bool has no definition.
• an int, hex or string becomes a macro with its value.

The build force-includes that header into every kernel translation unit with -include. CONFIG_* macros are always visible, so never include the header.

meson.build gates an optional file:

if kconfig.get('CONFIG_EXT2', 'n') == 'y'
    subdir('ext2')
endif

Do not add an #ifdef around a whole file. The gate belongs in Meson, so the file does not build at all when its option is off.

How the build works

Kconfig tree -> build/.config -> generated.config.h
                                 (force-included in every unit)
kernel/meson.build
  +-- one archive for each top directory of kernel/
  +-- ld --whole-archive -T kernel/arch/amd64/kernel.ld
  +-- build/kernel/vexsys.elf

The archives keep the top directories independent. Each meson.build only appends its files to kernel_sources. The table in kernel/meson.build names the directories and the log tag of each one. A new top directory needs a row in that table.

The source map explains the directories and the archives.

Traps

• A change to the defconfig does nothing while build/.config exists.
• -Ddefconfig takes a file name inside configs/, not a path.
• The generated config header is force-included. Do not include it.
• An optional file needs a Kconfig symbol and a Meson gate, not an #ifdef.
• A top directory without a kernel_subsystems row is not built and does not exist as an archive.

Run

The Vex repository has no userspace. The kernel loads one program from the root filesystem and gives control to it. This page makes a disk that boots such a program, and explains what that program must do.

The test image boots kst, a test runner. It is one userspace, and the next page covers it. This page covers the general case.

What a boot needs

Three parts:

• Limine, the bootloader, as an EFI executable
• vexsys.elf, the kernel
• a block device with a root filesystem and an init program on it

The kernel receives one command line from Limine. It names the root device, the init path, the consoles and the log level.

The first process

In a Unix-like system, process 1 is the first user process. The kernel does not start a shell or a service manager. It starts one program, and that program starts everything else. Process 1 adopts the orphans and reaps the zombies. Linux, the BSDs and Vex all work this way.

Vex does this in kmain():

1. Run the BSP initcalls.
2. Mount the device from root= at /.
3. Open the program from init=, or CONFIG_DEFAULT_INIT.
4. Load it and spawn it.
5. Enable interrupts and idle.

See kernel/init/kmain.c.

In the test image, kst is process 1. A test runner needs the rights and the duties of init: it forks the tests, waits for them and owns the terminal. When it exits, the kernel panics, because init must not die.

The contract

The consequences:

• The program must open its own console. The kernel gives it no standard input, output or error.
• The kernel mounts only the root filesystem. If init wants /dev, it makes the directory and mounts devfs. If it wants /tmp, it mounts tmpfs.
• The executable must not have PT_INTERP or PT_DYNAMIC. The loader returns ENOSYS for both, so there is no ld.so and no shared library yet.
• Nothing reaps for init. It must wait for its own children.
• exit from init is fatal to the machine. Shutdown is a separate system call.

The working example is kst itself: it mounts devfs, opens /dev/tty1337, makes it the controlling terminal and duplicates it onto 0, 1 and 2. See ktest/kst.c.

Make a disk

The test image has a GPT disk with an EFI system partition, an ext2 root and a FAT partition for the FAT tests. A userspace image needs the first two.

The commands below make a 40 MiB disk with the same layout. The kernel and the bootloader go on the ESP, the root filesystem in the second partition.

# 1. An empty disk with an ESP and a root partition
dd if=/dev/zero of=vex.img bs=1M count=40

sfdisk --quiet --force vex.img <<'EOF'
label: gpt
start=2048,size=16384,type=C12A7328-F81F-11D2-BA4B-00A0C93EC93B,name=ESP
start=18432,size=53248,type=0FC63DAF-8483-4772-8E79-3D69D8477DE4,name=ROOT
EOF

# 2. The filesystems
mkfs.fat -F16 -s 1 --offset 2048 vex.img $((16384 / 2))
mke2fs -q -F -t ext2 -b 4096 \
    -E offset=$((18432 * 512)),root_owner=0:0 \
    -d root vex.img $((53248 / 2))k

# 3. Limine, the kernel and the config on the ESP
esp="vex.img@@2048s"
mmd -i "$esp" ::/EFI ::/EFI/BOOT
mcopy -i "$esp" contrib/limine/BOOTX64.EFI ::/EFI/BOOT/BOOTX64.EFI
mcopy -i "$esp" build/kernel/vexsys.elf ::/vexsys.elf
mcopy -i "$esp" limine.conf ::/limine.conf

The root/ directory holds the root filesystem. It needs an init program and the files that the program opens:

root/
└── init

mke2fs -d copies the tree, and root_owner=0:0 makes root own it. The partition sizes come from ktest/mkimage.sh. Any size works if the filesystem fits.

The @@2048s suffix is mtools syntax for an offset in sectors. mmd and mcopy write into the FAT filesystem inside the image without a loop device.

The Limine config

Limine reads /limine.conf from the ESP. On EFI it also tries the directory of its own executable, then /boot/limine/limine.conf, /boot/limine.conf and /limine/limine.conf. See the Limine configuration reference.

timeout: 0
verbose: yes

/Vex
    comment: Vex
    protocol: limine
    path: boot():/vexsys.elf
    cmdline: root=ada0n1p2 init=/init console=serial1,115200 serial=serial1,tty0
    kaslr: yes

• timeout: 0 boots the entry at once, with no menu.
• path is <resource>(<argument>):/<file>. boot() means the partition that holds this config file, which is the ESP.
• protocol: limine is the Limine protocol, which the kernel uses for its requests.
• cmdline is the kernel command line. See below.
• kaslr: yes asks Limine to place the kernel at a random base. The kernel asks Limine for its base address.

The config is a set of menu entries and options. A line that starts with / opens an entry, and the options after it belong to that entry. Lines that start with # are comments.

Boot it

qemu-system-x86_64 \
    -bios contrib/edk2/RELEASEX64_OVMF.fd \
    -machine type=q35 \
    -drive format=raw,file=vex.img \
    -serial mon:stdio \
    -vga std \
    -m 512M \
    -smp 4

• -bios loads the OVMF firmware. The repository vendors it.
• -drive attaches the disk as an ATA disk. The kernel names it ada0.
• -serial mon:stdio connects the first serial port to the terminal. Ctrl-A X quits QEMU, and Ctrl-A C opens its monitor.
• -vga std gives the kernel a framebuffer.

Under WSL, call qemu-system-x86_64.exe and convert the paths with wslpath -a -w. ktest/qemu.amd64.sh does this for the test image.

The kernel logs to the console. When the init opens its terminal, the init writes there too.

The example is the test image, because kst is the only init that exists today. The kernel log and the init share the serial port.

The command line

The kernel reads the command line as a list of key=value words. The keys that matter for a boot are:

The consoles are serial<N> for a serial port and fbd0 for the framebuffer. The kernel passes the options to the console. A serial console takes its baud rate. A key can repeat: one console= per console, one unit= per device.

Device names are <prefix><unit>n<index>p<partition>. In ada0n1p2, ada is the ATA class, 0 is the controller, 1 is the port or connector and 2 is the partition. The probe order decides the numbers. unit= pins a number to a node path, as /dev/hwtree shows it. The test image pins its serial ports for this reason.

loglevel takes verbose, inform, notice, warning, error, critical or alert. The default shows the important messages.

Consoles

The kernel can draw its log in two places at once:

• Serial. console=serial1,115200 sends the log to the first serial port. QEMU connects that port to the terminal with -serial mon:stdio.
• Framebuffer. console=fbd0 draws the log on the framebuffer that Limine set up. This is the fbcons backend, and it needs CONFIG_FBCONS.

The same boot on fbd0. The framebuffer console shows the kernel log only. The init writes to its own terminal.

Both consoles can be active. The test image sets both, so a failure to open the serial port still leaves the log on the screen.

Limits

• The init is static ELF64. Dynamic linking needs the loader support that does not exist yet.
• The kernel does not ship a C library. The system call numbers and the user ABI are in kernel/include/usr/vex/.
• The kernel mounts only root=. Everything else is the init’s job.
• An init that exits panics the kernel. Use the shutdown system call to stop the machine.

The test image and kst

ktest/ is the kernel’s own test image. It holds the Limine config, the script that makes the disk, the test runner kst and the test programs that kst runs. It is not the userspace: it exists to check that the kernel behaves as it should.

The image boots kst as init. kst runs on the kernel as a normal process, with the full capability set, and forks the tests.

The image

The image is a 40 MiB GPT disk with three partitions:

The kernel names them ada0n1p1, ada0n1p2 and ada0n1p3. Limine boots from the ESP and the kernel mounts DATA at /. The FAT tests write to ada0n1p3.

The ext2 partition holds a tree that the tests need:

• hello.txt, dir/nested/file.txt, a symlink and a long symlink
• empty/ and many/, the second with 200 long file names
• big.bin, 5 MiB, which reaches the double indirect block
• sparse.bin, a file with a hole
• dev/ and tmp/, the mount points that kst and the tests use
• kst.elf at the root and one ELF per test under kst/

ktest/mkimage.sh makes the disk. The offsets live in ktest/meson.build and in the script.

Build and boot

ninja -C build ktest-image    # build/ktest/vexsys.boot.img
ninja -C build ktest-run      # build the image and boot it

The image needs sfdisk, mkfs.fat, mtools (mmd, mcopy) and mke2fs. ninja -C build ktest-run runs ktest/qemu.amd64.sh, which starts QEMU with OVMF and attaches the image.

-Dktest=false at configure time excludes the whole directory, so the two targets disappear.

ktest/limine.conf.in is a template. The build fills in the port names:

The kernel command line is:

root=ada0n1p2 init=/kst.elf
unit=serial1,acpi:PCI0/pci:0000:00:1f.0/isa:3f8
unit=serial2,acpi:PCI0/pci:0000:00:1f.0/isa:2f8
serial=serial1,tty1337
console=serial1,115200 console=serial2,115200 console=fbd0

The config pins the ports with unit=. The probe order does not decide the names. serial1 becomes the tty tty1337, and kst opens it. The kernel writes its log to both serial ports and to the framebuffer console.

kst

kst is init. It does what an init must do:

1. Make /dev and mount devfs.
2. Open /dev/tty1337.
3. Make it the controlling terminal with TIOCSCTTY.
4. Duplicate it onto file descriptors 0, 1 and 2.
5. Set the line discipline for a serial terminal.
6. Clear the screen and print the banner.

Before step 2 it writes to kplog, because it has no output yet. If the terminal does not open, the message says so and names serial= on the command line.

The commands are:

run forks, execs /kst/<name>.elf and waits. The child leads a process group and owns the terminal. Ctrl-C then reaches the test, not the runner. The runner prints [ OK ] or [FAIL] with a timestamp for each program, and the reason for a failure: an exit status, a signal or a failed waitpid.

A test that draws on the framebuffer: the fbtest logo.

The same test fills the screen. The framebuffer test runs last, because it takes the machine over.

The QEMU wrapper

ktest/qemu.amd64.sh connects the shell port to stdio and the log port to kernel.log. It switches the terminal to raw mode: the terminal would otherwise echo each line and the guest would echo it again. Under WSL it calls qemu-system-x86_64.exe and converts the paths.

The script removes qemu.log and kernel.log at the start. The kernel log is also on the framebuffer console, which survives a crash that loses the file.

Ctrl-A X quits QEMU. Ctrl-A C opens the QEMU monitor.

After a run

The tests write to the ext2 partition. Check it after a run:

e2fsck -fn "build/ktest/vexsys.boot.img?offset=$((18432 * 512))"

The offset is the first sector of the DATA partition in bytes. e2fsck accepts the ?offset= suffix and reads the filesystem inside the image.

Tests

Each test is a separate ELF from ktest/test.<name>.c. ktest/meson.build lists them in ktest_programs, in the order that all runs them. A test returns 0 for success and checks with ktest_expect.

Writing a test explains the test ABI.

Source map

The kernel lives in kernel/. Each top directory is one subsystem, one archive and one log tag. This page explains the layout, the rules that keep the directories apart, and where new code belongs.

The tree

kernel/
|-- arch/amd64/   paging, CPU, IRQs, timers, ACPI glue
|-- bus/          PCI, ISA and IDE buses
|-- core/         kprintf, kplog, consoles, panic, cmdline
|-- crypto/       blake2s, chacha20, crc32
|-- dev/          block, char, fb, serial and tty interfaces
|-- device/       device tree, binding, resources, /dev/hwtree
|-- drivers/      storage, display, input, serial hardware
|-- exec/         binfmt registry and the ELF64 loader
|-- fbcons/       framebuffer console and fonts
|-- firmware/     fwnode providers, ACPI through uACPI
|-- fs/           VFS and the devfs, echfs, ext2, fat, tmpfs backends
|-- include/      the kernel API and the user ABI
|-- init/         kmain and the initcall runner
|-- ipc/          pipes
|-- irq/          IRQ core and interrupt controllers
|-- libk/         freestanding C support
|-- mm/           physical and virtual memory
|-- proc/         processes, threads, signals, syscalls
|-- random/       entropy sources, /dev/random, /dev/urandom
`-- time/         clocksources, clock events, RTC, wallclock

Archives

Each top directory builds into its own static archive. The table in kernel/meson.build names the directories:

• The key is the directory, such as fs or arch/amd64.
• The value is the log tag, such as KP_FS, that every pr_* call in that archive uses.

The archive receives the tag with -DKP_SUBSYSTEM=<tag>. A file that moves to another top directory logs under the new tag.

Two details follow from the table:

• A new top directory needs a row. Without one, the directory is not built.
• fbcons is a top directory that logs as KP_CORE. firmware also builds the vendored uACPI sources into its archive.

The build links the archives with ld --whole-archive. Every object then survives the link. That is what keeps the registration sections below intact.

Sections, not calls

A top directory does not call another directory’s init function. It registers an entry in a linker section, and one generic file walks that section. Four registries work this way:

The linker script keeps these sections and sorts the initcalls by name. The name starts with a stage number, so the sort gives the boot order. The order is: early, arch, bootinfo, pmm, slab, mmu, heap, irq, timer, syscall, multicore, bus, vfs, dev, fs, cpudev, binfmt, services, late.

This pattern is the reason the directories can stay independent. It also means that the boot order is data, not code: a new initcall belongs where its stage says, not where a call site says.

Headers

Rules:

• A generic header such as vex/pmap.h includes <arch/pmap.h> and declares the arch-neutral interface. Generic code includes the vex/ header only.
• A userspace header re-exports the __k_ types from usr/vex/ as _t typedefs, for example typedef struct __k_stat stat_t;.
• A filesystem has no public header. Other code reaches it through the VFS and names its driver with a string.
• A kernel service that needs files of its own has a public header under its own name, such as vex/shmem.h.

Headers under include/usr/ must compile as C89. Kernel headers use #pragma once only.

Generic and arch

kernel/arch/amd64/ mirrors the generic directories and implements their arch-specific halves:

kernel/mm/            kernel/arch/amd64/mm/
kernel/proc/          kernel/arch/amd64/proc/
kernel/irq/           kernel/arch/amd64/irq/
kernel/time/          kernel/arch/amd64/time/
kernel/firmware/      kernel/arch/amd64/firmware/
kernel/bus/           kernel/arch/amd64/bus/
kernel/core/          kernel/arch/amd64/core/

A file that the architecture implements lives in its arch directory. A file that the architecture only offers to the generic code lives in include/arch/. amd64 is the only implemented architecture. The build knows the names of riscv64 and aarch64, but there is no code for them.

Naming and placement

• Every kernel type has a _t typedef. The tag ends in _s, _u or _e: struct thread_s, union fat_entry_u, enum cpu_feature_e.
• A public function is <subsystem>_<verb>: block_interface_add_root, not add_block_interface_root.
• Name a variable after the stem of its type: thread_t* thread. A role name such as parent or curr is better when it says more.
• Use whole words in new names. Established terms stay: vnode, pmap, pslab, pdma, hart, irq.
• Do not rename an existing file. The short file names will be renamed together later.

Placement follows the device model:

• A driver belongs in drivers/<class>/.
• A class core, such as the tty layer, belongs in dev/.
• A device that shows a kernel subsystem to userspace stays with that subsystem: /dev/hwtree in device/, /dev/kplog in core/.
• A filesystem belongs in fs/<name>/ and registers with vfs_driver_add.
• Vendored code belongs in contrib/, not in kernel/.

CONTRIBUTING.md holds the full style rules.

Where to add things

A new system call needs no dispatch table change. The registration macro places the handler in the .syscalls section, and proc/syscall.c builds the table at the syscall stage.

Overview

Vex is one kernel binary. Limine jumps to kmain, the kernel prepares its parts through initcalls, and then it creates the first process. This page gives the layer map of the source tree and follows the path from boot to process 1.

The kernel has many parts, and no one function can prepare them in a safe order. An initcall places each preparation in a linker section, and one runner walks the sections. The code declares no layer object and no dependency graph. The map below groups the top directories by their work. The initcall stage order is the only boot order that the code states.

The layer map

arch/amd64/ is not only the bottom layer. It mirrors mm/, proc/, irq/, time/, firmware/, bus/, core/ and random/, and supplies the machine half of each. This map gives that machine half no entry of its own.

amd64 is the only architecture with code today. The build maps the riscv64 and aarch64 names, and the EDK2 and Limine binaries for both are vendored. A port adds kernel/arch/<arch>/ and implements the machine half of each mirrored directory. The generic half does not change.

kernel/include/ has no archive. It holds the headers that all layers include.

A directory is not a stage. One directory can add initcalls at several stages: random/ registers at early, bootinfo, services and dev. The stage of a call, not the directory, gives the boot order.

Each enabled entry in kernel_subsystems builds one static archive. The table gives each archive one KP_SUBSYSTEM tag, so its pr_* calls share a log prefix. ld links the archives into vexsys.elf with --whole-archive, which keeps an object that holds only a registration.

The path from boot to the first process

The linker script names kmain in ENTRY(kmain). Limine loads vexsys.elf and jumps to kmain. The kernel is position-independent, and it reads its real base from limine_executable_address_request.

kmain then does five things:

1. It prints the version banner.
2. It calls invoke_initcalls(initcalls_bsp_start, initcalls_bsp_end).
3. It mounts the filesystem from the root= device at /.
4. It loads init= or CONFIG_DEFAULT_INIT as the first process.
5. It enables interrupts and spins in hart_spin().

Interrupts are off for steps 1 to 4, and the scheduler does not switch yet.

An initcall is a { .function, .name } entry in a linker section. The macro initcall_bsp_<stage>(fn, order) writes it to .initcalls.bsp.<stage number><order>. The linker script brackets the BSP sections with initcalls_bsp_start and initcalls_bsp_end, and SORT puts them in name order. The stage number is the prefix in the section name. The order is one of INIT_FIRST, INIT_EARLY, INIT_MIDDLE, INIT_LATE or INIT_LAST.

The stages run in this order: early, arch, bootinfo, pmm, slab, mmu, heap, irq, timer, syscall, multicore, bus, vfs, dev, fs, cpudev, binfmt, services, late.

mount_root reads root= with cmdline_argument and finds the interface with block_interface_find. It calls vfs_mount for / with a null type. The VFS then probes each registered driver that has an ops->probe, and stops at the first that accepts the volume.

spawn_init calls process_create(nullptr). next_pid starts at INIT_PID, which is 1, so the process gets PID 1. It holds a reference to kernel_credentials, and its working directory is the VFS root. spawn_init then opens the program, loads it, and starts the user thread and the init_watchdog kernel thread.

load_binary finds the ELF64 loader because init_elf64 added it to the registry at the binfmt stage. thread_spawn_* only enqueues the thread. The first scheduler interrupt after enable_interrupts() switches to the init thread. The kernel does not return to the kmain stack.

The boot order is the dependency order. The dev stage adds the block interface and parses its partition table before kmain calls mount_root. The vfs and fs stages register the filesystem drivers before vfs_mount probes them. The binfmt stage registers the loader before load_binary asks for it.

Invariants and traps

• The stage is the dependency. An initcall uses only what an earlier stage prepared. slab_alloc before slab, or vfs_* before vfs, is a bug.
• The order is data, not a call list. No code runs the functions in sequence. The link must keep an object that no symbol references, and --whole-archive does.
• Within one stage and order, link order decides. Do not rely on it. Use a different stage or order.
• Interrupts are off in a BSP initcall. Do not block, sleep or take a lock that can block.
• bsp_ runs once, smp_ runs on every hart. The boot hart also runs the SMP stream, from init_hart_boot at multicore/INIT_LAST.
• An initcall cannot report failure. It returns void. invoke_initcalls has no error path, so an initcall calls panic().
• spawn_init starts one user process and one kernel thread. init is PID 1. init_watchdog is not a process.
• init must not exit. init_watchdog waits on init_exited, calls vfs_sync_all() and panics.

Limits

• The code has no declared dependency graph between directories. kernel_subsystems is a flat list of archives and log tags. Nothing stops fs/ from including a header of proc/, or a lower layer from calling a higher one. Real files cross the layers. core/kplog.c uses the char interface of dev/ and file_t of fs/. dev/tty_interface.c uses process_t and the scheduler.
• arch/amd64/ is not a bottom layer. It mirrors eight generic directories, and its code interleaves them, so a strict stack is a simplification.
• Only amd64 has code. The build maps the riscv64 and aarch64 names, but kernel/arch/ has no code for them.
• cpudev is a stage with no call. The order list is complete, but the stage is empty today.
• kmain starts no shell, service manager or second user process. Everything after process 1 is the job of init.
• init_hart_boot has no timeout. A hart that never reports online hangs the boot.
• The layer map describes the source tree, not a runtime boundary. Every layer runs in ring 0 with the same heap and the same direct map.

Source

Boot and init

Vex boots in three steps. Limine loads the kernel and jumps to kmain. The boot hart runs the BSP initcalls with interrupts off. kmain then mounts the root filesystem and starts init. This page follows that path. The full contract of the first process is in Run.

The handoff

Limine loads vexsys.elf, builds the page tables, and jumps to kmain (ENTRY(kmain) in the linker script). The kernel is linked at 0xFFFFFFFF80000000 and is position-independent, so Limine may slide it. The kernel reads the real bases from limine_executable_address_request. It does not assume the link address.

Limine gives the kernel a stack of at least 64 KiB, clears IF, and loads a GDT. The IDT is undefined, so the kernel loads its own. The kernel places its requests in .limine_requests with base revision 6. They cover the HHDM, memory map, MP table, executable address, command line and RSDP. They also cover the framebuffer, entropy, boot date and paging mode.

The Limine boot protocol defines the handoff, the machine state and each request.

The BSP initcalls

kmain() calls invoke_initcalls(initcalls_bsp_start, initcalls_bsp_end). Interrupts are off, and the scheduler does not run yet. The calls run in the order that the linker script gives them.

A subsystem declares a call with initcall_bsp_<stage>(fn, order):

static void init_ext2(void)
{
    ...
}

initcall_bsp_vfs(init_ext2, INIT_EARLY);

The macro writes a { .function = fn, .name = "fn" } entry into .initcalls.bsp.<stage><order>. For init_ext2, that is .initcalls.bsp.3100000.3. The stage is the suffix of the macro name, vfs. The macro gives the stage the number 3100000 in the section name. The order is INIT_FIRST, EARLY, MIDDLE, LATE or LAST. The linker script brackets the BSP sections with initcalls_bsp_start and initcalls_bsp_end, and it sorts them with SORT.

The stages

The stage and the order are the sort key. A call may use what the earlier stages prepared. This order is the dependency system. Within one stage and order, the link order sets the sequence. Do not rely on it. invoke_initcalls does not look at a return value. An initcall returns void and calls panic() on failure.

A bsp_ call runs once, on the boot hart. An smp_ call runs on every hart that comes online, the boot hart included. The SMP stages are hart, arch, irq, syscall, timer and late. bring_online runs them.

The APs

init_harts at arch/INIT_FIRST reads the Limine MP response. It registers each hart. It calls arch_start_hart to give the AP an entry point through goto_address. The AP enters hart_park, probes its CPU features, and waits.

The boot hart does not wait. It continues through the stages. At multicore/INIT_LAST, init_hart_boot sets the bring-up state to GO. It then waits until every usable hart reports online.

Each AP then runs run_idle:

1. Switch to sys_pmap.
2. Call bring_online.
3. Enable interrupts.
4. Halt in hart_stop until the scheduler wakes it.

bring_online calls hart_setup, runs the initcalls_smp_* stream, marks the TLB as online, and sets HART_FLAG_ONLINE. On amd64, the SMP stream initializes the GDT and TSS, the IDT, the PAT and the FPU. It also initializes the PIC, the LAPIC, the syscall entry, and the LAPIC timer on each hart.

The boot hart runs the same bring_online path inside init_hart_boot. After that call, its thread pointer is the boot hart’s idle thread. The static boot thread from arch_init_boot_thread is no longer current.

The first process

After the BSP initcalls, kmain() runs the last steps:

1. It prints the version banner.
2. It mounts the block device from root= at /.
3. It opens the path from init=, or from CONFIG_DEFAULT_INIT.
4. It loads the ELF through the binfmt registry and creates the process.
5. It spawns the user thread and the init_watchdog kernel thread.
6. It enables interrupts and spins.

The order matters. The dev stage attached the block driver and parsed the partition tables, so root= names a device. The binfmt stage registered the ELF loader, so load_binary finds it. The vfs stage registered the root source and the filesystem drivers, so vfs_mount can mount the root.

The process is PID 1. It has the kernel credentials, / as its working directory, no open file descriptors, and an empty environment. Run has the full contract.

init_watchdog waits on init_exited. When init dies, the watchdog syncs the filesystems and panics. Init must not exit.

sched_start at late/INIT_FIRST already sent the scheduler IPI to every hart. The boot hart has interrupts off, so its IPI stays pending until step 6. The first scheduler interrupt runs sched_irq_handler. That handler updates the clock, wakes expired waits, runs expired timers, and switches to the init thread. The kernel does not return to the kmain stack.

Invariants and traps

• The stage declares dependencies. A call may use only what earlier stages prepared. kmalloc before heap, or vfs_* before vfs, is a bug. The bug may survive until the first use.
• Interrupts are off. Do not block, sleep, or take a lock that can block in a BSP initcall. A blocking call cannot work. The scheduler switch needs interrupts enabled.
• The scheduler does not run yet. thread_spawn_* only enqueues. sched_start starts the ticks.
• bsp_ once, smp_ on every hart. The boot hart runs the SMP stream too, at multicore/INIT_LAST.
• Within one stage and one order, the link order sets the sequence. Do not rely on it. Use a different stage or order.
• The runner ignores return values. An initcall returns void. Panic on failure.
• init_hart_boot has no timeout. A hart that never reports online hangs the boot.
• The command line points into bootloader memory. init_cmdline_preserve copies it at heap/INIT_LAST. Use cmdline_argument after that point.
• The page tables change at mmu. Before init_mmu, the kernel runs on Limine’s tables. After it, the kernel runs on sys_pmap. The kernel maps the HHDM in the same step.
• cpudev is empty. The stage exists. No code uses it today.
• The link must include the whole archive. A registration is data that no code references. The link uses --whole-archive. Without it, the linker drops the object and the initcall.

Where the code is

Memory

The kernel gives each address one of three kinds and each frame one allocator. The kinds stop a physical address from becoming a pointer by mistake. The commit accounting rejects a mapping that the limit cannot cover.

user_addr_t is an address as a system call received it, not checked yet. virt_addr_t is an address in an address space, which the kernel cannot follow as a pointer. phys_addr_t is a physical address.

Three allocators hand out memory. pdma owns the frames below PDMA_APPROX_END, which ISA devices can reach. pslab owns single frames above that range. The slab allocator serves objects up to SLAB_MAX_SIZE. kmalloc builds the kernel heap from pslab pages. pdma serves a run of pages. pslab serves one page at a time.

An address space holds user translations below pmap_user_end and the shared kernel mappings above it. pmap_create copies the kernel half of the top-level entries from sys_pmap. A later kernel mapping does not reach the new address space.

What they share

The direct map reaches every range that memmap_is_ram_type accepts, at hhdm_base. phys_to_virt and virt_to_phys convert between the two names. Each frame below the top of usable RAM has a pframe_t from pframe_of(phys). It holds the reference count of the frame and the translations that reach it.

Four rules hold across the subsystem.

An address of one kind never takes the place of another. A number becomes an address through user_addr(), virt_addr() or phys_addr(). A virt_addr_t becomes a pointer only through virt_addr_pointer, and only while its address space is current. Memory that the kernel owns, such as the heap and the kernel stacks, stays a plain pointer.

A frame returns to pslab only when its last user drops it. A pmap_unmap call removes one translation and frees no frame. The reverse map in rmap.c lists the translations of a frame. A write fault uses it to tell whether it must copy.

A change to a translation that another hart may have cached needs tlb_shootdown. The pmap_*_noflush calls change the tables and leave the flush to the caller. A caller that unmaps many pages can flush once for a batch.

The kernel charges a private writable mapping when it appears, not when a page faults. counts_commit selects the regions that count: not device, not shared, not VMS_NORESERVE, and writable. So mmap, mprotect and fork fail at the call, not at the first touch. A stack is the exception: it grows on a fault and charges then. A shared anonymous mapping is a file with no name. The file takes its whole size from the commit limit, so the region does not count.

Pages

• Address types — the three address types, the _Generic operations in vex/address.h and the pointer rule.
• Physical memory — the memory map, pdma, pslab, the pframe_t array, the slab allocator and kmalloc.
• Virtual memory — pmap_t, vmspace_t and vm_region_t, the user half and the direct map.
• Commit accounting — commit_charge, the kernel reserve, VMS_NORESERVE and shared anonymous memory.

Limits

The kernel has no swap, so only the file cache returns frames under pressure, from fcache_reclaim.

The kernel fixes commit_limit_pages at boot. It is pslab_numpages minus the reserve, so free pages do not raise it. The reserve covers the slab, the kernel stacks and the page tables. They take pages from pslab without a charge.

mlock counts bytes in vmspace.locked_bytes against RLIMIT_MEMLOCK and pins nothing.

The pmap code is generic, but only the amd64 page tables have an implementation.

Address types

An address is a number, and C lets one number stand for any other. A user address, a virtual address and a physical address are not interchangeable. The same value names different memory in each. Vex gives each kind its own type, so that the compiler rejects a mix at the call.

The three types are the same size. Each holds one uintptr_t, and each passes in one register. The type names the kind of the address. It does not check that the address is mapped or that it is in range.

The three kinds

user_addr_t is an address as a system call got it, before any check. It is a transparent union with one member, uintptr_t value. A define_syscall handler takes it as a parameter. The dispatcher passes the raw register, so no cast is needed.

virt_addr_t and phys_addr_t are structs with one uintptr_t value field. Their shape is the same, and the types are still separate. A virtual address cannot take the place of a physical one.

A virt_addr_t is an address in the address space of a pmap_t or a vmspace_t. The kernel cannot follow it as a pointer. A phys_addr_t is an address in physical memory. The kernel reaches RAM through the direct map.

Operations

DEFINE_ADDRESS_OPS(kind, type) in address.h defines the same set for the three kinds:

• <kind>_addr() makes an address from a uintptr_t.
• <kind>_addr_add() and <kind>_addr_sub() move it by a size_t offset.
• <kind>_addr_diff() gives the distance from a low address to a high one.
• <kind>_addr_equal(), _less(), _less_equal(), _greater() and _greater_equal() compare two addresses of the kind.
• <kind>_addr_min() and <kind>_addr_max() pick one of two.
• <kind>_addr_null() and <kind>_addr_valid() test for zero.

All of them are static __always_inline __nodiscard. An address becomes a number through its value field.

The address_* macros dispatch with _Generic on the first argument. They are address_add(), address_sub(), address_diff(), address_equal(), address_less(), address_less_equal(), address_greater(), address_greater_equal(), address_min(), address_max(), address_null() and address_valid(). A second argument, where there is one, is an address of the same kind. The exception is the size_t offset of address_add() and address_sub().

Page operations live in page.h, because they need PAGE_SIZE: <kind>_addr_page_align(), <kind>_addr_page_align_up() and <kind>_addr_page_offset(). The generic page_align(), page_align_up() and page_offset() also accept a plain number through their default: branch. The first two give a uintptr_t for a plain number, and page_offset() gives a size_t.

Between the kinds

user_addr_to_virt() names a user address as one in the address space of a vmspace_t. It changes no bit and checks nothing. The vms_* functions check the range.

The kernel reaches a user page through the direct map, not by following the user address. access_begin_locked() in vms.c pins the page, calls phys_to_virt() on the frame, and adds page_offset(virt). Device memory is the exception. It is not in the HHDM, so the code calls virt_addr_pointer() on the user address. It does so only when that address space is current.

virt_addr_from_pointer() and virt_addr_pointer() convert between a kernel pointer and a virt_addr_t. The result of virt_addr_pointer() has a meaning only in the address space that is current.

phys_to_virt() and virt_to_phys() in hhdm.h convert between a phys_addr_t and a kernel pointer through hhdm_base. They return no virt_addr_t. They do not check that the address is RAM.

pmap_resolve_address() returns the phys_addr_t that a virt_addr_t maps to, or phys_addr(0). vms_pin() and vms_touch() return a phys_addr_t for an address in a vmspace_t, with the page offset added.

The user half

The user half of the address space ends at pmap_user_end(). The function computes the top from pmap->num_levels. Four levels give 0x0000800000000000. A start at or above that end is not a user address, and neither is a length that passes it.

user_range_ok() compares a virt_addr_t start and a size_t size with the end. user_range_end() in sys_mman.c does the same for a range that must be page aligned, and it rejects a zero length.

VMS_MMAP_TOP is 0x0000600000000000, and VMS_MMAP_MIN is 0x0000000000010000. A placement without a fixed address searches down from the first and stops at the second. Neither is a limit on a fixed mapping. vms_map() accepts one up to pmap_user_end(). The user stack ends at ELF64_STACK_TOP, 0x0000700000000000, which is above VMS_MMAP_TOP.

Invariants and traps

• address_diff(high, low) is valid only when high is not below low. The subtraction is unsigned, so the other order gives a huge size_t.
• address_add() and address_sub() do not detect a wrap. A size_t offset can wrap past zero or past the top of the address space.
• Zero is the failure value of the physical allocators. pdma_alloc_phys() and pslab_alloc_phys() return phys_addr(0), and the callers test it with address_null() or address_valid().
• For a user address, zero is a hint and not a failure. sys_mmap() tests address_valid(addr) to tell “no hint” from a hint. sys_mmap() still accepts a MAP_FIXED mapping at address 0.
• user_addr_to_virt() and virt_addr_pointer() check nothing. An address that the vmspace_t does not map becomes a pointer all the same.
• address_valid() says only that the value is not zero. It does not say that the address is mapped, in range, or in RAM.
• A check of the start of a range does not cover the bytes after it. in_user_space() in sys_thread.c compares one user_addr_t with pmap_user_end(), and the object at that address can still cross the end.
• phys_to_virt() accepts any value. A phys_addr_t outside RAM gives a pointer outside the direct map.

Limits

• There is no type for a range of addresses. Each call takes a start and an end of one kind, or a start and a size_t size.
• The code provides no operation that turns a phys_addr_t into a virt_addr_t. It goes through a kernel pointer with phys_to_virt() and virt_addr_from_pointer().
• There is no 32-bit user address type. amd64 is the only implemented architecture.
• The userspace ABI does not use these types. A user address in a structure under include/usr/ is a __k_uintptr_t.
• The address types do not keep a reference, a mapping or a lock. A virt_addr_t does not say which pmap_t gives it a meaning.

Source

Physical memory

The bootloader gives the kernel a map of physical memory. Two page allocators split that map. pdma owns the low 16 MiB, which ISA DMA can reach. pslab owns single pages above that zone. A slab allocator serves objects of up to half a page from pslab pages, and kmalloc builds its heap on pslab pages too.

A frame is one page of PAGE_SIZE bytes. One pframe_t describes each frame below the highest usable end.

The memory map

memmap points at the Limine memory map response. The request itself sits in .limine_requests. init_memmap() runs at bootinfo/INIT_FIRST and panics when the bootloader gives no map or an empty one.

memmap_is_ram_type() treats five Limine types as RAM: LIMINE_MEMMAP_USABLE, LIMINE_MEMMAP_ACPI_RECLAIMABLE, LIMINE_MEMMAP_ACPI_NVS, LIMINE_MEMMAP_BOOTLOADER_RECLAIMABLE and LIMINE_MEMMAP_EXECUTABLE_AND_MODULES. memmap_is_ram() checks a byte run against the map and follows the run across entry boundaries. Every byte of the run must lie in an entry of one of those five types.

Both page allocators take memory from LIMINE_MEMMAP_USABLE entries only. The other four types are not free, although memmap_is_ram() accepts them.

0x00000000  pdma: bitmap and pages, from USABLE entries
0x00FFFFFF  PDMA_APPROX_END, the end of the DMA zone
0x01000000  pslab zone; pslab excludes the pframe_t array
            each free pslab page points at the next

The kernel keeps the bootloader’s response, not a copy, so the map must stay valid for the life of the kernel.

The frame descriptors

pframe_of() indexes a pframe_t array with phys.value / PAGE_SIZE. pframe_phys() reverses it. init_pframe() sizes the array by the highest usable end in the map. The array therefore also covers a frame in a hole and a frame that no allocator owns.

The array lives in the first usable entry with room above PDMA_APPROX_END. init_pframe() runs at pmm/INIT_EARLY, before pslab, so pslab can keep the array out of its range.

refcount is 0 for a free frame. pslab sets it to 1 when it gives a page out, and pframe_incref() adds a reference for a mapping or a sharing. pframe_decref() decrements only a count above 1 and returns true when the count is 1. The caller frees the page at that point. PFRAME_PSLAB marks a frame that pslab manages.

pdma

pdma serves ISA DMA, which cannot address memory at or above 16 MiB. PDMA_APPROX_END is 0xFFFFFF. A bitmap with one bit per page tracks the zone, and a set bit means free. init_pdma() clears the bitmap and then sets the bits of each usable run, so a hole in the map never becomes allocatable.

The bitmap comes from the first usable entry below PDMA_APPROX_END with room for it, and that entry gives the bitmap pages up. pdma_numpages is rounded up to a multiple of BITMAP_CHUNK_BITS pages.

pdma_alloc_phys() finds a run of num_pages set bits, starting at pdma_lastpage and wrapping to 0 once. It clears the bits, records the new hint and returns page * PAGE_SIZE. pdma_alloc_virt() returns the direct map address of the same pages.

pdma_free_phys() sets the bits and lowers pdma_numused. pdma_lock protects the bitmap, and alloc and free take it with interrupts off.

pslab

pslab is a free list of single pages. init_pslab() adds every usable page at or above PDMA_APPROX_END + 1, less the range that pframe_storage() reports. It runs at pmm/INIT_MIDDLE, after pframe and pdma.

A free page holds the next link in its first sizeof(void*) bytes, so the list costs no memory outside the pages. take_page() pops a page under pslab_lock, sets refcount to 1 and returns the direct map address.

pslab_free_virt() asserts PFRAME_PSLAB, a refcount of 1 and no mappings, sets refcount to 0 and pushes the page. pslab_alloc_phys() and pslab_free_phys() convert through the direct map.

pslab can ask the file cache for pages. When the list is empty, pslab_alloc_virt() calls fcache_reclaim(RECLAIM_BATCH) once and retries if it frees a page. When fewer than RESERVE_PAGES pages remain, it reclaims ahead.

The slab allocator

slab_alloc() serves an object of up to SLAB_MAX_SIZE, which is half a page. The slab table has one entry per power of two from SLAB_BLOCKSIZE(0) to SLAB_MAX_SIZE, so nine sizes from 8 to 2048 bytes on amd64. init_slab() runs at slab/INIT_MIDDLE and starts each slab with one pslab page.

The table of slab_t comes from pdma_alloc_virt() and stays in the low zone. A page starts with a slab_t*, and the rest of the page is blocks. A free block holds the next free block in its first sizeof(void*) bytes. expand_slab() builds that chain when a slab runs empty.

slab_alloc() takes the slab of the exact size when one exists, and otherwise the first slab whose blocks are large enough. It zeroes size bytes, not the whole block. slab_realloc() copies min(sl->blocksize, size) bytes and frees the old block. slab_free() finds the slab_t* at the start of the page and pushes the block.

Who takes pages

• pdma: the slab table, the AHCI DMA area, the PATA scratch page and the bounce buffer of a block request.
• pslab: page tables, vms pages, the file cache, kmalloc, kstack and many small buffers.
• kmalloc maps its pslab pages from HEAP_REGION_BASE in sys_pmap, and describes each block with a memblock_t from the slab.
• kstack maps KSTACK_PAGES pslab pages into a slot in KSTACK_REGION_BASE and leaves the page below them unmapped as a guard.

Invariants and traps

• A pframe_t exists for every frame below the highest usable end, but only a frame with PFRAME_PSLAB belongs to pslab.
• pdma_free_phys() accepts any non-null address. It checks neither the zone nor the allocation that the address came from. A pslab page writes past the bitmap. A run that crosses a hole marks the hole free. Both decrement pdma_numused.
• pdma_alloc_phys() returns phys_addr(0) for a request of 0 pages and for a request larger than the zone.
• A pslab page comes back with its old contents, but its first sizeof(void*) bytes hold the free-list link. Neither page allocator zeroes a page. slab_alloc() zeroes size bytes of a block.
• The kassert checks in pslab_free_virt() vanish without CONFIG_KASSERT. A wrong free then corrupts the free list in silence.
• slab_free() cannot detect a double free. A second free with no allocation between makes a cycle in the free list of the slab.
• slab_alloc() returns nullptr above SLAB_MAX_SIZE. Use kmalloc for a larger object.
• A guard page is never mapped, so a stack overflow faults at once. kstack_is_guard() identifies the guard page of a slot in KSTACK_REGION_BASE.

Limits

• pdma is the only address-limited zone. There is no NUMA node, no high-memory zone and no memory hotplug.
• pdma cannot serve a page above PDMA_APPROX_END. A caller that needs a page above the zone uses pslab.
• pslab has one lock and one list. It has no per-CPU cache and no fragmentation control.
• The slab allocator has no constructor, no destructor, no per-object metadata and no debugging mode. Size classes are powers of two only.
• The heap does not charge the commit limit. It takes pslab pages, so a large heap leaves fewer pages for mappings. Commit accounting describes the limit itself.
• memmap_is_ram() scans the entries for each run. It has no interval index.

Source

Virtual memory

A program names addresses that no hart can follow as pointers. The kernel must give each page a frame at the first access. It cannot know in advance which pages the program will touch. It must also reach any RAM frame from its own code, at any time.

Three objects divide the work:

• pmap_t is a hardware page table.
• vmspace_t is the set of ranges that a program may name, as vm_region_t records them.
• The HHDM, the direct map, makes every RAM frame a plain pointer.

The page table and the region list have their own locks. The kernel half of every pmap_t holds the same mappings, and the HHDM belongs to all address spaces. The page table is the amd64 one. A port implements the same pmap_* functions for its own table format.

Page tables

pmap_t holds a root page (virt and phys), num_levels, a lock, and the counters resident_pages and peak_pages.

pmap_create() takes a root page from pslab and copies the entries from AMD64_PAGEMAP_START_KERN through PAGEMAP_SIZE - 1 from sys_pmap. Every address space therefore shares the kernel half and starts with an empty user half.

The copy takes entry values, not tables. init_mmu() creates every kernel top-level entry first, because a copy does not propagate later additions.

root table entry
             +-----------------------------------+
  0 .. 255   | user half: one program            |
             | pmap_create leaves it empty       |
             +-----------------------------------+
256 .. 511   | kernel half: shared by every pmap |
             | arch_pmap_kcopy copies it from    |
             | sys_pmap when the pmap is made    |
             +-----------------------------------+

pmentry_walk() descends from the root to a leaf or a large leaf. It allocates the missing tables on the way. pmentry_get() takes each table page from pslab. split_large_nolock() replaces one large leaf with a table of 512 entries, so that one page below it can change.

pick_leaf_level() keeps a user page at 4 KiB. A 2 MiB or 1 GiB leaf needs virtual and physical addresses aligned and the range at least that size. A 1 GiB leaf needs CPU_FEATURE_PAGE_1G.

pmentry_setup() encodes the VPROT_* bits. A user page with no right clears AMD64_PML_PRESENT and sets AMD64_PML_PROTNONE, because a present x86 page is always readable. pmentry_valid() accepts either bit.

pmap_release() frees the tables of the user half only. The kernel half belongs to sys_pmap.

Address spaces and regions

vmspace_t holds regions, a list sorted by start, its pmap and a lock. find_region() walks that list.

vms_map() inserts a vm_region_t and maps no page. The first access of each page faults. vms_unmap() splits the list at both ends with split_region() and drops the whole regions between them.

vm_region_t keeps vprot without VPROT_USER, because every user page has that bit. file and file_offset make a file mapping. shared, may_write, device, noreserve, grows_down and grow_floor describe how the range faults and what it costs.

The commit limit pays for a private writable region in alloc_region(), and free_region() gives the pages back. A read-only, shared, device or VMS_NORESERVE region takes nothing.

A pmap answers a virtual address with a frame. The rmap answers a frame with its mappings. rmap_map() writes the page table entry and adds an rmap_entry_t to the pframe_t. A frame then knows every pmap and virt that holds it. A device page has no pframe, so it stays out of the rmap.

rmap_pin() returns a frame with a new reference. It also sets sole when the frame has one mapping and no file cache (PFRAME_CACHE). A write fault uses that answer to choose between a patch and a copy.

vms_map_any() searches down from VMS_MMAP_TOP. The lowest address is VMS_MMAP_MIN, which keeps a null pointer dereference faulting.

Faults

isr.c reads CR2 and the error code, enables interrupts, and calls vms_fault() with VPROT_READ, VPROT_WRITE or VPROT_EXEC. A fault from the kernel itself panics.

fault_locked() runs under vmspace->lock and looks for the region. A page that no region contains may extend a stack down (grow_stack_locked()). The growth stops at grow_floor, and it needs a free STACK_GUARD_BYTES gap above the mapping below.

Then the fault checks the access against region->vprot. A device region goes to fault_device_locked(), which maps the frame that vnode_resolve_page() returns, with the cache bits of the node.

Anonymous memory takes a page from pslab, zeroes it and maps it with rmap_map(). A file calls vnode_fault(), which lets the filesystem map the page. A private page of a file starts read-only. A write to it reaches unshare_locked(). It patches the entry when the frame is sole. Otherwise it copies the page and calls rmap_replace().

A shared page becomes writable only on a write fault, and that fault marks it dirty.

A successful fault returns VMS_FAULT_MINOR or VMS_FAULT_MAJOR, and the handler counts it. -EFAULT becomes SEGV_MAPERR and -EACCES becomes SEGV_ACCERR. Any other error becomes SIGBUS with BUS_ADRERR.

vms_clone() maps every RAM frame of the parent read-only in the child. A private writable region loses write in the parent too, so both sides copy on the next write.

The direct map

hhdm_base comes from the Limine HHDM response. phys_to_virt() adds that offset and virt_to_phys() subtracts it.

map_hhdm() in mm/pmap.c walks memmap for memmap_is_ram_type() entries, merges runs that touch, and calls pmap_map_range() with VPROT_RW. It panics when a run fails. The mapping lands in sys_pmap in the kernel half, so every pmap_t shares it.

The HHDM covers RAM only. Device registers live in the window at MMIO_REGION_BASE. mmio_map() finds a gap there and maps the range into sys_pmap. It refuses a physical range that another mapping holds with a different memory type. mmio_unmap() keeps the entry until the last reference goes.

A device page of a user mapping is not in the HHDM. The kernel reaches it through the user mapping, and only while that address space is loaded.

Invariants and traps

• The locks nest in one order: vmspace->lock, then the rmap lock of the frame, then pmap->lock. The rmap lock runs with interrupts off.
• pmap_flush() invalidates one address on the local hart only. tlb_shootdown() raises tlb_generation and sends an IPI to every other hart, and each one flushes its CR3 in tlb_poll().
• A _noflush call leaves the old translation in a TLB. The caller runs tlb_shootdown() before the old entry can matter, or it knows that no hart used the address.
• vms_release() flushes nothing. No hart may have the pmap loaded.
• pmap_unmap_range_noflush() clears a large leaf only when the range covers all of it. It splits a leaf that the range covers in part.
• A frame that rmap_unmap() returns is the caller’s reference. The pmap does not free it. put_frame() does.
• vms_clone() takes only the lock of the source and needs vmspace->regions == nullptr.
• A file region that vms_release() frees goes to stale_regions and dies in release_thread, because file_close() can sleep.
• type_conflicts_nolock() refuses one physical range with two memory types. x86 leaves the result undefined.

Limits

• Only amd64 provides arch_pmap_*. The kernel detects 3, 4 or 5 paging levels from the bootloader response.
• A user page is always 4 KiB. There is no huge page for user memory.
• The page tables have no reclaim, and there is no swap. A table page returns to pslab only when the pmap goes.
• A device region works in the loaded address space only. The case of another one is marked UNDONE in access_begin_locked().
• vms_protect() cannot add write where may_write is false, and it removes write from a shared page.
• locked_bytes counts locked regions against RLIMIT_MEMLOCK. Each vm_region_t has a locked bit. mlock, munlock, and mlockall split regions at range edges. MCL_FUTURE charges new mappings. Nothing is pinned yet.

Source

Commit accounting

Vex reserves physical pages before it lets a process map memory that can become private and writable. The reservation is a count of pages, not a range and not an object. One global limit bounds the total of these counts.

A charge that the limit cannot cover returns -ENOMEM. A mapping call fails at that point, not at a later fault. The caller can still handle the error before it relies on the memory.

Shared anonymous memory and pipe pages use the same counter. The counter thus covers more than the writable mappings of a process.

The commit limit

init_commit() computes commit_limit_pages once, at the INIT_LATE stage of the pmm initcalls. The value is pslab_numpages minus a reserve for the kernel. The reserve is an eighth of the pages, or 4096 pages (16 MiB), whichever is larger. When the page count is not larger than the reserve, the limit stays 0 and the kernel logs a warning.

commit_charged_pages counts the charged pages. charge() updates it with a compare-and-swap, so any context can charge without a lock. A charge that fails takes nothing and returns -ENOMEM. commit_charge() takes pages with no credit, and commit_uncharge() gives them back.

cap_reserve_pages is a second slice, inside the limit. It is a 32nd of the limit, or 256 pages (1 MiB), whichever is larger. It never passes the limit. A charge with use_reserve set may use the whole limit. A charge without use_reserve stops at commit_limit_pages - cap_reserve_pages.

0            limit - cap_reserve         limit
+--------------------+------------------------+
| any charge         | use_reserve charges    |
+--------------------+------------------------+
|<------------- commit_limit_pages ----------->|

commit_charge_replacing() takes the pages that the caller will give back as credit. The total may then pass the limit by that many pages for a moment. A plain charge fails while the total is over the limit, until the caller uncharges the replaced pages. vms_map_replace() charges the new region, then removes the old one.

What takes pages

alloc_region() in vms.c charges a region when region_counted() is true. That needs four conditions. The region is neither device memory nor shared. It does not carry VMS_NORESERVE, and its protection has VPROT_WRITE. The charge is region_pages(), the page count of the range. free_region() gives the pages back.

• A private anonymous writable mapping charges for its whole range.
• A private writable file mapping charges too, because a write can make a private page. A read-only private mapping charges nothing until a mprotect adds write.
• A stack charges for its initial range at exec, which is at most 128 KiB. grow_stack_locked() charges the pages that a growth adds, at the fault that grows it.
• fork charges the private writable regions of the child again. The frames stay shared until a write, so the pair charges twice for the same frames.
• A tmpfs file charges for each page that its size grows by. shmem_file_create() sets the size of its file, so the whole file charges at creation.
• A pipe charges one page for each page that it holds.

mprotect can move a charge when it changes the write bit. vms_protect() charges the regions that gain a charge and uncharges those that lose one. mremap charges the pages that a growth adds. A move charges the new region, with the pages of the old one as credit. The old region uncharges when it goes.

MAP_NORESERVE

sys_mmap() sets VMS_NORESERVE only when the calling thread holds CAP_VM_NORESERVE. Without the capability the kernel accepts the flag and ignores it. A program that passes the flag out of habit gets the same charge as without it.

A region with VMS_NORESERVE takes nothing from the limit. An anonymous page of it comes from pslab at the fault. When pslab_alloc_phys() returns null, the fault fails with SIGBUS and BUS_ADRERR. The fault does not read the commit limit, because the region has no charge.

The capability has a second effect. may_use_reserve() reads it at each mapping charge, so a mapping without MAP_NORESERVE may use the cap reserve.

fork and mremap copy the noreserve flag of a region. They do not check the capability again.

Shared anonymous memory

MAP_SHARED | MAP_ANONYMOUS makes a file in the internal tmpfs. map_shared_anonymous() gives the page-aligned length as the size of the file. tmpfs_charge() then charges the whole size at once.

The mapping is a shared file mapping, so the region takes no charge. The charge belongs to the file, not to the region. A fork copies the region but not the charge, so two processes share one charge. See Shared memory.

MAP_NORESERVE does not remove this charge. The file takes its whole size from the limit when the mapping appears. A CAP_VM_NORESERVE holder can still make that charge use the cap reserve.

Invariants

• The charged total stays at or below the limit, except while a commit_charge_replacing() credit is outstanding.
• commit_uncharge() gives back pages that an earlier charge took. Its kassert fails when the counter is smaller.
• The reserve check uses the credentials of the calling thread, not those of the process that owns the mapping.
• A split keeps the total charge. split_region() copies the accounting fields, and each part uncharges its own pages.
• The kernel fixes the limit at boot. It does not follow the free pages of pslab, and kernel allocations come from the same pool. The reserve is headroom, not a hard boundary.

Traps

• MAP_NORESERVE without CAP_VM_NORESERVE is not an error. The mapping counts like any other.
• A shared anonymous mapping with MAP_NORESERVE still charges its whole size.
• A charge is not an allocation. The page does not exist until the fault, and a fault can still fail with SIGBUS when pslab is empty.
• fork charges the private writable memory of the child again. A process with a large private writable mapping can fail to fork at about half of the commit limit.
• A stack growth over the limit fails at the fault, with SIGSEGV. Only the initial range is charged at exec.
• tmpfs_charge() returns -ENOSPC when its page limit or the commit limit is full. shmem_file_create() turns that into -ENOMEM.
• commit_charged_pages uses relaxed atomics, so a concurrent reader can see a stale value. tmpfs_statvfs() reads it for the free space report.

Limits

• There is no reservation object and no record per mapping. The accounting is two counters and two reserved slices.
• There is no swap and no overcommit mode.
• Only a CAP_VM_NORESERVE holder gets the effect of MAP_NORESERVE.
• Device memory takes no charge. A device mapping is always shared.
• The kernel does not enforce RLIMIT_AS.
• There is no reclaim, and no charge shrinks under memory pressure. A charge goes away only when the pages are freed.
• The unit is PAGE_SIZE. A user page is never huge.

Source

Processes

A process holds an address space, a table of descriptors and one signal disposition table. A thread is the unit that the scheduler runs. A process starts with one thread, and sys_thread_create adds more.

kernel/proc/ creates and reaps processes, and creates, schedules and reaps their threads. Three pages follow:

Harts

A hart is one hardware thread of the CPU. harts[MAX_HARTS] holds one hart_local_t per hart. MAX_HARTS is CONFIG_MAX_HARTS with CONFIG_SMP, and 1U without it. num_harts counts the harts that arch_enumerate_harts registered.

Hart 0 is the boot hart, and boot_hart() returns it. The kernel counts a hart past MAX_HARTS in ignored_harts and leaves it unused. init_harts starts the others with arch_start_hart.

A secondary hart waits in hart_park on hart->bringup. init_harts marks a hart that cpucaps_merge refused with HART_BRINGUP_PARK, and init_hart_boot sets HART_BRINGUP_GO for the others. A parked hart never runs a thread. Boot and init give the full order.

Every online hart runs bring_online, so the initcalls_smp_* stream runs on each hart, the boot hart included. this_hart() returns this_thread()->last_hart: the hart that runs the thread now, or the last hart that ran it.

Each hart has one run queue, runqueues[hart->index]. Every online hart also has one idle thread that runs sched_idle. A hart with HART_FLAG_ONLINE set and HART_FLAG_ACTIVE clear is idle, as hart_is_idle reports. Only a hart that would otherwise idle takes work from another queue, in rq_steal.

A thread with no mask of its own, thread->affinity == nullptr, may run on every hart. A thread created from another thread inherits its mask. The first sys_setaffinity gives a thread without one a mask of SCHED_AFFINITY_WORDS words, with one bit per hart. A thread with bound_hart set runs only on that hart. Only the uACPI worker sets it.

What they share

The three mechanisms meet at thread->pending_work, a word of THREAD_WORK_* bits. A thread reads it on the way back to user mode. exit_to_user acts on it in a fixed order: THREAD_WORK_EXIT calls sched_terminate, THREAD_WORK_STOP calls job_park, and THREAD_WORK_SIGNAL calls signal_deliver. The scheduler never runs that work itself.

The pid and the tid come from one counter, process_alloc_id. The first thread of a process takes its pid as its tid, in attach_thread_user. A tid therefore never names a thread of another process.

The process keeps the resources. A thread keeps its process alive. attach_thread_user takes a reference with process_incref, and process_thread_reaped drops it when the scheduler frees the thread. When the scheduler reaps the last thread, the process gives up its vmspace with process_set_vmspace(process, nullptr). It then sets PROCESS_ZOMBIE and sends SIGCHLD to the parent. It stays a zombie until a waiter claims it with process_claim and calls process_destroy.

The lock order is signal_actions->lock, then process->lock, then a thread->sched_lock, then the run queue lock. rq_take_nolock holds the run queue lock and only tries the thread locks. Elsewhere sched_lock comes before the run queue lock. A held hart_lock means another hart is still on that thread’s stack.

A thread changes state only under its sched_lock. A wait follows one protocol. Register as a waiter under the lock of the waker, and call sched_dequeue before that lock is released. Then call sched_yield, and check the condition again. Without the first two steps, a wakeup gets lost.

Pages

• Scheduler — the run queue of each hart, nice, affinity and the tick.
• Threads — process_create, the kernel stack, kernel threads and the end of a process.
• Signals — the pending queues, the mask, delivery and job control.

Limits

• There is no hart hotplug. num_harts and the set of parked harts never change after init_harts.
• The only policy is SCHED_OTHER with priority 0. sys_setscheduler refuses every other policy, and sys_getschedparam reports priority 0. sys_sched.c marks SCHED_FIFO and SCHED_RR as UNDONE.
• A hart takes work from another queue only when its own queue has nothing it can run. The TODO in choose_hart notes that the tick does not balance queues between busy harts.
• nice is a field of process_t, not of thread_t. Threads of one process share one nice value, so their timeslices have the same length.
• The kernel cannot use more than MAX_HARTS harts. A machine with more harts runs on the first MAX_HARTS that the kernel registers.

Scheduler

Each hart runs one thread at a time. The scheduler chooses the next thread and gives the current thread a timeslice. It uses one run queue per hart, a per-thread affinity mask and the nice value of the process. All threads use SCHED_OTHER.

The scheduler has two jobs. It shares each hart among the runnable threads, so one thread cannot hold a hart forever. It also keeps a thread on a hart that the affinity mask allows.

Run queues

Each hart has a runqueue_t in runqueues[]. It holds a lock, a head and a tail for an intrusive doubly linked list of thread_t. num_queued is an atomic count that an idle or stealing hart reads without the lock.

A thread in THREAD_RUNNABLE is on exactly one run queue. A thread in THREAD_RUNNING is on a hart. A thread in THREAD_BLOCKED is on no queue. THREAD_DEAD is a thread that must leave its stack before the kernel frees it.

sched_enqueue() wakes a blocked thread. It calls choose_hart(), marks the thread THREAD_RUNNABLE and puts it at the tail of that hart’s queue.

choose_hart() returns bound_hart first. Otherwise it prefers last_hart, the hart that ran the thread last. It keeps that hart when the thread may run there. The hart must also be idle, or the thread must still hold its hart_lock. Otherwise it looks for an idle hart that the affinity mask permits. If every permitted hart is busy, it still returns one of them.

At a tick, rq_take_nolock() walks the queue from head. It takes the first thread that thread_may_run_on() permits and whose hart_lock and sched_lock it can acquire. A held hart_lock shows that another hart still uses the stack of the thread. The scheduler skips such a thread.

A hart that would otherwise idle calls rq_steal(). It tries the other queues in a rotating order, starting after its own index. When no thread is available, the hart clears HART_FLAG_ACTIVE, loads idle_thread and stops. sched_idle() sends itself a scheduler IPI when its queue becomes non-empty.

wake  sched_enqueue --> choose_hart --> rq_push_nolock
                                         |
tick  rq_take_nolock <-------------------+
           | empty
           v
       rq_steal --> next thread, else idle_thread

The queue does not order threads by priority. It is first in, first out. A thread that becomes runnable goes behind the threads that are already queued.

Priorities

Vex does not have priority queues. The nice value of a process changes only the timeslice of its threads. process->nice holds the value, and thread_t has no nice field.

CONFIG_SCHED_TIMESLICE sets the base timeslice in microseconds. The default is 5000, so SCHED_TIMESLICE_NS is 5 ms. init_nice_timeslices() builds the table for the 40 levels from NICE_MIN to NICE_MAX.

A step down from 0 multiplies the timeslice by 5/4. A step up from 0 multiplies it by 4/5. The result stays between SCHED_TIMESLICE_MIN_NS (100000 ns) and SCHED_TIMESLICE_MAX_SCALE * SCHED_TIMESLICE_NS, which is four times the base. sched_timeslice_for_nice() clamps a value outside the range to the nearest end.

A kernel thread has no process. It always receives the base timeslice. getpriority() returns NICE_BIAS - nice, with NICE_BIAS equal to 20. setpriority() clamps the value and checks ownership or CAP_SYS_NICE. A thread without the capability cannot lower a nice value below the floor that RLIMIT_NICE sets.

All threads use SCHED_OTHER. sched_setscheduler() rejects any other policy. It and sched_setparam() reject a nonzero sched_priority.

Affinity

thread_t.affinity points to SCHED_AFFINITY_WORDS words of 64 bits. Each bit is one hart. A null pointer means that every hart is allowed. thread_may_run_on() checks bound_hart first, then tests the bit of the current hart. bound_hart is an internal constraint for a thread that must stay on one hart.

thread_reserve_affinity() allocates a mask with every bit set if the thread has none. thread_set_affinity() stores the new words in place and calls affinity_changed(). It does not wait for the thread to move.

The words are atomic, but a mask update is not one transaction. A reader can see a mix of old and new words. That mix only changes where the thread goes next, and the next check corrects the choice.

affinity_changed() moves a runnable thread that sits on a disallowed hart. It removes the thread from that queue and wakes it on a permitted hart. For a running thread, it sends an IPI to the hart. At the next tick the thread becomes blocked and the scheduler enqueues it again.

The affinity system calls apply online_word() to the user mask. sched_setaffinity() fails with EINVAL when the mask has no online hart. sched_getaffinity() reports only online harts. sched_setaffinity() with a tid of 0 gives each thread of the process its own mask.

Preemption

A thread has preempt_count. preempt_disable() raises the count and preempt_enable() lowers it. spinlock_acquire() and spinlock_release() call both functions. A thread with a nonzero count must not be preempted. Another thread on the same hart could spin on the lock.

When the timeslice expires, sched_irq_handler() runs. If a running thread has a nonzero preempt_count, the handler sets need_resched and rearms the timer. It does not switch. preempt_enable() calls sched_yield() when the count reaches zero, need_resched is set and interrupts are enabled.

A thread that waits calls sched_dequeue() and then sched_yield(). sched_dequeue() marks the thread THREAD_BLOCKED and takes a runnable thread off its queue, but it does not switch. sched_yield() raises a self-IPI. The thread continues only after the scheduler picks it again. It requires interrupts enabled and preempt_count equal to zero.

For a live thread, the handler saves its context at thread_context(curr). It takes the next thread from a queue, or the idle thread, loads the chosen context and calls sched_enter(). The assembly sets %rsp to that context. It releases the old hart_lock only after the stack change. Another hart can then resume the old thread.

A wakeup does not replace the current thread at once. The scheduler sends an IPI only to an idle hart. The current thread then runs until its next tick or until it yields.

Invariants and traps

• A THREAD_RUNNABLE thread is on exactly one run queue. The scheduler changes its state under sched_lock and its queue links under the runqueue lock.
• When the scheduler holds both, it takes sched_lock before a runqueue lock. With a runqueue lock held, it only tries hart_lock and sched_lock.
• A thread taken from a run queue runs only after rq_take_nolock() acquires its hart_lock.
• sched_enter releases the hart_lock of the previous live thread only after the stack switch.
• The timeslice is not a hard limit. A thread with a spinlock can hold a hart past the end of its timeslice.
• A mask read can mix two updates. A running thread can stay on a disallowed hart until the next tick.
• The kernel does not free a dead thread on its own stack. The next tick reaps hart->dead_thread.

Limits

• SCHED_OTHER is the only policy. The constants SCHED_FIFO, SCHED_RR, SCHED_BATCH and SCHED_IDLE exist in the ABI, but the calls reject them.
• Nice changes the length of a timeslice only. It does not change queue order or select a different queue.
• Nice belongs to a process, not to a thread. Every thread of a process gets the same nice value.
• There is no periodic load balance. A TODO in sched.c records this limit. A busy hart keeps its queue, and only an idle hart steals from it.
• The kernel does not provide a user interface for bound_hart. Affinity is the only user control of placement.
• SCHED_AFFINITY_WORDS follows MAX_HARTS at compile time. A larger machine needs a new build.

Source

Threads

Vex schedules threads, not processes. A process_t owns the address space, the credentials, the descriptor table and the signal actions. A thread_t owns the register context, the kernel stack and the state that a hart needs to run it. The process ends when its last thread leaves. Scheduler covers where a thread runs.

The two objects

process_t in vex/process.h holds pid, ppid, flags and vmspace. It also holds the threads list, the child list, credentials, rlimits, the descriptor table and cwd. process.c caps its size at PROCESS_SIZE_BUDGET bytes with a static_assert, and it comes from the slab.

Every process sits in one bucket of proctable[PROCTABLE_BUCKETS], keyed by pid % PROCTABLE_BUCKETS and chained through hash_next. process_locate() takes proctable_lock with interrupts disabled, because the scheduler looks up parents there.

thread_t in vex/thread.h holds tid, state, the scheduling locks and affinity. It also holds pending_work, the signal masks and queue, usage, kstack_top, io_page and arch. Its process_next and process_prev links put it on the list of its process, under process->lock.

Process lifetime

process_create() builds the object and returns it with one reference. It creates the vmspace and takes the rlimits of the parent, or creates them. It allocates the signal actions and two SIGCHLD notes, exit_note and adopt_note. It takes the pid from process_alloc_id(). Then it adds the process to the child list of the parent and to the process table. spawn_init() calls it with nullptr.

A user thread comes from thread_create_user(), thread_create_fork(), thread_create_spawn() or thread_create_sibling(). Each calls attach_thread_user(), which adds the thread and takes a reference, so the process outlives it.

The exit has two halves, and one thread does not do both:

begin_exit
  sets PROCESS_EXITING once, records exit_code and exit_signal
  posts THREAD_WORK_EXIT on every thread
      |
      v
each thread, on the way out
  process_finish_exit: itimer, terminal, groups, files
      |
      v
the last reap, in the scheduler
  vmspace released, PROCESS_ZOMBIE set, SIGCHLD to the parent
      |
      v
the waiter
  process_claim -> process_destroy

begin_exit() sets PROCESS_EXITING with one atomic OR, so only the first call records exit_code and exit_signal. It posts THREAD_WORK_EXIT on every thread under process->lock and calls sched_kick() for each one.

A thread acts on that bit only when it returns to user mode, in exit_to_user(). A thread in an interruptible wait leaves that wait when the wakeup arrives. Nothing stops a thread in the middle of a system call.

process_thread_exit() decrements num_live_threads for a thread that is not already leaving. The thread that finds it at zero calls process_exit(process, 0). The process ends with its last live thread.

The half that may sleep runs in the exiting thread, not in the scheduler. process_finish_exit() cancels the itimer and hangs up the terminal of a session leader. It hangs up the groups that the exit orphans and calls release_files(). PROCESS_EXIT_FINISHED makes the call idempotent, and a filesystem close may block here.

process_thread_reaped() runs once for each thread that the scheduler frees. For the last one it releases the vmspace with process_set_vmspace(process, nullptr), because no hart has those page tables loaded anymore. It sets PROCESS_ZOMBIE and triggers init_exited for init. Then it sends SIGCHLD to the parent and moves the children to init.

The event goes out before the signal, so a handler that calls waitpid() finds the zombie. process_claim() then hands it to exactly one waiter. process_destroy() unlinks it from the process table and the child list and releases the files again. It also detaches the group and drops the reference that process_create() returned.

Thread lifetime

A new thread starts in THREAD_BLOCKED. The caller publishes it with sched_enqueue(), and the thread_spawn_* forms and sys_thread_create() do that themselves. A thread attached while the process is already exiting gets THREAD_WORK_EXIT at once under the same lock. So does a thread attached while another thread execs. Neither can slip past the walk in begin_exit() or process_dethread().

attach_thread_user() gives the first thread of a process the pid as its tid. A later thread takes a new id from process_alloc_id(), the same counter. That is why a tid never names a thread of another process.

sys_thread_create() receives the entry, the user stack top, the TCB, the argument and the address of the clear word. It checks each address against pmap_user_end() and then calls thread_create_sibling().

sys_thread_exit() leaves the process first, with process_thread_exit(), then clears the word at clear_tid and wakes the waiters on it. It ends in sched_terminate(), which marks the thread THREAD_DEAD and gives up the hart.

A thread never frees itself. The next tick on that hart calls reap_thread() on hart->dead_thread, when the stack is no longer in use. It drops the process reference, the credentials, the pending signals and the kernel stack with kstack_free(). It also frees io_page, the event list, the affinity mask and the thread_t.

Kernel threads and stacks

Every thread, user or kernel, runs on a kernel stack. kstack_alloc() takes a slot from free_slots, allocates KSTACK_PAGES pages from pslab and maps them VPROT_RW in sys_pmap. It returns the top of the stack, and the page below the stack stays unmapped.

The slots lie in one region, KSTACK_REGION_BASE. A slot is one guard page and then the stack, so KSTACK_SLOT_SIZE is (KSTACK_PAGES + 1) pages. KSTACK_NUM_SLOTS is CONFIG_MAX_THREADS, and free_slots has exactly that many bits.

The stack is mapped in every address space. A system call and an interrupt from user mode run on it. arch_thread_ctx_load() writes thread->kernel_rsp into TSS.rsp_0, and amd64_syscall_entry loads it from %gs:8.

The saved context sits at the very top of the stack, where the running code never reaches. thread_context() returns kstack_top - THREAD_CTX_RESERVE, and the live stack grows down from kernel_rsp.

A stack that runs off its bottom hits the guard page. The fault handler cannot run on the broken stack. On the double fault the handler reads CR2, and kstack_is_guard() decides whether to panic with a kernel stack overflow.

A kernel thread has process == nullptr, credentials set to kernel_credentials, the CR3 of sys_pmap and no FPU state. Its entry has the type kernel_thread_entry_t. arch_thread_setup_kern() enters it with the context as the initial %rsp. The code installs no return address: no kernel thread in the tree returns, and a kernel-mode page fault panics. init_watchdog in kmain.c is a kernel thread, and so is the idle thread of each hart, made by sched_init() with sched_idle. A system call that needs a process returns ENOSYS on one.

Invariants and traps

• A process flag is only ever set, with one atomic OR. PROCESS_EXITING, PROCESS_ZOMBIE, PROCESS_COLLECTED and PROCESS_EXIT_FINISHED mark the stages of the exit, and PROCESS_DID_EXEC marks an exec.
• A process that nobody waits for stays a zombie. It keeps its process_t and its pid, but no files and no page tables.
• Each thread holds one reference on its process, and each reaped thread drops it. The waiter’s process_destroy() drops the reference that process_create() returned.
• process_thread_exit() returns at once for a thread that already carries THREAD_WORK_EXIT, so num_live_threads cannot fall twice.
• attach_thread_user(), begin_exit(), process_dethread() and process_thread_exit() change a thread or the count under process->lock.
• process_dethread() makes the execing thread the only thread and gives it the pid as its tid. exec waits until num_threads is one.
• Signals no longer pick a thread once it carries THREAD_WORK_EXIT, and process_has_thread() reports it as gone.
• kstack_free() panics for any address that is not the top of a slot. A thread cannot free its own stack, and reap_thread() runs on another stack.

Limits

• There is no thread join in the kernel. clear_tid and the futex wake are the only notice, and user space waits for it.
• A thread has no name and no detached state. Creation takes the entry, the stack top, the TCB, the argument and the address of the clear word.
• CONFIG_MAX_THREADS caps kernel and user threads together, and the stack slots are static. A thread that finds no slot fails with ENOMEM.
• A kernel stack has a fixed size, CONFIG_KSTACK_PAGES pages. It does not grow, and every reap unmaps its pages.
• Nothing reaps an unclaimed zombie, and only init adopts the children of a dying process. There is no subreaper.
• No pid namespace exists, and a pid is never reused below a wrap.
• User space cannot create a kernel thread, and a kernel thread cannot return. A subsystem that needs one starts it from its initcall.

Source

Signals

A signal is an asynchronous notification to a process or to one thread. It reports a fault, a terminal event or a request from another process. The kernel queues it and chooses a thread that can take it. On the way back to ring 3, it builds a handler frame for a caught signal. The ABI follows POSIX: there are 64 signal numbers, and SIGRTMIN starts the real-time range.

The kernel sends a signal for a fault, a timer or a terminal event. Another process sends one through kill(2), tgkill(2) or sigqueue(2).

Delivery

A sender calls signal_send(), signal_queue() or signal_raise(). signal_queue() serves sigqueue(2), and signal_raise() serves the timer. signal_send() allocates a pending_signal_t. When memory is short, a standard signal still arrives, with SI_KERNEL if no entry waits for it.

Only a signal from SIGRTMIN up queues more than one entry in one queue. A standard signal sets one bit, and a second send to the same queue merges with the pending entry.

queue_signal() takes both locks, then chooses the thread. It drops a signal as ignored only when some thread could take it now. A blocked signal stays pending, because its action may change before it is unblocked.

choose_thread_locked() prefers the caller, then walks process->threads. It skips a thread that blocks the signal or has THREAD_WORK_EXIT. A signal for one tid goes to the queue of that thread.

recalc_locked() sets THREAD_WORK_SIGNAL when a thread has a deliverable signal. exit_to_user() handles that bit before it returns to ring 3. sched_kick() makes a running thread pass that point.

deliver() takes the lowest signal number first. It looks at the queue of the thread, then at the queue of the process. It removes the entry, or clears the bit, under signal_actions->lock.

A signal with the default action runs the action in default_actions[]. The actions are terminate, core, ignore, stop and continue. A signal with a handler gets a sigframe_t.

The init process is special. Only a signal it handles reaches it, and SIGKILL spares it, because its death stops the system. A fault that resolves to the default action still kills it, through signal_force().

signal_force() raises a fault signal for the calling thread. It turns an ignored action or a blocked signal into the default action. A fatal default action kills the process at once.

kill(2) -> signal_send -> queue of the process or of a thread
                              |
                        queue_signal sets
                        THREAD_WORK_SIGNAL
                              |
                   exit_to_user, on the way to ring 3
                              |
                signal_actions->actions[sig - 1]
                     /                     \
              SIG_DFL                  a handler
        stop, kill or ignore     arch_signal_setup

Masks

sig_blocked is per thread. sigset_t is a 64-bit mask, and sigbit(sig) maps a signal number to its bit. signal_mask() applies SIG_BLOCK, SIG_UNBLOCK or SIG_SETMASK.

SIGKILL and SIGSTOP are never blocked. sigaction(2) also removes them from sa_mask.

signal_replace_mask() saves the mask for a wait, and signal_restore_mask() puts it back. A handler restores the saved uc_sigmask through sigreturn.

A handler runs with the old mask, sa_mask and its own signal blocked. SA_NODEFER keeps its own signal unblocked. SA_RESETHAND resets the action to SIG_DFL.

fork copies the mask and the alternate stack. exec keeps the mask and the pending signals of the thread and the process. It clears the alternate stack and resets every handler except SIG_IGN.

Waiting

sigsuspend() replaces the mask and sleeps. A signal of the set ends the sleep and runs its handler on the way out. A stop does not end the wait. The process stays in the call when it continues.

sigtimedwait() takes a pending signal of the set without running its handler. It unblocks the wanted set for the time of the wait, and returns -EAGAIN on a timeout.

sigpending() reports the set that is pending and blocked. waitpid() and waitid() wait on process->child_exited.

wait_child() takes a zombie, or a stop or continue report, from job.report. WNOHANG returns zero when no child reports. SA_NOCLDSTOP suppresses SIGCHLD for a stop or a continue, but not the wait report.

An interruptible wait that gets a signal returns -ERESTART. The system call entry rewinds the call and sets thread->syscall_restart. A caught handler without SA_RESTART turns it into -EINTR. Otherwise the call runs again.

Job control

job_control_t holds the state of one process: JOB_RUNNING or JOB_STOPPED, the stop signal, two report bits and the resume event. process->lock protects the state. The report bits change with atomic operations.

job_stop() sets JOB_STOPPED, records stop_signal, sets JOB_REPORT_STOPPED and posts THREAD_WORK_STOP to every live thread. job_park() blocks a thread until the process runs again.

SIGCONT acts when it is sent. It purges the stop signals. A stopped process clears JOB_REPORT_STOPPED, sets JOB_REPORT_CONTINUED and triggers resume. A stop signal purges a pending SIGCONT.

SIGSTOP, SIGTSTP, SIGTTIN and SIGTTOU stop by default. A terminal sends SIGTTIN or SIGTTOU to a background group. A refused SIGTTIN, or an orphaned group, fails the access with -EIO. A refused SIGTTOU lets the access through.

process_group_orphaned_locked() says that no member has a parent outside the group in the same session. A terminal stop signal does not stop an orphaned group, because nobody could continue it.

An exiting session leader sends SIGHUP and SIGCONT to the foreground group. An orphaned group with a stopped member also gets SIGHUP and SIGCONT.

kill(2) sends to a process, a group or every process. kill_all skips the sender and init. may_signal() requires CAP_KILL or a matching uid.

Invariants and traps

• signal_actions->lock is always taken before process->lock. process_group_lock nests outside both.
• The kernel looks up a target thread under the locks that queue the signal. The thread therefore cannot be reaped in between.
• The kernel drops a signal as ignored only when a thread could take it now. A signal that is blocked at send time stays pending.
• A handler frame is never built inside a system call. signal_deliver_uncaught() leaves a caught signal pending for the return.
• The process dies when arch_signal_setup() cannot build a frame.
• A fault signal must not return to the faulting instruction. The kernel turns an ignored action or a blocked signal into the default action, which kills.
• signal_take() removes a pending signal, and no handler runs for it.
• A standard signal has at most one entry in a queue. Each real-time entry takes memory, and RLIMIT_SIGPENDING limits sigqueue(2) only.
• A zombie goes to exactly one waiter. process_claim() decides which one.

Limits

• There is no sigwait(), no sigwaitinfo() and no signalfd. The only synchronous wait for a signal is sigtimedwait().
• SA_SIGINFO passes the flag check, but no kernel code reads it. The frame always holds a siginfo_t, and the kernel always calls sa_handler with three arguments.
• SA_NOCLDWAIT passes the flag check, but no kernel code reads it. A zombie stays until a wait claims it.
• DEFAULT_CORE terminates the process like DEFAULT_TERM. The kernel writes no core file.
• RLIMIT_SIGPENDING counts the process queue and the thread queues together. kill(2), signal_send() and signal_raise() do not check it.
• A real-time signal can be lost when no entry is available and an entry of the same signal waits already.
• SI_TIMER, SI_MESGQ and SI_ASYNCIO are defined, but no kernel path sends them.

Source

System calls

A system call is how a process asks the kernel to do work for it. The number in a register selects a handler from one table. The handler reads the arguments and returns one value.

The mechanism has two halves. The generic half is the number blocks, the table, the dispatcher and the handler contract. The arch half is the entry stub, the register layout, the restart and the return to user. amd64 is the only implemented arch, so the syscall instruction and every register name on this page are amd64. The paragraphs that describe an instruction or a register say so. A new port supplies its own arch half and keeps the generic contract.

The path

 user space     | arch (amd64 today)  | generic kernel
 ---------------+---------------------+---------------------
                |                     |
 mov number/args|                     |
 syscall ------>| entry stub          |
                |  save the frame     |
                |  arch handler ----->| syscall_dispatch
                |                     |  table[number]
                |                     |  handler
                |  intptr_t      <----|
                |  restart and check  |
                |  exit_to_user ----->| deliver signals
                |  restore the frame  |
 sysretq <------| return stub         |

The middle column is the arch code. A port replaces it and keeps the right column and the table. The names in the middle column are roles. The amd64 functions are amd64_syscall_entry, amd64_syscall_handler and the return path in the same stub.

The arch half, on amd64

Vex uses the SysV AMD64 ABI for a system call, as Linux does. rax holds the number and the result. The arguments are in rdi, rsi, rdx, r10, r8 and r9. The fourth argument is r10 and not rcx, because syscall keeps the return address in rcx. The SysV ABI specification defines the rest of the register state.

The entry stub runs with the user stack still loaded. It swaps gs to the kernel base, saves the user stack pointer in thread::entry_scratch, and loads the kernel stack from the thread. It then pushes a hart_context_t frame with the user registers. usage_enter_kernel() runs before sti, so an interrupt in that window counts as system time. Interrupts are enabled when the dispatcher runs.

arch_init_syscall() sets EFER.SCE, STAR and LSTAR on every hart, and clears TF, IF, DF and AC in SFMASK. A call therefore starts with interrupts disabled and with a clear direction flag.

The generic code never names a register of the hart. It reads the frame through the syscall_number, syscall_retval, syscall_arg_1 to syscall_arg_6 and syscall_sp macros of <arch/hart.h>. A port defines these macros for its own registers, and its entry stub fills the frame. The port also supplies the restart rewind and the return path in the next section.

Dispatch

syscall_dispatch() reads the number through syscall_number. A number at or past syscall_table_size is not a call, and a null entry is not a call either. Both return -ENOSYS. The function copies the six arguments into an array, records the frame in thread::syscall_ctx and calls the handler.

thread::syscall_ctx stays valid for the whole call. fork, sigreturn and the job control code read it.

A handler returns intptr_t. A negative value is an error, and the absolute value is the errno number. Zero and positive values are results. The dispatcher stores the value through syscall_retval and returns.

The table

A handler declares itself with define_syscall(function, number, count). count is the number of registers that the call reads. The macro makes a syscall_t entry in the .syscalls section, and the linker script brackets that section with unsorted_syscalls_start and unsorted_syscalls_end.

init_syscall() builds the table once, at the syscall stage of the BSP initcalls. It sizes the table from the highest number, allocates it with kmalloc, and copies every entry into its slot. A duplicate number trips a kassert. A slot that no call claimed stays null. The table does not change after this point, and nothing removes a call.

Two other macros do work around the handler:

• define_syscall_fd resolves the first register as a descriptor and passes a file_t* in its place. The dispatcher holds a reference for the call and closes the file when the handler returns.
• define_syscall_dirfd copies the second register, a path, into a PATH_MAX buffer on the kernel stack. A path without a terminator fails with -ENAMETOOLONG. The handler gets the raw dirfd and the copied path, and resolves the base itself with syscall_dirfd() or syscall_resolve_at().

A new macro is for work that the dispatcher must do around every call of that shape. It is not for work that one handler does with its arguments.

Number blocks

Each subsystem owns a block of 32 numbers, and the block starts at a multiple of 0x20. A new call takes the next free number in its block. Number 0 stays invalid, so that a zeroed register fails with ENOSYS and not with a real call. A gap in a block also fails with ENOSYS.

Restart and signals

A handler that cannot finish yet returns -ERESTART. The arch handler keeps the number, rewinds the saved program counter to the entry instruction, and sets thread::syscall_restart. The call then runs again, unless a signal needs a handler first.

exit_to_user() delivers the pending signals. A caught signal without SA_RESTART replaces the restarted call with -EINTR and moves the program counter past the entry instruction. A signal with SA_RESTART leaves the rewind in place, and the call runs again. SYS_SIGRETURN is exempt, as its frame brings back the interrupted result register.

On amd64, the rewind and the skip are two bytes, the size of the syscall instruction. arch_syscall_interrupted() sets -EINTR in rax and moves RIP and RCX by the same amount. Before it leaves, the handler checks that the user RIP is below the end of the address space. A higher value kills the process with SIGSEGV, because SYSRET with such a value faults in ring 0 on Intel. If the frame no longer matches RCX and R11, the return goes through IRETQ instead of SYSRET.

Rules for a handler

• The signature of the handler is the signature of the call. The arguments are register-wide integers, except the object that a _fd or _dirfd macro passes in front.
• A call reads at most six registers. A seventh argument needs a struct or a pointer.
• A user pointer arrives as a user_addr_t. The handler copies through it with the user_* helpers, and never follows it as a pointer.
• A handler that the _fd macro wrapped must not close the file. The dispatcher owns that reference.
• The handler runs with interrupts enabled, and it may block.
• A negative return is an errno. Only -ERESTART is special, and only the arch return path sees it.

See also

• Syscalls lists every call, with its number, arguments and handler.

Source

Generic:

• syscall.c — dispatch, descriptors and path resolution
• syscall_internal.h — the registration macros
• syscall.h — the table entry and the dispatch interface
• syscall.h (usr) — the numbers
• signal.c — SA_RESTART and -EINTR
• user_exit.c — pending work on the way out

amd64:

• syscall.c — the handler, the restart and the MSRs
• syscall.S — the entry and exit stubs
• hart.h — the register aliases of hart_context_t
• kernel.ld — the .syscalls section

VFS

The VFS turns a path into an object. It gives every filesystem one interface. The rest of the kernel then reads and writes a file without the name of the filesystem that holds it.

The design follows the vnode interface of Kleiman: Vnodes: An Architecture for Multiple File System Types in Sun UNIX (PDF, 1986). A name and an inode are separate. A vnode stands for one inode. The VFS keeps no name cache. Its cache maps the inode number of a filesystem to the vnode of that inode.

The objects

A vfs_t holds the root vnode, the ops table of the driver, the block volume, the device number, and the flags readonly and unmounting. It also counts the vnodes that lost their last name but still have references.

A vnode_t holds its type, its filesystem, its inode number and the ops table. It holds the parent of a directory, the filesystem mounted over it, the page cache of the inode, and the list of file locks. vnode_alloc makes an uncached vnode. The filesystem fills it in lookup, create, mknod or symlink.

A file_t holds the vnode, the access flags, the offset and a mode word. The ctxdata field belongs to the vnode and its open op. file_dupe shares the same file_t, so two descriptors share one offset.

The interface itself is vnode_ops_t (vnode.h:64). A filesystem implements the operations that it supports. An operation set to nullptr fails in a default way that the VFS chooses. The table has no per-operation version number, so a new op needs a default in the VFS.

The cache

A vnode starts with a reference count of one. The caller that got the vnode owns that reference. The last vnode_decref does not free the vnode at once. It calls vcache_keep (vnode.c:691):

• The VFS destroys a vnode that has no cache entry at once.
• A vnode that has an entry goes to the tail of the unused list.
• The VFS destroys the oldest entries past CONFIG_VCACHE_MAX_UNUSED (1024 by default).

The cache keeps a vnode without references, so a second lookup of the same path costs no disk access. vcache_get takes an entry back from the unused list and gives the caller a new reference.

The cache key is the pair of fs and ino, not the name (vcache.c:21). An inode takes one vnode in the whole system. Two names of one inode, such as a hard link, share the same vnode.

A pinned entry belongs to its owner, which holds a reference until it calls vcache_remove (vcache.h:19). Devfs uses this for every device node (devfs.c:124). The pin fails with -EEXIST when another vnode already holds the key.

A file that loses its last name while it is open becomes an orphan. unlink marks the vnode orphaned and adds one to fs->orphans (vnode.c:310). The vnode lives until its last reference goes. The count keeps the filesystem from unmounting, because an orphan has no cache entry for the reference check to see.

vnode_destroy (vnode.c:706) drops the page cache, the file locks and the parent reference. It calls ops->release last, which frees the storage of the inode. A filesystem therefore frees its inode data in release, not in unlink.

Lookup and crossing

A lookup starts with a directory vnode and one name:

vnode_lookup(dir, name)
  |
  |-- vfs_cross_mount(dir) -> the root of a mounted filesystem, if any
  |
  |-- dir->ops->lookup(name) -> ino
  |
  |-- vcache_get(fs, ino) ------------ hit --> return the cached vnode
  |
  `-- vnode_alloc(fs, ino)
        |
        |-- fs->ops->fill_node(node)
        `-- vcache_get_or_insert(node)

The cache can already hold the node, because another thread looked it up in the meantime. vcache_get_or_insert then returns the cached vnode, and the caller destroys its new vnode (vnode.c:113).

A mount point changes the answer of every operation. vfs_cross_mount (mount.c:650) returns the root of the mounted filesystem in place of the mount point directory. Every operation that takes a vnode from a path calls it at the start. The vnode from a path lookup can be a mount point, and the operation that uses it crosses on its own.

A vnode that is not a directory never crosses. A mount point is always a directory.

vfs_cross_mount fails with -EBUSY while a filesystem unmounts. The operation then fails before it reaches the filesystem.

Paths

path_resolve_at walks one component at a time (path.c:170). Each component:

1. Must not be longer than NAME_MAX. The VFS returns -ENOTDIR for a longer one.
2. Needs X_OK on the current directory.
3. Goes through vnode_lookup.
4. Follows a symbolic link, unless it is the last component and flags contains PATH_NOFOLLOW.

The walk skips a dot component. A dot-dot component goes to parent_of, which climbs the mount stack: the root of a mounted filesystem stands for the directory that it covers (path.c:113). The walk stops at the root of the calling process. It never leaves that tree.

The walk reads a symbolic link into one page. A relative target continues from the directory that holds the link. An absolute target continues from the root of the process. The depth stops at 8 links, and the walk fails with -ELOOP (path.c:11).

A trailing separator means that the path continues, as POSIX says. link/ therefore follows the link even with PATH_NOFOLLOW, because the directory behind it must be a directory.

The root of the walk is per process. process.c sets path_set_root_source to the root of the current process (process.c:1068). chroot moves that root. A thread with no process root starts at the root of the VFS.

Two other entry points share the walk:

• path_resolve_parent_at resolves the directory that holds a new name and returns the name. file_open uses it for O_CREAT.
• path_build makes a path from a vnode. A vnode has no name, so it climbs to the root and iterates each parent directory to find the entry with the right inode number (path.c:376). A directory outside the root of the process fails with -ENOENT.

Mount and unmount

A driver declares itself with a vfs_driver_t and calls vfs_driver_add in a vfs stage initcall. The call needs a name, a mount op and an unmount op. A second driver with the same name fails with -EEXIST.

vfs_mount takes a path and a type. A type of nullptr asks each driver to probe the device: the first probe that returns 0 wins (mount.c:53). The VFS itself reads ro and readonly from the parameters and sets MNT_RDONLY from the flags.

vfs_mount_at does the part that needs a vnode. The mount point must be a directory. A second mount on the same directory fails with -EBUSY. On success the vnode holds the mounted filesystem in mounted_fs, and the filesystem holds the vnode in mountpoint. The VFS holds one reference to the mount point, and the driver holds one to its root. The VFS also adds the filesystem to its list of mounts.

kmain mounts the root with a nullptr mount point (kmain.c:39). That filesystem becomes the root of the VFS, and its root vnode lives in vfs_root.

vfs_create makes a filesystem that no path leads to (mount.h:73). It has no device and no mount point, it is not in the list of mounts, and nothing can unmount it. Pipefs and the internal tmpfs of shared memory use it. A driver marks itself internal to keep vfs_mount from mounting it by name.

A busy filesystem refuses to unmount. vfs_unmount_at first sets unmounting, so new operations fail. It syncs the page cache, then checks two counts (mount.c:470):

• fs->orphans must be zero.
• The sum of the reference counts of the vnodes must not exceed the references that the VFS knows about. Those are the references of the root and of the owners of pinned entries, plus one per cached directory with a parent.

The second check is exact. A leaked reference to a vnode fails the unmount with -EBUSY, and the leak stays visible.

Unmount then syncs the filesystem, removes the entry, clears mounted_fs, evicts every vnode of the filesystem, and calls ops->unmount. The driver drops its own state and the reference to its root.

Open files

file_open resolves the path. If the path does not exist and the flags have O_CREAT, it resolves the parent, checks W_OK | X_OK, and calls vnode_create. A lost race with another creator retries the lookup.

A create with O_EXCL, and any open with O_NOFOLLOW, resolves the last component with PATH_NOFOLLOW, so a symbolic link there counts as an existing name.

file_open_node then applies the checks that need the vnode (file.c:89):

• O_DIRECTORY needs a directory.
• A write to a directory fails with -EISDIR.
• A write to a regular file on a read-only filesystem fails with -EROFS. A device node stays writable, because its filesystem is not its device.
• O_TRUNC removes set-id bits and file capabilities first, then sets the size to zero.

The file layer decides if a file is seekable by asking vnode_seek(..., SEEK_CUR). A file that answers -ESPIPE is a stream, such as a FIFO or a terminal. Every other answer makes the file seekable (file.c:136).

file_read and file_write take a pointer to the offset. A normal call passes &file->offset. pread and pwrite pass a private copy, so they do not move the shared offset. The file layer ignores O_APPEND: the caller picks the position.

A write to a regular file stops at RLIMIT_FSIZE. A write that starts at the limit fails with -EFBIG and sends SIGXFSZ to the calling thread. A file that is longer than the limit can still shrink.

The last file_close releases the file locks of the open file, calls vnode_close, drops the vnode reference and frees the file_t.

Two kinds of lock live on the vnode: a POSIX record lock, which belongs to a process, and an open-file lock, which belongs to a file_t (file_lock.h:14). The VFS keeps the ranges in a list on the vnode. A process loses its locks on a file when any descriptor of that file closes (process.c:210). The conflict test, the wait and the deadlock check are in file_lock.c.

The page cache

Every vnode has an fcache_t (vnode.h:203). It holds the pages of the inode by page index, and it is the only cache of file data. A filesystem passes its block map to fcache_read, fcache_write and fcache_fault. The cache calls back for the sectors that it needs.

A page that a caller dirties goes to one global write-back queue. A thread writes the queue back at CONFIG_FCACHE_WRITEBACK_MSEC intervals. A write that finds more than CONFIG_FCACHE_DIRTY_PERCENT of memory dirty writes its own file back before it returns. fcache_sync writes back one filesystem, and unmount calls it.

A tmpfs vnode sets the cache to memory mode (fcache_set_memory): the pages are the only copy, they are never dirty, and a hole reads as zeroes.

The cache lives inside the vnode, so the vnode’s lifetime sets its lifetime. vnode_destroy deinits the cache, and the deinit asserts that the vnode is not on the write-back queue.

Invariants and traps

• The cache key is (fs, ino). A filesystem must give one inode number to one file. A filesystem whose inode number follows the location of the entry calls vcache_rekey after a rename (vnode.c:423).
• The last-name rule. When the last name of an inode goes, the filesystem calls vcache_remove under its own lock, before the entry can be reused (vnode.h:85). Otherwise a new file at that location gets the vnode of the old one. The VFS cannot do this for the filesystem, because only the filesystem knows which name was the last.
• The VFS holds no filesystem lock. Each filesystem serializes its own operations with one mutex (ext2_internal.h:386, fat_internal.h:173, echfs_internal.h:79, tmpfs_internal.h:19). The VFS locks are narrow: mounts_lock for the mount list and the crossing, cache_lock for the cache, drivers_lock for the driver list. No filesystem call runs under one of them.
• The per-vnode lock is not the file lock. It guards the parent link and the capability snapshot. It does not guard the ops.
• One mutex covers every rename in the kernel. The mutex (vnode.c:48) also covers the cache steps of the rename, so they cannot interleave with another rename.
• Crossing happens at the operation, not at the lookup. A path can end on a mount point. The vnode is the mount point, and the next operation crosses it.
• A dot-dot never leaves the root of the process. The check is current == root, not “the parent is null” (path.c:231).
• A missing op has a default. lookup, create, unlink, rename, read, write and stat fail with -ENOSYS. mknod, link, symlink and set_attr fail with -EPERM. fallocate and the xattr ops fail with -EOPNOTSUPP. mmap succeeds.
• The VFS owns the parts that every filesystem would repeat. It applies the read-only check, the new-name check and the rename checks. It also applies the access time policy, the capability removal on write, and the namespace split of xattrs. A filesystem stores xattrs and does not check their permissions.
• Access time follows CONFIG_ATIME_*. The VFS sets it on a successful read and on the start of a directory iteration, through set_attr (vnode.c:479). A read-only filesystem and a filesystem without set_attr never get one.
• A directory holds a reference to its parent. The chain ends at the root, which has no parent. This reference is why the unmount check counts expected references. The check does not test for zero.
• vnode_fault, vnode_mmap, vnode_resolve_page and vnode_fallocate do not cross a mount. They run on the vnode of an open file. A mount point is a directory, so a file vnode never needs the crossing there.

Limits

• The VFS keeps no name cache. Every lookup of a component asks the filesystem for the inode number, even when the cache holds the vnode. A name cache would need invalidation from every filesystem.
• One mutex covers all renames in the kernel. Two renames on unrelated filesystems wait for each other.
• The unused list of the cache is global. A filesystem that fills it evicts the unused vnodes of the other filesystems.
• A device node on a filesystem other than devfs does not open. device_node_open returns -ENXIO, because the kernel has no table from a device number to an interface (vnode.c:215).
• There are no mount namespaces. The kernel has one tree of mounts. A process root is the only per-process view of it.
• There is no lazy unmount. A busy filesystem stays mounted until its last user goes.

Source

Device model

Vex must drive hardware that firmware describes and hardware that code finds. kernel/device/ holds one tree of device_t nodes for this. A bus adds and removes the nodes that it finds. A driver claims a node and publishes an interface on top, which devfs shows to userspace.

After init, the tree changes only on device_worker, one kernel thread. Probe, attach and detach run there. A driver can sleep during attach, and the tree needs no lock around driver code.

The device tree

device_get_root() makes the root on the first call, from fwnode_root() when the firmware describes one. The root has id 0 and the name "". Every other node takes the next value of next_id, so no id repeats. device_add() adds a child below a parent and gives the caller a new reference to it.

All children of a parent share one list through priv.next and priv.children. add_node() walks that list and returns -EEXIST for a name that a sibling already has. A name is unique among siblings only, not in the tree. device_get_path() writes the path from the root, such as acpi:PCI0/pci:0000:00:1f.0/isa:3f8.

A child holds a reference to its parent. The tree holds one reference to each node, and device_add() gives the caller another. device_decref() frees a node at its last reference. It asserts that its children, interrupts, mappings, providers, consumers and waits_for are all empty. remove_node() takes the node out of the list and then drops the tree’s reference. A node that others still hold stays alive.

copy_resources() copies the resources of the node’s firmware node. It skips a range with FWNODE_RANGE_WINDOW, which a bridge passes on to its children. The copy holds at most DEVICE_RESOURCE_MAX (16) entries.

device_sync_firmware_children() compares the firmware children with the tree. It places a present child through bus_ops->place_child(). When that op returns -ENOENT or is missing, it adds the child as an unplaced node. It removes an absent child only when firmware_judges() is true. The test holds for an unplaced child. It also holds when the parent is not a bus, or has no rescan op. A bus with rescan judges its own children.

device_bus_of() returns nullptr for an unplaced child, even when the parent is a bus. Such a child uses its firmware description for ranges and interrupts, and the parent bus ignores it.

device_set_gone() marks the node and its subtree as gone. device_is_gone() is true for that flag, or for the state DEVICE_GONE. A bus that lost the hardware calls it before it queues the removal.

device_worker

Every change after init goes through the worker:

   device_queue_request(node, request)
        |  pending |= request, one reference, enqueue once
        v
   queue_head --> device_worker
                     |  queue_pop, then run_queue
                     v
   EJECT > REMOVE > UNBIND, then RESCAN
                     |
                     v
   bind -> wait -> attach -> rescan children

device_queue_request() accepts any context. It sets the bit of the request in priv.pending under queue_lock, puts the node in a FIFO once, takes a reference, and triggers worker_wakeup. A second request for a queued node only sets another bit.

run_queue() pops the node and takes all pending bits. It acts in this order:

1. DEVICE_REQUEST_EJECT runs eject_node(), which calls fwnode_eject().
2. DEVICE_REQUEST_REMOVE runs take_offline(), then remove_node().
3. DEVICE_REQUEST_UNBIND runs take_offline(), then unbind_node().
4. DEVICE_REQUEST_RESCAN runs rescan_node().

A removal or an eject makes the other requests of the node moot. An unbind comes before a rescan, so a node asked for both ends up bound anew. take_offline() calls offline on every child and consumer first, and on the node last. If any of them refuses, online_node() restores all of them and the request does not happen.

init_device_tree() runs at INIT_LATE. It warns about each driver that is_complete() rejects, and makes the root. The scheduler does not run yet, so it rescans the root on the spot and then starts the worker.

/dev/hwtree reports each change. Its ioctls queue a rescan, an unbind or an eject for a node id. Userspace never changes the tree directly.

Probe and attach

is_complete() accepts a driver only with detach and release, and with both offline and online or neither. init_device_tree() warns about the other drivers and leaves them out.

bind() walks the drivers_start to drivers_end range, which the .drivers section fills through define_driver. For each driver it takes the first driver_match_t that matches and calls probe(). The probe returns a DRIVER_SCORE_* level, a higher value, or -ENODEV. It never returns zero.

The device goes to the driver with the highest score. A tie goes to the driver that comes first in the section. attach() then runs with no tree lock, and may sleep.

On success the node gets driver and the state DEVICE_BOUND. device_wake_waiters() then queues a rescan of every node that waited for it.

On failure:

• attach returning -EAGAIN with a dependency sets DEVICE_WAITING. The node attaches later, when device_wake_waiters() queues its rescan.
• Any other error sets DEVICE_PRESENT and attach_failed. A rescan does not bind the node again.
• undo_attach() runs device_release_resources() and release(), and clears ctxdata.
• The device stays unbound. It does not fall back to a lower-scored driver.

device_wait_for_dependencies() walks fwnode_for_each_dependency(), which ACPI’s _DEP fills. device_wait_for() links the consumer to a bound provider, so unbind_consumers() unbinds the consumer first. It returns -EDEADLK for a cycle and -ENODEV for a provider that is gone. A provider that is not bound yet gives -EAGAIN. device_request_irq() calls device_use() for the controller of the GSI.

Interfaces

A node is not a file. A driver publishes a block_interface_t with block_interface_add_root(), or a char_interface_t with char_interface_add(). The interface has a name from dev_name_t, an ops table and a reference count. Its device pointer names the node, and the driver sets it before the add.

devfs subscribes to the block and char event buses and mirrors each interface as a vnode. A block interface with BLOCK_FLAG_HIDDEN gets no vnode. It forwards the vnode operations to the interface, so userspace reaches a device only through that interface. The interface name follows Device names.

char_interface_t serves a byte stream: open, read, write, seek, ioctl, poll, mmap and resolve_page. block_interface_t serves sectors through the submit op. A driver for a terminal line, a serial port or a framebuffer embeds a char_interface_t. The containing type is tty_interface_t, serial_interface_t or fb_interface_t, and the ops belong to that core.

device_request_irq() and device_map_io() record what device_release_resources() takes back. That happens after the driver detaches the device, or after its attach fails. The framework does not remove an interface. detach() removes it, and release() frees the state.

Invariants and traps

• device_t state changes only on device_worker.
• device_tree_mutex guards children, next, the provider and consumer links, and the interrupt and mapping lists. No driver call runs under it.
• A child holds a reference to its parent. A node cannot outlive its children.
• A failed attach is final for the node: a rescan does not bind it again. An unbind clears attach_failed.
• An offline refusal cancels the whole request. online_node() undoes every offline that succeeded.
• A resource list holds 16 entries. collect_resource() drops the 17th entry without an error.
• device_bus_of() ignores the bus of an unplaced node. A child that bus_ops->place_child() rejected gets no bus translation.
• remove_node() unbinds the root but leaves it in the tree.

Limits

• There is one worker thread. A slow attach delays every other node.
• After a failed attach, the node waits for an unbind, and no other driver gets the device.
• The tree has no device class, no power management beyond offline and online, and no user-space driver.
• Hotplug comes only from a rescan. A bus finds its hardware, a firmware notify starts one, or userspace asks for one.
• Sibling names are unique. Names at different depths need not be.
• A name that does not fit DEVICE_NAME_MAX (32) bytes truncates silently.
• A path that does not fit DEVICE_PATH_MAX (256) truncates silently.
• An interface is the driver’s to remove in detach(). The framework never removes one, so a driver that skips it leaks the interface.

Source

Interrupts

A device raises an interrupt when it needs the CPU. The CPU suspends the running thread and takes a vector from the IDT. One stub saves the registers, and irq_dispatch() calls the handler that a driver registered. The mechanism turns a hardware signal into a call of a C function.

Three numbers appear on that path, and the page keeps them apart. A vector is an index in the IDT. An IRQ number is an index in the handler tables of kernel/irq/irq.c. A GSI names an input of an interrupt controller, and the firmware or the bus gives it once.

The hardware on this page is amd64: the IDT, the 8259 PIC, the IOAPIC and the LAPIC. A port implements the same arch_* entry points for its own controller model.

Vectors

The IDT has IDT_SIZE entries, 256 in all. Every installed gate points into a stub in idts.S. The CPU pushes an error code for some exceptions only, so a stub that has none pushes a zero itself.

arch_init_idt_bsp() loads the table at INIT_EARLY. Every hart runs arch_init_idt_smp() at INIT_MIDDLE, and it loads the same table.

 device --> IOAPIC RTE or MSI message --> LAPIC --> IDT gate
        --> irq_stub --> amd64_irq_handler --> EOI
        --> irq_dispatch(number) --> irq_handler_t handler

The low vectors serve the CPU. Vectors 0x00 to 0x1F are the exceptions, and amd64_isr_handler() turns one into a panic or a signal. The gates of 0x02, 0x08 and 0x12 use an IST from IDT_IST_NMI, IDT_IST_DOUBLE_FAULT and IDT_IST_MACHINE_CHECK. A stack overflow still finds a stack there.

Vectors 0x20 to 0x2F hold the spurious stubs of the old PIC. The gates from 0x30 to 0xFF use an IRQ stub. Only 0x30 to 0xFE carry an IRQ number: ARCH_IRQ_BASE is 0x30, and ARCH_IRQ_MAX is 0xFE. The gate 0xFF is the LAPIC spurious vector, outside the number space.

amd64_irq_handler() sends the EOI before it dispatches. A handler therefore runs with the interrupt already acknowledged, and an asserted level-triggered input can raise again during it.

Handler numbers

irq_handler_add() gives a number that means the same on every hart. The tick and the TLB shootdown use it, because a hart sends an IPI to another hart at that number. irq_handler_add_hart() gives a number on one hart only, and interrupt_line_t uses it.

irq_table holds the shared entries, and hart_tables[] holds one table per hart. The first call that needs the table of a hart allocates it. A number is free only when irq_table has no handler for it and no hart uses it: is_free_everywhere().

Shared numbers come from the top, and per-hart numbers from the bottom. A higher vector has a higher priority in the LAPIC, so the tick and the IPIs sit above the devices.

irq_dispatch() reads the shared entry first, and the entry of its hart otherwise (entry_of()). It raises in_flight before it loads the handler, and the removal waits for that count to reach zero. A dispatch that finds no handler logs an unhandled IRQ.

Lines

The device framework calls interrupt_attach() for a GSI. A GSI becomes one interrupt_line_t: one hart, one IRQ number of that hart, and a list of interrupt_action_t. interrupt_controller_find() selects the controller whose gsi_base and gsi_count cover the GSI, and the attach fails with ENODEV without one.

Two drivers share a line only when both ask for INTERRUPT_SHARED and agree on trigger and polarity (may_join()). Any other case fails with EBUSY.

bind_line() starts with the boot hart and keeps it unless another online hart has fewer lines. If that hart cannot take the line, it tries every other hart. A hart that accepts the line adds one entry with irq_handler_add_hart(), and hart_lines[] holds the load of that hart.

program_line() writes irq_number + ARCH_IRQ_BASE into the controller or into the MSI message. A new line routes its GSI with the entry masked. add_action() unmasks it after the handler is in the list. The order keeps an interrupt from reaching a handler that is not there yet.

interrupt_detach() removes the action, and destroy_line() runs when the last one goes. The destroy masks the line, gives the number back and frees the memory.

The IOAPIC

arch_init_ioapic() reads the MADT and makes one interrupt_controller_t per IOAPIC entry. gsi_count comes from the version register: the maximum redirect index plus one. Every redirection entry starts masked.

ioapic_route() writes a whole RTE. It sets the vector, the destination LAPIC id, level from TRIGGER_LEVEL, active_low from ACTIVE_LOW, and masked. ioapic_mask() and ioapic_unmask() change one bit of the entry.

An ISA IRQ does not always reach the IOAPIC at the same GSI. interrupt_isa_route() maps it through the MADT interrupt source overrides, which record_override() records. Without an override the GSI is the IRQ itself, at TRIGGER_EDGE and ACTIVE_HIGH.

The IOAPIC controllers enter the device tree at INIT_LATE. A driver that uses their GSIs can then depend on their nodes.

The PIC

The kernel does not route an interrupt through the PIC. arch_init_pic_bsp() remaps the two chips to 0x20 to 0x2F, masks every input and sends end-of-interrupt commands to both. arch_init_pic_smp() installs amd64_spur_20 to amd64_spur_2F on those vectors. Their handler only logs, and it sends no EOI.

The local APIC

arch_init_lapic() reads MSR_IA32_APIC_BASE, and it panics when the global enable bit is clear. It then maps one page of registers with mmio_map(). It sets LAPIC_SVR_ENABLE and the spurious vector in LAPIC_REG_SVR.

lapic_write(LAPIC_REG_EOI, 0) acknowledges an interrupt. lapic_ipi() sends an IPI, and it disables interrupts while it writes LAPIC_REG_ICR_HI and LAPIC_REG_ICR_LO. The LAPIC timer puts irq + ARCH_IRQ_BASE in its LVT entry.

The spurious vector 0xFF is above ARCH_IRQ_MAX, so no IRQ number maps to it. amd64_irq_handler() returns before the EOI for it. A spurious interrupt is not in service, so an EOI would end another one.

Message-signalled interrupts

A message source needs no interrupt controller. interrupt_attach_message() allocates a line with message_ops and source, masks the source, composes the message and adds the action.

arch_msi_compose() builds the address 0xFEE00000 OR the LAPIC id shifted left by 12. The data byte is the vector. A PCI function writes those values through its MSI capability, in msi_write(). The write clears PCI_MSI_CONTROL_MME, so the function sends one message. It unmasks vector 0 when the capability supports per-vector masking. It also sets PCI_CMD_INT_DISABLE, so the INTx pin stays quiet.

pci_attach_irq() uses MSI when the index is 0 and pci_get_cap() finds PCI_CAP_MSI. With no such capability at index 0, the device framework falls back to the INTx pin of the bus. msi_mask() and msi_unmask() clear and set PCI_MSI_CONTROL_ENABLE.

Invariants and traps

• A number has one handler on a hart. A shared handler and a hart handler never take the same number, in either order.
• A per-hart number goes back with irq_handler_remove_hart(), which asserts that the entry exists. irq_handler_remove() owns the shared entries.
• irq_handler_remove() holds irq_table_lock while it waits for in_flight. A handler that calls irq_handler_add() can spin on that lock while a removal waits for it to return.
• irq_handler_add_hart() can allocate the table of the hart. Its caller must have interrupts enabled.
• All handlers run with interrupts disabled. A line handler runs on the hart of its line, and line->lock serializes the actions of one line.
• A line keeps a raw controller pointer. interrupt_controller_remove() asserts that no line uses the controller, so the caller detaches them first.
• A message line is not in line_head, so find_line() never returns it.

Limits

• There is no MSI-X. PCI_CAP_MSIX is defined, and nothing reads it. A function gets one MSI message at most.
• No trap gate is installed. idt_set_kernel_gate() takes the flag, and every caller passes false.
• The IOAPIC RTEs use the fixed delivery mode only. There is no NMI, SMI or ExtINT route, and no interrupt remapping.
• The PIC only reports spurious interrupts. Nothing routes an ISA IRQ through it, and its vectors never map to an IRQ number.
• A line cannot change its hart. There is no affinity request from userspace, and no way to move a line off a busy hart.
• The set of IRQ numbers is fixed by ARCH_IRQ_BASE and ARCH_IRQ_MAX. The tables do not grow, and a full table returns UINT_MAX.
• irq_handler_add_hart() needs memory for the table of the hart. A hart whose first line arrives under low memory loses that line with ENOMEM.

Source

Time

Vex keeps time on three independent scales. The clock source counts the time since boot. The wall clock adds an offset to that count. The cycle counter counts only the time of one hart, for CPU time accounting. Each scale has its own path, and its section shows it.

Clock sources

 counter --> clock source --> monotonic ns --> CLOCK_MONOTONIC

A clock source wraps a counter that never stops, such as the HPET or the ACPI power management timer. Its read op returns the raw value. The registration gives the frequency of the counter, and the kernel converts the ticks to nanoseconds with a fixed-point multiplier and shift. A source declares the bits of the counter that wrap, so a counter that is narrower than 64 bits keeps the time across its rollover. The tick also calls clock_source_update(), so a narrow counter that wraps between two reads still converts correctly.

Each source has a rating, and the highest rating is active. A source that arrives with a higher rating takes over at once. It starts from the time that the old source reached, so the clock never goes backwards. A source that goes away hands the time to the best source that is left. The last active source cannot be removed, because the kernel would have no time at all. The call fails with EBUSY.

The clock source lock is a spinlock with interrupts disabled, so a read is short. clock_source_peek_ns() tries the lock and reads the last value when another caller holds it, because a panic path must not wait. delay_nsec() and its two larger units spin on the source.

The amd64 sources are the HPET, at rating 200, and the ACPI power management timer, at rating 100. The TSC is not a clock source, as its rate can change.

Clock events

A clock event is a timer that raises an interrupt on request. Each hart has one active timer, the best of the events that serve it. An event with CLOCK_EVENT_PER_HART serves the hart that adds it, and every other event serves the boot hart, because device interrupts go there.

The caller asks for a delay from now, and the timer clamps it to the range of the device. With clock_event_oneshot() the interrupt comes once. With clock_event_periodic() it repeats until clock_event_stop(). A timer with only one of the two modes uses that mode for both requests.

A switch from one timer to another arms the new timer at its shortest delay when it serves this hart. When it serves another hart, the kernel sends that hart an IPI, and the handler arms the timer there. A removal that would leave a hart without a timer fails with EBUSY.

The amd64 timers are the LAPIC timer and the PIT. The LAPIC timer has rating 300 and serves one hart. The PIT has rating 100 and serves the boot hart.

The tick

 clock event --> tick --> scheduler, sleeps, itimers, CPU charge

There is no periodic tick. The scheduler arms a one-shot event for the timeslice of the running thread, and arms it again on every switch. That interrupt is the tick. It stops the timer and refreshes the clock source. It wakes the threads whose sleep expired, and runs the expired interval timers and the deferred events. It charges the CPU time of the thread and picks the next thread.

An interval timer of a process is a deadline on the clock source, with an optional interval. The armed timers sit in one list, sorted by deadline. The tick walks the list from the front. It sends the signal of each timer that expired, and moves an interval timer to the next point of its grid.

The CPU timers of a process count down in the tick instead. The tick compares the time that the hart charged to the thread, so such a timer fires at most one tick late.

The wall clock

 monotonic ns + wall clock offset --> CLOCK_REALTIME

The wall clock is the monotonic time plus an offset. The offset is a timespec_t under a seqlock, so a reader retries when a writer is in the middle of a change.

wallclock_set() computes a new offset, publishes it, and writes the RTC. A failure to write the RTC only logs a warning: the system clock has the new time all the same. The call needs CAP_SYS_TIME.

At boot the kernel takes the date from the Limine date request. The RTC lives in the device tree, which arrives later. When the first RTC comes into use, the kernel takes its time if no date is known, or compares it with the boot date. A difference of more than 2 seconds gets a warning. If the difference is close to a whole number of 15 minutes, the warning adds that the RTC may hold local time instead of UTC.

wallclock_wait_until() sleeps until a wall clock target. A wallclock_set() moves the target with the clock, so the wait ends on the new scale and not on the old one.

CPU time

 cycle counter --> local_clock_ns --> CPU time

local_clock_ns() reads the cycle counter of the hart when the counter has a constant rate, and the clock source otherwise. Its value is only compared with a value of the same hart. The scheduler uses it to separate user time from system time, and CLOCK_THREAD_CPUTIME_ID and CLOCK_PROCESS_CPUTIME_ID report the sum.

The amd64 probe takes the TSC frequency from CPUID, or from the hypervisor leaf. It marks the value as inexact, so the kernel also measures the frequency against the clock source. The measure is the median of five rounds of 20 ms, and it keeps the CPUID value when that value is not zero. A difference of more than 1% logs a warning. The cputime=clocksrc command line skips the TSC and leaves CPU time on the clock source.

Interfaces

The clock IDs of the system calls reduce to two clocks: realtime and monotonic. The raw and the coarse IDs read as their fine ID, because the kernel steps the clock and never slews it. The CPU time IDs read the usage counters instead. A nanosleep(2) with TIMER_ABSTIME on the realtime clock uses wallclock_wait_until(), and a sleep on the monotonic clock uses a deadline on the clock source.

Limits

• A global timer serves the boot hart alone. A broadcast to harts whose own timer stops in idle is not done yet.
• The RTC is read as UTC, and the kernel applies no zone.
• The wall clock cannot be set past the point where the offset and the uptime would overflow. The conversion of a timespec_t saturates instead.
• The cycle counter is the better CPU clock only on a CPU with a constant rate, and only after the calibration.
• The interval timers and the sleeps have the resolution of the tick, not of the clock source.

Source

• clocksrc.c — the registry, the conversion and the active source
• clockevt.c — the timers of each hart and the switch
• wallclock.c — the offset, the boot date and the RTC check
• rtc.c — the clocks that keep the time while the system is off
• cycles.c — the calibration of the cycle counter
• delay.c — the busy waits
• calendar.c — the proleptic Gregorian calendar
• hpet.c and acpi_pmt.c — the clock sources
• lapic_timer.c and pit.c — the clock events
• tsc.c — the rate and the frequency of the cycle counter
• cmos_rtc.c — the RTC driver
• sched.c — the one-shot tick
• itimer.c — the interval timers
• sys_time.c — the clock IDs and the calls

Firmware and ACPI

The firmware or the code knows which devices exist, where their registers are and which interrupt they raise. A driver reads that knowledge through fwnode_t, not from an ACPI namespace or from the command line.

A provider fills a firmware node. Vex has two providers: ACPI through uACPI, and fixed descriptions. The device tree consumes both in the same way.

The firmware node

fwnode_t holds an ops table and an opaque handle. The ops say what a consumer may ask. They cover presence, ids, bus address, CPU id, name, children, resources, INTx route, dependencies and eject.

The fwnode_t is a value with no lifetime of its own. A provider passes it to a callback on the stack. A consumer that keeps a node copies it, as the device tree does in device_add(). Identity is the pair of ops and handle, which fwnode_is_same() compares.

  ACPI tables / namespace        code, or fixed= on the command line
             |                                  |
          uACPI                          fwnode_fixed_t
             |                                  |
             +------------> fwnode_t <----------+
                               |
                    device tree and driver match

fwnode_root() returns the node that the devices of the system hang from. ACPI answers with its predefined System Bus node. Without that node the call returns -ENODEV, and the tree starts with an empty root.

ACPI through uACPI

contrib/uacpi holds an unmodified copy of uACPI. The kernel implements the uacpi_kernel_* API in two files. kernel/firmware/acpi/uacpi.c holds memory, time, semaphores, PCI config access, interrupt install and a work queue. kernel/arch/amd64/firmware/acpi/uacpi.c holds port I/O, the interrupt flag and the arch spinlock.

The RSDP comes from a Limine request and lands in rsdp_address. uACPI gets it from uacpi_kernel_get_rsdp(). init_acpi_tables() lends uACPI one page for early table access at the mmu stage. At the bus stage, init_acpi() loads and initializes the namespace. It sets the interrupt model through _PIC.

acpi_node_ops answers from the uACPI namespace:

• is_present accepts a node whose _STA reports present and enabled.
• matches reads _HID, then _CID. A Processor object matches the id ACPI0007, which older firmware such as QEMU still uses.
• get_cpu_id reads _MAT first. Without _MAT, it matches the processor id against a MADT entry.
• get_name writes acpi: and the four-character name segment, with the trailing underscores removed.
• for_each_resource translates _CRS into fwnode_resource_t entries. A memory, port or bus range carries its translation and flags.
• route_pci_interrupt reads _PRT. A route without a source uses its index as the GSI, level-triggered, active-low and shared.
• for_each_dependency resolves the name paths of _DEP.
• eject runs _EJ0. On success it reports _OST. A busy device gets OST_DEVICE_BUSY and no _EJ0.

The child walk visits Device and Processor objects only. It includes the children that the firmware says are absent. This is the for_each_child contract. fwnode_is_present() tells an absent child from a present one.

The kernel turns an ACPI interrupt into a device. uACPI asks for a GSI, and the kernel builds a fixed node named sci or gpe_gsi%u. Its id is ACPI_IRQ, and it carries one IRQ resource. The acpi_irq driver attaches to the node and calls device_request_irq(). The GSI then goes through the interrupt controller that owns it, like every other device.

ACPI 6.5, 5.2.9 defines the SCI as level-triggered, active-low and shared. A GPE block interrupt has the same shape.

_Lxx and _Exx send notifications. handle_notify() rescans the tree around the node, or ejects the node on request. It runs as uACPI work on a kernel thread, so it queues the tree work that device_worker runs. The work thread runs on the boot hart because some firmware SMI handlers assume it.

Fixed descriptions

fwnode_fixed_t holds a name, an id and a resource table. fwnode_init_fixed() installs fixed_node_ops. The node is always present. Its id matches exactly. It has no children, no dependency and no address. Eject does nothing.

The name becomes the path component fixed:<name>. The id keys DRIVER_MATCH_FIRMWARE(), as _HID does for an ACPI device.

A fixed description gives a node to hardware that code knows is there. The PIT adds one for its ports and its IRQ. An IDE channel builds one for its command and control ranges, its bus-master range and its IRQ. An ACPI interrupt node is a fixed description. Its fwnode_fixed_t is the first field of acpi_irq_trampoline_t.

A fixed= command line option puts a fixed description under an existing device. fixed=PNP0501,io:0x2e8+8,irq:3 adds the node under the root. A path before the id selects another parent, as in fixed=acpi:PCI0/PNP0501,....

parse_option() takes the text before the first comma. The part after the last slash is the id. The part before it is the parent path, and no slash means the root. The remaining fields are resources: io:<start>+<len>, mem:<start>+<len>, irq:<n>, gsi:<n> and dma:<n>.

An irq: is an ISA IRQ. It gets FWNODE_IRQ_ISA and defaults to edge-triggered and active-high. A gsi: has no ISA flag. A range sets its translation and flags to zero.

The kernel builds the list once, at INIT_FIRST of the bus stage. A node appears when device_sync_firmware_children() runs on its parent. A parent path that never matches produces one warning at INIT_LAST, not an error.

Invariants and traps

• A fwnode_t from a callback lives on the stack. Copy it if it must outlive the callback.
• The description behind handle must outlive every device that holds the node. fwnode_init_fixed() stores the pointer, not a copy.
• fwnode_is_same() compares ops and handle. Two nodes are the same device only when both match.
• A child walk includes absent nodes. A consumer that skips fwnode_is_present() sees hardware that is not there.
• A failed _STA read is not an error to the consumer. The node is simply absent.
• The kernel writes the fixed= list once and never changes it, so its walk takes no lock.
• A notify handler does not change the tree. It queues work for device_worker.
• An ACPI interrupt node is never removed. uACPI never tears down.

Limits

• There is no flattened device tree provider. Without a System Bus node, only fixed descriptions add devices.
• A fixed= id is at most 15 characters. A fixed option holds at most 8 resources.
• A fixed node has no bus address. A bus that places children by address cannot place it, so the node becomes unplaced.
• A _PRT link with no interrupt returns -ENXIO. The kernel does not pick one from _PRS or set it through _SRS.
• The kernel still reports an extended IRQ with a resource source as a system GSI. It does not route the IRQ to another interrupt controller.
• No op exposes _DSD or a power resource.
• uacpi_kernel_uninstall_interrupt_handler() returns UACPI_STATUS_UNIMPLEMENTED, because the kernel never tears uACPI down.

Source

IPC

Processes talk to each other through three mechanisms:

• a pipe or a FIFO, a byte stream with one read end and one write end.
• a futex, a wait on a 32-bit word that both sides map.
• a shared mapping, memory that several processes read and write.

There is no socket layer, no message queue and no semaphore.

A named shared memory object, as shm_open makes it, is not a kernel object either. The C library uses a file on a tmpfs that userspace mounted at a fixed path. The shared memory page gives the detail.

What they share

A blocked read or write, and a contended futex, sleep through the scheduler. The tick wakes a sleeper whose deadline passed, so a timeout lands on a tick and not earlier.

Pipes and shared mappings count their pages against the commit limit. A pipe page takes one page while the queue holds it. A shared file takes its whole size when the mapping appears. A futex takes none, as its waiter lives on the stack of its thread.

Only pipes and shared mappings carry an access check. A pipe holds the effective user and group of the process that made it. A shared file is made with the credentials of the kernel and reached only through a mapping that mmap already accepted. A futex trusts the mapping of the caller.

Pipes reuse the file path of the VFS, so read, write, poll and ioctl reach the same vnode ops as any other file. A futex and a shared mapping have their own system call paths.

Pages

• Pipes and FIFOs — the ring of pages, the open handshake and poll.
• Futexes — the private and the shared key, the waiter and the timeout.
• Shared memory — the unnamed file, the commit charge and the lifetime.

Pipes and FIFOs

A pipe is a byte queue with one read end and one write end. pipe(2) makes one that no name leads to. A FIFO is a vnode of a filesystem with the same queue behind it, and any process that opens the path joins the queue.

Both use pipe_t. The queue is a ring of 16 pages, and the pipe holds no page until the first byte arrives.

The queue

pipe_put() fills the last page and adds a page when that one is full. pipe_get() reads the first page and gives it back as soon as its last byte is read. An empty pipe therefore holds no page, and a reader that copies slowly does not pin the whole queue behind one page.

Each page takes one page from the commit limit when the pipe allocates it, and gives it back when the read drops it. If the charge fails, the write stops and returns the bytes that it wrote so far, or ENOMEM when there are none.

A write of up to PIPE_ATOMIC_SIZE (one page) goes in all or nothing. A larger write waits only for one byte of room, and it then writes as much as the queue takes. The system call cuts a large write into pieces of FILE_IO_CHUNK, so a piece never exceeds the atomic size.

Blocking and the ends

A reader waits on the readable event while the queue is empty and a writer still exists. It returns end of file when the last writer closed. A writer waits on writable while the queue has no room. It fails with EPIPE and sends SIGPIPE when the last reader closed.

The open and close counts of each side drive those events. The last close of a reader triggers writable and the last close of a writer triggers readable. O_NONBLOCK turns both waits into EAGAIN.

poll reports POLL_READABLE when a byte waits, POLLHUP when no writer is left, POLLERR when no reader is left, and POLL_WRITABLE only when a whole atomic write fits. FIONREAD returns the bytes in the queue. seek always fails with ESPIPE.

FIFOs

A FIFO node starts with no queue. The first open attaches a pipe_t to the node, and the last close detaches it and frees the data, as POSIX requires.

An open that waits for the other end uses the partner event and two counters of opens that ran so far. A reader that opens alone waits for a writer. A writer that opens alone waits for a reader, and with O_NONBLOCK it fails with ENXIO instead. A reader with O_NONBLOCK goes on at once. An open for both directions never waits.

The counter of opens, and not only the count of open files, is the reason that the wait ends. A partner that came and closed again still satisfies it. The check runs under the queue lock, so the open that ends the wait cannot pass between the check and the sleep.

The pipe filesystem

pipefs is an internal filesystem, in the sense of VFS: no kernel command line can mount it. Its root is a directory, and pipe(2) adds a FIFO vnode below it with a queue attached. Both ends of the pipe are ordinary file_t objects on that vnode, so the file code, the file descriptor table and poll need no pipe-specific path.

The queue carries the effective user and group of the process that created the pipe. A FIFO shows the owner of its node instead.

Why it is done this way

• Pages, not a ring buffer. An empty pipe costs nothing, and a slow reader returns each page as soon as it is done with it.
• One atomic size. A writer of a small message cannot be interleaved with another writer. A larger write is a stream by design.
• The same code for a pipe and a FIFO. Only the attach and the open handshake differ.
• The open counters. A wait for a partner must end even when that partner opened and closed before the waiter ran again.

Limits

• A pipe holds at most 16 pages, which is 64 KiB.
• There is no splice(2), no packet mode and no way to read one message at a time.
• A call can block on a full queue while another thread of its process closes the reader. The writer then wakes with EPIPE, as POSIX has it.

Source

• pipe.c — the queue, the events, the open handshake and pipefs
• pipe.h — pipe_create
• sys_file.c — pipe(2)
• poll.c — the poll and ppoll calls

Futexes

A futex is a wait on a 32-bit word that several threads or processes map. The kernel holds no state while nobody waits, so the fast path of a lock stays in user space. Only contention enters the kernel.

SYS_FUTEX_WAIT takes the address, the value that the caller expects, an optional relative timeout and the flags. SYS_FUTEX_WAKE takes the address, the number of waiters to wake and the flags. The only flag is FUTEX_SHARED.

The key

The kernel identifies a futex by a key of two numbers: a vmspace_t*, which is null for a shared futex, and an address.

• A private futex keys on the vmspace_t of the caller and the virtual address. Two threads of one process reach the same key through the same mapping, and another process never does.
• A shared futex keys on the physical address of the page. Two processes that map the same page reach the same key even when the page is at a different virtual address in each process.

The wait pins the page with vms_pin() and reads the word through the direct map. A private wait unpins the page before it sleeps. A shared wait keeps the pin until it is done, because the physical address is part of the key and the frame must not move.

The keys spread over 256 buckets, with the top 8 bits of a multiplication by the golden ratio as the index. Each bucket holds one lock and one list.

Wait

The wait runs these steps under the lock of the bucket:

1. It reads the word. A value other than the expected one fails with EAGAIN.
2. A deadline that already passed fails with ETIMEDOUT.
3. It puts a futex_waiter_t on the list. The waiter lives on the stack of its thread and is linked in arrival order.
4. It removes the thread from the scheduler, asks for a wake at the deadline, and yields.

The waker stores the new word before it calls the wake, and the wake takes the bucket lock. A store either happens before the read of step 1, or it happens after the waiter is linked, where the waker finds it.

On the way back the thread takes the bucket lock again. A waiter that is still on the list timed out or lost a wake race. It unlinks itself.

The call then reports these results, in this order. It reports 0 when the waker took the waiter, EINTR when work is pending, ETIMEDOUT when the deadline passed, and 0 for a spurious wake. The caller looks at the word again in every case.

Wake

The wake takes the bucket of the key and walks the list from the head. The waiters of one futex leave in the order that they arrived. It re-enqueues up to count threads whose key matches, and it returns the number. A shared wake pins the page first to learn the physical address, then unpins it.

Why it is done this way

• The waiter lives on the stack. A contended wait allocates nothing, and the bucket lock is the only thing that keeps the waiter valid.
• The word is checked once, under the lock. A store that happens before the check is seen by it. A store that happens after finds the waiter on the list.
• The shared key is physical. Two processes rarely map a shared page at the same virtual address.
• The timeout is a scheduler deadline. The tick already wakes threads whose deadline passed, so no separate timer queue exists.

Limits

• There is no priority inheritance, no FUTEX_ROBUST support and no owner-death handling.
• Only FUTEX_WAIT and FUTEX_WAKE exist. There is no requeue, no bitset wait and no FUTEX_WAITV.
• A large count wakes every waiter on the key. There is no separate broadcast flag.

Source

• futex.c — the buckets, the waiter and the two operations
• futex.h — the interface
• sys_futex.c — the two system calls
• sched.h — sched_wake_at() and sched_wake_cancel()

Shared memory

A shared anonymous mapping, MAP_SHARED | MAP_ANONYMOUS, is a mapping of a file that no name leads to. The kernel makes the file in an internal tmpfs, unlinks it at once, and maps it as a shared file. Both processes of a fork then map the same file and see the same pages.

POSIX shared memory is not a kernel object. Userspace mounts a tmpfs at a fixed path, such as /run/shmem, and shm_open creates a file there. The C library hardcodes that path. The mount needs CAP_MOUNT, so the init process or a service manager makes it. The kernel serves the file with the same tmpfs and mmap code as any other file.

The file

shmem_file_create() makes the file. It takes a name from a counter, creates a vnode in the internal tmpfs, and unlinks the name before it returns. Nothing else can reach the file, so the name only serves the moment of creation, and the number in it is never reused.

The call then sets the size of the file, and the tmpfs charges the whole size to the commit limit. A file of 4 MiB takes 1024 pages of 4 KiB at this point. The pages themselves arrive later, on the faults of the mapping. The tmpfs of this file sets no page limit of its own, so the commit limit is the whole bound.

The mapping

map_shared_anonymous() maps the file with backing.shared set. The mapping takes its own reference to the file, and the system call closes the file at once. The mapping is the only thing that keeps the file and its pages alive, and the last unmap takes the last reference and frees them.

The shared flag also changes how fork treats the mapping. A private anonymous mapping is copied on write, so the child starts with its own pages. A shared mapping of a file stays shared: both processes fault on the same vnode and get the same page.

MAP_NORESERVE has no effect here. The whole size is taken from the commit limit when the mapping appears, and the reserve of CAP_VM_NORESERVE changes nothing for this kind of mapping.

Why it is done this way

• A file, not a new object. The VFS already shares a file-backed region across fork, handles the faults and frees the pages on the last unmap. A second memory object with its own lifetime rules would repeat that work.
• The anonymous mapping has no name. It exists for a fork and nothing else. Named shared memory is a file on a mounted tmpfs. The path, the permissions and the removal rule belong to the filesystem, and not to a new kernel object.
• The size is charged at once. A shared mapping must not fail on a fault after another process already mapped it, so the whole range is reserved at mmap.
• The file uses the kernel credentials. It is made for the kernel and reached only through the mapping, so no path check applies to it.

Limits

• The kernel has no shm_open(3). A C library provides it on a tmpfs that userspace mounted, at a path that both agree on.
• A shared anonymous mapping has no name, so only the children of a fork reach it.
• There is no System V shared memory, no memfd_create(2) and no sealing.
• msync has nothing to flush for a tmpfs file.

Source

• shmem.c — the unnamed file and the tmpfs
• shmem.h — shmem_file_create
• sys_mman.c — the shared anonymous mapping
• vms.c — the reference that a region takes
• tmpfs.c — the charge of the pages

Security

Vex has no security module and no policy engine. A privileged decision reads the credentials of the calling thread and compares them with the object. The credentials say who the thread is, and which capabilities it holds. The kernel also contains a few cryptographic primitives for its own use.

Capabilities are one field of the credentials. Their bits and sets have their own page: Capabilities.

The credential object

credentials_t holds a reference count. It holds the real, effective and saved user and group ids, and four capability masks with a flag word. It also holds a sorted array of supplementary group ids. The array is part of the allocation, so the structure has a size that depends on the number of groups.

The object never changes after a process publishes it. A call that changes an id or a capability takes the credentials_lock of the process, copies the object, changes the copy, and swaps it in with process_set_cred(). The old object loses the reference that the process held, and it dies when its last reference goes. A small copy comes from the slab, and a copy with many groups from kmalloc.

kernel_credentials is a static object with every capability and no group. It never dies. The kernel uses it for its own file operations, and a kernel thread starts with it.

Which copy a thread uses

A thread caches a reference in thread->credentials. Another thread of the same process can replace the credentials between two system calls, so the kernel checks the cache at every system call entry. catch_up_cred() compares the cached object with process->credentials, takes the new one when they differ, and drops the old reference.

process_get_cred() returns a new reference. A caller that keeps the pointer across a call that can block holds that reference, so a concurrent change cannot free the object under it.

A fork gives the child a reference to the credentials of the parent. An exec builds a copy, applies the setuid and setgid bits and the file capabilities, and swaps it in.

Ids

Each of the user and group ids has three values: real, effective and saved. A process may set one of them to its current value or to one of the other two. CAP_SETUID or CAP_SETGID removes that limit. The saved id keeps a program able to return to the id that started it.

A change of a user id also moves the capability sets. The rules are in Capabilities.

The supplementary groups are sorted in ascending order, and cred_in_group() finds one with a binary search. CONFIG_NGROUPS_MAX sets the limit, and setgroups(2) needs CAP_SETGID.

Access checks

vnode_access() makes the decision for a file:

1. CAP_DAC_OVERRIDE grants the request. An execute request still fails when the file has no execute bit for any user and is not a directory.
2. The owner bits apply when the effective user id is the owner.
3. The group bits apply when the effective group id or a supplementary group matches.
4. The other bits apply in every other case.

The path walk and the file operations use the effective ids. access(2) is the exception: it checks the real ids, unless AT_EACCESS is set. cred_copy_real() makes that copy. It also makes the effective set equal to the permitted set when the real user id is 0, and empty otherwise.

chmod, chown and the timestamp calls compare the effective user id with the owner, and a capability lifts each comparison. The bits table of Capabilities names the capability for each operation.

Program start

exec copies the credentials. It applies the setuid bit to the effective user id. It applies the setgid bit to the effective group id when the group execute bit is set. The saved ids follow the effective ids. cred_exec_caps() then works out the capability sets. The kernel reports AT_SECURE to the new program when an id differs from the real id. It also reports it when the real id is not 0 and the permitted set has a bit that is not ambient.

Cryptography

There is no general cryptographic interface. Three primitives exist, and each one serves one subsystem:

• BLAKE2s hashes the entropy pool and mixes a seed into the key.
• ChaCha20 generates the random bytes from that key. Both primitives live in Random numbers.
• CRC32 is a checksum, not a security primitive. The GPT parser checks the header and the entry array with it, and the device-name code hashes a prefix with it.

The CRC32 code builds a table for a polynomial and an initial value, so a second user can pick its own.

Traps

• The cached credentials of a thread can be one change behind. Only the system call entry brings them up to date.
• A credentials_t* that crosses a blocking call needs its own reference.
• cred_capable() reads the effective set only.
• Never copy credentials_t with sizeof(credentials_t). The group array is outside it. Use cred_copy().
• A kernel thread has no process. A system call from one returns ENOSYS.

Source

• cred.h — the object and its interface
• cred.c — the copy, the reference count, the id rules and the exec transition
• sys_cred.c — the id system calls
• syscall.c — the refresh of the cached credentials
• process.c — the swap of the published object
• vnode.c — the access check
• sys_path.c — access(2) and the real ids
• blake2s.c, chacha20.c and crc32.c — the primitives

Random numbers

Vex supplies random bytes to getrandom(2), /dev/random and /dev/urandom. One generator serves all three. The design has three layers: sources, a pool and a generator.

The three layers

 sources         pool                output
+------------+   +------------+      +------------+
| rdseed     |   | BLAKE2s    | seed | ChaCha20   |
| rdrand     |-->| hash state |----->| fast key   |--> getrandom(2)
| jitter     |   | + credit   |      | erasure    |--> /dev/random
| limine     |   +------------+      +------------+--> /dev/urandom
| irq events |
+------------+

The sources collect noise. The pool mixes the samples and counts the entropy that the kernel trusts. The generator turns the pool into output.

Sources

A source declares itself with define_random_source_polled or define_random_source_event. The declaration lands in the .random_sources linker section. The kernel walks that section at boot.

A polled source has a probe function and a poll function. The probe tells whether the hardware exists. The poll fills a buffer of at most 64 bytes. A short poll earns a proportional share of the credit.

An event source has no poll function. Its code pushes an event into a buffer for the current hart. The IRQ source mixes the interrupt number into that buffer with a timestamp.

The trusted flag controls only the credit. Every sample enters the pool. An untrusted source can add bytes to the pool. It cannot make the generator ready.

The random.trust_<name> kernel option changes the default. The value 0 removes the credit. Any other value grants it.

The kernel polls a polled source at most once in 100 ms. A caller can poll the sources before it reads bytes. A worker thread also polls them when the pool needs noise. random_source_poll_all() takes a trylock, so one poller runs at a time.

The kernel stops asking a source that returns -ENODEV. It also stops after five failures in a row.

Why the trust differs

rdseed is the architectural entropy instruction. The kernel counts its output as entropy.

rdrand returns the output of a random generator in the CPU. The kernel mixes the bytes and counts no entropy. A compromised CPU must not seed the kernel alone.

The kernel trusts limine as a whole. Limine collects entropy from RDSEED, RDRAND and the UEFI random generator. It falls back to the PCG32 generator. The reply does not say which source made a value. The kernel cannot separate the sources. It trusts the bootloader, unless the command line changes the trust.

jitter measures time deltas around a small workload. The timing of a virtual machine can be regular. The source claims one bit for eight measurements. A poll with more than 32 repeated deltas returns -EAGAIN.

irq events are weak because software can observe interrupt timing. One event earns 1/64 of a bit. The stream is continuous, so the events still contribute.

Credit accounting

The pool counts trusted bits in credit_bits. The count stops at 256 bits. The generator needs 256 bits to take its first seed. A reseed sets the count back to 0.

This count is a policy, not a measurement. The kernel cannot test a sample. The estimate comes from the author of the source. The trust flag says whether the kernel accepts the estimate.

Event credit accumulates in fractions of a bit. The worker keeps the remainder for the next drain.

The pool and reseeds

The pool is a BLAKE2s-256 hash state, not a byte buffer. random_add() feeds the sample into the state. It also adds the credit.

A reseed does four steps:

1. It finishes a copy of the pool. The result is a 32-byte seed.
2. It starts the pool again and feeds the seed back into it. The next seed depends on this one.
3. It mixes the seed into the key with a keyed BLAKE2s. The old key is an input, so a weak seed cannot reduce the strength of the key.
4. It sets the credit to 0. On the first reseed it also triggers the ready event.

Two conditions start a reseed. The credit must be at least 256 bits, and 100 ms must have passed since the last reseed. The first reseed ignores the interval.

The code checks the conditions in two places. random_add() checks them while the generator has no seed. The output path checks them for each 256-byte chunk. There is no periodic reseed timer.

Between reseeds, the generator produces bytes from its key.

Output bytes

fill() produces output in 256-byte chunks. For each chunk it calls generate():

1. It starts ChaCha20 with the current key, a zero nonce and counter 0.
2. It XORs the keystream into the output buffer.
3. It takes the next 64-byte block as the new key.
4. It zeroes the block and the stream state.

Each chunk uses a fresh key, so the nonce stays zero. The erasure means a later compromise of the key does not reveal earlier output.

Before the first seed, generate_unseeded() derives a temporary key from the pool. It feeds that key back into the pool, so the next call differs. The bytes do not repeat, but an attacker can guess them. GRND_INSECURE uses this path.

Waiting for the first seed

random_wait_ready() polls the sources and checks the ready flag. A blocking caller waits on the ready event with a 100 ms timeout. The timeout matters because no other thread polls the sources while the caller sleeps. The caller wakes, polls again and repeats.

getrandom(2) has two flags:

• GRND_NONBLOCK fails with EAGAIN when the generator has no seed.
• GRND_INSECURE skips the wait and accepts weak bytes.

Without GRND_INSECURE, the call waits for the first seed. Then it copies the bytes out in 256-byte chunks. A pending signal or stop ends a long call early. The call returns the bytes that it produced.

/dev/random and /dev/urandom use the same generator and the same rules. Both wait for the first seed. O_NONBLOCK turns that wait into EAGAIN. A write to either device stirs the pool and earns no credit. poll() reports readable only after the first seed.

Boot sequence

The IRQ hook drops events until the worker publishes its buffers. Event noise therefore starts after the services stage.

Why it is done this way

• The pool is a hash, not a buffer. The sources produce different sizes and different claims. A hash accepts any size and keeps no copy of the samples.
• The key chains. The new key depends on the old key and the new seed. A weak reseed cannot lower the entropy that the key already has.
• The key changes for each chunk. This gives forward secrecy. It also holds the pool lock for less time.
• The credit is explicit. An untrusted source cannot seed the kernel alone. The rule is visible in the code and in the command line.
• Both devices are the same. This follows the FreeBSD model. Vex does not copy the Linux behavior where /dev/random blocks after the first seed.
• The reseed is lazy. A timer would add a thread and a wakeup for no gain. The output path already knows when it needs a new key.

Limits

• The kernel cannot prove an entropy claim. A trusted source that lies can seed the generator with weak data.
• Limine can use the PCG32 fallback. The kernel cannot detect this case.
• The jitter source measures timing. Timing is regular on some virtual machines.
• The tests check basic properties: length, distinct calls, bit balance and error paths.
• The secure random_bytes() has no caller in the tree. The syscall and the devices wait for the seed, then they use the insecure path.

Source

• random.c — pool, reseed, output and wait
• random_source.c — polling, event buffers and the worker
• random_source.h — the source structure and the registration macros
• random_dev.c — /dev/random and /dev/urandom
• sys_random.c — getrandom(2)
• limine.c — the bootloader entropy source
• jitter.c — the timing source
• rdseed.c and rdrand.c — the CPU instructions
• irq.c — the interrupt source
• test.random.c — the tests

Drivers

TODO: write this page.

Covers: how a driver is written and which drivers Vex has.

Storage

TODO: write this page.

Covers: AHCI, PATA and the helpers they share.

AHCI

TODO: write this page.

Covers: port bring-up, the command list, PRDT and completion.

PATA

TODO: write this page.

Covers: PIO and DMA transfers on the legacy ATA interface.

Display

TODO: write this page.

Covers: framebuffers, the Bochs VBE adapter and fbcons.

Limine framebuffer

TODO: write this page.

Covers: the framebuffer that Limine hands over.

Bochs VBE

TODO: write this page.

Covers: the QEMU std-vga display adapter.

Framebuffer console

TODO: write this page.

Covers: fonts, glyph drawing and the console backend.

Input

TODO: write this page.

Covers: input drivers.

PS/2 keyboard

TODO: write this page.

Covers: the i8042 controller and scan code translation.

Serial

TODO: write this page.

Covers: UART drivers and the serial interface.

UART 16550

TODO: write this page.

Covers: the core port, PCI discovery and firmware discovery.

Filesystems

TODO: write this page.

Covers: the backends behind the VFS.

ext2

TODO: write this page.

Covers: the ext2 layout and what the driver supports.

FAT

TODO: write this page.

Covers: FAT12, FAT16, FAT32, long names and the FAT tests.

echfs

TODO: write this page.

Covers: the echfs layout and the driver.

devfs

devfs is the filesystem of device nodes. It has one directory, its root, and one node for each block or char interface that the kernel publishes. A node appears when the interface appears, and it goes when the interface goes.

Discovery

devfs does not search for hardware. It subscribes to the two event buses of the device model, one for block interfaces and one for char interfaces. Each subscription replays every interface that already exists. A devfs that is mounted after the disks are up therefore shows them at once.

A block node appears on BLOCK_EVENT_MEDIA_CONNECTED or BLOCK_EVENT_PARTITION_ADDED, and it goes on BLOCK_EVENT_MEDIA_DISCONNECTED or BLOCK_EVENT_PARTITION_REMOVED. An interface with BLOCK_FLAG_HIDDEN gets no node. A char node appears on CHAR_EVENT_INTERFACE_ADDED and goes on CHAR_EVENT_INTERFACE_REMOVED. CHAR_EVENT_MEMORY_CHANGED revokes the mappings of the node and keeps it.

The name of the node is the name of the interface, in the form that Device names describes, such as ada0n1p1, fbd0 or serial1. The kernel services that show their own state, such as /dev/kplog and /dev/hwtree, register a char interface, so devfs makes their nodes like any other.

Attach

A mount allocates the state of the filesystem, which is one lock, one list of nodes and one count, and makes the root directory. The root has mode 0555, and the mount reads neither a block volume nor an option string.

The mount then subscribes to the two buses. When a subscription fails, the mount removes what it made so far and fails. An unmount unsubscribes, removes every node from the cache of vnodes, and drops the reference of each node and of the root.

The kernel does not mount devfs. An init process mounts it on /dev, and the test image mounts it there before it runs the first test.

Data path

A lookup walks the list of nodes and compares the names. The inode number of a node is its vnode pointer, so it is unique while the node lives and costs no allocation. An iteration gives the dots first, then the nodes in the order of the list. The list is unsorted, and each insert puts the new node at the head.

A char node keeps a reference to its interface. Every operation of the vnode forwards to the char interface. Open and close make the per-file context. read, write, seek, ioctl, poll and mmap call the matching op. stat reports S_IFCHR with mode 0660 and the rdev of the interface.

A block node keeps the interface in vnode->volume and gives the device as a file of bytes. A read or a write maps the byte offset to a sector and a byte inside it. A run that starts on a sector and covers whole sectors goes to block_read() or block_write() in one call. A partial first or last sector goes through one bounce buffer of the node, which a mutex protects. A write reaches the device at once, with no page cache to hold it. stat reports the size as the sector count times the sector size.

A removal takes the node out of the list and out of the cache, and it drops the reference of the filesystem. An open file or a mapping still holds a reference, so the vnode and its context live until the last one goes.

Why it is done this way

• The bus replays. The mount does not need a second path to find the devices that already exist. A device that arrives later uses the same handler as one that was there first.
• The interface owns the work. devfs forwards every operation, so a driver has one implementation, in the char or block interface, and not a second one in the filesystem.
• The vnode pointer is the inode number. A devfs node has no number of its own to allocate or to free.
• A separate handler per interface kind. The two paths share the list and the cache, and nothing else, so a char device does not carry block fields.

Limits

• devfs has one directory. There is no /dev/disk/by-id, no per-bus directory and no symbolic link.
• A lookup and an iteration walk the list. The position of an iteration is an index in that list. A node that is added or removed between two getdents calls can then move what the reader sees next.
• The permissions are fixed: 0555 for the root, 0660 for a char or block node. There is no request that changes them, and no create or mknod op, so userspace cannot add a node.
• A block node offers read, write and stat. It has no ioctl, no poll, no mmap and no seek.
• A name is unique only because the interfaces keep their names unique. A second insert with the same name adds a second node, and a lookup finds the newest one.

Source

• devfs.c — the mount, the list and the insert
• devfs_dir.c — the root directory
• devfs_char.c — the char nodes and the event handler
• devfs_block.c — the block nodes and the bounce buffer
• devfs_internal.h — the node and the state

tmpfs

tmpfs is the in-memory filesystem. It has no volume and no copy on a disk: the pages of a file are the only copy. Userspace mounts it for a directory that must not survive a reboot, and the kernel makes instances of it that no path leads to.

Discovery

A filesystem has no discovery step. init_tmpfs adds the tmpfs driver to the registry of the VFS at the vfs stage, and a mount finds it by that name. The driver is not marked internal, so userspace can mount it.

vfs_create() makes an instance with no device and no mount point, and nothing can unmount it. Shared memory uses one such instance for the file behind a shared anonymous mapping.

Attach

The mount takes no block volume, and a mount that names one fails with EINVAL. The options come from the mount parameters:

The root directory defaults to mode 01777 and to the owner and group 0. Any process may create a file in it, and only the owner may remove one. Mounted with no option, the filesystem has no limit of its own and the commit limit is the only bound.

A mount holds one mutex, one list of inodes, the two limits and two counters.

Data path

Every node has a vnode and a tmpfs_inode_t. The inode holds the permission bits, the owner, the link count and three timestamps. It also holds the size, the target of a symbolic link and the entries of a directory. The type lives in the vnode, and the inode number comes from a counter of the mount.

The data pages come from the file cache with fcache_set_memory(). That mode makes the pages of the vnode the only copy. They are never dirty, and the cache needs no bmap and no volume. A read of a hole gives zeroes and takes no page, and reclaim never takes a page. Nothing writes the pages back, because there is nowhere to write them.

A write holds the mutex of the mount. When it extends the file, it first charges the pages of the new size to the limit of the mount and to the commit limit. If the charge fails, the write fails whole. A short write then shrinks the file back to the bytes that it kept. truncate and fallocate use the same resize, and a shorter file gives its pages back.

A page fault runs fcache_fault(), which puts the page of the file into the page map of the process. The pages were paid for when the size grew, so a fault does not charge them again.

A directory is a list of entries, in the order that they were created. Each entry carries a sequence number that grows and never repeats, and getdents reports that number as the position. A reader that removes an entry in the middle does not move the position of the entries after it. A lookup walks the list and compares the names.

A symbolic link keeps its target in the inode. A target of at most SLAB_MAX_SIZE bytes sits in a slab object, and a longer one takes a page. A FIFO, a character device and a block device have an inode and no data.

An entry holds one reference to its vnode for as long as the name exists. An unlink drops the name and the reference, and it removes the node from the cache of the vnode when the link count reaches 0. The last reference, which an open file or a mapping can still hold, frees the pages, the target and the inode.

Why it is done this way

• The pages are the only copy. A tmpfs has no disk to read from and no writeback to schedule. The memory mode of the file cache removes the bmap, the dirty list and the volume that other filesystems need.
• The whole size is charged. A hole costs a page in the commit limit, because the file can be written there at any time. This keeps a write from failing after it has already copied part of the data.
• One mutex for the mount. The filesystem is small and its operations are short. A lock per inode would add nothing but state.
• Sequence numbers in the directories. POSIX lets another thread remove an entry between two getdents calls, and the position of the reader must still name the next entry.
• No discovery. A tmpfs instance exists only because somebody mounted it, or because the kernel created one.

Limits

• Every operation takes the one mutex, so two writes to different files also wait for each other.
• A directory lookup walks a list. A directory with many entries is slow.
• There are no extended attributes and no per-user quota. The size and nodes options are the whole limit.
• A page is never reclaimed or moved out. The file holds it until a truncate or an unlink.
• A sparse file still counts its holes in the commit limit.
• Nothing survives a reboot.

Source

• tmpfs.c — the mount, the options and the limits
• tmpfs_vnode.c — the vnode operations
• tmpfs_internal.h — the mount and the inode
• fcache.h — the memory mode of the file cache
• vnode.h — the operations that the vnode offers

Buses

TODO: write this page.

Covers: bus ops and the buses that Vex enumerates.

PCI

TODO: write this page.

Covers: configuration space, BARs, MSI and the PCI bus.

ISA

TODO: write this page.

Covers: the ISA bus and fixed resources.

IDE

TODO: write this page.

Covers: the legacy IDE controller and its two channels.

Syscalls

This page lists every system call: its number, the arguments that the call reads, and the kernel function that runs it. The mechanism is in System calls.

The numbers come from kernel/include/usr/vex/syscall.h. Each subsystem owns a block of 32 numbers that starts at a multiple of 0x20. The table gives the calls of each block in number order and leaves out the numbers that no call uses. A call with such a number fails with ENOSYS. A number in the header without a registered handler fails with ENOSYS too.

Conventions

• The arguments are in the order of the registers, one for each register. A call reads at most six.
• user_addr_t is a pointer into the address space of the caller. The handler copies through it. It is never a kernel pointer.
• A descriptor is an int. When the _fd macro registered the handler, the handler gets the resolved file instead, and the table shows the descriptor that the caller passes.
• A call with a dirfd also takes the path as a user pointer. The kernel copies the path before it uses it.
• The return value is an intptr_t. A negative value is an errno number that is negated, and every other value is a result.
• The link on a name goes to the handler.

Processes and scheduling

Threads

Signals

Credentials

Memory

Files

Paths

Extended attributes and mounts

System

ABI

The ABI is the set of headers that a program outside the kernel compiles against. They live in kernel/include/usr/vex/ and a program includes them as <vex/...>. They fix the numbers of the system calls, the errors, the ioctls and the layout of every structure that a call passes.

Where it lives

The headers under kernel/include/usr/ are the whole userspace ABI. The architecture adds its own, such as arch/amd64/include/usr/arch/limits.h, and <vex/types.h> includes the one of the target. The test image compiles against both directories, and a C library takes the same two.

A header here compiles as ANSI C89 or ISO C90. It uses /* */ comments, no nullptr, no bool, no static_assert, no restrict, no inline and no designated initializers, and it declares every variable at the start of its block. A C library can therefore read the headers with an old compiler.

The guard comes from the path: usr/vex/errno.h becomes USR_VEX_ERRNO_H, and the #endif repeats the name. The name never starts with _.

Only usr/vex/types.h uses <stdint.h>, and only when the compiler is C23 or C++. In C89 the header picks its types from the widths in <limits.h>.

Names

Every name in the ABI starts with __k_. That prefix keeps the POSIX name free for the C library:

Most names reach the C library this way. A few constants, such as the RLIMIT_* numbers, the library writes as the same literal. It also adds a few flags of its own, such as the O_* bits that the kernel ignores.

The system call numbers are the exception: there is no public SYS_* name. The C library in the bootstrap tree, mlibc, includes <vex/syscall.h> inside its own system call layer and passes __k_SYS_* to the kernel. A program calls read, and not a number.

The kernel does not include the ABI headers directly. A header under kernel/include/vex/ includes the one under usr/, defines the plain names for kernel code, and gives each structure its _t typedef.

Types

usr/vex/types.h defines every integer the ABI uses:

A structure in the ABI uses these types for every field, and never int, long or a plain pointer where an integer holds an address. The layout then does not depend on the widths that the compiler gives to its plain types.

A field with the address of user memory is a __k_uintptr_t or a pointer. A field with a size in memory is a __k_size_t. A structure keeps the order that its header shows, and its fields are naturally aligned.

struct __k_stat is the largest common example. It holds the device, the inode, the mode and the link count. It also holds the owner and group, the file size, three __k_timespec values and the block counts. Its mode constants are the ext2 ones, __k_S_IFREG and the rest, so a filesystem passes the value through without a translation.

struct __k_dirent is the record of getdents: inode, the position of the next record, the length of this record, the type and the name. The record ends after the name, padded to 8 bytes, and d_reclen is the step to the next one.

Errors

A system call returns the negated error number in its result register. The C library turns that into -1 and stores the positive number in errno. The numbers are Vex numbers and not the Linux ones. A library defines each kernel error from the header, and not from a number that it chose. It may add numbers above them for errors that the kernel never returns. Errors holds the whole list.

ioctls

An ioctl request is one 32-bit number with a direction, the size of its argument, a group and a command. ioctls gives the layout and the groups. Each group page lists the requests of its device class:

• Serial port covers the 'S' group, the line settings and the binding to a consumer.
• Terminal covers the 'T' group and the line discipline.
• Framebuffer covers the 'F' group.
• Device feeds covers the 'L' and 'H' groups and the record format that /dev/kplog and /dev/hwtree use.

The headers

The values of a header that an outside standard fixes, such as the S_IF* bits of stat.h and the RLIMIT_* numbers of resource.h, keep the values of that standard. A value that Vex invents starts at a free bit or a free number and never moves.

Changing the ABI

There is no version field in these headers. A program that a compiler built against an old copy of them keeps calling with the old numbers. A value that a program can see must not change. A new option gets a new bit, a new error gets the next number, and a new structure is a new name. A change to a field of an existing structure changes the ABI, and the ioctl request of the call carries its size.

Source

• types.h — the integer types of the ABI
• stat.h — struct __k_stat and the mode bits
• dirent.h — struct __k_dirent
• syscall.h — the system call numbers

Errors

An error is a positive number in usr/vex/errno.h. A system call returns its negative in the result register, and the C library turns that into -1 with the number in errno.

The numbers are Vex numbers. They are not the Linux numbers. A program that compares an error against a literal from Linux is wrong on Vex. A C library defines each POSIX name from the __k_ name in this header. It may add numbers of its own above the kernel ones for errors that the kernel never returns. The bootstrap C library, mlibc, does so from 2001.

ISO C takes the range 101 to 103. POSIX takes 201 and up. The kernel also has -ERESTART (4095), which never reaches a program: the return path of a system call turns it into a restart or into -EINTR. The C library has its own ERESTART (2032) in the range that the kernel never returns, so the two do not clash. The mechanism is in System calls.

The string of an error comes from strerror_r() in kernel/libk/string.c. It reads the absolute value of its argument, so a caller may pass the positive number or the negated one from a system call. A number that it does not know gives unknown errnum (N), and 0 gives no error.

The values

A new error takes the next free number above the current ones. A number that a program can see must not change.

Source

• errno.h — the numbers
• vex/errno.h — the plain names for kernel code
• string.c — strerror_r and the string of each error

ioctls

An ioctl request is one 32-bit number. It carries the direction of the data, the size of the argument, the class of the device and the command:

 31    30 29            16 15       8 7        0
+--------+----------------+----------+----------+
| dir    | size (14 bit)  | group    | command  |
+--------+----------------+----------+----------+

The head of usr/vex/ioctl.h fixes that layout with __k_IOCTL_SET_DIR, __k_IOCTL_SET_SIZE, __k_IOCTL_SET_GROUP and __k_IOCTL_SET_CMD. The helpers __k_IOCTL_VOID, __k_IOCTL_READ, __k_IOCTL_WRITE and __k_IOCTL_RDWR build a request from these parts, and each takes sizeof() of the structure that it passes.

Direction and size