Partie 14 - La unsorted bin - rôle et fonctionnement (1/4)

La unsorted bin : rôle et fonctionnement (1/4)

Poursuivons l’analyse détaillée des différents types de corbeilles avec la unsorted bin. Littéralement “corbeille non triée”, cette corbeille contiendra notamment les blocs libérés qui n’ont pu être traités ni par le tcache ni par une des fastbins.

Contrairement à tous les autres types de corbeilles (tcache, fastbins, small bins et large bins) la unsorted bin n’est constituée que d’une seule corbeille contrairement aux autres qui pouvaient en contenir plusieurs en fonction de la taille du bloc libéré. Ce qui est logique : ce type de corbeille n’étant pas trié, tous les blocs sont placés dans la même corbeille.

Toutefois, cette unique corbeille peut contenir plusieurs blocs qui sont organisés sous la forme d’une liste doublement chaînée circulaire.

Utilisation

La unsorted bin est une zone tampon où les blocs qui n’ont pas pu être traités par la fastbin et le tcache seront reçus en raison de leur grande taille.

L’idée derrière l’utilisation de cette corbeille est de pouvoir réutiliser rapidement, si possible, un bloc de grande taille qui a été récemment libéré. Prenons par exemple le cas d’un programme qui gère l’envoi et la réception des messages via la structure suivante :

struct message 
{
	int message_type;
	unsigned int message_size; // Est censé toujours être < 0x500
	char content[0x500];
};

Bien que la taille des données contenues dans le message peut varier de 0 à 0x500, la structure, elle, a toujours la même taille supérieure à 0x500 octets. Voici comment peut être recyclé un bloc lors de l’envoi de plusieurs messages :

1. un message doit être envoyé : un appel à malloc(sizeof(message)) est réalisé ;
2. une fois le message envoyé, la mémoire qui lui était allouée est libérée avec free : le bloc ayant une taille supérieure à 0x500 octets, il est placé dans la unsorted bin ;
3. un nouveau message doit être envoyé : l’appel à malloc est réalisé à nouveau mais cette fois-ci, le bloc est récupéré depuis la unsorted bin plutôt que d’allouer un nouveau bloc dans le tas.

Bah oui mais ça on le savait déjà, c’est aussi le principe des autres types de corbeilles 🤨 …

C’est vrai 😅. Pour tout vous dire, ce comportement est effectivement partagé par tous les autres types de corbeilles : s’il existe un bloc de taille n dans une corbeille et qu’une allocation de taille n est demandée, le bloc en question sera retourné par malloc. Mais bon, une piqûre de rappel de temps à autre, ça ne fait pas de mal 😊.

Fragmentation des blocs libres

La différence notable dans la gestion des blocs de la unsorted bin comparée aux autres, est qu’il est possible de fragmenter un bloc libre en un bloc de plus petite taille pour satisfaire une demande lorsque la taille du bloc à allouer est plus petite que la taille du bloc présent dans la unsorted bin. C’est du charabia 🫣 ?

Voyons ce que cela signifie à l’aide d’un schéma :

1. initialement deux blocs sont alloués : un premier de 0x500 octets et un second afin d’éviter la consolidation du bloc A avec le bloc du sommet ;
2. le bloc A est libéré, comme sa taille ne lui permet pas d’être traité par une fastbin ou le tcache, il est inséré dans la unsorted bin ;
3. afin d’allouer un bloc de 0x100 octets, la unsorted bin sépare le bloc libre de 0x500 octets qu’elle contient en deux blocs :
   1. un bloc de 0x100 octets qui sera réutilisé et retourné par malloc ;
   2. un bloc de 0x400 octets qui reste dans cette corbeille.

Gestion des blocs libres

Taille des blocs gérés

Concernant la taille des blocs, la règle à retenir est la suivante : un bloc dont la taille ne lui permet pas d’être géré par une fastbin ou le tcache atterrit dans la unsorted bin.

Si vous souhaitez absolument avoir des chiffres concernant la taille indicative à partir de laquelle un bloc peut être envoyé dans la unsorted bin, les voici :

	glibc < 2.26	glibc ≥ 2.26
32 bits	0x48	0x410
64 bits	0x90	0x420

Si à un moment donné, vous souhaitez envoyer un bloc de grande taille non pas dans la unsorted bin mais dans la fastbin, n’oubliez pas que cela est possible en modifiant la variable globale global_max_fast 😉.

Le tableau ci-dessus donne une idée de la taille à partir de laquelle un bloc est envoyé dans la unsorted bin. Cela ne veut pas pour autant qu’elle ne peut pas contenir des blocs de plus petite taille. Ce n’est pas une règle stricte.

