标签：minode int 编程文件系统 Unix ino Linux mip 节点

chapter11

EXT2文件系统

Linux一直使用EXT2（Card等1995）作为默认文件系统。EXT3 (EXT3,2014)是EXT2的扩展。EXT3中增加的主要内容是一个日志文件，它将文件系统的变更记录在日志中。日志可在文件系统崩溃时更快地从错误中恢复。没有错误的EXT3文件系统与EXT2文件系统相同。EXT3的最新扩展是EXT4（Cao等2007）。EXT4的主要变化是磁盘块的分配。在EXT4中，块编号为48位。EXT4不是分配不连续的磁盘块，而是分配连续的磁盘块区，称为区段。除了这些细微的更改之外，文件系统结构和文件操作保持不变。下面的学习将以EXT2作为文件系统。

EXT2文件系统数据结构

通过命令：

mke2fs [-b blksize -N ninodes] device nblocks

创建虚拟磁盘，若blksize未指定，则默认块大小为1KB，若ninodes未指定，mke2fs将根据nblocks计算一个默认的ninodes数。例如：

dd if=/dev/zero of=vdisk bs=1024 count=1440
mke2fs vdisk 1440

可在一个名为vdisk的虚拟磁盘文件上创建一个EXT2文件系统，有1440个大小为1KB的块。

虚拟磁盘布局

下面是简单的EXT2文件系统布局：

| 0  |  1  |  2 |  3-7   | 8  | 9  | 10 | . . . 32|33          1439|
--------------------------------------------------------------------
|boot|super| GD |reserved|bmap|imap|inodes blocks |   data blocks  |

对于上述系统布局中的块的详细介绍，见第七章中对EXT2文件系统的知识点总结。

邮差算法

在计算机系统中，经常出现下面这个问题。一个城市有M个街区，编号从0到M-1。每个街区有N座房子，编号从0到N-1。每座房子有一个唯一的街区地址，用（街区，房子）表示，其中0≤街区<M，0≤房子<N。来自外太空的外星人可能不熟悉地球上的街区寻址方案，倾向于采用线性方法将这些房子地址编为0，1，…，N-1，N，N+1等。已知某个街区地址BA=（街区，房子），怎么把它转换为线性地址LA，反过来，已知线性地址，怎么把它转换为街区地址?如果都从0开始计数，转换就会非常简单。

Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);

只有都从0开始计数时，转换才有效。如果有些条目不是从0开始计数的，则不能直接在转换公式中使用。我们把这种转换方法称为邮差算法。下面是邮差算法的两种应用。

C语言中的Test-Set-Clear位

标准C语言程序中，最小的可寻址单元是一个字符或字节。在一系列位组成的位图中，通常需要对位进行操作。考虑字符buf[1024]，它有1024个字节，用buf[i]表示，其中i = 0,1,...,1023。它还有8192个位，编号为0,1,2,...8191。已知一个位号BIT，例如1234，那么哪个字节i包含这个位，以及哪个位j在该字节中呢？

i = BIT/8;  j = BIT%8;  //8 = number of bits in a byte.

可以在C语言中结合使用邮差算法和位屏蔽来进行下面的位操作。

.TST a bit for 1 or 0: if (buf[i] &   (1 << j))
.SET a bit to 1      :     buf[i] |=  (1 << j);
.CLR a bit to 0      :     buf[i] &= ~(1 << j);

一些C语言编译器允许在结构体中指定位，如:

struct bits{
    unsigned int bit0       :  1;   //bit0 field is a single bit
    unsigned int bit123     :  3;   //bit123 field is a range of 3 bits
    unsigned int otherbits  : 27;   //other bits field has 27 bits
    unsigned int bit31      :  1;   //bit31 is the highest bit
}var;

该结构体将var.定义位一个32位无符号整数，具有单独的位或位范围。那么，var.bit0=0；将1赋值给第0位，则有var.bit123=5；将101赋值给第1位到第3位等。但是，生成的代码仍然依赖于邮差算法和位屏蔽来访问各个位。可以使用邮差算法直接操作位图中的位，无须定义复杂的C语言结构体。

将索引节点号转换为磁盘上的索引节点

在EXT2文件系统中，每个文件都有一个唯一的索引节点结构。在文件系统磁盘上，索引节点从inode_table块开始。每个磁盘块包含

INODES_PER_BLOCK = BLOCK_SIZE/sizeof(INODE)

个索引节点。每个索引节点都有一个唯一的索引节点号，ino=1,2,...,从1开始线性计数，已知一个ino，如1234，那么哪个磁盘块包含该索引节点，以及哪个索引节点在该块中呢？我们需要知道磁盘块号，因为需要通过块来读/写一个真正的磁盘。

block = (ino - 1) / INODES_PER_BLOCK + inode_table;
inode = (ino - 1) % INODES_PER_BLOCK;

同样，将EXT2文件系统中的双重和三重间接逻辑块号转换为物理块号也依赖于邮差算法。
将线性磁盘块号转换为CHS = (柱面、磁头、扇区)格式：软盘和旧硬盘使用CHS寻址，但文件系统始终使用线性块寻址。在调用BIOS INT13时，可使用该算法将磁盘块号转换为CHS。

遍历EXT2文件系统树

在EXT2文件系统中，查找文件相当于查找其索引节点。

遍历算法

（1）读取超级块，检查幻数验证它为EXT2 FS。

（2）读取块组描述符块（1+s_first_data_block），以访问组0描述符。从块组描述符的bg_inode_table条目中找到索引节点的起始块编号，并将其称为InodesBeginBlock。

（3）读取InodeBeginBlock，获取/的索引节点，即INODE #2。

（4）将路径名标记为组件字符串，假设组件数量为n。比如路径名=/a/b/c，则组件字符串是“a”“b”“c”，其中n=3。用name[0]，name[1]，...，name[n-1]来表示组件。

（5）从（3）中的根索引节点开始，在其数据块中搜索name[0]。假设某个目录中的条目数量很少，因此一个目录索引节点只有12个直接数据块，做出了这个假设就能在12个（非零）直接块中搜索name[0]。目录索引节点的每个数据块都包含以下形式的dir_entry结构体：

[ino rec_len name_len NAME][ino rec_len name_len NAME] ......

其中NAME是一系列nlen字符，不含终止NULL。对于每个数据块，将该块读入内存并使用dir_entry *dp指向加载的数据块。然后使用name_len将NAME提取为字符串，并与name[0]进行比较。如果它们不匹配，则通过一下代码转到下一个dir_entry：

dp = (dir_entry *)((char *)dp + dp->rec_len);

继续搜索。如果存在name[0]，则可以找到它的dir_entry，从而找到它的索引节点号。

（6）使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino从1开始计数。使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。

blk     = (ino - 1) /   INODES_PER_BLOCK + InodesBeginBlock;
offset  = (ino - 1) % INODES_PER_BLOCK;

然后在索引节点中读取/a，从中确定它是否是一个目录（DIR）。如果/a不是目录，则不能有/a/b，因此搜索失败。如果它是目录，并且有更多需要搜索的组件，那么继续搜索下一个组件name[1]。问题是：在索引节点中搜索/a的name[1]，与第（5）步完全相同。

（7）由于（5）~（6）步将会重复n次，所以最好编写一个搜索函数：

u32 search(INODE *inodePtr, char *name)
{
    // search for name in the data blocks of current DIR inode
    //if found, return its ino; else return 0
}

然后只需要调用search()n次，如下。

