diff options
Diffstat (limited to 'web/server/h2o/libh2o/lib/http2/hpack.c')
| -rw-r--r-- | web/server/h2o/libh2o/lib/http2/hpack.c | 917 |
1 files changed, 917 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/lib/http2/hpack.c b/web/server/h2o/libh2o/lib/http2/hpack.c new file mode 100644 index 00000000..4adb15cd --- /dev/null +++ b/web/server/h2o/libh2o/lib/http2/hpack.c @@ -0,0 +1,917 @@ +/* + * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku, Fastly, Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include "h2o.h" +#include "h2o/http2.h" +#include "h2o/http2_internal.h" + +#define HEADER_TABLE_OFFSET 62 +#define HEADER_TABLE_ENTRY_SIZE_OFFSET 32 +#define STATUS_HEADER_MAX_SIZE 5 +#define CONTENT_LENGTH_HEADER_MAX_SIZE \ + (3 + sizeof(H2O_UINT64_LONGEST_STR) - 1) /* uses Literal Header Field without Indexing (RFC7541 6.2.2) */ + +struct st_h2o_hpack_static_table_entry_t { + const h2o_token_t *name; + const h2o_iovec_t value; +}; + +struct st_h2o_decode_header_result_t { + h2o_iovec_t *name; + h2o_iovec_t *value; +}; + +#include "hpack_huffman_table.h" +#include "hpack_static_table.h" + +static inline int value_is_part_of_static_table(const h2o_iovec_t *value) +{ + return &h2o_hpack_static_table[0].value <= value && + value <= &h2o_hpack_static_table[sizeof(h2o_hpack_static_table) / sizeof(h2o_hpack_static_table[0]) - 1].value; +} + +static h2o_iovec_t *alloc_buf(h2o_mem_pool_t *pool, size_t len) +{ + h2o_iovec_t *buf = h2o_mem_alloc_shared(pool, sizeof(h2o_iovec_t) + len + 1, NULL); + buf->base = (char *)buf + sizeof(h2o_iovec_t); + buf->len = len; + return buf; +} + +/* validate a header value against https://tools.ietf.org/html/rfc7230#section-3.2 */ +static int contains_invalid_field_value_char(const char *s, size_t len) +{ + /* all printable chars + horizontal tab */ + static const char valid_h2_field_value_char[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0-31 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 32-63 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 64-95 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 96-127 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 128-159 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 160-191 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 192-223 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 224-255 */ + }; + + for (; len != 0; ++s, --len) { + unsigned char ch = (unsigned char)*s; + if (!valid_h2_field_value_char[ch]) { + return 1; + } + } + return 0; +} + +static const char *err_found_upper_case_in_header_name = "found an upper-case letter in header name"; +static const char *soft_err_found_invalid_char_in_header_name = "found an invalid character in header name"; +static const char *soft_err_found_invalid_char_in_header_value = "found an invalid character in header value"; + +/* validate a header name against https://tools.ietf.org/html/rfc7230#section-3.2, + * in addition to that, we disallow upper case chars as well. + * This sets @err_desc for all invalid characters, but only returns true + * for upper case characters, this is because we return a protocol error + * in that case. */ +static const char *validate_header_name(const char *s, size_t len) +{ + const char *ret = NULL; + /* all printable chars, except upper case and separator characters */ + static const char valid_h2_header_name_char[] = { + 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-31 */ + 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 32-63 */ + 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, 1, 1, /* 64-95 */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, /* 96-127 */ + 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, /* 128-159 */ + 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, /* 160-191 */ + 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, /* 192-223 */ + 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, /* 224-255 */ + }; + + for (; len != 0; ++s, --len) { + unsigned char ch = (unsigned char)*s; + if (!valid_h2_header_name_char[ch]) { + if (ch - 'A' < 26U) { + return err_found_upper_case_in_header_name; + } + ret = soft_err_found_invalid_char_in_header_name; + } + } + return ret; +} + +static int32_t decode_int(const uint8_t **src, const uint8_t *src_end, size_t prefix_bits) +{ + int32_t value, mult; + uint8_t prefix_max = (1 << prefix_bits) - 1; + + if (*src >= src_end) + return -1; + + value = (uint8_t) * (*src)++ & prefix_max; + if (value != prefix_max) { + return value; + } + + /* we only allow at most 4 octets (excluding prefix) to be used as int (== 2**(4*7) == 2**28) */ + if (src_end - *src > 4) + src_end = *src + 4; + + value = prefix_max; + for (mult = 1;; mult *= 128) { + if (*src >= src_end) + return -1; + value += (**src & 127) * mult; + if ((*(*src)++ & 128) == 0) + return value; + } +} + +static char *huffdecode4(char *dst, uint8_t in, uint8_t *state, int *maybe_eos, uint8_t *seen_char_types) +{ + const nghttp2_huff_decode *entry = huff_decode_table[*state] + in; + + if ((entry->flags & NGHTTP2_HUFF_FAIL) != 0) + return NULL; + if ((entry->flags & NGHTTP2_HUFF_SYM) != 0) { + *dst++ = entry->sym; + *seen_char_types |= (entry->flags & NGHTTP2_HUFF_INVALID_CHARS); + } + *state = entry->state; + *maybe_eos = (entry->flags & NGHTTP2_HUFF_ACCEPTED) != 0; + + return dst; +} + +static h2o_iovec_t *decode_huffman(h2o_mem_pool_t *pool, const uint8_t *src, size_t len, uint8_t *seen_char_types) +{ + const uint8_t *src_end = src + len; + char *dst; + uint8_t state = 0; + int maybe_eos = 1; + h2o_iovec_t *dst_buf = alloc_buf(pool, len * 2); /* max compression ratio is >= 0.5 */ + + dst = dst_buf->base; + for (; src < src_end; src++) { + if ((dst = huffdecode4(dst, *src >> 4, &state, &maybe_eos, seen_char_types)) == NULL) + return NULL; + if ((dst = huffdecode4(dst, *src & 0xf, &state, &maybe_eos, seen_char_types)) == NULL) + return NULL; + } + + if (!maybe_eos) + return NULL; + + *dst = '\0'; + dst_buf->len = dst - dst_buf->base; + return dst_buf; +} + +static h2o_iovec_t *decode_string(h2o_mem_pool_t *pool, const uint8_t **src, const uint8_t *src_end, int is_header_name, + const char **err_desc) +{ + h2o_iovec_t *ret; + int is_huffman; + int32_t len; + + if (*src >= src_end) + return NULL; + + is_huffman = (**src & 0x80) != 0; + if ((len = decode_int(src, src_end, 7)) == -1) + return NULL; + + if (is_huffman) { + uint8_t hflags = 0; + if (*src + len > src_end) + return NULL; + if ((ret = decode_huffman(pool, *src, len, &hflags)) == NULL) + return NULL; + if (is_header_name) { + if (ret->len <= 0) { + return NULL; + } + /* pseudo-headers are checked later in `decode_header` */ + if (hflags & NGHTTP2_HUFF_INVALID_FOR_HEADER_NAME && ret->base[0] != ':') { + if (hflags & NGHTTP2_HUFF_UPPER_CASE_CHAR) { + *err_desc = err_found_upper_case_in_header_name; + return NULL; + } else { + *err_desc = soft_err_found_invalid_char_in_header_name; + } + } + } else { + if (hflags & NGHTTP2_HUFF_INVALID_FOR_HEADER_VALUE) { + *err_desc = soft_err_found_invalid_char_in_header_value; + } + } + } else { + if (*src + len > src_end) + return NULL; + if (is_header_name) { + /* pseudo-headers are checked later in `decode_header` */ + if (**src != (uint8_t)':') { + *err_desc = validate_header_name((char *)*src, len); + if (*err_desc == err_found_upper_case_in_header_name) { + return NULL; + } + } + } else { + if (contains_invalid_field_value_char((char *)*src, len)) { + *err_desc = soft_err_found_invalid_char_in_header_value; + } + } + ret = alloc_buf(pool, len); + memcpy(ret->base, *src, len); + ret->base[len] = '\0'; + } + *src += len; + + return ret; +} + +static void header_table_evict_one(h2o_hpack_header_table_t *table) +{ + struct st_h2o_hpack_header_table_entry_t *entry; + assert(table->num_entries != 0); + + entry = h2o_hpack_header_table_get(table, --table->num_entries); + table->hpack_size -= entry->name->len + entry->value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET; + if (!h2o_iovec_is_token(entry->name)) + h2o_mem_release_shared(entry->name); + if (!value_is_part_of_static_table(entry->value)) + h2o_mem_release_shared(entry->value); + memset(entry, 0, sizeof(*entry)); +} + +static struct st_h2o_hpack_header_table_entry_t *header_table_add(h2o_hpack_header_table_t *table, size_t size_add, + size_t max_num_entries) +{ + /* adjust the size */ + while (table->num_entries != 0 && table->hpack_size + size_add > table->hpack_capacity) + header_table_evict_one(table); + while (max_num_entries <= table->num_entries) + header_table_evict_one(table); + if (table->num_entries == 0) { + assert(table->hpack_size == 0); + if (size_add > table->hpack_capacity) + return NULL; + } + table->hpack_size += size_add; + + /* grow the entries if full */ + if (table->num_entries == table->entry_capacity) { + size_t new_capacity = table->num_entries * 2; + if (new_capacity < 16) + new_capacity = 16; + struct st_h2o_hpack_header_table_entry_t *new_entries = + h2o_mem_alloc(new_capacity * sizeof(struct st_h2o_hpack_header_table_entry_t)); + if (table->num_entries != 0) { + size_t src_index = table->entry_start_index, dst_index = 0; + do { + new_entries[dst_index] = table->entries[src_index]; + ++dst_index; + src_index = (src_index + 1) % table->entry_capacity; + } while (dst_index != table->num_entries); + } + memset(new_entries + table->num_entries, 0, sizeof(*new_entries) * (new_capacity - table->num_entries)); + free(table->entries); + table->entries = new_entries; + table->entry_capacity = new_capacity; + table->entry_start_index = 0; + } + + ++table->num_entries; + table->entry_start_index = (table->entry_start_index + table->entry_capacity - 1) % table->entry_capacity; + return table->entries + table->entry_start_index; +} + +static int decode_header(h2o_mem_pool_t *pool, struct st_h2o_decode_header_result_t *result, + h2o_hpack_header_table_t *hpack_header_table, const uint8_t **const src, const uint8_t *src_end, + const char **err_desc) +{ + int32_t index = 0; + int value_is_indexed = 0, do_index = 0; + +Redo: + if (*src >= src_end) + return H2O_HTTP2_ERROR_COMPRESSION; + + /* determine the mode and handle accordingly */ + if (**src >= 128) { + /* indexed header field representation */ + if ((index = decode_int(src, src_end, 7)) <= 0) + return H2O_HTTP2_ERROR_COMPRESSION; + value_is_indexed = 1; + } else if (**src >= 64) { + /* literal header field with incremental handling */ + if (**src == 64) { + ++*src; + } else if ((index = decode_int(src, src_end, 6)) <= 0) { + return H2O_HTTP2_ERROR_COMPRESSION; + } + do_index = 1; + } else if (**src < 32) { + /* literal header field without indexing / never indexed */ + if ((**src & 0xf) == 0) { + ++*src; + } else if ((index = decode_int(src, src_end, 4)) <= 0) { + return H2O_HTTP2_ERROR_COMPRESSION; + } + } else { + /* size update */ + int new_apacity; + if ((new_apacity = decode_int(src, src_end, 5)) < 0) { + return H2O_HTTP2_ERROR_COMPRESSION; + } + if (new_apacity > hpack_header_table->hpack_max_capacity) { + return H2O_HTTP2_ERROR_COMPRESSION; + } + hpack_header_table->hpack_capacity = new_apacity; + while (hpack_header_table->num_entries != 0 && hpack_header_table->hpack_size > hpack_header_table->hpack_capacity) { + header_table_evict_one(hpack_header_table); + } + goto Redo; + } + + /* determine the header */ + if (index > 0) { + /* existing name (and value?) */ + if (index < HEADER_TABLE_OFFSET) { + result->name = (h2o_iovec_t *)h2o_hpack_static_table[index - 1].name; + if (value_is_indexed) { + result->value = (h2o_iovec_t *)&h2o_hpack_static_table[index - 1].value; + } + } else if (index - HEADER_TABLE_OFFSET < hpack_header_table->num_entries) { + struct st_h2o_hpack_header_table_entry_t *entry = + h2o_hpack_header_table_get(hpack_header_table, index - HEADER_TABLE_OFFSET); + *err_desc = entry->err_desc; + result->name = entry->name; + if (!h2o_iovec_is_token(result->name)) + h2o_mem_link_shared(pool, result->name); + if (value_is_indexed) { + result->value = entry->value; + h2o_mem_link_shared(pool, result->value); + } + } else { + return H2O_HTTP2_ERROR_COMPRESSION; + } + } else { + /* non-existing name */ + const h2o_token_t *name_token; + if ((result->name = decode_string(pool, src, src_end, 1, err_desc)) == NULL) { + if (*err_desc == err_found_upper_case_in_header_name) { + return H2O_HTTP2_ERROR_PROTOCOL; + } + return H2O_HTTP2_ERROR_COMPRESSION; + } + if (!*err_desc) { + /* predefined header names should be interned */ + if ((name_token = h2o_lookup_token(result->name->base, result->name->len)) != NULL) { + result->name = (h2o_iovec_t *)&name_token->buf; + } + } + } + + /* determine the value (if necessary) */ + if (!value_is_indexed) { + if ((result->value = decode_string(pool, src, src_end, 0, err_desc)) == NULL) { + return H2O_HTTP2_ERROR_COMPRESSION; + } + } + + /* add the decoded header to the header table if necessary */ + if (do_index) { + struct st_h2o_hpack_header_table_entry_t *entry = + header_table_add(hpack_header_table, result->name->len + result->value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, SIZE_MAX); + if (entry != NULL) { + entry->err_desc = *err_desc; + entry->name = result->name; + if (!h2o_iovec_is_token(entry->name)) + h2o_mem_addref_shared(entry->name); + entry->value = result->value; + if (!value_is_part_of_static_table(entry->value)) + h2o_mem_addref_shared(entry->value); + } + } + + return *err_desc ? H2O_HTTP2_ERROR_INVALID_HEADER_CHAR : 0; +} + +static uint8_t *encode_status(uint8_t *dst, int status) +{ + /* see also: STATUS_HEADER_MAX_SIZE */ + + assert(100 <= status && status <= 999); + + switch (status) { +#define COMMON_CODE(code, st) \ + case st: \ + *dst++ = 0x80 | code; \ + break + COMMON_CODE(8, 200); + COMMON_CODE(9, 204); + COMMON_CODE(10, 206); + COMMON_CODE(11, 304); + COMMON_CODE(12, 400); + COMMON_CODE(13, 404); + COMMON_CODE(14, 500); +#undef COMMON_CODE + default: + /* use literal header field without indexing - indexed name */ + *dst++ = 8; + *dst++ = 3; + sprintf((char *)dst, "%d", status); + dst += 3; + break; + } + + return dst; +} + +static uint8_t *encode_content_length(uint8_t *dst, size_t value) +{ + char buf[32], *p = buf + sizeof(buf); + size_t l; + + do { + *--p = '0' + value % 10; + } while ((value /= 10) != 0); + l = buf + sizeof(buf) - p; + *dst++ = 0x0f; + *dst++ = 0x0d; + *dst++ = (uint8_t)l; + memcpy(dst, p, l); + dst += l; + + return dst; +} + +void h2o_hpack_dispose_header_table(h2o_hpack_header_table_t *header_table) +{ + if (header_table->num_entries != 0) { + size_t index = header_table->entry_start_index; + do { + struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + index; + if (!h2o_iovec_is_token(entry->name)) + h2o_mem_release_shared(entry->name); + if (!value_is_part_of_static_table(entry->value)) + h2o_mem_release_shared(entry->value); + index = (index + 1) % header_table->entry_capacity; + } while (--header_table->num_entries != 0); + } + free(header_table->entries); +} + +int h2o_hpack_parse_headers(h2o_req_t *req, h2o_hpack_header_table_t *header_table, const uint8_t *src, size_t len, + int *pseudo_header_exists_map, size_t *content_length, h2o_cache_digests_t **digests, + const char **err_desc) +{ + const uint8_t *src_end = src + len; + + *content_length = SIZE_MAX; + + while (src != src_end) { + struct st_h2o_decode_header_result_t r; + const char *decode_err = NULL; + int ret = decode_header(&req->pool, &r, header_table, &src, src_end, &decode_err); + if (ret != 0) { + if (ret == H2O_HTTP2_ERROR_INVALID_HEADER_CHAR) { + /* this is a soft error, we continue parsing, but register only the first error */ + if (*err_desc == NULL) { + *err_desc = decode_err; + } + } else { + *err_desc = decode_err; + return ret; + } + } + if (r.name->base[0] == ':') { + if (pseudo_header_exists_map != NULL) { + /* FIXME validate the chars in the value (e.g. reject SP in path) */ + if (r.name == &H2O_TOKEN_AUTHORITY->buf) { + /* FIXME should we perform this check? */ + if (req->input.authority.base != NULL) + return H2O_HTTP2_ERROR_PROTOCOL; + req->input.authority = *r.value; + *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_AUTHORITY_EXISTS; + } else if (r.name == &H2O_TOKEN_METHOD->buf) { + if (req->input.method.base != NULL) + return H2O_HTTP2_ERROR_PROTOCOL; + req->input.method = *r.value; + *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_METHOD_EXISTS; + } else if (r.name == &H2O_TOKEN_PATH->buf) { + if (req->input.path.base != NULL) + return H2O_HTTP2_ERROR_PROTOCOL; + req->input.path = *r.value; + *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_PATH_EXISTS; + } else if (r.name == &H2O_TOKEN_SCHEME->buf) { + if (req->input.scheme != NULL) + return H2O_HTTP2_ERROR_PROTOCOL; + if (h2o_memis(r.value->base, r.value->len, H2O_STRLIT("https"))) { + req->input.scheme = &H2O_URL_SCHEME_HTTPS; + } else { + /* draft-16 8.1.2.3 suggests quote: ":scheme is not restricted to http and https schemed URIs" */ + req->input.scheme = &H2O_URL_SCHEME_HTTP; + } + *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_SCHEME_EXISTS; + } else { + return H2O_HTTP2_ERROR_PROTOCOL; + } + } else { + return H2O_HTTP2_ERROR_PROTOCOL; + } + } else { + pseudo_header_exists_map = NULL; + if (h2o_iovec_is_token(r.name)) { + h2o_token_t *token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, r.name); + if (token == H2O_TOKEN_CONTENT_LENGTH) { + if ((*content_length = h2o_strtosize(r.value->base, r.value->len)) == SIZE_MAX) + return H2O_HTTP2_ERROR_PROTOCOL; + } else { + /* reject headers as defined in draft-16 8.1.2.2 */ + if (token->http2_should_reject) { + if (token == H2O_TOKEN_HOST) { + /* just skip (and :authority is used) */ + goto Next; + } else if (token == H2O_TOKEN_TE && h2o_lcstris(r.value->base, r.value->len, H2O_STRLIT("trailers"))) { + /* do not reject */ + } else { + return H2O_HTTP2_ERROR_PROTOCOL; + } + } + if (token == H2O_TOKEN_CACHE_DIGEST && digests != NULL) { + /* TODO cache the decoded result in HPACK, as well as delay the decoding of the digest until being used */ + h2o_cache_digests_load_header(digests, r.value->base, r.value->len); + } + h2o_add_header(&req->pool, &req->headers, token, NULL, r.value->base, r.value->len); + } + } else { + h2o_add_header_by_str(&req->pool, &req->headers, r.name->base, r.name->len, 0, NULL, r.value->base, r.value->len); + } + } + Next:; + } + + if (*err_desc) { + return H2O_HTTP2_ERROR_INVALID_HEADER_CHAR; + } + return 0; +} + +static inline int encode_int_is_onebyte(uint32_t value, size_t prefix_bits) +{ + return value < (1 << prefix_bits) - 1; +} + +static uint8_t *encode_int(uint8_t *dst, uint32_t value, size_t prefix_bits) +{ + if (encode_int_is_onebyte(value, prefix_bits)) { + *dst++ |= value; + } else { + /* see also: MAX_ENCODE_INT_LENGTH */ + value -= (1 << prefix_bits) - 1; + if (value > 0x0fffffff) + h2o_fatal("value out of range"); + *dst++ |= (1 << prefix_bits) - 1; + for (; value >= 128; value >>= 7) { + *dst++ = 0x80 | value; + } + *dst++ = value; + } + return dst; +} + +static size_t encode_huffman(uint8_t *_dst, const uint8_t *src, size_t len) +{ + uint8_t *dst = _dst, *dst_end = dst + len; + const uint8_t *src_end = src + len; + uint64_t bits = 0; + int bits_left = 40; + + while (src != src_end) { + const nghttp2_huff_sym *sym = huff_sym_table + *src++; + bits |= (uint64_t)sym->code << (bits_left - sym->nbits); + bits_left -= sym->nbits; + while (bits_left <= 32) { + *dst++ = bits >> 32; + bits <<= 8; + bits_left += 8; + if (dst == dst_end) { + return 0; + } + } + } + + if (bits_left != 40) { + bits |= ((uint64_t)1 << bits_left) - 1; + *dst++ = bits >> 32; + } + if (dst == dst_end) { + return 0; + } + + return dst - _dst; +} + +static size_t encode_as_is(uint8_t *dst, const char *s, size_t len) +{ + uint8_t *start = dst; + *dst = '\0'; + dst = encode_int(dst, (uint32_t)len, 7); + memcpy(dst, s, len); + dst += len; + return dst - start; +} + +size_t h2o_hpack_encode_string(uint8_t *dst, const char *s, size_t len) +{ + if (H2O_LIKELY(len != 0)) { + /* try to encode using huffman */ + size_t hufflen = encode_huffman(dst + 1, (const uint8_t *)s, len); + if (H2O_LIKELY(hufflen != 0)) { + size_t head_len; + if (H2O_LIKELY(encode_int_is_onebyte((uint32_t)hufflen, 7))) { + dst[0] = (uint8_t)(0x80 | hufflen); + head_len = 1; + } else { + uint8_t head[8]; + head[0] = '\x80'; + head_len = encode_int(head, (uint32_t)hufflen, 7) - head; + memmove(dst + head_len, dst + 1, hufflen); + memcpy(dst, head, head_len); + } + return head_len + hufflen; + } + } + return encode_as_is(dst, s, len); +} + +static uint8_t *encode_header(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_iovec_t *name, + const h2o_iovec_t *value) +{ + int name_index = 0, dont_compress = 0, name_is_token = h2o_iovec_is_token(name); + + /* try to send as indexed */ + { + size_t header_table_index = header_table->entry_start_index, n; + for (n = header_table->num_entries; n != 0; --n) { + struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + header_table_index; + if (name_is_token) { + if (name != entry->name) + goto Next; + } else { + if (!h2o_memis(name->base, name->len, entry->name->base, entry->name->len)) + goto Next; + if (name_index == 0) + name_index = (int)(header_table->num_entries - n + HEADER_TABLE_OFFSET); + } + /* name matched! */ + if (!h2o_memis(value->base, value->len, entry->value->base, entry->value->len)) + goto Next; + /* name and value matched! */ + *dst = 0x80; + dst = encode_int(dst, (uint32_t)(header_table->num_entries - n + HEADER_TABLE_OFFSET), 7); + return dst; + Next: + ++header_table_index; + if (header_table_index == header_table->entry_capacity) + header_table_index = 0; + } + } + + if (name_is_token) { + const h2o_token_t *name_token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, name); + name_index = name_token->http2_static_table_name_index; + dont_compress = (name_token->dont_compress == 1 && value->len < 20) ? 1 : 0; + } + + if (name_index != 0) { + /* literal header field with indexing (indexed name). */ + if (dont_compress == 1) { + /* mark the field as 'never indexed' */ + *dst = 0x10; + dst = encode_int(dst, name_index, 4); + } else { + *dst = 0x40; + dst = encode_int(dst, name_index, 6); + } + } else { + /* literal header field with indexing (new name) */ + *dst++ = 0x40; + dst += h2o_hpack_encode_string(dst, name->base, name->len); + } + if (dont_compress == 1) { + /* bypass huffman encoding */ + dst += encode_as_is(dst, value->base, value->len); + } else { + /* add to header table (maximum number of entries in output header table is limited to 32 so that the search (see above) would + not take too long) */ + dst += h2o_hpack_encode_string(dst, value->base, value->len); + struct st_h2o_hpack_header_table_entry_t *entry = + header_table_add(header_table, name->len + value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, 32); + if (entry != NULL) { + if (name_is_token) { + entry->name = (h2o_iovec_t *)name; + } else { + entry->name = alloc_buf(NULL, name->len); + entry->name->base[name->len] = '\0'; + memcpy(entry->name->base, name->base, name->len); + } + entry->value = alloc_buf(NULL, value->len); + entry->value->base[value->len] = '\0'; + memcpy(entry->value->base, value->base, value->len); + } + } + + return dst; +} + +static uint8_t *encode_method(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value) +{ + if (h2o_memis(value.base, value.len, H2O_STRLIT("GET"))) { + *dst++ = 0x82; + return dst; + } + if (h2o_memis(value.base, value.len, H2O_STRLIT("POST"))) { + *dst++ = 0x83; + return dst; + } + return encode_header(header_table, dst, &H2O_TOKEN_METHOD->buf, &value); +} + +static uint8_t *encode_scheme(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_url_scheme_t *scheme) +{ + if (scheme == &H2O_URL_SCHEME_HTTPS) { + *dst++ = 0x87; + return dst; + } + if (scheme == &H2O_URL_SCHEME_HTTP) { + *dst++ = 0x86; + return dst; + } + return encode_header(header_table, dst, &H2O_TOKEN_SCHEME->buf, &scheme->name); +} + +static uint8_t *encode_path(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value) +{ + if (h2o_memis(value.base, value.len, H2O_STRLIT("/"))) { + *dst++ = 0x84; + return dst; + } + if (h2o_memis(value.base, value.len, H2O_STRLIT("/index.html"))) { + *dst++ = 0x85; + return dst; + } + return encode_header(header_table, dst, &H2O_TOKEN_PATH->buf, &value); +} + +static uint8_t *encode_literal_header_without_indexing(uint8_t *dst, const h2o_iovec_t *name, const h2o_iovec_t *value) +{ + /* literal header field without indexing / never indexed */ + *dst++ = 0; + dst += h2o_hpack_encode_string(dst, name->base, name->len); + dst += h2o_hpack_encode_string(dst, value->base, value->len); + return dst; +} + +static size_t calc_capacity(size_t name_len, size_t value_len) +{ + return name_len + value_len + 1 + H2O_HTTP2_ENCODE_INT_MAX_LENGTH * 2; +} + +static size_t calc_headers_capacity(const h2o_header_t *headers, size_t num_headers) +{ + const h2o_header_t *header; + size_t capacity = 0; + for (header = headers; num_headers != 0; ++header, --num_headers) + capacity += calc_capacity(header->name->len, header->value.len); + return capacity; +} + +static void fixup_frame_headers(h2o_buffer_t **buf, size_t start_at, uint8_t type, uint32_t stream_id, size_t max_frame_size) +{ + /* try to fit all data into single frame, using the preallocated space for the frame header */ + size_t payload_size = (*buf)->size - start_at - H2O_HTTP2_FRAME_HEADER_SIZE; + if (payload_size <= max_frame_size) { + h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), payload_size, type, H2O_HTTP2_FRAME_FLAG_END_HEADERS, + stream_id); + return; + } + + /* need to setup continuation frames */ + size_t off; + h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), max_frame_size, type, 0, stream_id); + off = start_at + H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size; + while (1) { + size_t left = (*buf)->size - off; + h2o_buffer_reserve(buf, H2O_HTTP2_FRAME_HEADER_SIZE); + memmove((*buf)->bytes + off + H2O_HTTP2_FRAME_HEADER_SIZE, (*buf)->bytes + off, left); + (*buf)->size += H2O_HTTP2_FRAME_HEADER_SIZE; + if (left <= max_frame_size) { + h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), left, H2O_HTTP2_FRAME_TYPE_CONTINUATION, + H2O_HTTP2_FRAME_FLAG_END_HEADERS, stream_id); + break; + } else { + h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), max_frame_size, H2O_HTTP2_FRAME_TYPE_CONTINUATION, 0, + stream_id); + off += H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size; + } + } +} + +void h2o_hpack_flatten_request(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t stream_id, + size_t max_frame_size, h2o_req_t *req, uint32_t parent_stream_id) +{ + size_t capacity = calc_headers_capacity(req->headers.entries, req->headers.size); + capacity += H2O_HTTP2_FRAME_HEADER_SIZE /* first frame header */ + + 4; /* promised stream id */ + capacity += calc_capacity(H2O_TOKEN_METHOD->buf.len, req->input.method.len); + capacity += calc_capacity(H2O_TOKEN_SCHEME->buf.len, req->input.scheme->name.len); + capacity += calc_capacity(H2O_TOKEN_AUTHORITY->buf.len, req->input.authority.len); + capacity += calc_capacity(H2O_TOKEN_PATH->buf.len, req->input.path.len); + + size_t start_at = (*buf)->size; + uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE); + + /* encode */ + dst = h2o_http2_encode32u(dst, stream_id); + dst = encode_method(header_table, dst, req->input.method); + dst = encode_scheme(header_table, dst, req->input.scheme); + dst = encode_header(header_table, dst, &H2O_TOKEN_AUTHORITY->buf, &req->input.authority); + dst = encode_path(header_table, dst, req->input.path); + size_t i; + for (i = 0; i != req->headers.size; ++i) { + const h2o_header_t *header = req->headers.entries + i; + if (header->name == &H2O_TOKEN_ACCEPT_ENCODING->buf && + h2o_memis(header->value.base, header->value.len, H2O_STRLIT("gzip, deflate"))) { + *dst++ = 0x90; + } else { + dst = encode_header(header_table, dst, header->name, &header->value); + } + } + (*buf)->size = (char *)dst - (*buf)->bytes; + + /* setup the frame headers */ + fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_PUSH_PROMISE, parent_stream_id, max_frame_size); +} + +void h2o_hpack_flatten_response(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t stream_id, + size_t max_frame_size, h2o_res_t *res, h2o_timestamp_t *ts, const h2o_iovec_t *server_name, + size_t content_length) +{ + size_t capacity = calc_headers_capacity(res->headers.entries, res->headers.size); + capacity += H2O_HTTP2_FRAME_HEADER_SIZE; /* for the first header */ + capacity += STATUS_HEADER_MAX_SIZE; /* for :status: */ +#ifndef H2O_UNITTEST + capacity += 2 + H2O_TIMESTR_RFC1123_LEN; /* for Date: */ + if (server_name->len) { + capacity += 5 + server_name->len; /* for Server: */ + } +#endif + if (content_length != SIZE_MAX) + capacity += CONTENT_LENGTH_HEADER_MAX_SIZE; /* for content-length: UINT64_MAX (with huffman compression applied) */ + + size_t start_at = (*buf)->size; + uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE); /* skip frame header */ + + /* encode */ + dst = encode_status(dst, res->status); +#ifndef H2O_UNITTEST + /* TODO keep some kind of reference to the indexed headers of Server and Date, and reuse them */ + if (server_name->len) { + dst = encode_header(header_table, dst, &H2O_TOKEN_SERVER->buf, server_name); + } + h2o_iovec_t date_value = {ts->str->rfc1123, H2O_TIMESTR_RFC1123_LEN}; + dst = encode_header(header_table, dst, &H2O_TOKEN_DATE->buf, &date_value); +#endif + size_t i; + for (i = 0; i != res->headers.size; ++i) + dst = encode_header(header_table, dst, res->headers.entries[i].name, &res->headers.entries[i].value); + if (content_length != SIZE_MAX) + dst = encode_content_length(dst, content_length); + (*buf)->size = (char *)dst - (*buf)->bytes; + + /* setup the frame headers */ + fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_HEADERS, stream_id, max_frame_size); +} |