Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Audit dlmalloc — distillation pour l’allocateur global Air

Note de travail (2026-06-30). Objectif : étudier le design de dlmalloc pour outiller la décision BDFL — ne pas vendorer en boîte noire, ne pas réinventer, mais s’inspirer d’un design éprouvé en restant simple et posséder la politique Air au-dessus. Source lue : crate rust-lang/dlmalloc-rs v0.2.14 (le port Rust no_std que la std utilise comme allocateur par défaut de wasm32-unknown-unknown), inspection statique de src/{lib,dlmalloc,unix,global}.rs — aucun build d’allocateur lancé. Concepts canoniques rapportés à Doug Lea’s malloc (dlmalloc.c, domaine public). Cette note ne tranche rien : l’ADR sera rédigé en session après elle.

0. Pourquoi cet audit

Air a besoin d’un allocateur global couche 1 (core::alloc::GlobalAlloc, no_std, thread-safe, adossé à mmap). Il remplacera le placeholder AbortOnAlloc (rt/crates/air-rt/src/lib.rs : tout alloc ⇒ exit_process(102), jamais invoqué car le bootstrap selftest n’alloue pas) et, à terme, deviendra le malloc/free/realloc de la libc C-ABI Air (ADR-046/047, famille stdlib/malloc, cible pilote OpenSSH).

La décision de design retenue par le BDFL est : inspiration, pas vendoring ni réinvention. Cette note sépare donc, sur du concret lu dans la source, le cœur à emprunter (correction) de ce qui se simplifie (optimisations), puis décrit la politique Air qu’on greffe par-dessus (fork-gardien, instrumentation, fail-not-hang).

1. Comment dlmalloc fonctionne (concis et juste)

