Librairie Malloc

Novembre 2020

Alexandra Demski

Dépôt Github du projet

Généralités

L'objectif principal du projet est d'implémenter mes propres fonctions d'allocation dynamique malloc, free, calloc et realloc en utilisant les appels système permettant de manipuler la limite supérieure du tas.

int brk(void *addr);
void *sbrk(intptr_t increment);

Le Projet

Les Fonctionnalités

Le projet va inclure les fonctions de base ainsi qu'un outil de debug.

xxxxxxxxxx
void* malloc(size_t size);
void* realloc(void *ptr, size_t size);
void* calloc(size_t nmemb, size_t size);
void  free(void *ptr);
void  print_stats();

Chaque bloque alloué comprendra une entête contenant toutes les informations administratives nécessaires au bon fonctionnement de malloc ainsi qu'un espace de données pour stocker des informations.

L'algorithme d'allocation va, dans un premier temps, chercher un bloque alloué libre dont la taille est suffisante. En cas de succès, il retourne l'adresse de la zone et indique le bloque comme utilisé, sinon, en cas d'échec, il crée un nouveau bloque en utilisant sbrk.

Avec cette implémentation minimaliste, désallouer un bloque en mémoire avec la fonction free va seulement changer son statut d'utilisé à libre.

L'outil de debug print_stats affichera des informations utiles comme le nombre total de bloque alloué, utilisé et libre, leur taille et la quantité d'espace gâché.

La Structure

Le projet est divisé en plusieurs fichier. La majeure partie du code est stockée dans memory.c qui possède également un header memory.h incluant les fonctions. Les nombreux fichiers test.c sont utilisés pour confirmer l'efficacité de la librairie. Le dernier fichier appelé Makefile permet tout simplement de compiler tout le code : on utilisera la commande make pour créer tous les fichiers executables nécessaires.

Le Code

Bloque

Un bloque de mémoire possède des informations utiles qui seront toutes stockées dans un header.

xxxxxxxxxx
struct block {
    size_t size;
    size_t used_size;
    struct block *next;
    struct block *previous;
    int free;
};
#define META_SIZE sizeof(struct block)

Cette structure de données fonctionne comme une liste chaînée : chaque bloque va pointer vers le précédent et le suivant. Le premier bloque de la liste sera appelé first et initialisé à NULL puisque malloc n'a pas encore été appelé.

xxxxxxxxxx
void *first = NULL;

Malloc

La première étape avant d'allouer un bloque est d'aligner la taille demandée. Cela permet de rendre le programme plus rapide et efficace. Ainsi, dans la fonction malloc nous allons appeler la méthode align qui retourne un multiple de 4 de la taille donnée.

xxxxxxxxxx
size_t align(size_t size){
    size_t n = size;
    if(!multiple4(n)){
        return ((n/4)+1)*4;
    }
    return n;
}

La fonction multiple4 vérifie seulement si la taille donnée n'est pas déjà un multiple de 4 et qui donc n'a pas besoin d'être alignée.

xxxxxxxxxx
int multiple4(size_t n){
    int x = (int)n;
    while(x > 0){
        x = x-4;
    }
    if(x == 0){
        return 1;
    }
    return 0;
}

Bien évidemment, après avoir aligné la taille, on vérifie si elle est inférieure ou égale à zéro pour ainsi éviter tout comportement anormal.

Après cela, on distingue deux possibilités : on utilise malloc pour la première fois et nous avons donc pas besoin de chercher de bloque libre ou on a déjà appelé malloc et on doit, par conséquence, parcourir la liste chaînée.

​x
void *_malloc (size_t size) {
    struct block *b;
    size_t s;
    s = align(size);
​
    if(s <= 0)
        return NULL;
    if(!first){
        b = _new_block(NULL,s);
        if(!b)
            return NULL;
        first = b;
    } else {
        struct block *last = first;
        b = _find_block(&last, s);
        if(!b){
            b = _new_block(last, s);
            if(!b)
                return NULL;
        } else {
            b->free = 0;
            b->used_size = s;
        }
    }
    return(b+1);
}

La fonction _new_block déplace le program break avec l'appel système sbrk et retourne le nouveau bloque créé.

xxxxxxxxxx
struct block *_new_block(struct block* last, size_t size){
    struct block *b;
    b = sbrk(0);
    void *ptr = sbrk(size + META_SIZE);
    if(ptr == (void*)-1)
        return NULL;
    if(last){
        last->next = b;
        b->previous = last;
    }
    b->size = size;
    b->next = NULL;
    b->free = 0;
    b->used_size = size;
    return b;
}

La fonction _find_block cherche à travers la liste chaînée le bloque le plus optimal. Si la fonction n'en trouve pas, elle retourne NULL.

xxxxxxxxxx
struct block *_find_block(struct block **last, size_t size){
    struct block *current = first;
    struct block *optimal = NULL;
    while(current){
        if(current->free && current->size >= size){
            if(optimal){
                if(optimal->size > current->size){
                    optimal = current;
                }
            } else {
                optimal = current;
            }
        }
        *last = current;
        current = current->next;
    }
}

Free

Puisqu'il est impossible de désallouer l'espace mémoire avec sbrk la fonction free va seulement indiquer qu'un bloque est libre. Avant d'appeler la fonction, il est important de vérifier le pointeur passé en paramètre pour éviter des erreurs.

xxxxxxxxxx
void _free(void *ptr) {
    if(!ptr)
        return;
    struct block *b;
    b = _block_ptr(ptr);
    b->free = 1;
    b->used_size = 0;
}

La fonction _block_ptr retourne l'adresse de l'espace alloué pour les données, sans l'en-tête.

xxxxxxxxxx
struct block *_block_ptr(void *ptr){
    return (struct block*)ptr - 1;
}

Calloc

La fonction calloc utilisera notre mallo pour allouer un bloque et mettre ses bits à 0 avec la fonction memset.

xxxxxxxxxx
void *_calloc(size_t nmemb, size_t size){
    size_t s = nmemb * size;
    void *ptr = malloc(s);
    memset(ptr, 0, size);
    return ptr;
}

Realloc

Tout comme calloc la fonction realloc va simplement appeler les fonctions malloc et free pour, tout d'abord, copier les données du bloque passé en paramètre vers un nouveau avec la fonction memcpy, puis libérer ce même bloque. Il est important de vérifier le pointeur passé en paramètre pour éviter toute erreur.

xxxxxxxxxx
void *_realloc(void *ptr, size_t size){
    if(!ptr)
        return malloc(size);
    struct block *b_ptr = _block_ptr(ptr);
    if(b_ptr->size >= size)
        return ptr;
    void *new_ptr;
    new_ptr = malloc(size);
    if(!new_ptr)
        return NULL;
    memcpy(new_ptr, ptr, b_ptr->used_size);
    free(ptr);
    return new_ptr;
}

Les Améliorations

Pour améliorer la librairie, des fonctionnalités supplémentaires ont été ajoutées. En effet, notre librairie génère beaucoup de fragmentation et pour limiter son impact j'ai implémenté deux améliorations.

Division à l'allocation

Avant qu'un bloque libre soit alloué par la fonction _find_block, si sa taille est suffisamment grande, le bloque sera divisé en deux pour générer un nouveau bloque ajouté à la liste chaînée.

xxxxxxxxxx
if(optimal && (optimal->size >= (size + META_SIZE + 4))){ 
    struct block *next, *new;
    next = optimal->next;
    new = _block_ptr(optimal) + size;
    new->next = next;
    optimal->next = new;
    new->previous = optimal;
    if(next != NULL){
        next->previous = new;
    }
    new->size = optimal->size - size - META_SIZE;
    optimal->size = size;
    new->free = 1;
    new->used_size = 0;
}

Fusionnement à la libération

L'amélioration complémentaire de la fonctionnalité précédente va fusionner les voisins d'un bloque à sa libération si eux aussi sont libres. Cette fonctionnalité fonctionne de façon similaire que la précédente mais au lieu d'ajouter un nouvel élément à la liste, on en supprime en les fusionnant.

xxxxxxxxxx
struct block *n, *p;
n = b->next;
p = b->previous;
if(n && n->free){
    b->next = n->next;
    b->size = b->size + n->size + META_SIZE;
}
if(p && p->free){
    p->next = b->next;
    p->size = p->size + b->size + META_SIZE;
}