[patch 0/2] HFS+: custom dentry hash and comparison operations

[patch 0/2] HFS+: custom dentry hash and comparison operations

[Duane Griffin]

The HFS+ filesystem is case-insensitive and does automatic unicode
decomposition by default, but does not provide custom dentry
operations. This can lead to multiple dentries being cached for lookups
on a filename with varying case and/or character (de)composition.

These patches add custom dentry hash and comparison operations for
case-sensitive and/or automatically decomposing HFS+ filesystems.
Unicode decomposition and case-folding are performed as required to
ensure equivalent filenames are hashed to the same values and compare
as equal.

Tested on i386, x86_64 and PPC.

See bug reports here for more information:
http://bugzilla.kernel.org/show_bug.cgi?id=7240
http://bugs.gentoo.org/show_bug.cgi?id=178298

Cheers,
Duane Griffin.

-- 
"I never could learn to drink that blood and call it wine" - Bob Dylan

[patch 1/2] HFS+: Refactor ASCII to unicode conversion routine for later reuse

[Duane Griffin]

[-- Attachment #1: hfsplus-refactor-unicode.patch --]
[-- Type: text/plain, Size: 3890 bytes --]

Refactor existing HFS+ ASCII to unicode string conversion routine to
split out character conversion functionality. This will be reused by
the custom dentry hash and comparison routines. This approach avoids
unnecessary memory allocation compared to using the string conversion
routine directly in the new functions.

Signed-off-by: Duane Griffin <duaneg@dghda.com>
---

--- linux-2.6.21.orig/fs/hfsplus/unicode.c
+++ linux-2.6.21/fs/hfsplus/unicode.c
@@ -239,58 +239,97 @@ out:
 	return res;
 }
 
