diff options
| -rw-r--r-- | src/nxt_application.c | 91 | ||||
| -rw-r--r-- | src/nxt_application.h | 2 | ||||
| -rw-r--r-- | src/nxt_controller.c | 46 | ||||
| -rw-r--r-- | src/nxt_http_parse.c | 545 | ||||
| -rw-r--r-- | src/nxt_http_parse.h | 55 | ||||
| -rw-r--r-- | src/nxt_router.c | 16 | ||||
| -rw-r--r-- | src/test/nxt_http_parse_test.c | 117 |
7 files changed, 445 insertions, 427 deletions
diff --git a/src/nxt_application.c b/src/nxt_application.c index 50375569..49d785e8 100644 --- a/src/nxt_application.c +++ b/src/nxt_application.c @@ -28,14 +28,22 @@ static nxt_app_module_t *nxt_app_module_load(nxt_task_t *task, const char *name); static nxt_app_type_t nxt_app_parse_type(u_char *p, size_t length); +static nxt_int_t nxt_app_request_content_length(void *ctx, + nxt_http_field_t *field, uintptr_t data); +static nxt_int_t nxt_app_request_content_type(void *ctx, + nxt_http_field_t *field, uintptr_t data); +static nxt_int_t nxt_app_request_cookie(void *ctx, nxt_http_field_t *field, + uintptr_t data); +static nxt_int_t nxt_app_request_host(void *ctx, nxt_http_field_t *field, + uintptr_t data); -static nxt_thread_mutex_t nxt_app_mutex; -static nxt_thread_cond_t nxt_app_cond; -static nxt_http_fields_hash_entry_t nxt_app_request_fields[]; -static nxt_http_fields_hash_t *nxt_app_request_fields_hash; - -static nxt_application_module_t *nxt_app; +static nxt_http_field_proc_t nxt_app_request_fields[] = { + { nxt_string("Content-Length"), &nxt_app_request_content_length, 0 }, + { nxt_string("Content-Type"), &nxt_app_request_content_type, 0 }, + { nxt_string("Cookie"), &nxt_app_request_cookie, 0 }, + { nxt_string("Host"), &nxt_app_request_host, 0 }, +}; static uint32_t compat[] = { @@ -43,6 +51,14 @@ static uint32_t compat[] = { }; +static nxt_lvlhsh_t nxt_app_request_fields_hash; + +static nxt_thread_mutex_t nxt_app_mutex; +static nxt_thread_cond_t nxt_app_cond; + +static nxt_application_module_t *nxt_app; + + nxt_int_t nxt_discovery_start(nxt_task_t *task, void *data) { @@ -359,16 +375,9 @@ nxt_app_module_load(nxt_task_t *task, const char *name) nxt_int_t nxt_app_http_init(nxt_task_t *task, nxt_runtime_t *rt) { - nxt_http_fields_hash_t *hash; - - hash = nxt_http_fields_hash_create(nxt_app_request_fields, rt->mem_pool); - if (nxt_slow_path(hash == NULL)) { - return NXT_ERROR; - } - - nxt_app_request_fields_hash = hash; - - return NXT_OK; + return nxt_http_fields_hash(&nxt_app_request_fields_hash, rt->mem_pool, + nxt_app_request_fields, + nxt_nitems(nxt_app_request_fields)); } @@ -512,12 +521,12 @@ nxt_app_msg_write(nxt_task_t *task, nxt_app_wmsg_t *msg, u_char *c, size_t size) nxt_int_t nxt_app_msg_write_prefixed_upcase(nxt_task_t *task, nxt_app_wmsg_t *msg, - const nxt_str_t *prefix, const nxt_str_t *v) + const nxt_str_t *prefix, u_char *c, size_t size) { u_char *dst, *src; size_t i, length, dst_length; - length = prefix->length + v->length; + length = prefix->length + size; dst_length = length + (length < 128 ? 1 : 4) + 1; @@ -531,8 +540,8 @@ nxt_app_msg_write_prefixed_upcase(nxt_task_t *task, nxt_app_wmsg_t *msg, nxt_memcpy(dst, prefix->start, prefix->length); dst += prefix->length; - src = v->start; - for (i = 0; i < v->length; i++, dst++, src++) { + src = c; + for (i = 0; i < size; i++, dst++, src++) { if (*src >= 'a' && *src <= 'z') { *dst = *src & ~0x20; @@ -704,18 +713,19 @@ nxt_app_msg_read_size(nxt_task_t *task, nxt_app_rmsg_t *msg, size_t *size) static nxt_int_t nxt_app_request_content_length(void *ctx, nxt_http_field_t *field, - nxt_log_t *log) + uintptr_t data) { - nxt_str_t *v; nxt_app_parse_ctx_t *c; nxt_app_request_header_t *h; c = ctx; h = &c->r.header; - v = &field->value; - h->content_length = *v; - h->parsed_content_length = nxt_off_t_parse(v->start, v->length); + h->content_length.length = field->value_length; + h->content_length.start = field->value; + + h->parsed_content_length = nxt_off_t_parse(field->value, + field->value_length); return NXT_OK; } @@ -723,7 +733,7 @@ nxt_app_request_content_length(void *ctx, nxt_http_field_t *field, static nxt_int_t nxt_app_request_content_type(void *ctx, nxt_http_field_t *field, - nxt_log_t *log) + uintptr_t data) { nxt_app_parse_ctx_t *c; nxt_app_request_header_t *h; @@ -731,15 +741,15 @@ nxt_app_request_content_type(void *ctx, nxt_http_field_t *field, c = ctx; h = &c->r.header; - h->content_type = field->value; + h->content_type.length = field->value_length; + h->content_type.start = field->value; return NXT_OK; } static nxt_int_t -nxt_app_request_cookie(void *ctx, nxt_http_field_t *field, - nxt_log_t *log) +nxt_app_request_cookie(void *ctx, nxt_http_field_t *field, uintptr_t data) { nxt_app_parse_ctx_t *c; nxt_app_request_header_t *h; @@ -747,15 +757,15 @@ nxt_app_request_cookie(void *ctx, nxt_http_field_t *field, c = ctx; h = &c->r.header; - h->cookie = field->value; + h->cookie.length = field->value_length; + h->cookie.start = field->value; return NXT_OK; } static nxt_int_t -nxt_app_request_host(void *ctx, nxt_http_field_t *field, - nxt_log_t *log) +nxt_app_request_host(void *ctx, nxt_http_field_t *field, uintptr_t data) { nxt_app_parse_ctx_t *c; nxt_app_request_header_t *h; @@ -763,22 +773,13 @@ nxt_app_request_host(void *ctx, nxt_http_field_t *field, c = ctx; h = &c->r.header; - h->host = field->value; + h->host.length = field->value_length; + h->host.start = field->value; return NXT_OK; } -static nxt_http_fields_hash_entry_t nxt_app_request_fields[] = { - { nxt_string("Content-Length"), &nxt_app_request_content_length, 0 }, - { nxt_string("Content-Type"), &nxt_app_request_content_type, 0 }, - { nxt_string("Cookie"), &nxt_app_request_cookie, 0 }, - { nxt_string("Host"), &nxt_app_request_host, 0 }, - - { nxt_null_string, NULL, 0 } -}; - - nxt_app_parse_ctx_t * nxt_app_http_req_init(nxt_task_t *task) { @@ -805,8 +806,6 @@ nxt_app_http_req_init(nxt_task_t *task) return NULL; } - ctx->parser.fields_hash = nxt_app_request_fields_hash; - return ctx; } @@ -832,7 +831,7 @@ nxt_app_http_req_header_parse(nxt_task_t *task, nxt_app_parse_ctx_t *ctx, return rc; } - rc = nxt_http_fields_process(p->fields, ctx, task->log); + rc = nxt_http_fields_process(p->fields, &nxt_app_request_fields_hash, ctx); if (nxt_slow_path(rc != NXT_OK)) { return rc; diff --git a/src/nxt_application.h b/src/nxt_application.h index 615efc37..ce14bc27 100644 --- a/src/nxt_application.h +++ b/src/nxt_application.h @@ -164,7 +164,7 @@ NXT_EXPORT nxt_int_t nxt_app_msg_write(nxt_task_t *task, nxt_app_wmsg_t *msg, u_char *c, size_t size); NXT_EXPORT nxt_int_t nxt_app_msg_write_prefixed_upcase(nxt_task_t *task, - nxt_app_wmsg_t *msg, const nxt_str_t *prefix, const nxt_str_t *v); + nxt_app_wmsg_t *msg, const nxt_str_t *prefix, u_char *c, size_t size); nxt_inline nxt_int_t nxt_app_msg_write_nvp_(nxt_task_t *task, nxt_app_wmsg_t *msg, diff --git a/src/nxt_controller.c b/src/nxt_controller.c index be7bfd5d..0a65ada7 100644 --- a/src/nxt_controller.c +++ b/src/nxt_controller.c @@ -65,7 +65,7 @@ static void nxt_controller_conn_close(nxt_task_t *task, void *obj, void *data); static void nxt_controller_conn_free(nxt_task_t *task, void *obj, void *data); static nxt_int_t nxt_controller_request_content_length(void *ctx, - nxt_http_field_t *field, nxt_log_t *log); + nxt_http_field_t *field, uintptr_t data); static void nxt_controller_process_request(nxt_task_t *task, nxt_controller_request_t *req); @@ -79,14 +79,12 @@ static u_char *nxt_controller_date(u_char *buf, nxt_realtime_t *now, struct tm *tm, size_t size, const char *format); -static nxt_http_fields_hash_entry_t nxt_controller_request_fields[] = { +static nxt_http_field_proc_t nxt_controller_request_fields[] = { { nxt_string("Content-Length"), &nxt_controller_request_content_length, 0 }, - - { nxt_null_string, NULL, 0 } }; -static nxt_http_fields_hash_t *nxt_controller_fields_hash; +static nxt_lvlhsh_t nxt_controller_fields_hash; static nxt_uint_t nxt_controller_listening; static nxt_controller_conf_t nxt_controller_conf; @@ -114,14 +112,13 @@ nxt_port_handlers_t nxt_controller_process_port_handlers = { nxt_int_t nxt_controller_start(nxt_task_t *task, void *data) { - nxt_mp_t *mp; - nxt_int_t ret; - nxt_str_t *json; - nxt_runtime_t *rt; - nxt_conf_value_t *conf; - nxt_event_engine_t *engine; - nxt_conf_validation_t vldt; - nxt_http_fields_hash_t *hash; + nxt_mp_t *mp; + nxt_int_t ret; + nxt_str_t *json; + nxt_runtime_t *rt; + nxt_conf_value_t *conf; + nxt_event_engine_t *engine; + nxt_conf_validation_t vldt; rt = task->thread->runtime; @@ -132,13 +129,14 @@ nxt_controller_start(nxt_task_t *task, void *data) return NXT_ERROR; } - hash = nxt_http_fields_hash_create(nxt_controller_request_fields, - rt->mem_pool); - if (nxt_slow_path(hash == NULL)) { + ret = nxt_http_fields_hash(&nxt_controller_fields_hash, rt->mem_pool, + nxt_controller_request_fields, + nxt_nitems(nxt_controller_request_fields)); + + if (nxt_slow_path(ret != NXT_OK)) { return NXT_ERROR; } - nxt_controller_fields_hash = hash; nxt_queue_init(&nxt_controller_waiting_requests); json = data; @@ -429,8 +427,6 @@ nxt_controller_conn_init(nxt_task_t *task, void *obj, void *data) return; } - r->parser.fields_hash = nxt_controller_fields_hash; - b = nxt_buf_mem_alloc(c->mem_pool, 1024, 0); if (nxt_slow_path(b == NULL)) { nxt_controller_conn_free(task, c, NULL); @@ -505,7 +501,8 @@ nxt_controller_conn_read(nxt_task_t *task, void *obj, void *data) return; } - rc = nxt_http_fields_process(r->parser.fields, r, task->log); + rc = nxt_http_fields_process(r->parser.fields, &nxt_controller_fields_hash, + r); if (nxt_slow_path(rc != NXT_OK)) { nxt_controller_conn_close(task, c, r); @@ -727,19 +724,20 @@ nxt_controller_conn_free(nxt_task_t *task, void *obj, void *data) static nxt_int_t nxt_controller_request_content_length(void *ctx, nxt_http_field_t *field, - nxt_log_t *log) + uintptr_t data) { off_t length; nxt_controller_request_t *r; r = ctx; - length = nxt_off_t_parse(field->value.start, field->value.length); + length = nxt_off_t_parse(field->value, field->value_length); if (nxt_fast_path(length > 0)) { if (nxt_slow_path(length > NXT_SIZE_T_MAX)) { - nxt_log_error(NXT_LOG_ERR, log, "Content-Length is too big"); + nxt_log_error(NXT_LOG_ERR, &r->conn->log, + "Content-Length is too big"); return NXT_ERROR; } @@ -747,7 +745,7 @@ nxt_controller_request_content_length(void *ctx, nxt_http_field_t *field, return NXT_OK; } - nxt_log_error(NXT_LOG_ERR, log, "Content-Length is invalid"); + nxt_log_error(NXT_LOG_ERR, &r->conn->log, "Content-Length is invalid"); return NXT_ERROR; } diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c index 03662ef2..2913fa90 100644 --- a/src/nxt_http_parse.c +++ b/src/nxt_http_parse.c @@ -7,31 +7,6 @@ #include <nxt_main.h> -typedef struct { - nxt_http_field_handler_t handler; - uintptr_t data; - - union { - uint8_t str[8]; - uint64_t ui64; - } key[]; -} nxt_http_fields_hash_elt_t; - - -struct nxt_http_fields_hash_s { - size_t min_length; - size_t max_length; - void *long_fields; - nxt_http_fields_hash_elt_t *elts[]; -}; - - -#define nxt_http_fields_hash_next_elt(elt, n) \ - ((nxt_http_fields_hash_elt_t *) ((u_char *) (elt) \ - + sizeof(nxt_http_fields_hash_elt_t) \ - + n * 8)) - - static nxt_int_t nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos, u_char *end); static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp, @@ -44,13 +19,25 @@ static u_char *nxt_http_lookup_field_end(u_char *p, u_char *end); static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, u_char *end); -static void nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *hash, - uint64_t key[4], nxt_http_field_t *field); -static void nxt_http_fields_hash_lookup_long(nxt_http_fields_hash_t *hash, - nxt_http_field_t *field); - static nxt_int_t nxt_http_parse_complex_target(nxt_http_request_parse_t *rp); +static nxt_int_t nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data); +static void *nxt_http_field_hash_alloc(void *pool, size_t size); +static void nxt_http_field_hash_free(void *pool, void *p); + +static nxt_int_t nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, + void *data); + + +#define NXT_HTTP_MAX_FIELD_NAME 0xff +#define NXT_HTTP_MAX_FIELD_VALUE NXT_INT32_T_MAX + +#define NXT_HTTP_FIELD_LVLHSH_SHIFT 5 + +#define NXT_HTTP_FIELD_HASH_INIT 159406 +#define nxt_http_field_hash_char(h, c) (((h) << 4) + (h) + (c)) +#define nxt_http_field_hash_end(h) (((h) >> 16) ^ (h)) + typedef enum { NXT_HTTP_TARGET_SPACE = 1, /* \s */ @@ -127,6 +114,22 @@ nxt_http_parse_target(u_char **pos, u_char *end) nxt_int_t +nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp) +{ + rp->mem_pool = mp; + + rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t)); + if (nxt_slow_path(rp->fields == NULL)){ + return NXT_ERROR; + } + + rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; + + return NXT_OK; +} + + +nxt_int_t nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b) { nxt_int_t rc; @@ -480,8 +483,9 @@ static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos, u_char *end) { - u_char *p, ch, c; - size_t i, size; + u_char *p, c; + size_t len; + uint32_t hash; static const u_char normal[256] nxt_aligned(64) = "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" @@ -496,62 +500,78 @@ nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"; - p = *pos; + p = *pos + rp->field_name.length; + hash = rp->field_hash; - size = end - p; - i = rp->field_name.length; + while (nxt_fast_path(end - p >= 8)) { - while (nxt_fast_path(size - i >= 8)) { - -#define nxt_field_name_test_char(i) \ +#define nxt_field_name_test_char(ch) \ \ - ch = p[i]; \ c = normal[ch]; \ \ if (nxt_slow_path(c == '\0')) { \ + p = &(ch); \ goto name_end; \ } \ \ - rp->field_key.str[i % 32] = c; + hash = nxt_http_field_hash_char(hash, c); /* enddef */ - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; + nxt_field_name_test_char(p[0]); + nxt_field_name_test_char(p[1]); + nxt_field_name_test_char(p[2]); + nxt_field_name_test_char(p[3]); + + nxt_field_name_test_char(p[4]); + nxt_field_name_test_char(p[5]); + nxt_field_name_test_char(p[6]); + nxt_field_name_test_char(p[7]); - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; - nxt_field_name_test_char(i); i++; + p += 8; } - while (nxt_fast_path(i != size)) { - nxt_field_name_test_char(i); i++; + while (nxt_fast_path(p != end)) { + nxt_field_name_test_char(*p); p++; } - rp->field_name.length = i; + len = p - *pos; + + if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { + return NXT_ERROR; + } + + rp->field_hash = hash; + rp->field_name.length = len; + rp->handler = &nxt_http_parse_field_name; return NXT_AGAIN; name_end: - if (nxt_fast_path(ch == ':')) { - if (nxt_slow_path(i == 0)) { + if (nxt_fast_path(*p == ':')) { + if (nxt_slow_path(p == *pos)) { return NXT_ERROR; } - *pos = &p[i] + 1; + len = p - *pos; - rp->field_name.length = i; - rp->field_name.start = p; + if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { + return NXT_ERROR; + } + + rp->field_hash = hash; + + rp->field_name.length = len; + rp->field_name.start = *pos; + + *pos = p + 1; return nxt_http_parse_field_value(rp, pos, end); } - if (nxt_slow_path(i != 0)) { + if (nxt_slow_path(p != *pos)) { return NXT_ERROR; } @@ -564,6 +584,7 @@ nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos, u_char *end) { u_char *p, ch; + size_t len; p = *pos; @@ -589,7 +610,13 @@ nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos, p = nxt_http_lookup_field_end(p, end); if (nxt_slow_path(p == end)) { - rp->field_value.length = p - *pos; + len = p - *pos; + + if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { + return NXT_ERROR; + } + + rp->field_value.length = len; rp->handler = &nxt_http_parse_field_value; return NXT_AGAIN; } @@ -611,7 +638,13 @@ nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos, } } - rp->field_value.length = p - *pos; + len = p - *pos; + + if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { + return NXT_ERROR; + } + + rp->field_value.length = len; rp->field_value.start = *pos; *pos = p; @@ -714,13 +747,15 @@ nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, return NXT_ERROR; } - field->name = rp->field_name; - field->value = rp->field_value; + field->hash = nxt_http_field_hash_end(rp->field_hash); + field->skip = 0; - nxt_http_fields_hash_lookup(rp->fields_hash, rp->field_key.ui64, - field); + field->name_length = rp->field_name.length; + field->value_length = rp->field_value.length; + field->name = rp->field_name.start; + field->value = rp->field_value.start; - nxt_memzero(rp->field_key.str, 32); + rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; rp->field_name.length = 0; rp->field_value.length = 0; @@ -736,228 +771,6 @@ nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, } -nxt_http_fields_hash_t * -nxt_http_fields_hash_create(nxt_http_fields_hash_entry_t *entries, - nxt_mp_t *mp) -{ - size_t min_length, max_length, length, size; - nxt_uint_t i, j, n; - nxt_http_fields_hash_t *hash; - nxt_http_fields_hash_elt_t *elt; - - min_length = 32 + 1; - max_length = 0; - - for (i = 0; entries[i].handler != NULL; i++) { - length = entries[i].name.length; - - if (length > 32) { - /* TODO */ - return NULL; - } - - min_length = nxt_min(length, min_length); - max_length = nxt_max(length, max_length); - } - - size = sizeof(nxt_http_fields_hash_t); - - if (min_length <= 32) { - size += (max_length - min_length + 1) - * sizeof(nxt_http_fields_hash_elt_t *); - } - - hash = nxt_mp_zget(mp, size); - if (nxt_slow_path(hash == NULL)) { - return NULL; - } - - hash->min_length = min_length; - hash->max_length = max_length; - - for (i = 0; entries[i].handler != NULL; i++) { - length = entries[i].name.length; - elt = hash->elts[length - min_length]; - - if (elt != NULL) { - continue; - } - - n = 1; - - for (j = i + 1; entries[j].handler != NULL; j++) { - if (length == entries[j].name.length) { - n++; - } - } - - size = sizeof(nxt_http_fields_hash_elt_t) + nxt_align_size(length, 8); - - elt = nxt_mp_zget(mp, n * size + sizeof(nxt_http_fields_hash_elt_t)); - - if (nxt_slow_path(elt == NULL)) { - return NULL; - } - - hash->elts[length - min_length] = elt; - - for (j = i; entries[j].handler != NULL; j++) { - if (length != entries[j].name.length) { - continue; - } - - elt->handler = entries[j].handler; - elt->data = entries[j].data; - - nxt_memcpy_lowcase(elt->key->str, entries[j].name.start, length); - - n--; - - if (n == 0) { - break; - } - - elt = nxt_pointer_to(elt, size); - } - } - - return hash; -} - - -static void -nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *hash, uint64_t key[4], - nxt_http_field_t *field) -{ - nxt_http_fields_hash_elt_t *elt; - - if (hash == NULL || field->name.length < hash->min_length) { - goto not_found; - } - - if (field->name.length > hash->max_length) { - - if (field->name.length > 32 && hash->long_fields != NULL) { - nxt_http_fields_hash_lookup_long(hash, field); - return; - } - - goto not_found; - } - - elt = hash->elts[field->name.length - hash->min_length]; - - if (elt == NULL) { - goto not_found; - } - - switch ((field->name.length + 7) / 8) { - case 1: - do { - if (elt->key[0].ui64 == key[0]) { - break; - } - - elt = nxt_http_fields_hash_next_elt(elt, 1); - - } while (elt->handler != NULL); - - break; - - case 2: - do { - if (elt->key[0].ui64 == key[0] - && elt->key[1].ui64 == key[1]) - { - break; - } - - elt = nxt_http_fields_hash_next_elt(elt, 2); - - } while (elt->handler != NULL); - - break; - - case 3: - do { - if (elt->key[0].ui64 == key[0] - && elt->key[1].ui64 == key[1] - && elt->key[2].ui64 == key[2]) - { - break; - } - - elt = nxt_http_fields_hash_next_elt(elt, 3); - - } while (elt->handler != NULL); - - break; - - case 4: - do { - if (elt->key[0].ui64 == key[0] - && elt->key[1].ui64 == key[1] - && elt->key[2].ui64 == key[2] - && elt->key[3].ui64 == key[3]) - { - break; - } - - elt = nxt_http_fields_hash_next_elt(elt, 4); - - } while (elt->handler != NULL); - - break; - - default: - nxt_unreachable(); - } - - field->handler = elt->handler; - field->data = elt->data; - - return; - -not_found: - - field->handler = NULL; - field->data = 0; -} - - -static void -nxt_http_fields_hash_lookup_long(nxt_http_fields_hash_t *hash, - nxt_http_field_t *field) -{ - /* TODO */ - - field->handler = NULL; - field->data = 0; -} - - -nxt_int_t -nxt_http_fields_process(nxt_list_t *fields, void *ctx, nxt_log_t *log) -{ - nxt_int_t rc; - nxt_http_field_t *field; - - nxt_list_each(field, fields) { - - if (field->handler != NULL) { - rc = field->handler(ctx, field, log); - - if (rc != NXT_OK) { - return rc; - } - } - - } nxt_list_loop; - - return NXT_OK; -} - - #define \ nxt_http_is_normal(c) \ (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0)) @@ -1260,3 +1073,163 @@ done: return NXT_OK; } + + +static const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = { + NXT_LVLHSH_BUCKET_SIZE(64), + { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 }, + nxt_http_field_hash_test, + nxt_http_field_hash_alloc, + nxt_http_field_hash_free, +}; + + +static nxt_int_t +nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data) +{ + nxt_http_field_proc_t *field; + + field = data; + + if (nxt_strcasestr_eq(&lhq->key, &field->name)) { + return NXT_OK; + } + + return NXT_DECLINED; +} + + +static void * +nxt_http_field_hash_alloc(void *pool, size_t size) +{ + return nxt_mp_align(pool, size, size); +} + + +static void +nxt_http_field_hash_free(void *pool, void *p) +{ + nxt_mp_free(pool, p); +} + + +static nxt_int_t +nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data) +{ + return NXT_OK; +} + + +nxt_int_t +nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, + nxt_http_field_proc_t items[], nxt_uint_t count) +{ + u_char ch; + uint32_t key; + nxt_str_t *name; + nxt_int_t ret; + nxt_uint_t i, j; + nxt_lvlhsh_query_t lhq; + + lhq.replace = 0; + lhq.proto = &nxt_http_fields_hash_proto; + lhq.pool = mp; + + for (i = 0; i < count; i++) { + key = NXT_HTTP_FIELD_HASH_INIT; + name = &items[i].name; + + for (j = 0; j < name->length; j++) { + ch = nxt_lowcase(name->start[j]); + key = nxt_http_field_hash_char(key, ch); + } + + lhq.key_hash = nxt_http_field_hash_end(key) & 0xffff; + lhq.key = *name; + lhq.value = &items[i]; + + ret = nxt_lvlhsh_insert(hash, &lhq); + + if (nxt_slow_path(ret != NXT_OK)) { + return NXT_ERROR; + } + } + + return NXT_OK; +} + + +nxt_uint_t +nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, + nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level) +{ + u_char ch; + uint32_t key, mask; + nxt_str_t *name; + nxt_uint_t colls, i, j; + nxt_lvlhsh_proto_t proto; + nxt_lvlhsh_query_t lhq; + + proto = nxt_http_fields_hash_proto; + proto.test = nxt_http_field_hash_collision; + + lhq.replace = 0; + lhq.proto = &proto; + lhq.pool = mp; + + mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xffff; + + colls = 0; + + for (i = 0; i < count; i++) { + key = NXT_HTTP_FIELD_HASH_INIT; + name = &items[i].name; + + for (j = 0; j < name->length; j++) { + ch = nxt_lowcase(name->start[j]); + key = nxt_http_field_hash_char(key, ch); + } + + lhq.key_hash = nxt_http_field_hash_end(key) & mask; + + if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) { + colls++; + } + } + + return colls; +} + + +nxt_int_t +nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx) +{ + nxt_int_t ret; + nxt_http_field_t *field; + nxt_lvlhsh_query_t lhq; + nxt_http_field_proc_t *proc; + + lhq.proto = &nxt_http_fields_hash_proto; + + nxt_list_each(field, fields) { + + lhq.key_hash = field->hash; + lhq.key.length = field->name_length; + lhq.key.start = field->name; + + if (nxt_lvlhsh_find(hash, &lhq) != NXT_OK) { + continue; + } + + proc = lhq.value; + + ret = proc->handler(ctx, field, proc->data); + + if (nxt_slow_path(ret != NXT_OK)) { + return ret; + } + + } nxt_list_loop; + + return NXT_OK; +} diff --git a/src/nxt_http_parse.h b/src/nxt_http_parse.h index 2baa36ce..da664ce9 100644 --- a/src/nxt_http_parse.h +++ b/src/nxt_http_parse.h @@ -14,8 +14,8 @@ typedef struct nxt_http_fields_hash_s nxt_http_fields_hash_t; typedef union { - u_char str[8]; - uint64_t ui64; + u_char str[8]; + uint64_t ui64; } nxt_http_ver_t; @@ -38,18 +38,13 @@ struct nxt_http_request_parse_s { nxt_http_ver_t version; - union { - uint8_t str[32]; - uint64_t ui64[4]; - } field_key; + nxt_list_t *fields; + nxt_mp_t *mem_pool; nxt_str_t field_name; nxt_str_t field_value; - nxt_http_fields_hash_t *fields_hash; - - nxt_list_t *fields; - nxt_mp_t *mem_pool; + uint32_t field_hash; /* target with "/." */ unsigned complex_target:1; @@ -64,45 +59,37 @@ struct nxt_http_request_parse_s { typedef nxt_int_t (*nxt_http_field_handler_t)(void *ctx, nxt_http_field_t *field, - nxt_log_t *log); + uintptr_t data); typedef struct { nxt_str_t name; nxt_http_field_handler_t handler; uintptr_t data; -} nxt_http_fields_hash_entry_t; +} nxt_http_field_proc_t; struct nxt_http_field_s { - nxt_str_t name; - nxt_str_t value; - nxt_http_field_handler_t handler; - uintptr_t data; + uint16_t hash; + uint8_t skip; /* 1 bit */ + uint8_t name_length; + uint32_t value_length; + u_char *name; + u_char *value; }; -nxt_inline nxt_int_t -nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp) -{ - rp->mem_pool = mp; - - rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t)); - if (nxt_slow_path(rp->fields == NULL)){ - return NXT_ERROR; - } - - return NXT_OK; -} - - +nxt_int_t nxt_http_parse_request_init(nxt_http_request_parse_t *rp, + nxt_mp_t *mp); nxt_int_t nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b); -nxt_http_fields_hash_t *nxt_http_fields_hash_create( - nxt_http_fields_hash_entry_t *entries, nxt_mp_t *mp); -nxt_int_t nxt_http_fields_process(nxt_list_t *fields, void *ctx, - nxt_log_t *log); +nxt_int_t nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, + nxt_http_field_proc_t items[], nxt_uint_t count); +nxt_uint_t nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, + nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level); +nxt_int_t nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, + void *ctx); #endif /* _NXT_HTTP_PARSER_H_INCLUDED_ */ diff --git a/src/nxt_router.c b/src/nxt_router.c index 7b52876a..103ba78c 100644 --- a/src/nxt_router.c +++ b/src/nxt_router.c @@ -3327,9 +3327,9 @@ nxt_python_prepare_msg(nxt_task_t *task, nxt_app_request_t *r, NXT_WRITE(&h->content_length); nxt_list_each(field, h->fields) { - RC(nxt_app_msg_write_prefixed_upcase(task, wmsg, - &prefix, &field->name)); - NXT_WRITE(&field->value); + RC(nxt_app_msg_write_prefixed_upcase(task, wmsg, &prefix, field->name, + field->name_length)); + RC(nxt_app_msg_write(task, wmsg, field->value, field->value_length)); } nxt_list_loop; @@ -3431,9 +3431,9 @@ nxt_php_prepare_msg(nxt_task_t *task, nxt_app_request_t *r, } nxt_list_each(field, h->fields) { - RC(nxt_app_msg_write_prefixed_upcase(task, wmsg, - &prefix, &field->name)); - NXT_WRITE(&field->value); + RC(nxt_app_msg_write_prefixed_upcase(task, wmsg, &prefix, field->name, + field->name_length)); + RC(nxt_app_msg_write(task, wmsg, field->value, field->value_length)); } nxt_list_loop; @@ -3511,8 +3511,8 @@ nxt_go_prepare_msg(nxt_task_t *task, nxt_app_request_t *r, nxt_app_wmsg_t *wmsg) RC(nxt_app_msg_write_size(task, wmsg, h->parsed_content_length)); nxt_list_each(field, h->fields) { - NXT_WRITE(&field->name); - NXT_WRITE(&field->value); + RC(nxt_app_msg_write(task, wmsg, field->name, field->name_length)); + RC(nxt_app_msg_write(task, wmsg, field->value, field->value_length)); } nxt_list_loop; diff --git a/src/test/nxt_http_parse_test.c b/src/test/nxt_http_parse_test.c index d2af4245..9af3acad 100644 --- a/src/test/nxt_http_parse_test.c +++ b/src/test/nxt_http_parse_test.c @@ -47,8 +47,7 @@ typedef struct { static nxt_int_t nxt_http_parse_test_run(nxt_http_request_parse_t *rp, nxt_str_t *request); static nxt_int_t nxt_http_parse_test_bench(nxt_thread_t *thr, - nxt_str_t *request, nxt_http_fields_hash_t *hash, const char *name, - nxt_uint_t n); + nxt_str_t *request, nxt_lvlhsh_t *hash, const char *name, nxt_uint_t n); static nxt_int_t nxt_http_parse_test_request_line(nxt_http_request_parse_t *rp, nxt_http_parse_test_data_t *data, nxt_str_t *request, nxt_log_t *log); @@ -57,7 +56,7 @@ static nxt_int_t nxt_http_parse_test_fields(nxt_http_request_parse_t *rp, static nxt_int_t nxt_http_test_header_return(void *ctx, nxt_http_field_t *field, - nxt_log_t *log); + uintptr_t data); static nxt_http_parse_test_case_t nxt_http_test_cases[] = { @@ -290,24 +289,27 @@ static nxt_http_parse_test_case_t nxt_http_test_cases[] = { }; -static nxt_http_fields_hash_entry_t nxt_http_test_fields[] = { +static nxt_http_field_proc_t nxt_http_test_fields[] = { { nxt_string("X-Bad-Header"), &nxt_http_test_header_return, - (uintptr_t) NXT_ERROR }, + NXT_ERROR }, { nxt_string("X-Good-Header"), &nxt_http_test_header_return, - (uintptr_t) NXT_OK }, - - { nxt_null_string, NULL, 0 } + NXT_OK }, }; -static nxt_http_fields_hash_entry_t nxt_http_test_bench_fields[] = { +static nxt_lvlhsh_t nxt_http_test_fields_hash; + + +static nxt_http_field_proc_t nxt_http_test_bench_fields[] = { { nxt_string("Host"), &nxt_http_test_header_return, NXT_OK }, { nxt_string("User-Agent"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Accept"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("Accept-Encoding"), &nxt_http_test_header_return, NXT_OK }, { nxt_string("Accept-Language"), @@ -316,22 +318,62 @@ static nxt_http_fields_hash_entry_t nxt_http_test_bench_fields[] = { &nxt_http_test_header_return, NXT_OK }, { nxt_string("Content-Length"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Content-Range"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("Content-Type"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Cookie"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Range"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("If-Range"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Transfer-Encoding"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Expect"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Via"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("If-Modified-Since"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("If-Unmodified-Since"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("If-Match"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("If-None-Match"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Referer"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("Date"), &nxt_http_test_header_return, NXT_OK }, { nxt_string("Upgrade"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Authorization"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Keep-Alive"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("X-Forwarded-For"), &nxt_http_test_header_return, NXT_OK }, + { nxt_string("X-Forwarded-Host"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("X-Forwarded-Proto"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("X-Http-Method-Override"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("X-Real-IP"), + &nxt_http_test_header_return, NXT_OK }, { nxt_string("X-Request-ID"), &nxt_http_test_header_return, NXT_OK }, - - { nxt_null_string, NULL, 0 } + { nxt_string("TE"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Pragma"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Cache-Control"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Origin"), + &nxt_http_test_header_return, NXT_OK }, + { nxt_string("Upgrade-Insecure-Requests"), + &nxt_http_test_header_return, NXT_OK }, }; @@ -418,8 +460,8 @@ nxt_http_parse_test(nxt_thread_t *thr) { nxt_mp_t *mp, *mp_temp; nxt_int_t rc; - nxt_uint_t i; - nxt_http_fields_hash_t *hash; + nxt_uint_t i, colls, lvl_colls; + nxt_lvlhsh_t hash; nxt_http_request_parse_t rp; nxt_http_parse_test_case_t *test; @@ -430,8 +472,10 @@ nxt_http_parse_test(nxt_thread_t *thr) return NXT_ERROR; } - hash = nxt_http_fields_hash_create(nxt_http_test_fields, mp); - if (hash == NULL) { + rc = nxt_http_fields_hash(&nxt_http_test_fields_hash, mp, + nxt_http_test_fields, + nxt_nitems(nxt_http_test_fields)); + if (rc != NXT_OK) { return NXT_ERROR; } @@ -449,8 +493,6 @@ nxt_http_parse_test(nxt_thread_t *thr) return NXT_ERROR; } - rp.fields_hash = hash; - rc = nxt_http_parse_test_run(&rp, &test->request); if (rc != test->result) { @@ -473,20 +515,41 @@ nxt_http_parse_test(nxt_thread_t *thr) nxt_log_error(NXT_LOG_NOTICE, thr->log, "http parse test passed"); - hash = nxt_http_fields_hash_create(nxt_http_test_bench_fields, mp); - if (hash == NULL) { + nxt_memzero(&hash, sizeof(nxt_lvlhsh_t)); + + colls = nxt_http_fields_hash_collisions(&hash, mp, + nxt_http_test_bench_fields, + nxt_nitems(nxt_http_test_bench_fields), + 0); + + nxt_memzero(&hash, sizeof(nxt_lvlhsh_t)); + + lvl_colls = nxt_http_fields_hash_collisions(&hash, mp, + nxt_http_test_bench_fields, + nxt_nitems(nxt_http_test_bench_fields), + 1); + + nxt_log_error(NXT_LOG_NOTICE, thr->log, + "http parse test hash collisions %ui out of %ui, level: %ui", + colls, nxt_nitems(nxt_http_test_bench_fields), lvl_colls); + + nxt_memzero(&hash, sizeof(nxt_lvlhsh_t)); + + rc = nxt_http_fields_hash(&hash, mp, nxt_http_test_bench_fields, + nxt_nitems(nxt_http_test_bench_fields)); + if (rc != NXT_OK) { return NXT_ERROR; } if (nxt_http_parse_test_bench(thr, &nxt_http_test_simple_request, - hash, "simple", 10000000) + &hash, "simple", 1000000) != NXT_OK) { return NXT_ERROR; } if (nxt_http_parse_test_bench(thr, &nxt_http_test_big_request, - hash, "big", 100000) + &hash, "big", 100000) != NXT_OK) { return NXT_ERROR; @@ -521,7 +584,7 @@ nxt_http_parse_test_run(nxt_http_request_parse_t *rp, nxt_str_t *request) static nxt_int_t nxt_http_parse_test_bench(nxt_thread_t *thr, nxt_str_t *request, - nxt_http_fields_hash_t *hash, const char *name, nxt_uint_t n) + nxt_lvlhsh_t *hash, const char *name, nxt_uint_t n) { nxt_mp_t *mp; nxt_nsec_t start, end; @@ -551,8 +614,6 @@ nxt_http_parse_test_bench(nxt_thread_t *thr, nxt_str_t *request, return NXT_ERROR; } - rp.fields_hash = hash; - buf.pos = buf.start; buf.free = buf.end; @@ -562,7 +623,7 @@ nxt_http_parse_test_bench(nxt_thread_t *thr, nxt_str_t *request, return NXT_ERROR; } - if (nxt_slow_path(nxt_http_fields_process(rp.fields, NULL, thr->log) + if (nxt_slow_path(nxt_http_fields_process(rp.fields, hash, NULL) != NXT_OK)) { nxt_log_alert(thr->log, "http parse %s request bench failed " @@ -693,7 +754,7 @@ nxt_http_parse_test_fields(nxt_http_request_parse_t *rp, { nxt_int_t rc; - rc = nxt_http_fields_process(rp->fields, NULL, log); + rc = nxt_http_fields_process(rp->fields, &nxt_http_test_fields_hash, NULL); if (rc != data->result) { nxt_log_alert(log, "http parse test hash failed:\n" @@ -708,7 +769,7 @@ nxt_http_parse_test_fields(nxt_http_request_parse_t *rp, static nxt_int_t -nxt_http_test_header_return(void *ctx, nxt_http_field_t *field, nxt_log_t *log) +nxt_http_test_header_return(void *ctx, nxt_http_field_t *field, uintptr_t data) { - return (nxt_int_t) field->data; + return data; } |