13.4 Arena, pool és region lifetime

Egy kérés feldolgozásakor a parser gyakran sok apró, rövid életű objektumot hoz létre: tokeneket, szintaxisfa-csomópontokat és ideiglenes másolatokat. Ha ezekre ugyanaddig van szükség, az egyenkénti malloc–free kezelés helyett célszerű közös régióhoz (region) kötni őket. A feldolgozás végén az egész régió felszabadítható.

Az aréna (arena) ilyen közös életciklusú allokációkat szolgál ki. A pool ezzel szemben tipikusan azonos típusú vagy méretű elemek helyeit hasznosítja újra, egyenkénti visszaadással. A választás elsődleges szempontja tehát nem a sebességígéret, hanem az élettartam.

Az igazítás szabályaira, az explicit tulajdonlási szerződésre, valamint a sizeof és az igazítás kapcsolatára építünk. A következő megoldás ISO C17-et használ; nem támaszkodik POSIX- vagy Linux-specifikus API-ra.

13.4.1 A régió élettartama és szerződése

Az itt megvalósított aréna egymáshoz láncolt tárolóblokkokból, úgynevezett chunkokból áll. Egy chunkon belül az új objektum helyét egy monoton növekvő foglalási pozíció, a bump pointer elve határozza meg. Ezt cím helyett size_t eltolással tároljuk.

Az API szerződése:

• az arénát nullára inicializált állapotból használjuk;
• az aréna objektuma kizárólagos tulajdonosa a chunkoknak;
• a visszaadott pointerek kölcsönzött hozzáférések, külön nem adhatók át free-nek;
• új chunk létrehozása nem mozgatja a korábbi objektumokat;
• a teljes reset minden chunkot felszabadít, így minden korábban kapott pointert érvénytelenít;
• sikertelen foglaláskor az aréna és a korábbi allokációk változatlanok.

Az aréna vezérlőobjektumának hatókörből kilépése nem szabadítja fel automatikusan a chunkokat. Előtte reset szükséges. Ha a parser eredménye túléli a kérést, vagy külön tárolóba kell másolni, vagy az egész aréna tulajdonlását kell szabályosan átadni.

13.4.2 Bump pointer és igazítás

Legyen egy chunk kapacitása $C$, foglalt előtagjának hossza $u$, a kért méret $n$, az igazítás pedig $a$. Minden mennyiség C bájtban értendő; egy C bájt bitszáma CHAR_BIT.

Az alapinvariáns:

$$0 \le u \le C.$$

Feltesszük, hogy a chunk kezdőcíme megfelel az $a$ igazításnak. A következő megfelelő eltoláshoz szükséges padding:

$$r=u\bmod a, \qquad p= \begin{cases} 0, & r=0,\\ a-r, & r\ne0. \end{cases}$$

A foglalás kezdete $u+p$, új foglalási pozíciója $u+p+n$. Ezeket azonban csak azután számítjuk ki, hogy igazoltuk:

$$p\le C-u \quad\text{és}\quad n\le C-u-p.$$

Így az ellenőrzést nem előzi meg túlcsorduló összeadás. A tömör (u + a - 1) / a * a képlet ellenőrizetlenül veszélyes.

Kidolgozott számpélda. Egy feltételezett, megfelelően igazított chunkban legyen $C=64$, $u=13$, $a=8$, $n=16$. Ekkor $r=5$, $p=3$. A fennmaradó hely $51$, ezért $3\le51$ és $16\le48$. Az objektum a 16-os eltolásnál kezdődik, az új pozíció 32. Ez aritmetikai illusztráció, nem mért memórialayout.

Bizonyításvázlat. A konstrukció miatt $(u+p)\bmod a=0$. A két méretellenőrzésből $u+p+n\le C$ következik, ezért a foglalás a chunkon belül marad. Az új foglalás a korábbi foglalt előtag után kezdődik, tehát a korábbi allokációkkal sem fed át.

13.4.3 Alignmentbiztos, növekvő aréna

