tcache : pourquoi free() est devenu
si rapide

Prérequis

• Langage C
• Syscalls Linux
• Maniement de GCC
• Introduction à ptmalloc2
• Chunks
• Arenas
• Bins

Hello ! o/

Le tcache (thread local cache, ou Thread Cache) a été implémenté à partir de la glibc 2.26, soit fin août 2017. Il a permis de gagner d'importantes performances.

Chaque thread contient une variable locale threadée qui se souvient de quelle arena il a utilisé en dernier. Si cette arena est en cours d'utilisation quand notre thread veut l'utiliser, le thread se bloque et attend que le mutex soit libéré.

Par conséquent, on introduit 2 nouvelles structures de données :

typedef struct tcache_entry
{
  struct tcache_entry *next;
  struct tcache_perthread_struct *key; // double free detection
} tcache_entry;

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread tcache_perthread_struct *tcache = NULL;

Chaque thread contient un pointeur tcache vers une tcache_perthread_struct, qui stocke un petit nombre de chunks libérés accessibles sans avoir à locker une arena. tcache_entry pointe les chunks dans une liste chaînée, comme pour les fastbins, mais pointe sur le user data. Le tableau entries de tcache_perthread_struct est indexé par taille de chunk :

  Thread A
  ┌─────────────────────────────────────────────────────────┐
  │  tcache (tcache_perthread_struct*)                       │
  │                                                         │
  │  counts[0..63]   entries[0..63]                         │
  │  ┌────────────┐  ┌────────────────────────────────────┐ │
  │  │  count[0]  │  │  entries[0] → tcache_entry → NULL  │ │
  │  │  count[1]  │  │  entries[1] → tcache_entry → NULL  │ │
  │  │  ...       │  │  ...                               │ │
  │  │  count[63] │  │  entries[63]→ NULL                 │ │
  │  └────────────┘  └────────────────────────────────────┘ │
  └─────────────────────────────────────────────────────────┘

  tcache_entry (pointe sur le user data, pas le header)
  ┌──────────────────────────────────────────────┐
  │  next  →  tcache_entry suivant (ou NULL)     │
  │  key   →  tcache_perthread_struct du thread  │
  └──────────────────────────────────────────────┘

Source : MallocInternals - glibc wiki

Priorité sur les fastbins

Du coup, avant de tomber dans un fastbin, free() peut faire tomber le chunk dans le tcache ! L'accès au tcache sera donc plus rapide qu'aux fastbins, ce qui en fait une structure très intéressante d'un point de vue performance.

Merci pour votre lecture :)