DESIGNING A WRITE-ONCE FILE SYSTEM

A general-purpose optical storage software technology

Although a binary search across the disk requires much "seeking" (movement of the optical head), each seek is precisely half the distance of the previous seek. If there are N blocks on the disk, the total number of seeks is guaranteed to be LOG2(N). In practice, WOFS takes less than four seconds to find the last written block on a 5.25-inch optical disk drive.

Transactions and Filemaps

WOFS writes to the optical disk in groups of operations called transactions. A transaction might be creating a file, changing its data, or erasing a file or directory; it also might consist of many operations grouped together. At the end of each transaction, WOFS writes a special block called the End of Transaction Block, or EOT.

When a disk is mounted, WOFS locates the last written block on the drive and checks to see if it is an EOT. If it isn't, then the last transaction was interrupted by a hardware failure (for example, a loss of power or a pulled cable); WOFS then searches backwards on the disk, block-by-block, to find the last complete transaction.

Every EOT contains a pointer to a block (or blocks, if necessary) that stores a list of current directories. The first directory in the list is the root directory.

Additional fields in the EOT are used to maintain the disk volume name and accounting information, such as the time of the last transaction. The EOT also has a pointer to the previous EOT, which is used for stepping the disk into the past.

WOFS uses the same basic structure to remember where both files and directories are stored. We call it a fragment table, but it can be thought of as a list of regions on the disk where data is located and pointers that tell the file system how to assemble the data into a continuous file.

When a file that has been written is closed (or when a modified directory entry is written to the disk), WOFS writes two additional blocks to the disk for that file: a "filemap," and a "file header."

The filemap is the database that tells WOFS where on the disk the data in the logical file is actually written. Each record in the database has three fields:

Ordinal (the byte position in the logical file where this data fragment starts)

Length (the number of bytes in this data fragment)

Starting block (the point on the disk where the data fragment is located)

Because WOFS writes most files contiguously on the optical disk, most files are represented by a single fragment. For example, a file consisting of 65,536 bytes starting at block 1000 might have a filemap that looked like that in Figure 1.

The filemap allows programs that update records within a file (such as database programs) to be used with the optical disk. If a program were to reopen file AAA, as in Figure 1, and rewrite the first 1024 bytes of the file with new information, the new filemap might look like that shown in Figure 2 when the file is closed (assuming a disk-block size of 512 bytes).

If this file is then opened for reading, WOFS will return to the calling program the 1024 bytes starting at block 1140, followed by the 64,512 bytes that start at block 1024.

Of course, the filemap for version 1 of file AAA is still on the write-once disk; the user can still access the original version of the file by reading the file with the first filemap instead of the second. A special function allows the calling program to find out which version of the file it is reading. Another special function is provided which can step individual files -- or an entire optical cartridge -- backwards in time.

At the heart of WOFS is a set of state machines that manipulate filemaps and transfer information to and from the optical disk. These state machines provide many standard file-system functions, as well as some that are only possible because of the WOFS filemaps. These functions include the following:

filestr_seek
filestr_read
filestr_write
filestr_insert
filestr_delete
filestr_check

The filestr_seek function repositions the file pointer in much the same way as lseek( ). Likewise, filestr_read works like read( ), and filestr_write is like write( ). The function filestr_insert has no equivalent in other file systems. This function opens up the file and inserts bytes at the current position within the file, making the file longer. A converse function, filestr_delete, also has no standard equivalent, and deletes bytes at the current position, making the file smaller.

Finally, filestr_check provides a consistency check, by checking the variables used by the state machines for self-consistency. Frequently, use of this function made it relatively easy to find and isolate programming errors during the file system's development.

The Insert and Delete functions are used primarily to maintain directories; by keeping the directory entries in sorted order, WOFS reduces the average time needed to create a file by a factor of two.

The state machines are optimized to transfer data directly between the optical disk interface and user memory when more than a complete block of data is transferred. Thus, WOFS often performs reads and writes of large files at the maximum possible transfer rate of the hardware.

Directory Entries

All of the operations that file systems perform can be broken down into four main categories:

Looking up a name in a directory

Making an entry in a directory (for a file or a subdirectory)

Removing an entry in a directory

Transferring data between an open file (or directory) and the operating systems

