編寫一個(gè)UNIX文件系統(tǒng)

近日有人求助，要寫一個(gè)UNIX文件系統(tǒng)作為暑假作業(yè)。這種事情基本是學(xué)操作系統(tǒng)的必須要做的或者是做過(guò)的，畢竟文件系統(tǒng)是操作系統(tǒng)課程的一個(gè)重要組成部分。要實(shí)現(xiàn)這個(gè)UNIX文件系統(tǒng)，很多人就扎進(jìn)了UNIX V6的的系統(tǒng)源碼，以及《萊昂氏UNIX源代碼分析》和《返璞歸真:UNIX技術(shù)內(nèi)幕》這兩本書(shū)，很多人出來(lái)了，很多人在里面迷失了...最終忘了自己只是要實(shí)現(xiàn)一個(gè)UNIX文件系統(tǒng)而已。
       為何會(huì)迷失，因?yàn)榇a不是自己寫的，而且年代久遠(yuǎn)，編程理念不同了，作者為何那樣寫不一定就能理解，實(shí)際上對(duì)于任何別人寫的代碼，總是會(huì)有一些不易理解的地方，當(dāng)然，如果作者水平超級(jí)高，那么代碼也就相對(duì)容易理解。因此，寫代碼永遠(yuǎn)比讀代碼要容易！既然是要寫一個(gè)文件系統(tǒng)，為何要用現(xiàn)成的UNIX V6代碼呢？如果理解了UNIX文件的布局和結(jié)構(gòu)，自己從零開(kāi)始不參考任何現(xiàn)有的代碼做一個(gè)也不是什么難事，最根本的是UNIX文件系統(tǒng)本身，至于說(shuō)代碼，僅僅是一個(gè)實(shí)現(xiàn)與用戶操作的一個(gè)接口而已。如果代碼是自己一點(diǎn)一點(diǎn)寫的，那么你肯定能徹底明白每一行的每一個(gè)語(yǔ)句的精確含義，至于為何這么寫，你當(dāng)然及其明了！
       本文留下我倉(cāng)促間幾個(gè)小時(shí)寫的一個(gè)類UNIX文件系統(tǒng)的代碼，不是讓別人看的，是為了自己留檔，因?yàn)楸疚囊呀?jīng)說(shuō)了，看別人的代嗎只能學(xué)習(xí)經(jīng)驗(yàn)，不能理解本質(zhì)，更何況，你看的還得是超級(jí)一流的代碼，而我寫的，則是超級(jí)垃圾的代碼。我只想說(shuō)，理解問(wèn)題的本質(zhì)要比代碼重要得多，代碼，碼，并不是很多人想象中的那般重要！本文的實(shí)現(xiàn)基于Linux系統(tǒng)，即在Linux系統(tǒng)上編寫一個(gè)用戶態(tài)程序，實(shí)現(xiàn)UNIX文件的IO接口以及操作。
       我一向堅(jiān)持的原則，那就是任何東西的根本性的，本質(zhì)上的原理以及背后的思想都是及其簡(jiǎn)單的，所謂的復(fù)雜性都是優(yōu)化與策略化的擴(kuò)展帶來(lái)的，正如TCP一樣，UNIX的文件系統(tǒng)也不例外！我們必須知道，什么是最根本的，什么是次要的。對(duì)于UNIX文件系統(tǒng)，最根本的就是其布局以及其系統(tǒng)調(diào)用接口，一個(gè)處在最低層，一個(gè)在最上層開(kāi)放給用戶，如下所示：
系統(tǒng)調(diào)用接口：open，write，read，close...
文件系統(tǒng)布局：引導(dǎo)快，超級(jí)塊，inode區(qū)表，數(shù)據(jù)塊區(qū)
所有的在二者中間的部分都是次要的，也就是說(shuō)那些東西不要也行，比如高速緩沖，高速緩存，VFS層，塊層...因此在我的實(shí)現(xiàn)代碼中，并沒(méi)有這些東西，我所做到的，僅僅是UNIX文件系統(tǒng)所要求必須做到的最小集，那就是：
面對(duì)一個(gè)按照UNIX文件系統(tǒng)標(biāo)準(zhǔn)布局的“塊設(shè)備”，可以使用open，read，write等接口進(jìn)行IO操作。
在實(shí)現(xiàn)中，我用一個(gè)標(biāo)準(zhǔn)的Linux大文件來(lái)模擬磁盤塊，這樣塊的操作基本都映射到了Linux標(biāo)準(zhǔn)的write，read等系統(tǒng)調(diào)用了。
首先定義必要的結(jié)構(gòu)體：

