zend_mm_search_large_block

2015-09-15 19:27:57   0  举报





`zend_mm_search_large_block`是Zend引擎中的一个函数，主要用于在大型内存块中进行搜索操作。这个函数的主要作用是在大内存块中查找特定的数据或模式。它使用了一种高效的搜索算法，可以在最短的时间内找到所需的数据。这种搜索方法特别适合于处理大量的数据，因为它不需要逐个检查每个数据，而是通过一些特殊的算法，直接定位到目标数据的位置。这种方法大大提高了搜索的效率，节省了大量的时间和资源。此外，`zend_mm_search_large_block`函数还具有很高的灵活性，可以根据实际需要进行配置和调整，以满足不同的搜索需求。

作者其他创作

大纲/内容

满足

应该目前没用

if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size))当前节点block的大小是否“正好”满足truesize通过p-info._size来判断

index++;index加一，去更大的那个bucket中去找

if (p-child[1])判断右孩子中是否有blk

为0，则我们需要在左孩子中继续寻找

bitmap = bitmap 1;当前heap-large_free_buckets[index];确定找不到可以满足truesize的block了，那么看看bitmap中更高一位是否存有东西，往存着更大size的block链表里面去找吧

有更大的block链表

是0

找到了

有

用

return null;large_free_buckets里面没有可以满足true_size需要的block

break;走到这个分支，意味着根据true_size的每一位bit值，我们在heap-large_free_buckets[index];中没有能够“恰好”满足true_size的block

return p-next_free_block;如果p所在树的这一层正好满足true_size我们就使用这一层同大小block链表的最近一个insert进来的那个block，即p-next_free_block

为1，则我们需要在右孩子中继续寻找

if (best_fit)这一路上是否找到不是恰好满足但是也能满足的block如果找到“恰好”满足的，肯定已经返回了，不会走到这里

for (m = true_size (ZEND_MM_NUM_BUCKETS - index); ; m = 1) 先将原truesize左移直到将最高位挤出，然后每次loop都将目前最高位挤出

是1

没有

best_fit = p;

if (UNEXPECTED(ZEND_MM_FREE_BLOCK_SIZE(p) == true_size))p指向的block的size是否恰好满足true_size？

当前节点不能恰好满足true_size，则需要继续在孩子中寻找p = p-child[p-child[0] != NULL]如果两个孩子都不为NULL，则如右孩子，直到左孩子或者右孩子为NULL时停止

没有更大的block链表

return best_fit-next_free_block;如果p所在树的这一层正好满足true_size我们就使用这一层同大小block链表的最近一个insert进来的那个block，即p-next_free_block

如果p所在树的这一层正好满足true_size我们就使用这一层同大小block链表的最近一个insert进来的那个block（如果只有一个，那next就是指向它自己），即p-next_free_block，为什么是next？详见add_to_free_list函数

return p-next_free_block;

是

while ((p = p-child[p-child[0] != NULL]))继续在当前block的孩子中寻找更小的block直到当前节点有任一孩子为NULL为止

return NULL;large_free_buckets里面没有可以满足true_size需要的block

bitmap = heap-large_free_bitmap index;将large_free_bitmap的最右边index位挪掉，剩余的最低位的位数即为原truesize的第index位

不满足

if ((m & (ZEND_MM_LONG_CONST(1) (ZEND_MM_NUM_BUCKETS-1))) == 0)判断当前最高位是0还是1

FALSE

if (!bitmap)还有没有更大的block链表了？

不恰好满足

index = ZEND_MM_LARGE_BUCKET_INDEX(true_size);index=truesize的最高位数的1的位数，比如index = LARGE_INDEX(80 = 1010000） = 6

for (p = rst; p; p = p-child[p-child[0] != NULL]) 如果在上面的搜寻中，虽然没有找到“恰好”满足true_size的block但在上面的逻辑中，如果我们试图找左孩子但为空时，记录了当时存在的右孩子，并放入rst，则在rst里面继续寻找，直到左孩子或者右孩子为NULL时停止

if (p-child[0])左孩子中是否有blk?

/* Search for smallest \"large\" free block */ best_fit = p = heap-large_free_buckets[index + zend_mm_low_bit(bitmap)];在比large_free_buckets[index]更大的bucket里面寻找，选择所有large_free_buckets里面比index大的，又有可用block的树表中，最小的那个，先将这个选中的bucket的头部作为目前的最优选择best_fit

恰好满足

p = p-child[0];将指针指向左孩子，进入下一循环

p = heap-large_free_buckets[index];取该链表头部指针

if (p-child[1]) { rst = p-child[1];}为避免左孩子中找不到合适的block，我们也记住当前的右孩子，一旦左孩子中找不到，我们可以使用右孩子中最小的block来满足truesize

if (ZEND_MM_FREE_BLOCK_SIZE(p) ZEND_MM_FREE_BLOCK_SIZE(best_fit))如果找到更小的比truesize大的内存设为best_fit

否

if (UNEXPECTED((bitmap & 1) != 0))通过bitmap来判断large_free_buckets[index]这一树表中是否有block因为large_free_buckets里面，index越大，里面的block大小越大所以我们先判断large_free_buckets[index]再判断large_free_buckets[larger]

p = p-child[1];将指针指向右孩子，进入下一循环

if (bitmap == 0)判断large_free_buckets[index or larger]中是否有blocks，来满足truesize的需求