在塊分配機(jī)制中，涉及到幾個(gè)主要的數(shù)據(jù)結(jié)構(gòu)。

　　通過ext4_allocation_request描述塊請(qǐng)求，然后基于塊查找結(jié)果即上層需求來決定是否執(zhí)行塊分配操作。

　　在分配過程中，為了更好執(zhí)行分配，記錄一些信息，需要對(duì)分配行為進(jìn)行描述，就有結(jié)構(gòu)體ext4_allocation_contex。

　　在搜尋可用空間過程中，是有可能使用預(yù)分配空間的，因此還需要有能夠描述預(yù)分配空間大小等屬性的描述符ext4_prealloc_space。

　　下面，對(duì)各個(gè)關(guān)鍵結(jié)構(gòu)體進(jìn)行詳細(xì)的分析。

　　1. 塊請(qǐng)求描述符ext4_allocation_request

　　塊分配請(qǐng)求屬性，有請(qǐng)求描述符ext4_allocation_request來描述：

　　structext4_allocation_request {

　　/* target inode for block wereallocating */

　　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 blockto the left */

　　ext4_lblk_t lleft;

　　/* the closest logical allocated blockto the right */

　　ext4_lblk_t lright;

　　/* phys. target (a hint) */

　　ext4_fsblk_t goal;

　　/* phys. block for the closest logicalallocated block to the left */

　　ext4_fsblk_t pleft;

　　/* phys. block for the closest logicalallocated block to the right */

　　ext4_fsblk_t pright;

　　/* flags. see above EXT4_MB_HINT_* */

　　unsigned int flags;

　　};

　　這個(gè)請(qǐng)求描述符結(jié)構(gòu)體在ext4_ext_map_blocks()中初始化(注：ext4_ext_map_blocks()的作用是查找或分配指定的block塊，并完成與緩存空間的映射)。

　　具體上述信息也就一個(gè)成員變量goal值的我們分析一下，goal記錄是物理塊號(hào)，其隱含含義比較重要：goal雖然只是記錄物理塊號(hào)，但是這個(gè)物理塊號(hào)的選擇可以很大程度的是文件保證locality特性及其物理地址連續(xù)性。

　　goal是由函數(shù)ext4_ext_find_goal()來定義：

　　static ext4_fsblk_t ext4_ext_find_goal(struct inode*inode,

　　struct ext4_ext_path *path,

　　ext4_lblk_t block)

　　{

　　if(path) {

　　intdepth = path->p_depth;

　　structext4_extent *ex;

　　/*

　　* Try to predict block placement assuming thatwe are

　　* filling in a file which will eventually be

　　* non-sparse --- i.e., in the case of libbfdwriting

　　* an ELF object sections out-of-order but in away

　　* the eventually results in a contiguousobject or

　　* executable file, or some database extendinga table

　　* space file. However, this is actually somewhat

　　* non-ideal if we are writing a sparse filesuch as

　　* qemu or KVM writing a raw image file that isgoing

　　* to stay fairly sparse, since it will end up

　　* fragmenting the file systems free space. Maybe we

　　* should have some hueristics or some way toallow

　　* userspace to pass a hint to file system,

　　* especially if the latter case turns out tobe

　　* common.

　　*/

　　ex= path[depth].p_ext;

　　if(ex) {

　　ext4_fsblk_text_pblk = ext4_ext_pblock(ex);

　　ext4_lblk_text_block = le32_to_cpu(ex->ee_block);

　　if(block > ext_block)

　　returnext_pblk + (block - ext_block);

　　else

　　returnext_pblk - (ext_block - block);

　　}

　　/*it looks like index is empty;

　　* try to find starting block from index itself*/

　　if(path[depth].p_bh)

　　returnpath[depth].p_bh->b_blocknr;

　　}

　　/*OK. use inodes group */

　　returnext4_inode_to_goal_block(inode);

　　}

　　細(xì)細(xì)分析這段代碼，如果從根目錄到指定邏輯塊的path存在，那么就需要根據(jù)path來計(jì)算目標(biāo)物理塊的地址。

　　(1) Path的終點(diǎn)若是dataextent，則說明該path是從根到葉子的。當(dāng)請(qǐng)求block號(hào)大于path葉子extent的起始邏輯塊號(hào)ext_block (對(duì)應(yīng)物理塊號(hào)為pblk)，其邏輯塊的距離為(block-ext_block)，為在最可能上保證對(duì)應(yīng)物理地址的連續(xù)性;只需返回與pblk+(block-ext_block)物理塊號(hào)最接近的空閑物理塊即可;而對(duì)于請(qǐng)求block號(hào)小于extent的起始邏輯塊號(hào)ext_block的情況，只需盡最可能以pblk-( ext_block -block)物理塊號(hào)為目標(biāo)尋找與其物理地址最接近的空閑物理塊即可。因此，我們指定goal分別為pblk+(block-ext_block)和pblk-(block-ext_block)。

