PHP Internals — A Few Hard-to-Understand Points in Zend Memory Management中文EN

PHP's memory management is split into two major parts. The first part is PHP's own memory management — the main content here is application-facing management like reference counting and copy-on-write. The second part is what I'll introduce today: the part described in zend_alloc, which concerns PHP's internal memory management itself, including how it manages available memory, how it allocates memory, and so on.
Also, why am I writing this? Because previously there was no material explaining the strategies, data structures, or algorithms used in PHP's memory management. Yet when we develop extensions day to day or fix PHP bugs, we need a solid understanding of this part. Many friends in the PHP dev group are also not very clear on this area, so I feel it's worth writing about specifically.
I won't belabor the basic concepts, since they're easy to read off the code. Here I'll mainly introduce a few points that are harder to read off the code. Why do I say that? Hehe — before writing this article I looked through the existing material to avoid duplicating work, and among it I saw the TIPI project's description of this part, which I found to be full of errors. So I think this is exactly the part that isn't easy to understand even by reading the code 🙂
Currently, an English version of the description is also being written: Zend MM
The Zend Memory Manager, abbreviated Zend MM, is the logic for memory management in PHP. It has a key data structure: zend_mm_heap:

Zend MM divides memory into two kinds — small blocks and large blocks — and treats them differently. For small blocks, which are by far the most common, it pursues high performance. For large blocks, it pursues safety, avoiding memory waste as much as possible.
So, for small blocks, PHP also introduced a cache mechanism:

Zend MM hopes that, thanks to the cache, it can locate and allocate in a single lookup.
One point that isn't easy to read is the declaration of free_buckets:
Q: Why is the length of the free_buckets array ZEND_MM_NUMBER_BUCKET?
A: It's because PHP uses a trick here — it stores ZEND_MM_NUMBER_BUCKET zend_mm_free_block entries in a fixed-length array, as shown by the red box in the figure above. For an unused free_buckets element, the only useful data structures are next_free_block and prev_free_block, so to save memory PHP does not allocate ZEND_MM_NUMBER_BUCKET * sizeof(zend_mm_free_block) worth of memory, but only ZEND_MM_NUMBER_BUCKET * (sizeof(*next_free_block) + sizeof(*prev_free_block)) worth..
Let's look at the definition of the ZEND_MM_SMALL_FREE_BUCKET macro:

#define ZEND_MM_SMALL_FREE_BUCKET(heap, index) \
    (zend_mm_free_block*) ((char*)&heap->free_buckets[index * 2] + \
        sizeof(zend_mm_free_block*) * 2 - \
        sizeof(zend_mm_small_free_block))

After this, Zend MM guarantees that it will only ever use the prev and next pointers, so it won't cause incorrect memory reads..
So, the second point that isn't easy to read is PHP's management of large_free_buckets. Let me first introduce allocation (the TIPI project's description of this part is a bit vague):

static zend_mm_free_block *zend_mm_search_large_block(zend_mm_heap *heap, size_t true_size)

large_free_buckets can be seen as a combination of a tree and a doubly-linked list:

large_free_buckets uses a macro to decide which index a given size of memory lands on:

#define ZEND_MM_LARGE_BUCKET_INDEX(S) zend_mm_high_bit(S)

zend_mm_high_bit gets the ordinal of the highest set bit in true_size (zend_mm_high_bit); the corresponding assembly instruction is bsr (here the TIPI project incorrectly describes it as: "This hash function is used to compute the number of bits of size, and the return value is the count of 1s in the binary representation of size minus 1").
In other words, each element in large_free_buckets holds a pointer to a memory block whose size has a 1 in the bit corresponding to that index. Whoa, that's a mouthful. An example:
For instance, large_free_buckets[2] holds only memory whose size is between 0b1000 and 0b1111. And for example: large_free_buckets[6] holds pointers to memory whose size is between 0b10000000 and 0b11111111.
This way, when allocating memory, Zend MM can quickly locate the most likely suitable region to search in, improving performance.
And each element is simultaneously a doubly-linked list, holding memory blocks of the same size, while its left and right children (child[0] and child[1]) represent the key values 0 and 1. What do these key values mean?
Let's take an example. Suppose I ask PHP for a piece of memory whose true_size is 0b11010. After a series of steps, no suitable memory is found, and PHP enters the zend_mm_search_large_block logic to look for suitable memory in large_free_buckets:
1. First, compute the index corresponding to true_size, using the ZEND_MM_LARGE_BUCKET_INDEX method described earlier.
2. Then, in a bitmap structure, check whether any available memory larger than true_size already exists in large_free_buckets; if not, return:

size_t bitmap = heap->large_free_bitmap >> index;
if (bitmap == 0) {
   return NULL;
}

3. Check whether free_buckets[index] has any available memory:

if (UNEXPECTED((bitmap & 1) != 0))

4. If it does, start from free_buckets[index] and look for the best-fitting memory, with the following steps:
4.1. Starting from free_buckets[index], if the current memory size of free_buckets[index] equals true_size, the search ends and it returns successfully.
4.2. Look at the current highest set bit of true_size after shifting (true_size << (ZEND_MM_NUM_BUCKETS - index)). If it is 1, keep searching under free_buckets[index]->child[1]; if free_buckets[index]->child[1] doesn't exist, break out. If the current highest bit of true_size is 0, keep searching under free_buckets[index]->child[0]; if free_buckets[index]->child[0] doesn't exist, then look for the smallest memory under free_buckets[index]->child[1] (because at this point we can guarantee that all memory under free_buckets[index]->child[1] is larger than true_size).
4.3. The starting point changes to the child mentioned in step 2, and left-shift ture_size by one bit.
5. If the above logic did not find suitable memory, then look for the smallest "large" free block:

   /* Search for smallest "large" free block */
    best_fit = p = heap->large_free_buckets[index + zend_mm_low_bit(bitmap)];
    while ((p = p->child[p->child[0] != NULL])) {
        if (ZEND_MM_FREE_BLOCK_SIZE(p) < ZEND_MM_FREE_BLOCK_SIZE(best_fit)) {
            best_fit = p;
        }
    }

Note the logic above: (p = p->child[p->child[0] != NULL]) — PHP is trying hard to find the smallest memory.
Why do we say large_free_buckets is a key tree? From the logic above we can see that PHP uses the binary 0s and 1s of a size as keys, projecting the memory-size information onto a key tree, which makes fast lookup easier.
In addition, there is also a rest_buckets. This structure is a doubly-linked list, used to hold the leftover memory after PHP allocates, avoiding the performance cost of pointlessly inserting the remaining memory into free_buckets (here the TIPI project incorrectly describes it as: "This is an array with only two elements. And the insertion and lookup operations we commonly use are against the first element, i.e. heap->rest_buckets[0]").