VU Operating Systems

Lecture 4: File systems

File systems
File systems are ways to organize and persistently store information

Memory is not persistent, but file systems allow data to be stored in disk. This is persistent.

Examples:
●​ FAT12/FAT16: MS-DOS or USB sticks
●​ Windows: NTFS
●​ Linux: Ext4
●​ MacOs: APFS

Files are abstract storage nodes

You either read files sequentially or randomly

File types:
●​ Regular files, directories, soft links (pointer to another file)
●​ Special files (device files, metadata files)
File structure:
●​ OS perspective: files as streams of bytes
●​ Program’s perspective: archives, executables etc

File naming
 ●​ Different file systems have different limitations/conventions for file names: like file
extensions
●​ File name length:
○​ FAT12: 8 characters for file name and 3 characters for extension (now 255)
○​ Ext4: 255 characters
●​ Special characters in file names:
○​ FAT12: No “ * / : < > ? \ |
○​ Ext4: No ‘\0’ and ‘/’ or the special names “.” and “..”
●​ Case sensitivity

File operations
●​ Create/delete
●​ open/close
●​ read/write
●​ Append
●​ Seek
●​ getAttributes/SetAttributes
●​ Rename

File operations - Unix

If open does not work:
●​ -ENOENT: file does not exist
●​ -EBADF: Bad file descriptor
 ●​ Seeking in files:
○​ lseek(fd, bytes, SEEK_CUR) ⇒ seek relative to current position
○​ Lseek can be used to skip forward or backward in a file

●​ Writing in files:
○​ Flags:
○​ O_WRONLY: writing only
○​ O_CREAT: creates the file if it doesnt already exist
○​ O_TRUNC: if the file does exist, it will truncate the file into 0 bytes (throw away
current file content)
●​ unlink() to remove a file
●​ Rename() to rename
●​ Chmod() to change permission attribute
●​ chown() to change file owner attribute

Directories
Data structures organizing and maintaining information about files

●​ Often stored as file entries with special attributes

Directories are denoted by “/” in unix and “\” in windows

●​ Special directory entries:

○​ . Current directory
○​ .. parent directory

We first only had one root, but now we have different users with subdirectories.

Directory operations
 ●​ create/delete
●​ opendir/closedir
●​ Readdir
●​ Rename
●​ link/unlink

Virtual File System (VFS)

Interface between user programs and underlying file systems

Advantage: user only sees one file system. Eg:
●​ /: Partition 1 (Ext3)
●​ /home: Partition 2 (Ext4)
●​ /mnt/usb: SUB partition 1 (FAT)
●​ /tmp: RAM (non-persistent) storage (tmpfs)

These are all different file systems but the VFS creates an abstraction layer so taht it looks like
one system
 1.​ VFS consults the process table where every process has an entry with some metadata
2.​ In the process table, the file descriptor table can be found
3.​ The file descriptor table gives us a specific V-node (aka I-node) which holds a lot of
information for that specific file
4.​ The V-node table points to a table of function pointers. Writing to a file has a function
pointer, same for reading or opening.
5.​ These function pointers point to the relevant driver for this action.

This is how different drivers and file systems can be used and abstracted by the Virtual file
system

File system implementation

●​ How to store files?
●​ How to implement directories
●​ How to manage disk space?
●​ How to ensure file system reliability

How to store files?

File system layout

Disks are organized in partitions
 ●​ Master boot record: contains boot code to locate the active primary partition (the OS)
and execute its boot block
●​ (old MBR scheme) Partitions: primary, extended, subpartitions
●​ MBR is nowadays superseded by GPT (similar to above but more flexible)

How to store the files on the disk?

●​ Contiguous allocation
○​ If you have a 2 MB file and you need contiguous space. This is too complex. The
hard disk is divided into blocks, a file could use non-contiguous blocks.
●​ Block-based strategies:
○​ Linked list
○​ File allocation table
○​ I-nodes

File storage: linked list

