root/kernel/fs.c

DEFINITIONS

1. readsb
2. fsinit
3. bzero
4. balloc
5. bfree
6. iinit
7. ialloc
8. iupdate
9. iget
10. idup
11. ilock
12. iunlock
13. ifree
14. iput
15. iunlockput
16. ireclaim
17. bmap
18. itrunc
19. stati
20. readi
21. writei
22. namecmp
23. dirlookup
24. dirlink
25. skipelem
26. namex
27. namei
28. nameiparent

   1 // File system implementation.  Five layers:
   2 //   + Blocks: allocator for raw disk blocks.
   3 //   + Log: crash recovery for multi-step updates.
   4 //   + Files: inode allocator, reading, writing, metadata.
   5 //   + Directories: inode with special contents (list of other inodes!)
   6 //   + Names: paths like /usr/rtm/xv6/fs.c for convenient naming.
   7 //
   8 // This file contains the low-level file system manipulation
   9 // routines.  The (higher-level) system call implementations
  10 // are in sysfile.c.
  11 
  12 #include "types.h"
  13 #include "riscv.h"
  14 #include "defs.h"
  15 #include "param.h"
  16 #include "stat.h"
  17 #include "spinlock.h"
  18 #include "proc.h"
  19 #include "sleeplock.h"
  20 #include "fs.h"
  21 #include "buf.h"
  22 #include "file.h"
  23 
  24 #define min(a, b) ((a) < (b) ? (a) : (b))
  25 // there should be one superblock per disk device, but we run with
  26 // only one device
  27 struct superblock sb;
  28 
  29 // Read the super block.
  30 static void
  31 readsb(int dev, struct superblock *sb)
  32 {
  33   struct buf *bp;
  34 
  35   bp = bread(dev, 1);
  36   memmove(sb, bp->data, sizeof(*sb));
  37   brelse(bp);
  38 }
  39 
  40 // Init fs
  41 void
  42 fsinit(int dev)
  43 {
  44   readsb(dev, &sb);
  45   if (sb.magic != FSMAGIC)
  46     panic("invalid file system");
  47   initlog(dev, &sb);
  48   ireclaim(dev);
  49 }
  50 
  51 // Zero a block.
  52 static void
  53 bzero(int dev, int bno)
  54 {
  55   struct buf *bp;
  56 
  57   bp = bread(dev, bno);
  58   memset(bp->data, 0, BSIZE);
  59   log_write(bp);
  60   brelse(bp);
  61 }
  62 
  63 // Blocks.
  64 
  65 // Allocate a zeroed disk block.
  66 // returns 0 if out of disk space.
  67 static uint
  68 balloc(uint dev)
  69 {
  70   int b, bi, m;
  71   struct buf *bp;
  72 
  73   bp = 0;
  74   for (b = 0; b < sb.size; b += BPB) {
  75     bp = bread(dev, BBLOCK(b, sb));
  76     for (bi = 0; bi < BPB && b + bi < sb.size; bi++) {
  77       m = 1 << (bi % 8);
  78       if ((bp->data[bi / 8] & m) == 0) { // Is block free?
  79         bp->data[bi / 8] |= m;           // Mark block in use.
  80         log_write(bp);
  81         brelse(bp);
  82         bzero(dev, b + bi);
  83         return b + bi;
  84       }
  85     }
  86     brelse(bp);
  87   }
  88   printk("balloc: out of blocks\n");
  89   return 0;
  90 }
  91 
  92 // Free a disk block.
  93 static void
  94 bfree(int dev, uint b)
  95 {
  96   struct buf *bp;
  97   int bi, m;
  98 
  99   bp = bread(dev, BBLOCK(b, sb));
 100   bi = b % BPB;
 101   m = 1 << (bi % 8);
 102   if ((bp->data[bi / 8] & m) == 0)
 103     panic("freeing free block");
 104   bp->data[bi / 8] &= ~m;
 105   log_write(bp);
 106   brelse(bp);
 107 }
 108 
 109 // Inodes.
 110 //
 111 // An inode describes a single unnamed file.
 112 // The inode disk structure holds metadata: the file's type,
 113 // its size, the number of links referring to it, and the
 114 // list of blocks holding the file's content.
 115 //
 116 // The inodes are laid out sequentially on disk at block
 117 // sb.inodestart. Each inode has a number, indicating its
 118 // position on the disk.
 119 //
 120 // The kernel keeps a table of in-use inodes in memory
 121 // to provide a place for synchronizing access
 122 // to inodes used by multiple processes. The in-memory
 123 // inodes include book-keeping information that is
 124 // not stored on disk: ip->ref and ip->valid.
 125 //
 126 // An inode and its in-memory representation go through a
 127 // sequence of states before they can be used by the
 128 // rest of the file system code.
 129 //
 130 // * Allocation: an inode is allocated if its type (on disk)
 131 //   is non-zero. ialloc() allocates, and iput() frees if
 132 //   the reference and link counts have fallen to zero.
 133 //
 134 // * Referencing in table: an entry in the inode table
 135 //   is free if ip->ref is zero. Otherwise ip->ref tracks
 136 //   the number of in-memory pointers to the entry (open
 137 //   files and current directories). iget() finds or
 138 //   creates a table entry and increments its ref; iput()
 139 //   decrements ref.
 140 //
 141 // * Valid: the information (type, size, &c) in an inode
 142 //   table entry is only correct when ip->valid is 1.
 143 //   ilock() reads the inode from
 144 //   the disk and sets ip->valid, while iput() clears
 145 //   ip->valid if ip->ref has fallen to zero.
 146 //
 147 // * Locked: file system code may only examine and modify
 148 //   the information in an inode and its content if it
 149 //   has first locked the inode.
 150 //
 151 // Thus a typical sequence is:
 152 //   ip = iget(dev, inum)
 153 //   ilock(ip)
 154 //   ... examine and modify ip->xxx ...
 155 //   iunlock(ip)
 156 //   iput(ip)
 157 //
 158 // ilock() is separate from iget() so that system calls can
 159 // get a long-term reference to an inode (as for an open file)
 160 // and only lock it for short periods (e.g., in read()).
 161 // The separation also helps avoid deadlock and races during
 162 // pathname lookup. iget() increments ip->ref so that the inode
 163 // stays in the table and pointers to it remain valid.
 164 //
 165 // Many internal file system functions expect the caller to
 166 // have locked the inodes involved; this lets callers create
 167 // multi-step atomic operations.
 168 //
 169 // The itable.lock spin-lock protects the allocation of itable
 170 // entries. Since ip->ref indicates whether an entry is free,
 171 // and ip->dev and ip->inum indicate which i-node an entry
 172 // holds, one must hold itable.lock while using any of those fields.
 173 //
 174 // An ip->lock sleep-lock protects all ip-> fields other than ref,
 175 // dev, and inum.  One must hold ip->lock in order to
 176 // read or write that inode's ip->valid, ip->size, ip->type, &c.
 177 
 178 struct {
 179   struct spinlock lock;
 180   struct inode inode[NINODE];
 181 } itable;
 182 
 183 void
 184 iinit()
 185 {
 186   int i = 0;
 187 
 188   initlock(&itable.lock, "itable");
 189   for (i = 0; i < NINODE; i++) {
 190     initsleeplock(&itable.inode[i].lock, "inode");
 191   }
 192 }
 193 
 194 static struct inode *iget(uint dev, uint inum);
 195 
 196 // Allocate an inode on device dev.
 197 // Mark it as allocated by  giving it type type.
 198 // Returns an unlocked but allocated and referenced inode,
 199 // or NULL if there is no free inode.
 200 struct inode *
 201 ialloc(uint dev, short type)
 202 {
 203   int inum;
 204   struct buf *bp;
 205   struct dinode *dip;
 206 
 207   for (inum = 1; inum < sb.ninodes; inum++) {
 208     bp = bread(dev, IBLOCK(inum, sb));
 209     dip = (struct dinode *)bp->data + inum % IPB;
 210     if (dip->type == 0) { // a free inode
 211       memset(dip, 0, sizeof(*dip));
 212       dip->type = type;
 213       log_write(bp); // mark it allocated on the disk
 214       brelse(bp);
 215       return iget(dev, inum);
 216     }
 217     brelse(bp);
 218   }
 219   printk("ialloc: no inodes\n");
 220   return 0;
 221 }
 222 
 223 // Copy a modified in-memory inode to disk.
 224 // Must be called after every change to an ip->xxx field
 225 // that lives on disk.
 226 // Caller must hold ip->lock.
 227 void
 228 iupdate(struct inode *ip)
 229 {
 230   struct buf *bp;
 231   struct dinode *dip;
 232 
 233   bp = bread(ip->dev, IBLOCK(ip->inum, sb));
 234   dip = (struct dinode *)bp->data + ip->inum % IPB;
 235   dip->type = ip->type;
 236   dip->major = ip->major;
 237   dip->minor = ip->minor;
 238   dip->nlink = ip->nlink;
 239   dip->size = ip->size;
 240   memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
 241   log_write(bp);
 242   brelse(bp);
 243 }
 244 
 245 // Find the inode with number inum on device dev
 246 // and return the in-memory copy. Does not lock
 247 // the inode and does not read it from disk.
 248 static struct inode *
 249 iget(uint dev, uint inum)
 250 {
 251   struct inode *ip, *empty;
 252 
 253   acquire(&itable.lock);
 254 
 255   // Is the inode already in the table?
 256   empty = 0;
 257   for (ip = &itable.inode[0]; ip < &itable.inode[NINODE]; ip++) {
 258     if (ip->ref > 0 && ip->dev == dev && ip->inum == inum) {
 259       ip->ref++;
 260       release(&itable.lock);
 261       return ip;
 262     }
 263     if (empty == 0 && ip->ref == 0) // Remember empty slot.
 264       empty = ip;
 265   }
 266 
 267   // Recycle an inode entry.
 268   if (empty == 0)
 269     panic("iget: no inodes");
 270 
 271   ip = empty;
 272   ip->dev = dev;
 273   ip->inum = inum;
 274   ip->ref = 1;
 275   ip->valid = 0;
 276   release(&itable.lock);
 277 
 278   return ip;
 279 }
 280 
 281 // Increment reference count for ip.
 282 // Returns ip to enable ip = idup(ip1) idiom.
 283 struct inode *
 284 idup(struct inode *ip)
 285 {
 286   acquire(&itable.lock);
 287   ip->ref++;
 288   release(&itable.lock);
 289   return ip;
 290 }
 291 
 292 // Lock the given inode.
 293 // Reads the inode from disk if necessary.
 294 void
 295 ilock(struct inode *ip)
 296 {
 297   struct buf *bp;
 298   struct dinode *dip;
 299 
 300   if (ip == 0 || ip->ref < 1)
 301     panic("ilock");
 302 
 303   acquiresleep(&ip->lock);
 304 
 305   if (ip->valid == 0) {
 306     bp = bread(ip->dev, IBLOCK(ip->inum, sb));
 307     dip = (struct dinode *)bp->data + ip->inum % IPB;
 308     ip->type = dip->type;
 309     ip->major = dip->major;
 310     ip->minor = dip->minor;
 311     ip->nlink = dip->nlink;
 312     ip->size = dip->size;
 313     memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
 314     brelse(bp);
 315     ip->valid = 1;
 316     if (ip->type == 0)
 317       panic("ilock: no type");
 318   }
 319 }
 320 
 321 // Unlock the given inode.
 322 void
 323 iunlock(struct inode *ip)
 324 {
 325   if (ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
 326     panic("iunlock");
 327 
 328   releasesleep(&ip->lock);
 329 }
 330 
 331 // Mark the on-disk inode free.
 332 static void
 333 ifree(uint dev, uint inum)
 334 {
 335   struct buf *bp = bread(dev, IBLOCK(inum, sb));
 336   struct dinode *dip = (struct dinode *)bp->data + inum % IPB;
 337   dip->type = 0;
 338   log_write(bp);
 339   brelse(bp);
 340 }
 341 
 342 // Drop a reference to an in-memory inode.
 343 // If that was the last reference, the inode table entry can
 344 // be recycled.
 345 // If that was the last reference and the inode has no links
 346 // to it, free the inode (and its content) on disk.
 347 // All calls to iput() must be inside a transaction in
 348 // case it has to free the inode.
 349 void
 350 iput(struct inode *ip)
 351 {
 352   acquire(&itable.lock);
 353 
 354   // Last reference of an unlinked inode?  Capture dev/inum before ref--,
 355   // since once ref hits 0, ip may be recycled by a concurrent iget()
 356   // for a different inum.
 357   int last = (ip->ref == 1 && ip->valid && ip->nlink == 0);
 358   uint dev = ip->dev, inum = ip->inum;
 359 
 360   if (last) {
 361     // ip->ref == 1 means no other process can have ip locked.
 362     acquiresleep(&ip->lock);
 363     release(&itable.lock);
 364 
 365     itrunc(ip); // free the data blocks (type stays nonzero on disk)
 366     ip->valid = 0;
 367 
 368     releasesleep(&ip->lock);
 369 
 370     acquire(&itable.lock);
 371   }
 372 
 373   ip->ref--;
 374   release(&itable.lock);
 375 
 376   if (last)
 377     ifree(dev, inum); // now clear type on disk: inum becomes allocatable
 378 }
 379 
 380 // Common idiom: unlock, then put.
 381 void
 382 iunlockput(struct inode *ip)
 383 {
 384   iunlock(ip);
 385   iput(ip);
 386 }
 387 
 388 void
 389 ireclaim(int dev)
 390 {
 391   for (int inum = 1; inum < sb.ninodes; inum++) {
 392     struct inode *ip = 0;
 393     struct buf *bp = bread(dev, IBLOCK(inum, sb));
 394     struct dinode *dip = (struct dinode *)bp->data + inum % IPB;
 395     if (dip->type != 0 && dip->nlink == 0) { // is an orphaned inode
 396       printk("ireclaim: orphaned inode %d\n", inum);
 397       ip = iget(dev, inum);
 398     }
 399     brelse(bp);
 400     if (ip) {
 401       begin_op();
 402       ilock(ip);
 403       iunlock(ip);
 404       iput(ip);
 405       end_op();
 406     }
 407   }
 408 }
 409 
 410 // Inode content
 411 //
 412 // The content (data) associated with each inode is stored
 413 // in blocks on the disk. The first NDIRECT block numbers
 414 // are listed in ip->addrs[].  The next NINDIRECT blocks are
 415 // listed in block ip->addrs[NDIRECT].
 416 
 417 // Return the disk block address of the nth block in inode ip.
 418 // If there is no such block, bmap allocates one.
 419 // returns 0 if out of disk space.
 420 static uint
 421 bmap(struct inode *ip, uint bn)
 422 {
 423   uint addr, *a;
 424   struct buf *bp;
 425 
 426   if (bn < NDIRECT) {
 427     if ((addr = ip->addrs[bn]) == 0) {
 428       addr = balloc(ip->dev);
 429       if (addr == 0)
 430         return 0;
 431       ip->addrs[bn] = addr;
 432     }
 433     return addr;
 434   }
 435   bn -= NDIRECT;
 436 
 437   if (bn < NINDIRECT) {
 438     // Load indirect block, allocating if necessary.
 439     if ((addr = ip->addrs[NDIRECT]) == 0) {
 440       addr = balloc(ip->dev);
 441       if (addr == 0)
 442         return 0;
 443       ip->addrs[NDIRECT] = addr;
 444     }
 445     bp = bread(ip->dev, addr);
 446     a = (uint *)bp->data;
 447     if ((addr = a[bn]) == 0) {
 448       addr = balloc(ip->dev);
 449       if (addr) {
 450         a[bn] = addr;
 451         log_write(bp);
 452       }
 453     }
 454     brelse(bp);
 455     return addr;
 456   }
 457 
 458   panic("bmap: out of range");
 459 }
 460 
 461 // Truncate inode (discard contents).
 462 // Caller must hold ip->lock.
 463 void
 464 itrunc(struct inode *ip)
 465 {
 466   int i, j;
 467   struct buf *bp;
 468   uint *a;
 469 
 470   for (i = 0; i < NDIRECT; i++) {
 471     if (ip->addrs[i]) {
 472       bfree(ip->dev, ip->addrs[i]);
 473       ip->addrs[i] = 0;
 474     }
 475   }
 476 
 477   if (ip->addrs[NDIRECT]) {
 478     bp = bread(ip->dev, ip->addrs[NDIRECT]);
 479     a = (uint *)bp->data;
 480     for (j = 0; j < NINDIRECT; j++) {
 481       if (a[j])
 482         bfree(ip->dev, a[j]);
 483     }
 484     brelse(bp);
 485     bfree(ip->dev, ip->addrs[NDIRECT]);
 486     ip->addrs[NDIRECT] = 0;
 487   }
 488 
 489   ip->size = 0;
 490   iupdate(ip);
 491 }
 492 
 493 // Copy stat information from inode.
 494 // Caller must hold ip->lock.
 495 void
 496 stati(struct inode *ip, struct stat *st)
 497 {
 498   st->dev = ip->dev;
 499   st->ino = ip->inum;
 500   st->type = ip->type;
 501   st->nlink = ip->nlink;
 502   st->size = ip->size;
 503 }
 504 
 505 // Read data from inode.
 506 // Caller must hold ip->lock.
 507 // If user_dst==1, then dst is a user virtual address;
 508 // otherwise, dst is a kernel address.
 509 int
 510 readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)
 511 {
 512   uint tot, m;
 513   struct buf *bp;
 514 
 515   if (off > ip->size || off + n < off)
 516     return 0;
 517   if (off + n > ip->size)
 518     n = ip->size - off;
 519 
 520   for (tot = 0; tot < n; tot += m, off += m, dst += m) {
 521     uint addr = bmap(ip, off / BSIZE);
 522     if (addr == 0)
 523       break;
 524     bp = bread(ip->dev, addr);
 525     m = min(n - tot, BSIZE - off % BSIZE);
 526     if (either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
 527       brelse(bp);
 528       tot = -1;
 529       break;
 530     }
 531     brelse(bp);
 532   }
 533   return tot;
 534 }
 535 
 536 // Write data to inode.
 537 // Caller must hold ip->lock.
 538 // If user_src==1, then src is a user virtual address;
 539 // otherwise, src is a kernel address.
 540 // Returns the number of bytes successfully written.
 541 // If the return value is less than the requested n,
 542 // there was an error of some kind.
 543 int
 544 writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
 545 {
 546   uint tot, m;
 547   struct buf *bp;
 548 
 549   if (off > ip->size || off + n < off)
 550     return -1;
 551   if (off + n > MAXFILE * BSIZE)
 552     return -1;
 553 
 554   for (tot = 0; tot < n; tot += m, off += m, src += m) {
 555     uint addr = bmap(ip, off / BSIZE);
 556     if (addr == 0)
 557       break;
 558     bp = bread(ip->dev, addr);
 559     m = min(n - tot, BSIZE - off % BSIZE);
 560     if (either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
 561       // Might have partially updated the block, so we need to log it.
 562       log_write(bp);
 563       brelse(bp);
 564       break;
 565     }
 566     log_write(bp);
 567     brelse(bp);
 568   }
 569 
 570   if (off > ip->size)
 571     ip->size = off;
 572 
 573   // write the i-node back to disk even if the size didn't change
 574   // because the loop above might have called bmap() and added a new
 575   // block to ip->addrs[].
 576   iupdate(ip);
 577 
 578   return tot;
 579 }
 580 
 581 // Directories
 582 
 583 int
 584 namecmp(const char *s, const char *t)
 585 {
 586   return strncmp(s, t, DIRSIZ);
 587 }
 588 
 589 // Look for a directory entry in a directory.
 590 // If found, set *poff to byte offset of entry.
 591 struct inode *
 592 dirlookup(struct inode *dp, char *name, uint *poff)
 593 {
 594   uint off, inum;
 595   struct dirent de;
 596 
 597   if (dp->type != T_DIR)
 598     panic("dirlookup not DIR");
 599 
 600   for (off = 0; off < dp->size; off += sizeof(de)) {
 601     if (readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
 602       panic("dirlookup read");
 603     if (de.inum == 0)
 604       continue;
 605     if (namecmp(name, de.name) == 0) {
 606       // entry matches path element
 607       if (poff)
 608         *poff = off;
 609       inum = de.inum;
 610       return iget(dp->dev, inum);
 611     }
 612   }
 613 
 614   return 0;
 615 }
 616 
 617 // Write a new directory entry (name, inum) into the directory dp.
 618 // Returns 0 on success, -1 on failure (e.g. out of disk blocks).
 619 int
 620 dirlink(struct inode *dp, char *name, uint inum)
 621 {
 622   int off;
 623   struct dirent de;
 624   struct inode *ip;
 625 
 626   // Check that name is not present.
 627   if ((ip = dirlookup(dp, name, 0)) != 0) {
 628     iput(ip);
 629     return -1;
 630   }
 631 
 632   // Look for an empty dirent.
 633   for (off = 0; off < dp->size; off += sizeof(de)) {
 634     if (readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
 635       panic("dirlink read");
 636     if (de.inum == 0)
 637       break;
 638   }
 639 
 640   strncpy(de.name, name, DIRSIZ);
 641   de.inum = inum;
 642   if (writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
 643     return -1;
 644 
 645   return 0;
 646 }
 647 
 648 // Paths
 649 
 650 // Copy the next path element from path into name.
 651 // Return a pointer to the element following the copied one.
 652 // The returned path has no leading slashes,
 653 // so the caller can check *path=='\0' to see if the name is the last one.
 654 // If no name to remove, return 0.
 655 //
 656 // Examples:
 657 //   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
 658 //   skipelem("///a//bb", name) = "bb", setting name = "a"
 659 //   skipelem("a", name) = "", setting name = "a"
 660 //   skipelem("", name) = skipelem("////", name) = 0
 661 //
 662 static char *
 663 skipelem(char *path, char *name)
 664 {
 665   char *s;
 666   int len;
 667 
 668   while (*path == '/')
 669     path++;
 670   if (*path == 0)
 671     return 0;
 672   s = path;
 673   while (*path != '/' && *path != 0)
 674     path++;
 675   len = path - s;
 676   if (len >= DIRSIZ)
 677     memmove(name, s, DIRSIZ);
 678   else {
 679     memmove(name, s, len);
 680     name[len] = 0;
 681   }
 682   while (*path == '/')
 683     path++;
 684   return path;
 685 }
 686 
 687 // Look up and return the inode for a path name.
 688 // If parent != 0, return the inode for the parent and copy the final
 689 // path element into name, which must have room for DIRSIZ bytes.
 690 // Must be called inside a transaction since it calls iput().
 691 static struct inode *
 692 namex(char *path, int nameiparent, char *name)
 693 {
 694   struct inode *ip, *next;
 695 
 696   if (*path == '/')
 697     ip = iget(ROOTDEV, ROOTINO);
 698   else
 699     ip = idup(myproc()->cwd);
 700 
 701   while ((path = skipelem(path, name)) != 0) {
 702     ilock(ip);
 703     if (ip->type != T_DIR) {
 704       iunlockput(ip);
 705       return 0;
 706     }
 707     if (ip->nlink == 0) {
 708       iunlockput(ip);
 709       return 0;
 710     }
 711     if (nameiparent && *path == '\0') {
 712       // Stop one level early.
 713       iunlock(ip);
 714       return ip;
 715     }
 716     if ((next = dirlookup(ip, name, 0)) == 0) {
 717       iunlockput(ip);
 718       return 0;
 719     }
 720     iunlockput(ip);
 721     ip = next;
 722   }
 723   if (nameiparent) {
 724     iput(ip);
 725     return 0;
 726   }
 727   return ip;
 728 }
 729 
 730 struct inode *
 731 namei(char *path)
 732 {
 733   char name[DIRSIZ];
 734   return namex(path, 0, name);
 735 }
 736 
 737 struct inode *
 738 nameiparent(char *path, char *name)
 739 {
 740   return namex(path, 1, name);
 741 }