Написание пользовательского malloc, который хранит информацию в указателе - PullRequest
Новая
       14

Написание пользовательского malloc, который хранит информацию в указателе

1 голос
/ 13 августа 2011

Недавно я читал о семействе методов автоматического управления памятью, которые полагаются на хранение информации в указателе, возвращаемом распределителем, то есть несколько битов заголовка, например, чтобы различать указатели или хранить информацию, связанную с потоками (обратите внимание, что яЯ не говорю о подсчете ссылок с ограниченным полем, здесь только неизменная информация.

Я бы хотел поиграть с этими методами.Теперь, чтобы реализовать их, мне нужно иметь возможность возвращать указатели с определенной формой из моего распределителя.Я полагаю, что я мог бы играть с битами с наименьшим весом, но для этого потребовалось бы заполнение, которое выглядит чрезвычайно потребляющим память, поэтому я считаю, что я должен играть с самыми тяжелыми битами.Тем не менее, я понятия не имею, как это сделать.Есть ли способ для меня, чтобы вызвать malloc или malloc_create_zone или какую-либо связанную функцию и запросить указатель, который всегда начинается с заданных битов?

Спасибо всем!

1 Ответ

2 голосов
/ 13 августа 2011

Объем информации, которую вы можете хранить в указателе, довольно ограничен (обычно один или два бита на указатель). И каждая попытка разыменования указателя должна сначала замаскировать магическую информацию. Технику часто называют маркировка , кстати. 

 #define TAG_MASK   0x3
 #define CONS_TAG   0x1
 #define STRING_TAG 0x2
 #define NUMBER_TAG 0x3

 typedef uintptr_t value_t; 
 typedef struct cons {
     value_t car;
     value_t cdr;
 } cons_t;

 value_t
 create_cons(value_t t1, value_t t2)
 {
     cons_t* pair = malloc(sizeof(cons_t));
     value_t addr = (value_t)pair;
     pair->car = t1;
     pair->cdr = t2;
     return addr | CONS_TAG;
 }

 value_t
 car_of_cons(value_t v)
 {
     if ((v % TAG_MASK) != CONS_TAG) error("wrong type of argument");
     return ((cons_t*) (v & ~TAG_MASK))->car;
 }

Одним из преимуществ этой техники является то, что вы можете напрямую вывести тип объекта из самого указателя. Вам не нужно разыменовывать его (скажем, чтобы прочитать специальное поле type или подобное). Многие языковые реализации, использующие эту схему, также имеют специальную комбинацию тегов для «непосредственных» чисел и других небольших значений, которые могут быть представлены непосредственно с помощью «указателя».

Недостаток в том, что объем информации, которая может быть сохранена, довольно ограничен. Кроме того, как показывает пример кода, вы должны знать о тегировании при каждом доступе к объекту и должны «разметить» указатель перед его фактическим использованием.

Использование младших значащих битов для пометки связано с наблюдением, что на большинстве платформ все указатели на malloc ed памяти фактически выровнены по небайтовой границе (обычно 8 байт), поэтому младшие значащие биты всегда равны нулю.

...