# Správa paměti a adresní prostor procesu

Pustíš `free -h` na stroji s 16 GB paměti a ve sloupci `free` uvidíš 400 MB. První reakce bývá hledat, co paměť žere.

Není co. **Volná paměť je z pohledu operačního systému promarněná paměť.** Co zrovna nikdo nepotřebuje, si jádro zaplní vyrovnávací pamětí disku (`buff/cache`, blíž u [vstupu a výstupu](Vstup-a-vystup)) a zahodí ji v okamžiku, kdy si o ni někdo řekne. Sloupec, na který se máš dívat, se jmenuje `available`, ne `free`.

Tahle stránka je o rozvržení adresního prostoru a o tom, jak se paměť přiděluje: halda, zásobník, co dělá `malloc` a jak číst čísla z `ps`. Překlad adres - tabulky stránek, TLB, výpadek stránky - je na [virtuální paměti a stránkování](Virtualni-pamet-a-strankovani) a tady se neopakuje. Předpokládá to [proces](Procesy) a [systémová volání](Systemova-volani).

## Adresní prostor není paměť, je to seznam slibů

Tohle je nejdůležitější věta na celé stránce: **adresní prostor procesu není paměť. Je to seznam slibů.**

Proces vidí souvislý prostor od nuly nahoru. Fyzická paměť za ním je roztroušená po stránkách 4 KiB kdekoli v RAM a velký kus těch slibů nemá za sebou nic, dokud na něj proces nesáhne.

Dva procesy proto můžou mít na adrese `0x400000` každý něco jiného, proces může mít „dva gigabajty paměti“ a zabírat čtyřicet megabajtů a `malloc`, který uspěl, nedokazuje vůbec nic.

## Mapa adresního prostoru odshora dolů

Uživatelská část je na x86-64 spodních 128 TiB, od `0xffff800000000000` nahoru je prostor jádra. Tam se z uživatelského režimu nedostaneš, o to se stará [ochrana režimů](Jadro-a-uzivatelsky-rezim).

| Oblast | Co v ní je | Chování |
|---|---|---|
| kód (text) | instrukce programu | čtení a spuštění |
| data | inicializované globální proměnné | čtení i zápis |
| BSS | proměnné vynulované na startu | v souboru jen číslo |
| halda | to, co vrací `malloc` | roste nahoru |
| mapované oblasti | knihovny, soubory, velké alokace | mezi haldou a zásobníkem |
| zásobník | lokální proměnné, návratové adresy | roste dolů |
| prostor jádra | data a tabulky jádra | nepřístupný |

Všimni si BSS: pole miliónu vynulovaných čísel zabere v souboru pár bajtů popisu, protože nuly vyrobí jádro až při dotyku.

### Přečti si `/proc/self/maps` nahlas

Nejužitečnější příkaz na téhle stránce vypíše mapu procesu, který ho právě vykonává:

```bash
cat /proc/self/maps        # mapa toho běžícího `cat`, ne shellu
```

```
57538aa88000-57538aa8d000 r-xp 00002000 103:02 2230078   /usr/bin/cat
57538aa90000-57538aa91000 rw-p 00009000 103:02 2230078   /usr/bin/cat
5753ab67d000-5753ab69e000 rw-p 00000000 00:00 0          [heap]
7fc8c1c28000-7fc8c1db0000 r-xp 00028000 103:02 2269286   /usr/lib/x86_64-linux-gnu/libc.so.6
7fc8c1ef2000-7fc8c1ef4000 r-xp 00000000 00:00 0          [vdso]
7ffe91c3c000-7ffe91c5d000 rw-p 00000000 00:00 0          [stack]
```

První sloupec je rozsah adres, druhý práva. **`r-xp` je čtení a spuštění bez zápisu** - kód. Že do něj nejde psát, je jediné, co brání přepsání instrukcí za běhu. **`rw-p` je čtení a zápis bez spuštění** - data. Písmeno `p` znamená soukromé mapování, tedy kopii při zápisu, `s` sdílené.

`[heap]` posouvá `brk` a má tu 132 KiB. `[stack]` je zásobník hlavního vlákna, taky 132 KiB, přestože strop je 8 MiB - roste podle potřeby. `[vdso]` jsou dvě stránky namapované jádrem, aby se `gettimeofday` obešlo bez [systémového volání](Systemova-volani).

## Co se dělalo dřív a proč to v učebnicích zůstalo

Před stránkováním dostal proces jeden souvislý kus fyzické paměti a dvojici registrů, bázi a limit. Jádro si drželo seznam volných děr a jednu z nich na každou žádost vybralo: **první vhodná** je první, do které se to vejde, **nejlepší vhodná** je nejtěsnější z celého seznamu, **nejhorší vhodná** naopak největší.

Vyhrála první vhodná. Nejlepší vhodná zní rozumně, ale za cenu průchodu seznamem zanechává drobty, do kterých se už nic nevejde.

Zůstaly dva druhy plýtvání, které se pletou dodnes. **Vnější fragmentace** znamená, že volné paměti je dost, ale ne v jednom kuse. **Vnitřní fragmentace** znamená, že přidělený blok je větší než žádost, protože se zaokrouhlilo nahoru.

