Linux内核-文件系统-位图操作
inode节点概念
文件与磁盘的映射
文件系统概念
不管读取什么磁盘上的资源，都是先getblk（获取该资源对应的设备和块号的高速缓冲区），然后在bread（确认有效数据的高速缓冲区），最后再进行区域内存的拷贝
一个设备的文件系统框架
所有块的大小都是固定的,称为盘块或磁盘块
扇区：块设备上一个长度为512B的数据块
在不同的文件系统中扇区和盘块的对应关系不同
- 两个扇区对应一个盘块–>1024B
- 四个扇区对应一个盘块–>2048B
i节点位图块中的一个比特对应一个i节点，如果是两个扇区一个盘块，那么i节点就是1024*8 = 8191个i节点,因为i节点位图的第0位不用
逻辑块位图中一个比特对应一个逻辑块
超级块结构体
在超级块结构体中有
// 内存中磁盘超级块结构
struct super_block {
unsigned short s_ninodes; // 节点数
unsigned short s_nzones; // 逻辑块数
unsigned short s_imap_blocks; // i 节点位图所占用的数据块数
unsigned short s_zmap_blocks; // 逻辑块位图所占用的数据块数
unsigned short s_firstdatazone; // 第一个数据逻辑块号,相对于引导块而言
unsigned short s_log_zone_size; // log(数据块数/逻辑块)
unsigned long s_max_size; // 文件最大长度
unsigned short s_magic;
/* These are only in memory */
struct buffer_head * s_imap[8]; // i 节点位图缓冲块指针数组(占用 8 块，可表示 64M)
struct buffer_head * s_zmap[8]; // 逻辑块位图缓冲块指针数组
unsigned short s_dev; // 超级块所在的设备号
struct m_inode * s_isup; // 被安装的文件系统根目录的 i 节点。(isup-super i)
struct m_inode * s_imount; // 被安装到的 i 节点
unsigned long s_time; // 修改时间
struct task_struct * s_wait; // 等待该超级块的进程
unsigned char s_lock; // 被锁定标志
unsigned char s_rd_only; // 只读标志
unsigned char s_dirt; // 已修改标志（脏标志）
};其中的
struct buffer_head * s_imap[8]; // i 节点位图缓冲块指针数组(占用 8 块，可表示 64M)
struct buffer_head * s_zmap[8]; // 逻辑块位图缓冲块指针数组指的是指向i节点位图和指向逻辑块位图的buffer_head指针数组,在这里每个数组都有八项，说明在当前linux0.1内核中一个文件系统支持8个i节点位图和8个逻辑块位图
那么对应逻辑块的最大大小：
8（个缓冲区头）* 1024（一个逻辑块位图1024字节） * 8（一个字节8个bit）* 1024（1个bit对应一个块） = 64M
i节点同理
位图操作源码bitmap.c
释放逻辑块free_block
//// 释放设备 dev 上数据区中的逻辑块 block。
// 复位指定逻辑块 block 的逻辑块位图比特位
void free_block(int dev, int block)释放逻辑块总共分为两个操作：
释放掉指定的逻辑块
struct super_block * sb;
struct buffer_head * bh;
if (!(sb = get_super(dev))) //get super block
panic("trying to free block on nonexistent device");
if (block < sb->s_firstdatazone || block >= sb->s_nzones) // 若逻辑块号小于首个逻辑块号或者大于设备上总逻辑块数
panic("trying to free block not in datazone");
bh = get_hash_table(dev,block); // 在hash表中找到该数据块
if (bh) {
if (bh->b_count != 1) {
printk("trying to free block (%04x:%d), count=%d\n",
dev,block,bh->b_count);
return;
}
bh->b_dirt=0; // 复位脏（已修改）标志位
bh->b_uptodate=0; // 复位更新标志
brelse(bh); // 释放缓冲块
}在最开始调用get_super函数获取得到这个设备对应的超级块,然后检查传入的逻辑块号是否是合理的
接着就使用get_hash_table在哈希表中获取得到对应设备异或逻辑块号的高速缓冲区块
如果得到了逻辑块，查看是否只有当前进程使用这个逻辑块，如果不是的话说明还有进程正在使用，还不能释放；如果只有当前进程使用，那么就将b_dirt和b_uptodate复位，并且释放缓冲块
注意：这里为什么没有调用getblk获取对应的高速缓冲区块，应该是本来getblk就会进行复位操作，这样子就多此一举的
复位指定逻辑块对应的逻辑块位图中的比特位
block -= sb->s_firstdatazone - 1 ;
// 计算 block 在数据区开始算起的逻辑块号（从 1 开始计数）。然后对逻辑块(区段)位图进行操作，复位对应的比特位
if (clear_bit(block&8191,sb->s_zmap[block/8192]->b_data)) {
printk("block (%04x:%d) ",dev,block+sb->s_firstdatazone-1);
panic("free_block: bit already cleared");
}
// 置相应逻辑块位图所在缓冲区已修改标志。
sb->s_zmap[block/8192]->b_dirt = 1;block -= sb->s_firstdatazone - 1 ;这里是算出block相对于逻辑块开始的块号s_firstdatazone的数值，因为逻辑块号是相对于引导块而言的clear_bit(block&8191,sb->s_zmap[block/8192]->b_data)这里使用了一个嵌入式汇编宏clear_bit(nr,addr)
//// 复位指定地址开始的第 nr 位偏移处的比特位。返回原比特位的反码（1 或 0）。
// 输入：%0 - eax（返回值)，%1 - eax(0)；%2 - nr，位偏移值；%3 - (addr)，addr 的内容。
#define clear_bit(nr,addr) 参数第一项：block&8191,这里是让与操作得到的结果只能是[0,8191]
参数第二项：sb->s_zmap[block/8192]->b_data，这里block/8192是每8192个block作为数组的一项
二者结合起来看，是因为struct buffer_head * s_zmap[8];逻辑块位图一共有八个，对于每一个单独的逻辑块位图他们的bit位置是相同的，所以找到了对于s_zmap指针数组,他指向的b_data就是一块逻辑块位图,然后第一项得到要复位这块逻辑块位图的第几位
最后记得将这个逻辑块位图对应高速缓冲区头中的b_dirt置1,表明这个高速缓冲区已经被修改了
申请逻辑块new_block
////向设备 dev 申请一个逻辑块（磁盘块，区段）。返回逻辑块号。
// 置位指定逻辑块 block 的逻辑块位图比特位。
int new_block(int dev)该函数用于向指定的设备申请一个逻辑块
主要分为三个操作
获取逻辑块位图空闲比特位
struct buffer_head * bh;
struct super_block * sb;
int i,j;
if (!(sb = get_super(dev)))
panic("trying to get new block from nonexistant device");
j = 8192;
for (i=0 ; i<8 ; i++)
if (bh=sb->s_zmap[i])
if ((j=find_first_zero(bh->b_data))<8192)
break;
if (i>=8 || !bh || j>=8192)
return 0;首先也是先从根据设备号获取得到指定的超级块，因为超级块存储着逻辑块位图和i节点位图信息
然后就是通过一个for循环去寻找逻辑块位图中第一个有空闲的比特位
for (i=0 ; i<8 ; i++)是因为s_zmap数组**一共八项,**每一项管理一块逻辑块位图，然后让bh=sb->s_zmap[i]在每一块位图上试j=find_first_zero(bh->b_data))<8192表示如果找到了第一个为0的比特位，并且没有超过这个位图块的大小，那么就是找到了
最后进行一个简单的判断查看找到的比特是否在合理的位置
置位逻辑块位图
if (set_bit(j,bh->b_data))
panic("new_block: bit already set");
bh->b_dirt = 1;
j += i*8192 + sb->s_firstdatazone-1;
if (j >= sb->s_nzones)
return 0;经过上面for循环找到了比特位和对应的逻辑块位图的高速缓冲区，那么就通过set_bit宏去设置这个比特位
//// 置位指定地址开始的第 nr 个位偏移处的比特位(nr 可以大于 32！)。返回原比特位（0 或 1）。
// 输入：%0 - eax（返回值)，%1 - eax(0)；%2 - nr，位偏移值；%3 - (addr)，addr 的内容。
#define set_bit(nr,addr)置位后说明高速缓冲区有数据更新，将b_dirt置1
j += i*8192 + sb->s_firstdatazone-1是计算出该比特位在整个设备内存中的位置,j表示他指向的逻辑块号，如果超过了最大的逻辑块号就报错
获取逻辑块号对应的高速缓冲区块
if (!(bh=getblk(dev,j))) //==============key============
panic("new_block: cannot get block");
if (bh->b_count != 1)
panic("new block: count is != 1");
clear_block(bh->b_data);
bh->b_uptodate = 1;
bh->b_dirt = 1;
brelse(bh);
return j;最后是获取设备号和该逻辑块号对应的高速缓冲区块getblk，拿到这个对应的高速缓冲区块之后会去判断是否b_count为1
它不是为了处理正常情况，而是为了捕捉文件系统逻辑上的严重错误（Bug）。 在正确的内核逻辑下，getblk 返回的 b_count 必须等于 1。
new_block 的作用是分配一个全新的、空闲的磁盘块。它的查找依据是逻辑块位图（s_zmap）。
- 在调用
getblk之前：函数已经通过find_first_zero在位图中找到了一个明确标记为“空闲（0）” 的比特位，并立即调用set_bit将其置为“占用（1）”。 - 关键推论：既然这个磁盘块号
j在位图中是“空闲”的，那就意味着当前文件系统中没有任何一个文件（inode）指向这个块号。因此，理论上绝对不可能有任何进程正在通过文件系统路径访问这个块。
既然没有进程通过文件系统访问它，那么当 getblk 去哈希表里查找 (dev, j) 时，可能出现的只有两种情况：
| 情况 | 哈希表中是否存在？ | b_count 原本是多少？ | getblk 后的 b_count | 结果 |
|---|---|---|---|---|
| 情况 A（缓存残留） | 存在（之前用过，释放后还在缓存里） | 0（无人使用，但数据残留） | 0 → 1 | 正常 |
| 情况 B（全新分配） | 不存在 | 无 | 从空闲链表拿新块，置为 1 | 正常 |
在这两种正常场景下，getblk 返回时 b_count 都是 1。
然后调用clear_block宏将这块高速缓冲区数据清空
// 将指定地址(addr)处的一块内存清零。嵌入汇编程序宏。 256B
// 输入：eax = 0，ecx = 数据块大小 BLOCK_SIZE/4，edi = addr。
#define clear_block(addr) 清空后表明这块高速缓冲区数据更新了，把b_uptodate和b_dirt都置1。然后释放掉这块内存的占用brelse
释放指定i节点free_inode
//// 释放指定的 i 节点。
// 复位对应 i 节点位图比特位
void free_inode(struct m_inode * inode)
{
struct super_block * sb;
struct buffer_head * bh;
if (!inode)
return;
if (!inode->i_dev) {
memset(inode,0,sizeof(*inode));
return;
}
if (inode->i_count>1) {
printk("trying to free inode with count=%d\n",inode->i_count);
panic("free_inode");
}
if (inode->i_nlinks)
panic("trying to free inode with links");
if (!(sb = get_super(inode->i_dev)))
panic("trying to free inode on nonexistent device");
if (inode->i_num < 1 || inode->i_num > sb->s_ninodes)
panic("trying to free inode 0 or nonexistant inode");
if (!(bh=sb->s_imap[inode->i_num>>13]))
panic("nonexistent imap in superblock");
if (clear_bit(inode->i_num&8191,bh->b_data))
printk("free_inode: bit already cleared.\n\r");
bh->b_dirt = 1;
memset(inode,0,sizeof(*inode));
}这里的流程和前面释放指定逻辑块的流程和思路都是一样的
先把i节点对应的i节点位图中的bit置0,然后情况i节点位图中的信息
创建inode
//// 为设备 dev 建立一个新 i 节点。返回该新 i 节点的指针。
// 在内存 i 节点表中获取一个空闲 i 节点表项，并从 i 节点位图中找一个空闲 i 节点。
struct m_inode * new_inode(int dev)
{
struct m_inode * inode;
struct super_block * sb;
struct buffer_head * bh;
int i,j;
if (!(inode=get_empty_inode())) //=======key=========
return NULL;
if (!(sb = get_super(dev)))
panic("new_inode with unknown device");
j = 8192;
for (i=0 ; i<8 ; i++)
if (bh=sb->s_imap[i])
if ((j=find_first_zero(bh->b_data))<8192)
break;
if (!bh || j >= 8192 || j+i*8192 > sb->s_ninodes) {
iput(inode);
return NULL;
}
if (set_bit(j,bh->b_data))
panic("new_inode: bit already set");
bh->b_dirt = 1;
inode->i_count=1;
inode->i_nlinks=1;
inode->i_dev=dev;
inode->i_uid=current->euid;
inode->i_gid=current->egid;
inode->i_dirt=1;
inode->i_num = j + i*8192;
inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
return inode;
}- 通过
super_block找到对应的inode信息（i节点位图，逻辑块位图） - 通过inode操作函数找到对应的inode的分配内存
- 设置inode位图中对应的位1
- 返回设置好的inode