Skip to contentSkip to conversation

xfsprogs: metadump: don't loop on too many dups

PATCH In review Alex Elder 2 participants 4 messages Feb 18, 2011 – Mar 3, 2011

lore
Share & tools
lore

Alex Elder

author
#0 lore raw

PATCH v3 9/16 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.

Signed-off-by Alex Elder <[email protected]>

The only change worth mentioning from the last version posted is that the duplicate count is now updated inside the loop that searches the name table.

---
 db/metadump.c |   32 ++++++++++++++++++++++++--------
 1 file changed, 24 insertions(+), 8 deletions(-)
db/metadump.c +24 -8
Index: 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);

@@ -437,8 +445,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

@@ -471,19 +480,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);

@@ -531,14 +538,22 @@ 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);
+
+	/* Use the original name if we got too many dups. */
+
+	newp = dup < DUP_MAX ? newname : name;
 
 	/* Create an entry for the name in the name table */
 

@@ -547,7 +562,7 @@ generate_obfuscated_name(
 		return;
 
 	p->namelen = namelen;
-	memcpy(p->name, newname, namelen);
+	memcpy(p->name, newp, namelen);
 	p->hash = hash;
 	p->next = nametable[hash % NAME_TABLE_SIZE];
 

@@ -555,7 +570,8 @@ generate_obfuscated_name(
 
 	/* Update the caller's copy with the obfuscated name */
 
-	memcpy(name, newname, namelen);
+	if (newp != name)
+		memcpy(name, newp, namelen);
 }
 
 static void

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Reviewed-by on v3 9/16
#1 lore raw
Quoted 9 lines · Alex Elder

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.

Quoted 5 lines
Signed-off-by Alex Elder <[email protected]>

The only change worth mentioning from the last version posted is that the duplicate count is now updated inside the loop that searches the name table.

The only thing that I'd suggest here is that we emit a warning to indicate that we haven't obfuscated a name due to excessive duplicates being created. If the user has asked for obfuscation, we shoul dat least inform them failures to do so for filenames that should be obfuscated....

Otherwise,

Reviewed-by Dave Chinner <[email protected]>
Signature · 7 lines
Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
author
#2 lore raw

PATCH v4 9/16 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.

Signed-off-by Alex Elder <[email protected]>
Reviewed-by Dave Chinner <[email protected]>

Updates (v4):
- Rearranged things a bit so that if too many duplicates are encountered, a warning gets emitted.

Dave already signed off on it but the update was different enough I thought I should post it once more.

---
 db/metadump.c |   42 +++++++++++++++++++++++++++++++-----------
 1 file changed, 31 insertions(+), 11 deletions(-)
db/metadump.c +31 -11
Index: 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

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Reviewed-by on v4 9/16
#3 lore raw
Quoted 12 lines · Alex Elder

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.

Signed-off-by Alex Elder <[email protected]>
Reviewed-by Dave Chinner <[email protected]>
Quoted 6 lines

Updates (v4):
- Rearranged things a bit so that if too many duplicates are encountered, a warning gets emitted.

Dave already signed off on it but the update was different enough I thought I should post it once more.

Reviewed-by Dave Chinner <[email protected]>
Signature · 7 lines
Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs