Realloc() does not correctly free memory in Windows

Question

I am attempting to use realloc() in a Windows application. I am allocating a large block of memory, then using realloc() to shrink it down later once I know the correct size.

I am finding that although realloc() appears to work correctly (memory in Task Manager reflects what you would expect) the application eventually runs out of memory. From what I can tell, it's as though relloc() frees the memory but does not free the virtual address space associated with the memory. As a result, malloc() will eventually fail.

Here's a small console app that demonstrates the problem:

int _tmain(int argc, _TCHAR* argv[])
{
    static const DWORD dwAllocSize = (50 * 1024 * 1024);
    static const DWORD dwReallocSize = 10240;
    static const DWORD dwMaxIterations = 200;

    BYTE* arpMemory[dwMaxIterations];
    memset( arpMemory, 0, sizeof(arpMemory) );

    for( DWORD i = 0; i < dwMaxIterations; i++ )
    {
        arpMemory[i] = (BYTE*) malloc( dwAllocSize );
        if( !arpMemory[i] )
        {
            printf("OUT OF MEMORY after %d iterations!\n", i);
            return -1;
        }

        BYTE* pRealloc = (BYTE*) realloc( arpMemory[i], dwReallocSize );
        if( !pRealloc )
        {
            printf("Realloc FAILED after %d iterations!\n", i);
            return -1;
        }
        else if( pRealloc != arpMemory[i] )
        {
            printf("Warning: Pointer changed: 0x%08X -> 0x%08X\n", arpMemory[i], pRealloc);
            arpMemory[i] = pRealloc;
        }
    }

    printf("Success!\n");

    for( int i = 0; i < dwMaxIterations; i++ )
        free( arpMemory[i] );

    return 0;
}

The app repeatedly allocates 50 MB of memory and then immediately resizes it to be only 10K. If you run it, you will find that it fails with an OUT OF MEMORY error after only 38 iterations. This corresponds to 2GB of originally allocated memory -- which is the address space limit for Windows applications.

Interestingly, if you look in Task Manager, you will see the application taking almost no memory at all. Yet malloc() is failing. This is what leads me to believe the virtual address space is being exhausted.

(Another experiment to try is to comment out the reallocation, so no memory is freed or reallocated. The app fails in exactly the same place: After 38 iterations. The only difference is that this time Task Manager reflects the full 2GB in use.)

One final point of information: This same application works under Linux. So this realloc() problem is strictly Windows-only.

Any thoughts?

Answer 1

After some experimentation, and reading between the lines of the documentation, I've reached the conclusion that large memory allocations (slightly less than 512k for 32-bit, slightly less than 1MB for 64-bit) use address space allocated using VirtualAlloc and reserved for that particular memory block.

If it is not practical to increase your buffer size on the fly as Hans suggests, and you don't want to copy the data, I think your only other option is to reserve a block of address space big enough for all your buffers and allocate space from it yourself. How complicated this would be depends on factors such as how your application uses and frees the buffers, whether more than one buffer is being written to at a time, and on how much data you will be processing over the lifetime of the application.

Additional: here is some test code showing what I see happening:

#include <windows.h>

#include <stdio.h>

DWORD reallocSize = 0x01000;    // 4K

void walkheap(HANDLE heap)
{
    PROCESS_HEAP_ENTRY phe;
    MEMORY_BASIC_INFORMATION mbi;

    phe.lpData = NULL;

    for (;;)
    {
        if (!HeapWalk(heap, &phe))
        {
            printf("HeapWalk: %u\n", GetLastError());
            return;
        }
        printf("%08x %08x %08x %08x %08x ", phe.lpData, phe.cbData, phe.cbOverhead, phe.iRegionIndex, phe.wFlags);
        if (VirtualQuery(phe.lpData, &mbi, sizeof(mbi)) != 0)
        {
            printf("--> %08x\n",mbi.AllocationBase);
        }
        else
        {
            printf("--> (error %u)\n", GetLastError());
        }
    }
}

void alloc(HANDLE heap, DWORD count, DWORD size)
{
    BYTE* ptr;
    BYTE* pRealloc;

    ptr = (BYTE *)HeapAlloc(heap, 0, size);
    printf("Pointer %u is %08x (%08x)\n", count, ptr, size);

    pRealloc = (BYTE*) HeapReAlloc( heap, 0, ptr, reallocSize);
    if( pRealloc != ptr)
    {
        printf("Pointer %u changed to %08x\n", count, pRealloc);
    }
}

int main(int argc, char ** argv)
{
    HANDLE heap;

    heap = HeapCreate(0, 0, 0);
    if (heap == NULL)
    {
        printf("HeapCreate: %u\n", GetLastError());
        return 1;
    }

    walkheap(heap);

    alloc(heap, 1, 0x08000);
    alloc(heap, 2, 0x08000);
    alloc(heap, 3, 0x08000);
    alloc(heap, 4, 0x08000);

    alloc(heap, 10, 0x20000000);
    alloc(heap, 11, 0x20000000);
    alloc(heap, 12, 0x20000000);
    alloc(heap, 13, 0x20000000);

    alloc(heap, 20, 0x10000000);
    alloc(heap, 21, 0x10000000);
    alloc(heap, 22, 0x10000000);
    alloc(heap, 23, 0x10000000);

    walkheap(heap);

    return 0;
}

and my results (see the PROCESS_HEAP_ENTRY structure):

Address  Alloc    Overhead Region   Flags        Virtual Address Range Base

00420000 00000588 00000000 00000000 00000001 --> 00420000
004207e8 000007f8 00000010 00000000 00000000 --> 00420000
00421000 0003f000 00000000 00000000 00000002 --> 00420000
HeapWalk: 259
Pointer 1 is 004207e0 (00008000)
Pointer 2 is 004217f8 (00008000)
Pointer 3 is 00422810 (00008000)
Pointer 4 is 00423828 (00008000)
Pointer 10 is 00740020 (20000000)
Pointer 11 is 20750020 (20000000)
Pointer 12 is 52580020 (20000000)
Pointer 13 is 00000000 (20000000)
Pointer 20 is 40760020 (10000000)
Pointer 21 is 00000000 (10000000)
Pointer 22 is 00000000 (10000000)
Pointer 23 is 00000000 (10000000)
00420000 00000588 00000000 00000000 00000001 --> 00420000
004207e0 00001000 00000018 00000000 00000004 --> 00420000
004217f8 00001000 00000018 00000000 00000004 --> 00420000
00422810 00001000 00000018 00000000 00000004 --> 00420000
00423828 00001000 00000018 00000000 00000004 --> 00420000
00424848 0000e798 00000010 00000000 00000000 --> 00420000
00433000 0002d000 00000000 00000000 00000002 --> 00420000
00740020 00001000 00000020 00000040 00000024 --> 00740000
20750020 00001000 00000020 00000040 00000024 --> 20750000
52580020 00001000 00000020 00000040 00000024 --> 52580000
40760020 00001000 00000020 00000040 00000024 --> 40760000
HeapWalk: 259

It can be seen that the small allocations are packed tightly, but the big allocations are all in separate virtual address allocations. The free space in the separate allocations isn't being used. Also, only the main virtual address allocation has any heap blocks that are flagged as free space (flag equal to 0 or 2).

Answer 2

You are fragmenting the heap doing this. Whatever you release with realloc() gets added to the list of free blocks. Never to be used again because you always ask for a new block that's larger than that. These free blocks will just accumulate taking up virtual memory until no more is left. Happens pretty quickly when you throw away almost 50 megabytes at a time.

You'll need to rethink your approach.