通配符哈希表 -- ngx_hash_wildcard_t

2015-09-19 03:05:33   最后更新: 2015-09-22 21:09:53   访问数量:1087




前面我们阅读了 nginx 的哈希表结构 ngx_hash_t

哈希表结构 -- ngx_hash_t

 

nginx 的哈希表的一个很重要的应用场景是虚拟主机 server name 的匹配,因此除了提供常规的哈希表匹配操作,基于通配符的哈希表也就必不可少了

 

nginx 支持对哈希表通过 “www.techlog.*” 或 “*.techlog.cn” 这样的前缀或后缀通配符关键字对哈希表进行查找

事实上,这是通过一个数据结构 ngx_hash_wildcard_t 实现的

 

可以看到 ngx_hash_wildcard_t 仅仅是对 ngx_hash_t 的一个简单的封装:

// struct ngx_hash_wildcard_t // 支持通配符的散列表结构 {{{ typedef struct { ngx_hash_t hash; void *value; } ngx_hash_wildcard_t; // }}}

 

 

事实上,它的结构还是我们在上一篇博客中讲到的 ngx_hash_t 结构,只是封装了额外的 value 字段

 

而支持前缀、后缀匹配的结构体正是通过它实现的:

// struct ngx_hash_combined_t // 通配符散列结构 {{{ typedef struct { ngx_hash_t hash; ngx_hash_wildcard_t *wc_head; ngx_hash_wildcard_t *wc_tail; } ngx_hash_combined_t; // }}}

 

 

在实际的使用中,hash 指向的哈希表存储了完整的字段,而 wc_head 指向的散列表中则存储了每个关键字去除前缀(首个 . 前面的部分)后逆置的 URL(如 www.techlog.cn 转换为 cn.techlog),而 wc_tail 指向的散列表则存储了去除尾缀的 URL(如 www.techlog.cn 转换为 www.techlog),这样,通过对关键字进行一个简单地处理并在相应的散列表中匹配,即可实现支持首位通配符的散列表查询了

 

 

// struct ngx_hash_keys_arrays_t // 用于初始化通配符散列结构的数据结构 {{{ typedef struct { // 下面 6 个数组每个数组的元素个数 ngx_uint_t hsize; // 用于分配空间的内存池结构 ngx_pool_t *pool; ngx_pool_t *temp_pool; // 存储完整匹配关键字的 ngx_str_t 结构动态数组 ngx_array_t keys; // 存储完整匹配关键字的 ngx_hash_key_t 结构动态数组 ngx_array_t *keys_hash; // 存储前缀匹配关键字的 ngx_str_t 结构动态数组 ngx_array_t dns_wc_head; // 存储前缀匹配关键字的 ngx_hash_key_t 结构动态数组 ngx_array_t *dns_wc_head_hash; // 存储后缀匹配关键字的 ngx_str_t 结构动态数组 ngx_array_t dns_wc_tail; // 存储后缀匹配关键字的 ngx_hash_key_t 结构动态数组 ngx_array_t *dns_wc_tail_hash; } ngx_hash_keys_arrays_t; // }}}

 

 

这个结构体中除了分配空间用的内存池,定义了6个动态数组,三个用来存储关键字,三个用来存储 ngx_hash_key_t 结构

这样,通过6个动态数组保存全部的 key,实现了对三个哈希表初始数据的保存

 

// ngx_int_t // ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type) // ngx_hash_keys_arrays_t 结构初始化 {{{ ngx_int_t ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type) { ngx_uint_t asize; if (type == NGX_HASH_SMALL) { asize = 4; ha->hsize = 107; } else { asize = NGX_HASH_LARGE_ASIZE; ha->hsize = NGX_HASH_LARGE_HSIZE; } if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize); if (ha->keys_hash == NULL) { return NGX_ERROR; } ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize); if (ha->dns_wc_head_hash == NULL) { return NGX_ERROR; } ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize); if (ha->dns_wc_tail_hash == NULL) { return NGX_ERROR; } return NGX_OK; } // }}}

 

 

这个函数实现了对 ngx_hash_keys_arrays_t 结构内存的分配工作

 

空间分配好了,接下来就要向里面添加数据了

