Amiga Developer CD v1.2/amidev_cd_12.iso/reference/amiga_mail_vol1/dos/ffsandrom

Text File | 1990-01-26 | 18KB | 390 lines

(c)  Copyright 1989 Commodore-Amiga, Inc.   All rights reserved.
The information contained herein is subject to change without notice, and
is provided "as is" without warranty of any kind, either expressed or implied.
The entire risk as to the use of this information is assumed by the user.




                  Low Level Differences Between FFS
                     and the ROM Filing System

                         by Steve Beats


Most developers know by now that a Fast Filing System (FFS) for hard disks
has been added to V1.3 of the Amiga system software.  The following are
descriptions and 'C' structure definitions representing the current layout
of data on both the new FFS and the old ROM filing system disks.

These structures are provided for those of you who wish to write disk salvage
utilities and have a valid requirement for this information.  It is also quite
useful to have this information handy if you've managed to trash a partition
and only have DiskEd available to attempt fixing it.  Please note that these
structures assume a fixed, 512 byte disk block.  This is a valid assumption
for filing systems up to V1.3.  However, this will NOT be the case under
V1.4 Kickstart which will support full variable-sized disk blocks.

DiskDoctor-type utilities should run as many DOS checks as possible before
assuming a disk has the layout described here.  Check the DOS type field on
the boot block and run checksums on the root block after ensuring that the
static fields are set to the expected values.  Hash table size will always
be set to 72 for instance, this can be used as one of the consistency checks
before proceeding to directly read from or write to the disk.

NEVER use this knowledge in an application program.  It is guaranteed to
break under V1.4 Kickstart.  We are moving away from the single file system
environment, especially since it's so easy to create and mount alternate
filing systems on the Amiga.  Applications should stick strictly to the DOS
library routines or the packet interface to a filing system.  Any other method
of accessing files from the disk will not work.





The Boot Block
--------------

The boot block is always on the first sector of a partition.  This is
calculated as LowCyl * Surfaces * BlocksPerTrack.  The only field of any
use in the boot block is the first ULONG.  This should contain the string
"DOS" terminated by a 0 for the old filing system or a 1 for the fast filing
system.  Generally this should be the only field that needs checking to
determine file system type.

However, if the first cylinder of a partition has gone bad, this field may
be invalid.  In this case, it is possible to use just the root block and the
data blocks to determine file system type.  Under V1.3 Workbench, DOSType
can be determined from the environment vector for the given partition
so this is a good alternative to snooping other parts of the disk.

On floppy drives, the boot block will also contain boot code which is
responsible for initializing DOS when booting from a floppy.  Make sure this
data remains valid, or advise the user to run Install before using the
"doctored" disk again.  On hard disks, there is no code executed from the
boot block, it is the responsibility of an autobooting hard disk driver to do
the DOS intitialization.  In this case, it's OK to write back the boot block
with just the DOSx identifier initialized.


Root Block
----------

This is the most important block as far as the filing system is concerned.
It is called the root block because it is actually the "root" of the filing
system tree.  All other files and directories are accessed by keying them
off the root block.  Even if a file is stored many levels deep in the
directory structure, it is ultimately connected to the root through its
parent directories.

If the root block of a disk goes bad, then the whole partition will have to
be scanned for "orphaned" files and directories.  The links to these
recovered files will have to be rebuilt in a new root block which can then
be written back to disk.

The root is positioned such that the worst case seek to get to the root will
be no more than half the number of cylinders in the partition.  In other
words, the root is in the middle of the partition.  The disk block that the
root is stored on is calculated as follows:

    LowerKey = LowerCyl * Surfaces * BlocksPerTrack + Reserved
    UpperKey = ((UpperCyl+1) * Surfaces * BlocksPerTrack) - 1
    RootKey  = (UpperKey - LowerKey) / 2

