DOOM in de kernel, of fibers in eBPF

BPF heeft een minuscule stack, vijf argumentregisters en een beperkte aanroepdiepte (call depth). Recursie is verboden. Een lus moet eindig zijn, niet alleen omdat de programmeur dat zegt, maar op een manier die de verifier kan bewijzen. Je kunt niet simpelweg een pointer in het geheugen opslaan, deze later laden en derefereren: de kernel moet onthouden waar deze vandaan komt en welk adresbereik hij mag aanspreken.

En toch accepteert een ongewijzigde Linux-kernel mijn BPF-object, controleert deze met de standaard verifier en voert hem uit via de standaard JIT-compiler. De initialisatie van DOOM, de gamelogica en het renderen worden allemaal in de kernel uitgevoerd. Eén game-tick, inclusief het volledige frame, wordt voltooid in een enkele BPF-aanroep. De userspace levert de WAD en de toetsenbordinvoer aan, en krijgt een pointer terug naar de voltooide framebuffer.

Context over eBPF

eBPF stelt gebruikersprogramma's in staat om binnen de Linux-kernel te draaien zonder dat daar een kernelmodule voor nodig is. Een programma wordt gecompileerd naar bytecode voor een kleine registermachine, geladen met de bpf(2) systeemoproep en gekoppeld aan een hook — bijvoorbeeld een binnenkomend pakket of een system-call tracepoint. De JIT-compiler van de kernel compileert de bytecode naar machinecode, die wordt uitgevoerd telkens wanneer de hook afgaat.

Maar voordat het programma kan draaien, moet de verifier het accepteren. Hier komen de bovengenoemde beperkingen vandaan: code waarvan de verifier niet kan bewijzen dat deze veilig is, wordt afgewezen. Deze controle, eerder dan de bytecode zelf, is wat DOOM binnen eBPF onmogelijk doet lijken.

BPF Capsule

Het project heet BPF Capsule. Het is een compiler en runtime voor grote C-programma's binnen standaard BPF, zonder kernel-patches en zonder een aparte virtuele machine in de userspace. Het oudste ondersteunde target-profiel is Linux 5.15. Een profiel bepaalt welke kernel-mogelijkheden de compiler mag gebruiken. De programma's zijn geladen en uitgevoerd op zowel x86-64 als arm64.

Natuurlijk heeft niemand games in de kernel nodig. Maar complexe applicatielogica is daar wel nuttig: bijvoorbeeld het parsen van pakketten of het bijhouden van statistieken daarover. Wanneer een dergelijk programma niet binnen de beperkingen van eBPF past, moet het handmatig worden vereenvoudigd en herschreven totdat de verifier tevreden is. Capsule verkent een ander pad: het neemt C, C++ of no_std Rust-code en transformeert dit naar een vorm die standaard Linux accepteert.

DOOM is hier niet de hoofdapplicatie, maar een stresstest voor deze aanpak. Lua, QuickJS, SQLite, zlib, wasm3, llama2.c, no_std Rust en CPython 3.14 draaien vandaag de dag op hetzelfde schema, waarbij Lua en Python live pakketten rechtstreeks vanuit XDP inspecteren. Dit artikel volgt de route van een handmatig getrimde poort via een trage interpreter naar regio's en fibers, en meet de kosten hiervan tijdens runtime.

Je kunt het met één commando proberen op elke ondersteunde kernel (vereist Nix en een WAD-bestand):

sudo nix run github:ayles/bpf-capsule#doom -- /path/to/doom1.wad tty

De truc zit in de vorm van het programma dat aan de verifier wordt gepresenteerd. Eerst kreeg ik DOOM gecompileerd naar BPF zodat het kon draaien zonder verifier. Daarna verwijderde ik alles wat de kernel niet leuk vond, loog ik over pointers en dwong ik lussen in één speciale vorm. Toen dat niet meer schaalde, schreef ik een virtuele machine binnen eBPF. De huidige machine met regio's, fibers en een software-stack is daaruit voortgekomen.

