File System API (6 points)

Consider the following commands sent to a UNIX-based system:

Line  1:  echo  ’hello’  >>  file1

Line  2:  ln  file1  file2

Line  3:  cat  file2

Line 4: rm  file1

Line  5:  cat  file2

Line  6:  echo  ’more’  >>  file1

Line  7:  cat  file2

Ignore any problems with whitespace or capitalization.  Assume  ; shows text separated across multiple lines in the shown output.

1. What will be the output from Line 3?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

2. What will be the output from Line 5?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

3. What will be the output from Line 7?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

Assume the ln command in Line 2 is changed to ln  -s.

4. What will be the output from Line 3?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

5. What will be the output from Line 5?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

6. What will be the output from Line 7?

A.  hello

B.  more

C.  more ; hello

D.  hello ; more

E.  ERROR: No such file or directory

File System Images (16 points)

These questions ask you to understand how different file system operations lead to different file system data structures being modified on disk. You do not need to consider journaling or crash consistency in these questions. This part is

based on the available homework simulations.

This file system supports 7 operations:

|  mkdir() - creates a new directory

|  creat() - creates a new (empty) file

| open(), write(), close() - appends a block to a file

|  link() - creates a hard link to a file

|  unlink() - unlinks a file (removing it if linkcnt==0)

The state of the file system is indicated by the contents of four different data structures:

|  inode bitmap - indicates which inodes are allocated (not shown, because not needed for questions) |  inodes - table of inodes and their contents

|  data bitmap - indicates which data blocks are allocated (not shown)

|  data - indicates contents of data blocks

The inodes each have three fields: the first field indicates the type of file (f for a regular file, d for a directory); the second indicates which data block belongs to a file (here, files can only be empty, which have the address of the data block set to -1, or one block in size, which would have a non-negative address); the third shows the reference count for the file or directory.  For example, the following inode is a regular file, which is empty (address field set to -1), and has just one link in the file system:  [f a:-1 r:1].  If the same file had a block allocated to it (say block 10), it would be shown as follows:  [f a:10 r:1].  If someone then created a hard link to this inode, it would then become [f a:10 r:2].

Data blocks can either retain user data or directory data. If filled with directory data, each entry within the block is of the form (name, inumber), where “name” is the name of the file or directory, and “inumber” is the inode number of the file.  Thus, an empty root directory looks like this, assuming the root inode is 0:  [(.,0) (..,0)].  If we add a single file “f” to the root directory, which has been allocated inode number 1, the root directory contents would then become:  [(.,0) (..,0) (f,1)]

If a data block contains user data, it is shown as just a single character within the block, e.g.,  “h” .  If it is empty and unallocated, just a pair of empty brackets ([]) are shown.

Empty inodes and empty data blocks may not all be shown.

An entire file system is thus depicted as follows:

inodes

data

[d  a:0 r:6]  [f  a:1 r:1]  [f  a:-1 r:1]  [d  a:2 r:2]  []  . . .

[( . ,0)  ( . . ,0)  (y,1)  (z,2)  (f,3)]  [u]  [( . ,3)  ( . . ,0)]  []  . . .

This file system has eight inodes and eight data blocks.  The root directory contains three entries (other than “ .” and “ ..”), to “y”, “z”, and “f” .  By looking up inode 1, we can see that “y” is a regular file (type f), with a single data block allocated to it (address 1).  In that data block 1 are the contents of the file “y”:  namely,  “u” .  We can also see that “z” is an empty regular file (address field set to -1), and that “f” (inode number 3) is a directory, also empty. You can also see from the bitmaps that the first four inode bitmap entries are marked as allocated, as well as the first three data bitmap entries.

For the following questions, begin by assuming you have a file system image in the following state:

inodes      [d  a:0 r:5]  [d  a:1 r:2]  [f  a:-1 r:1]  [f  a:-1 r:1]  []  []  []  []       data          [( . ,0)  ( . . ,0)  (g,1)  (q,2)  (u,3)]  [( . ,1)  ( . . ,0)]  []  []  []  []  []  []

7. What is /g?

A.  File

B.  Directory

C.  Does not exist in this file system image

D.  Not enough information to determine

E.  None of the above

8. What is /q?

A.  File

B.  Directory

C.  Does not exist in this file system image

D.  Not enough information to determine

E.  None of the above

9. What is /g/d?

A.  File

B.  Directory

C.  Does not exist in this file system image

D.  Not enough information to determine

E.  None of the above

Assume you now execute the command link(‘‘/u’’,  ‘‘/x’’);

10. What could be the resulting state of the file system image for inodes?

A.  No change (includes if the operation was invalid)

