Hey mon ami? T'as toujours voulu faire des malloc/free en assembleur?
L'article du jour va aborder l'organisation dynamique de la mémoire. Je n'invente rien, c'est l'algorithme free list avec fusion, un algorithme de distribution efficace qui s'auto-nettoie. Nous aborderons brièvement la version naïve qui libère des blocs et fini par limiter l'utilisation de la mémoire car elle finit par ne proposer que des blocs de petite taille.
L'algorithme free list tient à jour une liste de blocs de mémoire disponible. Mais pour avoir de la mémoire disponible, il faut déjà lui donner de la mémoire à utiliser, d'un seul tenant : C'est le HEAP
Nous allons donc nous créer un heap et l'initialiser.
struct memblock taille defw ; taille utile (hors entête) suivant defw ; bloc libre suivant endstruct free_list defw 0 ; pas de mémoire disponible par défaut memoryInit ; HL=début du bloc ; BC=taille du bloc ld (free_list),hl dec bc : dec bc : dec bc : dec bc ; corriger d'une taille d'entête ld (hl),c : inc hl : ld (hl),b : inc hl ld (hl),0 : inc hl : ld (hl),0 ; pas d'autre bloc libre ret programmePrincipal ld hl,heap ld bc,#BF00-finProgramme call memoryInit ... finProgramme |
Dans cet exemple, encore très théorique, nous disons que nous voulons utiliser toute la zone depuis la fin du programme jusqu'à l'adresse #BF00. On se réserve la plage #BF00-#BFFF pour la pile par exemple et bien entendu, la fin de la mémoire pour l'affichage graphique de notre cher Amstrad CPC.
L'allocateur mémoire
L'allocateur mémoire est plutôt simple. Il parcourt la liste des blocs libres jusqu'à en trouver un de taille suffisante. Je vais l'écrire volontairement avec IX pour être plus clair mais ça s'optimise bien sans, avec un peu de gymnastique ;)
memoryAlloc ; BC=taille souhaitée ld ix,(free_list) : ld iy,0 .boucleSurLesBlocs ld a,xh : or xl : jp z,guruMeditation ; plus de mémoire disponible ; est-ce que le bloc courant est assez grand? ld hl,(ix+memblock.taille) sbc hl,bc : jp m,.blocSuivant ; est-ce qu'on va découper le bloc? ld hl,(ix+memblock.taille) : dec hl : dec hl : dec hl : dec hl sbc hl,bc : jp m,.blocEntier : jr nz,.decoupeBloc .blocEntier ld hl,(ix+memblock.suivant) ld a,yl : or yh : jr z,.entierMAJFreeList; A-t'on déjà lu un bloc avant celui là? ld (iy+memblock.suivant),hl .renvoieZone ld hl,{sizeof}memblock : ld de,ix : add hl,de : ret ; HL=zone mémoire allouée .entierMAJFreeList ld (free_list),hl : jr .renvoieZone .decoupeBloc ; on créé un nouveau bloc HL dans le bloc courant + size ld de,ix : ld hl,4 : add hl,de : add hl,bc ; HL=nouveau bloc ; on relie ce nouveau bloc à free_list ou au bloc précédent ld a,yl : or yh : jr z,.decoupeMAJFreeList ld (iy+memblock.suivant),hl : jr .apresLien .decoupeMAJFreeList ld (free_list),hl .apresLien push hl : pop iy ; IY=nouveau bloc (plus besoin du précédent ici) ld hl,(ix+memblock.taille) : sbc hl,bc : ld de,-{sizeof}memblock : add hl,de : ld (iy+memblock.taille),hl ld hl,(ix+memblock.suivant) : ld (iy+memblock.suivant),hl ld (ix+memblock.taille),bc ld hl,{sizeof}memblock : ld de,ix : add hl,de : ret ; HL=zone mémoire allouée .blocSuivant ; IY=IX, IX=IX.suivant push ix : ld de,(ix+memblock.suivant) : ld ix,de : pop iy jr .boucleSurLesBlocs |
Notre liste de blocs libre termine par "suivant" qui vaut NULL (ou zéro). Si on arrive en fin de liste, on peut appeler une fonction dédiée qui bloque le programme et affiche du rouge dans le border, plutôt que chercher à gérer le manque de mémoire. Si vous avez quelques souvenirs des années 90 et du manque de mémoire sous Windows, ça devenait contreproductif de tenter de gérer le manque de mémoire, car afficher une fenêtre pour dire qu'il manque de la mémoire requiert encore plus de mémoire et on s'en sortait rarement bien. Fin de la parenthèse.
Visualiser facilement nos allocations mémoires
Nous avons assez de code pour passer à quelque chose de plus visuel :)
Plaçons notre HEAP dans la mémoire vidéo, l'entrelacement naturel nous permettra de bien lire nos zones. Un explorateur mémoire ne sera pas de trop pour confirmer nos valeurs.
buildsna : bankset 0 : org #100 : run #100 : di : ld sp,#100 ld hl,#C000 ; HEAP dans la mémoire vidéo! ld bc,16384 ; on prend les 16k call memoryInit ; on alloue 4 zones de 64,64,96 et 64 octets ld bc,64 : call memoryAlloc : push hl ; sauvegarder le pointeur ld bc,64 : call memoryAlloc : push hl ; sauvegarder le pointeur ld bc,96 : call memoryAlloc : push hl ; sauvegarder le pointeur ld bc,64 : call memoryAlloc : push hl ; sauvegarder le pointeur ; et on rempli les zones allouées de couleurs différentes pop hl : ld (hl),#F0 : ld de,hl : inc de : ld bc,63 : ldir pop hl : ld (hl),#0F : ld de,hl : inc de : ld bc,95 : ldir pop hl : ld (hl),#FF : ld de,hl : inc de : ld bc,63 : ldir pop hl : ld (hl),#C3 : ld de,hl : inc de : ld bc,63 : ldir jr $ |
Vous pouvez télécharger le source complet [ICI] si vous voulez jouer.
Visuellement, nous voyons 4 traits de longueur 64, 64, 96 et 64.
À l'explorateur mémoire, nous voyons chaque trait précédé de son entête sur 4 octets, confirmant la longueur de la zone. Enfin, le dernier entête disponible après nos traits est pointé par free_list et contient la quantité de mémoire restant dans notre programme, ici #3ECC (inversion Intel des valeurs 16 bits) soit 16076 octets restants :)
Comment libérer la mémoire allouée dynamiquement?
Nous avons vu précédemment que nos zones mémoires sont toutes précédées de l'entête de bloc. Pour savoir ce qu'on libère et le rendre disponible à nouveau, le free naïf est ultra-simple : Nous allons connecter le bloc à notre liste de blocs disponibles.
memoryFree ; HL=pointeur à libérer dec hl : ld (hl),hi(free_list) : dec hl : ld (hl),lo(free_list) dec hl : dec hl : ld (free_list),hl ret |
Et c'est...
...tout!
Bien entendu, ce free naïf pose un énorme problème. Chaque bloc de mémoire libéré ne peut être réutilisé qu'à l'identique ou plus petit. Même si nous libérons toute la mémoire, elle est définitivement fragmentée.
Néanmoins, selon votre contexte d'utilisation et si vous savez que toutes vos allocations sont libérées après usage, vous pouvez carrément ne rien libérer et relancer un memoryInit!
Fusionner les blocs libres pour éviter la fragmentation mémoire
Fusionner les blocs libres est idéal. Le temps de libération est un peu plus long puisqu'il faut parcourir et manipuler les blocs mais le temps d'allocation se voit en conséquence raccourci!
On doit d'abord trouver où notre bloc mémoire à libérer se situe au niveau des blocs libres pour l'insérer dans la liste des blocs libres en respectant l'incrémentation des adresses (insertion triée).
Une fois qu'on s'est inséré au bon endroit, on regarde le bloc suivant (si il existe). Si le bloc suivant démarre à la fin de celui qu'on libère, on fusionne!
Fusion du bloc courant avec le suivant :
- augmentation de la taille du courant de celle du suivant + taille entête
- bloc suivant du bloc courant devient le bloc suivant du bloc suivant (et le suivant disparait de la liste)
Enfin, on compare avec le bloc précédent, si il existe (IY!=zéro). C'est à peu près la même comparaison : Est-ce que le bloc précédent + entête + sa taille tombe sur notre bloc courant?
Si oui, fusion avec le bloc précédent :
- on augmente la taille du bloc précédent de celle du courant + taille entête
- le suivant du précédent devient le suivant du courant (et notre courant disparait de la liste)
Ouf! Voici le source!
memoryFree ; HL=pointeur à libérer ld bc,-4 : add hl,bc ; HL=pointeur du bloc à libérer ld bc,0 ; init du bloc précédent ex hl,de : ld hl,(free_list) ; DE=bloc à libérer HL=premier bloc de la liste .chercheInsertion ld a,h : or l : jr z,.trouveInsertion or a : sbc hl,de : add hl,de ; CP HL,DE jp p,.trouveInsertion ld bc,hl ; précédent=courant inc hl : inc hl : ld a,(hl) : inc hl : ld h,(hl) : ld l,a ; courant=courant.suivant jr .chercheInsertion .trouveInsertion ld ix,de ; IX=bloc à libérer ld (ix+memblock.suivant),hl ; le bloc à libérer pointe vers suivant ou NULL ld a,b : or c : jr z,.pasDePrecedent ld iy,bc : ld (iy+memblock.suivant),de : jr .depuisPrecedent .pasDePrecedent ld (free_list),de : .depuisPrecedent ; notre cellule est liée ; test de fusion avec le suivant si il y a un suivant ld a,(ix+memblock.suivant) : or (ix+memblock.suivant+1) : jr z,.pasDeSuivant ld hl,4 : add hl,de : ld bc,(ix+memblock.taille) : add hl,bc : ld bc,(ix+memblock.suivant) : sbc hl,bc : jr nz,.pasDeSuivant ld de,(ix+memblock.taille) : inc de : inc de : inc de : inc de ; bloc.taille+4 ld hl,(ix+memblock.suivant) : ld a,(hl) : inc hl : ld h,(hl) : ld l,a ; bloc.suivant.taille add hl,de : ld (ix+memblock.taille),hl ; taille fusionnée ld hl,(ix+memblock.suivant) : inc hl : inc hl : ld a,(hl) : inc hl : ld h,(hl) : ld l,a ; bloc.suivant.suivant ld (ix+memblock.suivant),hl ; bloc suivant retiré de la liste et son suivant copié dans le bloc courant .pasDeSuivant ; test de fusion avec le précédent, si il en existe un ld a,yl : or yh : ret z ld hl,4 : ld de,iy : add hl,de : ld de,(iy+memblock.taille) : add hl,de : ld de,ix : sbc hl,de : ret nz ld hl,(iy+memblock.taille) : ld de,(ix+memblock.taille) : add hl,de : ld de,4 : add hl,de : ld (iy+memblock.taille),hl ld hl,(ix+memblock.suivant) : ld (iy+memblock.suivant),hl ret |
Un test de stress pour notre allocateur mémoire
Sur le principe du précédent programme de visualisation de nos allocations, nous allons allouer/libérer aléatoirement des zones d'une taille variable, puis recommencer.
Nous verrons rapidement si nos zones allouées s'étendent ou si la libération s'effectue correctement. Ces libérations partielles permettent de tester que la fragmentation se résorbe bien en accord avec notre algorithme.
Le programme va utiliser un tableau de 8 pointeurs, il se déplace dedans au hasard, alloue ou libère. Enfin, pour rester visuel, on effacera les zones avant libération et on remplira de couleur à l'allocation.
Si vous voulez télécharger le source de démonstration, ça se passe [ICI]
