com php-src: zend_hash_do_resize: amortizing the cost of compaction: Zend/zend_hash.c

From: 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();

« previous php.cvs (#87650) next »