c - Hurtige fibre/coroutines under x64 Windows

Indlæg af Hanne Mølgaard Plasc

Problem



Så jeg har denne Coroutine API, udvidet af mig, baseret på kode jeg fandt her: https://the8bitpimp.wordpress.com/2014/10/21/coroutines-x64-and-visual-studio/[154]


struct mcontext {
  U64 regs[8];
  U64 stack\_pointer;
  U64 return\_address;
  U64 coroutine\_return\_address;
};

struct costate {
   struct mcontext callee;
   struct mcontext caller;
   U32 state;
};

void coprepare(struct costate **token,
       void *stack, U64 stack\_size, cofunc\_t func); /* C code */
void coenter(struct costate *token, void *arg);     /* ASM code */
void coyield(struct costate *token);                /* ASM code */
int  coresume(struct costate *token);               /* ASM code, new */


Jeg er fast ved at implementere coyield (). Coyield () kan skrives i C, men det er samlingen, som jeg har problemer med. Her er hvad jeg har hidtil (MASM/VC ++ syntax).


;;; function: void \_yield(struct mcontext *callee, struct mcontext *caller)
;;; arg0(RCX): callee token
;;; arg2(RDX): caller token
\_yield proc
    lea RBP, [RCX + 64 * 8]
    mov [RCX +  0], R15
    mov [RCX +  8], R14
    mov [RCX + 16], R13
    mov [RCX + 24], R12
    mov [RCX + 32], RSI
    mov [RCX + 40], RDI
    mov [RCX + 48], RBP
    mov [RCX + 56], RBX

    mov R11, RSP
    mov RSP, [RDX + 64]
    mov [RDX + 64], R11

    mov R15, [RDX + 0]
    mov R14, [RDX + 8]
    mov R13, [RDX + 16]
    mov R12, [RDX + 24]
    mov RSI, [RDX + 32]
    mov RDI, [RDX + 40]
    mov RBP, [RDX + 48]    
        mov RBX, [RDX + 56]

    ret
\_yield endp


Dette er en straight forward-tilpasning af 8bitpimp's kode. Hvad det ikke gør, hvis jeg forstår denne kode korrekt, sættes mcontext-> return\_address og mcontext-> coroutine\_return\_address på stakken, der skal vælges af ret. Er det også hurtigt? IIRC, forårsager det en fejlparametre på tilbagesendelsespræventoren, der findes i moderne x64-stykker.

Bedste reference


Disse svar omhandler kun 'er det hurtigt' en del af spørgsmålet.


Returadresseforudsigelse



For det første en kort beskrivelse af opførelsen af ​​en typisk returadresse-prediktor.



  • Hver gang en call er lavet, gemmes returadressen, der skubbes på den faktiske stak, også inde i en CPU-struktur kaldet returadressepufferen eller noget lignende.

  • Når en ret (retur) er foretaget, antager CPU'en, at destinationen vil være adressen for øjeblikket øverst på returadressepufferen, og den indtastning fra returadressebufferen er 'poppet'.



Effekten er at perfekt forudsige call/ret par, så længe de forekommer i deres sædvanlige korrekt indlejrede mønster, og at ret faktisk fjerner de umodificerede returadresse skubbet af call i hvert tilfælde. For flere detaljer kan du starte her. [155]


Normalfunktion opkald i C eller C ++ (eller stort set alle andre sprog) vil normalt altid følge dette korrekt indlejrede mønster 2 . Så du behøver ikke at gøre noget særligt for at drage fordel af afkast forudsigelsen.


Fejlfinding



