Поиск безопасного магического числа для структуры данных в памяти

Question

Я реализую распределитель кучи (malloc), и мне нужно выбрать магическое число, чтобы проверить, указывает ли данный указатель на структуру данных, которую я выделил. Мне кажется очевидным, что ни одно магическое число не может считаться полностью безопасным (если этот номер проверен, я могу быть уверен, что указывается на одну из моих структур данных), но, возможно, я что-то упустил, так что ... если кто-то может помочь принеси мне количество моих снов, я бы очень оценил. Спасибо заранее.

Answer 1

Это зависит от того, для чего вы это делаете. Если вы делаете это, чтобы попытаться поймать ошибки программирования (например, вы хотите убедиться, что вы случайно не перепутали my_malloc / my_free и malloc / free), тогда просто выберите случайное значение , Конечно, иногда он не сможет обнаружить такой случай, но это действительно не имеет значения. Такого не должно быть. Итак, вот:

#define MAGIC_32BIT 0x77A5844CU
#define MAGIC_64BIT 0xD221A6BE96E04673UL

Если от этого зависит правильность, тогда вы действительно должны сделать это по-другому. Например, отслеживая, какие адреса вы выделили в хэше или дереве или, в особых случаях, в растровом изображении.

Если вы на самом деле реализуете malloc / free (например, пишете свою собственную библиотеку C), то имейте в виду, что free то, что не было malloc ed (кроме NULL), по стандарту не определено поэтому вашему коду не нужно беспокоиться о том, что произойдет.

Answer 2

Вместо того, чтобы выбирать одно магическое число, вы должны использовать случайное число (предпочтительно, по крайней мере, с одним из 8 младших битов - вы можете форсировать это, например, с помощью ИЛИ в 1) или некоторую константу - ваш выбори затем XOR это (^) с адресом (например, адрес, который вы проверяете).Такой подход значительно сократит вероятность случайного столкновения.

Например, когда вы пишете заголовок объекта (или заголовок страницы, в зависимости от типа используемого вами распределителя), сохраняйте MAGIC ^ addr.Теперь, когда вы хотите проверить, является ли addr действительным, просто посмотрите, если value == addr ^ MAGIC (с соответствующими приведениями, конечно).

Кстати, прежде чем приступать к созданию собственного распределителя памяти, пожалуйста, прочитайтеэта статья ( Пересмотр пользовательского распределения памяти , автор Berger, Zorn и McKinley), из OOPSLA 2002.

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

Аннотация: Программистыв надежде на улучшение производительности часто используют пользовательские распределители памяти.В этом углубленном исследовании рассматриваются восемь приложений, использующих пользовательские распределители.Удивительно, что для шести из этих приложений современный распределитель общего назначения (распределитель Lea) работает так же хорошо или лучше, чем пользовательские распределители.В двух исключениях используются регионы, которые обеспечивают более высокую производительность (улучшение до 44%).Регионы также уменьшают нагрузку на программиста и устраняют источник утечек памяти.Однако мы показываем, что неспособность программистов освободить отдельные объекты внутри регионов может привести к значительному увеличению потребления памяти.Хуже того, это ограничение исключает использование областей для общих идиом программирования, снижая их полезность.Мы представляем обобщение универсальных и региональных распределителей, которые мы называем пожинаниями.Рипы представляют собой комбинацию областей и куч, обеспечивая полный диапазон семантики областей с добавлением удаления отдельных объектов.Мы показываем, что наша реализация reaps обеспечивает высокую производительность, опережая другие распределители с региональной семантикой.Затем мы используем пример из практики, чтобы продемонстрировать космические преимущества и преимущества программной инженерии, которые можно использовать на практике.Наши результаты показывают, что программисты, которым нужны быстрые регионы, должны использовать reaps, и что большинство программистов, рассматривающих пользовательские распределители, должны вместо этого использовать распределитель Lea.

Answer 3

TALLOC_MAGIC 0xe814ec70

Это из файла talloc.c в исходном коде здесь .Конечно, вам нужно выяснить, почему talloc выбрал это магическое число, но это только начало.

Answer 4

Я такого не делал (я работал с кучами, но я не реализовал никакой распределитель), и я не уверен в том, что вы пытаетесь сделать, но, возможно, в этом случае вам следует использовать хеширование.

В зависимости от того, что именно вы делаете, это означает хэширование адреса блока памяти или содержащихся в нем данных (и каждый раз, когда вы что-то меняете, это подразумевает пересчет хэша) или какой-то идентификатороперация памяти.

Опять же, я не уверен в том, чего вы пытаетесь достичь, тогда это мои 2 цента.