Waarom dit onmogelijk zou moeten zijn

Op papier is eBPF een kleine registerarchitectuur met een LLVM-backend. Het klinkt simpel: schrijf C, voer clang -target bpf uit en je hebt een object dat de kernel kan laden.

In de praktijk betekent "schrijf C" dat je tegelijkertijd in twee heel verschillende talen schrijft. LLVM begrijpt de ene; de Linux-verifier begrijpt de andere.

Voordat de verifier een programma laadt, voert hij het symbolisch uit. Voor elk register houdt hij niet alleen een waarde of bereik bij, maar ook een betekenis: een gewoon getal (SCALARVALUE), een pointer naar de stack, pakketdata, een map-waarde of een bpfarena. De verifier verkent vertakkingen, voegt staten samen en bewijst twee dingen: elke geheugentoegang is toegestaan en elk uitvoeringspad termineert uiteindelijk.

Dit creëert beperkingen die een gewoon programma nauwelijks merkt:

• r1 tot en met r5 zijn de enige argumentregisters in de klassieke ABI;
• de aanroepgraaf (call graph) moet acyclisch zijn en de aanroepdiepte is beperkt;
• er zijn slechts 512 bytes stack beschikbaar langs een aanroepketen;
• één geladen programma mag niet meer dan 256 BPF-functies bevatten;
• na het verwerken van ongeveer een miljoen instructies geeft de verifier het op.

Die laatste limiet is geen limiet voor de uitvoeringstijd. Zelfs een korte lus kan het budget uitputten als de analyzer deze met voldoende verschillende staten opnieuw moet bezoeken. Een eindige lus is op zichzelf legaal; het probleem begint wanneer de kernel de grens niet kan bewijzen of te veel mogelijkheden moet opsommen.

Geheugen is nog interessanter. Voor de CPU is een pointer uiteindelijk gewoon een getal. Voor de verifier is het een getal met een biografie. Hij weet bijvoorbeeld dat r10 - 8 wijst naar een geldig BPF-stackslot. Sla die pointer op als gewone 64 bits in een map en laad hem later terug, dan krijgt de CPU hetzelfde adres, maar de verifier ziet een getal zonder het recht om gedereferencieerd te worden.

Normale C-programma's plaatsen constant pointers in structuren, geven die structuren door aan verschillende functies en laden de pointers veel later. Op een gegeven moment in dat proces verliest de verifier het bewijs.

Een recent LLVM-voorbeeld

Een geldige bounds check in C schrijven is niet genoeg: de kernel ziet de code na optimalisatie. Hier is een fragment van BPF-code voor pakketverwerking:

size_t at = offset + index;
asm volatile("" : "+r"(at));
at &= PACKET_CAPACITY - 1;
if (data + at + 1 > data_end)
    return -1;
byte = data[at];

Het masker begrenst at, en de daaropvolgende vergelijking bewijst de pakketgrens. Later in de pipeline kan LLVM de index echter opnieuw uitdrukken in termen van de oorspronkelijke offset en index. In de ene vorm ziet de oude verifier (in het ondersteunde Linux 5.15-profiel) een begrensde index; in de andere vorm verliest hij het bewijs. De lege inline assembly is niet nodig voor de CPU, maar is er om LLVM te dwingen de exacte data-afhankelijkheid te behouden die de kernel begrijpt.

De weg naar implementatie

Stap 1: Willekeurige BPF produceren

Voordat de kernel in beeld kwam, was er een tussenstap: DOOM compileren naar BPF en het object draaien in een virtuele machine in de userspace. Zonder verifier konden bugs in de codegeneratie worden gescheiden van fouten in het bewijzen van veiligheid.

