[PATCH 1/2] apfsck: don't normalize key names for comparison

[Ernesto A. Fernández]

When two filenames have the same hash, compare them as character strings
to decide the order of their keys. That is, ignore the case-folding and
unicode decomposition.

This has only been tested for ascii names, so some uncertainty remains.
Either way, the change is an improvement and should also be applied to
the module.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---
apfsck/key.c | 38 ++------------------------------------
1 file changed, 2 insertions(+), 36 deletions(-)

diff --git a/apfsck/key.c b/apfsck/key.c
index be8c84c..a50c176 100644
--- a/apfsck/key.c
+++ b/apfsck/key.c
@@ -63,35 +63,6 @@ static inline u64 cat_cnid(struct apfs_key_header *key)
}

/**
- * filename_cmp - Normalize and compare two APFS filenames
- * @name1, @name2: names to compare
- *
- * returns 0 if @name1 and @name2 are equal
- * < 0 if @name1 comes before @name2 in the btree
- * > 0 if @name1 comes after @name2 in the btree
- */
-static int filename_cmp(const char *name1, const char *name2)
-{
- struct unicursor cursor1, cursor2;
- bool case_fold = apfs_is_case_insensitive();
-
- init_unicursor(&cursor1, name1);
- init_unicursor(&cursor2, name2);
-
- while (1) {
- unicode_t uni1, uni2;
-
- uni1 = normalize_next(&cursor1, case_fold);
- uni2 = normalize_next(&cursor2, case_fold);
-
- if (uni1 != uni2)
- return uni1 < uni2 ? -1 : 1;
- if (!uni1)
- return 0;
- }
-}
-
-/**
* keycmp - Compare two keys
* @k1, @k2: keys to compare
*
@@ -110,13 +81,8 @@ int keycmp(struct key *k1, struct key *k2)
if (!k1->name) /* Keys of this type have no name */
return 0;

- if (k1->type == APFS_TYPE_XATTR) {
- /* xattr names seem to be always case sensitive */
- return strcmp(k1->name, k2->name);
- }
-
- /* The assumption here is not the same as in the module... */
- return filename_cmp(k1->name, k2->name);
+ /* Normalization seems to be ignored here, even for directory records */
+ return strcmp(k1->name, k2->name);
}

/**
--
2.11.0

[Ernesto A. Fernández]

Despite sharing the same field, only the dentry hash is relevant for the
ordering; the name length must be ignored. This change is necessary in
the module as well.

Xattr length is also irrelevant, so update a comment on that matter.

Signed-off-by: Ernesto A. Fernández <ernesto.mn...@gmail.com>
---

apfsck/key.c | 12 +++++-------
apfsck/key.h | 2 +-
2 files changed, 6 insertions(+), 8 deletions(-)

diff --git a/apfsck/key.c b/apfsck/key.c
index a50c176..192564a 100644
--- a/apfsck/key.c
+++ b/apfsck/key.c
@@ -94,7 +94,6 @@ static u32 dentry_hash(const char *name)
struct unicursor cursor;
bool case_fold = apfs_is_case_insensitive();
u32 hash = 0xFFFFFFFF;
- int namelen;

init_unicursor(&cursor, name);

@@ -108,10 +107,8 @@ static u32 dentry_hash(const char *name)
hash = crc32c(hash, &utf32, sizeof(utf32));
}

- /* APFS counts the NULL termination for the filename length */
- namelen = cursor.utf8curr - name;
-
- return ((hash & 0x3FFFFF) << 10) | (namelen & 0x3FF);
+ /* Leave room for the filename length */
+ return (hash & 0x3FFFFF) << 10;
}

/**
@@ -131,13 +128,14 @@ static void read_dir_rec_key(void *raw, int size, struct key *key)
report("Directory record", "filename lacks NULL-termination.");
raw_key = raw;

- key->number = le32_to_cpu(raw_key->name_len_and_hash);
+ /* The filename length is ignored for the ordering, so mask it away */
+ key->number = le32_to_cpu(raw_key->name_len_and_hash) & ~0x3FFU;
key->name = (char *)raw_key->name;

if (key->number != dentry_hash(key->name))
report("Directory record", "filename hash is corrupted.");

- namelen = key->number & 0x3FF;
+ namelen = le32_to_cpu(raw_key->name_len_and_hash) & 0x3FFU;
if (strlen(key->name) + 1 != namelen) {
/* APFS counts the NULL termination for the filename length */
report("Directory record", "wrong name length in key.");
diff --git a/apfsck/key.h b/apfsck/key.h
index f4dac70..6b1516f 100644
--- a/apfsck/key.h
+++ b/apfsck/key.h
@@ -182,7 +182,7 @@ static inline void init_xattr_key(u64 ino, const char *name, struct key *key)
{
key->id = ino;
key->type = APFS_TYPE_XATTR;
- key->number = 0; /* Maybe use the name length here, for speed? */
+ key->number = 0;
key->name = name;
}

--
2.11.0