Introduction to File Systems CSE 120 Winter 2001 Files Files are an abstraction of memory that are stable and sharable Typically implemented in three different layers of abstraction 3 I O system interrupt handling scheduling 2 Physical file system logical blocks physical blocks 1 Logical file system paths containers CSE 120 Winter 2001 File Systems 2 Stream based files int open char path int oflag int close int fildes int read int filedes void buf int nbyte returns number actually read int write int filedes void buf int nbyte returns number actually written long lseek int fildes long offset int whence CSE 120 Winter 2001 File Systems 3 The need for caching read ahead Given a disk with 4KB blocks read metadata 15 10 3 sec seek 4 103 107 sec xfr read data 15 msec total xfr time 3 10 2 sec transfer rate 4 103 B 3 10 2 sec 133 KB sec vs 10 MB sec CSE 120 Winter 2001 File Systems 4 File Systems vs VM Systems Segment Naming Logical File System Page Aging Physical File System Swapping Driver Driver d1 open file read d compute a bit write d close d CSE 120 Winter 2001 File Systems 5 Mapped files void mmap void addr long len int prot int flags int fildes long off int munmap void addr long len CSE 120 Winter 2001 File Systems 6 Memory map example Write the first 1 024 characters of file arg 1 the character in arg 2 fd open argv 1 O RDWR O CREAT 0666 data char mmap 0 1024 PROT READ PROT WRITE MAP SHARED fd 0 for i 0 i 1024 i data i argv 2 munmap data 1024 CSE 120 Winter 2001 File Systems 7 The original Unix file system Logical File System open close read write Physical File System caching of data and metadata Driver CSE 120 Winter 2001 Two caches disk block cache metadata inode cache implemented as a hash table with LRU replacement of unlocked values File Systems 8 Locking values into the cache When should a value be locked into the cache disk cache for the duration of the systems call metadata cache for the time that the file is open CSE 120 Winter 2001 File Systems 9 inode cache issues A Unix file is deleted when there are no links to the file Ex echo 123 f ln f b rm f rm b Consider f creat foo unlink foo write f what now Can locking in cache lead to deadlock CSE 120 Winter 2001 File Systems 10 inode cache issues II Caching metadata can cause problems with respect to crashes example link count echo 123 f ln f b rm f rm b create file create entry for f file link count 1 remove entry for f file link count 1 create entry for b file link count 2 CSE 120 Winter 2001 File Systems remove entry for b file link count 0 delete file 11 Reliability induced synchronous writes Safety for all files f always number links to f link count in f s metadata How can this be implemented in the face of processor crashes CSE 120 Winter 2001 File Systems 12 R i synchronous writes II number links to f link count in f s metadata number links to f link count in f s metadata CSE 120 Winter 2001 File Systems 13 Summary so far Caching and read ahead are vital to file system performance Both techniques are important for physical data and for metadata Metadata consistency is an issue both for correctness and performance CSE 120 Winter 2001 File Systems 14 Containers The physical file system layer translates logical block addresses of a file into physical block addresses of the device The design of this mapping mechanism becomes more critical as the size of the physical device increases container name list of addresses representation of free blocks CSE 120 Winter 2001 File Systems 15 Threaded file system Use a bitmap to denote a disk block being allocated or free Container name is address of first block of file Each block contains pointer to next block in file or a special value indicating the last block in file Ex 8G disk 233 B 1K block 223 blocks disk bitmap 210 blocks 1K blocks pointer 3 or 4 bytes block CSE 120 Winter 2001 File Systems 16 File allocation table Improve random access by localizing pointers File Allocation Table Container name is first block address Free list is also stored in FAT 3 0 7 4 CSE 120 Winter 2001 1 8 6 0 free list 3 6 8 file 2 2 1 file 5 5 4 7 File Systems 17 FAT space requirements FAT 2f bytes disk 2d bytes or 2d b disk blocks block 2b bytes addressed with d b bits so2f 3 d b 2d b f 3 log d b d b b log d b d f 3 example 32G disk d 35 1M FAT f 20 smallest b is 17 or 128KB disk block example 32G disk d 35 4K block b 12 f is 25 or 32M FAT CSE 120 Winter 2001 File Systems 18 Unix File System Need to have a large FAT that exhibits better locality Can be done by having a FAT for each file superblock file system descriptor free inode list free disk block list CSE 120 Winter 2001 inode array data blocks container is index into inode array inumber File Systems 19 inode owner id group id type 0 free permissions access times number of links file length bytes direct pointer 1 direct pointer 2 direct pointer 10 indirect pointer 1 indirect pointer 2 indirect pointer 3 CSE 120 Winter 2001 block pointers block block block pointers pointers pointers block pointers File Systems block pointers block pointers 20 Free list management Finding a free inode is relatively simple can search list for a inode of type 0 Finding a free disk block is relatively hard it is free only if it is not linked in a file first problem allows more leeway for trading off accuracy for performance CSE 120 Winter 2001 File Systems 21 Free disk blocks Use free blocks to store the list of free blocks Superblock contains block s worth of free blocks in free list B blocks in files disk block pointers next blocks in free list B blocks in files blocks in free list B blocks in files good amortized performance poor locality of allocated blocks CSE 120 Winter 2001 File Systems 22 Free inodes time track switch time 3 msec having paid the cost of the initial seek it s more efficient to get many free inodes initial seek time 10 msec number found free inodes CSE 120 Winter 2001 File Systems 23 Free inodes II next remembered inode void ifree inumber i increment free inode count if superblock locked return if inode list full remembered min remembered i else store i in free inode list CSE 120 Winter 2001 File Systems 24 Other Unix file systems syscalls int int int int chdir char path chroot char path link char source char target unlink char path …
View Full Document
Unlocking...