Messages in this thread |  | | From | "Paul H. Hargrove" <> | Subject | Re: Extensions to HFS filesystem | Date | Mon, 29 Apr 1996 18:06:52 -0700 (PDT) |
| |
Raul Miller <rdm@tad.micro.umn.edu> wrote: > Hi, I've tried to reverse-engineer UMSDOS on several occasions (and > have always given up for lack of time). Here's a few leading > questions from my point of view: > > How does HFS currently deal with multiple files with the same CNID? The CNID is unique. HFS stores the location of the first three contiguous pieces of the file in the directory entry and the remainder of the allocation information in a B-tree sorted on a key that had the CNID as the most significant part. Multiple directory entries witht he same CNID would thus share part of the file contents automatically but great expense would be required to keep the allocation info in the directory entries consistent (not to mention the fact that a genuine Mac wouldn't keep the info up-to-date and something like Disk First Aid would complain.) The short answer is that multiple entries w/ the same CNID are illegal.
> How does HFS deal with a file which is in use by a program, but has > been removed from the file system? I handle this pretty much the same way as a native Linux filesystem. When the file is unlink()ed the directory entry is removed from disk and the i_nlink field of the in-core inode is set to zero (it must have been 1 before, and yes I do check that it is). When the file is no longer in use the put_inode() callback for HFS truncates the file to zero length, releasing the disk blocks that were in use and removing the allocation information from the B-tree. There is no messy hidden file or anything like that.
> If both of these are illegal under HFS, consider a special folder for > files that don't have the proper number of references. For the case > of multiple (hard) links, represent them using some reference into > that directory. I don't see that this is any better than the UMSDOS trick of having hardlinks be symlinks to a hidden file. The potential problems with a directory moving are reduced by keeping the files all in one location, but I still don't like the idea of the hidden file.
> If searching on a folder is linear time (is it?), consider > implementing something like a b-tree (or even just a hash table) using > nested folders, as this special folder might become quite large under > some circumstances. Since HFS directory entries are stored in a B-tree the time to find a file given the CNID of the directory containing it and its name is O(log(N)) where N is the total number of files and directories on the disk. Finding the Mth entry in a directory, however, is O(M).
> -- > Raul ---- Paul H. Hargrove All material not otherwise attributed hargrove@sccm.stanford.edu is the opinion of the author or a typo.
|  |