Assume:n,name[0],...,name[n-1] are globals
INODE *ip points at INODE of /
for(i=0;i<n;i++){
    ino = search(ip, name[i])
    if(!ino){ //can't find name[i], exit;}
    use ino to read in INODE and let ip point to INODE
}

如果搜索循环成功结束，ip必须指向路径名的索引节点。遍历有多个组的大型EXT2/3文件系统也是类似操作。

EXT2文件系统的实现

文件系统的结构

上图中（1）至（5）标签说明如下：

（1）是当前运行进程的PROC结构体。在实际系统中，每个文件操作都是由当前执行的进程决定的。每个进程都有一个cwd，指向进程当前工作目录（CWD）的内存索引节点。它还有一个文件描述符数组fd[]，指向打开的文件实例。

（2）是文件系统的根指针。它指向内存中的根索引节点。当系统启动时，选择其中一个设备作为根设备，它必须是有效的EXT2文件系统。根设备的根索引节点（inode #2）作为文件系统的根(/)加载到内存中。该操作称为“挂载根文件系统”。

（3）是一个openTable条目。当某个进程打开文件时，进程fd数组的某个条目会指向openTable，openTable指向打开文件的内存索引节点。

（4）是内存索引节点。当需要某个文件时，会把它的索引节点加载到minode槽中以供使用。因为索引节点是唯一的，所以在任何时候每个索引节点在内存中都只能有一个副本。在minode中，（dev,ino）会确定索引节点的来源，以便将修改后的索引节点写回磁盘。refCount字段会记录使用minode的进程数。

dirty字段表示索引节点是否已被修改。挂载标志表示索引节点是否已被挂载，如果已被挂载，mntabPtr将指向挂载文件系统的挂载表条目。lock字段用于确保内存索引节点一次只能由一个进程访问，例如在修改索引节点时，或者在读/写操作过程中。

（5）是已挂载的文件系统表。对于每个挂载的文件系统，挂载表中的条目用于记录挂载的文件系统信息，例如挂载的文件系统设备号。在挂载点的内存索引节点中，挂载标志打开，mntabPtr指向挂载表条目。在挂载表条目中，mntPointPtr指向挂载点的内存索引节点。图中这些双链接指针允许我们在遍历文件系统树时跨越挂载点。此外，挂载表条目还可能包含挂载文件系统的其他信息，例如超级块、块组描述符、位图和索引节点启动块的值，以便快速访问。如果任何缓存项有修改，当卸载设备时，必须将它们写回设备。

文件系统的级别

文件系统的实现分三个级别。FS目录包含实现EXT2文件系统的文件。结构如下。

-------------------Common files of FS-----------------------------
    type.h      :EXT2 data structure types
    global.c    :global variables of FS
    util.c      :common utility functions:getino(),iget(),iput(),search(),etc.
    allocate_deallocate.c:inodes/blocks management functions
------------------------------------------------------------------

第1级别实现了基本文件系统树。它包含以下文件，实现了指定函数。

----------------------Level-1 of FS-------------------------------
mkdir_creat.c       :make directory,create regular file
ls_cd_pwd.c         :list directory,change directory,get CWD path
rmdir.c             :remove directory
link_unlink.c       :hard link and unlink files
symlink_readlink.c  :symbolic link files
stat.c              :return file information
misc1.c             :access,chmod,chown,utime,etc.
------------------------------------------------------------------

使用第1级别的FS函数的用户命令程序有：

mkdir、creat、mknod、rmdir、link、unlink、symlink、rm、ls、cd和pwd等。

第2级别实现了文件内容读/写函数。

----------------------Level-2 of FS-------------------------------
open_close_lseek.c  :open file for READ|WRITE|APPEND,close file and lseek
read.c              :read from file descriptor of an opened regular file
write.c             :write to file descriptor of an opened regular file
opendir_readdir.c   :open and read directory
------------------------------------------------------------------

第3级别实现了文件系统的挂载、卸载和文件保护。

----------------------Level-3 of FS-------------------------------
mount_umount.c      :mount/umount file systems
file protection     :access permission checking
file-locking        :lock/unlock files
------------------------------------------------------------------

基本文件系统

type.h文件

这类文件包含EXT2文件系统的数据结构类型，比如超级块、组描述符、索引节点和目录条目结构。此外，它还包含打开文件表、挂载表、PROC结构体和文件系统常数。

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <ext2fs/ext2_fs.h>
#include <libgen.h>
#include <string.h>
#include <sys/stat.h>

// define shorter TYPES for convenience
typedef struct ext2_group_desc GD;
typedef struct ext2_super_block SUPER;
typedef struct ext2_inode INODE;
typedef struct ext2__dir_entry_2 DIR;
#define BLKSIZE 1024

// Block number of EXT2 FS on FD
#define SUPERBLOCK 1
#define GDBLOCK 2
#define ROOT_INODE 2

// Default dir and regular file modes
#define DIR_MODE 0x41ED
#define FILE_MODE 0x81AE
#define SUPER_MAGIC 0xEF53
#define SUPER_USER 0
// Proc status
#define FREE 0
#define BUSY 1
// file system table sizes
#define NMINODE 100
#define NMTABLE 10
#define NPROC 2
#define NFD 10
#define NOFT 40

// PROC structure
typedef struct proc{
    struct Proc *next;
    int pid;
    int uid;
    int gid;
    int ppid;
    int status;
    struct minode *cwd;
    OFT *fd[NFD];
}PROC;

// In-memory inodes structure
typedef struct minode{
    INODE INODE;    // disk inode
    int dev, ino;
    int refCount;   // use count
    int dirty;      // modified flag
    int mounted;    // mounted flag
    struct mount *mntPtr;   //mount table pointer
    // int lock;            // ignored for simple Fs
}MINODE;

// Open file Table          // opened file instance
typedef struct oft{
    int mode;       // mode of opened file
    int refCount;   // number of PROCs sharing this instance
    MINODE *minodePtr;      // pointer to minode of file
    int offset;     // byte offset for R| w
}OFT;

// Mount Table structure
typedef struct mtable{
    int dev;        // device number; 0 for FREE
    int ninodes;    // from superblock
    int nblocks;
    int free_blocks;// from superblock and GD
    int free_inodes;
    int bmap;       // from group descriptor
    int imap;
    int iblock;     // inodes start block
    MINODE *mntDirPtr;  // mount point DIR pointer
    chardevName [64];   // device name
    charmntName [64];   // mount point DIR name
}MTABLE;

global.c文件

这类文件包含文件系统的全局变量。全局变量的例子有：

MINODE minode[NMINODE];     //in memory INODEs
MTABLE mtable[NMTABLE];     //mount tables
OFT    oft[NOFT];           //Opened file instance
PROC   proc[NPROC]          //PROC structures
PROC   *running;            //current executing PROC

当文件系统启动时，将初始化所有全局数据结构，并让运行点位于PROC[0]，即超级用户的进程P0(uid = 0)。在实际系统中，每个操作都是由当前运行进程决定的。下图是执行全局数据结构初始化函数。

文件系统操作过程中，全局数据结构被视为系统资源，可灵活使用和释放。每一组资源都由一对分配和释放函数管理。例如，mialloc()分配一个空闲的minode供使用，而midalloc()则释放一个使用过的minode。其他资源管理函数与此类似。

MINODE *mialloc()       //allocate a FREE minode for use
{
    int i;
    for (i=0;i<NMINODE;i++){
        MINODE *mp = &minode[i];
        if (mp->refCount == 0){
            mp->refCount = 1;
            return mp;
        }
    }
    printf("FS panic:out of minodes\n");
    return 0;
}
int midalloc(MINODE *mip)   //release a used minode
{
    mip->refCount = 0;
}

实用程序函数

util.c file:该文件包含文件系统常用的实用程序函数。最重要的实用程序函数是读/写磁盘块函数iget()、iput()和getino()。

（1）get_block/put_block函数:我们假设某个块设备，例如真实磁盘或虚拟磁盘，只能以块大小为单位读写。对于真实磁盘，这是因为受到硬件的限制。对于虚拟磁盘，我们假设也是以块大小为单位读/写，这样就可以在需要时将代码移植到真实磁盘上。在虚拟磁盘上，我们先以读|写模式打开它，并使用文件描述符作为设备号。以下函数将虚拟磁盘块读/写到内存的缓冲区中。

int get_block(int dev,int blk,char *buf)
{
    lseek(dev,blk*BLKSIZE,SEEK_SET);
    int n = read(dev,buf,BLKSIZE);
    if(n<0) printf("get_block [%d %d] error\n",dev,blk);
}
int put_block(int dev,int blk,char *buf)
{
    lseek(dev,blk*BLKSIZE,SEEK_SET);
    int n = write(dev,buf,BLKSIZE);
    if(n != BLKSIZE)
        printf("put_block [%d %d] error\n",dev,blk);
}

（2）iget(dev,ino)函数:该函数返回一个指针，指向包含INODE(dev,ino)的内存minode。返回的minode是唯一的，即内存中只存在一个INODE副本。在实际文件系统中，返回的minode被锁定为独占使用，直到它被释放或解锁。为简单起见，假设minode锁定不是必要的。

MINODE *iget(int dev,int ino)
{
    MINODE *mip;
    MTABLE *mp;
    INODE *ip;
    int i,block,offset;
    char buf[BLKSIZE];

    //serach in-memory minodes first
    for(i=0;i<NMINODES;i++){
        MINODE *mip = &MINODE[i];
        if(mip->refCount && (mip->dev==dev) && (mip->ino==ino)){
        mip->refCount++;
        return mip;
        }
    }

    //needed INODE=(dev,ino) not in memory
    mip = mialloc();                    //allocate a FREEminode
    mip->dev = dev; mip->ino = ino;     //assign to (dev,ino)
    block = (ino-1)/8 + iblock;         //disk block containing this inode
    offset= (ino-1)%8;                  //which inode in this block
    get_block(dev,block,buf);
    ip = (INODE *) buf + offset;
    mip->INODE = *ip;                   //copy inode to minode.INODE
    //initialize minode
    mip->refCount = 1;
    mip->mounted = 0; 
    mip->dirty = 0;
    mip->mountptr = 0;
    return mip;
}

（3）iput(INODE *mip)函数:该函数会释放一个mip指向的用完的minode。每个minode都有一个refCount，表示使用minode. iput()的用户数量为refCount减1。如果refCount为非零，则表示minode仍有其他用户，那么调用者只是返回。如果调用者是minode的最后一个用户（refCount=0），那么如果INODE被修改（dirty），它将被写回磁盘。

int iput(MINODE *mip)
{
    INODE *ip;
    int i, block,offset;
    char buf[BLKSIZE];

    if(mip==0) return;
    mip->refcount--;                //dec refcount by 1
    if (mip->refcount > 0) return;  //still has user
    if (mip->dirty == 0)   return;  //no need to write back

    //write INODE back to disk
    block = (mip->ino - 1)/8 + iblock;
    offset = (mip->ino - 1)%8;

    //get block containing this inode
    get_block(mip->dev,block,buf);
    ip = (INODE *)buf + offset;     //ip points at INODE
    *ip = mip->INODE;               //copy INODE to inode in block
    put_block(mip->dev,block,buf);  //write back to disk
    midalloc(mip);                  //mip->refCount = 0;
}

（4）getino()函数：getino()函数可实现文件系统树遍历算法。它会返回指定路径名的INODE编号（ino）。首先，假设在1级文件系统的实现中，文件系统属于单个根设备，因此不存在挂载设备和挂载点交叉。因此，getino()函数本质上返回的是路径名的(dev,ino)。首先，该函数使用tokenize()函数将路径名分解为组件字符串。我们假设标记化字符串位于全局数据区中，每个字符串由一个name[i]指针指向，标记字符串的数量为nname。然后，它会调用search()函数来搜索连续目录中的标记字符串。下面是tokenize()和search()函数。

char *name[64];        //token string pointers
char gline[256];       //holds token strings,each pointed by a name[i]
int nname;             //number of token strings

int tokenize(char *pathname)
{
    char *s;
    strcpy(gline,pathname);
    nname = 0;
    s = strtok(gline,"/");
    while(s){
        name[nname++] = s;
        s = strtok(0,"/");
    }
}

int search(MINODE *mip,char *name)
{
    int i;
    char *cp,temp[256],sbuf[BLKSIZE];
    DIR *dp;
    for(i=0; i<12; i++){ //search DIR direct blocks only
        if(mip->INODE.i_block[i] == 0)
            return 0;
    get_block (mip->dev，mip->INODE.i_bloek [i],sbuf) ;dp = (DIR *)sbuf ;
    cp = sbuf;
    while (cp < sbuf + BLKSIZE){
    strncpy (temp, dp->name,dp->name_len) ;temp [dp->name_len] = 0 ;
    printf( "38d88d88u 8sin" ,
    dp->inode, dp->rec_len,dp->name_len, temp) ;
    if (strcmp (name, temp ) ==o){
    printf ( "found 8s : inumber = %d\n" . name，dp->inode) ;return dp->inode;
    )
    cp += dp->rec_len;dp = (DIR * ) Cp;)
    )
    return 0;
}

int getino(char *pathname)
{
    MINODE *mip;
    int i, ino;
    if(strcmp(pathname,"/")==0){
        return 2;           //return root ino=2
    }
    if(pathname[0] == '/')
        mip = root;         //if absolute pathname:start from root
    else
        mip = running->cwd; //if relative pathname:start from CWD
    mip->refCount++;        //in order to iput(mip) later

    tokenize(pathname);     //assume:name[ ], nname are globals

    for(i=0;i<nname;i++){   //search for each component string
        if(!S_ISDIR(mip->INODE.i_mode)){    //check DIR type
            printf("%s is not a directory\n",name[i]);
            iput(mip);
            return 0;
        }
        ino = search(mip,name[i]);
        if(!ino){
            printf("no such component name %s\n",name[i]);
            iput(mip);
            return 0;
        }
        iput(mip);              //release current minode
        mip = iget(dev,ino);    //switch to new minode
    }
    iput(mip);
    return ino;
}

（5）getino()/iget()/iput()的使用：在文件系统中，几乎每个操作都以一个路径名开头，例如mkdir路径名、cat路径名等。只要指定了路径名，就必须将其索引节点加载到内存中备用。索引节点的一般使用方式是：

. ino = getino(pathname);
. mip = iget(dev, ino);
.    use mip->INODE,which may modify the INODE;
. iput(mip);

这种使用方式只有少数例外情况。比如:

更改目录(chdir)：iget新目录的minode，但是iput旧目录的minode。
打开（open)：iget文件的minode，当文件关闭时释放。
挂载(mount)：iget挂载点的minode，稍后通过卸载释放。

