# 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.

```bash
grep -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.

```mermaid
flowchart 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ů:

```bash
grep -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:

```bash
ps -o min_flt,maj_flt -p $(pgrep -x firefox | head -n1)   # měkké a tvrdé od startu
perf stat -e page-faults,major-faults ./program           # totéž za jeden běh
vmstat 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