Aligned malloc in C ++

Question

I have a question about issue 13.9 in the book, "hacking interview coding." The question is to write an aligned alloc and free function that supports memory allocation, and the code below is in the answer:

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

I am so confused on line 5 and line 6. Why do you need to do "and" since you have already added the offset to p1? and what does [-1] mean? Thanks for your help in advance.

Answer 1

Sample code is empty. He emits nothing. It is very obvious that you are missing the malloc instruction, which sets the pointer p1. I don't have a book, but I think the full code should go along these lines:

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

So ... what does the code do?

• The strategy is to malloc more space than we need (in p1), and return a p2 pointer somewhere after the start of the buffer.
• Since alignment is a power of two, in binary terms it must consist of 1 followed by zeros. for example, if the alignment is 32, it will be 00100000 in binary format
• (alignment-1) in binary format will turn 1 to 0 and all 0 after 1 to 1. For example: (32-1) - 00011111
• ~ will override all bits. That is: 11100000
• now, p1 is a pointer to a buffer (remember that the buffer is larger in offset than we need). we add the offset to p1: p1 + offset.
• So now (p1 + offset) is more than what we want to return. We will lose all the minor bits by doing the bitwise and: (p1 + offset) and ~ (offset-1)
• This is p2, the pointer we want to return. Note that since its last 5 digits are zero, 32 is executed by default.
• p2 is what we will return. However, we should be able to reach p1 when the user calls aligned_free. To do this, note that we reserved space for one extra pointer when calculating the offset (which is sizeof (void *) on line 4.
• therefore we want to put p1 immediately before p2. This is p2 [-1]. This is a bit complicated calculation. Remember that p2 is defined as void *. One way to look at it is through an array of voids. When computing the array C, it is said that p2 [0] is exactly p2. p2 [1] - p2 + sizeof (void *). In the general case, p2 [n] = p2 + n * sizeof (void *). The compiler also supports negative numbers, so p2 [-1] is one void * (usually 4 bytes) before p2.

I'm going to guess that aligned_free is something like:

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

Answer 2

p1 is the actual distribution. p2 is the returned pointer, which refers to the memory behind the allocation point and leaves enough space for both binding and storing the actual allocated pointer in the first place. when aligned_free () is called, p1 will be fetched to execute "real" free ().

As for bit math, this gets a little more cumbersome, but it works.

 p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5 

Remember that p1 is a reference to the actual location. For kicks, let's assume the following: 32-bit pointers:

 alignment = 64 bytes, 0x40 offset = 0x40-1+4 = 0x43 p1 = 0x20000110, a value returned from the stock malloc() 

The important thing is that the original malloc() allocates an extra 0x43 bytes of space above and above the original request. This is necessary to take into account both the mathematics of alignment and the space for a 32-bit pointer:

 p2=(void**)(((size_t)(p1)+offset)&~(alignment-1)); //line 5 p2 = (0x20000110 + 0x43) &~ (0x0000003F) p2 = 0x20000153 &~ 0x0000003F p2 = 0x20000153 & 0xFFFFFFC0 p2 = 0x20000140 

p2 is aligned at the 0x40 boundary (that is, all bits in 0x3F are 0), and there is enough space left to store a 4-byte pointer for the original selection referenced by p1.

This was forever since I did the math alignment, so if I modified the bit, please someone would fix it.

Answer 3

And by the way, this is not the only way to do this.

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

As an example, size = 20, alignement = 16 and crt malloc returned address 10. and assuming sizeof (size_t) as 4 bytes

 - 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 

start

Similarly, align_free will point the void pointer to the size_t pointer, move back one place, read the value stored there, and adjust the offset to go to the beginning of crt alloc

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

Optimization: you do not need an additional sizeof (size_t) distribution if your alignment was greater than sizeof (size_t)