[THOMSON] Allocateur mémoire TLSF pour 6809

[Bentoc]

Salut,

J'ai le plaisir de partager avec vous une nouvelle routine d'allocation mémoire pour le 6809.
Il s'agit de l'implémentation de l'algorithme TLSF :
https://github.com/bhrousseau/6809-tlsf
Le lien vers la documentation détaillée se trouve dans le readme.md.

Il n'y a pas de spécificité liée aux Thomson, c'est utilisable sur n'importe quelle machine à base de 6809.

TLSF est un algorithme dont la complexité en temps des fonctions d'allocation et de désallocation mémoire est O(1). Le temps d'exécution est donc prévisible et ne dépend pas du niveau de fragmentation de la mémoire.

Il n'y a pas de boucle dans le code pour effectuer la recherche d'un bloc libre d'une taille optimale lors d'une allocation (malloc). Les mécanismes employés permettent d'obtenir ce bloc libre de manière indexée.

Les résultats obtenus en terme de fragmentation mémoire sont proches d'une solution de type "best-fit".

a+ Benoit.

[sporniket]

Merci du partage. Et pour ceux à qui -comme moi- l’acronyme estétait totalement inconnu, c'est donc "Two-Level Segregated Fit" ?

edit: j'ai pu lire l'article lié.

[Bentoc]

Merci d'avoir pris le temps de lire la doc.
Effectivement on parle de "deux niveaux" pour l'indexation, celle ci est basée sur la taille du bloc mémoire requis.
Je reprend ci dessous quelques éléments de la doc, en y ajoutant des précisions.

Exemple d'un bloc de 781 octets dont on demande l'allocation :

Code : Tout sélectionner

0000001 1000 01101
_______ ____
  fl=9  sl=8
(MSB position) (value)

Pour trouver les deux index, on réalise les opérations suivantes :
- on prend la taille du bloc et on calcule la position du bit le plus fort, ça nous donne l'index FL (first level)
- on prend les 4 bits suivants pour former une valeur entre 0 et 15, c'est l'index SL (Second Level)

Dans cet exemple on aura donc un bloc de 781 octets dont l'index FL=9 et SL=8

La recherche du bit le plus fort s'effectue avec la routine suivante :

Code : Tout sélectionner

;-----------------------------------------------------------------
; tlsf.bsr
; input  REG : [tlsf.bsr.in] 16bit integer (1-xFFFF)
; output REG : [B] number of leading 0-bits
;-----------------------------------------------------------------
; Bit Scan Reverse (bsr) in a 16 bit integer,
; searches for the most significant set bit (1 bit).
; Output number is bit position from 0 to 15.
; A zero input value will result in an unexpected behaviour,
; value 0 will be returned.
;-----------------------------------------------------------------
tlsf.bsr.in fdb 0 ; input parameter
tlsf.bsr
        lda   tlsf.bsr.in
        beq   @lsb
@msb
        ldb   #types.WORD_BITS-1
        bra   >
@lsb
            lda   tlsf.bsr.in+1
            ldb   #types.BYTE_BITS-1
!       bita  #$f0
        bne   >
            subb  #4
            lsla
            lsla
            lsla
            lsla
!       bita  #$c0
        bne   >
            subb  #2
            lsla
            lsla
!       bmi   >
            decb
!       rts

Une fois ces deux index obtenus, on va trouver le bloc libre de taille supérieure le plus proche dans l'index des blocs libres.
Cette index de blocs libres est représentée sous la forme d'une bitmap pour l'index FL et d'une bitmap pour l'index SL.
Chaque bit indique la présence ou non d'une liste chainée de blocs libres.
Chaque couple fl/sl détermine la taille des blocs libres, quelques exemples :

Code : Tout sélectionner

fl:5,sl:0 [blocs de 32,33]
fl:5,sl:1 [blocs de 34,35]
fl:5,sl:15 [blocs de 62,63]

Si on poursuit l'exemple, avec les index de blocs libres suivants :

Code : Tout sélectionner

FL : 0000 0101 0000 0000
bitmap SL du niveau FL 08 : 0010 0000 1100 0000
bitmap SL du niveau FL 10 : 0000 0100 0000 0001
(tous les autres bitmap SL sont à 0, car pas de bit FL set)

L'objectif est de trouver l'index FL/SL de la liste chainée qui contient les blocs libres d'une taille suffisante pour stocker le bloc de 781 octets.
Pour ça on utilise le FL=9, on récupère un masque de bits depuis une LUT et on applique ce masque sur le FL bitmap.
On obtient : 0000 0101 0000 0000 & 1111 1110 0000 0000 = 0000 0100 0000 0000
On calcule le bit de poids le plus faible (je vous mets pas le code ici c'est une routine Count Trailing Zeros très proche du BSR ci dessus).
ça nous donne l'index FL=10
On procède de la même manière pour le bitmap SL correspondant au FL=10, ce qui nous donne une position dans une matrice, dans laquelle est stockée l'adresse du bloc libre "best fit". (ici SL=0 si vous avez suivi )

Remarque:
Il s'agit d'un algo proche du "best fit" car dans certains cas particuliers il existe des blocs de taille plus proches qui sont adaptés, mais qu'on ne sélectionne pas.
Par exemple pour notre bloc de 781 octets, on ne prend pas en considération le fl=9/sl=8 dans l'index des blocs libres car celui ci peut contenir des blocs de taille 768 à 799 octets, soit potentiellement des valeurs plus petites que 781 octets.
Cela veut dire également que si un bloc de 790 octet s'y trouve, on ne l'utilisera pas. C'est pour ça que je parle de "proche" d'une solution best-fit.

D'autre part on prend toujours le premier bloc dans la liste chainée des blocs libres, on ne recherche pas celui ayant la taille la plus adaptée.
Si en FL=10/SL=0 on a deux blocs libres de taille 1080 suivi de 1024, on utilisera celui de 1080 octets pour couvrir les 781 octets demandé dans notre exemple, car c'est le premier de la liste.

[Fool-DupleX]

J'ai peut-être lu trop vite, mais tu peux nous en dire un peu plus sur la taille du code en mémoire et le nombre de cycles nécessaires pour exécuter une allocation ?

[Bentoc]

Je te dis ça dès que je suis de retour de mon déplacement pro.

[Bentoc]

Après avoir laissé tourner en boucle des allocations/désallocations de tailles aléatoires pendant plusieurs minutes,
j'ai relevé une vingtaine de temps d'exécution, ces temps comprennent l'appel et le retour à la routine.
Pour bien faire, il faudrait compter les cycles de la branche la plus longue du code (comme il n'y a pas de boucle), mais je ne l'ai pas encore fait ...
Enfin ça te donnera une idée assez réaliste.
Edit Il n'y a pas de boucle dans le code, donc j'ai ajouté un décompte manuel des cycles dans le pire des cas (branche la plus longue ci dessous).

malloc
minimum : 851 cycles
maximum : 1107 cycles
Edit branche du code la plus longue : 1242 cycles

free
minimum : 369 cycles
maximum : 1082 cycles
Edit branche du code la plus longue : 1360 cycles

Taille du code :
406 octets : index des blocs libres
878 octets : routines + variables

Overhead en mémoire :
4 octets par zone allouée