Gold Fish 1/GoldFishApril1994_CD2.img/d4xx/d429/dr/source/fastexnext.doc

Text File | 1991-01-10 | 17KB | 279 lines

                         FASTEXAMINE AND FASTEXNEXT

As we all know, the AmigaDOG ExNext() function is inexcusably inefficient,
as implemented by the old file system.  This is one way to approach
remedying the symptoms of that lameness.  (Too bad I didn't finish this three
years ago, huh?  Well, I couldn't afford an Amiga then.)

The idea here was to make two functions FastExamine() and FastExNext()
which would be completely compatible fast replacements for Examine and
ExNext in C programs.  Unfortunately, the goal of full compatibility has
proven impossible (at least for me), and all that the partial compatibility
means is that it's not too much work to convert an ExNext scanning routine
to a FastExNext routine, and that it's no trouble to internally convert a
FastExNext call to a regular ExNext when necessary.

The known differences from the Dos Examine and ExNext functions are:

     -- VERY IMPORTANT:  You have to use an extended version of the
        FileInfoBlock struct, with two extra longwords added onto the end.
        Something like this will do:
            struct Fib {
                struct FileInfoBlock f;         /* no "*" !! */
                long p, s;
            };
        The last extra field (called s above) must be initialized to either
        zero or negative one.  Use zero if you are not going to do a
        recursive scan of subdirectories (details below).  If you fail to
        initialize this field, prepare to meditate.  Use this struct as you
        would normally use struct FileInfoBlock, like FastExamine(lock, fib).

     -- VERY IMPORTANT:  There's a cleanup function you should use if you
        stop scanning before you reach the end of the directory.  Like this:
        FastExCleanup(fib); (where fib is the extended FileInfoBlock you've
        been passing to FastExNext).  Otherwise memory etc. won't be
        deallocated, and in the case of a floppy disk, THE MOTOR WON'T GET
:-(     TURNED OFF until the next file operation.

     -- If you want to do a recursive scan of subdirectories, there is
    special optimization you can use, by setting the last longword of the
    extended FileInfoBlock (the s field of struct Fib above) to negative
    one before calling FastExamine.  This will be referred to as using
    "the deep version" in this document.  This optimization works not
    just for recursive descent, but for any succession of nonrepeating
    multiple scans.  It causes FastExNext to remember extra information,
    so as to reduce the amount of disk reading it has to do.

     -- The set of possible error returns might be different.  Details below.

     -- You can't (yet) start inner FastExNext scans using a fib from an
        outer FastExNext instead of FastExamine'ing the new inner directory
        lock.  You MUST copy the struct Fib and then FastExamine with the
    copy, before using FastExNext on the inner directory.  Or you must at
        least copy the s field and then FastExamine.

     -- The files are returned in a different order.

     -- These are C functions.  Calling them in assembly has no resemblance
        to calling actual shared library Dos functions.  Furthermore, I have
    no knowledge of whether they will compile correctly without Aztec C,
    though I have no specific reason to think they won't.

     -- And, of course, it makes your program bigger (about 5k) and
        greedier.  But not as greedy as you might think.                  ß^)

     -- Since we end-run the dos handler and use the device driver task,
        any data buffered in there won't help;  AddBuffers goes to waste.
        But AddBuffers does work for the Fast File System if you're not using
        the deep version, because end running offers no advantage then.

     -- Examine often does not need to do any physical IO, but FastExamine
        usually reads one track, and may initiate the reading of another, if
        I ever get around to making the disk IO asynchronous, which I perhaps
        won't because the performance improvement is gonna be petite.

     -- FastExNext might return slightly out-of-date information if files are
        being renamed or deleted or whatever during the scan.

The cleanup function FastExCleanup() takes as its one parm the pointer to the
extended FileInfoBlock (struct Fib or whatever you want to call it) that
you've been using for the FastExNext scan and returns nothing.  It checks to
see whether it's involved in a current scan that is end-running regular
ExNext, and if so it turns off the disk motor (if it's a floppy), closes the
device, and frees all the memory it was using.  This is done automatically
when you get to the last entry in the directory, and is unnecessary if the
original FastExamine hit a file instead of a directory, if you're not using
the deep version.  If you attempt FastExNext on a FastExCleanup'ed fib, it
will yield ERROR_NO_MORE_ENTRIES, even if the scan wasn't finished.  If you
use the deep version, call FastExCleanup ONLY ONCE when the complete scanning
operation is finished.  Do NOT call it when an inner scan is finished but you
still want to finish an outer scan.  Furthermore, FastExCleanup is NEVER
AUTOMATIC with the deep version, you MUST call it when done scanning.  Even
if the first FastExamine does not return a directory.

The easiest way to handle FastExCleanup is not to test for different error
returns, but simply to call it always whenever you know that the directory
scan you are doing is over.  This is the most important change you will have
to make to change an ExNext program into a FastExNext program, besides using
the extended FileInfoBlock in place of the normal one.  It's okay to use
FastExCleanup twice on one fib.

One other thing to change, at least in the current version, is this:  with
regular ExNext, you can do a recursive scan of a subdirectory simply by
taking the fib from the ExNext that found this inner directory and passing it
to another ExNext with a lock on that subdirectory.  You can finish the upper
scan with a saved copy of the fib, or abandon it.  With FastExNext, you
currently must start each inner scan with another FastExamine with a separate
fib.  I might fix this someday.  Also:

IMPORTANT!  When using the deep version you must start each inner scan using
a fib THAT IS A COPY OF ONE THAT HAS BEEN USED IN A PREVIOUS SCAN; you cannot
start with a blank fib.  Or at least you must copy the value in the last
longword (the s field).  None of the optimization will work if this
information doesn't get transferred, and it might also fail to free some
memory.  And I aint gonna promise that worse things won't happen.

These functions call regular Examine and ExNext in cases which they can't
optimize.  This happens when it's not a true AmigaDos disk, but instead
something like RAM:, or when the block size is not 512 bytes (I guess I
should fix that someday) (but I heard that the file system itself can't even
handle such yet), also in the case of a null lock (note that if you DupLock a
null you get null, but if you have a null CD and go Lock("", ACCESS_READ),
you get a real non-null lock), or when there's not enough contiguous memory
for a track buffer (some disks need chip ram, others don't), or if OpenDevice
fails (unlikely).  One more condition:  if the disk has a MaxTransfer mount
parameter that is set to a size smaller than one track, and the size of the
track is not evenly divisible by the MaxTransfer size (rounded down to the
nearest whole sector), then it will call regular ExNext.  So far the only
instances I've seen are 8K MaxTransfer on 16K tracks, with Quantum Q40
drives.  (These would cause gurus in an earlier version before I paid
attention to MaxTransfer.)  The performance of this thing is just about equal
to the Fast File System, or superior to it if you are using the deep version
for multiple directories.

This version can set the following IoErr codes in addition to 232 (no more
entries):  103 if you run out of memory, 211 if you pass it an invalid lock
(not guaranteed to catch all bad locks), 218 (not mounted) if you pop the
disk out of the drive and cancel the "please replace" requester, and 225 (not
a dos disk) if there's a hardware IO error or other general trouble in
reading the disk.  (Why is there no DOS error number for hardware errors??)
Also, if perchance you pass it a null FileInfoBlock pointer, it indicates an
error condition by crashing the system.  I don't know what the full set of
possible error returns from vanilla Examine / ExNext is.

When to stop scanning:  Official Amiga programs don't seem to agree whether
you should stop scanning when ExNext returns an error other than 232 (no
more entries).  Dir abandons the scan, List sometimes keeps trying, like
when you pop the disk out, even cancelling the "Please replace" requester
doesn't stop it, it keeps putting out the same output line until the disk
goes back in or you use control-C.  With FastExNext, my goal is that you can
continue past error if the error is 218 (not mounted) or 225 (not a dos disk
= device level error).  You won't get a complete directory list under such
conditions, and I'm not too sure if that works, so I recommend abandoning
the scan and calling FastExCleanup.  Particularly you should abandon the scan
if the user has clicked Cancel on a "Please replace..." requester, which will
have happened if you get error 218 and your pr_WindowPtr is not -1.  Old
ExNext sets IoErr 218 if the disk is out of the drive, with a "Please replace
... in any drive" requester, as opposed to the "... in unit  N" requester that
FastExNext uses, but if you pop the disk out during a hardware read and
cancel the "You MUST replace ... in unit  N !!!" requester, it sets IoErr to
(of all things) 232 "no more entries"!  How bogus!  And also, how bogus to
say "You MUST replace ... !!!" for a read-only operation that it actually
recovers from with no problems, as far as I can tell.

A note about System Requests that pop up when there's an error:  I had to
mimic the official system requesters by hand, sort of, and I have discovered
that the intuition AutoRequest function is the one part of this that is
capable of guruing when memory is low.  It's supposed to display an alert
under such conditions, but only does so if the memory is just slightly too
low (it needs 6k of contiguous chip ram to DisplayAlert).  (THANKS TO JOHN
GERLACH JR for AllocMaster, which helped me to make most of this pretty
bulletproof under low memory conditions.)  There are two requesters which
this can fire up:  "Please replace volume Xxxxxxxx in unit  N" and "Volume
Xxxxxxxxxxx has a read/write error".  This latter does not necessarily mean a
physically defective disk or drive.  Elsewhere in Dos this can come up if
there is simply a bogus block pointer somewhere.  This is used as a catchall
for all device level errors other than popping out the disk.  In BCPL I think
there is a ROM function for firing up an appropriate disk trouble requester
which automatically knows what to say.  Too bad the rest of us don't get to
see such a thing.

Late addendum to above:  Now FastExNext does not include the System Request
feature unless you compile it with the word QUEST #defined.  Otherwise errors
simply fall through to the calling program with no requester interruption.

(Actually, it is remotely possible to get a "You MUST replace !!!" requester
by popping out a disk during a FastExNext scan.  I have only seen this
rarely.  When you put it back in and click retry (which you must do
manually), FastExNext's own "Please replace" then comes up.  I do not
understand the cause of this, or how to detect it.)


MY NOTES ON REGULAR EXAMINE AND EXNEXT:
There is no extra data hidden in the fib.  Apparently they simply go by the
key field and the hash value of the name, which sometimes causes rereading of
the block(s) they just read, if they get interleaved with other disk
activity.  The EntryType and DirEntryType fields apparently always hold the
same value:  2 for a directory, including a root directory, or -3 for a file.
ExNext reads sequentially through the hash table, chasing each list to the
end and then scanning for the next nonzero hash entry.  It puts zero in the
length and blocks fields for directories.  Examine works correctly with a
null lock.  Bryce Nesbitt says that ExNext pursues chains of extension blocks
just to get an exact count of blocks used.  Forget it, I'm just gonna
calculate the block consumption from the length in bytes.  Which should work
except for those times when people create bogus zero-length files full of bad
blocks and suchlike.

ExNext works like this under the Fast File System:  Examine scarfs the table
of block numbers in the directory header, and ExNext simply sorts them and
reads through them from lowest to highest.  Discovering new blocks to read
on hash lists doesn't disrupt the order because the FFS always maintains the
hash lists in sorted order, with lower numbered blocks pointing to higher
numbered ones, so ExNext can insert them into the part of the sorted list
that hasn't been handled yet.

I've noticed that if you call Examine and then ExNext when the lock is on a
file, not a directory, it puts up a "read/write error" requester.  I opine
that this is way bogus.  FastExNext will simply return ERROR_NO_MORE_ENTRIES,
unless it is just passing the call through to regular ExNext.


HOW FASTEXNEXT WORKS:
FastExamine scarfs the entire track that the directory or file being examined
is on, and saves the hash table plus any blocks on that same track that point
to that directory as parent.  Any blocks which do so and are also mentioned
in the hash table get pushed onto a "ready" list.  Any which are not men-
tioned in the hash table go into the "maybe" group, which is stored as a
binary tree.  Each file consumes about 80 bytes of memory, or twice that if
it has a filenote, plus some more to hold its hash table if it is a directory
and you're using the deep version.  Each file put on the ready list gets its
number removed from the hash table, and if it has a hash chain pointer, that
number gets inserted into an empty space in the table, and the maybe tree is
checked to see if this block is present there.  If so, that one is moved from
the maybe group to the ready group, and its hash pointer is similarly
checked.  The total count of block numbers in the table never increases.
Whenever you ExNext, it simply returns a file from the ready list.  If the
ready list is empty, it reads the track which contains the block number in
the hash table which is closest to the last track read (assumed to be zero at
the beginning).  It then checks this track for readies and maybes just like
the first track.  This process continues until both the ready list and the
hash table are empty, at which time it automatically calls FastExCleanup.

It's not quite as efficient as the Fast File System when operating on a Slow
File System volume, because a pointer found in a hash chain might cause it to
skip back to a track it already passed over, and because it can't make use of
blocks buffered inside the file system (that is, AddBuffers doesn't help),
but it will never read the same track twice.  Unless it runs out of memory,
in which case it will "forget" some of the maybes, which might cause it to
reread a track if a maybe it forgot turned out to be needed after all.  On
the fast file system when not using the deep version, usually no maybies
would be saved at all because of the sorted hash chains.  For this reason
there is no performance advantage, so we use regular ExNext which can take
advantage of AddBuffers.

The deep version works by simply remembering ALL files and directories it
finds on any track it reads in the maybe tree.  This can consume many K of
memory if it reads lots of tracks on a hard disk.  But it saves a lot of disk
IO, because if some directory needs to check a track that some other
directory has already referenced, the information is waiting for it.
Directories that are found get their hash tables saved in an area separate
from the maybe tree.  (In fact, a redundant copy of the information in the
maybe tree is kept there, just to simplify coding.)  No track is read twice
between the first FastExamine and the final FastExCleanup, given enough
memory.  An inner FastExamine will take its information from the maybe tree
instead of reading the disk, if the relevant track has already been read.

FastExamine and FastExNext are written in Aztec C by

                Paul Kienitz                email: none. BBSes: try
                6430 San Pablo ave.           Winners Circle 415-845-4812
                Oakland, CA  94608            Triple-A 415-222-9416
                USA                           Just Computing 415-961-7250
                                              FAUG 415-515-2479

and are in the public domain.  Feedback is appreciated, ESPECIALLY if you
find some device it doesn't work with (I know of none), or any bug, or know a
way to make it smaller and/or better.  I suppose I could make a shared
library out of it...