Le chunk et les boundary tags. L’unité est le Chunk (#[repr(C)]) :

#![allow(unused)]
fn main() {
struct Chunk { prev_foot: usize, head: usize, prev: *mut Chunk, next: *mut Chunk }
}
  • head = taille | bits de flag (3 bits bas : PINUSE=prev occupé, CINUSE=ce chunk occupé, FLAG4). La taille est masquée par head & !FLAG_BITS.
  • prev_foot = footer : recopie la taille du chunk précédent quand celui-ci est libre (lu seulement si PINUSE est à 0). C’est la boundary tag qui permet de remonter au voisin gauche en O(1).
  • prev/next ne servent qu’aux chunks libres : ils chaînent les free-lists et occupent en-bande la zone de payload du chunk libre (métadonnées intrusives, zéro structure annexe). La mémoire utilisateur commence à mem_offset = 2*size_of::<usize>().

Où vit la taille → la réponse au free(ptr) C-ABI. free(mem) ne reçoit pas la taille. dlmalloc la retrouve depuis l’en-tête : from_mem(mem) = mem − 2*usize, puis size = head & !FLAG_BITS. C’est exactement le contrat C : la taille est stockée par bloc, juste avant le pointeur rendu. (overhead réel = 1 usize par chunk occupé, le prev_foot du voisin servant de footer — astuce classique de Lea.)

Coalescence O(1). À la libération, pinuse/cinuse + prev_foot donnent immédiatement l’état des deux voisins ; dispose_chunk/free fusionnent gauche et droite sans parcours, mettent à jour les boundary tags, et rebinnent le chunk fusionné.

Bins par classe de taille. Deux familles, chacune indexée par un bitmap u32 qui donne en O(1) la plus petite bin non vide (least_bit/trailing_zeros) :

  • 32 smallbins (smallmap) : classes exactes espacées de 8 octets (SMALLBIN_SHIFT=3), listes doublement chaînées circulaires. Couvre < 256 octets.
  • 32 treebins (treemap) pour les grands (>= min_large_size = 1<<8 = 256). Chaque treebin est un trie digital bit-à-bit (TreeChunk { chunk, child[2], parent, index }) indexé par les bits de poids fort de la taille ; les chunks de taille identique sont chaînés en liste sur le nœud. C’est le fameux treemap — recherche best-fit en O(log) sur la plage de tailles, pas O(n).

dv et top. dv (designated victim) = dernier reliquat de split, réutilisé en priorité pour les petites demandes (réduit la fragmentation). top (wilderness) = chunk frontière adossé à la mémoire système ; on y taille quand aucune bin ne convient.

Trait système (sbrk/mmap abstrait). dlmalloc-rs isole l’OS derrière un trait Allocator (alloc(size) -> (base, size, flags), remap, free_part, free, page_size, allocates_zeros, …). L’impl unix.rs utilise mmap(MAP_ANON|MAP_PRIVATE) / munmap / mremap, page_size() câblé à 4096. sys_alloc arrondit demande + top_foot + align à la granularité (64 Kio par défaut), demande un gros bloc au système, l’enregistre comme segment, étend top, puis taille. ⇒ un mmap par segment de 64 Kio, pas par malloc (essentiel pour le matériel modeste, §3).

Le verrou n’est PAS dans le cœur. Dlmalloc<A> est Send mais pas Sync : la logique d’arène est mono-thread. La feature global ajoute GlobalDlmalloc, un static mut DLMALLOC protégé par un pthread_mutex global (global.rs/unix.rs). Le verrouillage est donc une couche au-dessus — exactement la frontière où Air greffe sa politique.

Surface double-face, même tas. dlmalloc-rs expose déjà deux API sur le même allocateur : malloc/free/realloc layout-carrying (Rust GlobalAlloc, reçoit Layout) et c_malloc/c_free/c_realloc/c_memalign layout-free (forme C, sans taille au free). Précédent direct pour le dual-face Air ([[libc-air-dual-face]]).

2. ⚠️ Constat d’honnêteté : le port Rust a ZAPPÉ le mmap-direct des gros blocs

Le dlmalloc canonique (C) a un mmap_threshold (~256 Kio) : au-dessus, chaque grosse demande reçoit son propre mmap dédié, rendu individuellement au free par munmap. Le port Rust 0.2.14 ne l’implémente pas. malloc/sys_alloc ne font que étendre des segments de granularité et tailler top ; la machinerie « chunk mmappé » (Chunk::mmapped, mmap_resize, mmap_foot_pad, mmap_chunk_overhead) existe dans les types mais est vestigiale : un chunk mmappé n’est créé que dans mmap_resize, atteignable seulement si le chunk est déjà mmappé — donc jamais en pratique. Conséquence : dans ce port, toute allocation, même multi-Mio, est taillée dans des segments de 64 Kio. Air devra décider consciemment de réintroduire le chemin « très grand → mmap direct » — il est quasi-correctness pour les allocations géantes (une demande > taille de segment ne doit pas dépendre d’une croissance de top) et indispensable au trim (rendre un gros bloc à l’OS sans fragmenter l’arène, §5c). Ne pas le copier tel quel du port en pensant qu’il y est.

3. CŒUR à EMPRUNTER (non négociable pour la correction)

ÉlémentPourquoi c’est du socle, pas du luxe
Boundary tags (head/prev_foot) + coalescence O(1)C’est ce qui rend free(ptr) sans taille possible (taille en en-tête) et ce qui borne la fragmentation. Sans coalescence exacte, on a une bombe à fragmentation. C’est le plancher de correction.
Bins par classe de taille + bitmapSans bins, malloc est O(n) sur la liste libre → inacceptable. Smallbins exacts = zéro recherche pour le cas dominant (petits objets). Le bitmap donne la bin non-vide en O(1).
mmap par gros chunks + sous-allocationUn mmap par malloc = un syscall par malloc = mort sur Pi 4 (ADR-014). dlmalloc amortit sur 64 Kio. À garder absolument.
Très grand → mmap direct (réintroduit, §2)Une demande dépassant la granularité doit obtenir sa propre cartographie, rendue telle quelle au free. Correctness des allocations géantes + reddition propre à l’OS.
Free-lists intrusives (métadonnées en-bande)Clé du bootstrap sain : l’allocateur stocke ses métadonnées dans la mémoire qu’il gère. Il n’a besoin d’aucun autre tas — juste de mmap brut. Résout le poule-et-œuf du #[global_allocator] (§5/§6).
dv + topMécanique simple et peu coûteuse qui réduit nettement la fragmentation des petits objets. Garder.

4. À SIMPLIFIER / ZAPPER (optimisations, pas correction)

Simplification v1Coût (perf)Pourquoi acceptable en v1
Treemap des grands bins → liste triée simple (par taille, dans chaque classe ou globale)malloc d’un grand bloc passe de O(log) à O(n) sur la liste des grands libresLes grands blocs sont rares vs les petits (servis, eux, par les smallbins exacts en O(1)). Mesurer avant de complexifier (Principe 5). Le trie est l’optimisation la plus subtile/risquée de dlmalloc — l’éviter en v1 réduit drastiquement la surface de bug.
tcache / magazines par-thread → différé (v2 perf)Contention du verrou global sous forte concurrence multi-threadv1 = arène globale unique sous un AirMutex. Simple, correct, fuzzable. La perf concurrente est un chantier v2 mesuré, pas un prérequis de correction.
Segments multiples fins, mremap, release_unused_segments agressif → minimalReddition mémoire à l’OS moins fine ; footprint qui décroît plus lentementGarder un trim simple du top + munmap des très-grands. La gestion fine multi-segments est différable.
FLAG4, compteurs release_checks, max_footprint, mallopt-like—Bruit non nécessaire à la v1. Garder head à 2 bits utiles (PINUSE/CINUSE).

Garde-fou (plancher de correction). Les simplifications ci-dessus touchent la vitesse, jamais : (a) les boundary tags, (b) la coalescence, (c) l’invariant que la granularité est une puissance de deux ≥ alignement malloc (sinon le résidu de trim corrompt les bits de flag empaquetés dans head — bug documenté dans la source, MIN_GRANULARITY). L’arithmétique de tailles/flags est impitoyable : une erreur = corruption de tas, pas une dégradation. C’est précisément pourquoi on emprunte le design éprouvé de Lea pour ces parties-là plutôt que d’improviser.

5. Greffe de la POLITIQUE Air (le vrai intérêt — ce qu’on possède)

(a) Fork-gardien — intégration native, plus propre que dlmalloc. Le deadlock classique : un thread tient le lock de l’allocateur au moment du fork, l’enfant (mono-thread) hérite d’un lock verrouillé pour toujours. dlmalloc le contourne par pthread_atfork(acquire, release, release) (unix.rs::enable_alloc_after_fork) : il acquiert le lock avant le fork et le relâche des deux côtés. Air a mieux : air-runtime possède déjà fork::register(AtForkHandlers { prepare, parent, child }) et reset_after_fork_in_child. L’arène enregistre un handler child qui remet à zéro le mot futex de son AirMutex (état UNLOCKED) directement dans l’enfant — au lieu de la danse acquire-around-fork. Plus simple, plus sûr, et intégré au reset fork global d’air-runtime. (Note : AirMutex n’expose pas aujourd’hui d’API de reset fork ; il faudra soit l’ajouter, soit passer par air_thread::runtime_primitives::reset_futex_word. À cadrer.)

(b) Instrumentation LIB_AIR_DEBUG — table des allocations vivantes (fuites, double-free ; vision pal-rust). Deux greffes possibles sur un design dlmalloc-like : (i) élargir l’en-tête sous cfg(debug) (champs site d’appel / canari) — local au chunk, coalescence à adapter ; (ii) table latérale ptr→métadonnée. ⚠️ Tension réelle : cette table ne peut pas s’allouer sur le tas qu’elle surveille (récursion/poule-et-œuf) → elle doit vivre dans une structure bootstrap-safe (adressage ouvert dans une cartographie mmap dédiée). À concevoir comme un module activable, pas un coût permanent.

(c) « malloc échoue plutôt que hang » — null déterministe sur OOM. L’arène appelle map_anonymous(...) -> Result<RawMapping, Errno> : un échec (ENOMEM) ⇒ on rend null déterministiquement (ou Err), pas de boucle, pas de hang. Mais : sous Linux, un mmap peut réussir puis fauter plus tard (overcommit → OOM-killer). Pour s’en rapprocher, choix à trancher (analyse, pas décision) :

  • Ne PAS utiliser MAP_NORESERVE ⇒ le noyau réserve le commit, et l’échec remonte au mmap quand le commit manque (failure tôt, plus déterministe) — coût : charge le commit du segment entier d’emblée, moins ami de l’overcommit sur Pi 4.
  • MAP_NORESERVE (+ éventuel MAP_POPULATE/pré-fault) ⇒ ami overcommit mais l’OOM réel se manifeste au fault, pas au malloc — la sémantique « fail-not-hang » devient bornée par la politique overcommit globale du noyau, qu’Air ne contrôle pas. MapFlags::{NORESERVE, POPULATE} sont disponibles côté air-sys-types. Honnêteté : un déterminisme OOM total sous Linux est illusoire ; on documente la borne.

(d) Alignement. L’alignement naturel = 2*size_of::<usize>() = 16 sur x86_64/aarch64 = max_align_t du C. Couvre Layout::align() du cas Rust courant. Sur-alignement (align > 16) : chemin memalign (sur-allocation + rognage du leader/trailer, comme dlmalloc) → support futur de aligned_alloc/posix_memalign côté C-ABI.

6. Layering & placement

Recommandation : nouvelle crate air-alloc, couche 1, no_std. Elle doit se situer sous air-memory::{arena,pool,slab,backing} — car ces modules consomment le global allocator (Vec/Box via alloc) et seront donc clients d’air-alloc, jamais l’inverse.

Dépendances visées (minimales, pour éviter tout cycle) :

  • air-sys-types (Errno, MapFlags/ProtectionFlags) — types purs.
  • L’accès mmap brut. Choix à trancher : (a) appeler air-sys-syscall::mem directement (le plus bas, zéro détour) ; ou (b) réutiliser air-memory::raw_mapping::{map_anonymous, unmap, protect_range} (syscall-direct, RawMapping en ManuallyDrop sans munmap auto — adapté car l’allocateur possède lui-même les durées de vie). Risque de (b) : faire dépendre air-alloc d’air-memory, qui par ailleurs est client de l’allocateur → smell architectural (pas un cycle de compilation, le #[global_allocator] étant câblé au binaire rt/, mais inélégant). Reco v1 : option (a) — air-alloc tape air-sys-syscall en direct ; on réconcilie la duplication avec air-memory::raw_mapping plus tard (ou on extrait raw_mapping dans une crate-socle partagée).
  • Verrou : AirMutex (air-thread::sync) est no_std et ne tire pas alloc (juste un mot futex + UnsafeCell) → utilisable sans cycle. Alternative ultra-prudente : air-alloc embarque son propre petit verrou futex (via air-sys-syscall::futex) pour ne dépendre de rien en couche 1. À trancher selon le graphe de dépendances réel d’air-thread.
  • Fork : l’intégration se fait par air-runtime qui dépend d’air-alloc (et enregistre le handler), pas l’inverse — pour éviter le cycle air-alloc ↔ air-runtime. air-alloc expose juste une fonction de reset que le runtime appelle.

7. Contrat & API

Face Rust (core::alloc::GlobalAlloc) : alloc, dealloc, realloc, alloc_zeroed (le calloc de dlmalloc saute le zéro-fill quand mmap rend déjà du zéro et que le chunk n’est pas mmappé — MAP_ANON zéroe les pages neuves ; reprendre cette optimisation). C’est l’impl qui remplace AbortOnAlloc et se branche en #[global_allocator] dans rt/.

Face C-ABI future (ADR-046) : malloc, free (sans taille — résolu par l’en-tête, §1), realloc, calloc, aligned_alloc/posix_memalign (via memalign). Même tas, deux faces — précédent c_malloc/c_free de dlmalloc-rs ([[libc-air-dual-face]]).

Thread-safety : v1 = un AirMutex<Arène> global. La logique d’arène reste mono-thread (comme Dlmalloc<A> : Send, non Sync) ; le verrou est la couche au-dessus.

8. Staging proposé

  • v1 — correct + simple + fuzzé. Boundary tags + coalescence, smallbins (bitmap), liste triée pour les grands (pas de treemap), dv/top, mmap 64 Kio + sous-alloc, très-grand → mmap direct, trim minimal, un AirMutex global, null sur OOM. Débloque : remplacement d’AbortOnAlloc, exécution réelle de Command/spawn et de tout code allouant (Vec/String/collections std) sur la cible *-linux-air.
  • v2 — perf (mesurée). Arènes/tcache par-thread, réintroduction d’un index de grands bins (treemap ou skiplist) si le profil le justifie, trim/segments plus fins.
  • v3 — instrumentation profonde + fork-gardien complet. Table live-allocs (LIB_AIR_DEBUG), détection double-free/fuite, canaris, comptabilité par-composant (cf. AirMemoryTracker).

9. Mandat de test (Principe 1, couche 1)

  • Couverture 100 % lignes + branches. L’arène est host-testable : on lui fournit un backing en test (un buffer/Vec<u8> hôte ou un mmap hôte) au lieu du vrai syscall — exactement le patron de dlmalloc-rs (impl System testée sur l’hôte ; tests/smoke.rs et tests/eat_memory.rs pilotent des séquences d’opérations aléatoires via arbitrary + SmallRng).
  • Property-based : invariants — roundtrip alloc/free ; alignement demandé respecté ; aucun chevauchement entre blocs vivants ; coalescence (deux libres adjacents → un seul) ; classe de taille correcte ; realloc préserve les octets min(old,new).
  • Fuzzing (cargo-fuzz) : séquences aléatoires alloc/free/realloc/calloc/memalign, modèle fantôme (shadow) vérifiant non-chevauchement et contenu ; différentiel possible vs un allocateur de référence trivial, ou vs glibc sur l’hôte.
  • Stress concurrent : N threads martelant l’arène sous le verrou (détecte deadlock/corruption).
  • Frontière TARGET-ONLY (gros enjeu couverture, ADR-035) : la LOGIQUE (sur backing fourni) est host-testable et doit l’être à 100 %. En revanche le câblage réel comme #[global_allocator], le #[thread_local] d’errno, et le reset-fork ne se valident qu’on-target (selftest rt/). Tracer nettement cette frontière pour ne pas gonfler artificiellement les exceptions de couverture.

10. Questions ouvertes (décisions BDFL à venir, pour l’ADR)

  1. Nom & placement : crate air-alloc dédiée, ou module d’air-memory ? (Reco : crate dédiée, §6.)
  2. Backing : air-sys-syscall::mem direct vs air-memory::raw_mapping vs crate-socle extraite ?
  3. Sémantique OOM : MAP_NORESERVE ou non ? pré-fault MAP_POPULATE ? (arbitrage déterminisme vs amitié-overcommit Pi 4, §5c).
  4. Tailles : granularité de segment initiale (64 Kio comme dlmalloc, ou plus petit sur RAM modeste ?) ; seuil mmap-direct pour les très-grands (256 Kio façon C ? réglable ?).
  5. Structure des grands bins en v1 : liste triée simple (reco) vs réintroduire le treemap.
  6. Verrou : réutiliser AirMutex ou embarquer un futex dédié dans air-alloc (anti-cycle) ?
  7. Politique d’alignement : périmètre des API alignées (aligned_alloc/posix_memalign) en v1 vs différé.
  8. Instrumentation : stratégie de stockage de la table live-allocs (mmap dédié bootstrap-safe vs en-tête élargi sous cfg).
  9. Périmètre v1 exact : trim/reddition à l’OS incluse ou minimale ?

Méthode : lecture statique de dlmalloc-rs v0.2.14 (~/.cargo/.../dlmalloc-0.2.14/src/) + concepts canoniques de Doug Lea malloc ; recoupement avec le code Air existant (air-memory::raw_mapping, air-runtime::fork, air-thread::sync::AirMutex, air-rt::AbortOnAlloc, air-sys-types::{Errno,MapFlags}, ADR-046/047). Aucun build d’allocateur lancé. Cette note est exploratoire et non engageante — l’ADR fait foi.