c++ - C++ 中的对齐 malloc

Question

我对《破解编码面试》一书中的第13.9题有一道题。 题目是写一个支持分配内存的aligned alloc and free function，答案中的代码如下:

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 添加了偏移量，为什么还必须执行“and”？ [-1] 是什么意思？提前感谢您的帮助。

Answer 1

您的示例代码不完整。它什么都不分配。很明显您缺少设置 p1 指针的 malloc 语句。我没有这本书，但我认为完整的代码应该遵循以下几行:

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;
}

那么...代码的作用是什么？

• 策略是 malloc 比我们需要的空间更多的空间(进入 p1)，并在缓冲区开始后某处返回一个 p2 指针。
• 由于对齐是 2 的幂，因此在二进制中它必须是 1 后跟 0 的形式。例如如果对齐为32，则二进制为00100000
• 二进制形式的(alignment-1)会将1变成0，1之后的0全部变成1，例如:(32-1)就是00011111
• ~ 将反转所有位。即:11100000
• 现在，p1 是指向缓冲区的指针(请记住，缓冲区比我们需要的偏移量大)。我们向 p1 添加偏移量:p1+offset。
• 现在，(p1+offset) 大于我们想要返回的值。我们将通过按位和运算来消除所有无关紧要的位:(p1+offset) & ~(offset-1)
• 这是p2，我们要返回的指针。请注意，因为它的最后 5 位数字为零，所以它按照要求进行了 32 位对齐。
• p2 是我们要返回的。但是，当用户调用 aligned_free 时，我们必须能够到达 p1。为此，请注意，我们在计算偏移量时为一个额外的指针保留了位置(即第 4 行中的 sizeof(void*)。
• 所以，我们想把 p1 放在 p2 之前。这是 p2[-1]。这是一个有点棘手的计算。请记住，p2 被定义为 void*。一种看待它的方式是将其视为 void 数组。 C 数组计算说 p2[0] 正好是 p2。 p2[1] 是 p2 + sizeof(void*)。通常 p2[n] = p2 + n*sizeof(void*)。编译器也支持负数，所以p2[-1]在p2之前是一个void*(一般4字节)。

我猜 aligned_free 是这样的:

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