Tout le monde (enfin .... presque) connaît la fonction malloc dans la bibliothèque standard. Mais beaucoup se demandent comment recoder cette fonction, comment allouer de la mémoire sans malloc ?

Note: Cet article est un peu dépassé, les dernière versions se trouvent sur http://git.iksaif.net

Allocation de mémoire

brk - man

 brk()  positionne  la fin du segment de données (le premier mot mémoire
 hors de la zone accessible) à l’adresse spécifiée par end_data_segment.
 Cette  valeur doit être raisonnable, le système doit avoir suffisamment
 de mémoire, et le processus ne doit pas dépasser sa taille maximale  de
 segment de données (voir setrlimit(2)).

 sbrk() incrémente l’espace de données du programme de increment octets.
 sbrk() n’est pas un appel  système,  juste  une  fonction  de  la  bib‐
 liothèque  C.  Appeler  sbrk()  avec  un incrément nul permet d’obtenir
 l’emplacement de la limite actuelle.
 Si elle réussit, la fonction brk() renvoie zéro. En cas d’erreur,  elle
 renvoie  -1  et  remplit errno avec la valeur d’erreur (voir la section
 NOTES SUR LINUX ci‐dessous).

 sbrk() retourne un pointeur  sur  le  début  de  la  nouvelle  zone  de
 données.  En  cas  d’échec  -1  est  renvoyé, et errno contient le code
 d’erreur ENOMEM.

mmap - man

Voir la manpage, mais de toute façon mon implémentation actuelle utilise brk/sbrk. Le mieux serait d'utiliser mmap, et ça sera fait dans une prochaine version.

Implémentation

Simple

Un implémentation simple consiste à faire une liste chaînée de tout les bouts de mémoires alloués lors d'un malloc. une utilise une structure de ce type:

struct s_chunk
{
   struct s_chunk *prev;
   size_t size;
   bool used;
};

Lors de chaque appel à malloc(size), on appelle sbrk(sizeof(s_chunk) + size). On utilise les sizeof(s_chunk) premier bit pour la structure utilisée dans la liste chaînée. Le reste est le bout de mémoire qu'on peut donner à l'application. Lors d'un free, il suffit de marquer used à false. Il est ainsi possible de parcourir la liste à la recherche d'un bout de bonne taille avant d'allouer encore plus de mémoires.

En gros, ça nous donne:

static t_chunk *list = NULL;
void *malloc(size_t size)
{
   s_chunk *chunk = sbrk(sizeof(*chunk) + size);
 
   chunk->size = size;
   chunk->prev = NULL;
   chunk->used = true;
   if (list)
     list->prev = chunk;
   list = chunk; 
   return chunk + 1; 
 }
void free(void *p)
{
   t_chunk *chunk = p;
   chunk -= 1;
   chunk->used = false;
}

Bon, cette approche est plutôt simple mais pose plusieurs problème. Tout d'abord la mémoire n'est pas alignée, mais pour ça il suffirais que t_chunk soit une structure dont la taille est une puissance de sizeof(long). Mais surtout, on à beaucoup de fragmentation, et la recherche de bout de bonne taille est très lente. Enfin la mémoire n'est jamais retournée au système.

Afin d'améliorer un peu les performances, il est possible d'utiliser juste une liste pour les bouts non utilisés, ce qui réduira la taille de la liste. Mais la complexité sera encore en O(n).

Mon choix

Avec encore plus de listes

J'utilise deux constantes

# define MALLOC_SHIFT_LOW       1
# define MALLOC_SHIFT_HIGH      10

La solution que j'ai adoptée comporte une liste de tout les bouts (nécessaires pour split/fusion, voir après) et 2^10+1 liste de morceaux libres. La taille des bouts est compté en sizeof(t_chunk) et non en bytes.

  • Tout les bouts dont la taille est plus petite que 2^MALLOC_SHIFT_LOW sont rangés ensembles.
  • Tout les bouts dont la taille est plus grande que 2^MALLOC_SHIFT_HIGH sont rangés ensembles.
  • Les autres bouts sont rangés avec leurs copains de puissance de 2 similaire (ou la puissance est entre MALLOC_SHIFT_LOW et MALLOC_SHIFT_HIGH).

split/fusion

Si on ne trouve pas de morceau alloué de la bonne taille, on en choisis un tros grand, et on le coupe en deux. La deuxième partie restera ainsi dans la liste des bouts libres. Lorsqu'on libère un morceau, si c'est possible, on le fusionne avec les bouts adjacents libres. C'est là que la liste de tout les bouts est nécessaire car elle garde les bouts dans l'orde dans le quel ils ont été alloués. Il est ainsi possible de retrouver très facilement les bouts adjacent.

Utilisation

Pour utiliser ce malloc dans vous programmes sans les recompiler (ça à très peut d'interêt, mais bon) vous pouvez utiliser le script mallocize.sh présent dans l'archive. En gros ça revient à rajouter le chemin de la lib dans la variable d'environement LD_PRELOAD.

Il est aussi possible de bidouiller le tout pour compiler vos programmes avec.

Télécharger

malloc-0.1.tar.gz

Liens