Memory leak on page allocation with malloc

Question

Consider the following C code, which creates 100,000 4KB-sized pages, then frees 99,999 pages and, finally, frees the last page:

#include <stdio.h>
#include <stdlib.h>

#define NUM_PAGES 100000

int main() {
    void *pages[NUM_PAGES];

    int i;
    for(i=0; i<NUM_PAGES; i++) {
        pages[i] = malloc(4096);
    }

    printf("%d pages allocated.\n", NUM_PAGES);
    getchar();

    for(i=0; i<NUM_PAGES-1; i++) {
        free(pages[i]);
    }

    printf("%d pages freed.\n", NUM_PAGES-1);
    getchar();

    free(pages[NUM_PAGES-1]);

    printf("Last page freed.\n");
    getchar();

    return 0;
}

If you compile it, run it and monitor the process' memory usage, you can see that the memory usage reaches about 400MB before the first getchar (when memory is allocated for 100,000 pages), then it keeps the same even after 99,999 pages are de-allocated (after the second getchar) and, finally, it drops to 1MB when the last page is de-allocated.

So, my question is why is this happening? Why is the entire memory returned to the OS only when all the pages are freed? Is there any page size or any page alignment which prevents this sort of thing to happen? I mean, is there any page size or alignment the makes any malloced page be entirely returned to the operating system when only one page gets freed?

Answer 1

This is completely implementation-dependent, but I believe that this has to do with how the memory allocator works. Typically, when the memory manager needs more memory from the OS, it calls the sbrk function to request additional memory. The typical implementation of this function is that the OS stores a pointer to the next free address in memory where the process can get space. The memory grows like a stack, much in the same way that the call stack works. For example, if you allocated five pages of memory, it might look like this:

 (existing memory) | Page 0 | Page 1 | Page 2 | Page 3 | Page 4 | (next free spot)

With this setup, if you free pages 0 - 4, the memory manager inside the program will mark them as free, like this:

 (existing memory) |                                   | Page 4 | (next free spot)

Since the OS is allocating memory in a stack-like fashion, it can't reclaim all this memory from the program until Page 4 is done being used. Once you free the very last page, the process's memory will look like this:

 (existing memory) |                                              (next free spot)

And at this point the program's memory manager can return that huge amount of free space to the OS:

 (existing memory) | (next free spot)

In other words, because memory is allocated as a stack, until you deallocate the very last thing you've allocated, the OS can't reclaim any of the memory.

Hope this helps!