Inodes, directories and path lookup

1warm-upChoose one

A struct inode in memory has both ref and nlink. What does each one count?

kernel/file.h

16// in-memory copy of an inode
17struct 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?
23
short type; // copy of disk inode
short major;
short minor;
short nlink;
uint size;
uint addrs[NDIRECT + 1];
30};

ref counts in-memory pointers to the table entry (open files, current directories, temporary lookups); nlink counts directory entries on disk that name the inode.ref counts the data blocks the inode owns; nlink counts the indirect blocks.They are the same count kept in two places, one in memory and one on disk.ref counts open file descriptors; nlink counts processes using the file.

2warm-upType a number

How many on-disk inodes (dinode) fit in one disk block in this file system (the value of IPB)?

kernel/fs.h

31// On-disk inode structure
32struct dinode {
33  short type;              // File type
34  short major;             // Major device number (T_DEVICE only)
35  short minor;             // Minor device number (T_DEVICE only)
36  short nlink;             // Number of links to inode in file system
37  uint size;               // Size of file (bytes)
38  uint addrs[NDIRECT + 1]; // Data block addresses
39};
40
41// Inodes per block.
42#define IPB (BSIZE / sizeof(struct dinode))
43
44// Block containing inode i
45#define IBLOCK(i, sb) ((i) / IPB + sb.inodestart)

decimal, 0x hex or 0b binary

3warm-upChoose one

What does the content of a directory (its data blocks) consist of in this file system?

kernel/fs.h

53// Directory is a file containing a sequence of dirent structures.
54#define DIRSIZ 14
55
56// The name field may have DIRSIZ characters and not end in a NUL
57// character.
58struct dirent {
59  ushort inum;
60  char name[DIRSIZ] __attribute__((nonstring));
61};

An array of 16-byte entries, each a 2-byte inode number and a 14-byte name; an entry with inode number 0 is free.A hash table from names to inode numbers.The full path of every file below it, for fast lookup.The inodes of the files it contains, copied inline.

4warm-upTrue or false, and why

True or false: when rm removes the only name of a file that another process still has open, the file’s data blocks are freed immediately.

TrueFalse

Why?

sys_unlink drops nlink to 0, but its iput sees ref greater than 1 (the open file’s reference), so it only decrements ref; the last close frees the blocks.sys_unlink refuses to remove a file that is open, and fails with -1.The blocks are freed only by ireclaim at the next boot.

5warm-upChoose one

iget returns an inode table entry with valid = 0 and does not read the inode from disk; ilock does that later. Why not read it in iget?

kernel/fs.c

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.
248static struct inode *
249iget(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}

Because iget does not know the inode number yet.iget runs while holding itable.lock, a spinlock, and reading the disk sleeps; ilock holds the inode’s sleep-lock, under which sleeping is allowed.Because the disk driver cannot be used until ilock has set up the buffer cache.To save disk reads, since most callers never look at the inode’s contents.

6warm-upMatch the pairs

Match each function with its job.

igetilockiupdateiputialloc

7warm-upClick the line

In namex, click the line that gives up the current directory (its lock and its reference) after finding the next element, before the loop locks that element.

kernel/fs.c

691static struct inode *
692namex(char *path, int nameiparent, char *name)
693{
struct inode *ip, *next;
695
if (*path == '/')
  ip = iget(ROOTDEV, ROOTINO);
else
  ip = idup(myproc()->cwd);
700
while ((path = skipelem(path, name)) != 0) {
  ilock(ip);
  if (ip->type != T_DIR) {
    iunlockput(ip);
    return 0;
  }
  if (ip->nlink == 0) {
    iunlockput(ip);
    return 0;
  }
  if (nameiparent && *path == '\0') {
    // Stop one level early.
    iunlock(ip);
    return ip;
  }
  if ((next = dirlookup(ip, name, 0)) == 0) {
    iunlockput(ip);
    return 0;
  }
  iunlockput(ip);
  ip = next;
}
if (nameiparent) {
  iput(ip);
  return 0;
}
return ip;
728}

Your pick: none yet (click a line in the code)

8warm-upType a number

What is the largest number of data blocks one file can have in this file system (MAXFILE)?

kernel/fs.h

26#define NDIRECT   12
27#define NINDIRECT (BSIZE / sizeof(uint))
28#define MAXFILE   (NDIRECT + NINDIRECT)

decimal, 0x hex or 0b binary

9solidType a number

In this image the superblock says inodestart = 33. Which disk block holds inode 24?

kernel/fs.h

