2006-11-20

AllocMem

Voilà deux semaines que je n'ai pas codé sur ChuOS. Je bloque sur un problème classique en informatique : l'allocation dynamique de mémoire.

J'avais déjà réfléchi depuis un certain temps à l'algorithme que je voulais utiliser, notamment après avoir lu un papier très intéressant de chez Sun sur l'allocateur « Slab ». C'est un allocateur mémoire très performant pour allouer fréquemment des blocs de petite taille. Le papier de Sun en parle bien, mais si on souhaite avoir une petite idée de comment ça fonctionne sans avoir à se plonger dans un PDF un peu laborieux à lire, il y a un joli exposé court avec illustrations sur le site d'Hyperion Entertainment. Il s'agit de la boite qui code l'AmigaOS 4, et c'est l'allocateur mémoire qu'ils ont également choisi pour cette nouvelle mouture de l'OS.

L'allocateur Slab c'est bien, mais pour allouer sa texture 3D en 512×512×512 on a besoin d'un autre type d'allocateur pour gérer de gros blocs. Quelle stratégie employer ?

J'avais initialement prévu un algorithme simple constituant une première marche vers quelque chose de plus évolué :

  • le code de l'allocateur Slab fonctionne par petits blocs de 4096 octets, dont l'adresse mémoire est alignée sur 12 bits, ce qu'on appelle des pages, qui ont l'avantage d'être manipulées facilement par le matériel (x86 ou PowerPC) ;
  • pour gérer des pages, on utilise deux fonctions de l'OS : AllocPages et FreePages, l'OS se chargeant de choisir l'algorithme de son choix pour gérer ces pages.

Allouer juste quelques pages de ci de là est une procédure lente, car il s'agit d'un appel système. Mais pour une première implémentation cela me semblait très bien. Cependant, comme je souhaitais faire un code qui fonctionne à la fois sous ChuOS et sous Windows, je me suis documenté sur les fonctions correspondante au sein de Windows. On y trouve VirtualAlloc et VirtualFree. Malheureusement, la granularité de ces fonctions n'est pas la page, mais le paquet de pages, pour un total de 64 Ko :-/ Pourquoi se limiter à allouer 64 Ko alors que sur x86 les pages font 4 Ko ? Ça vient d'une histoire d'optimisation pour un processeur Alpha.

Du coup, mes intentions initiales ne peuvent pas être mises en œuvre, il va me falloir programmer un algorithme d'allocation sophistiqué pour gérer les gros blocs mémoire. Par conséquent j'ai surtout lu beaucoup de littérature sur le sujet, et j'attends d'avoir l'inspiration nécessaire pour me décider sur une méthode. Ces derniers temps je penche sur l'allocateur buddy, qui casse un gros bloc en plus petits selon des puissances de 2, jusqu'à obtenir la taille souhaitée. Buddy + Slab, il me semble que c'est ce que fait le noyau Linux (à prendre avec des pincettes sachant que je ne suis pas un gourou du noyau Linux).

En attendant que l'inspiration me vienne, je remplis mon agenda :

  • Prison Break saison 1 : fait - saison 2 à faire
  • Scrubs saisons 1, 2 3 : fait - saison 4 à faire
  • Desperate Housewives saisons 1 et 2 : fait
  • Lost saisons 1 et 2 : fait
  • Weeds saison 1 : fait
  • My name is Earl saison 1 : en cours