Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!wuarchive!psuvax1!rutgers!cbmvax!steveb
From: steveb@cbmvax.commodore.com (Steve Beats)
Newsgroups: comp.sys.amiga.tech
Subject: Re: FFS and hash chains
Keywords: FFS
Message-ID: <14802@cbmvax.commodore.com>
Date: 2 Oct 90 16:16:55 GMT
References: <1348@cuenews.UUCP>
Reply-To: steveb@cbmvax.commodore.com (Steve Beats)
Organization: Commodore, West Chester, PA
Lines: 31

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