The Ziggy filesystem (we came up with the name while watching the movie Vibes) is designed to be as dynamic as it can be, without causing too many headaches. Basically, the project specifications (up to the 95% level) specify everything to be handled statically in memory. The 95-100% level specs (which Ziggy is designed to handle) are such that the project will be much more like an actual filesystem, including the requirement that the program interface with a file on disk which in the project's view is a disk. However, the project specifications are also limited to mostly static parameters (block size=256 bytes/block, maximum of 30 entries per directory, 1024 blocks on the disk, etc.) Ziggy was designed with the premise that since the above is possible, a little extra work would allow for completely dynamic values for the above parameters.

Technical Data

Structure of a disk w/ Ziggy FS

The Filesystem Information Block (FIB)

The FIB is located at block #1, and it contains all of the information needed for the operation of the dynamic filesystem (it is much like a Superblock from the *NIX type filesystems.) The information stored in the FIB:

• Disk Size - 2 bytes - The number of blocks within the disk. (Default=1024)
• Number of Inodes - 2 bytes - The total number of i-nodes. (Default=32)
• Start Inode Block - 2 bytes - The start of the i-node block range can change, depending on the size of the disk and the number of i-nodes (and therefore, the number of blocks used by the i-node/disk bitmaps). This value will cut down on the mathematics needed by the program to figure out where to read the i-nodes from per access. (For this project, 3)
• Start Data Block - 2 bytes - The start of the data block range using the same reasons as the Start Inode Block. (For this project, 6)
• Bytes Per Block - 2 bytes - This is the physical number of bytes contained within a block. (Default=256)
• Number of Free Inodes - 2 bytes - Number of Free Inodes
• Number of Free Data Blocks - 2 bytes - Number of Free Data Blocks

All of the above fields are set at format (initialization) time, along with the creation of the root directory (inode 0, block 6).

Inode/Data Bitmaps

In memory, keeping track of which i-nodes and data blocks are free or used is handled by the use of two seperate bitmaps. Basically, each bit in a character array (ie: string) defines whether or not corresponding block/i-node is free or used. If the bit is not set (0), then the block/i-node is free. If the bit is set (1), then the block/i-node is used.

I-Nodes

Each i-node only uses 18 bytes. We figured this would waste lots of space on the disk if we used the 1 block per i-node method (for this project, it would waste 238 bytes per block, or a grand total of 7616 bytes =~ 7.4k.) Therefore, each disk block will hold 14 i-nodes, so for this assignment, the i-nodes will use 3 disk blocks. The structure of a Ziggy i-node:

• Block Type - 2 bytes - For this project, file or directory. Used to tell the different blocks apart, also good if the user tries to do directory commands ((ch/rm/mk)dir) on a file, or visa-versa.
• Size - 2 bytes - The size of the file, in blocks.
• Direct Blocks - 12 bytes - This is a set of blocks (6) that are directly addressed by the inode (each of the six direct block numbers are 2 bytes in length, therefore 12 bytes total.)
• Core Indirect Block (CIB) - 2 bytes - This project's version of a *NIX Indirect block. The CIB is a block (in the data section of the disk) which contains 2 byte block numbers which are also part of the file.

The above descriptions assume a basic knowledge about *NIX style i-nodes.

Algorithms Used Within the Program

Inode/Directory Cache

Per the project specifications, there is a cache for inodes and directories, each keep 10 respective entries. We're still thinking about making the cache size dynamic, but it's a low priority at the moment. All commands will access both i-nodes and directories. When either data type is requested, the cache is checked to see if the data is already in memory. If so, it is returned. If not, the data is read off of the disk, put into the cache, and then gets returned.

To make things a little more efficient, we've designed in a write-cache, based on the read cache. Basically, whenever new data is added to the cache, the oldest entry has to be removed (assuming a full cache.) Each cache entry will have the actual data in the cache (i-node or directory), an identifier (i-nodes have the i-node number, directories have the corresponding i-node number), and also a modified flag. When the oldest entry is removed, the modified flag is examined. If set, the data is written out to disk. The theory goes like this:

Read-Only Cache - Worst Case Scenario: All commands that change data (either i-node, directory, or both) will have to read in the data from the disk, change the data, and then write it to the disk. Therefore, worst case has 2 disk accesses per change.

Our Read-Write Cache - Worst Case Scenario: The first 10 changes will only have to read from the disk. The cache will store the data. After the cache is filled, then all changes will require the same number of disk access as the Read-Only Cache.

However, the Average Case for Read-Only is the same as the Worst Case (Read and Write per change). The Average Case for the Read-Write Cache though is much better as changes will most likely be to the same i-node/directory, so the cache can just change it's data without needing to write anything to the disk.

Another reason to do the Write-Cache is due to the fact that any changes that need to be written to disk, also need to be written to the cache. Otherwise the next time the data is read from the cache, it will be out of date. Since you're half-way to having a write-cache, a small change in the remove-from-cache routine gives you a fully functional read-write cache, which is (worst case) only as efficient as the read-only cache.

Directory Entries

A directory entry is made up of the directory name (max of 13 characters - 14 bytes (it's null terminated)), and the i-node number (2 bytes) for it's entries. The i-node number comes first in the entry, and then the filename. The directory blocks are made up of a number of entries (including the '.' and '..' directories). It's pretty straight-forward.

Current Working Directory

This is very simple... The CWD's i-node number is stored in memory.

VFS-like Interface

Planning ahead for Project 3 (extending this project to be a distributed filesystem), we've designed a standardized interface to the file system, which will then interface with a disk, be it local or remote. (Obviously for this project, the disk is local.) This will at least be partially implemented in this project, but the complete implementation will occur after the requirements for Project 3 are made public.

Future Possible Implementation Options

• Disk Corruption Check - Kind of like the MS-DOS program 'chkdsk'. Check to see that the bitmap is correctly representing free/used blocks, check for cross-linked blocks, etc.