# Post: File System

## Overview

Introduction: this blog post will cover the basics of an operating system’ s file systems.

Hardware:

• In a spinning hard disk, data are encoded around a circular disk
• To access a certain data, the disk will need to spin such that the data location on the hard disk coincide with the head.

### File Data

File data: the data that is associated to the file (excludes metadata)

Structure:

1. Array of bytes:
• All the data in a file can be seen as an array of raw bytes
• Each byte will have a unique offset
2. Records:
• File data is stored as a collection of records.
• Each file has many records and each records has many bytes
• Variant 1: fixed length records:
• Each record has a fixed length
• Structured as an array of fixed length record
• Easily access a record by getting the offset in the record array
• Variant 2: variable length records:
• Each record can have different length

Access method:

1. Sequential Access:
• Access the bytes in the file data sequentially
• Cannot skip a byte
2. Random Access:
• Can access any byte in the file data
• Using Read(offset) or Seek(offset)
3. Direct Access:
• Randomly access any records directly

## File operations

• Open: prepare all the information needed for file. Must be used before any file operation
• Create: new file created
• Write: write data usually starting from current position
• Repositioning aka seek: move the current position to a new location
• Truncate: removes data between position to end of file

### File Operation as System calls

Information needed for file operation:

• File pointer: current location inside the file
• Disk location: actual file location on disk
• Open count: how many process has this file opened

Caveats:

• What if two process open the same file?
• What if process want to open many files?

Unix Implementation:

• System-wide Open File Table (OS Level)
• The OS maintains a global table of open files “context”
• (klement: nobody uses context but it context seems like an apt description for it)
• Table is shared among all processes
• Each entry in the table represents an open file context
• The permission, file location (offset), the pointer to the data (vnode)
• If process A and process B open the same file, process A and process B will have its own entry.
• File descriptor table (Process Level)
• Each process maintains a file descriptor table
• Each entry of the file descriptor table points to an entry in the System Open File table.
• File descriptor: an index in the process’ file descriptor table. (ie stdout fd = 0, first entry in the file descriptor table)
• Independent file descriptor table allow different processes to access files independently.
• Forking:
• When a process fork, the child process will inherit the file descriptor table of the parent
• Each entry in the child and parent file descriptor table will point to the same entry in the system open file table.
• This is the reason why forked children stdout to the same console as the parent.
• vnode:
• The OS also maintains a table for all open files
• Each entry is an open file
• Open file are contextless (no concept of offset in file) vnode
• (klement: For unique file, there can only be one vnode entry?)
• Contains pointer to inode (physical file) and information for the file

Reference Counting:

• System wide open file table and vnode table use reference count to decide when to evict the entry
• Process’ file descriptor table has a reference to system wide open file table
• System wide open file table has reference to vnode table
• OS uses reference counting to determine when there are no higher level table’s entries that refers to it.
• Evict that entry once the reference count goes to 0.

More details: here

## File System Implementation

Components:

• Disk structure: a disk can be treated as a 1-D array of logical block
• logical block: smallest accessible unit in the disk (usually 512b to 4kb)
• disk sector: each logical block belongs to a disk sector
• Master Boot Record (MBR): located at the start of sector 0
• Stores the OS boot up information
• Partition: after the MBR
• Stores information on how the files are located and accessed

Problem: similar to memory allocation, file system face the problem of external fragmentation.

• Should the blocks be contiguous or non-contiguous?
• (klement: Internal fragmentation is not really a problem as it is restricted by the logical block size)

Naive solutions:

• Each file will have a head block and each block will contain a pointer to the next block.
• Random Access: O(N)
• Can be optimised by having the block pointers loaded in memory (still O(N)).
• Direct indexing:
• Each file will have a special index block
• Index block will contain an array of pointers to all the blocks that belongs to the file.
• Cons: the file size is limited by the maximum size of the array in a logical block.
• Can be optimised using multi level table (similar to multi level paging)

### Unix Solution

Combine Scheme: uses both direct indexing and multi-level scheme

• Each inode has 15 blocks
• 0 - 11 blocks: direct pointers
• direct pointers are actual data on disk
• 12 block: single pointer
• contains an array of direct pointers (direct indexing)
• 13 block: double indirect
• points to an array of single pointers
• 14 block: triple indirect
• points to an array of double indirect

Tags:

Categories:

Updated: