Dans le cadre de mes forums, je me suis fait deux allocateurs utilisant de la shared.
 
Il s'agit d'un allocateur de blocs de taille fixe (cad. qu'il renvoie des blocs faisant toujours la même taille). Pour l'implémenter, j'utilise une liste chaînée de headers. Un header pointe sur un morceau de mémoire. Le header comporte un champ de bits correspondant à l'état d'utilisation pour chacun des blocs (0/1 pour utilisé ou non). Ce champ de bits est variable selon la taille du morceau de mémoire et la taille des blocs à retourner. Ca donne un système avec un overhead assez faible en terme de mémoire (la taille des headers+1 bit par bloc % les conneries d'alignement). Concernant la manipulation des bits, j'ai préféré utiliser des masques précalculés plutôt que d'avoir à faire des opérations de décalage. Je n'ai pas testé mais a priori ça doit être plus rapide. Dans l'ensemble, c'est plutôt simple et efficace.
 
Maintenant, mon problème est de faire la même chose mais avec un allocateur retournant des blocs de taille variable. Là, je me pose des questions.
 
A priori, il me faut utiliser le même type de champ de bits pour l'utilisation.  
 
Après, une première implémentation serait de faire une liste chaînée entre les blocs. Ca donne la taille du bloc encours via calcul relativement au suivant (offset_next-offset(bloc)) sauf pour le dernier où il faut se servir de taille du morceau où sont alloués les blocs. Comme avantage, c'est pratique à parcourir en partant d'un bloc vers ses suivants. Par contre, il faut se parcourir tous les blocs du header depuis le début pour trouver le précédent (par exemple quand on libère un bloc pour savoir si le précédent est libre et si on doit donc faire un merge des deux blocs).
 
L'autre solution serait d'utiliser un champ avec les positions de chaque bloc. La taille se déterminerait aussi via calcul relativement au suivant et aussi sauf pour le dernier. L'avantage, c'est qu'en ayant l'index d'un bloc, on peut directement savoir où il se trouve, donc pas de recherche à faire pour le précédent. L'autre avantage qui me semble pas mal, c'est que cela groupe les positions dans les mêmes pages mémoire. Le gros inconvénient, c'est que les tailles étant variables, il faut trouver l'index du bloc pour pouvoir faire une opération dessus (systématiquement lors d'un realloc ou d'un free par exemple) et donc parcourir le champ des positions pour le trouver.
 
A priori, vous choisiriez quelle solution? (si vous en avez une meilleure, je suis aussi preneur)

Pour tes masques je ne suis pas sur que ce soit vraiment une bonne idée de les précalculer, y'a beaucoup de processeurs sur lesquels un décalage binaire est plus lent qu'un accès en mémoire ?
 
