ext2 块预留机制源代码分析

文件:	ext2 块预留机制源代码分析.pdf
大小:	104KB
下载:	下载

前言

终于可以写源代码分析这一部分了。前边的知识准备工作比较难弄，特别是画图。

Ext2分配一个新的磁盘块的执行流程大概是这样：

ext2_get_block

    →ext2_get_blocks

        →ext2_block_to_path

        →ext2_get_branch

        →ext2_find_goal

        →ext2_blks_to_allocate

        →ext2_alloc_branch

            →ext2_alloc_blocks

                →ext2_new_blocks

                    →ext2_get_group_desc

                    →read_block_bitmap

                    →ext2_try_to_allocate_with_rsv

                        →ext2_try_to_allocate

        →ext2_splice_branch

ext2磁盘块分配过程，《Linux内核源代码情景分析》第六章中已经分析的很详细了，在此不罗嗦了。但是因为情景分析是基于2.4.0内核的，那时候ext2还没有块预留机制，所以本文的重点在块预留机制，主要是ext2_try_to_allocate_with_rsv这个函数。

内核版本：2.6.35

一、关于块预留机制的几个相关函数的解释

下述函数都在fs/ext2/balloc.c文件中。

1、 ext2_rsv_window_add将一个预留窗口节点添加到红黑树上

340 void ext2_rsv_window_add(struct super_block *sb,struct ext2_reserve_window_node *rsv)

参数说明：

sb:所在文件系统的超级块结构

rsv:要往红黑树上添加的预留窗口节点

功能：

保存预留信息的红黑树是动态创建的。文件系统刚挂载时，树只有一个根节点，随着块的不断分配，新的预留窗口会不断加入到这棵红黑树上，使它生根发芽，不断壮大。

2、 rsv_window_remove将一个预留窗口节点从红黑树上移除

379 static void rsv_window_remove(struct super_block *sb,

struct ext2_reserve_window_node *rsv)

参数说明：

sb:所在文件系统的超级块结构

rsv:要从红黑树上删除的预留窗口节点

功能：

有生有死，福祸相依。当不需要某个预留窗口时，可以将预留窗口节点从树上移除。比如说当文件关闭时，肯定不再需要预留窗口了。

3、search_reserve_window搜索一个包含磁盘块goal的预留窗口节点

301 static struct ext2_reserve_window_node *search_reserve_window(struct rb_root *root, ext2_fsblk_t goal)

参数说明：

root:红黑树的根节点

goal:要搜索的目标磁盘块号

功能：

搜索包含goal的预留窗口节点，如果没有节点包含goal，则返回goal前面的节点。如果没有找到预留窗口或者所有的窗口都开始于goal之后，返回NULL。

4、 goal_in_my_reservation检查goal是否在预留窗口rsv中

274 static int

275 goal_in_my_reservation(struct ext2_reserve_window *rsv,

ext2_grpblk_t grp_goal,

unsigned int group,

struct super_block * sb)

参数说明：

rsv:当前的预留窗口节点

grp_goal:相对于块组号为group的块组开头的目标块号，就是说这个块号是相对于一个块组的。如果一个块组有1024个块，则grp_goal可以为0到1023。

group:块组号，我们要在这个块组中查找

sb:所在文件系统的超级块结构

功能：

测试goal是否位于预留节点rsv中。

如果goal在预留窗口之外，返回0；

如果goal在预留窗口内，返回1。

5、 find_next_reservable_window查找一块可预留的空间，修改相应的预留窗口节点，并加入红黑树

785 static int find_next_reservable_window( struct ext2_reserve_window_node *search_head,

struct ext2_reserve_window_node *my_rsv,

struct super_block * sb,

ext2_fsblk_t start_block,

ext2_fsblk_t last_block)

参数说明：

search_head:搜索的起点，不包括该节点

my_rsv:一个旧的预留窗口节点，已从红黑树中移除了，本函数会修改其中的预留窗口的开始、结束值，并把该节点重新加入红黑树。

sb:所在文件系统的超级块结构

start_block:搜索开始的块号。因为搜索虽然是在一个块组中进行的，但这里的块号是相对于文件系统开头。

last_block:搜索结束的块号。因为搜索虽然是在一个块组中进行的，但这里的块号是相对于文件系统开头。

功能：

本函数尝试从预留窗口节点search_head开始，在一个块组的子空间[start_block, last_block]中查找一个大小为rsv_goal_size的新的预留窗口。若找到，则修改旧的预留窗口节点my_rsv，并将my_rsv加入红黑树。所谓新的，就是新创建的这个预留窗口不能与已经存在的窗口重叠（因为已存在的预留窗口属于别的文件，不能鸠占鹊巢啊）。

