# 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 free space

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |S|b|b|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 - where file contents are stored
- I: inode blocks - where metadata is stored
- f: free space information
- S: superblock - disk metadata

- free space information: usually tracked as an array of size= number of blocks
  - the array is an array of _bits_ (rather than booleans/ints)
  - 1 means free / 0 means taken (allocated)

- /home/ferd/docs/info.txt
- directories:
  - i-node (entry) - metadata about directory
  - data block - contents of the directory
- storing /: 
  - allocate inode 0: conventional entry for root dir
  - store the creation date, owner, access rights, etc.

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

  - allocate a data block for the root directory
  - directory: maps filenames (also directory names) to inode numbers
  - the first entry in a directory is '.' which points to the inode of the directory itself

    root directory:
    .     0

- for a new filestystem: allocate and inode for the root dir
- and allocate a datablock containing a reference to the root dir
- mark the blocks as taken in the block bitmap
- mark the inode entry for / as taken in the inode bitmap

- `open("/data.txt", O_CREAT | ..., 0644)`
  - create directory entry for data.txt
  - create an inode entry for the new file
  - allocate a data block for the new file


    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |S|i|b|I|_|_|_|_|R|_|h|f|t|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    0             7               15              23              31      

0. check whether the directories along the path exist and whether the user has the appropriate access rights for them

1. create an inode entry for the new file
   - allocate inode => 1
   - populate inode with info

     user: ferd
     created: (current date and time)
     access mode: 0644
     group: users
     blocks: 

2. create directory entry in /
   - grab inode 0
   - find the data block => 8
   - check if file exists, if doesn't create a new inode entry
   
     .          0
     data.txt   1

3. allocate a data block
   - grab the first available data block => 8
   - update inode entry with block: 8

     user: ferd
     created: (current date and time)
     access mode: 0644
     group: users
     blocks: 8

4. If writing data
   - find the data block, write the data at the appropriate offset




- `mkdir /home`

  1. grab an inode => 2 (mark it as allocated)
  2. fill it in with the metadata (user, access, timestamps, ...)
  3. add to root directory entry (in block 7)
    
     home      2

  4. grab a free data block => 9 (mark it as allocated)
     - store

     .         2


- `mkdir /home/ferd`
  1. grab an inode => 3, populate
  2. grab a data block, insert entry for .
  3. add entry to data block 9


- `echo hello > /home/ferd/hello.txt`
  - create a new file in /home/ferd, and write string "hello" into it

  1. check that space is available
  2. `/`: go to inode 0, check that user has access, find its data block
  3. find `home` in `/`: take its inode (2), check that user has access, go to its data block
  4. find `ferd` in `home`: take `ferd`'s inode, check that current user has access, go to its data block
  5. grab a free inode entry => 4, populate
  6. grab a free block => 12 (t)
  7. write block number to inode
  8. add directory entry to `ferd`
    
    .           3
    hello.txt   4

  9. write "hello" to block 12 at offset 0  
  

- `rm /data.txt`
  1. find entry in `/`
  2. remove the `data.txt` entry from `/`'s directory
  3. go to `data.txt`'s inode
  4. mark its block 9 as free
  5. mark the inode 1 as free

- `cat 5kofdata.txt > /home/ferd/hello.txt`
  1. ... traverse /, home, ferd to find the inode for hello.txt
  2. check whether we have enough data blocks
  3. allocate additional block => 9
  4. write first 4K into block 12
  5. write remaining 1K into block 9
  6. update the inode with `blocks: 12, 9`


- my inode entry can store at most 4 block numbers (pointers)
- say that a block no. takes 4 bytes
- I want to be able to support arbitrarily large files, but optimize for small ones
- dedicate one block no. as an indirect pointer
- data block will point to other block numbers
- with 4 bytes per bloc no, this gives me 1024 blocks
- gives me a max file size of ~4MB