Random access is slow, but bigger issue is that the blocks are no longer a power of two since
each block has metadata that stocks blocks from being power of two. To solve the power of two
storage problem: we move to the next storage strategy
File storage: file allocation table
Store all the pointers in a file allocation table, now the blocks themselves have power of two data
Random access is efficient now
Issue here: we need to preallocate table for every block on disk, if we have many blocks, the table
will need to be very very big

File storage: I-node

I-nodes store the blocks used per file

This has better scalability: you only require the metadata for files that are being used
For larger files, one i-node can point to additional blocks containing more data block addresses

How to implement directories?

Problems to tackle:
●​ How to store directory information?
●​ Are attributes stored in directory entries?
 ●​ How to find the root directory?
●​ How to find any other directory?

FAT12/FAT16 layout

Boot sector: starts OS

Reserved: later used for file metadata
FAT#1 and FAT#2 are file allocation tables containing links to blocks
Preallocated root directory - to find the root directory (its hard coded)
Clusters represent addressable blocks:
●​ FAT contains chains indexed by starting cluster

FAT12/FAT16 Directory Entry

Later on Long File Name (LFN) entries used multiple entries for a single file, setting several
reserved bits for backwards compatibility

Using the FAT (file allocation table), we can use the first block to find all other files in this
directory
UNIX directory entry

●​ Directory entry stores only name and #i-node

●​ Attributes are stored in the i-node
●​ One i-node per file, first i-node is the root
●​ Where are the i-nodes stored?

UNIX FS layout

Directory lookup
 1.​ We know where the root dir is so we start there and we find the first part of the path we
want which is /usr which has i-node 6
2.​ In I-node number 6, we find the index of the block of the usr directory
3.​ In block 132, we get the inode number for the ast directory, inode 26
4.​ We go to inode 26 and we get the index of the block of the ast directory
5.​ Mbox file has inode number 60

How to manage disk space?

Disk space: block size impact

How to choose the block size?
​ Trade off between data rate and space overhead (fragmentation)
If you have large blocks but small files, the blocks will be empty (fragmentation risk). However,
Larger blocks is better for the datarate. A hard disk is more efficient if you read data one byte
after another (which is so with larger blocks).

Disk space: tracking free blocks

1.​ Linked list of all free blocks
a.​ Stored in free blocks, less metadata the fuller the disk gets
2.​ Static bitmap with 1 bit per block (0 or 1 depending if free block or not)
a.​ Size is fixed even if disk is full

If the file system is empty, the linked list will be huge because every block is free
While the bitmap is a fixed small size

The fuller the file system is, the smaller the linked list, so this is more efficient

Creating a file system

●​ Format partition
●​ Create basic layout, FS specific
●​ UNIX: mkfs (eg mkfs.ext4 or [Link])

File systems: reliability threats

How to ensure file system reliability?

●​ Disk failures
○​ Bad blocks
○​ Whole-disk errors
●​ Power failures
○​ (Meta)data inconsistently written to disk
 ●​ Software bugs
○​ Bad (meta)data written to disk
●​ User errors
○​ Rm *.o (remove all files in dir) vs rm * .o (delete the file .o)

Reliability solution: backups

Backups: technical aspects

●​ Incremental vs full backups
●​ Online vs offline (while system is running or not)
●​ Physical vs logical
●​ Compressed vs uncompressed
●​ Local vs remote

One way to do backups:

RAID: Redundant Array of Independent Disks

●​ Raid 0 & 2: expand file system over multiple disks (increase storage)
●​ RAID 1: duplicate file system over disks (increase redundancy)
●​ RAID 3-6: Parity on one disk (increase both)
○​ Parity data stored in all disks, if one disk fails, the other parity data in the other
disks is enough to restore lost data

File system integrity and repair

Backups are great, but how do we know when there are problems?

●​ On unix: fsck
●​ On windows: chkdsk
●​ Finds consistency errors in file system metadata
○​ Corrupt values
○​ Used blocks also marked as free
○​ Blocks not marked as free nor used
 ○​ Blocks being used multiple times

