HTTP parser: reduced memory consumption of header fields list.

4 files changed, 162 insertions, 156 deletions

diff --git a/src/nxt_controller.c b/src/nxt_controller.c
index b098d581..f96f93ef 100644
--- a/src/nxt_controller.c
+++ b/src/nxt_controller.c
@@ -51,7 +51,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, uintptr_t data, nxt_log_t *log);
+    nxt_http_field_t *field, nxt_log_t *log);
 
 static void nxt_controller_process_request(nxt_task_t *task,
     nxt_conn_t *c, nxt_controller_request_t *r);
@@ -213,6 +213,8 @@ 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);
@@ -287,8 +289,7 @@ nxt_controller_conn_read(nxt_task_t *task, void *obj, void *data)
         return;
     }
 
-    rc = nxt_http_fields_process(r->parser.fields, nxt_controller_fields_hash,
-                                 r, task->log);
+    rc = nxt_http_fields_process(r->parser.fields, r, task->log);
 
     if (nxt_slow_path(rc != NXT_OK)) {
         nxt_controller_conn_close(task, c, r);
@@ -512,7 +513,7 @@ 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,
-    uintptr_t data, nxt_log_t *log)
+    nxt_log_t *log)
 {
     off_t                     length;
     nxt_controller_request_t  *r;
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index d5a43bd0..21d8f99c 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -8,20 +8,21 @@
 
 
 typedef struct {
-    nxt_http_fields_hash_entry_t  *entry;
+    nxt_http_field_handler_t    handler;
+    uintptr_t                   data;
 
     union {
-        uint8_t                   str[8];
-        uint64_t                  ui64;
+        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[];
+    size_t                      min_length;
+    size_t                      max_length;
+    void                        *long_fields;
+    nxt_http_fields_hash_elt_t  *elts[];
 };
 
 
@@ -43,9 +44,10 @@ 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 nxt_http_fields_hash_entry_t *nxt_http_fields_hash_lookup_long(
-    nxt_http_fields_hash_t *hash, nxt_http_field_t *field);
+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);
 
 
 typedef enum {
@@ -426,7 +428,7 @@ nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
     p = *pos;
 
     size = end - p;
-    i = rp->field.name.length;
+    i = rp->field_name.length;
 
 #define nxt_http_parse_field_name_step                                        \
     {                                                                         \
@@ -437,7 +439,7 @@ nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
             goto name_end;                                                    \
         }                                                                     \
                                                                               \
-        rp->field.key.str[i % 32] = c;                                        \
+        rp->field_key.str[i % 32] = c;                                        \
         i++;                                                                  \
     }
 
@@ -459,7 +461,7 @@ nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
 
 #undef nxt_http_parse_field_name_step
 
-    rp->field.name.length = i;
+    rp->field_name.length = i;
     rp->handler = &nxt_http_parse_field_name;
 
     return NXT_AGAIN;
@@ -473,8 +475,8 @@ name_end:
 
         *pos = &p[i] + 1;
 
-        rp->field.name.length = i;
-        rp->field.name.start = p;
+        rp->field_name.length = i;
+        rp->field_name.start = p;
 
         return nxt_http_parse_field_value(rp, pos, end);
     }
@@ -511,13 +513,13 @@ nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
 
     *pos = p;
 
-    p += rp->field.value.length;
+    p += rp->field_value.length;
 
     for ( ;; ) {
         p = nxt_http_lookup_field_end(p, end);
 
         if (nxt_slow_path(p == end)) {
-            rp->field.value.length = p - *pos;
+            rp->field_value.length = p - *pos;
             rp->handler = &nxt_http_parse_field_value;
             return NXT_AGAIN;
         }
@@ -539,8 +541,8 @@ nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
         }
     }
 
-    rp->field.value.length = p - *pos;
-    rp->field.value.start = *pos;
+    rp->field_value.length = p - *pos;
+    rp->field_value.start = *pos;
 
     *pos = p;
 
