Recepty z programátorské kuchařky
Práce s pamětí

V této kuchařce se, poněkud netradičně, nepodíváme pod pokličku nějakého algoritmu, ale povíme si něco o tom, co se děje na pozadí, když se v našem programu rozhodneme vytvořit nějakou proměnnou, číst z ní, nebo do ní zapisovat.

Strojový kód, instrukce a registry

Jak asi víte, procesory počítačů neumí přímo vykonávat jednotlivé řádky našich programů a potřebujeme přivolat na pomoc nějaký kompilátor nebo interpret, který z našeho programu vyrobí tzv. strojový kód, což je dlouhý seznam jednoduchých instrukcí, kterým už procesor rozumí. Takové instrukce například vezmou čísla ze dvou registrů, udělají na nich nějakou aritmetickou operaci, a pak výsledek uloží do jiného registru.

Takový registr je našim dobře známým proměnným velmi podobný v tom, že se jedná o krabičku uvnitř procesoru, kam si můžeme uložit nějaké jedno číslo a později si ho odtamtud zase přečíst. Bohužel jich ale každý procesor má jen pár – počet velmi závisí na konkrétním procesoru, ale ty, které najdeme ve většině dnešních počítačů, jich mají jen 16 všeobecných (a pak ještě pár specializovaných, ale těmi se s dovolením nebudeme zabývat). Na velmi jednoduché programy nám to možná bude stačit, ale hned jak budeme chtít pracovat se seznamem čísel delším než 16, už budeme mít problém. Registry mají také omezenou velikost, obvykle 64 nebo 32 bitů, což odpovídá tomu, že se procesorům říká „64-bitové“ nebo „32-bitové“.

Paměť

Proto mají kromě registrů procesory také k dispozici paměť. Tu si můžeme představit jako dlouhatánský seznam očíslovaných políček, do kterých se dají opět, jak jinak, ukládat čísla. Číslům, kterými jsou označena políčka, se obvykle říká adresy, číslům uloženým v políčkách hodnoty a často mluvíme o hodnotě paměti na adrese X nebo také obsahu paměti na adrese X. Všechny hodnoty jsou ve skutečnosti jen posloupnosti bytů. Všechna data, která chceme ukládat, včetně celých čísel, floatů, obrázků nebo i instrukcí procesoru, tak musíme do jednotlivých bytů nějak zakódovat. Adresy mají velikost jednoho slova, která odpovídá velikosti registrů.¹ Každá adresa odpovídá jednomu bytu paměti,² ale objekty uložené v paměti mohou být různě velké. Adresa pak ukazuje na jejich první byte. Adresy bývají často zarovnané na slova, ale není to povinné. Jediné, co taková paměť umí, je na požádání vrátit hodnotu, která se nachází na dané adrese, nebo na danou adresu konkrétní hodnotu zapsat.

Procesor nám proto nabízí instrukce, které nám umožňují načíst hodnotu z pevné (tzv. okamžité, angl. immediate) adresy a uložit ji do nějakého registru. Taková adresa je pak pevně zabudovaná ve strojovém kódu a pokaždé, když program spustíme, bude procesor pracovat s tou stejnou adresou. To na některé věci stačí, ale složitější věci s tím nevyřešíme. Nejjednodušším příkladem, kdy pevné adresy nestačí, je třeba práce s polem – museli bychom do strojového kódu zapéct adresu každé buňky, navíc bychom nemohli pracovat například s poli proměnlivé velikosti. Proto existují také instrukce, které si přečtou adresu, ze které mají hodnoty načítat, z nějakého dalšího registru. Dokonce máme i instrukce, které dělají: „Načti hodnotu z registru X, přičti k ní tuhle pevnou hodnotu a z výsledné adresy načti hodnotu do registru Y“. To se stane třeba ve chvíli, kdy v Céčku přistoupíte k nějakému políčku ve struktuře – víme adresu celé struktury a zajímá nás konkrétní políčko v ní.

Části paměti