B.  [d  a:0 r:6]  [d  a:1 r:2]  [f  a:-1 r:2]  [f  a:-1 r:1]  []  []  []  []

C.  [d  a:0 r:6]  [d  a:1 r:2]  [f  a:-1 r:1]  [f  a:-1 r:2]  []  []  []  []

D.  [d  a:0 r:5]  [d  a:1 r:2]  [f  a:-1 r:1]  [f  a:-1 r:1]  [f  a:-1 r:1]  []  []  []

E.  None of the above

11. What could be the resulting state of the file system image for data blocks?

A.  No change (includes if the operation was invalid)

B.  [( . ,0)  ( . . ,0)  (g,1)  (q,2)  (u,3)  (x,3)]  [( . ,1)  ( . . ,0)]  []  []  []  []  []  []

C.  [( . ,0)  ( . . ,0)  (g,1)  (q,2)  (u,3)  (x,4)]  [( . ,1)  ( . . ,0)]  []  []  []  []  []  []

D.  [( . ,0)  ( . . ,0)  (g,1)  (q,2)  (u,3)]  [( . ,1)  ( . . ,0)  (x,4)]  []  []  []  []  []  []

E.  None of the above

Now, assume you have a different file system image:

inodes

data

[d  a:0 r:4]  [d  a:1 r:3]  [f  a:-1 r:2]  []  []  []  []  []

[( . ,0)  ( . . ,0)  (e,2)  (o,1)]  [( . ,1)  ( . . ,0)  (s,2)]  []  []  []  []  []  []

12.  For this file system image, which two pathnames can be used to access the same file?

A.  /o and /s

B.  /o and /e/s

C.  /e and /o

D.  /e and /o/s

E.  None of the above OR more than one of the above

Assume you now execute the following commands:

fd=open(‘‘/e’’,  O_WRONLY|O_APPEND); write(fd, buf, BLOCKSIZE);  close(fd);

13. What could be the resulting state of the file system image for inodes?

A.  No change (includes if the operation was invalid)

B.  [d  a:0 r:4]  [d  a:1 r:3]  [f  a:-1 r:3]  []  []  []  []  []

C.  [d  a:0 r:4]  [d  a:1 r:3]  [f  a:1 r:2]  []  []  []  []  []

D.  [d  a:0 r:4]  [d  a:1 r:3]  [f  a:2 r:2]  []  []  []  []  []

E.  None of the above OR more than one of the above

14. What could be the resulting state of the file system image for data blocks?

A.  No change (includes if the operation was invalid)

B.  [( . ,0)  ( . . ,0)  (e,2)  (o,1)]  [( . ,1)  ( . . ,0)  (s,2)  (e,1)]  []  []  []  []  []  []

C.  [( . ,0)  ( . . ,0)  (e,2)  (o,1)]  [( . ,1)  ( . . ,0)  (s,2)]  [a]  []  []  []  []  []

D.  [( . ,0)  ( . . ,0)  (e,2)  (o,1)]  [( . ,1)  ( . . ,0)  (s,2)]  [( . ,1)  ( . . ,0)]  []  []  []  []  []

E.  None of the above OR more than one of the above

File System Data Structures (16 points)

This question asks you about the read and write operations that a file system like FFS must send to disk to update its meta-data and data blocks. You should make the following assumptions:

|  Disk blocks are 4 KB

|  Nothing begins in the file system buffer cache

|  All modified data must be written to the disk (and not just the buffer cache)

|  All directory data always fits within 4 KB

|  No needed inode is ever in the same block as another needed inode

|  No timestamps are updated

|  The operations cause no errors (e.g., specified directories exist, files to be created do not already exist) |  There is no journaling or other mechanisms for crash consistency

Assume that you would like to create a new  (empty) file bar with the pathname /dir/dir2/bar.  Think about the read and write operations that will be required; it may be useful to write them all out to answer the following questions.

15.  How many disk blocks will be read to create the file?

A.  5     B.  6     C.  7     D.  8     E.  None of the above

16.  How many disk blocks will be written to create the file?

A.  3     B. 4     C.  5     D.  6     E.  None of the above

How must the disk blocks containing each of the following file system data structures be accessed to create the file? Possible options are the block A) must only be read, B) must only be written, C) must be both read and written,

D) does not need to be accessed. There is no E) option.

17.  The block containing the data for dir must be:

A. read only     B. written only     C. read and written     D.  nothing

18.  The block containing the inode for dir2 must be:

A. read only     B. written only     C. read and written     D.  nothing

19.  The block containing the data for dir2 must be:

A. read only     B. written only     C. read and written     D.  nothing

20.  The block containing the inode for bar must be:

A. read only     B. written only     C. read and written     D.  nothing

21.  The block containing the data for bar must be:

