The first and last exercises are problem set-esque questions that could easily appear on a midterm or final exam. In fact, all of the questions asked under Problem 4 were on previous midterms and finals. The middle two problems are experiments that'll require you fire up your laptop and run some programs and development tools.

The lab checkoff sheet for all students—both on-campus and off—can be found right here.

This lab was designed by Jerry Cain.

Problem 1: Direct, Singly Indirect, and Doubly Indirect Block Numbers

Assume blocks are 512 bytes in size, block numbers are four-byte ints, and that inodes include space for 6 block numbers. The first three contain direct block numbers, the next two contain singly indirect block numbers, and the final one contains a doubly indirect block number.

• What's the maximum file size?
  • Maximum file size is (3 * 512) + (2 * 128 * 512) + (128 * 128 * 512), or 8,521,216 bytes. (The first term is the direct blocks, the second term is the singly-indirect blocks, and the third term is the doubly-indirect block)
• How large does a file need to be before the relevant inode requires the first singly indirect block number be used?
  • 3 * 512 + 1, or 1,537 bytes. (The +1 is the first byte that cannot fit)
• How large does a file need to be before the relevant inode requires the first doubly indirect block number be used?
  • 3 * 512 + 2 * 128 * 512 + 1, or 132,609 bytes. (The +1 is the first byte that cannot fit)
• Draw as detailed an inode as you can if it's to represent a regular file that's 2049 bytes in size.
  • The first three block numbers would identify three, saturated payload blocks, and those three payload blocks would store the first 1,536 bytes.
  • The fourth block number—a singly, indirect one—would lead to a block of 512 bytes, although only the first eight bytes will be used. The first four bytes would identify the fourth payload block—itself saturated—to store 512 bytes of payload. The next four bytes would identify a fifth payload block where only the first byte is used.

Problem 2: Experimenting with the stat utility

