MIT6.S081-Lab9 FS [2021Fall]

Start date ：22.07.05

operating system ：Ubuntu20.0.4

Link：Lab file system

Lab Lock

Write it at the front

This section does not cover implementation details , You can read at ease

bigfile It mainly adopts the two-level linked list

symlink Need to be clear iput(),open(),create(),unlink() and namei() How functions interact , How do they make inode stay cache Release stored .

Step on the pit

• symlinktest Use in Storage path name It's a failure
  The author first adopted symlink Storage path name （ Character pointer ）, But in the test execution if(write(fd1, buf, sizeof(buf)) != 4) after , The path name will be lost directly , Can't quote , Result in failure . The specific reasons have not been analyzed .
• iput
iput The role of the ip->ref Minus one , If ip->ref == 1 Just take it from cache Release from
• fs.c Notes
  do symlinktest front , Be sure to read through fs.c Large comments （ Around the 105 line）
• writebig: panic freeing free block
  If it's done symlinktest, In execution usertests Before , You have to do it once bigfile.
  Failure to do so will result in an error , because wirtebif To write and MAXFILE A file of the same size , And only execution bigfile Then we have the revised MAXFILE
• make clean
  If you find that you can't pass the test anyway , I think the idea is also right , It may be that there are problems left in the previous version and you can try make clean

Reference material

• xv6- file system
• The Complete Guide to Creating Symbolic Links (aka Symlinks) on Windows

Experimental content

Warning ： This section covers implementation details

bigfile

The experimental requirements ： Realize the secondary mapping of disks , Change the disk space from 268 blocks Expand to 65803 blocks, About the original 256 times

Realize the idea ： The original 12 Direct mapping +1 The first level indirect mapping is changed to 11 Direct mapping +1 First level indirect mapping + A secondary mapping

Specifically, the linked list can be linked one more layer , Change the parameters again , You'd better understand the original version completely before writing bmap() function .

Note that before entering the secondary mapping , Remember to lose one NINDIRECT, Ensure that there are not many intermediate address numbers obtained 1.

access code

The first is to modify some definitions

/* fs.h */
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + (NINDIRECT*NINDIRECT))

/* file.h */
// in-memory copy of an inode
struct inode {
	...
  uint addrs[NDIRECT + 2]; // 11 direct blocks, 1 singly indirect block and 1 double indirect block
};

And then there's the implementation

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

  // 11 direct block[0 ~ 10] => [0 ~ 10] 
  if(bn < NDIRECT){
    // Load direct block, allocating if necessary.
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;
  
  // NDIRECT == 11
  // 1 singly direct block[11] => [0 ~ 255]
  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;
  }
  // go to double direct block[12]
  bn -= NINDIRECT;

  // 1 double direct block[12] => 256 * [0 ~ 255]
  if(bn < NINDIRECT * NINDIRECT){
    int mid_addr_num = bn / NINDIRECT; // get mid_addr_num and c-style: divide(/) to down 
    bn = bn % NINDIRECT; // get real bn

    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    
    // get the addr of mid_addr_num
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[mid_addr_num]) == 0){
      a[mid_addr_num] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    // get the addr of real bn
    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;
  }
  panic("bmap: out of range");
}

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j, k;
  struct buf *bp;
  uint *a, *botton_a;

  // 11 direct block[0 ~ 10] => [0 ~ 10] 
  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  // NDIRECT == 11
  // 1 singly direct block[11] => [0 ~ 255]
  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;
  }

  // 1 double direct block[12] => 256 * [0 ~ 255]
  if(ip->addrs[NDIRECT + 1]){
    // get a of mid_addr
    bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
    a = (uint*)bp->data;
    brelse(bp);
    
    for(j = 0; j < NINDIRECT; j++){
      // get botton_a of botton_addr 
      // exist block?
      if(a[j]){
        bp = bread(ip->dev, a[j]);
        botton_a = (uint*)bp->data;
        brelse(bp);
        // free content of botton_a
        for(k = 0; k < NINDIRECT; k++)
          if(botton_a[k])
            bfree(ip->dev, botton_a[k]);
      }
    }
    bfree(ip->dev, ip->addrs[NDIRECT + 1]);
    ip->addrs[NDIRECT + 1] = 0;
  }

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

symboil link

The experimental requirements ： Realize soft connection （symboil/soft link）
Soft connection is different from hard connection （hard link）, It can be connected under different disk blocks . such as , I think D Disk executes a program , But the location of the program file is C disc . Then through soft connection , Can be in D Disk execution C Program of disk , Hard connection doesn't work .

