看mballoc一开始是为了解决一个bug,但是代码没看完,bug已经解决了,仅仅是从C代码规范的处理的,和ext4自身逻辑没有什么关系,具体内容参看“ubsan: "shift exponent -1 is negative" in fs/ext4/mballoc.c:2612:15”,Bugzilla链接

ext4 mballoc特性是用进行一次性的多个块申请分配,官方定义:
What is multiblock allocation (mballoc)?
mballoc is a mechanism to allow many blocks to be allocated to a file in a single operation, in order to dramatically reduce the amount of CPU usage searching for many free blocks in the filesystem. Also, because many file blocks are allocated at the same time, a much better decision can be made to find a chunk of free space where all of the blocks will fit.
The mballoc code is active when using the O_DIRECT flag for writes, or if the delayed allocation(delalloc) feature isbeing used. This allows the file to have many dirty blocks submitted for writes at the same time, unlike the existing kernel mechanism of submitting each block to the filesystem separately for allocation.

整个机制就是使用了内存中曾经使用的buddy系统。在系统中最直接的体现就是:

如此就可以很明显的看到文件系统的每个group块组对应一个ext4_buddy,这里的buddy index是13,在ext4中每个group块组最多有32768即2^15个block,而ext4_buddy初始化时则将每个块组分成4个2^13的buddy组。

还是直接看代码,代码来自https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git: commit 3ec438afed6f166f1774b3e95b9a65e3b6da5f2c,主要就是ext4/mballoc.c。

ext4_mb_init_group是ext4 buddy的初始化函数,ext4_mb_get_buddy_page_lock名字上看似是获取buddy的访问锁,实际内容则是填充了ext4_buddy,进入ext4_mb_get_buddy_page_lock看一下是如何填充的:

本身也有lock的含义,就是稍后会填充具体的page内容,此时加锁而已,只是加锁地方比较隐晦,是在pagecache_get_page中实现的,在EXT4_MB_GRP_NEED_INIT这个宏上也有阻止并发的作用,指定group的bb_state被EXT4_GROUP_INFO_NEED_INIT_BIT反置。

ext4_buddy结构体如下:

ext4_mb_get_buddy_page_lock完成了内存的分配和结构体的填充,ext4_mb_init_cache则负责读取磁盘内存,初始化两个page的具体内容,

根据第二个参数incore是否存在判断是bitmap还是buddy初始化:

这就完成了块位图的初始化。

下面就是buddy的初始化,还是ext4_mb_init_cache,以incore作为判断条件,获取组描述符后初始化bb_counters。

整个ext4_group_info结构都是bb的东西了,重点就是ext4_mb_generate_buddy函数:

这样ext4 buddy初始化就完成了,实际进行block分配的时候去看ext4_mb_regular_allocator函数。

ext4_mb_regular_allocator是由ext4_mb_new_blocks调用的,先不看ext4_allocation_context的初始化,ext4_mb_load_buddy负责从磁盘上读取元数据到内存中,ext4_mb_load_buddy_gfp实际就是初始化ext4_buddy的过程,首先调用了ext4_mb_init_group函数,不提,然后使用find_get_page_flags从已经初始化后的内存中获取mmap的page内容,填充bd_buddy_page和bd_bitmap_page,基本和init差不太多。

回到ext4_mb_find_by_goal,看一下mb_find_extent函数,这个时候需要看一下ext4_allocation_context的初始化了,在ext4_mb_initialize_context中,通过对比ext4_allocation_context和ext4_allocation_request即可得出结果,后面可能会对于ext4_allocation_request.goal的值来源何处有疑问,可以参考ext4_inode_to_goal_block函数,来源于inode对应的块组的第一个block。

在ext4_mb_initialize_context中,

回到ext4_mb_find_by_goal下的mb_find_extent函数,block是group下的申请的block offset,needed则是length

这个时候就看到了一个函数mb_find_order_for_block,就是bugzilla中问题点,

----未完---


ext4 mballoc源代码分析来自于OenHan

链接为:http://oenhan.com/ext4-mballoc

