HW-buggar eller konstigt beteende DU känner till

Denna tråd skapas p.g.a av diskussion som gick lite väl off-topic.

Men diskussionen i sig är faktiskt riktigt intressant och tänkte testa med en tråd där alla kan visa exempel på buggar eller konstigt beteende som man upplevt som programmerare.

Kan köra två exempel på hur det kan se ut (det andra kommer i ett andra inlägg). Alla känner nog till historien om att den ursprungliga Pentium CPUn räknade fel i vissa lägen, men den CPUn hade även en annan lite mindre känd bug som går under namnet F00-buggen, egentligen ska det vara F00F då det är den op-kod (maskinkod) som orsakar felet.

Buggen triggas av att man kör

lock cmpxchg8b edi

lock betyder att nästföljande instruktion ska köras med RAM-bussen låst vilket i sin tur gör instruktionen atomär sett från andra CPU-kärnor. Instruktionen med det komplicerade namnet cmpxchg8b betyder jämför det som ligger i registren eax:edx (64 bitar, 8 bytes därav suffixet 8b) men en minnesadress som ska pekas ut av argumentet, om det är samma data så byter man ut innehållet i RAM mot det som ligger i registren ebx:ecx. Problemet är sista delen där det står edi inte är en pekare, utan ett register som bara kan hålla 4 bytes (32-bitar).

Den korrekta formen av denna instruktion skulle vara något likt

lock cmpxchg8b (edi)

som betyder jämför med det som ligger på den adress som edi innehåller, medan varianten ovan säger: jämför med värdet i registret.

Korrekt beteende här är att programmet ska orsaka ett undantag och hoppa in i OS-kärnan som typiskt ska städa upp programmet, men i stället så hängde sig hela datorn vilket var rätt illa då man får köra den instruktionen som "vanlig" användare (behöver ej vara UNIX "root" eller Windows "Administrator"). Buggen triggades tydligen av att man "glömt" ta bort effekten av lock prefixet så OS-et blev hängande på första bästa RAM access.

Det andra exemplet är ingen bug utan en intressant observation kring hur man ibland designar CPU-finesser på ett sätt som gör att program i teorin kan hänga sig i ett så kallat live-lock. Men i praktiken så är det lite som kärnkraftverk, sannolikheten att det ska ske ett haveri är ju så liten att man faktiskt kan ignorera problemet...

Alla RISC implementationer jag jobbat med, vilket inkluderar PowerPC, MIPS och ARM, implementerar s.k. atomära instruktioner på ungefär samma sätt. Stegen man gör är

1. läs upp innehållet från en minnesadress i ett speciellt läge som kallas load linked, detta leder till att systemet håller reda på skrivningar från ALLA CPU-kärnor på just den adressen

2. man utför det man ska utföra, addera 1 i mitt exempel nedan

3. man försöker sedan skrivna ner resultatet på samma adress man läste upp startvärdet från med en s.k store conditional instruktion. Denna operation kommer misslyckas om det skett ett interrupt som modifierat adressen eller om någon annan CPU-kärna modifierat adressen sedan steg 1. Misslyckas detta anrop går man till punkt 1 och gör om.

Den uppmärksamme inser snabbat att det finns faktiskt ingen garanti för att denna typ av operation någonsin lyckas då man inte har någon övre gräns för hur många misslyckade försök som tillåts. Men tittar man i assembler för t.ex. ARM på Linux så ser man att atomic_inc(atomic_t *v) är implementerat på följande sätt:

Notera semikolon är början på kommentar i assembler, så det som står efter ; på varje rad är alltså bara en kommentar

; värdet på pekaren v ligger i register r0 från start
movs    r3, #1 ; lagra 1 i register r3
1:
ldrex    r2, [r0] ; läs upp värdet som 'v' pekar på i "länkat" läge och lägg det i r2
add      r2, r3   ; lägg på 1 (som är det värde r3 har) till r2
strex    r1, r2, [r0] ; försök spara värdet i r2 i adressen som r0 innehåller, r1 kommer innehåller om det gick bra eller inte
teq      r1, #0 ; ett värde på 0 i r1 betyder att det gick bra
bne      1b ; om r1 inte var 0, hoppa tillbaka till 1:

(Jag förenklade detta jämfört med diskussionen detta kommer i från där operationen var atomic_inc_and_return())

Ganska komplicerat för att lägga ett till en cell i RAM, eller hur?

Jämför detta med den, så ofta bespottade, x86 arkitekturen där samma sak ser ut så här

lock xadd 0x1, (rdi) ; värdet på pekaren v ligger i register rdi (som alltid innehåller första argumentet till en C-funktion)

Denna instruktion kan inte misslyckas med mindre än att rdi är en ogiltig adress och då blir det ett undantag. Är ju inte heller någon större nackdel för CPUn att det är en enda instruktion som utför read-modify-update i en smäll, något som man då kan optimera för.

Dessa typer av atomära instruktioner är kritiska för att implementera saker som lås (mutex, semaphores) så det är lite intressant att se att x86 som anses "dålig" och "komplicerad" är så väldigt enklare än RISC som ska vara "enkel" och "vacker".

Har någon annan exempel på konstigheter, buggar eller något som visar väldigt för/nackdelar mellan RISC/CICS?

Att "lock" prefix kan ta upp till 200 cykler är extremt enkelt att förklara: vad är latensen mot RAM? Ungefär 150-200 cykler. I vissa lägen så måste saker ända ut till RAM och "lock", precis som "dmb", säkerställer att nästföljande instruktion inte körs innan man vet att alla CPU-kärnor nu ser de skrivningar som den lokala CPUn gjort upp till punkten där "lock" / "dmb" körs. Så x86, ARM, PowerPC eller MIPS fungerar på exakt samma sätt här.

Och för att kommentera mitt exempel ovan: hur skulle du annars lösa detta på ARM? Det jag skrev ovan är exakt den kod som Linux och Windows kommer använda för att implementera atomic add. Det är också den kod som gcc genererar om du använder __sync_fetch_and_add (gcc atomic extensions).

RISC CPU:er har endast ett sätt att göra något atomärt (de är ju "reduced" instruction set) och det är via "load-linked" / "store conditional".

Har en till intressant exempel på x86 kontra ARM, PowerPC och MIPS

Om du initialt har

volatile int x = 0;
volatile int y = 1;

och sedan kör detta på en tråd

x = 10;
y = 11;

och ungefär samtidigt kör detta på en annan tråd

while (x != 10) /* do nothing*/;

int a = y;
printf("%d\n", a);

Vad kommer skrivas ut?

På x86 kommer det ALLTID bli 11, på ARM, PowerPC eller MIPS blir antagligen 11, men det kan även bli 1...

Notera att detta är inte en bug i HW utan en bug i mitt program som saknar en explicit minnesbarriär mellan "x=10;" och "y=11;", men det visar att finns sätt att skjuta sig i foten på ARM som inte existerar på x86. Att köra en minnesbarriär är som du redan noterat med "lock" (som är en implicit minnesbarriär) allt annat än snabbt.

Spelar absolut ingen roll att jag använder ett register på ARM, sedan är jag TVUNGEN att använda register på ARM. Kombinationen av ldrex, some-op, strex är det som motsvaras av lock some-op på x86. ldrex och strex gör, per definition en läsning respektive en skrivning mot delad cache / RAM och de kommer kosta MINST lika mycket som en instruktion som körs med lock-prefix. x86 har ju fördelen att den vet hela förloppet som ska vara atomärt då instruktioner som t.ex. xadd är av typen read-modify-write, detta går då naturligtvis att optimera. RISC:ar vet inte vad som kommer mellan load-linked (ldrex på ARM) och store-conditional (strex på ARM) så det är svårare att optimera det hela i HW.

