关于块预留机制的一些基本概念

1、理论依据

为什么要采用块预留机制呢？

这个应该还是局部性原理的一种表现。

在磁盘上组织文件时，我们想将文件的数据尽可能存放在连续的磁盘块上，这样读写文件时，因为磁头移动的距离比较短，故速度会有很大提高。

2、块预分配机制

旧的（有多旧？不去考证最旧，kernel 2.4.0即可作为样本）ext2采用了一种机制preallocation，可称之为块预分配机制。实现方法是当为文件分配一个磁盘块时，顺手牵羊地在该磁盘块周围预先多分配几个块。这样，下次再为文件分配磁盘块时，就可以使用之前预分配的块，这样既减少了查找空闲块的时间，又能使文件的数据在磁盘上连续存放。

注意这里的预分配，在磁盘块位图上已经做了修改，所以从文件系统使用磁盘的角度来看，这些预分配的磁盘块与已分配的磁盘块是一样的。但是预留块的信息是存放在ext2_inode_info结构中的，该结构只是在内存中存在。这就埋下了一个隐患了。

3、ext3为什么一开始禁用ext2的块预分配机制

（这里说的一开始，也不去考证日期，只认为是刚刚发布ext3吧。）ext3对ext2的最大改进就是增加了日志功能。日志的主要功能是减少系统崩溃后的文件系统的恢复时间，核心思想是将关系到文件系统一致性的关键信息（如超级块、块组描述符块，inode位图块、磁盘块位图块等）及时地写到磁盘的日志空间中，这样一旦发生崩溃，可以利用日志空间的数据对文件系统进行恢复。关于日志将有另文专论，在此就不展开。

如果ext3不禁用ext2的块预分配机制，考虑一种情况，假设为文件1分配了磁盘块203，并为之预分配了204，并修改了磁盘块位图b1，这个位图会被ext3写到日志中去。假设此时，系统崩溃了，那么恢复时，根据磁盘块位图b1，磁盘块204已经被使用，但是因为保存预分配信息204对应的ext2_inode_info结构已随着系统崩而消失，于是文件系统再也不知道到底是哪个文件使用了磁盘块204，或者是预留了磁盘块204。这就造成了一种不一致性，磁盘块204实际上并未被任何文件使用，但是因为磁盘块位图b1中标记它已被使用，它就“被使用了”。只有当文件系统进行彻底扫描，才会发现块204并未被任何文件使用，进而才能重新把它标记为空闲块。

因为日志功能会使ext2的块预分配机制造成文件系统的不一致，故ext3一开始是禁用ext2的块预分配机制的。正所谓问题就是一个新的机会，Mingming Cao等人为ext3设计了块预留机制（block reservation），解决了上述问题。

4、ext3块预留机制 block reservation

块预留机制的核心思想是文件系统应该提前考虑如果文件增长，可以从哪块空间分配磁盘块，并将这些磁盘块预留。采用这种方法，当文件增长时，会在磁盘的合适位置有空闲磁盘块供使用。

为了达到这个目的，ext3块分配器被改为基于预留机制了。当一个文件第一次需要分配一个新块时，文件系统为它创建一个预留窗口，该窗口中保留了一些磁盘块（初始值为8个），然后从预留窗口中分配磁盘块。当预留窗口中的块用完时，尽量会在旧的预留窗口周围创建一个扩展的预留窗口，以代替旧的预留窗口。预留窗口会持续到写文件的进程关闭文件，然后，这些预留块又重新变为空闲块。

有趣的是，文件系统本身并不跟踪这些预留块。预留块由一颗红黑树管理。块预留机制不能真正阻止别的文件分配属于预留窗口的磁盘块。因为，文件系统优先考虑块预留机制，尽可能在预留窗口中分配磁盘块，并且，这些预留窗口不会重叠，但是，某些情况下，比如说所有空闲块都被预留了，则文件系统就不会考虑块预留机制，从任何地方都可以分配磁盘块。

注意块预留机制与预分配块机制的本质区别是块预留机制是在内存中操作的，也仅仅是在内存中操作，不会修改真正存在磁盘上的磁盘块位图。这样就不会影响ext3的日志功能了。

5、新的ext2为什么也采用块预留机制

开玩笑吧？ext2不是采用块预分配机制么？为什么这里又说采用了块预留机制？这是事物发展的必然。新的（有多新？不去考证最新，kernel 2.6.35即可作为样本） ext2也采用了块预留机制。可以说块预留机制发轫于ext3，结果大家发现不错，于是将ext2的块预分配机制废掉了，也采用块预留机制了。所以你看新的代码，发现 ext2也采用了块预留机制了。

6、块预留信息的组织方式——红黑树

为什么要选择红黑树呢？

主要是查找速度快，因为红黑树是一种平衡的二叉排序树么。

一个块预留信息其实就是一个区间，比如说[8,12]，[13,18]等等，并且这些区间是不能重叠的。这样图1上每个节点的数值在这里就要变成一个区间了，见图2：

至于红黑树相关的代码，在lib/rbtree.c中，网上有很多帖子分析，这里从略了。