Operating Systems : Assignment 5Filesystem
DUE DATES
1. Introduction:
The task for this project is to use the block storage library created in Assignment 4 as a logical storage device, on top of which you are now going to build the F19 Filesystem F19FS. F19FS will closely model the original Unix Filesystem and the Unix Fast Filesystem.
Please review your class notes. Additionally, these references may be useful:
https:www.cs.berkeley.edubrewercs262FFS.pdf
http:en.wikipedia.orgwikiExtendedfilesystem
http:www.cs.cornell.educoursescs64102010falectures04filesystems.pdfhttps:en.wikipedia.orgwikiExt2
2. Filesystem Design:
Files and filesystems are designed to operate using an abstraction of the underlying storage hardware. You will implement a filesystem that interfaces to a Block Store similar to Assignment 4. Recall the Block Store library specifications; specifically, the purpose of the library is to simulate a block storage device that provides access to storage blocks based on a block index.
The following are the sizing constraints of the Block Store note these sizes differ from the block store assignment:
1. The total number of blocks is 216.
2. The size of blocks is fixed at 1024 bytes.
3. Some of these blocks are preallocated to the free block map as before.
The following are sizing constraints with regard to the file system itself. In particular, these constraints should allow you to pass the writefullfill test.
1. Any overhead metadata for your file system should be stored within 17 blocks.
2. If your overhead takes less than 17 blocks, say 16, then we waste the additional block.
3. Milestones:
This project will be divided into four submissions:
0. Milestone 0 Design,
1. Milestone 1,
2. Milestone 2, and
3. Milestone 3
All milestones after milestone 1 will provide code for the previous milestone for you to use as you wish. As
such, no late submissions will be accepted.
Each milestone also requires pseudocode for the next milestone. The pseudocode should be submitted as comments in the appropriate functions.
0. DESIGN: Submitted to Canvas as PDF by Monday 11411:59 PM
1. Milestone 1: Monday 111111:59 PM
2. Milestone 2: Monday 111811:59 PM
3. Milestone 3: Monday 12211:59 PM
Milestone 0Design:
A failure to plan is a plan to fail. This will be a large project; understanding the basic concepts, planning your structures, functions, and what issues can occur is vital to any programming project.
You are to draft pictorial representations of drawings on paper and scannedphotographed are sufficient:
1. Inodes and their block references
2. The filesystem layout, and how its layout relative to Back Store.
You are to put together your proposed layout read: structure definitions for:
1. F19FS objects
2. Inodes
3. Directory files
You are to write pseudocode for the following problems given the specified information and list potential errors that can occur:
1. FileDirectory Creation given an absolute path to the filedirectory and a flag indicating file or directory
2. File Writing given a file descriptor, a buffer, and a byte count
3. FileDirectory Deletion given an absolute path to the filedirectory
Once you have completed your draft designs, structure definitions, and pseudocode; collect them into a PDF document and submit them to Canvas by the M0 due date.
Milestone 1Basic Building Blocks:
You are to implement formatting, mounting, and unmounting fsformat, fsmount, and fsunmount of your F19FS filesystem. You will also prepare pseudocode for the following milestone.
Once you have completed your implementation, be sure to commit all changes and push to master branch on OSGit by the M1 due date.
Milestone 2Directory Traversal, Inodes, and File Descriptors:
You are to implement the creation of files and directories, the opening and closing of files, and the enumeration of directories fscreate, fsopen, fsclose, and fsgetdir. You will also prepare pseudocode for the following milestone.
Once you have completed your implementation, be sure to commit all changes and push to master branch on OSGit by the M2 due date.
Milestone 3Data management:
You are to implement the reading and writing of data to a file, the seeking of file descriptors, and the deletion of files as well as empty directories, fsseek, and fsremove.
Graduate students will also need to submit implementation for the moving files and directories as well as the creation of hardlinks fsmove and fslink. This will also be bonus for undergrads. It is suggested that you start early on these features, as you will need to consider these operations while implementing Milestone 2.
Once you have completed your implementation, be sure to commit all changes and push to master branch on OSGit by the M3 due date.
fsread,
fswrite
4. Filesystem Specification, Implementation, and API:
Your implementation of the F19 Filesystem must be a CMake system library project. A header with the expected functions and operation details will be located in your repository. Please refer to it for implementation details and bring any additional questions to the Canvas LMS.
Specifications:
Your F19FS implementation must be capable of:
Format an F19FS file
Mount and unmount an F19FS file
Create directories and regular files
Open, close, and seek files
Read and write to files
Remove files
List directory contents
Move files and directories
Create hardlinks
The F19FS filesystem will incorporate file descriptors as an intermediary for operating on files, and they will be used much like they are in a POSIXcompliant OS.
Structuring the F19FS
Regarding inodes:
Each inode will be exactly 64 bytes. The general inode structure is as follows: MetadataACL: bytes 047
Data Block Pointers: bytes 4863
The inode table will be 16 KB in size, i.e., 16 data blocks worth of inodes. Inodes will use 16bit addressing for block references. Your filesystem root directory must be located at the first inode.
Regarding block pointers:
Inodes contain 8 block pointers: 6 direct, 1 indirect, and 1 double indirect. Direct pointers, as the name suggests, are the id numbers of the data blocks that make up the file. Indirect pointers point to a data block that is made of direct pointers. A double indirect pointer points to a block of data that is made of indirect pointers. Indirect and double indirect pointers greatly increase the maximum size of a file while the direct pointers allow for quick and simple access to small files.
Regular File Block Structure:
The regular file blocks have no structure, they are pure data. Be sure to keep track of the files size somewhere in your inode metadata!
Directory File Block Structure:
To simplify the filesystem, directory files will be limited to 31 entries. Each entry will consist of:
1. The files name: 32 bytes
2. The files inode number: 1 byte
This allows a directory to be contained on a single data block. The remaining space on the directorys data block should be allocated to MetadataACL as you see fit.
Note that creating an empty directory requires only an inode. However, as soon as a file or subdirectory for that matter is created within that directory, it will be necessary to allocate space for the directory block. This is important in order to assure that you pass all of the tests correctly.
File Descriptors:
The F19FS filesystem will be using file descriptors to manage open files. The filesystem will be limited to 256 file descriptors. Each file descriptor will track a single readwrite position for that descriptor. How you manage this is up to you. Files should be able to be opened multiple times, meaning your implementation should support multiple descriptors to the same file, but with different readwrite positions. Seeking allows the user to move the readwrite position to where they want. Be sure to read the header for additional notes or requirements on how a function affects a file descriptor.
Hardlinks:
Hard links allow for multiple references to the same file on a disk, typically in a way that is invisible to the user. In F19FS, this is achieved by decoupling the files name from the files contents. With F19FS, there is no differentiation between the original file and the hardlinked file i.e. there is no original. A hardlinked file must have all links removed before the file will have its resources released. An inode cannot be referenced more than 255 times.
Testing:
Your implementation should be capable of doing all operations listed above cleanly and safely. Like all projects, a tester will be provided to test the frontend of your implementation. You will be expected to deliver a functional and correct solution for each milestone. Be sure to be comfortable with various debugging and file inspection tools, and they will prove vital to writing a correct implementation.
5. Rubric:
Milestone 0 Design
50 points
Milestone 1
100 points
Milestone 2
150 points
Milestone 3
200 points
Total
500 points
For all students, for all milestones:
Insufficient Parameter Validation: up to 25 of rubric score Insufficient Error Checking: up to 25 of rubric score Insufficient Comments: up to 25 of rubric score
Incorrect implementation: up to 50 of rubric score Memory Leaks: up to 20 of rubric score
Submission compiles with warnings: 90 of rubric score
Submission does not compile, or refuses to build: 100 of rubric score
Reviews
There are no reviews yet.