Partie 18 - Les small bins - fonctionnement et exploitation (1/2)

Les small bins : fonctionnement et exploitation (1/2)

Pour être honnête avec vous, j’ai longuement hésité à écrire les chapitres dédiés aux small bins et large bins tant leur usage est marginal depuis la présence du tcache. Mais bon, qui sait, peut-être qu’avoir écrit quelque part la manière dont ces types de corbeilles fonctionnent sera utile un jour ou l’autre 🤷‍♂️.

Utilisation

Nous avons récemment analysé le fonctionnement de la unsorted bin au cours des précédents chapitres. Vous vous rappelez sans doute qu’un bloc libre de la unsorted bin n’a qu’une seule chance d’être réutilisé. S’il n’est pas utilisé lors de la prochaine allocation (ex : taille d’allocation plus importante), alors il est inséré soit dans une small bin soit dans une large bin en fonction de sa taille.

Gestion des blocs libres

Taille des blocs gérés

Agencement en mémoire

Voyons quelles sont les tailles de bloc gérées par les small bins, cela est très utile pour savoir si un bloc de la unsorted bin ira dans une small bin ou large bin. Tout d’abord, voici ce que dit le code source au sujet du nombre de small bins :

/*
   Indexing

    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
    8 bytes apart. Larger bins are approximately logarithmically spaced:
    
    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left
     
    There is actually a little bit of slop in the numbers in bin_index
    for the sake of speed. This makes no difference elsewhere.
    
    The bins top out around 1MB because we expect to service large
    requests via mmap.
    
    Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
    a valid chunk size the small bins are bumped up one.
 */
 
#define NBINS             128
#define NSMALLBINS         64

Les nombres affichés dans cette section de code de la glibc peuvent prêter à confusion 😵‍💫, il faut le reconnaître. Nous allons détailler étape par étape la manière de compter le nombre de small bins et large bins pour que vous compreniez comment s’effectue, au final, leur dénombrement.

Faisons la somme de toutes les corbeilles listées dans le commentaire ci-dessus : 64+32+16+8+4+2+1 = 127. Or la valeur de NBINS est 128. On s’attendrait donc à ce qu’il y ait : 64 small bins et 64 large bins. Mais non, il y a une unité de différence 🤔 …

La fin du commentaire stipule Bin 0 does not exist.. Vous remarquerez, d’ailleurs, que les boucles indexées par rapport à NBINS démarrent toujours à 1, comme ici.

Bah faut savoir : soit les tableaux en informatique commencent à 0, soit à 1 😑.

Tout à fait d’accord ! C’est très perturbant pour la compréhension de l’agencement des small bins et large bins. Mais bon, au moins nous comprenons pourquoi il y en a bien 127 et non 128 au total.

Mais il y a autre chose qui peut sembler étrange : NSMALLBINS vaut 64. Le problème ? Bah c’est que les small bins, il n’y en a pas 64 mais 62 😅. Puisque la Bin 0 n’existe pas, on passe de 64 à 63 corbeilles. Reste à déterminer comment nous sommes passés de 63 à 62.

De plus, d’après le commentaire Bin 1 is the unordered list, on en déduit que la première corbeille n’est tout autre que la unsorted bin. Ainsi, voici comment se décomposent ces 127 corbeilles :

• 1 unsorted bin ;
• 62 small bins ;
• 64 large bins ;

Et la boucle est (presque) bouclée ! Il nous faut désormais comprendre le tableau bins qui fait partie de l’arène :

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

Normalement le tableau bins devrait vous dire quelque chose étant donné que ses deux premiers éléments pointent vers le premier et dernier bloc de la unsorted bin. Vous avez sûrement dû le voir passer en utilisant la commande arena. Pour rappel, il ressemble à :

Il est important de comprendre l’agencement des small bins et large bins dans ce tableau car ce n’est pas évident de prime abord.

Déjà, calculons sa taille : NBINS * 2 - 2 = 128 * 2 - 2 = 254. 254 c’est aussi 127*2. Cette précision n’est pas anodine. Vu que chaque corbeille “classique” (unsorted bin, small bin et large bin) est une liste doublement chaînée, l’arène a besoin d’avoir un pointeur vers son premier et son dernier élément. C’est pourquoi la glibc utilise un tableau de 127*2 éléments pour représenter les 127 corbeilles.