Teď už nám zbývá jen vyřešit, jak se mají jednotlivé programy a jejich části domluvit, na jaké adresy mají uložit obsah svých proměnných, aby si vzájemně nepřekážely. K tomu slouží tři různá místa: tzv. datová paměť, kde se ukládají globální proměnné, a poté halda a zásobník. Pozor, ty nemají nic společného s datovými strukturami halda a zásobník, a byť se občas mohou chovat podobně, jsou to odlišné koncepty.

Do datové paměti, se kromě globálních proměnných ukládá také například strojový kód programu. Důležité je, že ve chvíli, kdy generujeme strojový kód, už víme, kolik celkem budeme mít globálních proměnných, takže všemu, co se nachází v datové paměti, můžeme přiřadit pevné adresy, a ty si pevně zapsat do kódu. Virtualizace paměti nám pak zařídí, aby dva různé programy mohly používat stejné pevné adresy pro datovou paměť a nesrazily se (jak virtualizace funguje, si ukážeme později).

Na lokální proměnné nám proto zbývá právě halda se zásobníkem. Vzhledem k tomu, že předem nevíme, kolik paměti budeme potřebovat, je nutné, abychom uměli haldu i zásobník postupně nafukovat, jak v nich budou přibývat data. Proto haldu dáme na začátek volné paměti a zásobník na samotný konec, přičemž haldu pak můžeme rozšiřovat směrem k vyšším adresám a zásobník směrem k nižším. Často se říká, že „zásobník roste dolů“, čímž popisujeme přesně tuto skutečnost – čím více hodnot na zásobníku bude, tím menší bude jejich adresa.

Volání funkcí a zásobník

Než se dostaneme k tomu, jak funguje zásobník, povíme si něco o tom, jak se ve strojovém kódu volají funkce. Strojový kód máme uložený v datové paměti (podobně jako globální proměnné, jak jsme si popsali výše). To znamená, že už v době kompilace známe adresu všech instrukcí, speciálně tedy i adresu začátku všech funkcí. Když voláme funkci, stačí nám tedy „skočit“ na předem známé místo v datové paměti a začít vykonávat kód odsud (instrukci provádějící tento skok se většinou říká jump). Ale kam pak skočit, když funkce skončí? Bylo by pěkné si ve chvíli, kdy voláme nějakou funkci, poznamenat, z jakého místa ve strojovém kódu jsme přišli, abychom se tam pak po skončení volané funkce mohli vrátit. Nejjednodušší by bylo si na to vyhradit jeden celý registr, tam bychom ale narazili na problém, kdybychom potřebovali uvnitř volané funkce volat nějakou jinou funkci. Chtěli bychom si pořídit datovou strukturu, které můžeme při každém volání funkce předhodit aktuální adresu, a při návratu z funkce z ní vytáhnout tu adresu, kterou jsme tam přidali jako poslední. A někteří z vás už si bezesporu všimli, že to je přesný popis chování zásobníku.

Přeci jen má zásobník něco společného se stejnojmennou datovou strukturou. A jak ho implementujeme jen pomocí pár jednoduchých instrukcí? Prostě mu vyhradíme nějaké předem dané místo v paměti (v tom nejjednodušším případě, jak jsme se dočetli výše, na úplném konci) a vyhradíme si jeden registr (v terminologii x86³ mu obvykle říkáme rsp – Register for Stack Pointer), kde si budeme ukládat ukazatel (adresu) na místo v paměti, kde je aktuálně vršek zásobníku. Když chceme na zásobník přidat hodnotu X, prostě rsp zmenšíme o jedničku (připomeňte si, že zásobník roste dolů) a na adresu, kam rsp ukazuje, zapíšeme X. Při čtení postupujeme přesně obráceně.

Když už si na zásobník ukládáme návratové adresy (return address), mohli bychom tam začít dávat i lokální proměnné, jen si musíme dát na pár věcí pozor. Vytváření nových lokálních proměnných nebude složité, můžeme je přidávat na zásobník beze změny. Jak ale později zjistíme, kde máme proměnnou uloženou? Zapéct její adresu do kódu nemůžeme, neboť může být pokaždé někde jinde. Můžeme si pamatovat, že jsme ji uložili na adresu, kam ukazuje rsp, ale tak získáme jen adresu úplně poslední lokální proměnné. Řešením je pamatovat si, jak daleko od konce zásobníku naše proměnná je – tomu se říká offset vůči rsp. Pokud bychom si ale uprostřed funkce pořídili novou lokální proměnnou, posuneme tím rsp, a tím pádem i offset všech ostatních lokálních proměnných na zásobníku. Je proto obvyklé, že se všechny lokální proměnné vytvoří na začátku funkce najednou a po dobu běhu funkce už se pozice rsp nemění.