I tilfælde, hvor call/ret ikke parreres normalt, kan forudsigelserne mislykkes i (i det mindste) et par forskellige måder:



  • Hvis stakpekeren eller returværdien på stakken manipuleres, så at en ret ikke vender tilbage til det sted, hvor den tilsvarende call skubbes, får du et affaldsforudsigelsesfejl for at ret, men efterfølgende normalt indlejrede ret instruktioner vil fortsætte med at forudsige korrekt, så længe de er nestede korrekt. Hvis du f.eks. Tilføjer et par byte til værdien ved [rsp] for at springe over instruktionen efter call i opkaldsfunktionen, vil den næste ret misforstå, men ret, der følger inde i opkaldsfunktionen, skal være fint.

  • På den anden side er funktionerne call og ret ikke nestede, kan hele retursprediktionsbufferen blive fejljusteret, hvilket forårsager fremtidige ret instruktioner, hvis nogen, der bruger De eksisterende værdier for at mispredicere 2.5 . Hvis du f.eks. call indgår i en funktion, men derefter bruger jmp til at vende tilbage til den, der ringer op, er der en mismatched call]] uden ret. ret inde i opkalderen vil misprediktere, og det vil også ret inde i opkalderen af ​​opkalderen og så videre, indtil alle ukorrekte værdier bliver brugt op eller overskrevet 3 . En lignende sag ville forekomme, hvis du havde en ret ikke matchet med et tilsvarende opkald (og denne sag er vigtig for den efterfølgende analyse).



I stedet for de to ovenstående regler kan du også simpelthen bestemme returspecifikorens opførsel ved at spore gennem koden og spore, hvad returstakken ligner på hvert punkt. Hver gang du har en ret instruktion, skal du se om den vender tilbage til den aktuelle top af returstakken - hvis ikke, får du en misforståelse.


Misforståelsesomkostninger



De faktiske omkostninger ved en misprediktion afhænger af den omgivende kode. En figur på ~ 20 cykler er almindeligvis givet og ses ofte i praksis, men de faktiske omkostninger kan være lavere: f.eks. Så lavt som nul, hvis CPU'en er i stand til at løse fejlpredningen tidligt og og begynde at hente langs den nye vej uden at afbryde den kritiske vej eller højere: Hvis forgreningsprediktionsfejlene tager lang tid at løse og reducere den effektive parallelisme af langtidsaktionsoperationer. Uanset om vi kan sige, at straffen normalt er signifikant , når den opstår i en operation, den anden kun tager en håndfuld instrukser.


Hurtigkoroutiner



Eksisterende adfærd for Coresume og Coyield



Den eksisterende \_yield -funktion (kontekstomskifter) bytter stakpekeren rsp og bruger derefter ret til at returnere til en anden placering end den, der faktisk ringede op (især vender den tilbage til stedet blev skubbet på caller stakken, når opkalderen kaldte yield tidligere). Dette vil generelt medføre en misprediktion på ret inde i \_yield.


For eksempel overveje det tilfælde, hvor en funktion A0 gør et normalt funktionsopkald til A1, hvilket det bliver kaldt coresume 4 for at genoptage en coroutine B1, som senere kalder coyield for at give tilbage til A1. Inden for opkaldet til coresume ser returstakken ud A0, A1, men så coresume bytter rsp for at pege på stakken til B1 og den største værdi af den stak er en adresse indenfor B1 umiddelbart efter coyield i koden for B1. ret inde i coresume springer derfor til et punkt i B1 og ikke til et punkt i A1 som returstakken forventer. Derfor får du en forkert forudsigelse på det ret og returstakken ligner A0.


Overvej nu hvad der sker, når B1 kalder coyield, som implementeres i stort set samme måde coresume: opkaldet til coyield skubber B1 på returstakken ser nu ud som A0, B1 og bytter derefter stakken for at pege på A1 stakken og gør derefter ret, som vender tilbage til A1. Så vil ret misforståelsen ske på samme måde, og stakken er tilbage som A0.


Så den dårlige nyhed er, at en stram række opkald til coresume og coyield (som det er typisk med en udbyttebaseret iterator, for eksempel), vil misforstå hver gang. Den gode nyhed er, at nu i A1 er returstakken korrekt (ikke forkert) - hvis A1 vender tilbage til sin opkalder A0, er returen korrekt forudsagt (og så videre, når A0 vender tilbage til sin ringer, osv.). Så du lider en misforstået straf hver gang, men i det mindste afviger du ikke returstakken i dette scenario. Den relative betydning af dette afhænger af hvor ofte du ringer coresume/coyield i forhold til kaldfunktioner normalt under den funktion, der ringer coresume.


