Meltdown, Spectre a branch prediction
Na Poslední Sobotě, kde jsem mluvil o Meltdown a Spectre (slajdy zde), jsem dostal dotaz jak jsou implementovány branch predictory. Něco jsem odpověděl, ale z trhanců vzpomínek mi nepřipadá, že šlo o uspokojivou odpověď. Proto jsem se rozhodl o tom něco málo napsat a hlavně poskytnout odkazy na autoritativní zdroje.
O branch prediction (BP) jsem se zmiňoval na funkcionálně.cz tady a trochu i tady. Šlo ale jenom o dopady BP na výkon, ne detaily nebo principy implementace. O tom se něco dá vyčíst z článku na wikipedii. Mnohem lepší úvod však poskytuje Dan Luu na svém blogu. Pokud vás toto téma zajímá, rozhodně si jeho článek přečtěte. (Už jsem ho tu vychvaloval)
Zajímavý ja také paper The YAGS Branch Prediction Scheme, který prezentuje, jak může vypadat o něco sofistikovanější, ale přesto klasická implementace.
Branch predictor nemusí být implementován jen pomocí tabulek historie skoků, ale i neuronovými sítěmi. Tím se AMD chlubili při ohlášení své mikroarchitektury Zen. Ale co tím vlastně myslí je otázka, na kterou nikdo nezná přesněou odpověď. Nejspíš nejde o nijak komplikované neuronosítě, ale o perceptrony, jak je popsáno v Dynamic Branch Prediction with Perceptrons. Predikce musí být rychlá, ideálně dostupná v jednom taktu, navíc je vždy tlak na to, aby extra hardware zabíral co nejméně místa čipu a konzumoval co nejméně energie.
x86 procesory mají několik nezávislých mechanismů pro predikci skoků. Jednak je
již zmíněný to branch predictor, který odhaduje, zdaji bude skok proveden
nebo ne a dále jsou to mechanismy odhadující, kam povede nepřímý skok.
Jde jednak o branch target buffer (BTB) pro obecné skoky a pak return
stack buffer (RSB) pro predikci cílů ret
instrukcí. Protože ret
se
typicky vrátí na místo call
instrukce, je RSB implementován jako jednoduchý
zásobník. call
na vrchol zásobníku vrazí svojí adresu a ret
ji vyjme.
Toho je možné využít pro retpoline chránící před druhou variantou útoku Spectre. Nepřímý skok, který by se zkompiloval jako prosté
jmp *%r11
se správnými přepínači GCC/LLVM namísto toho zkompiluje jako
call set_up_target; capture_spec: // nekonečná smyčka slouží jako trampolína, kde uvázne spekulativní exekuce pause; jmp capture_spec; set_up_target: mov %r11, (%rsp); // tady se přepíše návratová adresa na zásobníku ret; // ret se vrátí na přepsanou adresu
Dojde náhradu za pár korespondujících call
/ret
instrukcí a na zásobníku se
přepíše návratová adresa. To znemožní, aby byl spekulativně vykonán neznámý
kód. Predikce ret
použije adresu z RSB, která povede do nekonečné smyčky, a procesor poté, co odhalí, že jde o chybu, skočí nespekulativně na správnou
adresu. Má to dopady na výkon, protože kód běží, jako kdyby byly spekulace a predikce zakázány.
Relevantní čtení:
- Branch Prediction and the Performance of Interpreters – Don't Trust Folklore – branch prediction je natolik efektivní, že správně odhaduje závislé skoky v interpretech.
- Čím více se věci mění, tím více zůstávají stejné
- KPTI/KAISER Meltdown Initial Performance Regressions