Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96499
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain zend.com designates 104.47.40.121 as permitted sender)
To: Benjamin Coutu <ben.coutu@zeyos.com>, Xinchen Hui <xinchen.h@zend.com>,
	Nikita Popov <nikita.ppv@gmail.com>, Joe Watkins <pthreads@pthreads.org>,
	"Bob Weinand" <bobwei9@hotmail.com>, Andrea Faulds <ajf@php.net>
CC: PHP Internals <internals@lists.php.net>
Thread-Topic: [PHP-DEV] Exploit fully packed array/hash property
Thread-Index: AQHSKjq2ICe6fWB8KU2gY2cKABBs9qCwPSMb
Date: Wed, 19 Oct 2016 20:45:05 +0000
Message-ID: <MWHPR02MB24770D9226ECEBD03E242481BFD20@MWHPR02MB2477.namprd02.prod.outlook.com>
References: <20161019185802.B88FE5FAC0@mx.zeyos.com>
In-Reply-To: <20161019185802.B88FE5FAC0@mx.zeyos.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: [25.164.163.132]
x-ms-office365-filtering-correlation-id: 5dcde86f-b837-4d7a-df77-08d3f860cedc
x-microsoft-exchange-diagnostics:
	1;MWHPR02MB2511;6:kJ/z0gnMLmYPFgZQaDyd2pKK3WwnveqZjRn6RH0ykN0Zqxk1Qz4UzlMZrNx5Bz3eaMx2Xxxi8iHx4lSMHnXgaTL3IraShisYdZJy8nXoMDwxCKcfvof/BV1SbDfwAMC0tC5MR30oE4gCQNCwAmW1KNukUxX/M1L5NWq9hfs119bsjQeuyaWJz6G3IDYpZztkE2nJvWObcFoCtDrPPcaQ2D8/69AVTwGN+sxK9RgKTNTzMwBrf1RNMi6Yij052HS/dHqaW0OletROTBJYhmYPJaMcfUD5Nbn494H4o14rDZVVm0qXMhTngkPQ21rRHp++;5:qnphAugQ7c2D+lZQGy8X8w98FYn5swvxVfollxREGJyP+5k7H3mPzYJwAirEyxMJn3qPuWOsX/FMtzOQzlaJxG/Zwz0a1zydn8eO28pF8G0nliQ1C841p7/cw2P9FvfUdf5kMRTI5Ukoqxs9ZiljOsMxSAZdBZLhiA515LSBF9s=;24:vePWa69q/OMKfppskY8MSLh791R/7iH4J1OsmDAkRiGqjSFBdKmdWMq4579x3ryJejcIwjMAt/Z2Z8mCmXlqKPH5fXeAShZKTbJdeBmTsGc=;7:FBxnKFLR84dWraob3+OIi3g1607zojme/042NHTMmqb44CckIZJdUXQRXRZyG/DcCv70HHII85hdr1Ug5Q5t8J9ZKhIYbkVaXxxexI3zpa4WEUkJjnk5Rqd8W0+KIWV4ozIYL5e/MdQDmxAeWmWp/YRpfE/F/LAhl0Ju6D2RTBI+dKsSRmfU9yTlbLe9qGYd5el9ANGZbIjywCpeKxu94x/cYsxiAcvk361aHH+fkQTtzMwEzVr0k36JL8o5NvbyUW3E3+gjwO35TMGwtP3IXdLvNUVQHpjoujj3JTV6BjjLKDvajUIJX9KUT3sueOL6k74R1F41Es00ahd4MjzGHJNpClHbunKlSJr2ePxhDiI=
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:MWHPR02MB2511;
x-microsoft-antispam-prvs: <MWHPR02MB2511F44AF97E79DE181AF328BFD20@MWHPR02MB2511.namprd02.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(23657631684272)(166708455590820)(194151415913766)(192278398808882)(17755550239193);
x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(6040176)(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001);SRVR:MWHPR02MB2511;BCL:0;PCL:0;RULEID:;SRVR:MWHPR02MB2511;
x-forefront-prvs: 0100732B76
x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(7916002)(199003)(189002)(76104003)(377454003)(66066001)(33656002)(6116002)(15975445007)(105586002)(4326007)(87936001)(19580395003)(8676002)(5660300001)(2906002)(575784001)(2900100001)(6606003)(8936002)(2950100002)(10400500002)(50986999)(19627405001)(102836003)(9686002)(77096005)(586003)(54356999)(86362001)(76576001)(5001770100001)(97736004)(3660700001)(106356001)(19580405001)(5002640100001)(92566002)(3846002)(76176999)(7846002)(189998001)(7736002)(122556002)(81156014)(15188155005)(16236675004)(19625215002)(19617315012)(74316002)(16799955002)(106116001)(7696004)(81166006)(7906003)(3280700002)(68736007)(101416001)(99286002)(556834004);DIR:OUT;SFP:1102;SCL:1;SRVR:MWHPR02MB2511;H:MWHPR02MB2477.namprd02.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en;
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_MWHPR02MB24770D9226ECEBD03E242481BFD20MWHPR02MB2477namp_"
MIME-Version: 1.0
X-OriginatorOrg: zend.com
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Oct 2016 20:45:05.6999
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 32210298-c08b-4829-8097-6b12c025a892
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR02MB2511
Subject: Re: [PHP-DEV] Exploit fully packed array/hash property
From: dmitry@zend.com (Dmitry Stogov)

