• 标题
  • 简介
  • 内容
  • 作者
  • 全部
推荐 最新 电子工程 机器人 物联网 电子工程 机器人 物联网
ext4_extent 算法设计真巧妙
Linux开发架构之路 2024-11-22

内核版本3.10.96

一、ext4 extent示意图演示

1 ext4 extent由来介绍

ext4之前的文件系统(ext2、ext3)由文件逻辑地址寻址到物理块地址，采用的是直接+间接寻址的方式，间接寻址又细化为1级间接寻址、2级间接寻址、3级间接寻址。


按照我的理解画了如上示意图，最左边的是ext4_inode的i_block[15]数组，它的前12个成员保存是保存文件数据的物理块号。第13个成员即i_block12，保存的是个索引号(也是个物理块号)，根据它找到的物理块里的4K数据才是保存文件数据的物理块号，这就是1级间接寻址，或者叫1级间接映射。第14个成员即i_block13，保存的是个索引号，根据它找到的物理块，该物理块里边的4K数据还是索引号。根据这个索引号找到物理块，里边的4K数据才是保存文件数据的物理块号，这就是2级间接寻址，或者叫2级间接映射。第15个成员即i_block14，保存的是个索引号，它指向的物理块里还是索引数据，这个索引数据指向的物理块里保存的数据还是索引数据，这个索引数据指向的物理块里保存的数据才是保存文件数据的物理块号，这就是3级间接寻址，或者叫3级间接映射。

ext2/ext3 这种直接+间接的寻址方式，缺点比较多，比如浪费物理块，大文件时寻址浪费磁盘性能和效率低，还有说容易碎片化。改良方案是引入extent，由一个extent结构就可以描述大文件的逻辑地址和物理地址的映射关系，可以节省磁盘空间，提升寻址性能，还能减少碎片化。

2 ext4 extent简单举例演示