6、bitmap_search_next_usable_block在磁盘块位图中查找下一个空闲磁盘块的块号

586 static ext2_grpblk_t bitmap_search_next_usable_block(ext2_grpblk_t start,

struct buffer_head *bh,

ext2_grpblk_t maxblocks)

参数说明：

start:从哪个位开始查找

bh:指向一个磁盘块位图

maxblocks:最多查找maxblocks个位

功能：

在一个磁盘块位图中，从start位开始查找第一个为0的位（即空闲位），最多搜索maxblocks个位。

7、alloc_new_reservation分配一个预留窗口节点

907 static int alloc_new_reservation(struct ext2_reserve_window_node *my_rsv,

ext2_grpblk_t grp_goal,

struct super_block *sb,

unsigned int group,

struct buffer_head *bitmap_bh)

参数说明：

my_rsv:一个旧的预留窗口节点， 因为它不包含grp_goal，故需要新创建一个预留窗口节点。

grp_goal:相对于块组开头的块号

sb:所在文件系统的超级块结构

group:当前块组号

bitmap_bh:当前块组位图

功能：

在块组号为group的块组中，从块号grp_goal开始，查找一块可预留的空间，以之创建一个新的块组，并加入红黑树。

什么叫可预留的空间，就是这块空间不属于任何一个已存在的预留窗口。

当一个文件发现自己的预留窗口不包含启发值goal之后，它就需要为自己重新分配一个预留窗口了。新创建的预留窗口如果能包含goal，那再好不过了。否则，将goal设为-1，使这个启发值不起作用。

8、 try_to_extend_reservation

1049 static void try_to_extend_reservation(struct ext2_reserve_window_node *my_rsv,

1050 struct super_block *sb, int size)

参数说明：

my_rsv:试图扩展的预留窗口节点

sb:所在文件系统的超级块结构

size:试图增加的大小

功能：

本函数试图扩展预留窗口my_rsv，增加size个块。

二、分配磁盘块时几种典型情况分析

注意：

goal是个启发值，是通过ext2_find_goal()函数得到的“被认为是极有可能本次要分配的块”。

1、如果本文件没有预留窗口，创建并初始化一个。

ext2_get_blocks（）函数

677 if (S_ISREG(inode->i_mode) && (!ei->i_block_alloc_info))

678 ext2_init_block_alloc_info(inode);

2、如果goal在inode的预留窗口中，并且预留窗口空间足够大，则在预留窗口中分配。

3、如果goal在inode的预留窗口中，但是预留窗口空间不足，则通过try_to_extend_reservation（）扩展预留窗口。

4、如果goal不在inode的预留窗口，则通过alloc_new_reservation（）为之分配一个新的预留窗口。

5、如果inode的预留窗口已不在goal所在的块组中，则直接在块组中分配，本次分配不考虑预留窗口。

6、如果在goal所在的块组中无法分配新块，则尝试下一个块组。

三、ext2_try_to_allocate_with_rsv()函数分析

1083 * This is the main function used to allocate a new block and its reservation

1084 * window.

这是分配一个新的磁盘块和预留窗口的主要函数。

1085 *

1086 * Each time when a new block allocation is need, first try to allocate from

1087 * its own reservation. If it does not have a reservation window, instead of

1088 * looking for a free bit on bitmap first, then look up the reservation list to

1089 * see if it is inside somebody else's reservation window, we try to allocate a

1090 * reservation window for it starting from the goal first. Then do the block

1091 * allocation within the reservation window.

每次需要分配一个新的磁盘块时，首先尝试从文件的预留窗口中进行分配。如果文件尚未有预留窗口，我们首先为它分配一个从块号goal开始的预留窗口，然后在此预留窗口中进行磁盘块分配，而不是在磁盘块位图上查找空闲的磁盘块，然后再判断该磁盘块是否已属于别的文件的预留窗口。

1092 *

1093 * This will avoid keeping on searching the reservation list again and

1094 * again when somebody is looking for a free block (without

1095 * reservation), and there are lots of free blocks, but they are all

1096 * being reserved.

这样，如果有很多空闲块，但是他们都被预留了，上述方法能够避免查找空闲块时在预留链表（现在已经是红黑树了）中反复搜索。

1097 *

1098 * We use a red-black tree for the per-filesystem reservation list.

现在已经是红黑树了，刚开始采用的是预留链表，是个排序链表。

1100 static ext2_grpblk_t

