OSI Lab7: File System

In lab7, you will implement a simplified Unix-like file system with the following tasks:

initialization of file system state
management of inodes
reads and writes to files

As always, there is not too much code to write (if you organize your code nicely), yet you need to invest time in understanding and internalizing the file system design. All your implementation will be done in library/file/fs_rw.c.

Fetch lab7 from upstream repo

fetch lab7 branch

$ git fetch upstream lab7

<you should see:>
...
 * [new branch]      lab7       -> upstream/lab7

create a local lab7 branch

$ git checkout --no-track -b lab7 upstream/lab7
<you should see:>
Switched to a new branch 'lab7'

confirm you’re on local branch lab7

$ git status
<you should see:>
On branch lab7
nothing to commit, working tree clean

rebase your lab6 to the current branch
```
<you're now on branch lab7>
$ git rebase lab6
```
You need to resolve any conflict caused by the rebase. Read how to resolve conflict here.
push branch lab7 to remote repo origin
```
$ git push -u origin lab7
```

confirm everything runs as expected (note: DISK=SDCARD in Makefile):

$ make && make qemu
...
// everything should work
➜ /home/cs6640 %

Then, try to run fstest:

➜ /home/cs6640 % fstest
// you should run into this error message
[FATAL] rwfs is off; should not be here

Section 1: File system design

A) Disk interface

The disk (an SD card) is abstracted as an array of blocks. The block number is the index in this array. For example, block number 0 is the first block on disk. The size of each block is 512B (BLOCK_SIZE). You can read/write disk by a simple interface:

int block_read(int block_no, char* dst);
int block_write(int block_no, char* src);

The dst is a pointer to memory where you want to store the data from disk (for block_read); the src points to the data you want to write to disk (for block_write). The block_no is the block number (starting from 0) you want to read/write.

The block_read() and block_write() functions rely on your SD card driver implementation from Lab6. To understand how the file system works with your SD card driver, read earth/dev_disk.c, which shows how the file system uses your driver for block-level access.

B) File system layout

Below we introduce how our read-write file system (rwfs) uses the disk blocks, namely its layout on disk:

Block 0: superblock
Block 1: bitmap block
Blocks 2–11: inode array
Blocks 12 and onward: data blocks

                    |<-inode arr->|<-data blocks->|
   +-------+--------+-------------+---------------+
   | super | block  |  |  | ...   |  |  | ...     |
   | block | bitmap |  |  |       |  |  |         |
   +-------+--------+-------------+---------------+
block  0       1     2  3    ...11 12...

Block 0: superblock

The superblock is the first block in the file system, and contains the information needed to find the rest of the file system structures. The following C structure (see library/file/fs.h) defines the superblock:

    struct fs_super {
        m_uint32 magic;       /*==0x6640*/
        m_uint32 disk_size;   /* in blocks */

        /* pad out to an entire block */
        char pad[BLOCK_SIZE - 2 * sizeof(m_uint32)];
    };

The magic should be 0x6640. The rwfs uses the magic to tell if it locates the superblock correctly.

Block 1: bitmap block

This block bitmap indicates which blocks have been used and which are free. One bit represents one block: the first bit represents the first block (block 0), the second bit represents the second block (block 1), and so forth. If a bit is 0, the corresponding block is free; otherwise, the block is used.

The bitmap is cached in a memory buffer. When initializing the rwfs, you will need to read the bitmap block into memory, go through the bitmap, and count the available blocks. You’re given a function to test the bits in bitmap:

  int bit_test((void*)map, int i);

It will return non-zero values if the bit is set and return zero if the bit is 0.

Block 2–11: inode array

The inode array is an array of inodes struct fs_inode (described below). This array is stored in the blocks starting at block 2 to block 11; ten blocks in total. Given this fixed allocation, the maximum number of inodes (i.e., files and directories) is: 10*BLOCK_SIZE/sizeof(struct fs_inode). Using a fixed-size array of inodes starting at a known block simplifies inode lookup, as you will see later.

C) Inode

Our rwfs simplifies the standard Unix inode. Here is our inode’s definition (see also fs.h):

struct fs_inode {
    m_uint32 mode;
    m_uint32 size;     /* file size in bytes */
    m_uint32 pads[3];
    m_uint32 ptrs[NUM_PTRS]; /* direct data block pointer */
    m_uint32 indirect_ptr; /* indirect pointer */
};

Here is a visualized example of an inode with 11 data blocks (so it uses the indirect_ptr):

ERROR: the figure is missing

File metadata: In inode, mode tells fs if this inode is a file or a dir and contains the permission bits. size is the size of a file. ptrs is an array of data block pointers (pointing to data blocks). indirect_ptr points to a block containing block pointers, which then point to data block. All the pointers are block numbers.

Inode numbers: Each inode represents a file or a directory. In egos, files/dirs can be uniquely identified by its inode number. By design, inode numbers are unique in a machine; that means, multiple file systems share the same inode number space with different ranges. For your fs, the inode number starts at 100 (FS_ROOT_INODE) and ends at 100 plus the maximum nmber of inodes.