@@ -634,16 +636,23 @@ nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos,
     if (nxt_fast_path(*p == '\n')) {
         *pos = p + 1;
 
-        if (rp->field.name.length != 0) {
+        if (rp->field_name.length != 0) {
             field = nxt_list_add(rp->fields);
 
             if (nxt_slow_path(field == NULL)) {
                 return NXT_ERROR;
             }
 
-            *field = rp->field;
+            field->name = rp->field_name;
+            field->value = rp->field_value;
+
+            nxt_http_fields_hash_lookup(rp->fields_hash, rp->field_key.ui64,
+                                        field);
 
-            nxt_memzero(&rp->field, sizeof(nxt_http_field_t));
+            nxt_memzero(rp->field_key.str, 32);
+
+            rp->field_name.length = 0;
+            rp->field_value.length = 0;
 
             rp->handler = &nxt_http_parse_field_name;
             return NXT_OK;
@@ -726,7 +735,8 @@ nxt_http_fields_hash_create(nxt_http_fields_hash_entry_t *entries,
                 continue;
             }
 
-            elt->entry = &entries[j];
+            elt->handler = entries[j].handler;
+            elt->data = entries[j].data;
 
             nxt_memcpy_lowcase(elt->key->str, entries[j].name.start, length);
 
@@ -744,86 +754,87 @@ nxt_http_fields_hash_create(nxt_http_fields_hash_entry_t *entries,
 }
 
 
-nxt_http_fields_hash_entry_t *
-nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *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 (field->name.length < hash->min_length) {
-        return NULL;
+    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) {
-            return nxt_http_fields_hash_lookup_long(hash, field);
+            nxt_http_fields_hash_lookup_long(hash, field);
+            return;
         }
 
-        return NULL;
+        goto not_found;
     }
 
     elt = hash->elts[field->name.length - hash->min_length];
 
     if (elt == NULL) {
-        return NULL;
+        goto not_found;
     }
 
     switch ((field->name.length + 7) / 8) {
     case 1:
         do {
-            if (elt->key[0].ui64 == field->key.ui64[0]) {
-                return elt->entry;
+            if (elt->key[0].ui64 == key[0]) {
+                break;
             }
 
             elt = nxt_http_fields_hash_next_elt(elt, 1);
 
-        } while (elt->entry != NULL);
+        } while (elt->handler != NULL);
 
         break;
 
     case 2:
         do {
-            if (elt->key[0].ui64 == field->key.ui64[0]
-                && elt->key[1].ui64 == field->key.ui64[1])
+            if (elt->key[0].ui64 == key[0]
+                && elt->key[1].ui64 == key[1])
             {
-                return elt->entry;
+                break;
             }
 
             elt = nxt_http_fields_hash_next_elt(elt, 2);
 
-        } while (elt->entry != NULL);
+        } while (elt->handler != NULL);
 
         break;
 
     case 3:
         do {
-            if (elt->key[0].ui64 == field->key.ui64[0]
-                && elt->key[1].ui64 == field->key.ui64[1]
-                && elt->key[2].ui64 == field->key.ui64[2])
+            if (elt->key[0].ui64 == key[0]
+                && elt->key[1].ui64 == key[1]
+                && elt->key[2].ui64 == key[2])
             {
-                return elt->entry;
+                break;
             }
 
             elt = nxt_http_fields_hash_next_elt(elt, 3);
 
-        } while (elt->entry != NULL);
+        } while (elt->handler != NULL);
 
         break;
 
     case 4:
         do {
-            if (elt->key[0].ui64 == field->key.ui64[0]
-                && elt->key[1].ui64 == field->key.ui64[1]
-                && elt->key[2].ui64 == field->key.ui64[2]
-                && elt->key[3].ui64 == field->key.ui64[3])
+            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])
             {
-                return elt->entry;
+                break;
             }
 
             elt = nxt_http_fields_hash_next_elt(elt, 4);
 
-        } while (elt->entry != NULL);
+        } while (elt->handler != NULL);
 
         break;
 
@@ -831,32 +842,39 @@ nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *hash,
         nxt_unreachable();
     }
 
-    return NULL;
+    field->handler = elt->handler;
+    field->data = elt->data;
+
+    return;
+
+not_found:
+
+    field->handler = NULL;
+    field->data = 0;
 }
 
 
-static nxt_http_fields_hash_entry_t *
+static void
 nxt_http_fields_hash_lookup_long(nxt_http_fields_hash_t *hash,
     nxt_http_field_t *field)
 {
     /* TODO */
-    return NULL;
+
+    field->handler = NULL;
+    field->data = 0;
 }
 
 
 nxt_int_t
