Zend Memory Manager

• Version: 1.0
• Date: 2011-11-09
• Author: Xinchen Hui laruence@php.net
• Chinese(中文版): http://www.laruence.com/2011/11/09/2277.html
• First Published at: https://wiki.php.net/internals/zend_mm

<laruence> Felipe, is there any docs about zend mm?  
<Felipe> laruence: almost nothing... just Zend/README.ZEND_MM 

So I decided to write one, to describe the whole implement of Zend mm(memory allocating, memory freeing)

I am not good at english, so if you find some wrong words, plz feel free to edit it.

PHP is written entirely in C. In C, the programmer is responsible for the allocation and release of memory during runtime.

PHP has very specific requirements for management of memory and many modes of execution; all sharing a common set of requirements.

The memory manager in PHP, named Zend MM, facilitates these requirements in the same way, whatever the mode of execution, whatever the code.

The memory manager has two distinct types of allocation:

small: when allocating small blocks of memory, it is important that the manager is fast and efficient. 

large: when allocating large blocks of memory, it is important that the manager minimizes wastage.

The developer makes allocations that have two distinct life cycles:

request: the most common type of allocation made; the developer requires the memory to service the current request

persistent: the developer intends to reference the memory in multiple requests

The MM provides the following (per request) functions:

void*  emalloc(size_t size);
void*  erealloc(void* pointer, size_t size);
void*  ecalloc(size_t num, size_t count);
void   efree(void* pointer);

They all share prototype and functionality with the standard C implementation, but the allocation is optimized, and tracked. Tracking allocations allows a margin of error not normally present in C programming: memory that is not free'd explicitly will normally be free'd by the implementation at the appropriate time, such as the end of the request, or the end of execution.

Zend provides the following (persistence) functions:

void* pemalloc(size_t size, zend_bool persistent);
void* perealloc(void* pointer, size_t size, zend_bool persistent);
void* pecalloc(size_t num, size_t count, zend_bool persistent);
void  pefree(void* pointer, zend_bool persistent);

Persistent memory is not optimized, or tracked by the implementation, and should only be used if the developer requires a structure to survive requests.

The following diagrams and explanations provide insight into how and why Zend MM manages the per request memory it allocates.

struct _zend_mm_heap {
    int                 use_zend_alloc;
    void               *(*_malloc)(size_t);
    void                (*_free)(void*);
    void               *(*_realloc)(void*, size_t);
    size_t              free_bitmap;
    size_t              large_free_bitmap;
    size_t              block_size;
    size_t              compact_size;
    zend_mm_segment    *segments_list;
    zend_mm_storage    *storage;
    size_t              real_size;
    size_t              real_peak;
    size_t              limit;
    size_t              size;
    size_t              peak;
    size_t              reserve_size;
    void               *reserve;
    int                 overflow;
    int                 internal;
#if ZEND_MM_CACHE
    unsigned int        cached;
    zend_mm_free_block *cache[ZEND_MM_NUM_BUCKETS];
#endif
    zend_mm_free_block *free_buckets[ZEND_MM_NUM_BUCKETS*2];
    zend_mm_free_block *large_free_buckets[ZEND_MM_NUM_BUCKETS];
    zend_mm_free_block *rest_buckets[2];
    int                 rest_count;
#if ZEND_MM_CACHE_STAT
    struct {
        int count;
        int max_count;
        int hit;
        int miss;
    } cache_stat[ZEND_MM_NUM_BUCKETS+1];
#endif
};

the free_buckets and large_free_buckets is the key part we will introduce, since it is the main role in the memory allocating/freeing.

there is one question I want do explain is that free_buckets, we saw that there are ZEND_MM_NUMBER_BUCKETS * 2, why *2? let's looking at the struct zend_mm_small_free_block:

typedef struct _zend_mm_small_free_block {
    zend_mm_block_info info;
#if ZEND_DEBUG
    unsigned int magic;
# ifdef ZTS
    THREAD_T thread_id;
# endif
#endif
    struct _zend_mm_free_block *prev_free_block;
    struct _zend_mm_free_block *next_free_block;
} zend_mm_small_free_block;

and 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))

this is a tricky way to store ZEND_MM_NUMER_BUCKET into a fixed length array.

and only the prev_free_block and next_free_block will be use in that way, looking at the picture above, the red box.

so actually there is same ZEND_MM_NUMBER_BUCKET buckets stored in the free_buckets array.

cache is used to cache some memory, make emalloc/efree of samll memory quickly.

looking at the codes in the zend_mm_alloc_int:

size_t index = ZEND_MM_BUCKET_INDEX(true_size);
.....
.....
#if ZEND_MM_CACHE
        if (EXPECTED(heap->cache[index] != NULL)) {
            /* Get block from cache */
#if ZEND_MM_CACHE_STAT
            heap->cache_stat[index].count--;
            heap->cache_stat[index].hit++;
#endif
            best_fit = heap->cache[index];
            heap->cache[index] = best_fit->prev_free_block;
            heap->cached -= true_size;
            ZEND_MM_CHECK_MAGIC(best_fit, MEM_BLOCK_CACHED);
            ZEND_MM_SET_DEBUG_INFO(best_fit, size, 1, 0);
            HANDLE_UNBLOCK_INTERRUPTIONS();
            return ZEND_MM_DATA_OF(best_fit);
        }
#if ZEND_MM_CACHE_STAT
        heap->cache_stat[index].miss++;
#endif
#endif

and the ZEND_MM_BUCKET_INDEX macro:

#define ZEND_MM_BUCKET_INDEX(true_size)     ((true_size>>ZEND_MM_ALIGNMENT_LOG2)-(ZEND_MM_ALIGNED_MIN_HEADER_SIZE>>ZEND_MM_ALIGNMENT_LOG2))

so if the index at the cache is valid, the memory is returned immediatly.

if a memory block with a size bigger than ZEND_MM_MAX_SMALL_SIZE, then it will be considerd as a large block, stored in the large_free_buckets.

the large_free_buckets is almost a trie tree + list:

as I said above, that there is a number of ZEND_MM_NUMBER_BUCKET large_free_bucket, and will see that Zend MM use the order of the highest 1 in the true_size of a memory request to determined the index.

that means, each item in the large_free_buckets holds the size which with a corresponding index order value 1.

ie: the heap->large_free_buckets[2] holds the pointer of memory block which size is between 0b1000 and 0b1111, and the heap->large_free_buckets[6] holds pointer of memory block which size is between 0b10000000 and 0b11111111.

when PHP call emalloc. the whole process will be like:

1. compute the ture_size, the true size if a padding size.

#define ZEND_MM_TRUE_SIZE(size)             ((size<ZEND_MM_MIN_SIZE)?(ZEND_MM_ALIGNED_MIN_HEADER_SIZE):(ZEND_MM_ALIGNED_SIZE(size+ZEND_MM_ALIGNED_HEADER_SIZE+END_MAGIC_SIZE)))

2. if the true size is a small size, then goto 3. otherwise goto 6.

3. compute the index at the cache for the true size.

#define ZEND_MM_BUCKET_INDEX(true_size)     ((true_size>>ZEND_MM_ALIGNMENT_LOG2)-(ZEND_MM_ALIGNED_MIN_HEADER_SIZE>>ZEND_MM_ALIGNMENT_LOG2))

4. if the heap->cache[index] is valid, then allocating succeed and return.

5. try to find a “best smallest” memory for the need at the heap->free_buckets, if found, return

        bitmap = heap->free_bitmap >> index;
        if (bitmap) {
            /* Found some "small" free block that can be used */
            index += zend_mm_low_bit(bitmap);
            best_fit = heap->free_buckets[index*2];
            goto zend_mm_finished_searching_for_block;
        }

5.1 is there any memory bigger than true_size?

   bitmap = heap->free_bitmap >> index;
   if (bitmap) {
   }

5.2 looking for the smallest of the memorys:

   index += zend_mm_low_bit(bitmap);

