Outline for TodayReview of File System IssuesRole of FilesAbstractionsFunctions of File SystemFunctions of Device SubsystemVFS: the Filesystem SwitchVnodes*Network File System (NFS)File AbstractionsMemory Mapped FilesUNIX File System CallsFile Sharing Between Parent/Child (UNIX)Sharing Open File InstancesCorresponding Linux File ObjectsGoals of File NamingMeta-DataOperations on Directories (UNIX)Slide 26LinksA Typical Unix File TreeSlide 29Access Control for FilesImplementation Issues: UNIX InodesPathname ResolutionLinux dcacheFile Structure AlternativesFile Allocation Table (FAT)Finally Arrive at FileKnow your Workload!Generalizations from UNIX WorkloadsMore on Access PatternsWhat to do about long paths?What to do about Disks?File Buffer CacheHandling Updates in the File CacheDisk SchedulingPoliciesLayout on DiskThe Problem of Disk LayoutFFS and LFSFFS Cylinder GroupsFFS Allocation PoliciesAllocating a BlockClustering in FFSLog-Structured File System (LFS)Writing the Log in LFSExample of log growthWriting the Log: the Rest of the StoryCleaning in LFSOutline for Today•Objective–Review of basic file system material•Administrative–??Review ofFile System Issues•What is the role of files? What is the file abstraction?•File naming. How to find the file we want?Sharing files. Controlling access to files.•Performance issues - how to deal with the bottleneck of disks? What is the “right” way to optimize file access?Role of Files•Persistance  long-lived  data for posterity non-volitile storage media semantically meaningful (memorable) namesAbstractionsAddressbook, record for Duke CPSUserviewApplicationFile Systemaddrfile fid, byte range*Disk Subsystemdevice, block #surface, cylinder, sectorbytesfidblock#Functions of File System•(Directory subsystem) Map filenames to fileids-open (create) syscall. Create kernel data structures.Maintain naming structure (unlink, mkdir, rmdir)•Determine layout of files and metadata on disk in terms of blocks. Disk block allocation. Bad blocks.•Handle read and write system calls•Initiate I/O operations for movement of blocks to/from disk.•Maintain buffer cacheFunctions of Device SubsystemIn general, deal with device characteristics•Translate block numbers (the abstraction of device shown to file system) to physical disk addresses. Device specific (subject to change with upgrades in technology) intelligent placement of blocks. •Schedule (reorder?) disk operationsVFS: the Filesystem Switchsyscall layer (file, uio, etc.)user spaceVirtual File System (VFS)networkprotocolstack(TCP/IP)NFSFFS LFSext2.*FS xfs.device driversSun Microsystems introduced the virtual file system framework in 1985 to accommodate the Network File System cleanly.•VFS allows diverse specific file systems to coexist in a file tree, isolating all FS-dependencies in pluggable filesystem modules.VFS was an internal kernel restructuringwith no effect on the syscall interface.Incorporates object-oriented concepts:a generic procedural interface withmultiple implementations.Based on abstract objects with dynamicmethod binding by type...in C.Other abstract interfaces in the kernel: device drivers,file objects, executable files, memory objects.Vnodes*In the VFS framework, every file or directory in active use is represented by a vnode object in kernel memory.syscall layerNFS UFSfree vnodesActive vnodes are reference-counted by the structures thathold pointers to them, e.g.,the system open file table.Each vnode has a standardfile attributes struct.Vnode operations aremacros that vector tofilesystem-specificprocedures. Generic vnode points atfilesystem-specific struct(e.g., inode, rnode), seenonly by the filesystem. Each specific file system maintains a hash of its resident vnodes.*inode object in Linux VFSNetwork File System (NFS)syscall layerUFSNFSserverVFSVFSNFSclientUFSsyscall layerclientuser programsnetworkserverFile Abstractions•UNIX-like files–Sequence of bytes–Operations: open (create), close, read, write, seek•Memory mapped files–Sequence of bytes –Mapped into address space–Page fault mechanism does data transfer•Named, Possibly typedMemory Mapped Filesfd = open (somefile, consistent_mode);pa = mmap(addr, len, prot, flags, fd, offset);VASlenlenpafd + offsetR, W, X,noneShared,Private,Fixed,NoreserveReading performed by Load instr.UNIX File System Callschar buf[BUFSIZE];int fd;if ((fd = open(“../zot”, O_TRUNC | O_RDWR) == -1) {perror(“open failed”);exit(1);}while(read(0, buf, BUFSIZE)) {if (write(fd, buf, BUFSIZE) != BUFSIZE) {perror(“write failed”);exit(1);}}Pathnames may be relative to process current directory.Process does not specify current file offset: the system remembers it.Process passes status back to parent on exit, to report success/failure.Open files are named to by an integer file descriptor.Standard descriptors (0, 1, 2) for input, output, error messages (stdin, stdout, stderr).File Sharing Between Parent/Child (UNIX)main(int argc, char *argv[]) {char c;int fdrd, fdwt;if ((fdrd = open(argv[1], O_RDONLY)) == -1)exit(1);if ((fdwt = creat([argv[2], 0666)) == -1)exit(1);fork(); for (;;) {if (read(fdrd, &c, 1) != 1)exit(0);write(fdwt, &c, 1);}}[Bach]Sharing Open File Instancesshared seek offset in shared file table entrysystem open file tableuser IDprocess IDprocess group IDparent PIDsignal statesiblingschildrenuser IDprocess IDprocess group IDparent PIDsignal statesiblingschildrenprocess file descriptorsprocessobjectsshared file(inode or vnode)childparentCorresponding Linux File Objectssystem open file tableuser IDprocess IDprocess group IDparent PIDsignal statesiblingschildrenuser IDprocess IDprocess group IDparent PIDsignal statesiblingschildrenprocess file descriptorsprocessobjectschildparentper-processfiles_structfile objectscreated on opendcachedentryobjectsinodeobjectGoals of File Naming•Foremost function - to find files, Map file name to file object.•To store meta-data about files.•To allow users to choose their own file names without undue name conflict problems.•To allow sharing.•Convenience: short names, groupings.•To avoid implementation complicationsMeta-Data•File size•File type•Protection - access control information•History: creation time, last modification,last access.•Location of file - which device•Location of individual blocks of the file on disk.•Owner of file•Group(s) of users associated with fileOperations on Directories (UNIX)•Link - make entry