La fonction malloc, définie dans l'en-tête <stdlib.h>, alloue un bloc de mémoire contigu d'une taille spécifiée et renvoie un pointeur vers celui-ci. Son portotype est : void *malloc(size_t size).

Pour comprendre les raisons des bonnes pratiques associées à son utilisation – comme la nécessité de libérer la mémoire allouée pour éviter les fuites, ou les dangers d'un accès hors limites – il est instructif d'en réaliser une implémentation simplifiée. Cet exercice permet de maîtriser la gestion des pointeurs et de découvrir les mécanismes sous-jacents.

L'approche repose sur une gestion explicite de la zone de mémoire (le tas ou heap). Chaque bloc alloué est précédé d'un en-tête de contrôle qui permet de constituer une liste chaînée des blocs libres et occupés.

Structure de contrôle des blocs

Chaque bloc de mémoire, qu'il soit alloué ou libre, est précédé d'un en-tête de contrôle dont la structure est la suivante :

typedef struct {
    int est_libre;           /* 1 si le bloc est libre, 0 s'il est alloué */
    size_t taille_precedente; /* Taille du bloc libre précédent */
    size_t taille_bloc;      /* Taille des données utiles du bloc courant */
} EnTeteBloc;

Cet en-tête établit une liste doublement chaînée au sein de la zone mémoire gérée. Grâce à taille_bloc, on peut parcourir la liste vers l'avant ; avec taille_precedente, on peut la parcourir vers l'arrière.

Algorithme de l'allocation (malloc)

Lors d'un appel à malloc, la fonction parcourt la liste des blocs depuis le début de la zone mémoire gérée. Elle recherche un bloc libre dont la taille est suffisante. Plusieurs cas se présentent :

1. Correspondance exacte : Si la taille du bloc libre correspond exactement à la demande, le bloc est marqué comme alloué (est_libre = 0) et un pointeur vers sa zone de données est renvoyé.
2. Bloc plus grand : Si le bloc est libre et qu'il est assez grand pour contenir à la fois la taille demandée et un nouvel en-tête de contrôle pour le bloc restant, alors le bloc est scindé. La partie avant est allouée à l'utilisateur. Un nouvel en-tête est créé pour la partie restante, qui est marquée comme libre.
3. Bloc insuffisant : Si le bloc est trop petit, on passe au bloc suivant dans la liste. La recherche continue ainsi jusqu'à trouver un bloc convenable ou jusqu'à la fin de la zone mémoire.

Si aucun bloc approprié n'est trouvé, la fonction renvoie NULL.

Algorithme de la libération (free)

Lorsqu'un bloc est libéré, son en-tête est marqué comme libre (est_libre = 1). Ensuite, la fonction tente de fusionner ce bloc avec ses voisins adjacents (précédent et suivant) si ceux-ci sont égalemant libres. Cette consolidation réduit la fragmentation et permet de récupérer des blocs plus grands.

• Si le bloc suivant est libre, les deux blocs sont fusionnés en un seul. L'en-tête du bloc suivant est alors supprimé de la liste.
• De même, si le bloc précédent est libre, la fusion est effectuée dans l'autre sens.
• Après une fusion, les en-têtes des blocs voisins encore existants sont mis à jour (notamment leur champ taille_precedente).

Initialisation de la zone mémoire (malloc_init)

Une fonction d'initialisation est nécessaire pour configurer la zone mémoire à gérer. Elle prend en entrée l'adresse de début et la taille totale d'un segment mémoire (par exemple, un tableau statique ou une zone allouée par le système).

L'initialisation crée le premier bloc libre, couvrant toute la zone mémoire. Son en-tête est initialisé pour indiquer qu'il est libre et qu'il n'a pas de bloc précédent.

void *zone_memoire;    /* Pointeur vers le début de la zone gérée */
size_t taille_zone;    /* Taille totale de la zone gérée */
int initialise = 0;    /* Drapeau d'initialisation */

void init_malloc(void *debut, size_t taille) {
    zone_memoire = debut;
    taille_zone = taille;
    
    EnTeteBloc *premier_bloc = (EnTeteBloc *)zone_memoire;
    premier_bloc->est_libre = 1;
    premier_bloc->taille_precedente = 0;
    premier_bloc->taille_bloc = taille_zone - sizeof(EnTeteBloc);
    
    initialise = 1;
}

Exemple d'implémentation

Voici une version simplifiée des fonctions malloc et free basée sur l'algorithme décrit. Le code utilise des adresses absolues pour naviguer dans la zone mémoire.

#include <stddef.h>

/* Déclarations externes de la zone mémoire */
extern void *zone_memoire;
extern size_t taille_zone;
extern int initialise;

