看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系统。在系统中最直接的体现就是:

[oenhan@oenhan.com]$ cat /proc/fs/ext4/loop0/mb_groups
#group: free  frags first [ 2^0   2^1   2^2   2^3   2^4   2^5   2^6   2^7   2^8   2^9   2^10  2^11  2^12  2^13  ]
#0    : 28809 3     134   [ 3     3     2     1     1     1     1     0     0     0     0     0     1     3     ]
#1    : 32647 1     121   [ 1     1     1     0     0     0     0     1     1     1     1     1     1     3     ]
#2    : 28672 1     4096  [ 0     0     0     0     0     0     0     0     0     0     0     0     1     3     ]
#3    : 32647 1     121   [ 1     1     1     0     0     0     0     1     1     1     1     1     1     3     ]
#4    : 32768 1     0     [ 0     0     0     0     0     0     0     0     0     0     0     0     0     4     ]
#5    : 32647 1     121   [ 1     1     1     0     0     0     0     1     1     1     1     1     1     3     ]
#6    : 32768 1     0     [ 0     0     0     0     0     0     0     0     0     0     0     0     0     4     ]
#7    : 14643 1     121   [ 1     1     2     1     0     1     0     2     2     1     1     2     2     0     ]

如此就可以很明显的看到文件系统的每个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看一下是如何填充的:

static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
ext4_group_t group, struct ext4_buddy *e4b, gfp_t gfp)
{      //所有的buddy的内存内容都是由s_buddy_cache统一管理
struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
int block, pnum, poff;
int blocks_per_page;
struct page *page;

e4b->bd_buddy_page = NULL;
e4b->bd_bitmap_page = NULL;
        // 此处我们假定所有的块大小都是4k,所以blocks_per_page=1
blocks_per_page = PAGE_SIZE / sb->s_blocksize;
/*
 * 对ext系列了解的就清楚,数据块位图需要占用一个块,
 * 同时buddy的存储也是占用一个块,所以一个块组里面
 * 需要使用2个块,因为所有的buddy的内存内容都是顺序
         * 排列的,offset其实就是group*2。
 */block = group * 2;
pnum = block / blocks_per_page;
poff = block % blocks_per_page;
//pnum作为offset传入。
page = find_or_create_page(inode->i_mapping, pnum, gfp);
if (!page)
return -ENOMEM;
BUG_ON(page->mapping != inode->i_mapping);
e4b->bd_bitmap_page = page;
//获取映射的page
e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);

if (blocks_per_page >= 2) {
/* buddy and bitmap are on the same page */return 0;
}

block++;
pnum = block / blocks_per_page;
page = find_or_create_page(inode->i_mapping, pnum, gfp);
if (!page)
return -ENOMEM;
BUG_ON(page->mapping != inode->i_mapping);
e4b->bd_buddy_page = page;
return 0;
}

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

ext4_buddy结构体如下:

struct ext4_buddy {
struct page *bd_buddy_page; //page结构
void *bd_buddy; // buddy的page地址
struct page *bd_bitmap_page;
void *bd_bitmap; //位图的page地址
struct ext4_group_info *bd_info;
struct super_block *bd_sb;
__u16 bd_blkbits;
ext4_group_t bd_group;
};

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

page = e4b.bd_bitmap_page;
ret = ext4_mb_init_cache(page, NULL, gfp);
page = e4b.bd_buddy_page;
ret = ext4_mb_init_cache(page, e4b.bd_bitmap, gfp);

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

static int ext4_mb_init_cache(struct page *page, char *incore, gfp_t gfp)
{
//page->index就是find_or_create_page中的offset
first_group = page->index * blocks_per_page / 2;
for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
//读取位图blk
     bh[i] = ext4_read_block_bitmap_nowait(sb, group);
//等待IO完成
     err2 = ext4_wait_block_bitmap(sb, group, bh[i]);
}

struct buffer_head *
ext4_read_block_bitmap_nowait(struct super_block *sb, ext4_group_t block_group)
{
desc = ext4_get_group_desc(sb, block_group, NULL);
bitmap_blk = ext4_block_bitmap(sb, desc);
bh = sb_getblk(sb, bitmap_blk);
//比较简单,以上三个函数就完成了功能
//但因为块位图是异步的,后续的一大串都是同步处理,不提
}

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

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

struct ext4_group_info {
unsigned long   bb_state;
struct rb_root  bb_free_root;
ext4_grpblk_tbb_first_free;/* first free block */ext4_grpblk_tbb_free;/* total free blocks */ext4_grpblk_tbb_fragments;/* nr of freespace fragments */ext4_grpblk_tbb_largest_free_order;/* order of largest frag in BG */
//所谓的buddy就是指下面的计数器了
ext4_grpblk_tbb_counters[];/* Nr of free power-of-two-block
 * regions, index is order.
 * bb_counters[3] = 5 means
 * 5 free 8-block regions. */};

memset(grinfo->bb_counters, 0,
//就是前面提到的blocksizebit+2
sizeof(*grinfo->bb_counters) * (sb->s_blocksize_bits+2));

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