Par exemple, si un bloc libre de 0x500 octets est présent dans la unsorted bin et qu’une allocation nécessite 0x400 octets, le bloc libre sera fragmenté et le reste de 0x100 restera dans la unsorted bin alors qu’un bloc de cette taille devrait normalement être géré par le tcache.

Pour résumer cette histoire de taille : les blocs qui ne vont pas dans une fastbin ou dans le tcache sont gérés par la unsorted bin mais il est possible qu’elle contienne des blocs de plus petite taille issus des restes de la fragmentation.

Organisation de la corbeille

Encore une fois, la unsorted bin n’est constituée que d’une seule corbeille qui peut contenir plusieurs blocs. Voici les spécificités de la gestion des blocs dans 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 (si sa taille est évidemment adaptée à la taille demandée lors de l’allocation) ;
• si un ou plusieurs blocs contigus sont libérés, ils sont consolidés en un seul bloc libre de plus grande taille.

Le fait que la liste soit doublement chaînée et circulaire implique plusieurs choses :

1. chaque bloc pointe vers son prédécesseur et son successeur via les pointeurs fd et bk ;
2. le prédécesseur du premier bloc et le successeur du dernier bloc sont une adresse dans l’arène.

Pour y voir plus clair concernant le fonctionnement de la liste chaînée et de la consolidation, prenons deux exemples :

• dans le premier exemple, les blocs libérés seront consolidés ;
• dans le deuxième exemple les blocs ne seront pas fusionnés.

Lorsque des blocs libres sont présents dans différents types de corbeilles et qu’une allocation est demandée, voici l’ordre de recherche : tcache ➡️ fastbins ➡️ small bins ➡️ unsorted bins ➡️ large bins (source).

↕️ Consolidation des blocs

1. Trois blocs A, B et C de 0x500 octets sont alloués. Un quatrième bloc est alloué afin d’éviter la consolidation du bloc C, une fois libéré, avec le bloc du sommet ;
2. le bloc A est libéré et tombe dans la unsorted bin. Étant donné qu’il est le seul bloc, il pointe, de part et d’autre, vers la unsorted bin qui elle-même pointe vers lui ;
3. le bloc B est libéré et est consolidé avec le bloc A ;
4. le bloc C est libéré et est fusionné de la même manière. Au final, il n’y a qu’un seul bloc de 0xf00 (0x500 * 3 ) dans l’unsorted bin.

Nous verrons un peu plus loin comment le premier et dernier bloc pointent vers l’arène. Pour le moment, faisons comme si la unsorted bin avait réellement une place attitrée quelque part en mémoire.

Pour rappel, fd est l’abréviation de forward qui désigne le bloc suivant. Tandis que bk est l’abréviation de backward qui désigne le bloc précédent.

🔃 Liste doublement chaînée circulaire

Que se passe-t-il dans le cas où plusieurs blocs sont placés dans la unsorted bin ?

1. Cette fois-ci, les trois blocs de 0x500 sont séparés par des blocs de petite taille afin de ne pas déclencher de consolidation ;
2. le bloc A est libéré : comme il n’y a qu’un seul bloc dans la unsorted bin, il pointe de part et d’autre vers la unsorted bin et inversement ;
3. le bloc B est libéré : étant donné que la structure est de type FIFO, le bloc B est placé derrière le bloc A. Désormais, la unsorted bin pointe vers le bloc A, qui est son premier bloc, et le bloc B, qui est son dernier bloc ;
4. le bloc C est libéré : ce dernier est placé derrière le bloc B. La unsorted bin pointe vers le bloc A (premier bloc) et le bloc C (dernier bloc).

Mon Dieu j’ai la tête qui tourne 😵‍💫.

Le souci des listes à la fois doublement chaînées et circulaires est qu’il y a, en effet, des pointeurs dans tous les sens 😅. N’hésitez pas à revoir le schéma à tête reposée ou de le refaire à la main pour vous assurer de bien avoir compris la gestion des blocs placés dans la unsorted bin.

La unsorted bin pointe vers le premier et le dernier bloc.

🖥️ Dans la vraie vie

Bon, ça c’était sur le papier. Voyons ce que le précédent exemple donne dans gdb. Le code à compiler est le suivant :

#include <stdlib.h>

int main()
{
  // Allocations
  void *a = malloc(0x500);
  malloc(1);
  void *b = malloc(0x500);
  malloc(1);
  void *c = malloc(0x500);

  // Evite la consolidation
  malloc(1);

  // Liberations
  free(a);
  free(b);
  free(c);

  return 0;

}

