在C ++中对齐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]是什么意思? 我在这里先向您的帮助表示感谢。

您的示例代码不完整。 它什么都不分配。 很明显你缺少一个设置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后跟零。 例如,如果对齐为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个字节)。

我猜想align_free是这样的:

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

p1是实际分配。 p2是返回的指针,它引用超过分配点的内存,并为第一个位置的所有分配指针留出足够的空间并存储实际分配的指针。 当调用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引用。

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

顺便说一下,这不是唯一的方法。

  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(crtAlloc); // treat as int for pointer arithmetic void* pRet = crtAlloc + (alignment - (crtArithmetic%alignment)); size_t *pMetadata = reinterprete_cast(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 (ie 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 (ptr); free(ptr-pMetadata[-1]); } 

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