heap/pt2-arenas.tsx

Où vit ton heap : arenas
et malloc_state

Structure malloc_state au coeur des arenas ptmalloc2 : mutex, fastbinsY, top chunk, last_remainder, bins et binmap. Cas particulier de la main_arena et schéma multi-threadé via heap_info.

Maxime Jérôme·12 novembre 2024·5 min de lecture

Prérequis

Langage C
Syscalls Linux
Maniement de GCC
Introduction à ptmalloc2
Chunks

Hello ! o/

Aaaah.. les arenas :)

Les arenas dans ptmalloc2 sont simplement les structures de données qui permettent de gérer la heap correctement en mémoire. Pour introduire les arenas dans le game de ptmalloc2, voici la structure de données (directement tirée de malloc.c évidemment) :

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS]; // NFASTBINS = 10

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2]; // NBINS = 128

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE]; // BINMAPSIZE = 4

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

Ce qu'il faut retenir de cette structure :

Un mutex pour définir quel thread a accès à l'arena.
Un petit tableau (liste chaînée) fastbinsY pour gérer des listes de chunks libérés d'une taille spécifique - utile pour la performance.
Le pointeur top sur le top chunk : frontière entre la heap et le wilderness. Ce chunk diminue à chaque allocation et peut grossir via sbrk(2) si besoin.
Le chunk last_remainder : utile quand malloc coupe un chunk en deux pour en allouer une partie - si le reste (remainder) est assez grand pour la prochaine allocation, il est renvoyé directement.
Les bins : tableaux pour ranger les chunks libérés par catégorie de taille.
Les pointeurs next et next_free vers la prochaine arena (et la prochaine arena libre) dans un contexte multi-threadé.

malloc_state-layout.txt

  struct malloc_state
  ┌──────────────────────────────────────────────────┐
  │  mutex              (serialise l'accès)           │
  │  flags                                            │
  │  have_fastchunks                                  │
  ├──────────────────────────────────────────────────┤
  │  fastbinsY[0..9]    (10 listes chaînées)          │
  │    [0] → chunk16 → chunk16 → NULL                 │
  │    [1] → chunk24 → NULL                           │
  │    ...                                            │
  ├──────────────────────────────────────────────────┤
  │  top                → [top chunk / wilderness]    │
  │  last_remainder     → [dernier reste de split]    │
  ├──────────────────────────────────────────────────┤
  │  bins[0..253]       (unsorted + small + large)    │
  ├──────────────────────────────────────────────────┤
  │  binmap[0..3]       (bitmap 128 bits)             │
  ├──────────────────────────────────────────────────┤
  │  next               → prochaine arena             │
  │  next_free          → prochaine arena libre       │
  │  attached_threads                                 │
  │  system_mem / max_system_mem                      │
  └──────────────────────────────────────────────────┘

Vue d'ensemble des champs de malloc_state pour une arena.

Dans un programme single-threadé, absolument tous les chunks sont gérés par main_arena.

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

Evidemment main_arena fait référence au bit NON_MAIN_ARENA des chunks, qui est 0 si le chunk appartient à main_arena.

Multi-threaded heap

Dans un programme multi-threadé, glibc a tout prévu ! On va avoir plusieurs heaps et donc plusieurs arenas, toutes reliées les unes aux autres sous la forme d'une jolie liste chaînée :)

arenas-linked-list.txt

  ┌──────────────┐      ┌──────────────┐      ┌──────────────┐
  │  main_arena  │─next▶│  thread_arena│─next▶│  thread_arena│
  │  (sbrk heap) │      │  (mmap heap) │      │  (mmap heap) │
  └──────────────┘      └──────────────┘      └──────────────┘
         ▲                                            │
         └────────────────────next────────────────────┘
                        (liste circulaire)

Les arenas forment une liste chaînée circulaire via le champ next.

Ces heaps supplémentaires ne sont pas générées avec brk/sbrk, mais avec mmap. La main_arena devient alors une simple thread_arena parmi les autres.

Chaque heap mmap-ée est décrite par la structure heap_info :

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena pour cette heap. */
  struct _heap_info *prev; /* Heap précédente. */
  size_t size;   /* Taille courante en octets. */
  size_t mprotect_size; /* Taille protégée PROT_READ|PROT_WRITE. */
  /* Alignement pour que sizeof(heap_info) + 2 * SIZE_SZ
     soit un multiple de MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

multithread-heap-overview.txt

  Processus multi-threadé
  ┌─────────────────────────────────────────────────────────────┐
  │                                                             │
  │  Thread principal                                           │
  │  ┌───────────────────┐                                      │
  │  │   main_arena      │◄── sbrk heap (segment .bss étendu)  │
  │  │   malloc_state    │                                      │
  │  └───────┬───────────┘                                      │
  │          │ next                                             │
  │          ▼                                                  │
  │  Thread 1                                                   │
  │  ┌───────────────────┐   ┌───────────────────┐             │
  │  │  thread_arena 1   │   │    heap_info       │             │
  │  │  malloc_state     │◄──│    ar_ptr          │             │
  │  └───────┬───────────┘   │    prev → NULL     │             │
  │          │ next          │    size            │             │
  │          ▼               └───────────────────┘             │
  │  Thread 2                  (mmap'd region)                  │
  │  ┌───────────────────┐   ┌───────────────────┐             │
  │  │  thread_arena 2   │   │    heap_info       │             │
  │  │  malloc_state     │◄──│    ar_ptr          │             │
  │  └───────┬───────────┘   │    prev → ...      │             │
  │          │ next          └───────────────────┘             │
  │          └──────────► (retour vers main_arena)             │
  └─────────────────────────────────────────────────────────────┘

Vue d'ensemble d'un processus multi-threadé : chaque thread peut avoir sa propre arena et heap.

Une arena peut gérer plusieurs heaps

Pour conclure : une arena peut gérer plusieurs heaps ! Le top de la heap aux adresses basses est libre, et pointe vers celle aux adresses plus hautes. C'est le seul truc un peu contre-intuitif du schéma, mais ca fait sens : quand la heap courante est pleine, on en mmap une nouvelle et on relie les deux.

arena-multiple-heaps.txt

  arena (malloc_state)
  ┌──────────────────────┐
  │  top ────────────────┼──► heap2 (adresses hautes)
  │  ...                 │    ┌─────────────────────┐
  └──────────────────────┘    │ heap_info            │
                              │   prev ──────────────┼──► heap1 (adresses basses)
                              │   ar_ptr             │    ┌─────────────────────┐
                              ├─────────────────────┤    │ heap_info            │
                              │ chunks heap2        │    │   prev → NULL        │
                              │   ...               │    ├─────────────────────┤
                              │   top chunk (free)  │    │ chunks heap1        │
                              └─────────────────────┘    │   ...               │
                                                         │   [plein]           │
                                                         └─────────────────────┘

Une arena peut chaîner plusieurs heaps via heap_info.prev.

Article suivant

Les 4 bins de ptmalloc2, à quoi ils servent vraiment