专栏首页原创分享文件系统杂谈

文件系统杂谈

文件系统中重要的概念有大概有超级块、inode、file、文件描述符、文件缓存系统、目录。下面我们逐个说一下。

文件系统的概念:

1.超级块

超级块是负责管理整个文件系统,他记录了文件系统的元数据。从数据结构中我们可以看到他记录了文件系统的inode数量、文件系统在硬盘中占据的扇区数、inode位图、数据块位图、文件系统在硬盘中第一块的块号、该文件系统中文件大小的最大值。 #### 1.1 inode数量 文件系统中每个文件对应一个inode,文件的内容需要占据存储空间,而inode本身也需要存储空间,inode数量决定的了文件系统的可存储文件的个数。 #### 1.2 文件系统位置 一个硬盘分为很多个扇区,可以同时存在多个文件系统,所以每个文件系统需要记录他在硬盘中的首块号和块数。 #### 1.3 inode位图、数据块位图 inode位图是标记文件系统中,哪些inode节点已经被使用了,数据块位图则是标记哪些数据块被使用了。 一个文件系统在硬盘中的布局如下。

在这里插入图片描述

2.inode节点

文件系统中,每个文件对应一个inode节点,inode节点记录了文件的元数据。比如创建者、创建时间、文件大小、权限、数据块信息等。inode节点是文件系统中非常重要的概念,unix/linux系统万物皆文件的实现和inode有很大的关系。inode节点屏蔽了不同类型文件的细节,为上层提供抽象的接口。

3.file结构体

file结构体是实现多个进程操作文件的结构体。他指向一个inode节点。因为inode保存的是文件的元数据。他对每个进程来说都是一样的。但是一个文件,在每个进程的视角下,有些属性是不一样的,比如文件偏移,文件的打开标记(可读可写可执行)。这些是每个进程独立的信息。

4 文件描述符

文件描 述符本质是一个数字索引。他和文件系统其实没有太大关系,他主要是用于进程中。进程进行通过文件描述符可以找到对应的文件。

5 文件缓存系统

相对内存读写而言,读写硬盘的速度是非常慢的,如果每次读写都要和硬盘打交道,那无疑是很低效的。所以文件系统中加了一层缓存。缓存系统管理着文件数据的有效性。减少对硬盘的操作。

6 目录

我们知道操作系统中的文件其实是一棵树,而目录就是用来实现这棵树的重要数据结构。因为在文件树中,文件就是叶子节点。目录则是非叶子节点。目录本质也是文件。他和一般文件的区别是,一般文件存储的是用户的数据,目录存储的则是文件的信息。

文件系统的数据结构

文件系统的本质是利用一些策略对一块存储进行管理。所以我们首先需要了解文件系统的数据结构。

/*
 * 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结构体。

1 文件系统的结构

文件系统的结构大概分为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);
}

本文分享自微信公众号 - 编程杂技(theanarkh)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • linux系统调用之sys_close(基于linux0.11)

    进程PCB中有一个指针数组,文件描述符是数组索引,每个元素指向一个file结构体,file结构体有一个字段指向文件对应的inode。关闭一个文件主要的步骤是 1...

    theanarkh
  • linux系统调用之sync源码解析(基于linux0.11)

    我们知道write函数写入的数据不是实时同步硬盘的,系统提供了一个函数让我们的数据可以实时地同步到硬盘,那就是sync。但这个实时也是相对的,毕竟同步数据也需要...

    theanarkh
  • 当创建一个文件的时候,操作系统发生了什么

    操作文件是我们平时经常有的操作。但是我们可能并不是很了解他们原理,比如为什么删除一个很大的文件,会非常快?创建一个文件的时候,系统发生了什么?为什么删除的文件,...

    theanarkh
  • 关于dirty buffer

    SQL> select VIEW_DEFINITION from v$fixed_view_definition where VIEW_NAME = 'GV$B...

    数据和云01
  • 视频背景抠图:世界是您的绿屏

    是否希望在没有完整工作室的情况下制作专业质量的视频?还是在视频会议期间Zoom的虚拟背景功能效果更好?

    代码医生工作室
  • HDR关键技术:质量评价技术(续)

    在上一篇HDR质量评价帖中,我们列举了业内常见的HDR质量评估算法,然而不同算法有不同的应用领域。本文将结合重要的HDR技术,进一步描述HDR质量评价技术。本文...

    用户1324186
  • Reddit热点 | 想看被打码的羞羞图片怎么办?CNN帮你解决

    翻译 | 刘畅 编辑 | Donna,波波 超分辨重构是图像处理领域地一项非常有趣的任务。它可以通过算法将一张低分辨率的图片放大成一张高分辨率地图片。这个事情乍...

    AI科技大本营
  • vue插件开发练习--实用弹窗

    上回说了组件(vue组件开发练习--焦点图切换)的一个练习项目,这次换下口味,说下vue的插件练手的项目。相对于现在之前的焦点图切换的组件,这个可能就更简单了,...

    守候i
  • PHP中Smarty引擎的常用语法

    后天Date of the day after tomorrow (Day+2):

    Enjoy233
  • 思想的碰撞:非局部均值偶遇深度学习(第二部)

    code:https://github.com/SHI-Labs/Cross-Scale-Non-Local-Attention

    马上科普尚尚

扫码关注云+社区

领取腾讯云代金券