// ngx_int_t // ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value, // ngx_uint_t flags) // 向 ngx_hash_keys_arrays_t 结构中添加 key、value {{{ ngx_int_t ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value, ngx_uint_t flags) { size_t len; u_char *p; ngx_str_t *name; ngx_uint_t i, k, n, skip, last; ngx_array_t *keys, *hwc; ngx_hash_key_t *hk; last = key->len; if (flags & NGX_HASH_WILDCARD_KEY) { /* * supported wildcards: * "*.example.com", ".example.com", and "www.example.*" */ n = 0; // 判断是否符合通配符哈希的条件 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; } } // 首个位置遇到 .,说明是 ".example.com" 的情况,需要适配通配符 if (key->len > 1 && key->data[0] == '.') { skip = 1; goto wildcard; } if (key->len > 2) { // "*.example.com" if (key->data[0] == '*' && key->data[1] == '.') { skip = 2; goto wildcard; } // "www.example.*" if (key->data[i - 2] == '.' && key->data[i - 1] == '*') { skip = 0; last -= 2; goto wildcard; } } // * 不是出现在指定的位置 if (n) { return NGX_DECLINED; } } /* exact hash */ k = 0; // 完全匹配的 hash 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; /* check conflicts in exact hash */ // 去掉重复的 key 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) { return NGX_BUSY; } } } else { if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK) { return NGX_ERROR; } } name = ngx_array_push(&ha->keys_hash[k]); if (name == NULL) { return NGX_ERROR; } *name = *key; hk = ngx_array_push(&ha->keys); if (hk == NULL) { return NGX_ERROR; } hk->key = *key; hk->key_hash = ngx_hash_key(key->data, last); hk->value = value; return NGX_OK; wildcard: /* wildcard hash */ k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip); k %= ha->hsize; if (skip == 1) { /* check conflicts in exact hash for ".example.com" */ name = ha->keys_hash[k].elts; if (name) { len = last - skip; for (i = 0; i < ha->keys_hash[k].nelts; i++) { if (len != name[i].len) { continue; } if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) { return NGX_BUSY; } } } else { if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK) { return NGX_ERROR; } } name = ngx_array_push(&ha->keys_hash[k]); if (name == NULL) { return NGX_ERROR; } name->len = last - 1; name->data = ngx_pnalloc(ha->temp_pool, name->len); if (name->data == NULL) { return NGX_ERROR; } ngx_memcpy(name->data, &key->data[1], name->len); } if (skip) { /* * convert "*.example.com" to "com.example.\0" * and ".example.com" to "com.example\0" */ p = ngx_pnalloc(ha->temp_pool, last); if (p == NULL) { return NGX_ERROR; } len = 0; n = 0; for (i = last - 1; i; i--) { if (key->data[i] == '.') { ngx_memcpy(&p[n], &key->data[i + 1], len); n += len; p[n++] = '.'; len = 0; continue; } len++; } if (len) { ngx_memcpy(&p[n], &key->data[1], len); n += len; } p[n] = '\0'; hwc = &ha->dns_wc_head; keys = &ha->dns_wc_head_hash[k]; } else { /* convert "www.example.*" to "www.example\0" */ last++; p = ngx_pnalloc(ha->temp_pool, last); if (p == NULL) { return NGX_ERROR; } ngx_cpystrn(p, key->data, last); hwc = &ha->dns_wc_tail; keys = &ha->dns_wc_tail_hash[k]; } /* check conflicts in wildcard hash */ name = keys->elts; if (name) { len = last - skip; for (i = 0; i < keys->nelts; i++) { if (len != name[i].len) { continue; } if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) { return NGX_BUSY; } } } else { if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK) { return NGX_ERROR; } } name = ngx_array_push(keys); if (name == NULL) { return NGX_ERROR; } name->len = last - skip; name->data = ngx_pnalloc(ha->temp_pool, name->len); if (name->data == NULL) { return NGX_ERROR; } ngx_memcpy(name->data, key->data + skip, name->len); /* add to wildcard hash */ hk = ngx_array_push(hwc); if (hk == NULL) { return NGX_ERROR; } hk->key.len = last - 1; hk->key.data = p; hk->key_hash = 0; hk->value = value; return NGX_OK; } // }}}

 

 

flags 有以下三种取值:

ngx_hash_add_key 的 flags 参数的取值(前两个可取 | 操作)
取值意义
NGX_HASH_WILDCARD_KEY需要处理通配符
NGX_HASH_READONLY_KEY不将key转换为小写(否则全部转换为小写实现不区分大小写的key)
0既不处理通配符也不区分关键字大小写

 

ngx_hash_add_key 函数在已经创建好的 ngx_hash_keys_arrays_t 结构中插入了关键字与对应的值

如果需要处理通配符,则对于 key 中的前缀通配符情况进行了对逆置的 key 的按 . 分隔后存储

 

保存有所有数据的 ngx_hash_keys_array_t 结构已经初始化完成,通过他的紧接着就需要用它来初始化我们的通配符散列表 ngx_hash_wildcard_t 了

 

// ngx_int_t // ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, // ngx_uint_t nelts) // 通配符散列表初始化 {{{ ngx_int_t ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) { size_t len, dot_len; ngx_uint_t i, n, dot; ngx_array_t curr_names, next_names; ngx_hash_key_t *name, *next_name; ngx_hash_init_t h; ngx_hash_wildcard_t *wdc; // 在临时内存池上创建 ngx_hash_key_t 动态数组用于存放关键字 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } // 在临时内存池上创建 ngx_hash_key_t 动态数组用于存放去掉通配符后的关键字 if (ngx_array_init(&next_names, hinit->temp_pool, nelts, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } for (n = 0; n < nelts; n = i) { #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "wc0: \"%V\"", &names[n].key); #endif dot = 0; // 遍历查找 '.' for (len = 0; len < names[n].key.len; len++) { if (names[n].key.data[len] == '.') { dot = 1; break; } } // 将 '.' 前的关键字插入到 curr_names 数组中 name = ngx_array_push(&curr_names); if (name == NULL) { return NGX_ERROR; } 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; #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "wc1: \"%V\" %ui", &name->key, dot); #endif dot_len = len + 1; if (dot) { len++; } next_names.nelts = 0; // 如果names[n] 在 '.' 后还有剩余关键字,将剩余关键字放入 next_names 中 if (names[n].key.len != len) { next_name = ngx_array_push(&next_names); if (next_name == NULL) { return NGX_ERROR; } 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; #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "wc2: \"%V\"", &next_name->key); #endif } // 剩下的全部放入 next_names 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 = ngx_array_push(&next_names); if (next_name == NULL) { return NGX_ERROR; } 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; #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "wc3: \"%V\"", &next_name->key); #endif } if (next_names.nelts) { h = *hinit; h.hash = NULL; // 递归创建哈希表 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts, next_names.nelts) != NGX_OK) { return NGX_ERROR; } // 将用户 value 放入新的哈希表 wdc = (ngx_hash_wildcard_t *) h.hash; if (names[n].key.len == len) { wdc->value = names[n].value; } // 将当前 value 指向新的哈希表 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2)); } else if (dot) { name->value = (void *) ((uintptr_t) name->value | 1); } } // 将最外层hash初始化 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts, curr_names.nelts) != NGX_OK) { return NGX_ERROR; } return NGX_OK; } // }}}

 

这个初始化过程看似简单,其实内藏玄机,在前一篇博客中我们看到 ngx_hash_init 函数的实现较为简单,然而 ngx_hash_wildcard_init 则并非如此

首先,这个函数递归调用了自己,这是为什么呢?原因是对于逆序的 "com.techlog",我们首先需要匹配 com 然后再去匹配 techlog

 

这个过程的另一个玄机在于对 ngx_hash_wildcard_t 结构的 value 字段的处理

name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));

 

name->value = (void *) ((uintptr_t) name->value | 1);

 

 

这两行代码分别在不同的情况下执行:

ngx_hash_wildcard_t value 尾部2位取值
取值意义
01无下一级哈希
10指向最后一级哈希
11后续还有很多级哈希

 

查找的过程相比上面介绍的创建过程要好理解的多了

在通配符哈希表的匹配过程中,nginx 首先调用上一篇博客中介绍的 ngx_hash_find 函数进行完全匹配,如果无法匹配成功则会调用 ngx_hash_find_wc_head 进行前向匹配,如果仍无法匹配成功则最终会调用 ngx_hash_find_wc_tail 进行后置匹配

 

// void * // ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) // 按照前置散列表规则查询指定字符串 {{{ void * ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) { void *value; ngx_uint_t i, n, key; #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name); #endif n = len; while (n) { if (name[n - 1] == '.') { break; } n--; } key = 0; for (i = n; i < len; i++) { key = ngx_hash(key, name[i]); } #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key); #endif value = ngx_hash_find(&hwc->hash, key, &name[n], len - n); #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value); #endif if (value) { /* * the 2 low bits of value have the special meaning: * 00 - value is data pointer for both "example.com" * and "*.example.com"; * 01 - value is data pointer for "*.example.com" only; * 10 - value is pointer to wildcard hash allowing * both "example.com" and "*.example.com"; * 11 - value is pointer to wildcard hash allowing * "*.example.com" only. */ if ((uintptr_t) value & 2) { if (n == 0) { /* "example.com" */ if ((uintptr_t) value & 1) { return NULL; } hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3); return hwc->value; } hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3); value = ngx_hash_find_wc_head(hwc, name, n - 1); if (value) { return value; } return hwc->value; } if ((uintptr_t) value & 1) { if (n == 0) { /* "example.com" */ return NULL; } return (void *) ((uintptr_t) value & (uintptr_t) ~3); } return value; } return hwc->value; } // }}}

 

 

// void * // ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) // 按照后置散列表规则查询指定字符串 {{{ void * ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) { void *value; ngx_uint_t i, key; #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name); #endif key = 0; for (i = 0; i < len; i++) { if (name[i] == '.') { break; } key = ngx_hash(key, name[i]); } if (i == len) { return NULL; } #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key); #endif value = ngx_hash_find(&hwc->hash, key, name, i); #if 0 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value); #endif if (value) { /* * the 2 low bits of value have the special meaning: * 00 - value is data pointer; * 11 - value is pointer to wildcard hash allowing "example.*". */ if ((uintptr_t) value & 2) { i++; hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3); value = ngx_hash_find_wc_tail(hwc, &name[i], len - i); if (value) { return value; } return hwc->value; } return value; } return hwc->value; } // }}}

 

 

由于通配符散列表的创建是递归的,因此对他的检索也是递归进行的

 

为了方便说明,这里我们配置了同一 IP、端口下的 5 个虚拟主机:*.baidu.com、*.google.com、*.techlog.com、*.baidu.com.cn、*.google.com.cn,最终,完成哈希表的初始化工作以后,我们将得到下图的结构:

 

 






linux      nginx      opensource      sourcecode      webserver      开源      hash      source      code      wildcard      ngx_hash_t      ngx_hash_wildcard_t     


京ICP备15018585号