Re: Extensions to HFS filesystem

Paul H. Hargrove (hargrove@sccm.stanford.edu)
Sun, 05 May 1996 19:59:53 -0700


H. Peter Anvin wrote:
>
> In article <199604300106.SAA04153@Kutta.Stanford.EDU>,
> Paul H. Hargrove <hargrove@sccm.stanford.edu> wrote:
> >
> >> 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.
> >
>
> Actually, that is a pretty darn close emulation of the UNIX behaviour.
>
> Consider the filename of the hidden file a "virtual inode number", and
> you will see why it works. It pretty much will solve all the semantic
> problems. It is still ugly, but I don't think there is a way around
> *that*.
>
> -hpa

This actually makes a lot of sense now that I think through it enough.
The filename could be the ASCII representation of the inode number (CNID)
since that is known to be unique. Then the correspondence to normal UNIX
behavior is more obvious.

Keeping them all inside a single hidden directory would remove the UMDOS
problem with directories that can't be deleted due to a hidden file inside
and the problem of a unresolved link due to a renamed parent directory.
This is all possible under HFS (but not FAT) because there is actually a
number that can be used as the inode number.

There is only one problem that I see remaining and that is the task of
keeping an accurate count of the number of links to these files. Counting
links that are created and destroyed under Linux is no problem. However
if the last is deleted under MacOS then the file continues to use disk
space until some sort of garbage collection is done (in user space I
hope). The fact is, however, that by representing a hard link as a
pseudo-symlink to a hidden file means that a copy of the link under MacOS
would create an extra link. This means that the kernel can't know when it
is deleting the last link unless the kernel actually does the garbage
collection (i.e. link counting) when the fs is mounted. I really don't
want to do the counting in the kernel.

One option I may explore is have fsck.hfs do all the link counting and
any other post-MacOS-use cleanups, and extend the definition of "dirty"
to include use of the fs by MacOS since the last use by Linux. Such a
fsck would remove ALL the links if the luser was dumb enough to delete
the hidden file under MacOS.

Under my original proposal every hardlink, symlink and device would use
the HFS equivalent of one "cluster", which in the worst case is 1/32767
of the disk and 1/65535 in the best case. If you have a 1Gb HFS fs then
devices and links would take 16k each, as under UMSDOS. I don't like this
idea very much so I've been thinking of an alternative. If all the info
such as device numbers and "link targets" were stored in a single database
then links and devices would be empty files and would only use the disk
space required for their directory entries and the space in the database.

This database would actually be easy to implement efficiently since the
HFS code includes routines for manipulating the B*-trees which store the
directory and allocation information. An additional B*-tree could hold
all the "extra" info such as UNIX uid, gid and permissions for all files
and directories and "link targets" and device numbers. The records in a
B*-tree are variable length with a practical limit of just under 255
bytes. Symlinks that are too long to fit in a record would be stored in
a disk block allocated to the file, just as ext2 does if the name won't
fit in the inode. In essence this B*-tree would hold inode entries for
all the files that have them. As under UMSDOS files without an entry in
the "inode B*-tree" would receive default uid, gid and permissions as is
currently done in HFS.

Under this "inode B*-tree" system fsck.hfs would still need to update the
link counts and remove the "inodes" for files that have been deleted (or
had all their links deleted in the case of the special hidden files) under
MacOS. However, since the data is no longer associated directly with the
file under MacOS, a Finder copy of a symlink, hardlink, fifo, socket or
device file would produce an empty file that has the Creator and Type of
the original, but would under Linux would have none on the special
properties of the original. I think this is an acceptable solution.
What do others think of this idea?

One other note: I guess I'd put the complete i_mode field into the "inode"
so I'd not need different Types for each variety of special file, so I was
thinking of using "EHFS" (Extended HFS) for the Creator and "V1.0" for the
Type, with the Type to be incremented in any later revisions that use an
incompatible format for the "inode".

I have not yet considered how to deal with the fact that HFS is mixed-case
but case insensitive. I want a name-mangling scheme that leaves the file
recognizable under MacOS. Note that HFS names are 31 characters long so
there is no need extend it.

To prevent name conflicts with the inode B*-tree and the directory full of
multi-linked files. I plan to use the simple fact that '/' is a legal
character in HFS filenames (but not Linux ones of course). I have not
picked actual names yet, but they will certainly contain '/'.

With the B*-tree for inodes and an acceptable name-mangling scheme I
imagine that EHFS could be a POSIX file system. However I could be
missing something. Comments?

-- 
Paul H. Hargrove                   All material not otherwise attributed
hargrove@sccm.stanford.edu         is the opinion of the author or a typo.