Выровненный malloc в переполнении стека
У меня есть вопрос по проблеме 13.9 из книги «Взлом интервью по кодированию».
Вопрос состоит в том, чтобы написать выровненную функцию alloc и free, которая поддерживает выделение памяти, и в ответе код приведен ниже:
void *aligned_malloc(size_t required_bytes, size_t alignment) {
void *p1;
void **p2;
int offset=alignment-1+sizeof（void*);
if((p1=(void*)malloc(required_bytes+offset))==NULL)
return NULL;
p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5
p2[-1]=p1; //line 6
return p2;
}
Я так запутался со строкой 5 и строкой 6. Почему вы должны сделать «и», так как вы уже добавили смещение к p1? и что значит [-1]? Спасибо за помощь заранее.
Решение
Ваш пример кода не является полным. Это ничего не выделяет. Совершенно очевидно, что вам не хватает инструкции malloc, которая устанавливает указатель p1. У меня нет книги, но я думаю, что полный код должен идти по следующим направлениям:
void *aligned_malloc(size_t required_bytes, size_t alignment) {
void *p1;
void **p2;
int offset=alignment-1+sizeof（void*);
p1 = malloc(required_bytes + offset); // the line you are missing
p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5
p2[-1]=p1; //line 6
return p2;
}
Итак … что делает код?
- Стратегия состоит в том, чтобы распределить больше места, чем нам нужно (в p1), и вернуть указатель p2 где-нибудь после начала буфера.
- Поскольку выравнивание является степенью двойки, в двоичном виде оно должно образовывать 1, за которым следуют нули. например если выравнивание 32, это будет 00100000 в двоичном
- (alignment-1) в двоичном формате превратит 1 в 0, а все 0 после 1 в 1. Например: (32-1) — 00011111
- ~ обратит все биты. То есть: 11100000
- теперь p1 — указатель на буфер (помните, что буфер больше по смещению, чем нам нужно). мы добавляем смещение к p1: p1 + смещение.
- Итак, теперь (p1 + offset) больше того, что мы хотим вернуть. Мы обнуляем все незначащие биты, выполняя побитовое и: (p1 + смещение) & ~ (Смещение-1)
- Это p2, указатель, который мы хотим вернуть. Обратите внимание, что, поскольку последние 5 цифр равны нулю, он выровнен по запросу.
- p2 — это то, что мы вернем. Тем не менее, мы должны быть в состоянии достичь p1, когда пользователь вызывает align_free. Для этого обратите внимание, что мы зарезервировали расположение для одного дополнительного указателя, когда вычислили смещение (это sizeof (void *) в строке 4.
- Итак, мы хотим поставить p1 непосредственно перед p2. Это р2 [-1]. Это немного хитрый расчет. Помните, что p2 определяется как void *. Один из способов взглянуть на это как массив пустот. Вычисление массива C говорит, что p2 [0] точно p2. p2 [1] равно p2 + sizeof (void *). В общем случае p2 [n] = p2 + n * sizeof (void *). Компилятор также поддерживает отрицательные числа, поэтому p2 [-1] равен одному void * (обычно 4 байта) перед p2.
Я собираюсь догадаться, что align_free это что-то вроде:
void aligned_free( void* p ) {
void* p1 = ((void**)p)[-1]; // get the pointer to the buffer we allocated
free( p1 );
}
Другие решения
p1 — фактическое распределение. p2 — это возвращаемый указатель, который ссылается на память после точки выделения и оставляет достаточно места как для выравнивания, так и для хранения фактически выделенного указателя в первую очередь. когда выровнен align_free (), будет получено p1, чтобы сделать «реальный» free ().
Что касается математики, это становится немного более громоздким, но это работает.
p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5
Помните, что p1 — фактическая ссылка распределения. Для пиков давайте предположим следующее с 32-битными указателями:
alignment = 64 bytes, 0x40
offset = 0x40-1+4 = 0x43
p1 = 0x20000110, a value returned from the stock malloc()
Что важно, так это оригинал malloc() это выделяет дополнительные 0x43 байта пространства выше и вне исходного запроса. Это должно обеспечить как математику выравнивания а также пространство для 32-битного указателя может быть учтено:
p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5
p2 = (0x20000110 + 0x43) &~ (0x0000003F)
p2 = 0x20000153 &~ 0x0000003F
p2 = 0x20000153 & 0xFFFFFFC0
p2 = 0x20000140
p2 выравнивается по границе 0x40 (то есть все биты в 0x3F равны 0), и остается достаточно места для хранения 4-байтового указателя для исходного распределения, на который ссылается p1.
Это было навсегда так как я сделал выравнивание по математике, так что, если я уловил биты, пожалуйста кто-то исправит это.
И, кстати, это не единственный способ сделать это.
void* align_malloc(size_t size, size_t alignment)
{
// sanity check for size/alignment.
// Make sure alignment is power of 2 (alignment&(alignment-1) ==0)
// allocate enough buffer to accommodate alignment and metadata info
// We want to store an offset to address where CRT reserved memory to avoid leak
size_t total = size+alignment+sizeof(size_t);
void* crtAlloc = malloc(total);
crtAlloc += sizeof(size_t); // make sure we have enough buffer ahead to store metadata info
size_t crtArithmetic = reinterprete_cast<int>(crtAlloc); // treat as int for pointer arithmetic
void* pRet = crtAlloc + (alignment - (crtArithmetic%alignment));
size_t *pMetadata = reinterprete_cast<size_t*>(pRet);
pMetadata[-1] = pRet - crtArithmetic- sizeof(size_t);
return pRet;
}
В качестве примера size = 20, alignement = 16 и crt malloc вернули адрес 10. и принимая sizeof (size_t) как 4 байта
- total bytes to allocate = 20+16+4 = 40
- memory committed by crt = address 10 to 50
- first make space in front by adding sizeof(size_t) 4 bytes so you point at 14
- add offset to align which is 14 + (16-14%16) = 16
- move back sizeof(size_t) 4 bytes (i.e. 12) and treat that as size_t pointer and store offset 2 (=12-10) to point to crt malloc
Начните
Таким же образом, align_free приведёт пустой указатель к указателю size_t, переместится назад на одну позицию, прочитает значение, сохраненное там, и отрегулирует смещение, чтобы перейти к началу crt alloc
void* align_free(void* ptr)
{
size_t* pMetadata = reinterprete_cast<size_t*> (ptr);
free(ptr-pMetadata[-1]);
}
Оптимизация: вам не нужно дополнительное выделение sizeof (size_t), если ваше выравнивание было больше, чем sizeof (size_t)