HTTP parser: reworked header fields handling.

1 files changed, 259 insertions, 286 deletions

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;
+}