Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/std_unix/volume.20/text0003.txt

Internet Message Format | 1990-08-02 | 9.0 KB

From: <[e-mail]>


           An Update on UNIX*-Related Standards Activities

                               May 1990

                 USENIX Standards Watchdog Committee

                   Jeffrey S. Haemer, Report Editor

ANSI X3B11.1: WORM File Systems

Andrew Hume <[e-mail]> reports on the April 17-19, 1990
meeting in Tucson, AZ:

Introduction

X3B11.1 is working on a standard for file interchange on write-once,
non-sequential (random access) media: a portable file system for
WORMs.  This was our fourth meeting.  With many major issues somewhat
settled, our main, remaining decisions are how to implement directory
hierarchies and how to manage free space.

Multi-Volume Sets

WORM file systems store a fair amount of information per file (such as
most of the fields in struct stat), per directory, per partition, and
per volume.  A volume is a logical address space associated with a
piece of physical media.  For example, a WORM disk that can only be
accessed one side at a time would be two volumes.  Each volume has a
label block describing its size, partitions, directory hierarchies,
free-space management, and so on.  (Free-space management is discussed
below; for now, this could mean a pointer to the next free block.)

Informally, multi-volume sets means files and directories can be
spread over several volumes.  Here are some requirements for this
feature:

   - A file can be bigger than a volume (file sizes are limited to
     2**64 bytes).

   - You can append to a file.

   - You can update any part of a file.

   - All volumes need not be simultaneously accessible.  (That is, if
     you have a three-volume volume set, you don't need three drives.)

__________

  * UNIX is a registered trademark of AT&T in the U.S. and other
    countries.

May 1990 Standards Update              ANSI X3B11.1: WORM File Systems


                                - 2 -

   - Each volume, and the whole volume set, must be consistent after
     an update.

   - Usable, although perhaps not fast, on a single drive.  The idea
     is that you can't mandate that the control structures for the
     volume set be distributed over the set, because that would mean
     that on single-drive systems, users might have to mount every
     volume to recover even a single file.  We would like to require
     only that the user mount the volume the file is on and perhaps
     one other (the master volume).

   - Each volume must be self-contained (for disaster recovery),

   - Security control is per volume, directory, and file.

After convincing ourselves that we all spoke roughly the same
language, we came to consensus decisions for the following questions:

   - Can a file description point to extents (files are spread across
     a list of extents) on later volumes? (Yes)

   - Can a directory entry point to a file description on a later
     volume? (Yes)

   - Must a directory be completely contained on a single volume? (No)
     Why?  There's no reason to require it.  All implementations are
     likely to use the same primitives to manage files and directories
     (that is, they'll implement directories as files); if you can
     handle multi-volume files correctly, directories should be easy
     too.  Some people were concerned about being able to get the
     directory in one (more or less) I/O or block (especially for MS-
     DOS) but that can't happen in general; directories and files are
     likely to be spread all over the volume.

   - must all the file descriptions for a single directory hierarchy
     fit on a single volume? (no)

   - should each volume of a volume set point to the volume describing
     the root of the main directory hierarchy for that set? (yes)

The above involve subtleties not readily apparent; details available
on request.

Directory Hierarchies

Much discussion centered on how to implement directory hierarchies --
at least, after our initial surprise discovery that we are committed
to support multiple directory hierarchies.  This commitment comes from
the CD-ROM standard, ISO 9660, where the intent was to have an ASCII
directory tree and one or more national-character-set trees.

May 1990 Standards Update              ANSI X3B11.1: WORM File Systems


                                - 3 -

[Editor: CD-ROMs, like WORMs, are on write-only media, but solve
different problems.  Both provide tremendous storage capacity, but
CD-ROMs appear to the user to be read-only, while WORMs appear to
provide read and write access.  Nevertheless, on WORMs, writing to a
file means either appending characters to a pre-allocated chunk of
disk, or rewriting a new version of the file in a new place.  Once a
file, or file version, is discarded, the piece of the physical medium
it's stored on is forever lost, not released for re-use.  CD-ROMs are
for storing the Encyclopedia Britannica; WORMs are for storing
backups.  ]

Our basic choice is between what I call the scattered directory tree,
which is much like the standard, UNIX file system, and path tables
(linearized encodings of the tree structure).  ISO 9660 supports both.
Scattered directories are simpler to deal with and somewhat easier to
update, but probably slow to access because they require too much
seeking.  Path tables seem faster at first glance (large contiguous
reads, etc.), but their simplicity and speed seem to evaporate when
the tables are modified.  There is no consensus on which method to
use.  I originally held out for two methods, a flexible one and a
really fast one, but have come to the conclusion, reinforced by
conversations with Ken Thompson, that it is better to have one
flexible method in the standard -- scattered directories --  and
handle accelerators, such as directory trees cached on magnetic disk,
as system-dependent structures outside the standard.

Suppose you update a file; doesn't that mean you also have to re-write
the directory, and, therefore, its parent directory, and, therefore,
its parent directory, and so on all the way up to the root directory?
And the volume header?  How do you find the root directory, the volume
header, and so on?  This stuff is not yet decided but we envision that
the file description stuff will have preallocated spare space so that
a few updates can be done without changing anything outside the file
description.  Once this space is full, the system will have to get
free space elsewhere, which implies updating some other area
describing the free space.  The volume header is in a fixed location
(probably 8KB in from the start of media) and will point to any later
volume headers and other stuff (such as where the root of the various
directory trees are).

Requirements for the directory hierarchy include space and time
efficiency, robustness (e.g., to minimize damage from a single I/O
error), a single, fast structure (unlike ISO 9660's two), and that a
directory entry for a file must be complete (that is, point to all the
extents for that file).

May 1990 Standards Update              ANSI X3B11.1: WORM File Systems


                                - 4 -

Space Allocation and Management

We must support pre-allocation of space (e.g., ``Reserve 40MB of
contiguous space for file `xyz'. '') both for speed and to support
systems like the MacIntosh.  Because of the latter, we also need to
support giving back unused reserved space for later use.

These two requirements appear to force the standard to address
describing the free space in a volume set, which will also be
important if the standard is extended to cover R/W optical disks,
where freed blocks need to be cleared before reuse.  The two choices
appear to be run-length encodings of the free space or bitmap
techniques.  The former can degrade to being quite large, while the
latter have a fixed, but high, overhead (current media hold up to
8.2GB/side!).

Finale

We hope to conduct a letter ballot soon after the October, 1990
meeting.  If we can approve a proposal by January, 1991 then it may be
an ANSI standard by January, 1992.  Our next meeting is in Murray
Hill, New Jersey, on July 17-19, where we expect to adopt the proposal
being edited by Howard Kaikow as our working proposal.  Anyone
interested in attending should contact either the chairman, Ed Beshore
([e-mail]), or me ([e-mail]).

While this standard may seem of limited interest, because it deals
only with WORMs, X3B11.1 expects approval shortly to develop a similar
standard for R/W optical media.  It doesn't take much imagination to
see that standard being extended to apply to all rewritable, direct-
access media.  (Unlike the CD-ROM standards committee, which ignored
UNIX, this committee has a significant number of UNIX users, including
representatives from AT&T Bell Labs, Sun, Hewlett-Packard.  That, at
least, insures filenames won't be required to have a compulsory
three-character suffix and a version number.) Once we have a working
paper, anyone who cares about portable, multi-volume, multiple-
character-set file systems should take a look.  [Editor: Pay
attention.  He's giving you fair warning.]

May 1990 Standards Update              ANSI X3B11.1: WORM File Systems


Volume-Number: Volume 20, Number 4