A. read only     B. written only     C. read and written     D.  nothing

22.  A block containing a portion of the inode bitmap must be:

A. read only     B. written only     C. read and written     D.  nothing

23.  A block containing a portion of the data bitmap must be:

A. read only     B. written only     C. read and written     D.  nothing

Assume that you would now like to open an existing file foo with the pathname /dir/dir2/foo; to open the file, you must read the file’s inode into memory.  Again, assume nothing begins cached in the file system buffer cache. Think about the read and write operations that will be required; it may be useful to write them all out to answer the following questions.

24.  How many disk blocks will be read to open the file?

A. 4     B.  5     C.  6     D.  7     E.  None of the above

25.  How many disk blocks will be written to open the file?

A.  1     B.  2     C.  3     D. 4     E.  None of the above

How must the disk blocks containing each of the following file system data structures be accessed to open the file?

26.  The block containing the inode for dir2 must be:

A. read only     B. written only     C. read and written     D.  nothing

27.  The block containing the data for dir2 must be:

A. read only     B. written only     C. read and written     D.  nothing

28.  The block containing the inode for bar must be:

A. read only     B. written only     C. read and written     D.  nothing

29.  The block containing the data for bar must be:

A. read only     B. written only     C. read and written     D.  nothing

30.  A block containing a portion of the inode bitmap must be:

A. read only     B. written only     C. read and written     D.  nothing

31.  A block containing a portion of the data bitmap must be:

A. read only     B. written only     C. read and written     D.  nothing

Data Journaling with Barriers (10 points)

You are using a journaling file system  (such as Linux ext3) in full data-journaling mode without the checksum performance optimization (i.e., the transaction commit block does NOT contain a checksum over the blocks of that transaction).

As described in class, each transaction is composed of a single transaction header block  (also called transaction descriptor block), multiple meta-data and data blocks in the transaction, and a single transaction commit block; there is also an in-place checkpoint region on the disk.

As you know, some of the transaction blocks and some blocks to the checkpoint region can be written out concurrently to disk.  Other blocks cannot be written concurrently:  to guarantee crash consistency, the file system must ensure that particular blocks (e.g., A), are persisted to disk before others (e.g., B). Thus, the file system flushes A to disk and sends a barrier operation to the disk before sending B.

What crash consistency errors could occur if the journaling file system does not send a barrier to the disk between the following types of blocks for A and B? Note that a barrier may not be needed between A and B. In each question, assume all other barriers are inserted correctly;  that is,  each question is independent.   Ignore any performance problems.

32.  A = Transaction header block; B = First transaction meta-data/data block

A.  No correctness problem occurs

B.  Could replay garbage located in transaction to checkpoint region

C.  Could partially overwrite in-place checkpoint data and not replay transaction

D.  Other correctness problem

33.  A = First meta-data/data block in transaction; B = Other meta-data/data blocks in transaction

A.  No correctness problem occurs

B.  Could replay garbage located in transaction to checkpoint region

C.  Could partially overwrite in-place checkpoint data and not replay transaction

D.  Other correctness problem

34.  A = Last meta-data/data block in transaction; B = Transaction commit block

A.  No correctness problem occurs

B.  Could replay garbage located in transaction to checkpoint region

C.  Could partially overwrite in-place checkpoint data and not replay transaction

D.  Other correctness problem

35.  A = Transaction commit block; B = Blocks to in-place checkpoint region

A.  No correctness problem occurs

B.  Could replay garbage located in transaction to checkpoint region

C.  Could partially overwrite in-place checkpoint data and not replay transaction

D.  Other correctness problem

36.  A = Blocks to in-place checkpoint region; B = Transaction commit block

A.  No correctness problem occurs

B.  Could replay garbage located in transaction to checkpoint region

C.  Could overwrite in-place checkpoint data and not replay transaction

D.  Other correctness problem

Distributed File Systems (20 points)

The next questions explore the cache consistency behavior of AFS and NFS.

The next two pages show two identical traces; you should use one trace for answering how NFS behaves and one trace for answering how AFS behaves.

Each trace contains two clients that each generate file opens, reads, writes, and closes on a single file. The 2 columns show the actions being taken on each of the two clients, c0 and c1.  Time increases downwards in seconds.  Assume the time required to send/receive messages over the network and for the server to respond is negligible.

Opening a file returns a file descriptor which would be used for each call to read, write, and close, but is not shown because only a single file is involved.  The file contains multiple blocks.  The arguments to read and write show the block number of the file that is being accessed. Note that it does not matter what data is actually read or written.

For each protocol, assume that the server and clients have sufficient memory and disk space such that no operations are performed unless required by the protocol.  NFS Hint:  Every interaction with the server returns the current attributes for the requested file.