I'm trying to understand how exactly glibc's malloc does its bookkeeping on my 64-bit machine.
According to the documentation it stores the actual size(the malloc value plus the bookkepping bytes) right before the chunk. So I took the following code from here:
int *a = (int *) malloc(4);
int *b = (int *) malloc(7);
int *c = (int *) malloc(1);
int *d = (int *) malloc(32);
int *e = (int *) malloc(4);
printf("0x%x\n", a);
printf("0x%x\n", b);
printf("0x%x\n", c);
printf("0x%x\n", d);
printf("0x%x\n", e);
printf("a[-1] = %d, a[-2] = %d\n", a[-1], a[-2]);
printf("b[-1] = %d, b[-2] = %d\n", b[-1], b[-2]);
printf("c[-1] = %d, c[-2] = %d\n", c[-1], c[-2]);
printf("d[-1] = %d, d[-2] = %d\n", d[-1], d[-2]);
printf("e[-1] = %d, e[-2] = %d\n", e[-1], e[-2]);
which yields:
0xfca042a0
0xfca042c0
0xfca042e0
0xfca04300
0xfca04330
a[-1] = 0, a[-2] = 33 // letter[-2] is how much memory malloc has actually allocated
b[-1] = 0, b[-2] = 33
c[-1] = 0, c[-2] = 33
d[-1] = 0, d[-2] = 49
e[-1] = 0, e[-2] = 33
So you can see that the first three addresses are 32 bytes apart, that makes sense since the smallest chunk malloc allocates is 32 or rather 4 * sizeof(void*). However when I allocate 32 bytes the next chunk is 48 bytes away and not 64, why is that?
And if malloc has allocated 32 and 48 bytes why is it printing 33 and 49 respectively?
The internal glibc representation of a chunk is the following structure:
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
Every field except mchunk_prev_size and mchunk_size is only populated if the chunk is free. Those two fields are right before the user usable buffer. The mchunk_prev_size field holds the size of the previous chunk (only if it's free), while the mchunk_size field always holds the real size of the chunk (which is at least 16 bytes more than the requested size). Furthermore, in order to save space, the mchunk_prev_size field can actually resides inside the previous chunk (since it's free).
Chunks are always aligned to 16 bytes boundaries (i.e., their hexadecimal address always ends with a 0). The minimum allocation size is 16 (requests for smaller sizes are just rounded up to 16), and there always need to be 16 additional bytes for mchunk_prev_size and mchunk_size (8 bytes each).
So now you can probably guess the answer to your first question:
[...] the smallest chunk malloc allocates is 32 or rather
4 * sizeof(void*). However when I allocate 32 bytes the next chunk is 48 bytes away and not 64, why is that?
Well, yes, the smallest chunk size is 32, but the increment is actually 16. You can therefore have any size which is multiple of 16 and is above or equal to 32. If you request a size between 17 and 32 you will get a chunk of 48 bytes (32 of which are usable for user data). Furthermore, the minimum malloc allocation size doesn't have much to do with sizeof(void *), it's more related to sizeof(size_t) really (as your link also notes).
The state of the heap after the allocations in your example is the following:
+-----------+ 0xfca04290
| prev size |
|-----------|
| size |
a --> |-----------| 0xfca042a0
| user data |
| |
+-----------+ 0xfca042b0
| prev size |
|-----------|
| size |
b --> |-----------| 0xfca042c0
| user data |
| |
+-----------+ 0xfca042d0
| prev size |
|-----------|
| size |
c --> |-----------| 0xfca042e0
| user data |
| |
+-----------+ 0xfca042f0
| prev size |
|-----------|
| size |
d --> |-----------| 0xfca04300
| user data |
| |
| |
| |
+-----------+ 0xfca04320
| prev size |
|-----------|
| size |
e --> |-----------| 0xfca04330
| user data |
| |
+-----------+
One thing that isn't not clear from the above diagram is the fact that, as explained above, mchunk_prev_size can actually reside inside the previous chunk to save space.
To further clarify this, we can also take a look at the heap layout after executing the following code:
void *a = malloc(24); // 0x123400a0
void *b = malloc(16); // 0x123400c0
For both a and b, the mchunk_size will be 32. The mchunk_prev_size of b will overlap with the last 8 bytes of a. Both chunks will nonetheless be aligned to 16 bytes.
+-----------------------+ 0x12340090
| prev size |
|-----------------------|
| size |
a --> |-----------------------| 0x123400a0
| user data |
| |
+-----------------------+ 0x123400b0
| user data / prev size |
+-----------------------+ 0x123400b8
| size |
b --> |-----------------------| 0x123400c0
| user data |
| |
+-----------------------+ 0x123400d0
Without making the mchunk_prev_size field of b overlap with the last 8 bytes of a, in order to keep the alignment of 16 bytes, some empty space would need to be left between the end of a and the start of b (exactly 8 bytes), and this space would be wasted.
Now, coming to the second question:
And if malloc has allocated 32 and 48 bytes why is it printing 33 and 49 respectively?
Since every chunk must have a size multiple of 16 bytes, the lowest 4 bits of the size (one hexadecimal digit) would remain unused. malloc saves space and uses those to store additional information about the chunk. The last 3 bits are actually flags for malloc's internal usage. This is explained in source code comments as well:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P| <== flags
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... |
Those flag bits A|M|P are:
A: non main arena chunk.M: chunk is mmaped.P: previous chunk is in use (i.e. not free).You can find a more thorough explanation of the above right in the malloc source code.
Since all of your chunks are still in use, in the size field you see size | PREV_IN_USE. Since the "previous in use" (P) is the least significant bit, this has the effect of incrementing the value of the size by 1, so you see 33 instead of 32 for example.
Some additional notes:
If you want to inspect the size of a chunk you should use size_t instead of int, like this:
void *a = malloc(32);
size_t *ptr = a;
size_t chunk_size = ptr[-1] & ~0x7; // Strip the A|M|P flags from the size.
Keep in mind that this chunk_size is the internal size of the chunk, not the usable user size (which is 32).
Last but not least: the correct format specifier for pointers for printf is %p, not %x (and it should also already include the leading 0x):
printf("%p\n", a);