Changeset 4497:95ab6658654a in nginx


Ignore:
Timestamp:
02/27/12 22:15:39 (8 years ago)
Author:
Maxim Dounin <mdounin@…>
Branch:
default
Phase:
public
Convert:
svn:c3fe7df1-7212-e011-8a91-001109144009/trunk@4498
Message:

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.

Location:
src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/core/ngx_open_file_cache.c

    r4493 r4497  
    11431143        /* hash == node->key */
    11441144
    1145         do {
    1146             file = (ngx_cached_open_file_t *) node;
    1147 
    1148             rc = ngx_strcmp(name->data, file->name);
    1149 
    1150             if (rc == 0) {
    1151                 return file;
    1152             }
    1153 
    1154             node = (rc < 0) ? node->left : node->right;
    1155 
    1156         } while (node != sentinel && hash == node->key);
    1157 
    1158         break;
     1145        file = (ngx_cached_open_file_t *) node;
     1146
     1147        rc = ngx_strcmp(name->data, file->name);
     1148
     1149        if (rc == 0) {
     1150            return file;
     1151        }
     1152
     1153        node = (rc < 0) ? node->left : node->right;
    11591154    }
    11601155
  • src/core/ngx_resolver.c

    r4496 r4497  
    16901690        /* hash == node->key */
    16911691
    1692         do {
    1693             rn = (ngx_resolver_node_t *) node;
    1694 
    1695             rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen);
    1696 
    1697             if (rc == 0) {
    1698                 return rn;
    1699             }
    1700 
    1701             node = (rc < 0) ? node->left : node->right;
    1702 
    1703         } while (node != sentinel && hash == node->key);
    1704 
    1705         break;
     1692        rn = (ngx_resolver_node_t *) node;
     1693
     1694        rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen);
     1695
     1696        if (rc == 0) {
     1697            return rn;
     1698        }
     1699
     1700        node = (rc < 0) ? node->left : node->right;
    17061701    }
    17071702
  • src/event/ngx_event_openssl.c

    r4414 r4497  
    18021802        /* hash == node->key */
    18031803
    1804         do {
    1805             sess_id = (ngx_ssl_sess_id_t *) node;
    1806 
    1807             rc = ngx_memn2cmp(id, sess_id->id,
    1808                               (size_t) len, (size_t) node->data);
    1809             if (rc == 0) {
    1810 
    1811                 if (sess_id->expire > ngx_time()) {
    1812                     ngx_memcpy(buf, sess_id->session, sess_id->len);
    1813 
    1814                     ngx_shmtx_unlock(&shpool->mutex);
    1815 
    1816                     p = buf;
    1817                     sess = d2i_SSL_SESSION(NULL, &p, sess_id->len);
    1818 
    1819                     return sess;
    1820                 }
    1821 
    1822                 ngx_queue_remove(&sess_id->queue);
    1823 
    1824                 ngx_rbtree_delete(&cache->session_rbtree, node);
    1825 
    1826                 ngx_slab_free_locked(shpool, sess_id->session);
     1804        sess_id = (ngx_ssl_sess_id_t *) node;
     1805
     1806        rc = ngx_memn2cmp(id, sess_id->id, (size_t) len, (size_t) node->data);
     1807
     1808        if (rc == 0) {
     1809
     1810            if (sess_id->expire > ngx_time()) {
     1811                ngx_memcpy(buf, sess_id->session, sess_id->len);
     1812
     1813                ngx_shmtx_unlock(&shpool->mutex);
     1814
     1815                p = buf;
     1816                sess = d2i_SSL_SESSION(NULL, &p, sess_id->len);
     1817
     1818                return sess;
     1819            }
     1820
     1821            ngx_queue_remove(&sess_id->queue);
     1822
     1823            ngx_rbtree_delete(&cache->session_rbtree, node);
     1824
     1825            ngx_slab_free_locked(shpool, sess_id->session);
    18271826#if (NGX_PTR_SIZE == 4)
    1828                 ngx_slab_free_locked(shpool, sess_id->id);
     1827            ngx_slab_free_locked(shpool, sess_id->id);
    18291828#endif
    1830                 ngx_slab_free_locked(shpool, sess_id);
    1831 
    1832                 sess = NULL;
    1833 
    1834                 goto done;
    1835             }
    1836 
    1837             node = (rc < 0) ? node->left : node->right;
    1838 
    1839         } while (node != sentinel && hash == node->key);
    1840 
    1841         break;
     1829            ngx_slab_free_locked(shpool, sess_id);
     1830
     1831            sess = NULL;
     1832
     1833            goto done;
     1834        }
     1835
     1836        node = (rc < 0) ? node->left : node->right;
    18421837    }
    18431838
     
    19091904        /* hash == node->key */
    19101905
    1911         do {
    1912             sess_id = (ngx_ssl_sess_id_t *) node;
    1913 
    1914             rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data);
    1915 
    1916             if (rc == 0) {
    1917 
    1918                 ngx_queue_remove(&sess_id->queue);
    1919 
    1920                 ngx_rbtree_delete(&cache->session_rbtree, node);
    1921 
    1922                 ngx_slab_free_locked(shpool, sess_id->session);
     1906        sess_id = (ngx_ssl_sess_id_t *) node;
     1907
     1908        rc = ngx_memn2cmp(id, sess_id->id, len, (size_t) node->data);
     1909
     1910        if (rc == 0) {
     1911
     1912            ngx_queue_remove(&sess_id->queue);
     1913
     1914            ngx_rbtree_delete(&cache->session_rbtree, node);
     1915
     1916            ngx_slab_free_locked(shpool, sess_id->session);
    19231917#if (NGX_PTR_SIZE == 4)
    1924                 ngx_slab_free_locked(shpool, sess_id->id);
     1918            ngx_slab_free_locked(shpool, sess_id->id);
    19251919#endif
    1926                 ngx_slab_free_locked(shpool, sess_id);
    1927 
    1928                 goto done;
    1929             }
    1930 
    1931             node = (rc < 0) ? node->left : node->right;
    1932 
    1933         } while (node != sentinel && hash == node->key);
    1934 
    1935         break;
     1920            ngx_slab_free_locked(shpool, sess_id);
     1921
     1922            goto done;
     1923        }
     1924
     1925        node = (rc < 0) ? node->left : node->right;
    19361926    }
    19371927
  • src/http/modules/ngx_http_limit_conn_module.c

    r4458 r4497  
    326326        /* hash == node->key */
    327327
    328         do {
    329             lcn = (ngx_http_limit_conn_node_t *) &node->color;
    330 
    331             rc = ngx_memn2cmp(vv->data, lcn->data,
    332                               (size_t) vv->len, (size_t) lcn->len);
    333             if (rc == 0) {
    334                 return node;
    335             }
    336 
    337             node = (rc < 0) ? node->left : node->right;
    338 
    339         } while (node != sentinel && hash == node->key);
    340 
    341         break;
     328        lcn = (ngx_http_limit_conn_node_t *) &node->color;
     329
     330        rc = ngx_memn2cmp(vv->data, lcn->data,
     331                          (size_t) vv->len, (size_t) lcn->len);
     332        if (rc == 0) {
     333            return node;
     334        }
     335
     336        node = (rc < 0) ? node->left : node->right;
    342337    }
    343338
  • src/http/modules/ngx_http_limit_req_module.c

    r4424 r4497  
    386386        /* hash == node->key */
    387387
    388         do {
    389             lr = (ngx_http_limit_req_node_t *) &node->color;
    390 
    391             rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);
    392 
    393             if (rc == 0) {
    394                 ngx_queue_remove(&lr->queue);
    395                 ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
    396 
    397                 ms = (ngx_msec_int_t) (now - lr->last);
    398 
    399                 excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
    400 
    401                 if (excess < 0) {
    402                     excess = 0;
    403                 }
    404 
    405                 *ep = excess;
    406 
    407                 if ((ngx_uint_t) excess > limit->burst) {
    408                     return NGX_BUSY;
    409                 }
    410 
    411                 if (account) {
    412                     lr->excess = excess;
    413                     lr->last = now;
    414                     return NGX_OK;
    415                 }
    416 
    417                 lr->count++;
    418 
    419                 ctx->node = lr;
    420 
    421                 return NGX_AGAIN;
    422             }
    423 
    424             node = (rc < 0) ? node->left : node->right;
    425 
    426         } while (node != sentinel && hash == node->key);
    427 
    428         break;
     388        lr = (ngx_http_limit_req_node_t *) &node->color;
     389
     390        rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);
     391
     392        if (rc == 0) {
     393            ngx_queue_remove(&lr->queue);
     394            ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
     395
     396            ms = (ngx_msec_int_t) (now - lr->last);
     397
     398            excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
     399
     400            if (excess < 0) {
     401                excess = 0;
     402            }
     403
     404            *ep = excess;
     405
     406            if ((ngx_uint_t) excess > limit->burst) {
     407                return NGX_BUSY;
     408            }
     409
     410            if (account) {
     411                lr->excess = excess;
     412                lr->last = now;
     413                return NGX_OK;
     414            }
     415
     416            lr->count++;
     417
     418            ctx->node = lr;
     419
     420            return NGX_AGAIN;
     421        }
     422
     423        node = (rc < 0) ? node->left : node->right;
    429424    }
    430425
  • src/http/ngx_http_file_cache.c

    r4474 r4497  
    800800        /* node_key == node->key */
    801801
    802         do {
    803             fcn = (ngx_http_file_cache_node_t *) node;
    804 
    805             rc = ngx_memcmp(&key[sizeof(ngx_rbtree_key_t)], fcn->key,
    806                             NGX_HTTP_CACHE_KEY_LEN - sizeof(ngx_rbtree_key_t));
    807 
    808             if (rc == 0) {
    809                 return fcn;
    810             }
    811 
    812             node = (rc < 0) ? node->left : node->right;
    813 
    814         } while (node != sentinel && node_key == node->key);
    815 
    816         break;
     802        fcn = (ngx_http_file_cache_node_t *) node;
     803
     804        rc = ngx_memcmp(&key[sizeof(ngx_rbtree_key_t)], fcn->key,
     805                        NGX_HTTP_CACHE_KEY_LEN - sizeof(ngx_rbtree_key_t));
     806
     807        if (rc == 0) {
     808            return fcn;
     809        }
     810
     811        node = (rc < 0) ? node->left : node->right;
    817812    }
    818813
Note: See TracChangeset for help on using the changeset viewer.