lab9

文件系统

文件系统API

  • 文件描述符必须与文件名无关（修改文件名后仍然可以通过文件描述符操作文件）

  • 记录offset（当前读写位置）

  • 友好的文件名

  • 在用户/进程间共享文件

  • 持久性

inode满足以下两种条件时可以删除文件

  • link count == 0
  • open fd count == 0

Bcache

  • 在内存中只有一个副本

  • 通过维护bcache锁维持bcache链表的一致性，维护buffer睡眠锁实现只有一个进程能修改该块。

  • 通过睡眠锁来节省因磁盘访问速度而浪费的CPU时间

  • 通过LRU策略将最近使用的块（引用归0）置于bcache链表前。因为最近用过的块可能会在未来的时间继续使用。

文件崩溃的安全性：系统崩溃或断电

解决方案：日志系统

  • 使系统调用是原子性的，例如是否发生了open
  • 快速修复
  • 高性能

日志系统行为（即事务）

  • 它们要么全部成功执行，要么全部失败。即原子的。

  • 将事务中的所有操作记录到日志文件中。

  • 在记录日志后，系统开始执行事务中的操作。
  • 若系统崩溃，重新执行日志内容。（REDO）（幂等性）

  • 清除日志，若完成操作，清除日志。

  • 幂等性：指的是一个操作执行多次和执行一次的效果相同，即多次执行的结果不会因为执行次数的增加而改变。

FILE SYSTEM ext3

write-ahead rule： 预先声明更新在将更新写入磁盘前

freeing rule：我们不能在写入磁盘前覆盖重用日志

  • log super block：保存第一个事务的偏移
  • …
  • describe block：块编号
  • log block：日志
  • commit block：提交块
  • ….
  • 异步ASYNC
    • 优势
      • I/O CONCURRENCY：允许计算和文件写入并行
      • HELP BATCHING：为批处理提供支持
    • 劣势
      • 不能保证操作已完成，可能导致数据丢失
    • unix提供fsync()强制写入避免异步写入导致的数据丢失
  • 批处理BATCHING
    • one “OPEN” action：降低磁盘寻道时间等访问磁盘的开销
    • WRITE ABSORBTION：在内存上将多个inode写入一个块显然比一次次在磁盘写入快
    • DISK SCHEDUING：允许对磁盘访问进行排序，加快磁盘（特别是机械硬盘）的访问速度
  • 并发CONCURRENCE
    • SYS CALLS IN PARALLEL：系统调用可以修改事务
    • MANY OLDER XACTIONS
      • ONE OPEN
      • COMMITING TO LOG
      • WRITING TO HEOME
      • FREED
  • Journaled Data 侧重于通过记录操作日志来保护数据不受系统故障的影响。
  • Ordered Data 侧重于数据的逻辑顺序，这有助于提高数据处理效率和保证数据的一致性。

Large files(moderate)

在fs.h修改文件

块组合为：11+512+512*512

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NINDIRECT2 (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT2)

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+2];   // Data block addresses
};

同时修改file.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+2];
};

取bn的索引和偏移，像页表那样，只为分配的inode分配块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;
  uint idx, offset;
 
  ....
    
  bn-= NINDIRECT;

    if(bn < NINDIRECT2){
        idx = bn / NINDIRECT;
        offset = bn % NINDIRECT;
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);    //分配一级索引块
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[idx]) == 0){     //分配二级索引块
      a[idx] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[offset]) == 0){    //分配块
      a[offset] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  panic("bmap: out of range");
}

释放掉所有子块后才释放上一级块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp, *bp1;
  uint *a, *a1;
....

  if(ip->addrs[NDIRECT+1]){
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j]){
          bp1 = bread(ip->dev, a[j]);
          a1 = (uint*)bp1->data;
          for(i = 0; i < NINDIRECT; i++)
          {

            if(a1[i])
              {
                bfree(ip->dev, a1[i]);  
              }
          }
          brelse(bp1);
        }
   
  }
   brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;

  }
  ip->size = 0;
  iupdate(ip);
}

系统调用添加过程这里就不赘述了

1
2
3
4
5
//添加标志
#define O_NOFOLLOW 0x800


#define T_SYMLINK 4   //符号链接

在sysfile文件添加sys_symlink()，创建文件并写入T_SYMLINK 标志和指向的文件路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int64
sys_symlink(void)
{
  char target[MAXPATH], path[MAXPATH];
  struct inode *dp;
  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;

  begin_op();
  if((dp = create(path, T_SYMLINK, 0, 0)) == 0)
    {
      end_op();
      return -1;
    }
  if(writei(dp, 0, (uint64)target, 0, MAXPATH) < MAXPATH)
    {
      iunlockput(dp);
      end_op();
      return -1;
    }
    iunlockput(dp);
    end_op();
    return 0;
}

当文件类型为符号链接且O_NOFOLLOW未被设置访问指向的路径，同时当循环深度大于10时，返回错误，避免环状引用无法退出open。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
uint64
sys_open(void)
{


  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }

  if(ip->type == T_SYMLINK && !(omode & O_NOFOLLOW))
  {
    for(int i = 0; i < 10; ++i) {
    if(readi(ip, 0, (uint64)path, 0, MAXPATH) != MAXPATH)
    {
      iunlockput(ip);
      end_op();
      return -1;
    }
    iunlockput(ip);
      ip = namei(path);
      if(ip == 0) {
        end_op();
        return -1;
      }
      ilock(ip);
      if(ip->type != T_SYMLINK)
        break;
    }
    if(ip->type == T_SYMLINK) {
      iunlockput(ip);
      end_op();
      return -1;
    }
  
    
  }

  
}