To resolve a filename, WOFS starts at the root directory and searches for the names of each successive subdirectory, one-by-one. Eventually, WOFS determines the location on the disk of the file's containing directory. These translations are cached, which substantially improves the file system's performance.

Like the data in files, each WOFS subdirectory is stored in one or more fragments. The actual directory entries are built out of one or more variable-length records. The contents of a directory entry are shown in Figure 3.

Figure 3: Contents of a directory entry

  * directory entry flag (0x00001000, used for
    byte-swap detection)
  * size of directory entry
  * file type
  * modification time
  * file version number
  * x,y location (for Macintosh OS)
  * file header location
  * file length in bytes
  * filename

The first four bytes of the directory record are the directory entry flag, 0x00001000. If WOFS reads 0x00100000 instead of 0x00001000, all of the binary values stored in the directory entry are byte-swapped. This might happen if the directory entry was written by a VAX and read back by a SPARC microprocessor -- the VAX and the SPARC store the same binary value in the reverse order. By detecting byte-swaps and swapping the data back, WOFS allows cartridges written with one byte order to be read back on a system that uses another.

WOFS only swaps on read. If WOFS running on a SPARC updates a directory written by WOFS running on a VAX, it does not swap the binary values back before writing. Chances are that data written by one microprocessor will be read back by that same microprocessor; if the directory entry is eventually read again by a VAX, the VAX will swap the data when it reads it.

Directory entries are created with the filestr_insert( ) function; likewise, they are deleted with the filestr_delete( ) function. A function called wofsfile_readdir( ) reads directory entries and translates them into a form appropriate for Unix, MS-DOS, or the Macintosh operating system.

When a file is opened for reading or writing, that file's fragment table is loaded into memory and a state machine is set up to handle data transfer. When the file is closed, the fragment table is written back to the optical disk, followed by a file header.

Individual Files

Every WOFS file has a file header. File headers contain all of the information in the directory entry -- allowing the directory entry to be reconstructed in the event of media damage -- as well as additional information used by operating systems other than MS-DOS. File headers can be extended to include security-related information such as access control lists used by newer, security-conscious operating systems. Normally, however, the file header is used only by WOFS and remains invisible to the user.

The file header fits within a single WORM block. The information it contains is shown in Figure 4.

Figure 4: Contents of the file header block

  * File header version number
  * File number
  * File type
  * File version number
  * Location of previous version
  * Directory number of containing
    directory
  * Filename (without directory name prefix)
  * Time of last write
  * Time of file creation
  * Number of bytes in file
  * x,y (for Macintosh OS)
  * Location on disk of fragment table
  * Number of fragments in fragment
    table
  * Name and version of operating
    system that created file
  * Name of site that created file

File System Blocks

EOTs, File Headers, and Fragment Tables are all stored on the optical disk within a special kind of data structure called a File System Block (FSB). The FSB has a special 12-byte header that makes it possible to identify the block in the event of a media failure, which allows for quick and reliable recovery of the data on the WORM disk.

The FSB header contains a 4-byte FSB flag, a 4-byte "type" field which indicates whether the FSB holds an EOT, a file header or a fragment table, and a 4-byte self-referential pointer that contains the disk block address where the FSB was actually written. In C, the FSB has the structure shown in Figure 5.

Figure 5: FSB structure declarations

  typedef struct {
      u_long   flag;
      u_long   location;
      u_long   type;
  } fs_hdr;

  typedef struct {
      fs_hdr   hdr;
      char     data[ BLOCK_SIZE - sizeof(fs_hdr) ];
  } fs_block;

In the event of media failure, the user can scan the entire optical cartridge with a special recovery program that searches for FSBs that hold file headers. The entire directory hierarchy can then be automatically recovered. In practice, this procedure takes less than 20 minutes for a 400-Mbyte cartridge.

Identifying a file-system block by both self-referential pointer and 4-byte flag minimizes the chance that a random block of data will appear to be an FSB.

WOFS also uses the FSB to allow implementations running on computers with one byte order to use files written by implementations using another byte order. If the WOFS function that reads the EOT discovers that the byte order of the FSB flag is reversed, it reverses the byte order of every 4-byte integer value stored in the EOT. Like the byte-swapping for directory entries, this swapping happens only on read operations. When the EOT is written to the disk at the conclusion of the next transaction, it is written in the new byte order. The functions which read file headers and fragment tables swap similarly when necessary.