Skip to content

Instantly share code, notes, and snippets.

@stylianipantela

stylianipantela/a4-design.md

Last active April 20, 2026 20:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save stylianipantela/ca776c6b8b097c58fa50 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save stylianipantela/ca776c6b8b097c58fa50 to your computer and use it in GitHub Desktop.
Download ZIP
a4-design.md
Raw
a4-design.md

Code reading questions

###1. What happens (in broad terms) if sys_remove is called on a file that is currently open by another running process? Will a read on the file by the second process succeed? A write? Why or why not? (1 point)

sys_remove removes the inode of the file from the file system. The processes that have a reference to the file will retain that reference and will be able to call read/write on that file and succeed. Processes trying to open the flie after sys_remove will not be allowed to do so. The file is purges from the filesystem after all open file descriptors fo that file have been closed.

###2. Describe the control flow, starting in the system call layer and proceeding through the VFS layer to reach SFS, that occurs for each of the following system calls. You need only trace the names of the functions that are called. Feel free to skip secondary or minor code paths that don't lead into SFS. (1 point)

###3. Now similarly describe the control flow within SFS for each of the same operations. Follow how we get to logic that makes specific updates to on-disk data structures (stopping where buffer-handling code takes over), and feel free to skip code paths that don't do so. (2 points)

####SYS_open

Essentially calls vfs_open.

O_CREAT flag

  • vfs_lookparent
    • getdevice
  • VOP_LOOKPARENT
  • VOP_DECREF
  • VOP_CREAT
  • VOP_DECREF

All flags

  • VOP_EACHOPEN

  • VOP_DECREF

  • vfs_open

  • sfs_create

    • sfs_dinode_load
    • sfs_dinode_map
    • sfs_make_obj
    • sfs_dinode_map (new inode)
    • sfs_dirlink
    • sfs_mark_dirty
    • sfs_dinode_unload

####SYS_write

  • sfs_write
  • sfs_io

####SYS_mkdir vfs_mkdir sfs_mkdir

  • sfs_mkdir
  • sfs_dir_findname
  • sfs_makeobject (checks name is not ., ..)
  • sfs_dinode_map (map directory inode ... to what)?
  • sfs_dir_link gets called with new_directory, "." and".." and they each add a link to the new directory
  • sfs_dinode_mark_dirty (current, new guy)
  • sfs_dinode_unload (current, new guy)

###4. And finally, for mkdir, describe what happens to the block containing the newly allocated directory inode from the time the logic you've described in #3 ends to the time the inode eventually reaches the disk device. Trace the code that handles it, at a similar level of detail: function names and a very brief description of what happens at each point is enough. (2 points)

  • lock vnode
  • resreve buffers
  • sfs_dinode_load
  • sfs_makeobject (checks name is not ., ..)
  • sfs_dinode_map (map directory inode ... to what)?
  • sfs_dir_link newguy to ".", "..", parent mapping to us (3 new links added)
  • sfs_dinode_mark_dirty (current, new guy)
  • sfs_dinode_unload (current, new guy)

###5. Which of the following lock acquisitions are safe? (1 point)

  • lock a vnode, lock the vnode table
  • lock a vnode, lock the freemap
  • lock the physical journal, get (lock) a buffer

We assume that our directories are stored in a tree format (if no hard links), DAG if hard links. lock foo, lock foo/bar - ok lock foo, lock foo/.. - deadlock potential

let foo = '/' in  

  lock(foo)

###6. Name two problems that the current implementation of sfsck can repair, and one that it cannot. (1 point)

  • When two file indirect blocks point to the same object, we reach an unrecoverable state.
  • When a file does not have a .., and no file links to it.

###7. Describe four different types of inconsistent states the filesystem could end up in after a crash, and give a sequence of events that could lead to each. You will probably want to explain in your design doc how you handle these problems. (2 points)

  • We are in the process of creating a new directory. We have created the new inode but not removed the link of the parent to the old inode.
  • We could have deleted an inode but not freed the bitmap yet. The system might crash and some users might be able to obtain a reference to the inode.
  • We have created a new directory but not linked to ., .. and our parents.
  • We are in the middle of a truncate and have not freed all the corresponding blocks.

Design Document

###1. What will your log records look like?

struct record {
	unsigned transaction_id;
    int type;
    union {
      struct b_record {
      	daddr_t id;
        bool freed;
        bool is_dir;
      }
      
      struct inode_link_dir {
        uint32_t parent_ino;
        uint32_t child_ino;
        char name[100];
        int slot;
      	uint16_t child_linkcount;
      	uint16_t parent_linkcount;
      }
      
      struct inode_unlink_dir {
      	uint32_t parent_ino;
        int slot;
      }
      struct inode_makeobj {
      	bool is_dir;
        unit32_t ino;
      }
      struct begin{
      	unsigned transaction_id;
      }
      struct commit{
      	unsigned transaction_id;
      }
     
    } r;
}