File system performance

How quickly you can write or read data
Two ways to do so:
1.​ Minimize disk access
2.​ Minimize seek time

Minimize disk accesses: caches

●​ Buffer cache: cache disk blocks in RAM (read from this cache instead of disk)
●​ Page cache: cache VFS pages (before going to driver)
○​ Both caches often contain the same data, so OSs often merge them

Cache management
●​ Caches have LRU semantic adapted to:
○​ Get rid of blocks with poor temporal locality
○​ Critical blocks for file system consistency

●​ Write-through caching (immediately write data in disk after storing in cache) vs periodic
syncing (only store in cache and periodically flush to disk)
 ●​ Disk read-ahead: read blocks into cache that may be used soon

Minimize seek time (traditional HDDs):

●​ Try to allocate files contiguously
●​ Defragment disk
●​ Spread i-nodes over disk
●​ Store small file data “inline” in i-node
The image below wants to tell us that the arm that moves in an HDD to read data takes a lot of
time. If you have to read the inodes in one section (left) and then find the block id and then keep
doing that its very inefficient. The right is better for this.

●​ Not so much an issue on SSDs

○​ Instead optimize wear reduction. SDDs wear out the more you read them and
then you cant store data in those sections anymore.

Log-structured file systems

idea: lets assume we have a lot of memory and we only rely on cached reads. Now we want to
optimize small writes since those are common.

We design a file system based on this.

Left is the file system we are used to.
Right is the log-structured fs.

●​ Whenever we write something, we collect the write operation in a log segment. A log
segment contains i-nodes, directories, blocks.

●​ Segments are regularly flushed to disk and can be large (eg 1MB)

●​ I-node map to find i-node in the log

●​ Garbage collection to reclaim old log entries

Ask chatgpt, why does this file system not work for reads? He says smth about it being slower
but i dont understand why

Journaling file system

The above is not very efficient since it doesnt work with existing file systems

●​ Idea: use “logs” for crash recovery

●​ First write transactional operations in log before doing any operations
○​ Eg: removing a file:
■​ Remove file from its directory
■​ Release i-node to the pool of free i-nodes
■​ Return all disk blocks to pool of free disk blocks
●​ After crash, replay operations from log
●​ Single operations need to be idempotent (=repeatable)
●​ Should support multiple, arbitrary crashes
●​ Journaling widely used in modern systems
○​ Eg: ext4 and NTFS

FUSE: (filesystem userspace) drivers

This allows an arbitrary userspace program to act as a driver for a filesystem

The FUSE userspace program can do syscalls like any other user program

FUSE
●​ Makes driver development much easier
●​ No permissions required for new FS drivers
●​ But, slower than in-kernel drivers

Examples using FUSE:

●​ sshfs: mount remote machine over ssh
●​ ntfs-3g: NTFS on linux
 ●​ Exfat: exfat on Linux (in-kernel only since Nov 2019)
●​ WikipediaFS: “View and edit wikipedia as files”
●​ EmojiFS: “manipulate your emojis on Slack/Discord”
●​ Piefs: “store files (as offsets) in pie”

Using FUSE
●​ Compile and link a program against libfuse
●​ Run binary to mount into VFS
●​ Callback driven:
○​ Kernel/FUSE calls you when someone interacts with your files/directories

When a program tries to read a file, FUSE will call the hello_read function. The above shows the
function pointers of FUSE.

FUSE callbacks
●​ Most important callback: getattr
●​ Called before any operation on file
●​ Retrieves file(/directory) attributes
○​ Via struct stat -see man 2 stat
●​ Directory example: stbuf -> st_mode = S_IFDIR | 0755
●​ File example: stbuf -> st_mode = S_IFREG | 0755
●​ Non-existing entry: return -ENOENT

Familiar from syscalls:

●​ Readdir
●​ Read
●​ Mkdir
●​ Rmdir
●​ Unlink
●​ Create
●​ Truncate
●​ Write
●​ Rename