Note: there is a simple one-to-one mapping between inode numbers and index in inode array (located at block 2–11). Given an inode number X (for example, 101), the inode can be located by X-100 (1) in the inode array.

Section 2: rwfs implementation

You will implement multiple fs functions in the following exercises. All your code will be in library/file/fs_rw.c. The fs is mounted on /home/cs6640/fs.

Before that, ensure your egos runs as expected:

Turn on the rwfs: in Makefile, change the line RWFS=RWFSOFF to RWFS=RWFSON
make and run:
$ make && make qemu
...
// you should see:
[SUCCESS] Enter kernel process GPID_FILE
[FATAL] fs_init is not implemented
This error occurs because the initialization of the rwfs has not been implemented.

Exercise 1 Initialize rwfs

Read data structure fs_t and super_t in library/file/fs.h
Implement fs_init() in library/file/fs_rw.c
After finish, you should be able to boot.
Try cd into the fs and ls:
[CRITICAL] Welcome to the egos-2k+ shell!
...
➜ /home/cs6640 % cd fs
...
➜ /home/cs6640/fs % ls
[FATAL] fs_read is not implemented

The cmd ls fails because it needs to read the contents of the directory (here, /home/cs6640/fs) to list files and folders under it. Next, you will implement reading files.

Exercise 2 Implementing file read

Read data structure inode_t in library/file/fs.h
Implement load_inode(), flush_inode(), and fs_read() in library/file/fs_rw.c
After finish, you should be able to run ls and cat:
➜ /home/cs6640 % (cd fs;ls)
.   ..   file1.txt   dir1
➜ /home/cs6640/fs % cat file1.txt
hello world
Now, try append:
➜ /home/cs6640/fs % append file1.txt xyz
[FATAL] fs_fsize is not implemented

The cmd append will append a given string at the end of the file. It needs to read the size of the file first, and then write the string to the end of the file.

Exercise 3 Implementing file write

Implement fs_fsize() and fs_write() in library/file/fs_rw.c
After finish, try:
➜ /home/cs6640 % (cd fs;cat file1.txt;append file1.txt xyz; cat file1.txt)
...
hello world
...
hello worldxyz
you should see “xyz” is appended to file1.txt
If you successfully implement everything, you should pass all tests in fstest:
$ make && make qemu
...
➜ /home/cs6640 % fstest
[SUCCESS] PASS test1
[SUCCESS] PASS test2
[SUCCESS] PASS test3
[SUCCESS] PASS test4
[SUCCESS] PASS test5
[SUCCESS] PASS test6
[SUCCESS] PASS test7
[SUCCESS] PASS test8
[SUCCESS] PASS test9
[SUCCESS] PASS test10
If you fail some tests, you can see the test case in apps/user/fstest.c.
Note: fstest expects a clean disk. To ensure this, run make before testing fstest; it will regenerate the disk image.

Finally, submit your work

Submitting consists of three steps:

Executing this checklist:
- Fill in ~/osi/egos/slack/lab7.txt.
- Make sure that your code build with no warnings.

Push your code to GitHub:

 $ cd ~/osi/egos/
 $ git commit -am 'submit lab7'
 $ git push origin lab7

 Counting objects: ...
  ....
  To github.com/NEU-CS6640-labs/egos-<YOUR_ID>.git
     c1c38e6..59c0c6e  lab7 -> lab7

Actually commit your lab (with timestamp and git commit id):
1. Get the git commit id of your work. A commit id is a 40-character hexadecimal string. You can obtain the commit id for the last commit by running the command git log -1 --format=oneline.
2. Submit a file named git.txt to Canvas. (there will be an assignment for this lab on Canvas.) The file git.txt contains two lines: the first line is your github repo url; the second line is the git commit id that you want us to grade. Here is an example:
```
 git@github.com:NEU-CS6640-labs/egos-<YOUR_ID>.git
 29dfdadeadbeefe33421f242b5dd8312732fd3c9
```
  Notice: the repo address must start with git@github.com:... (not https://...). You can get your repo address on GitHub repo page by clicking the green “Code” button, then choose “SSH”.
3. Note: You can submit as many times as you want; we will grade the last commit id submitted to Canvas. Also, you can submit any commit id in your pushed git history; again, we will grade the commit id submitted to Canvas.
  Notice: if you submit multiple times, the file name (git.txt) changes to git-N.txt where N is an integer and represents how many times you’ve submitted. We will grade the file with the largest N.

NOTE: Ground truth is what and when you submitted to Canvas.

A non-existent repo address or a non-existent commit id in Canvas means that you have not submitted the lab, regardless of what you have pushed to GitHub—we will not grade it. So, please double check your submitted repo and commit id!
The time of your submission for the purposes of tracking lateness is the timestamp on Canvas, not the timestamp on GitHub.

This completes the lab.