internals:zend_mm

Differences

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

Link to this comparison view

internals:zend_mm [2013/01/22 13:20]
krakjoe [Zend MM]
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 ===== 
-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 the same 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 MM provides the following (basic) 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 memory returned is optimized, and tracked. Tracking memory 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 works the way it does. 
-===== 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: 
- 
-1. 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> 
- 
-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.  
-<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> 
- 
-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 
-<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> 
- 
-5.1 is there any memory bigger than true_size?   
-<code c>  
-   bitmap = heap->free_bitmap >> index; 
-   if (bitmap) { 
-   } 
-</code> 
-    
-5.2 looking for the smallest of the memorys: 
-<code c> 
-   index += zend_mm_low_bit(bitmap); 
-</code> 
-  
-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 
-<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. 
- 
-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> 
- 
-6.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[4], 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 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. 
-<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. 
- 
-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.txt · Last modified: 2017/09/22 13:28 (external edit)