1 COS 318: Operating Systems File Systems 2 Topics  Storage hierarchy  File system abstraction  File system operations  File system protection 3 Traditional Data Center Storage Hierarchy Network SAN Clients Server Storage … Storage Onsite Backup Offsite backup Remote mirror 4 Evolved Data Center Storage Hierarchy Network Clients Storage … Onsite Backup Offsite backup Remote mirror Network Attached Storage (NAS) w/ snapshots to protect data2 5 Modern Data Center Storage Hierarchy Network Clients … Onsite Backup Remote mirror Network Attached Storage (NAS) w/ snapshots to protect data WAN Remote Backup “Deduplication” Capacity and bandwidth optimization Why Files?  Can’t we just use main memory?  Can’t we use a mechanism like swapping to disk? 6  Need to store large amounts of information  Need the information to survive process termination  Need the information to be share-able by processes Recall Some High-level Abstractions  Processes are an abstraction for processors  Virtual memory is an abstraction for memory  File systems are an abstraction for disk (disk blocks) 7 8 File System Layers and Abstractions  Network file system maps a network file system protocol to local file systems  NFS, CIFS, DAFS, etc  Local file system implements a file system on blocks in volumes  Local disks or network of disks  Volume manager maps logical volume to physical disks  Provide logical unit  RAID and reconstruction  Disk management manages physical disks  Sometimes part of volume manager  Drivers, scheduling, etc Disk Management Volume Manager Local File System Network File System3 9 Volume Manager  What and why?  Group multiple disk partitions into a logical disk volume • No need to deal with physical disk, sector numbers • To read a block: read( vol#, block#, buf, n );  Volume can include RAID, tolerating disk failures • No need to know about parity disk in RAID-5, for example • No need to know about reconstruction  Volume can provide error detections at disk block level • Some products use a checksum block for 8 blocks of data  Volume can grow or shrink without affecting existing data  Volume can have remote volumes for disaster recovery  Remote mirrors can be split or merged for backups  How to implement?  OS kernel: Veritas (for SUN and NT), Linux  Disk subsystem: EMC, Hitachi, IBM  How many lines of code are there for a volume manager? 10 Block Storage vs. Files Disk abstraction  Block oriented  Block numbers  No protection among users of the system  Data might be corrupted if machine crashes File abstraction  Byte oriented  Named files  Users protected from each other  Robust to machine failures 11 File Structure Alternatives  Byte sequence  Read or write a number of bytes  Unstructured or linear  Unix, Windows  Record sequence  Fixed or variable length  Read or write a number of records  Not used: punch card days  Tree  Records with keys  Read, insert, delete a record (typically using B-tree, sorted on key)  Used in mainframes for commercial data processing … … … … 12 File Types  ASCII  Binary data  Record  Tree  An Unix executable file • header: magic number, sizes, entry point, flags • text • data • relocation bits • symbol table  Devices  Everything else in the system4 13 File Operations  Operations for “sequence of bytes” files  Create: create a mapping from a name to bytes  Delete: delete the mapping  Open: authentication, bring key attributes, disk info into RAM  Close: free up table space, force last block write  Seek: jump to a particular location in a file  Read: read some bytes from a file  Write: write some bytes to a file  Get attributes, Set attributes  A few more on directories: talk about this later  Implementation goal  Operations should have as few disk accesses as possible and have minimal space overhead 14 Access Patterns  Sequential (the common pattern)  File data processed sequentially  Examples • Editor writes out a new file • Compiler reads a file  Random access  Address a block in file directly without passing through predecessors  Examples: • Data set for demand paging • Read a message in an inbox file • Databases  Keyed access  Search for a record with particular values  Usually not provided by today’s file systems  Examples • Database search and indexing 15 VM Page Table vs. File System Metadata Page table  Manage the mappings of an address space  Map virtual page # to physical page #  Check access permission and illegal addressing  TLB does all in one cycle File metadata  Manage the mappings of files  Map byte offset to disk block address  Check access permission and illegal addressing  All implement in software and may cause disk accesses 16 File System vs. Virtual Memory  Similarity  Location transparency  Oblivious to size  Protection  File system is easier than VM  CPU time to do file system mappings is not a big deal  Files are dense and mostly sequential  Page tables deal with sparse address spaces and random accesses  File system is harder than VM  Each layer of translation causes potential disk accesses  Memory space for caching is never enough  Range very extreme: many < 10k, some > GB  Implementation must be very reliable5 17 Protection Policy vs. Mechanism  Policy is about what and mechanism is about how  A protection system is the mechanism to enforce a security policy  Roughly the same set of choices, no matter what policy  A security policy delineates what acceptable behavior and unacceptable behavior  Example security policies: • Each user can only allocate 40MB of disk • No one but root can write to the password file • You cannot read my mail 18 Protection Mechanisms  Authentication  Make sure system knows whom it is talking to • Unix: password • Credit