Heap Data Structures

A power tool to understand memory layout

Core analyzer

Anatomy of Memory Managers

The advantage of Core analyzer is its ability to parse heap memory into millions of individual memory blocks, which are allocated to application by heap memory manager. Only with this knowledge can Core Analyzer check memory corruption and search for object references. Users are encouraged to understand the basic heap data structures in order to maximize the benefits of the tool and develop your own support of custom memory manager if necessary.

I will briefly illustrate the data structures used by Linux/Windows/Mac OS system runtime memory managers. They are either open sourced or reverse engineered. You can find more detail in the source files of the project, Linux kernel source or from numerous on-line websites. Since OS vendors may change the implementation for each new version, this description may differ from what you are using. In all figures below, shaded areas represent heap data structures and blank areas are user space.

1. Ptmalloc

This is the memory manager used by GNU C library on Linux. The library glibc has a global “struct malloc_state” object, named main_arena, which is the root of all managed heap memory.

size

prev_size

in-use chunk

next chunk

user data

size

prev_size

free chunk

next chunk

free space

Arena is a logic collection of memory regions which are illustrated by various colored outlines. An arena could serve one memory request at a time. If there are multiple requests at the same time, ptmalloc would use other arenas to fulfill the requests simultaneously. If no arena is immediately available, new arena is created. Heap is a single contiguous memory region which consists of user memory blocks. An arena may have one or more arenas at any time.

The difference between the main arena and a dynamically created arena is how they acquire memory from kernel. Main arena calls sbrk() which usually starts immediately after the executable’s data section. On the other hand, a dynamic arena uses mmap() with fixed size, e.g. 64MB, and make sure the starting address is also aligned on the multiple of the size. If the first heap is used up, a new fix-sized heap is mmap-ed, which links to the dynamic arena’s heap data “strcut malloc_state”.

If the user’s request exceeds a threshold, e.g. 128KB, which may be changed dynamically, ptmalloc calls mmap() to allocate the memory and munmap() when it is freed. This class of memory blocks is not linked by any heap data.

Each memory block on a heap is managed by a “struct malloc_chunk”, boundary tag. We can easily walk the heap as a link list with each tag as the offset to the next memory block.

struct malloc_chunk {

INTERNAL_SIZE_T prev_size;

INTERNAL_SIZE_T size;

struct malloc_chunk* fd;

struct malloc_chunk* bk;

};

Depending on whether a block and its previous and next blocks are free or in-use, some data fields of the structure are not used and may be part of the user space. Data in shaded area are heap data and belong to ptmalloc. If overwritten by application, it is typical heap data corruption.

2. Windows Memory Manager

To walk through memory heaps on Windows, we start with a global object peb (Process Environment Block). Its data member “ProcessHeaps” points to an array of pointers of “struct _HEAP”, which is terminated by a NULL pointer. A heap keeps a list of segments.

peb

ProcessHeaps

struct _HEAP

. . .

strcut _HEAP*

SegmentList

. . .

struct _HEAP_SEGMENT

A segment is a piece of contiguous memory space, which is described by a “struct _HEAP_SEGMENT”. It has pointers to the first and last memory block residing in the segment. There are also some uncommitted memory ranges in the segment which will be made available when necessary. Each memory block is preceded by a “struct _HEAP_ENTRY” which consists of the information of the block’s user space size, padding, status, encryption byte, etc. In debug mode, a “struct _CrtMemBlockHeader” is added ahead of user space.

3. Mac OS Memory Manager

The memory manager on Mac OS has two global variables that sit on top of the heap data structures: “malloc_zones” and “malloc_num_zones”. The former points to an array of “struct szone_t” and the later is the size of the array. Compared with Ptmalloc of glibc, zone is the equivalent of arena on Mac OS, while region is the same as heap. Multiple zones are created to serve many threads simultaneously.

struct _HEAP_SEGMENT

FirstEntry

LastValidEntry

UCRSegmentList

Reserved/Uncommited

struct _HEAP_ENTRY

release mode

struct _HEAP_ENTRY

debug mode

struct _CrtMemBlockHeader

Like most memory managers, different algorithm is adopted based on the size of a memory request. If memory request size is no larger than 31*TINY_QUANTUM, or 496 byte, tiny region is used. If the size is equal to or larger than 15KB, large region is utilized. Otherwise, small region is picked to fulfill the request. Their heap data structures are illustrated below. Unlike Ptmalloc, there is no tag attached to each memory block. Instead, each region has a bit map which flags the status of the corresponding block in the region.