0xDEADBEEF

[RSS]
««« »»»

Meltdown, Spectre a branch prediction

31. 1. 2018

Na Po­slední Sobotě, kde jsem mluvil o Mel­t­down a Spectre (slajdy zde), jsem dostal dotaz jak jsou im­ple­men­to­vány branch pre­dic­tory. Něco jsem od­po­vě­děl, ale z tr­hanců vzpo­mí­nek mi ne­při­padá, že šlo o uspo­ko­ji­vou od­po­věď. Proto jsem se roz­hodl o tom něco málo napsat a hlavně po­skyt­nout odkazy na au­to­ri­ta­tivní zdroje.

O branch pre­diction (BP) jsem se zmi­ňo­val na funk­ci­o­nálně.cz tady a trochu i tady. Šlo ale jenom o dopady BP na výkon, ne de­taily nebo prin­cipy im­ple­men­tace. O tom se něco dá vyčíst z článku na wi­ki­pe­dii. Mnohem lepší úvod však po­sky­tuje Dan Luu na svém blogu. Pokud vás toto téma zajímá, roz­hodně si jeho článek pře­čtěte. (Už jsem ho tu vy­chva­lo­val)

Za­jí­mavý ja také paper The YAGS Branch Pre­diction Scheme, který pre­zen­tuje, jak může vy­pa­dat o něco so­fis­ti­ko­va­nější, ale přesto kla­sická im­ple­men­tace.

Branch pre­dic­tor nemusí být im­ple­men­to­ván jen pomocí ta­bu­lek his­to­rie skoků, ale i neu­ro­no­vými sítěmi. Tím se AMD chlu­bili při ohlá­šení své mik­ro­ar­chi­tek­tury Zen. Ale co tím vlastně myslí je otázka, na kterou nikdo nezná přes­něou od­po­věď. Nej­spíš nejde o nijak kom­pli­ko­vané neu­ro­no­sítě, ale o per­ceptrony, jak je po­psáno v Dy­na­mic Branch Pre­diction with Per­ceptrons. Pre­dikce musí být rychlá, ide­álně do­stupná v jednom taktu, navíc je vždy tlak na to, aby extra hard­ware za­bí­ral co nejméně místa čipu a kon­zu­mo­val co nejméně ener­gie.

x86 pro­ce­sory mají ně­ko­lik ne­zá­vis­lých me­cha­nismů pro pre­dikci skoků. Jednak je již zmí­něný to branch pre­dic­tor, který od­ha­duje, zdaji bude skok pro­ve­den nebo ne a dále jsou to me­cha­nismy od­ha­du­jící, kam povede ne­přímý skok. Jde jednak o branch target buffer (BTB) pro obecné skoky a pak return stack buffer (RSB) pro pre­dikci cílů ret in­strukcí. Pro­tože ret se ty­picky vrátí na místo call in­strukce, je RSB im­ple­men­to­ván jako jed­no­du­chý zá­sob­ník. call na vrchol zá­sob­níku vrazí svojí adresu a ret ji vyjme.

Toho je možné využít pro ret­po­line chrá­nící před druhou va­ri­an­tou útoku Spectre. Ne­přímý skok, který by se zkom­pi­lo­val jako prosté

jmp *%r11

se se správ­nými pře­pí­nači GCC/LLVM na­místo toho zkom­pi­luje 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 ko­re­spon­du­jí­cích call/ret in­strukcí a na zá­sob­níku se pře­píše ná­vra­tová adresa. To zne­možní, aby byl spe­ku­la­tivně vy­ko­nán ne­známý kód. Pre­dikce ret po­u­žije adresu z RSB, která povede do ne­ko­nečné smyčky, a pro­ce­sor poté, co odhalí, že jde o chybu, skočí ne­spe­ku­la­tivně na správ­nou adresu. Má to dopady na výkon, pro­tože kód běží, jako kdyby byly spe­ku­lace a pre­dikce za­ká­zány.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)