Les 4 bins de ptmalloc2, à quoi ils
servent vraiment
Les quatre familles de bins ptmalloc2 : fast bins (sans fusion), unsorted bin (DCLL pour la seconde chance), small bins (moins de 512 octets) et large bins triees par classes de taille.
Maxime Jérôme··5 min de lecture
Prerequis
- Langage C
- Syscalls Linux
- Maniement de GCC
- Introduction a ptmalloc2
- Chunks
- Arenas
Hello ! o/
La derniere fois on avait vu les arenas, enfin surtout comment la heap etait structuree au final. Il y a encore des choses a creuser, et une de ces choses ce sont les bins (les poubelles). En effet, lors de la liberation d'un chunk, celui-ci est automatiquement mis dans une bin, et c'est bien sur le role de free(3).
Pour augmenter les performances de l'allocation memoire, ptmalloc2 implemente plusieurs bins : fast, unsorted, small et large. Ne vous inquietez pas, on va les detailler une par une et comprendre leur fonctionnement et leur utilite.
Fast bins
Comme on l'a vu dans l'article sur les arenas, il y a un tableau de 10 elements qui correspond a fastbinsY. Ces elements sont en realite des listes chainees simplement de tailles 16, 24, 32, jusqu'a 80, avec un pas (step) de 8 octets. Une particularite de ces chunks : on ne permet pas leur fusion pour former un chunk plus gros. Ca les rend ultra-rapides a allouer et liberer, au prix d'une fragmentation potentielle.
Pourquoi pas de fusion ?
malloc/free quasi constant pour ces tailles. fastbinsY (dans malloc_state / arena)
┌─────────────────────────────────────────────────────────────┐
│ [0] taille 16 → [ chunk ] → [ chunk ] → NULL │
│ [1] taille 24 → [ chunk ] → NULL │
│ [2] taille 32 → [ chunk ] → [ chunk ] → [ chunk ] → NULL │
│ [3] taille 40 → NULL │
│ [4] taille 48 → [ chunk ] → NULL │
│ [5] taille 56 → NULL │
│ [6] taille 64 → [ chunk ] → NULL │
│ [7] taille 72 → NULL │
│ [8] taille 80 → NULL │
│ [9] (reserve) → NULL │
└─────────────────────────────────────────────────────────────┘
Chaque chunk freed conserve :
┌────────┬────────┬─────────────────────────────────┐
│ prev │ size │ fd (Forward pointer) → suivant │
│ size │ │ (pas de bk dans les fast bins) │
└────────┴────────┴─────────────────────────────────┘Source : Understanding glibc malloc, sploitfun
Unsorted bin
Dans le cas ou vous liberez un chunk qui correspond a une bin Small ou Large, il est d'abord mis dans l'Unsorted bin. Ca lui donne une 2e chance : si vous devez free une structure pour rea-allouer derriere une structure de meme taille, cette bin prend toute son importance dans les performances.
Il n'y a qu'une seule unsorted bin, et elle est sous la forme d'une DCLL (Doubly Circular Linked List = liste doublement chainee circulaire). Les chunks freed conservent ici deux pointeurs : FD (Forward pointer) et BK (Backward pointer).
unsorted_bin (dans bins[1])
┌──────────────────────────────────────────────────────────┐
│ │
│ ┌──────────────────────────────────────────────────┐ │
│ │ │ │
│ ▼ │ │
│ HEAD ◄──── chunk_A ◄──── chunk_B ◄──── chunk_C │ │
│ │ │ │ │ │ │
│ └──────────┘ │ │ │ │
│ └──────────────┘ │ │ │
│ └──────────────┘──────────┘ │
│ │
│ Structure d'un chunk freed dans l'unsorted bin : │
│ ┌──────────┬──────────┬──────────┬────────────────────┐ │
│ │ prev_sz │ size │ fd │ bk │ │
│ │ │ │ (Forward)│ (Backward) │ │
│ └──────────┴──────────┴──────────┴────────────────────┘ │
└──────────────────────────────────────────────────────────┘Source : Understanding glibc malloc, sploitfun
Small bins
Il y a 62 small bins, toutes sous forme de DCLL (Doubly Circular Linked List, comme l'unsorted bin). Elles acceptent tous les chunks < 512 octets. Elles sont evidemment moins rapides que les fast bins. Les tailles vont de 16 a 504 avec un pas de 8.
Contrairement aux fast bins, la fusion de chunks est ici possible : si deux chunks freed sont adjacents en memoire et qu'on peut satisfaire une demande avec leur reunion, on les coalesce en un seul. Ca evite la fragmentation.
small bins (dans bins[2..63])
bins[2] taille 16 : HEAD ◄► chunk ◄► chunk ◄► HEAD (circulaire)
bins[3] taille 24 : HEAD ◄► chunk ◄► HEAD
bins[4] taille 32 : HEAD ◄► HEAD (vide)
...
bins[63] taille 504 : HEAD ◄► chunk ◄► HEAD
Fusion de chunks adjacents :
┌────────────────────────────────────────────────────────────┐
│ [chunk_A freed] [chunk_B freed] → [chunk_AB fusionne] │
│ taille 64 taille 64 taille 128 │
└────────────────────────────────────────────────────────────┘
Insertion : FIFO (First In, First Out)Large bins
Il y a 63 large bins, pour tous les chunks >= 512 octets. Ce sont les bins les plus lentes : les chunks n'ont pas tous la meme taille dans une meme bin, et la liste est triee. La fusion de chunks est evidemment possible, et heureusement : sinon imaginez les trous en memoire que ca ferait...
Les 63 large bins sont reparties en 6 groupes, chacun couvrant une plage de tailles avec un pas different :
| Nb de bins | Debut (octets) | Fin (octets) | Pas (step) |
|---|---|---|---|
| 32 | 512 | 2432 | 64 |
| 16 | 2433 | 10240 | 512 |
| 8 | 10241 | 40960 | 4096 |
| 4 | 40961 | 131072 | 32768 |
| 2 | 131073 | 524288 | 262144 |
| 1 | 524289 | sans limite | - |
Pourquoi des pas croissants ?
large bin (exemple : bins[64], taille 512..575)
┌────────────────────────────────────────────────────────────────┐
│ │
│ HEAD ◄──────────────────────────────────────────────────┐ │
│ │ │ │
│ ▼ │ │
│ [chunk 568] ◄──fd/bk──► [chunk 568] ◄──fd/bk──► [chunk 524] │
│ │ │ │
│ fd_nextsize ◄────────────────────────────────────────┘ │
│ bk_nextsize ──────────────────────────────────────────► │
│ │
│ Structure chunk freed large bin : │
│ ┌────────┬────────┬────┬────┬─────────────┬─────────────┐ │
│ │prev_sz │ size │ fd │ bk │ fd_nextsize │ bk_nextsize │ │
│ └────────┴────────┴────┴────┴─────────────┴─────────────┘ │
│ trie par taille decroissante │
└────────────────────────────────────────────────────────────────┘Recapitulatif
En resume, les quatre familles de bins de ptmalloc2 et leurs caracteristiques cles :
| Bin | Nb | Taille chunks | Structure | Fusion |
|---|---|---|---|---|
| Fast | 10 | 16..80 | Liste simplement chainee (fd seul) | Non |
| Unsorted | 1 | Small ou Large | DCLL (fd + bk) | Oui |
| Small | 62 | 16..504 (< 512) | DCLL (fd + bk) | Oui |
| Large | 63 | >= 512 | DCLL triee (fd + bk + fd_nextsize + bk_nextsize) | Oui |
Article suivant
tcache : pourquoi free() est devenu si rapide