-int hfsplus_asc2uni(struct super_block *sb, struct hfsplus_unistr *ustr, const char *astr, int len)
+/*
+ * Convert one or more ASCII characters into a single unicode character.
+ * Returns the number of ASCII characters corresponding to the unicode char.
+ */
+static
+int asc2uc(struct super_block *sb, const char *astr, int len, wchar_t *uc)
 {
-	struct nls_table *nls = HFSPLUS_SB(sb).nls;
-	int size, off, decompose;
-	wchar_t c;
-	u16 outlen = 0;
+	int size = HFSPLUS_SB(sb).nls->char2uni(astr, len, uc);
+	if (size <= 0) {
+		*uc = '?';
+		size = 1;
+	}
+	switch (*uc) {
+	case 0x2400:
+		*uc = 0;
+		break;
+	case ':':
+		*uc = '/';
+		break;
+	}
+	return size;
+}
+
+struct decomposed_uc {
+	int size;
+	wchar_t str[3];
+};
+
+/* Decomposes a single unicode character. */
+static void decompose_uc(wchar_t uc, struct decomposed_uc *duc)
+{
+	int off, ii;
 
-	decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+	duc->size = 1;
+	duc->str[0] = uc;
+
+	off = hfsplus_decompose_table[(uc >> 12) & 0xf];
+	if (off == 0 || off == 0xffff)
+		return;
+
+	off = hfsplus_decompose_table[off + ((uc >> 8) & 0xf)];
+	if (!off)
+		return;
+
+	off = hfsplus_decompose_table[off + ((uc >> 4) & 0xf)];
+	if (!off)
+		return;
+
+	off = hfsplus_decompose_table[off + (uc & 0xf)];
+
+	duc->size = off & 3;
+	off /= 4;
+	for (ii = 0; ii < duc->size; ++ii)
+		duc->str[ii] = hfsplus_decompose_table[off++];
+}
+
+/*
+ * Convert a ASCII character(s) to a unicode character.
+ * The unicode character will be decomposed, if required.
+ * Returns the number of ASCII characters converted.
+ */
+static int asc2ucd(struct super_block *sb,
+	const char *astr, int len, struct decomposed_uc *duc)
+{
+	int size = asc2uc(sb, astr, len, duc->str);
+	bool decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+
+	if (decompose && *duc->str >= 0xc0)
+		decompose_uc(*duc->str, duc);
+	else
+		duc->size = 1;
+
+	return size;
+}
+
+int hfsplus_asc2uni(struct super_block *sb,
+	struct hfsplus_unistr *ustr, const char *astr, int len)
+{
+	u16 outlen = 0;
+	struct decomposed_uc duc;
 
 	while (outlen < HFSPLUS_MAX_STRLEN && len > 0) {
-		size = nls->char2uni(astr, len, &c);
-		if (size <= 0) {
-			c = '?';
-			size = 1;
-		}
+		int ii;
+		int size = asc2ucd(sb, astr, len, &duc);
+		if (outlen + duc.size > HFSPLUS_MAX_STRLEN)
+			break;
+
 		astr += size;
 		len -= size;
-		switch (c) {
-		case 0x2400:
-			c = 0;
-			break;
-		case ':':
-			c = '/';
-			break;
-		}
-		if (c >= 0xc0 && decompose) {
-			off = hfsplus_decompose_table[(c >> 12) & 0xf];
-			if (!off)
-				goto done;
-			if (off == 0xffff) {
-				goto done;
-			}
-			off = hfsplus_decompose_table[off + ((c >> 8) & 0xf)];
-			if (!off)
-				goto done;
-			off = hfsplus_decompose_table[off + ((c >> 4) & 0xf)];
-			if (!off)
-				goto done;
-			off = hfsplus_decompose_table[off + (c & 0xf)];
-			size = off & 3;
-			if (!size)
-				goto done;
-			off /= 4;
-			if (outlen + size > HFSPLUS_MAX_STRLEN)
-				break;
-			do {
-				ustr->unicode[outlen++] = cpu_to_be16(hfsplus_decompose_table[off++]);
-			} while (--size > 0);
-			continue;
-		}
-	done:
-		ustr->unicode[outlen++] = cpu_to_be16(c);
+		for (ii = 0; ii < duc.size; ++ii)
+			ustr->unicode[outlen++] = cpu_to_be16(duc.str[ii]);
 	}
 	ustr->length = cpu_to_be16(outlen);
 	if (len > 0)

-- 
"I never could learn to drink that blood and call it wine" - Bob Dylan

Re: [patch 1/2] HFS+: Refactor ASCII to unicode conversion routine for later reuse

[Roman Zippel]

Hi,

On Wed, 20 Jun 2007, Duane Griffin wrote:

> Refactor existing HFS+ ASCII to unicode string conversion routine to
> split out character conversion functionality. This will be reused by
> the custom dentry hash and comparison routines. This approach avoids
> unnecessary memory allocation compared to using the string conversion
> routine directly in the new functions.

I like the idea of this, but not that it generates larger code, so I 
reformatted it a little to get rid of the decomposed_uc struct which 
required an unnecessary data copy, so now the it even generates slightly 
smaller code. :)

bye, Roman


From: Duane Griffin <duaneg@dghda.com>

Refactor existing HFS+ ASCII to unicode string conversion routine to
split out character conversion functionality. This will be reused by
the custom dentry hash and comparison routines. This approach avoids
unnecessary memory allocation compared to using the string conversion
routine directly in the new functions.

Signed-off-by: Duane Griffin <duaneg@dghda.com>
Signed-off-by: Roman Zippel <zippel@linux-m68k.org>
---
 fs/hfsplus/unicode.c |  105 +++++++++++++++++++++++++++++----------------------
 1 file changed, 60 insertions(+), 45 deletions(-)

Index: linux-2.6/fs/hfsplus/unicode.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/unicode.c
+++ linux-2.6/fs/hfsplus/unicode.c
@@ -239,58 +239,73 @@ out:
 	return res;
 }
 