I teorin är load-linked/store-conditional mer generell, men i praktiken finns det nog inget man kan göra på RISC som inte har en direkt motsvarighet på x86. Och med TSX i Haswell så kommer x86 få en variant av load-linked/store-conditional som är LÅNGT mer generell än något som implementerats i någon RISC CPU.

Ah, du har en poäng att jag missade poängen. Poängen är att du kan skriva ett KORREKT program på x86 som inte behöver skrivbarriärer då ordningen för synlighet är för andra CPU:er är garanterad att vara korrekt. Detta betyder att du kan implementera saker som "work-stealing scheduler" (fork/join i Java, OpenMP för C/C++, TPL för .Net) mer effektivt på x86 än på RISC, då RISC (eller i alla fall ARM, PowerPC och MIPS) kommer kräva explicita minnesbarriärer som, per definition, är synkroniserade instruktioner och att köra sådana är DYRT på en out-of-order CPU (som ARM är sedan Cortex A9).

Inte alls onödigt, det är snabbare att addera register än att addera register + konstant. Visst blir detta en extra instruktion, men om det blir fler än ett varv i loopen så spar man in denna a instruktion. Du konstaterade redan nedan att man adderad mot register r3, som just innehåller en 1:a.

Man läser upp värdet r0 pekar på i r2 och man låser inget, gjorde man det skulle aldrig strex misslyckas. Man sätter någon intern flagga i CPUn så att den håller reda på om någon skriver till den cache-line som värdet r0 pekar på. Notera att denna instruktion är säker 50-100 gånger dyrare än den "movs" du optimerade bort, så den optimeringen är meningslös.

Därför att r3 innehåller värdet 1. Om man måste köra denna loop flera varv så är detta snabbare, sedan kommer min implementation från en mer generell funktion än att addera exakt 1. Du kan bara addera ett tal mellan 0 och 4095 med på ditt sätt med att addera ett konstant värde, med "mov" till ett register utanför loopen hanterar man tal mellan 0-65535 + att man enkelt kan lägga till en extra mov för att hantera 0-0xffffffff.

Och här har du nästa instruktion som är betydligt mycket dyrare än t.ex. en "movs" som du optimerat bort.

; värdet på pekaren v ligger i register r0 från start
try:
   ldrex   r2, [r0] 
   add     r2,r2,#1 
   strex   r1, r2, [r0]
   cmpeq    r1, #0 
   bne try

Vad tror du tiden för ldrex och strex är? Kanske lägre i antal cykler, men det är i så fall för att din ARM CPU inte går på 3GHz som din x86 CPU gjorde. Den erfarenhet jag har av att jobba med x86, PowerPC och MIPS är just hanteringen av atomära instruktioner definitivt är mer effektivt på x86. På lås som det är "contention" om så ökar bara skillnaden.

Har svårt att tro den kod jag listade initialt har några som helst prestandaproblem, för det var inget jag skrev (är som sagt ingen ARM expert) utan är vad gcc producerar när man använder __sync_add_and_fetch (vilket också resulterar i "lock xadd" på x86) samt kolla precis upp Linux kärnan på ARM och de använder också exakt denna implementation för atomic_add och personen som skrivit den koden jobbar (eller i alla fall jobbade) på ARM.

Edit: och en poäng jag försökte göra är att x86, tvärt om vad du skrev, är MER deterministisk än RISC. Visst, det KAN ta latensen motsvarande en RAM access att köra en instruktion med lock-prefix, men det är i alla fall en specificerat worst-case.

På en RISC är den maximala tid det tar att köra motsvarande sekvens obestämd!!

gcc använder definitivt xor för att nollställa variabler, på Sandy Bridge och senare känns just sekvensen xor regX, regX igen och kan utföras utan att det ens tar upp en exekveringsport!

