[Per i guru del C] I segreti della malloc

[Scoperchiatore]

Argomento del thread: vita, morte e miracoli dell'allocazione di memoria in C

1. Come funziona a basso livello? [Usa il buddy system? Alloca solo blocchi a potenze di due? Alloca a pagine?
2. Se io faccio free, viene effettivamente liberata la memoria? In tutte le condizioni possibili?
3. Se faccio
   int* p = malloc(4)
   int* p2 = malloc(4)
   int* p3 = malloc(4)
   e poi faccio
   free(p2)
   vedo EFFFETTIVAMENTE quell'area di memoria libera, oppure il sistema operativo non la libera dato che non è contigua?
4. Dipende dal sistema operativo come e quanta memoria si alloca/libera? Se sì, come si comporta Linux?
5. I problemi di frammentazione esistono? Vi è mai capitato di affrontarli?
6. Quali sono le cause, secondo la vostra esperienza, di allocazioni maggiori del previsto, ESCLUDENDO puntatori allocati ma non liberati?
7. Perchè la documentazione di realloc dice che il puntatore allocato è lo stesso, mentre nella realtà ciò sembra non avvenire?

Dopo l'interrogatorio spiego brevemente il perchè della cosa.
Devo analizzare i dati provenienti dai route collector mondiali, che sono parecchiotti: una giornata = 20Gb.
Dato che ogni giorno devo processare 20Gb per avere poi un output su cui lavorare, ho fatto un programma in C, abbastanza banale, dedito allo scopo.
Il programma è veloce (2 ore) ma spreme la memoria: arriva a chiedere il massimo allocabile, 3,2 Gb.
Diminuendo l'input, mi sono fatto il calcolo delle strutture dati allocate, in modo preciso e pedissequo, a partire dalle statistiche che il programma stesso stampa.
Con poche possibilità di errore, ho scoperto che dovrei occupare poco più di 1,5 Gb, mentre alla fine la memoria arriva a 2020 Mb.

Se si parte dal presupposto che puntatori non liberati ed inutili non ce ne sono, perchè tutto il programma fa 4 malloc, e sono ipercontrollate, allora il dubbio è che le free e le deallocazioni dallo stack non rilascino effettivamente la memoria, magari per problemi di frammentazione.
Tenete presente che il programma alloca ad ogni iterazoine parecchi dati sullo stack delle varie funzioncine (cose del tipo char linea[MAX_LINE] e char delim[]=".,-/" per capirsi), e facendo sicuramente molte migliaia di iterazioni, se quelli non sono realmente deallocati, il problema si pone!

E solo voi "guru" del C potete dirmi se è vero o no

[andbin]

Premesso che non sono il guru-della-funzione-malloc, vedrò di rispondere al meglio. Alcune cose che riporterò sono prese dalla pagina di 'man' della malloc su linux, dalla documentazione della libc (vedere <qui>) e dal VC++.

Originariamente inviato da Scoperchiatore

Come funziona a basso livello? [Usa il buddy system? Alloca solo blocchi a potenze di due? Alloca a pagine?

Questo ovviamente dipende dal sistema operativo. Non c'è una regola aurea o standard unico e comune.
La documentazione della libc dice:

The address of a block returned by malloc or realloc in the GNU system is always a multiple of eight (or sixteen on 64-bit systems).

VC++ dice:

The storage space pointed to by the return value is guaranteed to be suitably aligned for storage of any type of object.

Originariamente inviato da Scoperchiatore

Se io faccio free, viene effettivamente liberata la memoria? In tutte le condizioni possibili?

Cosa intendi per "tutte le condizioni possibili"?? La free libera quel blocco di memoria. Il sistema, a seguito di una successiva malloc, potrà eventualmente riallocare quel blocco di memoria, sempre che quel blocco abbia la quantità di memoria tale da soddisfare la richiesta. Vedi punto seguente.

Originariamente inviato da Scoperchiatore

[*]Se faccio
int* p = malloc(4)
int* p2 = malloc(4)
int* p3 = malloc(4)
e poi faccio
free(p2)
vedo EFFFETTIVAMENTE quell'area di memoria libera, oppure il sistema operativo non la libera dato che non è contigua?

Ok, faccio una prova di esempio:

int *p1;
int *p2;
int *p3;

p1 = (int*) malloc (sizeof (int));
p2 = (int*) malloc (sizeof (int));
p3 = (int*) malloc (sizeof (int));

printf ("p1 = %p\n", p1);
printf ("p2 = %p\n", p2);
printf ("p3 = %p\n", p3);

free (p2);

p2 = (int*) malloc (sizeof (int));

printf ("p2 = %p\n", p2);

free (p1);
free (p2);
free (p3);

Provato adesso su Linux, ottengo in output:
p1 = 0x80496c0
p2 = 0x80496d0
p3 = 0x80496e0
p2 = 0x80496d0

Come vedi, la quarta malloc ha "ripreso" quel blocco di memoria che prima era stato liberato. Se avessi richiesto una quantità di memoria maggiore, molto probabilmente la malloc avrebbe cercato un'altra zona di memoria tale da soddisfare la richiesta.

Originariamente inviato da Scoperchiatore

Dipende dal sistema operativo come e quanta memoria si alloca/libera? Se sì, come si comporta Linux?

Questa non l'ho capita ... è la applicazione che decide quanta memoria allocare, non il sistema.

Originariamente inviato da Scoperchiatore

I problemi di frammentazione esistono? Vi è mai capitato di affrontarli?

Affrontarli, io personalmente, no. Ma il problema esiste.
Nel "vecchio" DOS, dove non c'era una gestione della memoria virtuale, si poteva frammentare la memoria fisica (e non c'era molto da fare ...). Nei sistemi moderni con gestione della memoria virtuale, la frammentazione della memoria fisica non c'è più. La memoria fisica viene suddivisa in N pagine della stessa dimensione (es. 4KB) e il gestore della memoria virtuale può anche usare poca memoria fisica dando però l'impressione al sistema di avere molta memoria virtuale (-> swapping su disco). Quello che si può ancora frammentare è lo spazio di memoria "lineare" che ogni processo "vede".

Originariamente inviato da Scoperchiatore

Quali sono le cause, secondo la vostra esperienza, di allocazioni maggiori del previsto, ESCLUDENDO puntatori allocati ma non liberati?

Non lo so di preciso. Comunque, a seguito di una richiesta di memoria per tot bytes, il sistema ne potrebbe allocare di più per una pura questione di allineamento e per mantenere delle informazioni sui blocchi.

Originariamente inviato da Scoperchiatore

Perchè la documentazione di realloc dice che il puntatore allocato è lo stesso, mentre nella realtà ciò sembra non avvenire?

Non so dove l'hai letto ma non è così. Dalla pagina di man della realloc:

void *realloc(void *ptr, size_t size);

[...] realloc() returns a pointer to the newly allocated memory, which is suitably aligned for any kind of variable and may be different from ptr, or NULL if the request fails.

Dice che può essere differente.


Ma proprio alle 21.00 di una calda notte di Luglio ti devi porre queste domande esistenziali sulla malloc??

[Scoperchiatore]

Ma proprio alle 21.00 di una calda notte di Luglio ti devi porre queste domande esistenziali sulla malloc??

Io alle 21 di una calda notte di Luglio sto lavorando alla tesi, quindi...

Grazie delle risposte, soprattutto sulla prova fatta .

Cmq, ieri notte mi sono messo a cercare, ed ho scoperto un mondo di cose. Tra cui il fatto che la frammentazione è un serio problema, e ci sono delle linee guida per tentare di limitarlo.
Ed inoltre, lo sapevate che esistono i garbage collector per C?

[andbin]

Originariamente inviato da Scoperchiatore

Grazie delle risposte, soprattutto sulla prova fatta .

C'è un'altra prova interessante sulla realloc:

char *p1, *p2, *p3;

p1 = (char*) malloc (100);
p2 = (char*) malloc (100);
p3 = (char*) malloc (100);

printf ("p1 = %p\n", p1);
printf ("p2 = %p\n", p2);
printf ("p3 = %p\n", p3);
printf ("\n");

free (p2);

p2 = (char*) malloc (50);

printf ("p2 = %p\n", p2);
printf ("\n");

p2 = (char*) realloc (p2, 70);

printf ("p2 = %p\n", p2);
printf ("\n");

p2 = (char*) realloc (p2, 200);

printf ("p2 = %p\n", p2);
printf ("\n");

free (p1);
free (p2);
free (p3);

Output su Linux:
p1 = 0x8049798
p2 = 0x8049800
p3 = 0x8049868

p2 = 0x8049800

p2 = 0x8049800

p2 = 0x80498d0

Le prime 3 malloc allocano 3 blocchi consecutivi da 100 byte (ci può essere dello spazio in più occupato per i motivi già detti).

p2 viene poi liberato; viene poi riallocato uno spazio di 50 byte e dato che ci sta in quello spazio vuoto di 100 byte, si riottiene lo stesso indirizzo di prima.

La prima realloc rialloca lo spazio a 70 byte e visto che "ci sta" ancora, si riottiene nuovamente lo stesso indirizzo.

La seconda realloc alloca 200 byte e visto che quello spazio di prima non è più sufficiente, va ad allocare memoria nello spazio successivo ai blocchi.

Da qui si vede bene che la realloc può restituire un nuovo puntatore oppure anche lo stesso.

[Marco Giunio Silano]

Originariamente inviato da Scoperchiatore

Io alle 21 di una calda notte di Luglio sto lavorando alla tesi, quindi...

Grazie delle risposte, soprattutto sulla prova fatta .

Cmq, ieri notte mi sono messo a cercare, ed ho scoperto un mondo di cose. Tra cui il fatto che la frammentazione è un serio problema, e ci sono delle linee guida per tentare di limitarlo.
Ed inoltre, lo sapevate che esistono i garbage collector per C?

frammentazione: nei sistemi senza MMU è un mostro terribile

[ilsensine]

Fermo restando che queste domande non sono specifiche per il c:

Originariamente inviato da Scoperchiatore

Come funziona a basso livello? [Usa il buddy system? Alloca solo blocchi a potenze di due? Alloca a pagine?

Dipende dalle librerie runtime.
In genere le librerie gestiscono un proprio heap, dinamicamente espandibile, che contiene aree di indirizzi virtuali (non necessariamente memoria fisica!!) forniti dal s/o. All'interno dell'heap, viene implementato un altro sistema di allocazione e gestione della frammentazione.
A volte vengono allocate altre regioni oltre l'heap principale.
Il buddy allocator è solo un algoritmo di gestione dei blocchi liberi; lo usa il kernel linux internamente (e su questo implementa altri allocatori), non so quale sia l'algoritmo utilizzato dalle libc.

Se io faccio free, viene effettivamente liberata la memoria? In tutte le condizioni possibili?

Non necessariamente, viene marcata "libera" nell'heap.

Se faccio
int* p = malloc(4)
int* p2 = malloc(4)
int* p3 = malloc(4)
e poi faccio
free(p2)
vedo EFFFETTIVAMENTE quell'area di memoria libera, oppure il sistema operativo non la libera dato che non è contigua?

Come sopra.
Visto che le allocazioni sono piccole, probabilmente ti troverai con un "buco" di 4 byte nell'heap, pronto per le allocazioni successive.

Dipende dal sistema operativo come e quanta memoria si alloca/libera? Se sì, come si comporta Linux?

Due modi (un terzo è caduto in disuso):
1) brk()
2) mmap(MAP_ANONYMOUS)
Vengono invocate automaticamente dalle libc quando necessario. Non azzardarti a toccare brk manualmente.
Una mmap esplicita può essere utile se devi allocare un blocco enorme di indirizzi _virtuali_ (continuo fino alla nausea a ripetere che sono diversi dalla memoria fisicamente assegnata al programma); le libc dovrebbero però fare lo stesso in questo caso.

