Just Carry On

Nginx 源代码笔记 - 哈希表 [2]

本文目录

复合哈希表

Nginx 接收到有效的请求数据 (request line, request headers) 后，会根据请求包 头的 "Host" 字段和事先配置好的虚拟主机名 (由配置指令 server_name 配置) 进行匹 配，然后使用匹配成功的虚拟主机 对请求进行后续处理。

其中，配置文件中指定的虚拟主机名可以是常规字符串，也可以是包含通配符的特殊字符 串 (具体规则参见下文)。为了支持类似虚拟主机名 (作为查找键) 查找这样的应用场景， Nginx 实现了一种特殊的哈希表结构 ngx_hash_combined_t，我们暂时将其译为复合哈 希表。

另外，为了表述方便，我们将 *.example.org 和 .example.org 称为前置通配符；将 www.example.* 称为后置通配符；将实现通配符哈希表功能的结构体 ngx_hash_wildcard_t 称为通配符哈希表。同时，下面的分析过程以虚拟主机名相关应用 场景为上下文。

下面的篇幅就来分析一下复合哈希表是如何同时存储含有和不含有通配符的键值对 (键、 值分别对应虚拟主机名和虚拟主机配置结构体指针)，以及如何使用具体的 "Host" 字段值 定位虚拟主机的。

在分析具体代码之前，先补充一下虚拟主机名的配置语法：

Server names are defined using the server_name directive and determine which server {} block is used for a give request...They may be defined using exact names, wildcard names, or regular expressions.

