In this assignment, you will be implementing the brittle file system. BFS is designed to work with the HAWX kernel where the filesystem will run as a user space daemon. We also need to have a utility which will allow us to create and populate an initial disk image which will be used by our system. So really, this system will see two types of usage:
- In a linux utility used to build the disk image.
- In the user space daemon, running under HAWX.
To provide this level of portability, we are going to implement the file system as a library, which will work in both scenarios. There is a small abstraction present in that the library will interface with the disk exclusively through two functions, and these functions will be supplied by the program using the library. We’ll discuss these abstractions in the implementation portion of this assignment. First, we will discuss the layout and functioning of the Brittle File System.
The Brittle File System (BFS) is a simplified version of the FAT filesystem. It deviates in several significant ways in order to make it easier to create and manage. This comes at the cost of reliability, but since these disk images will only exist for short periods of time, that’s ok. We want to learn how to put a file system together, and this one is a rather simple example.
The basic unit of measurement in BFS is the block. A block is 1024 bytes long, and each block can be allocated or free. The overall concept is that we manage blocks via a block chain table (BCT), which creates a linked list of blocks which comprise the files and directory of the system. Note that in BFS, the “directory” is singular, there is only one. This is what’s called a flat file system. It would be possible to add subdirectories, but then that would only make the assignment longer. Feel free to add that extension if you like.
The first block of the BFS file system (block 0) contains the super block, which contains information about the file system. The block chain table begins at block 1, and is large enough to contain one 4-byte entry per volume block. The first block of the directory dblock follows the block chain table, and then the data blocks begin at dblock + 1. Data blocks are allocated as needed, forming chains of file which span the disk in block chain order. Subsequent blocks of the directory also reside in this area.
The super block contains a magic number to verify the system and then 3 pieces of meta data. The fields of the super block are:
- magic (4 bytes)
0xBF5BF52A- This is used to verify that the volume is, in fact, a BFS file system. - size (4 bytes) - The volume size in blocks
- used (4 bytes) - The number of blocks that have been allocated
- dblock (4 bytes) - The block which contains the first block of the directory.
The rest of the super block is left blank. Or at least, it does not matter what is placed in the rest of the block.
The block chain table (BCT) is the heart of the brittle file system. Each block on disk has a corresponding 32-bit (4 byte) entry on this table. All blocks on the disk, include those used by the super block and BCT, are accounted for by these entries. The entry numbers have the following meanings:
#define BFS_EOC 0xFFFFFFFF- End of chain. This is the indicates that this block is the end of a block chain.#define BFS_FREE 0x00000000- Free Block. This indicates that this block is available for use.- next - Any value other than those mentions above is the number of the next block in the chain.
The BCT shown above is the beginning of a block chain table right after formatting and with the addition of a single file. We have the super block, which is a 1 block chain, indicated by an immediate EOC. Then we have blocks 1 - 9 forming an 9 block BCT. This means the
dblockis located at block 10, and the data blocks begin at block 11. We also have a 2-block file which begins at 11 and has a second block at 15. If you can understand how to read this table and how you can build it, then you can build the file system.
A BFS directory block contains a 32 entries which are 32 bytes in size. (32 x 32 = 1,024, so it all works out.) The entries contain the following information in this order:
fblock(4 bytes) — The first block of the filesize(4 bytes) — The size of the file in bytes.name(23 bytes) — A null-terminated file name string. (File names can be a maximum of 22 bytes long, and yes you can use spaces.)inuse(1 byte) — 0=free, 1=used
Your objective in this assignment is to implement the brittle file system. This assignment is a bit different as you will be working in your native Linux environment. The files to observe in this assignment are:
fs/fs.h- Definitions of the file system functions.fs/fstypes- Types and constants for file system interaction.fs/fs.c- The implementation file of the file system. All of your work will be done here.utils/mkdisk.c- A small utility which makes a binary disk image for a specified number of blocks.utils/bfs.c- A utility which allows you to work with a disk image to create and manipulate a brittle file system.
You should read through all of the files in the fs directory, and definitely have a look at the utils/bfs.c as well because this will show you how the file system is intended to be used. utils/mkdisk is pretty simple, it just writes a bunch of binary zeros to a file, but feel free to have a look in there as well.
This library will be the only implementation of the brittle file system. It will be used by both the utilities in this assignment, and the daemon you will write in the next one. This is accomplished by adding an abstraction layer for the disk. In the fs/fs.h file, there are two function prototypes:
// Write the data block to the disk
// block - block number
// data - A data buffer of BSIZE bytes
void disk_write(bfs_blockno block, void *data);
// Read the data block from the disk
// block - block number
// data - A data buffer of BSIZE bytes
void disk_read(bfs_blockno block, void *data);
These functions are not implemented in the fs/fs.c file. Instead, they are implemented in the utils/bfs.c file. When you write the daemon, you will provide a different version of these functions. Any time the bfs library interacts with the disk, it will do so through these functions. This time around, these functions work with a file. In the next assignment, you’ll write versions of these functions which work with the port system to accomplish the same task.
All of the code you need to write is in fs/fs.c. As always, there are a set of function stubs for you to look at and fill in, along with hints about what the function needs to do. There are some definite things you should do before attempting to fill in these functions:
- Make sure you understand what each of the structures in
fs/fstype.hare doing. In particular, make sure you have a look at the disk structures. These are packed in a way that their byte order matches their corresponding structures on disk. - Make sure you understand how the disk abstraction works. You need to think in terms of blocks, and sometimes that means you’ll need to create an array of
BSIZEbytes to act as a buffer. - Do not use functions such as
mallocorfree. You may use the functions that are defined instring.h, however, because we have those in our OS too. - Look over each of the constants and macros in
fs/fstype.hand make sure you understand what they are telling you. - Think about how you would accomplish each of the following:
- Adding a file
- Overwriting a file
- Delete a file
- Growing the directory
- Familiarize yourself with the behavior of the static helper functions. Implement those functions first.
- Write the remaining functions in terms of the static helper functions.
When you run make on this project, this will simply build the two utilities utils/mkdisk and utils/bfs:
$ make
gcc -Wall -o utils/mkdisk utils/mkdisk.c
gcc -Ifs -Iutils -Wall -o utils/bfs.o -c utils/bfs.c
gcc -g -Ifs -Iutils -Wall -o utils/fs.o -c fs/fs.c
gcc -g -Wall -o utils/bfs utils/bfs.o utils/fs.o
$
To create a disk image, use utils/bfs. The following shows you how to see the usage text for the utility, and then use the utility to create a 1MB disk image:
$ utils/mkdisk
Usage: mkdisk <diskname> <blocks>
$ utils/mkdisk disk.img 1024
$ ls -lh disk.img
-rw-rw-rw- 1 codespace codespace 1.0M Apr 10 18:49 disk.img
Something that might be useful at this stage is to use xxd linux utility to display the contents of the image in hexadecimal. This is handy for debugging. Piping xxd’s output through less will enable you to search back and forth within the image:
$ xxd disk.img | less
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000100: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000120: 0000 0000 0000 0000 0000 0000 0000 0000 ................
...
What this shows you is a listing of the file with an address column, followed by 16 bytes of information in hexadecimal, followed by a column displaying the text rendering of those 16 bytes. Note that if a byte does not contain a printable character, you will see a . in this column. As mentioned before, utils/mkdisk simply fills the disk with 0x00, and so we just see a bunch of zeroes and dots.
The utils/bfs utility allows you to do several useful things with the file system. Here is a sample run showing the formatting of the disk and copying a few files into the disk:
$ utils/bfs
Usage: utils/bfs disk-image <command> [args]
Commands
============
help This message
format Initialize a blank file system
ls List the BFS directory contents.
cp src dest Add src file to the BFS file system under name dest.
cat filename Dump a BFS file to stdout.
del filename Delete the file from the file system.
info Display disk information
$ utils/mkdisk disk.img 1024
$ utils/bfs disk.img info
No valid filesystem found on image
$ utils/bfs disk.img format
Disk blocks: 1024 used: 5 free: 1019
$ utils/bfs disk.img cp fs/fstypes.h fstypes.h
Disk blocks: 1024 used: 8 free: 1016
$ utils/bfs disk.img cp fs/fs.h fs.h
Disk blocks: 1024 used: 12 free: 1012
$ utils/bfs disk.img info
Disk blocks: 1024 used: 12 free: 1012
$ utils/bfs disk.img ls
fstypes.h
fs.h
Disk blocks: 1024 used: 12 free: 1012
$ utils/bfs disk.img del fs.h
fs.h deleted successfully.
Disk blocks: 1024 used: 8 free: 1016
$ utils/bfs disk.img del fs.h
fs.h failed to delete
Disk blocks: 1024 used: 8 free: 1016
$ utils/bfs disk.img cat fstypes.h
#ifndef FSTYPES_H
#define FSTYPES_H
#define BSIZE 1024
#define BFS_ENTRY_SIZE 32
#define BFS_NENTRY (BSIZE / BFS_ENTRY_SIZE)
#define BFS_BNOSIZE 4
#define BFS_NCTBLOCKS (BSIZE / BFS_BNOSIZE)
#define BFS_FREE 0x00
#define BFS_EOC 0xFFFFFFFF
#define BFS_MAGIC 0xBF5BF52A
...
Note that the first bfs info command fails because the disk has not been formatted yet. Lacking the magic number at the start of the super block, it fails the sanity check which is executed every time we load a bfs disk image and attempt to do something with it.
Now that we have a disk image with some things on it, we can poke around a bit using xxd. For instance, here is the super block:
00000000: 2af5 5bbf 0004 0000 0800 0000 0500 0000 *.[.............
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
...
Here is the beginning of the block chain table (which begins at address 1024 or 0x400 in hexadecimal. We can get there in less by typing / followed by 0400: and pressing enter. Learn to search for greater debugging! Here’s what we see:
00000400: ffff ffff 0200 0000 0300 0000 0400 0000 ................
00000410: ffff ffff ffff ffff 0700 0000 0800 0000 ................
00000420: ffff ffff 0000 0000 0000 0000 0000 0000 ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Can you see the structure? Our little 1MB disk has block 0 set aside for the super block, which is marked with BFS_EOC in the first 32 bits (8 bytes) of the BCT. Then the BCT begins at block 1, as seen at address 0x404. We have a link to block 2, followed by a link to block 4. The dblock begins at block 5, as shown in the super block. We also see that block 5 is the end of its chain. It looks like there is a file that starts on block 6 and spans block 7 and 8 where it terminates. How can we find out for sure where the file is? We need to have a look at the dblock! The dblock begins at byte 5 * 1024 = 5,120 which is 0x1400 in hexadecimal:
00001400: 0600 0000 1d0a 0000 6673 7479 7065 732e ........fstypes.
00001410: 6800 0400 0000 0000 82e0 0400 0000 0001 h...............
00001420: 0900 0000 360e 0000 6673 2e68 0000 0000 ....6...fs.h....
00001430: 60ec 1f00 0000 0000 60fc 1f00 0000 0000 `.......`.......
00001440: 60fc 1f00 0000 0000 684a 0000 0000 0000 `.......hJ......
00001450: 3021 0100 0000 0000 0010 0000 0000 0000 0!..............
00001460: 0200 0000 0000 0000 4019 2000 0000 0000 ........@. .....
00001470: 4029 2000 0000 0000 4029 2000 0000 0000 @) .....@) .....
00001480: 4002 0000 0000 0000 4002 0000 0000 0000 @.......@.......
00001490: 0800 0000 0000 0000 0400 0000 0400 0000 ................
000014a0: 5003 0000 0000 0000 5003 0000 0000 0000 P.......P.......
...
We can see from this that the file fstypes.h begins at block 6. We can also see the remnants of the record that was deleted. fs.h is still listed, but close inspection of its fields will show you that it has been marked as not in use, and its blocks are all marked as free in the BCT.
Let’s round this out by having a look at block 6, which is at address 0x1800:
00001800: 2369 666e 6465 6620 4653 5459 5045 535f #ifndef FSTYPES_
00001810: 480a 2364 6566 696e 6520 4653 5459 5045 H.#define FSTYPE
00001820: 535f 480a 0a23 6465 6669 6e65 2042 5349 S_H..#define BSI
00001830: 5a45 2020 2020 2020 2020 2020 3130 3234 ZE 1024
00001840: 0a23 6465 6669 6e65 2042 4653 5f45 4e54 .#define BFS_ENT
00001850: 5259 5f53 495a 4520 3332 0a23 6465 6669 RY_SIZE 32.#defi
00001860: 6e65 2042 4653 5f4e 454e 5452 5920 2020 ne BFS_NENTRY
00001870: 2020 2842 5349 5a45 202f 2042 4653 5f45 (BSIZE / BFS_E
00001880: 4e54 5259 5f53 495a 4529 0a23 6465 6669 NTRY_SIZE).#defi
00001890: 6e65 2042 4653 5f42 4e4f 5349 5a45 2020 ne BFS_BNOSIZE
000018a0: 2020 340a 2364 6566 696e 6520 4246 535f 4.#define BFS_
000018b0: 4e43 5442 4c4f 434b 5320 2028 4253 495a NCTBLOCKS (BSIZ
000018c0: 4520 2f20 4246 535f 424e 4f53 495a 4529 E / BFS_BNOSIZE)
000018d0: 0a23 6465 6669 6e65 2042 4653 5f46 5245 .#define BFS_FRE
000018e0: 4520 2020 2020 2020 3078 3030 0a23 6465 E 0x00.#de
000018f0: 6669 6e65 2042 4653 5f45 4f43 2020 2020 fine BFS_EOC
00001900: 2020 2020 3078 4646 4646 4646 4646 0a23 0xFFFFFFFF.#
00001910: 6465 6669 6e65 2042 4653 5f4d 4147 4943 define BFS_MAGIC
00001920: 2020 2020 2020 3078 4246 3542 4635 3241 0xBF5BF52A
Here we see the beginning of the file, hanging out in our disk file system.
There is a built in bfs test which you can run to verify your program. You can do this by running make fstest:
$ make fstest
utils/fstest.sh
Running format test
==========================================
/workspaces/hawx-private/utils/mkdisk disk.img 1024; /workspaces/hawx-private/utils/bfs disk.img format 2>&1
/workspaces/hawx-private/utils/mkdisk disk.img 2048; /workspaces/hawx-private/utils/bfs disk.img format 2>&1
/workspaces/hawx-private/utils/mkdisk disk.img 4096; /workspaces/hawx-private/utils/bfs disk.img format 2>&1
format test.....PASSED
Running empty directory test
==========================================
Creating disk image
Disk blocks: 2048 used: 9 free: 2039
Disk blocks: 2048 used: 9 free: 2039
/workspaces/hawx-private/utils/bfs disk.img info 2>&1
empty directory test.....PASSED
Running small write test
==========================================
Creating disk image
Disk blocks: 2048 used: 9 free: 2039
/workspaces/hawx-private/utils/bfs disk.img cp small . 2>&1
small write test.....PASSED
Running small read test
==========================================
Disk blocks: 2048 used: 10 free: 2038
small read test.....PASSED
Running large write test
==========================================
Creating disk image
Disk blocks: 2048 used: 9 free: 2039
/workspaces/hawx-private/utils/bfs disk.img cp large . 2>&1
large write test.....PASSED
Running large read test
==========================================
Disk blocks: 2048 used: 18 free: 2030
large read test.....PASSED
Running directory test
==========================================
Creating disk image
Disk blocks: 2048 used: 9 free: 2039
Adding files
1
2
3
4
5
6
7
8
9
10
...
191
192
193
194
195
196
197
198
199
200
Disk blocks: 2048 used: 1815 free: 233
/workspaces/hawx-private/utils/bfs disk.img info 2>&1
directory test.....PASSED
If any test fails, the program will halt on the failed test. (You can read the script that does the testing by looking at utils/fstest.sh. The final test creates 200 files which span multiple blocks, thus forcing your directory to grow. This is a stress test on the system as it will use up most of a 2MB disk image. You’ll see the numbered files as they are written, and after they are written, they are read back out to make sure your file system works.
Once you get that final PASSED on the directory test, you should be very proud of yourself. You’ve now implemented a file system! Now that wasn’t so bad, was it?