　　(2) 而如果path存在，卻沒有葉子，那則么辦，很簡(jiǎn)單，我們只需要將goal物理塊號(hào)指定為最后一個(gè)的extent block對(duì)應(yīng)的物理塊號(hào)既可。

　　(3) 還有一種情況，沒有給出path。個(gè)人認(rèn)為，這種場(chǎng)景即inode剛create的情況。有專門的ext4_inode_to_goal_block()來實(shí)現(xiàn)：

　　ext4_fsblk_t ext4_inode_to_goal_block(struct inode*inode)

　　{

　　structext4_inode_info *ei = EXT4_I(inode);

　　ext4_group_tblock_group;

　　ext4_grpblk_tcolour;

　　intflex_size = ext4_flex_bg_size(EXT4_SB(inode->i_sb));

　　ext4_fsblk_tbg_start;

　　ext4_fsblk_tlast_block;

　　block_group= ei->i_block_group;

　　if(flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) {

　　/*

　　* If there are at leastEXT4_FLEX_SIZE_DIR_ALLOC_SCHEME

　　* block groups per flexgroup, reserve thefirst block

　　* group for directories and special files. Regular

　　* files will start at the second blockgroup. This

　　* tends to speed up directory access andimproves

　　* fsck times.

　　*/

　　block_group&= ~(flex_size-1);

　　if(S_ISREG(inode->i_mode))

　　block_group++;

　　}

　　bg_start= ext4_group_first_block_no(inode->i_sb, block_group);

　　last_block= ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;

　　/*

　　* If we are doing delayed allocation, we dontneed take

　　* colour into account.

　　*/

　　if(test_opt(inode->i_sb, DELALLOC))

　　returnbg_start;

　　if(bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)

　　colour= (current->pid % 16) *

　　(EXT4_BLOCKS_PER_GROUP(inode->i_sb)/ 16);

　　else

　　colour= (current->pid % 16) * ((last_block - bg_start) / 16);

　　returnbg_start + colour;

　　}

　　其思想是：如果flex_size至少有EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME個(gè)block groups，則定義inode所在flex_group的第二個(gè)block group的首個(gè)可用block為起始物理塊號(hào)bg_block。

　　當(dāng)然，如果該flex_group的所有文件都以bg_block為goal的，肯定會(huì)產(chǎn)生競(jìng)爭(zhēng)，所以增加color的作用，目的就是加入一個(gè)隨機(jī)值，降低可能帶來的競(jìng)爭(zhēng)。

　　因此,最后這種情況的goal會(huì)選擇inode所在flex_group中某個(gè)隨機(jī)值。

　　【說明：如果flex_size只有不小于EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME，則才有可能將flex_group中第一個(gè)group分離出來，用于專門存放directories和一些特殊文件，普通文件從第二個(gè)group中分配，該特可以加速directory的訪問及fsync效率。】

　　2. 分配行為描述符ext4_allocation_contex

　　在分配過程中，為了更好執(zhí)行分配，記錄一些信息，需要對(duì)分配行為進(jìn)行描述，就有結(jié)構(gòu)體ext4_allocation_contex：

　　struct ext4_allocation_context{

　　struct inode *ac_inode;

　　struct super_block *ac_sb;

　　/* original request */

　　struct ext4_free_extent ac_o_ex;

　　/* goal request (normalized ac_o_ex) */

　　struct ext4_free_extent ac_g_ex;

　　/* the best found extent */

　　struct ext4_free_extent ac_b_ex;

　　/* copy of the best found extent takenbefore preallocation efforts */

　　struct ext4_free_extent ac_f_ex;

　　__u16 ac_groups_scanned;

　　__u16 ac_found;

　　__u16 ac_tail;

　　__u16 ac_buddy;

　　__u16 ac_flags; /* allocation hints */

　　__u8 ac_status;

　　__u8 ac_criteria;

　　__u8 ac_2order; /* if request is to allocate 2^N blocks and

　　* N > 0, the field stores N, otherwise 0 */

　　__u8 ac_op; /* operation, for history only */

　　struct page *ac_bitmap_page;

　　struct page *ac_buddy_page;

　　struct ext4_prealloc_space *ac_pa;

　　struct ext4_locality_group *ac_lg;

　　};

　　這個(gè)數(shù)據(jù)結(jié)構(gòu)用來描述分配上下文的屬性?；诮Y(jié)構(gòu)體ext4_allocation_request，由函數(shù)ext4_mb_initialize_context()進(jìn)行初始化。

　　ext4_mb_initialize_context()主要工作: 利用請(qǐng)求描述符的信息初始化ac->ac_o_ex:申請(qǐng)的邏輯塊號(hào)fe_logical、goal所在的group，goal的cluster號(hào)(暫時(shí)理解為物理塊號(hào));然后將ac_g_ex 賦值為ac_o_ex。

