Názory k článku
Jak funguje malloc a free

Zajímala by mě jedna věc. Zkoušel jsem s mallocem experimentovat.

Spustil jsem program A, který alokoval 70% veškeré paměti počítače (RAM + SWAP).

Spustil jsem program B, který si též alokoval 70% paměti. Poté oba dva programy začaly přidělenou paměť přepisovat, čímž se začala paměť fyzicky zaplňovat.

Po chvíli swapování jako blázen se jádro OS naštvalo, protože mu došla paměť, došlo k tzv. deadlocku. To Linux vyřešil zabitím jednoho z programů.

A já se ptám: Jak je možné, že korektně napsaný program je odstřelen, i když obsahuje test, dostal-li přidělenou paměť?

Deadlock je teda podle mě něco jinýho (když si dva nebo více procesů čeká navzájem na zámky).

Ale jinak je to proto, že Linux používá optimistickou strategii alokace -- fyzické stránky se přidělují, až je to skutečně potřeba. Předpokládá se, že když doje paměť, tak je něco tak špatně, že už je putna, jestli se něco zabije.

Bylo by možné používat pesimistickou alokační strategii, která tomuto problému zamezuje, ale v praxi by to znamenalo dost velké plýtvání pamětí.

OT: oprava: zaokrouhluje to na *násobky* osmi, ne na dělitele osmi (dělitelé osmi jsou v přirozených číslech 1, 2, 4 a 8).

Vypadá to, že jo, takže optimistická strategie je akorát default, a v novějších jádrech jsou navíc možné ještě hodnoty 2 a 3 -- viz /usr/src/linux/Documentation/vm/overcommit-accounting ;-)

Podle me je to logicke. OOM killer proste zabije bumbrlicka, ktery ohrozuje cely system. Co treba s programem, ktery diky memory leakum naalokuje giga pameti (ikdyz mu to teda v systemu projde) a ostatni procesy si pak neskrtnou?

mel jsem si napsat cvika u tebe....

to je iny holecek :))

Zdravim,

kdyz uz se autor pousti do podobneho tematu, nemel by rozhodne zapominat na 'odolnost' heapy jako takove, to jest odolnost proti prepisum marku/velikosti, odolnost proti leakum a tak dale. Fakt, ze Dag Lemovo heapa (std pouzivana v glibc a zminovana autorem) nema defacto zadne podobne funknce a tise veskere 'chyby' ignoruje nas napr. donutila napsat si vlastni (dokonce jsme si psal s Dagem :) Jasne, jsou ruzne 'nadstavby', ale jsou to vetsinu zaplaty nez systemove reseni....

Osobne si myslim, ze odolnost heapy vuci 'chybam' je velice dulezita cast a nemala byt zcela ingorovana.

Popsana 'fragmentace' je take dost silne zkreslena. Spojeni vice free bloku do jednoho samo o sobe nic neresi, specialne v c++. Jsou tu daleko horsi problemy. U resizovani bloku predvidani (at uz se jedna o velke nebo male bloky), pridelovani V pameti bez prideleni fyzicke a rada dalsich metod.

Nu, kdyz uz autor zabrousil do podobneho tematu, nemel dle mne opomenou dost dulezite veci :)

ps: ledaze by se chystal druhy dil :)

Pekny den,
R.

O dalsim dile uvazuju, ale ten bude spis zamereny na alokaci pameti v jadre. Ja tento clanek napsal pote, co jsem nekolik dni zkoumal zdrojak mallocu a hledal ruzne clanky na googlu. Jako cil jsem si dal popsat jak funguje stavajici malloc.

Rozhodne ale dik za pripominky, urcite se na to jeste kouknu a jestli me to chytne, urcite pouvazuju o pokracovani na toto tema.

Taky by nebylo spatne zminit promenne prostredi, ktere ridi strategie malloc -- nastavuji prah pouziti mmap. Nekdy se to hodi.

Kdyby v tom článku bylo všechno co popisujete, byl by třikrát tak dlouhý. Takže se to může objevit v pokračování, ale podle mě byl tenhle článek přimeřený.

BTW, proč je v C++ spojování bloků k ničemu? (Přiznávám se, že o implementaci new a delete v GCC nic nevím.)

new/delete je obycejne volani malloc/free (z hlediska heapy samozrejmne). Pokud by tedy byl kod ala

obj - objekt zabirajici 8 bajtu (+8 heapa -> 16 real)

o1=new obj;
o2=new obj;
o3=new obj;
o4=new obj;

...
delete o1
delete o2
delete o4

Vznikne 'fragment'... Klasicke (typicky dedeni a vytvareni child objektu - knihovny MFC, GTK a dalsi) se vyznacuji prave obrovskym mnozstvim 'malych' alokaci (odtud i jejich pametova narocnost, rezie klasicke heapy je OBROVSKA).

Takze ac 'mame' volnou pamet 3*16 bajtu, nejsme schopni ji nalokovat. Takhle to smozrejmne vypada trivialne, ale tech alokaci jsou stovky tisic/miliony. Dag mel na strankach hezke grafy, podivam se jesli je tam ma jeste... Ma :)