Note that the UpperKey used here may not be the physical UpperKey used by
an FFS partition if PreAlloc is set to something other than 0.  Since the use
of PreAlloc was a new feature of FFS it was not included in the calculation
of the root block so as to maintain compatibility with the Format and DiskEd
commands.  If an FFS partition is being used, UpperKey should be modified as
UpperKey -= PreAlloc AFTER performing the root block calculation.  The values
of UpperKey and LowerKey will be useful for checking extension and hash
chains for validity.

   Note: all block numbers stored within the filing system are relative to
   the beginning of the partition not including the Reserved blocks.  This
   means that the physical disk block = LowerKey + Block# - Reserved.  Since
   a block number of 0 is used to terminate lists, the zero block can never
   be made available to the filing system.  Hence the need for at least 1
   "Reserved" block on all partitions.

Here is the 'C' structure definition of a 512 byte root block as used by
both FFS and OLDFS partitions or floppies.  It is very similar to a
UserDirectoryBlock but some of the fields are different or used in a
different manner by the filing system.




   struct RootBlock {
    LONG    Type;        /* This is used to mark the type of this
                   block and is set to TYPE_SHORT (2) */
    ULONG    OwnKey;        /* Not used by root, must be set to 0 */
    ULONG    SeqNum;        /* Not used by root, must be set to 0 */
    ULONG    HTSize;        /* Size of the hash table in longwords,
                   must be set to 72 */
    ULONG    Nothing1;    /* reserved for future revs, must be 0 */
    LONG    Checksum;    /* balance to 0 checksum.  When all longs
                   in the block are added (ignoring carry)
                   the sum should be 0 */
    ULONG    HashTable[72];    /* hash table containing block numbers of
                   files and directories in the root */
    LONG    BitmapFlag;    /* flag to say whether the bitmap is valid
                   or not.  -1=valid. 0=invalid.  If a
                   partition is mounted (or uninhibited)
                   with BitmapFlag = 0 then the validator
                   will kick in to rebuild the bitmap */

/* the BitmapKeys and BitmapExtend fields shown here are valid for FFS only.
   The ROM filing system has these two entries reversed and the slots in the
   BitmapKeys array are used from BitmapKeys[24] to BitmapKeys[0] */

    ULONG    BitmapKeys[25];    /* An array of block numbers for the bitmap
                   on this partition.  A block number of 0
                   indicates the end of the list. */
    ULONG    BitmapExtend;    /* If all of the BitmapKeys have been used
                   then this will contain the block number
                   of a disk block containing more Bitmap-
                   Keys.  0 means no extender block present.
                   OLDFS has a bug where it assumes that
                   the root has protection bits and attempts
                   to set them.  Since they coincide with this
                   field, this is why there is a 53Meg limit
                   on partition size under OLDFS */
    ULONG    DirAltered[3];    /* A DOS DateStamp indicating the date when
                   the root block was last modified or a
                   file in the root block was modified */
    char    Name[40];    /* Name of this volume as a BCPL string
                   with number of bytes as the first
                   character.  Only 30 chars used */
    ULONG    DiskAltered[3];    /* A DOS DateStamp indicating the date when
                   any file or section of the partition was
                   modified.  (FFS has a bug which prevents
                   it from updating this correctly, the
                   DirAltered date gets changed instead) */
    ULONG    DiskMade[3];    /* A DOS DateStamp indicating the date when
                   this partition was first formatted and
                   therefore created */
    ULONG    Nothing2;    /* reserved for future revs, must be 0 */
    ULONG    Nothing3;    /* reserved for future revs, must be 0 */
    ULONG    Nothing4;    /* reserved for future revs, must be 0 */
    LONG    SecondaryType;    /* Qualifier to Type.  Will be set to
                   ST_ROOT (1) */
};


Bitmap Extension
----------------

Bitmap extensions, which are pointed to by the BitmapExtend entry in the root
block, are very simple in structure.  They consist of a list of 127 pointers
to bitmap blocks with the last entry being a pointer to another bitmap
extender block.  There are no checksums on this data at all.  An entry of
0 terminates the list.


Bitmap blocks
-------------

Bitmap blocks are pointed to by the root blocks BitmapKeys array and also
by any subsequent bitmap extender blocks if the disk is large enough.

Each bitmap block contains a longword sum-to-zero followed by 127 longs of
bitmap information (i.e., the 128 longwords in the bitmap block will sum up
to zero on a valid disk).  This means that each bitmap block can hold enough
information for 127*32 disk blocks or just less than 2 Megabytes of disk
space.