5.3 allocating succeed and return

6. try to find the best memory in the heap->large_free_buckets

6.1 compute the index at heap->large_free_buckets

#define ZEND_MM_LARGE_BUCKET_INDEX(S) zend_mm_high_bit(S)

the zend_mm_high_bits return the order of highest 1 in the S(bsr in asm). ie: 0x01001001 will result a 6.

6.2 is there any valid memory bigger than true_size? if not goto 7.

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

6.3-A if heap->large_free_buckets[index] is valid, otherwise goto 6.3-B

    if (UNEXPECTED((bitmap & 1) != 0)) {
    } else /* goto 6.3-B */

as I said, the large_free_buckets is kind of trie tree, assuming a true_size(b01001010), Zend vm try to find the best_fit by hash the binary value as a 'key'. that is, Zend MM start from large_free_buckets[4], try to find the best fit size memory for the true size accroding to the each bit of the true_size.

    if (UNEXPECTED((bitmap & 1) != 0)) {
        /* Search for best "large" free block */
        zend_mm_free_block *rst = NULL;
        size_t m;
        size_t best_size = -1;
 
        best_fit = NULL;
        p = heap->large_free_buckets[index];
        for (m = true_size << (ZEND_MM_NUM_BUCKETS - index); ; m <<= 1) {
            if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size)) {
                return p->next_free_block;
            } else if (ZEND_MM_FREE_BLOCK_SIZE(p) >= true_size &&
                       ZEND_MM_FREE_BLOCK_SIZE(p) < best_size) {
                best_size = ZEND_MM_FREE_BLOCK_SIZE(p);
                best_fit = p;
            }
            if ((m & (ZEND_MM_LONG_CONST(1) << (ZEND_MM_NUM_BUCKETS-1))) == 0) {
                if (p->child[1]) {
                    rst = p->child[1];
                }
                if (p->child[0]) {
                    p = p->child[0];
                } else {
                    break;
                }
            } else if (p->child[1]) {
                p = p->child[1];
            } else {
                break;
            }
        }
 
        for (p = rst; p; p = p->child[p->child[0] != NULL]) {
            if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size)) {
                return p->next_free_block;
            } else if (ZEND_MM_FREE_BLOCK_SIZE(p) > true_size &&
                       ZEND_MM_FREE_BLOCK_SIZE(p) < best_size) {
                best_size = ZEND_MM_FREE_BLOCK_SIZE(p);
                best_fit = p;
            }
        }
 
        if (best_fit) {
            return best_fit->next_free_block;
        }
        bitmap = bitmap >> 1;
        if (!bitmap) {
            return NULL;
        }
        index++;
    }

let's take the b101010 as a example:

a. first compute the index, if the memory block in the large_free_buckets[index] is exactly is the same size as true_size, then allocating succeed, and return the block->next_free_buckets.

b. look at highest(based on index: m = true_size << (ZEND_MM_NUM_BUCKETS - index)) bit of the true_size, it's 0, so Zend MM will looking for the best fit in the block->child[0], if the block->child[0] is the same size as true_size, then allocating succeed, return, if it's 1, Zend MM will do the looking loop in the block->child[1].

c. if the bit is 0, but the block doesn't has a child[0]? Zend MM will try to find the samllest memory under the block->child[1].

d. if the bit is 1, but the block doesn't has a child[1], goto 6.3-B

f. left shift m(which make the next bit in the true_size will be considered in the next loop), and make the current node as child[1] or child[0](described above), then goto a, start a new loop.

6.3-B looking for the smallest “large memory”. if found, allocating succeed, and return best_fit->next_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 (p = p->child[p->child[0] != NULL]), Zend MM is trying to find the “smallest” one.

7. search in the rest_buckets, it is a list. used to cache some big size memory before put them into free_buckets, if found allocating succeed, and return

8. apply for new memory from OS, then allocating part of it to PHP, store the rest parts. and return.

• 2011-11-09 Xinchen Hui: Initial creation