From 7ca6c1ff782afbb83b9f17d6552566c823247e29 Mon Sep 17 00:00:00 2001
From: Maxim Dounin <mdounin@mdounin.ru>
Date: Mon, 27 Feb 2012 22:15:39 +0000
Subject: 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/http/modules/ngx_http_limit_conn_module.c | 19 ++++------
 src/http/modules/ngx_http_limit_req_module.c  | 53 ++++++++++++---------------
 src/http/ngx_http_file_cache.c                | 19 ++++------
 3 files changed, 38 insertions(+), 53 deletions(-)

(limited to 'src/http')

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 */
-- 
cgit