Goal: The primary goal
of this assignment is to build files from the block allocating
and deallocating routines of the last assignment. This will include
the implementation of UNIX-like directories, inodes, and (optionally)
sub-directories. The descriptions below apply to all but the
95%-above implementations. If your group does not have a working
solution to assignment #1, please see me.
Grading Leftovers: The
% grade your group receives on this assignment will be multiplied
by 50% of the total number of points missed on the last assignment,
and that total will be added to last project's grade. For example,
55/75 last time == 20 missed points, 100% on this project will
change last project's grade from 55 to 65.
Root Directory: The root
directory will support 30 unique entries, each containing a 2-byte
inode number and a null-terminated filename <= 14 bytes in
length. The root directory (a global array of directory entry
structures) need not have any disk blocks allocated to it. Entries
in this structure should be allocated from the lowest index available.
Inodes: The inodes should
contain a type field (although we only support file and directory
types), 6 direct block numbers, and 1 single-indirect block number.
The system should contain 32 inodes. This global array of inodes
need not have any disk blocks allocated to it. Inodes should
be allocated from this array from the lowest index available.
Core Indirect Blocks:
When the system creates (or extends) files larger than what can
be addressed by the 6 direct blocks, it will need to allocate
and manage an indirect block. For most of the implementation
levels, these blocks can be allocated statically and stored in
memory as a global array of CIBs. Each CIB will contain: a) the
id of the disk block it represents (returned from the allocate
routine) and b) the actual contents of the disk block (namely,
a list of 2-byte block numbers). CIBs should be allocated from
the lowest index available.
Operations (70-85% level): (basic file/directory operations)
New Filename NumBlocks
Extend Filename NumBlocks
Truncate Filename NumBlocks
Delete Filename
Short
Long
Most of these operations are self-explanatory. New
(when successful) should acquire a directory entry, an inode,
and (if needed) a CIB. New and extend (when successful) should
both acquire blocks from the store of 1024 blocks (numbered from
1-1024), and (optionally) acquire a CIB. Truncate and delete
(when successful) should return their blocks, inodes, and directory
entries to the store of available structures. Short and long
should provide directory listings (short containing only filenames
and inode numbers, long containing filenames, inode numbers, and
a list of allocated blocks (including CIBs).
(cont'd)
New should fail if the file already exists, and/or
if there are not enough blocks, inodes, and/or directory entries.
Extend should fail if the file doesn't exist or if there are
not enough blocks to meet the request. Truncate should fail if
the file doesn't exist or if no blocks are allocated to it (if
NumBlocks > OwnedBlocks the file should be truncated to length==0).
Delete should fail if the file doesn't exist.
Operations (85-95% level):
(basic file/directory operations plus sub-directory support)
Mkdir DirectoryName
Chdir DirectoryName
Rmdir DirectoryName
For this implementation the system will start in
the root directory and maintain a (global is fine) "current
directory". All file operations are assumed to apply to
the current directory (no absolute pathnames). Each operation
should fail if the DirectoryName parameter does not exist in the
active context. "C .." (and "C /") should
be supported to move up one level in the directory (or to move
directly to the root). Rmdir should fail if the sub-directory
is not empty.
Operations (95-100% level):
(file/directory/sub-directory ops with caching and restart)
This level is significantly harder than the preceeding
level. It is provided for those who find the first levels to
be trivial and are motivated more by approximating real systems
than by points. The additional constraints include: dynamically
allocated CIB's, cached directory entries and inodes (keeping
only 10 (of each) of the most recently referenced structures in
memory), and storing (with the option of reloading) the filesystem
on disk. To support this, the directory and inodes will need
to use disk blocks from the 1024 available. Any data that needs
to be written to disk (or read from disk) should be stored in
a real file using the same format that would be used in a real
file system (binary format, treated as if the 1 file were the
disk). Since none of the files have real contents, only the directory(s),
inodes, and indirect blocks really need to be written. If your
group plans to implement this level, you must decide what constitutes
a good design (and what constitutes a good design presentation),
present it to Kevin and I, and have it approved before Wednesday
12/4 at 5:00pm.
Data Files: The format
for the datafiles will adhere strictly to what is shown above.
The first character will be one of those shown to be a valid
opcode. If additional parameters are required by the operation
they will occur beginning in the 3rd byte of the line
(after a space character) and be further delimited by single space
characters. No lines will contain trailing whitespace.
What to turn in: This
assignment requires the same paper submission required in assignment
#1 (one page per group, listing the members, signed by each, each
member's % contribution, a sentence or two describing each member's
contribution, step by step instructions for compiling and running
the code, and the %-level of completed implementation). In addition
to this sheet, and using turnin to submit your code and a makefile,
each team will also create and submit their own input file for
testing (also sumbitted with turnin). 5% of the project's grade
will be based on the quality of tests (not quantity) provided
in the testfile. The test file you submit should be as short
as possible, while still demonstrating the maximum capacity/correctness
of your program.
Sample Data & Output:
Below is a sample data file and the corresponding
output. The output reflects the implicit requirement that the
system report what is happening with inodes and blocks as they
are allocated and deallocated. Your output should be short, but
clear. If you have any doubt about my opinions regarding "short"
and/or "clear", your safest bet is to match the sample
output character for character.
N TestFile.One 6
N lkj 0
N TestTwo 3
N lkjlkj 8
D TestTwo
N lkjlkj 3
E TestFile.One 5
E TestFile.One 2000
E lkjlkjlkj 22
N TheTest 8
N lkjlkjlkj 3
N lkjlkjsdf 4000
D lkj
T lkjlkjlkj 1
L
new TestFile.One: ok,
0 inode, 6 blocks (1 2 3 4 5 6 )
new lkj: ok,
1 inode, 0 blocks ()
new TestTwo: ok,
2 inode, 3 blocks (7 8 9 )
new lkjlkj: ok,
3 inode, 8 blocks (10 11 12 13 14 15 [17] 16 18 )
delete TestTwo: ok,
free inode 2, free blocks (7 8 9 )
new lkjlkj: failed,
file already exists
extend TestFile.One: ok,
by 5 blocks ([8] 7 9 19 20 21 )
extend TestFile.One: failed,
insufficient space (A=1003, N=2000)
extend lkjlkjlkj: failed,
file doesn't exist
new TheTest: ok,
2 inode, 8 blocks (22 23 24 25 26 27 [29] 28 30 )
new lkjlkjlkj: ok,
4 inode, 3 blocks (31 32 33 )
new lkjlkjsdf: failed,
insufficient space (A=991, N=4000)
delete lkj: ok,
free inode 1, free blocks ()
trunc lkjlkjlkj: ok,
free blocks (33 )
Long Directory: (inode, data
blocks, [iblocks])
TestFile.One: 0 (1 2 3 4
5 6 [8] 7 9 19 20 21 )
TheTest: 2 (22 23 24
25 26 27 [29] 28 30 )
lkjlkj: 3 (10 11 12
13 14 15 [17] 16 18 )
lkjlkjlkj: 4 (31 32 )