Mercurial > hg > nginx
changeset 2027:f321b59ae0e9
locations tree
| author | Igor Sysoev <igor@sysoev.ru> |
|---|---|
| date | Sat, 24 May 2008 14:14:13 +0000 |
| parents | 72db8932f782 |
| children | bff8689c6953 |
| files | src/http/modules/ngx_http_rewrite_module.c src/http/ngx_http.c src/http/ngx_http.h src/http/ngx_http_core_module.c src/http/ngx_http_core_module.h |
| diffstat | 5 files changed, 773 insertions(+), 412 deletions(-) [+] |
line wrap: on
line diff
--- a/src/http/modules/ngx_http_rewrite_module.c +++ b/src/http/modules/ngx_http_rewrite_module.c @@ -524,7 +524,7 @@ ngx_http_rewrite_if(ngx_conf_t *cf, ngx_ ngx_conf_t save; ngx_http_module_t *module; ngx_http_conf_ctx_t *ctx, *pctx; - ngx_http_core_loc_conf_t *clcf, *pclcf, **clcfp; + ngx_http_core_loc_conf_t *clcf, *pclcf; ngx_http_script_if_code_t *if_code; ngx_http_rewrite_loc_conf_t *nlcf; @@ -567,21 +567,10 @@ ngx_http_rewrite_if(ngx_conf_t *cf, ngx_ clcf->name = pclcf->name; clcf->noname = 1; - if (pclcf->locations == NULL) { - pclcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *)); - if (pclcf->locations == NULL) { - return NGX_CONF_ERROR; - } - } - - clcfp = ngx_array_push(pclcf->locations); - if (clcfp == NULL) { + if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) { return NGX_CONF_ERROR; } - *clcfp = clcf; - - if (ngx_http_rewrite_if_condition(cf, lcf) != NGX_CONF_OK) { return NGX_CONF_ERROR; }
--- a/src/http/ngx_http.c +++ b/src/http/ngx_http.c @@ -27,8 +27,21 @@ static ngx_int_t ngx_http_add_names(ngx_ ngx_http_core_srv_conf_t *cscf, ngx_http_conf_in_addr_t *in_addr); static char *ngx_http_merge_locations(ngx_conf_t *cf, - ngx_array_t *locations, void **loc_conf, ngx_http_module_t *module, + ngx_queue_t *locations, void **loc_conf, ngx_http_module_t *module, ngx_uint_t ctx_index); +static ngx_int_t ngx_http_init_locations(ngx_conf_t *cf, + ngx_http_core_srv_conf_t *cscf, ngx_http_core_loc_conf_t *pclcf); +static ngx_int_t ngx_http_init_static_location_trees(ngx_conf_t *cf, + ngx_http_core_loc_conf_t *pclcf); +static ngx_int_t ngx_http_cmp_locations(const ngx_queue_t *one, + const ngx_queue_t *two); +static ngx_int_t ngx_http_join_exact_locations(ngx_conf_t *cf, + ngx_queue_t *locations); +static void ngx_http_create_locations_list(ngx_queue_t *locations, + ngx_queue_t *q); +static ngx_http_location_tree_node_t * + ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations, + size_t prefix); static ngx_int_t ngx_http_optimize_servers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, ngx_array_t *in_ports); @@ -91,6 +104,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma ngx_array_t in_ports; ngx_http_module_t *module; ngx_http_conf_ctx_t *ctx; + ngx_http_core_loc_conf_t *clcf; ngx_http_core_srv_conf_t **cscfp; ngx_http_core_main_conf_t *cmcf; @@ -206,8 +220,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma rv = ngx_conf_parse(cf, NULL); if (rv != NGX_CONF_OK) { - *cf = pcf; - return rv; + goto failed; } /* @@ -231,8 +244,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma if (module->init_main_conf) { rv = module->init_main_conf(cf, ctx->main_conf[mi]); if (rv != NGX_CONF_OK) { - *cf = pcf; - return rv; + goto failed; } } @@ -241,12 +253,10 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma /* merge the server{}s' srv_conf's */ if (module->merge_srv_conf) { - rv = module->merge_srv_conf(cf, - ctx->srv_conf[mi], + rv = module->merge_srv_conf(cf, ctx->srv_conf[mi], cscfp[s]->ctx->srv_conf[mi]); if (rv != NGX_CONF_OK) { - *cf = pcf; - return rv; + goto failed; } } @@ -254,28 +264,43 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma /* merge the server{}'s loc_conf */ - rv = module->merge_loc_conf(cf, - ctx->loc_conf[mi], + rv = module->merge_loc_conf(cf, ctx->loc_conf[mi], cscfp[s]->ctx->loc_conf[mi]); if (rv != NGX_CONF_OK) { - *cf = pcf; - return rv; + goto failed; } /* merge the locations{}' loc_conf's */ - rv = ngx_http_merge_locations(cf, &cscfp[s]->locations, + clcf = cscfp[s]->ctx->loc_conf[ngx_http_core_module.ctx_index]; + + rv = ngx_http_merge_locations(cf, clcf->locations, cscfp[s]->ctx->loc_conf, module, mi); if (rv != NGX_CONF_OK) { - *cf = pcf; - return rv; + goto failed; } } } } + /* create location trees */ + + for (s = 0; s < cmcf->servers.nelts; s++) { + + clcf = cscfp[s]->ctx->loc_conf[ngx_http_core_module.ctx_index]; + + if (ngx_http_init_locations(cf, cscfp[s], clcf) != NGX_OK) { + return NGX_CONF_ERROR; + } + + if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) { + return NGX_CONF_ERROR; + } + } + + if (ngx_http_init_phases(cf, cmcf) != NGX_OK) { return NGX_CONF_ERROR; } @@ -337,6 +362,12 @@ ngx_http_block(ngx_conf_t *cf, ngx_comma } return NGX_CONF_OK; + +failed: + + *cf = pcf; + + return rv; } @@ -544,6 +575,511 @@ ngx_http_init_phase_handlers(ngx_conf_t } +static char * +ngx_http_merge_locations(ngx_conf_t *cf, ngx_queue_t *locations, + void **loc_conf, ngx_http_module_t *module, ngx_uint_t ctx_index) +{ + char *rv; + ngx_queue_t *q; + ngx_http_core_loc_conf_t *clcf; + ngx_http_location_queue_t *lq; + + if (locations == NULL) { + return NGX_CONF_OK; + } + + for (q = ngx_queue_head(locations); + q != ngx_queue_sentinel(locations); + q = ngx_queue_next(q)) + { + lq = (ngx_http_location_queue_t *) q; + + clcf = lq->exact ? lq->exact : lq->inclusive; + + rv = module->merge_loc_conf(cf, loc_conf[ctx_index], + clcf->loc_conf[ctx_index]); + if (rv != NGX_CONF_OK) { + return rv; + } + + rv = ngx_http_merge_locations(cf, clcf->locations, clcf->loc_conf, + module, ctx_index); + if (rv != NGX_CONF_OK) { + return rv; + } + } + + return NGX_CONF_OK; +} + + +static ngx_int_t +ngx_http_init_locations(ngx_conf_t *cf, ngx_http_core_srv_conf_t *cscf, + ngx_http_core_loc_conf_t *pclcf) +{ + ngx_uint_t n; + ngx_queue_t *q, *locations, *named, tail; + ngx_http_core_loc_conf_t *clcf; + ngx_http_location_queue_t *lq; + ngx_http_core_loc_conf_t **clcfp; +#if (NGX_PCRE) + ngx_uint_t r; + ngx_queue_t *regex; +#endif + + locations = pclcf->locations; + + if (locations == NULL) { + return NGX_OK; + } + + ngx_queue_sort(locations, ngx_http_cmp_locations); + + named = NULL; + n = 0; +#if (NGX_PCRE) + regex = NULL; + r = 0; +#endif + + for (q = ngx_queue_head(locations); + q != ngx_queue_sentinel(locations); + q = ngx_queue_next(q)) + { + lq = (ngx_http_location_queue_t *) q; + + clcf = lq->exact ? lq->exact : lq->inclusive; + + if (ngx_http_init_locations(cf, NULL, clcf) != NGX_OK) { + return NGX_ERROR; + } + +#if (NGX_PCRE) + + if (clcf->regex) { + r++; + + if (regex == NULL) { + regex = q; + } + + continue; + } + +#endif + + if (clcf->named) { + n++; + + if (named == NULL) { + named = q; + } + + continue; + } + + if (clcf->noname) { + break; + } + } + + if (q != ngx_queue_sentinel(locations)) { + ngx_queue_split(locations, q, &tail); + } + + if (named) { + clcfp = ngx_palloc(cf->pool, + (n + 1) * sizeof(ngx_http_core_loc_conf_t **)); + if (clcfp == NULL) { + return NGX_ERROR; + } + + cscf->named_locations = clcfp; + + for (q = named; + q != ngx_queue_sentinel(locations); + q = ngx_queue_next(q)) + { + lq = (ngx_http_location_queue_t *) q; + + *(clcfp++) = lq->exact; + } + + *clcfp = NULL; + + ngx_queue_split(locations, named, &tail); + } + +#if (NGX_PCRE) + + if (regex) { + + clcfp = ngx_palloc(cf->pool, + (r + 1) * sizeof(ngx_http_core_loc_conf_t **)); + if (clcfp == NULL) { + return NGX_ERROR; + } + + pclcf->regex_locations = clcfp; + + for (q = regex; + q != ngx_queue_sentinel(locations); + q = ngx_queue_next(q)) + { + lq = (ngx_http_location_queue_t *) q; + + *(clcfp++) = lq->exact; + } + + *clcfp = NULL; + + ngx_queue_split(locations, regex, &tail); + } + +#endif + + return NGX_OK; +} + + +static ngx_int_t +ngx_http_init_static_location_trees(ngx_conf_t *cf, + ngx_http_core_loc_conf_t *pclcf) +{ + ngx_queue_t *q, *locations; + ngx_http_core_loc_conf_t *clcf; + ngx_http_location_queue_t *lq; + + locations = pclcf->locations; + + if (locations == NULL) { + return NGX_OK; + } + + if (ngx_queue_empty(locations)) { + return NGX_OK; + } + + for (q = ngx_queue_head(locations); + q != ngx_queue_sentinel(locations); + q = ngx_queue_next(q)) + { + lq = (ngx_http_location_queue_t *) q; + + clcf = lq->exact ? lq->exact : lq->inclusive; + + if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) { + return NGX_ERROR; + } + } + + if (ngx_http_join_exact_locations(cf, locations) != NGX_OK) { + return NGX_ERROR; + } + + ngx_http_create_locations_list(locations, ngx_queue_head(locations)); + + pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0); + if (pclcf->static_locations == NULL) { + return NGX_ERROR; + } + + return NGX_OK; +} + + +ngx_int_t +ngx_http_add_location(ngx_conf_t *cf, ngx_queue_t **locations, + ngx_http_core_loc_conf_t *clcf) +{ + ngx_http_location_queue_t *lq; + + if (*locations == NULL) { + *locations = ngx_palloc(cf->temp_pool, + sizeof(ngx_http_location_queue_t)); + if (*locations == NULL) { + return NGX_ERROR; + } + + ngx_queue_init(*locations); + } + + lq = ngx_palloc(cf->temp_pool, sizeof(ngx_http_location_queue_t)); + if (lq == NULL) { + return NGX_ERROR; + } + + if (clcf->exact_match +#if (NGX_PCRE) + || clcf->regex +#endif + || clcf->named || clcf->noname) + { + lq->exact = clcf; + lq->inclusive = NULL; + + } else { + lq->exact = NULL; + lq->inclusive = clcf; + } + + lq->name = &clcf->name; + lq->file_name = cf->conf_file->file.name.data; + lq->line = cf->conf_file->line; + + ngx_queue_init(&lq->list); + + ngx_queue_insert_tail(*locations, &lq->queue); + + return NGX_OK; +} + + +static ngx_int_t +ngx_http_cmp_locations(const ngx_queue_t *one, const ngx_queue_t *two) +{ + ngx_int_t rc; + ngx_http_core_loc_conf_t *first, *second; + ngx_http_location_queue_t *lq1, *lq2; + + lq1 = (ngx_http_location_queue_t *) one; + lq2 = (ngx_http_location_queue_t *) two; + + first = lq1->exact ? lq1->exact : lq1->inclusive; + second = lq2->exact ? lq2->exact : lq2->inclusive; + + if (first->noname && !second->noname) { + /* shift no named locations to the end */ + return 1; + } + + if (!first->noname && second->noname) { + /* shift no named locations to the end */ + return -1; + } + + if (first->noname || second->noname) { + /* do not sort no named locations */ + return 0; + } + + if (first->named && !second->named) { + /* shift named locations to the end */ + return 1; + } + + if (!first->named && second->named) { + /* shift named locations to the end */ + return -1; + } + + if (first->named && second->named) { + return ngx_strcmp(first->name.data, second->name.data); + } + +#if (NGX_PCRE) + + if (first->regex && !second->regex) { + /* shift the regex matches to the end */ + return 1; + } + + if (!first->regex && second->regex) { + /* shift the regex matches to the end */ + return -1; + } + + if (first->regex || second->regex) { + /* do not sort the regex matches */ + return 0; + } + +#endif + + rc = ngx_strcmp(first->name.data, second->name.data); + + if (rc == 0 && !first->exact_match && second->exact_match) { + /* an exact match must be before the same inclusive one */ + return 1; + } + + return rc; +} + + +static ngx_int_t +ngx_http_join_exact_locations(ngx_conf_t *cf, ngx_queue_t *locations) +{ + ngx_queue_t *q, *x; + ngx_http_location_queue_t *lq, *lx; + + q = ngx_queue_head(locations); + + while (q != ngx_queue_last(locations)) { + + x = ngx_queue_next(q); + + lq = (ngx_http_location_queue_t *) q; + lx = (ngx_http_location_queue_t *) x; + + if (ngx_strcmp(lq->name->data, lx->name->data) == 0) { + + if ((lq->exact && lx->exact) || (lq->inclusive && lx->inclusive)) { + ngx_log_error(NGX_LOG_EMERG, cf->log, 0, + "duplicate location \"%V\" in %s:%ui", + lx->name, lx->file_name, lx->line); + + return NGX_ERROR; + } + + lq->inclusive = lx->inclusive; + + ngx_queue_remove(x); + + continue; + } + + q = ngx_queue_next(q); + } + + return NGX_OK; +} + + +static void +ngx_http_create_locations_list(ngx_queue_t *locations, ngx_queue_t *q) +{ + u_char *name; + size_t len; + ngx_queue_t *x, tail; + ngx_http_location_queue_t *lq, *lx; + + if (q == ngx_queue_last(locations)) { + return; + } + + lq = (ngx_http_location_queue_t *) q; + + if (lq->inclusive == NULL) { + ngx_http_create_locations_list(locations, ngx_queue_next(q)); + return; + } + + len = lq->name->len; + name = lq->name->data; + + for (x = ngx_queue_next(q); + x != ngx_queue_sentinel(locations); + x = ngx_queue_next(x)) + { + lx = (ngx_http_location_queue_t *) x; + + if (len > lx->name->len + || (ngx_strncmp(name, lx->name->data, len) != 0)) + { + break; + } + } + + q = ngx_queue_next(q); + + if (q == x) { + ngx_http_create_locations_list(locations, x); + return; + } + + ngx_queue_split(locations, q, &tail); + ngx_queue_add(&lq->list, &tail); + + if (x == ngx_queue_sentinel(locations)) { + ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list)); + return; + } + + ngx_queue_split(&lq->list, x, &tail); + ngx_queue_add(locations, &tail); + + ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list)); + + ngx_http_create_locations_list(locations, x); +} + + +/* + * to keep cache locality for left leaf nodes, allocate nodes in following + * order: node, left subtree, right subtree, inclusive subtree + */ + +static ngx_http_location_tree_node_t * +ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations, + size_t prefix) +{ + size_t len; + ngx_queue_t *q, tail; + ngx_http_location_queue_t *lq; + ngx_http_location_tree_node_t *node; + + q = ngx_queue_middle(locations); + + lq = (ngx_http_location_queue_t *) q; + len = lq->name->len - prefix; + + node = ngx_pcalloc(cf->pool, + offsetof(ngx_http_location_tree_node_t, name) + len); + if (node == NULL) { + return NULL; + } + + node->exact = lq->exact; + node->inclusive = lq->inclusive; + + node->auto_redirect = (u_char) ((lq->exact && lq->exact->auto_redirect) + || (lq->inclusive && lq->inclusive->auto_redirect)); + + node->len = (u_char) len; + ngx_memcpy(node->name, &lq->name->data[prefix], len); + + ngx_queue_split(locations, q, &tail); + + if (ngx_queue_empty(locations)) { + /* + * ngx_queue_split() insures that if left part is empty, + * then right one is empty too + */ + goto inclusive; + } + + node->left = ngx_http_create_locations_tree(cf, locations, prefix); + if (node->left == NULL) { + return NULL; + } + + ngx_queue_remove(q); + + if (ngx_queue_empty(&tail)) { + goto inclusive; + } + + node->right = ngx_http_create_locations_tree(cf, &tail, prefix); + if (node->right == NULL) { + return NULL; + } + +inclusive: + + if (ngx_queue_empty(&lq->list)) { + return node; + } + + node->tree = ngx_http_create_locations_tree(cf, &lq->list, prefix + len); + if (node->tree == NULL) { + return NULL; + } + + return node; +} + + static ngx_int_t ngx_http_init_server_lists(ngx_conf_t *cf, ngx_array_t *servers, ngx_array_t *in_ports) @@ -756,38 +1292,6 @@ ngx_http_add_names(ngx_conf_t *cf, ngx_h } -static char * -ngx_http_merge_locations(ngx_conf_t *cf, ngx_array_t *locations, - void **loc_conf, ngx_http_module_t *module, ngx_uint_t ctx_index) -{ - char *rv; - ngx_uint_t i; - ngx_http_core_loc_conf_t **clcfp; - - clcfp = locations->elts; - - for (i = 0; i < locations->nelts; i++) { - rv = module->merge_loc_conf(cf, loc_conf[ctx_index], - clcfp[i]->loc_conf[ctx_index]); - if (rv != NGX_CONF_OK) { - return rv; - } - - if (clcfp[i]->locations == NULL) { - continue; - } - - rv = ngx_http_merge_locations(cf, clcfp[i]->locations, - clcfp[i]->loc_conf, module, ctx_index); - if (rv != NGX_CONF_OK) { - return rv; - } - } - - return NGX_CONF_OK; -} - - static ngx_int_t ngx_http_optimize_servers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf, ngx_array_t *in_ports)
--- a/src/http/ngx_http.h +++ b/src/http/ngx_http.h @@ -57,6 +57,10 @@ struct ngx_http_log_ctx_s { #define ngx_http_set_ctx(r, c, module) r->ctx[module.ctx_index] = c; +ngx_int_t ngx_http_add_location(ngx_conf_t *cf, ngx_queue_t **locations, + ngx_http_core_loc_conf_t *clcf); + + void ngx_http_init_connection(ngx_connection_t *c); #ifdef SSL_CTRL_SET_TLSEXT_HOSTNAME
--- a/src/http/ngx_http_core_module.c +++ b/src/http/ngx_http_core_module.c @@ -17,19 +17,14 @@ typedef struct { } ngx_http_method_name_t; -#define NGX_HTTP_LOCATION_EXACT 1 -#define NGX_HTTP_LOCATION_AUTO_REDIRECT 2 -#define NGX_HTTP_LOCATION_NOREGEX 3 -#define NGX_HTTP_LOCATION_REGEX 4 - - #define NGX_HTTP_REQUEST_BODY_FILE_OFF 0 #define NGX_HTTP_REQUEST_BODY_FILE_ON 1 #define NGX_HTTP_REQUEST_BODY_FILE_CLEAN 2 -static ngx_int_t ngx_http_core_find_location(ngx_http_request_t *r, - ngx_array_t *locations, ngx_uint_t regex_start, size_t len); +static ngx_int_t ngx_http_core_find_location(ngx_http_request_t *r); +static ngx_int_t ngx_http_core_find_static_location(ngx_http_request_t *r, + ngx_http_location_tree_node_t *node); static ngx_int_t ngx_http_core_preconfiguration(ngx_conf_t *cf); static void *ngx_http_core_create_main_conf(ngx_conf_t *cf); @@ -45,8 +40,6 @@ static char *ngx_http_core_server(ngx_co void *dummy); static char *ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy); -static ngx_int_t ngx_http_core_cmp_locations(const void *first, - const void *second); static char *ngx_http_core_types(ngx_conf_t *cf, ngx_command_t *cmd, void *conf); @@ -787,14 +780,11 @@ ngx_http_core_find_config_phase(ngx_http size_t len; ngx_int_t rc; ngx_http_core_loc_conf_t *clcf; - ngx_http_core_srv_conf_t *cscf; r->content_handler = NULL; r->uri_changed = 0; - cscf = ngx_http_get_module_srv_conf(r, ngx_http_core_module); - - rc = ngx_http_core_find_location(r, &cscf->locations, cscf->regex_start, 0); + rc = ngx_http_core_find_location(r); if (rc == NGX_HTTP_INTERNAL_SERVER_ERROR) { ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR); @@ -832,8 +822,7 @@ ngx_http_core_find_config_phase(ngx_http return NGX_OK; } - - if (rc == NGX_HTTP_LOCATION_AUTO_REDIRECT) { + if (rc == NGX_DONE) { r->headers_out.location = ngx_list_push(&r->headers_out.headers); if (r->headers_out.location == NULL) { ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR); @@ -1112,143 +1101,148 @@ ngx_http_update_location_config(ngx_http static ngx_int_t -ngx_http_core_find_location(ngx_http_request_t *r, - ngx_array_t *locations, ngx_uint_t regex_start, size_t len) +ngx_http_core_find_location(ngx_http_request_t *r) { - ngx_int_t n, rc; - ngx_uint_t i, found; + ngx_int_t rc; + ngx_http_core_loc_conf_t *pclcf; + + pclcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module); + + rc = ngx_http_core_find_static_location(r, pclcf->static_locations); + + if (rc == NGX_AGAIN) { + /* look up nested locations */ + rc = ngx_http_core_find_location(r); + } + + if (rc == NGX_OK || rc == NGX_DONE) { + return rc; + } + + /* rc == NGX_DECLINED or rc == NGX_AGAIN in nested location */ + +#if (NGX_PCRE) + { + ngx_int_t n; ngx_http_core_loc_conf_t *clcf, **clcfp; -#if (NGX_PCRE) - ngx_uint_t noregex; + + clcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module); + + if (clcf->noregex == 0 && pclcf->regex_locations) { + + for (clcfp = pclcf->regex_locations; *clcfp; clcfp++) { + + ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, + "test location: ~ \"%V\"", &(*clcfp)->name); + + n = ngx_regex_exec((*clcfp)->regex, &r->uri, NULL, 0); + + if (n == NGX_REGEX_NO_MATCHED) { + continue; + } + + if (n < 0) { + ngx_log_error(NGX_LOG_ALERT, r->connection->log, 0, + ngx_regex_exec_n + " failed: %d on \"%V\" using \"%V\"", + n, &r->uri, &(*clcfp)->name); + return NGX_HTTP_INTERNAL_SERVER_ERROR; + } + + /* match */ + + r->loc_conf = (*clcfp)->loc_conf; + + /* look up nested locations */ + + return ngx_http_core_find_location(r); + } + } + } #endif - ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, - "find location for \"%V\"", &r->uri); - - found = 0; -#if (NGX_PCRE) - noregex = 0; -#endif - - clcfp = locations->elts; - for (i = 0; i < locations->nelts; i++) { - - if (clcfp[i]->noname -#if (NGX_PCRE) - || clcfp[i]->regex -#endif - || clcfp[i]->named) - { - break; + return rc; +} + + +/* + * NGX_OK - exact match + * NGX_DONE - auto redirect + * NGX_AGAIN - inclusive match + * NGX_DECLINED - no match + */ + +static ngx_int_t +ngx_http_core_find_static_location(ngx_http_request_t *r, + ngx_http_location_tree_node_t *node) +{ + u_char *uri; + size_t len, n; + ngx_int_t rc, rv; + + len = r->uri.len; + uri = r->uri.data; + + rv = NGX_DECLINED; + + for ( ;; ) { + + if (node == NULL) { + return rv; } ngx_log_debug2(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, - "find location: %s\"%V\"", - clcfp[i]->exact_match ? "= " : "", &clcfp[i]->name); - - if (clcfp[i]->auto_redirect - && r->uri.len == clcfp[i]->name.len - 1 - && ngx_strncmp(r->uri.data, clcfp[i]->name.data, - clcfp[i]->name.len - 1) - == 0) - { - /* the locations are lexicographically sorted */ - - r->loc_conf = clcfp[i]->loc_conf; - - return NGX_HTTP_LOCATION_AUTO_REDIRECT; - } - - if (r->uri.len < clcfp[i]->name.len) { + "test location: \"%*s\"", node->len, node->name); + + n = (len <= (size_t) node->len) ? len : node->len; + + rc = ngx_memcmp(uri, node->name, n); + + if (rc != 0) { + node = (rc < 0) ? node->left : node->right; + continue; } - n = ngx_strncmp(r->uri.data, clcfp[i]->name.data, clcfp[i]->name.len); - - if (n < 0) { - /* the locations are lexicographically sorted */ - break; - } - - if (n == 0) { - if (clcfp[i]->exact_match) { - - if (r->uri.len == clcfp[i]->name.len) { - r->loc_conf = clcfp[i]->loc_conf; - return NGX_HTTP_LOCATION_EXACT; - } + if (len > (size_t) node->len) { + + if (node->inclusive) { + + r->loc_conf = node->inclusive->loc_conf; + rv = NGX_AGAIN; + + node = node->tree; + uri += n; + len -= n; continue; } - if (len > clcfp[i]->name.len) { - /* the previous match is longer */ - break; - } - - found = 1; - - r->loc_conf = clcfp[i]->loc_conf; -#if (NGX_PCRE) - noregex = clcfp[i]->noregex; -#endif - } - } - - if (found) { - clcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module); - - if (clcf->locations) { - rc = ngx_http_core_find_location(r, clcf->locations, - clcf->regex_start, len); - - if (rc != NGX_OK) { - return rc; - } - } - } - -#if (NGX_PCRE) - - if (noregex) { - return NGX_HTTP_LOCATION_NOREGEX; - } - - /* regex matches */ - - for (i = regex_start; i < locations->nelts; i++) { - - if (!clcfp[i]->regex) { - break; - } - - ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, - "find location: ~ \"%V\"", &clcfp[i]->name); - - n = ngx_regex_exec(clcfp[i]->regex, &r->uri, NULL, 0); - - if (n == NGX_REGEX_NO_MATCHED) { + /* exact only */ + + node = node->right; + continue; } - if (n < 0) { - ngx_log_error(NGX_LOG_ALERT, r->connection->log, 0, - ngx_regex_exec_n - " failed: %d on \"%V\" using \"%V\"", - n, &r->uri, &clcfp[i]->name); - return NGX_HTTP_INTERNAL_SERVER_ERROR; + if (len == (size_t) node->len) { + + r->loc_conf = (node->exact) ? node->exact->loc_conf: + node->inclusive->loc_conf; + return NGX_OK; } - /* match */ - - r->loc_conf = clcfp[i]->loc_conf; - - return NGX_HTTP_LOCATION_REGEX; + /* len < node->len */ + + if (len + 1 == (size_t) node->len && node->auto_redirect) { + + r->loc_conf = (node->exact) ? node->exact->loc_conf: + node->inclusive->loc_conf; + rv = NGX_DONE; + } + + node = node->left; } - -#endif /* NGX_PCRE */ - - return NGX_OK; } @@ -1896,29 +1890,29 @@ ngx_http_internal_redirect(ngx_http_requ ngx_int_t ngx_http_named_location(ngx_http_request_t *r, ngx_str_t *name) { - ngx_uint_t i; ngx_http_core_srv_conf_t *cscf; ngx_http_core_loc_conf_t **clcfp; ngx_http_core_main_conf_t *cmcf; cscf = ngx_http_get_module_srv_conf(r, ngx_http_core_module); - clcfp = cscf->locations.elts; - - for (i = cscf->named_start; i < cscf->locations.nelts; i++) { - - if (name->len != clcfp[i]->name.len - || ngx_strncmp(name->data, clcfp[i]->name.data, name->len) != 0) + for (clcfp = cscf->named_locations; *clcfp; clcfp++) { + + ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, + "test location: \"%V\"", &(*clcfp)->name); + + if (name->len != (*clcfp)->name.len + || ngx_strncmp(name->data, (*clcfp)->name.data, name->len) != 0) { continue; } ngx_log_debug3(NGX_LOG_DEBUG_HTTP, r->connection->log, 0, - "named location: %V \"%V?%V\"", name, &r->uri, &r->args); + "using location: %V \"%V?%V\"", name, &r->uri, &r->args); r->internal = 1; r->content_handler = NULL; - r->loc_conf = clcfp[i]->loc_conf; + r->loc_conf = (*clcfp)->loc_conf; ngx_http_update_location_config(r); @@ -1935,6 +1929,7 @@ ngx_http_named_location(ngx_http_request "could not find named location \"%V\"", name); ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR); + return NGX_DONE; } @@ -1983,7 +1978,6 @@ ngx_http_core_server(ngx_conf_t *cf, ngx ngx_http_module_t *module; ngx_http_conf_ctx_t *ctx, *http_ctx; ngx_http_core_srv_conf_t *cscf, **cscfp; - ngx_http_core_loc_conf_t **clcfp; ngx_http_core_main_conf_t *cmcf; ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t)); @@ -2061,37 +2055,6 @@ ngx_http_core_server(ngx_conf_t *cf, ngx *cf = pcf; - if (rv != NGX_CONF_OK) { - return rv; - } - - ngx_sort(cscf->locations.elts, (size_t) cscf->locations.nelts, - sizeof(ngx_http_core_loc_conf_t *), ngx_http_core_cmp_locations); - - clcfp = cscf->locations.elts; - -#if (NGX_PCRE) - - cscf->regex_start = cscf->locations.nelts; - - for (i = 0; i < cscf->locations.nelts; i++) { - if (clcfp[i]->regex) { - cscf->regex_start = i; - break; - } - } - -#endif - - cscf->named_start = cscf->locations.nelts; - - for (i = 0; i < cscf->locations.nelts; i++) { - if (clcfp[i]->named) { - cscf->named_start = i; - break; - } - } - return rv; } @@ -2105,8 +2068,7 @@ ngx_http_core_location(ngx_conf_t *cf, n ngx_conf_t save; ngx_http_module_t *module; ngx_http_conf_ctx_t *ctx, *pctx; - ngx_http_core_srv_conf_t *cscf; - ngx_http_core_loc_conf_t *clcf, *pclcf, **clcfp; + ngx_http_core_loc_conf_t *clcf, *pclcf; ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t)); if (ctx == NULL) { @@ -2201,15 +2163,10 @@ ngx_http_core_location(ngx_conf_t *cf, n pclcf = pctx->loc_conf[ngx_http_core_module.ctx_index]; - if (pclcf->name.len == 0) { - cscf = ctx->srv_conf[ngx_http_core_module.ctx_index]; - - clcfp = ngx_array_push(&cscf->locations); - if (clcfp == NULL) { - return NGX_CONF_ERROR; - } - - } else { + if (pclcf->name.len) { + + /* nested location */ + #if 0 clcf->prev_location = pclcf; #endif @@ -2230,6 +2187,14 @@ ngx_http_core_location(ngx_conf_t *cf, n return NGX_CONF_ERROR; } + if (clcf->named) { + ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, + "named location \"%V\" must be " + "on server level only", + &clcf->name); + return NGX_CONF_ERROR; + } + #if (NGX_PCRE) if (clcf->regex == NULL && ngx_strncmp(clcf->name.data, pclcf->name.data, pclcf->name.len) @@ -2244,22 +2209,11 @@ ngx_http_core_location(ngx_conf_t *cf, n &clcf->name, &pclcf->name); return NGX_CONF_ERROR; } - - if (pclcf->locations == NULL) { - pclcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *)); - - if (pclcf->locations == NULL) { - return NGX_CONF_ERROR; - } - } - - clcfp = ngx_array_push(pclcf->locations); - if (clcfp == NULL) { - return NGX_CONF_ERROR; - } } - *clcfp = clcf; + if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) { + return NGX_CONF_ERROR; + } save = *cf; cf->ctx = ctx; @@ -2269,103 +2223,10 @@ ngx_http_core_location(ngx_conf_t *cf, n *cf = save; - if (rv != NGX_CONF_OK) { - return rv; - } - - if (clcf->locations == NULL) { - return rv; - } - - ngx_sort(clcf->locations->elts, (size_t) clcf->locations->nelts, - sizeof(ngx_http_core_loc_conf_t *), ngx_http_core_cmp_locations); - -#if (NGX_PCRE) - - clcf->regex_start = clcf->locations->nelts; - clcfp = clcf->locations->elts; - - for (i = 0; i < clcf->locations->nelts; i++) { - if (clcfp[i]->regex) { - clcf->regex_start = i; - break; - } - } - -#endif - return rv; } -static ngx_int_t -ngx_http_core_cmp_locations(const void *one, const void *two) -{ - ngx_int_t rc; - ngx_http_core_loc_conf_t *first, *second; - - first = *(ngx_http_core_loc_conf_t **) one; - second = *(ngx_http_core_loc_conf_t **) two; - - if (first->named && !second->named) { - /* shift named locations to the end */ - return 1; - } - - if (!first->named && second->named) { - /* shift named locations to the end */ - return -1; - } - - if (first->named && second->named) { - return ngx_strcmp(first->name.data, second->name.data); - } - - if (first->noname && !second->noname) { - /* shift no named locations to the end */ - return 1; - } - - if (!first->noname && second->noname) { - /* shift no named locations to the end */ - return -1; - } - - if (first->noname || second->noname) { - /* do not sort no named locations */ - return 0; - } - -#if (NGX_PCRE) - - if (first->regex && !second->regex) { - /* shift the regex matches to the end */ - return 1; - } - - if (!first->regex && second->regex) { - /* shift the regex matches to the end */ - return -1; - } - - if (first->regex || second->regex) { - /* do not sort the regex matches */ - return 0; - } - -#endif - - rc = ngx_strcmp(first->name.data, second->name.data); - - if (rc == 0 && second->exact_match) { - /* an exact match must be before the same inclusive one */ - return 1; - } - - return rc; -} - - static char * ngx_http_core_types(ngx_conf_t *cf, ngx_command_t *cmd, void *conf) { @@ -2541,12 +2402,6 @@ ngx_http_core_create_srv_conf(ngx_conf_t * conf->client_large_buffers.num = 0; */ - if (ngx_array_init(&cscf->locations, cf->pool, 4, sizeof(void *)) - == NGX_ERROR) - { - return NGX_CONF_ERROR; - } - if (ngx_array_init(&cscf->listen, cf->pool, 4, sizeof(ngx_http_listen_t)) == NGX_ERROR) { @@ -3345,7 +3200,7 @@ static ngx_http_method_name_t ngx_metho static char * ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf) { - ngx_http_core_loc_conf_t *clcf = conf; + ngx_http_core_loc_conf_t *pclcf = conf; char *rv; void *mconf; @@ -3355,13 +3210,13 @@ ngx_http_core_limit_except(ngx_conf_t *c ngx_http_module_t *module; ngx_http_conf_ctx_t *ctx, *pctx; ngx_http_method_name_t *name; - ngx_http_core_loc_conf_t *lcf, **clcfp; - - if (clcf->limit_except) { + ngx_http_core_loc_conf_t *clcf; + + if (pclcf->limit_except) { return "duplicate"; } - clcf->limit_except = 0xffffffff; + pclcf->limit_except = 0xffffffff; value = cf->args->elts; @@ -3369,7 +3224,7 @@ ngx_http_core_limit_except(ngx_conf_t *c for (name = ngx_methods_names; name->name; name++) { if (ngx_strcasecmp(value[i].data, name->name) == 0) { - clcf->limit_except &= name->method; + pclcf->limit_except &= name->method; goto next; } } @@ -3382,8 +3237,8 @@ ngx_http_core_limit_except(ngx_conf_t *c continue; } - if (!(clcf->limit_except & NGX_HTTP_GET)) { - clcf->limit_except &= (uint32_t) ~NGX_HTTP_HEAD; + if (!(pclcf->limit_except & NGX_HTTP_GET)) { + pclcf->limit_except &= (uint32_t) ~NGX_HTTP_HEAD; } ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t)); @@ -3419,27 +3274,16 @@ ngx_http_core_limit_except(ngx_conf_t *c } - lcf = ctx->loc_conf[ngx_http_core_module.ctx_index]; - clcf->limit_except_loc_conf = ctx->loc_conf; - lcf->loc_conf = ctx->loc_conf; - lcf->name = clcf->name; - lcf->noname = 1; - - if (clcf->locations == NULL) { - clcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *)); - if (clcf->locations == NULL) { - return NGX_CONF_ERROR; - } - } - - clcfp = ngx_array_push(clcf->locations); - if (clcfp == NULL) { + clcf = ctx->loc_conf[ngx_http_core_module.ctx_index]; + pclcf->limit_except_loc_conf = ctx->loc_conf; + clcf->loc_conf = ctx->loc_conf; + clcf->name = pclcf->name; + clcf->noname = 1; + + if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) { return NGX_CONF_ERROR; } - *clcfp = lcf; - - save = *cf; cf->ctx = ctx; cf->cmd_type = NGX_HTTP_LMT_CONF;
--- a/src/http/ngx_http_core_module.h +++ b/src/http/ngx_http_core_module.h @@ -28,6 +28,10 @@ #define NGX_HTTP_SATISFY_ANY 1 +typedef struct ngx_http_location_tree_node_s ngx_http_location_tree_node_t; +typedef struct ngx_http_core_loc_conf_s ngx_http_core_loc_conf_t; + + typedef struct { unsigned default_server:1; unsigned bind:1; @@ -127,37 +131,30 @@ typedef struct { typedef struct { - /* - * array of the ngx_http_core_loc_conf_t *, - * used in the ngx_http_core_find_location() and in the merge phase - */ - ngx_array_t locations; - - unsigned regex_start:15; - unsigned named_start:15; - /* array of the ngx_http_listen_t, "listen" directive */ - ngx_array_t listen; + ngx_array_t listen; /* array of the ngx_http_server_name_t, "server_name" directive */ - ngx_array_t server_names; + ngx_array_t server_names; /* server ctx */ - ngx_http_conf_ctx_t *ctx; + ngx_http_conf_ctx_t *ctx; - ngx_str_t server_name; + ngx_str_t server_name; - size_t connection_pool_size; - size_t request_pool_size; - size_t client_header_buffer_size; + size_t connection_pool_size; + size_t request_pool_size; + size_t client_header_buffer_size; - ngx_bufs_t large_client_header_buffers; + ngx_bufs_t large_client_header_buffers; - ngx_msec_t client_header_timeout; + ngx_msec_t client_header_timeout; - ngx_flag_t optimize_server_names; - ngx_flag_t ignore_invalid_headers; - ngx_flag_t merge_slashes; + ngx_flag_t optimize_server_names; + ngx_flag_t ignore_invalid_headers; + ngx_flag_t merge_slashes; + + ngx_http_core_loc_conf_t **named_locations; } ngx_http_core_srv_conf_t; @@ -231,8 +228,6 @@ typedef struct { } ngx_http_err_page_t; -typedef struct ngx_http_core_loc_conf_s ngx_http_core_loc_conf_t; - struct ngx_http_core_loc_conf_s { ngx_str_t name; /* location name */ @@ -240,8 +235,6 @@ struct ngx_http_core_loc_conf_s { ngx_regex_t *regex; #endif - unsigned regex_start:15; - unsigned noname:1; /* "if () {}" block or limit_except */ unsigned named:1; @@ -251,8 +244,10 @@ struct ngx_http_core_loc_conf_s { unsigned auto_redirect:1; unsigned alias:1; - /* array of inclusive ngx_http_core_loc_conf_t */ - ngx_array_t *locations; + ngx_queue_t *locations; + + ngx_http_location_tree_node_t *static_locations; + ngx_http_core_loc_conf_t **regex_locations; /* pointer to the modules' loc_conf */ void **loc_conf; @@ -339,6 +334,31 @@ struct ngx_http_core_loc_conf_s { }; +typedef struct { + ngx_queue_t queue; + ngx_http_core_loc_conf_t *exact; + ngx_http_core_loc_conf_t *inclusive; + ngx_str_t *name; + u_char *file_name; + ngx_uint_t line; + ngx_queue_t list; +} ngx_http_location_queue_t; + + +struct ngx_http_location_tree_node_s { + ngx_http_location_tree_node_t *left; + ngx_http_location_tree_node_t *right; + ngx_http_location_tree_node_t *tree; + + ngx_http_core_loc_conf_t *exact; + ngx_http_core_loc_conf_t *inclusive; + + u_char auto_redirect; + u_char len; + u_char name[1]; +}; + + void ngx_http_core_run_phases(ngx_http_request_t *r); ngx_int_t ngx_http_core_generic_phase(ngx_http_request_t *r, ngx_http_phase_handler_t *ph);