文件系统中重要的概念有大概有超级块、inode、file、文件描述符、文件缓存系统、目录。下面我们逐个说一下。
超级块是负责管理整个文件系统,他记录了文件系统的元数据。从数据结构中我们可以看到他记录了文件系统的inode数量、文件系统在硬盘中占据的扇区数、inode位图、数据块位图、文件系统在硬盘中第一块的块号、该文件系统中文件大小的最大值。 #### 1.1 inode数量 文件系统中每个文件对应一个inode,文件的内容需要占据存储空间,而inode本身也需要存储空间,inode数量决定的了文件系统的可存储文件的个数。 #### 1.2 文件系统位置 一个硬盘分为很多个扇区,可以同时存在多个文件系统,所以每个文件系统需要记录他在硬盘中的首块号和块数。 #### 1.3 inode位图、数据块位图 inode位图是标记文件系统中,哪些inode节点已经被使用了,数据块位图则是标记哪些数据块被使用了。 一个文件系统在硬盘中的布局如下。
在这里插入图片描述
文件系统中,每个文件对应一个inode节点,inode节点记录了文件的元数据。比如创建者、创建时间、文件大小、权限、数据块信息等。inode节点是文件系统中非常重要的概念,unix/linux系统万物皆文件的实现和inode有很大的关系。inode节点屏蔽了不同类型文件的细节,为上层提供抽象的接口。
file结构体是实现多个进程操作文件的结构体。他指向一个inode节点。因为inode保存的是文件的元数据。他对每个进程来说都是一样的。但是一个文件,在每个进程的视角下,有些属性是不一样的,比如文件偏移,文件的打开标记(可读可写可执行)。这些是每个进程独立的信息。
文件描 述符本质是一个数字索引。他和文件系统其实没有太大关系,他主要是用于进程中。进程进行通过文件描述符可以找到对应的文件。
相对内存读写而言,读写硬盘的速度是非常慢的,如果每次读写都要和硬盘打交道,那无疑是很低效的。所以文件系统中加了一层缓存。缓存系统管理着文件数据的有效性。减少对硬盘的操作。
我们知道操作系统中的文件其实是一棵树,而目录就是用来实现这棵树的重要数据结构。因为在文件树中,文件就是叶子节点。目录则是非叶子节点。目录本质也是文件。他和一般文件的区别是,一般文件存储的是用户的数据,目录存储的则是文件的信息。
文件系统的本质是利用一些策略对一块存储进行管理。所以我们首先需要了解文件系统的数据结构。
/*
* This file has definitions for some important file table
* structures etc.
*/
#ifndef _FS_H
#define _FS_H
#include <sys/types.h>
/* devices are as follows: (same as minix, so we can use the minix
* file system. These are major numbers.)
*
* 0 - unused (nodev)
* 1 - /dev/mem
* 2 - /dev/fd
* 3 - /dev/hd
* 4 - /dev/ttyx
* 5 - /dev/tty
* 6 - /dev/lp
* 7 - unnamed pipes
*/
#define IS_SEEKABLE(x) ((x)>=1 && (x)<=3)
#define READ 0
#define WRITE 1
// 预读写
#define READA 2 /* read-ahead - don't pause */
#define WRITEA 3 /* "write-ahead" - silly, but somewhat useful */
void buffer_init(long buffer_end);
// 设备的主设备号和次设备号,低八位是次设备号,高位是主设备号
#define MAJOR(a) (((unsigned)(a))>>8)
#define MINOR(a) ((a)&0xff)
// 文件名长度
#define NAME_LEN 14
// 文件系统的根inode节点号
#define ROOT_INO 1
// 块位图和inode位图占据的最大硬盘块数
#define I_MAP_SLOTS 8
#define Z_MAP_SLOTS 8
// 超级块的魔数,说明是有效的超级块
#define SUPER_MAGIC 0x137F
// 一个进程打开文件数的大小
#define NR_OPEN 20
// 系统同时打开的inode数大小,即同时只能打开32个文件
#define NR_INODE 32
// file结构体数,进程间共享的
#define NR_FILE 64
// 超级块数,即文件系统的个数
#define NR_SUPER 8
#define NR_HASH 307
// 缓存文件系统数据的buffer个数,操作系统启动的时候初始化该变量
#define NR_BUFFERS nr_buffers
// 硬盘一块对应的字节数
#define BLOCK_SIZE 1024
// 2 >> 10 即块的大小,用于计算字节数到块数
#define BLOCK_SIZE_BITS 10
#ifndef NULL
#define NULL ((void *) 0)
#endif
// 每个硬盘块有几个inode节点,即块大小除以硬盘中每个inode结构的大小,硬盘里是d_inode,内存是m_inode结构
#define INODES_PER_BLOCK ((BLOCK_SIZE)/(sizeof (struct d_inode)))
// 每个硬盘块包含的目录项数
#define DIR_ENTRIES_PER_BLOCK ((BLOCK_SIZE)/(sizeof (struct dir_entry)))
// 下面宏用于匿名管道,可结合管道的实现理解
#define PIPE_HEAD(inode) ((inode).i_zone[0])
#define PIPE_TAIL(inode) ((inode).i_zone[1])
#define PIPE_SIZE(inode) ((PIPE_HEAD(inode)-PIPE_TAIL(inode))&(PAGE_SIZE-1))
#define PIPE_EMPTY(inode) (PIPE_HEAD(inode)==PIPE_TAIL(inode))
#define PIPE_FULL(inode) (PIPE_SIZE(inode)==(PAGE_SIZE-1))
#define INC_PIPE(head) \
__asm__("incl %0\n\tandl $4095,%0"::"m" (head))
// 该版本没有用这个定义
typedef char buffer_block[BLOCK_SIZE];
// 管理文件系统的数据缓存的结构
struct buffer_head {
char * b_data; /* pointer to data block (1024 bytes) */
unsigned long b_blocknr; /* block number */
unsigned short b_dev; /* device (0 = free) */
unsigned char b_uptodate;
unsigned char b_dirt; /* 0-clean,1-dirty */
unsigned char b_count; /* users using this block */
unsigned char b_lock; /* 0 - ok, 1 -locked */
struct task_struct * b_wait;
struct buffer_head * b_prev;
struct buffer_head * b_next;
struct buffer_head * b_prev_free;
struct buffer_head * b_next_free;
};
// 文件系统在硬盘里的inode节点结构
struct d_inode {
// 各种标记位,读写执行等,我们ls时看到的
unsigned short i_mode;
// 文件的用户id
unsigned short i_uid;
// 文件大小
unsigned long i_size;
unsigned long i_time;
// 文件的用户组id
unsigned char i_gid;
// 文件入度,即有多少个目录指向他
unsigned char i_nlinks;
// 存储文件内容对应的硬盘块号
unsigned short i_zone[9];
};
// 内存中的inode节点结构
struct m_inode {
// 和d_inode一样
unsigned short i_mode;
unsigned short i_uid;
unsigned long i_size;
unsigned long i_mtime;
unsigned char i_gid;
unsigned char i_nlinks;
unsigned short i_zone[9];
/* these are in memory also */
// 在内存中使用的字段
// 等待该inode节点的进程队列
struct task_struct * i_wait;
// access time文件被访问就会修改这个字段
unsigned long i_atime;
/*
change time,修改文件内容和属性就会修改这个字段,
还有一个是mtime,修改文件内容就会修改这个字段,但是这个版本没有实现
*/
unsigned long i_ctime;
// inode所属的设备号
unsigned short i_dev;
// 该结构引用的inode在硬盘里的号
unsigned short i_num;
// 多少个进程在使用这个inode
unsigned short i_count;
// 互斥锁
unsigned char i_lock;
// inode内容是否被修改过
unsigned char i_dirt;
// 是不是管道文件
unsigned char i_pipe;
// 该节点是否挂载了另外的文件系统
unsigned char i_mount;
// 这个版本没用到
unsigned char i_seek;
/*
数据是否是最新的,或者说有效的,
update代表数据的有效性,dirt代表文件是否需要回写,
比如写入文件的时候,a进程写入的时候,dirt是1,因为需要回写到硬盘,
但是数据是最新的,update是1,这时候b进程读取这个文件的时候,可以从
缓存里直接读取。
*/
unsigned char i_update;
};
// 管理打开文件的内存属性的结构,比如操作位置(inode没有读取操作位置这个概念,),实现系统进程共享inode
struct file {
unsigned short f_mode;
unsigned short f_flags;
unsigned short f_count;
struct m_inode * f_inode;
off_t f_pos;
};
// 超级块,管理一个文件系统元数据的结构
struct super_block {
// inode节点个数
unsigned short s_ninodes;
// 数据块占据的逻辑块总块数
unsigned short s_nzones;
// inode和数据块位图占据的硬盘块数,位图是记录哪个块或者inode节点被使用了
unsigned short s_imap_blocks;
unsigned short s_zmap_blocks;
/*
第一块在硬盘的块号,一个硬盘可以有几个文件系统,
每个文件系统占据一部分,所以要记录开始的块号和总块数
*/
unsigned short s_firstdatazone;
/*
用于计算文件系统块等于多少个硬盘块,硬盘块大小乘以2
的s_log_zone_size次方等于文件系统的块大小(硬盘块的
大小和文件系统块的大小不是一回事,比如硬盘块的大小是1kb,
文件系统是4kb)
*/
unsigned short s_log_zone_size;
// 文件名最大字节数
unsigned long s_max_size;
// 魔数
unsigned short s_magic;
/* These are only in memory */
// 缓存inode位图的内容
struct buffer_head * s_imap[8];
// 缓存数据块位图的内容
struct buffer_head * s_zmap[8];
// 设备号
unsigned short s_dev;
// 挂载在哪个文件的inode下
struct m_inode * s_isup;
struct m_inode * s_imount;
unsigned long s_time;
// 等待使用该超级块的进程队列
struct task_struct * s_wait;
// 互斥访问变量
unsigned char s_lock;
// 文件系统是否只能读不能写
unsigned char s_rd_only;
// 是否需要回写到硬盘
unsigned char s_dirt;
};
// 超级块在硬盘的结构
struct d_super_block {
// inode节点数量
unsigned short s_ninodes;
// 硬盘块数量
unsigned short s_nzones;
// inode位图块数量
unsigned short s_imap_blocks;
// 数据块位图数量
unsigned short s_zmap_blocks;
// 文件系统的第一块块号,不是数据块第一块块号
unsigned short s_firstdatazone;
// 参考上面
unsigned short s_log_zone_size;
// 最大文件长度
unsigned long s_max_size;
// 判断是否是超级块的标记
unsigned short s_magic;
};
// 目录项结构
struct dir_entry {
// inode号
unsigned short inode;
// 文件名
char name[NAME_LEN];
};
// 进程共享的inode列表
extern struct m_inode inode_table[NR_INODE];
// 进程共享的file结构列表
extern struct file file_table[NR_FILE];
// 超级块列表
extern struct super_block super_block[NR_SUPER];
// 缓存区管理
extern struct buffer_head * start_buffer;
// 缓冲区个数
extern int nr_buffers;
上面的数据结构大概可以分为几个部分。超级块、文件系统缓存、管理单个文件的inode、目录,file结构体。
文件系统的结构大概分为2个部分。分别是在硬盘中的结构。在内存中的结构。
在这里插入图片描述
在这里插入图片描述
当进程想操作一个文件的时候,需要告诉文件系统文件的路径和名字,如果相对路径,则文件系统会根据进程的当前工作目录判断出文件的绝对路径。文件系统根据绝对路径,在文件树中逐层查找。最后会找到硬盘中的一个inode节点。然后从pcb中找到一个可用的文件描述符。再从系统中申请一个file结构体。最后完成文件描述符到file结构体到inode节点的关联,后续就可以操作文件了。
在操作系统启动的时候由进程1进行初始化。
// 系统初始化时挂载根文件系统
void mount_root(void)
{
int i,free;
struct super_block * p;
struct m_inode * mi;
if (32 != sizeof (struct d_inode))
panic("bad i-node size");
// 初始化file结构体列表,struct file file_table[NR_FILE];
for(i=0;i<NR_FILE;i++)
file_table[i].f_count=0;
// 如果根文件系统是软盘提示插入软盘
if (MAJOR(ROOT_DEV) == 2) {
printk("Insert root floppy and press ENTER");
wait_for_keypress();
}
// 初始化超级块列表
for(p = &super_block[0] ; p < &super_block[NR_SUPER] ; p++) {
p->s_dev = 0;
p->s_lock = 0;
p->s_wait = NULL;
}
// 读取某个设备(硬盘分区)中的超级块,即根文件系统的超级块
if (!(p=read_super(ROOT_DEV)))
panic("Unable to mount root");
// 获取根文件系统的第一个inode节点,里面存的是根目录的数据
if (!(mi=iget(ROOT_DEV,ROOT_INO)))
panic("Unable to read root i-node");
// mi在下面四个地方有赋值,iget里面的get_empty_inode函数已经设置i_count=1,所以这里加三就行
mi->i_count += 3 ; /* NOTE! it is logically used 4 times, not 1 */
// 超级块挂载到了mi对应的inode节点,p->s_isup设置根文件系统的根节点
p->s_isup = p->s_imount = mi;
// 设置当前进程(进程1)的根文件目录和当前工作目录
current->pwd = mi;
current->root = mi;
free=0;
// 文件系统的逻辑数据块和inode数量
i=p->s_nzones;
while (-- i >= 0)
if (!set_bit(i&8191,p->s_zmap[i>>13]->b_data))
free++;
printk("%d/%d free blocks\n\r",free,p->s_nzones);
free=0;
i=p->s_ninodes+1;
while (-- i >= 0)
if (!set_bit(i&8191,p->s_imap[i>>13]->b_data))
free++;
printk("%d/%d free inodes\n\r",free,p->s_ninodes);
}
这里以读为例子,这时候还没有vfs。其他操作也是类似的。
进程通过系统调用,从而进入中断处理,中断处理从系统调用表里找到sys_read函数执行。
int sys_read(unsigned int fd,char * buf,int count)
{
struct file * file;
struct m_inode * inode;
if (fd>=NR_OPEN || count<0 || !(file=current->filp[fd]))
return -EINVAL;
if (!count)
return 0;
verify_area(buf,count);
inode = file->f_inode;
// 该文件描述符对应的是一个管道文件,并且是读端则读管道
if (inode->i_pipe)
return (file->f_mode&1)?read_pipe(inode,buf,count):-EIO;
if (S_ISCHR(inode->i_mode))
return rw_char(READ,inode->i_zone[0],buf,count,&file->f_pos);
if (S_ISBLK(inode->i_mode))
return block_read(inode->i_zone[0],&file->f_pos,buf,count);
if (S_ISDIR(inode->i_mode) || S_ISREG(inode->i_mode)) {
// 读的长度不能大于剩下的可读长度
if (count+file->f_pos > inode->i_size)
count = inode->i_size - file->f_pos;
// 到底了
if (count<=0)
return 0;
return file_read(inode,file,buf,count);
}
printk("(Read)inode->i_mode=%06o\n\r",inode->i_mode);
return -EINVAL;
}
我们这里只分析普通文件的读写。所以我们继续看file_read函数。
int file_read(struct m_inode * inode, struct file * filp, char * buf, int count)
{
int left,chars,nr;
struct buffer_head * bh;
if ((left=count)<=0)
return 0;
while (left) {
// bmap取得该文件偏移对应的硬盘块号,然后读进来
if (nr = bmap(inode,(filp->f_pos)/BLOCK_SIZE)) {
if (!(bh=bread(inode->i_dev,nr)))
break;
} else
bh = NULL;
// 偏移
nr = filp->f_pos % BLOCK_SIZE;
// 读进来的数据中,可读的长度和还需要读的长度,取小的,如果还没读完继续把块从硬盘读进来
chars = MIN( BLOCK_SIZE-nr , left );
filp->f_pos += chars; // 更新偏移指针
left -= chars; // 更新还需药读取的长度
if (bh) {
char * p = nr + bh->b_data;
while (chars-->0)
put_fs_byte(*(p++),buf++); //复制到buf里
brelse(bh);
} else {
while (chars-->0)
put_fs_byte(0,buf++);
}
}
// 更新访问时间
inode->i_atime = CURRENT_TIME;
// 返回读取的长度,如果一个都没读则返回错误
return (count-left)?(count-left):-ERROR;
}
这个函数主要的操作是从底层读取对应文件的对应数据。这里的底层首先是buffer缓存,如果没有的话需要去硬盘读。我们看bread函数。
struct buffer_head * bread(int dev,int block)
{
struct buffer_head * bh;
// 先从buffer链表中获取一个buffer
if (!(bh=getblk(dev,block)))
panic("bread: getblk returned NULL\n");
// 之前已经读取过并且有效,则直接返回
if (bh->b_uptodate)
return bh;
// 返回读取硬盘的数据
ll_rw_block(READ,bh);
//ll_rw_block会锁住bh,所以会先阻塞在这然后等待唤醒
wait_on_buffer(bh);
// 底层读取数据成功后会更新该字段为1,否则就是读取出错了
if (bh->b_uptodate)
return bh;
brelse(bh);
return NULL;
}
bread函数首先从缓存里读取需要的数据,如果有并且是有效的即最新的数据。则直接返回。如果没有的话,就调用ll_rw_block函数到硬盘读。我们看一下ll_rw_block及相关函数。
void ll_rw_block(int rw, struct buffer_head * bh)
{
unsigned int major;
if ((major=MAJOR(bh->b_dev)) >= NR_BLK_DEV ||
!(blk_dev[major].request_fn)) {
printk("Trying to read nonexistent block-device\n\r");
return;
}
// 新建一个读写硬盘数据的请求
make_request(major,rw,bh);
}
static void make_request(int major,int rw, struct buffer_head * bh)
{
struct request * req;
int rw_ahead;
/* WRITEA/READA is special case - it is not really needed, so if the */
/* buffer is locked, we just forget about it, else it's a normal read */
if (rw_ahead = (rw == READA || rw == WRITEA)) {
// 预读写的时候,buffer被锁则直接返回,因为预读本身不是必须的
if (bh->b_lock)
return;
if (rw == READA)
rw = READ;
else
rw = WRITE;
}
if (rw!=READ && rw!=WRITE)
panic("Bad block dev command, must be R/W/RA/WA");
// 锁住buffer导致bread阻塞
lock_buffer(bh);
/*
写但数据块装载后还没有被修改过
读但内容和硬盘的内容是一致的
*/
if ((rw == WRITE && !bh->b_dirt) || (rw == READ && bh->b_uptodate)) {
unlock_buffer(bh);
return;
}
repeat:
/* we don't allow the write-requests to fill up the queue completely:
* we want some room for reads: they take precedence. The last third
* of the requests are only for reads.
*/
// 请求队列1/3用于读,2/3用于写
if (rw == READ)
req = request+NR_REQUEST;
else
req = request+((NR_REQUEST*2)/3);
/* find an empty request */
while (--req >= request)
// 小于0说明该结构没有被使用
if (req->dev<0)
break;
/* if none found, sleep on new requests: check for rw_ahead */
// 没有找到可用的请求结构
if (req < request) {
// 预读写则直接返回
if (rw_ahead) {
unlock_buffer(bh);
return;
}
// 阻塞等待可用的请求结构
sleep_on(&wait_for_request);
// 被唤醒后重新查找
goto repeat;
}
/* fill up the request-info, and add it to the queue */
req->dev = bh->b_dev;
req->cmd = rw;
req->errors=0;
req->sector = bh->b_blocknr<<1; // 一块等于两个扇区所以乘以2,即左移1位,比如要读地10块,则读取第二十个扇区
req->nr_sectors = 2;// 一块等于两个扇区,即读取的扇区是2
req->buffer = bh->b_data;
req->waiting = NULL;
req->bh = bh;
req->next = NULL;
// 插入请求队列
add_request(major+blk_dev,req);
}
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
struct request * tmp;
req->next = NULL;
cli();
if (req->bh)
req->bh->b_dirt = 0;
// 当前没有请求项,开始处理请求
if (!(tmp = dev->current_request)) {
dev->current_request = req;
sti();
(dev->request_fn)();
return;
}
// 电梯算法插入相应的位置
for ( ; tmp->next ; tmp=tmp->next)
if ((IN_ORDER(tmp,req) ||
!IN_ORDER(tmp,tmp->next)) &&
IN_ORDER(req,tmp->next))
break;
req->next=tmp->next;
tmp->next=req;
sti();
}
我们看到,这里是给一个队列插入了一个请求节点。那么这个队列是啥呢?继续看驱动程序的代码。系统有一张表,保存了驱动程序需要处理的请求和处理函数。
struct blk_dev_struct {
void (*request_fn)(void);
struct request * current_request;
};
struct blk_dev_struct blk_dev[NR_BLK_DEV] = {
{ NULL, NULL }, /* no_dev */
{ NULL, NULL }, /* dev mem */
{ NULL, NULL }, /* dev fd */
{ NULL, NULL }, /* dev hd */
{ NULL, NULL }, /* dev ttyx */
{ NULL, NULL }, /* dev tty */
{ NULL, NULL } /* dev lp */
};
struct request {
int dev; /* -1 if no request */
int cmd; /* READ or WRITE */
int errors;
unsigned long sector;
unsigned long nr_sectors;
char * buffer;
struct task_struct * waiting;
struct buffer_head * bh;
struct request * next;
};
我们看硬盘驱动的初始化代码。
void hd_init(void)
{
blk_dev[MAJOR_NR].request_fn = DEVICE_REQUEST;
set_intr_gate(0x2E,&hd_interrupt);
outb_p(inb_p(0x21)&0xfb,0x21);
outb(inb_p(0xA1)&0xbf,0xA1);
}
#define DEVICE_REQUEST do_hd_reques
do_hd_reques函数就是摘取待处理的请求队列中摘下一个节点然后进行处理。我们这里是读取的操作,所以只看相关代码。把命令和参数写入硬盘控制器。
hd_out(dev,nsect,sec,head,cyl,WIN_READ,&read_intr);
=>
static void hd_out(unsigned int drive,unsigned int nsect,unsigned int sect,
unsigned int head,unsigned int cyl,unsigned int cmd,
void (*intr_addr)(void))
{
register int port asm("dx");
if (drive>1 || head>15)
panic("Trying to write bad sector");
if (!controller_ready())
panic("HD controller not ready");
// 数据准备好触发中断时执行的回调,在blk.h定义,每个驱动都维护了自己的do_hd
do_hd = intr_addr;
outb_p(hd_info[drive].ctl,HD_CMD);
port=HD_DATA;
outb_p(hd_info[drive].wpcom>>2,++port);
outb_p(nsect,++port);
outb_p(sect,++port);
outb_p(cyl,++port);
outb_p(cyl>>8,++port);
outb_p(0xA0|(drive<<4)|head,++port);
outb(cmd,++port);
}
至此,驱动到硬盘控制器的处理完成。我们回到ll_rw_block函数处理,继续往下看,发现执行了
wait_on_buffer(bh);
我们看wait_on_buffer的代码
// 加锁,互斥访问
static inline void wait_on_buffer(struct buffer_head * bh)
{
cli();
while (bh->b_lock)
sleep_on(&bh->b_wait);
sti();
}
// 当前进程挂载到睡眠队列p中,p指向队列头指针的地址
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
/*
*p为第一个睡眠节点的地址,即tmp指向第一个睡眠节点
头指针指向当前进程,这个版本的实现没有采用真正链表的形式,
他通过每个进程在栈中的临时变量形成一个链表,每个睡眠的进程,
在栈里有一个变量指向后面一个睡眠节点,然后把链表的头指针指向当前进程,
然后切换到其他进程执行,当被wake_up唤醒的时候,wake_up会唤醒链表的第一个
睡眠节点,因为第一个节点里保存了后面一个节点的地址,所以他唤醒后面一个节点,
后面一个节点以此类推,从而把整个链表的节点唤醒,这里的实现类似nginx的filter,
即每个模块保存后面一个节点的地址,然后把全局指针指向自己。
*/
tmp = *p;
*p = current;
// 不可中断睡眠只能通过wake_up唤醒,即使有信号也无法唤醒
current->state = TASK_UNINTERRUPTIBLE;
schedule();
// 唤醒后面一个节点
if (tmp)
tmp->state=0;
}
因为bh在ll_rw_block中被加锁了,所以进程被阻塞在这。系统调度其他进程执行。
时间过了很久...
硬盘读好了数据,给系统发了中断。从硬盘驱动的初始化函数中(参考上面的hd_init)我们发现。硬盘中断的处理函数是hd_interrupt。该函数是用汇编定义的。
_hd_interrupt:
pushl %eax
pushl %ecx
pushl %edx
push %ds
push %es
push %fs
movl $0x10,%eax
mov %ax,%ds
mov %ax,%es
movl $0x17,%eax
mov %ax,%fs
movb $0x20,%al
outb %al,$0xA0 # EOI to interrupt controller #1
jmp 1f # give port chance to breathe
1: jmp 1f
1: xorl %edx,%edx
// 把do_hd的内容和edx的交换
xchgl _do_hd,%edx
// 判断do_hd是否有效
testl %edx,%edx
jne 1f
movl $_unexpected_hd_interrupt,%edx
1: outb %al,$0x20
// 执行注册的回调
call *%edx # "interesting" way of handling intr.
pop %fs
pop %es
pop %ds
popl %edx
popl %ecx
popl %eax
iret
该函数执行了do_hd执行的函数。该函数就是在执行do_hd_request时注册的read_intr。
阻塞
static void read_intr(void)
{
if (win_result()) {
bad_rw_intr();
do_hd_request();
return;
}
// 从硬盘控制器的缓存读取数据
port_read(HD_DATA,CURRENT->buffer,256);
CURRENT->errors = 0;
CURRENT->buffer += 512;
CURRENT->sector++;
// 还有数据要读,继续注册该函数,等待中断回调
if (--CURRENT->nr_sectors) {
do_hd = &read_intr;
return;
}
// 结束该request,通知上层进程
end_req
uest(1);
// 处理下一个request
do_hd_request();
}
// 数据读写完后执行该函数
extern inline void end_request(int uptodate)
{
DEVICE_OFF(CURRENT->dev);
// 读写数据成功,数据有效位置1
if (CURRENT->bh) {
CURRENT->bh->b_uptodate = uptodate;
// 唤醒进程
unlock_buffer(CURRENT->bh);
}
if (!uptodate) {
printk(DEVICE_NAME " I/O error\n\r");
printk("dev %04x, block %d\n\r",CURRENT->dev,
CURRENT->bh->b_blocknr);
}
// 唤醒等待该request的请求,貌似暂时没有使用这个字段
wake_up(&CURRENT->waiting);
// 有request可用了
wake_up(&wait_for_request);
CURRENT->dev = -1;
// 更新请求队列,移除当前处理完的节点
CURRENT = CURRENT->next;
}
static inline void unlock_buffer(struct buffer_head * bh)
{
if (!bh->b_lock)
printk("ll_rw_block.c: buffer not locked\n\r");
bh->b_lock = 0;
// 唤醒进程
wake_up(&bh->b_wait);
}
至此,数据读取的过程差不多就结束了,等系统调度时选择该进程执行,然后进程从buffer里就获取了需要的数据,再返回到应用层。
缓存系统主要是处理应用层和硬件层来往的数据,目的是减少这种数据的来回读写。比如读的时候,最好能命中缓存的数据,写的时候,先写到缓存系统,系统会定期刷到硬盘。
为了避免每次对文件的读写都操作硬盘,操作系统实现了一个buffer缓存系统。以此减少和硬盘的交互。buffer系统是在内存里开辟一块空间做缓存。缓存的结构由两部分组成,一个是哈希链表,一个是双向循环链表,第一个链表是使用数据的时候为了快速找到对应的buffer,第二个链表是为了找可用的buffer。 buffer的操作主要是从buffer池中找到一个空闲的结构,然后请求底层,他的下一层是io调度层,buffer的读写都是发请求给底层的调度层,由调度层进行请求的调度,然后调用硬盘驱动层去完成真正的硬盘读写操作。完成后通知buffer层。 我们首先看一下buffer系统的初始化。
// 系统初始化的时候执行该函数,主要是建立buffer对应的数据结构,一个双向循环链表
void buffer_init(long buffer_end)
{
// buffer开始地址,从内存里划出一块
struct buffer_head * h = start_buffer;
void * b;
int i;
// buffer的结束地址
if (buffer_end == 1<<20)
b = (void *) (640*1024);
else
b = (void *) buffer_end;
// buffer_head在头部分配,data字段对应的内容在末端分配,data字段的地址和buffer_head结构的地址要相差至少一个struct buffer_head
while ( (b -= BLOCK_SIZE) >= ((void *) (h+1)) ) {
h->b_dev = 0;
h->b_dirt = 0;
h->b_count = 0;
h->b_lock = 0;
h->b_uptodate = 0;
h->b_wait = NULL;
h->b_next = NULL;
h->b_prev = NULL;
h->b_data = (char *) b;
// 初始化时每个节点都是空闲的,形成一条freelist
h->b_prev_free = h-1;
h->b_next_free = h+1;
h++;
// buffer个数
NR_BUFFERS++;
if (b == (void *) 0x100000)
b = (void *) 0xA0000;
}
// h--后h为最后一个buffer_head结构的地址
h--;
// 整条链都是空闲的
free_list = start_buffer;
// 更新第一个节点的prev指针和最后一个节点的next指针,因为在while循环的时候他们指向了无效的地址
free_list->b_prev_free = h;
h->b_next_free = free_list;
for (i=0;i<NR_HASH;i++)
hash_table[i]=NULL;
}
buffer系统的结构体大致如下:
buffer系统结构体 下面是buffer相关的操作函数。需要使用的时候再具体看就行。
/*
* linux/fs/buffer.c
*
* (C) 1991 Linus Torvalds
*/
/*
* 'buffer.c' implements the buffer-cache functions. Race-conditions have
* been avoided by NEVER letting a interrupt change a buffer (except for the
* data, of course), but instead letting the caller do it. NOTE! As interrupts
* can wake up a caller, some cli-sti sequences are needed to check for
* sleep-on-calls. These should be extremely quick, though (I hope).
*/
/*
* NOTE! There is one discordant note here: checking floppies for
* disk change. This is where it fits best, I think, as it should
* invalidate changed floppy-disk-caches.
*/
#include <stdarg.h>
#include <linux/config.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/system.h>
#include <asm/io.h>
extern int end;
// 内存中开辟的一块内存,end是内核代码的结束地址
struct buffer_head * start_buffer = (struct buffer_head *) &end;
// 哈希链表,主要是为了快速找到数据
struct buffer_head * hash_table[NR_HASH];
// 缓存区的结构是双向循环链表,free_list指向第一个理论上可用的节点,他的最后一个节点是最近被使用的节点
static struct buffer_head * free_list;
// 没有buffer可用而被阻塞的进程挂载这个队列上
static struct task_struct * buffer_wait = NULL;
// 一共有多少个buffer块
int NR_BUFFERS = 0;
// 加锁,互斥访问
static inline void wait_on_buffer(struct buffer_head * bh)
{
cli();
while (bh->b_lock)
sleep_on(&bh->b_wait);
sti();
}
int sys_sync(void)
{
int i;
struct buffer_head * bh;
// 把所有inode写入buffer,等待回写,见下面代码
sync_inodes(); /* write out inodes into buffers */
bh = start_buffer;
for (i=0 ; i<NR_BUFFERS ; i++,bh++) {
wait_on_buffer(bh);
if (bh->b_dirt)
// 请求底层写硬盘操作,等待底层驱动回写到硬盘,不一定立刻写入
ll_rw_block(WRITE,bh);
}
return 0;
}
// 把buffer中属于dev设备的缓存全部回写到硬盘
int sync_dev(int dev)
{
int i;
struct buffer_head * bh;
bh = start_buffer;
// 先把属于该dev的缓存回写硬盘
for (i=0 ; i<NR_BUFFERS ; i++,bh++) {
if (bh->b_dev != dev)
continue;
wait_on_buffer(bh);
if (bh->b_dev == dev && bh->b_dirt)
ll_rw_block(WRITE,bh);
}
// 同步所有inode到buffer中
sync_inodes();
// 把属于该dev的buffer再写一次
bh = start_buffer;
for (i=0 ; i<NR_BUFFERS ; i++,bh++) {
if (bh->b_dev != dev)
continue;
wait_on_buffer(bh);
if (bh->b_dev == dev && bh->b_dirt)
ll_rw_block(WRITE,bh);
}
return 0;
}
// 使属于dev的buffer全部失效
void inline invalidate_buffers(int dev)
{
int i;
struct buffer_head * bh;
bh = start_buffer;
for (i=0 ; i<NR_BUFFERS ; i++,bh++) {
if (bh->b_dev != dev)
continue;
wait_on_buffer(bh);
if (bh->b_dev == dev)
bh->b_uptodate = bh->b_dirt = 0;
}
}
/*
* This routine checks whether a floppy has been changed, and
* invalidates all buffer-cache-entries in that case. This
* is a relatively slow routine, so we have to try to minimize using
* it. Thus it is called only upon a 'mount' or 'open'. This
* is the best way of combining speed and utility, I think.
* People changing diskettes in the middle of an operation deserve
* to loose :-)
*
* NOTE! Although currently this is only for floppies, the idea is
* that any additional removable block-device will use this routine,
* and that mount/open needn't know that floppies/whatever are
* special.
*/
void check_disk_change(int dev)
{
int i;
if (MAJOR(dev) != 2)
return;
if (!floppy_change(dev & 0x03))
return;
for (i=0 ; i<NR_SUPER ; i++)
if (super_block[i].s_dev == dev)
put_super(super_block[i].s_dev);
invalidate_inodes(dev);
invalidate_buffers(dev);
}
// 通过dev和block算出在哈希表的位置
#define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
// 取得哈希链表中某条链表
#define hash(dev,block) hash_table[_hashfn(dev,block)]
// 把节点移出哈希链表和空闲链表
static inline void remove_from_queues(struct buffer_head * bh)
{
/* remove from hash-queue */
if (bh->b_next)
bh->b_next->b_prev = bh->b_prev;
if (bh->b_prev)
bh->b_prev->b_next = bh->b_next;
// bh是哈希链表的第一个节点的话则更新哈希链表的头指针
if (hash(bh->b_dev,bh->b_blocknr) == bh)
hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
/* remove from free list */
// 双向循环链表不能存在这种情况
if (!(bh->b_prev_free) || !(bh->b_next_free))
panic("Free block list corrupted");
bh->b_prev_free->b_next_free = bh->b_next_free;
bh->b_next_free->b_prev_free = bh->b_prev_free;
// bh是当前空闲链表的第一个节点则更新空闲链表的头指针
if (free_list == bh)
free_list = bh->b_next_free;
}
static inline void insert_into_queues(struct buffer_head * bh)
{
/* put at end of free list */
/*
free_list指向第一个空闲的buffer,
free_list->b_prev_free指向最近刚使用的buffer,即每次找到一个可用buffer的时候
都成为free_list的尾节点
*/
bh->b_next_free = free_list;
bh->b_prev_free = free_list->b_prev_free;
free_list->b_prev_free->b_next_free = bh;
free_list->b_prev_free = bh;
/* put the buffer in new hash-queue if it has a device */
bh->b_prev = NULL;
bh->b_next = NULL;
if (!bh->b_dev)
return;
// 头插法插到哈希链表
// 指向哈希链表当前的第一个节点
bh->b_next = hash(bh->b_dev,bh->b_blocknr);
// 哈希链表头指针指向bh
hash(bh->b_dev,bh->b_blocknr) = bh;
// 旧的头指针的prev指针指向bh
bh->b_next->b_prev = bh;
}
// 从哈希链表中找到某个节点
static struct buffer_head * find_buffer(int dev, int block)
{
struct buffer_head * tmp;
// 先找到哈希链表中的某条链表的头指针
for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
if (tmp->b_dev==dev && tmp->b_blocknr==block)
return tmp;
return NULL;
}
/*
* Why like this, I hear you say... The reason is race-conditions.
* As we don't lock buffers (unless we are readint them, that is),
* something might happen to it while we sleep (ie a read-error
* will force it bad). This shouldn't really happen currently, but
* the code is ready.
*/
// 找dev+block对应的buffer
struct buffer_head * get_hash_table(int dev, int block)
{
struct buffer_head * bh;
for (;;) {
// 找不到直接返回NULL
if (!(bh=find_buffer(dev,block)))
return NULL;
// 存在则先把引用数加1,防止别人释放
bh->b_count++;
// 看该buffer是不是正在被使用
wait_on_buffer(bh);
// 可能在阻塞的时候buffer已经被修改过
if (bh->b_dev == dev && bh->b_blocknr == block)
return bh;
// 引用数减一,重新再找
bh->b_count--;
}
}
/*
* Ok, this is getblk, and it isn't very clear, again to hinder
* race-conditions. Most of the code is seldom used, (ie repeating),
* so it should be much more efficient than it looks.
*
* The algoritm is changed: hopefully better, and an elusive bug removed.
*/
// 数据脏或者被锁,脏的位置比锁更高,即被锁了可以接收,脏数据的buffer尽量不用,除非找不到buffer
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
struct buffer_head * getblk(int dev,int block)
{
struct buffer_head * tmp, * bh;
repeat:
// 找到直接返回
if (bh = get_hash_table(dev,block))
return bh
tmp = free_list;
do {
// 已经被使用则找下一个节点
if (tmp->b_count)
continue;
/*
尽量找到一个数据是干净并且没有被锁的buffer,如果没有,则找干净但被锁的,
还没有就找不干净又被锁的
1 找到第一个buffer的时候,!bh成立,bh等于第一个可用的buffer,如果干净又没有被锁直接返回,
继续尝试查找更好的buffer
2 后面再找到buffer的时候,!bh就不会成立了,从而执行BADNESS(tmp)<BADNESS(bh),根据定义,
我们知道BADNESS的结果和数据是否干净、被锁相关,其中干净的权重更大,即如果两个buffer,一个脏,一个被锁,
则被锁是更好的选择,所以BADNESS(tmp)<BADNESS(bh)的意思是,找到一个比当前节点更好的,如果没有,则继续找
如果有则执行bh=tmp,即记录当前最好的节点,然后再判断该节点是不是干净又没有被锁的,是则返回,否则继续找
更好的节点。
*/
if (!bh || BADNESS(tmp)<BADNESS(bh)) {
bh = tmp; // 记录当前最好的节点
// 当前最好的节点是否满足要求,是则返回,否则继续找更好的
if (!BADNESS(tmp))
break;
}
/* and repeat until we find something good */
} while ((tmp = tmp->b_next_free) != free_list);
// 没有buffer可用,则阻塞等待
if (!bh) {
sleep_on(&buffer_wait);
goto repeat;
}
// 到这里说明有buffer可用,但是情况有,1被锁的 2 数据不干净的 3 不干净且被锁 4 干净又没有被锁
// 处理lock的情况
wait_on_buffer(bh);
// 阻塞的时候被其他进程使用了,则继续找
if (bh->b_count)
goto repeat;
// 处理数据脏的情况
while (bh->b_dirt) {
// 回写数据到硬盘
sync_dev(bh->b_dev);
wait_on_buffer(bh);
if (bh->b_count)
goto repeat;
}
/* NOTE!! While we slept waiting for this block, somebody else might */
/* already have added "this" block to the cache. check it */
if (find_buffer(dev,block))
goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
bh->b_count=1;
bh->b_dirt=0;
bh->b_uptodate=0;
// 移除空闲链表
remove_from_queues(bh);
bh->b_dev=dev;
bh->b_blocknr=block;
// 插入空
insert_into_queues(bh);
return bh;
}
// 有buffer可用, 唤醒等待buffer的队列
void brelse(struct buffer_head * buf)
{
if (!buf)
return;
wait_on_buffer(buf);
if (!(buf->b_count--))
panic("Trying to free free buffer");
wake_up(&buffer_wait);
}
/*
* bread() reads a specified block and returns the buffer that contains
* it. It returns NULL if the block was unreadable.
*/
struct buffer_head * bread(int dev,int block)
{
struct buffer_head * bh;
// 先从buffer链表中获取一个buffer
if (!(bh=getblk(dev,block)))
panic("bread: getblk returned NULL\n");
// 之前已经读取过并且有效,则直接返回
if (bh->b_uptodate)
return bh;
// 返回读取硬盘的数据
ll_rw_block(READ,bh);
//ll_rw_block会锁住bh,所以会先阻塞在这然后等待唤醒
wait_on_buffer(bh);
// 底层读取数据成功后会更新该字段为1,否则就是读取出错了
if (bh->b_uptodate)
return bh;
brelse(bh);
return NULL;
}
// movsl每次传送四个字节,所以cx等于BLOCK_SIZE除以4
#define COPYBLK(from,to) \
__asm__("cld\n\t" \
"rep\n\t" \
"movsl\n\t" \
::"c" (BLOCK_SIZE/4),"S" (from),"D" (to) \
:"cx","di","si")
/*
* bread_page reads four buffers into memory at the desired address. It's
* a function of its own, as there is some speed to be got by reading them
* all at the same time, not waiting for one to be read, and then another
* etc.
*/
// 读取四个块到address
void bread_page(unsigned long address,int dev,int b[4])
{
struct buffer_head * bh[4];
int i;
for (i=0 ; i<4 ; i++)
if (b[i]) {
if (bh[i] = getblk(dev,b[i]))
if (!bh[i]->b_uptodate)
ll_rw_block(READ,bh[i]);
} else
bh[i] = NULL;
for (i=0 ; i<4 ; i++,address += BLOCK_SIZE)
if (bh[i]) {
wait_on_buffer(bh[i]);
if (bh[i]->b_uptodate)
COPYBLK((unsigned long) bh[i]->b_data,address);
brelse(bh[i]);
}
}
/*
* Ok, breada can be used as bread, but additionally to mark other
* blocks for reading as well. End the argument list with a negative
* number.
*/
// 预读多个块,最后一个参数以负数结尾,只返回第一块的buffer指针,预读得存在buffer哈希链表里,等待以后用
struct buffer_head * breada(int dev,int first, ...)
{
va_list args;
struct buffer_head * bh, *tmp;
va_start(args,first);
if (!(bh=getblk(dev,first)))
panic("bread: getblk returned NULL\n");
if (!bh->b_uptodate)
ll_rw_block(READ,bh);
while ((first=va_arg(args,int))>=0) {
tmp=getblk(dev,first);
if (tmp) {
if (!tmp->b_uptodate)
// bh应该是tmp,因为需要每次给底层传一个新的buffer结构,如果一直用bh,预读的数据会覆盖前面的数据
ll_rw_block(READA,bh);
tmp->b_count--;
}
}
va_end(args);
// 等待底层唤醒
wait_on_buffer(bh);
if (bh->b_uptodate)
return bh;
brelse(bh);
return (NULL);
}