-
To implement
Filesystem::debug
, you will need to load the file system data structures and report the superblock and inodes.- How will you read the superblock?
- The superblock contains four numbers, the magic number, the number of blocks, the number of inode blocks and the number of inodes. They can be read in using the
Data
block type in the defined unionBlock
and then be interpreted easily using theSuper
block type.
- The superblock contains four numbers, the magic number, the number of blocks, the number of inode blocks and the number of inodes. They can be read in using the
- How will you traverse all the inodes?
- From
Super.InodeBlocks
, we can get the number of inode blocks. Also, we know that from the second block, the inode blocks begin. Hence, we only need to have a loop which traverses from thesecond
block to theInodeBlocks + 1
th block. - Then, in each inode block, we know that there are
INODES_PER_BLOCK = 128
inodes, so here is the second loop which goes from the first inode to the 128th one within one inode block . - With the two loops above, we can go through every inode in the given disk.
- From
- How will you determine all the information related to an inode?
- Within each inode, the first thing we need to determine is the validity, which we can achieve from
Inode.Valid
. - Then, the size of a inode is defined in
Inode.Size
.
- Within each inode, the first thing we need to determine is the validity, which we can achieve from
- How will you determine all the blocks related to an inode?
- The direct blocks can be found using a loop built according to
POINTERS_PER_INODE = 5
. We just need to concatenate all the non-zero block numbers written in each direct array element. - Whether the inode contains an indirect block can be told by whether
Inode.Indirect
equals zero. Therefore, ifInode.Indirect
is a non-zero number, it points to an indirect block. If so, we can read in the block usingDisk::read
and then go through thePOINTERS_PER_INODE = 1024
block pointers in the block to find non-zero data block pointers.
- The direct blocks can be found using a loop built according to
- How will you read the superblock?
-
To implement
FileSystem::format
, you will need to write the superblock and clear the remaining blocks in the file system.- What pre-condition must be true before this operation can succeed?
Disk::mounted
must be false, otherwise, do nothing and return false.
- What information must be written into the superblock?
- According to the definition of superblock, we should construct a union
Block
and give it aMagicNumber = MAGIC_NUMBER
, aBlocks = disk->size()
, aInodeBlocks
which is rounded from 10% ofBlocks
andInodes = InodeBlocks * INODES_PER_BLOCK
. - One thing to mention is that before we set the fields in
SuperBLock
, we should first usememset
to set all the bits in the block to 0 because the four fields inSuperBlock
only occupy 16 bytes instead of 4096.
- According to the definition of superblock, we should construct a union
- How would you clear all the remaining blocks?
- To utilize the
Disk::write
function, we can use a loop from the second block to the last one to clear each of the remaining blocks one by one. For each block, we can write a block filled with0
, created usingmemset
function.
- To utilize the
- What pre-condition must be true before this operation can succeed?
-
To implement
FileSystem::mount
, you will need to prepare a filesystem for use by reading the superblock and allocating the free block bitmap.- What pre-condition must be true before this operation can succeed?
- The disk hasn't been mounted.
- What sanity checks must you perform?
- The
MagicNumber
should be right. - The
InodeBlocks
should equalCeil(0.1 * Blocks)
. - The
Inodes
should equalInodeBlocks * INODES_PER_BLOCK
.
- The
- How will you record that you mounted a disk?
- Call
Disk::mount
which will update theDisk::Mounts
attribute.
- Call
- How will you determine which blocks are free?
- I will build a bit map using
std::vector
, where containsBlocks
of int values, each one of which represents whether a block is free or occupied. In my design, there are two const int values defined infs.h
:FREE = 1
,OCCUPIED = 0
. - The super block and inode blocks are
OCCUPIED
. - Go through the inode blocks, compute how many data blocks needs to be occupied to store the
inode.Size
of data. Then, go through the direct and indirect (if needed) blocks and markCeil(inode.Size / disk->BLOCK_SIZE)
blocks to beOCCUPIED
. - If there is a indirect block, it should also be marked as
OCCUPIED
. - The work is done by
initialize_free_blocks()
.
- I will build a bit map using
- What pre-condition must be true before this operation can succeed?
-
To implement
FileSystem::create
, you will need to locate a free inode and save a new inode into the inode table.-
How will you locate a free inode?
- This is a relatively basic operation which only calls for a double loop to go through every inode block of a disk then every inode of an inode block. The program doesn't pursue performance, so we can simply do a linear scan and record the first invalid inode we find which would be the free inode we are looking for.
- If no empty inode was found, -1 should be returned.
-
What information would you see in a new inode?
- The new inode should hava
Valid = 1
,Size = 0
,Direct[0 ~ (POINTERS_PER_INODE - 1)] = 0
andIndirect = 0
.
- The new inode should hava
-
How will you record this new inode?
-
I implemented
FileSystem::save_inode
as instructed. The function should compute the block index and inode index according to theinumber
passed in. -
Then, it should
read in the corresponding block andmodify the selected inode.In improved version, it doesn't need to read the block again, instead, the block will be passed in as a parameter.
-
Finally, it should write the whole block back onto the disk.
-
-
-
To implement
FileSystem::remove
, you will need to locate the inode and then free its associated blocks.- How will you determine if the specified inode is valid?
- Firstly, I implemented
FileSystem::load_inode
as suggested, which is quite similar toFileSystem::save_inode
except for the value assignment toInode *
and the return valuenode->Valid
. - By utilizing the
load_inode
function, I can load the indicated inode gracefully withinumber
, of which the validity is determined by itsValid
value. When we want to remove an inode, theValid
should surely be 1 instead of 0. According to the definition ofload_inode
, the validity can be determined according to the return value of the function.
- Firstly, I implemented
- How will you free the direct blocks?
- Just go through the
Direct
array using a loop and mark all corresponding element in vectorbitMap
asFREE
. The actual value ofDirect
array doesn't need to be reset because it would be done whencreate
is called. A lazy strategy can be used here to improve performance.
- Just go through the
- How will you free the indirect blocks?
- This work is just like freeing direct blocks except that we should make sure that the inode does have indirect blocks by examining
inode.Indirect != 0
.
- This work is just like freeing direct blocks except that we should make sure that the inode does have indirect blocks by examining
- How will you update the inode table?
- The only value needs to be changed is
inode.Valid
due to the lazy strategy. After settingValid = 0
, just callsave_inode
to write the inode back to disk.
- The only value needs to be changed is
- How will you determine if the specified inode is valid?
-
To implement
FileSystem::stat
, you will need to locate the inode and return its size.- How will you determine if the specified inode is valid?
- Just make sure that
inode.Valid == 1
, otherwise, return -1. - Again,
load_inode
is a useful helper.
- Just make sure that
- How will you determine the inode's size?
- The size of an inode can simply be retrieved by reading
inode.Size
.
- The size of an inode can simply be retrieved by reading
- How will you determine if the specified inode is valid?
-
To implement
FileSystem::read
, you will need to locate the inode and copy data from appropriate blocks to the user-specified data buffer.- How will you determine if the specified inode is valid?
- Again, use
load_inode
and make sure thatinode.Valid == 1
.
- Again, use
- How will you determine which block to read from?
- For me, the data blocks related to an inode can be seen sequentially, although they may come from direct or indirect pointers.
- From the
offset
, we can tell how many blocks are completely skipped (skipBlocks
) and how many bytes still need to be skipped (remainder
) in the next block to come. When looping over the sequence of data blocks, the first few of blocks will be skipped, and the skip count will be updated, until it comes to the first valid block to be read (when skip count is decreased fromoffset / disk->BLOCK_SIZE
to0
). - From the
length
, we can know how many bytes of data we need to read in total. In my implementation, I will loop over the sequence of data blocks related to the inode. Each time I read a data block, I will readmin(disk->BLOCK_SIZE, rlength)
bytes of data, whererlength
is the remaining length to read, in case that too many bytes of data is read than needed. After reading, I will update the remaining length to read byrlength -= bytes_read
and turn to scan next data block untilrlength == 0
.
- How will you handle the offset?
- The offset mainly gives me two pieces of information.
- It determines the number of blocks to skip and the remainder bytes to skip in the first block to be read as mentioned above.
min(length, inode.Size - offset)
gives me the actual bytes needed to be read to avoid reading too many bytes which may be out of the scope of the indicated inode.
- The offset mainly gives me two pieces of information.
- How will you copy from a block to the data buffer?
- For a specific block's data copy, I will utilize
memcpy
. Fromoffset
andrlength
, I can know how many bytes of data to copy and which byte to start as described above. - The only thing left to be determined is where should the data be written to in
char *data
. So I keep a variablesize
to record how many bytes of data I have already copied. Then, the destination offset would besize
. - After finishing copy,
size
can be used to indicate how many bytes of data were copied.
- For a specific block's data copy, I will utilize
- How will you determine if the specified inode is valid?
-
To implement
FileSystem::write
, you will need to locate the inode and copy data the user-specified data buffer to data blocks in the file system.- How will you determine if the specified inode is valid?
- Again, use
load_inode
and make sure thatinode.Valid == 1
.
- Again, use
- How will you determine which block to write to?
- This is similar to
FileSystem::read
, use the relationship betweenoffset
anddisk->BLOCK_SIZE
so that we can tell how many blocks and another bytes to skip. - Then, we can loop over the sequence of blocks (direct first, then indirect) until find the first block to write in.
- The write loop should continue until all
length
of bytes are written or there is no free block to allocate or we meet the end of the inode.
- This is similar to
- How will you handle the offset?
- This work is the same as the one in
read
:skipBlocks
andremainder
.
- This work is the same as the one in
- How will you know if you need a new block?
- When meeting empty blocks during the loop, we can call
allocate_free_block
to get a free block assigned. - It is the same no matter the empty block is in direct array or indirect block.
- When meeting empty blocks during the loop, we can call
- How will you manage allocating a new block if you need another one?
- We can simply loop over the
bitMap
vector we maintained and find the first index marked asFREE
. That block can be the new block. - Before returning the index, the element should be set to
OCCUPIED
.
- We can simply loop over the
- How will you copy from a block to the data buffer?
- Similar to
read
,size
andbytesToWrite = min(disk->BLOCK_SIZE, rlength)
tell me what place at thedata
pointer to write and how many bytes to write at a time. - Each time I copy from a block to the data buffer, I use
memcpy
function. - After finishing copy, the
size
variable would be the total bytes written.
- Similar to
- How will you update the inode?
- There are three fields that may be changed during the writing process, they are
Size
,Direct
andIndirect
. - I will follow a lazy strategy to minimize the times of calling
Disk::write
, which means I will do all the updating things just before return. - I have a
size
variable which keeps tracking how many bytes are written. Therefore,inode.Size += size
is all I need. - The
Direct
array is changed during write process. When it is before writing,Direct
is surely ready. - The
Indirect
is the same asDirect
.
- There are three fields that may be changed during the writing process, they are
- How will you determine if the specified inode is valid?
The test result is shown below. The failed tests are all caused by performance incoherence. In all the cases, my implementation has better performance than the test requires.
hnoodles@hnoodles-UX410UQK:~/17302010002/OperatingSystemI/SimpleFileSystem$ make test
g++ -g -gdwarf-2 -std=gnu++11 -Wall -Iinclude -fPIC -c -o src/library/fs.o src/library/fs.cpp
ar rcs lib/libsfs.a src/library/disk.o src/library/fs.o
g++ -Llib -o bin/sfssh src/shell/sfssh.o -lsfs
Testing cat on data/image.5 ... Success
Testing cat on data/image.20 ... Failure
--- /dev/fd/63 2020-05-16 22:20:04.810435945 +0800
+++ /dev/fd/62 2020-05-16 22:20:04.810435945 +0800
@@ -143,7 +143,7 @@
0 bytes copied
0 disk block writes
-20 disk block reads
+21 disk block reads
27160 bytes copied
9546 bytes copied
Abraham Clark
Testing copyin in /tmp/tmp.xoaZh20yYg/image.5 ... Success
Testing copyin in /tmp/tmp.xoaZh20yYg/image.20 ... Success
Testing copyin in /tmp/tmp.xoaZh20yYg/image.200 ... Success
Testing copyout in data/image.5 ... Success
Testing copyout in data/image.20 ... Success
Testing copyout in data/image.200 ... Success
Testing create in data/image.5.create ... Files /dev/fd/63 and /dev/fd/62 differ
False
Testing debug on data/image.5 ... Success
Testing debug on data/image.20 ... Success
Testing debug on data/image.200 ... Success
Testing format on data/image.5.formatted ... Success
Testing format on data/image.20.formatted ... Success
Testing format on data/image.200.formatted ... Success
Testing mount on data/image.5 ... Success
Testing mount-mount on data/image.5 ... Success
Testing mount-format on data/image.5 ... Success
Testing bad-mount on /tmp/tmp.3dZos4qHQG/image.5 ... Success
Testing bad-mount on /tmp/tmp.3dZos4qHQG/image.5 ... Success
Testing bad-mount on /tmp/tmp.3dZos4qHQG/image.5 ... Success
Testing bad-mount on /tmp/tmp.3dZos4qHQG/image.5 ... Success
Testing bad-mount on /tmp/tmp.3dZos4qHQG/image.5 ... Success
Testing remove in /tmp/tmp.ry27gDmNee/image.5 ... False
--- /dev/fd/63 2020-05-16 22:20:05.022429932 +0800
+++ /dev/fd/62 2020-05-16 22:20:05.022429932 +0800
@@ -38,5 +38,5 @@
Inode 2:
size: 0 bytes
direct blocks:
-17 disk block reads
+25 disk block reads
8 disk block writes
Testing remove in /tmp/tmp.ry27gDmNee/image.5 ... False
--- /dev/fd/63 2020-05-16 22:20:05.030429705 +0800
+++ /dev/fd/62 2020-05-16 22:20:05.030429705 +0800
@@ -54,5 +54,5 @@
Inode 2:
size: 965 bytes
direct blocks: 4
-23 disk block reads
+27 disk block reads
10 disk block writes
Testing remove in /tmp/tmp.ry27gDmNee/image.20 ... False
--- /dev/fd/63 2020-05-16 22:20:05.038429478 +0800
+++ /dev/fd/62 2020-05-16 22:20:05.038429478 +0800
@@ -41,5 +41,5 @@
direct blocks: 4 5 6 7 8
indirect block: 9
indirect data blocks: 13 14
-31 disk block reads
-11 disk block writes
+41 disk block reads
+18 disk block writes
Testing stat on data/image.5 ... Success
Testing stat on data/image.20 ... Success
Testing stat on data/image.200 ... Success
Testing valgrind on /tmp/tmp.0xOvTFPQph/image.200 ... Success
Let's walk through those "failures" one by one.
This one is because my implementation used less reads.
...
-20 disk block reads
+21 disk block reads
...
This one only gives me a False
with no more information. Thus I modified the test shell code to seek more details. Here is the actual result.
Testing create in data/image.5.create ... False
--- /dev/fd/63 2020-05-16 18:03:27.829294066 +0800
+++ /dev/fd/62 2020-05-16 18:03:27.829294066 +0800
@@ -524,5 +524,5 @@
Inode 127:
size: 0 bytes
direct blocks:
-134 disk block reads
+261 disk block reads
127 disk block writes
You can see that this is also because my implementation has better read performance.
-
Again, mine have better read performance.
...
-17 disk block reads
+25 disk block reads
...
-
Same as above.
...
-23 disk block reads
+27 disk block reads
...
In this case, my implementation is better in both read and write.
...
-31 disk block reads
-11 disk block writes
+41 disk block reads
+18 disk block writes
In this section, I will explain the main optimization I have done to improve my performance(, though it's not requested).
Besides size_t inumber
and Inode *node
, I added two more parameters Block *block
and bool needRead
to these two functions.
The reason why I made the change is that I found that in some cases such as create
, the inode block has already been located, so it's unnecessary to read it from the disk again when saving a node.
Also, in remove
, we can use the Block *
to store the inode block we read in load_inode
and reuse it in save_inode
to decrease the time of calling Disk::read
.
In common sense, allocating a free block may come with cleaning it at once (use memset
to set all its bits to 0). However, it doesn't need to be like this. Instead, it can be treated in a way like malloc
, not calloc
.
In some cases, we know that we are going to write a whole block of data to a newly allocated block, where allocating a "clean" block is unnecessary. Actually in those cases, all we care about is that the block is FREE
. This happens in write
.
Even though in some cases, for instance, when we want to allocate a block as indirect block, or when the new block isn't going to be written wholly, we can still explicitly call memset
to do the cleaning work on demand.
In this way, we can have less Disk::write
operations.