http://gee.cs.oswego.edu/dl/malloc-plots/index.html

Na nekterych grafech je pekne videt o cem mluvim a navic je se da podivat i na velikosti alokacnich bloku. Autor mohl techno grafu zneuzit :)

I proto se vyplati (a dela se to) rozdelit heapu ne na ~2, ale na ~3 casti. Jedna na male bloky, jena na normlani (rekneme ~32bajtu az ~stovky kil) a potom velke bloky (povetsine se nechava na kernelu).

Ad poznamka o velikosti (3x tak vetsi clanek).... Neni prece duvod to rozepisovat do detajlu, ale kdyz uz se autor pustil do tohoto tematu (a ma pravdu v tom, ze hodne lidu o tom nema ani potuchy), tak myslim, ze odstavec venovany na tema robusnosti a pod. neni od veci.

A hlavne, neuskodil by trochu vice kriticky pohled na Dagovo malloc (srovnani s jinymi open source nahrazkamy - je jich dost.

R.

Ad grafy: ty jsou fakt dost dobrý.

Ad child objekty: zjišťoval někdo, jak velký má vliv na Gtk+ to, že glib si uchovává pooly volných objektů (teda žádných objektů, prostě svých datových typů, jako GSList, GList, ...), takže při g_blabla_free() se akorát přihodí do poolu a při g_blabla_new() se zase akorát zrecykluje? Nějaký pěkný graf? ;-)

Ad kritický pohled: asi jo. Ale těžiště článku je v srozumitelném popisu fungování mallocu glibc, a to bych řekl, že se podařilo.

... Namísto brk(2) proto použijeme jeho obdobu z libc sbrk(2).. - opravdu to je z libc, kdyz to je (2)?

man sbrk 2 ukaze manovou stranku o sbrk a v libc skutecne je.

ty vole nazdar bundo!! vis ze mi jeste dluzis 120 Kc? uz si na tebe s martinem krauskopfem louskame zuby. posleme na tebe negra s ledlampou. ani smrt ti nepomuze. jsme furt za tebou

Tomu sa povie: "vrouci setkani po letech" ;-))

Tohle se mi libi. Doufam, ze budete pokracovat a pritom (prilis) nezvedat obtiznost. Diky!

Diky za super clanek, uz se tesim na pokracovani!

Mate nekdo tuseni, jak je to s alokaci pro globalni promenne? Cekal jsem, ze to pujde pekne po rade, ale program:

int i;
char a[8];
char b[8];

int main()
{
printf("0x%08lx\n0x%08lx\n0x%08lx\n", (unsigned long)&i, (unsigned long)a, (unsigned long)b);

return 0;
};

mi vypise:

0x080496dc
0x080496e0
0x080496d4

Jiny, podobne slozity program mi je posklada tak jak bych cekal, tj. od nejnizsi adresy...

Diky za odpovedi i za clanek

Jak jsou uspořádené v paměti globální proměnné, to je věcí kompilátoru a nikomu do toho nic není, čímž chci říci, že mohou být uspořádané jakkoli, a není na tom nic k divení. ISO C žádné uspořádní nezaručuje.

Já jsem si teda vžycky myslel, že

0x080496d4

Pekny clanek!

Podle mne je skoda, ze primo na urovni libc nelze tento memory managment vice rizsirit. To pak vede k tomu, ze vetsi projekty si delaji nad malloc/free jeste vlastni managment, ktery vetsinou dela to same jeste jednou + pridava dalsi rozsireni. Napada mne Apache a PostgreSQL. Ta rozsireni jsou vetsinou v moznosti jednotlive alokace bloku sdruzovat do logickych celku a pak mit moznost uvolnit cely tento celek najednou (na misto volani free() pro kazdy fragment pameti). Je to i rychlejsi (pry cca 5-10% pokud alokujeto hodne a po malych castech). Mezi dalsi potrebna rozsireni u vetsich projektu bych pocital detekci leaku (to je napriklad u PostgreSQL).

Sdruzovat alokace do skupin a uvolnovat je pak najednou je mozne i v glibc - hledejte obstack. Treba zde:
http://www.gnu.org/manual/glibc-2.2.3/html_chapter/libc_3.html#SEC42

Obstack znam a pouzival jsem ho, ale to je dost orezavatko oproti mmgr o kterych jem mluvil.

normalne som si ho precital az 2 krat

Dve veci - jedna detail - jsou malloc(3) a free(3), sbrk je taky 3, ale v manu je pod dva, nevim proc ;) Mmch, nevim, jestli se vola sbrk pri uvolneni posledniho bloku, zalezi asi na jeho implementaci, ale kdyby ano, pak to neni tak uplne cisty wrapper na brk, bo pri neustalem volani free(malloc(...)) by vse bylo tragicky pomale ;)

K te druhe - /dev/zero se pise kde? Vzpominam-li si spravne, tak se na vetsi bloky vola kernel via MMAP_ANONYMOUS.

