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.

6 files changed, 81 insertions, 116 deletions

diff --git a/src/core/ngx_open_file_cache.c b/src/core/ngx_open_file_cache.c
index 73a2db0c8..c44ac96b8 100644
--- a/src/core/ngx_open_file_cache.c
+++ b/src/core/ngx_open_file_cache.c
@@ -1142,20 +1142,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 5c516175e..2e3047135 100644
--- a/src/core/ngx_resolver.c
+++ b/src/core/ngx_resolver.c
@@ -1689,20 +1689,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_conn_module.c b/src/http/modules/ngx_http_limit_conn_module.c
index 6322fd682..c119945ef 100644
--- a/src/http/modules/ngx_http_limit_conn_module.c
+++ b/src/http/modules/ngx_http_limit_conn_module.c
@@ -325,20 +325,15 @@ ngx_http_limit_conn_lookup(ngx_rbtree_t *rbtree, ngx_http_variable_value_t *vv,
 
         /* hash == node->key */
 
-        do {
-            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;
-            }
+        lcn = (ngx_http_limit_conn_node_t *) &node->color;
 
-            node = (rc < 0) ? node->left : node->right;
-
-        } while (node != sentinel && hash == node->key);
+        rc = ngx_memn2cmp(vv->data, lcn->data,
+                          (size_t) vv->len, (size_t) lcn->len);
+        if (rc == 0) {
+            return node;
+        }
 
-        break;
+        node = (rc < 0) ? node->left : node->right;
     }
 
     return NULL;
diff --git a/src/http/modules/ngx_http_limit_req_module.c b/src/http/modules/ngx_http_limit_req_module.c
index e4d90a98f..f1698a394 100644
--- a/src/http/modules/ngx_http_limit_req_module.c
+++ b/src/http/modules/ngx_http_limit_req_module.c
@@ -385,47 +385,42 @@ ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, 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);
 
-                ms = (ngx_msec_int_t) (now - lr->last);
-
-                excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
-
-                if (excess < 0) {
-                    excess = 0;
-                }
-
-                *ep = excess;
+            ms = (ngx_msec_int_t) (now - lr->last);
 
-                if ((ngx_uint_t) excess > limit->burst) {
-                    return NGX_BUSY;
-                }
+            excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
 
-                if (account) {
-                    lr->excess = excess;
-                    lr->last = now;
-                    return NGX_OK;
-                }
+            if (excess < 0) {
+                excess = 0;
+            }
 
-                lr->count++;
+            *ep = excess;
 
-                ctx->node = lr;
+            if ((ngx_uint_t) excess > limit->burst) {
+                return NGX_BUSY;
+            }
 
-                return NGX_AGAIN;
+            if (account) {
+                lr->excess = excess;
+                lr->last = now;
+                return NGX_OK;
             }
 
-            node = (rc < 0) ? node->left : node->right;
+            lr->count++;
 
-        } while (node != sentinel && hash == node->key);
+            ctx->node = lr;
+
+            return NGX_AGAIN;
+        }
 
-        break;
+        node = (rc < 0) ? node->left : node->right;
     }
 
     *ep = 0;
diff --git a/src/http/ngx_http_file_cache.c b/src/http/ngx_http_file_cache.c
index eb1e99015..bd6cebadd 100644
--- a/src/http/ngx_http_file_cache.c
+++ b/src/http/ngx_http_file_cache.c
@@ -799,21 +799,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 */