最近看到Yoshinori Matsunobu在官方buglist上提交的一个Bug#68077，大意是说，当使用压缩表时，在bp吃紧时，存在过度碎片合并的情况。Innodb压缩表由于存在不同的Page Size，因此使用buddy allocator的方式进行内存分配，他的内存块来自于buffer pool中。
如bug#68077所提到的，如果我们使用的全部是4kb的内存块，那么把他们合并成8k的又有什么意义呢？并且在碎片整理的过程中，函数buf_buddy_free
的效率是很低的。在之前已经碰到过很多类似的案例，例如DROP TABLE，在遍历block，释放adaptive hash index记录时，可能会在这里hang住。
但从Marko的角度来看，由于内存是从buffer pool中分配的，如果不做碎片合并的话，很容易导致大量的4KB的页面存留在内存中，这对非压缩表而言是不可用的;如果你释放了4*n*4k的压缩页内存，那在buffer pool中就有n个16kb的block是可以为非压缩表所用的。
不过合并成8KB的block对只使用4kb和16kb的场景用处并不大，在回收内存时，也存在时间复杂度较高的情况
简单看看buddy allocator如何分配和回收内存。
A.分配内存
接口函数：buf_buddy_alloc
参数描述：
buf_pool_t* buf_pool //当前page所在的bp对象
ulint size //压缩页需要的内存大小
ibool* lru //表示是否是从bp->LRU上分配的内存
通过size，计算出其在buf_pool->zip_free[]数组中的slot（buf_buddy_get_slot），例如1kb，对应slot 0，4kb对应slot 2
具体内存分配实现函数是buf_buddy_alloc_low，注意调用这个函数需要持有bp->mutex，并且不可持有bp->zip_mutex或者任何block->mutex。内存分配的方式也是典型的binary buddy allocator 算法
1.首先尝试从buf_pool->zip_free[]数组中查找(buf_buddy_alloc_zip)，优先从buddy system中分配block
>>根据slot，查看bp->zip_free对应数组元素链表，如果有的话，则将其从zip_free中移除，以占用这个block(buf_buddy_remove_from_free)
>>如果没有对应slot的空闲块，则查找更大的空闲块，例如，如果没有4kb的空闲块，我们就去看有没有8kb的空闲块，这里采用递归调用buf_buddy_alloc_zip(buf_pool, i + 1)的方法来返回block。
虽然递归算法存在效率问题，不过幸好这里的递归深度不会很大，最多4层调用
例如，我们申请4kb的内存块，这里我们获得一个8kb的内存块，只将低位的拿来用，而高位的4kb则放到bp->zip_free链表上，状态设置为BUF_BLOCK_ZIP_FREE
如果我们申请的是2kb的内存块，当前只有8kb的空闲块，那么会产生一个新的4kb的和2Kb的空闲块
这种情况下，我们可以直接返回获得的block首地址；
2.如果bp->zip_free上没有空闲块，就从bp->free上取一个block（buf_LRU_get_free_only）
如果buffer pool没有的话，就调用buf_LRU_get_free_block，获得的block的状态被设置为BUF_BLOCK_READY_FOR_USE
这里存在的困惑是，buf_LRU_get_free_block同样也会调用buf_LRU_get_free_only,因为它是一个通用的获取空闲块的函数，同样也会先去看看free list上有没有空闲块，这里似乎存在着重复调用，尽管这对性能影响不大。
3.当我们从LRU或Free List上得到一个空闲块后，就：
首先将其状态设置为BUF_BLOCK_MEMORY，再将其插入到bp->zip_hash中（buf_buddy_block_register）
再从其中首地址取得想要的内存块大小，剩下的进行切分，放到bp->zip_free中(buf_buddy_alloc_from)
B.回收内存
接口函数：buf_buddy_free
参数描述
buf_pool_t* buf_pool //当前Page所在的bp对象
void* buf //将被释放的块首地址
ulint size //块大小
相对于分配，回收内存要复杂一些，因为这里还涉及到内存整理。回收内存具体函数为buf_buddy_free_low，由于函数中存在大量的goto，以下按照正常思维的逻辑，而非代码的至上而下分析：
首先，判断是否需要进行碎片整理：
1.如果相同大小的碎片数小于16，不进行整理(UT_LIST_GET_LEN(buf_pool->zip_free[i]) < 16)；
2.看看相邻的block(buf_buddy_get)，称为buddy
如果这个block被标记为BUF_BLOCK_ZIP_FREE，会遍历当前slot对应的bp->zip_free，看看buddy是不是在其中。
这一步的目的实际上是为了确认邻居block和当前要释放的block是否是同样大小的，但不幸的是，这里采用遍历bp->zip_free的方法，复杂度为O(n)。如果zip_free链表很长的话，显然开销是不可接受的。
如果邻居节点可以用来合并，那就将其从zip_free中移除(buf_buddy_remove_from_free)，并继续去尝试合并；
例如，我们要释放2kb的block，发现邻近有个空闲2kb的，合并成4kb后，如果发现邻近还有个4kb的，就会去合并成8kb的block。
当合并成16kb的block后，已经和普通非压缩表使用的块一样了，就将其“还”给bp，从bp->zip_hash中删除，并将其加入到bp->free空闲链表中（buf_LRU_block_free_non_file_page），这种情况就直接返回，不进行下面的逻辑了。
当发现无法再合并buddy后，查看当前slot在zip_free中是否存在空闲块，如果有的话，则先将这个page从zip_free中移除（buf_buddy_remove_from_free），然后尝试把buddy的数据转移到zip_free链表头（buf_buddy_relocate，在某些情况下不可以迁移，例如这个buddy是被IO FIX的），将其置为BUF_BLOCK_ZIP_FREE，再去进行合并。如果不能块迁移，就再把这个block加入到free list上。
以上都是比较典型的binary buddy allocator算法。但也可以看到，这里面涉及到大量的内存操作和内存块迁移，难怪会被人吐槽该函数的效率太低下。。。
~~~~~~~~~~~
另外最近一个跟Percona相关的bug#1100159，属于Percona在引入新的特性时的失误导致，一个用buf_page_alloc_descriptor分配的内存块，却使用buf_buddy_free来释放，尽管对应的code path不容易触发，但这依然是一个很严重的问题，如果碰到了，直接就导致crash了。Percona应该在下一个版本，也就是Percona Server 5.5.30版本Fix这个问题
