1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Igor Sysoev
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#include <ngx_config.h>
9e18a033bSKonstantin Ananyev#include <ngx_core.h>
10e18a033bSKonstantin Ananyev#include <ngx_http.h>
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyev
13e18a033bSKonstantin Ananyevtypedef struct {
14e18a033bSKonstantin Ananyev    u_char                       color;
15e18a033bSKonstantin Ananyev    u_char                       dummy;
16e18a033bSKonstantin Ananyev    u_short                      len;
17e18a033bSKonstantin Ananyev    ngx_queue_t                  queue;
18e18a033bSKonstantin Ananyev    ngx_msec_t                   last;
19e18a033bSKonstantin Ananyev    /* integer value, 1 corresponds to 0.001 r/s */
20e18a033bSKonstantin Ananyev    ngx_uint_t                   excess;
21e18a033bSKonstantin Ananyev    ngx_uint_t                   count;
22e18a033bSKonstantin Ananyev    u_char                       data[1];
23e18a033bSKonstantin Ananyev} ngx_http_limit_req_node_t;
24e18a033bSKonstantin Ananyev
25e18a033bSKonstantin Ananyev
26e18a033bSKonstantin Ananyevtypedef struct {
27e18a033bSKonstantin Ananyev    ngx_rbtree_t                  rbtree;
28e18a033bSKonstantin Ananyev    ngx_rbtree_node_t             sentinel;
29e18a033bSKonstantin Ananyev    ngx_queue_t                   queue;
30e18a033bSKonstantin Ananyev} ngx_http_limit_req_shctx_t;
31e18a033bSKonstantin Ananyev
32e18a033bSKonstantin Ananyev
33e18a033bSKonstantin Ananyevtypedef struct {
34e18a033bSKonstantin Ananyev    ngx_http_limit_req_shctx_t  *sh;
35e18a033bSKonstantin Ananyev    ngx_slab_pool_t             *shpool;
36e18a033bSKonstantin Ananyev    /* integer value, 1 corresponds to 0.001 r/s */
37e18a033bSKonstantin Ananyev    ngx_uint_t                   rate;
38e18a033bSKonstantin Ananyev    ngx_http_complex_value_t     key;
39e18a033bSKonstantin Ananyev    ngx_http_limit_req_node_t   *node;
40e18a033bSKonstantin Ananyev} ngx_http_limit_req_ctx_t;
41e18a033bSKonstantin Ananyev
42e18a033bSKonstantin Ananyev
43e18a033bSKonstantin Ananyevtypedef struct {
44e18a033bSKonstantin Ananyev    ngx_shm_zone_t              *shm_zone;
45e18a033bSKonstantin Ananyev    /* integer value, 1 corresponds to 0.001 r/s */
46e18a033bSKonstantin Ananyev    ngx_uint_t                   burst;
47e18a033bSKonstantin Ananyev    ngx_uint_t                   nodelay; /* unsigned  nodelay:1 */
48e18a033bSKonstantin Ananyev} ngx_http_limit_req_limit_t;
49e18a033bSKonstantin Ananyev
50e18a033bSKonstantin Ananyev
51e18a033bSKonstantin Ananyevtypedef struct {
52e18a033bSKonstantin Ananyev    ngx_array_t                  limits;
53e18a033bSKonstantin Ananyev    ngx_uint_t                   limit_log_level;
54e18a033bSKonstantin Ananyev    ngx_uint_t                   delay_log_level;
55e18a033bSKonstantin Ananyev    ngx_uint_t                   status_code;
56e18a033bSKonstantin Ananyev} ngx_http_limit_req_conf_t;
57e18a033bSKonstantin Ananyev
58e18a033bSKonstantin Ananyev
59e18a033bSKonstantin Ananyevstatic void ngx_http_limit_req_delay(ngx_http_request_t *r);
60e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit,
61e18a033bSKonstantin Ananyev    ngx_uint_t hash, ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account);
62e18a033bSKonstantin Ananyevstatic ngx_msec_t ngx_http_limit_req_account(ngx_http_limit_req_limit_t *limits,
63e18a033bSKonstantin Ananyev    ngx_uint_t n, ngx_uint_t *ep, ngx_http_limit_req_limit_t **limit);
64e18a033bSKonstantin Ananyevstatic void ngx_http_limit_req_expire(ngx_http_limit_req_ctx_t *ctx,
65e18a033bSKonstantin Ananyev    ngx_uint_t n);
66e18a033bSKonstantin Ananyev
67e18a033bSKonstantin Ananyevstatic void *ngx_http_limit_req_create_conf(ngx_conf_t *cf);
68e18a033bSKonstantin Ananyevstatic char *ngx_http_limit_req_merge_conf(ngx_conf_t *cf, void *parent,
69e18a033bSKonstantin Ananyev    void *child);
70e18a033bSKonstantin Ananyevstatic char *ngx_http_limit_req_zone(ngx_conf_t *cf, ngx_command_t *cmd,
71e18a033bSKonstantin Ananyev    void *conf);
72e18a033bSKonstantin Ananyevstatic char *ngx_http_limit_req(ngx_conf_t *cf, ngx_command_t *cmd,
73e18a033bSKonstantin Ananyev    void *conf);
74e18a033bSKonstantin Ananyevstatic ngx_int_t ngx_http_limit_req_init(ngx_conf_t *cf);
75e18a033bSKonstantin Ananyev
76e18a033bSKonstantin Ananyev
77e18a033bSKonstantin Ananyevstatic ngx_conf_enum_t  ngx_http_limit_req_log_levels[] = {
78e18a033bSKonstantin Ananyev    { ngx_string("info"), NGX_LOG_INFO },
79e18a033bSKonstantin Ananyev    { ngx_string("notice"), NGX_LOG_NOTICE },
80e18a033bSKonstantin Ananyev    { ngx_string("warn"), NGX_LOG_WARN },
81e18a033bSKonstantin Ananyev    { ngx_string("error"), NGX_LOG_ERR },
82e18a033bSKonstantin Ananyev    { ngx_null_string, 0 }
83e18a033bSKonstantin Ananyev};
84e18a033bSKonstantin Ananyev
85e18a033bSKonstantin Ananyev
86e18a033bSKonstantin Ananyevstatic ngx_conf_num_bounds_t  ngx_http_limit_req_status_bounds = {
87e18a033bSKonstantin Ananyev    ngx_conf_check_num_bounds, 400, 599
88e18a033bSKonstantin Ananyev};
89e18a033bSKonstantin Ananyev
90e18a033bSKonstantin Ananyev
91e18a033bSKonstantin Ananyevstatic ngx_command_t  ngx_http_limit_req_commands[] = {
92e18a033bSKonstantin Ananyev
93e18a033bSKonstantin Ananyev    { ngx_string("limit_req_zone"),
94e18a033bSKonstantin Ananyev      NGX_HTTP_MAIN_CONF|NGX_CONF_TAKE3,
95e18a033bSKonstantin Ananyev      ngx_http_limit_req_zone,
96e18a033bSKonstantin Ananyev      0,
97e18a033bSKonstantin Ananyev      0,
98e18a033bSKonstantin Ananyev      NULL },
99e18a033bSKonstantin Ananyev
100e18a033bSKonstantin Ananyev    { ngx_string("limit_req"),
101e18a033bSKonstantin Ananyev      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE123,
102e18a033bSKonstantin Ananyev      ngx_http_limit_req,
103e18a033bSKonstantin Ananyev      NGX_HTTP_LOC_CONF_OFFSET,
104e18a033bSKonstantin Ananyev      0,
105e18a033bSKonstantin Ananyev      NULL },
106e18a033bSKonstantin Ananyev
107e18a033bSKonstantin Ananyev    { ngx_string("limit_req_log_level"),
108e18a033bSKonstantin Ananyev      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE1,
109e18a033bSKonstantin Ananyev      ngx_conf_set_enum_slot,
110e18a033bSKonstantin Ananyev      NGX_HTTP_LOC_CONF_OFFSET,
111e18a033bSKonstantin Ananyev      offsetof(ngx_http_limit_req_conf_t, limit_log_level),
112e18a033bSKonstantin Ananyev      &ngx_http_limit_req_log_levels },
113e18a033bSKonstantin Ananyev
114e18a033bSKonstantin Ananyev    { ngx_string("limit_req_status"),
115e18a033bSKonstantin Ananyev      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE1,
116e18a033bSKonstantin Ananyev      ngx_conf_set_num_slot,
117e18a033bSKonstantin Ananyev      NGX_HTTP_LOC_CONF_OFFSET,
118e18a033bSKonstantin Ananyev      offsetof(ngx_http_limit_req_conf_t, status_code),
119e18a033bSKonstantin Ananyev      &ngx_http_limit_req_status_bounds },
120e18a033bSKonstantin Ananyev
121e18a033bSKonstantin Ananyev      ngx_null_command
122e18a033bSKonstantin Ananyev};
123e18a033bSKonstantin Ananyev
124e18a033bSKonstantin Ananyev
125e18a033bSKonstantin Ananyevstatic ngx_http_module_t  ngx_http_limit_req_module_ctx = {
126e18a033bSKonstantin Ananyev    NULL,                                  /* preconfiguration */
127e18a033bSKonstantin Ananyev    ngx_http_limit_req_init,               /* postconfiguration */
128e18a033bSKonstantin Ananyev
129e18a033bSKonstantin Ananyev    NULL,                                  /* create main configuration */
130e18a033bSKonstantin Ananyev    NULL,                                  /* init main configuration */
131e18a033bSKonstantin Ananyev
132e18a033bSKonstantin Ananyev    NULL,                                  /* create server configuration */
133e18a033bSKonstantin Ananyev    NULL,                                  /* merge server configuration */
134e18a033bSKonstantin Ananyev
135e18a033bSKonstantin Ananyev    ngx_http_limit_req_create_conf,        /* create location configuration */
136e18a033bSKonstantin Ananyev    ngx_http_limit_req_merge_conf          /* merge location configuration */
137e18a033bSKonstantin Ananyev};
138e18a033bSKonstantin Ananyev
139e18a033bSKonstantin Ananyev
140e18a033bSKonstantin Ananyevngx_module_t  ngx_http_limit_req_module = {
141e18a033bSKonstantin Ananyev    NGX_MODULE_V1,
142e18a033bSKonstantin Ananyev    &ngx_http_limit_req_module_ctx,        /* module context */
143e18a033bSKonstantin Ananyev    ngx_http_limit_req_commands,           /* module directives */
144e18a033bSKonstantin Ananyev    NGX_HTTP_MODULE,                       /* module type */
145e18a033bSKonstantin Ananyev    NULL,                                  /* init master */
146e18a033bSKonstantin Ananyev    NULL,                                  /* init module */
147e18a033bSKonstantin Ananyev    NULL,                                  /* init process */
148e18a033bSKonstantin Ananyev    NULL,                                  /* init thread */
149e18a033bSKonstantin Ananyev    NULL,                                  /* exit thread */
150e18a033bSKonstantin Ananyev    NULL,                                  /* exit process */
151e18a033bSKonstantin Ananyev    NULL,                                  /* exit master */
152e18a033bSKonstantin Ananyev    NGX_MODULE_V1_PADDING
153e18a033bSKonstantin Ananyev};
154e18a033bSKonstantin Ananyev
155e18a033bSKonstantin Ananyev
156e18a033bSKonstantin Ananyevstatic ngx_int_t
157e18a033bSKonstantin Ananyevngx_http_limit_req_handler(ngx_http_request_t *r)
158e18a033bSKonstantin Ananyev{
159e18a033bSKonstantin Ananyev    uint32_t                     hash;
160e18a033bSKonstantin Ananyev    ngx_str_t                    key;
161e18a033bSKonstantin Ananyev    ngx_int_t                    rc;
162e18a033bSKonstantin Ananyev    ngx_uint_t                   n, excess;
163e18a033bSKonstantin Ananyev    ngx_msec_t                   delay;
164e18a033bSKonstantin Ananyev    ngx_http_limit_req_ctx_t    *ctx;
165e18a033bSKonstantin Ananyev    ngx_http_limit_req_conf_t   *lrcf;
166e18a033bSKonstantin Ananyev    ngx_http_limit_req_limit_t  *limit, *limits;
167e18a033bSKonstantin Ananyev
168e18a033bSKonstantin Ananyev    if (r->main->limit_req_set) {
169e18a033bSKonstantin Ananyev        return NGX_DECLINED;
170e18a033bSKonstantin Ananyev    }
171e18a033bSKonstantin Ananyev
172e18a033bSKonstantin Ananyev    lrcf = ngx_http_get_module_loc_conf(r, ngx_http_limit_req_module);
173e18a033bSKonstantin Ananyev    limits = lrcf->limits.elts;
174e18a033bSKonstantin Ananyev
175e18a033bSKonstantin Ananyev    excess = 0;
176e18a033bSKonstantin Ananyev
177e18a033bSKonstantin Ananyev    rc = NGX_DECLINED;
178e18a033bSKonstantin Ananyev
179e18a033bSKonstantin Ananyev#if (NGX_SUPPRESS_WARN)
180e18a033bSKonstantin Ananyev    limit = NULL;
181e18a033bSKonstantin Ananyev#endif
182e18a033bSKonstantin Ananyev
183e18a033bSKonstantin Ananyev    for (n = 0; n < lrcf->limits.nelts; n++) {
184e18a033bSKonstantin Ananyev
185e18a033bSKonstantin Ananyev        limit = &limits[n];
186e18a033bSKonstantin Ananyev
187e18a033bSKonstantin Ananyev        ctx = limit->shm_zone->data;
188e18a033bSKonstantin Ananyev
189e18a033bSKonstantin Ananyev        if (ngx_http_complex_value(r, &ctx->key, &key) != NGX_OK) {
190e18a033bSKonstantin Ananyev            return NGX_HTTP_INTERNAL_SERVER_ERROR;
191e18a033bSKonstantin Ananyev        }
192e18a033bSKonstantin Ananyev
193e18a033bSKonstantin Ananyev        if (key.len == 0) {
194e18a033bSKonstantin Ananyev            continue;
195e18a033bSKonstantin Ananyev        }
196e18a033bSKonstantin Ananyev
197e18a033bSKonstantin Ananyev        if (key.len > 65535) {
198e18a033bSKonstantin Ananyev            ngx_log_error(NGX_LOG_ERR, r->connection->log, 0,
199e18a033bSKonstantin Ananyev                          "the value of the \"%V\" key "
200e18a033bSKonstantin Ananyev                          "is more than 65535 bytes: \"%V\"",
201e18a033bSKonstantin Ananyev                          &ctx->key.value, &key);
202e18a033bSKonstantin Ananyev            continue;
203e18a033bSKonstantin Ananyev        }
204e18a033bSKonstantin Ananyev
205e18a033bSKonstantin Ananyev        hash = ngx_crc32_short(key.data, key.len);
206e18a033bSKonstantin Ananyev
207e18a033bSKonstantin Ananyev        ngx_shmtx_lock(&ctx->shpool->mutex);
208e18a033bSKonstantin Ananyev
209e18a033bSKonstantin Ananyev        rc = ngx_http_limit_req_lookup(limit, hash, &key, &excess,
210e18a033bSKonstantin Ananyev                                       (n == lrcf->limits.nelts - 1));
211e18a033bSKonstantin Ananyev
212e18a033bSKonstantin Ananyev        ngx_shmtx_unlock(&ctx->shpool->mutex);
213e18a033bSKonstantin Ananyev
214e18a033bSKonstantin Ananyev        ngx_log_debug4(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
215e18a033bSKonstantin Ananyev                       "limit_req[%ui]: %i %ui.%03ui",
216e18a033bSKonstantin Ananyev                       n, rc, excess / 1000, excess % 1000);
217e18a033bSKonstantin Ananyev
218e18a033bSKonstantin Ananyev        if (rc != NGX_AGAIN) {
219e18a033bSKonstantin Ananyev            break;
220e18a033bSKonstantin Ananyev        }
221e18a033bSKonstantin Ananyev    }
222e18a033bSKonstantin Ananyev
223e18a033bSKonstantin Ananyev    if (rc == NGX_DECLINED) {
224e18a033bSKonstantin Ananyev        return NGX_DECLINED;
225e18a033bSKonstantin Ananyev    }
226e18a033bSKonstantin Ananyev
227e18a033bSKonstantin Ananyev    r->main->limit_req_set = 1;
228e18a033bSKonstantin Ananyev
229e18a033bSKonstantin Ananyev    if (rc == NGX_BUSY || rc == NGX_ERROR) {
230e18a033bSKonstantin Ananyev
231e18a033bSKonstantin Ananyev        if (rc == NGX_BUSY) {
232e18a033bSKonstantin Ananyev            ngx_log_error(lrcf->limit_log_level, r->connection->log, 0,
233e18a033bSKonstantin Ananyev                          "limiting requests, excess: %ui.%03ui by zone \"%V\"",
234e18a033bSKonstantin Ananyev                          excess / 1000, excess % 1000,
235e18a033bSKonstantin Ananyev                          &limit->shm_zone->shm.name);
236e18a033bSKonstantin Ananyev        }
237e18a033bSKonstantin Ananyev
238e18a033bSKonstantin Ananyev        while (n--) {
239e18a033bSKonstantin Ananyev            ctx = limits[n].shm_zone->data;
240e18a033bSKonstantin Ananyev
241e18a033bSKonstantin Ananyev            if (ctx->node == NULL) {
242e18a033bSKonstantin Ananyev                continue;
243e18a033bSKonstantin Ananyev            }
244e18a033bSKonstantin Ananyev
245e18a033bSKonstantin Ananyev            ngx_shmtx_lock(&ctx->shpool->mutex);
246e18a033bSKonstantin Ananyev
247e18a033bSKonstantin Ananyev            ctx->node->count--;
248e18a033bSKonstantin Ananyev
249e18a033bSKonstantin Ananyev            ngx_shmtx_unlock(&ctx->shpool->mutex);
250e18a033bSKonstantin Ananyev
251e18a033bSKonstantin Ananyev            ctx->node = NULL;
252e18a033bSKonstantin Ananyev        }
253e18a033bSKonstantin Ananyev
254e18a033bSKonstantin Ananyev        return lrcf->status_code;
255e18a033bSKonstantin Ananyev    }
256e18a033bSKonstantin Ananyev
257e18a033bSKonstantin Ananyev    /* rc == NGX_AGAIN || rc == NGX_OK */
258e18a033bSKonstantin Ananyev
259e18a033bSKonstantin Ananyev    if (rc == NGX_AGAIN) {
260e18a033bSKonstantin Ananyev        excess = 0;
261e18a033bSKonstantin Ananyev    }
262e18a033bSKonstantin Ananyev
263e18a033bSKonstantin Ananyev    delay = ngx_http_limit_req_account(limits, n, &excess, &limit);
264e18a033bSKonstantin Ananyev
265e18a033bSKonstantin Ananyev    if (!delay) {
266e18a033bSKonstantin Ananyev        return NGX_DECLINED;
267e18a033bSKonstantin Ananyev    }
268e18a033bSKonstantin Ananyev
269e18a033bSKonstantin Ananyev    ngx_log_error(lrcf->delay_log_level, r->connection->log, 0,
270e18a033bSKonstantin Ananyev                  "delaying request, excess: %ui.%03ui, by zone \"%V\"",
271e18a033bSKonstantin Ananyev                  excess / 1000, excess % 1000, &limit->shm_zone->shm.name);
272e18a033bSKonstantin Ananyev
273e18a033bSKonstantin Ananyev    if (ngx_handle_read_event(r->connection->read, 0) != NGX_OK) {
274e18a033bSKonstantin Ananyev        return NGX_HTTP_INTERNAL_SERVER_ERROR;
275e18a033bSKonstantin Ananyev    }
276e18a033bSKonstantin Ananyev
277e18a033bSKonstantin Ananyev    r->read_event_handler = ngx_http_test_reading;
278e18a033bSKonstantin Ananyev    r->write_event_handler = ngx_http_limit_req_delay;
279e18a033bSKonstantin Ananyev
280e18a033bSKonstantin Ananyev    r->connection->write->delayed = 1;
281e18a033bSKonstantin Ananyev    ngx_add_timer(r->connection->write, delay);
282e18a033bSKonstantin Ananyev
283e18a033bSKonstantin Ananyev    return NGX_AGAIN;
284e18a033bSKonstantin Ananyev}
285e18a033bSKonstantin Ananyev
286e18a033bSKonstantin Ananyev
287e18a033bSKonstantin Ananyevstatic void
288e18a033bSKonstantin Ananyevngx_http_limit_req_delay(ngx_http_request_t *r)
289e18a033bSKonstantin Ananyev{
290e18a033bSKonstantin Ananyev    ngx_event_t  *wev;
291e18a033bSKonstantin Ananyev
292e18a033bSKonstantin Ananyev    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
293e18a033bSKonstantin Ananyev                   "limit_req delay");
294e18a033bSKonstantin Ananyev
295e18a033bSKonstantin Ananyev    wev = r->connection->write;
296e18a033bSKonstantin Ananyev
297e18a033bSKonstantin Ananyev    if (wev->delayed) {
298e18a033bSKonstantin Ananyev
299e18a033bSKonstantin Ananyev        if (ngx_handle_write_event(wev, 0) != NGX_OK) {
300e18a033bSKonstantin Ananyev            ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
301e18a033bSKonstantin Ananyev        }
302e18a033bSKonstantin Ananyev
303e18a033bSKonstantin Ananyev        return;
304e18a033bSKonstantin Ananyev    }
305e18a033bSKonstantin Ananyev
306e18a033bSKonstantin Ananyev    if (ngx_handle_read_event(r->connection->read, 0) != NGX_OK) {
307e18a033bSKonstantin Ananyev        ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
308e18a033bSKonstantin Ananyev        return;
309e18a033bSKonstantin Ananyev    }
310e18a033bSKonstantin Ananyev
311e18a033bSKonstantin Ananyev    r->read_event_handler = ngx_http_block_reading;
312e18a033bSKonstantin Ananyev    r->write_event_handler = ngx_http_core_run_phases;
313e18a033bSKonstantin Ananyev
314e18a033bSKonstantin Ananyev    ngx_http_core_run_phases(r);
315e18a033bSKonstantin Ananyev}
316e18a033bSKonstantin Ananyev
317e18a033bSKonstantin Ananyev
318e18a033bSKonstantin Ananyevstatic void
319e18a033bSKonstantin Ananyevngx_http_limit_req_rbtree_insert_value(ngx_rbtree_node_t *temp,
320e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
321e18a033bSKonstantin Ananyev{
322e18a033bSKonstantin Ananyev    ngx_rbtree_node_t          **p;
323e18a033bSKonstantin Ananyev    ngx_http_limit_req_node_t   *lrn, *lrnt;
324e18a033bSKonstantin Ananyev
325e18a033bSKonstantin Ananyev    for ( ;; ) {
326e18a033bSKonstantin Ananyev
327e18a033bSKonstantin Ananyev        if (node->key < temp->key) {
328e18a033bSKonstantin Ananyev
329e18a033bSKonstantin Ananyev            p = &temp->left;
330e18a033bSKonstantin Ananyev
331e18a033bSKonstantin Ananyev        } else if (node->key > temp->key) {
332e18a033bSKonstantin Ananyev
333e18a033bSKonstantin Ananyev            p = &temp->right;
334e18a033bSKonstantin Ananyev
335e18a033bSKonstantin Ananyev        } else { /* node->key == temp->key */
336e18a033bSKonstantin Ananyev
337e18a033bSKonstantin Ananyev            lrn = (ngx_http_limit_req_node_t *) &node->color;
338e18a033bSKonstantin Ananyev            lrnt = (ngx_http_limit_req_node_t *) &temp->color;
339e18a033bSKonstantin Ananyev
340e18a033bSKonstantin Ananyev            p = (ngx_memn2cmp(lrn->data, lrnt->data, lrn->len, lrnt->len) < 0)
341e18a033bSKonstantin Ananyev                ? &temp->left : &temp->right;
342e18a033bSKonstantin Ananyev        }
343e18a033bSKonstantin Ananyev
344e18a033bSKonstantin Ananyev        if (*p == sentinel) {
345e18a033bSKonstantin Ananyev            break;
346e18a033bSKonstantin Ananyev        }
347e18a033bSKonstantin Ananyev
348e18a033bSKonstantin Ananyev        temp = *p;
349e18a033bSKonstantin Ananyev    }
350e18a033bSKonstantin Ananyev
351e18a033bSKonstantin Ananyev    *p = node;
352e18a033bSKonstantin Ananyev    node->parent = temp;
353e18a033bSKonstantin Ananyev    node->left = sentinel;
354e18a033bSKonstantin Ananyev    node->right = sentinel;
355e18a033bSKonstantin Ananyev    ngx_rbt_red(node);
356e18a033bSKonstantin Ananyev}
357e18a033bSKonstantin Ananyev
358e18a033bSKonstantin Ananyev
359e18a033bSKonstantin Ananyevstatic ngx_int_t
360e18a033bSKonstantin Ananyevngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash,
361e18a033bSKonstantin Ananyev    ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account)
362e18a033bSKonstantin Ananyev{
363e18a033bSKonstantin Ananyev    size_t                      size;
364e18a033bSKonstantin Ananyev    ngx_int_t                   rc, excess;
365e18a033bSKonstantin Ananyev    ngx_msec_t                  now;
366e18a033bSKonstantin Ananyev    ngx_msec_int_t              ms;
367e18a033bSKonstantin Ananyev    ngx_rbtree_node_t          *node, *sentinel;
368e18a033bSKonstantin Ananyev    ngx_http_limit_req_ctx_t   *ctx;
369e18a033bSKonstantin Ananyev    ngx_http_limit_req_node_t  *lr;
370e18a033bSKonstantin Ananyev
371e18a033bSKonstantin Ananyev    now = ngx_current_msec;
372e18a033bSKonstantin Ananyev
373e18a033bSKonstantin Ananyev    ctx = limit->shm_zone->data;
374e18a033bSKonstantin Ananyev
375e18a033bSKonstantin Ananyev    node = ctx->sh->rbtree.root;
376e18a033bSKonstantin Ananyev    sentinel = ctx->sh->rbtree.sentinel;
377e18a033bSKonstantin Ananyev
378e18a033bSKonstantin Ananyev    while (node != sentinel) {
379e18a033bSKonstantin Ananyev
380e18a033bSKonstantin Ananyev        if (hash < node->key) {
381e18a033bSKonstantin Ananyev            node = node->left;
382e18a033bSKonstantin Ananyev            continue;
383e18a033bSKonstantin Ananyev        }
384e18a033bSKonstantin Ananyev
385e18a033bSKonstantin Ananyev        if (hash > node->key) {
386e18a033bSKonstantin Ananyev            node = node->right;
387e18a033bSKonstantin Ananyev            continue;
388e18a033bSKonstantin Ananyev        }
389e18a033bSKonstantin Ananyev
390e18a033bSKonstantin Ananyev        /* hash == node->key */
391e18a033bSKonstantin Ananyev
392e18a033bSKonstantin Ananyev        lr = (ngx_http_limit_req_node_t *) &node->color;
393e18a033bSKonstantin Ananyev
394e18a033bSKonstantin Ananyev        rc = ngx_memn2cmp(key->data, lr->data, key->len, (size_t) lr->len);
395e18a033bSKonstantin Ananyev
396e18a033bSKonstantin Ananyev        if (rc == 0) {
397e18a033bSKonstantin Ananyev            ngx_queue_remove(&lr->queue);
398e18a033bSKonstantin Ananyev            ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
399e18a033bSKonstantin Ananyev
400e18a033bSKonstantin Ananyev            ms = (ngx_msec_int_t) (now - lr->last);
401e18a033bSKonstantin Ananyev
402e18a033bSKonstantin Ananyev            excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
403e18a033bSKonstantin Ananyev
404e18a033bSKonstantin Ananyev            if (excess < 0) {
405e18a033bSKonstantin Ananyev                excess = 0;
406e18a033bSKonstantin Ananyev            }
407e18a033bSKonstantin Ananyev
408e18a033bSKonstantin Ananyev            *ep = excess;
409e18a033bSKonstantin Ananyev
410e18a033bSKonstantin Ananyev            if ((ngx_uint_t) excess > limit->burst) {
411e18a033bSKonstantin Ananyev                return NGX_BUSY;
412e18a033bSKonstantin Ananyev            }
413e18a033bSKonstantin Ananyev
414e18a033bSKonstantin Ananyev            if (account) {
415e18a033bSKonstantin Ananyev                lr->excess = excess;
416