From 88b1fe2aa7fded8f5036ec32cba6f576503aa235 Mon Sep 17 00:00:00 2001 From: Alex Elder Date: Fri, 25 Feb 2011 18:13:44 +0000 Subject: [PATCH] xfsprogs: metadump: don't loop on too many dups Don't just loop indefinitely when an obfuscated name comes up as a duplicate. Count the number of times we've found a duplicate and if if it gets excessive despite choosing names at random, just give up and use the original name without obfuscation. Technically, a typical 5-character name has 255 other names that can have the same hash value. But the algorithm doesn't hit all possible names (far from it) so duplicates are still possible. Updates (v4): - Rearranged things a bit so that if too many duplicates are encountered, a warning gets emitted. Signed-off-by: Alex Elder Reviewed-by: Dave Chinner --- db/metadump.c | 42 +++++++++++++++++++++++++++++++----------- 1 file changed, 31 insertions(+), 11 deletions(-) diff --git a/db/metadump.c b/db/metadump.c index 143fcba13..8298d95cb 100644 --- a/db/metadump.c +++ b/db/metadump.c @@ -29,6 +29,14 @@ #define DEFAULT_MAX_EXT_SIZE 1000 +/* + * It's possible that multiple files in a directory (or attributes + * in a file) produce the same obfuscated name. If that happens, we + * try to create another one. After several rounds of this though, + * we just give up and leave the original name as-is. + */ +#define DUP_MAX 5 /* Max duplicates before we give up */ + /* copy all metadata structures to/from a file */ static int metadump_f(int argc, char **argv); @@ -444,8 +452,9 @@ generate_obfuscated_name( { xfs_dahash_t hash; name_ent_t *p; - int dup; + int dup = 0; uchar_t newname[NAME_MAX]; + uchar_t *newp; /* * Our obfuscation algorithm requires at least 5-character @@ -481,19 +490,17 @@ generate_obfuscated_name( do { int i; xfs_dahash_t newhash = 0; - uchar_t *newp = &newname[0]; uchar_t *first; uchar_t high_bit; int shift; - dup = 0; - /* * The beginning of the obfuscated name can be * pretty much anything, so fill it in with random * characters. Accumulate its new hash value as we * go. */ + newp = &newname[0]; for (i = 0; i < namelen - 5; i++) { *newp = random_filename_char(); newhash = *newp ^ rol32(newhash, 7); @@ -541,14 +548,31 @@ generate_obfuscated_name( ASSERT(libxfs_da_hashname(newname, namelen) == hash); + /* + * Search the name table to be sure we don't produce + * a name that's already been used. + */ for (p = nametable[hash % NAME_TABLE_SIZE]; p; p = p->next) { if (p->hash == hash && p->namelen == namelen && !memcmp(p->name, newname, namelen)) { - dup = 1; + dup++; break; } } - } while (dup); + } while (dup && dup < DUP_MAX); + + /* + * Update the caller's copy with the obfuscated name. Use + * the original name if we got too many duplicates--and if + * so, issue a warning. + */ + if (dup < DUP_MAX) + memcpy(name, newname, namelen); + else + print_warning("duplicate name for inode %llu " + "in dir inode %llu\n", + (unsigned long long) ino, + (unsigned long long) cur_ino); /* Create an entry for the name in the name table */ @@ -557,15 +581,11 @@ generate_obfuscated_name( return; p->namelen = namelen; - memcpy(p->name, newname, namelen); + memcpy(p->name, name, namelen); p->hash = hash; p->next = nametable[hash % NAME_TABLE_SIZE]; nametable[hash % NAME_TABLE_SIZE] = p; - - /* Update the caller's copy with the obfuscated name */ - - memcpy(name, newname, namelen); } static void -- 2.47.2