Realize the idea ： Realization syccall: sys_symlink, Put the target file inode The pointer is stored in the path file inode In structure , Then you can access the target file through the path file

In the process of realization , Note that the path file itself may or may not exist , So you need to check , Create according to the situation . This requires dealing with two situations , That is, if the path file itself does not exist , After creation, it is locked , Then naturally, there is no need to lock ; But if the path file itself exists , Then it is unlocked , Then we need to use if(!holdingsleep(&ip->lock)) Inspection .

meanwhile , Soft connect to a nonexistent target file is allowed , That is to say, the target file is the same as the path file , It may or may not exist , So you need to check , Create according to the situation . This will lead to a situation , Namely If you carry O_CREATE Parameter to open() When the target file , The target file may already be in symlink() Be created , If you re create it Recreate 了 , The solution is to check , If it is T_SYMLINK, There is no need to create a new , Just change the parameters ; If not , You need to release it , And then create .

stay open() Remember to unlock when searching in a loop in the function , Re lock , Guaranteed atomicity , After the search , You need to check whether the target file really exists , The existing situation is nlink Greater than 0.

Whether it is a target file or a path file , As long as it is T_SYMLINK type , When unlink() when , It needs to be implemented iput(), Subtract one from its quotation , Give it a chance to be released , otherwise T_SYMLINK Type of inode Will be left in cache, Can't release , More than one , It will lead to cache There is no free inode It can be stored .（ This is inferred from the error reporting and test procedures ）

Be careful , We don't need to deal with linked objects direcitory The situation of

access code

First of all syccall: sys_symlink Registration process , I won't write it in detail here , Just follow the prompts .

Then there is the realization sys_symlink

uint64
sys_symlink(void)
{ 
  char target[MAXPATH], path[MAXPATH];
  struct inode *ip, *ip_target;

  // get the parameter of target and path
  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;
  
  begin_op();

  // Symlinking to nonexistent file should succeed
  if((ip_target = namei(target)) == 0){
    if((ip_target = create(target, T_SYMLINK, 0, 0)) == 0){ // diff char* path
      end_op();
      return -1;
    }
  }

  // create ip if not exist
  if((ip = namei(path)) == 0){ // diff char* path
    if((ip = create(path, T_SYMLINK, 0, 0)) == 0){
      end_op();
      return -1;
    }   
  }

  // not have to handle symbolic links to directories for this lab.
  if(ip_target){
    if(ip_target->type == T_DIR){
      end_op();
      return -1;
    }
  }

  // inode(ip) with lock return from create(path) 
  // inode(ip) without lock return from namei(path)
  // so we need to check and maybe ilock it
  if(!holdingsleep(&ip->lock)){
    ilock(ip);
  }
  ip->sym_link = ip_target;
  iupdate(ip);
  iunlock(ip);
  end_op();
  return 0;
}

modify open()

// Modify the open system call to handle the case where the path refers to a symbolic link. 
// If the file does not exist, open must fail. 
// When a process specifies O_NOFOLLOW in the flags to open, 
// open should open the symlink (and not follow the symbolic link).
uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

  if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
    return -1;

  begin_op();

  if(omode & O_CREATE){
    ip = namei(path);
    if(ip){
      // if it is T_SYMLINK, we just change it type
      if(ip->type == T_SYMLINK){
        ip->type = T_FILE;
        ip->major = ip->minor = 0;
      }
      else{
        // if not T_SYMLINK we need free it, then create a inode
        // becasue it is a new path so we can sure 'ip->ref == 1'
        // 'ip->ref == 1'(namei()=>namex()=>idup()=>ip->ref++=>1)
        iput(ip);
        ip = create(path, T_FILE, 0, 0);
        if(ip == 0){
          end_op();
          return -1;
        }        
      }
    }
    else{
      ip = create(path, T_FILE, 0, 0);
      if(ip == 0){
        end_op();
        return -1;
      }
    }
  } 
  else{
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ilock(ip);
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  if(ip->type == T_SYMLINK){
    // if((omode & O_NOFOLLOW)){
    //     // do nothing
    // }

    // FOLLOW => follow symlink
    if(!(omode & O_NOFOLLOW)){
      // we set threshold = 10, so we only check 10 times
      int threshold = 10;
      for(int i = 0; i < threshold; i++){
        iunlockput(ip);
        ip = ip->sym_link;
        ilock(ip);
        if(ip->type != T_SYMLINK){
          break;
        }
      }

      // check: file really exists?
      if(ip->nlink == 0){
        iunlockput(ip);
        end_op();
        return -1;        
      }
    }
  }

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

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

  if(ip->type == T_DEVICE){
    f->type = FD_DEVICE;
    f->major = ip->major;
  } else {
    f->type = FD_INODE;
    f->off = 0;
  }
  f->ip = ip;
  f->readable = !(omode & O_WRONLY);
  f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
  
  if((omode & O_TRUNC) && ip->type == T_FILE){
    itrunc(ip);
  }

  iunlock(ip);
  end_op();

  return fd;
}

