Nginx 源代码笔记 - URI 匹配

在 Nginx 的配置文件中，一个虚拟主机 (server {}) 中可以配置多个 location {}。 location 有什么作用呢？

location

This directive allows different configurations depending on the URI. It can be configured using both literal strings and regular expressions.

location 就是从 URI 层对 HTTP request 进行区分，从而进行不同处理的方法。比 如，有些对有些 URI 返回静态内容；另有些 URI 分发到后端应用服务器后，返回由这 些应用服务器生成的动态内容。

总而言之，location 实现了对 HTTP request 的细分处理。

location 匹配

一个 server {} 能够配置多个 location，请求到达时，如何从这些 location 中选 择一个合适的 location 呢？

location order

The order in which location directives are checked as follows:

1. Directives with the "=" prefix that match the query exactly (literal string). If found, searching stops.
2. All remaining directives with conventional strings. If this match used the `^~" prefix, searching stops.
3. Regular expressions, in the order they are defined in the configuration file.
4. If #3 yielded a match, that result is used. Otherwise, the match from #2 is used.

To determine which location directive matches a particular query, the literal strings are checked first. Literal strings match the beginning portion of the query - the most specific match will be used. Afterwards, regular expressions are checked in the order defined in the configuration file. The first regular expression to match the query will stop the search. If no regular expression matches are found, the result from the literal search is used.

总结下来：

• 不包含正则的 location 在配置文件中的顺序不会影响匹配顺序。而包含正则表达式的 location 会按照配置文件中定义的顺序进行匹配。

• 设置为精确匹配 (with = prefix) 的 location 如果匹配请求 URI 的话，此 location 被马上使用，匹配过程结束。

• 在其它只包含普通字符的 location 中，找到和请求 URI 最长的匹配。如果此 server {} 没有包含正则的 location 或者该 location 启用了 ^~ 的话，这个最 长匹配的 location 会被使用。如果此 server {} 中包含正则的 location，则先在 这些正则 location 中进行匹配，如果找到匹配，则使用匹配的正则 location，如果 没找到匹配，依然使用最大匹配的 location。

• ^~, =, ~, ~* 这些修饰符和后面的 URI 字符串中间可以不使用空格隔开。@ 修饰符必须和 URI 字符串 (实际上应该叫 “命名”) 直接连接。

• location 可以嵌套定义。但是要符合以下几条规则：

  • = 修饰的 location 中不能再嵌套其它 location
  • @ 修饰的 location 中不能再嵌套其它 location
  • @ 修饰的 location 不能嵌套到其它 location 中
  • 父 location 的 URI 字符串必须是子 location 的 URI 字符串的前缀 (子 location 启用了正则的情况除外)

接下来的篇幅，分析一下 Nginx 是如何组织存储 location，以及上面的匹配规则是如何 实现的。

存储结构

对 location 指令的配置解析，在 配置解析 一文中 已经进行了简单描述。先来介绍一下，这部分涉及到的主要数据类型。

• ngx_http_core_loc_conf_t - location 作用域结构体。这个结构体也负责在其它高 层作用域中存储能同时定义于多个作用域的 location 配置项，还负责连接高层作用域和 location 作用域。

  struct ngx_http_core_loc_conf_s {
      ngx_str_t           name;   /* URI 部分字符串 */
      ngx_http_regex_t    *regex; /* 正则引擎编译过的 正则表达式对象 */
      ...
      unsigned            named:1;        /* @ 修饰符 */
      unsigned            noname:1;       /* if () {} */
      unsigned            exact_match:1;  /* = 修饰符 */
      unsigned            noregex:1;      /* ^= 修饰符 */
  
      ...
      ngx_http_location_tree_node_t   *static_location;
      ngx_http_core_loc_conf_t        **regex_location;
      void                **loc_conf;
      ...
      ngx_queue_t         *locations; /* 连接 `location` 作用域，由
                                         ngx_http_location_queue_t 强制转
                                         换而来 */
  };
  

• ngx_http_location_queue_t - 用于临时保存 location 的 ngx_queue_t 封装结 构。即作为 queue head，又可作用 queue node。

  typedef struct {
      ngx_queue_t                 queue;
      ngx_http_core_loc_conf_t    *exact; /* exact_match, regex, named, noname */
      ngx_http_core_loc_conf_t    *inclusive; /* 非 exact 的 location */
      ngx_str_t                   *name;
      u_char                      *file_name;
      ngx_uint_t                  *line;
      ngx_queue_t                 list;
  } ngx_http_location_queue_t;
  

• ngx_http_location_tree_node_t - 运行时 location 的树状存储结构节点。便于 location 的快速查找。

  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];
  };
  

在配置解析初步完成后，一个server {} location 指令的临时存储结构可以参考 配置解析 中的图例。

ngx_http_block 完成配置读取和存储后，调用 ngx_init_locations 函数和 ngx_http_init_static_location_tree 函数对每个虚拟主机 (server {}) 中定义的 location 进行重新整理。

    ------------http/ngx_http.c:114------------
    static char *
    ngx_http_block(ngx_conf_t *cf, ngx_combined_t *cmd, void *conf)
    {
        ...
        cmcf = ctx->main_conf[ngx_http_core_module.ctx_index];
        cscfp = cmcf->servers.elts;
        ...
        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;
            }
        }
        ...
    }

对上述代码的补充说明：

• clcf 最终指向用于连接每个 server {} 和其中定义的各 location 的 ngx_http_loc_conf_t 的结构体 (参见 配置解析)。

其中，ngx_http_init_locations 负责将 location 排序，并且分类存放。函数处理完 成后，locations 队列中只剩下了 exact 和 inclusive 类型的 location。而后， ngx_http_init_static_location_trees 再将 exact 和 inclusive 类型的 location 进一步处理，构造出更容访问的数据结构。

先看一下 ngx_http_init_locations 是如何将 location 分类存放的。

    -----------http/ngx_http.c:626-------------
    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)
    {
        ...
        locations = pclcf->locations;
        ...
        ngx_queue_sort(locations, ngx_http_cmp_locations);
        named = NULL;
        n = 0;
        regex = NULL;
        r = 0;

        for (q = ngx_queue_head(locations);
            q != ngx_queue_sentinel(locations);
            q = ngx_queue_next(q))
        {
            clcf = lq->exact ? lq->exact : lq->inclusive;

            if (ngx_http_init_locations(cf, NULL, clcf) != NGX_OK) {
                return NGX_ERROR;
            }

            if (clcf->regex) {
                r++;
                if (regex == NULL) {
                    regex = q;
                }

                continue;
            }

            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 **));
            ...
            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 (regex) {
            ...
            pclcf->regex_locations = clcfp;
            ...
        }

        return NGX_OK;
    }

对上面代码的补充说明：

• ngx_queue_sort 将所有的 location 按其类型进行排序。操作完成后， 各类 location 的顺序如下 (inclusive 表示这个 location 配置的 URI 如果出现于 request URI 的前部，就认为此 location 是匹配的)：

  exact(sorted) -> inclusive(sorted) -> regex -> named -> noname
  

• ngx_http_init_locations 递归调用了自己。这是为了处理 location 嵌套的情况。

• noname 类型的 location 被丢弃。

• named 类型的 location 加入到了 ngx_http_srv_conf_t 成员 named_locations 指向的数组中。named 类型的 location 不能嵌套到其它 location 或被嵌套其它 location 的，所以存储到了 ngx_http_srv_cont_t 结构体中。

• regex 类型的 location 加放到了起关联作用的 ngx_http_loc_conf_t 成员 regex_locations 指向的数组中。

• exact 和 inclusive 类型的 location 依然保留在 locations 队列中。它们都 属于 static location。

接下来， exact 和 inclusive 类型的 location 被 ngx_http_init_static_location_trees 函数进一步处理：

    --------------http/ngx_http.c:755---------------
    static ngx_int_t
    ngx_http_init_static_location_trees(ngx_conf_t *cf,
        ngx_http_core_loc_conf_t *pclcf)
    {
        locations = pclcf->locations;
        ...
        for (q = ngx_queue_head(locations);
             q != ngx_queue_sentinal(locations);
             q = ngx_queue_next(q))
        {
            lq = (ngx_http_location_queue_t *) q;

            clcf = lq->exact ? lq->exact : lq->inclusive;

            ngx_http_init_static_location_trees(cf, clcf);
        }

        ngx_http_join_exact_locations(cf, locations);

        ngx_http_create_locations_list(locations, ngx_queue_head(locations));

        pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0);
        ...
    }

对以上代码的补充说明：

• ngx_http_init_static_location_trees 函数会被嵌套调用，为了处理 location 嵌套定义的情况。

• ngx_http_join_exact_locations 将当前虚拟主机中 uri 字符串完全一致的 exact 和 inclusive 类型的 location 进行合并。

• ngx_http_create_locations_list 和 ngx_http_create_locations_tree 用于构造 相对平衡的二叉查找树。详细实现代码，接下来进行分析。

由于 inclusive 类型的 location 在 ngx_http_init_locations 函数中已经被按字 典顺序进行了排序。也就是说，有共同前缀的 inclusive 类型的 location 会被集中 存放。 如果一个 location 的 URI 是后面一个或多个 location URI 的前缀，那 么这几个 location 节点会被 ngx_http_create_locations_list 整理合并。

为了使分析更具体化，下面使用示例 locations (只列出 URI，即节点 name 部分) /a /ab /abc /abd /b /bc 对代码进行举例说明。

exact 类型的节点依然保留在 locations 队列中。

    --------------http/ngx_http.c:959--------------------
    static void
    ngx_http_create_locations_list(ngx_queue_t *locations, ngx_queue_t *q)
    {
        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;
            }
        }
        ...
        ngx_queue_split(locations, q, &tail);
        ngx_queue_add(&lq->list, &tail);
        ...
        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);
    }

对上面代码的补充说明：

• 有些边界操作上面摘录中被省略掉了。

• 参数 locations 指向第一级的 location 节点 (其它级别的 location 节点已经 被追加到上级 location 节点的 list 变量中)，q 指向 locations 中还未被整理 过的 location 节点。

• 由于这个函数存在递归调用，q == ngx_queue_last(locations) 是递归的退出条件。

• 对于非 inclusive 类型 (此时 locations 队列中也只包含 exact 和 inclusive 类型的 location 节点) 的 location 节点，直接跳过，不做任何整理。

  if (lq->inclusive == NULL) {
      ngx_http_create_locations_list(locations, ngx_queue_next(q));
      return;
  }
  

• lq 指向第一个待整理的 location 节点。lx 指向第一个 URI 不以 lq 指向 的节点 URI 为前缀的节点。例如，以上面的示例 locations 为例，如果 lq 指向 /a，那么 lx 最终将指向 /b。那么/a /ab /abc /abd 就是可以被整理合并到第一 级节点 /a 的节点。

• 将可以合并的节点，通过 ngx_queue_split 和 ngx_queue_add 操作，追加到 /a 节点的 list 变量中。从 lx 开始的剩余节点使用 ngx_queue_list 和 ngx_queue_add 操作，放回 locations 队列中。

• 最后对 lq->list 中的节点和从 lx 开始的剩余节点进行相同的操作。

• ngx_http_create_locations_list 函数完成后，示例 locations 的结构体如下：

ngx_http_create_location_list 将某个 location 节点和其后以其 URI 为 URI 前缀的一个或多个节点进行整理合并，并且在 ngx_http_create_location_trees 转化成 二叉查找树 (location 节点在树中是有序排列的) 后，可以加快针对某 request URI 进行 location 查找匹配的速度。

二叉查找树构造在 ngx_http_create_location_trees 函数中完成。

    ------------http/ngx_http.c:1023------------------
    static ngx_http_location_tree_node_t *
    ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations)
    {
        ...
        q = ngx_queue_middle(location);

        lq = (ngx_http_location_queue_t *) q;
        len = lq->name->len - prefix;

        node = ngx_palloc(cf->pool,
                          offsetof(ngx_http_location_tree_node_t, name) + len);
        ...
        node->len = (u_char) len;
        ngx_memcpy(node->name, &lq->name->data[prefix], len);

        ngx_queue_split(locations, q, &tail);
        ...
        node->left = ngx_http_create_locations_tree(cf, locations, prefix);
        ...
        ngx_queue_remove(q);
        ...
        node->right = ngx_http_create_locations_tree(cf, &tail, prefix);
        ...
    inclusive:

        if (ngx_queue_empty(&lq->list)) {
            return node;
        }

        node->tree = ngx_http_create_locations_tree(cf, &lq->list, prefix + len);
        ...
        return node;
    }

对上述代码的补充说明：

• 有些边界操作上面摘录中被省略掉了。

• 值得一提的是 ngx_queue_middle 函数使用了快慢指针，单次遍历就确定了中间节点的 位置。虽然，复杂度上没有任何提高，但是技巧很赞。queue 中节点数为奇数时，函数返 回正中间位置的节点；节点数为偶数时，函数返回后半部分的首个节点。

• locations 队列里，中间节点 q 前的元素成为 q 的左子树节点；中间节点 q 后面的元素，变成了 q 的右子树节点。随后，在这两部分节点上再重复建左右子树的过 程。

• 然后，再对 q 的 list 里包含的由 ngx_http_create_locations_list 函数合并 的节点递归构建二叉查找树。需要注意的一点是 ngx_http_create_locations_list 生成 的分级别链表中，上级的 URI 总是下级的 URI 前缀。这样一来，下级节点就不需要再 存储完整 URI 了，它只用存储多上级多出的部分。这么做，在节省的空间的同时，也能 提高查找效率 (已经比较过的前缀，再对下级进行查找时，就不用再次比较了)。

• 针对 q 的下级节点构造的二叉查找树由node->tree 成员变量记录。

• 最终，locations 队列节点全部转化成了二叉树的节点。临时存储结构 ngx_http_location_queue_t 的 list 成员中的节点，全部转化成了 ngx_http_location_tree_node_t 结构体 tree 成员中的节点。

• 对上面的示例 locations 队列调用 ngx_http_create_locations_tree 后，结构图 如下：

到此为止，location 相关的数据结构算是构造完成了。剩下的就是如何定位每个请求对 应的 location 作用域了。

请求匹配

在开始定位 request 应由哪个 location 处理之前，Nginx 已经确定了 request 所 属的虚拟主机。

请求的 location 匹配，在请求处理的 FIND_CONFIG phase (可参见 模块分类 中对 handler 模块的介绍) 相对应的 checker ngx_http_core_find_config_phase 函数中完成。ngx_http_core_find_config_phase 函数调用 ngx_http_core_find_location 函数完成实际的匹配工作。

    ------------http/ngx_http_core_module.c:1427----------
    static ngx_int_t
    ngx_http_core_find_location(ngx_http_request_t *r)
    {
        ...
        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) {
            ...
            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 (noregex == 0 && pclcf->regex_locations) {

            for (clcfp = pclcf->regex_locations; *clcfp; clcfp++) {
                ...
                n = ngx_http_regex_exec(r, (*clcfp)->regex, &r->uri);
                ...
            }
        }

        return rc;
    }

对上面代码的补充说明：

• ngx_http_core_find_static_location 函数的返回值决定是否再次尝试正则查找。其 允许的返回值如下：

  • NGX_OK - exact match
  • NGX_DONE - auto redirect
  • NGX_AGAIN - inclusive match
  • NGX_DECLINED - no match

• 返回值为 NGX_AGAIN 时，也就是 inclusive match 时，根据预先设定的逻辑，接下 来需要完成正则匹配了。但是，由于嵌套 location 的存在，还要在完成嵌套查找后再决 定是否开始正则匹配。

• 但是关于嵌套 location 查找一个疑问：假如一个 inclusive 类型的 location A 被匹配上了，那么第一次 ngx_http_core_find_static_location 函数调用，返回值为 NGX_AGAIN，接下来，开始检查 A 有没有嵌套 locaton。如果 A 没有嵌套，那么 用于检测嵌套的对 ngx_http_core_find_location 函数的递归调用返回 NGX_DECLINED。 再如果并没有设置和 A 并列的正则调用时，整个查找过程会返回 NGX_DECLINED。 这 和函数 ngx_http_core_find_static_location 返回值的定义不符啊？

关于函数 ngx_http_core_find_location 的代码逻辑，和上一节的树结构紧密相关。主 要逻辑就不再分析了。唯一一个需要注意的地方是，在我使用的 0.8.34 的代码中，对 exact 类型 location 的检查逻辑和当前 Nginx 的使用文档描述不符：

    if (len == (size_t) node->len) {
        r->loc_conf = (node->exact) ? node->exact->loc_conf:
                                      node->inclusive->loc_conf;
        return NGX_OK;
    }

根据此函数的返回值定义和代码中看到的，不论该 location 类型是否是 exact，只要 出现了完全匹配，Nginx 都认为是发生了 exact match。

幸运的是，在较新版本 1.4.1 中，这段代码已经变为：

    if (len == (size_t) node->len) {

        if (node->exact) {
            r->loc_conf = node->exact->loc_conf;
            return NGX_OK;

        } else {
            r->loc_conf = node->inclusive->loc_conf;
            return NGX_AGAIN;
        }
    }

并且，从 CHANGES 文件中，找到了这个行为变动的版本号和时间：

1353 Changes with nginx 0.8.42 21 Jun 2010 1354 1355 *) Change: now nginx tests locations given by regular expressions, if 1356 request was matched exactly by a location given by a prefix string. 1357 The previous behavior has been introduced in 0.7.1.