一般来说，iget和iput要成对出现，就像一对配套的括号。我们可在实现代码过程中依赖这种使用方式，来确保每个INODE都能够正确加载和释放。

minode锁定:在实际文件系统中，每个minode都有一个锁字段，确保一次只有一个进程可以访问minode，例如在修改INODE时。Unix内核使用忙碌标志和休眠/唤醒来同步访问同一minode的进程。在其他系统中，每个minode可能有一个互斥量或一个信号量锁。进程只有在持有minode锁的情况下才能访问minode。minode锁定的原因如下所示。

假设一个进程Pi需要内存中没有的索引节点(dev, ino)。Pi必须将该索引节点加载到minode条目中。minode必须标记为(dev, ino)，以防止其他进程再次加载同一个索引节点。从磁盘加载索引节点时，Pi可能会等待I/O完成，切换到另一个进程Pj。如果Pj恰好需要相同的索引节点，它会发现所需的minode已经存在。如果没有锁，Pj可能会在加载minode之前使用它。有了锁，Pj就必须等待minode被Pi加载、使用和释放之后再使用。此外，当进程读/写某个打开的文件时，它必须锁定文件的minode，以确保每个读/写操作都是原子操作。为简单起见，假设一次只运行一个进程，因此不需要锁。但是，在实际文件系统中，minode锁定是必要的。

