Introduction to File SystemsCSE 120Winter 2001CSE 120 Winter 2001 File Systems 2FilesFiles are an abstraction of memory that are stable and sharable.Typically implemented in three different layers of abstraction3 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 3Stream-based filesint open(char *path, int oflag)int close(int fildes)int read(int filedes, void *buf,int nbyte) returns number actually readint write(int filedes, void *buf,int nbyte) returns number actually writtenlong lseek(int fildes, longoffset, int whence)CSE 120 Winter 2001 File Systems 4The need for caching/read-aheadGiven a disk with 4KB blocks:• read metadata 15×10-3sec seek4×103/107sec xfr• read data + 15 msec• total xfr time 3×10-2sec• transfer rate 4×103B/3×10-2sec= 133 KB/sec(vs. 10 MB/sec)CSE 120 Winter 2001 File Systems 5File Systems vs. VM SystemsDriverPhysical File SystemLogical File SystemDriverPage AgingSegment NamingSwappingd1 = open(file);read(d);compute a bit.write(d);close(d);CSE 120 Winter 2001 File Systems 6Mapped filesvoid *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 7Memory map exampleWrite 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 8The (original) Unix file systemTwo caches:• disk block cache• metadata (inode) cache... implemented as a hash table with LRU replacement of unlocked values.DriverPhysical File System:caching of data and metadataLogical File System:open, close, read, writeCSE 120 Winter 2001 File Systems 9Locking values into the cacheWhen 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 10inode 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 bConsiderf = creat(“foo”);unlink(“foo”);write(f, ...);... what now?• Can locking in cache lead to deadlock?CSE 120 Winter 2001 File Systems 11inode cache issues IICaching metadata can cause problems with respect to crashes.example: link countecho 123 > f; ln f b; rm f; rm bcreate filecreate entry for ffile link count = 1create entry for bfile link count = 2remove entry for ffile link count = 1remove entry for bfile link count = 0delete fileCSE 120 Winter 2001 File Systems 12Reliability-induced synchronous writesSafety: 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 13R-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 14Summary 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 15ContainersThe 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 blocksCSE 120 Winter 2001 File Systems 16Threaded 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 (233B), 1K block, 223blocks/diskbitmap: 210blocks (1K blocks)pointer: 3 or 4 bytes/block.CSE 120 Winter 2001 File Systems 17File allocation tableImprove random access by localizing pointers: File Allocation Table.Container name is first block address.Free list is also stored in FAT.free list: 3, 6, 8, ...file 2: 2, 1file 5: 5, 4, 70847...6103CSE 120 Winter 2001 File Systems 18FAT space requirements|FAT| = 2fbytes|disk| = 2dbytes or 2d−bdisk blocks|block| = 2bbytes addressed with d−b bitsso2f+3≥ (d−b)2d−bf + 3 ≥ log(d−b) + d − bb ≥ log(d−b) + d − f − 3example 32G disk (d=35), 1M FAT (f=20): smallest b is 17or 128KB disk blockexample 32G disk (d=35), 4K block (b=12): f is 25or 32M FATCSE 120 Winter 2001 File Systems 19Unix File SystemNeed to have a large FAT that exhibits better locality. Can be done by having a FAT for each file.superblock inode array data blocks• file system descriptor• free inode list• free disk block listcontainer is index intoinode array (inumber)CSE 120 Winter 2001 File Systems 20inodeowner idgroup idtype (0=free)permissionsaccess timesnumber of linksfile length (bytes)direct pointer 1direct pointer 2...direct pointer 10indirect pointer 1indirect pointer 2indirect pointer 3blockpointers......blockpointersblockpointersblockpointersblockpointersblockpointersblockpointersCSE 120 Winter 2001 File Systems 21Free 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 22Free disk blocksUse free blocks to store the list of free blocks.Superblock contains block’s worth of free disk block pointers.next...}{}{filesinblocksBlistfreeinblocks−=}{}{filesinblocksBlistfreeinblocks−⊇}{}{filesinblocksBlistfreeinblocks−⊆good amortized performancepoor locality of allocated blocksCSE 120 Winter 2001 File Systems 23Free inodesnumber found free inodestimeinitialseek time(~10 msec)track switchtime (~3 msec)having paid the cost of the initial seek, it’s more efficient to get many free inodes.CSE 120 Winter 2001 File Systems 24Free inodes, IInext“remembered” inodevoid 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 25Other Unix file systems syscallsint chdir(char
View Full Document
Unlocking...