The last is the revision unlink()

uint64
sys_unlink(void)
{
  struct inode *ip, *dp;
  struct dirent de;
  char name[DIRSIZ], path[MAXPATH];
  uint off;

  if(argstr(0, path, MAXPATH) < 0)
    return -1;

  begin_op();
  if((dp = nameiparent(path, name)) == 0){
    end_op();
    return -1;
  }

  ilock(dp);

  // Cannot unlink "." or "..".
  if(namecmp(name, ".") == 0 || namecmp(name, "..") == 0)
    goto bad;

  if((ip = dirlookup(dp, name, &off)) == 0)
    goto bad;
  ilock(ip);

  if(ip->nlink < 1)
    panic("unlink: nlink < 1");
  if(ip->type == T_DIR && !isdirempty(ip)){
    iunlockput(ip);
    goto bad;
  }

  memset(&de, 0, sizeof(de));
  if(writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
    panic("unlink: writei");
  if(ip->type == T_DIR){
    dp->nlink--;
    iupdate(dp);
  }
  iunlockput(dp);

  ip->nlink--;
  iupdate(ip);
  iunlockput(ip);

  // we need to ip->ref-- or free symlink when we call unlink 
  if(ip->type == T_SYMLINK){
    iput(ip);
  }

  end_op();

  return 0;

bad:
  iunlockput(dp);
  end_op();
  return -1;
}

result

make[1]: Leaving directory '/home/duile/xv6-labs-2021'
== Test running bigfile ==
$ make qemu-gdb
running bigfile: OK (170.2s)
    (Old xv6.out.bigfile failure log removed)
== Test running symlinktest ==
$ make qemu-gdb
(0.9s)
== Test   symlinktest: symlinks ==
  symlinktest: symlinks: OK
== Test   symlinktest: concurrent symlinks ==
  symlinktest: concurrent symlinks: OK
== Test usertests ==
$ make qemu-gdb
usertests: OK (294.8s)
== Test time ==
time: OK
Score: 100/100

summary

• Completion date ：22.07.07
• Time consuming 15h, I didn't see any reference answers at all ,bigfile It was used 3 Hours ,2 I was looking at the materials for hours , Look at the code ,1 Hours in Write code , In fact, it may not take an hour ;symlink It was used 12 Hours ,3 Look at the materials when you are young , Check information , Look at the code ,9 Hours in Call code
• Write at the beginning symlink When and bigfile Difference and big ,bigfile I know exactly what I want to do , Very clear , and symlink There is no clue , I checked a lot of information and didn't fully understand it , Behind it is imitation link() Just write a general , Then keep adjusting, keep adjusting . Keep guessing what the title wants me to write .
  I draw experience from this , Only when you really understand the knowledge used in programming can you write smoothly .
• Write symlink At the quarter, I came up with two solutions. One is to store the path name pointer , One is the storage path file inode The pointer , Start with the former , failed , But I didn't find out the reason , Then use the latter , But when it comes to testing open("/testsymlink/4", O_CREATE | O_RDWR) Found duplicate files created , There are contradictions , Can't think of a good solution . therefore , Fold back to realize the name pointer , This time I found the reason , The name pointer is missing , But I can't find the principle , It's a black box problem for me , Unable to resolve . Last , Fold back to realize inode The pointer , Find a way to modify and clarify the problematic open(), Solved the problem of repeated creation .
  This process tells me , When programming encounters obvious problems , Some seem impossible to solve , You should rest first , Instead of giving up immediately , Adjust your state and think again . meanwhile , Facing the black box problem and the white box problem , Even if the former is more beautiful and concise , It's not as reliable as the latter .
• open() I don't think my writing is concise enough to solve the part of repeated creation , Maybe it can be optimized , But adding a function is too artificial .
• printf It's very useful , But it's used too much , Just thinking maybe it's more convenient to interrupt , I'm just not familiar with interruptions
• I've been listening to I Don't Want To Say Goodbye Teddy Thompson