Operating Systems: Three Easy Pieces Ch. 40

File System Implementation

• Very Simple File System
  • The file system is pure software
  • we will not be adding hardware features to make some aspect of the file system work better
• The first is the data structure of the file system
  • data and metadata
  • access method → open(), read(), write()
• Overall Organization
  • Block
    • one block size, the common size of 4 KB
    • size 4 KB
  • Data region
  • Metadata
    • Inode
    • Inode table
  • Allocation structures
    • Free list
      • points to the next free block
    • bitmap
      • Data region
      • Inode
  • Superblock
    • Contains information about this particular file system
    • inode bitmap
    • data bitmap
    • Inodes
• File Organization: The Inode
  • inode (short for index node)
  • these nodes were originally arranged in an array, and the array indexed into when accessing a particular inode
  • Each inode is implicitly referred to by a number (called the i-number), which we’ve earlier called the low-level name of the file
  • 20KB in size (five 4KB blocks) and thus consisting of 80 inodes (assuming each inode is 256 bytes)
• metadata
• direct pointers
• The Multi-Level Index
  • Indirect Pointer
    • it points to a block that contains more pointers, each of which point to user data
  • If a file grows large enough, an indirect block is allocated
  • the double indirect pointer
  • triple is possible
  • multi-level index approach to pointing to file blocks. Let’s examine an example with twelve direct pointers and a single and a double indirect block. Assuming a block size of 4 KB, and 4-byte pointers, this structure can accommodate a file of just over 4 GB in size
  • Other file systems, including SGI XFS and Linux ext4, use extents instead of simple pointers
  • Most files are small
• Directory Organization
  • each entry has an inode number, record length (the total bytes for the name plus any left over space), string length (the actual length of the name), and finally the name of the entry
  • Deleting the file → unlink()
  • directory has an inode, somewhere in the inode table
• free space management
  • pre-allocation policy
  • the file system guarantees that a portion of the file will be contiguous on the disk
• Access Path
  • The file system must traverse the pathname and thus locate the desired inode
  • root directory
  • i-number of file or directory
  • read and lseek
    • read in the first block of the file, consulting the inode to find the location of such a block
  • Close
    • No disk I/Os take place
  • Writing to the file may also allocate a block
    • Overwritten
  • Traffic of reading and writing
    • one for inode bitmap, new inode, directory, and directory inode
• Caching and Buffering
  • fixed-size cache
  • LRU
  • static partioning
    • 10% of the total memory
  • Dynamic Partioning
    • unified page cache
  • Write Buffering
  • Batch
  • Schedule
  • Fsync()
    • direct I/O interfaces
    • raw disk interface