mount-root

mount_root.c文件：该文件包含mount_root()函数，在系统初始化期间调用该函数来挂载根文件系统。它读取根设备的超级块，以验证该设备是否为有效的EXT2文件系统。然后，它将根设备的根INODE(ino = 2)加载到minode中，并将根指针设置为根minode。它还将所有进程的当前工作目录设置为根minode。分配一个挂载表条目来记录挂载的根文件系统。根设备的一些关键信息，如inode和块的数量、位图的起始块和inode表，也记录在挂载表中，以便快速访问。（示例代码见后面代码实践部分）

如何执行ls：ls[pathname]列出了目录或文件的信息。其工作原理如下。

（1）ls_dir(dirname)：使用opendir()和readdir()获取目录中的文件名。对于每个文件名，调用ls_file(filename)。
（2）ls_file(filename)：stat文件名，以在STAT结构体中获取文件信息。然后，列出STAT信息。

由于stat系统调用实质上返回的是minode的相同信息，所以可以通过直接使用minode来修改原始的ls算法。下面是修改后的ls算法。

/******************************* Algorithm of ls *******************************/
(1). From the minode of a directory,step through the dir_entries in the datablocks of the minode.INODE. Each dir_entry contains the inode number, ino, and name of a file. For each dir_entry, use iget() to get its minode, as in
        MINODE *mip = iget(dev, ino);
