0xDEADBEEF

realloc, mremap & virtuální paměť

V poslední době¹ mě baví psát programy pro malé stroje. Když říkám malé, mám na mysli něco ve stylu Raspberry Pi s 1 GB RAM – zdaleka ne miniaturní, přesto limitující.

Jednoduchý problém: čtu data z disku do paměti. Později budou opakovaně potřeba a disky jsou pomalé (tím spíš na maličkém stroji, kde jako disk slouží SD karta). Chci je přitom do paměti nacpat takovým způsobem, aby celá operace měla co nejmenší špičku resident set size (RSS).

Klasickým přístupem pro data neznámé délky je alokovat pole nějaké výchozí délky, postupně ho plnit daty, když se pole naplní, alokovat dvakrát větší (nebo libovolný jiný násobek velikosti, aby se práce amortizovala), zkopírovat stará data do nového pole, staré zahodit, další data přidávat do nového a opakovat, dokud není úkol splněn. Něco jako tohle:

void add(X x) {
  if (isFull(arr)) {
    auto newArr = new X[arr.length * 2];
    newArr[0 .. arr.length] = arr[];
    arr = newArr;
  }
  arr.append(x);
}

Kolik paměti potřebuje tenhle manévr? Překvapivě hodně.

Jeden problém mají na svědomí pohodlné jazyky ve stylu Javy nebo D, které alokovanou paměť vždy vynulují nebo inicializují na výchozí hodnotu. Runtime se při nulování musí dotknout každé stránky virtuální paměti, což vyvolá alokaci paměti fyzické. Virtuální paměťový prostor je prakticky nekonečný (aspoň na 64-bit systémech), zato fyzická RAM je omezená a každý bajt stojí tvrdá €€€. Navíc nechci swapovat, protože to by eliminovalo výhody držení dat v RAM.

Situace se může mít takhle: V paměti mám přesně 128 MB dat a potřebuju k nim přidat jeden poslední bajt. Přílepek do plného pole způsobí alokování 256 MB virtuální paměti, kterou runtime vynuluje, což vyvolá alokaci 256 MB fyzické paměti. Data se pak zkopírují na nové místo, přidá se onen bajt a staré pole je dealokováno. V jednom okamžiku operace potřebuje 384 MB místa ve fyzické paměti, ~3× tolik, než by bylo nezbytně nutné.

Co když ale použiju prastaré funkce malloc a realloc ze standardní knihovny jazyka C? Jejich výhoda spočívá v tom, že data se nenulují předem a v důsledku toho dojde k alokaci jen takového množství fyzické paměti, kolik se skutečně použije.

V D jsem napsal jednoduchý test, který se to snaží ověřit.

import core.stdc.stdlib;
import std.stdio;

void main() {
  enum M = 1 << 20; // 1 MB
  auto p = malloc(M);

  foreach (i; 2 .. 70) {
    auto n = realloc(p, i * M);
    (cast(byte*) n)[0 .. i * M] = 0; // vynulování dat
    writeln(i, "M ", p != n ? "moved" : "     ", " ", rssSize());
    p = n;
  }

  free(p);
}

private auto rssSize() {
  long x, rss;
  File("/proc/self/statm").readf!"%d %d"(x, rss);
  return rss * (1 << 12);
}

Program testuje dvě věci: Jaký je RSS v každém okamžiku a kdy dojde ke změně pointeru. realloc může alokovaný prostor prodloužit na místě nebo, když mu v adresním prostoru něco překáží, přesune data na jinou virtuální adresu a vrátí pointer na ní. Stará alokace se tím okamžikem stane neplatná. Když prodlužuje na místě, spotřebované množství paměti by mělo růst plynule po jednom megabajtu.

Výsledky jsou přesně takové, jaké bych čekal: Ke změně pointeru dojde vždy při překročení mocniny dvou (2 MB, 4 MB, 8 MB, …) a RSS odpovídá tomu, kolik místa je skutečně třeba, neroste skokově v mocninách dvou.

Když ale zkoumám /proc/[pid]/status, metrika VmHWM udávající maximální RSS během života procesu je podezřele nízká. Test vyžadoval maximálně 70 MB a max RSS se pohybovalo jen mírně nad 70 MB, rozhodně mnohem méně než 128 MB, které bych čekal v okamžiku, kdy se 64 MB dat kopíruje do nového místa v paměti.

Tohle je zajímavé, protože do hry vstupuje inteligentní práce s virtuální pamětí. Technicky vzato realloc nemusí nic kopírovat, data leží kdesi ve fyzické paměti a tam můžou zůstat, změnit se musí jen mapování virtuální paměti, kdy nová adresa ukazuje na již existující fyzické rámce.

Zdrojáky glibc říkají tohle:

Large chunks that were internally obtained via mmap will always be grown using malloc-copy-free sequences unless the system supports MREMAP (currently only linux).

mremap je linuxový syscall pro manipulaci mapování virtuální paměti. Může existující mapování rozšířit nebo smrsknout, ideálně na místě, ale když není zbytí, dojde k přesunu na jinou virtuální adresu. V dokumentaci se přímo píše:

mremap() changes the mapping between virtual addresses and memory pages. This can be used to implement a very efficient realloc(3).

Zkusmé prohnání testovacího programu přes strace -e trace=mremap potvrzuje, že se skutečně používá mremap pro každý realloc.

Tak tady to máte: realloc v jediném systému, který mě zajímá, je velice efektivní a potřebuje jen tolik paměti, kolik je nezbytně nutné, což mi krásně hraje do karet.

Dodatek: Pokud potřebuju vynulovanou paměť, která alokuje fyzickou RAM líně a podle potřeby, dá se toho docílit přes mmap a MAP_ANON. Když si program vyžádá paměť přímo od operačního systému, ta je líně nulována, protože OS nemůže dovolit, aby proces viděl, co se nacházelo na dané stránce fyzické paměti, která mohla původně patřit jinému procesu. Když poprvé sáhnu na stránku od OS, fault hander ji vynuluje. malloc tohle interně používá, ale stránky s daty které program uvolnil, obvykle nevrací systému, ale drží se jich, aby jimi uspokojil další malloc požadavky bez nutnosti dělat syscall. Může tak vrátit buď vynulovanou stránku přímo od operačního systému nebo starší stránku s daty, které do ní zapsal program dříve. To asi bude důvod, proč runtime rozumných jazyků inicializuje/nuluje alokace horlivě – nevědí, co můžou dostat a tak se musí chovat defenzivně.

1. To aspoň platilo v době psaní tohohle článku, říjnu 2021. Situace se od té doby mnohokrát změnila.