Free list e riutilizzo
Tenga traccia dei blocchi e li riutilizzi.
Free list e riutilizzo è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Oltre il bump allocator
Per liberare singoli blocchi e riutilizzarli, è necessario tenere traccia delle informazioni. Una free list è una lista concatenata di blocchi disponibili che l'allocator esamina prima di acquisire memoria nuova.
Ogni blocco contiene un'intestazione, così l'allocator può trovarne la dimensione e il collegamento al blocco successivo della catena.
Intestazione del blocco con collegamento
Estendiamo l'intestazione con un puntatore next e un flag free. Insieme, questi elementi trasformano il nostro pool in una lista navigabile di blocchi.
Il payload segue immediatamente l'intestazione in memoria.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Inizializzare un unico grande blocco libero
All'avvio, l'intero pool è un enorme blocco libero. Quando avvengono le allocazioni lo dividiamo; quando avvengono le liberazioni, contrassegniamo i blocchi come riutilizzabili.
La testa della lista è questo blocco iniziale, che copre l'intera arena.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}Ricerca first-fit
La strategia di riutilizzo più semplice è first-fit: si scorre la lista e si restituisce il primo blocco libero sufficientemente grande. È veloce e tende a mantenere i blocchi piccoli vicino all'inizio.
Le alternative sono best-fit (il blocco sufficiente più piccolo) e worst-fit, che scambiano velocità e comportamento rispetto alla frammentazione.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Allocare da un blocco libero
Quando troviamo un blocco adatto, lo contrassegniamo come utilizzato e restituiamo il puntatore subito dopo la sua intestazione. Per ora assegniamo l'intero blocco; la divisione sarà trattata nella lezione successiva.
Il puntatore restituito è block + 1, nascondendo l'intestazione al chiamante.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Liberare un blocco
Per liberare un blocco, si torna indietro dal puntatore dell'utente fino alla sua intestazione e si modifica il flag free. Il blocco è ora disponibile per il riutilizzo nella ricerca successiva.
Recuperare l'intestazione dal payload è lo stesso trucco di aritmetica dei puntatori a un passo visto in precedenza.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Unire blocchi liberi adiacenti
La sola liberazione lascia il pool pieno di piccoli blocchi liberi. La coalescenza unisce un blocco liberato al blocco successivo se anche quest'ultimo è libero, ricostruendo regioni contigue più grandi.
In questo modo si contrasta la frammentazione esterna e le richieste future di grandi dimensioni possono ancora essere soddisfatte.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Una dimostrazione eseguibile della free list
Questo programma completo inizializza un pool, alloca due blocchi, libera il primo e poi lo riutilizza per una richiesta più piccola, dimostrando che la free list funziona.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}Il costo della ricerca
Una singola free list concatenata rende l'allocazione O(n) rispetto al numero di blocchi. Con molte allocazioni, questo processo diventa lento.
Gli allocator reali usano free list segregate (bin suddivisi per dimensione) o alberi per rendere la ricerca prossima a O(1). Il principio del riutilizzo rimane lo stesso.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Double free e corruzione
Contrassegnare due volte un blocco come libero, oppure scrivere oltre la dimensione del blocco, corrompe le intestazioni adiacenti. La ricerca successiva segue quindi un puntatore next spazzatura e va in crash.
È per questo che i bug di memoria in C sono così pericolosi: i metadati usati dall'allocator vivono proprio accanto ai dati.
Combinare il riutilizzo
Una free-list allocator funzionante richiede inizializzazione, una strategia di ricerca del blocco adatto, allocazione, liberazione e coalescenza. Con questi elementi, la memoria circola nel pool invece di crescere senza fine.
L'ultimo perfezionamento consiste nel dividere i blocchi sovradimensionati e rispettare l'allineamento: è l'argomento della lezione finale.
Verifica rapida
Rifletta su ciò che impedisce a una free list di frammentarsi eccessivamente.
Riepilogo
Una free list collega i blocchi tramite intestazioni, così è possibile liberare e riutilizzare singole allocazioni. La ricerca first-fit trova un blocco, la liberazione modifica un flag e la coalescenza unisce i blocchi vicini per contrastare la frammentazione.
La ricerca lineare è O(n); gli allocator di produzione raggruppano i blocchi per dimensione per aumentare la velocità. Ora aggiungeremo divisione e allineamento.
Domande Frequenti
La lezione «Free list e riutilizzo» è gratuita?
Sì — il testo completo di «Free list e riutilizzo» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Free list e riutilizzo»?
Tenga traccia dei blocchi e li riutilizzi. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Free list e riutilizzo»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Come funziona malloc
- Un semplice allocatore bump
- Free list e riutilizzo
- Allineamento e suddivisione