Wanneer ldaxr niet werkt: Exclusieve toegangen en cachebaarheid op AArch64

Inleiding

Dit bericht beschrijft mijn reis bij het implementeren van een basis spin lock en het uitzoeken waarom het uitvoeren van een load exclusive een exceptie veroorzaakt op echte hardware, maar niet in QEMU. We behandelen een boeiende combinatie van onderwerpen, waaronder: spin locks, exception handling, virtueel geheugen, geheugentypen, geheugenattributen, cachebaarheid, de verschillen tussen QEMU en echte hardware, en bovenal hoe exclusieve geheugenoperaties werken.

Een Spin Lock implementeren

Zodra ik op het punt was gekomen waarop ik secundaire cores op de CPU kon inschakelen en opstarten, was het tijd om een vorm van wederzijdse uitsluiting (mutual exclusion) te implementeren. Als triviaal voorbeeld: elke core print zijn eigen id tijdens het opstartproces, bijvoorbeeld: "Running core 0". Zonder wederzijdse uitsluiting zullen de cores met elkaar racen en hun output door elkaar weven, wat resulteert in een onleesbare chaos zoals in het onderstaande fragment:

Running core 0
RRRununing cournnien ng 2cni
onrge  1co
re 3

Om leesbare output te krijgen, willen we het printproces beschermen met een vorm van wederzijdse uitsluiting, zodat slechts één core tegelijk kan printen.

Ter voorbereiding op locks en synchronisatie heb ik Arm's Implementation Software Synchronization Primitives in A64 gelezen en samengevat, evenals mijn favoriete OS-boek Operating Systems: Three Easy Pieces. Als goed startpunt besloot ik een spin lock te implementeren, wat in zijn eenvoudigste vorm zeer rechttoe rechtaan is. Ik besloot er ook toe om de spin lock handmatig in assembly te schrijven, wat leuker is dan in C/C++.

Mijn basisversie maakt gebruik van de load exclusive en store exclusive instructies, die samenwerken om atomiciteit te bereiken. Het idee is dat de stxr-instructie alleen slaagt als er geen andere schrijfacties naar dezelfde geheugenlocatie zijn waargenomen sinds de ldaxr-instructie heeft plaatsgevonden.

void SpinLock::lock() {
    uint32_t lock_read;
    uint32_t store_result;
    asm volatile(
        "1:                    \t\n\
        ldaxr  %w0, [%2]      \t\n\
        cbnz   %w0, 1b        \t\n\
        mov    %w0, #1        \t\n\
        stxr   %w1, %w0, [%2] \t\n\
        cbnz   %w1, 1b        \t\n\
        "
        : "=&r"(lock_read), "=&r"(store_result) // outputs
        : "r"(&_lock) // input
        : "memory" // clobber
    );
}

void SpinLock::unlock() {
    asm volatile(
        "stlr   wzr, [%0]"
        : // no output
        : "r"(&_lock) // input
        : "memory" // clobber
    );
}

De lock maakt gebruik van een 32-bits lock-woord (vandaar het gebruik van w-registers), waarbij 0 staat voor ontgrendeld en 1 voor vergrendeld. Om correctheid te garanderen, is de load exclusive gemarkeerd met acquire-semantiek (de "a" in ldaxr), wat garandeert dat alle geheugentoegangen na de load niet vóór deze load worden geherordend. Evenzo is de store in het unlock-pad gemarkeerd met release-semantiek (de "l" in stlr), wat garandeert dat alle geheugentoegangen vóór de store niet ná deze store worden geherordend.

Locks worden meestal beoordeeld op drie categorieën: correctheid, eerlijkheid (fairness) en prestaties. De correctheid valideren we later empirisch, en de geheugenvolgorde hebben we al overwogen. Eerlijkheid is in deze basisversie geen prioriteit, maar een core zou kunnen worden uitgesloten (starved) en de lock nooit krijgen als andere cores hem steeds als eerste bemachtigen. De prestaties zijn niet optimaal, aangezien cores cycli verspillen aan busy-waiting om de lock te verkrijgen.

Een aanpak om het prestatieprobleem aan te pakken is het gebruik van Arm's wfe (wait for event) en sev (send event) paar, die de core in een energiezuinige stand zetten terwijl deze wacht op een event, en alle wachtende cores weer wakker maken. Dat is een onderwerp voor in de toekomst.

Validatie

Ik heb de spin lock aanvankelijk getest in het pad met de onleesbare output die ik eerder beschreef, om leesbare output te krijgen tijdens het opstarten van meerdere cores. In de virt en rpi4 boards van QEMU leek alles prima te werken. Voor de zekerheid heb ik het programma een paar duizend keer opnieuw uitgevoerd en nooit onleesbare output waargenomen.

