Preview

  • FS API open, read, write, close, link, unlink, mkdir, rmdir, etc.
  • Implementation

Simple Implementation

  • On-disk data structures
  • Access methods
---------------------------------------------
|    |             D  A  T  A               |
--------------------------------------------

close up first part:
--------------------------------------------------------------
|Super block|Inode BM|Data BM|         I N O D E S           |
--------------------------------------------------------------
math: true
BM = bitmap
Superblock = meta-info about FS

Inode: (~256 bytes)
-------------
| type      |
| size      |
| #of blocks|  (size smaller than block size, sparse file)
| owner     |
| permission|
| addresses |
| of data blocks  (direct pointer)
-------------

Questions:

  • Access?
  • Large Files?
  • Performance: Use memory as cache
  • Pathname:
    • /a/b/c/d/main.c
    • root inode
    • root data -> a’s inode #
    • a’s inode
    • a’s data -> b’s inode #
    • …
    • d’s inode
    • d’s data -> main.c inode #
    • main.c inode

Large Files:

  • inode:
    • type
    • size
    • # blocks
    • owner
    • permissions
    • direct pointers … (addresses of first N blocks)
    • indirect pointer -> points to data block (more direct pointers)
    • double indirect ptr -> points to block with indirect -> direct
    • tripe indirect ptr
  • Some file systems use extents (ptr, length)

Caching / Write Buffering

Caching

  • frequently accessed -> in memory (use LRU-like replacement)

Write Buffering

  • write() -> fast
  • buffers in memory + return
  • (not immediately written to disk)
  • Crash => lost data
  • to ensure no data loss
    • write()
    • fsync() forces writes to disk (SLOW)
  • Delayed write benefits
    • Batch
    • Perceive lower latency
    • Avoid overwrite, ignore deleted

FFS

  • Locality: Case study of early file system (Berkeley Fast File System) [FFS]

  • FFS: Main idea “treat disk like a disk” (technology aware)

  • Simple Ideas

    • “block groups”:
      • contiguous part of disk allocate “related” items in a group
      • (spread out “unrelated” items into different group)
    • Disk
    -------------------------------------------
| Block Group | Block Group | Block Group |
-------------------------------------------

Closeup:
----------------------------------------
|Bit map     | Inodes |      DATA      |
|inodes data |        |                |
----------------------------------------

  • Allocation Policies:

    • mkdir() Directory
      • Spread across disk (e.g. pick group w/ low# of directories)
    • creat() File
      • Put files in same group as parent directory

  • Large File exception