C++中对齐的malloc

Question

我有一个关于书中问题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上加了偏移量，为什么还要做"one_answers"呢？[-1]是什么意思？感谢您提前提供的帮助。

Answer 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指针
• 由于对齐是2的幂，因此在二进制中，对齐的形式是1后跟0。例如，如果对齐为32，则二进制值为00100000
• 二进制格式的(alignment-1)将把1变成0，并把1之后的所有0变成1。例如：(32-1)是00011111
• ~将反转所有位。即：11100000
• 现在，p1是指向缓冲区的指针(记住，缓冲区的偏移量比我们需要的要大)。我们将offset添加到p1:p1+offset
• 现在，(p1+偏移量)大于我们想要返回的值。我们将通过逐位和：(p1+offset)&(偏移-1)
• 这是p2，我们想要返回的指针。请注意，因为它的最后5位数字是零，所以根据要求，它是32位对齐的
• p2是我们要返回的。但是，当用户调用aligned_free时，我们必须能够到达p1。为此，请注意，当我们计算第4行中的偏移量(即sizeof(void*))时，我们为一个额外的指针保留了位置
• 所以，我们想把p1直接放在p2之前。这是p2[-1]。这是一个有点棘手的计算。请记住，p2被定义为void**。一种看待它的方法是将其视为空数组*。C数组计算表明p2[0]正是p2。p2[1]是p2+sizeof(void*)。通常，p2[n]=p2+nsizeof(void)。编译器也支持负数，所以p2[-1]在p2之前是一个空*(通常是4个字节)

我猜aligned_free类似于：

void aligned_free( void* p ) {
void* p1 = ((void**)p)[-1];         // get the pointer to the buffer we allocated
free( p1 );
}

Answer 2

p1是实际分配。p2是返回的指针，它引用经过分配点的内存，并为最初存储实际分配指针的allignment and留出足够的空间。当aligned_free()被调用时，p1将被检索以执行"真正的"free()。

关于bit数学，这会变得有点麻烦，但它是有效的。

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)，并且留下足够的空间来存储由p1引用的用于原始分配的4字节指针。

自从我做对齐数学以来，它一直是，所以如果我把比特加起来，请有人纠正它。

Answer 3

顺便说一句，这不是唯一的方法。

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会将void指针强制转换为size_t指针，移回一个位置，读取存储在那里的值，并调整偏移量以移动到crt分配开始

void* align_free(void* ptr)
{
size_t* pMetadata = reinterprete_cast<size_t*> (ptr);
free(ptr-pMetadata[-1]);  
}

优化：如果对齐大于sizeof(size_t)，则不需要sizeof(size _t)额外分配