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

Maxim Dounin 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.

Maxim Dounin

More information about the nginx-devel mailing list