A Simple File Manager
In this exercise, you will write a simple space file manager. In doing so, you will make a number of simplifying assumptions:
- Your on-disk file descriptor will fit into one disk block. It should contain (1) a filename of six or fewer characters (2) at most four disk
blocks per file (you can use 2-byte block addresses)
- The disk blocks are small, e.g. 50 bytes per block
- Directories can contain the smallest amount of information possible, just enough to get your file manager working
- Don't implement file sharing (no locks)
- Don't implement file modes (read,write,execute)
- Don't include protection in your file system
- Don't implement path names, just filenames within the current directory
- Don't implement buffering
Part A
The file manager should implement the following API;
int fLs();
int fOpen(char *name);
int fClose(in fileID);
int fRead(in fileID,char *buffer,int length);
int fSeek(int fileID,int position);
Generally, fOpen(),fClose(),fRead(),and fSeek() functions should behave like the UNIX kernel functions open(),close(),read(), and lseek()
respectively. The behavior will be modified by your asumptions, of course. For example, fOpen() does not have a flag parameter, so your function should
operate as if O_RDWR | O_CREAT were used in the kernel function equivalent. The fLs() fuinction should print all of the information your systme knows
about the file, then return -1 if you detect an error and 0 otherwise.
Use the follwoing disk interface:
#define NUM_BLOCKS 100
#define BLOCK_SIZE 50
void initDisk();
int dRead(int addr, char *buf);
You may also add a few more routines to the API-for example if you wish to initialize the file manager prior to using it the first time. Although
it is not necessary, you can add a fcntl/ioctl command if you need one.
Part B
The file manager must contain the following API:
int fMkdir(char *name);
int fCd(char *name);
int fWrite(int fileID, char *buffer, int length);
Generally, the fWrite() functions should behave like the UNIX kernel write() function, except with behavior that is simplified by the
assumptions. It returns the number of bytes actually written by the function call. The fMkdir() function should create the named directory, then
return -1 if you detect an error and 0 otherwise. The fCd() function should change the current directory to the named directory if it exists, then
return -1 if you detect an error and 0 otherwise.
Part C
Write a driver program that tests each function and feature, e.g. sub-directories.
Background
This section will help with the organization of your file system
Disk Layout
When a disk is formatted, it is done so with the expectation that the file manager will access certain information which it needs in
fixed locations. You will need to define your own format for your simulated disk.
File Descriptors
When the file manager laods the external file descriptor into primary memory, it copies all of the information
from the disk representation,a ndadds other information that it need to manage the open file. For example, the external file descriptor
does not indicate which user and process currently has the file open or what the current location is for the file pointer.
When the file is opened, the file manager looks up the file in the directory to obtain the inode. The inode is copied into a
memory-resident set of inodes. The file manager then creates an entry in the file table that will contain the new dynamic information
needed by the process when the file is open (e.g the struct file defintion in /usr/src/linux/include/linux/fs.h). The file table entry
references the inode. Finally, the file manager creates an entry in the process's file descriptor table; this entry establishes the "file
identification number" returned by the open command and points to the file table entry.
Directories
A directory entry must contain enough information to allow the file manager to match a character string filename
with the entry's name and to find the external file descriptor on the disk if the names match. In a UNIX system, the directory entry
must have only the name and the inode number for the file. To list the files in a directory, the file manager traverses the directory contents,
printing the name from each entry and then retrieving any other information to be included in the listing directly from the inode.
The layout for a directory entry is shown in the table below. All multibyte integers are in little-endian order, meaning that the least significant
bit is stored first.
Offset | Length | Description |
0x00 | 8 | Filename |
0x08 | 3 | Extension |
0x0B | 1 | Bit field for attributes |
0x0C | 10 | Reserved |
0x16 | 2 | Time |
0x18 | 2 | Date |
0x1 | 2 | Starting cluster number A |
0x1C | 4 | File size in bytes |
The filename and extension are stored as uppercase ASCII characters. Invalid entries have names beginning with 0x00(the entry has not been used before)
or 0xe5(the entry was used before, but has been released). The starting cluster(sector) number cannot reference serctors used for teh boot record or the
root directory. Hence if the starting clsuter number is k, it acttually refers to logical sector number 31+k.
The attribute byte stores bits for attributes, similar to UNIX. The bit fields are shown in the table below. Bit 0 is the least significant bit. A bit
set to 1 means that the file has that attribute, and 0 means it does not have it.
Bit | Mask | Atribute |
0 | 0x01 | Read-only |
1 | 0x02 | Hidden |
2 | 0x04 | System |
3 | 0x08 | Volume lable |
4 | 0x10 | Subdirectory |
5 | 0x20 | Archive |
6 | 0x40 | Unused |
7 | 0x80 | Unused |
Attacking the Problem
You need to create a disk layout and file descriptor formats. You are given a disk interface are are required to provide an API.
Disk Interface
The virtual disk is implemented s blocks of primary memory. It includes a statement to randomly produce disk read and write errors. You can change the threshold
of the statment. Here is code on which to base your virtual disk code.
disk.h
#include
#include NUM_BLOCKS 100
#incldue BLOCK_SIZE 50
#include RELIABILITY 0.95
#include PERIOD 2147483647.0
#include ERROR 0
#include NO_ERROR 1
#include NULL 0
void initDisk();
int dRead(int addr,char *buf);
int dWrite(int addr, char *buf);
disk.cs
#include
#include "disk.h"
static int threshold;
static char *bList[NUM_BLOCKS];
void initDisk() {
int i:
for(i=0; i
threshold = (int) (RELIABILITY*PERIOD);
sleep(3);
}
int dRead(int addr,char *buf){
int i;
char *bufPtr;
if(addr >= NUM_BLOCKS) return error;
if(rand() > threshold)return error;
if(bList[addr] != NULL {
bufPtr=bList[addr];
for(i=0; i
}
else
for(i=0;i
return no_error;
}
int dWrite(int addr, char *buf) {
int i;
char *bufPtr;
if(addr>=NUM_BLOCLS) return error;
if(rand()>threshold) return error;
if(bList[addr]==NULL)
bList[addr]=(char*)malloc(BLOCK_SIZE);
bufPtr=bList[addr];
for(i=0;i
*bufPtr++=buf[i];
return no_error;
}
This virtual disk statically allocates 100 blocks of 50 bytes each, then reads and writes those with the possibility of I/O failure. You may change the
block size and the reliability values.
Game Plan
- The disk simulation code does not format the disk. You will need to design your own low-level format. No bootstrap area is needed, but information on the
layout of the disk and the root directory are going to be needed. You will need to decide how inodes are laid out on the disk(use inodes please)
- Design your directories. You need to be able to associate a name and a file descriptor. Then implement the root directory.
- Build a tool which creates a simple file system with a root dierctory and a few files. Build a tool which dumps the virtual disk contents so that you can
analyze it as you design it and also debug it.
- Implement your first version of the fls() command which works only on the file system root directory. After implementing subdirectories, you can finish
fls().
- Design and implement the file descriptor and the open-file data structure(s).
- Implement the commands on the API. Start with the commands which only read the directory and don't write to it.
- Implement the file operations-open/close and read/write. Start with the reads.
- Implement a fWrite(), which means that you need to do block allocation.
- Implement subdirectories.
- Implement fmkdir() and fCD().
Write your driver program as you are developing the parts. When you implement fLs(), your driver only needs to invoke the fLs() function.
Test your program as you go along.