Section 1 Solutions

Sections Thu Oct 06 to Fri Oct 07

This section handout was designed by Jerry Cain. Compiled by Parthiv Krishna.

Solutions

1) Direct, Singly Indirect, and Doubly Indirect Block Numbers

  • 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.

    • (Diagram created by Parthiv Krishna) 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.

2) valgrind and orphaned file descriptors

The key for this exercise is that you need a close statement 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 open-fds.cc file.

// fd1 = 3, since 0,1,2 already taken (now 0,1,2,3 taken)
int fd1 = open("open-fds.cc", O_RDONLY);

// STDIN (0) is closed (now 1,2,3 taken)
close(STDIN_FILENO);

// fd2 = 0, since 0 is available (now 0,1,2,3 taken)
int fd2 = open("open-fds.cc", O_RDONLY);

// fd3 = 4, since 0,1,2,3 already taken (now 0,1,2,3,4 taken)
int fd3 = open("Makefile", O_RDONLY);

// 0 is closed (now 1,2,3,4 taken)
close(fd2);

// 3 is closed (now 1,2,4 taken)
close(fd1);

// fd1 = 0, since 0 available (now 0,1,2,4 taken)
fd1 = open("Makefile", O_RDONLY);

// STDOUT (1) is closed (now 0,2,4 taken)
close(STDOUT_FILENO);

// fd4 = 1, since 1 is avaiable (now 0,1,2,4 taken)
int fd4 = open("open-fds.cc", O_RDONLY);

// fd1 (0) is still open
// fd4 (1) is still open
// STDERR_FILENO (2) is still open
// fd3 (4) is still open
return fd3 + fd4;

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

int fd1 = open("open-fds.cc", O_RDONLY);
close(STDIN_FILENO);
int fd2 = open("open-fds.cc", O_RDONLY);
int fd3 = open("Makefile", O_RDONLY);
close(fd2);
close(fd1);
fd1 = open("Makefile", O_RDONLY);
close(STDOUT_FILENO);
int fd4 = open("open-fds.cc", O_RDONLY);

// Added
close(fd1);
close(fd4);
close(STDERR_FILENO);
close(fd3);

return fd3 + fd4;

3) Unix V6 Filesystem

  • Consider the Unix V6 filesystem, which uses 512-byte blocks and 32-byte inodes. Which sector should we read in order to get inode 256? If that sector is an array of inodes, which index should we go to in order to get inode 256? What about inode 345?

    • Keep in mind that inode numbers start from 1, not 0!
    • 512B / 32B = 16 inodes/block
    • Inode 256 is at block 2 + (256 - 1) / 16 = 17. It is at index (256 - 1) % 16 = 15.
    • Inode 345 is at block 2 + (345 - 1) / 16 = 23. It is at index (345 - 1) % 16 = 8.

  • Unlike the Unix V6 filesystem we learned about in class, the ext2/3/4 family of filesystems (commonly used on Linux) use variable-length directory entries. What is the benefit to designing directory entries this way? What are some drawbacks? (Consider what happens when deleting files.)

    • Benefit: you can store long filenames without wasting lots of space if some names are long but most are short
    • Drawback: Iterating over directory entries is more complicated. It’s no longer a simple array of directory entries, and we can no longer have random access to dirents; instead, we need to read each entry one by one, since each entry tells you where the next one is (via the name_length)
    • Drawback: Deleting a directory entry leaves a "hole” of a particular size based on the name length, and if you want to create a new directory entry with a longer name, you won’t be able to put it in that "hole”. There is more complexity in choosing where to put directory entries, since you need to find a suitable spot for the directory entries.

  • Explain what happens when you type cd .././../. at the shell prompt. Frame your explanation in terms of the Unix V6 filesystem. Assume that the inode number of the current working directory is the only relevant global variable maintained by your terminal.

    • 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 .

Checkoff Questions

  1. [Problem 1] If the inode were extended to include a space for 7 block numbers instead of 6, and the 7th block number was 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. [Problem 2] How many calls to the close function did you need to insert?

    • 4

  3. [Problem 3.3] Explain what happens when you type cd .././../. at the shell prompt. Frame your explanation in terms of the Unix V6 filesystem. Assume that the inode number of the current working directory is the only relevant global variable maintained by your terminal.

    • 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 .