Then, call ls_file(mip, name).
(2). ls_file(MINODE *mip,char *name): use mip->INODE and name to list the file information.

如何执行chdir[pathname]：chdir算法如下。

/********************* Algorithm of chdir *********************/
(1). int ino = getino(pathname);       //return error if ino=0
(2). MINODE *mip = iget(dev, ino);
(3). Verify mip->INODE is a DIR        //return error if not DIR
(4). iput(running->cwd);               //release old cwd
(5). running->cwd = mip;               //change cwd to mip

如何pwd：下面展示了pwd算法，在目录minode上使用递归。

/********************* Algorithm of pwd *********************/
    rpwd(MINODE *wd){
        (1). if(wd==root) return;
        (2). from wd->INODE.i_block[0], get my_ino and parent_ino
        (3). pip = iget(dev, parent_ino);
        (4). from pip->INODE.i_block[ ]: get my_name string by my_ino as LOCAL
        (5). rpwd(pip);     //recursive call rpwd(pip) with parent minode
        (6). print "/%s", my_name;
    }

pwd(MINODE *wd){
    if(wd == root)  print "/"
    else            rpwd(wd);
}
//pwd start:
pwd(running->cwd);

文件系统函数

1级文件系统函数

mkdir算法

creat算法

rmdir算法

