Virtualni-pamet-a-strankovani.md

# Virtuální paměť a stránkování Spusť ten samý program dvakrát. Oba procesy přečtou adresu `0x400000` a každý dostane jiná data. Ani jeden o tom neví a ani jeden se nemůže podívat druhému do paměti, i kdyby znal přesnou adresu. V počítači je přitom jedna paměť s jedinou sadou adres. Ani jeden proces nedělá nic zvláštního: jedna instrukce, načtení z adresy, žádné [systémové volání](Systemova-volani). O žádném překladu neví a nemá jak se o něm dozvědět. Tahle stránka vysvětluje, jak procesor a jádro vyrábějí iluzi, že každý proces má počítač sám pro sebe. Neřeší, která stránka poletí ven, když se paměť zaplní - to je na [výměnných algoritmech](Vymenne-algoritmy). Předpokládá [správu paměti](Sprava-pameti) a [režim jádra](Jadro-a-uzivatelsky-rezim), bez kterého by ochrana neměla o co se opřít. ## Adresa, kterou vidí tvůj program, není adresa v paměti Je to index do tabulky, kterou vede jádro a překládá hardware při každém jediném přístupu. Tohle je nejdůležitější věta na celé stránce. Zbytek je jen její rozvedení. Adrese v programu se říká **virtuální**, adrese skutečné paměťové buňky **fyzická**. Mezi nimi stojí jednotka pro správu paměti (MMU) uvnitř procesoru, která překlad provádí sama a bez vědomí programu. Jádro jen dopředu připraví tabulku a řekne, kde leží. Odtud plyne odpověď na otvírák: `0x400000` je v každém procesu jiný index do jiné tabulky. ## Proč se paměť vůbec virtualizuje **Izolace.** Když v tabulce procesu záznam pro cizí paměť není, nedostane se do ní žádnou instrukcí. Není co obcházet, ta paměť pro něj nemá adresu. **Iluze souvislého prostoru.** Program dostane rovný prostor od nuly nahoru, i když je fyzická paměť rozsekaná mezi ostatní procesy. **Můžeš mít v paměti víc, než se do ní vejde.** Stránka, na kterou se dlouho nesáhlo, se odloží na disk a její záznam zneplatní. Až si o ni proces řekne, jádro ji přitáhne zpátky - proces nepozná nic, jen jeden přístup trval stotisíckrát déle. **Sdílení.** Dvě tabulky mohou ukazovat na stejný fyzický rámec. Tím je jedna kopie `libc` v paměti pro všechny naráz a tím je levný `fork`. ## Jak se adresa rozpadá na kusy ### Posun a číslo stránky Překládat po bajtech nejde, tabulka by byla větší než paměť. Překládá se po blocích pevné velikosti, kterým se říká **stránka**; jejich protějšek ve fyzické paměti je **rámec**. Na x86-64 má stránka 4 KiB. Protože 4096 je 2^12, spodních **dvanáct bitů** ukáže na libovolný bajt uvnitř stránky. Těm se říká **posun** a překlad se jich nedotkne. Všechno nad nimi je **číslo stránky** a to je ten index. ```0x4005A3  =  0x400          |  0x5A3             číslo stránky  |  posun             1024           |  1443``` Zkontroluj si to: 1024 × 4096 + 1443 = 4 195 747, což je `0x4005A3`. Když stránka 1024 sedí ve fyzickém rámci číslo 9, výsledná adresa je 9 × 4096 + 1443. **Posun se přenese beze změny, mění se jen horní část.** ### Proč zrovna 4 KiB a kdy 2 MiB Menší stránky znamenají víc záznamů, větší znamenají, že proces potřebující 100 bajtů drží celý blok. Čtyři kilobajty jsou kompromis, který drží od osmdesátých let. Procesor umí i **velké stránky 2 MiB**. Jedna nahradí 512 malých, takže na stejné množství paměti padne jeden překladový záznam místo pěti set dvanácti. Vyplatí se databázím a virtuálním strojům, tedy všemu, co se pohybuje po velkém souvislém bloku. Běžné aplikaci si tím spíš uškodíš - každá skoro prázdná oblast zabere celé dva megabajty. ## Jedna plochá tabulka nepřipadá v úvahu ### Spočítej si, jak velká by byla Virtuální prostor má na x86-64 v praxi 48 bitů. Při stránce 4 KiB je to 2^48 / 2^12 = 2^36 stránek, tedy 68 719 476 736 záznamů po 8 bajtech. Vyjde 2^39 bajtů, tedy **512 GiB tabulky na jeden proces**, na stroji s 16 GB RAM. To není otázka optimalizace, to je nepoužitelné o čtyři řády. ### Čtyři úrovně, devět bitů na patro Řešením je nepopisovat prázdno. Tabulka se rozdělí na strom, ve kterém existují jen větve, které něco mapují - typický proces má obsazené tři malé oblasti, kód, haldu a zásobník, a zbytek stromu není. ``` 47-39  |  38-30  |  29-21  |  20-12  |  11-0 PML4   |  PDPT   |   PD    |   PT    |  posun``` Devět bitů znamená 512 položek po 8 bajtech, dohromady 4096 bajtů: **každá tabulka je přesně jedna stránka**. To není náhoda, to je důvod, proč je patro devítibitové. Adresa `0x4005A3` se rozpadne na PML4[0] → PDPT[0] → PD[2] → PT[0] → rámec, posun 1443. Od jádra 4.14 (rok 2017) umí Linux volitelně **pět úrovní a 57 bitů**; na běžném stroji se to nezapíná, protože to přidá krok každému překladu. Kořen stromu drží procesor v registru `cr3`. Přepnutí procesu je z pohledu paměti jen zápis nové hodnoty do `cr3` - jedna instrukce, po které se ta samá adresa překládá jinam. Kolik to stojí, řeší [přepínání kontextu](Prepinani-kontextu). ### Co je v položce kromě adresy rámce Osm bajtů je na adresu rámce zbytečně moc. Zbytek nesou příznakové bity a ty jsou to zajímavé: | Bit | Význam | Nastavuje ||---|---|---|| P (present) | záznam platí, stránka je v paměti | jádro || R/W | povolen zápis, jinak jen čtení | jádro || U/S | smí na ni uživatelský režim | jádro || A (accessed) | od posledního vynulování se na ni sáhlo | **hardware** || D (dirty) | do stránky se zapsalo | **hardware** || NX | nesmí se z ní vykonávat kód | jádro | **Bity A a D nastavuje procesor sám, jádro je jen čte a nuluje.** Jinak by nemělo šanci zjistit, které stránky se používají - běžné přístupy do paměti přes jádro nejdou. Na těch dvou bitech stojí [výměnné algoritmy](Vymenne-algoritmy): clock se dívá na bit A, aby poznal, co se od minule nepoužilo, a bit D rozhoduje, jestli se stránka musí při odkládání zapsat na disk, nebo se dá zahodit. ## TLB: bez ní by každý přístup stál čtyři další Průchod čtyřmi úrovněmi znamená čtyři čtení z paměti, aby se mohlo provést to páté, o které šlo. Přístup do RAM stojí zhruba 80 ns, takže by se počítač zpomalil pětkrát. Proto má MMU vyrovnávací paměť hotových překladů, **TLB** (Translation Lookaside Buffer). První úroveň má řádově desítky položek, druhá jednotky tisíc. Na 16 GB paměti to zní jako málo, ale úspěšnost je běžně přes 99 %, protože programy se drží pohromadě. Minutí stojí ten průchod tabulkami, tedy desítky nanosekund. **Při přepnutí na jiný proces jsou všechny záznamy v TLB rázem lživé**, protože totéž číslo stránky teď znamená jiný rámec. Historicky se proto při každém zápisu do `cr3` celá vyhodila. Dnes to řeší **PCID** (na ARM se jmenuje ASID): záznam nese identifikátor adresního prostoru, takže záznamy různých procesů v TLB koexistují. Linux ho používá od jádra 4.14, což se vyplatilo hned potom, co KPTI kvůli Meltdownu začalo přepínat tabulky i při vstupu do jádra. ```bashgrep -m1 -o '\bpcid\b' /proc/cpuinfo     # prázdný výstup = procesor PCID neumíperf stat -e dTLB-load-misses ./program  # kolik překladů minulo TLB``` Druhým příkazem si lokalitu ověříš na vlastním programu. Ve virtuálním stroji ti u hardwarových událostí často vrátí `<not supported>`. ## Výpadek stránky krok za krokem Když MMU narazí na položku s nulovým bitem P nebo na přístup porušující práva, vyvolá výjimku (na x86 vektor 14) a předá jádru adresu i důvod; mechanika je u [přerušení a výjimek](Preruseni-a-vyjimky). Jádro ví o adresním prostoru víc než tabulka: tahle oblast je namapovaný soubor, tamta zásobník, který smí růst, a tamhleta není nic. Podle toho se rozhodne mezi třemi možnostmi. ```mermaidflowchart TD    A[Přístup na adresu] --> B{Je překlad v TLB?}    B -->|ano| C[Přístup proběhne]    B -->|ne| D[MMU projde tabulky]    D --> E{Platný záznam a práva sedí?}    E -->|ano| F[Doplní se do TLB]    E -->|ne| G[Výjimka, řízení přebírá jádro]    G --> H{Patří adresa do některé oblasti procesu?}    H -->|ne| I[Neplatný výpadek: SIGSEGV]    H -->|ano| J{Je obsah stránky na disku?}    J -->|ne| K[Měkký výpadek: přidělí se rámec]    J -->|ano| L[Tvrdý výpadek: čeká se na disk]    K --> M[Instrukce se zopakuje]    L --> M``` Poslední krok je na tom to hezké: jádro se nevrací za instrukci, která výpadek způsobila, ale **na ni**. Provede se znovu a tentokrát projde. ### Tři druhy výpadku a co stojí | Druh | Co se stalo | Cena ||---|---|---|| Měkký | stránka je v paměti nebo se přiděluje vynulovaný rámec | jednotky mikrosekund || Tvrdý | obsah se musí načíst z disku nebo ze swapu | zhruba 100 µs z NVMe || Neplatný | proces sáhl tam, kde nic není nebo kam nesmí | SIGSEGV | Rozdíl mezi měkkým a tvrdým je stokrát až stotisíckrát. **Měkkých má normální program statisíce a je to v pořádku** - `malloc` ti dá adresy, ale fyzická paměť se přidělí až při prvním doteku. ## Copy-on-write, čili proč je fork levný i u procesu s 8 GB `fork` nezkopíruje paměť rodiče. Zkopíruje tabulky stránek a v obou kopiích označí **všechny stránky jen pro čtení**, i ty zapisovatelné. Oba procesy ukazují na stejné rámce. Dokud se čte, nikdo nic nepozná. Jakmile jeden zapíše, MMU ohlásí porušení práv, jádro pozná stránku označenou pro **copy-on-write**, teprve teď udělá kopii a zápis povolí. Proto stojí `fork` u procesu s 8 GB řádově tolik co u procesu s osmi megabajty; podrobnosti jsou u [procesů](Procesy). Zrádné to je, když potomek žije dlouho a hodně zapisuje - paměť se rozpadá na kopie postupně a nikde to nevypadá jako jedna velká alokace. ### Dirty COW, 2016 V říjnu 2016 se ukázalo, že obsluha copy-on-write v Linuxu obsahuje souběh (CVE-2016-5195). Útočník s právem jen ke čtení dokázal střídáním zápisu a zahození mapování trefit okno mezi kontrolou práv a zápisem, takže se změna zapsala do původního souboru místo do soukromé kopie. Znamenalo to zápis do `/etc/passwd` nebo do setuid binárky pro kohokoliv, kdo měl na stroji shell. Zranitelné bylo prakticky všechno včetně Androidu a chyba byla v jádře **devět let**. **Poučení: souběh v kódu, který proběhne miliardkrát denně a ve všech normálních případech dopadne správně, zůstane neviditelný libovolně dlouho.** ## Sdílené stránky a proč je RSS zavádějící Sdílená knihovna je v paměti **jednou**. Padesát procesů s `libc` má padesát záznamů ukazujících na tytéž rámce. Totéž platí pro `mmap` souboru: namapované stránky jsou přímo stránky [page cache](Vstup-a-vystup), takže kdo ten soubor zároveň čte přes `read`, čte z těch samých rámců. Odtud plyne, proč je RSS zavádějící: **počítá každou rezidentní stránku celou, i když ji proces sdílí s padesáti dalšími.** Sečti RSS všech procesů a klidně ti vyjde víc, než má stroj paměti. Poctivější je PSS, kde se sdílená stránka dělí počtem držitelů: ```bashgrep -E '^(Rss|Pss):' /proc/$(pgrep -x nginx | head -n1)/smaps_rollup``` ## Ochrana, kterou stránkování umožnilo | Prostředek | Co dělá | Jak se podívat ||---|---|---|| NX | zakáže vykonání kódu ze zásobníku a haldy | `grep -m1 -o '\bnx\b' /proc/cpuinfo` || ASLR | posune zásobník, haldu, knihovny i binárku | `cat /proc/sys/kernel/randomize_va_space` || Stránky stráže | nemapovaná mezera pod zásobníkem | `cat /proc/self/maps` | **NX vznikl jako přímá reakce na přetečení zásobníku.** Do devadesátých let se do zásobníku daly nasypat instrukce a skočit na ně, protože paměť neměla oddělené právo pro spuštění. AMD ho přidalo v roce 2003 s architekturou AMD64, Intel ho jmenuje XD. U ASLR chceš vidět `2`, plnou randomizaci; je to výchozí hodnota a měnit ji má smysl jedině při ladění. ## Co se dnes už nedělá **Segmentace jako rovnocenná volba.** Návody pořád staví „segmentaci a stránkování" vedle sebe jako dvě možnosti, mezi kterými se vybírá. Na x86-64 v 64bitovém režimu je segmentace prakticky vypnutá: báze je nulová a zbylo jen `fs` a `gs` pro lokální úložiště vlákna. **Vybírat není z čeho, vyhrálo stránkování.** ## Diagnostika Nejužitečnější věc na téhle stránce je rozdíl mezi měkkými a tvrdými výpadky u konkrétního procesu: ```bashps -o min_flt,maj_flt -p $(pgrep -x firefox | head -n1)   # měkké a tvrdé od startuperf stat -e page-faults,major-faults ./program           # totéž za jeden běhvmstat 1                                                  # sloupce si a so``` Ve `vmstat` je `si` počet kilobajtů za vteřinu čtených ze swapu a `so` zapisovaných do něj; nenulové `si` po delší dobu znamená, že se pracovní množina do paměti nevejde. `/proc/PID/pagemap` řekne o konkrétní stránce, jestli je rezidentní a ve kterém rámci sedí, jen se to čte binárně a chce práva roota. Zbytek nástrojů je u [diagnostiky](Nastroje-a-diagnostika). | Příznak | Kde je problém ||---|---|| `maj_flt` roste za běhu | pracovní množina se nevejde do RAM || Po startu pomalý, pak zrychlí | normální, stránky se dotahují při prvním doteku || SIGSEGV | přístup bez platného mapování nebo zápis do jen pro čtení || Paměť roste po `fork` | rozpadá se copy-on-write, potomek zapisuje || Součet RSS větší než RAM | sdílené stránky, koukej na PSS | ## Co si odnést **Adresa v programu je index do tabulky, ne místo v paměti.** Překlad dělá hardware při každém přístupu. **Plochá tabulka by měla 512 GiB, proto jsou čtyři úrovně po devíti bitech.** Popisuje se jen to, co se opravdu mapuje. **Bity accessed a dirty nastavuje procesor.** Bez nich by výměnné algoritmy neměly z čeho vycházet. **TLB dělá z pěti přístupů jeden.** Úspěšnost přes 99 % není štěstí, je to lokalita. **Měkký výpadek stojí mikrosekundu, tvrdý stovku.** Statisíce měkkých jsou normální, desítky tvrdých za vteřinu ne. **`fork` kopíruje tabulky, ne paměť.** Kopie stránky vznikne až při prvním zápisu do ní. **RSS je nafouknuté o všechno sdílené.** Skutečnou spotřebu ti řekne PSS. ## Kam dál - **[Výměnné algoritmy](Vymenne-algoritmy)** - která stránka poletí ven, když se paměť zaplní, a co je thrashing- **[Správa paměti](Sprava-pameti)** - adresní prostor procesu a odkud se berou stránky- **[Přepínání kontextu](Prepinani-kontextu)** - co stojí zápis do `cr3` a studená TLB po něm- **[Vstup a výstup](Vstup-a-vystup)** - page cache, se kterou `mmap` sdílí stránky- **[Virtualizace a kontejnery](Virtualizace-a-kontejnery)** - co se stane, když se stránkuje dvakrát pod sebou