extent结构内核用” struct ext4_extent”表示，如下所示： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_extent { //起始逻辑块地址 __le32  ee_block; //逻辑块映射的连续物理块个数 __le16  ee_len;  //由ee_start_hi和ee_start_lo一起计算出起始逻辑块地址映射的起始物理块地址 __le16  ee_start_hi;  __le32  ee_start_lo; };

成员ee_block是起始逻辑块地址，成员ee_len是映射的连续物理块个数，成员ee_start_hi和ee_start_lo一起计算出起始逻辑块地址映射的起始物理块地址，我们这里假设这里计算出来的起始物理块地址是p_block。则这个ext4_extent结构表示文件逻辑块地址ee_block~(ee_block+ee_len)与物理块地址范围p_block~(p_block+ee_len)构成映射。进一步说，通过ext4_extent结构我们就知道了文件的逻辑块地址ee_block~(ee_block+ee_len)映射的物理块号，文件逻辑块地址ee_block~(ee_block+ee_len)与物理块地址范围p_block~(p_block+ee_len)一一对应。

一个ext4_extent可以表示文件一段逻辑块地址与物理块地址的映射关系，一个庞大的文件一般会有有多段逻辑块，此时需要用多个ext4_extent结构表示每段逻辑块映射的物理块。当有非常多ext4_extent结构时，太乱了，需要想办法把这么多的ext4_extent结构组织起来！内核用的是B+树，我们这里称为ext4 extent B+树，如下演示了这个B+树：


演示是3层B+树，第1层是根节点、第2层索引节点、第3层是叶子节点。B+树的根节点比较好理解，叶子节点主要保存数据结构就是ext4_extent。索引节点是什么？索引节点像是起着指引作用，根节点通过索引节点可以找到叶子节点。这里出现了两个新的数据结构ext4_extent_header和ext4_extent_idx。ext4_extent_header是头部结构，主要保存叶子节点或者索引节点的统计信息，ext4_extent_idx主要包含ext4_extent的索引信息，通过ext4_extent_idx可以找到ext4_extent结构。如下是两个结构体的定义： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



//索引节点或叶子节点头结构体信息struct ext4_extent_header { __le16 eh_magic; //索引节点或叶子节点目前有效的ext4_extent_idx或ext4_extent个数 __le16 eh_entries; //索引节点或叶子节点最多可以保存多少个ext4_extent_idx或ext4_extent __le16 eh_max; //当前叶子节点或者索引节点所处B+数的层数 __le16 eh_depth; __le32 eh_generation;=};struct ext4_extent_idx { //起始逻辑块地址 __le32 ei_block;  //由ei_leaf_lo和ei_leaf_hi组成起始逻辑块地址对应的物理块地址 __le32 ei_leaf_lo; __le16 ei_leaf_hi; __u16 ei_unused;};

ext4 extent B+树第一层的根节点由1个ext4_extent_header+ 4个ext4_extent_idx组成，根节点的ext4_extent_idx指向第2层的叶子节点。B+树第2层中，索引节点由1个ext4_extent_header+N个ext4_extent_idx组成，第2层索引节点的ext4_extent_idx指向了第3层的叶子节点。B+树第3层中，叶子节点由1个ext4_extent_header+N个ext4_extent组成。

需要说明，根节点最对可以有4个ext4_extent_idx，它们每个都指向1个第2层的索引节点，就是说第2层最多有4个索引节点，为了演示方便示意图中只画了两个索引节点。第2层的索引节点中的每个ext4_extent_idx都指向一个第3层的叶子节点，为了演示方便示意图中只画了3个叶子节点。

ext4 extent B+树最核心的作用是通过它可以找到文件逻辑块地址与物理块地址的映射关系，我们可以通过ext4 extent B+树可以找到文件逻辑块地址映射的物理块地址，下边我们做个演示。先把上文的示意图简单改造下，标记上根节点/索引节点的ext4_extent_idx和叶子节点的ext4_extent对应的逻辑块地址。


假设我们想知道文件逻辑地址0映射的物理块地址是什么？首先找到根节点的第一个ext4_extent_idx，它的起始逻辑块号是0。然后找到它指向的索引节点，再找到该索引节点的第一个ext4_extent_idx，它的起始逻辑块号也是0。继续，找到当前索引节点第一个ext4_extent_idx指向的叶子节点。因为该叶子节点的第一个ext4_extent对应的逻辑块地址范围是0~10，我们要查找逻辑块地址0正好在它的逻辑块地址范围内。好的，每一个有效的ext4_extent数据结构都保存了其代表的逻辑块地址映射的物理块地址，理所应当，通过逻辑块地址范围0~10这个ext4_extent就可以直到逻辑块地址0映射的物理块地址。

提醒一下，只有叶子节点或者根节点的ext4_extent才会保存文件逻辑块地址与物理块地址的映射关系，索引节点或者根节点的ext4_extent_idx只保存了它代表的起始逻辑块地址和起始物理块地址，ext4_extent_idx只是起了一个索引作用，只是通过ext4_extent_idx的起始逻辑块地址找到它指向的ext4_extent。

再说明一下，ext4文件系统的一个物理块经测试是4K大小，一个内存page也是4K大小，内核里文件的逻辑块看代码也是以4K大小为单位，如下示意图演示了这个关系：


后续我们介绍文件逻辑块地址与物理块地址时，默认逻辑块和物理块都是以4K大小为单位。

3 简单演示ext4  extent B+树的形成过程

第2节的示意图演示了文件逻辑块地址与物理块地址的关系，ext4  extent B+树有根节点、索引节点、叶子节点。刚开始读写文件时，文件逻辑块地址和物理块地址映射关系比较简单，此时只是把保存文件逻辑块地址和物理块地址映射关系的ext4_extent存储到ext4  extent B+的根节点。后续随着文件逻辑块地址和物理块地址映射关系越来越复杂，需要的ext4_extent越来越多，便会出现叶子节点、索引节点。我们下边演示这个过程：

3.1 根节点4个extent插入过程

最开始，ext4  extent B+树是空的


好的，现在经过复杂的查找，我们知道了文件逻辑块地址0~10映射物理块地址是10000~10010(文件逻辑块地址映射的物理块地址是连续的)，我们把这个映射的关系保存到第一个ext4_extent结构，如下简单演示一下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_extent { __le32 ee_block = 0 __le16 ee_len = 10 //由ee_start_hi和ee_start_lo一起计算出起始物理块地址是10000 __le16 ee_start_hi;  __le32 ee_start_lo; };

好的，现在我们把这个ext4_extent插入到ext4  extent B+树，如下所示：


ext4  extent B+树的第一个位置保存了逻辑地址范围是0~10的ext4_extent。图中标出了ext4_extent代表的逻辑地址是0~10范围，没有标出映射的物理块地址。

好的，随着文件读写，文件逻辑块地址与物理块地址的映射关系越来越复杂，现在又多了3段映射关系，如下所示：

  • 逻辑块地址 20~30 映射的物理块地址 12000~12010

  • 逻辑块地址 50~60 映射的物理块地址 13000~13010

  • 逻辑块地址 80~90 映射的物理块地址 18000~12010

好的，现在当然需要3个ext4_extent保存这3段逻辑块地址与物理块地址的映射关系，并插入到ext4  extent B+树，全插入后如下所示：

示意图每个ext4_extent下边的数字都是他们代表的逻辑块地址范围，ext4_extent上边的a0、a20、a50、a80是我对他们的编号，为了后续叙述方便，字母a后边的数字是他们的起始逻辑块号，后边叙述中也经常用到。

3.2 根节点下的叶子节点extent插入过程

继续，现在来了一个新的文件逻辑块地址与物理块地址的映射：逻辑块地址100~130映射了物理块地址19000~19010，于是分配一个新的ext4_extent结构保存这个映射关系，但是把把这个ext4_extent插入ext4  extent B+树时遇到问题了，根节点空间用完了。此时会创建一个叶子节点缓解尴尬局面，如下所示：

先把根节点原有的4个ext4_extent移动到了叶子节点前4个，然后把逻辑块地址100~130映射了物理块地址19000~19010的ext4_extent插入到叶子节点第5个ext4_extent位置。还有一个重点，根节点的原有的4个ext4_extent结构全清空，然后变成ext4_extent_idx。第一个ext4_extent_idx是有效的，它的起始逻辑块地址是原来该位置的ext4_extent的起始逻辑块地址(就是0)，后3个ext4_extent_idx是无效的(就是没有使用)。

这里说明一点:从这里开始，根节点、索引节点有效的ext4_extent_idx圈了红色边框，叶子节点有效的ext4_extent也圈了红色边框(根节点的第一个ext4_extent_idx和叶子节点的前5个ext4_extent)。无效的ext4_extent_idx和ext4_extent红色边框都是原始黑色的，他们都还没用用来标识逻辑地址与物理地址的映射关系。

好的，我们继续。随着继续读写文件，新的文件逻辑块地址与物理块地址映射陆续产生，因此又产生了很多新的ext4_extent，最后把叶子节点所有的的ext4_extent全占满了，叶子节点最后一个ext4_extent的逻辑块地址是280~290，如下图所示。(后续文章为了叙述方便，我们大部分情况只说明ext4_extent的逻辑块地址，不再提逻辑块地址映射的物理块地址。)


好的，现在又来了一个新的逻辑块地址与物理块地址的映射关系：逻辑块地址 300~320 映射的物理块地址 28000~28020。新建一个ext4_extent保存这个映射关系后，该怎么把ext4_extent插入ext4  extent B+树呢？此时需要先在根节点第2个ext4_extent_idx (该ext4_extent_idx此时空闲，并未使用) 位置处，创建新的ext4_extent_idx，它的起始逻辑块地址是300，编号b300。然后创建b300这个ext4_extent_idx指向的叶子节点，该叶子节点的第一个ext4_extent就保存逻辑块地址 300~320 映射与物理块地址 28000~28020的映射关系，如下所示：

根节点的第2个ext4_extent_idx起始逻辑块地址正是300(图中标号是b300)，它指向的叶子节点是新创建的，该叶子节点的第一个ext4_extent的逻辑块地址是 300~320。

好的，继续读写文件，有了新的逻辑块地址与物理块地址映射关系，把它们对应的ext4_extent添加到b300那个ext4_extent_idx指向的叶子节点，直到占满这个叶子节点，如下图所示：

继续，读写文件，再次产生新的逻辑块地址与物理块地址映射关系（逻辑块地址都大于>=600），只能把它们对应的ext4_extent添加到b300后边的ext4_extent_idx指向的叶子节点，但是这个叶子节点还没有，需要创建新的叶子节点………...下图直接来个最终演示结果，把根节点的4个ext4_extent_idx指向叶子节点的ext4_extent全占满了。

如图，根节点的这4个ext4_extent_idx编号一次是b0、b300、b500、b900。在b300指向叶子节点的ext4_extent全占满后，此时新添加的ext4_extent逻辑块地址是600~620，则创建b600指向的叶子节点，然后把逻辑块地址是600~620的ext4_extent插入到该叶子节点第一个ext4_extent位置处。后续又把逻辑块地址是680~690的ext4_extent插入到该叶子节点第2个ext4_extent位置处………. 把逻辑块地址是880~890的ext4_extent插入到该叶子节点最后一个ext4_extent位置处。

好的，b600指向的叶子节点ext4_extent也全占满了。此时来了一个新的ext4_extent，它代表的逻辑块地址是900~920，该怎么插入？老方法，创建b900指向的叶子节点，把它插入到该叶子节点第一个ext4_extent位置处。后续又把逻辑块地址是980~990的ext4_extent插入到该叶子节点第2个ext4_extent位置处………. 把逻辑块地址是1290~1290的ext4_extent插入到该叶子节点最后一个ext4_extent位置处。这个过程上边的示意图都演示了！

Ok，本小节完整介绍了根节点的4个ext4_extent_idx指向的叶子节点添加ext4_extent的过程，包括逻辑块地址与ext4_extent怎么建立联系、叶子节点的创建、叶子节点与ext4_extent_idx的关系。

3.3 根节点下索引节点的创建

这里发出疑问，上小节最后ext4 extent B+树根节点的4个ext4_extent_idx指向的叶子节点的ext4_extent全占满了(如图3.2.5所示)，如果此时向B+树添加逻辑块地址是1300~1320的ext4_extent，会发生什么？我们直接在示意图中演示

如图所示，新增了一层索引节点，把根节点的原有的4个ext4_extent_idx(b0、b300、b600、b900)移动到了该索引节点的前4个ext4_extent_idx位置处。在索引节点的第5个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处，创建新的ext4_extent_idx(编号是b1300)，令它的起始逻辑块地址是1300。接着创建b1300指向的叶子节点，最后把逻辑块地址是1300~1320的ext4_extent插入到b1300指向的叶子节点的第一个ext4_extent位置。

Ok，继续向b13000指向的叶子节点添加了ext4_extent，直到把该叶子节点的所有位置的ext4_extent全占满，如下图所示：

继续，ext4 extent B+树第2层的索引节点前5个ext4_extent_idx(b0、b300、b600、b900、b1300)指向的叶子节点的ext4_extent全占满了，此时如果向ext4 extent B+树插入逻辑块地址是1600~1620的ext4_extent该怎么办？下边的示意图演示了：

显然，就是在第2层的索引节点的第6个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处，创建新的ext4_extent_idx，它的起始逻辑块地址1600，我们给它编号b1600。然后创建b1600指向的叶子节点，把逻辑块地址是1600~1620的ext4_extent插入到该叶子节点第一个ext4_extent位置处。

接下来，继续向b1600这个ext4_extent_idx指向的叶子节点的插入ext4_extent，最后把该叶子节点所有的ext4_extent全占满了。再插入新的ext4_extent时，则在索引节点第7个ext4_extent_idx位置处(b1600后边的那个ext4_extent_idx, 该ext4_extent_idx此时空闲，并未使用)创建新的ext4_extent_idx，然后为这个新的ext4_extent_idx创建叶子节点，把新的ext4_extent插入到该叶子节点第一个ext4_extent位置处。这个过程跟前边b1300那个ext4_extent_idx指向的叶子节点的ext4_extent全占满时，向ext4 extent B+树插入逻辑块地址是1600~1620的ext4_extent的过程是类似的(图3.3.3)。

加大力度，随着不断向向ext4 extent B+树新的ext4_extent，第2层的索引节点的所有ext4_extent_idx全部被创建，这些ext4_extent_idx指向的叶子节点的ext4_extent也全占满，如下图所示：

说明一下，为了节省空间，把第2层的索引节点中b1300和b1600这两个ext4_extent_idx及其指向的叶子节点省略了，实际上索引节点的所有ext4_extent_idx都创建了，并且它们的叶子节点也都有创建。图中只显示了索引节点最后一个ext4_extent_idx，它的起始逻辑块地址是2000，标号b2000，它指向的叶子节点的ext4_extent全占满了。

继续，如果此时我们继续向ext4_extent B+树添加逻辑块地址是5000~5020的ext4_extent，怎么办？这里情况就有点特殊了，我们详细说下：第2层的索引节点的ext4_extent_idx全用完了，只能回到上一层的根节点，找到c0这ext4_extent_idx后边第2个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处，创建新的ext4_extent_idx，它的起始逻辑块地址是5000，然后创建它指向的索引节点。注意，是创建索引节点！然后在新创建的索引节点的第一个ext4_extent_idx位置处，创建新的ext4_extent_idx，令它的起始逻辑块地址是5000。这个过程用下图演示：

如图，在根节点第2个ext4_extent_idx位置处创建了起始逻辑块地市是5000的ext4_extent_idx，编号c5000。然后创建c5000这个ext4_extent_idx指向的索引节点，在该索引节点第一个ext4_extent_idx位置处创建起始逻辑块地址是5000的ext4_extent_idx，编号c5000_2。

继续，创建c5000_2这个ext4_extent_idx指向的叶子节点，并且把逻辑块地址是5000~5020的ext4_extent插入到该叶子节点第一个ext4_extent位置处，如下图所示：


继续向c5000_2这个ext4_extent_idx指向的叶子节点插入ext4_extent，直到把这个叶子节点的ext4_extent占满。然后再插入ext4_extent时，会在c5000_2后边的ext4_extent_idx位置处创建新的ext4_extent_idx，再创建该ext4_extent_idx指向的叶子节点，最后再把这个叶子节点的ext4_extent占满………..一直不停的插入ext4_extent，直到把c5000指向的索引节点上的所有ext4_extent_idx全用上，并且把这些ext4_extent_idx指向叶子节点的ext4_extent全占满，此时是如下状态：

为了画图方便，只把c5000_2和c8200这两个ext4_extent_idx指向叶子节点的ext4_extent显示了出来，其实二者之间的ext4_extent_idx指向叶子节点的ext4_extent也是被占满状态。

好的，现在演示了根节点c5000指向的索引节点被占满的情况，后续再插入ext4_extent，需要考虑向它后边的ext4_extent_idx位置处创建新的ext4_extent_idx，再创建该ext4_extent_idx指向的索引节点，再创建叶子节点，再插入新的ext4_extent………..这个过程跟图3.3.5上边的过程一致。最最后，在又插入了非常多的ext4_extent后，把目前整个ext4 extent B+树全占满了，如下图所示


显示空间有限，部分ext4_extent_idx和ext4_extent没有显示出来，实际是每个ext4 extent B+树每个索引节点ext4_extent_idx、每个叶子节点的ext4_extent全用满了！

Ok，再来最后一击，如果此时我们向该ext4 extent B+树插入逻辑块地址是1500~1520的ext4_extent该怎么办？

首先需要创建一层索引节点，把原根节点的c0、c5000、c9000、c13000这4个ext4_extent_idx移动到该索引节点的前4个ext4_extent_idx位置处，如下图所示：

继续，在新创建的索引节点第5个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处创建起始逻辑块地址是15000的ext4_extent_idx，编号c15000。并且，还创建了c15000指向的索引节点，并且在该索引节点的第一个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处，也创建起始逻辑块地址是150000的ext4_extent_idx，编号c15000_2。最后，创建c15000_2指向的叶子节点，把逻辑块地址是15000~15020的ext4_extent插入到该叶子节点的第一个ext4_extent位置处。需注意，c5000、c9000、c13000索引节点ext4_extent_idx指向的索引节点及下边的叶子节点与c0是类似的，这些索引节点和叶子节点全占满，只是空间限制没有画出来。

二、ext4 extent内核源码解析

什么时候会用到ext4 extent B+树呢？我们看一个函数流程ext4_readpage()->mpage_readpages()->ext4_get_block()->_ext4_get_block()->ext4_map_blocks()->ext4_ext_map_blocks()，这是一个典型的ext4文件系统读文件的流程。里边有一个核心操作是，把应用层读文件的逻辑地址转成实际保存文件数据的物理块地址，有个这个物理块地址，才能从磁盘读到文件数据。而ext4_ext_map_blocks()正是完成文件逻辑地址与物理块地址映射的核心函数。这里先把ext4_ext_map_blocks()函数整体流程图贴下，然后结合上文中ext4  extent B+树的形成过程，结合源码讲解一下函数流程。


最后执行ext4_ext_insert_extent()把新的ext4_extent插入到ext4 extent b+树，ext4_ext_insert_extent()函数是个重点函数，逻辑非常复杂，它的源码流程简单画下：


接下来将以ext4_ext_map_blocks()函数为切入点，详细讲解把怎么找到文件的逻辑块地址映射的物理块地址，完成文件逻辑块地址与物理块地址的映射，然后把表示这个映射关系的ext4_extent结构插入ext4_extent b+树。在正式开始讲解前，把下边讲解源码时高频出现的词汇单独列下：

  • map：本次参与文件逻辑块地址映射的 struct ext4_map_blocks 结构

  • map->m_lblk：待映射的起始逻辑块地址

  • map->m_len：待映射的逻辑块个数，或者说逻辑块地址需映射的物理块个数

  • depth 或 ext_depth(inode): ext4 extent b+树深度

  • ex：原型是struct ext4_extent *ex，执行ext4_ext_find_extent(...map->m_lblk...)后被赋值叶子节点中起始逻辑块地址最接近map->m_lblk的ext4_extent结构

  • ex->ee_block 或 ee_block：ex这个ext4_extent结构的起始逻辑块地址

  • ee_len：ex映射的连续物理块个数

  • ee_start：ex的起始逻辑块地址映射的起始物理块号

1 ext4_ext_map_blocks()函数源码解析

ext4_ext_map_blocks()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



int ext4_ext_map_blocks(handle_t *handle, struct inode *inode, struct ext4_map_blocks *map, int flags){ struct ext4_ext_path *path = NULL; struct ext4_extent newex, *ex, *ex2; struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); ext4_fsblk_t newblock = 0; int free_on_err = 0, err = 0, depth, ret; unsigned int allocated = 0, offset = 0; unsigned int allocated_clusters = 0; struct ext4_allocation_request ar; ext4_io_end_t *io = ext4_inode_aio(inode); ext4_lblk_t cluster_offset; int set_unwritten = 0; ......... /*在ext4 extent B+树每一层索引节点(包含根节点)中找到起始逻辑块地址最接近传入的起始逻辑块地址map->m_lblk的ext4_extent_idx结构保存到path[ppos]->p_idx.然后找到最后一层的叶子节点中最接近传入的起始逻辑块地址map->m_lblk的ext4_extent结构，保存到path[ppos]->p_ext。这个ext4_extent才包含了逻辑块地址和物理块地址的映射关系。*/ path = ext4_ext_find_extent(inode, map->m_lblk, NULL); //ext4 extent B+树深度 depth = ext_depth(inode); //指向起始逻辑块地址最接近map->m_lblk的ext4_extent ex = path[depth].p_ext; if (ex) { //ext4_extent结构代表的起始逻辑块地址 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block); //ext4_extent结构代表的起始物理块地址 ext4_fsblk_t ee_start = ext4_ext_pblock(ex); unsigned short ee_len;  //ex的逻辑块地址映射的物理块个数 ee_len = ext4_ext_get_actual_len(ex); //如果map->m_lblk在ex的逻辑块地址范围内 if (in_range(map->m_lblk, ee_block, ee_len)) { //newblock : map->m_lblk这个起始逻辑块地址对应的物理块地址 newblock = map->m_lblk - ee_block + ee_start; //map->m_lblk到(ee_block+ee_len)这个范围的物理块个数 allocated = ee_len - (map->m_lblk - ee_block); /*ex已经初始化过直接goto out返回，否则执行下边的ext4_ext_handle_uninitialized_extents()*/ if (!ext4_ext_is_uninitialized(ex)) goto out;  /*对ex的逻辑块地址进行分割，高版本内核函数名称改为 ext4_ext_handle_unwritten_extents()*/ ret = ext4_ext_handle_uninitialized_extents( } } .......... //设置newex的起始逻辑块号，newex是针对本次映射分配的ext4_extent结构 newex.ee_block = cpu_to_le32(map->m_lblk); ......... //找到map->m_lblk映射的目标起始物理块地址并返回给ar.goal ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk); //ar.logical是起始逻辑块地址map->m_lblk ar.logical = map->m_lblk; ....... //offset测试时0 offset = EXT4_LBLK_COFF(sbi, map->m_lblk); //本次映射需分配的物理块个数，即allocated ar.len = EXT4_NUM_B2C(sbi, offset+allocated); //物理块起始地址，offset是0 ar.goal -= offset; ar.logical -= offset; ....... /*分配map->m_len个物理块，这就是newex逻辑块地址映射的map->m_len个物理块，并返回这map->m_len个物理块的起始物理块号newblock。测试结果 newblock 和 ar.goal有时相等，有时不相等。本次映射的起始逻辑块地址是map->m_lblk，映射物理块个数map->m_len，ext4_mb_new_blocks()除了要找到newblock这个起始逻辑块地址，还得保证找到newblock打头的连续map->m_len个物理块，必须是连续的，这才是更重要的。*/ newblock = ext4_mb_new_blocks(handle, &ar, &err); ..............got_allocated_blocks: /*设置本次映射的map->m_len个物理块的起始物理块号(newblock)到newex，newex是针对本次映射分配的ext4_extent结构*/ ext4_ext_store_pblock(&newex, newblock + offset);//offset是0 /*设置newex映射的物理块个数，与执行ext4_ext_mark_initialized()标记ex已初始化一个效果*/ newex.ee_len = cpu_to_le16(ar.len); ......... if (!err)//把newex这个插入ext4 extent B+树 err = ext4_ext_insert_extent(handle, inode, path, &newex, flags); ..........out: .......... map->m_flags |= EXT4_MAP_MAPPED; //本次起始逻辑块地址map->m_lblk映射的起始物理块号 map->m_pblk = newblock; /*本次逻辑块地址完成映射的物理块数，并不能保证allocated等于传入的map->m_len，还有可能小于*/ map->m_len = allocated;  //返回成功映射的物理块个数 return err ? err : allocated;}

ext4_ext_map_blocks()函数主要流程有如下几点：

1：先执行ext4_ext_find_extent()，试图找到逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构并保存到path[]。ext4_ext_find_extent()函数源码下文详解。如果找到匹配的叶子节点ext4_extent结构，则ex = path[depth].p_ext保存这个找到的ext4_extent结构。此时if (ex)成立，如果map->m_lblk在ex的逻辑块地址范围内，即if (in_range(map->m_lblk, ee_block, ee_len))成立，则执行里边代码newblock = map->m_lblk - ee_block + ee_start和allocated = ee_len - (map->m_lblk - ee_block)，通过ex已经映射的逻辑块地址和物理块地址找到map->m_lblk映射的起始物理块，allocated是找到的映射的物理块个数。简单说，本次要映射的起始逻辑块地址map->m_lblk在ex的逻辑块地址范围内，那就可以借助ex这个ext4_extent已有的逻辑块地址与物理块地址映射关系，找到map->m_lblk映射的起始物理块地址，并找到已经映射过的allocated个物理块。

2：如果ex是已初始化状态，则if (!ext4_ext_is_uninitialized(ex))成立，直接goto out 。否则ex未初始化状态，则要执行ext4_ext_handle_uninitialized_extents()->ext4_ext_convert_to_initialized()对ex的逻辑块地址进行分割，还有概率创建新的索引节点和叶子节点。高版本内核 ext4_ext_handle_uninitialized_extents()函数名称改为 ext4_ext_handle_unwritten_extents()，需注意，ext4_ext_convert_to_initialized()源码下文详解。

3：继续ext4_ext_map_blocks()代码，如果ex = path[depth].p_ext是NULL，则if (ex)不成立。则执行下文newblock = ext4_mb_new_blocks(handle, &ar, &err)函数，针对本次需映射的起始逻辑块地址map->m_lblk和需映射的逻辑块个数map->m_len，分配map->m_len个连续的物理块并返回这map->m_len个物理块的第一个物理块号给newblock。

4：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址，newex是针对本次逻辑块地址映射创建的ext4_extent结构。然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址map->m_lblk ~( map->m_lblk+ map->m_len)映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len，即map->m_len。

5：执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址映射关系的newex插入到ext4  extent b+树。

2 ext4_ext_find_extent()函数源码解析

ext4_ext_find_extent()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_ext_path * ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block, struct ext4_ext_path *path)//block是传入的起始逻辑块地址{ struct ext4_extent_header *eh; struct buffer_head *bh; short int depth, i, ppos = 0, alloc = 0; int ret; //从ext4_inode_info->i_data数组得到ext4 extent B+树的根节点 eh = ext_inode_hdr(inode); //xt4 extent B+树深度 depth = ext_depth(inode); if (!path) { //按照B+树的深度分配ext4_ext_path结构 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2), GFP_NOFS); if (!path) return ERR_PTR(-ENOMEM); alloc = 1; } path[0].p_hdr = eh; path[0].p_bh = NULL; i = depth; while (i) { /*利用二分法在ext4 extent B+树path[ppos]->p_hdr[]后边的ext4_extent_idx[]数组中，找到起始逻辑块地址最接近block的ext4_extent_idx结构。path[ppos]->p_idx指向这个ext4_extent_idx*/ ext4_ext_binsearch_idx(inode, path + ppos, block); //通过索引节点ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员计算出的物理块号，这个物理块保存了下层叶子节点或者索引节点4K数据 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx); path[ppos].p_depth = i;//逻辑块地址接近map->m_lblk的索引节点或叶子节点所在ext4 extent B+树中的层数 path[ppos].p_ext = NULL; /*path[ppos].p_block是保存了下层叶子节点或者索引节点4K数据，bh映射指向这个物理块*/ bh = sb_getblk(inode->i_sb, path[ppos].p_block); .................. /*eh指向当前索引节点对应的 下层的索引节点或者叶子节点的头结点，注意，是当前ppos索引节点下层的索引节点或者叶子节点*/ eh = ext_block_hdr(bh); //索引节点层数加1 ppos++; .............. /*上边ppos++了，ppos代表下一层索引节点或者叶子节点了。path[ppos].p_bh指向新的ppos这一层 索引节点或者叶子节点 4K数据的物理块 映射的bh*/ path[ppos].p_bh = bh; //path[ppos].p_bh指向新的ppos这一层索引节点或者叶子节点的头结构 path[ppos].p_hdr = eh; i--; ................ } path[ppos].p_depth = i; path[ppos].p_ext = NULL; path[ppos].p_idx = NULL; /*利用二分法在ext4 extent B+树path[ppos]->p_hdr[]后边的ext4_extent[]数组中，找到起始逻辑块地址最接近block的ext4_extent，令path[ppos]->p_ext指向这个ext4_extent。如果叶子结点没有一个有效的ext4_extent结构，则path[ppos]->p_ext保持NULL*/ ext4_ext_binsearch(inode, path + ppos, block) if (path[ppos].p_ext) /*由ext4_extent结构的ee_start_hi和ee_start_lo成员计算出的物理块号，这个物理块号是ext4_extent的逻辑块地址映射的的起始物理块号*/ path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext); ext4_ext_show_path(inode, path); return path;err: ext4_ext_drop_refs(path); if (alloc) kfree(path); return ERR_PTR(ret);}

该函数根据ext4 extent B+树的根节点的ext4_extent_header，先找到每一层索引节点中起始逻辑块地址最接近传入的逻辑块地址block的ext4_extent_idx保存到path[ppos]->p_idx.然后找到最后一层的叶子节点中起始逻辑块地址最接近传入的逻辑块地址block的ext4_extent，保存到path[ppos]->p_ext，这个ext4_extent才包含了逻辑块地址和物理块地址的映射关系。注意，找到这些起始逻辑块地址接近block的ext4_extent_idx和ext4_extent的起始逻辑块地址<=block，在block的左边，必须这样！将来把block对应的ext4_extent插入ext4 extent B+树时，也是插入到这些ext4_extent_idx和ext4_extent的右边。ext4 extent B+树索引节点和叶子节点中的ext4_extent_idx和ext4_extent的逻辑块地址从左到右依次增大，顺序排布。

下边举例讲解，先看下这个示意图，在第一篇讲解ext4_extent 的文章出现过。在执行ext4_ext_map_blocks()函数时，待映射的起始逻辑块地址是map->m_lblk，需要映射的逻辑块个数是map->m_len。再简单说下ext4_ext_find_extent()函数的作用，简单说：根据传入的起始逻辑块地址map->m_lblk，在ext4  extent b+树中从根节点到索引节点再到叶子节点，找到起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx和ext4_extent保存到struct ext4_ext_path *path[]数组。下边用示意图举个例子：


假设待映射的起始逻辑块地址map->m_lblk是5，则根节点起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx是c0，索引节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx是d0，叶子节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent是e0。则进行如下赋值 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



path[0].p_idx = c0//指向根节点起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idxpath[1].p_idx = d0//指向索引节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idxpath[2].p_ext = e0//指向叶子节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent

struct ext4_ext_path *path[]结构体定义如下: 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_ext_path { /*ext4_ext_find_extent()中赋值，是索引节点时，是由ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员计算出的物理块号，这个物理块保存了下层叶子节点或者索引节点4K数据。是叶子节点时，是由ext4_extent结构的ee_start_hi和ee_start_lo成员计算出的物理块号，这个物理块号是ext4_extent的逻辑块地址映射的的起始物理块号*/ ext4_fsblk_t p_block; //当前索引节点或者叶子节点处于ext4 extent B+树第几层。ext4 extent B+树没有索引节点或者叶子节点时层数是0 __u16               p_depth; //起始逻辑块地址最接近map->m_lblk的ext4_extent struct ext4_extent *p_ext; //起始逻辑块地址最接近传map->m_lblk的ext4_extent_idx struct ext4_extent_idx *p_idx; //指向ext4 extent B+索引节点和叶子节点的头结点结构体 struct ext4_extent_header *p_hdr; //保存索引节点或者叶子节点4K数据的物理块映射的bh struct buffer_head *p_bh;};struct ext4_extent_idx { //起始逻辑块地址 __le32  ei_block;  /*由ei_leaf_lo和ei_leaf_hi一起计算出物理块号，这个物理块保存下层叶子节点或者索引节点4K数据。没错，索引节点ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi保存了下层索引节点或者叶子节点的物理块号，索引节点的ext4_extent_idx通过其ei_leaf_lo和ei_leaf_hi成员指向下层的索引节点或者叶子节点。这点非常重要*/ __le32  ei_leaf_lo; __le16  ei_leaf_hi; __u16   ei_unused;};struct ext4_extent { //起始逻辑块地址 __le32  ee_block; //逻辑块映射的连续物理块个数 __le16  ee_len;  //由ee_start_hi和ee_start_lo一起计算出起始逻辑块地址映射的起始物理块地址 __le16  ee_start_hi;  __le32  ee_start_lo; };

我们这里只展示了对它的成员p_idx和p_ext赋值，这两个成员最关键，其他成员没展示。下一节讲解ext4_ext_convert_to_initialized ()函数。

3 ext4_ext_convert_to_initialized ()函数源码解析

ext4_ext_convert_to_initialized ()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_ext_convert_to_initialized(handle_t *handle, struct inode *inode, struct ext4_map_blocks *map, struct ext4_ext_path *path, int flags){ //ext4 extent B+树深度 depth = ext_depth(inode); //指向ext4 extent B+树叶子节点头结构ext4_extent_header eh = path[depth].p_hdr; /*ext4 extent B+树叶子节点，指向起始逻辑块地址最接近map->m_lblk的ext4_extent*/ ex = path[depth].p_ext; //ex这个ext4_extent的起始逻辑块地址 ee_block = le32_to_cpu(ex->ee_block); //ex这个ext4_extent映射的物理块个数 ee_len = ext4_ext_get_actual_len(ex);  //要映射的起始逻辑块地址map->m_lblk等于ex的起始逻辑块地址 if ((map->m_lblk == ee_block) && (map_len < ee_len) &&/*要求映射的物理块数map_len要小于ex已经映射的物理块数ee_len*/ /*ex是指向叶子节点第2个及以后ext4_extent结构*/ (ex > EXT_FIRST_EXTENT(eh))) { ........... /*下边是重新划分ex这个ext4_extent结构的逻辑块地址范围，把之前ee_block~ee_block+map_len划分给abut_ex这个ext4_extent，ex新的逻辑块地址范围是(ee_block + map_len)~(ee_block + ee_len)。ex映射的逻辑块(物理块)个数减少了map_len个，abut_ex的增加了map_len个*/ ex->ee_block = cpu_to_le32(ee_block + map_len);//设置新的逻辑块首地址 ext4_ext_store_pblock(ex, ee_pblk + map_len);//设置新的物理块首地址 ex->ee_len = cpu_to_le16(ee_len - map_len);//设置新的映射的物理块个数 /*把ex这个ext4_extent设置"uninitialized"标记，这是重点*/ ext4_ext_mark_uninitialized(ex); //abut_ex映射的物理块个数增加map_len个 abut_ex->ee_len = cpu_to_le16(prev_len + map_len); //allocated是abut_ex增多的逻辑块个数 allocated = map_len; ........... } //要映射的结束逻辑块地址map->m_lblk+map_len等于ex的结束逻辑块地址ee_block + ee_len else if (((map->m_lblk + map_len) == (ee_block + ee_len)) && (map_len < ee_len) && /*L1*///要求映射的物理块数map_len要小于ex已经映射的物理块数ee_len ex < EXT_LAST_EXTENT(eh)) { /*L2*///ex是指向叶子节点最后一个ext4_extent结构 ........... /*下边这是把ex的逻辑块范围(ex->ee_block + ee_len - map_len)~(ex->ee_block + ee_len)这map_len个逻辑块合并到后边的abut_ex，合并后abut_ex的逻辑块范围是(ex->ee_block + ee_len - map_len)~(next_lblk+next_len),ex的逻辑块范围缩小为ex->ee_block~(ee_len - map_len)*/ abut_ex->ee_block = cpu_to_le32(next_lblk - map_len); ext4_ext_store_pblock(abut_ex, next_pblk - map_len);//设置新的物理块首地址 //ex映射的逻辑块个数减少了map_len个 ex->ee_len = cpu_to_le16(ee_len - map_len); /*标记ex为"uninitialized"状态,这是重点，ex还是未初始化状态*/ ext4_ext_mark_uninitialized(ex); //abut_ex逻辑块个数增大了map_len个 abut_ex->ee_len = cpu_to_le16(next_len + map_len); //abut_ex逻辑块个数增加了map+len个 allocated = map_len; ...........  } ............. if (allocated) {/*allocated非0说明abut_ex逻辑块范围吞并了ex map_len个逻辑块*/ /*ext4 extent叶子节点变为abut_ex，原来的ex废弃了，隐藏知识点*/ path[depth].p_ext = abut_ex; goto out;//退出该函数 } else /*即allocated=(ee_len+ee_block) - map->m_lblk。如果abut_ex没有吞并ex的逻辑块，allocated是map->m_lblk到ex结束逻辑块地址之间的逻辑块数*/ allocated = ee_len - (map->m_lblk - ee_block); ........... //重点，把ex的逻辑块地址进行分割 allocated = ext4_split_extent(handle, inode, path, &split_map, split_flag, flags);  return err ? err : allocated;}

该函数逻辑比较简单，主要功能总结如下：如果本次要映射的物理块数(或者逻辑块数)map->len小于ex已经映射的逻辑块数ee_len，则尝试把ex的map->len的逻辑块合并到它前边或者后边的ext4_extent结构(即abut_ex)。合并条件苛刻，需要二者逻辑块地址和物理块地址紧挨着等等。如果合并成功直接从ext4_ext_convert_to_initialized()函数返回。否则执行ext4_split_extent()把ex的逻辑块地址进程分割成2段或者3段，分割出的以map->m_lblk为起始地址且共allocated个逻辑块的逻辑块范围就是我们需要的，这allocated个逻辑块可以保证映射了物理块。但allocated<=map->len，即并不能保证map要求映射的map->len个逻辑块全映射完成。注意，ext4_split_extent()对ex分割后，还剩下其他1~2段逻辑块范围，则要把它们对应的ext4_extent结构插入的ext4_extent B+树。

该函数里重点执行的ext4_split_extent()函数。

4 ext4_split_extent()函数源码解析

ext4_split_extent()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_split_extent(handle_t *handle, struct inode *inode, struct ext4_ext_path *path, struct ext4_map_blocks *map, int split_flag, int flags){ ext4_lblk_t ee_block; struct ext4_extent *ex; unsigned int ee_len, depth; int err = 0; int uninitialized; int split_flag1, flags1; int allocated = map->m_len; depth = ext_depth(inode); ex = path[depth].p_ext; ee_block = le32_to_cpu(ex->ee_block); ee_len = ext4_ext_get_actual_len(ex); //ex是否是未初始化状态 uninitialized = ext4_ext_is_uninitialized(ex); /*如果map的结束逻辑块地址小于ex的结束逻辑块地址，则执行ext4_split_extent_at()把ex的逻辑块地址分割为ee_block~(map->m_lblk+map->m_len)和(map->m_lblk+map->m_len)~(ee_block + ee_len)*/ if (map->m_lblk + map->m_len < ee_block + ee_len) { split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;  flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;//flag加上EXT4_GET_BLOCKS_PRE_IO标记 /*如果ex有未初始化标记，则split_flag1被加上EXT4_EXT_MARK_UNINIT1和EXT4_EXT_MARK_UNINIT2标记。EXT4_EXT_MARK_UNINIT1是标记分割的前半段ext4_extent未初始化状态,EXT4_EXT_MARK_UNINIT2是标记分割的后半段ext4_extent未初始化状态*/ if (uninitialized) split_flag1 |= EXT4_EXT_MARK_UNINIT1 | EXT4_EXT_MARK_UNINIT2;  if (split_flag & EXT4_EXT_DATA_VALID2) split_flag1 |= EXT4_EXT_DATA_VALID1; /*以map->m_lblk + map->m_len这个逻辑块地址为分割点，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围ee_block~(ee_block+ee_len)分割成ee_block~(map->m_lblk + map->m_len)和(map->m_lblk + map->m_len)~(ee_block+ee_len)，然后把后半段map->m_lblk + map->m_len)~(ee_block+ee_len)对应的ext4_extent结构添加到ext4 extent B+树*/ err = ext4_split_extent_at(handle, inode, path, map->m_lblk + map->m_len, split_flag1, flags1); if (err) goto out; } else { /*到这里，说明map的结束逻辑块地址大于ex的结束逻辑块地址，则allocated=(ee_len+ee_block)-map->m_lblk，即本次映射map只能用到ex逻辑块范围里的allocated个逻辑块，下边if (map->m_lblk >= ee_block)肯定成立，则执行ext4_split_extent_at()把ex的逻辑块范围分割成ee_block~map->m_lblk 和 map->m_lblk~(ee_block + ee_len)。map->m_lblk~(ee_block + ee_len)是map本次映射的逻辑块，没有达到map->len个*/ allocated = ee_len - (map->m_lblk - ee_block); } ................. /*上边可能把ex的逻辑块范围分割了，这里重新再ext4 extent B+树查找逻辑块地址范围接近map->m_lblk的索引节点和叶子结点*/ path = ext4_ext_find_extent(inode, map->m_lblk, path); ................. depth = ext_depth(inode); ex = path[depth].p_ext; //ex是否是未初始化状态 uninitialized = ext4_ext_is_uninitialized(ex); split_flag1 = 0;  /*如果map的起始逻辑块地址大于等于ex的起始逻辑块地址，以map->m_lblk为分割点，再次分割新的ex逻辑块范围*/ if (map->m_lblk >= ee_block) { split_flag1 = split_flag & EXT4_EXT_DATA_VALID2; /*如果ex有未初始化标记，则split_flag1被加上EXT4_EXT_MARK_UNINIT1标记，EXT4_EXT_MARK_UNINIT1是标记分割的前半段ext4_extent未初始化状态*/ if (uninitialized) { split_flag1 |= EXT4_EXT_MARK_UNINIT1; split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT | EXT4_EXT_MARK_UNINIT2); } /*以map->m_lblk这个逻辑块地址为分割点，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围ee_block~(ee_block+ee_len)分割成ee_block~map->m_lblk和map->m_lblk~(ee_block+ee_len)，然后把后半段map->m_lblk~(ee_block+ee_len)对应的ext4_extent结构添加到ext4 extent B+树。*/ err = ext4_split_extent_at(handle, inode, path, map->m_lblk, split_flag1, flags); if (err) goto out; } .................out: return err ? err : allocated;}

该函数主要分两种情况：

4.1 map->m_lblk +map->m_len 小于ee_block + ee_len时的分割

如果 map->m_lblk +map->m_len 小于ee_block + ee_len，即map的结束逻辑块地址小于ex的结束逻辑块地址。则把ex的逻辑块范围分割成3段ee_block~map->m_lblk 和 map->m_lblk~(map->m_lblk +map->m_len) 和 (map->m_lblk +map->m_len)~(ee_block + ee_len)。这种情况，就能保证本次要求映射的map->m_len个逻辑块都能完成映射，即allocated =map->m_len。具体细节是:

1：if (map->m_lblk + map->m_len < ee_block + ee_len)成立，split_flag1 |= EXT4_EXT_MARK_UNINIT1|EXT4_EXT_MARK_UNINIT2,然后执行ext4_split_extent_at()以map->m_lblk + map->m_len这个逻辑块地址为分割点，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围ee_block~(ee_block+ee_len)分割成ee_block~(map->m_lblk + map->m_len)和(map->m_lblk + map->m_len)~(ee_block+ee_len)这两个ext4_extent。

2：前半段的ext4_extent还是ex，只是映射的逻辑块个数减少了(ee_block+ee_len)-(map->m_lblk + map->m_len)。后半段的是个新的ext4_extent。因为split_flag1 |= EXT4_EXT_MARK_UNINIT1|EXT4_EXT_MARK_UNINIT2，则还要标记这两个ext4_extent结构"都是未初始化状态"。然后把后半段 (map->m_lblk + map->m_len)~(ee_block+ee_len)对应的ext4_extent结构添加到ext4 extent B+树。回到ext4_split_extent()函数，ext4_ext_find_extent(inode, map->m_lblk, path)后path[depth].p_ext大概率还是老的ex。

3：if (map->m_lblk >= ee_block)肯定成立，里边的if (uninitialized)成立，if (uninitialized)里边的split_flag1 |= EXT4_EXT_MARK_UNINIT1，可能不会加上EXT4_EXT_MARK_UNINIT2标记。因为split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |EXT4_EXT_MARK_UNINIT2)，接着再次执行ext4_split_extent_at(),以map->m_lblk这个逻辑块地址为分割点，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围ee_block~(ee_block+ee_len)分割成ee_block~map->m_lblk和map->m_lblk~(ee_block+ee_len)两个ext4_extent结构。

前半段的ext4_extent结构还是ex，但是逻辑块数减少了(ee_block+ee_len)-map->m_lblk个。因为此时split_flag1有EXT4_EXT_MARK_UNINIT1标记，可能没有EXT4_EXT_MARK_UNINIT2标记，则再对ex加上"未初始化状态"，后半段的ext4_extent可能会被去掉"未初始化状态"，因为split_flag1可能没有EXT4_EXT_MARK_UNINIT2标记。接着，把后半段的ext4_extent结构添加到ext4 extent B+树。这里有个特例，就是 if (map->m_lblk >= ee_block)里的map->m_lblk == ee_block，即map的要映射的起始逻辑块地址等于ex的起始逻辑块地址，则执行ext4_split_extent_at()函数时，不会再分割ex，里边if (split == ee_block)成立，会执行ext4_ext_mark_initialized(ex)标记ex是"初始化状态"，ex终于转正了。

4.2 map->m_lblk +map->m_len 大于等于ee_block + ee_len时的分割

如果 map->m_lblk +map->m_len 大于等于ee_block + ee_len，即map的结束逻辑块地址大于ex的结束逻辑块地址。则把ex的逻辑块范围分割成2段ee_block~map->m_lblk 和 map->m_lblk~(ee_block + ee_len)，这种情况，不能保证本次要求映射的map->m_len个逻辑块都完成映射。只能映射 (ee_block + ee_len) - map->m_lblk个逻辑块，即allocated =(ee_block + ee_len) - map->m_lblk。这个分割过程就是4.1节的第3步，看4.1节的第3步节就行。

ext4_split_extent()里重点执行的是ext4_split_extent_at()函数，它完成对ex逻辑块地址的分割。

5 ext4_split_extent_at()函数源码解析

ext4_split_extent_at()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_split_extent_at(handle_t *handle, struct inode *inode, struct ext4_ext_path *path, ext4_lblk_t split, int split_flag, int flags){ //ext4 extent B+树深度 depth = ext_depth(inode); /*ext4 extent B+树叶子节点中起始逻辑块地址最接近map->m_lblk这个起始逻辑块地址的ext4_extent*/ ex = path[depth].p_ext; //ex这个ext4_extent代表的起始逻辑块地址 ee_block = le32_to_cpu(ex->ee_block); //ex这个ext4_extent代表的映射的物理块个数 ee_len = ext4_ext_get_actual_len(ex); /*ee_block是ex起始逻辑块地址，split是分割点的逻辑块地址，split大于ee_block，二者都在ex这个ext4_extent的逻辑块范围内。newblock是分割点的逻辑块地址对应的物理块地址*/ newblock = split - ee_block + ext4_ext_pblock(ex); ........... //分割点的逻辑块地址等于ex起始逻辑块地址，不用分割 if (split == ee_block) { if (split_flag & EXT4_EXT_MARK_UNINIT2) ext4_ext_mark_uninitialized(ex);//有"UNINIT2"标记就要标记ex "uninitialized" else ext4_ext_mark_initialized(ex);//标记ex初始化 if (!(flags & EXT4_GET_BLOCKS_PRE_IO)) //尝试把ex前后的ext4_extent结构的逻辑块和物理块地址合并到ex ext4_ext_try_to_merge(handle, inode, path, ex); /*ext4_extent映射的逻辑块范围可能发生变化了，标记对应的物理块映射的bh或者文件inode脏*/ err = ext4_ext_dirty(handle, inode, path + path->p_depth); goto out; } /*下边这是把ex的逻辑块分割成两部分(ee_block~split)和(split~ee_block+ee_len)。分割后，ex新的逻辑块范围是(ee_block~split)，ex2的逻辑块范围是(split~ee_block+ee_len)*/ //orig_ex先保存ex原有数据 memcpy(&orig_ex, ex, sizeof(orig_ex)); /*重点，标记ex->ee_len为映射的block数，这样ex就是被标记初始化状态了，因为ex->ee_len只要不是没被标记EXT_INIT_MAX_LEN，就是初始化状态，但是一旦下边执行ext4_ext_mark_uninitialized(ex)，ex又成未初始化状态了*/ ex->ee_len = cpu_to_le16(split - ee_block); if (split_flag & EXT4_EXT_MARK_UNINIT1) ext4_ext_mark_uninitialized(ex);//有EXT4_EXT_MARK_UNINIT1标记再把ex标记未初始化 ............. ex2 = &newex;//ex2就是ex分割后的后半段的逻辑块范围对应的ext4_extent结构 ex2->ee_block = cpu_to_le32(split);//ex2的逻辑块起始地址，分割点的逻辑块地址 ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));//ex2逻辑块个数 ext4_ext_store_pblock(ex2, newblock);//ex2的起始物理块地址 if (split_flag & EXT4_EXT_MARK_UNINIT2) ext4_ext_mark_uninitialized(ex2);//标记ex2未初始化状态 //把ex分割的后半段ext4_extent结构即ex2添加到ext4 extent B+树，重点函数 err = ext4_ext_insert_extent(handle, inode, path, &newex, flags); ..........}

ext4_split_extent_at()函数逻辑简单多了，主要作用是：以split这个逻辑块地址为分割点，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围ee_block~(ee_block+ee_len)分割成ee_block~split和split~(ee_block+ee_len)，然后把后半段split~(ee_block+ee_len)对应的ext4_extent结构添加到ext4 extent B+树。

ext4_split_extent_at()里执行的ext4_ext_insert_extent()才是重点函数，它负责把一个ext4_extent插入ext4_extent b+树，流程是相当复杂。

6 ext4_ext_insert_extent()函数源码解析

ext4_ext_insert_extent()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, struct ext4_ext_path *path, struct ext4_extent *newext, int flag)//newext正是要插入extent B+数的ext4_extent{ //ext4 extent B+树深度 depth = ext_depth(inode); /*ext4 extent B+树叶子节点中起始逻辑块地址最接近map->m_lblk这个起始逻辑块地址的ext4_extent*/ ex = path[depth].p_ext; eh = path[depth].p_hdr;  /*下判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并。但能合并还要符合一个苛刻条件:参与合并的两个ext4_extent必须是initialized状态，否则无法合并*/ if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)) { ................ if (ext4_can_extents_be_merged(inode, ex, newext)) { //把newext的逻辑块地址范围合并到ex ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) + ext4_ext_get_actual_len(newext)); if (uninitialized) ext4_ext_mark_uninitialized(ex);//标记ex未初始化 eh = path[depth].p_hdr;  nearex = ex;//nearex是ex  goto merge;//跳转到merge分支 ............... }prepend: if (ext4_can_extents_be_merged(inode, newext, ex)) { ........... //ex没有初始化过则uninitialized = 1 if (ext4_ext_is_uninitialized(ex)) uninitialized = 1; //把ex的逻辑块地址范围合并到newext，还是以ex为母体 ex->ee_block = newext->ee_block; //更新ex映射的的起始物理块地址为newext的映射的起始物理块地址 ext4_ext_store_pblock(ex, ext4_ext_pblock(newext)); //ex->ee_len增加newext的逻辑块(物理块)个数 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) + ext4_ext_get_actual_len(newext)); if (uninitialized) ext4_ext_mark_uninitialized(ex); eh = path[depth].p_hdr;  nearex = ex;//nearex是ex  goto merge;//跳转到merge分支 ............... } } ............. depth = ext_depth(inode); eh = path[depth].p_hdr; /*eh->eh_max是ext4_extent B+树叶子节点最大ext4_extent个数，这是测试path[depth].p_hdr所在叶子节点的ext4_extent结构是否爆满，没有爆满才会跳到has_space分支*/ if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) goto has_space;  /*如果要插入的newext起始逻辑块地址大于ext4 extent B+树叶子节点最后一个ext4_extent结构的，说明当前的叶子节点逻辑块地址范围太小了*/ if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)) /*回到上层找到起始逻辑块地址更大的索引节点，这个索引节点还必须得有空闲的ext4_extent_idx*/ next = ext4_ext_next_leaf_block(path); if (next != EXT_MAX_BLOCKS) {//成立说明找到了合适的ext4_extent_idx { /*next是ext4 extent B+树新找到的索引节点ext4_extent_idx的起始逻辑块地址，这个逻辑块地址更大，本次要插入的newext的逻辑块地址在这个ext4_extent_idx的逻辑块地址范围内。下边是根据next这个逻辑地址，在ext4 extent B+树，从上层到下层，一层层找到起始逻辑块地址最接近next的索引节点ext4_extent_idx结构和叶子节点ext4_extent结构，保存到npath[]*/ npath = ext4_ext_find_extent(inode, next, NULL); ............ //按照next这个逻辑块地址找到的新的叶子节点的ext4_extent_header头结构 eh = npath[depth].p_hdr; /*叶子节点已使用的ext4_extent个数没有超过eh->eh_max成立，即叶子节点ext4_extent没有爆满*/ if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) { //path指向按照next这个逻辑块地址找到的struct ext4_ext_path path = npath; //跳到has_space分支，把newext插入到按照next这个逻辑块地址找到的叶子节点 goto has_space; } } /*到这里说明ext4_extent B+叶子节点空间不够了/  //重点函数，创建新的叶子节点或者索引节点*/ err = ext4_ext_create_new_leaf(handle, inode, flags, path, newext); depth = ext_depth(inode); eh = path[depth].p_hdr; /*到这里，最新的path[depth].p_ext所在叶子节点肯定有空闲的ext4_extent，即空闲位置可以存放newext这个ext4_extent结构，则直接把newext插入到叶子节点某个合适的ext4_extent位置处*/has_space: /*nearex指向起始逻辑块地址最接近 newext->ee_block这个起始逻辑块地址的ext4_extent，newext是本次要ext4 extent b+树的ext4_extent*/ nearex = path[depth].p_ext; if (!nearex) {//path[depth].p_ext所在叶子节点还没有使用过一个ext4_extent结构 //nearex指向叶子节点第一个ext4_extent结构，newext就插入到这里 nearex = EXT_FIRST_EXTENT(eh); } else { //newext的起始逻辑块地址大于nearex的起始逻辑块地址 if (le32_to_cpu(newext->ee_block) > le32_to_cpu(nearex->ee_block)) { nearex++;//nearex++指向后边的一个ext4_extent结构 } else { /* Insert before */ } /*这是计算nearex这个ext4_extent结构到叶子节点最后一个ext4_extent结构(有效的)之间的ext4_extent结构个数。注意"有效的"3个字，比如叶子节点只使用了一个ext4_extent，则EXT_LAST_EXTENT(eh)是叶子节点第一个ext4_extent结构。*/ len = EXT_LAST_EXTENT(eh) - nearex + 1; if (len > 0) { /*这是把nearex这个ext4_extent结构 ~ 最后一个ext4_extent结构(有效的)之间的所有ext4_extent结构的数据整体向后移动一个ext4_extent结构大小，腾出原来nearex这个ext4_extent结构的空间，下边正是把newext插入到这里，这样终于把newex插入ext4_extent B+树了*/ memmove(nearex + 1, nearex, len * sizeof(struct ext4_extent)); } } /*下边是把newext的起始逻辑块地址、起始物理块起始地址、逻辑块地址映射的物理块个数等信息赋值给nearex，相当于把newext添加到叶子节点原来nearex的位置。然后叶子节点ext4_extent个数加1。path[depth].p_ext指向newext*/  //叶子节点ext4_extent个数加1 le16_add_cpu(&eh->eh_entries, 1); //相当于path[depth].p_ext指向newext path[depth].p_ext = nearex; //nearex->ee_block赋值为newext起始逻辑块地址 nearex->ee_block = newext->ee_block; //用newext起始物理块地址赋值给nearex ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext)); //nearex->ee_len赋值为newext的 nearex->ee_len = newext->ee_len; merge: if (!(flag & EXT4_GET_BLOCKS_PRE_IO)) /*尝试把ex后的ext4_extent结构的逻辑块和物理块地址合并到ex。并且，如果ext4_extent B+树深度是1，并且叶子结点有很少的ext4_extent结构，则尝试把叶子结点的ext4_extent结构移动到root节点，节省空间而已*/ ext4_ext_try_to_merge(handle, inode, path, nearex); ............ return err;}

先对该函数功能做个整体总结：首先尝试把newext合并到ex(即path[depth].p_ext)、或者(ex+1)、或者(ex-1)指向的ext4_extent结构，合并条件很苛刻，合并成功则直接返回。接着看ext4 extent B+树中与newext->ee_block(这个要插入B+树的ext4_extent结构的起始逻辑块地址)有关的叶子节点是否ext4_extent结构爆满，即是否有空闲entry。没有空闲entry的话就执行ext4_ext_create_new_leaf()创建新的索引节点和叶子节点，这样就可以保证ext4_ext_create_new_leaf()->ext4_ext_find_extent()执行后path[depth].p_ext指向的ext4_extent结构所在的叶子节点有空闲entry，可以存放newext。接着是该函数has_space分支，只是简单的把newex插入path[depth].p_ext前后的ext4_extent位置处。最后还会执行ext4_ext_try_to_merge()尝试把ex后的ext4_extent结构的逻辑块和物理块地址合并到ex，还会尝试把叶子结点的ext4_extent结构移动到root节点，节省空间。

什么时机会执行ext4_ext_insert_extent()函数?两种情况：

1:ext4_ext_map_blocks()为map在ext4 extent B+树找不到逻辑块地址接近的ext4_extent结构，则为map分配一个新的ext4_extent结构，然后执行ext4_ext_insert_extent()把这个新的ext4_extent结构插入ext4 extent B+树。

2:在ext4_split_extent_at()中，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围分割成两段，把后半段逻辑块范围对应的ext4_extent结构执行ext4_ext_insert_extent()插入ext4 extent B+树。

它里边执行的ext4_ext_create_new_leaf()函数及后续执行的ext4_ext_split()和ext4_ext_grow_indepth()函数才是隐藏boss，把这几个函数看懂，才算理解了ext4 extent b+树是怎么形成。

7 ext4_ext_create_new_leaf()函数源码解析

首先是ext4_ext_create_new_leaf()函数，源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode, unsigned int flags, struct ext4_ext_path *path, struct ext4_extent *newext){ struct ext4_ext_path *curp; int depth, i, err = 0;repeat: //ext4 extent B+树深度 i = depth = ext_depth(inode); //curp首先指向ext4 extent B+树叶子节点 curp = path + depth;  /*该while是从ext4 extent B+树叶子节点开始，向上一直到索引节点，看索引节点或者叶子节点的ext4_extent_idx或ext4_extent个数是否大于最大限制eh_max，超出限制EXT_HAS_FREE_INDEX(curp)返回0，否则返回1.从该while循环退出时，有两种可能，1:curp非NULL，curp指向的索引节点或叶子节点有空闲ext4_extent_idx或ext4_extent可使用，2:i是0，ext4 extent B+树索引节点或叶子节点ext4_extent_idx或ext4_extent个数爆满，没有空闲ext4_extent_idx或ext4_extent可使用*/ while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) { i--; curp--; } /*ext4 extent B+树索引节点或者叶子节点有空闲ext4_extent_idx或ext4_extent可使用。此时的i表示ext4 extent B+树哪一层有空闲ext4_extent_idx或ext4_extent可使用。newext是要插入ext4_extent B+树的ext4_extent，插入ext4_extent B+树的第i层的叶子节点或者第i层索引节点下边的叶子节点*/ if (EXT_HAS_FREE_INDEX(curp)) { /*凡是执行到ext4_ext_split()函数，说明ext4 extent B+树中与newext->ee_block有关的叶子节点ext4_extent结构爆满了。于是从ext4 extent B+树at那一层索引节点到叶子节点，针对每一层都创建新的索引节点，也创建叶子节点。还会尝试把索引节点path[at~depth].p_hdr指向的ext4_extent_idx结构的后边的ext4_extent_idx结构和path[depth].p_ext指向的ext4_extent结构后边的ext4_extent结构，移动到新创建的叶子节点和索引节点。这样就能保证ext4 extent B+树中，与newext->ee_block有关的叶子节点有空闲entry，就能存放newext这个ext4_extent结构了。*/ err = ext4_ext_split(handle, inode, flags, path, newext, i); ................. /*ext4_ext_split()对ext4_extent B+树做了重建和分割，这里再次在ext4_extent B+树查找起始逻辑块地址接近newext->ee_block的索引节点和叶子结点*/ path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block), path); } else { /*到这个分支，ext4 extent B+树索引节点的ext4_extent_idx和叶子节点的ext4_extent个数全爆满，没有空闲ext4_extent_idx或ext4_extent可使用，就是说ext4 extent B+树全爆满了，只能增加执行ext4_ext_grow_indepth()增加ext4 extent B+树叶子节点或者索引节点了*/ /*针对newext->ee_block分配一个新的物理块，作为新的索引节点或者叶子节点添加到ext4 extent B+树根节点下方，这样相当于跟ext4 extent B+树增加了一层新的节点*/ err = ext4_ext_grow_indepth(handle, inode, flags, newext); ....................... /*到这里，ext4 extent B+树根节点下方增加了一层新的索引或者叶子节点，再重新在ext4 extent B+树find_extent*/ path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block), path); depth = ext_depth(inode); /*如果path[depth].p_hdr指向的叶子结点保存ext4_extent结构达到eh_max，即叶子节点ext4_extent还是爆满，则goto repeat寻找有空闲ext4_extent_idr的索引节点，然后分割ext4 extent B+树*/ if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) { /* now we need to split */ goto repeat; } }out: return err;}}

先做个整体总结：执行到该函数，说明ext4 extent B+树中与newext->ee_block有关的叶子节点ext4_extent结构爆满了，需要扩容。首先尝试搜索叶子节点上的每一层索引节点有没有空闲entry的，有的话记录这一层索引节点的深度是at。接着执行ext4_ext_split():从ext4 extent B+树at那一层索引节点到叶子节点，针对每一层都创建新的索引节点，也创建叶子节点。还会尝试把索引节点path[at~depth-1].p_hdr指向的ext4_extent_idx结构的后边的ext4_extent_idx结构和path[depth].p_ext指向的ext4_extent结构后边的ext4_extent结构，移动到新创建的叶子节点和索引节点。这样就可能保证ext4 extent B+树中，与newext->ee_block有关的叶子节点有空闲entry，能存放newext。

如果ext4 extent B+树索引节点的ext4_extent_idx结构也爆满了，则执行ext4_ext_grow_indepth()在ext4 extent B+树root节点下的创建一层新的索引节点(或者叶子节点)。此时ext4 extent B+树第2层的索引节点(或者叶子节点)是空的，可以存放多个ext4_extent_idx结构，即有空闲entry了。然后大概率goto repeat处，执行ext4_ext_split()分割创建索引节点和叶子节点。总之，从ext4_ext_create_new_leaf()函数返回前，里边执行的ext4_ext_find_extent()找打的path[depth].p_ext指向的叶子节点有空闲entry，可以存放newext。

里边重点执行了ext4_ext_split()和ext4_ext_grow_indepth()函数。

8 ext4_ext_split()函数源码解析

ext4_ext_split()感觉是最重要最负责最难以理解的一个函数，源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_ext_split(handle_t *handle, struct inode *inode, unsigned int flags, struct ext4_ext_path *path, /*newext是要插入ext4_extent B+树的ext4_extent，在ext4_extent B+树的第at层插入newext，第at层的索引节点有空闲entry*/ struct ext4_extent *newext, int at){ /*path[depth].p_ext是ext4 extent B+树叶子节点中，逻辑块地址最接近map->m_lblk这个起始逻辑块地址的ext4_extent*/ if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) { /*path[depth].p_ext不是叶子节点最后一个ext4_extent结构，那以它后边的ext4_extent结构path[depth].p_ext[1]的起始逻辑块地址作为分割点border*/ border = path[depth].p_ext[1].ee_block; } else { /*这里说明path[depth].p_ext指向的是叶子节点最后一个ext4_extent结构*/ border = newext->ee_block; }  /*依照ext4_extent B+树层数分配depth个ext4_fsblk_t的数组，下边保存分配的物理块号*/ ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS); /*分配(depth - at)个物理块，newext是在ext4 extent B+的第at层插入，从at层到depth层，每层分配一个物理块*/ for (a = 0; a < depth - at; a++) { /*每次从ext4文件系统元数据区分配一个物理块，返回它的物理块号，4K大小，保存ext4 extent B+树索引节点的头结构ext4_extent_header+N个ext4_extent_idx或者或者叶子结点ext4_extent_header+N个ext4_extent结构*/ newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err, flags); .............. //分配的物理块的块号保存到ablocks数组 ablocks[a] = newblock; } ............. //bh映射newblock物理块号，这是叶子节点的物理块 bh = sb_getblk(inode->i_sb, newblock); if (unlikely(!bh)) { err = -ENOMEM; goto cleanup; } ........... /*neh指向新分配的叶子节点首内存的头结构ext4_extent_header，下边对新分配的叶子节点头结构ext4_extent_header进行初始化*/ neh = ext_block_hdr(bh); neh->eh_entries = 0; neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0)); neh->eh_magic = EXT4_EXT_MAGIC; neh->eh_depth = 0; ........... /*从path[depth].p_ext后边的ext4_extent结构到叶子节点最后一个ext4_extent结构之间，一共有m个ext4_extent结构*/ m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++; ext4_ext_show_move(inode, path, newblock, depth); if (m) { struct ext4_extent *ex; //ex指向上边新分配的叶子节点的第一个ext4_extent结构 ex = EXT_FIRST_EXTENT(neh); //老的叶子节点path[depth].p_ext后的m个ext4_extent结构移动到上边新分配的叶子节点 memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m); //新分配的叶子节点增加了m个ext4_extent结构 le16_add_cpu(&neh->eh_entries, m); } ............ /*ext4_extent B+树at那一层的索引节点到最后一层索引节点之间的层数，就是从at开始有多少层索引节点*/ k = depth - at - 1;  /*i初值是ext4_extent B+树最后一层索引节点的层数，就是叶子节点上边的那层索引节点*/ i = depth - 1; /*循环k次保证把at那一层的ext4_extent B+树索引节点到最后一层索引节点中，每一层索引节点path[i].p_idx指向的ext4_extent_idx结构到最后一个ext4_extent_idx结构之间的ext4_extent_idx结构，都复制到上边新创建的索引节点的物理块中，物理块号是ablocks[--a]即newblock，bh映射这个物理块。neh指向这个索引节点头ext4_extent_header结构，fidx是这个索引节点第一个ext4_extent_idx结构。注意，是从ext4_extent B+树最下层的索引节点向上开始复制，因为i的初值是depth - 1，这是ext4_extent B+树最下边一层索引节点的层数*/ while (k--) { oldblock = newblock; /*新取出一个物理块对应的块号newblock，这个物理块将来保存新创建的索引节点ext4_extent_header头结构+N个ext4_extent_idx结构的4K数据*/ newblock = ablocks[--a]; //newblock物理块映射的bh bh = sb_getblk(inode->i_sb, newblock); ................ //neh指向newblock这个物理块映射的bh的内存首地址，这是索引节点的头ext4_extent_header结构 neh = ext_block_hdr(bh); //索引节点有效的ext4_extent_idx个数初值是1 neh->eh_entries = cpu_to_le16(1); neh->eh_magic = EXT4_EXT_MAGIC; //计算索引结点能容纳的ext4_extent_idx结构个数 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0)); //索引节点所处ext4 extent B+树的层数 neh->eh_depth = cpu_to_le16(depth - i); //fidx指向索引节点的第一个ext4_extent_idx结构 fidx = EXT_FIRST_INDEX(neh); //fidx的起始逻辑块地址是上边的分割点逻辑块地址border fidx->ei_block = border; /*把下一层叶子节点或者下一层索引节点的物理块号保存到当前索引节点第一个ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员中。后续可以通过这个ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员找到它指向的下一层的索引节点或者叶子节点*/ ext4_idx_store_pblock(fidx, oldblock); ................ /*计算 path[i].p_hdr这一层索引节点中，从path[i].p_idx指向的ext4_extent_idx结构到最后一个ext4_extent_idx结构之间ext4_extent_idx个数*/ m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++; ................ if (m) { /*把path[i].p_idx后边的m个ext4_extent_idx结构赋值到newblock这个物理块对应的索引节点开头的第1个ext4_extent_idx的后边，即fidx指向的ext4_extent_idx后边。这里是++fid，即fidx指向的索引节点的第2个ext4_extent_idx位置处，这是向索引节点第2个ext4_extent_idx处及后边复制m个ext4_extent_idx结构*/ memmove(++fidx, path[i].p_idx, sizeof(struct ext4_extent_idx) * m); //newblock这个物理块对应的新的索引节点增加了m个ext4_extent_idx结构 le16_add_cpu(&neh->eh_entries, m); } ............. if (m) { /*path[i].p_hdr指向的老的ext4 extent B+树那一层索引节点减少了m个ext4_extent_idx结构*/ le16_add_cpu(&path[i].p_hdr->eh_entries, -m); } /*i--进入下次循环，就会把上一层ext4_extent B+树索引节点的path[i].p_idx指向的ext4_extent_idx结构到最后一个ext4_extent_idx结构之间所有的ext4_extent_idx结构，复制到ablocks[--a]即newblock这个物理块映射bh*/ i--; } ................ /*把新的索引节点的ext4_extent_idx结构(起始逻辑块地址border,物理块号newblock)插入到ext4 extent B+树at那一层索引节点(path + at)->p_idx指向的ext4_extent_idx结构前后。*/ err = ext4_ext_insert_index(handle, inode, path + at, le32_to_cpu(border), newblock); ................  return err;}

1:首先确定ext4 extent B+树的分割点逻辑地址border。如果path[depth].p_ext不是ext4_extent B+树叶子节点节点最后一个ext4 extent结构，则分割点逻辑地址border是path[depth].p_ext后边的ext4_extent起始逻辑块地址，即border=path[depth].p_ext[1].ee_block。否则border是新插入ext4 extent B+树的ext4_extent的起始逻辑块地址，即newext->ee_block。

2:因为ext4_extent B+树at那一层索引节点有空闲entry，则针对at~depth(B+树深度)之间的的每一层索引节点和叶子节点都分配新的索引节点和叶子结点，每个索引节点和叶子结点都占一个block大小(4K)，分别保存N个ext4_extent_idx结构和N个ext4_extent结构，还有ext4_extent_header。在while (k--)那个循环，这些新分配的索引节点和叶子节点中，B+树倒数第2层的那个索引节点的第一个ext4_extent_idx的物理块号成员(ei_leaf_lo和ei_leaf_hi)记录的新分配的保存叶子结点4K数据的物理块号(代码是ext4_idx_store_pblock(fidx, oldblock))，第一个ext4_extent_idx的起始逻辑块地址是border(代码是fidx->ei_block = border)。B+树倒数第3层的那个索引节点的第一个ext4_extent_idx的物理块号成员记录的是保存倒数第2层的索引节点4K数据的物理块号，这层索引节点第一个ext4_extent_idx的起始逻辑块地址是border(代码是fidx->ei_block = border)........其他类推。at那一层新分配的索引节点(物理块号是newblock，起始逻辑块地址border)，执行ext4_ext_insert_index()插入到ext4_extent B+树at层原有的索引节点(path + at)->p_idx指向的ext4_extent_idx结构前后的ext4_extent_idx结构位置处。插入过程是:把(path + at)->p_idx指向的索引节点的ext4_extent_idx结构后的所有ext4_extent_idx结构向后移动一个ext4_extent_idx结构大小，这就在(path + at)->p_idx指向的索引节点的ext4_extent_idx处腾出了一个空闲的ext4_extent_idx结构大小空间，新分配的索引节点就是插入到这里。

3:要把ext4_extent B+树原来的at~depth层的 path[i].p_idx~path[depth-1].p_idx指向的ext4_extent_idx结构后边的所有ext4_extent_idx结构 和 path[depth].p_ext指向的ext4_extent后的所有ext4_extent结构都对接移动到上边针对ext4_extent B+树at~denth新分配索引节点和叶子节点物理块号映射bh内存。这是对原有的ext4 extent B+树进行扩容的重点。

上边的解释没有诠释到本质。直击灵魂，为什么会执行到ext4_ext_insert_extent()->ext4_ext_create_new_leaf()->ext4_ext_split()?有什么意义?首先，ext4_split_extent_at()函数中，把path[depth].p_ext指向的ext4_extent结构(即ex)的逻辑块范围分割成两段，两个ext4_extent结构。前边的ext4_extent结构还是ex，只是逻辑块范围减少了。而后半段ext4_extent结构即newext就要插入插入到到ext4 extent B+树。到ext4_ext_insert_extent()函数，如果此时ex所在叶子节点的ext4_extent结构爆满了，即if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))不成立，但是if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))成立，即newext的起始逻辑块地址小于ex所在叶子节点的最后一个ext4_extent结构的起始逻辑块地址，则执行next = ext4_ext_next_leaf_block(path)等代码，回到上层索引节点，找到起始逻辑块地址更大的索引节点和叶子节点，如果新的叶子节点的ext4_extent结构还是爆满，那就要执行ext4_ext_create_new_leaf()增大ext4_extent B+树层数了。