link算法

unlink算法

symlink算法

readlink算法

其他1级函数的操作方式均相同

2级文件系统函数

open算法

lseek算法：lseek算法很简单，只需要检查请求的位置值是否在[0,fileSize-1]范围内。

close算法

read算法

将逻辑块转换为物理块的算法

write算法

opendir-readdir

这两个操作独立于文件系统，readdir()的形式如下：

struct dirent *ep = readdir(DIR *dp);

每次调用时返回一个指向dirent结构体的指针。这可以在用户空间中作为I/O库函数实现。直接实现opendir()和readdir()如下。

int opendir(pathname)
{   return open(pathname, RD|O_DIR); }

其中O_DIR是将文件作为目录打开的一个位模式。在打开的文件表中，mode字段包含O_DIR位。

int readdir(int fd，struct udir *udizp)         //struct udir{DIR udir;);
{
    //same as read() except:
    use the current byte offset in OFT to read the next dir_entry;
    copy the dir_entry into *udirp;
    advance offset by dir_entry's rec_len for reading next dir_entry;
}

3级文件系统

挂载（mount）算法

卸载（umount）算法

交叉挂载点

虽然可以轻松实现挂载和卸载，但是会有一定的影响。对于挂载，必须修改getino(pathname)函数来支持交叉挂载点。假设某文件系统newfs已被挂载到目录/a/b/c/上。当遍历一个路径名时，两个方向的挂载点可能会出现交叉。

