Qu'est-ce qu'un bon allocateur de mémoire C pour les systèmes intégrés? [fermé]

Question

J'ai une seule application intégrée, à threads, qui alloue et désalloue de nombreux blocs de petite taille (32 à 64b). Le scénario parfait pour un allocateur basé sur le cache. Et bien que je puisse essayer d’en écrire un, ce sera probablement une perte de temps et une solution qui n’a pas été aussi bien testée et mise au point qu’une solution qui a déjà fait l’objet d’une première ligne.

Alors, quel serait le meilleur allocateur que je pourrais utiliser pour ce scénario?

Remarque: j'utilise une machine virtuelle Lua dans le système (c'est-à-dire le coupable de plus de 80% des allocations). Je ne peux donc pas modifier mon code de manière triviale pour utiliser des allocations de pile afin d'améliorer les performances d'allocation.

Answer 1

J'ai récemment effectué des recherches sur ce sujet, car nous avions un problème de fragmentation de la mémoire. En fin de compte, nous avons décidé de nous en tenir à la mise en œuvre de GNU libc et d’ajouter des pools de mémoire de niveau application si nécessaire. Il y avait d'autres allocateurs qui avaient un meilleur comportement en matière de fragmentation, mais nous n'étions pas assez à l'aise avec eux pour remplacer malloc globalement. GNU bénéficie d’une longue histoire.

Dans votre cas, cela semble justifié. en supposant que vous ne puissiez pas réparer la VM, ces minuscules allocations sont très inutiles. Je ne sais pas ce qu'est votre environnement dans son ensemble, mais vous pouvez envisager de regrouper les appels à malloc / realloc / free uniquement sur la machine virtuelle afin de pouvoir les transmettre à un gestionnaire conçu pour les petits pools.

Answer 2

Dans le cadre d’un projet précédent en C sur lequel j’ai travaillé, nous nous sommes engagés dans la mise en œuvre de nos propres routines de gestion de la mémoire pour une bibliothèque exécutée sur un large éventail de plates-formes, y compris des systèmes intégrés. La bibliothèque a également alloué et libéré un grand nombre de petits tampons. Il fonctionnait relativement bien et ne nécessitait pas beaucoup de code à implémenter. Je peux vous donner quelques informations sur cette implémentation au cas où vous voudriez développer quelque chose vous-même.

L’implémentation de base incluait un ensemble de routines qui géraient les tampons d’une taille définie. Les routines ont été utilisées comme wrappers autour de malloc () et free (). Nous avons utilisé ces routines pour gérer l'allocation des structures que nous utilisions fréquemment, ainsi que pour gérer les mémoires tampons génériques de tailles définies. Une structure a été utilisée pour décrire chaque type de tampon géré. Quand un tampon d'un type spécifique était alloué, nous avions malloc () la mémoire en blocs (si une liste de tampons libres était vide). En d'autres termes, si nous gérons des tampons de 10 octets, nous pourrions créer un seul malloc () contenant 100 de l'espace pour cent de ces tampons afin de réduire la fragmentation et le nombre de mallocs sous-jacents nécessaires.

À l'avant de chaque mémoire tampon se trouverait un pointeur qui serait utilisé pour chaîner les mémoires tampons dans une liste libre. Lorsque les 100 mémoires tampons ont été allouées, chaque mémoire tampon est chaînée dans la liste disponible. Lorsque le tampon était utilisé, le pointeur était défini sur null. Nous avons également mis à jour une liste des "blocs". afin de pouvoir effectuer un nettoyage simple en appelant free () sur chacun des tampons réels de malloc'd.

Pour la gestion des tailles de mémoire tampon dynamique, nous avons également ajouté une variable size_t au début de chaque mémoire tampon indiquant la taille de la mémoire tampon. Cela a ensuite été utilisé pour identifier le bloc de tampon dans lequel replacer le tampon lors de sa libération. Nous avions des routines de remplacement pour malloc () et free () qui effectuaient une arithmétique de pointeur pour obtenir la taille de la mémoire tampon, puis pour la placer dans la liste des listes libres. Nous avions également une limite sur la taille des tampons que nous avons gérés. Les tampons supérieurs à cette limite étaient simplement malloc'd et transmis à l'utilisateur. Pour les structures que nous avons gérées, nous avons créé des routines pour l’allocation et la libération des structures spécifiques.

Finalement, nous avons également fait évoluer le système pour inclure la récupération de place lorsque l’utilisateur lui demande de nettoyer la mémoire inutilisée. Étant donné que nous avions le contrôle de l’ensemble du système, nous avons pu réaliser diverses optimisations au fil du temps pour en améliorer les performances. Comme je l'ai mentionné, cela a très bien fonctionné.

Answer 3

Je suis un peu en retard pour la fête, mais je veux juste partager une allocation de mémoire très efficace pour les systèmes embarqués que j'ai récemment trouvée et testée: https://github.com/dimonomid/umm_malloc

