diff options
| author | K <kaja47@k47.cz> | 2015-03-26 19:05:38 +0100 |
|---|---|---|
| committer | K <kaja47@k47.cz> | 2015-03-26 19:05:38 +0100 |
| commit | b3962ab94052254cec19034b77af0ca040b50fdd (patch) | |
| tree | fb2bf7132b22921b2238bc760360dc9e31b5631b | |
| parent | d9d74d37ac2de7267b3c9904bb6e77c231f4973a (diff) | |
| download | php-git-b3962ab94052254cec19034b77af0ca040b50fdd.tar.gz | |
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.
| -rw-r--r-- | Zend/zend_hash.c | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c index 1fd3ccf3d9..09b8fa488e 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(); |