Segmentace rozdělila proces na logické celky s vlastní bází a limitem, čímž vnitřní fragmentaci odstranila a vnější ne. **Na x86-64 prakticky zmizela:** `cs`, `ds`, `es` a `ss` mají bázi natvrdo nulovou a použitelnou si nechaly jen `fs` a `gs`, které slouží lokálním datům [vlákna](Vlakna). Píše se o ní dál proto, že terminologii po ní zdědilo stránkování.

## Jak se paměť doopravdy získá

Systémová volání jsou dvě. `brk` a `sbrk` posunou horní hranici haldy, `mmap` vytvoří novou oblast kdekoli v prostoru.

`malloc` mezi nimi není. Je to funkce knihovny, která si vezme paměť po velkých kusech a pak z nich rozdává. Jinak by nešlo obsloužit `malloc(24)`: jádro umí vydat jen celé stránky po 4 KiB a jedno volání stojí zhruba 50-100 ns.

**Od zhruba 128 KiB glibc přepne z haldy na `mmap`.** Ta hranice je pohyblivá a při uvolňování takových bloků roste až ke 32 MiB. Program s alokacemi po 100 KiB se proto chová jinak než s alokacemi po 200 KiB.

```bash
strace -e trace=brk,mmap,munmap ./program 2>&1 | head -20   # kolikrát se šlo do jádra
```

### Proč `free` paměť nevrátí systému

`free` vrátí blok do seznamu volných bloků alokátoru, ne jádru. Halda se zkracuje jen shora a jen když je souvislý volný konec větší než 128 KiB, takže jediný živý blok nahoře drží celý zbytek pod sebou. Bloky z `mmap` se naopak vracejí okamžitě.

Je to záměr: program, který v cyklu alokuje a uvolňuje, by jinak trávil čas v jádře místo v práci.

### Anonymní a souborové mapování

`mmap` s příznakem `MAP_ANONYMOUS` vyrobí oblast, za kterou není nic a jejíž stránky vzniknou vynulované při prvním dotyku. To je paměť v běžném smyslu slova.

Bez toho příznaku mapuje soubor a čtení z oblasti je čtením souboru bez `read`. S `MAP_SHARED` ji vidí i ostatní procesy, které mapují týž soubor - nejrychlejší [sdílená paměť](Meziprocesova-komunikace), jakou můžeš mít.

## Přeprodávání paměti a líné přidělování

`malloc(1 GB)` uspěje na stroji, kde volný gigabajt není. Nikdo nelže: alokace jen zapíše do seznamu oblastí další slib. Fyzická stránka se přidělí až při prvním dotyku, přes [výpadek stránky](Virtualni-pamet-a-strankovani).

```bash
cat /proc/sys/vm/overcommit_memory     # režim přeprodávání
```

| Hodnota | Co dělá | Kdy ji chceš |
|---|---|---|
| `0` | heuristika, odmítne nesmyslné žádosti | **výchozí, nech to tak** |
| `1` | vyhoví vždycky | řídká pole, mapuje se víc, než se použije |
| `2` | tvrdý strop `CommitLimit` | má-li selhat `malloc` místo procesu |

Režim `2` počítá strop jako odkládací prostor plus `overcommit_ratio` procent RAM, a protože ten poměr je implicitně 50, na stroji bez swapu ti z 16 GB povolí zhruba osm. Nech výchozí nulu, ale věz, co znamená: **tvůj program může být zabit, i když `malloc` uspěl.** Kdo koho zabije, je u [výměnných algoritmů](Vymenne-algoritmy).

## Jak číst čísla o paměti procesu

| Metrika | Co doopravdy měří | Kdy je zavádějící |
|---|---|---|
| VSZ | součet velikostí všech mapování | skoro vždy, počítá i nedotčené sliby |
| RSS | stránky přítomné ve fyzické paměti | sdílené knihovny počítá celé každému |
| **PSS** | sdílená stránka dělená počtem uživatelů | jen na Linuxu a jen ze `smaps` |
| USS | jen soukromé stránky | řekne, co uvolní zabití procesu |

Odtud plyne, co každého zarazí: **součet RSS všech procesů vyjde víc, než kolik je v počítači paměti.** Knihovnu `libc` má namapovanou každý proces a každému se počítá celá, přestože fyzicky je v paměti jednou.

Poctivější číslo dá PSS. Sečte ho `smem`, a bez instalace čehokoli funguje `/proc/PID/smaps_rollup`, které je od jádra 4.14 a je mnohem levnější než celé `smaps`. Zbytek je u [nástrojů a diagnostiky](Nastroje-a-diagnostika).

## Zásobník a jeho meze

Zásobník hlavního vlákna má implicitně 8 MiB a `ulimit -s` to ukáže v kilobajtech jako `8192`. Přeteče ze dvou příčin: rekurze, která se nezastaví, a lokální pole typu `char buf[16 * 1024 * 1024]`. Obojí končí signálem SIGSEGV, protože pod zásobníkem je stránka stráže, tedy nenamapovaná oblast. Velká pole patří na haldu.

