在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添加了偏移？[-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;
}

那么......代码做了什么？

• 策略是比我们需要的更多空间(进入p1),并在缓冲区开始后的某处返回一个p2指针.
• 由于对齐是2的幂,因此在二进制中它必须形成1,然后是零.例如,如果对齐是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*.看待它的一种方法是作为无效的数组.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 );
}

Answer 2

p1是实际分配.p2是返回的指针,它引用超出分配点的内存,并为第一个位置的allignment和存储实际分配的指针留下足够的空间.当调用aligned_free()时,将检索p1以执行"real"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引用.

自从我做对齐数学以来,它一直是永恒的,所以如果我找到这些位,请有人纠正这一点.