--_000_MWHPR02MB24770D9226ECEBD03E242481BFD20MWHPR02MB2477namp_
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable


I've committed the safe part of the patch (almost your original idea).


http://git.php.net/?p=3Dphp-src.git;a=3Dcommitdiff;h=3D9ded1b4edbb140520e06=
0de597267b3cb439f4c4


The part related to HASH_FLAG_LONG_KEYS/HASH_FLAG_STRING_KEYS is here


https://gist.github.com/dstogov/059c73e7c732fe55110ebf0ca18b4859


as I said, in current state, it makes reduction instead of improvement.

Probably, if we find more use cases for these flags, it may make improvemen=
t.


Thanks. Dmitry.


________________________________
From: Benjamin Coutu <ben.coutu@zeyos.com>
Sent: Wednesday, October 19, 2016 9:58:01 PM
To: Dmitry Stogov; Xinchen Hui; Nikita Popov; Joe Watkins; Bob Weinand; And=
rea Faulds
Cc: PHP Internals
Subject: Re: [PHP-DEV] Exploit fully packed array/hash property

Hi Dmitry,

On second thought, I might have dismissed your HASH_FLAG_*_KEYS idea premat=
urely.

Of course we will have to set/unset the flag in parts of the code that are =
very hot and naturally that will lead to a regression in terms of CPU instr=
uctions. But in regards to your idea of possibly eliminating redundant chec=
ks on every loop iteration, I think it could be interesting. It's a tradeof=
f between maintaining the necessary flags and avoiding repeatedly iterating=
 over branches. Given that bitwise operations on these flags are just about=
 the cheapest operations the CPU can perform (no pipeline stalls and flags =
usually already in L1 cache at that point), and branching inside a loop bei=
ng extremely costly (with the risk of pipeline stalls caused by branch miss=
 prediction, which might even happen repeatedly, and EXPECTED/UNEXPECTED ma=
cros undesirable in most of these cases), choosing to maintain those flags =
on write operations in order to speed up read operations suddenly looks muc=
h more appealing. In many operations that deal with the hash table in bulk =
we might even be able to set the flag just once upfront. So maybe we should=
 investigate further. Your quick test is not conclusive because you have ef=
fectively only benchmarked the negatives without settling it with the posit=
ives.

I don't know wether the additional code complexity is worth the effort thou=
gh. Personally I'd like to focus on getting more out of the packed hash tab=
le case, meaning trying to preserve the packed characteristics and utilizin=
g dedicated code paths as much as possible throughout the entire code base =
while using the existing infrastructure to do so without additional overhea=
d. Packed arrays are very ubiquitous after all, and as HT_IS_PACKED always =
implicates HASH_FLAG_LONG_KEYS, there is not that great of a need for the l=
atter if we can ensure to use packed arrays wherever possible.

On another note, and this comes without any caveats, we could at least use =
HT_IS_WITHOUT_HOLES to get rid of repeated checks for Z_TYPE(p->val) =3D=3D=
 IS_UNDEF inside loops. This would not entail any overhead on write. What d=
o you think?

Cheers,

Benjamin

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Original =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
From: Dmitry Stogov <dmitry@zend.com>
To: Benjamin Coutu <ben.coutu@zeyos.com>, Xinchen Hui <xinchen.h@zend.com>,=
 Nikita Popov <nikita.ppv@gmail.com>, Joe Watkins <pthreads@pthreads.org>, =
"Bob Weinand" <bobwei9@hotmail.com>, Andrea Faulds <ajf@php.net>
Date: Wed, 19 Oct 2016 18:02:53 +0200
Subject: Re: [PHP-DEV] Exploit fully packed array/hash property

This is an option.

If nobody propose a better solution, I'll prepare the patch tomorrow (this =
solution won't make BC breaks at all).

BTW: I think, HASH_FLAG_*_KEYS may be used to eliminate redundant checks on=
 every loop iteration in some functions.

Thanks. Dmitry.


--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php


--_000_MWHPR02MB24770D9226ECEBD03E242481BFD20MWHPR02MB2477namp_--