Jak se ale dostaneme k návratové adrese, když jsme si teď zaházeli volací zásobník lokálními proměnnými? Úplně stejně jako k lokálním proměnným, které nejsou na vrcholu zásobníku. Prostě si při generování kódu pamatujeme, kolik aktuálně máme na zásobníku lokálních proměnných, a víme, že hned pod nimi je návratová adresa. Těsně předtím, než skočíme z funkce ven, pak musíme taky zásobník uklidit, a to tak, že rsp posuneme na místo, kde byl před voláním funkce, tedy hned pod návratovou adresu.

Tohle dopočítávání během generování strojového kódu je sice hezké a stačí k funkčnímu modelu, ale je to nepřehledné a jednou za čas se hodí mít možnost si i strojový kód přečíst, což se dělá špatně, když všechno odpočítáváme od rsp. Proto se téměř vždy používá i druhý registr (kterému se v x86 říká rbp – Register for stack Base Pointer), který vždy ukazuje na začátek stack framu, hned pod ním je návratová adresa. Zásobníkový rámec, nebo častěji stack frame, je ta část paměti, která obsahuje všechna data pro jedno konkrétní volání funkce. Při volání funkce je posun rbp jednoduchý, prostě jeho hodnotu nastavíme na aktuální hodnotu rsp, protože právě tam budeme zapisovat návratovou adresu. Při návratu z funkce je to horší, musíme totiž zjistit, co bylo v rbp předtím, než jsme ho změnili. Takový problém jsme ale už přeci řešili, prostě při volání předchozí hodnotu rbp vložíme na zásobník za návratovou adresu a tam si ji pak také při návratu přečteme.

Na obrázku níže vidíte, jak bude vypadat zásobník, pokud ve funkci main zavoláme funkci f1 a uvnitř té zavoláme funkci f2. Šipky ukazují aktuální pozice rsp a rbp ve chvíli, kdy se nacházíme uvnitř f2.

Mimochodem, většina dnešních procesorů poskytuje na volání funkcí samostatné instrukce, v x86 je to konkrétně call, která přidá na zásobník adresu následující instrukce (té, na kterou se pak budeme vracet) a skočí na pevně danou adresu funkce. Instrukce ret poté z vrcholu zásobníku jednu adresu sundá a skočí na ni. Stejně tak pro práci s rbp poskytuje instrukční sada x86 instrukce enter a leave.

Halda a dynamická alokace

Teď už nám zbývá jen povědět, jak funguje halda. Ta už má s datovou strukturou stejného jména společného mnohem méně. Je to místo, kde si musí každý svůj prostor v paměti ručně zarezervovat (naalokovat) a pak, když už ho nepotřebuje, ho zase uvolnit ostatním (dealokovat). Na pozadí je pak nějaký alokátor, obvykle součástí standardní knihovny jazyka, který si drží přehled o zaplněnosti haldy (obvykle pomocí metadat uložených před nebo za alokovanou částí paměti) a vyřizuje požadavky na alokaci nebo dealokaci. Dealokovaná paměť se samozřejmě dále používá, takže pokud paměť nevynulujeme, můžeme tam najít data, která tam byla předtím. Nevýhoda haldy je samozřejmě to, že manuální alokace je pro programátora pracná, a pokud někde zapomeneme dealokovat, paměť nám postupně dojde a nejspíše brzy poté spadne celý počítač.

V C se paměť alokuje pomocí funkce void *malloc(size_t size), kde parametr size určuje velikost úseku, který chceme naalokovat. Funkce vrátí ukazatel na začátek nově vyhrazeného úseku (což je ve skutečnosti jen adresa), případně NULL, pokud alokace selhala. Funkce void free(void *ptr) pak umožňuje uvolnit daný úsek k dalšímu použití. Předává se jí ukazatel na začátek úseku, tedy ukazatel, který vrátil malloc.

