<!-- !> More on File System implementation. 
-->

# More on File system implementation

- Recap - purpose of a FS:
  1. Translate name+offset to disks blocks
  2. Keep track of free space

## Implementation

- Storage (i.e., disk, disk image, memory) organized into blocks
- Block = 4096 bytes = 4 KB
- Example: 32 blocks = 128 KB disk

- Need to store:
  1. file contents
  2. file information (metadata): owner, group, access rights, timestamps, size, where the file is stored, ...
  3. where things are: directory structure
  4. where is the free space

- disk layout:

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |S|b|i|I|I|I|I|I|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    0             7               15              23              31    

- D: data blocks
- I: inode blocks
- S: superblock
- F: free space management struct

- free space management
  - array of true/false (true = free, false = taken)
  - e.g., free[10] gives me whether block 10 is free or not
  - we effectively have an array of bits
  - to manage 32 blocks: we only need 32 / 8 bytes = 4 bytes

- Inode table
  - stores an array of inodes (inode entries)
  - each entry: owner (user/group), access mode, timestamps, refcount, blocks occupied by contents, ...
  - example inode struct (simplified):

    ```c
    struct inode {
      uint32_t size;       // size in bytes (4 bytes)
      uint16_t mode;       // access permission and file type (directory, regular, ...) (2 bytes)
      uint16_t uid;        // owner user ID (2 bytes)
      uint16_t gid;        // group ID (2 bytes)
      uint16_t refs;       // number of har links (2 bytes)
      uint32_t atime;      // access timestamp (4 bytes)
      uint32_t blocks[10]; // 10 direct block pointers (10 * 4 bytes = 40 bytes)
      uint8_t _padding[8]; // padding to make the size a power of 2 (8 bytes)
    };
    ```
- Note: the `uint*_t` types are defined in [stdint.h](https://pubs.opengroup.org/onlinepubs/009695399/basedefs/stdint.h.html)
- This inode struct takes up exactly 64 bytes, meaning 128 of them can fit into a single block

- Directory: map from filenames to inode numbers
  - has its own inode entry (like a file, just marked as a dir)
  - stores information about entries in its data block
  - e.g.:
    
    file1       23
    info.txt    42
    documents/  3


### Create a new FS

1. Start populating the superblock
2. Write the initial bitmaps (allocating at least the superblock, the bitmap blocks, the inode blocks)
3. Allocate blocks for inode table (say, 5 blocks)
4. Create the root directory `/`
   a) allocate root dir inode entry => 0
   b) allocate root dir block for directory entries => 8
   c) populate block no. 8 with
     
      .        0

### Create a file

    $ echo "hello" > /hello.txt
    
- Syscall sequence:

    open("/hello", O_CREAT | ..., 0644)
    write("/hello", "hello", 5)
    close("/hello")

1. Grab a free inode => 1
2. Grab a free block => 9
3. Check permissions for root dir / whether file exists
4. Write "hello" to block 9 at offset 0
5. Populate the inode
6. Write the directory entry in block 8

    .          0
    hello.txt  1


### Create a directory

    $ mkdir /home

1. Check permissions for root dir / whether directory exists
2. Grab a new inode entry => 2
3. Grab a new data block => 10 (for entries)
4. Write directory into the data block

    .              2
    ..             0

5. Populate inode
6. Add entry to `/` (block 8)

    .          0
    hello.txt  1
    home       2

### Create a file bigger than one block in another dir

    $ echo "...loooong text..." > /home/big.txt

- size 5096B
- look for `home` in `/`, look for `big.txt` in `home`

1. Grab inode 0 (for `/`), check permissions, look for data block (8)
2. Read block 8, find inode for `home` (2)
3. Read inode for `home`, check permissions, look for data block (10)
4. Read block 10, find inode for `big.txt`, if doesn't exists create...
5. Allocate inode => 3
6. Allocate 2 blocks => 11, 12
7. Write first 4096B into block 11
8. Write remaining 1000B into block 12
9. Populate the inode
10. Add directory entry to block 10

    .              2
    ..             0
    big.txt        3

### Delete `/hello.txt`

    $ rm /hello.txt

1. Get the root inode (0)
2. Check permission, find data block => 8
3. Read block 8 to get entries, find `hello.txt`, get inode => 1
4. Read inode 1, check permissions: user can modify and is a file
5. Remove from directory: remove from block 8
6. Dealloc data block (mark it as free)
7. Dealloc inode (mark it as free)

### Final view of the disk

#### Layout

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |S|b|i|I|I|I|I|I|/|h|g|g| | | | | | | | | | | | | | | | | | | | |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    0             7               15              23              31

Legend:
- S - superblock
- b - block bitmap
- i - inode bitmap
- I - inode table block containing several inodes
- / - root directory data block
- h - `hello.txt` data block
- g - `big.txt` data block

#### Bitmaps (b and i)

        0      7       15
        |      |       |
    b: 0000000001000111111...
    i: 0000111111111111111...

#### Inodes

        0: 
          uid/gid: ferd/users
          mode:    040755
          size:    ??
          ts:      ...
          refs:    1
          blocks:  [8, -, -, -, ...]


        1:  (this one got deleted in the last step)
          uid/gid: ferd/users
          mode:    010644
          size:    5
          atime:   ...
          refs:    0
          blocks:  [9, -, -, -, ...]

        2:
          uid/gid: ferd/users
          mode:    040755
          size:    ??
          atime:   ...
          refs:    2
          blocks:  [10, -, -, -, ...]

        3:
          uid/gid: ferd/uses
          mode:    010644
          size:    5096
          atime:   ...
          refs:    1
          blocks:  [11, 12, -, -, ...]