com php-src: zend_hash_do_resize: amortizing the cost of compaction: Zend/zend_hash.c
| From: | Xinchen Hui | Date: | Thu, 26 Mar 2015 18:05:38 +0000 |
| Subject: | com php-src: zend_hash_do_resize: amortizing the cost of compaction: Zend/zend_hash.c | ||
| Groups: | php.cvs | ||
| Request: | Send a blank email to php-cvs+get-87650@lists.php.net to get a copy of this message | ||
Commit: b3962ab94052254cec19034b77af0ca040b50fdd
Author: K <kaja47@k47.cz> Thu, 26 Mar 2015 19:05:38 +0100
Parents: d9d74d37ac2de7267b3c9904bb6e77c231f4973a
Branches: master
Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=b3962ab94052254cec19034b77af0ca040b50fdd
Log:
zend_hash_do_resize: amortizing the cost of compaction
New implementation of hashtables introduced a compaction step which is
triggered when a hashtable is full but it contains at least one deleted
bucket. Therefore there is a possibility that a cleverly crafted code can
trigger this compaction step (which takes time proportional to the size of
hashtabe) by executing constatnt number of operations. When the hashtable
is full, deletion and subsequent addition or single element triggers a
table compaction and these two steps can be repeated ad infinitum. This
might be avenue for a DOS attack.
This patch allows compaction to be performed only if the hashtable contains
at least 1/32 deleted elements, otherwise the hashtable is doubled in size.
Linear amount of work caused by compaction is amortized over multiple
malicious additions and deletions.
Changed paths:
M Zend/zend_hash.c
Diff:
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c
index 1fd3ccf..09b8fa4 100644
--- a/Zend/zend_hash.c
+++ b/Zend/zend_hash.c
@@ -777,7 +777,7 @@ static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
IS_CONSISTENT(ht);
HT_ASSERT(GC_REFCOUNT(ht) == 1);
- if (ht->nNumUsed > ht->nNumOfElements) {
+ if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /*
additional term is there to amortize the cost of compaction */
HANDLE_BLOCK_INTERRUPTIONS();
zend_hash_rehash(ht);
HANDLE_UNBLOCK_INTERRUPTIONS();