//超級(jí)塊結(jié)構(gòu)
struct filesys {
        unsigned int s_size;        //總大小                                           
        unsigned int s_itsize;        //inode表大小                                         
        unsigned int s_freeinodesize;    //空閑i節(jié)點(diǎn)的數(shù)量                           
        unsigned int s_nextfreeinode;    //下一個(gè)空閑i節(jié)點(diǎn)
        unsigned int s_freeinode[NUM];     //空閑i節(jié)點(diǎn)數(shù)組
        unsigned int s_freeblocksize;    //空閑塊的數(shù)量          
        unsigned int s_nextfreeblock;    //下一個(gè)空閑塊
        unsigned int s_freeblock[NUM];    //空閑塊數(shù)組
        unsigned int s_pad[];        //填充到512字節(jié)   
};
//磁盤inode結(jié)構(gòu)
struct finode {
        int fi_mode;            //類型：文件/目錄
        int fi_uid_unused;        //uid，由于和進(jìn)程無(wú)關(guān)聯(lián)，僅僅是模擬一個(gè)FS，未使用，下同
        int fi_gid_unused;
        int fi_nlink;            //鏈接數(shù)，當(dāng)鏈接數(shù)為0，意味著被刪除
        long int fi_size;        //文件大小
        long int fi_addr[BNUM];        //文件塊一級(jí)指針，并未實(shí)現(xiàn)多級(jí)指針
        time_t  fi_atime_unused;    //未實(shí)現(xiàn)
        time_t  fi_mtime_unused;
};
//內(nèi)存inode結(jié)構(gòu)
struct inode {
        struct finode   i_finode;
        struct inode    *i_parent;    //所屬的目錄i節(jié)點(diǎn)
        int     i_ino;            //i節(jié)點(diǎn)號(hào)
        int     i_users;        //引用計(jì)數(shù)
};
//目錄項(xiàng)結(jié)構(gòu)(非Linux內(nèi)核的目錄項(xiàng))
struct direct
{
        char d_name[MAXLEN];        //文件或者目錄的名字
        unsigned short d_ino;        //文件或者目錄的i節(jié)點(diǎn)號(hào)
};
//目錄結(jié)構(gòu)
struct dir
{
        struct direct direct[DIRNUM];    //包含的目錄項(xiàng)數(shù)組
        unsigned short size;        //包含的目錄項(xiàng)大小     
};
//抽象的文件結(jié)構(gòu)
struct file {
        struct inode *f_inode;        //文件的i節(jié)點(diǎn)
        int f_curpos;            //文件的當(dāng)前讀寫指針
};

之所以叫做類UNIX文件系統(tǒng)，是因?yàn)槲也](méi)有去精確確認(rèn)當(dāng)時(shí)的UNIX文件系統(tǒng)的超級(jí)塊以及inode表的結(jié)構(gòu)，只是大致的模仿其布局，比如超級(jí)塊中字段，以及字段的順序可能和標(biāo)準(zhǔn)的UNIX文件系統(tǒng)并不完全一致。但是不管怎么說(shuō)，當(dāng)時(shí)的UNIX文件系統(tǒng)基本就是這個(gè)一個(gè)樣子。另外，可以看到file結(jié)構(gòu)體內(nèi)容及其少，因?yàn)楸举|(zhì)上，我只是想表示“一個(gè)inode節(jié)點(diǎn)相對(duì)于一個(gè)讀寫者來(lái)說(shuō)，就是一個(gè)file”，僅此而已。接下來(lái)就是具體的實(shí)現(xiàn)了，我的方式是自下而上的，這樣做的好處在于便于今后的擴(kuò)展。那么首先要完成的就是i節(jié)點(diǎn)的分配和釋放了，我的實(shí)現(xiàn)中，是將文件i節(jié)點(diǎn)映射到了內(nèi)存i節(jié)點(diǎn)，這樣或許違背了我的初衷，我不是說(shuō)過(guò)不要那么多“額外”的東西來(lái)擾亂視聽(tīng)的嗎？是的，然而比起那些所謂的額外的優(yōu)化，我更不喜歡頻繁的調(diào)用read和write。反正，只要自己能控制住局面即可。
       在實(shí)現(xiàn)中，還有一個(gè)大事就是內(nèi)存的分配與釋放，這些也不是本質(zhì)的，記住，要實(shí)現(xiàn)的僅僅是一個(gè)UNIX文件系統(tǒng)，其它的能繞開(kāi)則繞開(kāi)！顯然malloc，free等也是我們要繞開(kāi)的，于是我基本都使用預(yù)分配空間的東西-全局?jǐn)?shù)組。以下是全局變量：