// SpinLockGuard is een RAII-object dat lockt tijdens
// constructie en unlockt tijdens destructie
{
    SpinLockGuard guard(&_print_lock);
    kprintf("Running core %d\n", cpu_id);
}

Echter, toen ik dezelfde code op mijn rpi5 uitvoerde, kreeg ik een mysterieuze exceptie. De onderstaande output is van mijn eigen exception handler, waarin we een Data Abort exceptie zien met een Exception Class (EC) waarde van 37 (0x25). Volgens Arm's "Types of exception": "Een data abort exception treedt op als gevolg van een load- of store-instructie".

Got an exception (from 0x84474)
- Syndrome is 0x96000410
- EC is 37 (Data Abort)
Register dump:
x0:  0x2bcf88
...
x30: 0x85554

Als we nauwer kijken naar de instructie die de CPU uitvoerde toen de exceptie optrad (0x84474), zien we dat dit precies de ldaxr-instructie is. Dit komt overeen met de Data Abort waarde die we kregen, dus er moet iets mis zijn gegaan met de ldaxr geheugentoegang. Als sanity check: het vervangen van de load exclusive en store exclusive door een "normale" load acquire (ldar) en een gewone store (str) lost het probleem op en er wordt geen exceptie geworpen. Dit vertelt me dat er iets is dat de exclusieve operaties blokkeert.

0000000000084470 <_ZN13SpinLockGuardC1EP8SpinLock>:
84470:       f9000001        str     x1, [x0]
84474:       885ffc20        ldaxr   w0, [x1] <-- De CPU was hier
84478:       35ffffe0        cbnz    w0, 84474
8447c:       52800020        mov     w0, #0x1
84480:       88027c20        stxr    w2, w0, [x1]
84484:       35ffff82        cbnz    w2, 84474
84488:       d65f03c0        ret

Uitzoeken waarom

Gelukkig herinnerde ik me uit de Implementation Software Synchronization Primitives in A64 dat er een specifieke sectie was over geheugenattributen. Deze sectie benadrukt de geheugenattributen waarvoor architectonisch is gegarandeerd dat atomaire instructies atoom zijn. Dit zijn:

• Inner Shareable, Inner Write-Back, Outer Write-Back Normal memory met Read allocation hints en Write allocation hints en niet transient.
• Outer Shareable, Inner Write-Back, Outer Write-Back Normal memory met Read allocation hints en Write allocation hints en niet transient.

De pagina somt ook geheugentypen op die mogelijk geen atomaire instructies ondersteunen. Het meest opvallende punt is:

• Device, Non-cacheable memory, of geheugen dat wordt behandeld als Non-cacheable, in een implementatie die hardware cache-coherentie ondersteunt.

Geheugentypen

Het standaardgeheugentype voor al het geheugen is Device memory. Ik heb echter virtueel geheugen zeer vroeg in floss opgezet en gemapt, waarbij alle regio's van RAM zijn gekoppeld aan het "Normal" geheugentype, zodat niet-uitgelijnde toegangen (unaligned accesses) kunnen worden uitgevoerd (bijv. een 8-byte load van een adres dat niet op 8-byte is uitgelijnd). Dit komt omdat Device memory uitlijningscontrole vereist. Ik werd me hiervan bewust bij het upgraden van QEMU v8.2.2 naar v11.1.50, wat een (niet zo recente) patch bevatte om uitlijningscontrole aan device memory toe te voegen, wat een behoorlijk frustrerende exceptie veroorzaakte die ook enige tijd kostte om te debuggen.

Normal memory is een vrij vage term, maar omvat over het algemeen alle typen geheugen die geen Device zijn. Normal memory kan over het algemeen gecached, speculatief en geherordend worden, afhankelijk van de attributen. Device memory dat wordt benaderd via memory mapped IO (MMIO) kan over het algemeen niet speculatief zijn of gecached worden zoals RAM.

Alle typen geheugen worden gedefinieerd door een set attributen, die kunnen worden geconfigureerd voor individuele virtuele geheugenmappings.

Geheugenattributen

Geheugenattributen worden geconfigureerd via de Memory Attribute Indirection Register (MAIR_EL1 voor EL1). Dit is een 64-bits register dat is verdeeld in 8 verschillende sets attributen van elk 8 bits. Een vermelding in de vertaaltabel (translation table of page table in Linux-terminologie) die naar een blok fysiek geheugen wijst (bijv. een Block- of Page-descriptor), heeft drie bits die refereren naar een index in het MAIR-register, wat de attributen voor die specifieke geheugenmapping aangeeft. Daarnaast heeft zo'n vermelding bits die de uitvoerbevoegdheden, toegangsrechten, deelbaarheid (shareability) en meer configureren.