7 对 “ext4 mballoc源代码分析”的想法;

  1. static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
    {
    int order = 1;
    int bb_incr = 1 <bd_blkbits – 1);
    void *bb;

    BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
    BUG_ON(block >= (1 <bd_blkbits + 3)));

    bb = e4b->bd_buddy;
    while (order bd_blkbits + 1) {
    block = block >> 1;
    if (!mb_test_bit(block, bb)) {
    /* this block is part of buddy of order ‘order’ */
    return order;
    }
    bb += bb_incr;
    bb_incr >>= 1;
    order++;
    }
    return 0;
    }

    这段函数,我看的很奇怪(可能是我理解的有问题)从我看来,这部分代码只会返回两种情况,一种情况是order =1 ,一种情况是order = 0.

    如果buddy 内存管理,可以看成每个高一级的层级下设两个低一级的成员,如果低层次的成员已经被占用,那么该成员对应的高一阶,必然也是被占用,因此,如果不可能返回大于2的order。

    所以这里while ,用的莫名其妙,效率并不高,空跑了10轮左右的判断。

    另外只能返回order 0 或者order 1,决定了外围步长的增长,每次增长2个block,如果 block = 7 needed = 3000,那么mb_find_extent 会循环1500次(如果bitmap空闲特别多的话)。

    因为此处理解不了代码的精妙,所以总觉得是我理解的有问题,望不吝赐教。

    1. @BEAN_LI 不太理解“不可能返回大于2的order”的推论,如果低层次的成员被占用,那么该成员所属的高层次成员也会被占用,但是如果某个order>2的成员下的所有低层次成员都没有被占用,那么该成员也没有被占用,那么为什么不能返回order>2呢?而且每个order层次上的成员也都并非只有一个。

      1. @OENHAN if (!mb_test_bit(block, bb)) {
        /* this block is part of buddy of order ‘order’ */
        return order;
        }

        因为如果某个order >2的成员下所有低层次成员都没有被占用,此处当order == 1时,mb_test_bit 返回0 ,即条件满足,直接return order了,没有机会再判断上一阶了。

        我们以军 师 旅 团 营 5阶为例阐述,军下设2个师,师下设2旅,旅下设2团, 依次类推。 如果 某一个营被占用了,那么该营所属的团必然也被占用,因为该团已经无法分配出整团的兵力去满足客户的需要了,依次类推,团所属的旅也一定被占用,因为无法调配出整个旅的兵力来满足内存需要了。 当前不在这条线路上的其他兄弟团 兄弟旅可能是 free的状态。但是这一支从树叶

        烦劳前辈赐教,我理解的错误之处。

        1. @BEAN_LI ext4_mb_mark_free_simple是buddy修改的代码,假定first=100,len=50,算一下mb_clear_bit行应该是什么样子,在这种情况下调用mb_find_order_for_block,block=100,如此order应该是多少;如果first=96,len=50呢?

        2. @BEAN_LI 这个地方“因为如果某个order >2的成员下所有低层次成员都没有被占用,此处当order == 1时,mb_test_bit 返回0 ,即条件满足,直接return order了,没有机会再判断上一阶了。” 你理解错了,order > 2的成员下所有低层次成员都没有被占用,但是根据算法bit位却都是1,只有order那个位置的bit位才是0,当计算到order == 1时, mb_test_bit 返回1 而不是0。
          在此答复,以方便后面的读者了解

  2. 这部分逻辑我基本看懂了,如下所示。 困惑点在mb_find_order_for_block。
    我再多花些时间琢磨琢磨吧,叨扰前辈了,多谢前辈指点。

    100 = 64 + 32 +4 len = 50 = 32+16+2
    max = 2 min = 5 ===> min = 2
    向前移动4位 + 4
    104 = 64 + 32 + 8 len = 46 = 50 -4 = 32 + 8 + 4 + 2
    max = 3 min = 5 ====> min = 3
    向前移动 8位
    112 = 64 +32 + 16 len = 38 = 32 + 4 + 2
    max = 4 min = 5 ===> min = 4
    向前移动16位
    128 = 128 len = 22 = 16 + 4 + 2
    max = 7 min = 4 ====> min = 4
    向前移动16位
    144 = 128 + 16 len = 6 = 4+2
    max = 4 min = 2 =====> min = 1
    向前移动 4位
    148 = 144 + 4 len = 2
    max = 2 min = 1 ===> min = 1
    向前移动2位
    150 = 144 +4 +2 len = 0
    ———————————————————
    96 = 64 + 32 len = 32+16+2
    max = 5 min = 5
    向前移动32位
    128 = 128 len = 18
    max = 7 min = 4
    向前移动16位
    144 = 128 + 16 len = 2
    max = 4 min = 1
    向前移动2位
    146 = 128 + 16 +2 len = 0

    1. @BEAN_LI 太客气了,我再补充两句:mb_find_order_for_block是依托于ext4_mb_mark_free_simple而存在的,block作为入参不是长度而是起始点,对于ext4_buddy减少块碎片不仅要处理申请的长度还要处理申请的起始点,起始点要尽可能紧凑,比如申请长度是50块的情况下,起点是96和100是不同的,96=64+32的起始点order=5,而100=64+32+4起始点order=2,目的就是要尽可能的紧凑,所谓的针对2的幂的削峰填谷。

发表评论