Here's the spec of the arbitrary extra bits of information file.

What is it for:

Anything that some application or other wants to store associated with a
particular object (file or directory).

Why is it needed:

Facility not available as a generally available facility.

What is its name:

,}<]{~>[!

This is a very silly name which is unlikely to be produced 'naturally'.

What is its structure:

Level 0 structure:

1st byte of the file is a file structure version number. The structure of
the rest of the file depends upon this version. If an information file is
come across which has a version number greater than that inderstood by the
particular version of FileSwitch, then tough - the information can be
considered invisible.

Version 0 files:

Version 0 files have a two-layer scheme to these files. The lower layer
(level 1) is a heap abstraction placed upon the file. That is, the file is
structured such that it can be thought of as being a heap in the RAM heap
type of thing. Of course, the higher layer must talk to the file via the
lower layer for all operations, including things such as assignment.

The upper layer (level 2) makes use of the heap abstraction to provide a
storage mechanism for the external interfaces.

OK this is the outline of the data model of these files, here's the
functional model. It is slightly strange that the level-0-understander talks
to the level-2-understander which talks to the level-1-understander, but
that's the way the cookie crumbles. Anyway:

The outside world (inside FileSwitch) sees this interface:

OpenInfoFileForFile(canonicalised path)->(handle)
OpenInfoFileInDirectory(canonicalised path)->(handle)
CloseInfoFile(handle)
ReadInfoSize(handle,tail,tag)->(size)
ReadInfo:(handle,tail,tag,buffer,length)->(length read)
SetInfo:(handle,tail,tag,buffer,length)->()
MoveInfo:(source handle,tail,destination handle,tail)->()

This is talking to a FileSwitch-like subsystem, which could be called
version-switch. It's job is to manage the conversions between the outside
world and the different file-version handlers:

                        The rest of FileSwitch
                                |
                                |
                                |
                        version-switch
                        /             \
                       /               \
                      /                 \
                version 0               version 1

Version switch performs the vital task of openning and closing the actual
information files, determining their version and organising their creation
and deletion when necessary. As each version handler is part of FileSwitch
it is not envisaged that any registration scheme for a version handler is
needed. So, here's the interface between version-switch and a version
handler:

ReadInfoSize:(file handle,leaf,tag)->(size)
ReadInfoPart:(file handle,leaf,tag,buffer,start,length)->(length read)
SetInfo:(file handle,leaf,tag,buffer,size)->(safety)
WriteInfoPart:(file handle,leaf,tag,buffer,start,length)->()
VersionFileEmpty:(file handle)->(its empty)
CreateVersionFile:(file handle)->()

For version 0 files the following interface is provided between the heap
and the structure handler:

AllocateSpace:(file handle,size)->(offset)
FreeSpace:(file handle,offset,size)->(its empty)
Assign:(file handle,offset,buffer,size)->()
Read:(file handle,offset,buffer,size)->()
ReadRoot:(file handle)->(root offset)
SetRoot:(file handle,root offset)->()
CreateHeapFile:(file handle,intial root offset)->()

Note that all accesses/assigns to space allocated by the heap layer must go
through the heap layer as what may be contiguous in the upper layer may not
be contiguous in the heap layer. The root is provided as a handle onto the
root of all structures contained in the heap, it is provided as a boot
mechanism into the heap.


Data Structure Of A Heap File
-----------------------------

A heap file is organised in this general form:

<version byte>
<header>
<heap>

The version byte is discussed above.
The header is the heap's header and boot mechanism into the file
The heap contains the actual data stored in the heap.

The header is organised as follows:

Root offset:4

The heap is organised as follows:

<free blocks sorted by location tree root>
<free blocks sorted by size tree root>
<bucket array>

Blocks are, at one level, always allocated at least a given size. This given
size, call it M, must be at least big enough to store a node for both the
trees. This level of the heap is used for allocating large blocks (those >=
M in size), and is used by the small block allocator to allocate blocks
which it manages and divides up. The small block allocator allocates blocks
of a given small size using a bucket mechanism. The bucket mechanism
essentially holds onto small items all the same size, allocating them when
necessary. The bucket array is the array of buckets for given sizes of
block. Each array entry is a link to the start and end of a singly linked
list of blocks (large blocks), each of this form:

<link>
<bit map of usage>
<array of blocks of the given size>

The lists are managed such that those blocks with some unused small blocks
in them are at the head of the list, and those without at the end. There are
never any blocks in the lists with all small blocks in them free - these
being freed to the large block allocation mechanism.

