9.2.5  位图

Ext2中,是采用位图来描述数据块和索引节点的使用情况的,每个块组中都有两个块,一个用来描述该组中数据块的使用情况,另一个描述该组中索引节点的使用情况。这两个块分别称为数据块位图块和索引节点位图块。数据位图块中的每一位表示该组中一个块的使用情况,如果为0,则表示相应数据块空闲,为1,则表示已分配,索引节点位图块的使用情况类似。

Ext2在安装后,用两个高速缓存分别来管理这两种位图块。每个高速缓存最多同时只能装入Ext2_MAX_GROUP_LOADED位图块或索引节点块,当前该值定义为8,所以也应该采用一些算法来管理这两个高速缓存,Ext2中采用的算法类似于LRU算法。

前面说过,ext2_sp_info结构中有四个域用来管理这两个高速缓存,其中s_block_bitmap_number[]数组中存有进入高速缓存的位图块号(即块组号,因为一个块组中只有一个位图块),而s_block_bitmap[]数组则存储了相应的块在高速缓存中的地址。

s_inode_bitmap_number[]s_inode_bitmap[]数组的作用类似上面。

我们通过一个具体的函数来看Ext2是如何通过这四个域管理位图块高速缓存的。在Linux/fs/ext2/balloc.c中,有一个函数load__block_bitmap(),它用来调入指定的数据块位图块,下面是它的执行过程:

如果指定的块组号大于块组数,出错,结束;

通过搜索s_block_bitmap_number[]数组可知位图块是否已进入高速缓存,如果已进入,则结束,否则,继续;

如果块组数不大于Ext2_MAX_GROUP_LOADED,高速缓存可以同时装入所有块组的数据块位图块,不用采用什么算法,只要找到s_block_bitmap_number[]数组中第一个空闲元素,将块组号写入,然后将位图块调入高速缓存,最后将它在高速缓存中的地址写入s_block_bitmap[]数组中;

如果块组数大于Ext2_MAX_GROUP_LOADED,则需要采用以下算法;

首先通过s_block_bitmap_number[]数组判断高速缓存是否已满,若未满,则操作过程类似上一步,不同之处在于需要将s_block_bitmap_number[]数组各元素依次后移一位,而用空出的第一个元素存储块组号,s_block_bitmap[]也要做相同处理;

如果高速缓存已满,则将s_block_bitmap[]数组最后一项所指的位图块从高速缓存中交换出去,然后调入所指定的位图块,最后对这两个数组作和上面相同的操作;

可以看出,这个算法很简单,就是对两个数组的简单操作,只是在块组数大于Ext2_MAX_GROUP_LOADED时,要求数组的元素按最近访问的先后次序排列,显然,这样也是为了更合理的进行高速缓存的替换操作。