Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!wuarchive!uunet!van-bc!ubc-cs!alberta!aunro!edm!cuenews!andrew From: andrew@cuenews.UUCP (Andrew Folkins) Newsgroups: comp.sys.amiga.tech Subject: FFS and hash chains Keywords: FFS Message-ID: <1348@cuenews.UUCP> Date: 30 Sep 90 02:38:50 GMT Followup-To: comp.sys.amiga.tech Organization: AmiCUE (Amiga SIG, Commodore Users of Edmonton) Lines: 61 [ 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)