-int hfsplus_asc2uni(struct super_block *sb, struct hfsplus_unistr *ustr, const char *astr, int len)
+/*
+ * Convert one or more ASCII characters into a single unicode character.
+ * Returns the number of ASCII characters corresponding to the unicode char.
+ */
+static inline int asc2unichar(struct super_block *sb, const char *astr, int len,
+			      wchar_t *uc)
 {
-	struct nls_table *nls = HFSPLUS_SB(sb).nls;
-	int size, off, decompose;
+	int size = HFSPLUS_SB(sb).nls->char2uni(astr, len, uc);
+	if (size <= 0) {
+		*uc = '?';
+		size = 1;
+	}
+	switch (*uc) {
+	case 0x2400:
+		*uc = 0;
+		break;
+	case ':':
+		*uc = '/';
+		break;
+	}
+	return size;
+}
+
+/* Decomposes a single unicode character. */
+static inline u16 *decompose_unichar(wchar_t uc, int *size)
+{
+	int off;
+
+	off = hfsplus_decompose_table[(uc >> 12) & 0xf];
+	if (off == 0 || off == 0xffff)
+		return NULL;
+
+	off = hfsplus_decompose_table[off + ((uc >> 8) & 0xf)];
+	if (!off)
+		return NULL;
+
+	off = hfsplus_decompose_table[off + ((uc >> 4) & 0xf)];
+	if (!off)
+		return NULL;
+
+	off = hfsplus_decompose_table[off + (uc & 0xf)];
+	*size = off & 3;
+	return hfsplus_decompose_table + (off / 4);
+}
+
+int hfsplus_asc2uni(struct super_block *sb, struct hfsplus_unistr *ustr,
+		    const char *astr, int len)
+{
+	int size, dsize, decompose;
+	u16 *dstr, outlen = 0;
 	wchar_t c;
-	u16 outlen = 0;
 
 	decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
-
 	while (outlen < HFSPLUS_MAX_STRLEN && len > 0) {
-		size = nls->char2uni(astr, len, &c);
-		if (size <= 0) {
-			c = '?';
-			size = 1;
-		}
-		astr += size;
-		len -= size;
-		switch (c) {
-		case 0x2400:
-			c = 0;
-			break;
-		case ':':
-			c = '/';
-			break;
-		}
-		if (c >= 0xc0 && decompose) {
-			off = hfsplus_decompose_table[(c >> 12) & 0xf];
-			if (!off)
-				goto done;
-			if (off == 0xffff) {
-				goto done;
-			}
-			off = hfsplus_decompose_table[off + ((c >> 8) & 0xf)];
-			if (!off)
-				goto done;
-			off = hfsplus_decompose_table[off + ((c >> 4) & 0xf)];
-			if (!off)
-				goto done;
-			off = hfsplus_decompose_table[off + (c & 0xf)];
-			size = off & 3;
-			if (!size)
-				goto done;
-			off /= 4;
-			if (outlen + size > HFSPLUS_MAX_STRLEN)
+		size = asc2unichar(sb, astr, len, &c);
+
+		if (decompose && (dstr = decompose_unichar(c, &dsize))) {
+			if (outlen + dsize > HFSPLUS_MAX_STRLEN)
 				break;
 			do {
-				ustr->unicode[outlen++] = cpu_to_be16(hfsplus_decompose_table[off++]);
-			} while (--size > 0);
-			continue;
-		}
-	done:
-		ustr->unicode[outlen++] = cpu_to_be16(c);
+				ustr->unicode[outlen++] = cpu_to_be16(*dstr++);
+			} while (--dsize > 0);
+		} else
+			ustr->unicode[outlen++] = cpu_to_be16(c);
+
+		astr += size;
+		len -= size;
 	}
 	ustr->length = cpu_to_be16(outlen);
 	if (len > 0)

Re: [patch 1/2] HFS+: Refactor ASCII to unicode conversion routine for later reuse

[Duane Griffin]

On 25/06/07, Roman Zippel <zippel@linux-m68k.org> wrote:
>
> I like the idea of this, but not that it generates larger code, so I
> reformatted it a little to get rid of the decomposed_uc struct which
> required an unnecessary data copy, so now the it even generates slightly
> smaller code. :)

Ah, nice one! Returning the pointer into the table is a much nicer way
of doing things.

