diff options
author | Igor Sysoev <igor@sysoev.ru> | 2008-05-24 18:14:13 +0400 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2008-05-24 18:14:13 +0400 |
commit | e55988c06941931d60241fb40c7e878cf5484ddf (patch) | |
tree | 8b02d15279950c3e41e31ea05ecc5219461f672c /src/http/ngx_http.c | |
parent | 5cdc511fcd825c522340742f005302d3d7d87771 (diff) |
locations tree
Diffstat (limited to 'src/http/ngx_http.c')
-rw-r--r-- | src/http/ngx_http.c | 600 |
1 files changed, 552 insertions, 48 deletions
diff --git a/src/http/ngx_http.c b/src/http/ngx_http.c index c708ddf03..4e5500fb4 100644 --- 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_conf_t *cf, 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_command_t *cmd, void *conf) 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_command_t *cmd, void *conf) 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_command_t *cmd, void *conf) 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_command_t *cmd, void *conf) /* 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_command_t *cmd, void *conf) /* 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_command_t *cmd, void *conf) } return NGX_CONF_OK; + +failed: + + *cf = pcf; + + return rv; } @@ -544,6 +575,511 @@ ngx_http_init_phase_handlers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf) } +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_http_core_srv_conf_t *cscf, } -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) |