Le tableau ci-dessous synthétise la correspondance entre le numéro d’une corbeille (qui va de 1 à 127) et ses deux index dans le tableau bins :

Numéro de la corbeille	Ses deux index dans bins	Type de la corbeille
1	{ 0 ; 1 }	unsorted bin
2	{ 2 ; 3 }	small bin
3	{ 4 ; 5 }	small bin
n	{ n*2 - 2 ; n*2 - 1 }	small bins
63	{ 0x7c ; 0x7d } ({ 124 ; 125 })	small bin
64	{ 0x7e ; 0x7f } ({ 126 ; 127 })	large bin
65	{ 0x80 ; 0x81 } ({ 128 ; 129 })	large bin
n	{ n*2 - 2 ; n*2 - 1 }	large bins
127	{ 0xfc ; 0xfd } ({ 252 ; 253 })	large bin

Pfiouu 🥵 ! Au moins maintenant, nous savons exactement où est stockée chaque corbeille et la manière dont se calculent les indices.

Résumé

Les tailles données ci-dessous incluent les métadonnées.

À partir du nombre de small bins et de l’espace entre deux small bins en fonction de l’architecture, nous obtenons les résultats suivants :

Version de la libc <= 2.25

Version	Espace entre deux corbeilles	Nombre de small bins	Taille min	Taille max (incluse)
32 bits	8 octets	62	0x10	0x1f8
64 bits	0x10 octets	62	0x20	0x3f0

Version de la libc > 2.25

Version	Espace entre deux corbeilles	Nombre de small bins	Taille min	Taille max (incluse)
32 bits	0x10 octets	62	0x20	0x3e0
64 bits	0x10 octets	62	0x20	0x3f0

Pour rappel, dans les anciennes versions de la glibc (≤ 2.25 (2017)), la contrainte d’alignement des blocs est de 8 octets. De ce fait, vous remarquerez qu’après la version 2.25, les intervalles de taille en 32 bits et 64 bits ne diffèrent pas tellement.

Les blocs non réutilisés de la unsorted bin vont dans une large bin lorsque leur taille ne leur permet pas d’être traités par une small bin ?

Exactement !

Organisation des corbeilles

Concernant la structure des corbeilles, ce sera assez facile à comprendre étant donné que cela est très proche de la structure de la unsorted bin :

• les blocs sont gérés via un système de liste doublement chaînée circulaire ;
• la liste est de type FIFO (First In First Out). Autrement dit le premier bloc arrivé, est le premier servi.

L’une des particularités de ce type de corbeilles est qu’un bloc qui vient d’être libéré ne va jamais directement dans une small bin mais passe dans un premier temps par la unsorted bin. Si ce bloc n’est pas réutilisé et qu’il a une petite taille, il va dans la small bin idoine.

Transition de la unsorted bin vers une small bin

Cas n°1 : un seul bloc

Comme à l’accoutumée, je vous propose de voir avec un schéma ce qui se passe lorsqu’un bloc n’est pas réutilisé dans la unsorted bin. Prenons comme support le programme suivant :

#include "stdlib.h"

// Version de la glibc : 2.24-9ubuntu2_amd64
int main()
{
    void *a = malloc(0x500);
    malloc(1);
    
    free(a); // Bloc A -> unsorted bin (taille = 0x500)
    malloc(0x500 - 0x100); // Bloc A reste dans unsorted bin (taille = 0x100)
    malloc(0x200); // 0x200 > 0x100 => Bloc A -> small bin (taille = 0x100)

	return 0;
}

Ci-dessous, les différentes étapes d’exécution du programme :