ISO C17: a malloc által adott tároló megfelelően igazított a fundamentális igazítási követelményű típusok számára. A példánk csak ilyen típusokat támogat: a hívó _Alignof(T) értéket ad át, amely nem nagyobb _Alignof(max_align_t) értékénél. A kiterjesztett, túlzott igazítású típusok külön megoldást igényelnek.

A chunk fejlécét és adattárolóját külön allokáljuk. Ez chunkonként két allokáció, viszont az adatkezdő cím igazítását nem kell egy fejléc utáni eltolással korrigálni. A malloc-kal kapott adattárolónak nincs deklarált típusa; a unsigned char * itt a címszámítást szolgálja. A kliens a megfelelően igazított helyen típushelyes írással inicializálja az objektumokat.

Az alábbi teljes fájl neve arena.c. Minden arénaparaméternek élő, írható objektumra kell mutatnia; párhuzamos hozzáférés nincs megengedve.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

struct chunk {
    struct chunk *next;
    unsigned char *data;
    size_t capacity;
    size_t used;
};

struct arena {
    struct chunk *head;
};

/* NULL: nulla meret, nem tamogatott igazitas, overflow vagy OOM.
   Hiba eseten az arena valtozatlan. */
static void *arena_alloc(struct arena *a, size_t count,
                         size_t element_size, size_t alignment)
{
    const size_t base_alignment = _Alignof(max_align_t);

    if (count == 0 || element_size == 0 ||
        alignment == 0 || alignment > base_alignment ||
        base_alignment % alignment != 0) {
        return NULL;
    }

    if (count > SIZE_MAX / element_size) {
        return NULL;
    }
    const size_t n = count * element_size;

    struct chunk *c = a->head;
    if (c != NULL) {
        const size_t remainder = c->used % alignment;
        const size_t padding =
            remainder == 0 ? 0 : alignment - remainder;
        const size_t remaining = c->capacity - c->used;

        if (padding <= remaining && n <= remaining - padding) {
            const size_t start = c->used + padding;
            c->used = start + n;
            return c->data + start;
        }
    }

    size_t capacity = 1024;
    if (c != NULL) {
        capacity = c->capacity <= SIZE_MAX / 2
                 ? c->capacity * 2
                 : SIZE_MAX;
    }
    if (capacity < n) {
        capacity = n;
    }

    struct chunk *fresh = malloc(sizeof *fresh);
    if (fresh == NULL) {
        return NULL;
    }

    unsigned char *data = malloc(capacity);
    if (data == NULL) {
        free(fresh);
        return NULL;
    }

    *fresh = (struct chunk) {
        .next = a->head,
        .data = data,
        .capacity = capacity,
        .used = n
    };
    a->head = fresh;
    return data;
}

/* Minden korabban visszaadott pointert ervenytelenit. */
static void arena_reset(struct arena *a)
{
    while (a->head != NULL) {
        struct chunk *c = a->head;
        a->head = c->next;
        free(c->data);
        free(c);
    }
}

struct token {
    size_t begin;
    size_t length;
};

int main(void)
{
    struct arena scratch = {0};

    struct token *tokens = arena_alloc(
        &scratch, 2, sizeof *tokens, _Alignof(struct token));

    if (tokens == NULL) {
        arena_reset(&scratch);
        return EXIT_FAILURE;
    }

    tokens[0] = (struct token){ .begin = 0, .length = 4 };
    tokens[1] = (struct token){ .begin = 5, .length = 3 };

    void *extra = arena_alloc(
        &scratch, 2048, sizeof(unsigned char),
        _Alignof(unsigned char));

    if (extra == NULL) {
        arena_reset(&scratch);
        return EXIT_FAILURE;
    }

    assert(tokens[0].length == 4);
    arena_reset(&scratch);
    assert(scratch.head == NULL);

    /* tokens es extra innen nem hasznalhato. */
    return EXIT_SUCCESS;
}