The bits in the bitmap do not correspond exactly to the way that the blocks
are arranged on the disk.  This is an artifact caused by the method in which
the bitmap is accessed.  When determining or setting the state of a bitmap
entry, the filing system fetches the data a longword at a time and then uses
the block number modulo 32 to determine which bit in that longword is to be
examined.

This means that bit 0 of longword 0 corresponds to block LowerKey while bit 0
of longword 1 corresponds to block LowerKey+32.  If you were to examine the
bitmap left to right one bit at a time, the bits would appear to be backwards
on 32 bit boundaries.  However, if you access the bits logically using the
68000 bit manipulation instructions, left to right ordering is preserved.

The bitmap only contains information about the blocks LowerKey through
UpperKey.  That is, Reserved and PreAlloc'ed blocks are not included in the
bitmap.  The bitmap blocks themselves are included and marked as used.

A bit set to 1 in the bitmap indicates that the corresponding block in the
partition is free while a 0 bit indicates that the block is used.  While
this may seem backwards, there is a valid reason for this.  When the filing
system is searching for a free block it is much easier to test a longword at
a time for the non-zero condition.  This indicates that there is a free bit
somewhere in that block of 32 bits and a bit search can be started.

If 0 were to indicate a free block, every single bit would have to be tested
individually to see if there were any free ones.  Testing all 32 bits at
once would not yield any useful information apart from the fact that all of
the blocks were free, a particularly rare occurence in a typical partition.




User Directory Blocks
---------------------

The user directory blocks are distinct from the root block in that they are
creatable and deletable by the user or application program.  The root block,
while being a special case of a directory, cannot be created or deleted
using normal filing system calls.  Another major distinction is that the root
will NEVER have a parent directory while user directory blocks will ALWAYS
have one.

   struct UserDirectoryBlock {
    LONG    Type;        /* This is used to mark the type of this
                   block and is set to TYPE_SHORT (2) */
    ULONG    OwnKey;        /* Set to directory's own block number */
    ULONG    Spare1;        /* Not used, must be set to 0 */
    ULONG    Spare2;        /* Not used, must be set to 0 */
    ULONG    Spare3;        /* Not used, must be set to 0 */
    LONG    Checksum;    /* balance to 0 checksum.  When all longs
                   in the block are added (ignoring carry)
                   the sum should be 0 */
    ULONG    HashTable[72];    /* hash table containing block numbers of
                   files and directories in this directory */
    LONG    Spare4;        /* Not used, must be set to 0 */
    LONG    Spare5;        /* Not used, must be set to 0 */
    ULONG    Protection;    /* Protection bits for this directory */
     LONG    Spare6;        /* Not used, must be set to 0 */
    char    Comment[92];    /* Directory comment as a BCPL string, only
                   80 characters can be used including the
                   length byte at the beginning */
    ULONG    Created[3];    /* DOS DateStamp struct indicating when
                   this directory was created or modified */
    char    DirName[36];    /* name of this directory as a BCPL string.
                   only 30 characters are used */
    LONG    Spare7[7];    /* Not used, must be set to 0 */
    ULONG    HashChain;    /* block number of the next file on the
                   hashchain if there's a hashing collision.
                   0 means no next file or directory. */
    ULONG    Parent;        /* Block number of the parent directory of
                   this directory.  */
    ULONG    Spare8;        /* Not used. must be set to 0 */
    LONG    SecondaryType;    /* Qualifier to Type.  Will be set to
                   ST_USERDIR (2) */

   };


File Header Blocks
------------------

All files have an associated file header block that describes the file name
and creation date along with pointers to the required ancilliary data such
as extension blocks and protection information.  When a file is Locked the
returned FileLock has a field called fl_Key.  This field contains the block
number where this header can be found in the partition. (This field contains
an address in the case of the RAM disk).

