Everything
php
Learn Community Releases The PHP Project
Home » Project » Newsgroups » php.internals » Re: [PATCH] opcache bug #69090, prepend user identifier to keys »

Re: [PATCH] opcache bug #69090, prepend user identifier to keys

php.internals

Dmitry Stogov

9 years ago
On Nov 16, 2016 8:03 PM, Nikita Popov <nikita.ppv@gmail.com> wrote:
> > On Tue, Nov 15, 2016 at 6:32 PM, Dmitry Stogov <dmitry@zend.com> wrote: >> >> On Nov 15, 2016 18:50, Nikita Popov <nikita.ppv@gmail.com> wrote: >> > >> > On Tue, Nov 15, 2016 at 4:19 PM, Dmitry Stogov <dmitry@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.

Dmitry Stogov

9 years ago
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-dev@coydogsoftware.net; Joe Watkins; internals@lists.php.net; rasmus@lerdorf.com; Anatol Belski (ab@php.net) Subject: Re: [PATCH] opcache bug #69090, prepend user identifier to keys On Nov 16, 2016 8:03 PM, Nikita Popov <nikita.ppv@gmail.com> wrote:
> > On Tue, Nov 15, 2016 at 6:32 PM, Dmitry Stogov <dmitry@zend.com> wrote: >> >> On Nov 15, 2016 18:50, Nikita Popov <nikita.ppv@gmail.com> wrote: >> > >> > On Tue, Nov 15, 2016 at 4:19 PM, Dmitry Stogov <dmitry@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.