Javasolt, külön ellenőrizendő laborprofil: Linux x86-64, System V ABI, LP64, GCC 14.2.0 vagy Clang 19.1.7, glibc 2.40. A példa nem függ e konkrét ABI méreteitől. A fordítási parancsok önálló laborhoz tartoznak; itt nincs hozzájuk közölt futtatási eredmény.

gcc -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -O1 -g -fsanitize=address,undefined arena.c -o arena-gcc

clang -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -O1 -g -fsanitize=address,undefined arena.c -o arena-clang

A count * element_size szorzás előtt osztásos korlátellenőrzés történik. A növekedés rendszerint kétszerezés, nagy kérésnél közvetlenül a szükséges kapacitást választjuk. A kétszerezést külön túlcsordulás-ellenőrzés védi.

Új chunkban a foglalás a megfelelően igazított kezdőcímen indul, ezért ott nem szükséges n + alignment - 1 méretet kérni. A régi chunkokat nem realloc-áljuk: ez őrzi meg a korábbi pointerek érvényességét.

A meglévő chunkból történő foglalás $O(1)$ saját műveletet végez, külső allokáció nélkül. A növekedés költségéhez viszont hozzátartozik a két malloc; ezek késleltetésére nem adunk konstans idejű garanciát. Az egymás utáni objektumok lokalitása jó lehet, de padding és kihasználatlan chunkvégek maradnak. A reset $k$ chunk esetén $O(k)$ bejárást és $2k$ felszabadító hívást végez.

13.4.4 Pool és free list: egyenkénti újrafelhasználás

A szabadlista (free list) a pool éppen elérhető helyeit láncolja össze. Foglaláskor levesszük az első helyet; visszaadáskor visszafűzzük. Mindkettő $O(1)$ saját művelet, ha a pool már rendelkezik tárolóval.

A következő C17-deklarációrészlet az előző struct token definíciójára épül:

struct token_slot {
    struct token value;
    struct token_slot *next_free;
};

struct token_pool {
    struct token_slot slots[16];
    struct token_slot *free_head;
};

A struct és a tömb nyelvi szabályai gondoskodnak az elemek igazításáról és szükséges paddingjéről. A szabadlista metaadata külön tagban van: nem írunk egy tetszőleges objektum elejére pointert.

A pool inicializálásakor mind a 16 helyet a szabadlistába kell láncolni. Foglaláskor egy struct token_slot * kezelő adható vissza, amelynek value tagját a kliens inicializálja. Üres listánál a hibakimenet NULL; visszaadáskor a hely csak akkor fűzhető vissza, ha ehhez a poolhoz tartozik és jelenleg ki van adva.

A típus nélküli pool ennél nehezebb: a slot méretének a payloadot és a szabadlista-pointert is be kell fogadnia, a kezdőcímet és a lépésközt pedig mindkettőhöz igazítani kell. Az effective type szabályait sem helyettesíti egy pointercast.

A pool tulajdonosa a teljes slottömb tulajdonosa. A kiadott hozzáférés a visszaadásig érvényes. Visszaadáskor a kölcsönzés API szerint megszűnik, noha ebben a deklarált tömbös megoldásban maga a C objektum tovább él. A későbbi hozzáférés így szerződéssértés lehet akkor is, ha memóriadiagnosztika nem jelzi.

13.4.5 Reset, erőforrások és szálbiztonság

ISO C17: a free nem hív objektumdestruktort. Ha egy arénában tárolt rekord fájlt, socketet vagy külön allokált memóriát birtokol, a rekord tárolójának felszabadítása nem zárja le ezeket.

A helyes sorrend:

1. megszüntetjük az új hozzáférések lehetőségét;
2. lezárjuk a rekordok által birtokolt külső erőforrásokat;
3. végrehajtjuk a resetet.

Cleanup-lista használható, de annak elemei és bejárási adatai is éljenek a takarítás végéig. Egy cleanup-hiba kezelését külön kell meghatározni; a memóriatakarítás nem jelent automatikusan sikeres erőforráslezárást.

