[BUG] memory leak risk in rbtree operation with hash collision
mdounin at mdounin.ru
Mon Feb 27 22:16:06 UTC 2012
On Mon, Feb 27, 2012 at 05:52:45PM +0800, lanshun zhou wrote:
> 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.
Good catch, thanx.
Patch committed with minor style fixes.
More information about the nginx-devel