Men det är väl extremt relevant hur effektivt en CPU kan hantera konstruktioner som moderna programmeringsspråk utnyttja. Är ju rätt få som sitter och pillar i assembler idag. Anledningen att fork/join är att man kan skriva sin "work-stealing" logik så att de andra CPU:erna inte kommer göra något innan de "ser" den sista förändringen man gjorde i en serie. På RISC så vet man inte om tidigare skrivningar är synliga med mindre än att lägga in explicita barriärer, men x86 garanterar inte NÄR man ser förändringen, men den garanterar att när man väl ser den SISTA förändringen så är även alla andra förändringar synliga.

Så för en out-of-order CPU så är ju x86 att föredra då man i vissa lägen kan optimera bort (dyra) skrivbarriärer.

Så fort du blandar in CPU-cache i systemet så kan du längre inte räkna klockcykler, det var en väldigt debatt om just detta i slutet av 80-talet (när CPU-cache började dyka upp) mellan arkitekter av realtids OS. I början så var det vissa som var så rabiata att de slog av CPU-cachen just p.g.a. detta, men man insåg ganska snart att det liksom inte riktigt höll.

Så du KAN INTE veta på klockcykelnivå när du får tillbaka kontrollen på en modern ARM heller. Och blandar du även in multicore så vet du än mindre eftersom instruktioner då kan stalla på MESI uppdateringar som sker över en bus som delas mellan alla CPU-kärnor, i.e. tiden det tar att köra en instruktion på CPU #0 kan alltså variera beroende på vad som händer på de andra CPU-kärnorna.

Och när CPUn även är out-of-order så blir det inte längre relevant att räkna antal instruktioner för att avgöra hur fort något exekverar, det viktiga är hur stor andel av instruktionerna som är helt eller delvis oberoende. Nu har i.o.f.s. Cortex A9 ett ganska litet out-of-order fönster, men när Cortex A15 börjar dyka upp så kommer ARM allt mer likna x86 i hur stor variation en specifik instruktion kan ta. Det absolut största problemet på en CPU som t.ex. Sandy Bridge som har ett enormt out-of-order fönster (har för mig att det är 160 instruktion långt) är: hur mäter du tiden det tar att exikverar enskilda instruktion? Variansen i en sådan mätning kan i princip vara ett out-of-order fönster stort...

Och precis som jag försökte påpeka så är antal CPU-cykler en sådan instruktion tar helt irrelevant, framförallt på en RISC där alla instruktioner normalt sätt tar 1 cykel att ta sig genom "dispatch" delen av pipe:en, vilket många anser vara "kostnaden" för att köra instruktionen. Men en annan sak som gör det lite meningslöst att prata klockcykler är att även på simpla CPU:er som ARM Cortex A9 och Intel Atom har man en pipeline på 10-14 steg.

Det kanske är relevant att prata om klockcykler per instruktion på en gammal ARM7 och tidigare där pipe:en bestod av 3 steg, fetch, decode, execute/retire.

Titta på denna rapport som bl.a. tar upp bandbredd och latens mot RAM på en Cortex A9.

Hur ska du överhuvudtaget kunna veta hur lång tid ldrex då tiden för minnesaccessen kan variera mellan 30ns (L1$-hit) till 700ns(måste gå mot RAM)? Då denna rapport kommer från 2009 så kan vi anta att de körde på ganska tidiga A9 utvecklingskort, så klockfrekvensen är nog inte mer än runt 500MHz, så detta motsvarar det en varians på 15-350 klockcykler (sida 17). Blandar man in flera CPU-kärnor går latensen upp än mer (sida 18).

Samma sak gäller genomsnittlig bandbredd, den varierar allt från strax under 1.5GB/s till 200-300MB/s för läsning.

Den som slår en här är vilken brutalt usel cache och RAM design en så pass modern CPU ändå har. Hade väntat mig att moderna x86:er skulle har något lägre latens och ungefär 10 gånger bättre bandbredd, men det räcker inte på långa vägar. Atom har ungefär 10 gånger mer bandbredd mot RAM, teoretiskt är den 4.1GB/s och folk får runt hälften i praktiken (2.6GB/s har uppmätts under Linux).

