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.

2 files changed, 37 insertions, 47 deletions

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)