1. le bloc A de 0x500 octets est alloué ainsi qu’un autre petit bloc afin d’éviter la consolidation avec le bloc du sommet lors de la libération ;
2. free(a) : étant donné que dans cette version de la glibc (2.24) il n’y a pas de tcache et que la taille de ce bloc n’est pas gérée par une fastbin, le bloc libre est géré par la unsorted bin ;
3. malloc(0x500 - 0x100) : un bloc de 0x400 octets est alloué. Sachant que le bloc libre A a été réutilisé, le reste du bloc (0x100 octets) ne quitte pas la unsorted bin. De nouveau, le bloc libre de 0x100 octets a une seule chance d’être réutilisé ;
4. malloc(0x200) : la taille de l’allocation demandée dépasse celle du bloc libre, ce dernier est donc placé dans la small bin de taille 0x100.

Cas n°2 : plusieurs blocs

Analysons désormais le comportement du programme suivant :

#include "stdlib.h"

// Version de la glibc : 2.24-9ubuntu2_amd64
int main()
{
    void *a = malloc(0x500);
    malloc(1);

    void *b = malloc(0x500);
    malloc(1);

    void *c = malloc(0x500);
    malloc(1);


    free(a); // Bloc A -> unsorted bin (taille = 0x500)
    malloc(0x500 - 0x100); // Bloc A reste dans unsorted bin (taille = 0x100)
    malloc(0x200); // 0x200 > 0x100 => Bloc A -> small bin (taille = 0x100)

    free(b); // Bloc B -> unsorted bin (taille = 0x500)
    malloc(0x500 - 0x100); // Bloc B reste dans unsorted bin (taille = 0x100)
    malloc(0x200); // 0x200 > 0x100 => Bloc B -> small bin (taille = 0x100)

    free(c); // Bloc B -> unsorted bin (taille = 0x500)
    malloc(0x500 - 0x100); // Bloc B reste dans unsorted bin (taille = 0x100)
    malloc(0x200); // 0x200 > 0x100 => Bloc B -> small bin (taille = 0x100)

	return 0;
}

Il s’agit du même programme que le précédent, si ce n’est qu’à la fin de son exécution, 3 blocs libres seront présents dans la small bin de taille 0x100.

Petite question pour voir si vous avez bien compris : quel est le numéro de la small bin qui gère les blocs libres de taille 0x100 ? Quels sont ses deux index dans le membre (tableau) bins de l’arène ?

Réponse : aWwgcydhZ2l0IGRlIGxhIHNtYWxsIGJpbiBuwrAxNiBkb250IGxlcyBkZXV4IGluZGV4IHNvbnQgeyAweDFlIDsgMHgxZn0u

En exécutant le programme jusqu’au retour du main dans gdb, nous pouvons effectivement constater la présence des trois blocs libres de 0x100 octets dans une small bin :

Selon la doc’ de la glibc qui stipule que la première bin (n°1) est la unsorted bin, le numéro de cette small bin est 16 parmi l’ensemble des trois corbeilles : unsorted bin + small bins + large bins.

Par contre, parmi toutes les small bins, celle qui gère les blocs de taille 0x100 est la numéro 15. D’où la valeur idx=15 utilisée dans gdb.

En gros : c’est la 16e bin (unsorted bin, small bins et large bins confondues) et la 15e small bin parmi les small bins.

Oui, c’est très pénible de devoir jongler entre différentes manières d’indexer les corbeilles 😮‍💨 … Ce qui est important est de se rappeler l’origine de ces différences.

En utilisant la commande arena, nous trouvons rapidement les indices de cette small bin :

En s’intéressant aux liens entre les différents blocs, vous constaterez que les blocs libres d’un small bin sont liés de la même manière que des blocs libres de la unsorted bin :

Les listes doublement chaînées circulaires sont un peu difficiles à lire au début, mais avec un peu de temps, on finit par en saisir la logique.

Structure et métadonnées d’un bloc issu d’une small bin

Ce qui est, au départ, compliqué avec les small bins, c’est le nombre de corbeilles qu’il y a et la manière dont elles sont indexées et gérées par l’arène. Quant à l’organisation des blocs au sein d’une corbeille, c’est semblable à ce qui est effectué dans la unsorted bin.

D’ailleurs, même la structure d’un bloc dans une small bin est similaire à celle des blocs de la unsorted bin :

On passe à la suite ?