Project ScopeImplementation DetailsFilesystem StructureConcurrent AccessConsiderationsProject 6Project 6File SystemRobert EscrivaSlide heritage: Krzysztof OstrowskiCornell CS 4411, November 22, 2010Project 6AnnouncementsProject 5 due tomorrow at 11:59PM.Project 6 due December 8 at 11:59PM.Web page is being updated frequently; check forupdates.Project 61 Project Scope2 Implementation Details3 Filesystem Structure4 Concurrent Access5 ConsiderationsProject 6Project Scope1 Project Scope2 Implementation Details3 Filesystem Structure4 Concurrent Access5 ConsiderationsProject 6Project ScopeWhat do you have to do?Implement a virtual file system using a virtual blockdevice.Implement a UNIX-like interface to the filesystem.You need to support:Create files of variable size (while efficiently using diskspace)Reclaim storage from deleted files.A hierarchy of nested directories.Concurrent access to the SAME file(s) by multiple threads.Project 6Project ScopeOur proposed plan of attackPlay with the block device, and see how it behaves.Learn the UNIX filesystem API:Parameters.Semantics.Decide on details of filesystem internals.Representation of directories, inodes, the superblock, etc..Implement.Perform extensive testing.Concurrent operations should be your focus when testing.Project 6Project ScopeWhat is this virtual block device?Stores blocks in a regular NT file.Creating a disk ⇒ create the NT file.Spin-up a disk ⇒ open the NT file.We support just one disk which will contain all of yourMINIFILESYSTEM.The block device is just a raw stream of bytes with noorganization.Need to create any and all structures on top of the blockdevice.Project 6Project ScopeHow does this block device work?Block-level operationsRead/write take a block-sized buffer, and block number.Blocks are hard coded using DISK_BLOCK_SIZE.Operations are asynchronous (just like a real device).You schedule requests by a control call to the device.A limited number of requests may be processed at anyone time.Requests will be arbitrarily delayed and re-ordered.Asynchronous events complete by means of an interrupt.Once again, you’ll need to write an interrupt handler.Project 6Implementation Details1 Project Scope2 Implementation Details3 Filesystem Structure4 Concurrent Access5 ConsiderationsProject 6Implementation DetailsCreating/attaching a block device// Create a new diskint disk_create(disk_t*disk,char*name,int size,int flags);// Access an existing diskint disk_startup(disk_t*disk,char*name);Flags: DISK_READWRITE or DISK_READONLYBoth prepare the disk for use.Project 6Implementation DetailsSending requests to the diskint disk_send_request(disk_t*disk,int blocknum, char*buffer,disk_request_type_t type);Request types:DISK_RESET Cancel any pending requests.DISK_SHUTDOWN Flush buffers and shutdown thedevice.DISK_READ Read a single block.DISK_WRITE Write a single block.Responses are returned asynchronously.Return values: 0 = success, -1 = error, -2 = too manyrequests.Wrappers: disk_read_block /disk_write_block.Project 6Implementation DetailsThe interrupt handlerInstall it with:void install_disk_handler(interrupt_handler_t disk_handler);Argument you will receive:typedef struct {disk_t*disk;disk_request_t request;disk_reply_t reply;} disk_interrupt_arg_t;Project 6Implementation DetailsInterrupt notification typesDISK_REPLY_OK operation succeeded.DISK_REPLY_FAILED disk failed on this request for noapparent reason.DISK_REPLY_ERROR disk nonexistent or block outsidedisk requested.DISK_REPLY_CRASHED it happens occasionally.Project 6Implementation DetailsThe API you will write ICreation (creat) / deletion (unlink)Open / closeModes are similar to fopen in UNIX.Sequential reading, writing (with truncation), appending.Any reasonable combination of the above.Read or write a chunk of data (for an open file)Position in the file is unspecified (by the API), andoperations are sequential.Chunk size may be any size, and is not related to block size.Blocking operations, which return when completed or failed.Short reads: when not enough data is present completelyfulfill the request.Project 6Implementation DetailsThe semantics of filesOnly sequential access (no fseek);Read from the begin to end.Writes at the beginning, but cause truncation.Appending starts at the end of a file.Writing/appending causes files to adjust to accommodatethe data.Assume binary data (that is, don’t assumenull-termination or newlines).Concurrent access.A notion of a “cursor” that indicates read / write position.A separate cursor is maintained for each open file.Restrictions apply. See below for semantics.Stat returns the file size for files.Project 6Implementation DetailsThe semantics of directoriesCreation and deletion of directories affects thefilesystem.Change and get current directory.Current directory is a local, per-process parameter.Does not affect the filesystem.List contents of the current directory.Stat returns -2 for directories.Project 6Implementation DetailsThe API Iminifile_t minifile_creat(char*filename);minifile_t minifile_open(char*filename,char*mode);int minifile_read(minifile_t file,char*data,int maxlen);int minifile_write(minifile_t file,char*data,int len);int minifile_close(minifile_t file);int minifile_unlink(char*filename);int minifile_mkdir(char*dirname);int minifile_rmdir(char*dirname);Project 6Implementation DetailsThe API IIint minifile_stat(char*path);int minifile_cd(char*path);char**minifile_ls(char*path);char*minifile_pwd(void);Project 6Filesystem Structure1 Project Scope2 Implementation Details3 Filesystem Structure4 Concurrent Access5 ConsiderationsProject 6Filesystem StructureA picture is worth 1,000 wordssuperblockinodeinode...inodedata blockdata block...data blockProject 6Filesystem StructureThe superblocksuperblockinodeinode...inodedata blockdata block...data blockPoints to the root inode (the ’/’directory).Points to the first free inodea.Points to the first free data blockbHolds statistics about the filesystem:Number of free inodes and blocks.Overall filesystem size.Contains a magic number (the firstfour bytes)Helps to detect a legitimate filesystem.aif the free inodes form a linked listbif the free data blocks form a linked listProject 6Filesystem StructureThe inodessuperblockinodeinode...inodedata blockdata block...data blockCumulatively occupy ∼ 10% of diskspace.Hold information about the file anddirectory:Metadata, including type, size, etc..Data blocks occupied by the file.A few are directly addressable.A single block is an