Ik baseerde het experiment op PureDOOM, een poort die de hele engine in één C-header verpakt. Zelfs zonder verifier wordt willekeurige C-code niet zomaar BPF. De klassieke ABI heeft geen plek voor een zesde argument, en BPF heeft geen floating-point operaties of indirecte aanroepen.

Stap 2: Porten met een schaar

De volgende stap was het laden van het programma in een echte kernel. De vrijheid van de userspace-VM was voorbij: ik kon de 512-byte frame, de aanroepdiepte of het budget van de verifier niet verhogen. De eerste poging was om PureDOOM te nemen en alles te verwijderen wat niet paste:

• Geluid verwijderd;
• Argument-parsing en demo-playback verwijderd;
• Netwerken verwijderd;
• Bestands-I/O verwijderd;
• Interne gettime-aanroep verwijderd;
• Dynamische geheugenallocatie verwijderd;
• Functies aangepast om 5 argumenten of minder te nemen;
• Indirecte aanroepen verwijderd;
• Recursie verwijderd (extreem veel inlining toegepast).

Functiepointers komen overal voor in DOOM. Ik verving deze door één indirect_call.c die een keten van vergelijkingen bevat tegen elk bekend doel. Recursieve BSP-traversal werd omgezet naar een array en een handmatige stack.

Uiteindelijk bleek inlining een doodlopende weg. Het verminderde de diepte, maar verhoogde het aantal waarden dat tegelijkertijd live was, wat leidde tot register-spills. Het werd duidelijk dat ik niet langer DOOM aan het porten was, maar het werk van een compiler handmatig uitvoerde.

De Hacks van BPF Capsule

Hack 1: Pointer Laundering

DOOM slaat een echte pointer op in een heap of globale structuur, en laadt deze later. Na het laden ziet de verifier een gewoon getal; de oorsprong en toegestane grenzen van de pointer zijn weg.

Om dit op te lossen, moet het getal vóór toegang opnieuw worden gekoppeld aan een object dat bekend is bij de kernel. Omdat de kernel scalar - pointer verbiedt, moest de basis van de sectie in twee vormen bestaan (dubbele boekhouding). Een "gewassen" (laundered) kopie kon worden afgetrokken van het onbekende adres, terwijl de originele kopie, die zijn biografie nog had, werd gebruikt na het controleren van het resultaat:

1. x wordt geladen uit het geheugen.
2. offset = x - scalarbase (waarbij scalarbase een gewassen kopie is).
3. Controleer of 0 <= offset <= size - width.
4. resultaat = realbase + offset (waarbij realbase de originele PTRTOMAP_VALUE is).

Hack 2: Eén teller voor alle lussen

De verifier heeft een budget van ongeveer een miljoen instructies. Om lussen hierdoor te krijgen, dwong ik elke lus in één vorm die de kernel kon bewijzen. Elke teller en pointer die in de lus werd gevorderd, werd uitgedrukt via één enkel iteratienummer n.

Als de bronlus i, j en p tegelijkertijd bevorderde, reconstrueerde de getransformeerde lus deze als:

• i = i0 + n * i_step
• j = j0 + n * j_step
• p = p0 + n * p_step

De definitieve oplossing: Regio's en Fibers

De meest complete oplossing is om programmacode als data op te slaan. De verifier hoeft dan niet de volledige control-flow graph te analyseren, maar slechts een kleine interpreter.

In plaats van één instructie te interpreteren, bevat één operatie in de nieuwe machine een heel stuk reeds gecompileerde code: een regio.

Een regio is begrensd: hij eindigt bij een complexe aanroep, een return, een yield, of waar de compiler besluit een te grote graaf door te snijden. De regio voert zijn werk volledig uit, slaat live waarden op en keert terug naar een dispatcher. De dispatcher roept vervolgens de volgende regio aan. Voor de verifier is dit een gewone aanroep-aanroep boundary, niet een onderdeel van de enorme control-flow graph van DOOM.

De Software-stack