-nxt_http_fields_process(nxt_list_t *fields, nxt_http_fields_hash_t *hash,
-    void *ctx, nxt_log_t *log)
+nxt_http_fields_process(nxt_list_t *fields, void *ctx, nxt_log_t *log)
 {
-    nxt_int_t                     rc;
-    nxt_http_field_t              *field;
-    nxt_http_fields_hash_entry_t  *entry;
+    nxt_int_t         rc;
+    nxt_http_field_t  *field;
 
     nxt_list_each(field, fields) {
-        entry = nxt_http_fields_hash_lookup(hash, field);
 
-        if (entry != NULL) {
-            rc = entry->handler(ctx, field, entry->data, log);
+        if (field->handler != NULL) {
+            rc = field->handler(ctx, field, log);
 
             if (rc != NXT_OK) {
                 return rc;
diff --git a/src/nxt_http_parse.h b/src/nxt_http_parse.h
index 590101be..da8c4ce6 100644
--- a/src/nxt_http_parse.h
+++ b/src/nxt_http_parse.h
@@ -9,58 +9,57 @@
 
 
 typedef struct nxt_http_request_parse_s  nxt_http_request_parse_t;
+typedef struct nxt_http_field_s          nxt_http_field_t;
 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;
 
 
-typedef struct {
-    union {
-        uint8_t       str[32];
-        uint64_t      ui64[4];
-    } key;
+struct nxt_http_request_parse_s {
+    nxt_int_t                 (*handler)(nxt_http_request_parse_t *rp,
+                                         u_char **pos, u_char *end);
 
-    nxt_str_t         name;
-    nxt_str_t         value;
-} nxt_http_field_t;
+    size_t                    offset;
 
+    nxt_str_t                 method;
 
-struct nxt_http_request_parse_s {
-    nxt_int_t         (*handler)(nxt_http_request_parse_t *rp,
-                                 u_char **pos, u_char *end);
+    u_char                    *target_start;
+    u_char                    *target_end;
+    u_char                    *exten_start;
+    u_char                    *args_start;
 
-    size_t            offset;
+    nxt_http_ver_t            version;
 
-    nxt_str_t         method;
+    union {
+        uint8_t               str[32];
+        uint64_t              ui64[4];
+    } field_key;
 
-    u_char            *target_start;
-    u_char            *target_end;
-    u_char            *exten_start;
-    u_char            *args_start;
+    nxt_str_t                 field_name;
+    nxt_str_t                 field_value;
 
-    nxt_http_ver_t    version;
+    nxt_http_fields_hash_t    *fields_hash;
 
-    nxt_http_field_t  field;
-    nxt_list_t        *fields;
+    nxt_list_t                *fields;
 
     /* target with "/." */
-    unsigned          complex_target:1;
+    unsigned                  complex_target:1;
     /* target with "%" */
-    unsigned          quoted_target:1;
+    unsigned                  quoted_target:1;
     /* target with " " */
-    unsigned          space_in_target:1;
+    unsigned                  space_in_target:1;
     /* target with "+" */
-    unsigned          plus_in_target:1;
+    unsigned                  plus_in_target:1;
 };
 
 
 typedef nxt_int_t (*nxt_http_field_handler_t)(void *ctx,
                                               nxt_http_field_t *field,
-                                              uintptr_t data, nxt_log_t *log);
+                                              nxt_log_t *log);
 
 
 typedef struct {
@@ -70,6 +69,14 @@ typedef struct {
 } nxt_http_fields_hash_entry_t;
 
 
+struct nxt_http_field_s {
+    nxt_str_t                 name;
+    nxt_str_t                 value;
+    nxt_http_field_handler_t  handler;
+    uintptr_t                 data;
+};
+
+
 nxt_inline nxt_int_t
 nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp)
 {
@@ -87,11 +94,8 @@ nxt_int_t nxt_http_parse_request(nxt_http_request_parse_t *rp,
 
 nxt_http_fields_hash_t *nxt_http_fields_hash_create(
     nxt_http_fields_hash_entry_t *entries, nxt_mp_t *mp);
-nxt_http_fields_hash_entry_t *nxt_http_fields_hash_lookup(
-    nxt_http_fields_hash_t *hash, nxt_http_field_t *field);
-
-nxt_int_t nxt_http_fields_process(nxt_list_t *fields,
-    nxt_http_fields_hash_t *hash, void *ctx, nxt_log_t *log);
+nxt_int_t nxt_http_fields_process(nxt_list_t *fields, void *ctx,
+                                  nxt_log_t *log);
 
 
 #endif /* _NXT_HTTP_PARSER_H_INCLUDED_ */
diff --git a/test/nxt_http_parse_unit_test.c b/test/nxt_http_parse_unit_test.c
index 2946b114..f264fe21 100644
--- a/test/nxt_http_parse_unit_test.c
+++ b/test/nxt_http_parse_unit_test.c
@@ -26,14 +26,12 @@ typedef struct {
 
 
 typedef struct {
-    nxt_http_fields_hash_entry_t  *entries;
-    nxt_int_t                     result;
 } nxt_http_parse_unit_test_fields_t;
 
 
 typedef union {
     void                                     *pointer;
-    nxt_http_parse_unit_test_fields_t        fields;
+    nxt_int_t                                result;
     nxt_http_parse_unit_test_request_line_t  request_line;
 } nxt_http_parse_unit_test_data_t;
 
@@ -62,21 +60,8 @@ static nxt_int_t nxt_http_parse_unit_test_fields(
     nxt_str_t *request, nxt_log_t *log);
 
 
-static nxt_int_t nxt_http_unit_test_header_return(void *ctx, nxt_http_field_t *field,
-    uintptr_t data, nxt_log_t *log);
-
-
-static nxt_http_fields_hash_entry_t  nxt_http_unit_test_fields[] = {
-    { nxt_string("X-Bad-Header"),
-      &nxt_http_unit_test_header_return,
-      (uintptr_t) NXT_ERROR },
-
-    { nxt_string("X-Good-Header"),
-      &nxt_http_unit_test_header_return,
-      (uintptr_t) NXT_OK },
-
-    { nxt_null_string, NULL, 0 }
-};
+static nxt_int_t nxt_http_unit_test_header_return(void *ctx,
+    nxt_http_field_t *field, nxt_log_t *log);
 
 
 static nxt_http_parse_unit_test_case_t  nxt_http_unit_test_cases[] = {
@@ -295,10 +280,7 @@ static nxt_http_parse_unit_test_case_t  nxt_http_unit_test_cases[] = {
                    "X-Good-Header: value\r\n\r\n"),
         NXT_DONE,
         &nxt_http_parse_unit_test_fields,
-        { .fields = {
-            nxt_http_unit_test_fields,
-            NXT_OK
-        }}
+        { .result = NXT_OK }
     },
     {
         nxt_string("GET / HTTP/1.1\r\n"
@@ -307,14 +289,24 @@ static nxt_http_parse_unit_test_case_t  nxt_http_unit_test_cases[] = {
                    "X-Bad-Header: value\r\n\r\n"),
         NXT_DONE,
         &nxt_http_parse_unit_test_fields,
-        { .fields = {
-            nxt_http_unit_test_fields,
-            NXT_ERROR
-        }}
+        { .result = NXT_ERROR }
     },
 };
 
 
+static nxt_http_fields_hash_entry_t  nxt_http_unit_test_fields[] = {
+    { nxt_string("X-Bad-Header"),
+      &nxt_http_unit_test_header_return,
+      (uintptr_t) NXT_ERROR },
+
+    { nxt_string("X-Good-Header"),
+      &nxt_http_unit_test_header_return,
+      (uintptr_t) NXT_OK },
+
+    { nxt_null_string, NULL, 0 }
+};
+
+
 static nxt_http_fields_hash_entry_t  nxt_http_unit_test_bench_fields[] = {
     { nxt_string("Host"),
       &nxt_http_unit_test_header_return, NXT_OK },
@@ -428,7 +420,7 @@ static nxt_str_t nxt_http_unit_test_big_request = nxt_string(
 nxt_int_t
 nxt_http_parse_unit_test(nxt_thread_t *thr)
 {
-    nxt_mp_t                         *mp;
+    nxt_mp_t                         *mp, *mp_temp;
     nxt_int_t                        rc;
     nxt_uint_t                       i;
     nxt_http_fields_hash_t           *hash;
@@ -437,20 +429,32 @@ nxt_http_parse_unit_test(nxt_thread_t *thr)
 
     nxt_thread_time_update(thr);
 
+    mp = nxt_mp_create(1024, 128, 256, 32);
+    if (mp == NULL) {
+        return NXT_ERROR;
+    }
+
+    hash = nxt_http_fields_hash_create(nxt_http_unit_test_fields, mp);
+    if (hash == NULL) {
+        return NXT_ERROR;
+    }
+
     for (i = 0; i < nxt_nitems(nxt_http_unit_test_cases); i++) {
         test = &nxt_http_unit_test_cases[i];
 
         nxt_memzero(&rp, sizeof(nxt_http_request_parse_t));
 
-        mp = nxt_mp_create(1024, 128, 256, 32);
-        if (mp == NULL) {
+        mp_temp = nxt_mp_create(1024, 128, 256, 32);
+        if (mp_temp == NULL) {
             return NXT_ERROR;
         }
 
-        if (nxt_http_parse_request_init(&rp, mp) != NXT_OK) {
+        if (nxt_http_parse_request_init(&rp, mp_temp) != NXT_OK) {
             return NXT_ERROR;
         }
 
+        rp.fields_hash = hash;
+
         rc = nxt_http_parse_unit_test_run(&rp, &test->request);
 
         if (rc != test->result) {
@@ -468,16 +472,11 @@ nxt_http_parse_unit_test(nxt_thread_t *thr)
             return NXT_ERROR;
         }
 
-        nxt_mp_destroy(mp);
+        nxt_mp_destroy(mp_temp);
     }
 
     nxt_log_error(NXT_LOG_NOTICE, thr->log, "http parse unit test passed");
 
-    mp = nxt_mp_create(1024, 128, 256, 32);
-    if (mp == NULL) {
-        return NXT_ERROR;
-    }
-
     hash = nxt_http_fields_hash_create(nxt_http_unit_test_bench_fields, mp);
     if (hash == NULL) {
         return NXT_ERROR;
@@ -557,6 +556,8 @@ nxt_http_parse_unit_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;
 
@@ -566,8 +567,7 @@ nxt_http_parse_unit_test_bench(nxt_thread_t *thr, nxt_str_t *request,
             return NXT_ERROR;
         }
 
-        if (nxt_slow_path(nxt_http_fields_process(rp.fields, hash, NULL,
-                                                  thr->log)
+        if (nxt_slow_path(nxt_http_fields_process(rp.fields, NULL, thr->log)
                           != NXT_OK))
         {
             nxt_log_alert(thr->log, "http parse unit %s request bench failed "
@@ -696,42 +696,25 @@ static nxt_int_t
 nxt_http_parse_unit_test_fields(nxt_http_request_parse_t *rp,
     nxt_http_parse_unit_test_data_t *data, nxt_str_t *request, nxt_log_t *log)
 {
-    nxt_mp_t                *mp;
-    nxt_int_t               rc;
-    nxt_http_fields_hash_t  *hash;
-
-    nxt_http_parse_unit_test_fields_t  *test = &data->fields;
-
-    mp = nxt_mp_create(1024, 128, 256, 32);
-    if (mp == NULL) {
-        return NXT_ERROR;
-    }
+    nxt_int_t  rc;
 
-    hash = nxt_http_fields_hash_create(test->entries, mp);
-    if (hash == NULL) {
-        nxt_log_alert(log, "unable to create hash");
-        return NXT_ERROR;
-    }
+    rc = nxt_http_fields_process(rp->fields, NULL, log);
 
-    rc = nxt_http_fields_process(rp->fields, hash, NULL, log);
-
-    if (rc != test->result) {
+    if (rc != data->result) {
         nxt_log_alert(log, "http parse unit test hash failed:\n"
                            " - request:\n\"%V\"\n"
                            " - result: %i (expected: %i)",
-                           request, rc, test->result);
+                           request, rc, data->result);
         return NXT_ERROR;
     }
 
-    nxt_mp_destroy(mp);
-
     return NXT_OK;
 }
 
 
 static nxt_int_t
 nxt_http_unit_test_header_return(void *ctx, nxt_http_field_t *field,
-    uintptr_t data, nxt_log_t *log)
+    nxt_log_t *log)
 {
-    return (nxt_int_t) data;
+    return (nxt_int_t) field->data;
 }