Btree directories (Re: Status of HFS+ support)

[flar at allandria.com]

Andi Kleen wrote:
> Only 64bit though, which may or may not be enough. If HFS indexes directly
> with names instead of hash values it'll probably not be enough so they
> would need to fall back to the no shrink hack.
> Anyways, you probably cannot ignore telldir of 32bit programs.

Yes, that's the main problem with HFS/HFS+. All catalog entries are keyed
on a combination of parent directory ID and filename, because this is the
data MacOS asks for when a file is opened. These entries have to be sorted
inside the tree, and the sort rules are a little messy, since the string
compares are supposed to be case-insensitive. If you are opening a file,
or doing a lookup() it's very convenient. If you are doing readdir() it's
a massive headache. Basically you have to find the first entry with a
parent ID that matches the directory being read, and then read every
entry in order until you find one with a different parent. Because of
the sorting issue, it's not just a problem with shrinking the directory,
because growing the directory could cause the same problem. In fact,
growing or shrinking ANY directory on the filesystem could theoretically
change the entire tree by forcing the tree to add a new layer of index
nodes and rebalancing the tree. It gets very messy. There's a reason the
HFS filesystem code in the kernel has always had a habit of destroying
disks any time it has to do anything too complex.

	Brad Boyer
	flar at pants.nu


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/