CS 111, Spring 2013 | File System Design | May,9 2013

File System Design

What is file system

• an on-disk data structure
• provides an abstraction of a set of files

Paul Eggert/RT-11 File System (1974)

• 16 sectors of fixed size directory (array of directory entries)
• each directory entry
  • 16-byte file name (NULL-filled if unused)
  • 16-bit start sector #
  • 16-bit length of file
• pros and cons
  • [+]simple
  • [+]fast for contiguous reads
  • [-]directory could be corrputed -> leads to disaster
  • [-]no subdirectories
  • [-]size of file must be known in advance (at least good estimated)
  • [-]fragmentation
    • internal fragmentation: space wasted due to last sector's tail left unused
    • external fragmentation: have enough free space, but not contiguous and cannot be used

FAT File System

• FAT: File Allocation Table
• Main goal is to solve fragmentation problem and no subdirectory problem mentioned in previous file system.
• Structure of FAT is as follows

  Overhead

  File Allocation Table(FAT)

  Data Blocks

  1. Overhead Table

     Boot Sector	Superblock
     contains bootstrapping programs which the MBR transfers to CPU	contains meta-data about the file systems, for example, the size of the file system, which version of FAT and etc. The super block is small and its size is fixed

  2. File allocation table
     • Array of instructions,2 bytes each (16bits)
     • For a block
       • 0: means the current block is the last of the file (EOF)
       • -1: means the block is free
       • n: the number of the next block in the file
  3. Data blocks
     • Block size is 4KiB, each sector is 512 bytes
     • The data of file may not be contiguous in a FAT file system
  4. Directories
     • Arrays of directory entries, each entry has the following structure

       File name and extension	Meta-data about file(size)	First file number	File type

     • File names and extension: 11 bytes fields divided into 8+3
     • Meta-data about file(size): 32 bits
     • File types: specify if its a file directory or file name
• How FAT works
  • Initially, data blocks are allocated sequentially,since all blocks are empty and sequential.
  • When trying to find a new empty block for new contents,we simply search the FAT to find an entry with value -1.
  • Whenever we gets the first block of the file, we can keep getting the next block number until we reached the end of file
  • later on, when early blocks are removed, and we are trying to fit a new file (which is larger than the size of the block we freed), the file might be saved non-sequentially
• Problems with FAT
  • Performance suffers when you have fragmentation
    defragmentor FAT[i]== i+1 as much as possible --> slow,ties up drive and can be flaky
  • Two directory entires pointing to the same file, remove one, go trough the FAT table, free its blockes --> disasters
  • Blocks may not be allocated continuously
  • Rename of a file is not allowed in FAT

Berkerley FFS(fast file system)--Unix File System

• Structure

  Boot sector	Superlock	Block bitmap	Inode tables	Data blocks

• Inode
  1. A data structure on disk that describes a files, independent of any directory
  2. The use of block bitmap encourages contiguous allocation, which would reduce fragmentations
  3. Unique for each file, containing meta information and block points to actually data file
• Inode structure

  Link count
  Owner
  10 directed data block pointers	→ 10*8KiB = 80kiB of data
  80 indirect block	→ (8 kiB/4) pointers = 16MiB data
  Double indirect block	→ (8kib/4) pointersˆ2 = 32 GiB

• Directory

  14 bytes name	2 byte inode number

• Special cases

  If a file doen't exit, put 0 in that block,file can have holes, holes are read as zeros, allocated when written

  1. fd = open("w", O_CREAT|O_RDWR)
  2. ftruncate(fd,1000000000): have a 1000000000 size file but have nothing in it