Il n’est pas nécessaire de le compiler avec une version en particulier de gcc, un simple gcc -g main.c -o exe devrait suffire. Lançons le programme fraîchement compilé dans gdb. Mettons un point d’arrêt au return et jetons un œil à ce qui s’est passé :

En y jetant un œil attentif on retrouve les mêmes principes présentés dans les précédents schémas :

• chaque bloc pointe vers le bloc précédent avec le champ bk et le bloc suivant avec le champ fd ;
• le premier et dernier bloc pointent vers l’adresse 0x00007ffff7e1ace0 qui était schématisé, jusque-là, comme étant la unsorted bin.

Voyons de plus près ce que contient cette adresse :

Il s’agit d’une adresse contenue dans l’arène principale. Utilisons la commande arena pour en savoir plus :

Il s’agit des deux premiers éléments du membre bins de l’arène. bins contient les corbeilles du type :

• unsorted bins ;
• small bins ;
• large bins.

Nous aurons longuement l’occasion d’expliciter le fonctionnement et l’agencement des corbeilles dans le tableau bins lors du chapitre sur les small bins.

En somme, il s’agit de toutes les corbeilles “classiques”. Les deux premiers indices sont uniquement utilisés pour la unsorted bin :

• l’index 0 (équivalent de fd) pointe vers le dernier bloc ;
• l’index 1 (équivalent de bk) pointe vers le premier bloc.

Voici ce que ça donne en ajoutant ces informations sur un schéma :

Cela peut paraître contre-intuitif que le champ fd de la unsorted bin ne pointe pas vers le premier bloc A mais cela est en réalité logique. En effet, si on suit le champ fd de chaque bloc on réalise un parcours circulaire de la liste.

Vous savez maintenant comment la unsorted bin est réellement utilisée en mémoire.

♻️ Recyclage et fragmentation des blocs libres

À quoi ça sert d’avoir une corbeille fourre-tout alors qu’il semble exister des corbeilles qui gèrent mieux les blocs de grande taille 🤔 ?

Comme son nom l’indique, la unsorted bin n’est pas triée et n’a pas vocation à être optimisée. Le but de cette corbeille est de réutiliser rapidement des blocs de grande taille, si possible, afin d’éviter de les trier dans une small bin ou large bin.

Ainsi, la unsorted bin est une corbeille “de passage”. Mais que signifie cela concrètement ? Prenons les deux exemples suivants :

1. un programme où un bloc de 0x500 octets est libéré avant d’effectuer une allocation de 0x100 octets ;
2. un programme où un bloc de 0x500 octets est libéré avant d’effectuer une allocation de 0x600 octets.

1️⃣ Fragmentation du bloc

Commençons avec le premier cas :

#include <stdlib.h>

int main()
{
  void *a = malloc(0x500);
  malloc(1); // Evite la consolidation

  free(a);

  malloc(0x100);

  return 0;
}

Après libération du gros bloc, ce dernier est bien évidemment placé dans la unsorted bin :

Que va-t-il se passer lorsqu’un bloc de 0x100 octets devra être alloué ? Voici le contenu de la unsorted bin au retour de malloc :

Pas besoin d’être un génie 🤓 pour comprendre ce qui s’est passé : le programme a besoin d’allouer 0x100 octets. Pour satisfaire sa demande, la unsorted bin lui donne volontiers 0x100 octets en les prenant du bloc libre.

2️⃣ Recyclage du bloc

Reprenons la même base de code sauf que cette fois-ci la nouvelle allocation sera de 0x600 octets :

#include <stdlib.h>

int main()
{
  void *a = malloc(0x500);
  malloc(1); // Evite la consolidation

  free(a);

  malloc(0x600); // 0x100 -> 0x600

  return 0;
}

Que se passe-t-il une fois l’allocation terminée ?

Le bloc a été transféré vers une large bin ! Ainsi, tant qu’un bloc libre dans la unsorted bin est réutilisé, totalement ou partiellement, il y reste. En revanche, s’il n’a pas pu satisfaire une allocation, par exemple de plus grande taille, il est transféré dans la small bin ou large bin en fonction de sa taille.

Nous n’allons pas nous étaler ici sur le fonctionnement de ces deux types de corbeilles qui feront l’objet d’un chapitre dédié.

Structure et métadonnées d’un bloc de la unsorted bin

Autant le fonctionnement de la liste doublement chaînée circulaire est, un peu complexe, autant les métadonnées d’un bloc sont très basiques :

Vous remarquerez que nous avons enfin un type de corbeille qui utilise réellement bk pour y stocker un pointeur vers le bloc précédent 🙃.