Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96935
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain zend.com designates 104.47.34.105 as permitted sender)
To: Nikita Popov <nikita.ppv@gmail.com>
CC: Dmitry Stogov <dmitry@zend.com>, Julien Pauli <julienpauli@gmail.com>,
	Zeev Suraski <zeev@zend.com>, Nikita Popov <nikic@php.net>,
	"php-dev@coydogsoftware.net" <php-dev@coydogsoftware.net>, Joe Watkins
	<pthreads@pthreads.org>, "internals@lists.php.net" <internals@lists.php.net>,
	"rasmus@lerdorf.com" <rasmus@lerdorf.com>, "Anatol Belski (ab@php.net)"
	<ab@php.net>
Thread-Topic: [PATCH] opcache bug #69090, prepend user identifier to keys
Thread-Index: AQHSQEg2D4h3upkAiEqzeDgxtnu8Qg==
Date: Wed, 16 Nov 2016 20:56:45 +0000
Message-ID: <MWHPR02MB24773D04124B9072DFCB2013BFBE0@MWHPR02MB2477.namprd02.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
received-spf: None (protection.outlook.com: zend.com does not designate
 permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative;
	boundary="_000_MWHPR02MB24773D04124B9072DFCB2013BFBE0MWHPR02MB2477namp_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Nov 2016 20:56:45.5991
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 32210298-c08b-4829-8097-6b12c025a892
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR02MB2479
Subject: Re: [PATCH] opcache bug #69090, prepend user identifier to keys
From: dmitry@zend.com (Dmitry Stogov)

--_000_MWHPR02MB24773D04124B9072DFCB2013BFBE0MWHPR02MB2477namp_
Content-Type: text/plain; charset="koi8-r"
Content-Transfer-Encoding: quoted-printable

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 c=
ollisions caused by the hash function? It looks like for inodes > 2^16 coll=
isions 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 =3D=3D F(S2) ^ R2 && R1 =3D=3D R2 && S1 =3D=3D S2
>>
>>
>> R1 =3D=3D R2 seems useless. The existing condition:
>>
>>
>> F(S1) ^ R1 =3D=3D F(S2) ^ R2 && S1 =3D=3D S2
>>
>>
>> fails if S1 !=3D S2 independently on R1 and R2.
>>
>> If S1 and S2 are the same, than F(S1) equal to F(S2) and consequently, t=
o 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 ino=
des I1 and I2 and two root hashes R1 =3D H(I1), R2 =3D H(I2). In that case =
it may be that R1 =3D=3D R2, but I1 !=3D I2. At least that's the way I unde=
rstood the patch -- it doesn't looks like there is anything explicitly prev=
enting this.

I see. Actually, for 64-bit systems it's better to eliminate bits permutati=
on at all, but for 32-bit we can't avoid possible collisions, even if we in=
clude high bits into hash.

The good thing, that inodes above 2^32 may make sense only on filesystems a=
bove 16TB with 4096 block sise (may be I'm wrong).

do you have any ideas?

Thanks. Dmitry.

>
> Nikita

--_000_MWHPR02MB24773D04124B9072DFCB2013BFBE0MWHPR02MB2477namp_--