I problemi di frammentazione esistono? Vi è mai capitato di affrontarli?

Una volta, sotto Delphi. Tanto tempo fa.

Quali sono le cause, secondo la vostra esperienza, di allocazioni maggiori del previsto, ESCLUDENDO puntatori allocati ma non liberati?

Se allochi parecchia memoria ma non la usi, non sottrai memoria _fisica_ al sistema, ma sottrai indirizzi virtuali al tuo programma.

Perchè la documentazione di realloc dice che il puntatore allocato è lo stesso, mentre nella realtà ciò sembra non avvenire?

Il puntatore restituito può essere ovviamente diverso, se non è possibile espandere il blocco corrente ma occorre migrarlo in qualche "buco" più capiente dell'heap.
La documentazione mi sembra chiara.

Con poche possibilità di errore, ho scoperto che dovrei occupare poco più di 1,5 Gb, mentre alla fine la memoria arriva a 2020 Mb.

E' un possibile effetto della frammentazione, questo valore dovrebbe stabilizzarsi a regime.
Nota che lo stack non gioca alcun ruolo nella frammentazione.
Preoccupati degli indirizzi virtuali occupati dal programma; cat /proc/<pid>/maps ti aiuta.

[71104]

Originariamente inviato da Scoperchiatore

Argomento del thread: vita, morte e miracoli dell'allocazione di memoria in C

