学步园

Front End Allocator (FEA)

FEA could be Look Aside List (LAL) FEA or Low Fragmentation (LF) FEA on Windows.

LAL is used on all pre-Vista Windows. It is a 128-entry table recording free heap memory blocks. Each entry points to a singly-linked list of free heap memory blocks of the same size, where the sizes are 16 for entry 1, 24 for entry 2, …, and 1024 for entry 127. Entry 0 is not used.

FEA is the first handling layer when a memory allocation request is received. If FEA finds a matching free block, the block is returned to caller. Otherwise, the request is passed to BEA below.

Back End Allocator (BEA)

BEA is also a 128-entry table recording free heap memory blocks. Each try in BEA points to a doubly-linked list of free heap memory blocks. Entry 2 is for 16-byte free block, entry 3 for 24, …, and entry 127 for 1016-byte free blocks. Entry 1 is not used. Entry 0 is special; it has a list of free blocks of 1024+ bytes, and they are sorted by ascending in size. We can see, both LAL and BEA are optimized to deal with small memory allocations faster.

BEA also has a bitmap, where each bit represents whether the corresponding entry has free blocks at all. This is to know faster without checking the actual lists. BEA always maintain the bitmap to be up-to-date.

Heap Blocks

The memory block that is returned to application is the user accessible part of a heap block. A heap block actually also has a preallocation metadata block and a postallocation metadata block. Heap blocks are next to each other linearly in a heap segment. Given any heap block, you can walk all the heap blocks in the same heap segment using the metadata.

Heap Segments

A heap segment is large chunk of memory allocated from the lower-level virtual memory manager. The heap manager keeps a list of up to 64 heap segments.

When BEA cannot satisfy a request, it tries to allocate a new heap segment. When allocating a new heap segment, the heap manager basically calls VirtualAlloc(MEM_RESERVE) to allocate a big chunk of virtual address block. The new heap segment size doubles that of the last one. If this fails, the size is reduced to its half. This repeats until it succeeds or the size is too small (64-byte).

When the heap segment is allocated, the heap manager commits the leading portion with VirtualAlloc(MEM_COMMIT) to satisfy the caller request. Further requests on the heap segment incur commits on the uncommitted portion of it.

In the end, all heap blocks are on the committed portion of one of the heap segments. The heap block can be in one of the following states:

1. In use by application. This heap block is not recorded in the LAL or BEA table/lists.
2. Free (in LAL). The free heap block is recorded in LAL only. BEA sees it as busy (i.e., in use by application).
3. Free (in BEA). The free heap block is recorded in BEA only.

Heap Coalescing

Over the time, with a lot of allocations and freeing, the heap may fragment, meaning there are a lot of small allocations here and there in the heap segment, but the no single free heap block is big enough to serve next request. Heap coalescing is an approach to help fighting this.

When an application frees a heap block to a heap segment, its two neighbor heap blocks are also checked. If at least one of them is free, the blocks are merged to create a larger free block. BEA’s free lists and bitmap are also updated to reflect the change.

User Allocation of Heap Memory

1. If LAL has a matching free block, it is removed and returned to the user; otherwise go to next step.
2. The heap manager checks the request.
   1. If BEA has a matching free block, the heap block is marked as “busy”, then removed from the free list and returned to the user; Bitmap is updated if necessary.
   2. If BEA has a larger (2x size) free block available, it is split into two. One is put into a free list; the other is marked “busy” and returned to the user; the larger block is removed from the free list. Bitmap is updated if necessary.
   3. If the heap segment has enough uncommitted portion, a new heap block is committed, marked as “busy” and returned to the user; Bitmap is updated if necessary.
   4. It tries to allocate a new heap segment, then commit a heap block, mark it as “busy” and return to the user. Bitmap is updated if necessary.
   5. If all the above fail, it returns an error (out of memory).

User Freeing Heap Memory

1. If LAL has a matching entry, the heap block is added to the corresponding entry’s free list; otherwise go to the next step.
2. The heap manager checks the neighboring heap blocks in the heap segment.
   1. If any of them is free, coalescing is performed to merge them into a larger heap block: a). Remove them from free lists; b). Add new large block to a free list or LAL; c). Update heap block metadata to “free”.
   2. If no coalescing is possible, the block is put into the free list or LAL, and heap block metadata is updated to “free”.

Reference
Advanced Windows Debugging, Addison-Wesley