-
单片机到底是不是嵌入式？
一定有很多人都听说过嵌入式和单片机，但在刚开始接触时，不知道大家有没有听说过嵌入式就是单片机这样的说法，其实嵌入式和单片机还是有区别的。单片机与嵌入式到底有什么关系？ 下面我们就来说说嵌入式和单片机之间的联系和区别吧。 01 什么是单片机？ 首先，我们来了解一下到底什么是单片机。 嵌入式系统的核心是嵌入式处理器。嵌入式处理器一般可以分为以下几种类型： 嵌入式微控制器MCU（Micro Control Unit） 嵌入式DSP处理器（Digital Signal Processor） 嵌入式微处理器MPU（Micro Processor Unit） 嵌入式片上系统SoC（System on Chip） 可编程片上系统SoPC（System on a Programmable Chip） 我们的单片机属于嵌入式微控制器MCU（Micro Control Unit） MCU内部集成ROM/RAM、总线逻辑、定时/计数器、看门狗、I/O、串口、A/D、D/A、FLASH等。典型代表如8051、8096、C8051F等。 单片机就是在一个芯片（Chip）上集成了CPU、SRAM、Flash及其他需要模块，在一个Chip上实现一个微型计算机系统，所以就叫Single Chip Microcomputer，也就是单片机了。 它其实就是一种集成电路芯片，是通过超大规模集成电路技术，将CPU、RAM、ROM、输入输出和中断系统、定时器/计数器等功能，塞进一块硅片上，变成一个超小型的计算机。 这么说来，单片机不就是一个嵌入式系统？ 别急，我们往下看。 “单片机”其实是一种古老的叫法。在那个年代半导体工艺还在起步阶段，集成能力很差，往往是CPU一个芯片，SRAM一个芯片，Flash一个芯片，需要中断的话又得有个专门处理中断的芯片，所以一个完整可用的计算机系统是很多个芯片（Chip）做在一个PCB板上构成的。 不同的功能无法做进一个芯片（Chip），所以会有多片机。现在半导体技术早已非常发达，所以不存在多片机。但是，“单片机”的叫法却一直延用至今。 单片机技术从上世纪70年代末诞生，早期的时候是4位，后来发展为8位，16位，32位。它真正崛起，是在8位时代。8位单片机功能很强，被广泛应用于工业控制、仪器仪表、家电汽车等领域。 我们在研究单片机的时候，经常会听到一个词——51单片机。让我们来了解一下它究竟是什么。 51单片机，其实就是一系列单片机的统称。该系列单片机，兼容Intel 8031指令系统。它们的始祖，是Intel（英特尔）的8004单片机。 注意，51单片机并不全是英特尔公司产品。包括ATMEL（艾德梅尔）、Philips（飞利浦）、华邦Dallas（达拉斯）、Siemens（西门子）、STC（国产宏晶等公司，也有很多产品属于51单片机系列。 ATMEL公司的51单片机，AT89C51这是一个51单片机的开发板，中间那个芯片才是51单片机 51单片机曾经在很长时间里都是市面上最主流、应用最广泛的单片机，占据大量的市场份额。 51单片机其实放在现在毫无技术优势，是一种很老的技术。之所以它的生命力顽强，除了它曾经很流行之外，还有一个原因，就是英特尔公司彻底开放了51内核的版权。 所以，无论任何单位或个人，都可以毫无顾忌地使用51单片机，不用付费，也不用担心版权风险，所以很多学校也都在用这个。 此外，51单片机拥有雄厚的存量基础和群众基础。很多老项目都是用的51单片机，出于成本的考虑，有时候只能继续沿用51单片机的技术进行升级。 而且，很多老一辈的工程师，都精通51单片机开发技术。 所以，51单片机的生命力得以不断延续。 02 什么是嵌入式？ 嵌入式系统是一种专用的计算机系统，作为装置或设备的一部分。通常，嵌入式系统是一个控制程序存储在ROM中的嵌入式处理器控制板。 事实上，所有带有数字接口的设备，如手表、微波炉、录像机、汽车等，都使用嵌入式系统，有些嵌入式系统还包含操作系统，但大多数嵌入式系统都是由单个程序实现整个控制逻辑。 从应用对象上加以定义，嵌入式系统是软件和硬件的综合体，还可以涵盖机械等附属装置。国内普遍认同的嵌入式系统定义为： 以应用为中心，以计算机技术为基础，软硬件可裁剪，适应应用系统对功能、可靠性、成本、体积、功耗等严格要求的专用计算机系统。 嵌入式系统具体应用于哪些“专用”方向呢？ 举例如下： 办公自动化：打印机，复印机、传真机 军事及航天类产品：无人机、雷达、作战机器人 家电类产品：数字电视、扫地机器人、智能家电 医疗电子类产品：生化分析仪血液分析仪、CT 汽车电子类产品：引擎控制、安全系统、汽车导航与娱乐系统 网络通信类产品：通信类交换设备、网络设备 (交换机、路由器、网络安全) 通信与娱乐：手机、数码相机、音乐播放器、可穿戴电子产品、PSP游戏机 工业控制类产品：工控机交互式终端 (POS、ATM)、安全监控、数据采集与传输、仪器仪表 上述这些领域，都使用了嵌入式系统。这还只是冰山一角。 可以说，嵌入式系统完完全全地融入了我们，时刻影响着我们的工作和生活。 嵌入式系统，既然是一个计算机系统，那么肯定离不开硬件和软件。 一个嵌入式系统的典型架构如下： 这里最重要的就是嵌入式操作系统和嵌入式微处理器。 从硬件角度来看，嵌入式系统就是以处理器（CPU）为核心，依靠总线（Bus）进行连接的多模块系统： 其实大家不难看出和个人PC是一样的方式。 单片机是有清晰定义的，就是单个片（chip）上的计算机系统。而不同的单片机虽然配置不同，性能不同，厂家不同，甚至指令集和开发方式不同，但是都是在一个片上的完整的计算机系统，这个定义不会错。 而嵌入式就是个不清晰的定义了，并没有非常明确的关于“嵌入式”这个词的定义。他也不像单片机一样，是个确定的“物”的名字。 03 单片机是不是嵌入式？ 那么单片机到底是不是嵌入式呢？ 简单来说：是。 因为很多嵌入式产品中被嵌入的计算机系统就是单片机，譬如空调中嵌入的控制板其实核心就是个单片机。实际上大部分家电产品中嵌入的计算机系统都是单片机。 因为单片机足够简单便宜而且够用，所以使用单片机是最划算最适合的。 而单片机现在出货量最大的领域也就是家电产品了，当然未来IOT类的应用会越来越多，会成为单片机的很大的增量市场。 04 广义和狭义的嵌入式 嵌入式这个概念实际上很泛化，现在讲嵌入式这个词的人，可能想表达的意思并不相同。咱们上面讲的嵌入式的概念是嵌入式本来的定义，也就是所谓广义上的嵌入式。 而狭义的嵌入式，其实是“嵌入式linux系统”的简称。 这种狭义的嵌入式最初指的是运行了linux系统的嵌入式计算机系统。后来也包括运行了和linux同级别的其他嵌入式系统（譬如WinCE、Vxworks、Android等）的计算机。 看过上面的介绍之后你就知道到底单片机是不是嵌入式了，其实这两者之间的联系有很深，总之，不管你是准备学习嵌入式或是单片机，都要自己想好了再做决定。 05 嵌入式和单片机的区别 说到这里，我们来看看，嵌入式和单片机的区别到底是什么。 从前文的介绍来看，嵌入式系统是一个大类，单片机是其中一个重要的子类。嵌式系统像是一个完整的计算机，而单片机更像是一个没有外设的计算机。 以前单片机包括的东西并不算多，两者的硬件区别较为明显。 但是，随着半导体技术的突飞猛进，现在各种硬件功能都能被做进单片机之中。所以，嵌入式系统和单片机之间的硬件区别越来越小，分界线也越来越模糊。 于是，人们倾向于在软件上进行区分。 从软件上，行业里经常把芯片中不带MMU（memory management unit，内存管理单元）从而不支持虚拟地址，只能裸奔或运行RTOS（实时操作系统，例如ucos、华为LiteOS、RT-Thread、freertos等）的system，叫做单片机（如STM32、NXP LPC系列、NXP imxRT1052系列等）。 同时，把芯片自带MMU可以支持虚拟地址，能够跑Linux、Vxworks、WinCE、Android这样的“高级”操作系统的system，叫做嵌入式。 在某些时候，单片机本身已经足够强大，可以作为嵌入式系统使用。它的成本更低，开发和维护的难度相对较小，尤其是针对一些针对性更强的应用。而嵌入式系统理论上性能更强，应用更广泛，但复杂度高，开发难度大。 06 我们为什么要学习嵌入式和单片机 今天我也只是给大家简单地介绍了一下单片机和嵌入式以及他们之间的关系和区别，虽然嵌入式系统已经有30多年的历史，但其实一直隐藏在背后的，自从物联网上升为国家战略后，嵌入式系统也渐渐从后台走到前台。 嵌入式和单片机并不是纯“硬件”类方向。如果你想学好嵌入式和单片机，只懂数字电路和微机接口这样的硬件知识是不够的，你更需要学习的，是汇编、C/C++语言、数据结构和算法知识。拥有软硬结合的能力，远远比单纯掌握某种程序开发语言更有价值。 其次，嵌入式和单片机拥有广泛的应用场景，在各个领域都有项目需求和人才需求。而且我们国家现在正在大力发展芯片产业，也会带动嵌入式人才的就业，提升待遇。 随着5G建设的深入，整个社会正在向“万物互联”的方向变革。 物联网技术也将迎来前所未有的历史机遇。嵌入式和单片机技术是物联网技术的重要组成部分，也将进入快速发展的时代。 技术越难，过程越苦，越有利于构建竞争壁垒。大学里很多同学都热衷于学习各种编程语言，往往忽视了这一块，可以说在嵌入式开发这一块的人才我们国家还是比较欠缺的。因此，我觉得大家非常值得投入时间去学习嵌入式开发的技能。原文：https://www.zhihu.com/question/315310041/answer/2179945564
01-03 93浏览 -
Bootloader的见鬼故障
【前面的话】在近几年的嵌入式社区中，流传着不少关于面相Cortex-M的Bootloader科普文章，借助这些文章，一些较为经典的代码片断和技巧得到了广泛的传播。 在从Bootloader跳转到用户APP的过程中，使用函数指针而非传统的汇编代码则成了一个家喻户晓的小技巧。相信类似下面 JumpToApp() 函数，你一定不会感到陌生： typedef void (*pFunction)(void); void JumpToApp(uint32_t addr){ pFunction Jump_To_Application; __IO uint32_t StackAddr; __IO uint32_t ResetVector; __IO uint32_t JumpMask; JumpMask = ~((MCU_SIZE-1)|0xD000FFFF); if (((*(__IO uint32_t *)addr) & JumpMask ) == 0x20000000) //�ж�SPָ��λ�� { StackAddr = *(__IO uint32_t*)addr; ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); }} 为了读懂这段代码，需要一些从事Cortex-M开发所需的“热知识”： 向量表是一个由 32bit 数据构成的数组 数组的第一个元素是 uintptr_t 类型的指针，保存着复位后主栈顶指针（MSP）的初始值。 从数组第二个元素开始，保存的是 (void (*)(void)) 类型的异常处理程序地址（BIT0固定为1，表示异常处理程序使用Thumb指令集进行编码） 数组的第二个元素保存的是复位异常处理程序的地址（Reset_Handler） 从理论上说，要想保证APP能正常执行，Bootloader通常要在跳转前“隐藏自己存在过的事实”——需要“对房间进行适度的清理”，并模拟芯片硬件的一些行为——假装芯片复位后是直接从APP开始执行的。 总结来说，Bootloader在跳转到App之前需要做两件事： 1. 清理房间——仿佛Bootloader从未执行过一样 2. 模拟处理器的硬件的一些复位行为——假装芯片从复位开始就直接从APP开始执行 一般来说，做到上述两点，就可以实现App将Bootloader视作黑盒子的效果，从而带来极高的兼容性。甚至在App注入了“跳床（trumpline）”的情况下，实现App既可以独立开发、调试和运行，也可以不经修改的与Bootloader一起工作的奇效。 如何在App中加入“跳床（trumpline）”值得专门再写一篇独立的文章，不是本文所需关注的重点，请允许我暂且略过。 这里，“清理房间”的步骤与Bootloader具体“弄脏了什么”（或者说使用了什么资源）有关；而“模拟处理器硬件的一些复位行为”就较为简单和具体：即，从Bootloader跳转到App前的最后两个步骤为： 从APP的向量表中读取MSP的初始值并以此来初始化MSP寄存器； 从APP的向量表中读取Reset_Handler的值，并跳转到其中去执行——完成从Bootloader到APP的权利交接。 结合前面的例子代码，值得我们关注的部分是： 1. 使用自定义的函数指针类型 pFunction 定义一个局部变量： pFunction Jump_To_Application; 2. 根据向量表的首地址 addr 读取第一个元素——作为MSP的初始值暂时保存在局部变量 StackAddr 中： StackAddr = *(__IO uint32_t*)addr; 3. 根据向量表的首地址 addr 读取第二个元素——将Reset_Handler的首地址保存到局部变量 ResetVector 中： ResetVector = *(__IO uint32_t *)(addr + 4); 4. 设置栈顶指针MSP寄存器： __set_MSP(StackAddr); 5. 通过函数指针完成从Bootloader到App的跳转： Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); 其实，无论具体的代码如何，只要实现步骤与上述类似，就存在一个隐藏较深的漏洞，而漏洞的“触发与否”则完全“看脸”——简单来说： 只要你是按照上述方法来实现从Bootloader到App的跳转的，那么就一定存在问题——而“似乎可以正常工作”就只是你运气较好，或者“由此引发的问题暂时未能引发注意”罢了。 在你试图争辩“老子代码已经量产了也没有什么不妥”之前，我们先来看看漏洞的原理是什么——在知其所以然后，如何评估风险就是你们自己的事情了。 【C语言基础设施是什么】 嵌入式系统的信息安全（Security）建立在基础设施安全（Safety）的基础之上。 由于“确保信息安全的很多机制”本质上是一套建立在“基础设施能够正常工作”这一前提之上的规则和逻辑，因此很多针对信息安全的攻击往往会绕开信息安全的“马奇诺防线”，转而攻击基础设施。芯片数字逻辑的基础设施是时钟源、供电、总线时序、复位时序等等，因此，针对硬件基础设施的攻击通常也就是针对时钟源、电源、总线时序和复位时序的攻击。此时，好奇的小伙伴会产生疑问：固件一般由C语言进行编写，那么C语言所依赖的基础设施又是什么呢？ 对C语言编译器来说，栈的作用是无可替代的： 函数调用 函数间的参数传递 分配局部变量 暂时保存通用寄存器中的内容 …… 可以说，离开了栈C语言寸步难行。因此对很多芯片来说，复位后为了执行用户使用C语言编译的代码，第一个步骤就是要实现栈的初始化。 作为一个有趣的“冷知识”，Cortex-M在宣传中一直强调自己“支持完全使用C语言进行开发”，这让很多人“丈二和尚摸不着头脑”甚至觉得“非常可笑”——因为这年月连51都支持用户使用C语言进行开发了，你这里说的“Cortex-M支持使用C语言进行开发”有什么意义呢？ 其实门道就在这里： 由于Cortex-M处理器会在复位时由硬件完成对C语言基础设施（也就是栈顶指针MSP）的初始化，因此无论是理论上还是实践中，从复位异常处理程序Reset_Handler开始用户就可以完全可以使用C语言进行开发了，而整个启动代码（startup）也可以全然不涉及任何汇编； 由于Cortex-M的向量表是一个完全由 32位整数（uintptr_t）构成的数组——保存的都是地址而非具体代码，可以使用C语言的数据结构直接进行描述——因此也完全不需要汇编语言的介入。 这种从复位一开始就完全不需要汇编介入的友好环境才是Cortex-M声称自己“支持完全使用C语言进行开发”的真实意义和底气。从这一角度出发，只要某个芯片架构复位后必须要通过软件来初始化栈顶指针，就不符合“从出生的那一刻就可以使用C语言”的基本要求。 【C语言编译器的约定】 栈对C语言来说如此重要，以至于编译器一直有一条默认的约定，即： 栈必须完全交由C语言编译器进行管理（或者用户对栈的操作必须符合对应平台所提供的调用规约，比如Arm的AAPCS规约）。 简而言之，如果你“偷偷摸摸”的修改了栈顶指针，C语言编译器是会“假装”完全不知道的，而此时所产生的后果C语言编译器会默认自己完全不用负责。 回头再看这段代码： StackAddr = *(__IO uint32_t*)addr; ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); 虽然我们觉得自己“正大光明”的使用了 __set_MSP() 来修改了栈顶指针，但它实际上是一段C语言编译器并不理解其具体功能的在线汇编——在编译器看来，无论是谁提供的 __set_MSP()，只要是在线汇编，这就算是用户代码——是编译器管不到的地带。 /** \brief Set Priority Mask \details Assigns the given value to the Priority Mask Register. \param [in] priMask Priority Mask */__STATIC_FORCEINLINE void __set_PRIMASK(uint32_t priMask){ __ASM volatile ("MSR primask, %0" : : "r" (priMask) : "memory");} 或者说：C语言编译器一般情况下会默认你“无论如何都不会修改栈顶指针”——它不仅管不着，也不想管。 从这点来看，上述代码的确打破了这份约定。即便如此，很多小伙伴会心理倔强的认为：我就这么改了，怎么DE了吧？！ 【问题的分析】 从原理上说，开篇那个典型的Bootloader跳转代码所存在的问题已经昭然若揭： typedef void (*pFunction)(void); void JumpToApp(uint32_t addr){ pFunction Jump_To_Application; __IO uint32_t StackAddr; __IO uint32_t ResetVector; __IO uint32_t JumpMask; JumpMask = ~((MCU_SIZE-1)|0xD000FFFF); if (((*(__IO uint32_t *)addr) & JumpMask ) == 0x20000000) //�ж�SPָ��λ�� { StackAddr = *(__IO uint32_t*)addr; ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); }} 我们不妨结合上述代码反汇编的结果进行深入解析： AREA ||i.JumpToApp||, CODE, READONLY, ALIGN=2 JumpToApp PROC000000 b082 SUB sp,sp,#8000002 4909 LDR r1,|L2.40|000004 9100 STR r1,[sp,#0]000006 6802 LDR r2,[r0,#0]000008 400a ANDS r2,r2,r100000a 2101 MOVS r1,#100000c 0749 LSLS r1,r1,#2900000e 428a CMP r2,r1000010 d107 BNE |L2.34|000012 6801 LDR r1,[r0,#0]000014 9100 STR r1,[sp,#0]000016 6840 LDR r0,[r0,#4]000018 f3818808 MSR MSP,r100001c 9001 STR r0,[sp,#4]00001e b002 ADD sp,sp,#8000020 4700 BX r0 |L2.34|000022 b002 ADD sp,sp,#8000024 4770 BX lr ENDP 000026 0000 DCW 0x0000 |L2.40| DCD 0x2fff0000 注意这里，StackAddr、ResetVector是两个局部变量，由编译器在栈中进行分配。汇编指令将SP指针向栈底挪动8个字节就是这个意思： 000000 b082 SUB sp,sp,#8 虽然 JumpMask 也是局部变量，但编译器根据自己判断认为它“命不久矣”，因此直接将它分配到了通用寄存器r2中，并配合r1和sp完成了后续运算。这里： __IO uint32_t JumpMask; JumpMask = ~((MCU_SIZE-1)|0xD000FFFF); if (((*(__IO uint32_t *)addr) & JumpMask ) == 0x20000000) //�ж�SPָ��λ�� { ... } 对应： 000002 4909 LDR r1,|L2.40|000004 9100 STR r1,[sp,#0]000006 6802 LDR r2,[r0,#0]000008 400a ANDS r2,r2,r100000a 2101 MOVS r1,#100000c 0749 LSLS r1,r1,#2900000e 428a CMP r2,r1000010 d107 BNE |L2.34|...|L2.34|000022 b002 ADD sp,sp,#8000024 4770 BX lrENDP 000026 0000 DCW 0x0000|L2.40|DCD 0x2fff0000 考虑到JumpMask的内容与本文无关，不妨暂且跳过。 接下来就是重头戏了： 编译器按照用户的指示读取栈顶指针MSP的初始值，并保存在StackAddr中： StackAddr = *(__IO uint32_t*)addr; 对应的汇编是： 000012 6801 LDR r1,[r0,#0]000014 9100 STR r1,[sp,#0] 根据Arm的AAPCS调用规约，编译器在调用函数时会使用R0~R3来传递前4个符合条件的参数（这里的条件可以简单理解为每个参数的宽度要小于等于32bit）。根据函数原型 void JumpToApp(uint32_t addr); 可知，r0 中保存的就是形参 addr 的值。所以第一句汇编的意思就是：根据 （addr + 0）作为地址读取一个uint32_t型的数据保存到r1中。 第二句汇编中，栈顶指针sp此时实际上指向局部变量 StackAddr，因此其含义就是将通用寄存器r1中的值保存到局部变量 StackAddr 中。 对于局部变量 ResetVector 的读取操作，编译器的处理如出一辙： ResetVector = *(__IO uint32_t *)(addr + 4); 对应： 000016 6840 LDR r0,[r0,#4]00001c 9001 STR r0,[sp,#4] 其实就是从 (addr + 4) 的位置读取 32bit 整数，然后保存到r0里，并随即保存到sp所指向的局部变量 ResetVector 中。到这里，细心地小伙伴会立即跳起来说“不对啊，原文不是这样的！”。是的，这也是最有趣的地方。实际的汇编原文如下： 000016 6840 LDR r0,[r0,#4]000018 f3818808 MSR MSP,r100001c 9001 STR r0,[sp,#4] 作为提醒，它对应的C代码如下： ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); 后面的 __set_MSP(StackAddr) 所对应的汇编代码 MSR MSR,r1 居然插入到了ResetVector赋值语句的中间？！ “C语言编译器这么自由的么？” “在我使用sp之前把栈顶指针更新了？！” 先别激动，还记得我们和C语言编译器之间的约定么？C语言编译器默认我们在任何时候都不应该修改栈顶指针。因此在他看来，“你 MSR 指令操作的是r1，关我sp和r0啥事”？“我就算随意更改顺序应该对你一毛钱影响都没有！（因为我不关心、也没法知道用户线汇编语句的具体效果，因此我只关心涉事的通用寄存器是否存在冲突）” 上述“骚操作”的后果是：保存在r0中的Reset_Handler地址值被保存到了新栈中（MSP + 4）的位置。这立即带来两个潜在后果： 由于MSP指向的是栈存储器的末尾（栈是从数值较大的地址向数值较小的地址生长），因此 (MSP+4）实际上已经超出栈的合法范围了。 这一操作与其说是会覆盖栈后续的存储空间，倒不如说风险主要体现在BusFault上——因为相当一部分人习惯将栈放到SRAM的最末尾，而MSP+4直接超出SRAM的有效范围。 我们以为的ResetVector其实已经不在原本C编译器所安排的地址上了。 精彩的还在后面： Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); 对应的翻译是： 00001e b002 ADD sp,sp,#8000020 4700 BX r0 通过前面的分析，我们知道，此时r0中保存的是Reset_Handler的地址，因此 BX r0 能够成功完成从Bootloader到APP的跳转——也许你会松一口气——好像局部变量ResetVector的错位也没引起严重的后果嘛。 看似如此，但真正吓人的是C语言编译器随后对局部变量的释放： 00001e b002 ADD sp,sp,#8 它与一开始局部变量的分配形成呼应： 000000 b082 SUB sp,sp,#8...00001e b002 ADD sp,sp,#8 好借好还，再借不难。但此sp非彼sp了呀！ 这里由于JumpToApp没有加上__NO_RETURN的修饰，因此C编译器并不知道这个函数是有去无回的，因此仍然会像往常一样在函数退出时释放局部变量。 就像刚才分析的那样：由于MSP指向的是栈存储器的末尾（栈是从数值较大的地址向数值较小的地址生长），因此 (MSP+8）实际上已经超出栈存储空间的合法范围了。 考虑到相当一部分人习惯将栈放到SRAM的最末尾，而MSP+8直接超出SRAM的有效范围，即便刚跳转到APP的时候还不会有事，但凡APP用了任何压栈操作，（无论是BusFault还是地址空间绕回）就很有可能产生灾难性的后果。 【宏观分析】 就事论事的讲，单从汇编分析来看，上述代码所产生的风险似乎是可控的，甚至某些人会觉得可以“忽略不计”。但最可怕的也就在这里，原因如下： 从原理上说，将关键信息保存在依赖栈的局部变量中，然后在编译器不知情的情况下替换了栈所在的位置，此后只要产生对相关局部变量的访问就有可能出现“刻舟求剑”的数据错误。这种问题是“系统性的”、“原理性的”。 （此图由GorgonMeducer借助GPT4进行一系列关键词调校、配上台词后获得） 不同编译器、同一编译器的不同版本、同一版本的不同优化选项都有可能对同一段C语言代码产生不同的编译结果，因此哪怕我们经过上述分析得出某一段汇编代码似乎不会产生特别严重的后果，在严谨的工程实践上，这也只能算做是“侥幸”，是埋下了一颗不知道什么时候以什么方式引爆的定时炸弹。 根据用户Bootloader代码在修改 MSP 前后对局部变量的使用情况不同、考虑到用户APP行为的不确定性、由上述缺陷代码所产生的Bootloader与APP之间配合问题的组合多种多样、由于涉及到用户栈顶指针位置的不确定性以及新的栈存储器空间中内容的随机性，最终体现出来的现象也是完全随机的。用人话说就是，经常性的“活见鬼” 【解决方案】 既然我们知道不能对上述缺陷代码抱有侥幸心理，该如何妥善解决呢？第一个思路：既然问题是由栈导致的，那么直接让编译器用通用寄存器来保存关键局部变量不就行了？修改代码为： typedef void (*pFunction)(void); void JumpToApp(uint32_t addr){ pFunction Jump_To_Application; register uint32_t StackAddr; register uint32_t ResetVector; register uint32_t JumpMask; JumpMask = ~((MCU_SIZE-1)|0xD000FFFF); if (((*(__IO uint32_t *)addr) & JumpMask ) == 0x20000000) //�ж�SPָ��λ�� { StackAddr = *(__IO uint32_t*)addr; ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); }} 相同编译环境下得出的结果为： AREA ||i.JumpToApp||, CODE, READONLY, ALIGN=2 JumpToApp PROC 000002 6801 LDR r1,[r0,#0]000004 4011 ANDS r1,r1,r2000006 2201 MOVS r2,#1000008 0752 LSLS r2,r2,#2900000a 4291 CMP r1,r200000c d104 BNE |L2.24| 00000e 6801 LDR r1,[r0,#0]000010 6840 LDR r0,[r0,#4]000012 f3818808 MSR MSP,r1 000016 4700 BX r0 |L2.24|000018 4770 BX lr ENDP 00001a 0000 DCW 0x0000 |L2.28| DCD 0x2fff0000 可见，上述汇编中半个 sp 的影子都没看到，问题算是得到了解决。 然而，需要注意的是 register 关键字对编译器来说只是一个“建议”，它听不听你的还不一定。加之上述例子代码本身相当简单，涉及到的局部变量数量有限，因此问题似乎得到了解决。 倘若编译器发现你大量使用 register 关键字导致实际可用的通用寄存器数量入不敷出，大概率还是会用栈来进行过渡的——此时，哪些局部变量用栈，哪些用通用寄存器就完全看编译器的心情了。 进一步的，不同编译器、不同版本、不同优化选项又会带来大量不可控的变数。 因此就算使用 register 修饰关键局部变量的方法可以救一时之疾（“只怪老板催我催得紧，莫怪我走后洪水滔天”），也算不得妥当。 第二个思路：既然问题出在局部变量上，我用静态（或者全局）变量不就可以了？修改源代码为： #include "cmsis_compiler.h" typedef void (*pFunction)(void); __NO_RETURNvoid JumpToApp(uint32_t addr){ pFunction Jump_To_Application; static uint32_t StackAddr; static uint32_t ResetVector; register uint32_t JumpMask; JumpMask = ~((MCU_SIZE-1)|0xD000FFFF); if (((*(__IO uint32_t *)addr) & JumpMask ) == 0x20000000) //�ж�SPָ��λ�� { StackAddr = *(__IO uint32_t*)addr; ResetVector = *(__IO uint32_t *)(addr + 4); __set_MSP(StackAddr); Jump_To_Application = (pFunction)ResetVector; Jump_To_Application(); }} 这种方法看似稳如老狗，实际效果可能也不差，但还是存在隐患，因为它“没有完全杜绝编译器会使用栈的情况”，只要我们还会通过 __set_MSP() 在C语言编译器不知道的情况下更新栈顶指针，风险自始至终都是存在的。 对某些连warning都要全数消灭的团队来说，上述方案多半也是不可容忍的。 第三个思路：完全用汇编来处理从Bootloader到App的最后步骤。对此我只想说：稳定可靠，正解。 只不过需要注意的是：这里整个函数都需要用纯汇编打造，而不只是在C函数内容使用在线汇编。 原因很简单：既然我们已经下定决心要追求极端确定性，就不应该使用线汇编这种与C语言存在某些“暧昧交互”的方式——因为它仍然会引入一些意想不到的不确定性。 本着一不做二不休的态度，完全使用汇编代码来编写跳转代码才是万全之策。 【说在后面的话】 在使用栈的情况下，on-fly 的修改栈顶指针就好比在飞行途中更换引擎——不是不行，只是要求有亿点点高。 我在微信群中帮读者分析各类Bootloader的见鬼故障时，经常在大费周章的一通分析和调试后，发现问题的罪魁祸首就是跳转代码。可怕的是，几乎每个故障的具体现象都各不相同，表现出的随机性也常常让人怀疑是不是硬件本身存在问题，亦或是产品工作现场的电磁环境较为恶劣。最要命的当数那种“偶尔出现”而复现条件颇为玄学的情形，甚至在办公室环境下完全无法重现的也大有人在。同样的问题出的多了，我几乎在每次帮人调试Bootloader时都会习惯性的先要求检查跳转代码——虽然不会每次都能猜个正着，但也有个恐怖的十之七八。这也许是某种幸存者偏差吧——毕竟大部分普通问题大家自己总能解决，到我这里的多半就是“驱鬼”了。见得多了，我突然发现，出问题的代码大多使用函数指针来实现跳转——而用局部变量来保存函数指针又成了大家自然而然的选择。加之此前很多文章都曾大规模科普上述技巧，甚至是直接包含一些存在缺陷的Bootloader范例代码，实际受影响的范围真是“细思恐极”。特此撰文，为您解惑。
01-03 14浏览 -
脑洞有多大，MCU就能玩得有多花
都说MCU本身不算什么高级东西，在MCU开发过程中，需要按照一定的标准化来执行，比如对变量，函数的定义，要确定他的生命周期，调用范围，访问条件等；常用的通信协议读写的协议往往应该抽象化，规定固定的输入输出，方便产品移植。 但实际上，很多时候，针对同一个需求其实有多种实现方案，但总有一个最优解。所以在这个过程中，总会有一些“脑洞大开”的操作，为人提供很多思路，今天就举几个例子给大家作为参考。 那些很惊艳的用法 当需要通过串口接收一串不定长数据时，可以使用串口空闲中断；这样就可以避免每接收到一个字符就需要进入中断进行处理，可以减少程序进入中断次数从而提高效率。 当需要测量一个波形的频率时，很多人会选择外部中断，其实通过定时器的外部时钟输入计数波形边沿，然后定时读取计数值计算频率的方式可以大大减少中断触发频率，提高程序执行效率。 在处理复杂的多任务场景时，可以利用实时操作系统（RTOS）来管理任务调度，提高系统的响应性和资源利用率。 对于需要低功耗运行的场景，可以采用动态电压频率调整（DVFS）技术，根据系统负载实时调整 MCU 的工作电压和频率，以降低功耗。 在进行数据存储时，采用闪存的磨损均衡算法，延长闪存的使用寿命。 利用硬件加密模块（如 AES 加密引擎）来保障数据的安全性和保密性，而不是通过软件实现加密，提高加密效率和安全性。 对于传感器数据的处理，采用数字滤波算法（如卡尔曼滤波），提高数据的准确性和稳定性。 当需要与多个设备进行通信时，采用总线仲裁机制和优先级设置，确保通信的高效和稳定。 在进行电源管理时，通过监测电源电压和电流，实现智能的电源管理策略，例如在低电量时进入低功耗模式。 对于实时性要求极高的控制任务，采用硬件直接触发中断，而不是通过软件轮询，减少响应延迟。 在单片机上跑的任何非线性系统的动态控制，都是高级用法。 用单片机去实现某种特殊的运动控制，赚很多钱，就是高级用法。 GPIO模拟一切 名为ShiinaKaze的网友，就非常“勇”，做了一个很折磨的事。 他用STM32F1利用GPIO模拟摄像头接口驱动OV2640摄像头模块。他表示，这是一个很折磨人的过程，我最多优化到了 1.5 FPSQ，所以选型一定要选好，不要折磨自己。设备采用STM32F103C8T6，OV2640，实现效果如下： OV2640实际时序图： 这个项目难点在于： 1.SCCB 模拟:SCCB 是12C-bus 的改版，主要是 OV2640 模块没有上拉电阻，无法进行通信，花了好长时间才发现这个问题； 2.并行接口的模拟:如果使用 IO 模拟的话，只能达到1FPS，但是使用了 Timer 和 DMA，就可以达到 1.5～2 FPS。 关于 image sensor 的数据接收和处理的问题背景：现有 ov2640 image sensor，接口为 DCMI（并行接口）问题：现有 STM32H7 想获取 OV2640 的 mjpeg 流数据，并通过传输数据到 PC 软件 1.采用 USART 还是 USB？ 2.接收数据选择哪种中断，Line interrupt 还是 Frame interrupt ？ 3.DCMI 通过 DMA 将数据转到 RAM 中的 Buffer，那么 Buffer 该如何设计，是设置一块大的连续 buffer？还是需要做一个 ring buffer，避免数据覆盖和数据顺乱？ 4.触发中断后，是否关闭 DCMI 和 DMA ？ 嵌入式软件架构挺重要的，特别是大型项目。这是 STM32 的软件架构，不知道各位还有没有其他架构。 有网友吐槽，你要是在学校，我敬你是条汉子，你要是在工作岗位上干这鸟事，那你们的架构也太坏了。而他也表示——“我错了，再也不模拟了。” 关于MCU不一样的观点 虽然如此，很多人还是认为，MCU不高级，使用单片机也不高级。高级的内容都是可以发论文的，使用单片机发不了论文。但使用单片机解决指定的任务，这很高级。 尤其是上面所说的一些例子，确实是MCU外设的一些高端玩法。只不过，这些机制可能只是一种标准用法。名为lion187的网友就表示，毕竟许多硬件机制有实际需求后才添加进来的，比如接收不定长数据，最初没有超时中断的情况下只能软件实现，极大的浪费了CPU的效率，所以才设计了超时中断来减少软件工作量，进而形成了一种标准使用方法。 当然，这也是芯片设计和制造工艺的提升带来的红利，早期芯片设计和工艺无法满足复杂外设电路时，谁也不敢会去想用硬件来实现这么复杂的功能，任何产品的开发，都离不开具体业务需求，MCU也不例外， 对产品来说，MCU外设的驱动只是完成开发的基本要素，更多的工作是围绕着业务逻辑展开的应用程序的开发。这时候数据结构与算法，各种控制算法和数值计算方法，设计模式，软件工程和设计理念成了高级的东西。 比如说，Linux 内核中的各驱动子系统的设计，设备对象和驱动对象这些沿用了 C++ 面向对象编程的思路，其实也可以沿用到 MCU的开发中，将设备与驱动分离，就可以使用同一套驱动算法来实现同类设备的不同驱动方法， 比如:同一个 UART 驱动可以根据配置的不同来驱动 UARTO，也可以驱动 UART1，而且波特率也可以不同(只要为 UART 类创建不同的实例对象就可以了，用 C 语言就行)，这就是 C++ 中方法与属性分离带来的好处。 同样在业务应用部分，单件模式、工厂模式等设计模式，状态机模型的使用也会给开发带来很多便利，使系统结构清晰，有效减少Bug数量，且易于维护和扩展。 当然，也有人认为，论高级还得是FPGA。就比如AMD（赛灵思）的ZYNQ，当你需要通过串口接收一串不定长数据时，可以直接用Programmable Logic部分写一个专用的，最终结果放到DRAM里，发个信号通知ARM处理器来读就好了；当你需要测量一个波形的频率时，可以直接用Programmable Logic部分写一个专用的，实时不间断测量。这就很高级。 所以，对此你有什么看法，你有什么很“高级”的用法想要分享？
01-03 44浏览 -
-
STM32最小系统板电路知识学习
STM32最小系统板电路知识学习 单片机最小系统是指用最少的电路组成单片机可以工作的系统，通常最小系统包含：电源电路、时钟电路、复位电路、调试/下载电路，对于STM32还需要启动选择电路。总之，刚开始如果不太懂电路的话，就抄别人的电路，然后自己拼凑。下图为stm32c8t6经典电路原理图 文章目录 STM32最小系统板电路知识学习 一、电源转换电路 二、JTAG/SWD调试接口电路 三、时钟电路 四、复位电路 提示：以下是本篇文章正文内容，下面案例可供参考 一、电源转换电路 开发板通常采用USB供电，通常USB都为5V，因此需要将5V转换成3.3V，使用TPS73633或者AMS1117芯片电源芯片即可实现。 首先设计电源入口部分，现在大多数开发板所使用的都是USB的5V供电，所以我们本次设计也采用USB接口供电，所以我们电源接口就采用5Pin的mini贴片的USB，将5V的电源引入开发板使用，其电路图如下，1脚为电源正极，5脚为负极，串接的二极管是为了保护我们的开发板，防止有个别的连接线极性不对烧坏板子，保护电路在我们设计任何电路时都要考虑到，这个大家以后自己设计时也要注意。这样我们就可以通过连接线将5V的USB电源引入到开发板中进行使用了。 接下来便是电源电路，STM32工作电压是DC3.3V，所以我们需要一个能将大于3.3V电压转换为稳定的3.3V电压的芯片，这里我们使用的是TPS73633或者AMS1117芯片电源芯片即可实现。 下图为TPS73633芯片的相关说明，TPS73633DBVR是一款3.3V固定输出低压降（LDO）线性稳压器，采用了一种新的拓扑-电压跟随器配置中的NMOS调整元件。使用具有低ESR的输出电容器，这种拓扑是稳定的，甚至可以在没有电容器的情况下运行。它还提供高反向阻塞（低反向电流）和接地引脚电流，该电流在所有输出电流值上都几乎恒定。该器件使用先进的BiCMOS工艺来产生高精度，同时提供非常低压降（LDO）的电压和低接地引脚电流。未启用时，电流消耗低于1uA，非常适合便携式应用。极低的输出噪声非常适合为VCO供电。该器件受热关断和折返电流限制保护。 二、JTAG/SWD调试接口电路 JTAG/SWD调试接口电路采用了标准的JTAG接法，这种接法兼容SWD接口，因为SWD只需要四根线（SWCLK、SWDIO、VCC和GND）。需要注意的是，该接口电路为JLINK或ST-Link提供3.3V的电源，因此，不能通过JLINK或ST-Link对STM32核心板进行供电，而是STM32核心板为JLINK或ST-Link供电。JLINK和ST-Link不仅可以下载程序，还可以对STM32微控制器进行在线调试。 三、时钟电路 MCU是一个集成芯片，由非常复杂的数字电路和其它电路组成，需要稳定的时钟脉冲信号才能保证正常工作。时钟如同人体内部的心脏一样，是芯片的“动力”来源。时钟产生一次，就推动处理器执行一下指令。除了CPU，芯片上所有的外设(GPIO、I2C、SPI等)都需要时钟，由此可见时钟的重要性。芯片运行的时钟频率越高，芯片处理的速度越快，但同时功耗也越高。为了功耗和性能兼顾，微处理器一般有多个时钟源，同时还将时钟分频为多个大小，适配不同需求的外设。下图为stm32的时钟树 这里我们将两个晶振电路，电源，以及各引脚的网络符号对应连接好即可，除去晶振和电源，其余的标号都是连接在我们引出的排针上边的，晶振电路这里包含了一个8MHz的主晶振，以及一个32.768kHz的内部RTC实时时钟晶振，这里时钟晶振作为预留，如果有用到时钟的小伙伴直接焊接上即可，方便使用，每个晶振后边并联的为起振电容，方便晶振起振，电源部分的电容C3-C7组成了一个低通滤波电路，目的是为了让32更好的工作 四、复位电路 嵌入式系统中，由于外界环境干扰，难免出现程序跑飞或死机，这时就需要复位让MCU重新运行。该电路将一个按键接在了NRST引脚，一旦按键按下，NRST就会接地，拉低NRST，实现复位。
01-03 94浏览 -
-
一个基于分层架构实现的MCU通用系统
大家好，今天分享一个仿linux分层架构实现的mcu通用系统，该项目的创建方便芯片级切换以及多产品线开发。 《一个基于分层架构实现的MCU通用系统》 项目整体框图 项目亮点 分层架构，清晰高效：usal_mcu采用仿Linux的分层架构设计，将系统划分为驱动层、系统层和应用层， 每一层都独立且清晰，既方便模块化的开发管理，也易于未来的功能扩展与维护。 面向对象，跨平台支持：项目采用C语言的面向对象编程风格，这种独特的编写方式不仅使代码更加优雅、易于理解，还实现了良好的跨平台能力，轻松应对不同硬件平台的需求。 配置灵活，易于裁剪：无论是驱动还是内核，项目都提供了简洁的配置文件，让开发者可以轻松实现外设的切换与系统的定制化裁剪，满足多样化的项目开发需求。 设备注册挂载，接口统一：借鉴Linux VFS的设计理念，所有设备均采用注册挂载方式，并提供统一的open、close、write、read等接口，极大地方便了应用程序的开发与调试。 清晰文档，易于上手：项目包含了详尽的文档结构，从目录介绍到部署步骤，再到具体功能说明，让初学者也能快速上手，享受到项目带来的便利与乐趣。 项目展望 usal_mcu项目不仅仅是一个技术实现上的创新，更是对未来嵌入式系统发展趋势的一次积极响应。 通过分层架构和模块化的设计，它为嵌入式开发提供了更多的可能性与灵活性，预示着更加高效、易用的开发时代即将到来。
2024-12-06 120浏览 -
嵌入式MCU里也能实现类安卓高级UI开发
AAGUI介绍 AAGUI是一个不依赖特定硬件、操作系统的跨平台通用型GUI。 链接：https://gitee.com/QQ1159465634/aagui 使用MIT开源许可协议 AAGUI采用C(兼容C89)与C++(兼容C++98)编写，兼容位置无关。面向对象、半声明式、等特性使得AAGUI的应用开发效率、可维护性都十分优秀！ 优雅的页面管理机制使得AAGUI也能拥有开发出大型系统级多页面UI应用的能力！ UI核心来源于对安卓的精简移植，以及超低的内存占用，终于在嵌入式MCU里也能实现类安卓的高级UI开发！ 软件架构 文件夹 是否开源 AAGUI_app 应用层 ✅ AAGUI_core 核心层 ❎ libAAGUI 已编译的核心层静态库 ❇ 移植教程 ⑴ 将AAGUI相关代码、静态库全部加入到项目中。加上头文件路径。自定义一个预处理符号方便标记当前目标平台。 ⑵ AABase.c中实现相关抽象移植接口，如aa_malloc()...。 ⑶ 定义主GUI并配置其显示设备信息，对接框架接口。 详情请参阅 AAGUI文档.chm 及已移植好的项目文件。 更多说明 内存空间推荐：flash >= 256KB，RAM >= 32KB(6K栈+26K堆)。 框架重要优势：完整应用框架、多GUI实例（多屏）、json半声明式高级UI、完整中文输入法、支持Alpha、支持剪辑区。 帧缓冲区格式：原生支持0bit自控、1bit单色、8bit灰度、16、24、32bit彩色，支持动态修改。 部分帧缓冲区：支持PFB部分帧缓存，最低只需1行缓存。比如240x320分辨率，最低只需要240的内存。 复用支持简要：页面（面板）复用、UI布局复用、UI控件复用、自定义高级UI组件。 高级布局简要：帧布局、线性布局、绝对布局、垂直&水平滚动容器、文本、文本编辑、按钮、进度条。 字体支持简要：自由管理字体、支持绘制带边框文字、文本缩放绘制。 底层图形绘制：点、线、矩形、圆、圆角矩形、椭圆矩形、渐变矩形、多边形、圆弧（可实现扇形）。 底层图片绘制：1、8、16、24、32bit位图、qoi格式图片。位图支持缩放、旋转。 更多图片
2024-11-22 177浏览 -
ext4_extent 算法设计真巧妙
内核版本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内核代码逻辑真的复杂，在最后的举例+示意图下才算较为透彻的理解了。
2024-11-22 99浏览 -
新能源汽车VCU、ECU、MCU、电池BMS图解
新能源汽车中的各种控制器主要包括：整车控制器（VCU）、发动机控制器（ECU）、电机控制器（MCU）和电池管理系统（BMS）。 新能源汽车的三电技术，包括电池、电驱和电控。电池部分阐述了动力电池系统的构成；电驱部分讲解了传动机构、电机和电机控制器的功能； 一、整车控制器（VCU） 1. 功能 1.1 驱动系统控制 1.2 整车能量管理和优化 1.3 整车通信和网络管理 1.4 故障处理与诊断 1.5 汽车状态显示 2. 工作模式 2.1 自检模式 2.2 启动模式 2.3 起步模式 2.4 行驶模式 2.5 制动模式 2.6 停车模式 2.7 故障模式 2.8 充电模式 整车域控制器（VCU）是整车控制的核心控制器，通过汽车总线或者硬线，实现对电池系统、电驱系统、热管理系统等的管理，具体包括档位、加速踏板、制动踏板的控制，根据实时的动力电池电量，计算出需要输出的扭矩控制，整车的低压、高压的上下电、能量回收等控制。 VCU的内部结构简图如下 二、电子控制单元（ECU） Engine Control Unit即发动机控制单元，特指电喷发动机的电子控制系统。 后来随着电子汽车的迅速发展，ECU的定义变成了Electronic Control Unit，即电子控制单元，泛指汽车上所有电子控制系统。 1. ECU基本组成 ECU和普通的单片机一样，由微控制器（MCU）、存储器（ROM、RAM）、输入/输出接口（I/O）、模数转换器（A/D）以及整形、驱动等大规模集成电路组成。 微控制器（MCU）是汽车电子控制单元ECU的核心，以CPU为核心，是集成在一块芯片上的微型计算机。ECU是包括微控制器和相关外围接器件的电路板的总称，是微控制器在汽车的应用系统。 2. ECU的作用 参数控制 故障自诊断和保护功能 3. ECU的工作原理 4. 常见的ECU的类型 ECU的控制范围已经扩张到巡航控制、灯光控制 、安全气囊控制、悬架控制 、燃油加热控制、排气控制、制动控制、EGR和增压压力控制等。 1. EMS（Engine Mangement System）发动机管理系统 2. TCU（Transmision Control Unit）自动变速箱控制单元 3. BCM（Body Control Module）车身控制模块 4. ESP（Electronic Stability Program）车身电子稳定控制系统，车身电子稳定控制系统 5. BMS（Battery Management System）电池管理系统 6. VCU（Vehicle Control Unit）整车控制器 三、电机控制器（MCU） MCU是新能源汽车特有的核心功率电子单元，通过接受VCU的车辆行驶控制指令，控制电机输出指定的扭矩和转速，驱动车辆行驶。实现把动力电池的直流电能转换为所需的高压交流电、并驱动电机本体输出机械能。 MCU具有电机系统故障诊断保护和存储功能；MCU由外壳及冷却系统、功率电子单元、控制电路、底层软件和控制算法软件组成 四、 电池管理系统（BMS） 通过BMS实现对电芯的管理，以及与整车的通讯及信息交换；BMS能够提高电池的利用率，防止电池出现过充电和过放电，延长电池的使用寿命，监控电池状态 本文来源:汽车电子库
2024-09-27 881浏览
-
精密半导体参数测试解决方案 直播时间：01月08日 10:00
- AI需求强劲增长，富士康第四季度营收超预期
- 又有11家中企被纳入实体清单，涉及光刻机…
- 苹果A系列芯片十年进化：晶体管数量激增19倍，晶圆成本跃升300%
- 豪掷800亿美元！微软宣布加码AI数据中心
- 11家中国实体被纳入实体清单，美资禁止投资中国三个行业
- 不跟风2纳米，联发科下一代天玑9500芯片采用台积电N3P工艺
- 华勤技术收购豪成智能科技，强化机器人业务领域布局
- “超越EUV”时代：美国研发拍瓦级铥激光器有望大幅提升芯片制造效率
- 关注我们
-
扫码关注面包板社区
