November 4, 2008
Written by Charles Lin
File System: an on disk data structure that provides an abstraction of a collection of files
| directory | file 1 | file 2 | file 3 | unused space |
Directory entry contains an "in use" bit
File descriptor:
| name | location | size |
Pros
+ simple
+ fast and predictable reads/writes/seeks
Cons
- directory fills up if you have lots of tiny files
- external fragmentation when you remove a file
- disk defragmentation is needed after awhile
- files can't easily grow
One solution for the last con is to use discontiguous allocation; typically, a fixed-size block-structured file system. To grow, just allocate a new block.
| boot sector | super block | FAT | blocks of data |
First block: boot sector.
Second block: super block (version number, size of the FS, amount of free space, and rootdir location).
Third block: FAT (array of block numbers that correspond to blocks in file) -1: free, 0: last block (EOF), >0: block number of block in file.
Data: 4 KiB blocks.
Directory: file that contains directory entries, each that contains: file name (11bytes), size, first block number
Pros
+ no external fragmentation
+ files can grow
Cons
- internal fragmentation due to block size
- slow and unpredictable reads/writes/seeks
- performance really takes a hit if you can't cache the FAT
Symbolic Links
File Names (e.g. "/usr/bin/sh")
File Name Components (e.g. "bin" in "/usr/bin/sh")
Inodes
File Systems
----------------------------------------------------------------------------------
Partitions
Blocks (8192 bytes)
Sectors on Disk (512 bytes)
Problems with these abstractions:
1) $ rm file
Doesn't remove the file info! Only removes down to the File Names/File Name Components level.
2) $ shred file
Overwrites the file's contents with random data 3 times, then removes it. What about caching in RAM? Use a syscall to flush it.
What about FS that allocate new blocks on writes to new regions? Shred the partition, this will successfully delete all data permanently.
Encrypting File System
All bytes on disk are encrypted
Secret key (in RAM only) to decrypt
Shredding is trivial (just lose the key!)
Free Block Bitmap: an array of bits that tells you which blocks are free (each bitmap block tells you 8192bytes x 8blocks of data ~ 512MiB of data)
Inode Table: array of inodes, each in-use inode describes a file.
Pros
+ no external fragmentation
+ files can grow
+ less internal fragmentation (worst case: 1 byte file -> 8191 bytes wasted)
+ much more compact than the FAT approach (only need to look at 1 bit to tell if a block is free)
Cons
- files have holes!
Original Unix (1977) directory entry
| name (14bytes) | inode# (2 bytes) |
Linux ext3 v.2 directory entry
| inode# (4) | direntry length (2) | filename length (1) | file type (1) | file name (N) | unused space |
mkdir("d")
-> allocate an inode
-> working directory needs to be uploaded to reflect the new inode
The link count of an inode, counts the number of directory entries pointing to this inode
Hard links can point from different dirs.
Why have hard links?
Now: to clone directory structures quickly
Originally: to avoid rename