1101 ext2_try_to_allocate_with_rsv(struct super_block *sb, unsigned int group,

1102 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,

1103 struct ext2_reserve_window_node * my_rsv,

1104 unsigned long *count)

1105 {

1106     ext2_fsblk_t group_first_block, group_last_block;

1107     ext2_grpblk_t ret = 0;

1108     unsigned long num = *count;

1109

1110     /*

1111      * we don't deal with reservation when

1112      * filesystem is mounted without reservation

1113      * or the file is not a regular file

1114      * or last attempt to allocate a block with reservation turned on failed

1115      */

1116      if (my_rsv == NULL) {

              // 如果预留窗口为空，则本次分配不使用预留窗口机制。

1117          return ext2_try_to_allocate(sb, group, bitmap_bh,

1118                                      grp_goal, count, NULL);

1119      }

1120     /*

1121      * grp_goal is a group relative block number (if there is a goal)

1122      * 0 <= grp_goal < EXT2_BLOCKS_PER_GROUP(sb)

1123      * first block is a filesystem wide block number

1124      * first block is the block number of the first block in this group

1125      */

         /* grp_goal是相对于块组开头的相对块号，

          * 0 <= grp_goal < EXT2_BLOCKS_PER_GROUP(sb)

          * group_first_block和group_last_block是相对于整个文件系统开头的块号

          */

1126      group_first_block = ext2_group_first_block_no(sb, group);

1127      group_last_block = group_first_block + (EXT2_BLOCKS_PER_GROUP(sb) – 1);

1129      /*

1130       * Basically we will allocate a new block from inode's reservation

1131       * window.

1132       *

1133       * We need to allocate a new reservation window, if:

1134       * a) inode does not have a reservation window; or

1135       * b) last attempt to allocate a block from existing reservation

1136       * failed; or

1137       * c) we come here with a goal and with a reservation window

1138       *

1139       * We do not need to allocate a new reservation window if we come here

1140       * at the beginning with a goal and the goal is inside the window, or

1141       * we don't have a goal but already have a reservation window.

1142       * then we could go to allocate from the reservation window directly.

1143       */

          /* 原则上说，我们总是从inode的预留窗口中分配新的磁盘块。

           * 下列情况下我们需要分配新的预留窗口：

           * 1、inode目前没有预留窗口；

           * 2、上一次从inode现存预留窗口中分配磁盘块失败了；

           * 3、 （原注释可能过期了）grp_goal不在预留窗口中。

           */

1144       while (1) {

1145           if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||

1146               !goal_in_my_reservation(&my_rsv->rsv_window,

1147                                       grp_goal, group, sb)) {

                    // 我们需要新分配一个预留窗口

1148                if (my_rsv->rsv_goal_size < *count)

1149                    my_rsv->rsv_goal_size = *count;

1150                ret = alloc_new_reservation(my_rsv, grp_goal, sb,

1151                                            group, bitmap_bh);

1152                if (ret < 0)

1153                   break; /* failed */

1154

1155                if (!goal_in_my_reservation(&my_rsv->rsv_window,

1156                                            grp_goal, group, sb))

1157                    grp_goal = -1;

1158                } else if (grp_goal >= 0) {

1159                    int curr = my_rsv->rsv_end -

1159                    int curr = my_rsv->rsv_end -

1160                               (grp_goal + group_first_block) + 1;

1161

1162                    if (curr < *count)

1163                        try_to_extend_reservation(my_rsv, sb,

1164                                                  *count – curr);

                            // 如果原来的预留窗口太小，扩展之。

1165                }

1166

1167                if ((my_rsv->rsv_start > group_last_block) ||

1168                   (my_rsv->rsv_end < group_first_block)) {

1169                   rsv_window_dump(&EXT2_SB(sb)->s_rsv_window_root, 1);

1170                   BUG();

1171                }

                    // 从预留窗口中分配磁盘块，详见下文详析

1172                ret = ext2_try_to_allocate(sb, group, bitmap_bh, grp_goal,

1173                                           &num, &my_rsv->rsv_window);

1174                if (ret >= 0) {

1175                    my_rsv->rsv_alloc_hit += num;

1176                    *count = num;

1177                    break; /* succeed */

                        // 运行到这里，表示本次分配了num个磁盘块，成功返回。

1178                }

1179                num = *count;

                   // 运行到这里，表示本次分配尝试失败了，ret < 0，转到1145行，再分配一个新的预留窗口。

1180       }

           // 返回本次分配的磁盘块数量

1181       return ret;

1182 }

四、ext2_try_to_allocate函数分析

672 static int