> +               if (decompose && (dstr = decompose_unichar(c, &dsize))) {
> +                       if (outlen + dsize > HFSPLUS_MAX_STRLEN)
>                                 break;
>                         do {
> -                               ustr->unicode[outlen++] = cpu_to_be16(hfsplus_decompose_table[off++]);
> -                       } while (--size > 0);
> -                       continue;
> -               }
> -       done:
> -               ustr->unicode[outlen++] = cpu_to_be16(c);
> +                               ustr->unicode[outlen++] = cpu_to_be16(*dstr++);
> +                       } while (--dsize > 0);

Andrew's comments about the loop in the second patch apply here too, I
think. The original code did have a check for this condition, so I
guess it is a potential problem. How about this (on top of your
version of the patches):

Index: linux-2.6.21.5/fs/hfsplus/unicode.c
===================================================================
--- linux-2.6.21.5.orig/fs/hfsplus/unicode.c
+++ linux-2.6.21.5/fs/hfsplus/unicode.c
@@ -280,7 +280,9 @@ static inline u16 *decompose_unichar(wch
                return NULL;

        off = hfsplus_decompose_table[off + (uc & 0xf)];
-       *size = off & 3;
+       if ((*size = off & 3) == 0)
+               return NULL;
+
        return hfsplus_decompose_table + (off / 4);
 }

