internals:zend_mm

This is an old revision of the document!


Zend Memory Manager

Background

<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.

Zend MM

Zend mm is the memory manager of PHP, it apply memory from OS, then allocate the memory to PHP script by emalloc.

Zend mm divides memory into two type, small memory and large memory.

for small memory, Zend mm target at emalloc/efree quickly, and also has a cache mechanism for them.

for large memory, Zend mm is very careful to avoid memory waste.

Struct zend_mm_heap

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.

zend_mm_heap->cache

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.

zend_mm_heap->free_buckets

zend_mm_heap->large_free_buckets

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.

zend_mm_heap->rest_buckets

memory allocating

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.

memory freeing

Changelog

  • 2011-11-09 Xinchen Hui: Initial creation
internals/zend_mm.1322633371.txt.gz · Last modified: 2017/09/22 13:28 (external edit)