Heap Walker

• Download source files - 7.52 Kb

Summary

The purpose of this article is to explain how the heap manager handles memory blocks in a heap. The article will brief about how to traverse a heap and understand the way the blocks are managed in a heap. The source code along with this article traverses a process’ default heap.

In Windows 2000, which is a 32 bit OS, every process has its own private virtual address space of 4 GB [which is 2^32). Since every process has its own virtual address space, threads associated with that process could access only the virtual address space of that process. The address space belonging to other processes is not accessible and it’s hidden from other process’ threads. Remember that virtual address space is only a range of memory address, which is just a range of hexadecimal numbers from 0 to 0xFFFFFFFF in a 32 bit OS, and in no way does it correspond to physical storage. Physical storage needs to be mapped to virtual address space before accessing a data without any runtime errors or crashes. From the user perspective, virtual address space is a linear address space.

The Tool Help library can be used to traverse a list of processes running, traversing a list of modules currently loaded in a process, threads running in a process, and traverse a list of heap addresses being used in a process and to walk through a heap. Most of us are familiar with processes, modules and threads. Let us understand more about the heap and why they are an important part of Windows Memory Management. This part of the article will be covering different aspects of heap memory.

Heap memory functions provide an API layer over a NT Virtual Memory Manager. Heap memory functions provide better control as compared to VirtualAlloc functions because the basic unit of memory with which VirtualAlloc function works is one page. Physical storage and the virtual address space of each process are divided into basic units of memory called pages. The size of a page depends on the host computer. Mostly, the page size is 4 KB. The virtual address space associated with a process is used for loading DLLs, heap, stack and virtual memory allocations. Heap is a region that corresponds to a reserved space in the virtual address space of a process. Heap management functions provide API layer return handles and pointers to memory blocks which have been allocated by these memory functions. Always remember that a pointer to memory is returned only when you have allocated a fixed block of memory and the handle will be returned for a movable block of allocated memory. The CRT [C Runtime Library] exposes memory management functions which provide a better performance if we are allocating blocks of small memory of the same size. It is always recommended to use VirtualXxx functions to allocate a memory block that could be a multiple of 1 page, i.e., 4KB. WinNT allows one process to allocate a memory in another process’ address space.

GlobalAlloc and LocalAlloc functions provide memory from a default heap, sometimes referred to as process heap. There is no local heap or global heap as it was in the 16 bit Win OS. There is no difference for the memory allocations from a local heap or a global heap. Always remember that the virtual address space that has been reserved needs to be mapped to physical memory [sum of RAM + paging file] before you can proceed to access that address space. The process’ default heap size can be controlled by the /HEAP switch. By default, the heap size is 1 MB. Windows NT marks all executable applications with 0x1000 (4K) initial committed memory for the default heap size.

GlobalAlloc and LocalAlloc functions allocate a block of memory that is already committed and hence it does not provide a better memory management. VirtualXxx function provides a better control over memory because you can commit a page based on your requirement. VirtualAlloc function provides functionality to reserve a page, reserve and commit a free page, or commit a reserved page. VirtualFree function releases/decomitts a region of pages within the virtual address space of a process. Decommitting means releasing a physical memory associated or mapped to that page in the virtual address space. Decommitting a memory and not releasing a memory will cause its state to be changed to reserve. Attempting to read from / write to a reserve page will cause an access violation exception. The memory pages in the virtual address space should be in the same state (reserve or commit) to be released by VirtualFree function.

Types of Memory Blocks

GlobalAlloc and LocalAlloc functions provide two blocks of memory: fixed and moveable. Moveable memory could be allocated with the DISCARDABLE flag. When allocating a fixed memory block, the GlobalAlloc and LocalAlloc functions return a pointer to a memory block. To work with a fixed memory block is same as working with malloc and the free function of CRT. The pointer returned for a fixed block can be used to free the memory allocated without retrieving a handle to that memory, by calling GlobalHandle function. In the case of moveable memory, instead of a pointer, the handle to the memory is returned. This is to provide an abstract layer over the allocated memory. Heap manager can move this memory block within its heap.

Moveable memory blocks are much preferable than fixed memory blocks. The system performance is better if we have minimum heap fragmentation. Fixed blocks get allocated at the bottom of the heap, and moveable blocks get locked down at the top. By marking your block moveable, once it has been freed, that free space will quickly be reused by other locked moveable blocks. If another fixed block is allocated, then when the first block is released, it will cause a hole to be created in the fixed memory area.

In brief, moveable means that a block may be moved in memory during a heap compaction to provide sufficient free space for other allocation requests. Discardable means that a block may be stored to disk and retrieved later, when needed again. Locked memory blocks are not moved or discarded. A fixed memory block will never be moved or discarded.