I'm using gmail to send this, so it will mess up the tabs I'm afraid :(

> bye, Roman

Cheers,
Duane.

-- 
"I never could learn to drink that blood and call it wine" - Bob Dylan

[patch 2/2] HFS+: Add custom dentry hash and comparison operations

[Duane Griffin]

[-- Attachment #1: hfsplus-custom-dentry-ops.patch --]
[-- Type: text/plain, Size: 5637 bytes --]

Add custom dentry hash and comparison operations for HFS+ filesystems
that are case-insensitive and/or do automatic unicode decomposition.
The new operations reuse the existing HFS+ ASCII to unicode conversion,
unicode decomposition and case folding functionality.

Signed-off-by: Duane Griffin <duaneg@dghda.com>
---

--- linux-2.6.21.orig/fs/hfsplus/dir.c
+++ linux-2.6.21/fs/hfsplus/dir.c
@@ -36,6 +36,11 @@ static struct dentry *hfsplus_lookup(str
 	u16 type;
 
 	sb = dir->i_sb;
+
+	if (!(HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX) ||
+	    !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE))
+		dentry->d_op = &hfsplus_dentry_operations;
+
 	dentry->d_fsdata = NULL;
 	hfs_find_init(HFSPLUS_SB(sb).cat_tree, &fd);
 	hfsplus_cat_build_key(sb, fd.search_key, dir->i_ino, &dentry->d_name);
--- linux-2.6.21.orig/fs/hfsplus/hfsplus_fs.h
+++ linux-2.6.21/fs/hfsplus/hfsplus_fs.h
@@ -321,6 +321,7 @@ void hfsplus_file_truncate(struct inode 
 /* inode.c */
 extern const struct address_space_operations hfsplus_aops;
 extern const struct address_space_operations hfsplus_btree_aops;
+extern struct dentry_operations hfsplus_dentry_operations;
 
 void hfsplus_inode_read_fork(struct inode *, struct hfsplus_fork_raw *);
 void hfsplus_inode_write_fork(struct inode *, struct hfsplus_fork_raw *);
@@ -353,6 +354,8 @@ int hfsplus_strcasecmp(const struct hfsp
 int hfsplus_strcmp(const struct hfsplus_unistr *, const struct hfsplus_unistr *);
 int hfsplus_uni2asc(struct super_block *, const struct hfsplus_unistr *, char *, int *);
 int hfsplus_asc2uni(struct super_block *, struct hfsplus_unistr *, const char *, int);
+int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str);
+int hfsplus_compare_dentry(struct dentry *dentry, struct qstr *s1, struct qstr *s2);
 
 /* wrapper.c */
 int hfsplus_read_wrapper(struct super_block *);
--- linux-2.6.21.orig/fs/hfsplus/inode.c
+++ linux-2.6.21/fs/hfsplus/inode.c
@@ -130,6 +130,12 @@ const struct address_space_operations hf
 	.writepages	= hfsplus_writepages,
 };
 
+struct dentry_operations hfsplus_dentry_operations = {
+	.d_revalidate = NULL,
+	.d_hash       = hfsplus_hash_dentry,
+	.d_compare    = hfsplus_compare_dentry,
+};
+
 static struct dentry *hfsplus_file_lookup(struct inode *dir, struct dentry *dentry,
 					  struct nameidata *nd)
 {
--- linux-2.6.21.orig/fs/hfsplus/super.c
+++ linux-2.6.21/fs/hfsplus/super.c
@@ -396,6 +396,10 @@ static int hfsplus_fill_super(struct sup
 	} else
 		hfs_find_exit(&fd);
 
+	if (!(HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX) ||
+	    !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE))
+		sb->s_root->d_op = &hfsplus_dentry_operations;
+
 	if (sb->s_flags & MS_RDONLY)
 		goto out;
 
--- linux-2.6.21.orig/fs/hfsplus/unicode.c
+++ linux-2.6.21/fs/hfsplus/unicode.c
@@ -314,6 +314,22 @@ static int asc2ucd(struct super_block *s
 	return size;
 }
 
+/*
+ * Convert a ASCII character(s) to a unicode character.
+ * The unicode character will be decomposed and/or case-folded, if required.
+ * Returns the number of ASCII characters converted.
+ */
+static int asc2ucdf(struct super_block *sb,
+	const char *astr, int len, struct decomposed_uc *duc)
+{
+	int ii;
+	int size = asc2ucd(sb, astr, len, duc);
+	bool fold = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX);
+	for (ii = 0; fold && ii <= duc->size; ++ii)
+		duc->str[ii] = case_fold(duc->str[ii]);
+	return size;
+}
+
 int hfsplus_asc2uni(struct super_block *sb,
 	struct hfsplus_unistr *ustr, const char *astr, int len)
 {
@@ -336,3 +352,89 @@ int hfsplus_asc2uni(struct super_block *
 		return -ENAMETOOLONG;
 	return 0;
 }
+
+/*
+ * Hash a string to an integer as appropriate for the HFS+ filesystem.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str)
+{
+	int len = str->len;
+	const char *astr = str->name;
+	struct decomposed_uc duc;
+	unsigned hash = init_name_hash();
+
+	while (len > 0) {
+		int ii;
+		int size = asc2ucdf(dentry->d_sb, astr, len, &duc);
+		astr += size;
+		len -= size;
+		for (ii = 0; ii < duc.size; ++ii) {
+			if (duc.str[ii])
+				hash = partial_name_hash(duc.str[ii], hash);
+		}
+	}
+	str->hash = end_name_hash(hash);
+
+	return 0;
+}
+
+/*
+ * Compare strings with HFS+ filename ordering.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int
+hfsplus_compare_dentry(struct dentry *dentry, struct qstr *s1, struct qstr *s2)
+{
+	int off1 = 0;
+	int off2 = 0;
+	struct decomposed_uc duc1;
+	struct decomposed_uc duc2;
+	int len1 = s1->len;
+	int len2 = s2->len;
+	const char *astr1 = s1->name;
+	const char *astr2 = s2->name;
+
+	duc1.size = 0;
+	duc2.size = 0;
+
+	while ((off1 < duc1.size || len1 > 0) &&
+	       (off2 < duc2.size || len2 > 0)) {
+
+		if (off1 == duc1.size) {
+			int size = asc2ucdf(dentry->d_sb, astr1, len1, &duc1);
+			astr1 += size;
+			len1 -= size;
+			off1 = 0;
+		}
+
+		if (off2 == duc2.size) {
+			int size = asc2ucdf(dentry->d_sb, astr2, len2, &duc2);
+			astr2 += size;
+			len2 -= size;
+			off2 = 0;
+		}
+
+		while (off1 < duc1.size && !duc1.str[off1])
+			++off1;
+		while (off2 < duc2.size && !duc2.str[off2])
+			++off2;
+
+		while (off1 < duc1.size && off2 < duc2.size) {
+			if (duc1.str[off1] < duc2.str[off2])
+				return -1;
+			if (duc1.str[off1] > duc2.str[off2])
+				return 1;
+			++off1;
+			++off2;
+		}
+	}
+
+	if (len1 < len2)
+		return -1;
+	if (len1 > len2)
+		return 1;
+	return 0;
+}

-- 
"I never could learn to drink that blood and call it wine" - Bob Dylan

Re: [patch 2/2] HFS+: Add custom dentry hash and comparison operations

[Roman Zippel]

Hi,

On Wed, 20 Jun 2007, Duane Griffin wrote:

> Add custom dentry hash and comparison operations for HFS+ filesystems
> that are case-insensitive and/or do automatic unicode decomposition.
> The new operations reuse the existing HFS+ ASCII to unicode conversion,
> unicode decomposition and case folding functionality.

The changes in the previous patch required a few changes in this patch as 
well, but there were also a few small problems. The case condition wasn't 
quite correct and some characters have to be ignored during compare/hash.

bye, Roman


From: Duane Griffin <duaneg@dghda.com>

Add custom dentry hash and comparison operations for HFS+ filesystems
that are case-insensitive and/or do automatic unicode decomposition.
The new operations reuse the existing HFS+ ASCII to unicode conversion,
unicode decomposition and case folding functionality.

Signed-off-by: Duane Griffin <duaneg@dghda.com>
Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---
 fs/hfsplus/btree.c      |    4 +
 fs/hfsplus/dir.c        |    2 
 fs/hfsplus/hfsplus_fs.h |    4 +
 fs/hfsplus/inode.c      |    5 +
 fs/hfsplus/super.c      |    1 
 fs/hfsplus/unicode.c    |  123 ++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 138 insertions(+), 1 deletion(-)

Index: linux-2.6/fs/hfsplus/dir.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/dir.c	2007-04-26 19:45:57.000000000 +0200
+++ linux-2.6/fs/hfsplus/dir.c	2007-06-25 13:39:46.000000000 +0200
@@ -36,6 +36,8 @@ static struct dentry *hfsplus_lookup(str
 	u16 type;
 
 	sb = dir->i_sb;
+
+	dentry->d_op = &hfsplus_dentry_operations;
 	dentry->d_fsdata = NULL;
 	hfs_find_init(HFSPLUS_SB(sb).cat_tree, &fd);
 	hfsplus_cat_build_key(sb, fd.search_key, dir->i_ino, &dentry->d_name);
Index: linux-2.6/fs/hfsplus/hfsplus_fs.h
===================================================================
--- linux-2.6.orig/fs/hfsplus/hfsplus_fs.h	2007-04-26 19:45:57.000000000 +0200
+++ linux-2.6/fs/hfsplus/hfsplus_fs.h	2007-06-25 12:59:16.000000000 +0200
@@ -150,6 +150,7 @@ struct hfsplus_sb_info {
 #define HFSPLUS_SB_NODECOMPOSE	0x0002
 #define HFSPLUS_SB_FORCE	0x0004
 #define HFSPLUS_SB_HFSX		0x0008
+#define HFSPLUS_SB_CASEFOLD	0x0010
 
 
 struct hfsplus_inode_info {
@@ -321,6 +322,7 @@ void hfsplus_file_truncate(struct inode 
 /* inode.c */
 extern const struct address_space_operations hfsplus_aops;
 extern const struct address_space_operations hfsplus_btree_aops;
+extern struct dentry_operations hfsplus_dentry_operations;
 
 void hfsplus_inode_read_fork(struct inode *, struct hfsplus_fork_raw *);
 void hfsplus_inode_write_fork(struct inode *, struct hfsplus_fork_raw *);
@@ -353,6 +355,8 @@ int hfsplus_strcasecmp(const struct hfsp
 int hfsplus_strcmp(const struct hfsplus_unistr *, const struct hfsplus_unistr *);
 int hfsplus_uni2asc(struct super_block *, const struct hfsplus_unistr *, char *, int *);
 int hfsplus_asc2uni(struct super_block *, struct hfsplus_unistr *, const char *, int);
+int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str);
+int hfsplus_compare_dentry(struct dentry *dentry, struct qstr *s1, struct qstr *s2);
 
 /* wrapper.c */
 int hfsplus_read_wrapper(struct super_block *);
Index: linux-2.6/fs/hfsplus/inode.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/inode.c	2007-04-26 19:45:57.000000000 +0200
+++ linux-2.6/fs/hfsplus/inode.c	2007-06-25 13:52:54.000000000 +0200
@@ -130,6 +130,11 @@ const struct address_space_operations hf
 	.writepages	= hfsplus_writepages,
 };
 
+struct dentry_operations hfsplus_dentry_operations = {
+	.d_hash       = hfsplus_hash_dentry,
+	.d_compare    = hfsplus_compare_dentry,
+};
+
 static struct dentry *hfsplus_file_lookup(struct inode *dir, struct dentry *dentry,
 					  struct nameidata *nd)
 {
Index: linux-2.6/fs/hfsplus/unicode.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/unicode.c	2007-06-25 12:59:15.000000000 +0200
+++ linux-2.6/fs/hfsplus/unicode.c	2007-06-25 13:35:23.000000000 +0200
@@ -312,3 +312,126 @@ int hfsplus_asc2uni(struct super_block *
 		return -ENAMETOOLONG;
 	return 0;
 }
+
+/*
+ * Hash a string to an integer as appropriate for the HFS+ filesystem.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str)
+{
+	struct super_block *sb = dentry->d_sb;
+	const char *astr;
+	const u16 *dstr;
+	int casefold, decompose, size, dsize, len;
+	unsigned long hash;
+	wchar_t c;
+	u16 c2;
+
+	casefold = (HFSPLUS_SB(sb).flags & HFSPLUS_SB_CASEFOLD);
+	decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+	hash = init_name_hash();
+	astr = str->name;
+	len = str->len;
+	while (len > 0) {
+		size = asc2unichar(sb, astr, len, &c);
+		astr += size;
+		len -= size;
+
+		if (decompose && (dstr = decompose_unichar(c, &dsize))) {
+			do {
+				c2 = *dstr++;
+				if (!casefold || (c2 = case_fold(c2)))
+					hash = partial_name_hash(c2, hash);
+			} while (--dsize > 0);
+		} else {
+			c2 = c;
+			if (!casefold || (c2 = case_fold(c2)))
+				hash = partial_name_hash(c2, hash);
+		}
+	}
+	str->hash = end_name_hash(hash);
+
+	return 0;
+}
+
+/*
+ * Compare strings with HFS+ filename ordering.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int hfsplus_compare_dentry(struct dentry *dentry, struct qstr *s1, struct qstr *s2)
+{
+	struct super_block *sb = dentry->d_sb;
+	int casefold, decompose, size;
+	int dsize1, dsize2, len1, len2;
+	const u16 *dstr1, *dstr2;
+	const char *astr1, *astr2;
+	u16 c1, c2;
+	wchar_t c;
+
+	casefold = (HFSPLUS_SB(sb).flags & HFSPLUS_SB_CASEFOLD);
+	decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+	astr1 = s1->name;
+	len1 = s1->len;
+	astr2 = s2->name;
+	len2 = s2->len;
+	dsize1 = dsize2 = 0;
+	dstr1 = dstr2 = NULL;
+
+	while (len1 > 0 && len2 > 0) {
+		if (!dsize1) {
+			size = asc2unichar(sb, astr1, len1, &c);
+			astr1 += size;
+			len1 -= size;
+
+			if (!decompose || !(dstr1 = decompose_unichar(c, &dsize1))) {
+				c1 = c;
+				dstr1 = &c1;
+				dsize1 = 1;
+			}
+		}
+
+		if (!dsize2) {
+			size = asc2unichar(sb, astr2, len2, &c);
+			astr2 += size;
+			len2 -= size;
+
+			if (!decompose || !(dstr2 = decompose_unichar(c, &dsize2))) {
+				c2 = c;
+				dstr2 = &c2;
+				dsize2 = 1;
+			}
+		}
+
+		c1 = *dstr1;
+		c2 = *dstr2;
+		if (casefold) {
+			if  (!(c1 = case_fold(c1))) {
+				dstr1++;
+				dsize1--;
+				continue;
+			}
+			if (!(c2 = case_fold(c2))) {
+				dstr2++;
+				dsize2--;
+				continue;
+			}
+		}
+		if (c1 < c2)
+			return -1;
+		else if (c1 > c2)
+			return 1;
+
+		dstr1++;
+		dsize1--;
+		dstr2++;
+		dsize2--;
+	}
+
+	if (len1 < len2)
+		return -1;
+	if (len1 > len2)
+		return 1;
+	return 0;
+}
Index: linux-2.6/fs/hfsplus/btree.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/btree.c	2007-04-26 19:45:57.000000000 +0200
+++ linux-2.6/fs/hfsplus/btree.c	2007-06-25 12:59:16.000000000 +0200
@@ -61,8 +61,10 @@ struct hfs_btree *hfs_btree_open(struct 
 		if ((HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX) &&
 		    (head->key_type == HFSPLUS_KEY_BINARY))
 			tree->keycmp = hfsplus_cat_bin_cmp_key;
-		else
+		else {
 			tree->keycmp = hfsplus_cat_case_cmp_key;
+			HFSPLUS_SB(sb).flags |= HFSPLUS_SB_CASEFOLD;
+		}
 	} else {
 		printk(KERN_ERR "hfs: unknown B*Tree requested\n");
 		goto fail_page;
Index: linux-2.6/fs/hfsplus/super.c
===================================================================
--- linux-2.6.orig/fs/hfsplus/super.c	2007-06-25 13:29:08.000000000 +0200
+++ linux-2.6/fs/hfsplus/super.c	2007-06-25 13:30:11.000000000 +0200
@@ -381,6 +381,7 @@ static int hfsplus_fill_super(struct sup
 		iput(root);
 		goto cleanup;
 	}
+	sb->s_root->d_op = &hfsplus_dentry_operations;
 
 	str.len = sizeof(HFSP_HIDDENDIR_NAME) - 1;
 	str.name = HFSP_HIDDENDIR_NAME;

Re: [patch 2/2] HFS+: Add custom dentry hash and comparison operations

[Andrew Morton]

On Mon, 25 Jun 2007 14:17:19 +0200 (CEST) Roman Zippel <zippel@linux-m68k.org> wrote:

> +/*
> + * Hash a string to an integer as appropriate for the HFS+ filesystem.
> + * Composed unicode characters are decomposed and case-folding is performed
> + * if the appropriate bits are (un)set on the superblock.
> + */
> +int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str)
> +{
> +	struct super_block *sb = dentry->d_sb;
> +	const char *astr;
> +	const u16 *dstr;
> +	int casefold, decompose, size, dsize, len;
> +	unsigned long hash;
> +	wchar_t c;
> +	u16 c2;
> +
> +	casefold = (HFSPLUS_SB(sb).flags & HFSPLUS_SB_CASEFOLD);
> +	decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
> +	hash = init_name_hash();
> +	astr = str->name;
> +	len = str->len;
> +	while (len > 0) {
> +		size = asc2unichar(sb, astr, len, &c);
> +		astr += size;
> +		len -= size;
> +
> +		if (decompose && (dstr = decompose_unichar(c, &dsize))) {
> +			do {
> +				c2 = *dstr++;
> +				if (!casefold || (c2 = case_fold(c2)))
> +					hash = partial_name_hash(c2, hash);
> +			} while (--dsize > 0);

Are you really sure that we cannot start this loop with dsize==0?  This isn't
obviously true to these bleary eyes.

> +		} else {
> +			c2 = c;
> +			if (!casefold || (c2 = case_fold(c2)))
> +				hash = partial_name_hash(c2, hash);
> +		}
> +	}
> +	str->hash = end_name_hash(hash);