the vault

File System Case Studies

Microsoft FAT File System

MBRPartition 1Partition 2Partition 3BootFATFAT(dupl)FAT(dupl)data blocksFAT

File data are allocated to

  • a number of data blocks/block clusters
  • allocation info kept as linked list.

The File Allocation Table

  • stores one entry per data block/cluster
  • disk block information such as the status, the next block, and if it is damaged
  • OS caches in RAM to facilitate linked list traversal

FAT entry code:

  • FREE
  • Block number
  • EOF code (end of file)
  • BAD code (damaged)

A directory is represented as a special type of file:

  • root directory is stored in special location
  • each file/subdirectory within folder is represented as a directory entry

The directory entry contains the following fields:

  • filename (8 characters)
  • extension (3 characters)
  • first byte contains special information (deleted, last entry, parent entry)
  • file creation time & date

Thus, as a summary:

  1. Get first block disk number stored in directory entry
  2. Use it to find the starting point of the linked disk blocks
  3. Use FAT to find out subsequent disk number
  4. Use disk block number to perform disk access
  5. Disk block contains directory entries (for a directory)

Variants

The variants generally differ from two factors

  • disk cluster
  • FAT size

Disk cluster

The allocation unit is changed from a singular disk block to a set of contiguous disk blocks.

Larger cluster size allows for a larger usable partition

Larger cluster size results in larger internal fragmentation

Bigger FAT

More disk block/cluster means more bits to represent each disk block/cluster

VirtualFAT

A workaround around FAT that supports long filenames by:

  • using multiple directory entries for an entry with a long name

Linux Ext2 File System

Disk space is split into blocks, which correspond to one or more disk sectors, which are grouped into block groups.

I-Node

A single special structure known as I-Node.

Contains file metadata, data block addresses.

MBRpartition1partition2BOOTBlock Group 0Block Group 1Block Group 2Super-BlockGroupDescriptorsBlockBitmapI-NodeBitmapI-NodeTableData Blocks

Superblock

Describes the whole file system

  • Total I-Nodes number, I-Nodes per group
  • Total disk blocks, disk blocks per group

Duplicated in each block group for redundancy

Group Descriptor

Describes the block group

  • Number of free disk blocks, free I-nodes
  • Location of bitmaps

Duplicated in each block group as well

Block Bitmap

Keeps track of the usage status of blocks of this block group.

I-Node Bitmap

Keeps track of the usage status of I-Nodes

I-Node table

An array of I-Nodes, containing I-Nodes of the block group.

I-Node Data Blocks

15 disk block pointers

  • 1- 12: Direct blocks
  • 13: Single indirect block
  • 14: Double indirect block
  • 15: Triple indirect block

The direct blocks store actual data, while the other indirect blocks point

  • to a disk block that stores direct pointers (single)
  • to a disk block that contains an indirect block (double & triple)

Fast access to small file

Flexibility in handling huge file

Directory Structure

Data blocks of a directory stores a linked list of directory entries for file/subdirectories information within the directory.

Each directory entry contains

  • I-Node number for file/subdirectory
  • Size of directory entry
  • Length of file/subdirectory name
  • File or subdirectory
  • File/subdirectory name

Hard link problems

Hard to delete I-Node with multiple references of I-Node.

  • need maintainance of an I-Node reference count

Symbolic link problems

Link can be easily invalidated.

  • [ ]

Graph View

Backlinks