From 0ffc4c3218a2a1ca45405754c86221d295d00dd1 Mon Sep 17 00:00:00 2001 From: Maxim Dounin Date: Mon, 5 Mar 2012 13:17:56 +0000 Subject: 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. --- src/core/ngx_open_file_cache.c | 17 +++---- src/core/ngx_resolver.c | 17 +++---- src/event/ngx_event_openssl.c | 72 ++++++++++++--------------- src/http/modules/ngx_http_limit_req_module.c | 51 +++++++++---------- src/http/modules/ngx_http_limit_zone_module.c | 33 ++++++------ src/http/ngx_http_file_cache.c | 19 +++---- 6 files changed, 87 insertions(+), 122 deletions(-) (limited to 'src') diff --git a/src/core/ngx_open_file_cache.c b/src/core/ngx_open_file_cache.c index 9ac552111..9a98fccf2 100644 --- a/src/core/ngx_open_file_cache.c +++ b/src/core/ngx_open_file_cache.c @@ -837,20 +837,15 @@ ngx_open_file_lookup(ngx_open_file_cache_t *cache, ngx_str_t *name, /* hash == node->key */ - do { - file = (ngx_cached_open_file_t *) node; - - rc = ngx_strcmp(name->data, file->name); + file = (ngx_cached_open_file_t *) node; - if (rc == 0) { - return file; - } + rc = ngx_strcmp(name->data, file->name); - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); + if (rc == 0) { + return file; + } - break; + node = (rc < 0) ? node->left : node->right; } return NULL; diff --git a/src/core/ngx_resolver.c b/src/core/ngx_resolver.c index 7e77b191a..817e65df1 100644 --- a/src/core/ngx_resolver.c +++ b/src/core/ngx_resolver.c @@ -1626,20 +1626,15 @@ ngx_resolver_lookup_name(ngx_resolver_t *r, ngx_str_t *name, uint32_t hash) /* 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; - } + rn = (ngx_resolver_node_t *) node; - node = (rc < 0) ? node->left : node->right; + rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen); - } while (node != sentinel && hash == node->key); + if (rc == 0) { + return rn; + } - break; + node = (rc < 0) ? node->left : node->right; } /* not found */ diff --git a/src/event/ngx_event_openssl.c b/src/event/ngx_event_openssl.c index f393334ad..93d38a11f 100644 --- a/src/event/ngx_event_openssl.c +++ b/src/event/ngx_event_openssl.c @@ -1801,44 +1801,39 @@ ngx_ssl_get_cached_session(ngx_ssl_conn_t *ssl_conn, u_char *id, int len, /* hash == node->key */ - do { - sess_id = (ngx_ssl_sess_id_t *) node; + 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) { + rc = ngx_memn2cmp(id, sess_id->id, (size_t) len, (size_t) node->data); - if (sess_id->expire > ngx_time()) { - ngx_memcpy(buf, sess_id->session, sess_id->len); + if (rc == 0) { - ngx_shmtx_unlock(&shpool->mutex); + if (sess_id->expire > ngx_time()) { + ngx_memcpy(buf, sess_id->session, sess_id->len); - p = buf; - sess = d2i_SSL_SESSION(NULL, &p, sess_id->len); + ngx_shmtx_unlock(&shpool->mutex); - return sess; - } + p = buf; + sess = d2i_SSL_SESSION(NULL, &p, sess_id->len); + + return sess; + } - ngx_queue_remove(&sess_id->queue); + ngx_queue_remove(&sess_id->queue); - ngx_rbtree_delete(&cache->session_rbtree, node); + ngx_rbtree_delete(&cache->session_rbtree, node); - ngx_slab_free_locked(shpool, sess_id->session); + 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; - } + ngx_slab_free_locked(shpool, sess_id); - node = (rc < 0) ? node->left : node->right; + sess = NULL; - } while (node != sentinel && hash == node->key); + goto done; + } - break; + node = (rc < 0) ? node->left : node->right; } done: @@ -1908,31 +1903,26 @@ ngx_ssl_remove_session(SSL_CTX *ssl, ngx_ssl_session_t *sess) /* hash == node->key */ - do { - sess_id = (ngx_ssl_sess_id_t *) node; + sess_id = (ngx_ssl_sess_id_t *) node; - rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data); + rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data); - if (rc == 0) { + if (rc == 0) { - ngx_queue_remove(&sess_id->queue); + ngx_queue_remove(&sess_id->queue); - ngx_rbtree_delete(&cache->session_rbtree, node); + ngx_rbtree_delete(&cache->session_rbtree, node); - ngx_slab_free_locked(shpool, sess_id->session); + 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; + ngx_slab_free_locked(shpool, sess_id); - } while (node != sentinel && hash == node->key); + goto done; + } - break; + node = (rc < 0) ? node->left : node->right; } done: diff --git a/src/http/modules/ngx_http_limit_req_module.c b/src/http/modules/ngx_http_limit_req_module.c index 1d156157f..3b879043c 100644 --- a/src/http/modules/ngx_http_limit_req_module.c +++ b/src/http/modules/ngx_http_limit_req_module.c @@ -372,47 +372,42 @@ ngx_http_limit_req_lookup(ngx_http_limit_req_conf_t *lrcf, ngx_uint_t hash, /* 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); + if (rc == 0) { + ngx_queue_remove(&lr->queue); + ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); - tp = ngx_timeofday(); + tp = ngx_timeofday(); - now = (ngx_msec_t) (tp->sec * 1000 + tp->msec); - ms = (ngx_msec_int_t) (now - lr->last); + 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; + excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; - if (excess < 0) { - excess = 0; - } - - *ep = excess; + if (excess < 0) { + excess = 0; + } - if ((ngx_uint_t) excess > lrcf->burst) { - return NGX_BUSY; - } + *ep = excess; - lr->excess = excess; - lr->last = now; + if ((ngx_uint_t) excess > lrcf->burst) { + return NGX_BUSY; + } - if (excess) { - return NGX_AGAIN; - } + lr->excess = excess; + lr->last = now; - return NGX_OK; + if (excess) { + return NGX_AGAIN; } - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && hash == node->key); + return NGX_OK; + } - break; + node = (rc < 0) ? node->left : node->right; } *ep = 0; diff --git a/src/http/modules/ngx_http_limit_zone_module.c b/src/http/modules/ngx_http_limit_zone_module.c index d92f5354a..9a8ea87fe 100644 --- a/src/http/modules/ngx_http_limit_zone_module.c +++ b/src/http/modules/ngx_http_limit_zone_module.c @@ -194,31 +194,26 @@ ngx_http_limit_zone_handler(ngx_http_request_t *r) /* 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); + + return NGX_HTTP_SERVICE_UNAVAILABLE; + } - break; + node = (rc < 0) ? node->left : node->right; } n = offsetof(ngx_rbtree_node_t, color) diff --git a/src/http/ngx_http_file_cache.c b/src/http/ngx_http_file_cache.c index 0fe2c4af8..68943a87b 100644 --- a/src/http/ngx_http_file_cache.c +++ b/src/http/ngx_http_file_cache.c @@ -673,21 +673,16 @@ ngx_http_file_cache_lookup(ngx_http_file_cache_t *cache, u_char *key) /* 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; - } - - node = (rc < 0) ? node->left : node->right; - - } while (node != sentinel && node_key == node->key); + if (rc == 0) { + return fcn; + } - break; + node = (rc < 0) ? node->left : node->right; } /* not found */ -- cgit