673 ext2_try_to_allocate(struct super_block *sb,

                         int group,

                         struct buffer_head *bitmap_bh,

                         ext2_grpblk_t grp_goal,

                         unsigned long *count,

                         struct ext2_reserve_window *my_rsv)

参数说明：

sb:所在文件系统的超级块结构

group:块组号

bitmap_bh:块组位图

grp_goal:相对于块组开头的块号,一个分配的启发值

count:申请分配的磁盘块数

my_rsv:申请磁盘块的inode对应的预留窗口节点

功能：

本函数尝试在块组group的一个区间内分配若干个磁盘块。

659 * Attempt to allocate blocks within a give range. Set the range of allocation

660 * first, then find the first free bit(s) from the bitmap (within the range),

661 * and at last, allocate the blocks by claiming the found free bit as allocated.

662 *

尝试在给定区间内分配若干个磁盘块。

首先设置分配的区间，（预留窗口在此发挥作用了）

然后在区间内查找第一个空闲块，

最后，将位图相应位置1，表示该块已被分配。

663 * To set the range of this allocation:

664 * if there is a reservation window, only try to allocate block(s)

665 * from the file's own reservation window;

666 * Otherwise, the allocation range starts from the give goal block,

667 * ends at the block group's last block.

668 *

如何设置分配区间：

1、如果预留窗口存在，my_rsv != NULL，则只尝试从预留窗口中分配磁盘块。

2、否则，预留窗口为空，则设置区间的起点是 grp_goal，终点是块组最后一个块。

669 * If we failed to allocate the desired block then we may end up crossing to a

670 * new bitmap.

671 */

672 static int

673 ext2_try_to_allocate(struct super_block *sb, int group,

674 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,

675 unsigned long *count,

676 struct ext2_reserve_window *my_rsv)

677 {

678     ext2_fsblk_t group_first_block;

679     ext2_grpblk_t start, end;

680     unsigned long num = 0;

681

682     /* we do allocation within the reservation window if we have a window */

683     if (my_rsv) {

            // 根据预留窗口设置分配区间

684         group_first_block = ext2_group_first_block_no(sb, group);

685         if (my_rsv->_rsv_start >= group_first_block)

686             start = my_rsv->_rsv_start - group_first_block;

687         else

688             /* reservation window cross group boundary */

689             start = 0;

690         end = my_rsv->_rsv_end - group_first_block + 1;

691         if (end > EXT2_BLOCKS_PER_GROUP(sb))

692             /* reservation window crosses group boundary */

693             end = EXT2_BLOCKS_PER_GROUP(sb);

694         if ((start <= grp_goal) && (grp_goal < end))

695             start = grp_goal;

696         else

697             grp_goal = -1;

698         } else {

                // 没有预留窗口，

699                 if (grp_goal > 0)

700                     start = grp_goal;

701                 else

702                     start = 0;

703         end = EXT2_BLOCKS_PER_GROUP(sb);

704    }

705

706    BUG_ON(start > EXT2_BLOCKS_PER_GROUP(sb));

707

708 repeat:

709     if (grp_goal < 0) {

            // grp_goal < 0表示没有设置搜索启发值，

            // 则我们从磁盘块位图上找一个空闲的块，作为启发值。

710         grp_goal = find_next_usable_block(start, bitmap_bh, end);

711         if (grp_goal < 0)

712             goto fail_access;

713         if (!my_rsv) {

714             int i;

715

716             for (i = 0; i < 7 && grp_goal > start &&

717                 !ext2_test_bit(grp_goal - 1,

718                 bitmap_bh->b_data);

719                 i++, grp_goal--)

720                 ;

721         }

722     }

723     start = grp_goal;

724

725     if (ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group), grp_goal,

726         bitmap_bh->b_data)) {

727         /*

728          * The block was allocated by another thread, or it was

729          * allocated and then freed by another thread

             * ext2_set_bit_atomic()返回1，表示该磁盘块已被其他线程分配了！

             * 那就继续尝试分配下一个磁盘块

730          */

731          start++;

732          grp_goal++;

733          if (start >= end)

734              goto fail_access;

735          goto repeat;

736      }

737      num++;

738      grp_goal++;

         // 顺手牵羊，不如一次多分配几个连续的磁盘块！

         // 尝试分配其后的块！

739      while (num < *count && grp_goal < end

740             && !ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group),

741          grp_goal, bitmap_bh->b_data)) {

742          num++;

743          grp_goal++;

744      }

745      *count = num;

746      return grp_goal - num;

747 fail_access:

748      *count = num;

749      return -1;

750 }