A process can have a dynamic heap, which is created by calling the HeapCreate API that can be created/destroyed on the fly. The default heap is created before the process begins and is released/destroyed when the process terminates. The handle to a process’ default heap can be obtained by calling the GetProcessHeap API. All processes have a private address space which ranges from 4 MB – 2 GB, which is not shared with any other process. All dynamic heaps get their allocations from this address range. Whenever the heap manager runs outs of memory, i.e., it does not have sufficient memory to fulfill a request for memory allocation, the heap will commit an additional page of memory. The size of the dynamic heap can be controlled by the parameters specified in a call to the HeapCreate API, whereas the size of the default heap is controlled by a /HEAP linker option. The /HEAP:0x2000, 0x1000 will reserve 8 KB (i.e., two pages) and commit 4 KB of memory at the time of linking an application. If not specified, then the linker uses the default values of 0x100000 (1 MB) reserved address space and 0x1000 (4K) committed memory. In Win32, GlobalAlloc and LocalAlloc use a common heap to fulfill a memory request— default heap.

Each application, whether it is an EXE or DLL, stores its information in its image file. The PE header information can be read by using a link program, which is a linker.

link –dump –headers <filepath>

The output of the above command for my executable is as follows:

1000 size of heap reserve
1000 size of heap commit

Default heap plays an important role as it caters the requests from CRT, Global and Local memory management functions. There is no difference in the way the CRT, Global and Local memory functions access the default heap.

Win32 provides rich APIs that can be used to traverse a heap and analyze each block within the heap. Let’s understand an example which will help us to grasp the concept of heap.

// HeapSample.H 

#include <windows.h> 
#include <iostream.h> 
#include <vector> 

using namespace std;
#define KB_SIZE 1024

#include "HeapSample.h"

typedef vector <PROCESS_HEAP_ENTRY> HeapEntryVector; 

int main()
{
  // Creating a Private Heap, with committed memory of 1 Page
  // and mazimum memory of 3 Page.
  HANDLE hPrivate = HeapCreate(0,4*KB_SIZE,12*KB_SIZE);

  if (hPrivate == NULL)
  {
    cout<<"HeapCreate Function Failed"<endl;
    return 1;
  }
  else
    cout<<"HeapCreate Function Succeeded::Value of Handle::"<hPrivate<endl;

  // Allocating a block of memory with a size of 0.5 Page.
  LPVOID lpFirstBlock = HeapAlloc(hPrivate,HEAP_ZERO_MEMORY,2 * KB_SIZE);

  // Allocating a second block of memory with a size of 0.5 Page.
  LPVOID lpSecondBlock = HeapAlloc(hPrivate,HEAP_ZERO_MEMORY,2 * KB_SIZE);

  // Traversing a Heap blocks by using a HeapWalk API.
  HeapEntryVector heapEntryVec;
  PROCESS_HEAP_ENTRY pHeapEntry;

  // Initialize data members of PROCESS_HEAP_ENTRY to Zero.
  ZeroMemory(&pHeapEntry,sizeof(pHeapEntry));

  pHeapEntry.lpData = NULL;

  unsigned long totalBytes = 0;
  unsigned long committedBytes = 0;
  unsigned long uncommittedBytes = 0;

  // This loop will be iterating all the blocks of the memory and will be 
  // Calculating the committed and uncommitted memory for a heap.

  BOOL bFirstBlock = false;
  unsigned long prevPointerAdd = 0;

  while (BOOL bWalk = HeapWalk(hPrivate,&pHeapEntry))
  {
    heapEntryVec.push_back(pHeapEntry);
  }

  HeapEntryVector::iterator iterHeapEntry = heapEntryVec.begin();
  int pos = 0;
  for (iterHeapEntry; iterHeapEntry != heapEntryVec.end(); 
                      iterHeapEntry++, pos++)
  {
    PROCESS_HEAP_ENTRY tempHeapEntry = (PROCESS_HEAP_ENTRY)(*iterHeapEntry);
    // This represents the REGION block,
    // which will containing all the details about
    // committed block and uncommitted block present in a Heap.

    if (!bFirstBlock)
    {
      totalBytes = (unsigned long) tempHeapEntry.lpData - 
                   (unsigned long) hPrivate;
      totalBytes += (unsigned long) tempHeapEntry.Region.lpFirstBlock - 
                    (unsigned long)tempHeapEntry.lpData;
      committedBytes += (unsigned long)tempHeapEntry.Region.lpFirstBlock - 
                        (unsigned long)tempHeapEntry.lpData;
      committedBytes += (unsigned long)tempHeapEntry.lpData - 
                        (unsigned long) hPrivate;
      bFirstBlock = true;
    }

    // This represents the allocated blocks in a heap.
    // The amount of bytes in the block is obtained 
    // by subtracting the starting address [virtual address]
    // of the next block from the 
    // starting address [ virtual address ] of the present block.
    if (tempHeapEntry.wFlags == PROCESS_HEAP_ENTRY_BUSY)
    {
      unsigned long bytesAllocated = 
         (unsigned long) heapEntryVec[pos + 1].lpData - 
         (unsigned long) tempHeapEntry.lpData;
      totalBytes += bytesAllocated;
      committedBytes += bytesAllocated;
    }

    // This represents the committed block which
    // is free, i.e. not being allocated or not being used
    // as control structure. Data member cbData represents
    // the size in bytes for this range of free block.

    if (tempHeapEntry.wFlags == 0)
    {
      totalBytes += tempHeapEntry.cbData;
      committedBytes += tempHeapEntry.cbData;
    }

    // For Uncommitted block, cbData represents the size
    // (in bytes) for range of uncommitted memory.
    //
    if (tempHeapEntry.wFlags == PROCESS_HEAP_UNCOMMITTED_RANGE)
    {
      uncommittedBytes += tempHeapEntry.cbData;
      totalBytes += tempHeapEntry.cbData;
    }
  }// end of for loop

  cout<<"Total Bytes in Heap::"<totalBytes<endl;
  cout<<"Total Committed Bytes in Heap::"<committedBytes<endl;
  cout<<"Total UnCommitted Bytes in Heap::"<<uncommittedBytes<endl;

  return 0;

}

