Recherche d'un nombre magique sûr pour la structure de données en mémoire

Question

J'implémente un allocateur de tas (malloc) et je dois choisir un nombre magique pour vérifier si un pointeur donné pointe vers une structure de données que j'ai allouée.Il me semble évident qu'aucun nombre magique ne peut être considéré comme complètement sûr (si le nombre est vérifié, je peux être sûr qu'il pointe vers l'une de mes structures de données), mais j'ai peut-être raté quelque chose, alors...si quelqu'un peut m'aider et m'apporter le numéro de mes rêves, j'apprécierais vraiment.Merci d'avance.

Answer 1

Cela dépend de la raison pour laquelle vous faites cela.Si vous le faites pour essayer de détecter des erreurs de programmation (par exemple, vous voulez vous assurer de ne pas confondre accidentellement my_malloc/my_free et malloc/free), puis choisissez simplement une valeur aléatoire.Bien sûr, parfois il ne parviendra pas à détecter un tel cas, mais cela n'a vraiment pas d'importance.Cela ne devrait jamais arriver.Alors, ici :

#define MAGIC_32BIT 0x77A5844CU
#define MAGIC_64BIT 0xD221A6BE96E04673UL

Si l’exactitude en dépend, alors vous devriez vraiment procéder d’une autre manière.Par exemple, en gardant une trace des adresses que vous avez allouées dans un hachage ou une arborescence ou, dans des cas particuliers, un bitmap.

Si vous implémentez réellement malloc/free (par exemple, en écrivant votre propre bibliothèque C), gardez à l'esprit que freequelque chose qui n'était pas malloced (sauf NULL) est un comportement non défini par la norme, votre code n'a donc pas à s'inquiéter de ce qui se passe.

Answer 2

Je n'ai pas fait une telle chose (j'ai travaillé avec des tas, mais j'ai noté aucun allocator) et je ne suis pas certain de ce que vous essayez de faire, mais peut-être que ceci est un cas que vous devriez utiliser hachage.

Selon ce que vous faites exactement, cela signifie que l'adresse du morceau de mémoire, ou des données qu'il contient (et chaque fois que vous modifiez quelque chose, cela implique de recalculer le hachage) ou une sorte d'identifiant de la mémoire.opération.

Encore une fois, je ne suis pas certain de ce que vous essayez d'atteindre, alors ce sont mes 2 cents.

Answer 3

TALLOC_MAGIC 0xe814ec70

Cela vient du fichier talloc.c dans le code source ici.Bien sûr, il faudra se demander pourquoi talloc a choisi ce nombre magique, mais c'est un début.

Answer 4

Plutôt que de choisir un seul nombre magique, vous devez utiliser un nombre aléatoire (de préférence avec au moins un des 8 bits inférieurs définis - vous pouvez forcer cela en faisant un OU en 1, par exemple) ou une constante - votre choix, puis XOR (^) avec une adresse (par exemple, l'adresse que vous vérifiez).Cette approche réduira considérablement les risques de collision accidentelle.

Par exemple, lorsque vous écrivez l'en-tête de l'objet (ou l'en-tête de la page, selon le type d'allocateur que vous écrivez), stockez MAGIC ^ addr.Maintenant, quand vous voulez vérifier si addr est valide, il suffit de voir si value == addr ^ MAGIC (avec des moulages appropriés, bien sûr).

À propos, avant de vous lancer dans la création de votre propre allocateur de mémoire personnalisé, veuillez lire cet article (Reconsidérer l'allocation de mémoire personnalisée, par Berger, Zorn et McKinley), tiré de OOPSLA 2002.

http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf

Abstrait: Les programmeurs dans l'espoir d'obtenir des améliorations de performances utilisent souvent des allocateurs de mémoire personnalisés.Cette étude approfondie examine huit applications qui utilisent des allocateurs personnalisés.Étonnamment, pour six de ces applications, un allocateur à usage général de pointe (l'allocateur LEA) fonctionne ainsi que ou mieux que les allocateurs personnalisés.Les deux exceptions utilisent des régions qui offrent des performances plus élevées (améliorations allant jusqu'à 44 %).Les régions réduisent également la charge de travail des programmeurs et éliminent une source de fuites de mémoire.Cependant, nous montrons que l'incapacité des programmeurs à libérer des objets individuels dans les régions peut entraîner une augmentation substantielle de la consommation de mémoire.Pire, cette limitation empêche l'utilisation de régions pour les idiomes de programmation courants, en réduisant leur utilité.Nous présentons une généralisation des allocateurs à usage général et basés sur la région que nous appelons les REAPS.Les Renaps sont une combinaison de régions et de tas, fournissant une gamme complète de sémantiques régionales avec l'ajout de délétion d'objets individuels.Nous montrons que notre implémentation de reaps offre des performances élevées, surpassant les autres allocateurs avec une sémantique de type région.Nous utilisons ensuite une étude de cas pour démontrer les avantages de l'espace et les avantages de l'ingénierie logicielle des REAPS dans la pratique.Nos résultats indiquent que les programmeurs ayant besoin de régions rapides devraient utiliser des REAPS et que la plupart des programmeurs qui envisagent des allocateurs personnalisés devraient plutôt utiliser l'allocateur LEA.