Omdat functies nu worden gesplitst door regiogrenzen, is de gewone BPF-stack niet meer voldoende. Argumenten, lokale variabelen en het retouradres moeten ergens overleven. Dit werd een software-stack in het Capsule-geheugen.

De stack groeit naar lagere adressen: fp (frame pointer) markeert de huidige framegrens, terwijl sp (stack pointer) de onderkant van de gealloceerde ruimte markeert. Een aanroep verandert alleen fp, sp en het volgende regionummer. Recursie resulteert nu in het pushen van een nieuwe software-frame, in plaats van een recursieve BPF-functieaanroep.

Fibers

Een huidige regio, de stack- en frame-pointers, de opgeslagen staat en een deel van de software-stack vormen samen een fiber. Er kunnen meerdere fibers zijn; elke fiber heeft een eigen staat en stack-opslag, terwijl globalen en de heap gedeeld worden.

Waarom de verifier deze dispatcher accepteert

De dispatcher bestaat uit drie begrensde lussen. De binnenste lus (de step) voert maximaal 32 regio's uit en keert dan terug. De laag daarboven roept de step tot 2.048 keer aan; het startprogramma roept die laag tot 64 keer aan.

De verifier controleert elke globale BPF-functie slechts één keer. De analysekosten zijn dus beperkt, terwijl het aantal overgangen tijdens runtime groot is: $32 \times 2048 \times 64 \approx 4,2$ miljoen regio's in één aanroep, terwijl de grafen die de kernel controleert klein blijven.

Het Geheugenmodel en Pointer Laundering 2.0

Het huidige ontwerp start met één 4-GB uitgelijnd virtueel venster dat globalen, de heap en software-stacks bevat. Een Capsule-pointer is een adres: window_base + displacement.

• Op Linux 6.9+: Het venster wordt ondersteund door bpfarena. Een pointer kan worden opgeslagen als een gewoon getal (scalar). Vóór dereferentie gebruikt de compiler de speciale BPF addrspacecast instructie, waardoor de verifier het resultaat markeert als PTRTO_ARENA.
• Op oudere kernels: Het venster wordt opgebouwd uit stukken van 4 MB. De compiler gebruikt een router om te bepalen in welk map-stuk een adres valt.

De userspace-proces mapt dezelfde pagina's op dezelfde adressen. BPF kan dus een unsigned char * naar de framebuffer teruggeven, en het proces kan dit direct lezen zonder kopieerkosten.

De Heap en Niet-onderbrekende Operaties

Capsule gebruikt TLSF voor geheugenbeheer. Omdat TLSF een lock vasthoudt, mag de berekening niet terugkeren naar de dispatcher tijdens een allocatie. Functies gemarkeerd met CAPSULE_NOSUSPEND mogen niet worden onderbroken; de compiler moet bewijzen dat deze functies en alles wat ze aanroepen, eindigen zonder suspensie.

Integratie met XDP

XDP maakt de grens tussen ordinary BPF en Capsule duidelijk. Een pointer naar een pakket (struct xdp_md *ctx) kan niet worden opgeslagen in een software-frame omdat hij na herladen slechts een scalar zou zijn.

De compiler splitst regio's daarom in twee klassen:

1. Scalar regions: Hebben alleen een fiber-nummer en staat nodig.
2. Context regions: Ontvangen de echte struct xdp_md * als eerste BPF-functieargument.

De integratie van DOOM

De integratie is nu relatief eenvoudig. PureDOOM is ontworpen om ingebed te worden. In Capsule zijn de functies voor geheugen, WAD-lezen en de engine zelf gecompileerd in één BPF-object.

De userspace participeert alleen aan de buitenrand: bij opstarten wordt de WAD in het Capsule-geheugen gekopieerd. Daarna leest de BPF-code de WAD in place. Elke game-tick, inclusief rendering, is één BPF-entry point. Na het renderen publiceert BPF een pointer naar de framebuffer, die de userspace direct uitleest voor terminal-output.

