Unix V6 Filesystem

its a File Payload Data with smartness.

Notably, the entire file system only supports \(2^{16} = 32MB\) worth of space due to short address types.

For each file on the disk, we store payload data in a bunch of places scattered across the disk, and a single inode which stores the location of each block for the file in an array.

• inodes contain an ordered list of block numbers, file size, permissions.
• all inodes are stored together in an inode table, which starts at block 2. Blocks 0 and 1 are disk metadata.
• inode can be read into memory individally to cache
• 10% of harddrive is used to inode

Unix V6 Filesystem limits the maximum file size in order to keep the inode a finite size.

The inode table for each file only contains space to point to \(8\) block. 1 block = 1 sector on Unix v6. inodes are usualy 32 bytes big, and 1 block = 1 sector = 512 bytes. usually this packs 16 inodes per block

inodes are 1 indexed in order to make.

inode

struct inode {
    uint16_t i_addr[8];
    uint16_t i_mode[8];
    uint16_t file_size;
}

Each inode contains 8 addresses in shorts in file order.

reading inode tables from disk

We read the raw 16-block inode data from the right sector, type coerce it into the inode type, and then read from it.

const size_t INODE_PER_BLOCK = SECTOR_SIZE / sizeof(struct inode);
struct inode inodes[INODE_PER_BLOCK];

char buf[SECTOR_SIZE];
readsector(2, &inodes); // recall this is the first 16 inodes: sec0 is fs info, sec1 is supernode

printf("addr: %d\n", inodes[0].i_add);

inode modes

inodes have two modes

if ((inode.i_mode & ILARG) != 0) == // node is in "large mode"

• in small mode, the inode stores in i_addr the block numbers to the data
• in large mode, the inode stores in the first seven numbers in i_addr block numbers to blocks that contain block numbers (512/2 = 256 block numbers, which are chars); the eighth number points to doubly indirect blocks that contain block numbers that point to other blocks

this is called indirect addressing

indirect addressing uses more steps to get to the data, and requires more blocks to get to the block numbers.

in large mode, this system can store \((7+256) \cdot (256 \cdot 512) = 34MB\), which is as large as the file system itself, which is fine now.

Directory

Folders! Directory is a container that contains files, folders, directories, etc.! Its a file container.

• All files ultimately live within root directory /.
• Absolute paths start with root directory, and gets you to the file.
• Relative paths start at the current folder, and gets you to the file

File names are NOT stored within the inode. They are stored in directories.

Unix stores 16 byte unsorted “directory entires” to represent directories:

Directory Entries

struct dirent {
    uint16_t d_inumber; // inode number of this file
    char d_name[14]; // the name; *NOT NECESSARILY NULL TERMINATED*
}

THE NAME MAY NOT BE NULL TERMINATED to cram max things. You have to use strncmp because it may not be terminated.

Lookup

Start at the root directory, /. We want to go to the root directory, and find the entry named /classes/, and then, in that directory, find the file. etc. Traverse recursively. Directory could have metadata.

A directory is basically just a file whose payload is a list of dirent.

The inode tells you whether something is a file or a directory. They can be small or large, as usual. Root directory always have inode number 1; 0 is reserved to NULL.

Because the directory entries are not sorted, in each direcotry the find is a linear search.

Key Points

• modularity: subdivision of a system into a collection of smaller systems
• layers: layer several modules over each other
• name resolution: system resolves human friendly name to machine friendly names
• visualization: making one thing look like another

Overall theme: multi-level index

Advantages

• can access all block numbers for a file
• still supports easy sequential access
• easy to grow files

Disadvantages

• lots of linear directory search

Caching

Freelist

Linked List

Linked list of free-blocks

Bitmap

Take a bit for every block in the disk, if its 1, its free. If 0, its not free. This allows locality: data likely used next is closed by, we can search local, continuous spaces.

problem: as the disk becomes full, we have to search basically \(O(n)\) for each bit until we find the free block—as the disk fills up, it becomes harder to find free space.

solution: lie to the user. don’t let the disk used up. grantee that there are some free space at all times. we typically reserve \(10\%\).

Block Cache

Getting blocks is very expensive. We can keep blocks around in memory because we may need to use them in the near future.

We will use part of the main memory to retain recently-accessed disk blocks. This is NOT at the granularity of individual files.

LRU

When you insert a new element into the cache, kick out the element on the cache that hasn’t been touched in the longest time.

Block Cache Modification

we can either write asap, or delay.

• write asap

  • safer: less risk of data loss, written as soon as possible
  • slow: program must wait to proceed until disk I/O completes

• write delay

  • dangerous: may loose data after crash
  • efficient: memory writes is faster