andrew@cuenews.UUCP (Andrew Folkins) (09/30/90)
[ Let's hash the lineeater and see what comes out ]
I wrote a simple 'list' type program while trying to find an error on
my hard drive, and came across ..., well, read on.
As I said, a simple program using Examine() and ExNext(). We print out
the fib_DiskKey to get the block number, the hash function is right out
of an old AmigaLine (or does that date me? :-). Anyway, under OFS,
a program using these calls basically does the following:
For each non-zero entry in a UserDirectory block's hash table
Get the File Header block
while the HashChain pointer is not zero
Print the file name of the header block
Get the next header block
Get the Parent block
OK? That's why an OFS dir command is so slow - while you're following
the hash chains you're skipping all over the disk. ExNext() simply
looks at the sector indicated in the FileInfo parameter, follows the
HashChain pointer if there is one, otherwise it uses the Parent
pointer to skip back to the parent UserDirectory, and continues
searching the hash table.
Now, under the FFS, I can't figure out what's going on. It's
definitely *not* the same, as printing the hash table values while
'list'ing produces something like:
sector track sector head hash filename
74375 364 17 3 52 list
74868 367 00 0 59 list.lnk
75259 368 17 5 47 list.c
75274 368 32 5 59 list.o
77000 377 24 2 0 skeleton.c
77002 377 26 2 33 textmap.c
77004 377 28 2 51 isqrt.c
77006 377 30 2 54 textmap
77008 377 32 2 5 textmap.lnk
77178 378 32 1 52 conpackets.c
etc.
The things to notice are that a) the processing appears to be done in
_sector_ order, b) the hash values are ignored, and c) duplicated hash
values (i.e. 52) do not follow each other (indicating that the hash
chains are not being followed).
I can understand part of this: FFS appears to be traversing the hash
table from lowest to highest sector number, instead of from position 0
to 71, and processing FileHeader blocks on a per cylinder basis.
ExNext() just grabs the Parent pointer from the current FileHeader and
searches for the next FileHeader with the same parent. At the end of
the cylinder, we jump back to the parent and look through the hash
table for the next higher cylinder.
But there's obviously something wrong there - how do we find the files
in the hash chains when we don't seem to be following the hash chains?
--
Andrew Folkins ...!alberta!edm!cuenews!andrew Edmonton, Alberta, Canada
^A1000^
Newsfeed for the Amiga SIG of the Commodore Users of Edmonton (AmiCUE)peterk@cbmger.UUCP (Peter Kittel GERMANY) (10/02/90)
In article <1348@cuenews.UUCP> andrew@cuenews.UUCP (Andrew Folkins) writes: > >Now, under the FFS, I can't figure out what's going on. It's >definitely *not* the same, as printing the hash table values while >'list'ing produces something like: > > sector track sector head hash filename > 74375 364 17 3 52 list > 74868 367 00 0 59 list.lnk > 75259 368 17 5 47 list.c > 75274 368 32 5 59 list.o > 77000 377 24 2 0 skeleton.c > 77002 377 26 2 33 textmap.c > 77004 377 28 2 51 isqrt.c > 77006 377 30 2 54 textmap > 77008 377 32 2 5 textmap.lnk > 77178 378 32 1 52 conpackets.c > etc. Thank you for exploring these details. Please correct me if I'm wrong, but this seems to be a sort of elevator seeking already. Everytime the algorithm finds a new block number, it does not go to that sector immediately but puts it into a sorted list of sectors yet to search for. Thus you can avoid many of the head movements necessary with the older, dumber mechanism. If I understand it correctly, there may still arise problems when the blocks are spread too wildly, but also then it boils down to only a few passes of the head across the disk. (This is all only speculation, I don't know the source, but had thought about this one already long for myself, but didn't get time for it. So I'm very pleased that they've done it already at West Chester, thanks.) -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
steveb@cbmvax.commodore.com (Steve Beats) (10/02/90)
In article <1348@cuenews.UUCP> andrew@cuenews.UUCP (Andrew Folkins) writes: >[lots of info about OFS and FFS directory scanning deleted] > >I can understand part of this: FFS appears to be traversing the hash >table from lowest to highest sector number, instead of from position 0 >to 71, and processing FileHeader blocks on a per cylinder basis. >ExNext() just grabs the Parent pointer from the current FileHeader and >searches for the next FileHeader with the same parent. At the end of >the cylinder, we jump back to the parent and look through the hash >table for the next higher cylinder. > >But there's obviously something wrong there - how do we find the files >in the hash chains when we don't seem to be following the hash chains? > When the first ExNext is performed FFS grabs all the keys referenced in the hash table of the owning directory and sorts them. This sorted list is associated with the lock that was used for the ExNext call. Now the first entry in the list is fetched and after some sanity checks the info is placed in the FileInfoBlock. If the current header has something on its hashchain, that entry is merged into the existing list. Since FFS hashchains are sorted, you`re guaranteed to travel in one direction on the disk. This also works for unsorted hashchains but then you will occasionally have to seek back. Of course, the real world isn`t that simple. FFS contains all manner of safety checks and recovery procedures to cater for programs that UnLock the lock between calls to ExNext. This loses all the state information (and sorted list of keys) which must be rebuilt and traversed back to the original point in the exnext chain. Steve