　　ext4_mb_normalize_request()會(huì)對(duì)ext4_allocation_contex結(jié)構(gòu)體進(jìn)行normalization：

　　1.計(jì)算file的大小size應(yīng)該是i_size_read(ac->ac_inode)和(offset+請(qǐng)求長(zhǎng)度)中的大值，其中offset是有指定block轉(zhuǎn)化而來。

　　2. 根據(jù)已定的算法估算文件可能的大小;

　　#define NRL_CHECK_SIZE(req, size, max, chunk_size)

　　(req<= (size) || max <= (chunk_size))

　　/*first, try to predict filesize */

　　/*XXX: should this table be tunable? */

　　start_off= 0;

　　if(size <= 16 * 1024) {

　　size= 16 * 1024;

　　}else if (size <= 32 * 1024) {

　　size= 32 * 1024;

　　}else if (size <= 64 * 1024) {

　　size= 64 * 1024;

　　}else if (size <= 128 * 1024) {

　　size= 128 * 1024;

　　}else if (size <= 256 * 1024) {

　　size= 256 * 1024;

　　}else if (size <= 512 * 1024) {

　　size= 512 * 1024;

　　}else if (size <= 1024 * 1024) {

　　size= 1024 * 1024;

　　}else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {

　　start_off= ((loff_t)ac->ac_o_ex.fe_logical >>

　　(21- bsbits)) << 21;

　　size= 2 * 1024 * 1024;

　　}else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {

　　start_off= ((loff_t)ac->ac_o_ex.fe_logical >>

　　(22- bsbits)) << 22;

　　size= 4 * 1024 * 1024;

　　}else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,

　　(8<<20)>>bsbits,max, 8 * 1024)) {

　　start_off= ((loff_t)ac->ac_o_ex.fe_logical >>

　　(23- bsbits)) << 23;

　　size= 8 * 1024 * 1024;

　　}else {

　　start_off= (loff_t)ac->ac_o_ex.fe_logical << bsbits;

　　size =ac->ac_o_ex.fe_len << bsbits;

　　}

　　size= size >> bsbits;

　　start= start_off >> bsbits;

　　由此可見，預(yù)估文件大小之后得到的size和start肯定比原來的要大一些。

　　3. check一下，是否覆蓋了已有的prealloc空間。(如果覆蓋，那就BUG);

　　4. 更新ac_g_ex：根據(jù)(2)中size和start更新ac_g_ex;

　　ac->ac_g_ex.fe_logical= start;

　　ac->ac_g_ex.fe_len= EXT4_NUM_B2C(sbi, size);

　　由上可見，通過ext4_mb_normalize_request()函數(shù)主要更新了ac->ac_g_ex成員。

　　而ac->ac_b_ex是在ext4_mb_regular_allocator()函數(shù)初始化的，其表示可以分配的最佳的extent;隱含意思，就是就按這么分配。

　　而ac-> ac_f_ex是在prealloc空間初始化之前保留ac_b_ex的副本，在ext4_mb_new_inode_pa()或ext4_mb_new_group_pa()中定義。

　　3. 預(yù)分配空間描述符ext4_allocation_contex

　　描述預(yù)分配空間大小等屬性的描述符ext4_prealloc_space：

　　structext4_prealloc_space {

　　struct list_head pa_inode_list;

　　struct list_head pa_group_list;

　　union {

　　struct list_head pa_tmp_list;

　　struct rcu_head pa_rcu;

　　} u;

　　spinlock_t pa_lock;

　　atomic_t pa_count;

　　unsigned pa_deleted;

　　ext4_fsblk_t pa_pstart; /*phys. block */

　　ext4_lblk_t pa_lstart; /*log. block */

　　ext4_grpblk_t pa_len; /*len of preallocated chunk */

　　ext4_grpblk_t pa_free; /* howmany blocks are free */

　　unsigned short pa_type; /* pa type.inode or group */

　　spinlock_t *pa_obj_lock;

　　struct inode *pa_inode; /*hack, for history only */

　　};

　　其中有四個(gè)結(jié)構(gòu)體非常重要：

　　pa_lstart -> prealloc 空間的起始邏輯地址(對(duì)文件而言);

　　pa_pstart -> prealloc 空間的起始物理地址;

　　pa_len -> prealloc 空間的長(zhǎng)度;

　　pa_free -> prealloc 空間的可用長(zhǎng)度;

　　這個(gè)結(jié)構(gòu)體是在函數(shù)ext4_mb_new_inode_pa()或ext4_mb_new_group_pa()中初始化。

　　暫時(shí)就分析這么幾個(gè)結(jié)構(gòu)體吧。

　　作者：Younger Liu，

　　本作品采用知識(shí)共享署名-非商業(yè)性使用-相同方式共享 3.0 未本地化版本許可協(xié)議進(jìn)行許可。