The output of this code will be:

Total Bytes in Heap::12288
Total Committed Bytes in Heap::8192
Total UnCommitted Bytes in Heap::4096

The above code may not work as expected with a process’ default heap because the default heap handling is slightly different from the private heap.

I preferred to write separate code to explore and study the internals of the default heap, and my findings are as follows:

The /HEAP switch impacts the distribution of the committed and uncommitted blocks in the default heap. If the /HEAP switch is not specified, the default values will be 0x100000 (1 MB) for reserved address space and 0x1000 (4K) for committed memory blocks. These values are the request to the OS, the heap manager may allocate a big chunk of committed memory blocks for better optimization.

If we walk through the default heap using the code, the output of our traverse is:

Region Details in Heap::
Committed Block Size::16384
UnCommitted Block Size::1032192
Total Bytes in Heap::1048576
Total Committed Bytes in Heap::16384
Total UnCommitted Bytes in Heap::1032192

It means that the heap manager commits the block of memory, which is of size 16 Kb, and the total of committed and uncommitted blocks comes out to be 1 MB.

And, if we change the default heap by using the /HEAP switch, the impact on the distribution of the reserved and committed blocks is as follows:

/HEAP:0x3000,0x1000

As we have requested a block of 1 page, but the heap manager can optimize committing a large block of memory, the output for the above heap settings is as follows:

This region represents the block which has been requested by the /HEAP switch and the memory allocated to it differs from what was already existing:

Region Details in Heap::
Committed Block Size::12288
UnCommitted Block Size::0

This region represents the region which is managed by the VirtualAlloc function, and hence in the code, we have used the VirtualQuery function to query the memory block within this region.

Region Details in Heap::
Committed Block Size::8192
UnCommitted Block Size::1040384 (This is a sum of 1MB – 2KB, 
       which were committed by heap manager to cater a request of 0.5 Page.)
Total Bytes in Heap::1060864
Total Committed Bytes in Heap::20480
Total UnCommitted Bytes in Heap::1040384

If we dig deeper into the HeapWalker code, we can come to know whether a block of memory which was requested has been allocated and from which of the regions. In the above case, the memory has been allocated from the second region.

The output for /HEAP:0x8000,0x8000 is as follows:

Region Details in Heap::
Committed Block Size::32768
UnCommitted Block Size::0
Total Bytes in Heap::32768
Total Committed Bytes in Heap::32768
Total UnCommitted Bytes in Heap::0

The output for /HEAP:0x14000,0x14000 is as follows:

Region Details in Heap::
Committed Block Size::16384
UnCommitted Block Size::65536
Total Bytes in Heap::81920
Total Committed Bytes in Heap::16384
Total UnCommitted Bytes in Heap::65536

Visual Studio 6.0 service pack 6.0 provides a better validation on the heap. It won’t allow the following heap settings: /HEAP:0x1000,0x3000, and the error will be as below:

LINK : fatal error LNK1229: Commit size greater than reserve size in "/HEAP"

The working of the heap manager differs with different operating systems/service packs.