Také je dobré vědět, že halda může trpět fragmentací – když alokujeme a dealokujeme různě velké kousky paměti, postupně na haldě vznikají díry, které se nedají znovu naplnit, pokud alokujeme větší úseky, než jsou díry. Tak se nám může stát, že máme na haldě spoustu volného místa, ale stejně nemáme novou alokaci kam dát.

Virtualizace paměti

Nakonec by se ještě slušelo zmínit, co že je to ta virtualizace paměti, která byla zmíněna výše. Ve zkratce se jedná o mechanismus, pomocí kterého se operační systém postará, aby to z pohledu všech programů vypadalo, že jsou samy na světě – na začátku je z jejich pohledu paměť prázdná a obrovská, neboť každá adresa délky slova je validní, i když je daleko za kapacitou fyzické paměti, kterou má počítač k dispozici. Operační systém si udržuje tzv. stránkovací tabulku, kde pro každý kus paměti, který se program rozhodne použít, udržuje místo, kde se tenhle kus paměti vyskytuje v paměti fyzické, a toto místo ve fyzické paměti rozděluje tak, aby každý program měl své. Díky tomu mohou všechny programy zasahovat do paměti, jak chtějí, a nemusí řešit, jestli nezasahují do cizích dat. Při startu každého programu se do této virtuální paměti připraví, mimo jiné, také místo pro haldu a zásobník, takže je běžící program může rovnou začít využívat. Program také nemůže jen tak přistupovat na jakékoliv místo v paměti, ale musí požádat OS, aby mu vyrobil pro dané místo v tabulce stránku ve stránkovací tabulce. To je další věc, kterou na pozadí dělá malloc. Kromě alokace samotné si také vyžaduje přidělení nových stránek, pokud v těch, které už má přidělené, nenajde místo. Když se stane, že paměť dojde celému počítači a OS už nemá žádnou volnou stránku, kterou by přidělil, vrátí malloc NULL. Pokud se pokusíme přečíst z nějaké adresy, kterou nám OS nepřidělil, program „vyhodí segfault“. Paměti, kterou nám ale už jednou malloc vrátil, můžeme věřit.

To bude z dnešní kuchařky vše. Ukázali jsme si, že převod našich programů na instrukce, kterým procesory rozumí, není vždy tak jednoduchý, jak se může na první pohled zdát. Také jsme si řekli, co jsou to registry, jak funguje paměť a jak si pomocí nich pořídit docela příjemně použitelná primitiva pro proměnné. Dozvěděli jsme se, co je to halda a zásobník v kontextu paměti programu a krátce jsme nastínili, jak funguje virtualizovaná paměť.

Guláš v paměti vám uvařil

Honza Černohorský

---

¹↑ Z historických důvodů se můžete také (obzvlášť v podkladech od společnosti Intel) setkat s tím, že se termín slovo nebo také WORD označuje velikost přesně 16-bitů, double WORD nebo DWORD pak značí přesně 32 bitů a quad WORD nebo QWORD značí 64 bitů. My se však budeme držet toho, že velikost slova vždy odpovídá velikosti registru daného procesoru.

²↑ To je mimochodem důvod, proč 32-bitové počítače nemohou mít více než ~4 GB paměti. Paměť je adresována celkem 2³² adresami, má tedy celkem 2³² bytů, což je právě téměř 4 GB.

³↑ x86 je název sady instrukcí, která byla poprvé použita pro procesor Intel 8086, od kterého má i název. Od té doby se rozšířila na další procesory a prakticky všechny procesory v počítačích a serverech jsou dnes postavené na jejím 64-bitovém rozšíření x86-64. I když autorem x86 je Intel (a x86-64 zase AMD), instrukční sadu používají, s malými rozdíly, všichni. Hlavní konkurencí x86 je skupina instrukčních sad ARM, která se používá spíše v mobilních zařízeních, ale některé společnosti experimentují i s použitím na desktopu, například architektura M1 a M2 od společnosti Apple.

Menu