When searching for a virtual server by name, if name matches more than one of the specificed variants, e.g. both wildcard name and regular expression match, the first matching variant will be chosen, in the following order of precedence:

  1. exact name
  2. longest wildcard name starting with an asterisk, e.g. "*.example.org"
  3. longest wildcard name ending with an asterisk, e.g. "mail.*"
  4. first matching regular expression (in order of appearance in a configuration file.

A wildcard name may contain an asterisk only on the name's start or end, and only on a dot border...An asterisk can match several name parts.

Some special server names:

  • If it is required to process requests without the "Host" header field in a server {} block which is not the default, an empty name "" should be jspecified.
  • If a server name is defined as "$hostname" (0.9.4), the machine's hostname is used.
  • A special wildcard name in the form ".example.org" can be used to match both the exact name "example.org" and the wildcard name "*.example.org".

除了上面描述的规则外，还有下面几条在实际使用中碰到的规则：

  • 对同一个地址 (listen) 设置的虚拟主机名，同一名称的两种通配符形式，如 .example.com 和 *.example.com，不会同时生效。Nginx 主动忽略配置文件中靠后的 那个，并打印：

    nginx: [warn] conflicting server name "*.example.com" on 0.0.0.0:80, ignored

  • 同一个地址 (listen) 设置的虚拟主机名，同一名称的通配符形式和精确形式，如 *.example.com 和 example.com 不会同时生效。Nginx 主动忽略配置文件中靠后的那 个，并打印：

    nginx: [warn] conflicting server name "example.com" on 0.0.0.0:80, ignored

  • 带有请求包头 Host: example.com 的请求不会被匹配到名为 *.example.com 的虚 拟主机上。

在 Nginx 配置解析和初始化过程中，虚拟主机名经配置指令回调函数 ngx_http_core_server_name 读取并存储后，由函数 ngx_http_server_names 转换成 虚拟主机名哈希表结构。

在 Nginx 处理请求过程中，在函数 ngx_http_find_virtual_server 中，根据请求包头 的 "Host" 字段内容，使用 ngx_hash_find_combined 函数对虚拟主机名哈希表中进行 查找匹配，寻找合适的虚拟主机。

创建

ngx_hash_combined_t 是复合哈希表结构体。它由三个子哈希表 - 精确匹配哈希表 (存 储未使用通配符的虚拟主机名)、前置通配符哈希表 (存储形如 *.example.org 和 .example.org 的前置通配符虚拟主机名查找) 和后置通配符哈希表 (用于提供形如 www.example.* 的后置通配符虚拟主机名查找) 组成。从下面的定义可以看到，这三个 子哈希表都是基于普通哈希表 ngx_hash_t 实现的。

typedef struct {
    ngx_hash_t        hash;
    void             *value;
} ngx_hash_wildcard_t;

typedef struct {
    ngx_hash_t            hash;
    ngx_hash_wildcard_t  *wc_head;
    ngx_hash_wildcard_t  *wc_tail;
} ngx_hash_combined_t;

复合哈希表由 ngx_hash_keys_array_init 函数、ngx_hash_add_key 函数和 ngx_hash_wildcard_init 函数创建，由 ngx_hash_find_combined 函数提 供查询功能。

以 Nginx 虚拟主机功能使用的复合哈希为例，其创建由 ngx_http_server_names 函数 完成，主要过程如下：

/* ngx_http_server_names */
ngx_http_keys_arrays_t      ha;
...
ngx_memzero(&ha, sizeof(ngx_hash_keys_arrays_t));
...
ngx_hash_keys_array_init(&ha, NGX_HASH_LARGE);
...
cscfp = addr->servers.elts;

for (s = 0; s < addr->servers.nelts; s++) {
    name = cscfp[s]->server_names.elts;
    for (n = 0; n < cscfp[s]->server_names.nelts; n++) {
        ...
        ngx_hash_add_key(&ha, &name[n], name[n].server,
                         NGX_HASH_WILDCARD_KEY);
        ...
    }
}
...
if (ha.keys.nelts) {
    ...
    ngx_hash_init(&hash, ha.keys.elts, ha.keys.nelts);
    ...
}

if (ha.dns_wc_head.nelts) {
    ngx_qsort(ha.dns_wc_head.elts, (size_t) ha.dns_wc_head.nelts,
              sizeof(ngx_hash_key_t), ngx_http_cmp_dns_wildcards);
    ...
    ngx_hash_wildcard_init(&hash, ha.dns_wc_head.elts,
                           ha.dns_wc_head.nelts);
    ...
}

if (ha.dns_wc_tail.nelts) {
    ngx_qsort(ha.dns_wc_tail.elts, (size_t) ha.dns_wc_tail.nelts,
              sizeof(ngx_hash_key_t), ngx_http_cmp_dns_wildcards);
    ...
    ngx_hash_wildcard_init(&hash, ha.dns_wc_tail.elts,
                           ha.dns_wc_tail.nelts);
    ...
}

对以上代码的补充说明：

  • 调用 ngx_hash_keys_array_init 函数初始化 ngx_hash_keys_arrays_t 类型变量 ha。此结构体定义如下：

    typedef struct {
    ngx_uint_t      hsize;

    ngx_pool_t      *pool;
    ngx_pool_t      *temp_pool;

    ngx_array_t     keys;
    ngx_array_t     *keys_hash;

    ngx_array_t     dns_wc_head;
    ngx_array_t     *dns_wc_head_hash;

    ngx_array_t     dns_wc_tail;
    ngx_array_t     *dns_wc_tail_hash;
} ngx_hash_keys_arrays_t;

    • keys、dns_wc_head 和 dns_wc_tail 三个成员数组分别用来保存 ngx_hash_key_t 类型的精确键值对、前置通配符键值对和后置通配符键值对。

    • _hash 后缀的成员为 hsize 大小的简易哈希表，它们从 temp_pool 申请空 间，用于检测和过滤重复虚拟主机名。

  • 调用 ngx_hash_add_key 函数向 ngx_hash_keys_arrays_t 中添加 ngx_hash_key_t 类型键值对。它完成的主要工作下面介绍。

  • 调用 ngx_hash_init 函数构造精确匹配子哈希表，调用 ngx_hash_wildcard_init 函数构造前置和后置通配符子哈希表。

实际上，上述流程也可以用于创建普通哈希表：传递 NGX_HASH_READONLY_KEY 参数给 ngx_hash_add_key 函数，然后针对 ngx_hash_keys_arrays_t::keys 调用 ngx_hash_init 构造普通哈希表。ngx_http_ssi_filter 等模块和 Nginx 变量引擎中 都使用了这种方式。

每次调用 ngx_hash_add_key 函数，它会将参数键值对添加到 ngx_hash_keys_arrays_t 中合适的键值对数组成员中。它主要完成的工作有：

  • 如果启用了通配符模式 (NGX_HASH_WILDCARD_KEY)，检查当前主机名中是否包含通配 符，并记录去掉通配符后的常规部分 (skip, last)。

  • 如果当前添加的主机名不包含通配符，检查它是否和己经添加的其它普通主机名重复。 如不重复，就将当前键值对存入 ngx_hash_keys_arrays_t::keys 中。

    for (i = 0; i < last; i++) {
    if (!(flags & NGX_HASH_READONLY_KEY)) {
        key->data[i] = ngx_tolower(key->data[i]);
    }
    k = ngx_hash(K, key->data[i]);
}

k %= ha->hsize;

name = ha->keys_hash[k].elts;

if (name) {
    for (i = 0; i < ha->keys_hash[k].nelts; i++) {
        if (last != name[i].len) {
            continue;
        }

        if (ngx_strncmp(key->data, name[i].data, last) == 0) {
            reeturn NGX_BUSY;
        };
} else {
    ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
                   sizeof(ngx_str_t));
    ...
}

name = ngx_array_push(&ha->keys_hash[k]);
...
*name = *key;

hk = ngx_array_push(&ha->keys);
...
hk->key = *key;
hk->key_hash = ngx_hash_key(key->data, last);
hk->value = value;

return NGX_OK;

  • 如果当前添加的主机名包含通配符，取出常规部分用于重复性检测。并根据不同的通配符 类型，进行不同的处理：

    • 由于形如 .example.com 的前置通配符主机名可以作为精确匹配串和 example.com 常规字符串相匹配，所以需对其在常规主机名简易哈希表 keys_hash 中进行检测：

      if (skip == 1) {
    name = ha->keys_hash[k].elts;
    ...
}

    • 对于包含前置通配符的主机名，为了方便存储，将以 "." 分隔的部分作为整体进行 反转，将可模糊匹配的部分放到后面。同时，对两种前置通配符形式 *.example.com 和 .example.com 进行区分 (*.example.com 转换成 com.example.， .example.com 转换成 com.example)：

      if (skip) {
    p = ngx_palloc(ha->temp_pool, last);
    ...
    p[n] = '\0';

    hwc = &ha->dns_wc_head;
    keys = &ha->wc_head_hash[k];

} else {
    ...

    • 对于包含后置通配符的主机名，只保留常规部分：

      } else {
    last++;

    p = ngx_pnalloc(ha->temp_pool, last);
    ...
    hwc = &ha->dns_wc_tail;
    keys = &ha->dns_wc_tail_hash[k];
}

  • 最后，在各自对应的简易哈希表中检测完是否重复后，将转换处理后的两类通配符主机 名进行分类存储：

        hk = ngx_array_push(hwc);
    ...
    hk->key.len = last - 1;
    hk->key.data = p;
    hk->key_hash = 0;
    hk->value = value;

    return NGX_OK;

ngx_hash_keys_arrays_t 结构体准备完毕后，Nginx 调用相关构造函数创建上面的三类 子哈希表。由于普通哈希表的构造过程上面已经分析过了，下面就主要分析通配符哈希表构 造函数 ngx_hash_wildcard_init。需要注意的是，在调用 ngx_hash_wildcard_init 之前，在 ngx_http_server_names 函数中对键值对按照虚拟主机名进行了从小到大的排 序操作：

/* ngx_http_server_names */
if (ha.dns_wc_head.nelts) {

    ngx_qsort(ha.dns_wc_head.elts, (size_t) ha.dns_wc_head.nelts,
              sizeof(ngx_hash_key_t), ngx_http_cmp_dns_wildcards);

    hash.hash = NULL;
    hash.temp_pool = ha.temp_pool;

    ngx_hash_wildcard_init(&hash, ha.dns_wc_head.elts,
                           ha.dns_wc_head.nelts);

    addr->wc_head = (ngx_hash_wildcard_t *) hash.hash;
}

另外，ngx_hash_wildcard_init 是递归函数，理解起来稍微有些许周折，外加个人描述 能力实在有限，所以介绍完该函数的主要逻辑后，再用些实例对分析进行补充和佐证。

互联网域名使用 '.' 区分不同级别的子域名，自然而然，Nginx 处理虚拟主机名时也 使用了相同的记法 - 以 '.' 作为区分主机名单元的分隔符。也就是说，“exmaple.com" 和 “2example.com" 两个主机名，只有 “com” 是相同部分。

ngx_hash_wildcard_init 函数对所有主机名建立多层哈希表，哈希表中的查询键并不是 整个主机名，而是主机名单元。比如，对 *.example.com 和 *.example.org 两个主机 名来讲，最终构造出的复合哈希表，可简略表示为：

     table 1
    +-----+
    | ... |         table 2
    | org | --->  +---------+
    | ... |       | example |         table 3
    | com | -----------------------> +---------+
    | ... |                          | example |
    +-----+                          +---------+

ngx_hash_wildcard_init 函数主要逻辑 (下面分析主要以前置通配符哈希表为例，后置 通配符哈希表过程大同小异) 如下：

  • 使用 curr_names 保存当前主机名的第一个单元 A。使用 next_names 保存当前主机 名去除单元 A 后的剩余所有单元，如果后面紧邻的主机名第一个单元也是 A 的话，将它们 的剩余所有单元也存入其中。

    • 确定当前主机名的第一个单元，并存入 curr_names：

      dot = 0;

for (len = 0; len < names[n].key.len; len++) {
    if (names[n].key.data[len] == '.') {
        dot = 1;
        break;
    }
}

name = ngx_array_push(&curr_names);
name->key.len = len;
name->key.data = names[n].key.data;
name->key_hash = hinit->key(name->key.data, name->key.len);
name->value = names[n].value;

dot_len = len - 1;

if (dot) {
    len++;
}

    • 如果当前主机名还有剩余单元，将其存入 next_names：

      if (names[n].key.len != len) {
    next_name = ngx_array_push(&next_names);
    next_name->key.len = names[n].key.len - len;
    next_name->key.data = names[n].key.data + len;
    next_name->key_hash = 0;
    next_name->value = names[n].value;
}

    • 判断后面紧邻的主机名 (所有主机名已经排序，拥有相同单元的主机名依次紧邻) 是 否和当前主机名的第一个单元相同。如果有，将这些主机名剩余部分都存到 next_names 中，同时，主循环中不会再次处理这些主机名 (n = i)。

      for (n = 0; n < nelts; n = i) { /* 主循环 */
    ...
    for (i = n + 1; i < nelts; i++) {
        if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
            break;
        }

        if (!dot && names[i].key.len > len && names[i].key.data[len] != '.') {
            break;
        }

        next_name->key.len = names[i].key.len - dot_len;
        next_name->key.data = names[i].key.data + dot_len;
        next_name->key_hash = 0;
        next_name->value = names[i].value;
    }
    ...
}

  • 对 next_names 递归创建子通配符哈希表，并调整当前键值对 (调整前的 “值” 为当 前主机名对应虚拟主机配置，调整后它可能指向子哈希表或者虚拟主机配置)。这个调整过 程是理解复合哈希表查询的关键点，分为三种情况：

    • 第一种情况，next_names 为空，且主机名单元后面没有出现 '.' (对前 置通配 符来讲，此主机名由 .example.com 转换而来)，保留原 “值” (后两位置 00)。

    • 第二种情况，next_names 为空，且主机名单元后面有 '.' (对前置通配符来讲， 此主机名由 *.example.com 转换而来)，原 “值” 后两位 置 01：

      else if (dot) {
    name->value = (void *) ((uintptr_t) name->value | 1);
}

    • 第三种情况，next_names 不为空。其中主机名，有可能来自当前主机名，也可能 来其它主机名。由 next_names 中的值创建并记录子通配符哈希表。参见注释：

      if (next_names.nelts) {
    ...
    ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
                           next_names.nelts);

    wdc = (ngx_hash_wildcard_t *) h.hash;

    /*
       * 如果主机名单元是当前主机名的最后一个，保存当前主机名对应的
         虚拟主机配置到 `wdc->value` 中。
       * 其它情况下，当前主机名在 `next_names` 的剩余部分依然维护着
         此虚拟主机配置。
    */
    if (names[n].key.len == len) {
        wdc->value = name->value;
    }

    /* 主机名单元后面是否有 '.' (`dot`):
       * 如 dot == 1，比如，当前主机名为 "com.example."，那么当前单
       元为 "com" 或者 "example" 时，表示只允许对它后的部分进行模糊
       匹配。`name->value` 后两位置 "11"

       * 如 dot == 0，比如，当前主机名为 "com.example"，那么当该单
       元为 "example" 时，表示允许对它进行精确匹配或者对其后的部分
       模糊匹配。`name->value` 后两位置 "10"
     */
    name->value = (void *) ((uintptr_t) wdc | (doc ? 3 : 2));
}

