关于PHP Hashtable引起的bug的问题学习

bug描述: http://www.laruence.com/2011/12/29/2412.html
相关资料: http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html

就像上面资料中提到的,构造hash冲突是利用了PHP Hashtable对数值key的简单处理实现的。如果用字符串key来构造hash冲突,似乎就比较麻烦了; 严格地将,这个和PHP中的hash算法没有必然联系,对于字符串key是通过hash函数计算出一个无符号整型数然后和Hashtable的size取模的,而对于数字key是直接使用该数字与Hashtable的size取模的。

有些同学通过限制post数据的大小来从一定程度上环节带来的危害,限制post数据大小为不超过100k,下面来分析一下这个数字是否够用:
脚本1:

 
  1. <?php
  2. $size = pow(2, 15); // 可以通过第二个参数来改变提交的数据量的大小
  3. $data = ;
  4. for ($key=0, $maxkey=($size-1) * $size$key<= $maxkey$key+=$size) {
  5. $data .= $key.‘=&’;
  6.     $i++;
  7. }
  8. echo "key num: $i \n";
  9. echo "data length:"strlen($data);

通过这个脚本来得出key的多少和对应的数据量。

脚本2:

 
  1. <?php
  2. $size = pow(2, 15); // 16 is just an example, could also be 15 or 17
  3. $startTime = microtime(true);
  4. $array = array();
  5. for ($key = 0, $maxKey = ($size – 1) * $size$key <= $maxKey$key += $size) {
  6.         $array[$key] = 0;
  7. }
  8. $endTime = microtime(true);
  9. echo ‘Inserting ‘$size‘ evil elements took ‘$endTime – $startTime‘ seconds’"\n";
  10. $startTime = microtime(true);
  11. $array = array();
  12. for ($key = 0, $maxKey = $size – 1; $key <= $maxKey; ++$key) {
  13.         $array[$key] = 0;
  14. }
  15. $endTime = microtime(true);
  16. echo ‘Inserting ‘$size‘ good elements took ‘$endTime – $startTime‘ seconds’"\n";

通过这个脚本可以得出key的多少和相应消耗的时间。

80k的数据就可以构造8000 个key,耗费cpu时间大约不到2s;

360k的数据可以构造3.2万个key,耗费cpu时间大约30多s;

 

看来限制 100k 的数据还是非常有效的。

关于该bug的修复,官方给出了补丁,允许限制post数据的个数; 那么GET数据和Cookie数据会不会有这个问题呢?答案是不会的,我们可以从apache的源码中找到答案:

关于PHP Hashtable的更多参考资料:
http://www.qingliangcn.com/2009/07/php%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90%E4%B9%8Bhashtable/
http://www.phpchina.com/index.php?action-viewthread-tid-88505

———————
关于PHP Hashtable的几点提示:
1. Hashtable的最小大小为8 ,如果元素个数为9,则大小重新调整为16,每次调整都要遍历所有元素,重新计算hash值
2. 数值key不做hash,直接和Hashtable 的size取模
3. nNextFreeElement 用于数字索引的计数,其值为当前数字索引值加1,初始值为0
4. pNext, pLast 是hash冲突时的冲突链表的双向指针
5. PListNext, pListLast 是用于遍历数组的双向链表指针
6. pInternalPointer  是用于遍历数组的一个位置指针

留下评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据