xfs_metadump in never ending loop

generate_obfuscated_name() in metadump.c can go into never ending loop for some file names. Reproducer below.

Can someone look into it? Thanks.

#include <stdlib.h>
#include <dirent.h>

typedef unsigned char uchar_t;
typedef __uint32_t xfs_dahash_t;

#define is_invalid_char(c) ((c) == '/' || (c) == '\0')
#define rol32(x,y) (((x) << (y)) | ((x) >> (32 - (y))))

static inline uchar_t
random_filename_char(void)

{
        uchar_t                 c;

        do {
                c = random() % 127 + 1;
        } while (c == '/');
        return c;
}

int main() {
	int namelen = 5, i, dup;
	xfs_dahash_t hash = 978052928;
	xfs_dahash_t newhash;
	uchar_t *name = "R\323\257NE\002\320\000";
	uchar_t newname[NAME_MAX];

        do {
                dup = 0;
                newname[0] = '/';

                for (;;) {
                        /* if the first char is a "/", preserve it */
                        i = (name[0] == '/');

                        for (newhash = 0; i < namelen - 5; i++) {
                                newname[i] = random_filename_char();
                                newhash = newname[i] ^ rol32(newhash, 7);
                        }
                        newhash = rol32(newhash, 3) ^ hash;
                        if (name[0] != '/' || namelen > 5) {
                                newname[namelen - 5] = (newhash >> 28) |
                                                (random_filename_char() & 0xf0);
                                if (is_invalid_char(newname[namelen - 5]))
                                        continue;
                        }
                        newname[namelen - 4] = (newhash >> 21) & 0x7f;
                        if (is_invalid_char(newname[namelen - 4]))
                                continue;
                        newname[namelen - 3] = (newhash >> 14) & 0x7f;
                        if (is_invalid_char(newname[namelen - 3]))
                                continue;
                        newname[namelen - 2] = (newhash >> 7) & 0x7f;
                        if (is_invalid_char(newname[namelen - 2]))
                                continue;
                        newname[namelen - 1] = ((newhash >> 0) ^
                                        (newname[namelen - 5] >> 4)) & 0x7f;
                        if (is_invalid_char(newname[namelen - 1]))
                                continue;
                        break;
                }
	} while (dup);
}

Arkadiusz Miśkiewicz        PLD/Linux Team
arekm / maven.pl            http://ftp.pld-linux.org/

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

The reason it hangs is that the algorithm for computing a name with the same hash value as the name is stuck with a portion of the hash whose only possible result includes the string "/" in it.

The hash for the file "R\323\257NE" is 0x3ab4b3740.

One step in the algorithm is this:

        newname[namelen - 3] = (newhash >> 14) & 0x7f;
        if (is_invalid_char(newname[namelen - 3]))
                continue;

But the result of that is 0x2f, which is the '/' character, which is illegal. So this algorithm will try again indefinitely, never finding a file name with a matching hash.

I am looking into this a bit more. Will report back later, probably tomorrow.

-Alex

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

I understand this problem, and have a solution. But before sending out the code I want to write up an explanation of the problem, including the effect of the hash and why the existing algorithm has problems.

Stay tuned.

-Alex

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