但愿把上面的过程讲明白了！还有几个小问题，需要提一下：

  • name->value 的后两位为什么能肯定都是 0 值？这个问题得从 Nginx 的内存池里寻 找答案了。所有从 Nginx 内存池申请的空间首地址都经过了 ngx_align_ptr 处理，也 就是对 NGX_ALIGNMENT (platform word) 对齐，这样就保证了最少低两位全 0：

    /* ngx_palloc */
m = ngx_align_ptr(p->d.last, NGX_ALIGNMENT);
...

  • 如果虚拟主机名设为 ""，对 "Host" 字段为空或不存的请求，Nginx 是如何触发虚拟主 机查询的：

    1705 ngx_int_t
1706 ngx_http_process_request_header(ngx_http_request_t *r)
1707 {
1708     if (r->headers_in.server.len == 0
1709         && ngx_http_set_virtual_server(r, &r->headers_in.server)
1710            == NGX_ERROR)
1711     {
1712         return NGX_ERROR;
1713     }

下面展示一些由实例构造出的复合哈希表的简易图：

查找

查找过程由 ngx_hash_find_combined 函数实现，根据 Nginx 定义的优先级，这个函数 会先查询复合哈希表中的精确匹配哈希表，然后是前置通配符哈希表，最后才去查询后置 通配符哈希表，这个函数大致实现代码如下：

/* ngx_hash_find_combined */
if (hash->hash.buckets) {
    value = ngx_hash_find(&hash->hash, key, name, len);

    if (value) {
        return value;
    }
}

if (len == 0) { /* 对于 "Host" 字段为空或不存在的请求，不再继续查询 */
    return NULL;
}

if (hash->wc_head && hash->wc_head->hash.buckets) {
    value = ngx_hash_find_wc_head(hash->wc_head, name, len);

    if (value) {
        return value;
    }
}

if (hash->wc_tail && hash->wc_tail->hash.buckets) {
    value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);

    if (value) {
        return value;
    }
}

ngx_hash_find_wc_head 和 ngx_hash_find_wc_tail 两个查询函数，在理解了复合哈 希表的结构后，就很容易看懂了。篇幅原因 (实在太长了)，有兴趣的自个探索吧。

疑问

  • 数组访问越界

    • ngx_hash_add_key:728
      for (i = 0; i < key->len; i++) {

    if (key->data[i] == '*') {
        if (++n > 1) {
            return NGX_DECLINED;
        }
    }

    if (key->data[i] == '.' && key->data[i + 1] == '.') {
        return NGX_DECLINED;
    }
}

  • 检验不严格

    • wildcard server name 的合法性校验，无法检测出 .*.example.com, .example.* 等等非法形式。可修改代码如下：
      if (key->len > 1 && key->data[0] == '.') {
+    if (n) {
+        return NGX_DECLINED;
+    }
+
    skip = 1;
    goto wildcard;
}
Comments

不要轻轻地离开我，请留下点什么...

comments powered by Disqus

Published

Category

Nginx

Tags

Contact