This is an old revision of the document!
Zend Memory Manager
- Version: 1.0
- Date: 2011-11-09
- Author: Xinchen Hui laruence@php.net
- First Published at: https://wiki.php.net/internals/zend_mm
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