[BUG] memory leak risk in rbtree operation with hash collision

[lanshun zhou]

The algorithm of many rbtree lookup functions in nginx requires that nodes
with the same hash

value are linked together, but sometimes this may be broken with the
rebalance of the tree

after new nodes inserted.  See the following example, the number contains
hash value and node

key, 51 shares the same hash value with 52. After the inserting of 63 and
the rebalancing of the

tree, they are separated. Then 51 is "lost" from the tree. every lookup for
51 returns null and new

nodes are always alloced until one of them is linked with 52 again.

[image: 内嵌图片 1]

rbtree2.diff is a clean diff which ignores white space changes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20120227/42ffcdbe/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rbtree.png
Type: image/png
Size: 8401 bytes
Desc: not available
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20120227/42ffcdbe/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rbtree.diff
Type: application/octet-stream
Size: 10301 bytes
Desc: not available
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20120227/42ffcdbe/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rbtree2.diff
Type: application/octet-stream
Size: 5059 bytes
Desc: not available
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20120227/42ffcdbe/attachment-0003.obj>