https://www.quora.com/What-is-the-maximum-number-of-inodes-in-Linux-filesystems-I-found-suggestion-that-for-Ext4-it-is-4-billion-files-32-bit-number-Is-it-true-for-XFS-and-or-BtrFS
________________________________ From: Dmitry Stogov Sent: Wednesday, November 16, 2016 11:56:45 PM To: Nikita Popov Cc: Dmitry Stogov; Julien Pauli; Zeev Suraski; Nikita Popov; php-...@coydogsoftware.net; Joe Watkins; internals@lists.php.net; ras...@lerdorf.com; Anatol Belski (a...@php.net) Subject: Re: [PATCH] opcache bug #69090, prepend user identifier to keys On Nov 16, 2016 8:03 PM, Nikita Popov <nikita....@gmail.com> wrote: > > On Tue, Nov 15, 2016 at 6:32 PM, Dmitry Stogov <dmi...@zend.com> wrote: >> >> On Nov 15, 2016 18:50, Nikita Popov <nikita....@gmail.com> wrote: >> > >> > On Tue, Nov 15, 2016 at 4:19 PM, Dmitry Stogov <dmi...@zend.com> wrote: >> >> >> >> New patch, attached to bug report, should fix both problems. >> >> >> >> I'm going to commit it tomorrow, if no objections. >> >> >> >> >> >> Thanks. Dmitry. >> > >> > For the new validate_root patch, wouldn't we still end up with inode >> > collisions caused by the hash function? It looks like for inodes > 2^16 >> > collisions should be "common". >> > >> > Nikita >> >> >> It's not a problem to add inode check, but I think we don't need it. >> >> >> Let S1 and S2 strings, R1 and R2 root_hashes and F a hash function. >> >> You propose the following comparison for collision checks >> >> >> F(S1) ^ R1 == F(S2) ^ R2 && R1 == R2 && S1 == S2 >> >> >> R1 == R2 seems useless. The existing condition: >> >> >> F(S1) ^ R1 == F(S2) ^ R2 && S1 == S2 >> >> >> fails if S1 != S2 independently on R1 and R2. >> >> If S1 and S2 are the same, than F(S1) equal to F(S2) and consequently, to >> satisfy the whole condition, R1 should be equal to R2 >> >> >> Am I wrong? > > To clarify: My concern is not with the way the hash is compared, but that the > root hash itself could have collisions. That is, you have two root inodes I1 > and I2 and two root hashes R1 = H(I1), R2 = H(I2). In that case it may be > that R1 == R2, but I1 != I2. At least that's the way I understood the patch > -- it doesn't looks like there is anything explicitly preventing this. I see. Actually, for 64-bit systems it's better to eliminate bits permutation at all, but for 32-bit we can't avoid possible collisions, even if we include high bits into hash. The good thing, that inodes above 2^32 may make sense only on filesystems above 16TB with 4096 block sise (may be I'm wrong). do you have any ideas? Thanks. Dmitry. > > Nikita
