[MIT 6.S081] Lab 9: file system

Lab 9: file system

• Lab Guidance: https://pdos.csail.mit.edu/6.828/2020/labs/fs.html
• Lab Code: https://github.com/peakcrosser7/xv6-labs-2020/tree/fs

Large files (moderate)

The main points of

• Implement secondary indirect block index (doubly-indirect block) Of inode structure : ip->addrs[] Before 11 The first element is a direct block (direct block), The first 12 Element is a first level indirect block index (singly-indirect block), The first 13 Element is a secondary indirect block index (doubly-indirect block).
• modify bmap() Function to fit double-indirect block

step

1. modify kernel/fs.h Macro definition of the direct block number in NDIRECT by 11.
   According to the requirements of the experiment , inode In the original 12 The direct block number is modified to 了 11 individual .

#define NDIRECT 11 // lab9-1

2. modify inode Array of block numbers of related structures . Specific include kernel/fs.h Disks in inode Structure struct dinode Of addrs Field ; and kernel/file.h Memory in inode Structure struct inode Of addrs Field . Set the array size of both to NDIRECT+2, Because of reality inode The total number of block numbers has not changed , but NDIRECT Less 1.

// On-disk inode structure
struct dinode {
    
  // ...
  uint addrs[NDIRECT+2];   // Data block addresses // lab9-1
};

// in-memory copy of an inode
struct inode {
    
  // ...
  uint addrs[NDIRECT+2];    // lab9-1
};

3. stay kernel/fs.h Add to the definition NDOUBLYINDIRECT, Indicates the total number of secondary indirect block numbers , analogy NINDIRECT. Because it's secondary , Therefore, the block number that can be represented should be the primary indirect block number NINDIRECT The square of .

#define NDOUBLYINDIRECT (NINDIRECT * NINDIRECT) // lab9-1

4. modify kernel/fs.c Medium bmap() function .
   This function returns inode The block number in the disk corresponding to the relative block number of .
   because inode Middle front of structure NDIRECT The block number is consistent with that before modification , Therefore, you only need to add a pair of NDIRECT namely 13 Processing code of secondary indirect index of blocks . Treatment method and treatment NDIRECT The method of block number, that is, the first level indirect block number, is similar , Just need to index twice .

