diff src/http/modules/ngx_http_limit_req_module.c @ 4497:95ab6658654a

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, 27 Feb 2012 22:15:39 +0000
parents aacd7356c197
children 778ef9c3fd2d
line wrap: on
line diff
--- 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
 
         /* hash == node->key */
 
-        do {
-            lr = (ngx_http_limit_req_node_t *) &node->color;
-
-            rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);
+        lr = (ngx_http_limit_req_node_t *) &node->color;
 
-            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;
-                }
+        rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);
 
-                *ep = excess;
-
-                if ((ngx_uint_t) excess > limit->burst) {
-                    return NGX_BUSY;
-                }
+        if (rc == 0) {
+            ngx_queue_remove(&lr->queue);
+            ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
 
-                if (account) {
-                    lr->excess = excess;
-                    lr->last = now;
-                    return NGX_OK;
-                }
+            ms = (ngx_msec_int_t) (now - lr->last);
 
-                lr->count++;
+            excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
 
-                ctx->node = lr;
-
-                return NGX_AGAIN;
+            if (excess < 0) {
+                excess = 0;
             }
 
-            node = (rc < 0) ? node->left : node->right;
+            *ep = excess;
+
+            if ((ngx_uint_t) excess > limit->burst) {
+                return NGX_BUSY;
+            }
 
-        } while (node != sentinel && hash == node->key);
+            if (account) {
+                lr->excess = excess;
+                lr->last = now;
+                return NGX_OK;
+            }
 
-        break;
+            lr->count++;
+
+            ctx->node = lr;
+
+            return NGX_AGAIN;
+        }
+
+        node = (rc < 0) ? node->left : node->right;
     }
 
     *ep = 0;