Por qué la memoria virtual lo cambia todo en un arena allocator.
El arena anterior hacía un solo malloc y listo; este le habla directamente al kernel sobre espacio de direcciones virtuales y memoria física como dos cosas separadas — y ese único cambio es lo que hace que el diseño realmente escale.
Si alguna vez escribiste un parser, un juego, o un compilador, te chocaste con la misma pared: no sabés qué tan grande tiene que ser el arena. Elegís un megabyte y desbordás con un input grande. Elegís un gigabyte y le diste al SO un gigabyte de RAM que casi nunca vas a usar. Redimensionar un bump allocator implica copiar todo, lo cual hace que los punteros hacia adentro queden colgando.
La memoria virtual disuelve el dilema. Los sistemas operativos modernos separan dos cosas que malloc mezcla:
- Espacio de direcciones — un rango de direcciones virtuales, indistinguible de memoria "real" para el programa. Prácticamente gratis; en una máquina de 64 bits podés reservar gigabytes.
- Memoria física — páginas de RAM reales mapeadas debajo de esas direcciones. Costosa; sólo lo que tocaste cuenta contra tu RSS.
El primer arena prometía: un bloque grande, sin resize, sin copia. Este promete lo mismo — pero el bloque puede ser enorme y no pagás por él hasta que lo llenás.
Dos operaciones, un mismo rango de direcciones.
Reservar reclama direcciones virtuales sin RAM; commitear mapea RAM debajo de direcciones previamente reservadas. Decommitear devuelve la RAM pero mantiene las direcciones; release tira las dos cosas.
| Operación | Espacio de direcciones | RAM física | Costo |
|---|---|---|---|
| reserve | reclamado | ninguna | unos pocos bytes de contabilidad en el kernel |
| commit | se mantiene | mapeada | los bytes que commiteás, cargados a tu RSS |
| decommit | se mantiene | liberada | el RSS baja; las direcciones siguen reservadas |
| release | liberado | liberada | todo vuelve al SO |
arrancando desde un rango recién reservado, vacío
La contabilidad del arena sigue viviendo en el byte 0 — sólo que ahora se apoya en otra memoria.
La struct mem_arena sigue estando al principio del bloque; la diferencia es que el bloque ahora abarca un rango enorme de direcciones virtuales, del cual sólo las primeras páginas son reales.
reserve_size = 1 GiB → espacio de direcciones virtuales, todavía sin RAM commit_size = 1 MiB → RAM física mapeada al arrancar [ mem_arena | 1 MiB committed | ......... 1 GiB reserved but no RAM yet ......... ] ^ ^ ^ ^ header base position commit_position end
El header rastrea cuatro valores: reserve_size, commit_size, position (lo que ve el usuario), y commit_position (lo que ve el SO). Dos cursores en vez de uno — su trabajo es no desacordar jamás.
El header, los macros, los prototipos de la capa de plataforma.
#ifndef _ARENA_H
#define _ARENA_H
#include <stdint.h>
typedef int8_t i8; typedef int16_t i16;
typedef int32_t i32; typedef int64_t i64;
typedef uint8_t u8; typedef uint16_t u16;
typedef uint32_t u32; typedef uint64_t u64;
typedef i8 b8; typedef i32 b32;
#define KiB(n) ((u64)(n) << 10)
#define MiB(n) ((u64)(n) << 20)
#define GiB(n) ((u64)(n) << 30)
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ALING_UP_POW2(n, p) (((u64)(n) + (u64)(p) - 1) & (~((u64)(p) - 1)))
typedef struct {
u64 reserve_size; // total reserved virtual address space
u64 commit_size; // commit granularity (typically the page size)
u64 position; // bump cursor — what the user sees
u64 commit_position; // how far we've committed — what the OS sees
} mem_arena;
#define ARENA_BASE_POSITION (sizeof(mem_arena))
#define ARENA_ALING (sizeof(void *))
#define PUSH_STRUCT(arena, T) (T*)arena_push((arena), sizeof(T), false)
#define PUSH_STRUCT_NZ(arena, T) (T*)arena_push((arena), sizeof(T), true)
#define PUSH_ARRAY(arena, T, n) (T*)arena_push((arena), (n)*sizeof(T), false)
#define PUSH_ARRAY_NZ(arena, T, n) (T*)arena_push((arena), (n)*sizeof(T), true)
u32 plat_get_pagesize(void);
void *plat_mem_reserve (u64 size);
b32 plat_mem_commit (void *ptr, u64 size);
b32 plat_mem_decommit(void *ptr, u64 size);
b32 plat_mem_release (void *ptr, u64 size);
#endifCinco funciones que esconden al SO.
El arena es neutral respecto a la plataforma; un adaptador chiquito abajo mapea reserve / commit / decommit / release a mmap en POSIX y VirtualAlloc en Windows.
#include <sys/mman.h>
#include <unistd.h>
u32 plat_get_pagesize(void) { return getpagesize(); }
void *plat_mem_reserve(u64 size) {
// PROT_NONE: claim the addresses, can't read/write yet.
return mmap(NULL, size, PROT_NONE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
}
b32 plat_mem_commit(void *ptr, u64 size) {
return mprotect(ptr, size, PROT_READ | PROT_WRITE) == 0;
}
b32 plat_mem_decommit(void *ptr, u64 size) {
return mprotect(ptr, size, PROT_NONE) == 0;
}
b32 plat_mem_release(void *ptr, u64 size) {
return munmap(ptr, size) == 0;
}#include <windows.h>
u32 plat_get_pagesize(void) {
SYSTEM_INFO sysinfo = {0};
GetSystemInfo(&sysinfo);
return sysinfo.dwPageSize;
}
void *plat_mem_reserve(u64 size) {
return VirtualAlloc(NULL, size, MEM_RESERVE, PAGE_READWRITE);
}
b32 plat_mem_commit(void *ptr, u64 size) {
return VirtualAlloc(ptr, size, MEM_COMMIT, PAGE_READWRITE) != NULL;
}
b32 plat_mem_decommit(void *ptr, u64 size) {
return VirtualFree(ptr, size, MEM_DECOMMIT);
}
b32 plat_mem_release(void *ptr, u64 size) {
return VirtualFree(ptr, 0, MEM_RELEASE);
}El arena no sabe en qué plataforma está, y la plataforma no sabe nada de arenas. Cinco funciones, un ABI, todo el problema de portabilidad resuelto en la costura donde es más chico.
Reservá grande, commiteá chico, escribí el header.
mem_arena *arena_create(u64 reserve_size, u64 commit_size) {
u32 pagesize = plat_get_pagesize();
reserve_size = ALING_UP_POW2(reserve_size, pagesize);
commit_size = ALING_UP_POW2(commit_size, pagesize);
mem_arena *arena = plat_mem_reserve(reserve_size);
if (!plat_mem_commit(arena, commit_size)) {
return NULL;
}
arena->reserve_size = reserve_size;
arena->commit_size = commit_size;
arena->position = ARENA_BASE_POSITION;
arena->commit_position = commit_size;
return arena;
}arena_push() hace crecer el límite de commit a medida que avanza.
void *arena_push(mem_arena *arena, u64 size, b32 non_zero) {
u64 pos_aligned = ALING_UP_POW2(arena->position, ARENA_ALING);
u64 new_pos = pos_aligned + size;
if (new_pos > arena->reserve_size) {
return NULL;
}
if (new_pos > arena->commit_position) {
u64 new_commit_pos = new_pos;
new_commit_pos += arena->commit_size - 1;
new_commit_pos -= new_commit_pos % arena->commit_size;
new_commit_pos = MIN(new_commit_pos, arena->reserve_size);
u8 *mem = (u8 *)arena + arena->commit_position;
u64 commit_size = new_commit_pos - arena->commit_position;
if (!plat_mem_commit(mem, commit_size)) {
return NULL;
}
arena->commit_position = new_commit_pos;
}
arena->position = new_pos;
u8 *out = (u8 *)arena + pos_aligned;
if (!non_zero) {
memset(out, 0, size);
}
return out;
}El camino rápido — el push entra en páginas ya commiteadas — es un bump puro. El camino lento sólo corre en el primer push que necesita cada página nueva, amortizado entre los muchos pushes que vienen después.
Por qué cada push redondea hacia arriba a sizeof(void *).
En x86-64, leer un entero de 8 bytes desde una dirección que no es múltiplo de 8 fuerza dos accesos a la línea de caché. En ARM, esa misma lectura levanta un SIGBUS. El alineamiento es un contrato de hardware, no una preferencia de estilo. ARENA_ALING = sizeof(void *) cubre todos los tipos escalares estándar.
#define ALING_UP_POW2(n, p) (((u64)(n) + (u64)(p) - 1) & (~((u64)(p) - 1)))n = 0 → 7 & ~7 = 0 n = 1 → 8 & ~7 = 8 n = 7 → 14 & ~7 = 8 n = 9 → 16 & ~7 = 16 n = 17 → 24 & ~7 = 24
Mové el cursor hacia atrás sin cruzar jamás el header.
void arena_pop(mem_arena *arena, u64 size) {
size = MIN(size, arena->position - ARENA_BASE_POSITION);
arena->position -= size;
}
void arena_pop_to(mem_arena *arena, u64 position) {
u64 size = position < arena->position
? arena->position - position
: 0;
arena_pop(arena, size);
}arena_pop no toca commit_position. La RAM se queda mapeada — si empujás 16 MiB, hacés pop, y volvés a empujar 16 MiB, el segundo push cae en el camino rápido porque esas páginas siguen commiteadas.
Si de verdad necesitás la RAM de vuelta, construí un helper arena_decommit_above(arena, threshold) arriba de plat_mem_decommit. El primitivo está ahí; el arena simplemente elige no llamarlo.
Una línea de código, uno de los patrones más útiles en programación de sistemas.
void arena_clear(mem_arena *arena) {
arena_pop_to(arena, ARENA_BASE_POSITION);
}Como clear mantiene las páginas commiteadas, un arena que se llena una vez y se limpia repetidamente nunca vuelve a pagar el costo del commit. El primer frame es caro. Cada frame siguiente es un único store a position.
Dos arenas, un programa: un perm_arena que vive toda la corrida, y un frame_arena al que le hacés arena_clear en cada iteración del loop.
Un syscall y toda la región desaparece.
void arena_destroy(mem_arena *arena) {
plat_mem_release(arena, arena->reserve_size);
}En Linux eso es un único munmap; en Windows es un único VirtualFree(_, 0, MEM_RELEASE). El espacio de direcciones vuelve al kernel, las páginas commiteadas se decommitean en la misma operación, y cada puntero que alguna vez salió de arena_push queda inválido al mismo tiempo.
Macros ergonómicos sobre arena_push.
typedef struct { f32 x, y, z; } v3;
mem_arena *arena = arena_create(GiB(1), MiB(1));
v3 *origin = PUSH_STRUCT(arena, v3); // v3 en cero
v3 *cloud = PUSH_ARRAY(arena, v3, 1024); // 1024 v3 en cero
char *buf = PUSH_ARRAY_NZ(arena, char, 4096); // sin el memsetLas variantes _NZ se saltean el memset cuando de todas formas vas a sobreescribir todo el bloque.
Viendo crecer el arena en htop.
int main(void) {
mem_arena *perm_arena = arena_create(GiB(1), MiB(1));
while (true) {
arena_push(perm_arena, MiB(16), false);
getc(stdin); // wait for enter to push again
}
arena_destroy(perm_arena);
}Mirá dos columnas en htop: VIRT salta a ~1 GiB al arrancar y no se mueve más; RES arranca en unos pocos MiB y crece ~16 MiB cada vez que apretás enter. Esa brecha entre las dos es la mentira que la memoria virtual le cuenta al kernel en tu nombre.
En Linux, los settings de overcommit (/proc/sys/vm/overcommit_memory) y ulimit -v pueden rechazar una reserva del tamaño de un gigabyte. Los dos se arreglan con una línea; los dos vale la pena conocerlos antes de shippear.
Compilando arena.c en Linux y Windows.
$ gcc -std=c11 -Wall -Wextra -O2 arena.c main.c -o arena_test
$ ./arena_test
# En otra terminal: htop, y mirá VIRT y RES.Este código llama a su macro ALING_UP_POW2 y a su constante ARENA_ALING — el typo sobrevive tal cual. Dejalo o arreglalo, pero elegí uno.
Lo que me enseñó esta versión.
- La interfaz entre un proceso y un kernel moderno es chica y hermosa. Reserve, commit, decommit, release. Cuatro operaciones y reemplazaste
mallocpara clases enteras de workloads. - El espacio de direcciones virtuales es un recurso igual que la RAM — pero uno mucho, mucho más barato. Los programas que actúan como si fuera gratis generalmente tienen razón.
- Dos cursores son mejores que uno. Separar "lo que ve el usuario" de "lo que ve el SO" convierte cada push en un camino rápido, y hace explícito el camino lento.
Crédito: el diseño reserve-vs-commit sigue casi al pie de la letra el artículo de Ryan Fleury "Untangling Lifetimes: The Arena Allocator". Si algo de esto te hizo click, el original es lo próximo que tenés que leer.
Preguntas frecuentes
¿Cuál es la diferencia entre reservar y commitear memoria?
Reservar memoria le pide al kernel un rango de direcciones virtuales sin respaldarlas con RAM física. Commitear memoria le dice al kernel que mapee páginas físicas reales sobre esas direcciones virtuales. Un arena construido sobre esta distinción reserva un rango enorme por adelantado, y después commitea páginas de forma lazy a medida que el cursor de posición avanza.
¿Cómo commitea memoria de forma lazy arena_push()?
arena_push redondea el tamaño pedido hacia arriba a ARENA_ALING y avanza position. Si la nueva posición pasa commit_position, redondea el nuevo objetivo hacia arriba a un múltiplo de commit_size, llama a plat_mem_commit sólo para las páginas nuevas, y actualiza commit_position. Los pushes que se quedan dentro de memoria ya commiteada se saltean el syscall por completo.
¿Por qué usar mmap / VirtualAlloc en vez de malloc?
malloc te da bytes que ya están commiteados y ya cuentan contra tu RSS. mmap y VirtualAlloc te dejan reservar un rango virtual contiguo enorme y pagar por memoria física recién cuando la tocás.
¿Qué pasa con la RAM cuando llamo a arena_pop o arena_clear?
Nada — pop y clear mueven hacia atrás el position visible para el usuario pero nunca tocan commit_position. Las páginas commiteadas se quedan mapeadas, así que los pushes siguientes caen inmediatamente en el camino rápido.
¿Qué es el alineamiento de memoria y por qué importa?
El alineamiento de memoria significa ubicar un valor en una dirección que sea múltiplo de su tamaño natural. Las lecturas desalineadas cuestan dos fetches de línea de caché en x86 y generan un trap en ARM. El ALING_UP_POW2 del arena redondea cada push hacia arriba a sizeof(void *).