Comprendre le heap avant
de l'attaquer

Prerequis

• Langage C
• Syscalls Linux
• Maniement de GCC

Hello ! o/

A travers une serie d'articles vous allez comprendre comment la heap est geree dans l'implementation de ptmalloc2 (pthread malloc v2). ptmalloc2 est le systeme de la heap qui est actuellement utilise dans la glibc. Comme d'habitude, on verra assez en profondeur pour que vous ayez une vue qui ne soit pas biaisee, mais pas trop non plus, sinon il suffirait de vous rediriger vers le code source.

Ces articles sont divises en 4 et on en tirera tous les details necessaires :

• Les chunks : le bloc memoire que vous allouez sur la heap
• Les arenas : les structures qui gerent les differentes heap
• Les bins : ou sont stockes les chunks liberes
• Le tcache : qui resout les conflits de threads

Heap vs Stack : pourquoi avoir les deux ?

Un peu de contexte : la heap permet de gerer les allocations dynamiques, typiquement quand vous voulez creer une structure de donnee qui augmente de taille au runtime, genre une liste chainee. La stack ne peut pas gerer ce type d'allocation du fait que chaque stackframe (memoire reservee a une fonction) a une taille definie par les declarations des variables, donc ecrire par-dessus risque tres fortement d'en reecrire d'autres.

Toute la problematique d'une heap reside dans la vitesse d'allocation et de gestion de la memoire : il faut pouvoir reutiliser au mieux et au plus vite ce qui a ete libere.

La heap est donc un espace memoire a part entiere, separee de la stack. Elle est creee par l'intermediaire de votre premier malloc(3), ou d'un call sur brk(2), mmap(2) ou tout autre syscall qui peut creer une plage d'adresses memoire.

Premier malloc : la heap nait

Voila un exemple minimal qui illustre exactement quand la heap apparait en memoire :

#include <stdio.h>
#include <stdlib.h>

int
main (int argc,
      char * argv [])
{
    unsigned short i;
    short * ptr;

    if (argc > 1)
    {
        fprintf(stderr, "[!] Error: Usage: ./program\n");
        exit(EXIT_FAILURE);
    }
    // Il n'y a toujours pas de heap en memoire a partir d'ici
    ptr = (short *) malloc ( sizeof(short) * 10 );
    // Et la, elle est declaree

    for (i = 0; i < 10; i++)
    {
        ptr[i] = i;
    }
    fprintf(stdout, "%hd\n", ptr[3]);

    return EXIT_SUCCESS;
}

  /proc/<PID>/maps -- AVANT malloc()
  ┌────────────────────────────────────────────────────────┐
  │ 55a1b2000000-55a1b2001000  r-xp  [.text]              │
  │ 55a1b2200000-55a1b2201000  rw-p  [.data / .bss]       │
  │ 7f3c00000000-7f3c00200000  r-xp  libc.so              │
  │ 7ffd12340000-7ffd12360000  rw-p  [stack]              │
  └────────────────────────────────────────────────────────┘

  /proc/<PID>/maps -- APRES malloc( sizeof(short)*10 )
  ┌────────────────────────────────────────────────────────┐
  │ 55a1b2000000-55a1b2001000  r-xp  [.text]              │
  │ 55a1b2200000-55a1b2201000  rw-p  [.data / .bss]       │
  │ 55a1b2402000-55a1b2423000  rw-p  [heap]  <-- NOUVEAU  │
  │ 7f3c00000000-7f3c00200000  r-xp  libc.so              │
  │ 7ffd12340000-7ffd12360000  rw-p  [stack]              │
  └────────────────────────────────────────────────────────┘

  => brk() a ete appele en coulisse par malloc() pour
     reserver un segment rw en memoire : c'est la heap.

Plan de la serie

Maintenant qu'on sait pourquoi la heap existe, voila comment on va l'eplucher dans les articles suivants :