summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorValentin Bartenev <vbart@nginx.com>2017-12-25 17:04:22 +0300
committerValentin Bartenev <vbart@nginx.com>2017-12-25 17:04:22 +0300
commit8830d732614276b015c56fec2fb3cb77de9f8441 (patch)
tree8d0408cdf4002413d6a9670a3e7025ab02ffd675
parent392abd03e5cbb4f6608403364721b5c1f26d9f06 (diff)
downloadunit-8830d732614276b015c56fec2fb3cb77de9f8441.tar.gz
unit-8830d732614276b015c56fec2fb3cb77de9f8441.tar.bz2
HTTP parser: reworked header fields handling.
-rw-r--r--src/nxt_application.c91
-rw-r--r--src/nxt_application.h2
-rw-r--r--src/nxt_controller.c46
-rw-r--r--src/nxt_http_parse.c545
-rw-r--r--src/nxt_http_parse.h55
-rw-r--r--src/nxt_router.c16
-rw-r--r--src/test/nxt_http_parse_test.c117
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;
}