41// Inodes per block.
42#define IPB (BSIZE / sizeof(struct dinode))
43
44// Block containing inode i
45#define IBLOCK(i, sb) ((i) / IPB + sb.inodestart)

decimal, 0x hex or 0b binary

10solidChoose one

Why does namex unlock the current directory before it locks the next path element, instead of locking the child first and then letting go of the parent?

kernel/fs.c

691static struct inode *
692namex(char *path, int nameiparent, char *name)
693{
struct inode *ip, *next;
695
if (*path == '/')
  ip = iget(ROOTDEV, ROOTINO);
else
  ip = idup(myproc()->cwd);
700
while ((path = skipelem(path, name)) != 0) {
  ilock(ip);
  if (ip->type != T_DIR) {
    iunlockput(ip);
    return 0;
  }
  if (ip->nlink == 0) {
    iunlockput(ip);
    return 0;
  }
  if (nameiparent && *path == '\0') {
    // Stop one level early.
    iunlock(ip);
    return ip;
  }
  if ((next = dirlookup(ip, name, 0)) == 0) {
    iunlockput(ip);
    return 0;
  }
  iunlockput(ip);
  ip = next;
}
if (nameiparent) {
  iput(ip);
  return 0;
}
return ip;
728}

Holding both could deadlock: looking up “.” returns the same inode (the process would wait for its own lock), and “…” lets two walks lock the same two directories in opposite orders.Because the inode table has room for only one locked inode per process.To make the whole path lookup one atomic snapshot of the tree.Because a sleep-lock cannot be acquired while another sleep-lock is held.

11solidPut in order

open("newfile", O_CREATE|O_WRONLY) calls create for a name that does not exist yet. Put the steps of create in order.

kernel/sysfile.c

258static struct inode *
259create(char *path, short type, short major, short minor)
260{
struct inode *ip, *dp;
char name[DIRSIZ];
263
if ((dp = nameiparent(path, name)) == 0)
  return 0;
266
ilock(dp);
268
if (dp->nlink == 0) {
  iunlockput(dp);
  return 0;
}
273
// a new directory's ".." would push dp->nlink past its maximum
if (type == T_DIR && dp->nlink >= NLINK_MAX) {
  iunlockput(dp);
  return 0;
}
279
if ((ip = dirlookup(dp, name, 0)) != 0) {
  iunlockput(dp);
  ilock(ip);
  if (type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE))
    return ip;
  iunlockput(ip);
  return 0;
}
288
if ((ip = ialloc(dp->dev, type)) == 0) {
  iunlockput(dp);
  return 0;
}
293
ilock(ip);
ip->major = major;
ip->minor = minor;
ip->nlink = 1;
iupdate(ip);
299
if (type == T_DIR) { // Create . and .. entries.
  // No ip->nlink++ for ".": avoid cyclic ref count.
  if (dirlink(ip, ".", ip->inum) < 0 || dirlink(ip, "..", dp->inum) < 0)
    goto fail;
}
305
if (dirlink(dp, name, ip->inum) < 0)
  goto fail;
308
if (type == T_DIR) {
  // now that success is guaranteed:
  dp->nlink++; // for ".."
  iupdate(dp);
}
314
iunlockput(dp);
316
return ip;

iunlockput(dp) and return the new inode, still locked
ialloc claims a free dinode and gives it type T_FILE
dirlink writes the entry (name, inum) into the parent
dirlookup finds no entry with that name
nameiparent returns the parent directory, referenced but unlocked, and the last name
ilock(dp), then check that dp->nlink is not 0
ilock(ip), set nlink = 1, iupdate

12solidChoose all that apply

Which of these code paths hold two inode sleep-locks at the same time?

sys_unlink() removing a filenamex() walking /a/b/ccreate() when the name already exists as a filesys_open() of an existing file without O_CREATEsys_link()create() making a new file

13solidType a number

Starting from nothing, a user runs mkdir /d, mkdir /d/x, mkdir /d/y and echo hi > /d/f. What is the nlink of directory d afterwards?

decimal, 0x hex or 0b binary

14solidChoose one

sys_unlink refuses the names . and .. (line 221) before it calls dirlookup and ilock(ip). Apart from keeping the tree intact, what would go wrong with the locks if unlink("d/.") were allowed through?

kernel/sysfile.c

