C Academy · Lezione

Allineamento e suddivisione

Renda i blocchi utilizzabili e ordinati.

Allineamento e suddivisione è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 4 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.

Perché l'allineamento è importante

Ogni tipo ha un requisito di allineamento: il suo indirizzo deve essere un multiplo di una potenza di due. Un double richiede in genere un allineamento di 8 byte.

Poiché malloc non sa che cosa verrà memorizzato, deve restituire puntatori allineati per il tipo con il requisito più restrittivo, generalmente 16 byte sui sistemi a 64 bit.

#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t);   /* often 16 */

Il trucco di align_up

Arrotondare una dimensione al multiplo successivo di un allineamento che sia una potenza di due è un classico trucco con i bit: si aggiunge a - 1, quindi si azzerano i bit meno significativi tramite una maschera.

Funziona solo quando a è una potenza di due, come avviene per tutti gli allineamenti reali.

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */

Verificare la matematica con un programma

Verifichiamo align_up con un programma eseguibile. Il programma arrotonda diverse dimensioni ai limiti di 8 e 16 byte e stampa i risultati.

#include <stdio.h>
#include <stddef.h>

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}

int main(void) {
    printf("%zu\n", align_up(13, 8));   /* 16 */
    printf("%zu\n", align_up(16, 8));   /* 16 */
    printf("%zu\n", align_up(1, 16));   /* 16 */
    printf("%zu\n", align_up(33, 16));  /* 48 */
    return 0;
}

Allineare le dimensioni richieste

All'interno dell'allocator, il primo passaggio di ogni richiesta consiste nell'arrotondare la dimensione richiesta fino all'allineamento. In questo modo garantiamo che anche il blocco successivo inizi allineato.

I byte di padding costituiscono una frammentazione interna, il prezzo dell'allineamento universale.

#define ALIGN 16
void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    /* now find a block of this aligned size */
    /* ... */
    return NULL;
}

Il problema del riutilizzo dell'intero blocco

Nella lezione precedente restituivamo un intero blocco libero anche per richieste minuscole. Un blocco libero di 4000 byte assegnato a una richiesta di 16 byte spreca tutto lo spazio rimanente.

La divisione separa il blocco nella parte che utilizziamo e in una parte residua che rimane libera.

Dividere un blocco

Se un blocco scelto è molto più grande del necessario, posizioniamo una nuova intestazione alla fine della regione richiesta. Lo spazio rimanente diventa un blocco libero più piccolo nella lista.

Dividiamo il blocco solo quando lo spazio residuo è abbastanza grande da contenere un'intestazione e una parte di payload; altrimenti il frammento sarebbe inutilizzabile.

void split(block_t *b, size_t size) {
    size_t rem = b->size - size;
    if (rem < sizeof(block_t) + ALIGN) return; /* too small */
    block_t *nb = (block_t *)((char *)(b + 1) + size);
    nb->size = rem - sizeof(block_t);
    nb->free = 1;
    nb->next = b->next;
    b->size = size;
    b->next = nb;
}

Allocare, allineare, dividere

Ora il percorso completo dell'allocazione allinea la dimensione, trova un blocco adatto, separa l'eventuale spazio residuo abbastanza grande e contrassegna il blocco come utilizzato.

In questo modo i blocchi mantengono dimensioni precise e lasciano spazio libero utilizzabile.

void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    block_t *b = first_fit(size);
    if (!b) return NULL;
    split(b, size);
    b->free = 0;
    return (void *)(b + 1);
}

Mantenere allineato il pool

Per la correttezza, anche l'indirizzo iniziale del pool e la dimensione dell'intestazione devono rispettare l'allineamento, così ogni payload si trova su un limite valido.

L'uso di alignas sul buffer statico garantisce che l'intero schema inizi allineato.

#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */

Un'allocazione allineata eseguibile

Questo programma alloca da un pool allineato e stampa l'indirizzo restituito modulo 16, mostrando che il risultato è sempre zero, cioè correttamente allineato.

#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>

static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;

void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }

int main(void){
    void *a = alloc16(1);
    void *b = alloc16(20);
    printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
    printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
    return 0;
}

Divisione e coalescenza

Divisione e coalescenza sono operazioni opposte che si bilanciano a vicenda. L'allocazione divide i blocchi grandi; la liberazione riunisce i blocchi piccoli.

Insieme permettono allo stesso pool di gestire una combinazione variabile di dimensioni richieste senza perdere spazio né frammentarsi in modo permanente.

Da prototipo ad allocator reale

Ora dispone di tutti e quattro i pilastri: una sorgente di memoria, intestazioni allineate, riutilizzo tramite free list con coalescenza e divisione. Gli allocator reali aggiungono bin per classi di dimensione, cache per i thread e integrazione con il sistema operativo per ottenere velocità e scalabilità.

Tuttavia, le idee fondamentali sviluppate qui sono alla base di ogni implementazione di malloc.

Verifica rapida

Consideri perché i blocchi vengono divisi durante l'allocazione.

Riepilogo

L'allineamento arrotonda le dimensioni verso l'alto con il trucco sui bit (n + a - 1) & ~(a - 1), così ogni payload è adatto a qualsiasi tipo. La divisione ritaglia dai blocchi liberi sovradimensionati una parte utilizzata e una parte residua libera, mentre la coalescenza esegue l'operazione inversa durante la liberazione.

Insieme, questi quattro pilastri formano un allocator di memoria completo e corretto.

Domande Frequenti

La lezione «Allineamento e suddivisione» è gratuita?

Sì — il testo completo di «Allineamento e suddivisione» è 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 «Allineamento e suddivisione»?

Renda i blocchi utilizzabili e ordinati. 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 4 di 4.

Quanto tempo richiede la lezione «Allineamento e suddivisione»?

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

← Torna a C Academy