Mercurial > hg > nginx
changeset 4515:8bb695c05870 stable-1.0
Merge of r4498:
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, 05 Mar 2012 13:17:56 +0000 |
parents | 79142134d616 |
children | b927410d9638 |
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_req_module.c src/http/modules/ngx_http_limit_zone_module.c src/http/ngx_http_file_cache.c |
diffstat | 6 files changed, 111 insertions(+), 146 deletions(-) [+] |
line wrap: on
line diff
--- a/src/core/ngx_open_file_cache.c Mon Mar 05 13:06:29 2012 +0000 +++ b/src/core/ngx_open_file_cache.c Mon Mar 05 13:17:56 2012 +0000 @@ -837,20 +837,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 Mar 05 13:06:29 2012 +0000 +++ b/src/core/ngx_resolver.c Mon Mar 05 13:17:56 2012 +0000 @@ -1626,20 +1626,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 Mar 05 13:06:29 2012 +0000 +++ b/src/event/ngx_event_openssl.c Mon Mar 05 13:17:56 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_req_module.c Mon Mar 05 13:06:29 2012 +0000 +++ b/src/http/modules/ngx_http_limit_req_module.c Mon Mar 05 13:17:56 2012 +0000 @@ -372,47 +372,42 @@ /* hash == node->key */ - do { - lr = (ngx_http_limit_req_node_t *) &node->color; + lr = (ngx_http_limit_req_node_t *) &node->color; - rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len); + rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len); - if (rc == 0) { - ngx_queue_remove(&lr->queue); - ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); - - tp = ngx_timeofday(); - - now = (ngx_msec_t) (tp->sec * 1000 + tp->msec); - ms = (ngx_msec_int_t) (now - lr->last); - - excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; + if (rc == 0) { + ngx_queue_remove(&lr->queue); + ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); - if (excess < 0) { - excess = 0; - } + tp = ngx_timeofday(); - *ep = excess; + now = (ngx_msec_t) (tp->sec * 1000 + tp->msec); + ms = (ngx_msec_int_t) (now - lr->last); - if ((ngx_uint_t) excess > lrcf->burst) { - return NGX_BUSY; - } + excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; - lr->excess = excess; - lr->last = now; - - if (excess) { - return NGX_AGAIN; - } - - return NGX_OK; + if (excess < 0) { + excess = 0; } - node = (rc < 0) ? node->left : node->right; + *ep = excess; + + if ((ngx_uint_t) excess > lrcf->burst) { + return NGX_BUSY; + } + + lr->excess = excess; + lr->last = now; - } while (node != sentinel && hash == node->key); + if (excess) { + return NGX_AGAIN; + } - break; + return NGX_OK; + } + + node = (rc < 0) ? node->left : node->right; } *ep = 0;
--- a/src/http/modules/ngx_http_limit_zone_module.c Mon Mar 05 13:06:29 2012 +0000 +++ b/src/http/modules/ngx_http_limit_zone_module.c Mon Mar 05 13:17:56 2012 +0000 @@ -194,31 +194,26 @@ /* hash == node->key */ - do { - lz = (ngx_http_limit_zone_node_t *) &node->color; + lz = (ngx_http_limit_zone_node_t *) &node->color; - rc = ngx_memn2cmp(vv->data, lz->data, len, (size_t) lz->len); + rc = ngx_memn2cmp(vv->data, lz->data, len, (size_t) lz->len); - if (rc == 0) { - if ((ngx_uint_t) lz->conn < lzcf->conn) { - lz->conn++; - goto done; - } - - ngx_shmtx_unlock(&shpool->mutex); - - ngx_log_error(lzcf->log_level, r->connection->log, 0, - "limiting connections by zone \"%V\"", - &lzcf->shm_zone->shm.name); - - return NGX_HTTP_SERVICE_UNAVAILABLE; + if (rc == 0) { + if ((ngx_uint_t) lz->conn < lzcf->conn) { + lz->conn++; + goto done; } - node = (rc < 0) ? node->left : node->right; + ngx_shmtx_unlock(&shpool->mutex); - } while (node != sentinel && hash == node->key); + ngx_log_error(lzcf->log_level, r->connection->log, 0, + "limiting connections by zone \"%V\"", + &lzcf->shm_zone->shm.name); - break; + return NGX_HTTP_SERVICE_UNAVAILABLE; + } + + node = (rc < 0) ? node->left : node->right; } n = offsetof(ngx_rbtree_node_t, color)
--- a/src/http/ngx_http_file_cache.c Mon Mar 05 13:06:29 2012 +0000 +++ b/src/http/ngx_http_file_cache.c Mon Mar 05 13:17:56 2012 +0000 @@ -673,21 +673,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 */