# A1

###### tags: `csc369`

### Simplify diagram

<img src="https://i.imgur.com/c2fT4W8.png" width=256 height=256/>

### Partition Description
> A description of how you are partitioning space. This will include how you are keeping track of free inodes and data blocks, and where those data structures are stored, how you determine which blocks are used for inodes. Note that the size of the disk image and the number of inodes are parameters to mkfs.

We will partition the disk into super block, inode bitmap block, data bitmap block, data block (including inode extend block).

Free inode and data blocks are stored in inode bitmap block data bitmap block respectively.

In the super block, we have
1. num_inode_count: to record the maximum number of inodes in the system.
2. s_nr_inode and s_inode: to determine the starting inode and the starting non reserved inode. Based on this, we can determine which blocks are used for inodes, it will be (s_inode + num_inode_count) * s_inode_size.

### Extend Description

Inode total size:128
Meta data:32 bytes
mode_t mode;
uint32_t links;
uint64_t size;
struct timespec mtime;

Extends 8 bytes
11 extents => 88 bytes
extent_block => 4 byte
num_extents_used => 4 byte

The first 11 extents will be stored directly in the inode after the meta data, if there are more extents required, the inode will allocate a block to store extents, a block can store 512 extents, so it is enough to store the maximum number of extents in a inode.

### Allocate Disk Blocks

To allocate disk blocks to a file:
1. Find the last extent of the current inode according to the value of num_extends_used field of this inode.
2. Check whether the last last block of the last available extent is enough to store the extra content.
* if yes, directly store the extra content in the last block.
* if no, go to step 3.
3. Check whether there is enough available block(s) after the last extent by checking the data bitmap:
* if yes, allocate enough new block(s) and go to step 5.
* if no, go to step 4.
4. Check if num_extents_used is below 512, if is above 512, abort. Else create a new extent by checking the block bitmap, find enough free block(s) to allocate and add this new a1fs_extent to the extent_block of this inode.
5. Store the extended content in the newly allocated data block(s).
6. Modify data bitmap accordingly.

### Free Disk Blocks

1. Find the last extent of the current inode according to the value of num_extends_used field of this inode.
2. Free blocks from the end to the beginning of a file. If the freed size exceeds the size of the last block(s), then free the last block(s) by the length of the extent. Otherwise,
3. Modify the data bitmap accordingly.

### Algorithm to Seek

To seek to a specific byte in a file:
1. Compute the number of the blocks before that specific byte. Assume that byte is $b$, then the blocks before it is $floor(b / A1FS\_BLOCK\_SIZE$). Denote it as $block\_num$.
2. Add the length of each extent, and find the correct extent that byte is in. For example, if the length of each extent is $l_1$, $l_2$,....,$l_n$ and $l_1+l_2+...+l_{i-1} < block\_num$, $l_1+l_2+...+l_{i-1}+l_{i} > block\_num$, then the extent the byte in is $i$.
3. Find that byte in $block\_num - (l_1+l_2+...+l_i)$ block of extent $i$.
4. Seek to block $i$ and byte $block\_num - (l_1+l_2+...+l_i)$.

### How to Allocate and Free Inodes

To allocate inodes, we can use s_nr_inode in superblock to find the first non-reserved inode and allocate that space and update s_nr_inode to the first non-reserved inode based on inode_bitmap (may or may not be the one after the allocated inode, we will loop over the inode_bitmap until we counter the first 0). Then we need to update the inode_bitmap.

To free inodes, we can simply set the inode location on the inode_bitmap to be 0.

### Allocate and Free Directory Entries within the Data Block

To allocate directory entries,
1. Allocate an inode based on the algorithm decribed above
2. Use this inode as a directory
3. Change the mode to directory mode
4. Modify the link of this inode accordingly
5. Find the parent of this inode
6. Modify all the parents' reference

To free directory entries,
1. Find current directory inode and see if it is empty, if not empty abort.
2. Else continue
3. Check its reference
4. If it is less than or equal to 2:
* Iterate over the extents of this inode, and free all of its data blocks by modifying the data bitmap.
* Free this inode by modifying the inode bitmap
5. If it is greater than 2
* Find all the directories that reference this directory, and modify the links of the parent directory and change the address to this inode from the parent directory to -1.
* Iterate over the extents of this inode, and free all of its data blocks by modifying the data bitmap.
* Free this inode by modifying the inode bitmap

### How to Lookup a File Given a Full Path to It

1. Lookup starts from the inode of root directory.
2. If the path has not been completely traversed, find the inode address of the next level in this path. Then check that inode.
3. Then repeat step 2, until the last level of this full path.