void *malloc_simple(size_t taille_demandee) {
    if (!initialise) return NULL;
    
    void *position_courante = zone_memoire;
    void *fin_zone = (char *)zone_memoire + taille_zone;
    EnTeteBloc *bloc_courant = NULL;
    void *resultat = NULL;
    
    while (position_courante < fin_zone) {
        bloc_courant = (EnTeteBloc *)position_courante;
        
        if (bloc_courant->est_libre) {
            if (bloc_courant->taille_bloc == taille_demandee) {
                /* Cas 1 : Taille exacte */
                bloc_courant->est_libre = 0;
                resultat = (char *)position_courante + sizeof(EnTeteBloc);
                break;
            } else if (bloc_courant->taille_bloc >= taille_demandee + sizeof(EnTeteBloc)) {
                /* Cas 2 : Bloc plus grand, scission nécessaire */
                size_t taille_originale = bloc_courant->taille_bloc;
                bloc_courant->est_libre = 0;
                bloc_courant->taille_bloc = taille_demandee;
                
                /* Créer un nouvel en-tête pour le bloc restant */
                void *adresse_nouveau_bloc = (char *)position_courante + sizeof(EnTeteBloc) + taille_demandee;
                EnTeteBloc *nouveau_bloc = (EnTeteBloc *)adresse_nouveau_bloc;
                nouveau_bloc->est_libre = 1;
                nouveau_bloc->taille_precedente = taille_demandee;
                nouveau_bloc->taille_bloc = taille_originale - taille_demandee - sizeof(EnTeteBloc);
                
                /* Mettre à jour le bloc suivant (si existant) */
                void *adresse_bloc_suivant = (char *)adresse_nouveau_bloc + sizeof(EnTeteBloc) + nouveau_bloc->taille_bloc;
                if (adresse_bloc_suivant < fin_zone) {
                    EnTeteBloc *bloc_suivant = (EnTeteBloc *)adresse_bloc_suivant;
                    bloc_suivant->taille_precedente = nouveau_bloc->taille_bloc;
                }
                
                resultat = (char *)position_courante + sizeof(EnTeteBloc);
                break;
            }
        }
        
        /* Passer au bloc suivant */
        position_courante = (char *)position_courante + sizeof(EnTeteBloc) + bloc_courant->taille_bloc;
    }
    
    return resultat;
}

void free_simple(void *pointeur_donne) {
    if (!pointeur_donne) return;
    
    /* Reculer pour trouver l'en-tête du bloc */
    EnTeteBloc *bloc_a_liberer = (EnTeteBloc *)((char *)pointeur_donne - sizeof(EnTeteBloc));
    bloc_a_liberer->est_libre = 1;
    
    void *fin_zone = (char *)zone_memoire + taille_zone;
    
    /* Tentative de fusion avec le bloc suivant */
    void *adresse_bloc_suivant = (char *)bloc_a_liberer + sizeof(EnTeteBloc) + bloc_a_liberer->taille_bloc;
    if (adresse_bloc_suivant < fin_zone) {
        EnTeteBloc *bloc_suivant = (EnTeteBloc *)adresse_bloc_suivant;
        if (bloc_suivant->est_libre) {
            /* Fusion */
            bloc_a_liberer->taille_bloc += sizeof(EnTeteBloc) + bloc_suivant->taille_bloc;
            
            /* Mettre à jour le nouveau bloc suivant */
            void *nouveau_suivant = (char *)bloc_a_liberer + sizeof(EnTeteBloc) + bloc_a_liberer->taille_bloc;
            if (nouveau_suivant < fin_zone) {
                EnTeteBloc *suivant_apres_fusion = (EnTeteBloc *)nouveau_suivant;
                suivant_apres_fusion->taille_precedente = bloc_a_liberer->taille_bloc;
            }
        }
    }
    
    /* Tentative de fusion avec le bloc précédent (si existant et libre) */
    if ((void *)bloc_a_liberer != zone_memoire) {
        /* Calculer l'adresse du bloc précédent via son propre en-tête */
        /* Cette partie est plus complexe car elle nécessite de parcourir la liste */
        /* Implémentation simplifiée non montrée ici */
    }
}

Points de vigilance et conséquences

La gestion manuelle de la mémoire via cette méthode implique plusieurs risques qui expliquent les pratiques de prudence :

• Fuites de mémoire : Ne pas appeler free pour chaque allocation conduit à l'épuisement progressif de la zone mémoire disponible.
• Double libération : Libérer un même bloc plusieurs fois peut corrompre les en-têtes de contrôle, entraînant un comportement imprévisible (crash, corruption de données). L'exemple ci-dessous montre comment la réutilisation d'un pointeur après libération et la double libération peuvent désorganiser la structure des blocs.
• Accès hors limites : Écrire au-delà de la taille allouée d'un bloc peut écraser l'en-tête d'un bloc adjacent, détruisant la cohérence de la liste chaînée et provoquant des erreurs graves lors des futures allocations ou libérations.
• Fragmentation : Même avec la consolidation lors de la libération, des opérations d'allocation/libération répétées de tailles différentes peuvent conduire à une fragmentation où la mémoire libre est morcelée en petits blocs non utilisables pour de grandes requêtes.

Cette implémentation simplifiée, bien que fonctionnelle pour des besoins pédagogiques ou dans des environnements très contraints comme les systèmes embarqués sans système d'exploitation, diffère considérablement des implémentations système (comme glibc) qui utilisent des structures de données plus complexes (comme des bins, des arenas) et interagissent avec le système d'exploitation via des appels comme sbrk ou mmap pour obtenir de la mémoire supplémentaire.