C’est une bibliothèque de gestion de mémoire spécialement conçue pour fonctionner avec ARM7. Personnellement, je l’utilise sur un périphérique PIC32, mais elle devrait fonctionner sur n’importe quel périphérique 16 et 8 bits (j’ai l’intention de tester le PIC24 16 bits. , mais je ne l'ai pas encore testé)

J'ai été sérieusement battu par la fragmentation avec allocateur par défaut: mon projet alloue souvent des blocs de tailles variées, allant de plusieurs octets à plusieurs centaines d'octets, et parfois je rencontrais une erreur «mémoire insuffisante». Mon périphérique PIC32 a un total de 32 Ko de RAM et 8192 octets sont utilisés pour le segment de mémoire. Au moment particulier, il reste plus de 5 Ko de mémoire disponible, mais l'allocateur par défaut dispose d'un bloc de mémoire non fragmenté maximal d'environ 700 octets, en raison de la fragmentation. C’est dommage, j’ai donc décidé de chercher une solution plus efficace.

J'étais déjà au courant de certains allocateurs, mais ils ont tous des limitations (par exemple, la taille du bloc doit être une puissance ou 2, et ne commence pas à partir de 2 mais à partir de 128 octets), ou était simplement erronée. Chaque fois auparavant, je devais revenir à l'allocateur par défaut.

Mais cette fois, j'ai de la chance: j'ai trouvé celui-ci: http: // hempeldesigngroup .com / embedded / stories / memorymanager /

Lorsque j'ai essayé cet allocateur de mémoire, dans exactement la même situation avec 5K de mémoire libre, il contient plus de 3 800 octets de blocs! C'était tellement incroyable pour moi (comparé à 700 octets) et j'ai effectué un test difficile: le dispositif a beaucoup travaillé plus de 30 heures. Aucune fuite de mémoire, tout fonctionne comme il se doit. J'ai également trouvé cet allocateur dans le référentiel FreeRTOS: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg= 1041 # , et ce fait est une preuve supplémentaire de la stabilité de umm_malloc. Alors je suis complètement passé à umm_malloc, et j'en suis assez content.

Je devais juste le modifier un peu: la configuration était un peu boguée lorsque la macro UMM_TEST_MAIN n'était pas définie, j'ai donc créé le référentiel github (le lien se trouve en haut de ce post). Maintenant, la configuration dépendante de l'utilisateur est stockée dans un fichier séparé, umm_malloc_cfg.h

Je ne connais pas encore très bien les algorithmes appliqués dans cet allocateur, mais celui-ci a une explication très détaillée des algorithmes, de sorte que toute personne intéressée peut consulter le haut du fichier umm_malloc.c. Au moins, & bin; binning " L’approche devrait donner d’énormes avantages en moins de fragmentation: http://g.oswego.edu/dl /html/malloc.html

Je pense que quiconque a besoin d'un allocateur de mémoire efficace pour les microcontrôleurs devrait au moins essayer celui-ci.

Answer 4

Même si cela fait longtemps que je n’ai pas posé cette question, ma solution finale a été d’utiliser SmallObjectAllocator de LoKi pour que cela fonctionne bien. Je me suis débarrassé de tous les appels du système d'exploitation et a amélioré les performances de mon moteur Lua pour les périphériques intégrés. Très agréable et simple, et à peu près 5 minutes de travail!

Answer 5

Depuis version 5.1 , Lua a autorisé un personnalisé allocateur à définir lors de la création de nouveaux états .

Answer 6

Je voudrais aussi ajouter quelque chose à cela même s'il s'agit d'un vieux fil. Dans une application intégrée, si vous pouvez analyser l'utilisation de la mémoire pour votre application et obtenir un nombre maximal d'allocation de mémoire de tailles variables, le type d'allocateur le plus rapide est généralement celui qui utilise des pools de mémoire. Dans nos applications intégrées, nous pouvons déterminer toutes les tailles d'allocation qui seront nécessaires pendant l'exécution. Si vous y parvenez, vous pourrez éliminer complètement la fragmentation du tas et bénéficier d'allocations très rapides. La plupart de ces implémentations ont un pool de débordement qui fera un malloc régulier pour les cas particuliers qui, espérons-le, seront très rares si vous avez bien analysé votre analyse.

Answer 7

J'ai utilisé le système 'Buddy Buddy' à bon escient sous vxworks. Fondamentalement, vous divisez votre segment en coupant des blocs en deux pour obtenir la plus petite puissance possible d'un bloc de deux tailles afin de contenir votre demande. Lorsque les blocs sont libérés, vous pouvez faire passer l'arborescence pour fusionner des blocs afin d'atténuer la fragmentation. Une recherche sur Google devrait afficher toutes les informations dont vous avez besoin.

Answer 8

J'écris un allocateur de mémoire C appelé tinymem destiné à défragmenter le segment de mémoire et à réutiliser la mémoire. Découvrez-le:

https://github.com/vitiral/tinymem

Remarque: ce projet a été interrompu pour travailler sur la mise en œuvre de la rouille:

https://github.com/vitiral/defrag-rs

De plus, je n’avais jamais entendu parler de umm_malloc auparavant. Malheureusement, cela ne semble pas être en mesure de traiter la fragmentation, mais cela semble certainement utile. Je vais devoir vérifier.