201uint64
202sys_unlink(void)
203{
struct inode *ip, *dp;
struct dirent de;
char name[DIRSIZ], path[MAXPATH];
uint off;
208
if (argstr(0, path, MAXPATH) < 0)
  return -1;
211
begin_op();
if ((dp = nameiparent(path, name)) == 0) {
  end_op();
  return -1;
}
217
ilock(dp);
219
// Cannot unlink "." or "..".
if (namecmp(name, ".") == 0 || namecmp(name, "..") == 0)
  goto bad;
223
if ((ip = dirlookup(dp, name, &off)) == 0)
  goto bad;
ilock(ip);
227
if (ip->nlink < 1)
  panic("unlink: nlink < 1");
if (ip->type == T_DIR && !isdirempty(ip)) {
  iunlockput(ip);
  goto bad;
}

Nothing would go wrong with the locks; the entry would be removed and d would become unreachable.The kernel would panic with “acquire”, because the same lock is taken twice.dirlookup would return d itself, and ilock(ip) on line 226 would wait forever for the lock this process already holds on d.dirlookup would panic, because “.” is not stored in the directory.

15solidChoose one

A program creates abcdefghijklmnop (16 characters) and then calls open("abcdefghijklmnXY", O_RDONLY) in the same directory. What happens?

kernel/fs.c

662static char *
663skipelem(char *path, char *name)
664{
char *s;
int len;
667
while (*path == '/')
  path++;
if (*path == 0)
  return 0;
s = path;
while (*path != '/' && *path != 0)
  path++;
len = path - s;
if (len >= DIRSIZ)
  memmove(name, s, DIRSIZ);
else {
  memmove(name, s, len);
  name[len] = 0;
}
while (*path == '/')
  path++;
return path;
685}

The create already failed, because names longer than 14 characters are rejected.The open succeeds and returns the same file, because names are cut to 14 bytes and compared with strncmp limited to 14.The open fails, because no file of that exact name exists.The open succeeds but reads garbage, since the stored name has no terminating zero.

16solidPut in order

iput is dropping the last reference to an inode whose nlink is 0. Put its steps in order.

kernel/fs.c

349void
350iput(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}

acquire itable.lock; compute last and copy dev and inum into locals
itrunc: free the data blocks, set size 0, iupdate
acquiresleep(&ip->lock) while still holding itable.lock
ifree(dev, inum): write type 0 on disk
release itable.lock
re-acquire itable.lock, ref-- (to 0), release it
valid = 0, then release the sleep-lock

17solidChoose one

fileclose wraps the iput of an inode in begin_op and end_op, even though closing a file usually writes nothing. Why?

kernel/file.c

58// Close file f.  (Decrement ref count, close when reaches 0.)
59void
60fileclose(struct file *f)
61{
struct file ff;
63
acquire(&ftable.lock);
if (f->ref < 1)
  panic("fileclose");
if (--f->ref > 0) {
  release(&ftable.lock);
  return;
}
ff = *f;
f->ref = 0;
f->type = FD_NONE;
release(&ftable.lock);
75
if (ff.type == FD_PIPE) {
  pipeclose(ff.pipe, ff.writable);
} else if (ff.type == FD_INODE || ff.type == FD_DEVICE) {
  begin_op();
  iput(ff.ip);
  end_op();
}
83}

Because iput takes itable.lock, which may only be taken inside a transaction.To flush the file’s modified data blocks to disk on close.To update the file’s access time on disk.This iput might be the last reference to an unlinked inode; then it truncates and frees it, writing the bitmap and inode blocks, and every disk change must be inside a transaction.

18solidDecode the bits

gdb shows the first 12 bytes of inode 24’s dinode (little-endian: type, major, minor, nlink as 2-byte shorts, then size as a 4-byte uint): 01 00 00 00 00 00 03 00 40 00 00 00. Decode it.

Value: 0100 0000 0000 0300 40000000

typenlinkHow many subdirectories does it have?How many 16-byte entries does its content hold (size / 16)?If its ref dropped to 0 now, would iput free it?

19deepChoose all that apply

rm /x removes a regular file /x that has 3 data blocks, nlink 1, and is not open anywhere. Which blocks does this one transaction log (pass to log_write)?

The bitmap blockThe root directory’s data block that held the entry for xThe block holding the root directory’s inodex’s 3 data blocksThe log header blockThe block holding x’s inode

20solidClick the line

In iput, click the line after which ialloc on another hart may hand this inode’s number to a brand-new file.

kernel/fs.c

349void
350iput(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}

Your pick: none yet (click a line in the code)

21deepFill in the machine state

cat calls close(3) on a file that rm already unlinked. Inside fileclose → iput, line 362’s acquiresleep has just returned and line 363 has not run yet. What is the state of the hart running cat?

kernel/fs.c

349void
350iput(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}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

22deepChoose one

iput copies ip->dev and ip->inum into the locals dev and inum (line 358), and line 377 calls ifree(dev, inum) rather than ifree(ip->dev, ip->inum). Why?

kernel/fs.c

349void
350iput(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}

Because ip->inum is cleared by itrunc.Only for speed, to avoid reading ip twice.After ref drops to 0 and itable.lock is released, another hart’s iget may recycle this table entry for a different inode, overwriting ip->dev and ip->inum.Because ifree needs the values after ip has been passed to kfree.

23deepChoose one

On a fresh disk a user runs mkdir /a, mkdir /a/b, cd /a/b, /rm /a/b, /rm /a, and then /ls ... What happens in this kernel, and which check is responsible?

kernel/fs.c

691static struct inode *
692namex(char *path, int nameiparent, char *name)
693{
struct inode *ip, *next;
695
if (*path == '/')
  ip = iget(ROOTDEV, ROOTINO);
else
  ip = idup(myproc()->cwd);
700
while ((path = skipelem(path, name)) != 0) {
  ilock(ip);
  if (ip->type != T_DIR) {
    iunlockput(ip);
    return 0;
  }
  if (ip->nlink == 0) {
    iunlockput(ip);
    return 0;
  }
  if (nameiparent && *path == '\0') {
    // Stop one level early.
    iunlock(ip);
    return ip;
  }
  if ((next = dirlookup(ip, name, 0)) == 0) {
    iunlockput(ip);
    return 0;
  }
  iunlockput(ip);
  ip = next;
}
if (nameiparent) {
  iput(ip);
  return 0;
}
return ip;
728}

ls prints that it cannot open “…”: namex locks b, finds nlink == 0 (b was unlinked) and returns 0 without looking up “…”.ls lists the root directory, because a deleted directory’s “…” is redirected to /.The kernel panics with “ilock: no type”./rm /a/b fails, because b is the shell’s current directory.

24deepChoose all that apply

Two processes on two harts call open("same", O_CREATE|O_WRONLY) in / at nearly the same moment; same does not exist yet. Which statements are true afterwards?

kernel/sysfile.c

258static struct inode *
259create(char *path, short type, short major, short minor)
260{
struct inode *ip, *dp;
char name[DIRSIZ];
263
if ((dp = nameiparent(path, name)) == 0)
  return 0;
266
ilock(dp);
268
if (dp->nlink == 0) {
  iunlockput(dp);
  return 0;
}
273
// a new directory's ".." would push dp->nlink past its maximum
if (type == T_DIR && dp->nlink >= NLINK_MAX) {
  iunlockput(dp);
  return 0;
}
279
if ((ip = dirlookup(dp, name, 0)) != 0) {
  iunlockput(dp);
  ilock(ip);
  if (type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE))
    return ip;
  iunlockput(ip);
  return 0;
}
288
if ((ip = ialloc(dp->dev, type)) == 0) {
  iunlockput(dp);
  return 0;
}

The two processes share one struct file and therefore one offsetBoth open calls succeedialloc was called only once for sameThe root directory contains exactly one entry named sameThe second open fails because the name already exists

25deepChoose one

sys_link increments the file’s nlink, then unlocks the file (line 153) before calling nameiparent and locking the target directory. Why not keep the file locked until the new entry is written?

kernel/sysfile.c

122// Create the path new as a link to the same inode as old.
123uint64
124sys_link(void)
125{
char name[DIRSIZ], new[MAXPATH], old[MAXPATH];
struct inode *dp, *ip;
128
if (argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
  return -1;
131
begin_op();
if ((ip = namei(old)) == 0) {
  end_op();
  return -1;
}
137
ilock(ip);
if (ip->type == T_DIR) {
  iunlockput(ip);
  end_op();
  return -1;
}
144
if (ip->nlink >= NLINK_MAX) {
  iunlockput(ip);
  end_op();
  return -1;
}
150
ip->nlink++;
iupdate(ip);
iunlock(ip);
154
if ((dp = nameiparent(new, name)) == 0)
  goto bad;
ilock(dp);
// dp may have been unlinked while we resolved it; linking into an
// orphaned directory leaks ip (itrunc discards the record without
// dropping ip->nlink).  create() has the same guard.
if (dp->nlink == 0) {
  iunlockput(dp);
  goto bad;
}
if (dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0) {
  iunlockput(dp);
  goto bad;
}
iunlockput(dp);
iput(ip);
171
end_op();

Because a process may hold at most one sleep-lock.So that other processes can see the higher nlink as soon as possible.Because dirlink panics if the inode it links to is locked.Locking a directory while holding a file in it reverses the parent-before-child order; a concurrent rm of the file (parent, then file) could deadlock with it.