（1）向下遍历:当遍历路径名/a/b/c/x时，一旦到达/a/b/c的minode，就能看到minode已经被挂载（挂载标志=1)。我们不是在/a/b/c的索引节点中搜索x，而是必须要:

跟随minode的mntPtr指针来定位挂载表条目。
从挂载表的设备号中，将其根索引节点(ino=2)放入内存。
然后，继续在挂载设备的根索引节点下搜索x。

（2）向上遍历:假设在目录/a/b/c/x/上，然后向上遍历，例如cd ../../)，将会与挂载点/a/b/c交叉。当到达挂载文件系统的根索引节点时，就能看到它是一个根目录(ino=2)，但是它的设备号与实根的设备号不同，因此它现在还不是实根。可以使用它的设备号，找到它的挂载表条目，它指向/a/b/c的minode。然后，切换到/a/b/c的minode，继续向上遍历。因此，交叉挂载点就像一只猴子或松鼠从一棵树跳到另一棵树上，然后又跳了回来。

由于交叉挂载点会更改设备号，因此一个全局设备号是不够的。必须要将getino()函数修改为

int getino(char *pathname， int *dev)

并将getino()调用修改为

int dev;                        //local in function that calls getino()
if(pathname[0]=='/')
    dev = root->dev;            //absolute pathname
else
    dev = running->cwd->dev;    //relative pathname

int ino = getino(pathname, &dev);   //pass &dev as an extra parameter

在修改后的getino()函数中，当路径名与挂载点交叉时，要修改设备号。因此，修改后的getino()函数实际上返回的是路径名的(dev, ino)。其中dev表示最终设备号。

文件保护

在Unix/Linux中，可通过文件索引节点中的权限位实现文件保护。每个文件的索引节点都有一个i_mode字段，其中下面的9位是权限。9个权限位为：

owner       group       other
------      ------      -------
r w x       r w x       r w x

前3位适用于文件所有人，中间3位适用于与所有人同一组的用户，最后3位适用于其他所有用户。对于目录，x位表示某进程是否可进入目录。每个进程都有一个uid和gid。当某进程试图访问某个文件时，文件系统会根据文件的权限位检查进程uid和gid，以确定它是否能以目标操作模式访问文件。如果该进程没有适当的权限，访问会被拒绝。为简单起见，可以忽略进程gid，只使用进程uid来检查访问权限。

实际uid和有效uid

在Unix/Linux中，每个进程都有一个实际uid和一个有效uid。文件系统通过进程的有效uid检查进程的访问权限。在正常情况下，进程的有效uid和实际uid是相同的。当某进程执行setuid程序时，该程序打开文件i_mode字段中的setuid位，该进程的有效uid就变成了该程序的uid。在执行setuid程序时，进程实际上成了程序文件的所有者。例如，当进程执行邮件程序（超级用户所有的setuid程序)，它会写入另一个用户的邮件文件中。当进程执行完setuid程序时，它会返回到实际uid。为简单起见，可以忽略有效uid。

文件锁定

文件锁定机制允许进程对一个文件或文件的某些部分设置文件锁，以防止在更新文件时出现竞态条件。文件锁可共享（允许同步读取），也可独占（执行独占写入）。文件锁既可以是强制性的，也可以是建议性的。例如，Linux既支持共享文件锁，也支持独占文件锁，但文件锁定只是建议性的。在Linux中，文件锁可通过fcntl()系统调用设置，也可通过flock()系统调用操作。为简单起见，假设一种非常简单的文件锁定。当一个进程试图打开一个文件时，将会检查目标操作模式的兼容性。唯一兼容模式是读模式。如果已经为更新模式打开了一个文件，即写|读写|追加，则该文件无法再次打开。但是，这并不会阻止相关进程（例如父进程和子进程）修改父进程打开的同一文件，而且在Unix/Linux中同样如此。在这种情况下，文件系统只能保证每个写操作是原子操作，但不能保证进程的写入顺序，写入顺序取决于进程调度。