# 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

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |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

- 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
    
    file1       23
    info.txt    42
    documents/  3

### Create a new FS

1. Start populating the Superblock
2. Write the initial bitmaps
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`

- `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

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |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:
          7 
b: 0000000001000111111...
i: 0000111111111111111...

### 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)

Inodes:

        0: 
          own: ferd/users
          acc: 040755
          siz: ??
          ts:  ...
          ref: 1
          bl:  [8, -, -, -]


        1:  (this one got deleted in the last step)
          own: ferd/users
          acc: 010644
          siz: 5
          ts:  ...
          ref: 0
          bl:  [9, -, -, -]

        2:
          own: ferd/users
          acc: 040755
          siz: ??
          ts:  ...
          ref: 2
          bl:  [10, -, -, -]

        2:
          own: ferd/uses
          acc: 010644
          siz: 5096
          ts:  ...
          ref: 1
          bl:  [11, 12, -, -]