Implement a restricted version of the Old File System as described in the sections that follow. You are to implement it in C and are allowed to use any standard libraries.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1   Overview

The Old File System (the original file system developed at Bell Labs) is the granddaddy of Unix filesystems. It divides each drive into a number of partitions, each of which may contain a file system. One file system never spans multiple partitions. A file system is described by its superblock, which contains the basic parameters of the file system which make it possible for the file system to find all the various components of the formatted partition: the number of data blocks in the system, a count of the maximum number of files, and an offset to the free block list.

Within the file system are files. Certain files are distinguished as directories and contain pointers to files that may themselves be directories. Every file has a descriptor associated with it called an inode. An inode contains information describing the file and an array of indices pointing to data blocks for the file. A file’s contents can be produced by specifying a file name, which is resolved to the specified file’s inode by parsing the individual parts of the file’s absolute path and retrieving directory data at each step as needed.

2     Assignment

Implement a restricted version of the Old File System as described in the sections that follow. You are to implement it in C and are allowed to use any standard libraries. The file system is to reside not in a partition on a disk, but rather in a single fixed-size (10MB) file. The interface to your file system will be a program (filefs) with command-line options for writing, reading, removing, and listing files contained in the file system.

3    Formatting

The fixed-size file that is acting as a stand-in for a disk partition will need to be formatted to provide some basic information about your file system each time it is opened by your program. The formatting will result in a superblock, free list, and inodes being written to your fixed-sized file. The superblock defines the file system, specifying the number of blocks available in the file system, the size and number of inodes, and potentially other useful information. The most straightforward free list might be implemented as a bit map of sufficient size to provide a bit for each block in the file system, specifying whether the corresponding block is free or used. Inodes should initially be unused. The blocks that are used for file data storage will appear after the superblock, free list,

and inodes. No action is required for the blocks themselves, since the only way they might be read or written is when the file system structures like the free list or inodes refer to them. Make the size of your file system 10MB. Do not turn your 10MB file system file in with your solution.

You can think of the file your file system will reside in as having roughly this structure:

<- 0 byte 10MB   ->

+------------------------------------------------------------------+

|	|	Free	|	|	|
|	Superblock  |	block	|	Inodes |	File  system data ...                       |
|	|	list	|	|	|

 

 

4   File Types

Your file system should support two file types, directories and regular files. Directories are basically implemented as regular files that are labeled as directories and only contain directory entries. Don’t worry about compacting directories as entries are added and removed, instead think about marking directory entries that belong to removed files as invalid, and potentially reusing them when a new file is written to that directory. No format should be assumed for regular files, you are only expected to be able to read and write these in their entirety. Keep in mind that files (and the files we call directories) will commonly span more than one block, and that the blocks need not be contiguous.

 

 

5    Inodes

Your inodes are to contain 100 direct block references. Don’t worry about indirect blocks. You are not reproducing a user environment, so you also don’t have to store the user, group and permissions information. I also don’t care about time stamps. Just focus on what will allow you to read and write a file in its entirety. Each block that the inode points to should be 512 bytes (your file system will apparently only handle smallish files). I will not be testing with more than 100 files, so have at least 100 inodes in your file system.

6   Functionality

 

Your program should allow files to be added to your file system, read and removed from it, and for the contents of the file system to be listed. It might be easiest to describe the intended functionality by providing examples of each. For example, the following command line invocation should list the contents of the example file system starting with the root directory:

./filefs -l -f example

The output might be a file system tree, showing the names of each directory and file contained within your file system (think about recursing through it starting with the root, adding a number of leading tabs to each line of output equivalent to the depth of recursion; similar to ‘ls -R‘).

The following invocation would add the specified file to your file system (as well as each directory in the path):

./filefs -a /a/b/c -f example

In this example, /a/b/c is the absolute path to an existing regular file c in /a/b/. The intended result is that your file system will likewise contain directory a, subdirectory b, and file c, with c’s contents being identical to the specified file’s. So, you’d find some free inodes and blocks and write directory entries to both /a and /a/b, then get another free inode for c, and copy c into your file system, repurposing free blocks and updating the block mapping in its inode as you perform the copy.

The following invocation would remove the specified file from your file system (as well as any directory that becomes empty after you remove the specified file):

./filefs -r /a/b/c -f example

So, if the only file in your file system is /a/b/c and you remove it as shown above, then listing the contents of the file system should result in nothing being printed, since both empty directories a and a/b would have been removed after c was removed.

The following invocation would read the contents of the specified file to stdout, then redirect that output to file foobar.

./filefs -e /a/b/c -f example > foobar

Reading a file’s contents in this manner should not result in the file being removed from your file system. There should be no difference between the original file and the data returned by your file system (diff should not indicate any differences between the original file and the extracted one).

7   Hard Requirements

 

Your file system should be self-contained; i.e. metadata and data comprising the file system should be inside of a single file, formatted according to your interpretation of the specifications.

• Your file system should work for any kind of file, text or

• Your file system should be able to support paths or filenames up to 255 characters

• Include an up-to-date Makefile. I don’t want to have to reproduce your

 

8   Grading

10 points if there is a reasonable attempt at a solution conforming to the original problem statement.

20 points if the file that is created to serve as the storage for your file system is formatted correctly.

20 points if files can be added to the file system (directories should be created in your file system as the specified input file’s path indicates).

20 points if the contents (directory and file names) of the file system are displayed when a listing is requested.

10 points if files can be removed from the file system. (listing contents of the file system no longer shows removed files)

20 points if files can be extracted from the file system. (file data returned via stdout matches the file data of the original that was previously added to your file system)

(extra credit: additional 100 points, making it possible to get 200/100 points for this project) (50 pts) When adding a new file to the archive, and after breaking the file up into blocks, only store those blocks that are not already present in the file system, otherwise make the new file’s inode refer to existing blocks. (50 pts) When removing files, ensure that blocks that are used by other files still remaining in the file system are not removed and that the files that shared blocks with the removed file extract fully and correctly

9  What to Turn In

Turn in 3 things as a group:

• txt containing information about your group.

A .tgz of your project directory, as before. (Include a design.txt file in which you explain where you made your changes and what the changes are intended to do (option 1) or what your design looks like and how you implemented it (option 2). Any additional information that would be useful for grading: testing, configuration, compiling, etc should go into a README file.)

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of