internals:zend_mm
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 < | ||
- | * Chinese: http:// | ||
- | * First Published at: https:// | ||
- | ===== Background ===== | ||
- | < | ||
- | < | ||
- | < | ||
- | </ | ||
- | 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, | ||
- | |||
- | for large memory, | ||
- | |||
- | ===== Struct zend_mm_heap ===== | ||
- | <code c> | ||
- | struct _zend_mm_heap { | ||
- | int | ||
- | void | ||
- | void (*_free)(void*); | ||
- | void | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | zend_mm_segment | ||
- | zend_mm_storage | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | size_t | ||
- | void | ||
- | int | ||
- | int | ||
- | #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 | ||
- | #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/ | ||
- | |||
- | {{: | ||
- | |||
- | there is one question I want do explain is that free_buckets, | ||
- | <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; | ||
- | </ | ||
- | |||
- | and the ZEND_MM_SMALL_FREE_BUCKET macro : | ||
- | <code c> | ||
- | #define ZEND_MM_SMALL_FREE_BUCKET(heap, | ||
- | (zend_mm_free_block*) ((char*)& | ||
- | 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 is used to cache some memory, | ||
- | |||
- | 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-> | ||
- | /* Get block from cache */ | ||
- | #if ZEND_MM_CACHE_STAT | ||
- | heap-> | ||
- | heap-> | ||
- | #endif | ||
- | best_fit = heap-> | ||
- | heap-> | ||
- | heap-> | ||
- | ZEND_MM_CHECK_MAGIC(best_fit, | ||
- | ZEND_MM_SET_DEBUG_INFO(best_fit, | ||
- | HANDLE_UNBLOCK_INTERRUPTIONS(); | ||
- | return ZEND_MM_DATA_OF(best_fit); | ||
- | } | ||
- | #if ZEND_MM_CACHE_STAT | ||
- | heap-> | ||
- | #endif | ||
- | #endif | ||
- | </ | ||
- | |||
- | and the ZEND_MM_BUCKET_INDEX macro: | ||
- | <code c> | ||
- | #define ZEND_MM_BUCKET_INDEX(true_size) | ||
- | </ | ||
- | |||
- | so if the index at the cache is valid, the memory is returned immediatly. | ||
- | |||
- | {{: | ||
- | ===== zend_mm_heap-> | ||
- | |||
- | ===== zend_mm_heap-> | ||
- | if a memory block with a size bigger than ZEND_MM_MAX_SMALL_SIZE, | ||
- | |||
- | 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, | ||
- | |||
- | that means, each item in the large_free_buckets holds the size which with a corresponding index order value 1. | ||
- | |||
- | ie: | ||
- | the heap-> | ||
- | ===== zend_mm_heap-> | ||
- | |||
- | ===== 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) | ||
- | </ | ||
- | |||
- | 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) | ||
- | </ | ||
- | |||
- | 4. if the heap-> | ||
- | |||
- | 5. try to find a "best smallest" | ||
- | <code c> | ||
- | bitmap = heap-> | ||
- | if (bitmap) { | ||
- | /* Found some " | ||
- | index += zend_mm_low_bit(bitmap); | ||
- | best_fit = heap-> | ||
- | goto zend_mm_finished_searching_for_block; | ||
- | } | ||
- | </ | ||
- | |||
- | 5.1 is there any memory bigger than true_size? | ||
- | <code c> | ||
- | | ||
- | if (bitmap) { | ||
- | } | ||
- | </ | ||
- | |||
- | 5.2 looking for the smallest of the memorys: | ||
- | <code c> | ||
- | index += zend_mm_low_bit(bitmap); | ||
- | </ | ||
- | |||
- | 5.3 allocating succeed and return | ||
- | |||
- | 6. try to find the best memory in the heap-> | ||
- | |||
- | 6.1 compute the index at heap-> | ||
- | <code c> | ||
- | #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. | ||
- | <code c> | ||
- | size_t bitmap = heap-> | ||
- | |||
- | if (bitmap == 0) { | ||
- | return NULL; | ||
- | } | ||
- | </ | ||
- | |||
- | 6.3-A if heap-> | ||
- | <code c> | ||
- | 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), | ||
- | that is, Zend MM start from large_free_buckets[index], | ||
- | <code c> | ||
- | if (UNEXPECTED((bitmap & 1) != 0)) { | ||
- | /* Search for best " | ||
- | zend_mm_free_block *rst = NULL; | ||
- | size_t m; | ||
- | size_t best_size = -1; | ||
- | |||
- | best_fit = NULL; | ||
- | p = heap-> | ||
- | for (m = true_size << (ZEND_MM_NUM_BUCKETS - index); ; m <<= 1) { | ||
- | if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size)) { | ||
- | return p-> | ||
- | } else if (ZEND_MM_FREE_BLOCK_SIZE(p) >= true_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-> | ||
- | rst = p-> | ||
- | } | ||
- | if (p-> | ||
- | p = p-> | ||
- | } else { | ||
- | break; | ||
- | } | ||
- | } else if (p-> | ||
- | p = p-> | ||
- | } else { | ||
- | break; | ||
- | } | ||
- | } | ||
- | |||
- | for (p = rst; p; p = p-> | ||
- | if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size)) { | ||
- | return p-> | ||
- | } else if (ZEND_MM_FREE_BLOCK_SIZE(p) > true_size && | ||
- | | ||
- | best_size = ZEND_MM_FREE_BLOCK_SIZE(p); | ||
- | best_fit = p; | ||
- | } | ||
- | } | ||
- | |||
- | if (best_fit) { | ||
- | return best_fit-> | ||
- | } | ||
- | bitmap = bitmap >> 1; | ||
- | if (!bitmap) { | ||
- | return NULL; | ||
- | } | ||
- | index++; | ||
- | } | ||
- | </ | ||
- | |||
- | let's take the b101010 as a example: | ||
- | |||
- | a. first compute the index, | ||
- | |||
- | b. look at second bit of the true_size, it's 0, so Zend MM will looking for the best fit in the block-> | ||
- | |||
- | c. if the bit is 0, but the block doesn' | ||
- | |||
- | d. if the bit is 1, but the block doesn' | ||
- | |||
- | 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. | ||
- | |||
- | 6.3-B looking for the smallest "large memory" | ||
- | <code c> | ||
- | /* Search for smallest " | ||
- | best_fit = p = heap-> | ||
- | while ((p = p-> | ||
- | if (ZEND_MM_FREE_BLOCK_SIZE(p) < ZEND_MM_FREE_BLOCK_SIZE(best_fit)) { | ||
- | best_fit = p; | ||
- | } | ||
- | } | ||
- | </ | ||
- | |||
- | Note the (p = p-> | ||
- | |||
- | 7. search in the rest_buckets, | ||
- | |||
- | 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)