Tittar man i stället på Sandy Bridge så ligger latensen mot RAM mellan 40-60ns och bandbredden mellan 15GB/s till 20GB/s (beroende på kvalité på RAM, detta är dual-channel). Latensen är en faktor 10 bättre, bandbredden är ju mellan 50-100 gånger bättre...

Men andra ord så kör du bara system utan OS och med alla interrupt avslagna, för hur kan du annars veta om det data du läste för ett par instruktioner sedan numer befinner sig i L1$, L2$ eller RAM. Det är en skillnad på över en tiopotens i hur lång till en ld instruktion kommer att ta i praktiken.

Och de som sitter och programmerar i assembler kan inte HELLER göra något åt saken för det finns INGEN CPU-tillverkar som ger dig tillräckligt med information för att du på klockcykelnivå kan räkna ut hur lång tid saker tar. I ett system med flera CPU-kärnor är det omöjligt även om du visste allt detta.

Detta är något jag fått förklara för mig av personer som jobbar med s.k. MILS (Multiple Independent Level of Security) system där variationer i hur lång tid det tar att köra något kan eventuellt vara en läcka av information.

Det finns lägen när det fortfarande kan vara vettigt att skriva assembler, ett sådant exempel är vissa former av checksummor och andra beräkningar där man kan ha stor nytta av att komma åt carry bit, något som C inte möjliggör. För den checksumma som används av UDP och TCP kan man bara summera 16-bitar i stöten i C, men 32 bitar i assembler tack vare carry-biten som effektivt gör att man får 33 bitar och man måste ha minst en bit mer än storleken på det man processar. Att använda 31-bitar i C är möjligt men blir så komplicerat att det går fortare att bara köra med 16. Samma sak gäller 64-bitar, men då är det 32-bitar i C mot 64-bitar assembler.

Andra saker som kan vara vettigt att skriva i assembler är implementationer av vissa primitiver som mutex, semaphorer och spinlocks. Men även detta kan man skriva i t.ex. gcc genom att använda (icke-standard) extensionen som då gör att samma kod fungerar på alla CPU:er som kompilatorn stödjer i stället för att sitta att hacka en version per CPU.

Rent generellt är det totalt slöseri med tid även för de mest prestandakritiska programmen att skriva i assembler idag. Moderna C kompilatorer har väldigt bra informationen om exakt vilka konstruktioner som är snabba, kolla bara på vilka udda ställen gcc tenderar att använda "lea" i stället för det mycket mer logiska "mov" bara för att "lea" automatiskt ger dig sign-extend. Tricks som xor rx,rx klarar de flesta assemblerprogrammera av, men det gör även moderna kompilatorer.

Om inte du jobbar på en microkontroller (något som ÄR populärt på enklare ARM:ar, men knappast på Cortex A9 som du verkar jobba med) som kör med ett ej preemtive-multitaskat OS och med interrupt avslagen så kan du inte säga något om tiden det tar att köra nästa instruktion för du vet inte om
* har det skett ett interrupt sedan förra instruktionen
* har en process med högre prioritet kör sedan förra instruktionen

Har du ett multicore system så är det helt omöjligt att exakt veta hur lång tid nästa instruktion tar då du inte kan veta vad den andra CPU gör och till vilka adresser den skrivit till.

Stänger du av interrupt på x86 och kör den som en microkontroller och antar att det bara är ett single core system så skulle du rent teoretiskt kunna räkna ut exakt hur långt tid varje instruktion tar. Det skulle kräva att du fick ut information EXAKT hur CPUn fungerar, något varken Intel eller AMD skulle ge dig, men det är teoretiskt möjligt.

Jobbar som sagt bara i undantagsfall med ARM så lär inte få åka på något ARM-specifikt konvent, även om det skulle vara intressant. Blir allt mer x86_64 för mig med även en hel del PowerPC och något mindre MIPS. Det företag jag jobbar på arbetar dock med ARM, så har en del ARM experter på kontoret.

