Differences

This shows you the differences between two versions of the page.

--- internals:zend_mm [2011/11/09 12:43]
laruence
+++ internals:zend_mm [2017/09/22 13:28]
@@ Line 1: / Line 1: @@
-====== 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
-===== Background =====
-<code>
-<laruence_> Felipe, is there any docs about zend mm?
-<Felipe> laruence_: almost nothing... just Zend/README.ZEND_MM
-</code>
-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 =====
-<code c>
-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
-};
-</code>
-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.
-{{:internals:zend_mm.png|}}
-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:
-<code c>
-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;
-</code>
-and the ZEND_MM_SMALL_FREE_BUCKET macro :
-<code c>
-#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))
-</code>
-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:
-<code c>
-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
-</code>
-and the ZEND_MM_BUCKET_INDEX macro:
-<code c>
-#define ZEND_MM_BUCKET_INDEX(true_size)     ((true_size>>ZEND_MM_ALIGNMENT_LOG2)-(ZEND_MM_ALIGNED_MIN_HEADER_SIZE>>ZEND_MM_ALIGNMENT_LOG2))
-</code>
-so if the index at the cache is valid, the memory is returned immediatly.
-{{:internals:zend_mm_cache.png|}}
-===== 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:
-{{:internals:zend_mm_large_buckets.png|}}
-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:
-. compute the ture_size, the true size if a padding size.
-<code c>
-#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)))
-</code>
-. if the true size is a small size,  then goto 3.  otherwise goto 6.
-. compute the index at the cache for the true size.
-<code c>
-#define ZEND_MM_BUCKET_INDEX(true_size)     ((true_size>>ZEND_MM_ALIGNMENT_LOG2)-(ZEND_MM_ALIGNED_MIN_HEADER_SIZE>>ZEND_MM_ALIGNMENT_LOG2))
-</code>
-. if the heap->cache[index] is valid,  then allocating succeed and return.
-. try to find a "best smallest" memory for the need at the heap->free_buckets, if found, return
-<code c>
-        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;
-        }
-</code>
-.1 is there any memory bigger than true_size?
-<code c>
-   bitmap = heap->free_bitmap >> index;
-   if (bitmap) {
-   }
-</code>
-.2 looking for the smallest of the memorys:
-<code c>
-   index += zend_mm_low_bit(bitmap);
-</code>
-.3 allocating succeed and return
-. try to find the best memory in the heap->large_free_buckets
-.1 compute the index at heap->large_free_buckets
-<code c>
-#define ZEND_MM_LARGE_BUCKET_INDEX(S) zend_mm_high_bit(S)
-</code>
-the zend_mm_high_bits return the order of highest 1 in the S(bsr in asm). ie: 0x01001001 will result a 6.
-.2 is there any valid memory bigger than true_size? if not goto 7.
-<code c>
-    size_t bitmap = heap->large_free_bitmap >> index;
-    if (bitmap == 0) {
-        return NULL;
-    }
-</code>
-.3-A if heap->large_free_buckets[index] is valid, otherwise goto 6.3-B
-<code c>
-    if (UNEXPECTED((bitmap & 1) != 0)) {
-    } else /* goto 6.3-B */
-</code>
-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[index], try to find the best fit size memory for the true size accroding to the each bit of the true_size.
-<code c>
-    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++;
-    }
-</code>
-let's take the b101010 as a example:
-a. first compute the index,  if the memory at the index is exactly  is the same size as true_size, then allocating succeed, and return the block->next_free_buckets.
-b. look at second 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 true_size(which make the next bit in the true_size will be considered in the next loop), goto a, start a new loop.
-.3-B looking for the smallest "large memory". if found, allocating succeed, and return best_fit->next_free_block.
-<code c>
-    /* 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;
-        }
-    }
-</code>
-Note the (p = p->child[p->child[0] != NULL]), Zend MM is trying to find the "smallest" one.
-. 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
-. 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

Differences

Page Tools