From e18a033b921d0d79fa8278f853548e6125b93e0c Mon Sep 17 00:00:00 2001 From: Konstantin Ananyev Date: Tue, 31 Oct 2017 12:40:17 +0000 Subject: Integrate TLDK with NGINX Created a clone of nginx (from https://github.com/nginx/nginx) to demonstrate and benchmark TLDK library integrated with real world application. A new nginx module is created and and BSD socket-like API is implemented on top of native TLDK API. Note, that right now only minimalistic subset of socket-like API is provided: - accept - close - readv - recv - writev so only limited nginx functionality is available for a moment. Change-Id: Ie1efe9349a0538da4348a48fb8306cbf636b5a92 Signed-off-by: Mohammad Abdul Awal Signed-off-by: Reshma Pattan Signed-off-by: Remy Horton Signed-off-by: Konstantin Ananyev --- app/nginx/src/core/ngx_hash.c | 988 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 988 insertions(+) create mode 100644 app/nginx/src/core/ngx_hash.c (limited to 'app/nginx/src/core/ngx_hash.c') diff --git a/app/nginx/src/core/ngx_hash.c b/app/nginx/src/core/ngx_hash.c new file mode 100644 index 0000000..1944c7a --- /dev/null +++ b/app/nginx/src/core/ngx_hash.c @@ -0,0 +1,988 @@ + +/* + * Copyright (C) Igor Sysoev + * Copyright (C) Nginx, Inc. + */ + + +#include +#include + + +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_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name); +#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_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 *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; +} + + +void * +ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name, + size_t len) +{ + void *value; + + if (hash->hash.buckets) { + value = ngx_hash_find(&hash->hash, key, name, len); + + if (value) { + return value; + } + } + + if (len == 0) { + 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; + } + } + + return NULL; +} + + +#define NGX_HASH_ELT_SIZE(name) \ + (sizeof(void *) + ngx_align((name)->key.len + 2, 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; + + if (hinit->max_size == 0) { + ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, + "could not build %s, you should " + "increase %s_max_size: %i", + hinit->name, hinit->name, hinit->max_size); + return NGX_ERROR; + } + + for (n = 0; n < nelts; n++) { + 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 %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 *))); + start = start ? start : 1; + + if (hinit->max_size > 10000 && nelts && 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; + } + + size = hinit->max_size; + + ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0, + "could not build optimal %s, you should increase " + "either %s_max_size: %i or %s_bucket_size: %i; " + "ignoring %s_bucket_size", + hinit->name, hinit->name, hinit->max_size, + hinit->name, hinit->bucket_size, hinit->name); + +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_short) names[n].key.len; + + ngx_strlow(elt->name, names[n].key.data, names[n].key.len); + + 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; + } + + name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2)); + + } else if (dot) { + name->value = (void *) ((uintptr_t) name->value | 1); + } + } + + 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_uint_t +ngx_hash_strlow(u_char *dst, u_char *src, size_t n) +{ + ngx_uint_t key; + + key = 0; + + while (n--) { + *dst = ngx_tolower(*src); + key = ngx_hash(key, *dst); + dst++; + src++; + } + + return key; +} + + +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_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; + } + + if (key->data[i] == '\0') { + return NGX_DECLINED; + } + } + + if (key->len > 1 && key->data[0] == '.') { + skip = 1; + goto wildcard; + } + + if (key->len > 2) { + + if (key->data[0] == '*' && key->data[1] == '.') { + skip = 2; + goto wildcard; + } + + if (key->data[i - 2] == '.' && key->data[i - 1] == '*') { + skip = 0; + last -= 2; + goto wildcard; + } + } + + if (n) { + return NGX_DECLINED; + } + } + + /* exact hash */ + + k = 0; + + 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 */ + + 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; +} -- cgit 1.2.3-korg