ext2读取并产生间接块和数据块
读取并产生数据块和间接块
在学习页缓存的时候，我们看到这样一张图：
do_generic_file_read()函数是通用的读文件函数，先从pagecache中读取，当缓存不命中的时候进行进行文件预读。预读算法则从硬盘上读取数据填充这个pagecache。从硬盘上读取数据的函数read_pages，要隔离各种文件系统读取文件内容的方式，就是通过给定文件关联的inode,利用函数指针mapping->a_ops->readpages读取文件内容。
const structaddress_space_operations ext2_aops = {
.readpage =ext2_readpage,
.readpages =ext2_readpages,
.writepage =ext2_writepage,
……
};
staticint ext2_readpages(struct file*file, struct address_space *mapping,
structlist_head *pages, unsigned nr_pages)
{
returnmpage_readpages(mapping, pages, nr_pages, ext2_get_block);
}
要从硬盘上读文件，首先要找到文件数据所在的数据块， ext2_get_block实现的就是这个关键的功能。ext2_get_block的函数声明是：
intext2_get_block(struct inode *inode, sector_t iblock, struct buffer_head*bh_result, int create);
该函数是对ext2_get_blocks的封装，其中的iblock是inode中的第几块.实际上，所有希望使用VFS的标准函数的文件系统都必须定义一个类型为get_block_t的函数，其原型如下：
typedef int(get_block_t)(struct inode *inode, sector_t iblock,
structbuffer_head *bh_result, int create);
接下来我们来看这个函数怎么寻找到数据块的。
首先要说明的是ext2_get_block不仅读取块，还有可能从内存向块设备的数据块写入数据，后者的情况就要创建新块了，而参数中的create就是控制是否创建新块的。
我们先看简单的情况，即只进行读取的情况，这时ext2_get_blocks的代码流程如下图所示：
ext2_get_block_to_path找到通向块的路径，ext2_get_branch循着这个路径到达一个数据块。
什么是路径？
要解释路径，就要讲讲ext2_inode是如何组织文件的。我们观察ext2_inode数据结构，发现有一个i_block字段，其中存放了属于该文件的块的地址，该数组大小为EXT2_N_BLOCKS，该值为15。
struct ext2_inode {
……
__le32 i_block[EXT2_N_BLOCKS];/*Pointers to blocks */
……
}
相关的宏定义如下：
#define EXT2_NDIR_BLOCKS 12 //直接块数目
#define EXT2_IND_BLOCK EXT2_NDIR_BLOCKS //简单间接12
#define EXT2_DIND_BLOCK (EXT2_IND_BLOCK+ 1) //二级间接13
#define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK+ 1) //三级间接14
#define EXT2_N_BLOCKS (EXT2_TIND_BLOCK+ 1) //ext2_inode中i_blocks数组的大小15
如果这15个项都存放数据块的地址，假设每个块大小是1024，那么文件的最大长度只能是1024*15。那大文件怎么办？linux中使用了一种叫做间接的解决方法，将大文件的数据块的指针间接存储，如下图所示：
i_block[15]中，前12项用来存储直接块号，直接指向属于该文件的各个数据块；第13项实现的是简单直接，即它所指的块不是数据块，而是一个跟数据块大小一样的用来存放数据块指针的块，我们称之为“一次间接块”，一次间接块不用于存储文件数据，专门用于存储块号；i_block[15]中的第14项数据实现的二次间接和第15项中实现的三次间接同理。
我们回到ext2_get_blocks。前面说的ext2_get_block_to_path要找到通向块的路径，就是确定该块是直接的还是间接的？是几次间接？每一次间接在间接块中的偏移量是多少？有了这些信息我们就一定可以定位到一个块了。
depth =ext2_block_to_path(inode,iblock,offsets,&blocks_to_boundary);
depth为1表示要寻找的数据块是直接块，为2表示是一次间接，以此类推。而每一次间接地偏移量保存在offsets数组，即offsets[1]存放的是直接数据块中的第几块，offsets[2]存放的是一次间接块中的第几个块号，等等。
举个例子，如果要寻找的数据块是上图中地址为0X1234。那么depth=3，offsets[1..3]={13,0,1}。
ext2_get_branch跟踪这个路径，最终到达一个数据块。函数中调用sb_bread()相继读取各个间接块。每个块的数据和从路径得知的偏移量，可用于找到指向下一个间接块的指针。一直重复，直到到达一个数据块，这时函数返回null，表示找到数据块了。接下来就检查是否有别的线程在我们读取的时候已经对这个文件进行了截断操作，然后将找到的数据块的信息由bh_result返回给上层函数进行数据块的读取。
需要向块设备写入数据的情况相对就复杂一点了。这时需要创建新块。创建新块需要两个信息：
找到一个空闲块，作为新块。为了使同一个文件的数据块更为紧凑，内核会进行预留块操作，这个我们稍后讨论。
新块的地址指针存放在哪里？直接数据块？间接块？几次间接？
之前说过，ext2_get_branch函数返回null表示找到数据块，那么非空的情况返回的是什么呢？是一个Indirect类型的数据，表示最后一个间接块的地址，以此作为文件扩展的起点。我们先看Indirect的定义。
typedef struct {
__le32 *p;
__le32 key;
structbuffer_head *bh;
} Indirect;
这是一个结构体，key表示块号，key的值是p所指向的内存中的地址存放的数值。缓冲头bh用于在内存中保存块的数据。
注意是先有p再有key，即key是用p所指向的地址中的数据来赋值的。
static inline voidadd_chain(Indirect *p, struct buffer_head *bh, __le32 *v)
{
p->key= *(p->p = v);
p->bh= bh;
}
Indirect实例有完整和不完整两种状态。完整状态是指key不为0，而p指向key在内存中的地址，这时相当于块号信息存储了两次，即*p=key。不完整状态是指key值为0的时候，这时候p所指的地方存的key还是初始值0。内核需要找到一个空闲的块号填充key。
什么时候Indirect实例是不完整的呢？当ext2_get_branch循着路径试图到达一个数据块时，将过程中读取到的间接块信息保存在Indirect类型的数组chain中，每一次填充chain数组中的Indirect实例，都会检查key是否为0。如果是，则表示要寻找的数据块不存在，即检测到没有指向下一个层次间接块（或数据块，如果是直接分配）的指针，这时返回当前的这个不完整的Indirect实例。这时候p成员指向下一层次间接块或数据块应该出现在间接块中的位置，但key为0，因为该块尚未分配。下图就表示了这样一种情况：需要寻址间接块所指的第三个数据块，该块现在尚不存在，但需要使用。这时候的p=0X1002=0X1000+2，而key=0。
我们到达不了一个数据块，那就要分配块了。首先检查当前文件节点是否为分配工作做好准备了，即保证ext2_inode_info->i_block_alloc_info不为null，因为其中包含了分配块时需要的信息。接下来的工作就是搜索空闲的数据块了，由函数ext2_find_goal()完成。由于文件组织的紧凑性，目标块的位置由好到坏：
与逻辑相邻的数据块物理相邻的空闲块
与当前间接块相邻或相近的空闲块
同一个柱面的空闲块
找到目标块后，函数计算用于保存间接信息的间接块和数据块的数量，分别保存在indirect_blks和count中。他们都是需要分配的块。实际的分配工作由ext2_alloc_branch完成。
块分配
ext2_alloc_branch函数调用ext2_alloc_blocks对给定的新路径分配所需的块，并建立连接块的间接链，即建立间接块的Indirect实例。所以ext2_alloc_blocks一次性把需要分配的块都分配到了。我们看他怎么做到的。实际上分配块的繁重的任务是由ext2_new_blocks完成的，ext2_alloc_blocks一直重复的调用它直到完成目的。到现在，我们发现很多创建的工作都是再ext2_new_blocks中完成的，它通过处理预留窗口或者是查看位图查找空闲块，机制很繁琐。先来看看ext2_new_blocks的函数原型：
ext2_fsblk_text2_new_blocks(struct inode *inode, ext2_fsblk_t goal,
unsigned long *count, int*errp);
inode表示当前文件节点，goal是目标块号（指定优先从哪个块开始分配），count指定所需块数，errp传递错误码，函数返回已分配的块序列中的第一个块号。还有一点值得注意：该函数总是分配连续的块。函数流程如下：
其中ext2_try_to_allocate_with_rsv实现了实际分配数据块的操作，有可能使用预留机制。函数原型如下：static ext2_grpblk_t
ext2_try_to_allocate_with_rsv(structsuper_block *sb, unsigned int group,
structbuffer_head *bitmap_bh, ext2_grpblk_t grp_goal,
struct ext2_reserve_window_node *my_rsv,//为null则不使用预留机制
unsignedlong *count)
呼~~~不想接着挖了，看了代码不难，主要就是根据预留窗口和目标块确定一个搜索区域，在块分配位图中搜索连续的空闲比特位。最后讲讲搜索区域的不同情况吧~