```bash
ulimit -s          # 8192 znamená 8192 KiB, tedy 8 MiB
ulimit -s 32768    # zvedne strop na 32 MiB pro tenhle shell a jeho potomky
```

Každé [vlákno](Vlakna) má vlastní zásobník a implicitní velikost bere z `ulimit -s`. **Tisíc vláken tedy znamená 8 GiB virtuálního prostoru.** Fyzicky se spotřebuje jen dotčená část, ale při `overcommit_memory` na `2` se započítá celý.

### Stack Clash, 2017

V červnu 2017 zveřejnila firma Qualys třídu útoků Stack Clash. Stránka stráže byla tehdy jediná stránka o 4 KiB a program, který si naráz vyrobil dostatečně velký rámec, ji přeskočil a zapisoval rovnou do sousedního mapování. Přes setuid binárky to vedlo k místní eskalaci [práv](Prava-a-uzivatele) na Linuxu i na několika BSD; opravovalo se to jako CVE-2017-1000364 a jádro zvětšilo mezeru z jedné stránky na 1 MiB.

Poučení: **stránka stráže chrání jen do té míry, do jaké je jisté, že do ní program šlápne.**

## Proč dlouho běžící proces roste, i když nikde neteče

Server obslouží ve špičce deset tisíc spojení po 20 KiB, pak jich má sto, a RSS zůstane nahoře. Paměť je uvolněná, ale sedí v seznamech alokátoru roztroušená mezi živými bloky, které brání zkrácení haldy. To je fragmentace haldy, ne únik.

**Rozlišíš je podle tvaru křivky.** Únik roste bez konce, fragmentace se ustálí na plató. Nech to běžet den; když se RSS zastaví, byť vysoko, žádný únik nehledej.

Druhá častá příčina je počet arén v glibc: ve vícevláknovém programu jich vyrobí až osminásobek počtu jader, aby se vlákna nepraly o zámek, a každá si drží vlastní zásobu. Na osmi jádrech je to až 64 arén.

```bash
MALLOC_ARENA_MAX=2 ./program                                     # méně arén, méně roztříštěné paměti
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 ./program  # balíček libjemalloc2
```

Jiný alokátor zkoušej, když má program hodně vláken a hodně malých alokací různých velikostí; jemalloc i tcmalloc mají třídy velikostí a vlákenné mezipaměti a fragmentují míň. Placebo je to u jednovláknového programu a všude, kde je příčinou skutečný únik.

## Diagnostika

```bash
free -h                                       # dívej se na available, ne na free
grep -E 'MemAvailable|Committed_AS' /proc/meminfo
pmap -x 1234                                  # oblasti procesu s RSS a Dirty na každou
grep -E '^(Rss|Pss|Private_Dirty)' /proc/1234/smaps_rollup
dmesg -T | grep -i 'out of memory'            # zabil ho OOM killer?
valgrind --leak-check=full ./program          # zpomalí 10-50x, na produkci ne
```

| Příznak | Kde je problém |
|---|---|
| RSS roste a nezastaví se | skutečný únik, na to `valgrind` |
| RSS vyskočil a drží se na plató | fragmentace haldy nebo neuvolněná špička |
| málo volné paměti, systém běží dobře | špatný sloupec, čti `available` |
| SIGKILL a v `dmesg` zmínka o OOM | přeprodaná paměť došla při dotyku |
| `malloc` vrátil NULL | `RLIMIT_AS`, limit cgroups nebo overcommit `2` |
| segfault na startu u velkého pole | lokální pole přes 8 MiB, přesuň ho na haldu |

V [kontejneru](Virtualizace-a-kontejnery) ukáže `free` paměť celého stroje, ale zabije tě strop cgroup z `/sys/fs/cgroup/memory.max`.

## Co si odnést

**Adresní prostor je seznam slibů, ne paměť.** Většina z nich nemá za sebou nic, dokud na ně nesáhneš.

**Sloupec `available`, ne `free`.** Vyrovnávací paměť disku se zahazuje na požádání.

**`/proc/PID/maps` odpoví na většinu otázek.** Práva, velikosti oblastí i mapované soubory.

**`malloc` je knihovna, ne jádro.** Do jádra chodí přes `brk` a `mmap`, a zřídka.

**Úspěšný `malloc` není záruka.** Stránka se přiděluje při dotyku a tehdy může přijít OOM killer.

**RSS sečtené přes procesy nedává smysl, PSS ano.** Sdílené stránky se jinak počítají mnohokrát.

**Únik roste bez konce, fragmentace se ustálí.** Podle toho poznáš, který nástroj vzít.

## Kam dál

- **[Virtuální paměť a stránkování](Virtualni-pamet-a-strankovani)** - jak se ze slibu stane fyzická stránka
- **[Výměnné algoritmy](Vymenne-algoritmy)** - co se děje, když paměť dojde, a jak vybírá OOM killer
- **[Vlákna](Vlakna)** - proč každé vlákno ukousne kus adresního prostoru
- **[Nástroje a diagnostika](Nastroje-a-diagnostika)** - `pmap`, `smem`, `/proc` a kdy který