the memory allocation's exercise in the book called "Expert C programming"

Question

The exercise asks me to see what will happen if the memory block which will be allocated is less than 1MB in the program followed:

#include <stdio.h>
#include <stdlib.h>
main()
{
    int MB=0;
    while(malloc(1<<20))
        ++MB;
    printf("Allocated %d MB total\n",MB);
}

The result on my laptop is

Allocated 3056 MB total

Than I change the program like this:

#include <stdio.h>
#include <stdlib.h>
main()
{
    int MB=0;
    while(malloc(1<<19))
        ++MB;
    printf("Allocated %d MB total\n",MB/2+MB%2);
}

And the result is

Allocated 3045 MB total

Is my program changed by myself correct? And why the result is smaller than 3056MB?

Answer 1

1. Yes, your program is fine. (Although always rounding the number of megabytes up is a little non-standard.)

2. When you call free, you don't tell it how big the block you are freeing is. That means that the memory management system has to know how big each block is. And that means that it has to store that information somewhere. Since it can't store the information inside of the block of memory, it must store it outside of the block, which usually means actually allocating slightly more memory than was requested. For example, it could actually allocate a block one size_t larger than the block requested, store the block size right at the beginning, and then tell you that the block starts after the size.

Most malloc implementations will put large allocations on page boundaries (typically a page is 4K). One way to do that is to waste an entire page for each allocation, using the page only for a single size_t value. That seems awful, but if you're asking for even half a megabyte, a page is less than 1% of the allocation size, and wasting 1% of total memory is not so awful.

Suppose your malloc did that. When you're allocating 1MB blocks, you manage to allocate 3056 of them. If each allocation is one 4k page larger than the request, the hidden allocations will be 3056*4k, or slightly less than 12 megabytes. (Actually it's slightly less than 12 mebibytes, but I'm going to just keep on saying mega when I mean mebi.) So the total memory available would have been 3068 MB.

When you change that to allocating ½MB blocks, you manage to allocate at least 3045*2 - 1 of them (assuming the number of MB was rounded up). That's 6089 extra pages, which is around 23.8 MB, plus an allocation of 3044.5 MB, for a total of about 3068.3 MB.

None of that proves that your malloc works that way, but it at least shows a possible mechanism.