来到ext4_ext_create_new_leaf()函数，从最底层的索引节点开始向上搜索，找到有空闲entry的索引节点。如果找到则执行ext4_ext_split()。如果找不到则执行ext4_ext_grow_indepth()在ext4_extent B+树root节点增加一层索引节点(或叶子节点)，然后也执行ext4_ext_split()。

当执行到ext4_ext_split()，at一层的ext4_extent B+树有空闲entry，则以从at层到叶子节点那一层，创建新的索引节点和叶子节点，建立这些新的索引节点和叶子节点彼此的物理块号的联系。我们假设ext4_ext_split()的if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr))成立，则这样执行：向新分配的叶子节点复制m个ext4_extent结构时，复制的第一个ext4_extent结构不是path[depth].p_ext，而是它后边的 path[depth].p_ext[1]这个ext4_extent结构。并且，下边新创建的索引节点的第一个ext4_extent_idx结构的起始逻辑器块地址都是border，即path[depth].p_ext[1]的逻辑块地址，也是path[depth].p_ext[1].ee_block。然后向新传创建的索引节点的第2个ext4_extent_idx结构处及之后复制m个ext4_extent_idx结构。新传创建的索引节点的第一个ext4_extent_idx的起始逻辑块地址是border，单独使用，作为分割点的ext4_extent_idx结构。如此，后续执行ext4_ext_find_extent(newext->ee_block)在老的ext4_extent B+树找到的path[depth].p_ext指向的ext4_extent还是老的，但是path[depth].p_ext后边的m个ext4_extent结构移动到了新分配的叶子节点，path[depth].p_ext所在叶子节点就有空间了，newext就插入到path[depth].p_ext指向的ext4_extent叶子节点后边。这段代码在ext4_ext_insert_extent()的has_space 的if (!nearex)........} else{......}的else分支。

