heap/pt2-chunks.tsx

Anatomie d'un
chunk ptmalloc2

Anatomie d'un chunk ptmalloc2 : champs mchunk_prev_size et mchunk_size, bits NON_MAIN_ARENA / IS_MMAPPED / PREV_INUSE et chainage FD/BK pour les chunks liberes.

Maxime Jérôme·22 octobre 2024·5 min de lecture

Prérequis

Langage C
Syscalls Linux
Maniement de GCC
Introduction à ptmalloc2

Hello ! o/

Vous allez comprendre ici comment les chunks dans ptmalloc2 sont faits quand ils sont dits alloués et désalloués. En réalité un chunk est l'espace mémoire qui vous est dédié lorsque vous appelez malloc(3). Un chunk est défini dans malloc.c par cette structure :

struct malloc_chunk
{
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;                /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize;       /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

Alors il faut comprendre qu'un chunk au final, ça se structure avec :

mchunk_prev_size (memory chunk previous size) : la taille du chunk précédent, comme son nom l'indique.
mchunk_size : la taille du chunk, multiple de 8 (les 3 derniers bits sont utilisés pour autre chose, voir ci-dessous).
bit NON_MAIN_ARENA (A) : 0 si le chunk appartient à main_arena, 1 sinon.
bit IS_MMAPPED (M) : 1 si le chunk est un chunk mmap-é, 0 sinon.
bit PREV_INUSE (P) : 1 si le chunk précédent est alloué, 0 sinon.
Mémoire utilisateur (avec fd, bk, fd_nextsize et bk_nextsize), de taille malloc_usable_size().

chunk-allocated.txt

  adresse basse
  ┌─────────────────────────────────────────────┐
  │  mchunk_prev_size  (8 octets sur x86-64)    │  ← taille du chunk precedent
  │                    (si chunk precedent free)│
  ├─────────────────────────────────────────────┤
  │  mchunk_size       (8 octets)               │  ← taille + bits de flags
  │  bits de poids faible :                     │
  │    bit 0 = P (PREV_INUSE)                   │
  │    bit 1 = M (IS_MMAPPED)                   │
  │    bit 2 = A (NON_MAIN_ARENA)               │
  ├─────────────────────────────────────────────┤
  │                                             │
  │  donnees utilisateur                        │  ← malloc() renvoie ce pointeur
  │  (fd / bk / fd_nextsize / bk_nextsize       │
  │   quand chunk est FREE, sinon payload)      │
  │                                             │
  └─────────────────────────────────────────────┘
  adresse haute

Layout d'un chunk alloue en memoire. mchunk_size encode la taille ET les 3 bits de flags dans ses bits de poids faible.

Pourquoi mchunk_prev_size peut etre vide ?

Quand le chunk precedent est alloue (bit PREV_INUSE = 1), le champ mchunk_prev_size n'est pas utilise par ptmalloc2 et peut etre utilise par le chunk precedent comme espace de payload supplementaire. Economie d'espace classique du glibc malloc.

Les 3 bits de flags dans mchunk_size

Comme la taille d'un chunk est toujours un multiple de 8 (alignement minimum), les 3 bits de poids faible de mchunk_size sont toujours a 0 pour la taille reelle. ptmalloc2 les recycle pour stocker les flags :

Bit	Nom	Signification
0	PREV_INUSE (P)	1 si le chunk precedent est alloue. Permet a ptmalloc2 de savoir si le chunk adjacent peut etre fusionne (coalescing) lors du free.
1	IS_MMAPPED (M)	1 si le chunk a ete alloue directement via `mmap(2)` (grandes allocations). Dans ce cas il n'appartient a aucune arena et sera libere via `munmap(2)`.
2	NON_MAIN_ARENA (A)	0 si le chunk appartient a `main_arena`, 1 s'il appartient a une arena secondaire (thread arena). Permet de retrouver la bonne arena au moment du free.

FD et BK

Lorsqu'un chunk est free (libere), il est considere comme noeud d'une liste doublement chainee de chunks free : FD (Forward) pointe sur le chunk suivant dans la liste, BK (Backward) pointe sur le precedent.

chunk-freed-doubly-linked.txt

  chunk A (free)                    chunk B (free)
  ┌──────────────────────┐          ┌──────────────────────┐
  │ mchunk_prev_size     │          │ mchunk_prev_size     │
  ├──────────────────────┤          ├──────────────────────┤
  │ mchunk_size  [P=0]   │          │ mchunk_size  [P=0]   │
  ├──────────────────────┤          ├──────────────────────┤
  │ fd  ─────────────────┼─────────►│ fd  ──► ...          │
  ├──────────────────────┤          ├──────────────────────┤
  │ bk  ◄────────────────┼──────────┼─ bk                  │
  ├──────────────────────┤          ├──────────────────────┤
  │ fd_nextsize (grands) │          │ fd_nextsize (grands) │
  ├──────────────────────┤          ├──────────────────────┤
  │ bk_nextsize (grands) │          │ bk_nextsize (grands) │
  └──────────────────────┘          └──────────────────────┘

  Note : fd_nextsize / bk_nextsize ne sont utilises que pour
  les "large bins" (grands chunks). Ils chainennt les chunks
  de tailles differentes a l'interieur d'un meme bin.

Deux chunks liberes chaines entre eux via FD/BK. La liste est doublement chainee pour permettre les insertions/suppressions en O(1).

FD/BK : surface d'attaque classique

La manipulation des pointeurs FD et BK sur des chunks liberes est la base de nombreuses techniques d'exploitation heap (unsafe unlink, house of force, tcache poisoning...). On les verra en detail dans la suite de la serie.

Article suivant

Où vit ton heap : arenas et malloc_state