Dans le article précédent de cette série sur l'implémentation de malloc() et free(), nous avons montré comment il est possible de réutiliser des blocs de mémoire et de réduire le tas en libérant des blocs plus récents. Cependant, la fonction actuelle introduit un problème subtil : elle donne la priorité à la réutilisation des blocs les plus récents, ce qui peut entraîner une augmentation de la consommation de mémoire au fil du temps. Pourquoi cela arrive-t-il ? Décomposons-le.

Réduction du tas en réutilisant les blocs récents

Considérez le scénario suivant. Tout d’abord, nous allouons quatre blocs de mémoire :

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

La structure de la mémoire peut être visualisée comme ceci :

Maintenant, nous publions les premier et troisième blocs…

abfree(ptr1);
abfree(ptr3);

… résultant en la structure suivante :

Ensuite, nous allouons un autre bloc de même taille :

void *ptr5 = abmalloc(8);

Lorsque la fonction abmalloc() commence à rechercher le bloc libre le plus récent, elle réutilise le bloc en haut. Si on libère maintenant le dernier bloc :

Si nous publions maintenant le dernier bloc…

abfree(ptr4);

…on peut réduire la taille du tas d'un seul bloc de 8 octets, puisque le bloc précédent n'est plus libre :

Réutilisation d'anciens blocs

Maintenant, imaginez le même scénario, mais avec une modification : notre fonction commence à rechercher les blocs libres à partir du plus ancien. La structure initiale sera la même…

…et encore une fois nous libérons les premier et troisième blocs de mémoire :

Cette fois, le premier bloc sera réutilisé :

Maintenant, lorsque nous libérerons le dernier bloc, nous aurons deux blocs libres en haut, ce qui nous permettra de réduire le tas de deux blocs de 8 octets :

Cet exemple illustre comment, en donnant la préférence aux blocs les plus récents, nous finissons par accumuler d'anciens blocs inutilisés, gaspillant de la mémoire et conduisant à une croissance inutile du tas. La solution est de modifier la stratégie de recherche, en donnant la priorité à la réutilisation des anciens blocs.

Implémentation de la préférence pour les anciens blocs

Pour résoudre ce problème, nous allons commencer par ajouter un pointeur vers le bloc suivant dans l'en-tête. Nous allons également créer un pointeur global vers le premier bloc, afin de pouvoir lancer la recherche à partir de celui-ci :

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

Nous allons créer des blocs mémoire avec des en-têtes dans deux situations différentes, faisons donc un petit refactoring : nous allons extraire cette logique vers une fonction d'assistance qui alloue et initialise l'en-tête (y compris en définissant le champ suivant avec NULL) :

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

Avec cette nouvelle fonction, nous pouvons simplifier la logique dans abmalloc() :

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  Header *header = last; 
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->previous; 
  } 
  last = header_new(last, size, false); 
  return last   1; 
}

Maintenant, nous avons accès au premier et au dernier bloc, et étant donné un bloc, nous pouvons connaître le précédent et le suivant. Nous savons également que lorsque le pointeur vers le premier bloc est nul, aucun bloc n'a encore été alloué. Donc dans ce cas, nous allouerons le bloc immédiatement et initialiserons le premier et le dernier :

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first   1; 
  }

Si firstit n'est plus NULL, il y a déjà des blocs alloués, nous allons donc commencer à chercher un bloc réutilisable. Nous continuerons à utiliser les en-têtes de variables comme itérateur, mais au lieu de commencer par le bloc le plus récent, la recherche commencera par le plus ancien :

  Header *header = first;

À chaque itération, nous avancerons au bloc suivant de la séquence, au lieu de revenir en arrière jusqu'au bloc précédent :

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->next; 
  }

La logique reste la même : si on trouve un bloc disponible de taille suffisante, il est renvoyé. Sinon, si aucun bloc réutilisable n'est trouvé après avoir parcouru la liste, un nouveau bloc est alloué :

  last = header_new(last, size, false);

Maintenant, nous devons ajuster le bloc qui était le dernier (après l'allocation, l'avant-dernier). Il pointait vers NULL, mais il devrait maintenant pointer vers le nouveau bloc. Pour ce faire, nous définissons le champ suivant du bloc précédent sur le nouveau dernier bloc :

  last->previous->next = last; 
  return last   1; 
}

Ajustements dans abfree()

La fonction abfree() conserve fondamentalement la même structure, mais nous devons maintenant gérer certains cas extrêmes. Lorsque nous libérons des blocs en haut du tas, un nouveau bloc devient le dernier, comme nous le faisons déjà dans cet extrait :

    last = header->previous;
    brk(header)

Ici, l'en-tête du pointeur fait référence au dernier bloc non nul disponible sur la pile. Nous avons deux scénarios possibles :

1. le bloc actuel a un bloc précédent, qui deviendra le nouveau dernier bloc. Dans ce cas, nous devrions définir le pointeur suivant de ce bloc sur NULL.
2. le bloc actuel n'a pas de bloc précédent (c'est-à-dire qu'il s'agit du premier et du plus ancien bloc). Lorsqu'elle est libérée, la pile est vide. Dans ce cas, au lieu d'essayer de mettre à jour un champ d'un bloc inexistant, nous le mettons d'abord à NULL, indiquant qu'il n'y a plus de blocs alloués.

Voici comment nous le mettons en œuvre :

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

Conclusion

Nos fonctions abmalloc() et abfree() ressemblent désormais à ceci :

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first   1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header   1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last   1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

Ce changement nous permet d'économiser considérablement plus de mémoire. Il reste cependant encore des problèmes à résoudre. Par exemple, considérons le scénario suivant : nous demandons l'allocation d'un bloc mémoire de 8 octets et abmalloc() réutilise un bloc de, disons, 1 024 octets. Il y a clairement du gaspillage.

Nous verrons comment résoudre ce problème dans le prochain article.