0xDEADBEEF

RSS
««« »»»

Meltdown, Spectre a branch prediction

31. 1. 2018

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 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í:

píše k47 (@kaja47, k47)