Skip to content

Virtualni pamet a strankovani

Jump to bottom
Martin Skalicky edited this page Aug 7, 2026 · 1 revision

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í. 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. Předpokládá správu paměti a režim jádra, 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.

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

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.

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.

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
Loading

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ů. 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, 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ů:

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:

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.

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

Našel jsi chybu nebo něco chybí? Založ issue nebo pošli pull request.

Úvod

Základy

Procesy

Souběh

Paměť

Soubory a zařízení

Systém v provozu

Praxe

Clone this wiki locally