argomento inesistente: lo standard non specifica nulla in merito all'implementazione.

[*]Come funziona a basso livello? [Usa il buddy system? Alloca solo blocchi a potenze di due? Alloca a pagine?

no, no e no; dove "no" sta per "non è detto"

[*]Se io faccio free, viene effettivamente liberata la memoria?

non è detto

[*]Se faccio
int* p = malloc(4)
int* p2 = malloc(4)
int* p3 = malloc(4)
e poi faccio
free(p2)
vedo EFFFETTIVAMENTE quell'area di memoria libera, oppure il sistema operativo non la libera dato che non è contigua?

forse intendevi dire "dato che se la liberassi non sarebbe più contigua", ma la risposta è sempre la stessa: non si sa.

[*]Dipende dal sistema operativo come e quanta memoria si alloca/libera?

la gestione della memoria è affidata alla piattaforma nel suo complesso

[*]I problemi di frammentazione esistono?

necessariamente

Vi è mai capitato di affrontarli?

si possono ignorare nel 95% delle situazioni, anche grazie all'hardware di oggi

[*]Quali sono le cause, secondo la vostra esperienza, di allocazioni maggiori del previsto,

?
spiegati...

[*]Perchè la documentazione di realloc dice che il puntatore allocato è lo stesso, mentre nella realtà ciò sembra non avvenire?

infatti non dice nulla del genere; quotami quello che hai letto

[...]Il programma è veloce (2 ore) ma spreme la memoria: arriva a chiedere il massimo allocabile, 3,2 Gb.

per curiosità, questo su Linux o su Windows con l'opzione di avvio /3GB ?

Diminuendo l'input, mi sono fatto il calcolo delle strutture dati allocate, in modo preciso e pedissequo, a partire dalle statistiche che il programma stesso stampa.
Con poche possibilità di errore, ho scoperto che dovrei occupare poco più di 1,5 Gb, mentre alla fine la memoria arriva a 2020 Mb.

dove hai letto quest'ultimo valore?

Se si parte dal presupposto che puntatori non liberati ed inutili non ce ne sono, perchè tutto il programma fa 4 malloc, e sono ipercontrollate, allora il dubbio è che le free e le deallocazioni dallo stack non rilascino effettivamente la memoria, magari per problemi di frammentazione.

o magari hai dimenticato di aggiungere nel tuo calcolo una marea di roba come codice e dati del tuo eseguibile e delle librerie di sistema, nonché stack di tutti i thread.

Tenete presente che il programma alloca ad ogni iterazoine parecchi dati sullo stack delle varie funzioncine (cose del tipo char linea[MAX_LINE] e char delim[]=".,-/" per capirsi), e facendo sicuramente molte migliaia di iterazioni, se quelli non sono realmente deallocati, il problema si pone!

non so su Linux, ma su Windows le pagine di stack non ancora allocate sono comunque riservate, quindi consumano spazio ugualmente.

e comunque su qualsiasi sistema Intel con paginazione, la deallocazione dallo stack non ti fa guadagnare spazio finché non scendi sotto il prossimo page bound, e su molte implementazioni non te ne fa guadagnare comunque. la dimensione dello stack è sempre un multiplo di 0x1000.

[wireless]

[OT, sono un amico di scoperchiatore]
e comprati sti 4 giga di ram, a purciaro! Stai a risolve' un problema np completo e pensi alla ram (si, lo so che sei troppo forte e trovi pure er tempo pe' la ram...)!
[/fine OT]