Поиск безопасного магического числа для структуры данных в памяти
Я реализую распределитель кучи (malloc), и мне нужно выбрать магическое число, чтобы проверить, указывает ли данный указатель на структуру данных, которую я выделил. Мне кажется очевидным, что ни одно магическое число не может считаться полностью безопасным (если этот номер проверен, я могу быть уверен в том, что он указывает на одну из моих структур данных), но, возможно, я что-то упустил, так что... если кто-то может помочь принеси мне номер моей мечты, я бы очень оценил. Спасибо заранее.
4 ответа
Это зависит от того, для чего вы это делаете. Если вы делаете это, чтобы попытаться поймать ошибки программирования (например, вы хотите, чтобы случайно не перепутать my_malloc/my_free а также malloc/free), затем просто выберите случайное значение. Конечно, иногда это не удается обнаружить такой случай, но это действительно не имеет значения. Такого не должно быть. Так вот:
#define MAGIC_32BIT 0x77A5844CU
#define MAGIC_64BIT 0xD221A6BE96E04673UL
Если от этого зависит правильность, то вы действительно должны сделать это по-другому. Например, отслеживая, какие адреса вы выделили в хэше или дереве или, в особых случаях, в растровом изображении.
Если вы на самом деле реализуете malloc/free (например, пишете свою собственную библиотеку C), то имейте в виду, что freeчто-то, чего не было malloced (за исключением NULL) является стандартным поведением, поэтому ваш код не должен беспокоиться о том, что произойдет.
Вместо того, чтобы выбирать одно магическое число, вы должны использовать случайное число (предпочтительно с хотя бы одним из 8 младших битов - вы можете форсировать это, например, с помощью ИЛИ в 1) или некоторую константу - по вашему выбору, а затем XOR это (^) с адресом (например, адрес, который вы проверяете). Такой подход значительно снизит вероятность случайного столкновения.
Например, когда вы пишете заголовок объекта (или заголовок страницы, в зависимости от типа используемого вами распределителя), сохраняйте MAGIC ^ addr, Теперь, когда вы хотите проверить, если addr действительно, просто посмотрите, если value == addr ^ MAGIC (с соответствующими бросками, конечно).
Кстати, прежде чем приступить к созданию собственного распределителя памяти, прочтите эту статью ("Пересмотр пользовательского выделения памяти" Бергера, Цорна и МакКинли) из OOPSLA 2002.
http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf
Аннотация: Программисты, надеющиеся добиться улучшения производительности, часто используют собственные распределители памяти. В этом углубленном исследовании рассматриваются восемь приложений, использующих пользовательские распределители. Удивительно, но для шести из этих приложений современный распределитель общего назначения (распределитель Lea) работает так же хорошо или лучше, чем пользовательские распределители. В двух исключениях используются регионы, которые обеспечивают более высокую производительность (улучшение до 44%). Регионы также уменьшают нагрузку на программиста и устраняют источник утечек памяти. Однако мы показываем, что неспособность программистов освободить отдельные объекты внутри регионов может привести к значительному увеличению потребления памяти. Хуже того, это ограничение исключает использование регионов для общих идиом программирования, снижая их полезность. Мы представляем обобщение универсальных и региональных распределителей, которые мы называем пожинаниями. Рипы представляют собой комбинацию областей и куч, обеспечивая полный диапазон семантики областей с добавлением удаления отдельных объектов. Мы показываем, что наша реализация reaps обеспечивает высокую производительность, опережая другие распределители с региональной семантикой. Затем мы используем пример из практики, чтобы продемонстрировать космические преимущества и преимущества программной инженерии, полученные на практике. Наши результаты показывают, что программисты, которым нужны быстрые регионы, должны использовать reaps, и что большинство программистов, рассматривающих пользовательские распределители, должны вместо этого использовать распределитель Lea.
Я не делал ничего подобного (я работал с кучами, но я не реализовывал никакой распределитель), и я не уверен в том, что вы пытаетесь сделать, но, возможно, вам следует использовать хеширование.
В зависимости от того, что именно вы делаете, это означает хэширование адреса блока памяти или содержащихся в нем данных (и каждый раз, когда вы что-то меняете, это подразумевает пересчет хэша) или какой-то идентификатор операции с памятью.
Опять же, я не уверен в том, чего вы пытаетесь достичь, тогда это мои 2 цента.
TALLOC_MAGIC 0xe814ec70
Это из файла talloc.c в исходном коде здесь. Конечно, вам придется посмотреть, почему talloc выбрал это магическое число, но это только начало.