//內(nèi)存i節(jié)點(diǎn)數(shù)組，NUM為該文件系統(tǒng)容納的文件數(shù)
struct inode g_usedinode[NUM];
//ROOT的內(nèi)存i節(jié)點(diǎn)
struct inode *g_root;
//已經(jīng)打開(kāi)文件的數(shù)組
struct file* g_opened[OPENNUM];
//超級(jí)塊
struct filesys *g_super;
//模擬二級(jí)文件系統(tǒng)的Linux大文件的文件描述符
int g_fake_disk = -1;

在給出實(shí)現(xiàn)代碼之前，要說(shuō)明的是，在刪除文件的時(shí)候，我并沒(méi)有實(shí)現(xiàn)文件塊區(qū)以及i節(jié)點(diǎn)的清除操作，眾所周知，那樣很耗時(shí)，和很多實(shí)現(xiàn)一樣，我只是記錄了一些信息，表示這個(gè)文件塊或者inode字段是可以隨時(shí)覆蓋的。

//同步i節(jié)點(diǎn)，將其寫入“磁盤”
void syncinode(struct inode *inode)
{
        int ino = -1, ipos = -1;
        ino = inode->i_ino;
    //ipos為inode節(jié)點(diǎn)表在文件系統(tǒng)塊中的偏移
        ipos = IBPOS + ino*sizeof(struct finode);
    //從模擬塊的指定偏移位置讀取inode信息
        lseek(g_fake_disk, ipos, SEEK_SET);
        write(g_fake_disk, (void *)&inode->i_finode, sizeof(struct finode));
}
//同步超級(jí)塊信息
int syncsuper(struct filesys *super)
{
        int pos = -1, size = -1;
        struct dir dir = {0};
        pos = BOOTBSIZE;
        size = SUPERBSIZE;
        lseek(g_fake_disk, pos, SEEK_SET);
        write(g_fake_disk, (void *)super, size);
        syncinode(g_root);
        breadwrite(g_root->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 1);
        breadwrite(g_root->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 0);
}
//關(guān)鍵的將路徑名轉(zhuǎn)換為i節(jié)點(diǎn)的函數(shù)，暫不支持相對(duì)路徑
struct inode *namei(char *filepath, char flag, int *match, char *ret_name)
{
        int in = 0;
        int repeat = 0;
        char *name = NULL;
        char *path = calloc(1, MAXLEN*10);
        char *back = path;
        struct inode *root = iget(0);
        struct inode *parent = root;
        struct dir dir = {0};
        strncpy(path, filepath, MAXLEN*10);
        if (path[0] != '/')
                return NULL;
        breadwrite(root->i_finode.fi_addr[0], &dir, sizeof(struct dir), 0, 1);
        while((name=strtok(path, "/")) != NULL) {
                int i = 0;
                repeat = 0;
                *match = 0;
                path = NULL;
                if (ret_name) {
                        strcpy(ret_name, name);
                }
                for (; i<dir.size; i++) {
                        if (!strncmp(name, dir.direct[i].d_name, strlen(name))) {
                                parent = root;
                                iput(root);
                                root = iget(dir.direct[i].d_ino);
                                root->i_parent = parent;
                                *match = 1;
                                if (root->i_finode.fi_mode == MODE_DIR) {
                                        memset(&dir, 0, sizeof(struct dir));
                                        breadwrite(root->i_finode.fi_addr[0], &dir, sizeof(struct dir), 0, 1);
                                } else {
                                        free(back);
                                        return root;
                                }
                                repeat = 1;
                        }
                }
                if (repeat == 0) {
                        break;
                }
        }
        if (*match != 1) {
                *match = 0;
        }
        if (*match == 0) {
                if (ret_name) {
                        strcpy(ret_name, name);
                }
        }
        free(back);
        return root;
}
//通過(guò)i節(jié)點(diǎn)號(hào)獲取內(nèi)存i節(jié)點(diǎn)的函數(shù)
struct inode *iget(int ino)
{
        int ibpos = 0;
        int ipos = 0;
        int ret = 0;
    //傾向于直接從內(nèi)存i節(jié)點(diǎn)獲取
        if (g_usedinode[ino].i_users) {
                g_usedinode[ino].i_users ++;
                return &g_usedinode[ino];
        }
        if (g_fake_disk < 0) {
                return NULL;
        }
    //實(shí)在不行則從模擬磁盤塊讀入
        ipos = IBPOS + ino*sizeof(struct finode);
        lseek(g_fake_disk, ipos, SEEK_SET);
        ret = read(g_fake_disk, &g_usedinode[ino], sizeof(struct finode));
        if (ret == -1) {
                return NULL;
        }
        if (g_super->s_freeinode[ino] == 0) {
                return NULL;
        }
    //如果是一個(gè)已經(jīng)被刪除的文件或者從未被分配過(guò)的i節(jié)點(diǎn)，則初始化其link值以及size值
        if (g_usedinode[ino].i_finode.fi_nlink == 0) {
                g_usedinode[ino].i_finode.fi_nlink ++;
                g_usedinode[ino].i_finode.fi_size = 0;
                syncinode(&g_usedinode[ino]);
        }
        g_usedinode[ino].i_users ++;
        g_usedinode[ino].i_ino = ino;
        return &g_usedinode[ino];
}
//釋放一個(gè)占有的內(nèi)存i節(jié)點(diǎn)
void iput(struct inode *ip)
{
        if (ip->i_users > 0)
                ip->i_users --;
}
//分配一個(gè)未使用的i節(jié)點(diǎn)。注意，我并沒(méi)有使用超級(jí)塊的s_freeinodesize字段，
//因?yàn)檫€會(huì)有一個(gè)更好更快的分配算法
struct inode* ialloc()
{
        int ino = -1, nowpos = -1;
        ino = g_super->s_nextfreeinode;
        if (ino == -1) {
                return NULL;
        }
        nowpos = ino + 1;
        g_super->s_nextfreeinode = -1;
    //尋找下一個(gè)空閑i節(jié)點(diǎn)，正如上述，這個(gè)算法并不好
        for (; nowpos < NUM; nowpos++) {
                if (g_super->s_freeinode[nowpos] == 0) {
                        g_super->s_nextfreeinode = nowpos;
                        break;
                }
        }
        g_super->s_freeinode[ino] = 1;
        return iget(ino);
}
//試圖刪除一個(gè)文件i節(jié)點(diǎn)
int itrunc(struct inode *ip)
{
        iput(ip);
        if (ip->i_users == 0 && g_super) {
                syncinode(ip);
                g_super->s_freeinode[ip->i_ino] = 0;
                g_super->s_nextfreeinode = ip->i_ino;
                return 0;
        }
        return ERR_BUSY;
}
//分配一個(gè)未使用的磁盤塊
int balloc()
{
        int bno = -1, nowpos = -1;
        bno = g_super->s_nextfreeblock;
        if (bno == -1) {
                return bno;
        }
        nowpos = bno + 1;
        g_super->s_nextfreeblock = -1;
        for (; nowpos < NUM; nowpos++) {
                if (g_super->s_freeblock[nowpos] == 0) {
                        g_super->s_nextfreeblock = nowpos;
                        break;
                }
        }
        g_super->s_freeblock[bno] = 1;
        return bno;
}
//讀寫操作
int breadwrite(int bno, char *buf, int size, int offset, int type)
{
        int pos = BOOTBSIZE+SUPERBSIZE+g_super->s_itsize + bno*BSIZE;
        int rs = -1;
        if (offset + size > BSIZE) {
                return ERR_EXCEED;
        }
        lseek(g_fake_disk, pos + offset, SEEK_SET);
        rs = type ? read(g_fake_disk, buf, size):write(g_fake_disk, buf, size);
        return rs;
}
//IO讀接口
int mfread(int fd, char *buf, int length)
{
        struct file *fs = g_opened[fd];
        struct inode *inode = fs->f_inode;
        int baddr = fs->f_curpos;
        int bondary = baddr%BSIZE;
        int max_block = (baddr+length)/BSIZE;
        int size = 0;
        int i = inode->i_finode.fi_addr[baddr/BSIZE+1];
        for (; i < max_block+1; i ++,bondary = size%BSIZE) {
                size += breadwrite(inode->i_finode.fi_addr[i], buf+size, (length-size)%BSIZE, bondary, 1);
        }
        return size;
}
//IO寫接口
int mfwrite(int fd, char *buf, int length)
{
        struct file *fs = g_opened[fd];
        struct inode *inode = fs->f_inode;
        int baddr = fs->f_curpos;
        int bondary = baddr%BSIZE;
        int max_block = (baddr+length)/BSIZE;
        int curr_blocks = inode->i_finode.fi_size/BSIZE;
        int size = 0;
        int sync = 0;
        int i = inode->i_finode.fi_addr[baddr/BSIZE+1];
    //如果第一次寫，先分配一個(gè)塊
        if (inode->i_finode.fi_size == 0) {
        int nbno = balloc();
                if (nbno == -1) {
                        return -1;
                }
                inode->i_finode.fi_addr[0] = nbno;
                sync = 1;
        }
    //如果必須擴(kuò)展，則再分配塊，可以和上面的合并優(yōu)化
        if (max_block > curr_blocks) {
                int j = curr_blocks + 1;
                for (; j < max_block; j++) {
            int nbno = balloc();
                    if (nbno == -1) {
                            return -1;
                    }
                        inode->i_finode.fi_addr[j] = nbno;
                }
                sync = 1;
        }
        for (; i < max_block+1; i ++,bondary = size%BSIZE) {
                size += breadwrite(inode->i_finode.fi_addr[i], buf+size, (length-size)%BSIZE, bondary, 0);
        }
        if (size) {
                inode->i_finode.fi_size += size;
                sync = 1;
        }
        if (sync) {
                syncinode(inode);
        }
        return size;
}
//IO的seek接口
int mflseek(int fd, int pos)
{
        struct file *fs = g_opened[fd];
        fs->f_curpos = pos;
        return pos;
}
//IO打開(kāi)接口
int mfopen(char *path, int mode)
{
        struct inode *inode = NULL;
        struct file *file = NULL;
        int match = 0;
        inode = namei(path, 0, &match, NULL);
        if (match == 0) {
                return ERR_NOEXIST;
        }
        file = (struct file*)calloc(1, sizeof(struct file));
        file->f_inode = inode;
        file->f_curpos = 0;
        g_opened[g_fd] = file;
        g_fd++;
        return g_fd-1;
}
//IO關(guān)閉接口
void mfclose(int fd)
{
        struct inode *inode = NULL;
        struct file *file = NULL;
        file = g_opened[fd];
        inode = file->f_inode;
        iput(inode);
        free(file);
}
//IO創(chuàng)建接口
int mfcreat(char *path, int mode)
{
        int match = 0;
        struct dir dir;
        struct inode *new = NULL;
        char name[MAXLEN] = {0};;
        struct inode *inode = namei(path, 0, &match, name);
        if (match == 1) {
                return ERR_EXIST;
        }
        breadwrite(inode->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 1);
        strcpy(dir.direct[dir.size].d_name, name);
        new = ialloc();
        if (new == NULL) {
                return -1;
        }
        dir.direct[dir.size].d_ino = new->i_ino;
        new->i_finode.fi_mode = mode;
        if (mode == MODE_DIR) {
        //不允許延遲分配目錄項(xiàng)
                int nbno = balloc();
                if (nbno == -1) {
                        return -1;
                }
                new->i_finode.fi_addr[0] = nbno;
        }
        new->i_parent = inode;
        syncinode(new);
        dir.size ++;
        breadwrite(inode->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 0);
        syncinode(inode);
        iput(inode);
        syncinode(new);
        iput(new);
        return ERR_OK;
}
//IO刪除接口
int mfdelete(char *path)
{
        int match = 0;
        struct dir dir;
        struct inode *del = NULL;
        struct inode *parent = NULL;
        char name[MAXLEN];
        int i = 0;
        struct inode *inode = namei(path, 0, &match, name);
        if (match == 0 || inode->i_ino == 0) {
                return ERR_NOEXIST;
        }
        match = -1;
        parent = inode->i_parent;
        breadwrite(parent->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 1);
        for (; i < dir.size; i++) {
                if (!strncmp(name, dir.direct[i].d_name, strlen(name))) {
                        del = iget(dir.direct[i].d_ino);
                        iput(del);
                        if (itrunc(del) == 0) {
                                memset(dir.direct[i].d_name, 0, strlen(dir.direct[i].d_name));
                                match = i;
                                break;
                        } else {
                                return ERR_BUSY;
                        }
                }
        }
        for (i = match; i < dir.size - 1 && match != -1; i++) {
                strcpy(dir.direct[i].d_name, dir.direct[i+1].d_name);
        }
        dir.size--;
        breadwrite(parent->i_finode.fi_addr[0], (char *)&dir, sizeof(struct dir), 0, 0);
        return ERR_OK;
}
//序列初始化接口，從模擬塊設(shè)備初始化內(nèi)存結(jié)構(gòu)
int initialize(char *fake_disk_path)
{
        g_fake_disk = open(fake_disk_path, O_RDWR);
        if (g_fake_disk == -1) {
                return ERR_NOEXIST;
        }
        g_super = (struct filesys*)calloc(1, sizeof(struct filesys));
        lseek(g_fake_disk, BOOTBSIZE, SEEK_SET);
        read(g_fake_disk, g_super, sizeof(struct filesys));
        g_super->s_size = 1024*1024;
        g_super->s_itsize = INODEBSIZE;
        g_super->s_freeinodesize = NUM;
        g_super->s_freeblocksize = (g_super->s_size - (BOOTBSIZE+SUPERBSIZE+INODEBSIZE))/BSIZE;
        g_root =  iget(0);
    //第一次的話要分配ROOT
        if (g_root == NULL) {
                g_root = ialloc();
                g_root->i_finode.fi_addr[0] = balloc();
        }
        return ERR_OK;
}