Relevant voor dit bericht, en specifiek voor exclusieve geheugenoperaties, is de shareability-configuratie, die kan worden ingesteld op: Non-Shareable, Inner-Shareable, of Outer-Shareable. In grote lijnen bepaalt shareability in welk domein, en voor welke waarnemers, geheugenoperaties binnen een eindige tijd en zonder expliciet cache-onderhoud voltooid moeten zijn. Dit onderwerp is behoorlijk complex; voor meer informatie verwijs ik naar de Arm ARM, sectie B 2.7.1. In floss is het Normal geheugentype geconfigureerd als Inner-Shareable, wat is wat Arm van besturingssystemen verwacht.

Momenteel configureert floss slechts twee sets geheugenattributen: één voor Device memory en één voor Normal memory. Laten we de details voor Device negeren en ons concentreren op Normal memory.

• Device: 0b00000000, Device-nGnRnE memory
• Normal: 0b11111111, Normal memory, Outer Write-Back, Inner Write-Back, met Read allocation hints en Write allocation hints en Non-transient.

De Write-Back eigenschap betekent dat schrijfacties naar de cache moeten worden geschreven, en pas naar het geheugen worden geflusht wanneer de cache-line wordt verwijderd (evicted). Kortom, dit betekent dat de geheugenattributen die ik heb geconfigureerd voor Normal memory volledige ondersteuning hebben voor caching. Het komt ook volledig overeen met de architecturale vereisten voor atomics.

Een alternatief voor Write-Back is Write-Through, waarbij onmiddellijk naar zowel de cache als het geheugen wordt geschreven, zonder te wachten tot de cache-line wordt verwijderd.

Globale en lokale cachebaarheidsscope

Zoals we hebben geconcludeerd, hebben de geheugenattributen voor het Normal geheugentype de cachebare Inner en Outer Write-Back eigenschap. Toch is, met alle details die we tot nu toe hebben, de enige logische verklaring voor waarom er een exceptie optreedt bij het uitvoeren van de load exclusive de cachebaarheid.

Met hulp van mijn LLM kwam ik erachter dat er een globale instelling is in het System Control Register (SCTLR): de "C" bit, die de cachebaarheid voor datatoegangen op EL1 en EL0 regelt (floss draait op EL1). Bij het opvragen van deze bit zie ik dat deze op alle cores op de standaardwaarde 0 staat, wat de datacache voor al deze cores uitschakelt. Het instellen van deze bit op 1 doet de exceptie op de rpi5 verdwijnen. Hoera!

In de documentatie over het L1-geheugensysteem en cachegedrag van de Cortex-A76 CPU (de CPU van de rpi5) staat enkele onthullende informatie:

Wanneer de datacache is uitgeschakeld, worden instructies en operaties als volgt beïnvloed:

Alle load- en store-instructies naar cachebaar geheugen worden behandeld alsof ze Non-cacheable zijn en zijn incoherent met de caches in zowel deze core als andere cores in de cluster. Software moet hier rekening mee houden.

Cachebaarheid

We hebben ontdekt waarom de exceptie optrad op de rpi5, omdat SCTLR.C met een waarde van 0 het geheugen effectief als non-cacheable behandelde. Interessant genoeg, als ik de globale cachebaarheidsinstelling voor elke core inschakel door SCTLR.C op 1 te zetten, maar het MAIR-attribuut wijzig naar iets waar Write-Back niet is ingeschakeld, treedt dezelfde exceptie op. Ik heb een kleine test gedaan met verschillende MAIR-configuraties voor het geheugen waar ldaxr naar verwijst, en dit is het resultaat op de rpi5:

Bit patroon	Beschrijving	Exceptie veroorzaakt
0b00110011	Normal memory, Outer/Inner Write-Through Transient	Ja
0b01000100	Normal memory, Outer/Inner Non-cacheable	Ja
0b01110111	Normal memory, Outer/Inner Write-Back Transient	Nee
0b10111011	Normal memory, Outer/Inner Write-Through Non-transient	Ja
0b11111111	Normal memory, Outer/Inner Write-Back Non-transient	Nee

Uit dit experiment lijkt het erop dat de load exclusive instructie niet werkt zonder Write-Back. Sterker nog, de documentatie van de geheugenattributen op de Cortex-A76 CPU zegt dat: "... een pagina alleen cachebaar is als de Inner en Outer geheugenattributen Write-Back zijn. In alle andere gevallen worden alle pagina's gedegradeerd naar Non-cacheable Normal memory". Dit betekent dat, hoewel Write-Through technisch gezien "schrijven naar cache" betekent, de Cortex-A76 CPU dit type geheugen in feite niet cached.

Hieruit volgt dat de load exclusive operatie alleen zonder exceptie wordt voltooid als cachebaarheid is ingeschakeld, zowel globaal (SCTLR.C staat op 1) als lokaal (geheugenattribuut voor de vertaaltabelvermelding is geconfigureerd met Write-Back).