This is one of the few things that can be assumed about file locks, and will
be supported in future revisions of the DOS filing system.  It's advisable
for alternate filing systems to support this field too, though not strictly
nescessary or enforced by the operating system.

   struct FileHeaderBlock {
    LONG    Type;        /* This is used to mark the type of this
                   block and is set to TYPE_SHORT (2) */
    ULONG    OwnKey;        /* Set to file headers own block number */
    ULONG    HighSeq;    /* total blocks used in file (not updated
                   by FFS, only the old filing system) */
    ULONG    DataSize;    /* number of data blocks used for this file */
    ULONG    FirstBlock;    /* block number of first block in the file */
    LONG    Checksum;    /* balance to 0 checksum.  When all longs
                   in the block are added (ignoring carry)
                   the sum should be 0 */
    ULONG    DataBlocks[72];    /* table of block numbers for the first 72
                   blocks of data in this file.  Slots are
                   used from DataBlocks[71] back to
                   DataBlocks[0], then extension is used */
    ULONG    Spare1;        /* Not used, must be set to 0 */
    ULONG    Spare2;        /* not used, must be set to 0 */
    ULONG    Protect;    /* protection bits mask */
    ULONG    Date[3];    /* DOS DateStamp indicating creation date */
    char    FileName[36];    /* Filename (only 30 characters used though) */
    ULONG    Spare3[7];    /* not used, must be set to 0 */
    ULONG    HashChain;    /* next entry with the same hash value */
    ULONG    Parent;        /* block number of parent directory */
    ULONG    Extension;    /* when all data block slots are used, this
                   points to an extension block that has the
                   same format as the file header block (but
                   FileName and Date are not maintained and
                   secondary type is ST_LIST (16)). A
                   Block number of 0 terminates the list */
    LONG    Second;        /* qualifier to type = ST_FILE (-3)
   };



Data Blocks
-----------

FFS puts nothing but data into data blocks so that it can make full use of
a DMA controller.  There is no need to strip any extra information before the
data can be DMA'ed directly to the caller's buffer.  The old filing system is
a little more paranoid and puts a lot of checksum information at the front
of each data block.  The format of a data block under the old system is as
follows.

   struct FileDataBlock {
    LONG    Type;        /* This is used to mark the type of this
                   block and is set to TYPE_DATA (8). There
                   is no secondary type on a data block */
    ULONG    OwnKey;        /* Set to data blocks own block number */
    ULONG    SeqNumber;    /* Sequence number of this block in the file */
    ULONG    DataSize;    /* number of bytes of info used in this block */
    ULONG    NextBlock;    /* block number of next block in the file */
    LONG    Checksum;    /* balance to 0 checksum.  When all longs
                   in the block are added (ignoring carry)
                   the sum should be 0 */
    char    Data[488];    /* the actual data */
   }


Hashing Algorithm
-----------------

The hashing algorithm, which is used to determine where a file header goes in
the hash table of a directory, is the same for both FFS and the ROM filing
system.  The easiest way to describe it is with a small 'C' function.  Given
a CPTR to a BCPL string, this routine will return the array index into the
hash table.  This value is used to insert the file header with that name into
the appropriate hash table entry in the owning directory.

Hash( name )
unsigned char *name;
{
int val,i;

    val = (int)*name++;
    for(i=0; i<val; i++) val = ((val*13) + (int)toupper( *name++ ))&0x7ff;
    return(val % 72);
}

One major difference between FFS and the old filing system is that hash
chains MUST be sorted for FFS.  When a hashing collision occurs, files
are linked together using the HashChain entry in the FileHeaderBlock or
UserDirectoryBlock.  The old filing system sticks the new header at the
head of the list, while FFS merges the new header into the list in
ascending block order.

If FFS finds an unsorted hashchain, files will begin to dissappear when
ExNexting a directory.  This "missing" file can still be accessed by name,
so renaming it something else and back to its original name will resort the
hashchain.  This should only be a problem if your FFS partition was created
using early gamma versions of FFS and you didn't reformat when installing
the release version.

Most differences between the old filing system and the new Fast Filing System
have been covered here.  Remember it is not appropriate to use this
information in applications other than disk salvage utilities.  You should
expect more changes to the file system under V1.4.  In particular, variable
sized blocks will be supported in the next release.  Stick to system calls
and the packet interface to insure future compatability.