下面是一個(gè)測(cè)試程序：

int main()
{
        int fd = -1,ws = -1;
        char buf[16] = {0};
        initialize("bigdisk");
        mfcreat("/aa", MODE_FILE);
        fd = mfopen("/aa", 0);
        ws = mfwrite(fd, "abcde", 5);
        mfread(fd, buf, 5);
        mfcreat("/bb", MODE_DIR);
        mfcreat("/bb/cc", MODE_FILE);
        fd = mfopen("/bb/cc", 0);
        ws = mfwrite(fd, "ABCDEFG", 6);
        mfread(fd, buf, 5);
        mflseek(0, 4);
        ws = mfwrite(0, "ABCDEFG", 6);
        mflseek(0, 0);
        mfread(0, buf, 10);
        mfclose(0);
        mfdelete("/aa");
        fd = mfopen("/aa", 0);
        mfcreat("/aa", MODE_FILE);
        fd = mfopen("/aa", 0);
        syncsuper(g_super);
}

這個(gè)文件系統(tǒng)實(shí)現(xiàn)得超級(jí)簡(jiǎn)單，除去了很多額外的非本質(zhì)的東西，并且也繞開(kāi)了煩人的內(nèi)存管理問(wèn)題！于是，我的這個(gè)實(shí)現(xiàn)也就顯示了UNIX文件系統(tǒng)的本質(zhì)。那么再看一下，還有什么東西雖然是額外的，但是卻是必不可少或者起碼說(shuō)是很有意思的？答案很顯然，那就是空閑塊或者空閑inode的組織以及分配算法，然而這個(gè)算法可以單獨(dú)抽象出來(lái)。