Mercurial > hg > nginx
changeset 4497:95ab6658654a
Fix of rbtree lookup on hash collisions.
Previous code incorrectly assumed that nodes with identical keys are linked
together. This might not be true after tree rebalance.
Patch by Lanshun Zhou.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Mon, 27 Feb 2012 22:15:39 +0000 |
parents | be6c250b827b |
children | 569ea17767bf |
files | src/core/ngx_open_file_cache.c src/core/ngx_resolver.c src/event/ngx_event_openssl.c src/http/modules/ngx_http_limit_conn_module.c src/http/modules/ngx_http_limit_req_module.c src/http/ngx_http_file_cache.c |
diffstat | 6 files changed, 105 insertions(+), 140 deletions(-) [+] |
line wrap: on
line diff
--- a/src/core/ngx_open_file_cache.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/core/ngx_open_file_cache.c Mon Feb 27 22:15:39 2012 +0000 @@ -1142,20 +1142,15 @@ /* hash == node->key */ - do { - file = (ngx_cached_open_file_t *) node; + file = (ngx_cached_open_file_t *) node; - rc = ngx_strcmp(name->data, file->name); + rc = ngx_strcmp(name->data, file->name); - if (rc == 0) { - return file; - } + if (rc == 0) { + return file; + } - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); - - break; + node = (rc < 0) ? node->left : node->right; } return NULL;
--- a/src/core/ngx_resolver.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/core/ngx_resolver.c Mon Feb 27 22:15:39 2012 +0000 @@ -1689,20 +1689,15 @@ /* hash == node->key */ - do { - rn = (ngx_resolver_node_t *) node; - - rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen); - - if (rc == 0) { - return rn; - } - - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); - - break; + rn = (ngx_resolver_node_t *) node; + + rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen); + + if (rc == 0) { + return rn; + } + + node = (rc < 0) ? node->left : node->right; } /* not found */
--- a/src/event/ngx_event_openssl.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/event/ngx_event_openssl.c Mon Feb 27 22:15:39 2012 +0000 @@ -1801,44 +1801,39 @@ /* hash == node->key */ - do { - sess_id = (ngx_ssl_sess_id_t *) node; - - rc = ngx_memn2cmp(id, sess_id->id, - (size_t) len, (size_t) node->data); - if (rc == 0) { - - if (sess_id->expire > ngx_time()) { - ngx_memcpy(buf, sess_id->session, sess_id->len); - - ngx_shmtx_unlock(&shpool->mutex); - - p = buf; - sess = d2i_SSL_SESSION(NULL, &p, sess_id->len); - - return sess; - } - - ngx_queue_remove(&sess_id->queue); - - ngx_rbtree_delete(&cache->session_rbtree, node); - - ngx_slab_free_locked(shpool, sess_id->session); + sess_id = (ngx_ssl_sess_id_t *) node; + + rc = ngx_memn2cmp(id, sess_id->id, (size_t) len, (size_t) node->data); + + if (rc == 0) { + + if (sess_id->expire > ngx_time()) { + ngx_memcpy(buf, sess_id->session, sess_id->len); + + ngx_shmtx_unlock(&shpool->mutex); + + p = buf; + sess = d2i_SSL_SESSION(NULL, &p, sess_id->len); + + return sess; + } + + ngx_queue_remove(&sess_id->queue); + + ngx_rbtree_delete(&cache->session_rbtree, node); + + ngx_slab_free_locked(shpool, sess_id->session); #if (NGX_PTR_SIZE == 4) - ngx_slab_free_locked(shpool, sess_id->id); + ngx_slab_free_locked(shpool, sess_id->id); #endif - ngx_slab_free_locked(shpool, sess_id); - - sess = NULL; - - goto done; - } - - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); - - break; + ngx_slab_free_locked(shpool, sess_id); + + sess = NULL; + + goto done; + } + + node = (rc < 0) ? node->left : node->right; } done: @@ -1908,31 +1903,26 @@ /* hash == node->key */ - do { - sess_id = (ngx_ssl_sess_id_t *) node; - - rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data); - - if (rc == 0) { - - ngx_queue_remove(&sess_id->queue); - - ngx_rbtree_delete(&cache->session_rbtree, node); - - ngx_slab_free_locked(shpool, sess_id->session); + sess_id = (ngx_ssl_sess_id_t *) node; + + rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data); + + if (rc == 0) { + + ngx_queue_remove(&sess_id->queue); + + ngx_rbtree_delete(&cache->session_rbtree, node); + + ngx_slab_free_locked(shpool, sess_id->session); #if (NGX_PTR_SIZE == 4) - ngx_slab_free_locked(shpool, sess_id->id); + ngx_slab_free_locked(shpool, sess_id->id); #endif - ngx_slab_free_locked(shpool, sess_id); - - goto done; - } - - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); - - break; + ngx_slab_free_locked(shpool, sess_id); + + goto done; + } + + node = (rc < 0) ? node->left : node->right; } done:
--- a/src/http/modules/ngx_http_limit_conn_module.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/http/modules/ngx_http_limit_conn_module.c Mon Feb 27 22:15:39 2012 +0000 @@ -325,20 +325,15 @@ /* hash == node->key */ - do { - lcn = (ngx_http_limit_conn_node_t *) &node->color; + lcn = (ngx_http_limit_conn_node_t *) &node->color; - rc = ngx_memn2cmp(vv->data, lcn->data, - (size_t) vv->len, (size_t) lcn->len); - if (rc == 0) { - return node; - } + rc = ngx_memn2cmp(vv->data, lcn->data, + (size_t) vv->len, (size_t) lcn->len); + if (rc == 0) { + return node; + } - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); - - break; + node = (rc < 0) ? node->left : node->right; } return NULL;
--- a/src/http/modules/ngx_http_limit_req_module.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/http/modules/ngx_http_limit_req_module.c Mon Feb 27 22:15:39 2012 +0000 @@ -385,47 +385,42 @@ /* hash == node->key */ - do { - lr = (ngx_http_limit_req_node_t *) &node->color; - - rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len); + lr = (ngx_http_limit_req_node_t *) &node->color; - if (rc == 0) { - ngx_queue_remove(&lr->queue); - ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); - - ms = (ngx_msec_int_t) (now - lr->last); - - excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; - - if (excess < 0) { - excess = 0; - } + rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len); - *ep = excess; - - if ((ngx_uint_t) excess > limit->burst) { - return NGX_BUSY; - } + if (rc == 0) { + ngx_queue_remove(&lr->queue); + ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); - if (account) { - lr->excess = excess; - lr->last = now; - return NGX_OK; - } + ms = (ngx_msec_int_t) (now - lr->last); - lr->count++; + excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; - ctx->node = lr; - - return NGX_AGAIN; + if (excess < 0) { + excess = 0; } - node = (rc < 0) ? node->left : node->right; + *ep = excess; + + if ((ngx_uint_t) excess > limit->burst) { + return NGX_BUSY; + } - } while (node != sentinel && hash == node->key); + if (account) { + lr->excess = excess; + lr->last = now; + return NGX_OK; + } - break; + lr->count++; + + ctx->node = lr; + + return NGX_AGAIN; + } + + node = (rc < 0) ? node->left : node->right; } *ep = 0;
--- a/src/http/ngx_http_file_cache.c Mon Feb 27 16:57:02 2012 +0000 +++ b/src/http/ngx_http_file_cache.c Mon Feb 27 22:15:39 2012 +0000 @@ -799,21 +799,16 @@ /* node_key == node->key */ - do { - fcn = (ngx_http_file_cache_node_t *) node; + fcn = (ngx_http_file_cache_node_t *) node; - rc = ngx_memcmp(&key[sizeof(ngx_rbtree_key_t)], fcn->key, - NGX_HTTP_CACHE_KEY_LEN - sizeof(ngx_rbtree_key_t)); + rc = ngx_memcmp(&key[sizeof(ngx_rbtree_key_t)], fcn->key, + NGX_HTTP_CACHE_KEY_LEN - sizeof(ngx_rbtree_key_t)); - if (rc == 0) { - return fcn; - } + if (rc == 0) { + return fcn; + } - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && node_key == node->key); - - break; + node = (rc < 0) ? node->left : node->right; } /* not found */