... hm, jeste jeden detail jsem si vzpomnel - stack miva velikost 2MB (na i386) bez par bytu nahore samozrejme, ktere se obsadi argv, env, pripadne thread-structama apod.

Zdar Kryso :)

No, /dev/zero se opravdu pouziva pro volani mmap (jakou source). Znas to, necht zije kompatibilita. Nektere kernely umi prez flag 'ignorovat' srouce a to je to o cem mluvis. #ifdef rulez :\ sbkr je dneska uz povetsinou pase, protoze neumoznuje udelat poradny memory management (NUTNOST pro vetsi projekty) a deska vicemene vsechny 'lepsi' CPU maji dobrou VM jednotku, ktera dovoluje pouzit primo featury mmap. I proto je DL malloc dost omezena, protoze se porad jeste da prelozit bez mmap.

R.

Vzhledem k tomu ze kernel stejne neumi sebrat mene nez 4KB bych si tipnul ze sbrk si hlida a vraci az cely 4KB nebo dokonce jeste vetsi kusy.

/dev/zero je UNIX standard - zarizeni ze ktereho lze cist same nuly, MMAP_ANONYMOUS je odjinud, kazdopadne prakticky efekt je stejny.

Chtel bych se zeptat, jestli je vubec jeste nutne testovat navratovou hodnotu malloc(). V jednoduchem C je to strasne otravne a trochu to zpomaluje program. V Linuxu na novejsi masine ja malloc() virtualne vzdy uspesna a pokud ne, jadro zabije cely program bez sance na nejake zachrane akce. Nebo se pletu?

pletete. nejen intelem ziv jest linux.

navic, pokud si virtualni uspesnost vypnete (viz vyse), tak ji mate vypnutou.

Mno dejme tomu, ze chci naprogramovat neco pro ix86, cili ne pro linux v lednici nebo v mobilu. A pak, co s tim killnutim zpatra?

Pro test uspesnosti alokace v cistem C muzes pouzit neco jako:

#include <assert.h>
int main() {
int *m;
assert(m=(int*)malloc(1234*sizeof(int)));
...
}

... je to trosku min otravne nez if (m==NULL) {blabla} :)

assert je makro a kdyz neni #ifdef _DEBUG_, tak se nic nekontroluje, tedy - konecna verze programu zadne kontroly neprovadi. Ja to obvykle resim:

void * xmalloc(int size)
{
void *v;
if ((v=malloc(size))==NULL) FATAL("Malo pameti");
return v;
}

Co takhle pokracovani o vecickach jako valgrind a spol?
http://www.gnu.org/directory/devel/Debugging/valgrind.html

valgrind je mrcha heuristicka. ma pozitivni i negativny "faily" ;). kdyby aspon nemel ty negativni :)
(pozitivni "fajl" je kdyz ti rekne ze tam je chyba a plete se, negativni je kdyz ti rekne ze tam chyba neni a plete se)

Jak autor v zaveru spravne podotyka, je nutne uvedomovat si rezii alokatoru na udrzovani struktur heapu - pro casto alokovane male struktury pak muze byt vhodne pouzit nejaky vlastni alokacni mechanismus. Specialne pokud struktura vyzaduje nejakou inicializaci a destrukci, je vyhodne nejaky takovy mechanismus pouzit - tato situace je typicka pro OOP (proto jak tu nekdo poznamenal se uzivaji treba pooly objektu).
Jistou vyhradu bych mel k poznamce, at se nebojime malloc volat casto. V jednothreadovem programu volani malloc bude skutecne temer zanedbatelne. Pravda to uz nemusi byt v multithreadovem programu. Vsak pro multithreadove (a specialne pro multiprocesorove) nasazeni existuji i specialni alokatory, ktere se snazi eliminovat cekani na zamku alokatoru - to by mozna mohl byt namet na nektere z pokrocilejsich pokracovani tohoto clanku.

Na single procesoru cekani na zamku absolutne nevadi- pokud je heap locknut, znamena to ze nektery jiny thread alokuje pamet a je tudiz runnable takze se akorat prohodej thready. Jo 99.99% systemu je single-cpu.

Pravda je, ze nejvetsi problem nastane na multiprocesoru - proto rikam "ze to problem byt nemusi". Nicmene i na singleprocesoru to muze znamenat urcite neprijemnosti (kdyz ne nutne problemy) - napr. v pripade, ze jedno z takovych vlaken musi z nejakych duvodu pracovat rychle (napr. zpracovava vstup, ktery nemuze moc cekat, nastavi si vyssi prioritu) a nektera jina vlakna maji nizke priority, muze vznikat v kriticke sekci alokatoru priority inversion. A to se zrovna v takovemto pripade, kdy pamet proste je treba naalokovat, obchazi blbe.
A jeste k zamykani - ani zamceni zamku pochopitelne neni zadarmo, zvlast neuspesny pokus, ktery konciva volanim kernelu (zalezi pochopitelne na implementaci zamku i vlaken).