Key Filesystem requirements:
 (1) Convenience (for users)
 (2) Efficiency (of time and disk space)

 Problems:
 (1) How do we store logical files on disk or device?
 (2) How do we allocate space as files grow/shrink?
 (3) How do we find/locate a file on a disk or device?
 (4) What kind of metadata do we need about the files?


 Contiguous Allocation:
 (a) mimics the logical file-handle/offset approach
 (b) good performance for sequential reads/writes
 (c) principle of locality....
 disadvantages:
 (d) need to reallocate files when the outgrow their space
 (e) need for defragmentation
 (f) difficult to implement -- guesstimate how much
     space we'll need for each file

 Clustered Allocation:
 (a) tends not to waste disk space
 disadvantages:
 (b) extra overhead to map logical address to physical
      disk address
 (c) external fragmentation; need for defragmentation
 (d) cluster boundary problems (principle of locality)



 Microsoft FAT-32 -- Windows 98/NT/2k/XP/Vista
 (a) maximum partition size of 2 terabytes
 (b) maximum file size of 4GB
 (c) no logging -- system failure is problematic
 (d) no enforcement of protection/security

 Microsoft NTFS
 (a) maximum partition size of 256 terabytes
 (b) maximum file size of 16 terabytes
 (c) do have logging -- recovery is much improved
 (d) enforcement of protection/security
 (e) no filename length limitations
 (f) support for Unicode and network file systems




 Multilevel Indexing
 -------------------
 e.g. block/cluster size is 4K (4,096 bytes)

 a single inode: 12 * 4K = 49,152 (48K)

 single indirect: 1,024 * 4,096 = 4,194,304 + 49,152

                               = 4,243,456 bytes

 double indirect: 1,024 * 1,024 * 4,096 =

                        4,294,967,296 bytes
                       +    4,243,456 bytes
                    ------------------------
                        4,299,210,752 bytes


                      3
 triple indirect: 1,024   blocks/clusters

            = 1,073,741,824 blocks/clusters * 4,096

            = 4,398,046,511,104 bytes
            +     4,299,210,752 bytes
           ----------------------------
              4,402,345,721,856 bytes