Het is een beetje frustrerend dat ik dit niet in QEMU kon ontdekken. QEMU heeft nog geen ondersteuning voor het rpi5 board, en er zijn waarschijnlijk een paar verschillen tussen de werkelijke rpi5 hardware en het beschikbare rpi4 QEMU board. Toch, bij het doorspitten van de QEMU-broncode, blijkt dat cachebaarheid simpelweg helemaal niet wordt gemodelleerd (zie referenties in commits fa2ef212df, b0fe242751), wat wordt bevestigd door het feit dat de constante voor SCTLR_C nergens wordt aangeroepen. Dus, ook al draait het prima in QEMU, neem niet aan dat alles perfect is totdat je het in de echte wereld hebt getest.

Exclusieve monitoren

Om atomiciteit te bereiken via de load exclusive en store exclusive instructies, worden één of meer exclusieve monitoren gebruikt. Elke core heeft zijn eigen lokale monitor, en alle cores hebben toegang tot een globale monitor. Elke monitor heeft twee mogelijke toestanden: open en exclusive. Bij het uitvoeren van een load exclusive instructie gaan de monitor(s) naar de exclusive staat en wordt het adres van de load geregistreerd. Bij het uitvoeren van een store exclusive instructie wordt gecontroleerd of de monitor(s) allemaal in de exclusive staat zijn en of het adres overeenkomt, waarna de operatie slaagt.

Nauwkeuriger gezegd is het adres dat in de exclusieve monitor(s) wordt opgeslagen alleen de bovenste adresbits, aangeduid als de Exclusive Reservation Granule (ERG). Twee adreslocaties binnen dezelfde ERG zullen verschijnen als dezelfde vermelding in de monitor(s). Op een typisch systeem komt de ERG overeen met de grootte van een cache-line.

Exclusieve toegangen tot geheugenlocaties die zijn gemarkeerd als Non-shareable zullen alleen de lokale monitor benaderen, en geheugenlocaties die gemarkeerd zijn als shareable (Inner of Outer) zullen zowel de lokale als de globale monitoren benaderen.

Opnieuw benadrukt de Implementation Software Synchronization Primitives in A64 van Arm een zeer interessant aspect in de documentatie over exclusieve monitoren:

Hoewel we de lokale en globale monitoren beschrijven als verschillende dingen, kunnen ze in feite logica delen. Bijvoorbeeld, een implementatiebenadering is het gebruik van een combinatie van de per-core lokale monitoren en de cache-coherentielogica om globale monitorfunctionaliteit te bieden voor cachebare locaties.

Dit voelt als de kers op de taart van dit mysterie. Blijkbaar (of empirisch?) lijkt de Cortex-A76 CPU van de rpi5 cachebaarheid te vereisen om te voorkomen dat een load exclusive instructie een Data Abort exceptie genereert. Dit zou zeer goed kunnen komen doordat het de globale monitor implementeert via cache-coherentielogica, en daarom elke exclusieve geheugenoperatie naar een geheugenlocatie die gemarkeerd is als shareable (Inner of Outer) en de globale monitor benadert, zal falen wanneer cachebaarheid is uitgeschakeld.

Conclusie

Laten we samenvatten: ik wilde wederzijdse uitsluiting en koos voor een "handgemaakte" spin lock met load exclusive en store exclusive. Het werkte prima in QEMU, maar ik kreeg een exceptie op de rpi5 met echte hardware. Ik ben vervolgens documentatie gaan doorspitten (Arm ARM, Cortex-A76, Implementation Software Synchronization Primitives in A64) om te begrijpen wat er aan de hand was.

Uit dit avontuur kan ik concluderen dat ik op deze implementatie en configuratie van de Raspberry Pi 5 met een Arm Cortex-A76 CPU waarneem dat een load exclusive operatie op shareable geheugen (die vermoedelijk de globale exclusieve monitor benadert), niet werkt tenzij cachebaarheid is ingeschakeld, zowel globaal (SCTLR.C staat op 1) als lokaal (geheugenattribuut voor vertaaltabelvermelding geconfigureerd met Write-Back).

Tijdens de ontwikkeling itereer ik snel met QEMU, maar verifieer ik van tijd tot tijd ook op echte hardware met de Raspberry Pi 5. Dit creëert verschillende lagen, wat dit een beetje verwarrend maar tegelijkertijd zeer interessant maakt. QEMU zegt het één, de Arm ARM het ander, en uiteindelijk de implementatie van de Cortex-A76 weer iets anders.

Dit is tot nu toe de meest interessante bug die ik ben tegengekomen tijdens het ontwikkelen van floss, maar waarschijnlijk niet de laatste. Bedankt voor het lezen!