Az aréna nem szálbiztos: a head és a used módosítása szinkronizálatlan konkurens hozzáférés esetén adatversenyhez vezethet. Praktikus megoldás a kérésenkénti aréna (per-request arena), amelynek egyszerre egy végrehajtója van. Ha a kérés objektumait több szál olvassa, reset előtt minden olvasónak be kell fejeznie a hozzáférést. Csak a foglalást mutexszel védeni nem elegendő.

Gyakori hiba az aréna érték szerinti másolása: ezzel két vezérlőobjektum ugyanazokat a chunkokat tekinti sajátjának. Ugyancsak hibás az egyedi free, a reset utáni pointerhasználat, illetve a poolhely kétszeri visszaadása. Ezeket a tulajdonlási szerződésnek kell kizárnia, nem a szerencsés futási eredménynek.

13.4.6 Feladatok

1. Magyarázó: Egy chunk kapacitása 48, foglalási pozíciója 19. Befér-e egy 24 C bájtos, 8-as igazítású objektum? Mi történik 25 C bájtos kérésnél?
2. Kódolási: Írj token_array wrappert, amely n tokennek kér megfelelően igazított tárolót, majd minden tokent inicializál!
3. Diagnosztikai: Egy worker arénában épít tokentömböt, átadja pointerét egy eredménysornak, majd resetel. Miért nem elég, hogy a sor mutexszel védett? Adj két javítást!

13.4.7 Megoldások

13.4.7.1 Igazított foglalás

$19\bmod8=3$, ezért a padding 5. A fennmaradó hely $48-19=29$, ebből igazítás után 24 használható.

A 24 C bájtos kérés pontosan befér: kezdete 24, vége 48. A 25 C bájtos nem fér be, ezért új chunk szükséges. Ellenőrzési feltétel: a végpozíció legfeljebb a kapacitás, a kezdőpozíció osztható az igazítással.

13.4.7.2 Inicializáló wrapper

C17-részlet az előző teljes példához:

static struct token *token_array(struct arena *a, size_t n)
{
    struct token *p = arena_alloc(
        a, n, sizeof *p, _Alignof(struct token));

    if (p == NULL) {
        return NULL;
    }

    for (size_t i = 0; i < n; ++i) {
        p[i] = (struct token){ .begin = 0, .length = 0 };
    }
    return p;
}

A tulajdonos továbbra is az aréna; a wrapper nem ad önálló ownershipet. Reset minden visszaadott pointert érvénytelenít. Nulla elemszám, túlcsordulás vagy allokációs hiba esetén NULL az eredmény.

Ellenőrizendő a nulla elemszám, a helyes mezőinicializálás, valamint — ha reprezentálható — a SIZE_MAX / sizeof(struct token) + 1 elemszám visszautasítása.

13.4.7.3 Eredménysor és élettartam

A mutex a sor műveleteit védi, nem hosszabbítja meg a tokenek tárolójának élettartamát. A fogyasztó reset után már felszabadított tárolóra hivatkozna.

Az egyik javítás a tokenek átmásolása a sor által birtokolt tárolóba. A másik a teljes aréna kizárólagos tulajdonlásának átadása, majd reset a fogyasztó befejezése után. Utóbbi nem egyszerű másolás: a korábbi tulajdonosnak le kell mondania a chunkokról.

Ellenőrzési feltétel: a fogyasztó utolsó hozzáférése előzze meg a tároló felszabadítását.

13.4.8 Összefoglalás

Arénát közös élettartamú objektumokhoz, poolt egyenként újrafelhasznált helyekhez válassz. A biztonságos aréna ellenőrzi az igazítást és a méretszámítást, növekedéskor nem mozgatja a korábbi objektumokat, resetkor pedig minden kölcsönzést megszüntet. A memória felszabadítása, a külső erőforrások lezárása és a konkurens hozzáférések befejezése három külön felelősség.