Eric, Am 25.04.2017 um 19:46 schrieb Eric Biggers: >> Sorry if this is a stupid question, but why do you have to compare hashes >> _and_ >> the last few bytes of the bigname? >> A lookup via bigname gives you two 32bits hash values, and there I'd assume >> that >> this is sufficient for a collisions free lookup. Especially since an >> resumed readdir() >> with a 64bits cookie has to work too on your filesystem. >> > > Well, the problem is that hashes may not be sufficient to uniquely identify a > name in all cases. f2fs uses only a 32-bit hash so it's trivial to create > collisions on it, as I demonstrated. Even collisions of two 32-bit hashes, as > used by ext4 and ubifs, are possible. And ext4 currently doesn't even compare > the hashes during directory searches, beyond using them to find the correct > directory block, since the hashes aren't stored in the directory entries.
I agree that finding a collision in a 32bits hash is easy, but for 64bits it is *much* harder. > Could this mean that telldir()/seekdir() is unreliable too, probably. But for > lookups of the "digested" names we aren't limited to just the 64-bit readdir > position, so we can avoid duplicating the bug. Also, collisions in the > digested > names are very problematic since they result in undeletable files, rather than > just poor performance and broken telldir()/seekdir(). True. Let me think whether we can add such a check to UBIFS. Thanks, //richard ------------------------------------------------------------------------------ Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Linux-f2fs-devel mailing list Linux-f2fs-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