如果ext4_ext_split()的if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr))不成立，则这样执行：不会向新分配的叶子节点复制ext4_extent结构，m是0，因为path[depth].p_ext就是叶子节点最后一个ext4_extent结构，下边的m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++=0。并且，下边新创建的索引节点的第一个ext4_extent_idx结构的起始逻辑器块地址都是newext->ee_block。这样后续执行ext4_ext_find_extent()在ext4_extent B+树就能找到起始逻辑块地址是newext->ee_block的层层索引节点了，完美匹配。那叶子节点呢?这个分支没有向新的叶子节点复制ext4_extent结构，空的，ext4_ext_find_extent()执行后，path[ppos].depth指向新的叶子节点的头结点，此时直接令该叶子节点的第一个ext4_extent结构的逻辑块地址是newext->ee_block，完美!这段代码在ext4_ext_insert_extent()的has_space 的if (!nearex)分支。

注意，这是ext4_extent B+树叶子节点增加增加的第一个ext4_extent结构，并且第一个ext4_extent结构的起始逻辑块地址与它上边的索引节点的ext4_extent_idx的起始逻辑块地址都是newext->ee_block，再上层的索引节点的ext4_extent_idx的起始逻辑块地址也是newext->ee_block，直到第at层。

因此，我们看到ext4_ext_split()最核心的作用是：at一层的ext4_extent B+树有空闲entry，则从at层开始创建新的索引节点和叶子节点，建立这些新的索引节点和叶子节点彼此的物理块号联系。然后把path[depth].p_ext后边的ext4_extent结构移动到新的叶子节点，把path[at~depth-1].p_idx这些索引节点后边的ext4_extent_idx结构依次移动到新创建的索引节点。这样要么老的path[depth].p_ext所在叶子节点有了空闲的ext4_extent entry，把newex插入到老的path[depth].p_ext所在叶子节点后边即可。或者新创建的at~denth的索引节点

和叶子节点，有大量空闲的entry，这些索引节点的起始逻辑块地址还是newext->ee_block，则直接把newext插入到新创建的叶子节点第一个ext4_extent结构即可。

最后，对ext4_ext_split简单总结: 凡是执行到ext4_ext_split()函数，说明ext4 extent B+树中与newext->ee_block有关的叶子节点ext4_extent结构爆满了。于是从ext4 extent B+树at那一层索引节点到叶子节点，针对每一层都创建新的索引节点，也创建叶子节点。还会尝试把索引节点path[at~depth].p_hdr指向的ext4_extent_idx结构的后边的ext4_extent_idx结构和path[depth].p_ext指向的ext4_extent结构后边的ext4_extent结构，移动到新创建的叶子节点和索引节点。这样可能保证ext4 extent B+树中，与newext->ee_block有关的叶子节点有空闲entry，能存放newext。

下边介绍里边最后执行的ext4_ext_insert_index()函数。

9 ext4_ext_insert_index ()函数源码解析

ext4_ext_insert_index()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_ext_insert_index(handle_t *handle, struct inode *inode, struct ext4_ext_path *curp, int logical, ext4_fsblk_t ptr){ struct ext4_extent_idx *ix; int len, err; ................ /*curp->p_idx是ext4 extent B+树起始逻辑块地址最接近传入的起始逻辑块地址map->m_lblk的ext4_extent_idx结构，现在是把新的ext4_extent_idx(起始逻辑块地址是logical,起始物理块号ptr)插入到curp->p_idx指向的ext4_extent_idx结构前后*/ if (logical > le32_to_cpu(curp->p_idx->ei_block)) { /*待插入的ext4_extent_idx结构起始逻辑块地址logical大于curp->p_idx的起始逻辑块地址， 就要插入curp->p_idx这个ext4_extent_idx后边，(curp->p_idx + 1)这个ext4_extent_idx后边。插入前，下边memmove先把(curp->p_idx+1)后边的所有ext4_extent_idx结构全向后移动一个ext4_extent_idx结构大小，然后把新的ext4_extent_idx插入到curp->p_idx + 1位置处*/ ix = curp->p_idx + 1; } else { /*待插入的ext4_extent_idx结构起始逻辑块地址logical更小，就插入到curp->p_idx这个ext4_extent_idx前边。插入前，下边memmove先把curp->p_idx后边的所有ext4_extent_idx结构全向后移动一个ext4_extent_idx结构大小，然后把新的ext4_extent_idx插入到curp->p_idx位置处*/ ix = curp->p_idx; } /*ix是curp->p_idx或者(curp->p_idx+1)。len是ix这个索引节点的ext4_extent_idx结构到索引节点最后一个ext4_extent_idx结构(有效的)之间所有的ext4_extent_idx结构个数。注意，EXT_LAST_INDEX(curp->p_hdr)是索引节点最后一个有效的ext4_extent_idx结构，如果索引节点只有一个ext4_extent_idx结构，那EXT_LAST_INDEX(curp->p_hdr)就指向这第一个ext4_extent_idx结构*/ len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1; if (len > 0) { //把ix后边的len个ext4_extent_idx结构向后移动一次ext4_extent_idx结构大小 memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx)); } //现在ix指向ext4_extent_idx结构是空闲的，用它保存要插入的逻辑块地址logial和对应的物理块号。相当于把本次要插入ext4 extent b+树的ext4_extent_idx插入到ix指向的ext4_extent_idx位置处 ix->ei_block = cpu_to_le32(logical); ext4_idx_store_pblock(ix, ptr); //索引节点有效的ext4_extent_idx增加一个，因为刚才新插入了一个ext4_extent_idx le16_add_cpu(&curp->p_hdr->eh_entries, 1); return err;}

这个函数简单多了：把新的索引节点ext4_extent_idx结构(起始逻辑块地址logical,物理块号ptr)插入到ext4 extent B+树curp->p_idx指向的ext4_extent_idx结构前后。插入的本质很简单，把curp->p_idx或者(curp->p_idx+1)后边的所有ext4_extent_idx结构全向后移动一个ext4_extent_idx结构大小，把新的ext4_extent_idx插入curp->p_idx或者(curp->p_idx+1)原来的位置。

10 ext4_ext_grow_indepth()函数源码解析

ext4_ext_grow_indepth()函数源码如下： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode, unsigned int flags, struct ext4_extent *newext){ struct ext4_extent_header *neh; struct buffer_head *bh; ext4_fsblk_t newblock; int err = 0; /*分配一个新的物理块，返回物理块号newblock。这个物理块4K大小，是本次新创建的索引节点或者叶子节点，将来会保存索引节点的头结构ext4_extent_header+N个ext4_extent_idx或者或者叶子结点ext4_extent_header+N个ext4_extent结构*/ newblock = ext4_ext_new_meta_block(handle, inode, NULL, newext, &err, flags); if (newblock == 0) return err; //bh映射到newblock这个物理块 bh = sb_getblk(inode->i_sb, newblock); .................. /*把ext4 extent B+树的根节点的数据(头结构ext4_extent_header+4个ext4_extent_idx或者叶子结点ext4_extent_header+4个ext4_extent结构)复制到bh->b_data。相当于把根节点的数据复制到上边新创建的物理块，腾空根节点*/ memmove(bh->b_data, EXT4_I(inode)->i_data, sizeof(EXT4_I(inode)->i_data)); /*neh指向bh首地址，这些内存的数据是前边向bh->b_data复制的根节点的头结构ext4_extent_header*/ neh = ext_block_hdr(bh);  //如果ext4 extent B+树有索引节点，neh指向的内存作为索引节点 if (ext_depth(inode)) neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0)); else//如果ext4 extent B+树没有索引节点，只有根节点，neh指向的内存作为叶子结点 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0)); neh->eh_magic = EXT4_EXT_MAGIC; ................... //现在neh又指向ext4 extent B+根节点 neh = ext_inode_hdr(inode); //根节点现在只有一个叶子节点的ext4_extent结构在使用或者只有一个索引节点的ext4_extent_idx结构在使用 neh->eh_entries = cpu_to_le16(1); /*这是把前边新创建的索引节点或者叶子节点的物理块号newblock记录到根节点第一个ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员。这样就建立了根节点与新创建的物理块号是newblock的叶子结点或索引节点的联系。因为通过根节点第一个ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员，就可以找到这个新创建的叶子节点或者索引节点的物理块号newblock*/ ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock); //如果neh->eh_depth是0，说明之前ext4 extent B+树深度是0，即只有根节点 if (neh->eh_depth == 0) { /*以前B+树只有根节点，没有索引节点。现在根节点作为索引节点，这是计算根节点最多可容纳的ext4_extent_idx结构个数，4*/ neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0)); /*以前B+树只有根节点，没有索引节点，根节点都是ext4_extent结构，现在B+树根节点下添加了newblock这个叶子节点。根节点成了根索引节点，因此原来第一个ext4_extent结构要换成ext4_extent_idx结构，下边赋值就是把原来的根节点第一个ext4_extent的起始逻辑块地址赋值给现在根节点的第一个ext4_extent_idx的起始逻辑块地址*/ EXT_FIRST_INDEX(neh)->ei_block = EXT_FIRST_EXTENT(neh)->ee_block; } ............. //ext4 extent B+树增加了一层索引节点或叶子结点，即物理块号是newblock的那个，树深度加1 le16_add_cpu(&neh->eh_depth, 1); ............. return err;}

这个函数只是针对ex->ee_block分配一个新的物理块，作为新的索引节点或者叶子节点添加到ext4 extent B+树根节点下方，这样相当于跟ext4 extent B+树增加了一层新的节点。然后建立这个新分配的节点与根节点的联系即可，相对简单多了。

ext4_extent 内核源码似乎并不多，但是它的逻辑相当复杂，很绕，尤其是ext4_extent b+树的增长、分割、创建的叶子节点和索引节点。看到最后，觉得这部分代码算法设计的很巧妙，并不是太多的代码实现了如此复杂的功能，牛！

三、ext4 extent内核源码流程讲解

1 ext4 extent B+树索引节点和叶子节点怎么建立联系

首先提一个问题，ext4 extent B+树的根节点、索引节点、叶子节点是怎么保存的呢？根节点共16*4=64字节大小，保存在struct ext4_inode_info的__le32    i_data[15]。索引节点和叶子节点的都是一个物理块大小，这里ext4文件系统一个物理块默认4K大小。保存索引节点和叶子节点4K数据的物理块都是调用ext4_ext_new_meta_block()函数在ext4文件系统分配的。先看下ext4 extent B+树的简单示意图：


第1层是根节点，第2层是索引节点，第3层是叶子节点。如图所示，根节点的ext4_extent_idx指向一个索引节点，索引节点的ext4_extent_idx指向一个叶子节点。可以看到ext4_extent_idx在ext4 extent B+树中起着非常重要的索引作用，那怎么通过ext4_extent_idx找打它指向的索引节点和叶子节点呢？先看下它的数据结构 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_extent_idx { //起始逻辑块地址 __le32 ei_block;  //由ei_leaf_lo和ei_leaf_hi组成起始逻辑块地址对应的物理块地址 __le32 ei_leaf_lo; __le16 ei_leaf_hi; __u16 ei_unused;};

一个叶子节点或者索引节点都是占一个物理块大小，这里ext4文件系统一个物理块默认是4K。也就是说，一个叶子节点或者索引节点的数据都是4K大小。并且，叶子节点和索引节点的物理块号保存在ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员。因此，正是通过ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi的成员，找到叶子节点或者索引节点物理块号，然后就可以访问叶子节点的4K数据(ext4_extent_header+N个ext4_extent数据)，或者访问索引节点的4K数据(ext4_extent_header+N个ext4_extent_idx数据)。这就是我们前边说的通过一个ext4_extent_idx找到它指向的索引节点或者叶子节点的原理。

好的，我们对上图做个简答改造，如下图所示。表上ext4_extent_idx和ext4_extent代表的逻辑块地址，我们这里演示一下怎么在ext4 extent b+树查找逻辑块地址5映射的物理块地址。

首先struct ext4_inode_info的__le32   i_data[15]保存的是ext4 extent b+树根节点的数据：1个ext4_extent_header结构+4个ext4_extent_idx结构(也有可能是1个ext4_extent_header结构+4个ext4_extent结构，以上边的示意图为准)。找到根节点中起始逻辑块地址最接近5并且小于等于5的ext4_extent_idx结构，显然肯定是根节点的第一个ext4_extent_idx位置处的那个ext4_extent_idx结构，我们给它编号c0。

继续，通过该ext4_extent_idx的成员ei_leaf_lo和ei_leaf_hi计算出它指向的索引节点的物理块块号。读取这个物理块号中的索引节点节点的4K数据，是1个ext4_extent_header结构+N个ext4_extent_idx结构。好的，现在就有了示意图中，ext4 extent b+树第2层最左边的索引节点的数据。找到该索引节点中起始逻辑块地址最接近5并且小于等于5的ext4_extent_idx结构，显然是该索引节点中的第一个ext4_extent_idx位置处的那个ext4_extent_idx结构，我们给它编号d0。

接着，知道了索引节点中的编号d0的ext4_extent_idx结构，通过其成员ei_leaf_lo和ei_leaf_hi计算出它指向的叶子节点的物理块号，最后读取这个物理块号中的叶子节点的4K数据，是1个ext4_extent_header结构+N个ext4_extent结构。好的，有了叶子节点的数据，找到该叶子节点中起始逻辑块地址最接近5并且小于等于5的ext4_extent结构，显然就是编号的e0的ext4_extent。该ext4_extent包含了逻辑块地址0~10映射的物理块号，那肯定就可以计算出逻辑块地址5映射的物理块号。

2 ext4_extent插入ext4 extent B+树函数流程总结

Ok，下边聊另外一个问题，什么时候会用到ext4 extent B+树呢？我们看一个函数流程ext4_readpage()->mpage_readpages()->ext4_get_block()->_ext4_get_block()->ext4_map_blocks()->ext4_ext_map_blocks()，这是一个典型的ext4文件系统读文件的流程。里边有一个核心操作是，把应用层读文件的逻辑地址转成实际保存文件数据的物理块地址，有个这个物理块地址，才能从磁盘读到文件数据。而ext4_ext_map_blocks()正是完成文件逻辑地址与物理块地址映射的核心函数。这里先把ext4_ext_map_blocks()函数整体流程图贴下


最后执行ext4_ext_insert_extent()把新的ext4_extent插入到ext4 extent b+树，ext4_ext_insert_extent()函数是个重点函数，逻辑非常复杂，它的源码流程简单画下：


在执行ext4_ext_map_blocks()函数时，待映射的起始逻辑块地址是map->m_lblk，需要映射的逻辑块个数是map->m_len。再简单说下ext4_ext_find_extent()函数的作用，简单说：根据传入的起始逻辑块地址map->m_lblk，在ext4  extent b+树中从根节点到索引节点再到叶子节点，找到起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx和ext4_extent保存到struct ext4_ext_path *path[]数组。一下边示意图举个例子：

假设待映射的起始逻辑块地址map->m_lblk是5，则根节点起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx是c0，索引节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idx是d0，叶子节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent是e0。则进行如下赋值 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



path[0].p_idx = c0//指向根节点起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idxpath[1].p_idx = d0//指向索引节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent_idxpath[2].p_ext = e0//指向叶子节点中起始逻辑块地址最接近map->m_lblk的并且小于等于map->m_lblk的ext4_extent

struct ext4_ext_path *path[]结构体定义如下: 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



struct ext4_ext_path { /*ext4_ext_find_extent()中赋值，是索引节点时，是由ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi成员计算出的物理块号，这个物理块保存了下层叶子节点或者索引节点4K数据。是叶子节点时，是由ext4_extent结构的ee_start_hi和ee_start_lo成员计算出的物理块号，这个物理块号是ext4_extent的逻辑块地址映射的的起始物理块号*/ ext4_fsblk_t p_block; //当前索引节点或者叶子节点处于ext4 extent B+树第几层。ext4 extent B+树没有索引节点或者叶子节点时层数是0 __u16               p_depth; //起始逻辑块地址最接近map->m_lblk的ext4_extent struct ext4_extent *p_ext; //起始逻辑块地址最接近传map->m_lblk的ext4_extent_idx struct ext4_extent_idx *p_idx; //指向ext4 extent B+索引节点和叶子节点的头结点结构体 struct ext4_extent_header *p_hdr; //保存索引节点或者叶子节点4K数据的物理块映射的bh struct buffer_head *p_bh;};struct ext4_extent_idx { //起始逻辑块地址 __le32  ei_block;  /*由ei_leaf_lo和ei_leaf_hi一起计算出物理块号，这个物理块保存下层叶子节点或者索引节点4K数据。没错，索引节点ext4_extent_idx结构的ei_leaf_lo和ei_leaf_hi保存了下层索引节点或者叶子节点的物理块号，索引节点的ext4_extent_idx通过其ei_leaf_lo和ei_leaf_hi成员指向下层的索引节点或者叶子节点。这点非常重要*/ __le32  ei_leaf_lo; __le16  ei_leaf_hi; __u16   ei_unused;};struct ext4_extent { //起始逻辑块地址 __le32  ee_block; //逻辑块映射的连续物理块个数 __le16  ee_len;  //由ee_start_hi和ee_start_lo一起计算出起始逻辑块地址映射的起始物理块地址 __le16  ee_start_hi;  __le32  ee_start_lo; };

我们这里只展示了对它的成员p_idx和p_ext赋值，这两个成员最关键，其他成员没展示。

还有一点，ext4 extent内核源码中经常看到ex变量，它的定义是struct ext4_extent *ex，赋值是ex = path[depth].p_ext。depth是ext4 extent b+树深度，上边的示意图中ext4 extent b+树深度是2。如果ext4 extent b+树只有根节点，没有叶子节点或者索引节点，ext4 extent b+树深度是0.

ok，准备的比较充分了，下边我们针对几个典型场景，说明下ext4  extent b+树的形成过程涉及的核心函数流程。

2.1 ext4  extent B+树插入第一个ext4_extent函数流程

首先，最初ext4  extent B+树是空的


现在要先找到逻辑块地址0~10映射的物理块，起始逻辑块地址map->m_lblk=0，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=10。首先执行到ext4_ext_map_blocks()：

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]，但是一个都没找到，即ex = path[depth].p_ext=NULL。

  • 2：故ext4_ext_find_extent()函数最开头的ex = path[depth].p_ext后的if (ex)不成立。则执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(0)和需映射的逻辑块个数map->m_len(10)，分配10个连续的物理块并返回这10个物理块的第一个物理块号给newblock。

  • 3：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址，然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址0~10映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是10，表示本次逻辑块地址0~10成功映射了10个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址0~10映射关系的newex，插入到ext4  extent b+树。

接着执行ext4_ext_insert_extent()把newex插入到b+树：

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)) 不成立，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))成立，则执行goto has_space跳到has_space分支。

  • 2：因为nearex = path[depth].p_ext是NULL，if (!nearex)成立。执行nearex = EXT_FIRST_EXTENT(eh)令nearex指向根节点第一个ext4_extent位置处(nearex 定义是struct ext4_extent *nearex)。

  • 3：然后执行nearex->ee_block = newext->ee_block=0(本次映射的起始逻辑块地址0)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (0)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=10，这是本次成功映射的物理块个数。Ok，这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的第一个ext4_extent位置处。

插入后的效果如图所示，逻辑块地址0~10的ext4_extent保存到了根节点第一个ext4_extent位置处，给这个ext4_extent编号a0。


好的，简单总结一下：先找到本次逻辑块地址0~10映射的10个连续物理块(起始物理块号是newblock)。然后把本次映射的起始逻辑块地址0、本次映射的起始物理块号newblock、本次成功映射的物理块个数等信息赋值给struct ext4_extent newex，然后把newex中的这3个参数保存到ext4  extent B+树第一个ext4_extent位置处的ext4_extent结构。为了描述方便，我们这里把这个过程称为逻辑块地址是0~10的ext4_extent插入到ext4  extent B+树，后续会经常遇到类似描述。

2.2 ext4  extent B+树插入第2~4个ext4_extent函数流程

现在向ext4  extent B+树插入逻辑块地址是20~30的ext4_extent，函数流程是什么呢？

现在要先找到逻辑块地址20~30映射的物理块，起始逻辑块地址map->m_lblk=20，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=10。首先执行到ext4_ext_map_blocks():

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]，即ex = path[depth].p_ext=a0(根节点插入的第一个ext4_extent结构)。

  • 2：故ext4_ext_find_extent()函数开头的ex = path[depth].p_ext后的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))不成立，因为map->m_lblk不在a0的逻辑块的地址范围内。于是执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(20)和需映射的逻辑块个数map->m_len(10)，分配10个连续的物理块并返回这10个物理块的第一个物理块号给newblock。

  • 3：接着执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址20~30映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是10，表示本次逻辑块地址20~30成功映射了10个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址20~30映射关系的newex，插入到ext4  extent b+树。

继续，执行ext4_ext_insert_extent()把newex插入到b+树。

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是:判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并，可惜本次执行不到这些代码。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))成立，则执行goto has_space跳到has_space分支。

  • 3：因为nearex = path[depth].p_ext是a0(nearex 定义是struct ext4_extent *nearex)，if (!nearex)不成立。则跳到else分支，并且if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))成立，因为newext->ee_block是本次要插入的ext4_extent的起始逻辑块地址20，nearex->ee_block是根节点第一个ext4_extent结构的起始逻辑块地址0。

  • 4：于是执行if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))里的nearex++，令nearex指向a0后边的ext4_extent，也就是根节点第2个ext4_extent。

  • 5：最后，执行nearex->ee_block = newext->ee_block=20(本次映射的起始逻辑块地址20)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (20)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=10，本次成功映射的起始物理块个数。这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的第2个ext4_extent位置处，如下图所示。这里对这个新插入的ext4_extent编号a20。


好的，现在向ext4  extent B+树根节点又插入了逻辑块地址是50~60、80~90的2个ext4_extent，过程与逻辑块地址是20~10的ext4_extent插入到根节点类似，不再赘述。插入后效果如下：


2.3 ext4  extent B+树根节点下创建叶子节点

在上一节的基础上， ext4  extent B+树根节点ext4_extent已经全占满了，如果此时把逻辑块地址100~130插入到ext4  extent B+树，过程是什么呢？

现在要先找到逻辑块地址100~130映射的物理块，起始逻辑块地址map->m_lblk=100，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=30。首先执行到ext4_ext_map_blocks()

  • 1：先定义并定义struct ext4_extent newex变量，接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]，即ex = path[depth].p_ext=a80(根节点插入的第4个ext4_extent结构)。

  • 2：故ext4_ext_find_extent()函数开头的ex = path[depth].p_ext后的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))不成立，因为map->m_lblk不在a80的逻辑块的地址范围内。于是执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(100)和需映射的逻辑块个数map->m_len(30)，分配30个连续的物理块并返回这30个物理块的第一个物理块号给newblock。

  • 3：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址，然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址100~130映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是30，表示本次逻辑块地址100~130成功映射了30个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址100~130映射关系的newex，插入到ext4  extent b+树。

继续，执行ext4_ext_insert_extent()把newex插入到b+树：

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是：判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并，可惜本次执行不到这些代码。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))不成立，eh->eh_entries是根节点现在已经使用的ext4_extent个数，eh->eh_max是根节点最多能保存的ext4_extent个数，二者都是4，显然不成立。

  • 3：继续，if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))成立，newext->ee_block是本次插入的ext4_extent的起始逻辑块地址100，fex->ee_block是叶子节点最后一个ext4_extent的起始逻辑块地址80，显然成立。但执行里边的next = ext4_ext_next_leaf_block(path)因if (depth == 0)返回EXT_MAX_BLOCKS(b+树深度是0)，则返回ext4_ext_insert_extent()函数后if (next != EXT_MAX_BLOCKS)不成立。

  • 4：继续，执行到ext4_ext_create_new_leaf(handle, inode, flags, path, newext)函数。先执行在该函数里的while (i > 0 && !EXT_HAS_FREE_INDEX(curp))循环，退出循环时curp指向根节点，i是0，if (EXT_HAS_FREE_INDEX(curp))不成立，因为此时根节点4个ext4_extent全用完了，于是执行ext4_ext_grow_indepth(handle, inode, flags, newext)函数。

  • 5：继续，执行ext4_ext_create_new_leaf(handle, inode, flags, path, newext)-> ext4_ext_grow_indepth(handle, inode, flags, newext)。在ext4_ext_grow_indepth()函数里，在根节点下创建一层叶子节点，具体过程是执行newblock = ext4_ext_new_meta_block(handle, inode, NULL,newext, &err, flags)分配一个物理块，将来保存叶子节点的4K数据。并且把根节点原有的a0、a20、a50、a80这4个ext4_extent复制到叶子节点前个ext4_extent位置处。此时根节点的原有的4个ext4_extent变为ext4_extent_idr。并且在根节点第一个ext4_extent_idr位置处创建新的ext4_extent_idr结构，令它的起始逻辑块地址是0(原叶子节点第一个ext4_extent结构的起始逻辑块地址)，还把这个新创建的叶子节点的物理块号newblock保存到该ext4_extent_idr的ei_leaf_lo和ei_leaf_hi成员。这样通过根节点第一个ext4_extent_idr位置处的ext4_extent_idr结构的ei_leaf_lo和ei_leaf_hi成员，就能找到它指向叶子节点。此时的ext4 extent B+树如下所示，注意，此时b+树的深度depth由0变为1。根节点此时只有第一个ext4_extent_idr(编号b0)是有效的，剩余3个ext4_extent_idr并没有使用。通过根节点的b0这个ext4_extent_idr指向新创建的叶子节点。


  • 6：从ext4_ext_grow_indepth()返回到ext4_ext_create_new_leaf()，执行path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block),path)重新在ext4_extent b+树查找逻辑块地址最接近newext->ee_block的根节点的ext4_extent_idr和叶子节点ext4_extent。newext->ee_block=100，查找后path[]如下所示： 


	path[0].p_idx = b0//path[0].p_idx指向根节点中逻辑块地址最接近newext->ee_block的ext4_extent_idr
path[depth].p_ext = a80//depth=1， path[1].p_idx指向叶子节点中逻辑块地址最接近newext->ee_block的ext4_extent

  • 7：从ext4_ext_create_new_leaf()回到ext4_ext_insert_extent()函数，因为nearex = path[depth].p_ext是a80(nearex 定义是struct ext4_extent *nearex)，if (!nearex)不成立。继续，if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))成立，newext->ee_block是本次要插入的ext4_extent的起始逻辑块地址100，nearex->ee_block是叶子节点第4个ext4_extent结构的起始逻辑块地址90。于是执行该if判断里的nearex++，令nearex指向a80后边的ext4_extent，也就是叶子节点第5个ext4_extent。最后，执行nearex->ee_block = newext->ee_block=100(本次映射的起始逻辑块地址100)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (90)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=30，这是本次成功映射的起始物理块个数。这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的叶子节点第5个ext4_extent位置处，如下图所示。这里对这个新插入的ext4_extent编号a100。


2.4 ext4  extent B+树向叶子节点插入ext4_extent

在上一节基础上，向ext4  extent B+树插入逻辑块地址是150~180的ext4_extent。

现在要先找到逻辑块地址150~180映射的物理块，起始逻辑块地址map->m_lblk=150，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=30。首先执行到ext4_ext_map_blocks()：

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]。此时ext4  extent B+树深度depth是1，则ext4_ext_find_extent()执行后的情况是： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



path[0].p_idx = b0//path[0].p_idx指向根节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即根节点第一个ext4_extent_idr结构，即b0path[depth].p_ext = a100//depth=1 ，path[1].p_idx指向叶子节点中逻辑块地址最接近map->m_lblk的ext4_extent，叶子节点第5个ext4_extent结构，即a100

则ex = path[depth].p_ext=a100

  • 2：继续， ext4_ext_find_extent()后边的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))不成立，因为map->m_lblk不在a100的逻辑块的地址范围内。于是执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(150)和需映射的逻辑块个数map->m_len(30)，分配30个连续的物理块并返回这30个物理块的第一个物理块号给newblock。

  • 3：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址，然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址150~180映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是30，表示本次逻辑块地址150~180成功映射了30个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址150~180映射关系的newex，插入到ext4  extent b+树。

继续，执行ext4_ext_insert_extent()把newex插入到b+树：

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是:判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并，可惜本次执行不到这些代码。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))成立，则执行goto has_space跳到has_space分支。

  • 3：因为nearex = path[depth].p_ext是a100(nearex 定义是struct ext4_extent *nearex)，if (!nearex)不成立。则跳到else分支，并且if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))成立，因为newext->ee_block是本次要插入的ext4_extent的起始逻辑块地址150，nearex->ee_block是叶子节点第5个ext4_extent结构的起始逻辑块地址100。

  • 4：于是执行if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))里的nearex++，令nearex指向a100后边的ext4_extent，也就是叶子节点第6个ext4_extent。

  • 5：最后，执行nearex->ee_block = newext->ee_block=150(本次映射的起始逻辑块地址150)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (150)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=30，这是本次成功映射的起始物理块个数。这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的叶子节点第6个ext4_extent位置处，如下图所示。这里对这个新插入的ext4_extent编号a150。


2.5 ext4  extent B+树创建叶子节点

在上一小节基础上，继续向叶子节点插入ext4_extent，把叶子节点的ext4_extent全用完，如下图所示：


此时向ext4  extent B+树插入逻辑块地址 300~320的ext4_extent时，函数流程是什么呢？

现在要先找到逻辑块地址300~320映射的物理块，起始逻辑块地址map->m_lblk=300，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=20。首先执行到ext4_ext_map_blocks()

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]。此时ext4  extent B+树深度depth是1，则ext4_ext_find_extent()执行后的情况是： 


	
	
    
		
		
  • 
			
		
    • 

		
  • 
			
		
    • 

	



path[0].p_idx = b0//path[0].p_idx指向根节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即根节点第一个ext4_extent_idr结构，即b0path[depth].p_ext = a280//depth=1 ，path[1].p_idx指向叶子节点中逻辑块地址最接近map->m_lblk的ext4_extent，叶子节点最后一个ext4_extent结构，即a280

则ex = path[depth].p_ext=a280

  • 2：故ext4_ext_find_extent()函数开头的ex = path[depth].p_ext后的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))不成立，因为map->m_lblk不在a280的逻辑块的地址范围内。于是执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(300)和需映射的逻辑块个数map->m_len(20)，分配20个连续的物理块并返回这20个物理块的第一个物理块号给newblock。

  • 3：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址，然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址300~320映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是20，表示本次逻辑块地址300~320成功映射了30个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址300~320映射关系的newex插入到ext4  extent b+树。