This problem is more about exploration and experimentation, and not so much about generating a correct answer. The file system reachable from each myth machine consists of the local file system (restated, it's mounted on the physical machine) and networked drives that are grafted onto the fringe of the local file system so that all of AFS—-which consists of many, many independent file systems from around the globe—all contribute to one virtual file system reachable from your local / directory.

Log into myth52 and use the stat command line utility (which is a user program that makes calls to the stat system call as part of its execution) and prints out oodles of information about a file. Type in the following commands and analyze the output:

• stat /
• stat /tmp
• stat /usr
• stat /usr/bin
• stat /usr/bin/g++
• stat /usr/bin/g++-5

The output for each of the five commands above all produce the same device ID but different inode numbers. Read through this to gain insight on what the Device values are.

• Output for s​tat /​ ​includes a size of 4096, a block count of 8, an I/O block size of 4096, an inode number of 2, and a nlinks value of 26. It's also clear it's a directory.

$ stat /
  File: '/'
  Size: 4096        Blocks: 8          IO Block: 4096   directory
Device: 801h/2049d  Inode: 2           Links: 26
Access: (0755/drwxr-xr-x)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2020-01-14 13:49:32.468000040 -0800
Modify: 2018-04-16 17:08:24.260965019 -0700
Change: 2018-04-16 17:08:24.260965019 -0700
 Birth: -

• Directory sizes are always exposed as multiples of the true block size, which is 4096.
• The sector size is 512, and ​stat​ ​states that it uses 8 sectors to store all of its directory entries. (It's unclear why s​tat​ uses blocks here instead of sectors).
• The I/O block size just happens to be the same as the actual block size, but it's listed separately, because it c​ould ​have been different. The I/O block size is the optimal byte transfer size supported by the file system hardware.
• The device information is expressed as a hexadecimal (801h) and a decimal equivalent (2049d). The 801 states that the major device number is 8, and then the minor device number (or partition) within that major device is 1. If you do an ls -lt /dev/sda*, you get a listing within the pseudo-file system like that below, where dev/sda1 ​is a pseudofile representing the device driver that interfaces with the file system holding the root directory. (Special files like this are set up so that software can programmatically interact with device drivers as if they were files.)

$ ls -lt /dev/sda*
brw-rw---- 1 root disk 8, 1 Jan 15 13:43 /dev/sda1
brw-rw---- 1 root disk 8, 5 Jan 15 13:43 /dev/sda5
brw-rw---- 1 root disk 8, 2 Jan 15 13:43 /dev/sda2
brw-rw---- 1 root disk 8, 0 Jan 15 13:43 /dev/sda

• The inode number is 2.
• The number of links is 26, which means that there are 26 different names leading to the root directory's payload: /. is one, and believe it or not, /.. is a second, since .. is the same as . for the root directory. If you ls -lt /​, you see that there are 24 subdirectories, each of which has a .. directory entry. That's the source of the 26.
• You can do similar listing for the other files as you get the same type of information.

For each of the above commands, replace stat with stat -f to get information about the file system on which the file resides (block size, inode table size, number of free blocks, number of free inodes, etc).

• Output for stat -f / l​ooks like this:

$ stat -f /
  File: "/"
    ID: 56c68aaafba5efed Namelen: 255     Type: ext2/ext3
Block size: 4096       Fundamental block size: 4096
Blocks: Total: 51833244   Free: 46320279   Available: 43681521
Inodes: Total: 13180928   Free: 12493200

• ext2​ ​and ext3​ are types of file systems, and the file systems on the myths are evidently a hybrid of the two.
• namelen​ i​s the maximum length of a filename component supported by the filesystem.
• the fundamental block size is the block size we've discussed in lecture, and the block size (without the fundamental prefix) is a hint as to the optimal transfer size for I/O operations (and is generally the same as the I/O Block value discussed above).

Now log into myth55 and run the same commands. Why are the outputs of stat and stat -f the same in some cases and different in others?

• Each of ​myth52​ ​and m​yth55​ h​ave independent file systems and might be populated slightly differently. However, the g++​ ​and g​++-5​ ​executable images, while independent copies of the same file, are exactly that — independent copies of the same file, so all of g++​'s and ​g++-5​'s file properties will be the same.

Now analyze the output of the stat utility when levied against AFS mounts where the master copies of all /usr/class and /usr/class/cs110 files reside. Do this from both myth52 and myth55.

• stat /usr/class
• stat -f /usr/class
• stat /afs/ir.stanford.edu/class
• stat -f /afs/ir.stanford.edu/class
• stat /usr/class/cs110
• stat /afs/ir.stanford.edu/class/cs110
• stat -f /usr/class/cs110

Why are most of the outputs the same for myth52 compared to myth55? Which ones are symbolic links? Why are the device numbers for remotely hosted file systems so small?

• All but one of the outputs is the same, because they all refer to the same files on a remote file system that's been grafted in to contribute to the overall virtual file system that is AFS (or Andrew File System). (The output for ​stat /usr/c​lass​ is slightly different, because that symbolic link resides on the myth52 filesystem).
• Output for stat /usr/class looks like this:

$ stat /usr/class
  File: '/usr/class' -> '/afs/ir.stanford.edu/class'
  Size: 26          Blocks: 0          IO Block: 4096   symbolic link
Device: 801h/2049d  Inode: 8437053     Links: 1
Access: (0777/lrwxrwxrwx)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2020-01-15 13:57:19.502993348 -0800
Modify: 2017-12-01 16:57:20.440137280 -0800
Change: 2017-12-01 16:57:20.440137280 -0800
 Birth: -

• This is a symbolic link stored on myth52's resident file system (note the 801h again). It's clearly identified as a symbolic link (represented via inode with inumber 8437053). Its payload size is 26, which is the length of the /afs/ir.stanford.edu/c​lass​ t​he link expands to. The surprising part is that the payload requires 0 blocks! But that's because symbolic link payloads are stored not in external blocks, but in the the space set aside for the inode's block numbers array. Sneaky!

• Interestingly, the output of s​tat/usr/c​lass/​ (note that extra slash at the end) is different, because that extra slash dereferences the symbolic link!

$ stat /usr/class/
  File: '/usr/class/'
  Size: 309248      Blocks: 604        IO Block: 4096   directory
Device: 28h/40d Inode: 262274      Links: 5
Access: (0755/drwxr-xr-x)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2020-01-15 11:13:50.000000000 -0800
Modify: 2020-01-15 11:13:50.000000001 -0800
Change: 2020-01-15 11:13:50.000000000 -0800
 Birth: -

• Why are the major device numbers so small here? AFS uses major number 0, hence the smaller device number. AFS doesn't expose much about how remotely managed files are stored, which is why they went with a 0.

What about these commands?

• stat /afs/northstar.dartmouth.edu
• stat -f /afs/northstar.dartmouth.edu
• stat /afs/asu.edu
• stat -f /afs/asu.edu

What files can you see within the dartmouth.edu and asu.edu mounts?

One interesting finding with ​stat​ ​and s​tat -f​ o​n those two remote directories is that the fundamental block sizes are 1024 instead of 4096. Additionally, we can see 20 directory entries within ​/afs/northstar.dartmouth.edu ​and 47 directory entries within ​/afs/asu.edu​.

Problem 3: valgrind and orphaned file descriptors

Here's a very short exercise to enhance your understanding of valgrind and what it can do for you. To get started, type the following in to create a local copy of the repository you'll play with for this problem:

~$ git clone /usr/class/cs110/repos/lab1/shared lab1
~$ cd lab1
~$ make

Now open the file and trace through the code to keep tabs on what file descriptors are created, properly closed, and orphaned.

What are dup and dup2? These are system calls that let us copy file descriptors. Here's more information about each of them:

• dup: creates a copy of the entry at the passed-in file descriptor location in the lowest-numbered unused file descriptor position and returns this second file descriptor. What this means is that both these file descriptor entries point to the same open file table entry. This means you can use either to access the file, and reading/writing with one impacts the other. You must also close both the original and the copy. For example, if we say int fd2 = dup(fd1) where fd1 = 3 (and assume no file descriptors beyond 3 are used), this means that fd2 = 4 and thus the index 3 and 4 file descriptor entries both point to the same open file table entry.

• dup2: creates a copy of the entry at the first passed-in file descriptor location in the file descriptor location specified by the second passed-in file descriptor. This is the same as dup, except that instead of the copy being the next available file descriptor, it is specified as the second parameter. If the second parameter is an already-open file descriptor, it is closed before being used. For example, if we say dup2(fd1, fd2) where fd1 = 3 and fd2 = 5, this means that the index 3 and 5 file descriptor entries both point to the same open file table entry.

With this information, try tracing through the program to better understand the file descriptors that are created, closed, and left open. In particular, with the knowledge that open will use the lowest unused file descriptor, as will dup, calculate the actual file descriptor numbers. Then run valgrind ./nonsense to confirm that there aren't any memory leaks or errors (how could there be?), but then run valgrind --track-fds=yes ./nonsense to get information about the file descriptors that were (intentionally) left open. Without changing the logic of the program, insert as many close statements as necessary so that all file descriptors (including 0, 1, and 2) are properly donated back. (In general, you do not have to close file descriptors 0, 1, and 2.)

• The key for this exercise is that you need a c​lose​ s​tatement for every open descriptor identified by ​valgrind​, and you should be careful to never ​close​ ​a previously closed descriptor. Here's an annotated copy of the nonsense.cc file.

int main(int argc, char *argv[]) {
  // fd1 is now open (fd1 = 3, since 0,1,2 already taken)
  int fd1 = open("nonsense.cc", O_RDONLY);

  // fd2 is open and its entry points to the same open file
  // table entry as fd1 (fd2 = 4)
  int fd2 = dup(fd1);

  // now fd1 is closed (fd 3 is now available)
  close(fd1);

  // fd3 is open and its entry points to the same open file
  // table entry as fd2 (fd3 = 3)
  int fd3 = dup(fd2);

  // fd4 is open and its entry points to the same open file
  // table entry as fd3 (and fd2) (fd4 = 5)
  int fd4 = dup(fd3);

  // this returns a new open file descriptor whose
  // entry points to the same open file table entry as
  // fd4, but we never store the return value so it's lost :(
  // we know it returns 6 since that is the next available fd
  dup(fd4);

  // this closes fd4 and makes its entry point to the same
  // open file table entry as STDERR (2)
  dup2(STDERR_FILENO, fd4);

  // this closes STDOUT (1) and makes is entry point to the
  // same open file table entry as STDERR (2) (and fd4)
  dup2(STDERR_FILENO, STDOUT_FILENO);

  // now STDIN (0) is closed (fd 0 is now available)
  close(STDIN_FILENO);

  // this returns a new open file descriptor whos entry
  // points to a new open file table entry for nonsense.cc,
  // but we never store the return value so it's lost :(
  // we know it returns 0 since that is the next available fd
  open("nonsense.cc", O_RDONLY);

  // now STDERR (2) is closed (fd 2 is now available)
  close(STDERR_FILENO);

  // fd2 (4) is still open
  // fd3 (3) is still open
  // fd4 (5) is still open
  // the dup(fd4) return value is still open (6)
  // the open("nonsense.cc", O_RDONLY) return value is still open (0)
  // STDOUT_FILENO (1) is still open
  return 0;
}

Here's a modified version of the program that closes all file descriptors correctly:

int main(int argc, char *argv[]) {
  int fd1 = open("nonsense.cc", O_RDONLY);
  int fd2 = dup(fd1);
  close(fd1);
  int fd3 = dup(fd2);
  int fd4 = dup(fd3);
  int fd5 = dup(fd4);
  dup2(STDERR_FILENO, fd4);
  dup2(STDERR_FILENO, STDOUT_FILENO);
  close(STDIN_FILENO);
  int fd6 = open("nonsense.cc", O_RDONLY);
  close(STDERR_FILENO);

  // Added
  close(fd2);
  close(fd3);
  close(fd4);
  close(fd5);
  close(fd6);
  close(STDOUT_FILENO);
  return 0;
}

Problem 4: Short Answer Questions

Provide clear answers and/or illustrations for each of the short answer questions below. Each of these questions is either drawn from old exams or based on old exam questions. Questions like this will certainly appear on the midterm.

1. The dup system call accepts a valid file descriptor, claims a new, previously unused file descriptor, configures that new descriptor to alias the same file session as the incoming one, and then returns it. Briefly outline what happens to the relevant file entry table and vnode table entries as a result of dup being called. (Read man dup if you'd like, though don't worry about error scenarios).

   • The vnode table entry is left alone, but we claim a new file descriptor and its entry is set to address the same entry in the open file table as the incoming one, and the reference count within that open file table entry would be incremented by one.

2. Now consider the prototype for the link system call (peruse man 2 link). A successful call to link updates the file system so the file identified by oldpath is also identified by newpath. Once link returns, it’s impossible to tell which name was created first. (To be clear, newpath isn’t just a symbolic link, since it could eventually be the only name for the file - it is a "hard link".) In the context of the file system discussed in lecture and/or the file system discussed in Section 2.5 of the secondary textbook, explain how link might be implemented.

   • Resolve o​ldpath​ to its inode number, append new directory entry to sequence of existing directory entries where n​ewpath​ ​resides. Fill in that newpath entry with the last component of ​newpath (e.g. the part after its last "/", meaning just the filename itself, not the whole path),​ and fill in that entry's inumber with the inumber of old path. Finally, increment the reference count within the inode itself to be clear the file has one more name.

3. Explain what happens when you type cd .././../. at the shell prompt. Frame your explanation in terms of the file system described in Section 2.5 of the secondary textbook, and the fact that the inode number of the current working directory is the only relevant global variable maintained by your shell.

   • Using the current working directory's inode number, search the current working directory's payload for .., then set the inumber of the current working directory to the inumber associated with ..; repeat for ., then .., and then .

4. All modern file systems allow symbolic links to exist as shortcuts for longer absolute and relative paths (e.g. search_soln might be a symbolic link for /usr/class/cs110/samples/assign1/search_soln, and tests.txt might be a symbolic link for ./mytests/tests.txt). Explain how the absolute pathname resolution process we discussed in lecture would need to change to resolve absolute pathnames to inode numbers when some of the pathname components might be symbolic links.

   • The absolute pathname resolution process (implemented as p​athname_lookup in assign2) should piecemeal tokenize pathnames as usual. When a component (e.g. tests.txt ​) is identified as a symlink, we must prepend its expansion (meaning the place it symlinks to) to the unprocessed set of tokens. Then, we either continue parsing from the inumber of the symlink's parent for relative symbolic link paths, or restart from inode 1 for absolute paths. Here are two examples to better understand this:
     • Relative Path: let's say we are trying to resolve a path /usr/class/cs110/sym/file.txt, and sym is a relative symbolic link to ../extra/other/. This means we start parsing the path at the root directory, then go to usr, then class, then cs110, and then we get to sym, which is a symbolic link. Because it is a symbolic link, we prepend it to the unprocessed set of tokens for our path, meaning now we must resolve ../extra/other/file.txt. Because it is relative, we keep parsing this path from where we currently are - in cs110. Thus, we go to .. (up a directory, to class), then we go to extra, then other, and then finally to file.txt, where we were trying to get to.
     • Absolute Path: let's say we are trying to resolve a path /usr/class/cs110/sym/file.txt, and sym is an absolute symbolic link to /afs/ir/users. This means we start parsing the path at the root directory, then go to usr, then class, then cs110, and then we get to sym, which is a symbolic link. Because it is a symbolic link, we prepend it to the unprocessed set of tokens for our path, meaning now we must resolve /afs/ir/users/file.txt. Because it is absolute, we must resume parsing this path from the root directory. Thus, we go to inode 1, then we go to afs, then ir, then users, and then finally to file.txt, where we were trying to get to.

Checkoff Questions

1. If the inode were extended to include a space for 7 block numbers instead of 6, and the 7th block number contained a triply indirect block number, what would be maximum file size be now?

   • Maximum file size is (3 * 512) + (2 * 128 * 512) + (128 * 128 * 512) + (128 * 128 * 128 * 512), or 1,082,263,040 bytes (roughly 1GB). (The first term is the direct blocks, the second term is the singly-indirect blocks, the third term is the doubly-indirect block, and the fourth term is the triply indirect block)

2. How many other files reference /usr/class/cs110, and where are most of those references coming from?

   • 17. It's likely that most of the links come via the ".." that's stored as an entry within each subdirectory. If you type ls -lUa /usr/class/cs110, you should see a number of entries in the list, for instance.

3. How many calls to the close function did you need to insert?

   • 5

4. What's the difference between dup and dup2?

   • dup makes a copy at the lowest-available file descriptor index, while dup2 makes a copy at the file descriptor index specified as the second parameter.