void ext4_mb_generate_buddy(struct super_block *sb,
void *buddy, void *bitmap, ext4_group_t group)
{
//max这里是簇的概念
ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
i = mb_find_next_zero_bit(bitmap, max, 0);
grp->bb_first_free = i;
 while (i < max) {
fragments++;
first = i;
//找到下一个空格
i = mb_find_next_bit(bitmap, max, i);
//len是两个簇之间空闲的长度了
len = i - first;
free += len;
if (len > 1)
//ext4_mb_mark_free_simple就是将len进行二进制化填充到bb_counters里面
//二进制化趋向最大化融合,初始化就是4*2^13
ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
else
//等于1,个数都划归到buddy0里面
grp->bb_counters[0]++;
if (i < max)
i = mb_find_next_zero_bit(bitmap, max, i);
}
//fragment就是碎片化,其实也是簇值
grp->bb_fragments = fragments;

//设置可选用的最大的碎片index
mb_set_largest_free_order(sb, grp);

clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));

period = get_cycles() - period;
spin_lock(&EXT4_SB(sb)->s_bal_lock);
EXT4_SB(sb)->s_mb_buddies_generated++;
EXT4_SB(sb)->s_mb_generation_time += period;
spin_unlock(&EXT4_SB(sb)->s_bal_lock);
}

这样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。

/*
 * i_block_group is the number of the block group which contains
 * this file's inode.  Constant across the lifetime of the inode,
 * it is ued for making block allocation decisions - we try to
 * place a file's data blocks near its inode block, and new inodes
 * near to their parent directory's inode.
 */block_group = ei->i_block_group;
bg_start = ext4_group_first_block_no(inode->i_sb, block_group);
return bg_start;

在ext4_mb_initialize_context中,

struct ext4_allocation_request {
/* target inode for block we're allocating */struct inode *inode;
/* how many blocks we want to allocate */unsigned int len;
/* logical block in target inode */ext4_lblk_t logical;
/* the closest logical allocated block to the left */ext4_lblk_t lleft;
/* the closest logical allocated block to the right */ext4_lblk_t lright;
/* phys. target (a hint) */ext4_fsblk_t goal;
/* phys. block for the closest logical allocated block to the left */ext4_fsblk_t pleft;
/* phys. block for the closest logical allocated block to the right */ext4_fsblk_t pright;
/* flags. see above EXT4_MB_HINT_* */unsigned int flags;
};
struct ext4_free_extent {
ext4_lblk_t fe_logical;
ext4_grpblk_t fe_start;/* In cluster units */ext4_group_t fe_group;
ext4_grpblk_t fe_len;/* In cluster units */};

ext4_mb_initialize_context(struct ext4_allocation_context *ac,
struct ext4_allocation_request *ar)
{
//goal的来源前面说了
goal = ar->goal;
//这个函数比较坑爹,如果认为和ext4_group_first_block_no不一致
//仔细看do_div函数
ext4_get_group_no_and_offset(sb, goal, &group, &block);

/* set up allocation goals */ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
ac->ac_status = AC_STATUS_CONTINUE;
ac->ac_sb = sb;
ac->ac_inode = ar->inode;
//inode的逻辑块
ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
ac->ac_o_ex.fe_group = group;
//目标对应的group中的block offset
ac->ac_o_ex.fe_start = block;
ac->ac_o_ex.fe_len = len;
ac->ac_g_ex = ac->ac_o_ex;
ac->ac_flags = ar->flags;
}

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

static int mb_find_extent(struct ext4_buddy *e4b, int block,
int needed, struct ext4_free_extent *ex)
{
buddy = mb_find_buddy(e4b, 0, &max);//max值是group最大block

//block已经被分配了,buddy中没有了
if (mb_test_bit(block, buddy)) {
ex->fe_len = 0;
ex->fe_start = 0;
ex->fe_group = 0;
return 0;
}
/* find actual order */order = mb_find_order_for_block(e4b, block);
block = block >> order;

ex->fe_len = 1 << order;
ex->fe_start = block << order;
ex->fe_group = e4b->bd_group;
}

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

static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
{
int order = 1;
void *bb;

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

bb = e4b->bd_buddy;
while (order <= e4b->bd_blkbits + 1) {
block = block >> 1;
if (!mb_test_bit(block, bb)) {
/* this block is part of buddy of order 'order' */return order;
}
//触发点就是order>bd_blkbits,也就是order==13
bb += 1 << (e4b->bd_blkbits - order);
order++;
}
return 0;
}

----未完---


ext4 mballoc源代码分析来自于OenHan

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

8 thoughts on “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的幂的削峰填谷。

      1. @OENHAN 您好,“目的就是要尽可能的紧凑,所谓的针对2的幂的削峰填谷”—我对这个结论还是不太能理解,请问下在分配50块长度的情况下,96和100哪个起点更合适,麻烦前辈能再解释的通俗些嘛,多谢了!

发表回复