GCC har blivit MYCKET bättre på både ARM, PowerPC och MIPS de senaste 5 åren, bl.a. tack vare arbete från Code Sourcery som merga:at tillbaka till "vanliga" gcc. Sedan borde LLVM/Clang vara rätt bra för ARM vid det här laget med tanke på hur viktig den kompilatorn är för Apple.

Men det händer även rätt mycket för x86, kolla in förbättringar för både Bulldozer och Sandy Bridge i gcc 4.7.

Diskussionen började väl med att jag ville ha ett konkret exempel på att x86 har fel som gör att "extrem exemplet köra samma kod två gånger och få olika resultat och det är inget för mig."

Skulle säga att den enda slutsatsen på detta är: det kanske finns sådana fall, men det har inget med ARM kontra x86 att göra utan systemet kan kör på och x86 används normalt sett inte på små och extremt applikationsspecifika produkter.

Tar man Linux, t.ex. i form av Android, som exempel så kan man inte säga exakt hur lång tid något tar att köra vare sig på ARM eller x86. Men x86 har i alla fall fördelen att det finns en övre gräns för allt, något som saknas på de flesta RISC:ar i teorin och möjligen även i praktiken.

Och jag skrev redan i tråden att Intels problem kommer vara att kunna konkurrera prismässigt med ARM om man vill in i telefoner och pekplattor, rent prestandamässigt har ju ARM ännu inte lyckats spöa Atom från 2008 men Intel har under den tiden fått ner strömförbrukningen på sina Atom baserade SoC:er till samma nivåer som Cortex A9 baserade SoC:er. Så tvivlar inte alls på att ert projekt skulle bli dyrare med ett Atom SoC, har däremot väldigt svårt att tro att strömförbrukningen skulle vara ett problem och inte heller GPUn då Intel just nu använder samma GPU-tillverkare som Apple, PowerVR.

De fördelar Intel/AMD har är att x86 är en mer effektiv plattform för multicore + övergången till 64-bitar är avklarad. Möjligen kan ARMv8 (Aarch64) göra ARM till en bättre plattform för multicore, men Aarch64 ligger LÅNGT borta med tanke på att man måste få till kisel (vilket är det lilla problemet) och börja utveckla tool-chains för Aarch64. Intel/AMD har ju 10 års försprång här och vi vet att det tog bra många år innan x86_64 kompilatorerna var lika bra som x86.

Men det är BARA därför att du har andra saker som kör i bakgrunden. Installera t.ex. Linux på ditt ARM-kort och testa samma sak där, du kommer se exakt samma resultat där då Linux är ett preemptive OS.

Eller gör det omvända, kör det exemplet "bare-metal" på x86. Det blir då helt deterministiskt, första anropet kommer kanske ta 200 cykler (beror på hur aggressiv prefetcher är) nästföljande kommer ligga på en konstant tid, 21 cykler är latens mot L2 så det är kanske vad "lock xadd" väntar på då.

Nej, men Atom kommer man som lägst ner till 1.3W för ett helt SoC. Men om ni klarar er på 0.5W så är det inte den högst klockade A9:an och heller inte en speciellt vass GPU, m.a.o även den långsammaste Atom SoC som finns är rejält mycket snabbare än ert system.

ARM gör precis samma sak som Atom, när den är i idle så "power-gate:ar" man CPUn vilket effektiv sätter klockfrekvensen till noll. Cortex A9 och Atom drar endast några enstaka mW när de befinner sig i det läget. Så om det var vad du menade att hela systemet drar 0.5W så borde även den snabbaste versionen av Medfield fixa ert 0.5W krav. Det jag listade är TDP, vilket är mer ett värde på genomsnittlig effekt vid max last.

Det är just detta som gör Haswell så cool, den kan "power-gate:a" enskilda delar av CPUn trots att andra delar i samma fysiska kärna används för fullt. Nog inte allt för djärv gissning att nästa Atom (som kommer H1 2013) kommer ha samma typ av funktion och då är det inte alls omöjligt att Atom kommer dra mindre än samtida ARM:ar med likvärdig prestanda