static uint
bmap(struct inode *ip, uint bn)
{
    
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;

  if(bn < NINDIRECT){
    
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
    
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  // doubly-indirect block - lab9-1
  bn -= NINDIRECT;
  if(bn < NDOUBLYINDIRECT) {
    
    // get the address of doubly-indirect block
    if((addr = ip->addrs[NDIRECT + 1]) == 0) {
    
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    }
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    // get the address of singly-indirect block
    if((addr = a[bn / NINDIRECT]) == 0) {
    
      a[bn / NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    bn %= NINDIRECT;
    // get the address of direct block
    if((addr = a[bn]) == 0) {
    
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}

5. modify kernel/fs.c Medium itrunc() function .
   This function is used to release inode A block of data .
   Due to the addition of a secondary indirect block structure , Therefore, you also need to add code for the release of blocks in this part . The way of release is the same as the structure of the indirect block number of the same level , Only two loops are needed to traverse the secondary indirect block and the primary indirect block respectively .

void
itrunc(struct inode *ip)
{
    
  int i, j, k;  // lab9-1
  struct buf *bp, *bp2;     // lab9-1
  uint *a, *a2; // lab9-1

  for(i = 0; i < NDIRECT; i++){
    
    if(ip->addrs[i]){
    
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
    
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }
  // free the doubly-indirect block - lab9-1
  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]) {
    
        bp2 = bread(ip->dev, a[j]);
        a2 = (uint*)bp2->data;
        for(k = 0; k < NINDIRECT; ++k) {
    
          if(a2[k]) {
    
            bfree(ip->dev, a2[k]);
          }
        }
        brelse(bp2);
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT + 1]);
    ip->addrs[NDIRECT + 1] = 0;
  }

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

6. modify kernel/fs.h Macro definition of the maximum file size in MAXFILE. Due to the addition of a secondary indirect block structure , xv6 The upper limit of the supported file size naturally increases , Here you need to change it to the correct value .

#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLYINDIRECT) // lab9-1

Have a problem

• stay xv6 In the implementation of bigfile adopt , But enforcement usertests appear virtio_disk_intr status Of panic, As shown in the figure below :
  
  solve : The panic The author is not very clear about the specific reasons for the emergence of , But at the beginning, the author did not modify NDIRECT by 11, But to keep 12, But in bmap() and itrunc() Revision in China . But will NDIRECT It is amended as follows 11 after , There is no need to panic.

test

• stay xv6 In the implementation of bigfile:
  
• stay xv6 In the implementation of usertests:
  
• ./grade-lab-fs bigfile Individual tests :
  

Symbolic links (moderate)

The main points of

• Add symbolic links ( Soft link ) System call symlink
• modify open System calls handle symbolic links , And when the target file of symbolic link is still a symbolic link file, you need to recursively find the target file .
• With O_NOFOLLOW Opening symbolic links does not track to linked files .
• Other system calls do not track symbolic links , Then deal with the symbolic link file itself .

step

1. Add something about symlink Definition declaration of system call . Include kernel/syscall.h, kernel/syscall.c, user/usys.pl and user/user.h.
   
   
   
   
   

2. Add a new file type T_SYMLINK To kernel/stat.h in .
   

3. Add new file flag bit O_NOFOLLOW To kernel/fcntl.h in .
   

4. stay kernel/sysfile.c To realize sys_symlink() function .
   This function is used to generate symbolic links . Symbolic link is equivalent to a special independent file , The stored data is the path of the target file .
   So in this function , First, through create() Create a symbolic link path corresponding to inode structure ( Use at the same time T_SYMLINK Distinguish from ordinary files ). And then through writei() Write the path of the linked target file inode ( Of block) Then you can . In the process , There is no need to judge whether the target path of the connection is valid .
   It should be noted that there are some lock release rules for file systems . function create() Will return the created inode, At this time, it will also hold its inode Lock of . And later writei() It can only be written when it is locked . After finishing the operation ( Success or not ), All need to be called iunlockput() To release inode The lock and itself , The function is iunlock() and iput() The combination of , The former is released inode Lock of ; The latter is to reduce one inode References to ( Corresponding Field ref, Record the memory pointing to this inode Number of pointers , there inode It's actually in memory inode, From memory inode cache icache Distributed , When ref by 0 It will be recycled to icache in ), It means that it is no longer necessary to hold this inode The pointer of continues to operate on it 了 .

// lab9-2
uint64 sys_symlink(void) {
    
  char target[MAXPATH], path[MAXPATH];
  struct inode *ip;
  int n;

  if ((n = argstr(0, target, MAXPATH)) < 0
    || argstr(1, path, MAXPATH) < 0) {
    
    return -1;
  }

  begin_op();
  // create the symlink's inode
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    
    end_op();
    return -1;
  }
  // write the target path to the inode
  if(writei(ip, 0, (uint64)target, 0, n) != n) {
    
    iunlockput(ip);
    end_op();
    return -1;
  }

  iunlockput(ip);
  end_op();
  return 0;
}

5. modify kernel/sysfile Of sys_open() function .
   This function uses , For symbolic links, generally, what you need to open is the linked target file , Therefore, additional processing of symbolic link files is required .
   Considering that the operation of tracking symbolic links is relatively independent , Here the author writes an independent function follow_symlink() The target file used to find symbolic links .
   When tracking symbolic links, you need to take into account that the target of symbolic links may still be symbolic links , At this time need Recursively track target links Until you get the real file . Two problems need to be solved : First, symbolic links may form rings , This will keep tracking recursively , therefore Ring forming detection is required ; On the other hand, we need Limit the depth of links , To reduce the burden of the system ( These two points are also the requirements of the experiment ).
   For the depth of the link , Here in kernel/fs.h It defines NSYMLINK Used to indicate the maximum symbolic link depth , Beyond this depth, the trace will not continue, but an error will be returned .

// the max depth of symlinks - lab9-2
#define NSYMLINK 10

And for the detection of looping , Here is also the simplest algorithm : Create a size of NSYMLINK Array of inums[] be used for Record the file tracked each time inode number, Every time the target file is tracked inode Post metropolis Put it inode number And inums Compare the records in the array , If there is repetition, it is proved to be a ring .
So on the whole follow_symlink() The process of function is actually relatively simple , At most NSYMLINK Track symbolic links recursively for times : Use readi() Function to read the path of the target file recorded in the symbolic link file , And then use namei() Get the corresponding file path inode, Then with what has been recorded inode number Compare and judge whether it forms a ring . Until the goal inode Type is not T_SYMLINK That is, symbolic link type .
And in the sys_open() in , You need to create a file object f=filealloc() Before , For symbolic links , In Africa NO_FOLLOW Under the circumstances You need to change the current file's inode Replace with follow_symlink() Get the target file inode And then carry out the following operations .
Finally, consider the rules of lock release in this process . For the case that symbolic links are not considered originally , stay sys_open() in , from create() or namei() Got the current file inode After that, he actually held the inode Lock of , It won't pass until the end of the function iunlock() Release ( Not used when the execution is successful iput() Release inode Of ref quote , The author believes that the follow-up is sys_close() Call this before execution inode It will always be active for the operation of the file , Therefore, references cannot be reduced ). And for symbolic links , Because the final open is the linked target file , Therefore, it will release the current inode The lock of gets the target in turn inode Lock of . When dealing with symbolic links, you need to ip->type Field to read , Naturally, it cannot be released at this time inode Lock of , So we're entering follow_symlink() Always keep inode The holding of the lock , When Use readi() After reading the target file path recorded in the symbolic link , At this point, the current symbolic link is no longer needed inode, Then use iunlockput() Release the lock and inode. When judging whether the type of the target file is not a symbolic link , Then lock it . In this way, the target file will also be held when the function returns correctly inode Lock of , The consistency before and after function call is achieved .

// recursively follow the symlinks - lab9-2
// Caller must hold ip->lock
// and when function returned, it holds ip->lock of returned ip
static struct inode* follow_symlink(struct inode* ip) {
    
  uint inums[NSYMLINK];
  int i, j;
  char target[MAXPATH];

  for(i = 0; i < NSYMLINK; ++i) {
    
    inums[i] = ip->inum;
    // read the target path from symlink file
    if(readi(ip, 0, (uint64)target, 0, MAXPATH) <= 0) {
    
      iunlockput(ip);
      printf("open_symlink: open symlink failed\n");
      return 0;
    }
    iunlockput(ip);
    
    // get the inode of target path 
    if((ip = namei(target)) == 0) {
    
      printf("open_symlink: path \"%s\" is not exist\n", target);
      return 0;
    }
    for(j = 0; j <= i; ++j) {
    
      if(ip->inum == inums[j]) {
    
        printf("open_symlink: links form a cycle\n");
        return 0;
      }
    }
    ilock(ip);
    if(ip->type != T_SYMLINK) {
    
      return ip;
    }
  }

  iunlockput(ip);
  printf("open_symlink: the depth of links reaches the limit\n");
  return 0;
}

uint64
sys_open(void)
{
    
  // ...

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

  // handle the symlink - lab9-2
  if(ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) {
    
    if((ip = follow_symlink(ip)) == 0) {
    
      //  There is no need to call iunlockput() Release the lock , Because in follow_symlinktest() When the return fails ip The lock of has been released in the function 
      end_op();
      return -1;
    }
  }

  if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
    
    if(f)
      fileclose(f);
    iunlockput(ip);
    end_op();
    return -1;
  }

  // ...
}

6. Last in Makefile Add a pair of test files symlinktest.c Compilation of .
   

Have a problem

• stay xv6 In the implementation of symlinktest There will be Failed to open 1 Error of , As shown in the figure below :
  
  solve : According to the output of the above figure, combine user/symlinktest.c Code for , You can see that the file cannot be opened due to looping 1, According to the code, we can know that there is no ring here .
  Finally, the author detected the looped code and found the problem , As shown in the following figure , The author It was not inode number But to perform inode The pointer to , And compare through the pointer . And one thing to note is , there struct inode It's actually in memory inode cache , When calling iput() stay ref The reference count is 0 In fact, it should inode Being recycled You can use iget() Storage disk inode Information ( Equivalent to having a memory inode The cache pool ).
  
  And if you use struct inode Compare with the pointer of , be It is possible that inode The cache is recycled and reused , This produces repetition . Therefore, it should be described above , Record inode number namely ip->inums, And use it to compare , This value is the disk pair inode The number of , Have uniqueness , This should be used inode Ring formation detection . The correct code is shown above .

test

• stay xv6 In the implementation of symlinktest test :
  
• stay xv6 In the implementation of usertests test :
  
• ./grade-lab-fs symlinktest Individual tests :