Assignment 3
File System
Operating Systems 2021
Assignment
Implement your own driver for a (simple) file system: SFS
Implemented as a FUSE driver (i.e., as user-space program).
Support directories, read/writing files, etc.
SFS
Extremely simple, FAT16-like, file system
Block lists recorded in file allocation table called Block Table
Block size of 512 byte
4 KB 32 KB 8 MB
M
a
g Rootdir Block table Data blocks
i
c
SFS Directories
Root directory of 64 entries, subdirectories 16 entries
Directory entry is 64 bytes
Subdirectories consist of two consecutive data blocks
4 2 58 struct sfs_entry {
char filename[58];
d size block filename blockidx_t first_block;
uint32_t size;
1 bit 28 bit } __attribute__((__packed__));
SFS Block Table
Directory entry refers to first blockidx of a file/directory
Block table describes blockidx’es of next blocks
Special values:
direntry.first_block = 4
0xffff: Block unused (free)
0xfffe: End of chain 0xffff
0xffff
6
0xffff
2
Update from last year (2020): free blocks are now 0xffff, and blockidx 0 0xffff
corresponds to the first block (not 1) 0xfffe
0xffff
...
Disk I/O
We use an image on the host file system, instead of an actual disk partition
Interface defined in diskio.h:
void disk_read(void *buf, size_t size, off_t offset);
void disk_write(const void *buf, size_t size, off_t offset);
Arbitrary sizes/offsets allowed (no need to read/write in aligned full disk blocks)
You are now allowed to cache any data in memory (i.e., must read from disk for
every operation).
Getting started
More details on SFS and framework in PDF/readme
Check out sfs.h for all required data types and constant values
Play around with mkfs.sfs, fsck.sfs and FUSE
Getting started
Prerecorded live demo: asg3.fs-demo.mkv on Canvas
You may use/copy any code
shown in the video
Make sure to switch to 1080p
quality when watching on canvas
Timestamps:
00:00 framework tool overview
08:05 framework code overview
18:24 readdir implementation
29:11 getattr implementation
Getting started - next steps
Follow along with included tests (make check):
- Reading files (from rootdir)
- Support subdirectories
- Creating/removing directories and files
- Modifying files
Getting started - how to traverse paths?
For example, a getattr of /foo/bar/baz:
root blocktable
SFS_ROOTDIR_OFF
foo
strtok(mypath, “/”)
Getting started - how to traverse paths?
For example, a getattr of /foo/bar/baz:
root blocktable
readme .filename=foo
SFS_ROOTDIR_OFF
foo .size=0x80000000
.first_block=7
spam
foo
strtok(mypath, “/”)
Getting started - how to traverse paths?
For example, a getattr of /foo/bar/baz:
root blocktable
.filename=bar
readme .filename=foo bar .size=0x80000000
SFS_ROOTDIR_OFF
foo .size=0x80000000 eggs .first_block=17
.first_block=7
spam
foo bar
strtok(mypath, “/”)
Getting started - how to traverse paths?
For example, a getattr of /foo/bar/baz:
root blocktable
.filename=bar
readme .filename=foo bar .size=0x80000000
SFS_ROOTDIR_OFF .filename=baz
foo .size=0x80000000 eggs .first_block=17
.first_block=7 baz .size=700
.first_block=13
spam
foo bar baz
strtok(mypath, “/”)
Getting started - how to read file?
For example, a read of /foo/bar/baz, size=700:
root blocktable
ffff
ffff
ffff
ffff
fffe Return buffer
ffff .filename=baz
ffff .size=700
ffff
ffff .first_block=13 512 bytes 188 bytes
ffff
ffff
ffff 700 bytes
ffff
4 Get direntry same
ffff
way as for getattr
...
(make helper func!)
Getting started - how to read file?
For example, a read of /foo/bar/baz, size=700:
root blocktable
ffff
ffff
ffff
ffff
fffe Return buffer
ffff .filename=baz
ffff .size=700
ffff
ffff .first_block=13 512 bytes 188 bytes
ffff
ffff
ffff 700 bytes
ffff
4
ffff
...
Submission
Deadline December 15th 23:59 CET. This is a strict deadline - no extensions!
Submissions on canvas, individual assignment (no teams).
Automatic grading on codegrade (see earlier warnings on tentative grade) -
submit early & often!
As always: do not share your solution, or copy from someone else or the internet.
Getting help: lab sessions, discussion board, mailing list
(do not contact us directly via email/canvas messages).
