A possible bug in ngx_rbtree

[YongFeng Wu]

Hi Maxim,

Thank you so much for looking into it:

Following is the nginx -V output:

nginx version: nginx/1.2.3
built by gcc 4.2.1 20070719  [FreeBSD]
configure arguments: --with-pcre --with-debug --with-http_geoip_module
--with-http_stub_status_module

Following is the content for cache, cache->rbtree, root and sentinel:

(gdb) p cache
$5 = (ngx_open_file_cache_t *) 0x8012495f8
(gdb) p *cache
$6 = {rbtree = {root = 0x803377580, sentinel = 0x801249610, insert =
0x423ba0 <ngx_open_file_cache_rbtree_insert_value>}, sentinel = {
    key = 0, left = 0x0, right = 0x0, parent = 0x8044d4100, color = 0 '\0',
data = 0 '\0'}, expire_queue = {prev = 0x8044d4ba8,
    next = 0x803376228}, current = 999, max = 1000, inactive = 60}
(gdb) p cache->rbtree
$7 = {root = 0x803377580, sentinel = 0x801249610, insert = 0x423ba0
<ngx_open_file_cache_rbtree_insert_value>}
(gdb) p *cache->rbtree->root
$8 = {key = 2661524630, left = 0x801230100, right = 0x8032b4100, parent =
0x0, color = 0 '\0', data = 46 '.'}
(gdb) p cache->sentinel
$9 = {key = 0, left = 0x0, right = 0x0, parent = 0x8044d4100, color = 0
'\0', data = 0 '\0'}
(gdb) p
*cache->sentinel->parent->parent->parent->parent->parent->parent->parent->pa
rent
$10 = {key = 3464485871, left = 0x803b35680, right = 0x8032b4d00, parent =
0x803377580, color = 0 '\0', data = 0 '\0'}
(gdb) p
*cache->sentinel->parent->parent->parent->parent->parent->parent->parent->pa
rent->parent
$11 = {key = 2661524630, left = 0x801230100, right = 0x8032b4100, parent =
0x0, color = 0 '\0', data = 46 '.'}

One thing weird is that the sentinel->parent is not null but set to a node.
Could this cause some problems? sentinel->parent could be set in code like
(function ngx_rbtree_delete, line 209 in ngx_rbtree.c, version 1.2.3):

    if (subst == node) {

        temp->parent = subst->parent;

    } else {


Again, thank you for your help.

Yongfeng Wu


-----Original Message-----
From: Maxim Dounin [mailto:mdounin at mdounin.ru] 
Sent: Tuesday, October 02, 2012 9:00 AM
To: nginx-devel at nginx.org; ywu at about.com
Subject: Re: A possible bug in ngx_rbtree

Hello!

On Fri, Sep 28, 2012 at 11:01:12AM -0400, YongFeng Wu wrote:

> Hi,
> 
>  
> 
> We just found a worker process was stuck in an infinite loop, in 
> function ngx_open_file_lookup(). Checking the open file cache RB tree 
> with GDB shows the following:
> 
>  
> 
> (gdb) p cache->rbtree.root->right
> 
> $3 = (ngx_rbtree_node_t *) 0x80122f900
> 
> (gdb) p cache->rbtree.root->right->right
> 
> $4 = (ngx_rbtree_node_t *) 0x8040ea400
> 
> (gdb) p cache->rbtree.root->right->right->left
> 
> $5 = (ngx_rbtree_node_t *) 0x801236980
> 
>  
> 
> (gdb) p cache->rbtree.root->right->right->left->right
> 
> $6 = (ngx_rbtree_node_t *) 0x8090ee080
> 
> (gdb) p cache->rbtree.root->right->right->left->right->right
> 
> $7 = (ngx_rbtree_node_t *) 0x804aab280
> 
> (gdb) p cache->rbtree.root->right->right->left->right->right->left
> 
> $8 = (ngx_rbtree_node_t *) 0x804aabf00

[...]

> That means the $9 == $9->parent->parent->parent, so the infinite loop.
> 
> I think there might be a bug in ngx_rbtree.c. I'll really appreciate 
> it if somebody can look into it.

I've looked though code again and don't see any obvious problems.

Could you please provide more details?  It would be helpful to see "nginx
-V" output, and to make sure there are no 3rd party modules/patches.  It
might be also helpful to look at "cache", "*cache" and "cache->rbtree", in
particular at root and sentinel addresses, as the best guess for now is some
memory corruption.  Stack trace might be also helpful.

--
Maxim Dounin
http://nginx.com/support.html