De prijs van grote code in de kernel

De kosten hangen af van hoe vaak de uitvoering een regiogrens overschrijdt en hoeveel floating-point berekeningen er zijn.

Prestaties Intel i7-12700K (Linux 7.1.3, 6.9 profiel):

Voorbeeld	Native	In kernel	Ratio
DOOM, één frame	0.105 ms	0.367 ms	3.5×
SQLite	43.8 ms	289.4 ms	6.6×
Lua	70.1 ms	524.0 ms	7.5×
QuickJS	116.6 ms	1068.0 ms	9.2×
CPython	120.9 ms	1889.2 ms	15.6×
llama2.c, Q8	14.6 ms	274.8 ms	18.8×
llama2.c, FP32	7.5 ms	471.2 ms	62.9×

Prestaties ARM64 (Linux 7.0.12, 6.10 profiel):

Voorbeeld	Native	In kernel	Ratio
DOOM, één frame	0.227 ms	0.913 ms	4.0×
SQLite	81.4 ms	639.2 ms	7.9×
Lua	127.6 ms	1090.4 ms	8.5×
QuickJS	224.0 ms	2313.1 ms	10.3×
CPython	242.3 ms	4487.9 ms	18.5×
llama2.c, Q8	23.2 ms	539.3 ms	23.2×
llama2.c, FP32	13.0 ms	775.2 ms	59.6×

Analyse:

• Integer- en pointer-code (DOOM, SQLite) draait slechts enkele keren trager dan native.
• Interpreters (Lua, Python) zijn ongeveer een orde van grootte trager door hun eigen dispatch-lussen.
• Floating point is de grootste uitschieter: llama2.c FP32 is 60× trager omdat de target geen FPU heeft en alles via software-emulatie gaat.

Impact op netwerkdoorvoer (XDP)

Bij het gebruik van een Lua-observer op een gigabit-interface daalt de downloadspeed van 995 Mbit/s naar 643 Mbit/s (Intel) of 295 Mbit/s (ARM64). Zonder de output naar userspace blijft de doorvoer bij Lua echter bijna intact (964 Mbit/s).

De kloof tussen LLVM en de verifier

Er is een fundamenteel probleem: LLVM mag programma's vervangen door semantisch equivalente versies, maar de verifier accepteert vaak slechts één specifieke vorm van het bewijs. Een kleine LLVM-update kan een noodzakelijke instructie verwijderen, waardoor een oude bewijsvoering breekt.

De oplossing is niet om de verifier te verzwakken, maar om een expliciet contract te schrijven tussen de compiler en de verifier. BPF Capsule levert zijn eigen passes omdat die laag nog niet bestaat.

Wat Capsule niet doet

• Geen security-boundary: Het is research-software; het beschermt programma-onderdelen niet tegen elkaar.
• Geen OS: Er zijn geen bestanden, sockets of processen. Systeemoproepen moeten door de applicatie worden geïmplementeerd.
• Finite capaciteit: Het aantal fibers, de grootte van de stack en heap zijn vastgelegd bij build- of laadtijd.
• Afhankelijkheid: De bewijzen die de verifier accepteert, hangen af van de LLVM- en kernelversies.

Conclusie

De verifier bewijst nooit dat DOOM termineert. Hij bewijst alleen dat de volgende regio en de begrensde dispatcher termineren. Tijdens runtime assembleert Capsule het volledige spel uit deze eindige stukjes.

Verder lezen

• BPF Capsule — Broncode, voorbeelden en instructies.
• Linux verifier — Registertypes, waardebereiken en state merging.
• BPF Design Q&A — Calling conventions en verifier-beperkingen.
• RFC 9669: BPF ISA.
• bpf_arena — De commit die deze feature introduceerde.
• Flying the nest — Een eerdere BPF-port van Doom.