Note: Descriptions are shown in the official language in which they were submitted.
CA 02534170 2006-01-27
L'i VEN'T STRYJCTTTRFD FILE S STEM (ESFfiI
FIELD OF THE XNVENTION
The present invention relates generally to computers and file systems.
BACKGROUND OF THE INVENTION
Computer file systems have traditionally involved some mechanism of data
storage at
a physical location (for instance, a disk sector) and a lookup table or index
of some sort
identifying the data and its physical address (or a logical address from which
that may be
inferred). The tables are implemented in various forms, and generally requize
the ability to
overwrite or update previous table entries as file system additions and
changes occur. These
approaches have the following disadvantages:
(a) there is a dependency on the file system to operate with specific storage
media
types (for example, rewritable)
(b) The file system is noxi-portable across different operating systems and
media
(c) Only the current filesystem state is available. There is no inherent
historical
record of changes or additions
(d) There are inefficiencies added when conventional file systems are extended
to
provide logging of changes.
Ds~initions - the following words have the following meanings throughout;
Data - information of any ldnd that is to be written to the File system for
possible
future access and retrieval, and normally provided by an external source to
the File system.
Event - a data structure existing within the file system indicating a specific
type of
change or addition to the file system.
File system - is a means to organize, store, process, retrieve and manage
information/data using a storage medium of any type.
Metadata - file system information that holds information describing and
relating the
user file system objects, files and directories. In the context of ESFS, the
list of Events for a
file system are its metadata. Metadata is not directly accessible to u,sers.
Object - an entity, such as a file or directory within a File System.
Examples of table based file systems are the Unix File System (UFS) and its'
associated directory tables and inodes, Windows FAT16, FAT32 ("File Allocation
Table")
-1-
CA 02534170 2006-01-27
file systems, and Wizidows NTFS, based on Master File Tables. Other file
system designs
extend existing file systems by adding journaling and logging to improve
reliability and
recoverability, and file versioning.
Computer file systems generally fall into the following classes:
1. "Inode" based with directory tables (Unix'UFS, FFS, ext2/ext3)
2. File Allocation Table (FAT) based file systems (FAT16/FAT32, etc.)
3. Master File Table (MFT) based (Microsoft NTFS) using tables and
index files to create metadata.
4. Journaling file systems (generally inode based, with sepaate journal)
5. Versioning file systems (VMS, OpenVMS, Cedar: table/inode like
internal structures)
6. Log Structured file systems (LFS, Sprite LFS: LFS like internal
stzi.letures and inode map tables writteu sequentially)
Im.plementatious of all of the above file systems require the ability to
update or
overwrite previously written metadata tables and data areas on the media, and
are reliant upon
rewritable tables, indexes, or inode maps.
Master File Table (Ng'T) file systezns, such as NTFS from Microsoft, are
heavily
designed around the use of rewritable tables and izadexes, which are
maintained in specially
allocated metadata 1"iles.
Journaling file systems are designed to improve reliability and recoverability
after a
crash or failure affecting the system. The journal component of such file
systems records
changes since a "checkpoint" or point in time at which the file system was
known to be
consistent, and to which it can be restored by reference to the recorded
changes since
"checkpoint". The journal component typically reuses space that was allocated
to it, and is not
integral to the file system itself, other than for the purpose of improving
reliability. The
joumal's contents are generally limited to only those changes since the last
checkpoint.
Versioning file systems maintain a file in its original forxxn, and any
subsequent
changes are saved using the sarzxe file name and an incrementing version
number. The number
of historical versions available is generally limited and application or
implementation
dependent_ The file's versions are generally implemented as "saves" of
separate files with a
-2-
CA 02534170 2006-01-27
naming convention for addressing specific different versions of the file in
some sequence or
order. These systems are generally implemented at a level closer to the user
than the disk
operating systems or low-level file systems to which this invention is
directed.
Log-based file systems are perhaps the closest of the prior art to this
invention- Sprite
azid LFS, as desczibed in Mendel Rosenblum's and John K. Ousterhout's 24 July
1991 paper
"The Design and Implementation of a Log-structured File System", published in
the
"Proceedings of the I3'1' ACM Symposturn on Operating System Principles" and
the February
1992 "ACM Transactions on Computer Systems" (copy filed contemporaneously with
this
provisional application), are typical of this famitly of file systems, and are
generally
implexnented using internal structures that are patterned after a conventional
table-based file
system, such as UFS. The logging component records standard file system
structures, such as
inodes and directozy entries, and adds a mapping table that describes the
current location of
all allocated inodes. The cornplete inode mapping table is then rewritten
regularly to the end
of the log, and is then used in a conventional manner to navigate the current
file system
structure.
It is, therefore, desirable to provide a computer file system which overcoznes
at least
some of the deficiencies of the prior art systems or provides for added
functionality not
present in the prior art.
SUMMARY OF THE INVENTION
The present invention is a method implerxienting a file system without table-
based
metadata, using instead a list or sequence of predefined Event types to
describe the state,
content, and complete history of the file system. This is useful (among other
uses) for
implementixag archival applications requiring secure, reliable and self-
auditing, tainper-
evident storage, and in particular for applications that require ',,vrite once
read many"
(WORM) behaviour for regulatory compliance in electronic storage systems. The
system by
design does not require overwriting of any previously written information, and
may be
implemented efficiently and consistently across all types of digital storage
media, including
WORM, erasable, rewritable, and tape.
Unlike a typical hierarchical file system, ESFS does not use any form of table
within
its' metadata to hold information describizig the contents of the file system.
Table-based
-3-
CA 02534170 2006-01-27
systems are entirely distinct from ESFS, which uses incremental updates to a
sequenced Event
list to reflect changes as they occur, and does not require any forin of
intemal table
whatsoever. In.stead of tables or indexes (e.g. File AJlocation Tables or
inodes of traditional
file systems), ESFS uses a small set of predefmed (but extensible) file system
"Events". A
single Event is a data structure that generaliy describes a single file system
operation (e.g. file
or directory creation, file write, or file close, etc.) md if applicable, the
location of data
related to the Event. Events are linked or related together into sequences
using one or more
"povaters" contained within the Event. Several pointer types are used to build
and navigate the
file system. By navigating the file system's stzucture using the pointers
contained in the Event
descriptions, one can perform all necessary tasks to operate a file system
with features and
operations equivalent to traditional hierarchical file systems.
Features of the Event Structured File System include:
= Low file system overhead: A basic ESFS implementation is very simple.
Overhead for storing the Events is xninimal. There is no requirement to
prepare
media or pre-allocate storage space for Events.
= Ideal for implementing WORM applications: ESFS records file system changes
as incremental Events in the sequence they occur, without overwriting
previously
written data. ESFS is thus ideally suited for use with applications that
require
WORM behaviour or media.
= Extensible Events: ESFS implementations can add custom Events types to add
inew features and coz-trols.
= Host xxidependent: ESFS is designed to be independent of the host system and
is
well suited for removable media implementations.
= Self-auditing: ESFS is self-contained, and requires no additional tables,
indexes
or data bases are required in order to access contents of the file system.
ESFS
Events can be used to audit and produce historical journals of the contents
and
state of the file system at any time since its' creation time.
= Sequential or Random Access storage devices and media.
= Adaptable to all media types: WORM, erasable media, rewritable, and pre-
mastered.
-4-
CA 02534170 2006-01-27
= Secure: Includes built-in tamper detection. ESFS can use both secure hash
algorithrns and encryption algorithms to ensure data integrity.
= Built-in Versioning: ESFS tracks file and director versions, or revisions.
This
jourxaal-like feature is built into the way Events are lxnked/related
together, and
reports can be inferred, generated or extracted.
= portability - file systems are binary compatible across all supported
operating
systems
= Sxnall footprint - low overhead and resource requirements
= Fast - data can be archived at very near the rated speed of the underlying
hardware
= Secure - ESFS provides mechanisms to detect tampering with file data or file
system Metadata.
The EFSF inay be briefly described as follows:
1. File system rrietadata, including one or znore Events, linked together in a
fashiom to completely describe, in aggregate with all other Event
descriptions,
the entire contents and structure of the file system.
2. ESFS funCtiona.lity or featares can be extended by en.hancing or increasing
Event types to perxnit, for example, customization of the ESFS for a
particular
application, security model, or Operating System ("OS")
3. ESFS can be implemented independently of the host computing hardware,
operating system, storage device, or media. Because of it
4. Because of its' inherent portability, ESFS is very well suited for
removable
media and archival applications.
5. ESFS has a small iinplementation "footprint", and the logic and structure
of the
system is easy to understand.
In prior art, file system implementations must make tradeoffs among media
portability, media type, performance, security, verification, audit support,
and robustness. It is
an object of the present invention to obviate or mitigate at least ozle
disadvantage of the
previous art.
The ESFS of this invention may be consistently applied to all forms of
erasable and
write-once media, including physical devices and in-memory implementations.
The benefits
-5-
CA 02534170 2006-01-27
of the 3nnethod seem significant, in particular in applications where "Write
once read many"
("WORM") beha.viors are useful or desirable or where the ability to
authenticate the integrity
of stored information is usefiil or desirable.
Other aspects and features of the present invention will become apparent to
those
ordinarily slcilled in the art upon review of the following description of
specific embodiments
of the iuvention in conjunction with the accompanying figures.
BRIEF DESCRIPTION OF'TDE DRAWINGS
Embodiments of the present invention will now be described, by way of example
only,
with reference to the attached Figures, wherein:
Fig. 1 is a block diagram showing the relationship between parts of an ESFS
Volume
Structure.
Definitions - the following words have the following meanings throughout:
Block - the smallest unit of storage addressable by an ESFS file system. Block
Address - a unique location identifier used to access a Block
Data - information of any kind that is to be written to the File system for
possible
future access and retrieval, and normally provided by an external source to
the File
system.
Directory - file system object that provides a way to name and organize
multiple,
related files. [For example, Users may perform the following file system
operations on
directories: Create, Delete, Rename, Get Info and List F'iles.]
Event - a data structure existing witbin the file systern indicating a
specific type of
change or addition to the file system.
Event Address - an Event Address specifies the location of a specific Event.
It is
conzprised of a Block Address and a Block Offset, indicating the byte location
of the
Event witliin the Block.
File - a file system object that provides a way to store and recall data by
name. Data
within the file can be sequentially or randomly read and written. i7sers may,
by
example, perforrn the following file system operations: Create, Delete, Open,
Close,
Position, Read, Write, Rename, Set File Times, and Get Info.
-6-
CA 02534170 2006-01-27
File system - is a means to organjze, store, process, retrieve and manage
information/data using a storage medium of any type.
Metadata - file system information that holds information describing and
relating the
user file system objects, files and directories. In the context of ESFS, the
list of Events
for a file system are its metadata. Metadata is not directly accessible to
users.
Offset - the number of bytes froin the beginning of a Block to the beginning
of an
Event
Partition - a logical container with addressable Sectors that holds a file
syster.a, in
whole or in part.
Pointer - an Event Address used to link Events into a list
DETAIY.ED DESCRIPTION
Generally, the present invention provides a File System comprising an ordered
list of
Events associated with Data, that may be implemented identically on all common
digital
storage media types, including write-once, erasable, and rewritable media,
whether in
sequential or random-access mode, (or otherwise).
The system uses the sequence and type of Event with its associated Data
without
reference to any external table or journal entry to operate and be verifiable.
The system's list of Events is accessible in a predefzned sequence, normally,
but not
limited to, reverse chronological order.
ESFS includes an ordered list of Events associated with Data made verifiable
in whole
or in part by provision of checksums and security information within the
Events and data
verii"ication means.
ESFS may be efficiently ixxaplemented using a"Write Once Read Many" (WORM)
model, irrespective of the underlying media type. Previously written areas of
the media may
be read, but are never overwritten or erased.
ESFS is made tamper-evident using checksums and security information on at
least
one of: Metadata and Data
The method set out below describes how a file system may be structured and
implemented using a small set of predefined set of Events, each of which
describes an
ineremental change to the file system. The Events, such as creating or writing
a file, form an
-7-
CA 02534170 2006-01-27
ordered list that allows the exact state and contents of the file system to be
Imown at any point
in time. Events associated with a specific directory or file are logically
linked as the file
system grows. The method is unique and represents a fundamental change in the
way
computer file systems are constructed.
Current art typically uses tables and indexes that are overwritten, extended,
or updated
to reflect file system additions and updates. Additionally, file system
implementations are
generally specific to either xnagnetic or write-once media, and are not self-
auditing.
SeLf-auditing means that the integrity of the file system (including the file
system of
this invention) can be assured without reference to an external or secondary
iztformation store,
such as a journal or log file.
. Using this invention's method, the list of Events and associated file data
taken
together are the file system and comprise its complete history since creation.
No other
information source is required either for normal use or for audit, integrity-
checking, or
tamper-evidencing.
Events stored within an ESFS file system are generally accessed sequentially
and
randomly using information within the Event to navigate to a desired location,
but the specific
means of providing such access is open to the ESFS implementer. For example,
implementations that require write-once behaviour may achieve sequential
access using
reverse linked lists, whi.le a rewritable implementation rnight use both
forward and reverse
link.ing. Thus, ESk'S requires only the ability to read and write specific
storage blocks on a
physical or electronic medium using reference to a unique identifier or block
number
associated with the storage block.
For clarity in describing the rnethod below, the most restrictive case will
generally be
used in this document: reverse linking using write-once media. Rewritable
implementations
would typically be a superset of the same Events and techniques, and other
than additional
implementation specific changes, still rely on the ability to sequentially
access an Event list in
a known order.
The method as described herein also demonstrates that all typical file system
operations (creating, modifying, deleting files and directories) can be
accomplished using a
small set of predefined, ordered Events, without ever having to overwrite the
storage media. It
-g-
CA 02534170 2006-01-27
is also to be understood that time-ordered sequencing may not be the only
sequence-ordering
logic useful to computer file systems using Event sequence as the base data
paradigm to
provide a file system.
ESFS Features:
Features of the Event Structured File Systein include:
= Low file system overltead: A basic ESFS implementation is very simple.
Overhead for storing the Events is rxtinimal. There is no requirement to
prepare
media or pre-allocate storage space for Events.
= Xdeal for implementing WOEa.VI applications: ESFS records file system
changes
as incremental Events in the sequence they occur, without overwriting
previously
written data. ESFS is thus ideally suited for use with applications that
require
WORM behaviour or media.
= Extensible Events; ESFS implementations can add custom Events types to add
new features and controls.
= Host independent: ESFS is designed to be independent of the host system and
is
well suited for removable media implememtations.
= Self-auditing: ESFS is self-contained, and requires no additional tables,
indexes
or data bases are required in order to access contents of the file system.
= Supports sequential or random access storage devices.
= Supports both WORM and erasable media.
= Secure: htcludes built in tamper detection. ESFS can use both secure hash
algorithms and encryption algorithms to ensure data integrity.
= Built-in Versioning: ESFS tracks ,fil.e and director versions, or revisions.
This
journal-like feature is built into the way Events are lir-ked/related
together, and
reports can be inferred, generated or extracted.
= portability - file systems are binary compatible across all supported
operating
systems
= Small footprint - low overhead and resource requirements
= Fast - data can be archived at very near the rated speed of the underlying
hardware;
-9-
CA 02534170 2006-01-27
. Secure - ESFS provides mechanisms to detect tampering with file data or file
system Metadata.
Zmplementation Requirements
The ESFS concept is very flexible, and may be implemented on diverse
hardware platforms, operating systems, and storage devices. Ignoring specific
implementation
issues, ESFS has the fbllowing minimum requirements for successfal
implementation and
operation: a block addressable storage device.
Volume Structure
Fig. 1 is a volume strnxcture diagram of a file system based on this ESFS.
Components
of the file system are:
= File System Volume Label (FSVL): This item is optional and implementation
dependent. It provides the host with a method of recognizing a specific 8SF
iniplementation on a storage medium.
* File System XnformatRion Block (FSIB): This structure provides basic
inforTnation
describing the ESF file system, including volume size, geometry, and pointers
to
the logical addresses of the first Evemt and first data block. Depending on
the
implementation, the FSIB may also contain pointers to the logical address of
the
last Event and last data block.
+Events: Individual data structures that are linked together by pointers. For
write-
once applications, Events are reversed linked together using one more types of
pointers. Examples of Events: Create Directory, Create File, Write Data,
Remove
File, etc.
= Data: logical blocks of file data; i.e., the contents of user files. The
data blocks are
pointed to by "Data Events".
Event Structnred File System Operations:
The method fnr implementing core file system operations is described in detaal
in the
following sections. The following operations are included-
~ Volume Creation - initializing storage medium with an empty, ready to use
file
system
-10-
CA 02534170 2006-01-27
= Volume Mounting - how to make an existing ESFS available for access and
updati.ng
Volume Creation:
1. If required by the implementation, write a Volume Label, typically at block
zero of the device.
2. 'VVrite a File System Information Block at a known Block offset ou the
storage
medium.
3. Prepare the root directory Create Directory Event.
4. If required by the implementation, initialize a Free Block List descxibing
all
available Blocks on the medium. Write the Free Block List to disk
5. Write an Unmount Event to disk
Volume Recognition;
1. If required by the implementation, zead the File system Volume Label (FSVL,
typically Block zero) on the media. Perform validations to ensure it is a
supported volume type and version.
2. Attempt to read an ESFS File System Informar.ion Block (FSIB) at an
implementation specific known Block location.
3. Validate ESFS ixnplementation specific identifiers and version numbers.
Volume Mountimg:
To access or mount an ESFS volume, the following steps are normally taken:
1. If required by the implementation, read the File system Volume Label
(FSVL).
2. Attempt to read an ESFS File Systein Information Block (FSIB) at an
implementation specific known block location.
3. As a minimum, the FSIB will contain the necessary information to locate the
first Event (First Event Address).
4. Using an implementation specific method, locate the last Event for the
voiurne.
A preferred method is to locate the last Event by performing a binary search
of
the file system area to locate ESFS blocks with identifiers that match the
FST.E
identiters. The last Event should be an Unxnount Event, indicating the last
-11-
CA 02534170 2006-01-27
mount session was properly closed and that the basic file system's integrity
is
intact.
5. If the Iast Event is not an Unmount Event, FAIL the Volume Mount.
6. Implementations will typically persist information about a mounted volume
in
a structure that is referred to by subsequent file system functions.
ESFS Pathnames:
An ESFS pathname is a unique identifier assigned to a darectory or file when
it is
created. After the file is created, the pathname can be used to access or
update the directory or
file. ESp'S pathnames may be implementation specific. A conrxmon file system
implementation
is hierarchical, consisting of a top-level directory (the root directory),
with zero or more file
entries and subdirectory entries. Each file system entry below the root
directory has a parent
directory. Each file or directory entry has a unique name within its parent
directory.
Fathnames for a specific file consist of one or more directory components,
each separated by
a pathname delimiter (for example "f '), fallowed by a filename. To access a
specific file, a
complete or absolute pathname may be used to navigate through all parent
directory levels
until the last filename component is reached.
Events:
The structure and contents of a file system constructed using the method is
described
by an ordered list of Events. One or more Events are contained within a Block,
where a Block
consists of one or more physical storage Sectors. Each Block is addressable by
a Elocle
Address, and contains a unique signature that is associated with the volume's
FSIE. A
specific Event is addressable by an Event Address, which contains both a Block
Address and
byte offset of the Event wi.thin the specified Elock.
There are several different types of Events, each describvng a single change
to the file
system, such as creating a file or directory, or writing to a file.
Ixidividual Events may be
linked together by Event pointers to associate related Events and easily
navigate through the
file system.
Event Types:
The system of this invention, uses several Event types that are considered
Core Events
that would typically be used by most implementations to create directories and
files. Also
-12-
CA 02534170 2006-01-27
described are Extended Events that would provide additional file system
functionality, such as
renaining or deleting files and directories, if required for a specific
iinplementation. Space
Events can be used to implement storage management for allocation and
reclaiming of Blocks
as files are created, written to, or deleted.
ESFS Events are extensible, allowing the file system to casily grow and evolve
while
maintaining compatibility with earlier implementations. For example,
"Security', Events
could establish access control mechanisms for files and directories. "Quota"
Events could
establish space limits within directories. "Stream" Events could associate
multiple types of
data streams with a specific file.
Event'i.'ype Category Description
Core Ei+en&s
Create Dkectory Directory Create a directory
Create File File Creates a new file or a new vezsion of an old file
Close File File Close a file
Write Data File Write data to a file (random or sequential)
Unmount System Denotes a successful nnmount of the file systern
Extended Events
Delete Directory Directory Remove a directory
Rename Directory Directory Rename a directory
Delete File File Delete a File
Rename File File Rename a File
Free Space Events
Allocate Block System Allocate a Block ffrom the Free Block List
Release Block System Return an allocated block to the Free Block List
Event Pointers_
Number Pointer Type Structural information
1 Link Links Events associated with a specific file or directory
2 Brother Links file and directory Events associated with a particular
-13-
CA 02534170 2006-01-27
directory
3 Parent Links file and directory Events to a parent directory Evemt in a
hierarchical directory structure
Link Pointers:
A link pointer is used to connect associated Events. That is, Events that are
associated
with one particular directory, file or list. The following tables are used to
express possible
connections among the Event types. For write-once implementations, link
pointers vvill point
to the last related Event (reverse iinking), if one exists, otherwise it will
be empty (nil).
Rewritable implementations may choose reverse linking, forward linking, or
both.
For clarity in describing the method, the most restrictive case will be used:
reverse
linking and wnte-once media. Rewritable implementations would typically be a
superset of
the same Events and tecWques, and other than additional implementation
specific changes,
still rely on the ability to sequemtially access an Event list in a time-
ordered manner.
The method as described herein also demomtrates that all typical file system
operations can be accomplished using ordered Events, without ever having to
ovezwrite
existing information.
The three Event tables below are orgazdzed "From:" rows and "To:" columns. An.
Event in the "k'rom:" coltunn will point to an Event in the "To=: " rows. For
example: a Delete
File Event may point to a Close File or Rename File Event, depending on which
was the last
to occur.
File Events are all Iiuced to other related file Events. A related file Event
will have the
identical Name field in each ESFS Name structure.
-14-
CA 02534170 2006-01-27
File Link
Events for
Write Once To One of: (whichever is most recent for the file in the From
Mode column)
Frown Create File Close File Delete File Data Rename Fi1e
Create File X X X
Ciose File X X
Delete File X
Data X X X
Rename File X
Directory Events are all linked to other related directory Events. A related
dixect.ory
Event will have the identical Name field in each ESF Name structure.
Directory Link
Events for To One of:
Write OnceMode (whichever is most recent for the file in the From columQ)
From Create Directory Delete Directory Rename Directory
Create Directory X X
Delete Directory X
rename Directory X
Brotber Pointer:
A brother pointer points to the most recent file or directory Event that has
the same
parent.
Pareiat Pointer:
A parent pointer always points to the Create Directory Event of the parent
directory, or
unless the parent directory is the root or top-level directory ("/"), in which
case the parent
pointer is empty (nil).
ESFS Path name Lookup:
Results in new 51e version, if versions are supported by the implementation
2 Resnlts in new directory version, if versions are supported by the
implementation
-15-
CA 02534170 2006-01-27
ESFS Patimame I.ookup is the process of navigating through the ESFS Events to
locate the most recent file or directory Event associated with the pathname.
It is a frequently
used process, and as such, specific implementations would normally include
eaching
mechanisms to boost performance for frequently accessed files and directories.
Each directory or file within ESFS has a unique pathname. In hierarchical
implementation, the pathname is first split into one or more components, where
each
componont is separated by a pathname delimiter. Each component is then used to
determine
the existence of the component name in the corresponding directory level.
Method:
The method for locating an entry in a bierarchical ESF file system is
explained below.
To assist in the explanation, the sample pathname
"/dir01/myfZles/mydocldocl.txt" is used:
(a) Separate the pathnarne into components, where each component is a sequence
of characters delimited by an implementation specilic patbname delimiter
character ("P' in the example), or the ead of the string of characters,
whichever
comes first. The list of components is used below to navigate through the file
system on directory level at a time (e.g. dirD01, myfiles, mydoc, docl.txt).
The
search begins in the root directory with the first component of the patb,
='dir00l ".
(b) Locate the most recent Event entry in the directory level being examined.
(c) If there are no file entries, then the pathnanae does not exist. The
pathname
texininates in failure.
(d) Examine the Event record for a match with the current component of the
patlmame.
(e) If the names do not match, then follow the brother ludc to locate the next
associated entry in the directory. Go to c)
(f) The component and Event names match. If there are additional components,
select the next
(g) component name, and go to b)
(h) If the Event is a Close Event or a Create Directory Event, the search
termi.nates
in SUCCESS.
-16-
CA 02534170 2006-01-27
(i) If the Event is a Delete Directory, Rename Directory, Delete File, or
Rename
File Event, the search terminates in FAILURE.
ESFS Endpoint Lookup:
Because ESFS creates linlts among associated Events as the file system grows,
access
to the last entry in an Event list (or "endpoint") is a frequently executed
process. Specific
iunplenaeritations may choose to incorporate an endpoi.nt caching mechanism to
reduce the
ti.me to access frequently referenced directories and add new Events.
Metbod:
The steps below assumes that ESFS Patbname lookup has already been performed,
and the required Event Address is available:
(a) starting from the last written Event in the ESFS file system, traverse the
Event
list in reverse order until an Event is found having a matching parent Event
Address
(b) if a match is found, the most recent Event is the Endpoint Event Address.
This
address would typically be saved i,z, an iuraplementation specific endpoint
cache.
(e) If a miatch is not found, the Endpoint Event is nil (empty)
ESF Block Events:
Oz-ie of the common requirements of a file system is the managernent of
storage space
allocated to files and directories as they are created, updated, or deleted.
Blocks must be
allocated from a lmovcwn list of available or free blocks (the Free Block
List). The Free Block
List must then be updated after each allocation or release of Blocks.
An implementation may use a simple Block allocation scheme that does not
require
Block Events at all_ For example, Blocks could be allocated from a contiguous
area, and the
size of the area reduced after each alloeation.
If the iumplementation requires more sophisticated space management, Block
Events
may be used for this purpose. In this case, Volume Creation would prepare a
Free List Event
through whieb all subsequent Block allocations would be accessed and tracked.
For
efficiency, a specific implementation need only generate and update a single
Block Event as
-17-
CA 02534170 2006-01-27
lozig as the allocations are contiguous, and Block Events need only be
committcd when the
file system is being dismounted, just prior to writing an Untnount Event.
Three types of Block Events are described:
(i) Allocate Block Events are gezterated every time a Block is allocated to a
file to
hold data, and the Blocks are successfully written. However, since allocations
tend to be contiguous in a Write Once storage model, only one Allocate Block
Event is likely required for the duration of a mount session.
(ii) Free Block Events are normally created only when a write to a file fails,
and
the Blocks allocated to hold that write are then returned to the Free Block
List.
(iii) A Free List Event is written when the file system is dismounted, and
contains
a complete, updated list of contiguous free Block entries. This list wili be
empty, (nil) when the file system is full.
VVhile the specific xnethod is implementation dependent, a method for managing
Block
Events axDd a Free Block List using reverse linked Events is described. For
clarity, it is
assumed that an ESFS file system has been created, and the most current
Unmount Event has
been established. The Unrxaount Event contains a pointer to the Free Block
List and the
Allocated Block List. The contezits of each list are loaded into memory during
the Volume
Mount operation.
Allocate Block Meth od:
The purpose of this method is to allocate one or more Blocks from the Free
Block List
to a file that will write data to the allocated Blocks. The method is passed a
parameter
indicating the number of Blocks required, and if successful, retuzns a list of
allocated blocks.
(a) For the purpose of this explanation, the Event specified by the Free Block
List
is the Current Event. Remai.ning Blocks is a value that is initialized to the
number of blocks required.
(b) If the Free Block List is emTty, or does not contain suffieient available
blocks
to satisfy the xequested amount, FAIL the request.
(e) Create a new, empty Allocation Event. Set the brother pointer of this
Event to
point the previous Allocation Event, if any.
-IB-
CA 02534170 2006-01-27
(d) Set the starting Block Address for the new Allocation Event to the
starting
address specified by the CurreDt Event.
(e) If the Cxrrent Event contains sufficient Blocks to satisfy the remaining
blocks
for request:
(i) set the nnmber of blocks in the new Allocation Event to the total
roquested.
(ii) add the number of blocks allocated to the starting address of the
Current Event.
(iii) go to g).
(f) The Current Event only partially satisfies the request:
(i) set the total number of blocks in the new Allocation Event to the
number available in the Current Event.
(ii) Release any resources associated with the Current Event list item, and
set Current Event to the next Event in the Free Block List.
(iii) deduct the number of blocks allocated from Remaining Blocks.
(iv) If the new Allocation Event is contiguous with the most recent System
Allocated Block Event, then extend the size of the most recent System
Allocated Block Event by the size of the current request.
(v) (3o to c).
(g) Set the Free Block List to Current Event.
(h) If the new Allocation Event is cozitiguous with the most recent System
Allocatad Block Event, then extend the size of the most recent System
Allocated Block Event by the size of the current request. Otherwise, create a
new Systenx Allocated Block Event, and set the brother pointer to the previous
Syste:m Allocated Block Event.
(i) The Allocated Event now contains a list of one or more contiguous Block
areas.
(j) Return SUCCESS
-19-
CA 02534170 2006-01-27
Free Block Method:
If the implementation is such that blocks previously allocated to a file can
be released
or de-allocated, then this may be accomplished by creating a list of BloclC
Events, one item for
each contiguous area of Blocks, and inserting the list at the beo Tnrit'lg of
the Free Block List.
Directory OQerations
Create Directory:
The method for creatiuag a new directory in an ESF file system is explained
below. A
pathname for the new directory is provided by an extemal application to the
file system, and
the following steps are executed:
(a) perform ESFS Pathname Lookup on the specified directory pathnarne.
(b) if the pathname exists, then FAIL, the directory creation and exit the
method
(c) the pathname does not exist: continue by performing Endpoint Lookup for
the
parent directory of the new directory. Remember the Event Address of the
parent directory.
(d) Create a new, empty Create Directory Event. Set the brother pointer of
this
Event to point to the endpoint located in c). Set the parent pointer of this
Event
from c). Copy the pathnaine component to the Event record.
(e) Commit the Event to the file system
(f) Done
Renazne Directory
The method renaming an existing directory in an ESF file system is explained
below.
An external application provides the existing pathname, and the new pathaame,
and the
following steps are then executed:
(a) perform ESFS Pathname lookup of the existing directory pathname.
(b) If the paChname does not exist, FAIL the rename operation
(c) If the pathname is NOT a directory, FAIL the rename operation
(d) The existing directory pathnerne is valid. Remember the Event Address of
the
Create Directory Event, and the Parent Event Address for the entry.
(e) perforna a patbname lookup of the new directory pathname
(f) If the pathaame does exist, FAIL the rename operation
-20-
CA 02534170 2006-01-27
(g) Perform Endpoint Lookup in the parent directory, and remember the Event
Address of the Endpoint Event entry.
(h) Create a new, empty Rename Directory Event
(i) Set the Link pointer to the Event Address of the Create Directory Event
from
d)
(j) Set the brother pointer to the Endpoint Event Address from g)
(k) Set the parent pointer to the 1'arent Event Address from d)
(1) Copy the last pathname component to the Rename Directory Event
(m) Create a mew, empty Create Directory Event
(n) Commit the Event to the file system, remember the Event Address of the new
Event.
(o) Set the Link pointer to the Event Addrass from n)
(p) Set the Brother pointer to the Event Address from n)
(q) Set Parent pointer to the Parent Event address from d)
(r) Commit the Event to the file system
(s) Done
Delete Directory
(a) perfozm EFS Patlaname Lookup on the specified directory pathnaane
(b) if the pathname does not exist, then FAIL the directory deletion
(c) The directory exists: if the Event fotmd is a Delete Directory or Rename
Event,
thezi FAIL the directory deletion.
(d) Perforrn Endpoint Lookup for the specified directory. If the directory is
not
empty (an Endpoint exists), then EAII., the directory deletion.
(e) The directory exists, it is active, and it is empty: create a new, empty
Delete
Directory Event.
(f) Set the brother pointer of this Event to point to the Eztdpoint Event
Address
located in d).
(g) Set the parent pointer of this Event from d).
(b) Copy the pathname component to the Event record.
(i) Commit the Event to the file system
-21-
CA 02534170 2006-01-27
(j) Done
File Operations
Create File (Create a New File)
The method for creating a new file in a MWSF file system is explained below. A
pathname for the naw file is provided by an external application to the file
system, and the
following steps are executed:
(a) perform ESFS Pathname Lookup on the specified fi1e pathname.
(b) If the pathname already exists, FAIL the file creation
(c) perform Endpoint Lookup for the parent directory of the new file.
Rc:member
the Event Address of the parent directory.
(d) Create a new, empty Create File Event.
(e) Set the brother pointer of this Event to point to the Endpoint Evezit
Address
located in c).
(f) Set the parent pointer of this Event from c)_
(g) Copy the pa#hmame component to the Event record.
(h) Commit the Event to the f le system
(i) Done
Open File (Open an Existing File)
The method for opening an existing file is explained below. A pathnarne for
the new
file is provided by an external application to the $le systexn, and the
following steps are
executed:
(a) Perfnrm ESFS Pathna.me lookup on the specified file pathname.
(b) If the pathnarne does not exist, FAIL the operation_
(c) If the last Event found for the pathname is not a Close File Event,
p'AIl'. the
operation.
(d) Itemember the Event Address for Close File Event.
(e) Perform Endpoint Lookup for the parent directory of the new file. Remember
the Event Address of the parent directory.
(f) Done
-22-
CA 02534170 2006-01-27
Rename File
The method renam.ing an existing file in an ESFS file system is explained
below:
An external application provides the existing pathnarne of the file to be
renamed, a
new pathnaxne, and the following steps are then executed:
(a) perform ESFS Pathname Lookup of the existing file patbname.
(b) xf the pathname does not exist, FAIL the rename operation
(e) Zf the pathname is NOT a file, FAIL the rename operation
(d) Remember the Event Address of the Close File Event, aud the Parent Event
Address for the entry.
(e) Perform a pathname lookup of the new file patunanne
(f) If the pathname DOES exist, FAIL the rename operation
(g) Perform Endpoint Lookup in the parent directory of the file, and remember
the
Event A,ddress of the Endpoint Event entry.
(h) Create a new, empty Renam.e File Event
(i) Set the Link pointer to the Event Address of the Close File Event from d)
(j) Set the brother pointer to the Endpoint Event Address from g)
(k) Set the parent pointer to the Parent Event Address from d)
(1) Copy the last pathname component to the Rename File Event
(zzl) Create a new, empty Create File Event
(n) Commit the Event to the file system, remember the Event Address of the new
Event.
(o) Set the Link pointer to the Event Address from n)
(p) Set the Brother pointer to the Event Address froxri n)
(q) Set Parent pointer to the Parent Event Address from d)
(r) Comrnit the Event to the file system
(s) Done
Delete File
(a) perform ESFS Pathname Lookup on the specified directory pathname
(6) if the pathname does not exist, then FAIL the deletion and exit the
procedure.
-23-
CA 02534170 2006-01-27
(c) if the last Event found for the pathname is a Delete File or Rename Event,
then
FAIL the file deletion and exit the procedure.
(d) create a new, empty Delete File Event.
(e) Set the brother poiuter of this Event to point to the Endpoint Event
Address
located i:n c).
(f) Set the parent pointer of this Event from c).
(g) Copy the pathname component to the Event record.
(h) Commit the Event to the file system
(i) Done
Write File
The method for writing data to a file in the ESFS file system is explained
below. A
specific implementation of the method would normally use a file desariptor or
handle that
provides access to a structure that retains information for an associated file
that has been
created or opened by the Create File or Open File methods.
The Write File method assumes that the following information is available:
(i) a file descriptor prbvidi.ng access to the file to which data vcrill be
written
(ii) a memory buffer containing the data to be written (Data)
(iii) the length of the data to be written (Data-Length)
(iv) the starting offset within the file (File-Offset) at which writing is to
commence (for sequential writing, the location can be zetained by the
file descriptor and updated automatically after each successful Write
File)
(a) from the file descriptor, get thc Event Address of the files' most recent
file
Event (a Create File or Close File Event). This address is the File-Event-
Address.
(b) set Parent-Event-Address to match parent specified in the most recent
write
Event.
(c) find the most recent Data Event for the specified file. This address is
Data Event Address.
-24-
CA 02534170 2006-01-27
(d) perform the Allocate Block method, specifying Data-Length number of
Blocks.
(e) If successful, a list of one or rnore areas of contiguous Blocks will be
returned
(Allocated-Block-List) that is sufficient to contain Data.
(t) If the requested number of blocks cannot be allocated, FAIL the Write
operation and exit the procedure.
(g) set Current-File-Offset to File-Offset.
(h) For each entry in Allocated-Block-List:
(i) Current-Allocated-Block refers to the current entry in Allocated-Block-
List.
(ii) create a new, empty Data Event record (Current-Write-Eveat)
(iii) set the Parent pointer to the Parent-Block-Address from a)
(iv) set the Brother pointer to the File-Event-Block-Address from a).
(v) set the Link pointer to the Write_Event Block Address from b).
(vi) set the Event Address in Current-Write-Event to the starting Event
Address specified in Cwrrent-Allocated-Bloek_
(vii) set the length in Current-Write-Event to the length specified in Current-
Allocated-Block.
(viii) set the File Offset in Current-Write-Eveztt to Curreiat-k'ile-Offset
(ix) wzite Data to the media, starting at Current-File-Offset, and continuing
for Current-Write-Length.
(x) commit Gurrent-Write-Event to the file system
(xi) add Current-Write-Length to Current-File-Offset
(xii) select the next entry in Allocated-Block-List
(i) Done
Read File
The metbod for reading data from a file in the ESFS file system is explained
below.
The specific implementation of the method would normally include a file
descriptor that
retains information concerning a file that has been created or opened by the
Create File or
Open File methods. Also, specific implementations may support reading at any
file location
-25-
CA 02534170 2006-01-27
and length, or restrict reading to locations and sizes that are multiples of
the underlying Block
size.
The Read File method described below assumes that the following information is
available:
(i) a file descriptor providing access to the file to which data will be
written
(ii) a memory buffer into which the data from the file will be transferred
(Data)
(iii) the length of the data to be read (Data-Length)
(iv) the starcing offset in bytes (File-Offset) from which reading is to
commence
(for sequential reading, this location can be retained by the file descriptor
and
updated automatically after each success~u1 Read File)
Since the specified File-Offset may not fall on an even Block boundary,
implementations may need to perfornn the first (and/or last) read operation
using a temporary
buffer to accept a fnll Block. Partial user data is then copied to Data from a
calculated offset
within the temporary buffer.
(a) if Data-Length is zero, return SUCCESS.
(b) Otherwise, pezfirm the following initialization steps:
(i) set File Eveut Address to the Event Address designated in the file
descriptor. This is the most recent file Event for the file. Read the File
Event.
(H) If the File Event is a Create File Event, then the file is empty. FAIZ,
the
read and exit the process.
(iii) If the File Event is a Close File Event, then the Link pointer will
point
to the most recent Data Event for the file. Set Write-Event-Address to
the Link pointer.
(iv) set Parent-Event-Address to the one specified in the file Event.
(v) initialize Current-File-Offset to File-Offset.
(vi) Initialize Remai.ning_Data Leugth to Data_Length
(c) Starting from Data Event Address, travexse the Data Event List until an
Event
is found that contains the Current-File-Ofifset This will be referred to as
Current-l7ata-Event.
-26-
CA 02534170 2006-01-27
(d) If such an Event is not found, FAIL the Read Filc operation, and exit the
process.
(e) Next, since Current_Data Event can specify many Blocks, determine the
first
Event Address for reading data as follows:
(f) l;'irst Block Address = StartingAddiess from Data Event
(g) Block Offset = Gtiurent_File Oifset - Data-Event File Offset
(h) If Block Offset is not a multiple of Block Size, then use a temporary
buffer
(Buffer) when t.ransferring data, and read one Block, startang at:
Read Address = First-Block-Address + (Block Offset. / Block Size)
Read the specified Block into Buffer, and copy from the Gtiurent-File_Offset.
This value is the Block-Offset, and the first Block to read is
Starting_Bloek Address + (Block-Offset Block-Size).
(i) set Read-Length to the lesser of Remai.ning_Data Length or (Write-Event-
Leztgth - Block-Offset)
(j) exit the procedure.
The above-described embodimernts of the present invention are intended to be
exarnples only. Alterations, modifications and variations may be effected to
the particular
embodiments by those of slall in the att without departing from the scope of
the invention,
which is defined solely by the claims appended hereto.
-27-
