HeapWalker

Summary

The purpose of an article is to explain that how the heap manager handles memory blocks in a heap. The article will brief you about how to traverse a heap and understand a way the blocks are managed in a heap. The source code comes along with the article, which traverses a private and processes the default heap.

In Windows 2000, which is a 32-bit OS, every process has its own private virtual address space of 4Gb (which is 2^32). Because 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 is hidden from other processes' threads. Remember that virtual address space is only a range of the memory address, which is just a range of hexadecimal numbers from 0 to 0xFFFFFFFF in a 32-bit OS and in no way corresponds to physical storage. Physical storage needs to be mapped to a virtual address space before accessing a data without any runtime errors or crashes. From the user's perspective, virtual address space is a linear address space.

The Tool Help library can be used to traverse a list of processes running, traverse a list of modules currently loaded in a process, number of threads running in a process, and traverse a list of heaps being used in a process and walk through a heap. Most of us are familiar with process, module, and threads. Now, understand more about the heap and why are it is an important part of Windows Memory Management. This part of article will cover 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 a basic unit of memory called page. The size of page depends on the host computer. Mostly, the page size is 4Kb.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 reserved space in the virtual address space of a process. Heap management functions provide a API layer, return handles, and a pointer to memory blocks that have been allocated by these memory functions.

Always remember that the pointer to a 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 that provide better performance if you are allocating blocks of small memory of the same size. It is always recommended that you use VirtualXxx functions to allocate a memory block that could be a multiple of 1 page; for example, 4Kb. WinNT allows one process to allocate a memory in another process's address space.

GlobalAlloc and LocalAlloc functions provide memory from a default heap, sometimes referred as process heap. There is no local heap or global heap as it was in 16-bit WINOS. 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's default heap size can be controlled by the /HEAP switch. By default, the heap size is 1Mb. Windows NT marks all executable applications with 0x1000 (4Kb) initial committed memory for the default heap size.

GlobalAlloc and LocalAlloc functions allocate a block of memory that is already committed; hence, it does not provide better memory management. The VirtualXxx function provides better control over memory because you can commit a page based on your requirement. The VirtualAlloc function provides a functionality to reserve a page, reserve and commit a free page, and commit a reserved page. The VirtualFree function releases/decommits a region of pages within the virtual address space of a process. Decommitting means releasing physical memory associated or mapped to that page in the virtual address space. Decommitting memory and not releasing memory will cause its state to be changed to reserve. Attempting to read from or 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 the VirtualFree function.

Types of Memory Blocks

GlobalAlloc and LocalAlloc functions provide two block of memory: FIXED and MOVEABLE. MOVEABLE memory could be allocated with a DISCARDABLE flag. When allocating a FIXED memory block, the GlobalAlloc and LocalAlloc functions returns a pointer to a memory block. Workin with a FIXED memory block is the same as working with malloc and the free function of CRT. The pointer returned for a FIXED block can be used to free 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 memory is returned. This provides an abstract layer over an allocated memory. The 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 you have minimum heap fragmentation. Fixed blocks get allocated at the bottom of the heap, and movable blocks get locked down at the top. By marking your block movable, once it has been freed, that free space will quickly be reused by other locked, movable blocks. If another fixed block is allocated, 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 a 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 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 the process's default heap can be obtained by calling GetProcessHeap API. All processes have a private address space that ranges from 4Mb–2Gb; this is not shared with any other process. All dynamic heaps gets their allocations from this address range. Whenever the heap manager runs outs of memory—it does not have a 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 a size of the default heap is controlled by a /HEAP linker option. The /HEAP:0x2000, 0x1000 will reserve 8Kb (2 Page) and commits 4Kb of memory at the time it links an application. If not specified, then linker uses the default values of 0x100000 (1 Mb) reserved address space and 0x1000 (4Kb) committed memory. In Win32, GlobalAlloc and LocalAlloc use a common heap to fulfill a memory request's 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

The default heap plays an important role because it caters the requests from the CRT, Global, and Local memory management functions. There is no difference in a 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. You can understand an example that will help you grasp the concept of a 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 maximum 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 Pages.
         LPVOID lpFirstBlock = HeapAlloc(hPrivate,HEAP_ZERO_MEMORY,
                                         2 * KB_SIZE);
      // Allocating a second block of memory with a size of 0.5 Pages.
      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 iterate all the blocks of the memory and
      // will be calculate 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 contain
         //  all the details about committed blocks and uncommitted
         //  blocks 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
         //  number 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;
   }

HeapWalker

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's default heap because default heap handling is slightly different from the private heap.

I preferred to write a separate code to explore and study the internals of a default heap. 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 (4Kb) for committed memory blocks. These values are the request to the OS. The Heap manager may allocate big chunks of the committed memory blocks for better optimization.

If you walk through the default heap using the code, the output of your 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 16Kb. The total of committed and uncommitted blocks comes out to be 1Mb. And, if you 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

You have requested a block of 1 Page, but Heap manager can optimize by committing a large block of memory. The output for the above heap settings is as follows:

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

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 a 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 you dig deeper into HeapWalker code, you can learn whether a block of memory that was requested has been allocated from which of the regions. In the above case, the memory has been allocated from a second region:

The output for /HEAP:0x8000,0x8000 are 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 better validation on a heap. It won't allow the following heap settings, /HEAP:0x1000,0x3000, and the error will be as shown below:

LINK : fatal error LNK1229: Commit size greater than reserve size
   in "/HEAP"
The working of heap manager differs from different operating
   system/service packs.


Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • IBM Worklight is a mobile application development platform that lets you extend your business to mobile devices. It is designed to provide an open, comprehensive platform to build, run and manage HTML5, hybrid and native mobile apps.

  • Companies must routinely transfer files and share data to run their business, work with partners, and speed operations. However, many find the traditional approach to file transfer lacks necessary security, is too complex and difficult to manage, does not support the levels of automation needed, and breaks down when addressing the file transfer requirements of new areas like Big Data analytics and mobile applications. This QuinStreet SmartSelect discusses how the changing business environment is making the use …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds