Mercurial > hg > nginx-vendor-current
view src/core/ngx_hash.c @ 196:8759b346e431 NGINX_0_3_45
nginx 0.3.45
*) Feature: the "ssl_verify_client", "ssl_verify_depth", and
"ssl_client_certificate" directives.
*) Change: the $request_method variable now returns the main request
method.
*) Change: the ° symbol codes were changed in koi-win conversion
table.
*) Feature: the euro и N symbols were added to koi-win conversion table.
*) Bugfix: if nginx distributed the requests among several backends and
some backend failed, then requests intended for this backend was
directed to one live backend only instead of being distributed among
the rest.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Sat, 06 May 2006 00:00:00 +0400 |
parents | 4cd3e70c4d60 |
children | e6da4931e0e0 |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev */ #include <ngx_config.h> #include <ngx_core.h> void * ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) { ngx_uint_t i; ngx_hash_elt_t *elt; #if 0 ngx_str_t line; line.len = len; line.data = name; ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%V\"", &line); #endif elt = hash->buckets[key % hash->size]; if (elt == NULL) { return NULL; } while (elt->value) { if (len != (size_t) elt->len) { goto next; } for (i = 0; i < len; i++) { if (name[i] != elt->name[i]) { goto next; } } return elt->value; next: elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, sizeof(void *)); continue; } return NULL; } void * ngx_hash_find_wildcard(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) { void *value; ngx_uint_t i, n, key; #if 0 ngx_str_t line; line.len = len; line.data = name; ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wc:\"%V\"", &line); #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 (value) { /* * the 2 low bits of value have the special meaning: * 00 - value is data pointer, * 01 - value is pointer to wildcard hash allowing * "*.example.com" only, * 11 - value is pointer to wildcard hash allowing * both "example.com" and "*.example.com". */ if ((uintptr_t) value & 1) { hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3); if (n == 0) { if ((uintptr_t) value & 2) { return hwc->value; } else { return NULL; } } value = ngx_hash_find_wildcard(hwc, name, n - 1); if (value) { return value; } return hwc->value; } return value; } return hwc->value; } #define NGX_HASH_ELT_SIZE(name) \ (sizeof(void *) + ngx_align((name)->key.len + 1, sizeof(void *))) ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) { u_char *elts; size_t len; u_short *test; ngx_uint_t i, n, key, size, start, bucket_size; ngx_hash_elt_t *elt, **buckets; for (n = 0; n < nelts; n++) { if (names[n].key.len >= 255) { ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, "the \"%V\" value to hash is to long: %uz bytes, " "the maximum length can be 255 bytes only", &names[n].key, names[n].key.len); return NGX_ERROR; } if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) { ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, "could not build the %s, you should " "increase %s_bucket_size: %i", hinit->name, hinit->name, hinit->bucket_size); return NGX_ERROR; } } test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log); if (test == NULL) { return NGX_ERROR; } bucket_size = hinit->bucket_size - sizeof(void *); start = nelts / (bucket_size / (2 * sizeof(void *)) - 1); start = start ? start : 1; if (hinit->max_size > 10000 && hinit->max_size / nelts < 100) { start = hinit->max_size - 1000; } for (size = start; size < hinit->max_size; size++) { ngx_memzero(test, size * sizeof(u_short)); for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } key = names[n].key_hash % size; test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: %ui %ui \"%V\"", size, key, test[key], &names[n].key); #endif if (test[key] > (u_short) bucket_size) { goto next; } } goto found; next: continue; } ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, "could not build the %s, you should increase " "either %s_max_size: %i or %s_bucket_size: %i", hinit->name, hinit->name, hinit->max_size, hinit->name, hinit->bucket_size); ngx_free(test); return NGX_ERROR; found: for (i = 0; i < size; i++) { test[i] = sizeof(void *); } for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } key = names[n].key_hash % size; test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); } len = 0; for (i = 0; i < size; i++) { if (test[i] == sizeof(void *)) { continue; } test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); len += test[i]; } if (hinit->hash == NULL) { hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t) + size * sizeof(ngx_hash_elt_t *)); if (hinit->hash == NULL) { ngx_free(test); return NGX_ERROR; } buckets = (ngx_hash_elt_t **) ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t)); } else { buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *)); if (buckets == NULL) { ngx_free(test); return NGX_ERROR; } } elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); if (elts == NULL) { ngx_free(test); return NGX_ERROR; } elts = ngx_align_ptr(elts, ngx_cacheline_size); for (i = 0; i < size; i++) { if (test[i] == sizeof(void *)) { continue; } buckets[i] = (ngx_hash_elt_t *) elts; elts += test[i]; } for (i = 0; i < size; i++) { test[i] = 0; } for (n = 0; n < nelts; n++) { if (names[n].key.data == NULL) { continue; } key = names[n].key_hash % size; elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); elt->value = names[n].value; elt->len = (u_char) names[n].key.len; for (i = 0; i < names[n].key.len; i++) { elt->name[i] = ngx_tolower(names[n].key.data[i]); } test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); } for (i = 0; i < size; i++) { if (buckets[i] == NULL) { continue; } elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]); elt->value = NULL; } ngx_free(test); hinit->hash->buckets = buckets; hinit->hash->size = size; #if 0 for (i = 0; i < size; i++) { ngx_str_t val; ngx_uint_t key; elt = buckets[i]; if (elt == NULL) { ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: NULL", i); continue; } while (elt->value) { val.len = elt->len; val.data = &elt->name[0]; key = hinit->key(val.data, val.len); ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "%ui: %p \"%V\" %ui", i, elt, &val, key); elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, sizeof(void *)); } } #endif return NGX_OK; } 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; if (ngx_array_init(&curr_names, hinit->temp_pool, nelts, sizeof(ngx_hash_key_t)) != NGX_OK) { return NGX_ERROR; } 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; } } 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; 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 } 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; } wdc = (ngx_hash_wildcard_t *) h.hash; if (names[n].key.len == len) { wdc->value = names[n].value; #if 0 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, "wdc: \"%V\"", wdc->value); #endif } name->value = (void *) ((uintptr_t) wdc | (dot ? 1 : 3)); } } if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts, curr_names.nelts) != NGX_OK) { return NGX_ERROR; } return NGX_OK; } ngx_uint_t ngx_hash_key(u_char *data, size_t len) { ngx_uint_t i, key; key = 0; for (i = 0; i < len; i++) { key = ngx_hash(key, data[i]); } return key; } ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len) { ngx_uint_t i, key; key = 0; for (i = 0; i < len; i++) { key = ngx_hash(key, ngx_tolower(data[i])); } return key; } ngx_int_t ngx_hash0_init(ngx_hash0_t *hash, ngx_pool_t *pool, void *names, ngx_uint_t nelts) { u_char *p; ngx_str_t *name, *bucket; ngx_uint_t i, n, key, size, best, *test, buckets, min_buckets; if (nelts == 0) { for (name = (ngx_str_t *) names; name->len; name = (ngx_str_t *) ((char *) name + hash->bucket_size)) { nelts++; } } test = ngx_alloc(hash->max_size * sizeof(ngx_uint_t), pool->log); if (test == NULL) { return NGX_ERROR; } min_buckets = hash->bucket_limit + 1; #if (NGX_SUPPRESS_WARN) best = 0; #endif for (size = 1; size < hash->max_size; size++) { buckets = 0; for (i = 0; i < size; i++) { test[i] = 0; } for (n = 0, name = (ngx_str_t *) names; n < nelts; n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size)) { if (name->data == NULL) { continue; } key = 0; for (i = 0; i < name->len; i++) { key += ngx_tolower(name->data[i]); } key %= size; if (test[key] == hash->bucket_limit) { break; } test[key]++; if (buckets < test[key]) { buckets = test[key]; } } if (n == nelts) { if (min_buckets > buckets) { min_buckets = buckets; best = size; } if (hash->bucket_limit == 1) { break; } } } if (min_buckets == hash->bucket_limit + 1) { ngx_log_error(NGX_LOG_EMERG, pool->log, 0, "could not build the %s hash, you should increase " "either %s_size: %i or %s_bucket_limit: %i", hash->name, hash->name, hash->max_size, hash->name, hash->bucket_limit); ngx_free(test); return NGX_ERROR; } hash->buckets = ngx_pcalloc(pool, best * hash->bucket_size); if (hash->buckets == NULL) { ngx_free(test); return NGX_ERROR; } if (hash->bucket_limit != 1) { for (i = 0; i < best; i++) { test[i] = 0; } for (n = 0, name = (ngx_str_t *) names; n < nelts; n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size)) { if (name->data == NULL) { continue; } key = 0; for (i = 0; i < name->len; i++) { key += ngx_tolower(name->data[i]); } key %= best; test[key]++; } for (i = 0; i < best; i++) { if (test[i] == 0) { continue; } bucket = ngx_palloc(pool, test[i] * hash->bucket_size); if (bucket == NULL) { ngx_free(test); return NGX_ERROR; } hash->buckets[i] = bucket; bucket->len = 0; } } for (n = 0, name = (ngx_str_t *) names; n < nelts; n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size)) { if (name->data == NULL) { continue; } key = 0; for (i = 0; i < name->len; i++) { key += ngx_tolower(name->data[i]); } key %= best; if (hash->bucket_limit == 1) { p = (u_char *) hash->buckets + key * hash->bucket_size; ngx_memcpy(p, name, hash->bucket_size); continue; } for (bucket = hash->buckets[key]; bucket->len; bucket = (ngx_str_t *) ((char *) bucket + hash->bucket_size)) { bucket->len &= 0x7fffffff; } ngx_memcpy(bucket, name, hash->bucket_size); bucket->len |= 0x80000000; } ngx_free(test); hash->hash_size = best; hash->min_buckets = min_buckets; return NGX_OK; } 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_wildcards, 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_wildcards_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize); if (ha->dns_wildcards_hash == NULL) { return NGX_ERROR; } return NGX_OK; } 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 *reverse; ngx_str_t *name; ngx_uint_t i, k, n, skip; ngx_hash_key_t *hk; if (!(flags & NGX_HASH_WILDCARD_KEY)) { /* exact hash */ k = 0; for (i = 0; i < key->len; 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 */ name = ha->keys_hash[k].elts; if (name) { for (i = 0; i < ha->keys_hash[k].nelts; i++) { if (key->len != name[i].len) { continue; } if (ngx_strncmp(key->data, name[i].data, key->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 = *key; hk = ngx_array_push(&ha->keys); if (hk == NULL) { return NGX_ERROR; } hk->key = *key; hk->key_hash = ngx_hash_key(key->data, key->len); hk->value = value; } else { /* wildcard hash */ skip = (key->data[0] == '*') ? 2 : 1; k = 0; for (i = skip; i < key->len; i++) { key->data[i] = ngx_tolower(key->data[i]); k = ngx_hash(k, key->data[i]); } k %= ha->hsize; if (skip == 1) { /* check conflicts in exact hash for ".example.com" */ name = ha->keys_hash[k].elts; if (name) { len = key->len - 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 = key->len - 1; name->data = ngx_palloc(ha->temp_pool, name->len); if (name->data == NULL) { return NGX_ERROR; } ngx_memcpy(name->data, &key->data[1], name->len); } /* * convert "*.example.com" to "com.example.\0" * and ".example.com" to "com.example\0" */ reverse = ngx_palloc(ha->temp_pool, key->len); if (reverse == NULL) { return NGX_ERROR; } len = 0; n = 0; for (i = key->len - 1; i; i--) { if (key->data[i] == '.') { ngx_memcpy(&reverse[n], &key->data[i + 1], len); n += len; reverse[n++] = '.'; len = 0; continue; } len++; } if (len) { ngx_memcpy(&reverse[n], &key->data[1], len); n += len; } reverse[n] = '\0'; hk = ngx_array_push(&ha->dns_wildcards); if (hk == NULL) { return NGX_ERROR; } hk->key.len = key->len - 1; hk->key.data = reverse; hk->key_hash = 0; hk->value = value; /* check conflicts in wildcard hash */ name = ha->dns_wildcards_hash[k].elts; if (name) { len = key->len - skip; for (i = 0; i < ha->dns_wildcards_hash[k].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(&ha->dns_wildcards_hash[k], ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK) { return NGX_ERROR; } } name = ngx_array_push(&ha->dns_wildcards_hash[k]); if (name == NULL) { return NGX_ERROR; } name->len = key->len - skip; name->data = ngx_palloc(ha->temp_pool, name->len); if (name->data == NULL) { return NGX_ERROR; } ngx_memcpy(name->data, key->data + skip, name->len); } return NGX_OK; }