Gør det hurtigt



Så kan vi løse misforståelsen? Desværre er det vanskeligt at kombinere C og eksterne ASM opkald, fordi opkaldet til coresume eller coyield indebærer et opkald indsat af kompilatoren, og det ' Det er svært at slappe af i asm.


Lad os dog prøve.


Brug indirekte opkald



En tilgang er at få brug for ret overhovedet og brug kun indirekte hopp.


Det er bare at erstatte ret i slutningen af ​​dine coresume og coyield opkald med:


pop r11
jmp r11


Dette er funktionelt ækvivalent med ret, men påvirker returstablerpufferen forskelligt (især påvirker den ikke det).


Hvis du analyserer den gentagne rækkefølge af coresume og coyield opkald som ovenfor, får vi det resultat, at returstablerpufferen bare begynder at vokse på ubestemt tid som A0, A1, B1, A1, B1, .... Dette skyldes, at vi i virkeligheden ikke bruger ret i denne implementering. Så vi lider ikke tilbage på misforståelser, fordi vi ikke bruger ret! I stedet stoler vi på nøjagtigheden af ​​den indirekte grenforudsigter at forudsige jmp11.


Hvordan denne forudsigelse virker afhænger af, hvordan coresume og coyeild implementeres. Hvis de begge kalder en fælles \_yield funktion, der ikke er indlejret, er der kun en enkelt jmp r11 placering, og denne jmp vil alternativt gå til en placering i A1 og B1. De fleste moderne indirekte forudsigelser repræsenterer dette simple gentagelsesmønster fint, selvom ældre, der kun spores et enkelt sted, ikke vil. Hvis \_yield blev indsnævret til coresume og coyield eller dig kopieres kun koden i hver funktion, der er to forskellige jmp r11 opkaldswebsteder, som kun ser en enkelt placering hver og bør forudsiges af enhver CPU med en indirekte grenforudsigter 6 .


Så dette bør generelt forudsige en række stramme coyield og coresume opkald godt 7 , men på bekostning af at udslette returbufferen, så når A1 beslutter at vende tilbage til A0 dette vil blive forvansket samt efterfølgende afkast af A0 og så videre. Størrelsen af ​​denne straf er begrænset af størrelsen af ​​returstablerbufferen, så hvis du laver mange stramme coresume/yield opkald kan det være en god afgang.


Det er det bedste, jeg kan tænke på inden for rammerne af eksterne opkald til funktioner skrevet i ASM, fordi du allerede har en underforstået call til dine co rutiner, og du skal gøre hoppet til anden couroutine indefra, og jeg kan ikke se hvordan man holder stablerne afbalanceret og vender tilbage til det rigtige sted med disse begrænsninger.


Inlined Code på Opkaldsstedet



Hvis du kan indkode kode på opkaldsstedet for dine couroutine metoder (fx med compiler support eller inline asm), så kan du måske gøre det bedre.


Opkaldet til coresume kunne indlejres som noget som dette (jeg har udeladt registret, der gemmer og gendanner kode fordi det er ligefrem):


; rcx - current context
; rdc - context for coroutine we are about to resume

; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [rsp - 8]
mov [rcx + 64], r11 ; save current stack pointer
mov r11, [rdx + 64] ; load dest stack pointer
call [r11]


Bemærk at coresume gør det rent faktisk ikke stakken bytte - det lægger bare destinationsstakken i r11 og gør derefter en call mod [r11] for at hoppe til coroutinen. er nødvendigt, så det call korrekt skubber placering, vi skal vende tilbage til på opkalderens stak.


Så ville coyield se noget ud (indlejret i kaldningsfunktionen):


; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [after\_ret]
push r11             ; save the return point on the stack
mov  rsp, [rdx + 64] ; load the destination stack
ret
after\_ret:
mov rsp, r11


