6

我对书中的问题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，为什么还要执行“and”？[-1] 是什么意思？我在这里先向您的帮助表示感谢。

4

3 回答 3

13

您的示例代码不完整。它什么也不分配。很明显，您缺少设置 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* 。一种看待它的方法是 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 );
}
于 2012-09-20T01:28:16.217 回答
11

p1 是实际分配。p2 是返回的指针，它引用分配点之后的内存，并为对齐和首先存储实际分配的指针留出足够的空间。当调用aligned_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 引用。

自从我做对齐数学以来，它已经永远存在了，所以如果我把这些位搞砸了，请有人纠正这个。

于 2012-09-20T00:54:44.010 回答
0

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

 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 and 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 alloc 开头

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

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

于 2014-03-20T05:01:31.510 回答