Sinon y'a un truc qui m'étonne, c'est que tu veuille lister les blocs occupés et pas les blocs libres, mais j'ai peut-être raté quelque chose (j'ai vraiment lut le code en diagonale). En listant les blocs occupés, plus tu alloue de petits packets, même consécutifs, plus tu ralentis ton système (augmentation du temps de scan pour les merge). En listant les blocs libres, si tu as de nombreux blocs petits consécutifs, ta liste reste petite, et une allocation se limite à réduire par l'avant un bloc libre sans toucher à la liste (sauf si tu mange complètement un bloc, ou que tu as plusieurs listes selon la taille).
 
Si tu veut un faible overhead de header, regarde du coté des buddy allocator avec les puissances de 2, la détermination de la taille du bloc se fait uniquement par la valeur du pointeur et les merges sont en log de la liste des libres si ma mémoire est bonne. (Par contre la frag interne peut ne pas être super bonne selon les cas d'utilisation).

 
Hrum. Je crois que j'ai besoin de vacances
 

 
Si vous parlez du code et donc de l'allocateur "fixe", je fais ainsi pour réduire l'overhead au max. Si l'on excepte le header, un bloc, alloué ou non, ne consomme qu'un seul bit. Si je procède au moindre chaînage, ça va me prendre 32 ou 64 bits en plus selon la plateforme. Dans la mesure où elle sert à éviter quelque chose d'aussi lourd qu'un accès à un sgbd, je pense qu'il est raisonnable de considérer que cette mémoire est *beaucoup* plus précieuse que la cpu utilisée pour l'allouer. Par contre, chaîner les headers où il reste des blocks libres me semble être un échange intéressant.
 
Pour l'allocateur variable, il y a au minimum une information en plus à stocker, la taille du bloc. De mon point de vue, la question réduite à sa plus simple expression est: comment stocker cette taille au mieux? (sans y passer trois semaines non plus ) Je verrais bien les headers de morceaux avec les infos taille du plus petit et du plus grand bloc libre. Ca me laissera toujours quelques recherches pour trouver un header contenant un bloc qui va bien. Bon. Disons qu'on tombe sur un malade qui nous file 4Go. La moitié se trouve en variable. On va dire que par défaut, on se prend des morceaux de 64Ko. Ca nous fait 2^31/2^16=32k headers max potentiels. Quand c'est bien plein, ça peut craindre s'il y a beaucoup de morceaux où il ne reste pas grand chose. Si on ne prend que 512Mo dans la tronche, ça nous fait 2^12=4k et c'est pas forcément top moumoute non plus.
 

 
Si j'en crois wikipedia, ça se fait uniquement ainsi pour les très petits blocs mais c'est effectivement intéressant dans la mesure où c'est avec eux que l'overhead est proportionnellement le plus important. Sinon, c'est un arbre qui est utilisé. Bon, je ne voulais pas trop m'emmerder avec ça, c'est pas gagné.

le verrou global ça craint un peu

C'est pour ça que je parlais de chainer les blocs libres, même si le pointeur fait 32 ou 64bits, il n'est pas en plus de la taille allouée, il est à la place d'un bloc alloué. Par exemple, au début d'un bloc libre il y a un header qui est fait de 2 pointeurs, formant une liste doublement chainée, quand on alloue un bloc, on relie le précédent et le suivant, et on retourne la position du header, ce qui fait qu'il ne prends alors plus de place, il est écrasé.
 

 
Et d'autant plus que pour l'instant, il n'existe même pas (la macro ne définit rien)
 

 
S'pas con ça. Ca fait que l'overhead est réduit au header de la zone où l'on prend les blocs . J'ai jeté un oeil à l'implémentation de la glibc et c'est la méthode qu'ils utilisent. Pour l'allocateur fixe, une liste simplement chaînée suffit. J'ai implémenté ça. Par contre, partant d'un offset à libérer, je suis obligé de chercher la zone d'où il vient. Je ne vois pas de solution simple et non-contraignante afin de faire sauter cette recherche. Il faudrait soit avoir des morceaux de taille fixe pour calculer directement à partir de l'offset, soit ajouter un header à chaque bloc pour avoir le header de zone.
 
Pour l'allocateur variable, je pense m'inspirer de la glibc aussi:

 
Ca donne un overhead de 8 octets par bloc alloué. Comme cet allocateur sera essentiellement utilisé pour des strings, j'ai regardé la taille moyenne des messages de ma base de test, et ça donne 636 octets sur ~110000 messages, soit un overhead de ~1.25% ce qui me semble plutôt acceptable.

Si tu as une forte proportion de petits blocs, tu peut tenter un codage "huffmanisé-mais-pas-vraiment" de la longueur, avec un ptit jeu de bitmask ça peut être assez rapide à décoder.
 
Pour une taille inférieure à 128, tu code la longueur sur un char avec 0 en préfixe: 1xxxxxxx
Pour une taille entre 129 et 16k, tu code la longueur sur 2 chars avec 10 en préfixe:01xxxxxxx xxxxxxxx
Pour une taille entre 16k+1 et 512m, tu code la longueur sur 4 chars avec 11 en préfixe: 011xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
( et si t'as envie d'éviter de limiter a 512m alors que la limite théorique est supérieure, tu continue avec plus de longueur...)
Tu commence par différencier en demandant le bit le plus significatif du premier octet (__builtin_msb sous gcc sinon une implé software en fallback), pous avoir la taille du header de longueur, tu lis 1,2 ou 4 octets en fonction tu maske à 0 les bits de préfixe et tadam, ta longueur \o/
 
ça te coute msb+switch+mask à chaque lecture (spa énorme), mais tu gagne en overhead, et accessoirement, si tu alloue bcp de strings, tu peut faire un allocateur spécifique + une "classe" adaptée et te servir de ce header de longueur pour faire des pascal-strings, et ainsi booster tes strlen/strcat etc...