继续，执行ext4_ext_insert_extent()把newex插入到b+树：

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是:判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并，可惜本次执行不到这些代码。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))不成立，eh->eh_entries是叶子节点现在已经使用的ext4_extent个数，eh->eh_max是叶子节点最多能保存的ext4_extent个数，现在叶子节点的ext4_extent全用完了，eh->eh_entries等于eh->eh_max，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))显然不成立。

  • 3：继续，if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))成立，newext->ee_block是本次插入的ext4_extent的起始逻辑块地址300，fex->ee_block是叶子节点最后一个ext4_extent的起始逻辑块地址280，显然成立。执行到里边的next = ext4_ext_next_leaf_block(path)函数，if (depth == 0)不成立，因为此时b+树深度depth是1。然后，执行depth--变为0，继续执行到while (depth >= 0)循环。第一次循环，if (path[depth].p_idx != EXT_LAST_INDEX(path[depth].p_hdr))不成立，因为此时path[depth].p_idx是根节点第1个ext4_extent_idx位置处的b0，而ext4 extent b+树根节点此时只有ext4_extent_idx即b0，因此b0就是根节点最后一个ext4_extent_idx。故if (path[depth].p_idx != EXT_LAST_INDEX(path[depth].p_hdr))不成立，于是执行depth—后，depth是负数，退出while (depth >= 0)循环 ，ext4_ext_next_leaf_block()函数返回EXT_MAX_BLOCKS。回到ext4_ext_insert_extent()函数，if (next != EXT_MAX_BLOCKS)不成立。

  • 4：继续，执行到ext4_ext_create_new_leaf(handle, inode, flags, path, newext)函数。先执行在该函数里的while (i > 0 && !EXT_HAS_FREE_INDEX(curp))循环，退出循环时curp指向根节点，i是0，if (EXT_HAS_FREE_INDEX(curp))成立，因此此时根节点只用了一个ext4_extent_idx即b0，还剩下3个空闲的ext4_extent_idx 。于是执行ext4_ext_split(handle, inode, flags, path, newext, i)函数。

  • 5：继续，来到ext4_ext_split()函数，形参at是0，if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr))不成立，因为path[depth].p_ext正是叶子节点最后一个ext4_extent即a280。于是执行else分支的border = newext->ee_block，赋值本次要插入的ext4_extent的起始逻辑块地址300。然后执行for (a = 0; a < depth - at; a++)里的newblock = ext4_ext_new_meta_block(handle, inode, path,newext, &err, flags)分配一个物理块，物理块号是newblock，循环只执行一次。这个物理块将来新创建的叶子节点使用，保存叶子节点的4K数据！接着执行bh = sb_getblk(inode->i_sb, newblock)令bh映射newblock的物理块。接着执行neh = ext_block_hdr(bh)及以下的几行代码，这是对新分配的叶子节点头结构ext4_extent_header的赋值。继续执行，m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++，计算结果是m=0，因为path[depth].p_ext就是老的叶子节点最后一个ext4_extent。后边的代码，if (m)不成立， k = depth - at – 1=0，while (k--)不成立。最后执行err = ext4_ext_insert_index(handle, inode, path + at,le32_to_cpu(border), newblock)，border = newext->ee_block即本次要插入的ext4_extent的起始逻辑块地址300，newblock是保存新创建的叶子节点数据的物理块号，path + at就是path+0.。

  • 6：执行到ext4_ext_insert_index()函数，if (logical > le32_to_cpu(curp->p_idx->ei_block))成立，logical是border(本次要插入的ext4_extent的起始逻辑块地址300)，curp->p_idx在第1步已经指向根节点的第一个索引节点，即curp->p_idx=path[0].p_idx = b0，curp->p_idx->ei_block是0。则执行ix = curp->p_idx + 1令ix指向根节点第2个ext4_extent_idx位置处的ext4_extent_idx。继续执行len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1=0，因为此时根节点只有第一个ext4_extent_idx位置处的b0是有效的，EXT_LAST_INDEX(curp->p_hdr)实际正是指向b0。因此if (len > 0)不成立。然后ix->ei_block = cpu_to_le32(logical)=300，即border(本次要插入的ext4_extent的起始逻辑块地址300)，执行ext4_idx_store_pblock(ix, ptr)，这是把刚新创建的叶子节点的物理块号保存到根节点第2个ext4_extent_idx位置的ext4_extent_idx结构的成员ei_leaf_lo和ei_leaf_hi。最后执行le16_add_cpu(&curp->p_hdr->eh_entries, 1)令根节点有效ext4_extent_idx数由1加到2。此时ext4 extent b+树如下所示。b300就是刚才提的根节点第2个ext4_extent_idx，空的叶子节点是刚新创建的叶子节点。b300这个ext4_extent_idx结构的成员ei_leaf_lo和ei_leaf_hi保存了该叶子节点的4K数据的物理块号，b300这个ext4_extent_idx指向该叶子节点。


  • 7：从ext4_ext_insert_index()返回ext4_ext_split()，再返回到ext4_ext_create_new_leaf()，执行path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block),path)重新在ext4_extent查找逻辑块地址最接近newext->ee_block的根节点的ext4_extent_idr和叶子节点ext4_extent。newext->ee_block=300，查找后path[]如下所示： 


	path[0].p_idx = b300//path[0].p_idx指向根节点中逻辑块地址最接近newext->ee_block的ext4_extent_idr






	path[depth].p_ext = NULL//depth=1， path[1].p_idx指向叶子节点中逻辑块地址最接近newext->ee_block的ext4_extent，但是这个新创建的叶子节点是空的

  • 8：从ext4_ext_create_new_leaf()回到ext4_ext_insert_extent()函数，因为nearex = path[depth].p_ext是NULL，if (!nearex)成立。执行nearex = EXT_FIRST_EXTENT(eh)令nearex指向新创建的叶子节点第一个ext4_extent位置处(nearex 定义是struct ext4_extent *nearex)。

  • 9：然后执行nearex->ee_block = newext->ee_block=300(本次映射的起始逻辑块地址300)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (300)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=20，这是本次成功映射的起始物理块个数。ok，这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的第一个ext4_extent位置处。如下是插入后的示意图，newex就是a300。

2.6 ext4  extent B+树创建索引节点

在上一节的基础上，继续向该ext4  extent B+树添加ext4_extent，把根节点的b300这个ext4_extent_idx指向的叶子节点的ext4_extent全占满(过程与2.4类似)。然后在根节点第3和第4个ext4_extent_idx位置处，创建新的ext4_extent_idx结构，接着再创建他们指向的叶子节点，继续向这些添加插入ext4_extent(过程与2.5类似)，直到把ext4  extent B+树的ext4_extent全占满，如下如所示：


为了演示方便，省略了叶子节点部分ext4_extent演示，此时向ext4  extent B+树插入逻辑块地址是1300~1320的ext4_extent时，函数流程是什么呢？

现在要先找到逻辑块地址1300~1320映射的物理块，起始逻辑块地址map->m_lblk=1300，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=20。首先执行到ext4_ext_map_blocks()，

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]。此时ext4  extent B+树深度depth是1，则ext4_ext_find_extent()执行后的情况是： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = b900//path[0].p_idx指向根节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即根节点最后一个ext4_extent_idr结构，即b900path[depth].p_ext = a1200//depth=1 ，path[1].p_idx指向叶子节点中逻辑块地址最接近map->m_lblk的ext4_extent，是第4个叶子节点最后一个ext4_extent结构，即a1200



	则ex = path[depth].p_ext=a1200

  • 2：故ext4_ext_find_extent()函数开头的ex = path[depth].p_ext后的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))不成立，因为map->m_lblk不在a1200的逻辑块的地址范围内。于是执行到newblock = ext4_mb_new_blocks(handle, &ar, &err)针对本次需映射的起始逻辑块地址map->m_lblk(1300)和需映射的逻辑块个数map->m_len(20)，分配20个连续的物理块并返回这20个物理块的第一个物理块号给newblock。

  • 3：接着先执行newex.ee_block = cpu_to_le32(map->m_lblk)赋值本次要映射的起始逻辑块地址1300，然后执行ext4_ext_store_pblock(&newex, newblock + offset)把本次逻辑块地址1300~1320映射的起始物理块号newblock保存到newex的ee_start_lo和ee_start_hi成。并执行newex.ee_len = cpu_to_le16(ar.len)把成功映射的物理块数保存到newex.ee_len。ar.len是20，表示本次逻辑块地址1300~1320成功映射了20个物理块。最后，执行err = ext4_ext_insert_extent(handle, inode, path,&newex, flags)把代表本次逻辑块地址1300~1320映射关系的newex插入到ext4  extent b+树。

继续，执行ext4_ext_insert_extent()把newex插入到b+树：

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是:判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并，可惜本次执行不到这些代码。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))不成立，eh->eh_entries是叶子节点现在已经使用的ext4_extent个数，eh->eh_max是根节点最多能保存的ext4_extent个数，现在叶子节点的ext4_extent全用完了，eh->eh_entries等于eh->eh_max，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))显然不成立。

  • 3：继续，if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))成立，newext->ee_block是本次插入的ext4_extent的起始逻辑块地址1300，fex->ee_block是叶子节点最后一个ext4_extent的起始逻辑块地址1200，显然成立。执行到里边的next = ext4_ext_next_leaf_block(path)函数，if (depth == 0)不成立，因为此时b+树深度depth是1。然后，执行depth--变为0，继续执行到while (depth >= 0)循环。第一次循环，if (path[depth].p_idx != EXT_LAST_INDEX(path[depth].p_hdr))不成立，因为此时path[depth].p_idx是根节点第4个ext4_extent_idx位置处的b900，而ext4 extent b+树根节点最后一个ext4_extent_idx正是b900。故if (path[depth].p_idx != EXT_LAST_INDEX(path[depth].p_hdr))不成立，于是执行depth--后，depth是负数，退出while (depth >= 0)循环 ，ext4_ext_next_leaf_block()函数返回EXT_MAX_BLOCKS。回到ext4_ext_insert_extent()函数，if (next != EXT_MAX_BLOCKS)不成立。

  • 4：继续，执行到ext4_ext_create_new_leaf(handle, inode, flags, path, newext)函数。先执行在该函数里的while (i > 0 && !EXT_HAS_FREE_INDEX(curp))循环，退出循环时curp指向根节点，i是0，if (EXT_HAS_FREE_INDEX(curp))不成立，因为此时根节点4个ext4_extent_idx全用完了，于是执行ext4_ext_grow_indepth(handle, inode, flags, newext)函数。

  • 5：继续，执行ext4_ext_create_new_leaf(handle, inode, flags, path, newext)-> ext4_ext_grow_indepth(handle, inode, flags, newext)。在ext4_ext_grow_indepth()函数里，在根节点下创建一层索引节点，具体过程是执行newblock = ext4_ext_new_meta_block(handle, inode, NULL,newext, &err, flags)分配一个物理块，将来保存索引节点的4K数据。并且把根节点原有的b0、b300、b600、b900这4个ext4_extent_idr复制到新创建的索引节点前个ext4_extent_idr位置处。并且，在根节点第一个ext4_extent_idr位置处创建新的ext4_extent_idr结构，令它的起始逻辑库地址是0(原来在这里的索引节点b0的的起始逻辑块地址)，然后把这个新创建的索引节点的物理块号newblock保存到该ext4_extent_idr的ei_leaf_lo和ei_leaf_hi成员。这样通过根节点第一个ext4_extent_idr位置处的ext4_extent_idr的ei_leaf_lo和ei_leaf_hi成员，就能找到它指向索引节点。此时的ext4 extent B+树如下所示，注意，此时b+树的深度depth由1变为2。根节点此时只有第一个ext4_extent_idr(编号c0)是有效的，剩余3个ext4_extent_idr并没有使用。通过根节点的c0这个ext4_extent_idr指向新创建的索引节点。

  • 6：从ext4_ext_grow_indepth()返回到ext4_ext_create_new_leaf ()，执行path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block),path)重新在ext4_extent b+树查找逻辑块地址最接近newext->ee_block的根节点的ext4_extent_idr和叶子节点ext4_extent。newext->ee_block=1300，查找后path[]如下所示： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = c0//path[0].p_idx指向根节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[1].p_idx =b900//path[1].p_idx指向索引节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[depth].p_ext = a1200//depth=2， path[2].p_idx指向叶子节点中逻辑块地址最接近newext->ee_block的ext4_extent

  • 7：继续执行，ext4_ext_create_new_leaf ()函数中，if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max)却成立了。因为path[depth].p_ext指向的根节点ext4_extent全用满了，path[depth].p_hdr->eh_entries表示该叶子节点已经使用的ext4_extent数，path[depth].p_hdr->eh_max表示叶子节点最多能容纳多少个ext4_extent。显然该if成立，于是执行goto repeat，跳转到ext4_ext_create_new_leaf ()函数的repeat分支，执行while (i > 0 && !EXT_HAS_FREE_INDEX(curp))循环。等该循环退出后，i=1，curp指向索引节点，if (EXT_HAS_FREE_INDEX(curp))成立，因为索引节点只用了ext4_extent_idr，还有大把空闲的ext4_extent_idr。接着就执行ext4_ext_split(handle, inode, flags, path, newext, i)函数了。

  • 8：来到ext4_ext_split()函数，形参at是1，if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr))不成立，因为path[depth].p_ext正是叶子节点最后一个ext4_extent即a1200。于是执行else分支的border = newext->ee_block，赋值本次要插入的ext4_extent的起始逻辑块地址1300。然后执行for (a = 0; a < depth - at; a++)里的newblock = ext4_ext_new_meta_block(handle, inode, path,newext, &err, flags)分配一个物理块，物理块号是newblock，循环只执行一次。这个物理块就是新分配的叶子节点！接着执行bh = sb_getblk(inode->i_sb, newblock)令bh映射newblock的物理块。接着执行neh = ext_block_hdr(bh)及以下的几行代码，这是对新分配的叶子节点简单赋值。继续执行，m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++，计算结果是m=0，因为path[depth].p_ext就是老的a1200所在的叶子节点最后一个ext4_extent。后边的代码，if (m)不成立， k = depth - at – 1=0，while (k--)不成立。最后执行err = ext4_ext_insert_index(handle, inode, path + at,le32_to_cpu(border), newblock)，border = newext->ee_block是本次要插入的ext4_extent的起始逻辑块地址1300，newblock是保存新创建的叶子节点数据的物理块号，path + at就是path+1。

  • 9：执行到ext4_ext_insert_index()函数，if (logical > le32_to_cpu(curp->p_idx->ei_block))成立，logical是border(本次要插入的ext4_extent的起始逻辑块地址1300)，curp->p_idx在第5步已经指向索引节点的第4个ext4_extent_idx，即curp->p_idx=path[1].p_idx = b900。则执行ix = curp->p_idx + 1令ix指向索引节点第5个ext4_extent_idx位置处的ext4_extent_idx。继续执行len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1=0，因为此时索引节点只有前4个ext4_extent_idx是有效的，EXT_LAST_INDEX(curp->p_hdr)实际正是指向b900。因此if (len > 0)不成立。然后ix->ei_block = cpu_to_le32(logical)=1300，即border(本次要插入的ext4_extent的起始逻辑块地址1300)。执行ext4_idx_store_pblock(ix, ptr)，这是把刚新创建的叶子节点的物理块号保存到索引节点第5个ext4_extent_idx位置的ext4_extent_idx结构的成员ei_leaf_lo和ei_leaf_hi。最后执行le16_add_cpu(&curp->p_hdr->eh_entries, 1)令索引节点有效ext4_extent_idx数由4加1。此时ext4 extent b+树如下所示，b1300就是刚才提的索引节点第5个ext4_extent_idx，空的叶子节点是刚新创建的叶子节点。b1300这个ext4_extent_idx结构的成员ei_leaf_lo和ei_leaf_hi保存了该叶子节点的4K数据的物理块号，b1300这个ext4_extent_idx指向该叶子节点。


  • 10：从ext4_ext_insert_index()返回ext4_ext_split()，再返回到ext4_ext_create_new_leaf()，执行path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block),path)重新在ext4_extent b+树查找逻辑块地址最接近newext->ee_block的根节点的ext4_extent_idr和叶子节点ext4_extent。newext->ee_block=1300，查找后path[]如下所示： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = c0//path[0].p_idx指向根节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[1].p_idx =1300//path[1].p_idx指向索引节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[depth].p_ext = NULL//depth=2， path[2].p_idx指向叶子节点中逻辑块地址最接近newext->ee_block的ext4_extent，但这个叶子节点是空的。

  • 12：从ext4_ext_create_new_leaf()回到ext4_ext_insert_extent()函数，因为nearex = path[depth].p_ext是NULL，if (!nearex)成立。执行nearex = EXT_FIRST_EXTENT(eh)令nearex指向新创建的叶子节点第一个ext4_extent位置处(nearex 定义是struct ext4_extent *nearex)。

  • 13：然后执行nearex->ee_block = newext->ee_block=1300(本次映射的起始逻辑块地址1300)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block (1300)映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=20，这是本次成功映射的起始物理块个数。Ok，这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树的b1300指向的叶子节点的第一个ext4_extent位置处。如下是插入后的示意图，newex就是a1300。

2.7 ext4  extent B+树继续插入ext4_extent

在上一节的基础上，继续向b1300指向的叶子节点插入逻辑块地址是1330~1350的ext4_extent，函数流程是什么呢？这个函数流程2.4节类似，在ext4_ext_map_blocks() 函数中执行ext4_ext_find_extent()后path如下所示： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = c0//path[0].p_idx指向根节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[1].p_idx =1300//path[1].p_idx指向索引节点中逻辑块地址最接近newext->ee_block的ext4_extent_idrpath[depth].p_ext = a1300//depth=2， path[2].p_idx指向叶子节点中逻辑块地址最接近newext->ee_block的ext4_extent，但这个叶子节点是空的。

后续的流程2.4节就很相似了，按部就班把逻辑块地址是1330~1350的ext4_extent插入ext4 extent b+树，这里不再详细介绍了。

继续，一直向ext4 extent b+树b1300指向的叶子节点插入ext4_extent，直到把该叶子节点的ext4_extent全占满，如下图所示：

继续，ext4 extent B+树第2层的索引节点前5个ext4_extent_idx(b0、b300、b600、b900、b1300)指向的叶子节点的ext4_extent全占满了，此时如果向ext4 extent B+树插入逻辑块地址是1600~1620的ext4_extent该怎么办？下边的示意图演示了：


显然，就是在索引节点的第6个ext4_extent_idx(该ext4_extent_idx此时空闲，并未使用)位置处，创建新的ext4_extent_idx，它的起始逻辑块地址1600，我们给它编号b1600。然后创建b1600指向的叶子节点，把逻辑块地址是1600~1620的ext4_extent插入到该叶子节点第一个ext4_extent位置处。这个过程的函数流程与2.5类似，无非ext4 extent B+树此时深度由1变为2。