Når et coresume opkald hopper til coroutinen ender den til after\_ret, og før brugerkoden udføres, skifter instruktionen mov rsp, r11 til den korrekte stak til coroutinen, der er stanset i r11 af coresume.


Så væsentligt coyield har to dele: den øverste halvdel udføres før udbyttet (som forekommer ved ret opkaldet og den nederste halvdel, der fuldender arbejdet startet af coresume. Dette giver dig mulighed for at bruge call som mekanisme til at gøre coresume hoppet og ret for at gøre coyield jump. call/ret er afbalanceret i denne sag.


Jeg har forklaret nogle detaljer om denne tilgang: For eksempel, da der ikke er nogen funktionsopkald involveret, er de ABI-specificerede ikke-flygtige registre ikke særlig specielle: i tilfælde af inline-samling skal du angive kompilator hvilke variabler du vil clobber og gemme resten, men du kan vælge, hvad der er praktisk for dig. Ved at vælge et større sæt af klumpede variabler gør coresume/coyield kodesekvenserne selv kortere, men potentielt sætter mere registertryk på den omgivende kode og kan tvinge kompilatoren til at spildere mere omkring dig kode. Måske er idealet bare at erklære alt clobbered og derefter kompilatoren vil bare spildes, hvad den har brug for.





1 Der er selvfølgelig begrænsninger i praksis: størrelsen af ​​returstablerbufferen er sandsynligvis begrænset til et lille antal (f.eks. 16 eller 24), så når dybden af ​​opkaldsstakken overstiger det, nogle Returadresser går tabt og bliver ikke forudsagt korrekt. Også forskellige begivenheder som en kontekstomskifter eller afbrydelser vil sandsynligvis ødelægge returstablerne.


2 En interessant undtagelse var et almindeligt mønster for at læse den nuværende instruktionspeger i x86 (32-bit) kode: der er ingen instruktion til at gøre dette direkte, så i stedet kan en call next; next: pop rax sekvens være brugt: a call til den næste instruktion, der kun tjener push adressen på stakken, som er slukket. Der er ingen tilsvarende ret. Nuværende CPU'er genkender faktisk dette mønster, men det er ikke ubalanceret returadresseprognosen i dette specielle tilfælde.


2.5 Hvor mange misforståelser dette indebærer afhænger af, hvordan net returnerer opkaldsfunktionen gør: hvis den straks begynder at kalde en anden dyb kæde af opkald, kan de misalignerede returstabler ikke bruges til alle, for eksempel.


3 Eller måske, indtil returadressestakken er re-aligneret af en ret uden et tilsvarende opkald, gør en sag med 'to fejl' ret '.


4 Du har ikke vist, hvordan coyield og coresume faktisk kalder \_yield, så for resten af ​​spørgsmålet vil jeg antage, at de implementeres i det væsentlige som \_yield er direkte inden for coyield eller coresume uden at kalde \_yield: dvs. kopiere og indsæt \_yield koden i hver funktion, mulig med nogle små redigeringer at redegøre for forskellen. Du kan også gøre dette arbejde ved at kalde \_yield, men så har du et ekstra lag af opkald og rets, der komplicerer analysen.


5 I det omfang disse udtryk også giver mening i en symmetrisk couroutine implementering, da der faktisk ikke er nogen absolut forestilling om opkalder og callee i så fald.


6 Selvfølgelig gælder denne analyse kun for det simple tilfælde, at du har et enkelt coresume opkald, der ringer til en coroutine med et enkelt coyield opkald. Mere komplekse scenarier er mulige, såsom flere coyield opkald i kalleen eller flere coresume opkald inden for opkalderen (muligvis til forskellige couroutines). Imidlertid gælder det samme mønster: sagen med split jmp r11 sites vil præsentere en enklere damp end den kombinerede sag (muligvis på bekostning af flere iBTB ressourcer).


7 En undtagelse ville være det første opkald eller to: ret forudsigeren behøver ingen 'warmup', men den indirekte grenforudsigelse kan, især når en anden coroutin er blevet kaldt i mellemtiden.