We have to following records corresponding to these sfs operations:

Transaction Begin/Commit Records

  • sfs_mkdir

    • begin t
    • sfs_balloc(new inode)
    • sfs_makeobj(TYPE)
    • sfs_dir_link(newguy, “.”)
    • sfs_dir_link(newguy, “..”)
    • sfs_dir_link(parent, newguy)
    • commit t

  • sfs_link (src, tgt) ->

    • begin t
    • sfs_dir_link parent, tgt, src_ino, slot
    • commit t

  • sfs_rename (old, new) ->

    • begin t
    • sfs_create(new)
    • sfs_remove(old)
    • commit t

  • sfs_truncate (f, sz) -> (free blocks)

    • begin t
    • for idx in new_sz...old_sz
      • sfs_bfree blk
      • sfs_blockobj_set f, idx, 0
    • commit t

  • sfs_truncate (f, sz) -> (add blocks)

    • begin t
    • for idx in old_sz...new_sz
      • sfs_balloc blk
      • sfs_blockobj_set f, idx, blk
    • commit t

  • sfs_creat(name) ->

    • begin t
    • sfs_balloc f
    • sfs_makeobj FILE, f
    • sfs_dir_link parent, name, f, slot
    • commit t

Individual Records

  • sfs_blockobj_set(din, block_idx, block_id), block_id == 0 => NULL

  • sfs_writeblock(daddr_t) (only record if it's user data)

    • daddr_t

  • sfs_makeobj()

    • file or directory after sfs_loadvnode succeeds

  • sfs_dir_link

  • sfs_dir_unlink

    • ino of parent
    • child ino
    • child name
    • slot

  • sfs_balloc

  • sfs_bfree

    • disk block id (daddr_t)
    • bool dir or file

###2. What will their corresponding recovery routines look like? We have enough information to call the functions from above in the right order. If a transaction got aborted we call the reverse the functions.

###3. What locking will you need?

Transaction Table Lock We will have a big lock on the transaction table. Every time we want to add an LSN to a transaction we grab the transaction table lock.

Buffer Locks

  1. io_lock

  2. metadata_lock

  3. buffer_lock

In order to flush the buffer we need to grab the io_lock In order to read metadata (active LSNs) we need to grab the metadata lock In order to destroy the buffer we need the buffer lock, as well as the metadata_lock and the io_lock

###4. What is the overall control flow of your recovery process? What will it have to do?

We read the journal sequentially and apply the changes. There is no need to undo anything.

###5. How will you know that recovery is working?

We will write a fake journal and reboot and see if our changes are registered in the system.

###6. What other problems do you anticipate?

###7. What is your implementation timeline? Who will get what done by when?

Sunday, April 19th => Printing functions

Monday, April 20th => Define Journal Structs/ Print functions

Tuesday, April 21st => Recovery/ mount

Wednesday, April 22nd => Recovery/ mount

Thursday, April 23rd => Recovery/ mount

Friday, April 24th => Insert code to write the journal

Saturday, April 25th => Insert code to write the journal

Sunday, April 26th => Insert code to write the journal

Monday April 27th => Checkpoints

Tuesday , April 28th => Test

Wednesday, April 29th => Test

Thursday, April 30th => Test

Friday, May 1st => We are done? Whaaat? :D

Peer Review Questions

##1. The Log/Journal

struct journal {
  unsigned log_head;
  unsigned log_checkpoint;
  unsigned log_tail;
}

  • Will you use an UNDO log, a REDO log, or a REDO/UNDO?

    • We are doing REDO/UNDO log. We feel more information does not hurt and its easier for debugging.

  • How will you enforce write-ahead-logging?

    • All we have to do is make sure we write a journal entry before taking the action. At every SFS function we will be writing the journal entry upon entering the function.
    • Make sure every buffer is associated with its LSNs. Make sure before it is flushed to disk, the corresponding journal is flushed to disk.
    • A buffer needs the newest LSN.
    • sfs_writeblock (to flush anything to disk, we need to put a call to flush your journal to disk in there, which is sfs_jphys_flush, sfs_jphys_flushall. One of them lets you flush up to a point, another makes you flush everything. How do you decide between the two? If you flush things all the time, you add a lot of padding. So, maybe flush part of the journal only.

  • What do you need to do to checkpoint? How often will you take them? (A checkpoint is way of ensuring that all the updates corresponding to some set of log records have been propagated to disk; checkpoints let you bound how much of the log you need to use at recovery time. Constructing a proper checkpoint will invoke calls on the container that reclaim space compatible with your checkpoint.

    • When we are running at less than 50% journal space, we enforce a checkpoint. We will call the checkpoint function periodically from hardclock.
    • It is importang that we do not deal with buffer flushing at checkpoint because we want to be able to return fast.
    • We trim the log record up to MIN (MIN LSN at an uncommitted transaction, MIN LSN at a live buffer) - 1.
    • If there are no live transactions or buffers, we just peek at the next LSN and trim up to that.
    • We maintain a transaction table and iterate through it. We maintain a list of minimum LSNs in that table.
    • We also iterate through all our buffer metadata to find minimum LSN associated with them.
    • Everything that gets trimmed belongs to a committed txn and has been flushed.
    • On checkpoint we allow other transactions to happen. We do not need to worry about race conditions because on checkpoint, we lock the transaction table and obtain the minimum LSN in that. If another record gets created it is going to have a higher LSN.
    • sfs_jphys_trim
    • call sfs_jphys_peeknextlsn before scanning the buffers and transactions unless we have a global lock for this,
    • callback, locks the transaction table

##2. The Recovery Process

  • What is your algorithm that must be executed after a failure to restore the file system to a consistent state? More specifically, how many times and in what direction(s) do you need to traverse the log?

    • After a failure we need go through the journal sequentially. If a transaction got committed we need to redo all the journal records from the very beginning. If a transaction did not abort or commit we need to undo the logged records. If a transaction got aborted we do not need to do anything.
    • Iterate over the disk structure to reclaim the inodes.

  • What assumptions can your recovery process make?

    • no torn writes (the disk is reasonable)
    • recovery can be replayed inifinite times as long as we are implementing undo/redo logs

  • What guarantees will your recovery process make? (That is, what can you say about the state of the system after recovery runs.)

    • All the data at the time of the last checkpoint will be accesible and available.

##3. Specific Log Records

  • For each file system operation, what are the lower-level micro operations that comprise it (note: these are the operations for which you will write log records and recovery routines).

    • We will record changes to the free bitmap as well as changes to the inodes.

  • Where can you make calls to logging routines?

  • How will you propagate information about the log to the locations at which you need to write log records?

    • We will add another parameter to the sfs functions that will have to write to the journal. That parameter will be a transaction struct.

  • What recovery actions are needed for each log record? Have you specified enough information in your log records to facilitate what you need during recovery?

    • Yes, check in the previous section.

##4. Transactions

  • How are you keeping track of the set of log records that comprise a file system operation?

    • A transaction is a file system operation. We assign and LSN at every point of the transaction. We maintain a transaction dynamic array that maintains the following records:
    
struct lock *transaction_table_lk;


struct transaction {
	bool committed;
    struct unsigned **lsn;
    unsigned id;
}

  • What happens if you crash after you've written some, but not all of these operations?

We will undo them on recovery.

  • How does SFS's synchronization and the log container's synchronization interact with your transaction implementation?

    Every time we flush a buffer, we update the live LSNs of the buffer. We keep track of those in the buffer's metadata. Every time we write a commit record we edit the transaction table for the specified transaction.

5. Testing

  • How will you test your system?

We will run a variety of tests.

Unit Tests will be implemented across all sfs_fs and sys_vnops functions that use the journal.

We wanted to guarantee that the journal is always written before the data operation it describes. We will run a given operation many times, say 100 times, and constantly stop the world at random points assuring that the data is never present without the associated journal entry.

We also wanted to guarantee that the filesystem is in a consistent state after each (successful or unseccesssful) system call. After each of the following system calls, we will run sfsck and make sure all links, reference counts, and free blocks are consistent with the file systems. We will run the badcall test suite and our own collection of individual system calls.

We will integration level tests that assert consistency of the file system after a crash and recovery. We will perform a set of redoable operations (create, remove, mkdir, rmdir, rename, link, truncate) and assert that after recovery, the filesystem reflects al; these operations.

Finally, we will maintain a list of regession tests for each bug we run into.

  • Can you outline a testing philosophy or strategy that will let you approach testing in a methodical fashion?

We want to test our filesystem at many levels.

We have unit tests to make sure each indivudal filesystem operation is correct. We use integration tests to make sure that the recovery program's behavior is consistent with our sfs method implementations. We also maintain a regression test suite to more quickly indentify bugs that tend to occur in our implmentation.

We will also make sure to implement some debug helper functions.

  • We will implement a print journal function that goes through the journal and prints the records sequentially.
  • We will write a function that tries to display the state of the disk, similar to how our coremapprint function shows the state of virtual memory.
void print_record(void) {


}

void print_journal(void) {
	for r in records:
    	print record

}
  • Can you perform unit testing? How?

Yes, first see our comments in the first questions about our unit testing strategy. We plan to create system tests for every high level sfs functions and functions that we modify. We assert our tests have apssed by asserting the disk is valid with sfsck and by checking the state of the disk reflects the test we ran.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment