Author: mdounin
Date: 2012-03-05 13:17:56 +0000 (Mon, 05 Mar 2012)
New Revision: 4516

Log:
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.


Modified:
branches/stable-1.0/
branches/stable-1.0/src/core/ngx_open_file_cache.c
branches/stable-1.0/src/core/ngx_resolver.c
branches/stable-1.0/src/event/ngx_event_openssl.c
branches/stable-1.0/src/http/modules/ngx_http_limit_req_module.c
branches/stable-1.0/src/http/modules/ngx_http_limit_zone_module.c
branches/stable-1.0/src/http/ngx_http_file_cache.c


Property changes on: branches/stable-1.0
___________________________________________________________________
Modified: svn:mergeinfo
- /trunk:3960-3974,3977-3987,3991-3996,3998,4000-4018,4020,4023,4025-4027,4034-4065,4073,4077,4086-4090,4094-4102,4106-4108,4113-4114,4129-4137,4143-4144,4147-4158,4177,4179,4182-4184,4186-4187,4189-4205,4207,4209-4210,4212,4217-4223,4227-4232,4235-4237,4265-4268,4270,4274-4276,4278-4280,4282-4284,4294-4295,4298,4300-4309,4313,4315,4320-4321,4326-4327,4335-4336,4338-4343,4372-4375,4377,4379,4381-4385,4393,4396,4398,4400-4406,4413,4415-4416,4422-4423,4460-4461,4468,4470-4471,4473-4474,4491-4493,4497
+ /trunk:3960-3974,3977-3987,3991-3996,3998,4000-4018,4020,4023,4025-4027,4034-4065,4073,4077,4086-4090,4094-4102,4106-4108,4113-4114,4129-4137,4143-4144,4147-4158,4177,4179,4182-4184,4186-4187,4189-4205,4207,4209-4210,4212,4217-4223,4227-4232,4235-4237,4265-4268,4270,4274-4276,4278-4280,4282-4284,4294-4295,4298,4300-4309,4313,4315,4320-4321,4326-4327,4335-4336,4338-4343,4372-4375,4377,4379,4381-4385,4393,4396,4398,4400-4406,4413,4415-4416,4422-4423,4460-4461,4468,4470-4471,4473-4474,4491-4493,4497-4498

Modified: branches/stable-1.0/src/core/ngx_open_file_cache.c
===================================================================
--- branches/stable-1.0/src/core/ngx_open_file_cache.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/core/ngx_open_file_cache.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -837,20 +837,15 @@

/* hash == node->key */

- do {
- file = (ngx_cached_open_file_t *) node;
+ file = (ngx_cached_open_file_t *) node;

- rc = ngx_strcmp(name->data, file->name);
+ rc = ngx_strcmp(name->data, file->name);

- if (rc == 0) {
- return file;
- }
+ if (rc == 0) {
+ return file;
+ }

- node = (rc < 0) ? node->left : node->right;
-
- } while (node != sentinel && hash == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

return NULL;

Modified: branches/stable-1.0/src/core/ngx_resolver.c
===================================================================
--- branches/stable-1.0/src/core/ngx_resolver.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/core/ngx_resolver.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -1626,20 +1626,15 @@

/* hash == node->key */

- do {
- rn = (ngx_resolver_node_t *) node;
+ rn = (ngx_resolver_node_t *) node;

- rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen);
+ rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen);

- if (rc == 0) {
- return rn;
- }
+ if (rc == 0) {
+ return rn;
+ }

- node = (rc < 0) ? node->left : node->right;
-
- } while (node != sentinel && hash == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

/* not found */

Modified: branches/stable-1.0/src/event/ngx_event_openssl.c
===================================================================
--- branches/stable-1.0/src/event/ngx_event_openssl.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/event/ngx_event_openssl.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -1801,44 +1801,39 @@

/* 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);

- ngx_queue_remove(&sess_id->queue);
+ return sess;
+ }

- ngx_rbtree_delete(&cache->session_rbtree, node);
+ ngx_queue_remove(&sess_id->queue);

- ngx_slab_free_locked(shpool, sess_id->session);
+ ngx_rbtree_delete(&cache->session_rbtree, node);
+
+ 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);
+ ngx_slab_free_locked(shpool, sess_id);

- sess = NULL;
+ sess = NULL;

- goto done;
- }
+ goto done;
+ }

- node = (rc < 0) ? node->left : node->right;
-
- } while (node != sentinel && hash == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

done:
@@ -1908,31 +1903,26 @@

/* 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);
+ ngx_slab_free_locked(shpool, sess_id);

- goto done;
- }
+ goto done;
+ }

- node = (rc < 0) ? node->left : node->right;
-
- } while (node != sentinel && hash == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

done:

Modified: branches/stable-1.0/src/http/modules/ngx_http_limit_req_module.c
===================================================================
--- branches/stable-1.0/src/http/modules/ngx_http_limit_req_module.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/http/modules/ngx_http_limit_req_module.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -372,47 +372,42 @@

/* 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;
- }
+ if (excess < 0) {
+ excess = 0;
+ }

- *ep = excess;
+ *ep = excess;

- if ((ngx_uint_t) excess > lrcf->burst) {
- return NGX_BUSY;
- }
+ if ((ngx_uint_t) excess > lrcf->burst) {
+ return NGX_BUSY;
+ }

- lr->excess = excess;
- lr->last = now;
+ lr->excess = excess;
+ lr->last = now;

- if (excess) {
- return NGX_AGAIN;
- }
-
- return NGX_OK;
+ if (excess) {
+ return NGX_AGAIN;
}

- node = (rc < 0) ? node->left : node->right;
+ return NGX_OK;
+ }

- } while (node != sentinel && hash == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

*ep = 0;

Modified: branches/stable-1.0/src/http/modules/ngx_http_limit_zone_module.c
===================================================================
--- branches/stable-1.0/src/http/modules/ngx_http_limit_zone_module.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/http/modules/ngx_http_limit_zone_module.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -194,31 +194,26 @@

/* 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);

- break;
+ return NGX_HTTP_SERVICE_UNAVAILABLE;
+ }
+
+ node = (rc < 0) ? node->left : node->right;
}

n = offsetof(ngx_rbtree_node_t, color)

Modified: branches/stable-1.0/src/http/ngx_http_file_cache.c
===================================================================
--- branches/stable-1.0/src/http/ngx_http_file_cache.c 2012-03-05 13:06:29 UTC (rev 4515)
+++ branches/stable-1.0/src/http/ngx_http_file_cache.c 2012-03-05 13:17:56 UTC (rev 4516)
@@ -673,21 +673,16 @@

/* 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;
- }
+ if (rc == 0) {
+ return fcn;
+ }

- node = (rc < 0) ? node->left : node->right;
-
- } while (node != sentinel && node_key == node->key);
-
- break;
+ node = (rc < 0) ? node->left : node->right;
}

/* not found */

_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel