Implémentation de malloc() et free() — fractionnement de gros blocs

Dans le post précédent de cette série, nous avons vu comment l'ordre dans lequel nous choisissons les blocs de mémoire à réutiliser peut conduire à une consommation de mémoire plus ou moins grande, et nous avons modifié nos fonctions pour éviter cela déchets. Mais nous devons résoudre un autre problème, encore plus grave : parfois, un très gros bloc de mémoire peut occuper l’espace que plusieurs blocs plus petits pourraient utiliser. Prenons le cas ci-dessous, où nous allouons une grande partie de la mémoire, la libérons, puis allouons deux blocs beaucoup plus petits :

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

Ici, nous avons un bloc de mémoire libre de 128 octets, et lorsque nous allouons un bloc de seulement 8 octets, les 128 octets deviennent indisponibles. Lorsque nous allouons un autre bloc de 8 octets, le tas doit à nouveau croître. Ce n'est pas une utilisation efficace de la mémoire.

Il existe au moins deux solutions populaires pour ce cas. L'une, plus efficace, consiste à utiliser des bins : des listes qui regroupent les blocs par taille. Il s’agit d’une approche plus sophistiquée et efficace, mais plus complexe. Une autre option, plus simple, consiste à trouver un gros bloc et à le diviser en blocs plus petits. Nous suivrons cette approche.

Mais rappelez-vous : plus simple ne veut pas dire simple ;-)

Refactorisation initiale

Avant de commencer, faisons une petite refactorisation. Actuellement, la fonction header_new() fait deux choses : elle alloue plus de mémoire pour un nouveau bloc et initialise son en-tête, définissant les métadonnées et les pointeurs vers le bloc précédent. La partie d’initialisation de l’en-tête peut être utile, alors extrayons-la. Nous allons créer deux nouvelles fonctions pour améliorer la lisibilité :

• La fonction header_plug(), qui « branche » le bloc initialisé aux blocs précédent et suivant.
• La fonction header_init(), qui définit les valeurs initiales des métadonnées du bloc (taille et disponibilité).

Voici à quoi ils ressemblent :

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

Maintenant, il ne nous reste plus qu'à modifier header_new() pour utiliser ces nouvelles fonctions :

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

(De plus, nous pouvons supprimer la ligne last->previous->next = last; de la fonction abmalloc(), puisque header_plug() s'en charge désormais.)

Fractionner des blocs

Avec ces outils en main, créons la fonction header_split(). Étant donné un en-tête et une taille minimale requise, cette fonction divise le bloc mémoire en deux si le bloc d'origine est suffisamment grand pour contenir

• la taille requise,
• un nouvel en-tête pour le nouveau bloc, et
• un peu de mémoire supplémentaire.

Tout d'abord, on vérifie si le bloc est suffisamment grand :

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

Si cette condition est remplie, nous scindons le bloc. Tout d'abord, on réduit la taille du bloc actuel en soustrayant la taille d'un en-tête et l'espace demandé par abmalloc :

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

Cela laisse un espace mémoire après le bloc actuel, que nous utiliserons pour créer le nouveau bloc. On calcule le pointeur de ce nouveau bloc :

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

Maintenant que nous avons le pointeur vers le nouveau bloc, nous initialisons son en-tête avec header_init() :

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

Et on connecte le nouveau bloc aux blocs précédent et suivant en utilisant header_plug() :

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

Si le bloc d'origine était le dernier, le nouveau bloc sera désormais le dernier, nous mettons donc à jour le dernier pointeur :

header->size = original_size - size - sizeof(Header);

Enfin, on renvoie le nouveau bloc :

Header *new_header = header + sizeof(Header) + header->size;

Si le bloc d'origine n'est pas assez grand, nous renvoyons simplement le bloc d'origine :

header_init(new_header, size, true);

Mise à jour d'abmalloc()

Maintenant, il suffit de revenir à la fonction abmalloc(), et à l'endroit où l'on trouve un bloc utilisable, on invoque header_split() pour essayer de le diviser :

header_plug(new_header, header, header->next);

Si le bloc peut être divisé, le nouveau bloc sera renvoyé. Dans le cas contraire, le bloc original sera conservé et restitué comme auparavant.

Remarque sur le fractionnement des blocs

Remarquez que nous avons créé le nouveau bloc à la fin du bloc d'origine. Nous aurions pu le créer au début, mais en créant le nouveau bloc utilisé à la fin, le nouveau bloc libre reste plus proche des anciens blocs. De cette façon, il sera trouvé en premier la prochaine fois que abmalloc() sera invoqué.

Le fractionnement de gros blocs de mémoire est un pas en avant, mais il existe un problème inverse : de petits blocs de mémoire peuvent provoquer une fragmentation, et des requêtes plus importantes entraînent une croissance du tas. Nous verrons comment résoudre ce problème dans le prochain post.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!