加下来，继续向b1600这个ext4_extent_idx指向的叶子节点的插入ext4_extent，最后把该叶子节点所有的ext4_extent全占满了。再插入新的ext4_extent时，则在索引节点第7个ext4_extent_idx位置处(b1600后边的那个ext4_extent_idx, 该ext4_extent_idx此时空闲，并未使用)创建新的ext4_extent_idx，然后为这个新的ext4_extent_idx创建叶子节点，把新的ext4_extent插入到该叶子节点第一个ext4_extent位置处。这个过程跟前边b1300那个ext4_extent_idx指向的叶子节点的ext4_extent全占满时，向ext4 extent B+树插入逻辑块地址是1600~1620的ext4_extent的过程是类似的。

加大力度，随着不断向向ext4 extent B+树新的ext4_extent，第2层的索引节点的所有ext4_extent_idx全部被使用，这些ext4_extent_idx指向的叶子节点的ext4_extent也全占满。如下图所示：

在上文讲解ext4_extent b+树形成，最后的ext4_extent b+树形态如下。它的函数流程是什么呢？虽然很复杂，但是上文介绍的知识点也是可以完全解释的，这里就不再啰嗦了。

3 ext4_exent B+树ext4_extent的分割

第2节向ext4_exent b+树插入的ext4_extent的逻辑块地址都是不连续的，如果现在要插入的逻辑块地址与ext4_exent b+树已有的ext4_extent的逻辑块地址有重叠，会发生什么？函数流程是什么？流程是相当复杂，这节主要介绍这个。

首先看下如下示意图，ext4_exent b+树深度是3，此时向ext4_exent b+树插入逻辑块地址是635~685的ext4_extent，函数流程是什么呢？

现在要先找到逻辑块地址635~685映射的物理块，起始逻辑块地址map->m_lblk=635，要映射的逻辑块个数(或者说要分配的连续物理块个数)map->m_len=50。首先执行到ext4_ext_map_blocks()，

  • 1：先定义并定义struct ext4_extent newex变量。接着执行ext4_ext_find_extent()，试图查找逻辑块地址最接近map->m_lblk的索引节点ext4_extent_idr结构和叶子节点ext4_extent结构保存到path[]。此时ext4  extent B+树深度depth是3，则ext4_ext_find_extent()执行后的情况是： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = d0//path[0].p_idx指向根节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即根节点第一个ext4_extent_idr结构，即d0path[1].p_idx = c0//path[0].p_idx指向第2层索引节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即c0path[2].p_idx = b600//path[0].p_idx指向第3层索引节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即 b600path[depth].p_ext = a630//depth=3 ，path[1].p_idx指向叶子节点中逻辑块地址最接近map->m_lblk的ext4_extent，即a630

则ex = path[depth].p_ext=a630

  • 2：故ext4_ext_find_extent()函数开头的ex = path[depth].p_ext后的if (ex)成立，但是if (in_range(map->m_lblk, ee_block, ee_len))成立，因为map->m_lblk在a630的逻辑块的地址范围内。于是执行里边的newblock = map->m_lblk - ee_block + ee_start，map->m_lblk是本次映射的起始逻辑块地址，ee_block是ex(a630)的起始逻辑块地址，ee_start是ex(a630)起始逻辑块地址映射的物理块地址。这是根据ex(a630)的逻辑块地址与物理块地址映射的线性关系，计算map->m_lblk映射的起始物理块地址，肯定在ex(a630)的逻辑块地址映射的物理块地址范围内。接着执行allocated = ee_len - (map->m_lblk - ee_block)计算成功映射的的物理块个数，ee_len是ex(a630)逻辑块地址630~650映射的物理块个数，即20。map->m_lblk是635， ee_block是630。因此本次映射的逻辑块范围635~685内，只有前半段635~650的逻辑块地址完成了映射，映射了15个物理块。后半段逻辑块地址651~685映射的物理块该怎么办？

  • 3：继续，假设ex是未初始化状态，if (!ext4_ext_is_uninitialized(ex))不成立，然后执行ext4_ext_handle_uninitialized_extents(handle, inode, map, path, flags,allocated, newblock)，在高版本内核该函数名字改为了ext4_ext_handle_unwritten_extents()。这个函数里验证主要执行了ext4_ext_convert_to_initialized(handle, inode, map, path, flags)函数。于是转到ext4_ext_convert_to_initialized()。

  • 4：进入ext4_ext_convert_to_initialized()函数，if ((map->m_lblk == ee_block) &&(map_len < ee_len) &&(ex > EXT_FIRST_EXTENT(eh)))不成立，因为map_len(本次逻辑块地址635~685映射的物理块数，50)大于ee_len(ex逻辑块地址映射的物理块数20)。继续执行if (allocated) 不成立则执行else分支的allocated = ee_len - (map->m_lblk - ee_block)=20-(635-630)=15，这是计算本次要映射的逻辑块地址635~685在ex的已经完成映射的逻辑块地址630~(630+20)内，捞到已经映射的20个物理块。继续，下边的if (max_zeroout && (ee_len <= max_zeroout))和if (max_zeroout && (allocated > map->m_len))测试都不成立，于是执行allocated = ext4_split_extent(handle, inode, path,&split_map, split_flag, flags)将ex的逻辑块地址进行分割。

  • 5：继续，进入ext4_split_extent()函数。if (map->m_lblk + map->m_len < ee_block + ee_len) 不成立，因为map->m_lblk + map->m_len(本次要映射的结束逻辑块地址，685)大于ex的逻辑块结束地址650。继续，执行path = ext4_ext_find_extent(inode, map->m_lblk, path)没啥用。if (map->m_lblk >= ee_block)成立，map->m_lblk本次要映射的起始逻辑块地址635，ee_block是ex的起始逻辑块地址630。接着执行ext4_split_extent_at(handle, inode, path,map->m_lblk, split_flag1, flags)把ex的逻辑块地址进行分割，630~650分割成630~635和635~650两段。

  • 6：进入ext4_split_extent_at()函数。if (split == ee_block)不成立。执行下边的代码ex->ee_len = cpu_to_le16(split - ee_block)；ex2 = &newex；ex2->ee_block = cpu_to_le32(split)；ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block))；ext4_ext_store_pblock(ex2, newblock)。这就是把ex的逻辑块地址630~650和物理块地址进行了跟个，ex只保存了逻辑块地址前半段630~635的映射关系，ex2或者newex保持了后半段逻辑块地址635~650的映射关系。然后执行ext4_ext_insert_extent(handle, inode, path, &newex, flags)把后半段的ex2插入ext4_extent b+树。

终于进入了久违的ext4_ext_insert_extent函数，newext此时是ex原来逻辑块地址630~650分割后的后半段635~650，即newext->ee_block=635，newext-> ee_len=650-635=15。ex此时的逻辑块地址只有630~635，这点需记住，下文经常用到ex。

  • 1：if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO))不成立，该if判断里边的代码作用是:判断newex跟ex、ex前边的ext4_extent结构、ex后边的ext4_extent结构逻辑块地址范围是否紧挨着，是的话才能将二者合并。不成立，最起码因为newex是未初始化状态，因此ext4_can_extents_be_merged(inode, ex, newext)肯定不成立。

  • 2：继续，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))不成立，eh->eh_entries是ex所在叶子节点现在已经使用的ext4_extent个数，eh->eh_max是该叶子节点最多能保存的ext4_extent个数，现在叶子节点的ext4_extent全用完了，eh->eh_entries等于eh->eh_max，if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))显然不成立。

  • 3：继续，if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))不成立，newext->ee_block是本次插入的ext4_extent的起始逻辑块地址635，fex->ee_block是叶子节点最后一个ext4_extent的起始逻辑块地址880，显然不成立。

  • 4：继续，执行到ext4_ext_create_new_leaf(handle, inode, flags, path, newext)函数。先执行在该函数里的while (i > 0 && !EXT_HAS_FREE_INDEX(curp))循环，退出循环时curp指向第2层的索引节点，i是1，if (EXT_HAS_FREE_INDEX(curp))成立，因此第2层的索引节点只用了一个ext4_extent_idx即c0，还剩下很多个空闲的ext4_extent_idx 。于是执行ext4_ext_split(handle, inode, flags, path, newext, i)函数。

  • 5：继续，来到ext4_ext_split()函数，形参at是1，if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr))成立，因为path[depth].p_ext是ex所在叶子节点的第2个ext4_extent即a630，不是叶子节点最后一个ext4_extent。于是border = path[depth].p_ext[1].ee_block，path[depth].p_ext[1]是ex后边的ext4_extent，也就是该叶子节点第3个ext4_extent，故path[depth].p_ext[1].ee_block=700。然后执行for (a = 0; a < depth - at; a++)里的newblock = ext4_ext_new_meta_block(handle, inode, path,newext, &err, flags)分配两个物理块，循环执行两次。这两个物理块，一个是将来新创建的叶子节点使用，保存叶子节点的4K数据，物理块号我们这里称为newblock1；一个是将来新创建的索引节点使用，保存索引节点的4K数据，物理块号我们这里称为newblock2。

  • 6: ext4_ext_split()函数中继续，执行bh = sb_getblk(inode->i_sb, newblock)令bh映射newblock1的物理块。接着执行neh = ext_block_hdr(bh)及以下的几行代码，这是对新创建的叶子节点头头结构ext4_extent_header的赋值。继续，m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++，计算结果是m大于0。path[depth].p_ext是叶子节点第2个ext4_extent，EXT_MAX_EXTENT(path[depth].p_hdr)是叶子节点最后一个ext4_extent，这是阶段叶子节点第2个ext4_extent到最后一个ext4_extent之间有多少个ext4_extent结构。后边的代码，if (m)里的memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m)，是把叶子节点path[depth].p_ext指向的ext4_extent(即ex，也是第2个ext4_extent a630)后的m个ext4_extent结构移动到前边新分配的叶子节点开头，该叶子节点就增加了m个ext4_extent结构。if (m) 里的le16_add_cpu(&path[depth].p_hdr->eh_entries, -m)，是path[depth].p_ext指向的叶子节点减少了m个ext4_extent结构。

  • 7：ext4_ext_split()函数中继续，k = depth - at – 1=1，while (k--)成立，该循环执行一次。这个循环里，先bh = sb_getblk(inode->i_sb, newblock)令bh指向物理块号是newblock2的物理块，这个物理块是新创建的索引节点使用。neh = ext_block_hdr(bh)即下边的几行代码，是对该索引节点的ext4_extent_header头结构赋值，fidx = EXT_FIRST_INDEX(neh)是令fidx指向该索引节点第一个ext4_extent_idx位置处的ext4_extent_idx，然后令fidx->ei_block = border，border前文提过是path[depth].p_ext指向的ext4_extent(即ex，也是第2个ext4_extent  a630)后边的ext4_extent的起始逻辑块地址，即700。接着执行ext4_idx_store_pblock(fidx, oldblock)，这是把上边新创建的叶子节点的物理块号newblock1保存到新创建的索引节点的第一个ext4_extent_idx结构(即fidx)的成员ei_leaf_lo和ei_leaf_hi。这样通过fidx就可以找到新创建的叶子节点。

  • 8：ext4_ext_split()函数中继续，执行while (k--)循环里的m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++。path[i].p_hdr是b600，这是计算b600所在索引节点中，b600到最后一个索引节点b2000之间的ext4_extent_idx个数。显然m大于0，于是执行memmove(++fidx, path[i].p_idx,sizeof(struct ext4_extent_idx) * m)把b600到最后一个索引节点b2000之间的m个ext4_extent_idx复制到新创建的索引节点第2个ext4_extent_idx位置处及后边。于是，创建的索引节点多了m个ext4_extent_idx结构(le16_add_cpu(&neh->eh_entries, m))，b600所在索引节点少了m个ext4_extent_idx结构(le16_add_cpu(&path[i].p_hdr->eh_entries, -m))。

  • 9：ext4_ext_split()函数中继续，while (k--)循环退出。最后执行err = ext4_ext_insert_index(handle, inode, path + at,le32_to_cpu(border), newblock)，border是path[depth].p_ext指向的ext4_extent(即ex，也是第2个ext4_extent  a630)后边的ext4_extent的起始逻辑块地址，即700。newblock(newblock2)是新创建的索引节点的物理块号，path + at是path+1。

  • 10：来到ext4_ext_insert_index()函数，if (logical > le32_to_cpu(curp->p_idx->ei_block))成立，logical是border(700)，curp->p_idx在第1步已经指向第2层节点的第一个索引节点c0，即curp->p_idx=path[1].p_idx = c0，curp->p_idx->ei_block是0。则执行ix = curp->p_idx + 1令ix指向第2层的索引节点第2个ext4_extent_idx位置处的ext4_extent_idx。继续执行len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1=0，因为此时第2层节点只有第一个ext4_extent_idx位置处的c0是有效的，EXT_LAST_INDEX(curp->p_hdr)实际正是指向c0。因此if (len > 0)不成立。然后ix->ei_block = cpu_to_le32(logical)=700，即border。执行ext4_idx_store_pblock(ix, ptr)，这是把刚新创建的索引节点的物理块号newblock2保存到第2层节点第2个ext4_extent_idx位置的ext4_extent_idx结构的成员ei_leaf_lo和ei_leaf_hi。最后执行le16_add_cpu(&curp->p_hdr->eh_entries, 1)令第2层节点有效ext4_extent_idx数由1加到2。此时ext4 extent b+树如下所示。加红的索引节点和叶子节点是新创建的，第2层的索引节点的c700就是前边说的ix指向的ext4_extent_idx。c700指向新创建的索引节点，这个索引节点的第一个ext4_extent_idx结构又指向新创建的叶子节点。标青色的叶子节点及其ext4_extent 和 标青色的索引节点的ext4_extent_idr都是从ext4 extent b+树原来的索引节点和叶子节点复制过来的，比如b900~b2000这些ext4_extent_idx原来在第3层索引节点b600后边，现在被复制到了新创建的索引节点上。a700~a880这些ext4_extent原来在b600指向的叶子节点 a630这个ext4_extent结构后边，现在被移动到了新创建的叶子节点。

  • 11：从ext4_ext_insert_index()返回ext4_ext_split()，再返回到ext4_ext_create_new_leaf()，执行path = ext4_ext_find_extent(inode, (ext4_lblk_t)le32_to_cpu(newext->ee_block),path)重新在ext4_extent查找逻辑块地址最接近newext->ee_block的索引节点的ext4_extent_idr和叶子节点ext4_extent。newext->ee_block可能都要忘了，它是要插入ext4 extent b+树的ext4_extent的起始逻辑块地址635，查找后path[]如下所示： 


	





    
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 
	
  • 
	
    • 



path[0].p_idx = d0//path[0].p_idx指向根节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即根节点第一个ext4_extent_idr结构，即d0path[1].p_idx = c0//path[0].p_idx指向第2层索引节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即c0path[2].p_idx = b600//path[0].p_idx指向第3层索引节点中逻辑块地址最接近map->m_lblk的ext4_extent_idr，即 b600path[depth].p_ext = a630//depth=3 ，path[1].p_idx指向叶子节点中逻辑块地址最接近map->m_lblk的ext4_extent，即a630

可以发现，ext4_ext_find_extent()执行后，path竟然与最开始一模一样。但是呢a630此时的逻辑块范围已经缩减为630~(635-1)。并且，a630后边的ext4_extent都是空的，有很多坑位了，这得感谢前边ext4_ext_split()函数。

  • 12：从ext4_ext_create_new_leaf()回到ext4_ext_insert_extent()函数，因为nearex = path[depth].p_ext=a630，不是NULL，if (!nearex)不成立。则执行else分支，又因为if (le32_to_cpu(newext->ee_block)> le32_to_cpu(nearex->ee_block))成立，newext->ee_block是本次要插入ext4 extent b+树的ext4_extent的起始逻辑块地址635，nearex->ee_block是a650的起始逻辑块地址630。则执行nearex++，令nearex++指向后边的一个ext4_extent结构，即a630后边的那个位置处的ext4_extent。len = EXT_LAST_EXTENT(eh) - nearex + 1后if (len > 0)不成立，因为EXT_LAST_EXTENT(eh)是a630所在叶子节点的最后一个有效的ext4_extent，就是a630，因为该叶子节点此时只有两个有效的ext4_extent，故len = EXT_LAST_EXTENT(eh) - nearex + 1=0。

  • 13：然后执行nearex->ee_block = newext->ee_block=635(本次映射的起始逻辑块地址635，逻辑块范围是635~650)；执行ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext))向nearex赋值本次起始逻辑块地址newext->ee_block映射的起始物理块地址；执行nearex->ee_len = newext->ee_len=650-635=15，这是本次成功映射的物理块个数。ok，这3个赋值后，就相当于把newex成功插入到了ext4  extent B+树a630所在叶子节点中第3个ext4_extent位置处，如下图所示，a635就是newex。


继续，我推测会执行ext4_ext_try_to_merge(handle, inode, path, nearex)，把a630和a635进行合并，合并后a630吞并了a635的逻辑块范围，a635消失，如下图所示。

折腾了一大圈，a630的逻辑块范围由630~650到630~650。但是总有效果的，a630所在的叶子节点有了很多空闲的ext4_extent，还分割产生了新的索引节点和叶子节点。

不得不服，ext4_extent 算法设计的真巧妙，几个函数不是太多的代码就完成了ext4_exent b+树针对ext4_extent结构的各种操作。内核开发者写的每一行代码真的是经过反复推敲的呀！不过ext4_extent内核代码逻辑真的复杂，在最后的举例+示意图下才算较为透彻的理解了。


登录阅读全文
声明： 本文转载自其它媒体或授权刊载，目的在于信息传递，并不代表本站赞同其观点和对其真实性负责，如有新闻稿件和图片作品的内容、版权以及其它问题的，请联系我们及时删除。（联系我们，邮箱：evan.li@aspencore.com ）
0
评论
  • 相关技术文库
  • C语言
  • 编程
  • 软件开发
  • 程序
下载排行榜
更多
评测报告
更多
最新精华
更多
原创博文
更多
EE直播间
更多
在线研讨会
更多
广告
白皮书下载
更多
最新资讯
阅读更多内容，狠戳这里