Repository: trafficserver Updated Branches: refs/heads/master 62ca9ec13 -> 0711dc2a2
TS-2729: implement HPACK support Implement an initial HPACK encoder/decoder, header compression format for HTTP/2. Now the encoder supports essential features. The decoder supports all of compression format required by hpack draft-09. Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/0711dc2a Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/0711dc2a Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/0711dc2a Branch: refs/heads/master Commit: 0711dc2a2971749998a8222022431fd1b9f4e830 Parents: 62ca9ec Author: Ryo Okubo <[email protected]> Authored: Mon Oct 20 21:40:12 2014 -0700 Committer: James Peach <[email protected]> Committed: Fri Oct 24 10:46:56 2014 -0700 ---------------------------------------------------------------------- proxy/hdrs/HPACK.cc | 945 ++++++++++++++++++++++++++++++++++++++++ proxy/hdrs/HPACK.h | 120 +++++ proxy/hdrs/HPACKHuffman.cc | 388 +++++++++++++++++ proxy/hdrs/HPACKHuffman.h | 34 ++ proxy/hdrs/HTTP.cc | 150 ++++++- proxy/hdrs/HTTP.h | 29 +- proxy/hdrs/Makefile.am | 4 +- 7 files changed, 1667 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HPACK.cc ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HPACK.cc b/proxy/hdrs/HPACK.cc new file mode 100644 index 0000000..9d8d337 --- /dev/null +++ b/proxy/hdrs/HPACK.cc @@ -0,0 +1,945 @@ +/** @file + + A brief file description + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#include "HPACK.h" +#include "HPACKHuffman.h" + +// 5.1. Maximum Table Size +// The size of an entry is the sum of its name's length in octets (as +// defined in Section 6.2), its value's length in octets (see +// Section 6.2), plus 32. +const static unsigned ADDITIONAL_OCTETS = 32; + +const static uint32_t HEADER_FIELD_LIMIT_LENGTH = 4096; + +// Constants for regression test +const static int BUFSIZE_FOR_REGRESSION_TEST = 128; +const static int MAX_TEST_FIELD_NUM = 8; + +typedef enum { + TS_HPACK_STATIC_TABLE_0 = 0, + TS_HPACK_STATIC_TABLE_AUTHORITY, + TS_HPACK_STATIC_TABLE_METHOD_GET, + TS_HPACK_STATIC_TABLE_METHOD_POST, + TS_HPACK_STATIC_TABLE_PATH_ROOT, + TS_HPACK_STATIC_TABLE_PATH_INDEX, + TS_HPACK_STATIC_TABLE_SCHEME_HTTP, + TS_HPACK_STATIC_TABLE_SCHEME_HTTPS, + TS_HPACK_STATIC_TABLE_STATUS_200, + TS_HPACK_STATIC_TABLE_STATUS_204, + TS_HPACK_STATIC_TABLE_STATUS_206, + TS_HPACK_STATIC_TABLE_STATUS_304, + TS_HPACK_STATIC_TABLE_STATUS_400, + TS_HPACK_STATIC_TABLE_STATUS_404, + TS_HPACK_STATIC_TABLE_STATUS_500, + TS_HPACK_STATIC_TABLE_ACCEPT_CHARSET, + TS_HPACK_STATIC_TABLE_ACCEPT_ENCODING, + TS_HPACK_STATIC_TABLE_ACCEPT_LANGUAGE, + TS_HPACK_STATIC_TABLE_ACCEPT_RANGES, + TS_HPACK_STATIC_TABLE_ACCEPT, + TS_HPACK_STATIC_TABLE_ACCESS_CONTROL_ALLOW_ORIGIN, + TS_HPACK_STATIC_TABLE_AGE, + TS_HPACK_STATIC_TABLE_ALLOW, + TS_HPACK_STATIC_TABLE_AUTHORIZATION, + TS_HPACK_STATIC_TABLE_CACHE_CONTROL, + TS_HPACK_STATIC_TABLE_CONTENT_DISPOSITION, + TS_HPACK_STATIC_TABLE_CONTENT_ENCODING, + TS_HPACK_STATIC_TABLE_CONTENT_LANGUAGE, + TS_HPACK_STATIC_TABLE_CONTENT_LENGTH, + TS_HPACK_STATIC_TABLE_CONTENT_LOCATION, + TS_HPACK_STATIC_TABLE_CONTENT_RANGE, + TS_HPACK_STATIC_TABLE_CONTENT_TYPE, + TS_HPACK_STATIC_TABLE_COOKIE, + TS_HPACK_STATIC_TABLE_DATE, + TS_HPACK_STATIC_TABLE_ETAG, + TS_HPACK_STATIC_TABLE_EXPECT, + TS_HPACK_STATIC_TABLE_EXPIRES, + TS_HPACK_STATIC_TABLE_FROM, + TS_HPACK_STATIC_TABLE_HOST, + TS_HPACK_STATIC_TABLE_IF_MATCH, + TS_HPACK_STATIC_TABLE_IF_MODIFIED_SINCE, + TS_HPACK_STATIC_TABLE_IF_NONE_MATCH, + TS_HPACK_STATIC_TABLE_IF_RANGE, + TS_HPACK_STATIC_TABLE_IF_UNMODIFIED_SINCE, + TS_HPACK_STATIC_TABLE_LAST_MODIFIED, + TS_HPACK_STATIC_TABLE_LINK, + TS_HPACK_STATIC_TABLE_LOCATION, + TS_HPACK_STATIC_TABLE_MAX_FORWARDS, + TS_HPACK_STATIC_TABLE_PROXY_AUTHENTICATE, + TS_HPACK_STATIC_TABLE_PROXY_AUTHORIZATION, + TS_HPACK_STATIC_TABLE_RANGE, + TS_HPACK_STATIC_TABLE_REFERER, + TS_HPACK_STATIC_TABLE_REFRESH, + TS_HPACK_STATIC_TABLE_RETRY_AFTER, + TS_HPACK_STATIC_TABLE_SERVER, + TS_HPACK_STATIC_TABLE_SET_COOKIE, + TS_HPACK_STATIC_TABLE_STRICT_TRANSPORT_SECURITY, + TS_HPACK_STATIC_TABLE_TRANSFER_ENCODING, + TS_HPACK_STATIC_TABLE_USER_AGENT, + TS_HPACK_STATIC_TABLE_VARY, + TS_HPACK_STATIC_TABLE_VIA, + TS_HPACK_STATIC_TABLE_WWW_AUTHENTICATE, + TS_HPACK_STATIC_TABLE_ENTRY_NUM +} TS_HPACK_STATIC_TABLE_ENTRY; + +const static struct { + const char* name; + const char* value; +} STATIC_TABLE[] = { + {"", ""}, + {":authority", ""}, + {":method", "GET"}, + {":method", "POST"}, + {":path", "/"}, + {":path", "/index.html"}, + {":scheme", "http"}, + {":scheme", "https"}, + {":status", "200"}, + {":status", "204"}, + {":status", "206"}, + {":status", "304"}, + {":status", "400"}, + {":status", "404"}, + {":status", "500"}, + {"accept-charset", ""}, + {"accept-encoding", "gzip, deflate"}, + {"accept-language", ""}, + {"accept-ranges", ""}, + {"accept", ""}, + {"access-control-allow-origin", ""}, + {"age", ""}, + {"allow", ""}, + {"authorization", ""}, + {"cache-control", ""}, + {"content-disposition", ""}, + {"content-encoding", ""}, + {"content-language", ""}, + {"content-length", ""}, + {"content-location", ""}, + {"content-range", ""}, + {"content-type", ""}, + {"cookie", ""}, + {"date", ""}, + {"etag", ""}, + {"expect", ""}, + {"expires", ""}, + {"from", ""}, + {"host", ""}, + {"if-match", ""}, + {"if-modified-since", ""}, + {"if-none-match", ""}, + {"if-range", ""}, + {"if-unmodified-since", ""}, + {"last-modified", ""}, + {"link", ""}, + {"location", ""}, + {"max-forwards", ""}, + {"proxy-authenticate", ""}, + {"proxy-authorization", ""}, + {"range", ""}, + {"referer", ""}, + {"refresh", ""}, + {"retry-after", ""}, + {"server", ""}, + {"set-cookie", ""}, + {"strict-transport-security", ""}, + {"transfer-encoding", ""}, + {"user-agent", ""}, + {"vary", ""}, + {"via", ""}, + {"www-authenticate", ""} +}; + +int +Http2HeaderTable::get_header_from_indexing_tables(uint32_t index, MIMEFieldWrapper& field) const +{ + // Index Address Space starts at 1, so index == 0 is invalid. + if (!index) return -1; + + if (index < TS_HPACK_STATIC_TABLE_ENTRY_NUM) { + field.name_set(STATIC_TABLE[index].name, strlen(STATIC_TABLE[index].name)); + field.value_set(STATIC_TABLE[index].value, strlen(STATIC_TABLE[index].value)); + } else if (index < TS_HPACK_STATIC_TABLE_ENTRY_NUM + get_current_entry_num()) { + const MIMEField* m_field = get_header(index - TS_HPACK_STATIC_TABLE_ENTRY_NUM + 1); + + int name_len, value_len; + const char* name = m_field->name_get(&name_len); + const char* value = m_field->value_get(&value_len); + + field.name_set(name, name_len); + field.value_set(value, value_len); + } else { + // 3.3.3. Index Address Space + // Indices strictly greater than the sum of the lengths of both tables + // MUST be treated as a decoding error. + return -1; + } + + return 0; +} + +// 5.2. Entry Eviction when Header Table Size Changes +// Whenever the maximum size for the header table is reduced, entries +// are evicted from the end of the header table until the size of the +// header table is less than or equal to the maximum size. +void +Http2HeaderTable::set_header_table_size(uint32_t new_size) +{ + uint32_t old_size = _settings_header_table_size; + while (old_size > new_size) { + int last_name_len, last_value_len; + MIMEField* last_field = _headers.last(); + + last_field->name_get(&last_name_len); + last_field->value_get(&last_value_len); + old_size -= ADDITIONAL_OCTETS + last_name_len + last_value_len; + + _headers.remove_index(_headers.length()-1); + _mhdr->field_delete(last_field, false); + } + + _settings_header_table_size = new_size; +} + +void +Http2HeaderTable::add_header_field(const MIMEField * field) +{ + int name_len, value_len; + const char * name = field->name_get(&name_len); + const char * value = field->value_get(&value_len); + uint32_t header_size = ADDITIONAL_OCTETS + name_len + value_len; + + if (header_size > _settings_header_table_size) { + // 5.3. It is not an error to attempt to add an entry that is larger than the maximum size; an + // attempt to add an entry larger than the entire table causes the table to be emptied of all existing entries. + _headers.clear(); + _mhdr->fields_clear(); + } else { + _current_size += header_size; + while (_current_size > _settings_header_table_size) { + int last_name_len, last_value_len; + MIMEField* last_field = _headers.last(); + + last_field->name_get(&last_name_len); + last_field->value_get(&last_value_len); + _current_size -= ADDITIONAL_OCTETS + last_name_len + last_value_len; + + _headers.remove_index(_headers.length()-1); + _mhdr->field_delete(last_field, false); + } + + MIMEField* new_field = _mhdr->field_create(name, name_len); + new_field->value_set(_mhdr->m_heap, _mhdr->m_mime, value, value_len); + // XXX Because entire Vec instance is copied, Its too expensive! + _headers.insert(0, new_field); + } +} + +/* + * Pseudo code + * + * if I < 2^N - 1, encode I on N bits + * else + * encode (2^N - 1) on N bits + * I = I - (2^N - 1) + * while I >= 128 + * encode (I % 128 + 128) on 8 bits + * I = I / 128 + * encode I on 8 bits + */ +int64_t +encode_integer(uint8_t *buf_start, const uint8_t *buf_end, uint32_t value, uint8_t n) +{ + if (buf_start >= buf_end) return -1; + + uint8_t *p = buf_start; + + if (value < (static_cast<uint32_t>(1 << n) - 1)) { + *(p++) |= value; + } else { + *(p++) |= (1 << n) - 1; + value -= (1 << n) - 1; + while (value >= 128) { + if (p >= buf_end) { + return -1; + } + *(p++) = (value & 0x7F) | 0x80; + value = value >> 7; + } + if (p+1 >= buf_end) { + return -1; + } + *(p++) = value; + } + return p - buf_start; +} + +int64_t +encode_string(uint8_t *buf_start, const uint8_t *buf_end, const char* value, size_t value_len) +{ + uint8_t *p = buf_start; + + // Length + const int64_t len = encode_integer(p, buf_end, value_len, 7); + if (len == -1) return -1; + p += len; + if (buf_end < p || static_cast<size_t>(buf_end - p) < value_len) return -1; + + // Value String + memcpy(p, value, value_len); + p += value_len; + return p - buf_start; +} + +int64_t +encode_indexed_header_field(uint8_t *buf_start, const uint8_t *buf_end, uint32_t index) +{ + if (buf_start >= buf_end) return -1; + + uint8_t *p = buf_start; + + // Index + const int64_t len = encode_integer(p, buf_end, index, 7); + if (len == -1) return -1; + + // Representation type + if (p+1 >= buf_end) { + return -1; + } + *p |= '\x80'; + p += len; + + return p - buf_start; +} + +int64_t +encode_literal_header_field(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper& header, uint32_t index, HEADER_INDEXING_TYPE type) +{ + uint8_t *p = buf_start; + int64_t len; + uint8_t prefix = 0, flag = 0; + + switch (type) { + case INC_INDEXING: + prefix = 6; + flag = 0x40; + break; + case WITHOUT_INDEXING: + prefix = 4; + flag = 0x00; + break; + case NEVER_INDEXED: + prefix = 4; + flag = 0x10; + break; + default: + return -1; + } + + // Index + len = encode_integer(p, buf_end, index, prefix); + if (len == -1) return -1; + + // Representation type + if (p+1 >= buf_end) { + return -1; + } + *p |= flag; + p += len; + + // Value String + int value_len; + const char* value = header.value_get(&value_len); + len = encode_string(p, buf_end, value, value_len); + if (len == -1) return -1; + p += len; + + return p - buf_start; +} + +int64_t +encode_literal_header_field(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper& header, HEADER_INDEXING_TYPE type) +{ + uint8_t *p = buf_start; + int64_t len; + uint8_t flag = 0; + + ink_assert(type >= INC_INDEXING && type <= NEVER_INDEXED); + switch (type) { + case INC_INDEXING: + flag = 0x40; + break; + case WITHOUT_INDEXING: + flag = 0x00; + break; + case NEVER_INDEXED: + flag = 0x10; + break; + default: + return -1; + } + if (p+1 >= buf_end) { + return -1; + } + *(p++) = flag; + + // Name String + int name_len; + const char* name = header.name_get(&name_len); + len = encode_string(p, buf_end, name, name_len); + if (len == -1) return -1; + p += len; + + // Value String + int value_len; + const char* value = header.value_get(&value_len); + len = encode_string(p, buf_end, value, value_len); + if (len == -1) { + return -1; + } + + p += len; + + return p - buf_start; +} + +/* + * 6.1. Integer representation + * + * Pseudo code + * + * decode I from the next N bits + * if I < 2^N - 1, return I + * else + * M = 0 + * repeat + * B = next octet + * I = I + (B & 127) * 2^M + * M = M + 7 + * while B & 128 == 128 + * return I + * + */ +inline int64_t +decode_integer(uint32_t& dst, const uint8_t *buf_start, const uint8_t *buf_end, uint8_t n) +{ + const uint8_t *p = buf_start; + + dst = (*p & ((1 << n) - 1)); + if (dst == static_cast<uint32_t>(1 << n) - 1) { + int m = 0; + do { + if (++p >= buf_end) return -1; + + uint32_t added_value = *p & 0x7f; + if ((UINT32_MAX >> m) < added_value) { + // Excessively large integer encodings - in value or octet + // length - MUST be treated as a decoding error. + return -1; + } + dst += added_value << m; + m += 7; + } while (*p & 0x80); + } + + return p - buf_start + 1; +} + +// 6.2 return content from String Data (Length octets) +// with huffman decoding if it is encoded +int64_t +decode_string(char **c_str, uint32_t& c_str_length, const uint8_t *buf_start, const uint8_t *buf_end) +{ + const uint8_t *p = buf_start; + bool isHuffman = *p & 0x80; + uint32_t encoded_string_len = 0; + int64_t len = 0; + + len = decode_integer(encoded_string_len, p, buf_end, 7); + if (len == -1) return -1; + p += len; + + if (encoded_string_len > HEADER_FIELD_LIMIT_LENGTH || buf_start + encoded_string_len >= buf_end) { + return -1; + } + + if (isHuffman) { + // Allocate temporary area twice the size of before decoded data + *c_str = static_cast<char*>(ats_malloc(encoded_string_len * 2)); + + len = huffman_decode(*c_str, p, encoded_string_len); + if (len == -1) return -1; + c_str_length = len; + } else { + *c_str = static_cast<char*>(ats_malloc(encoded_string_len)); + + memcpy(*c_str, reinterpret_cast<const char*>(p), encoded_string_len); + + c_str_length = encoded_string_len; + } + + return p + encoded_string_len - buf_start; +} + +// 7.1. Indexed Header Field Representation +int64_t +decode_indexed_header_field(MIMEFieldWrapper& header, const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table) +{ + uint32_t index = 0; + int64_t len = 0; + len = decode_integer(index, buf_start, buf_end, 7); + if (len == -1) return -1; + + if (header_table.get_header_from_indexing_tables(index, header) == -1) { + return -1; + } + + return len; +} + +// 7.2. Literal Header Field Representation +int64_t +decode_literal_header_field(MIMEFieldWrapper& header, const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table) +{ + const uint8_t *p = buf_start; + bool isIncremental = false; + uint32_t index = 0; + int64_t len = 0; + + if (*p & 0x40) { + // 7.2.1. index extraction based on Literal Header Field with Incremental Indexing + len = decode_integer(index, p, buf_end, 6); + if (len == -1) return -1; + isIncremental = true; + } else if (*p & 0x10) { + // 7.2.3. index extraction Literal Header Field Never Indexed + len = decode_integer(index, p, buf_end, 4); + if (len == -1) return -1; + } else { + // 7.2.2. index extraction Literal Header Field without Indexing + len = decode_integer(index, p, buf_end, 4); + if (len == -1) return -1; + } + p += len; + + if (index) { + header_table.get_header_from_indexing_tables(index, header); + } else { + char *c_name = NULL; + uint32_t c_name_len = 0; + len = decode_string(&c_name, c_name_len, p, buf_end); + if (len == -1) return -1; + p += len; + header.name_set(c_name, c_name_len); + ats_free(c_name); + } + char *c_value = NULL; + uint32_t c_value_len = 0; + len = decode_string(&c_value, c_value_len, p, buf_end); + if (len == -1) return -1; + p += len; + header.value_set(c_value, c_value_len); + ats_free(c_value); + + // Incremental Indexing adds header to header table as new entry + if (isIncremental) { + header_table.add_header_field(header.field_get()); + } + + return p - buf_start; +} + +// 7.3. Header Table Size Update +int64_t +update_header_table_size(const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table) +{ + if (buf_start == buf_end) return -1; + + int64_t len = 0; + + // Update header table size if its required. + if ((*buf_start & 0xe0) == 0x20) { + uint32_t size = 0; + len = decode_integer(size, buf_start, buf_end, 5); + if (len == -1) return -1; + + header_table.set_header_table_size(size); + } + + return len; +} + +#if TS_HAS_TESTS + +#include "TestBox.h" + +/*********************************************************************************** + * * + * Test cases for regression test * + * * + * Some test cases are based on examples of specification. * + * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-09#appendix-D * + * * + ***********************************************************************************/ + +// D.1. Integer Representation Examples +const static struct { + uint32_t raw_integer; + uint8_t* encoded_field; + int encoded_field_len; + int prefix; +} integer_test_case[] = { + { 10, (uint8_t*)"\x0A", 1, 5 }, + { 1337, (uint8_t*)"\x1F\x9A\x0A", 3, 5 }, + { 42, (uint8_t*)"\x2A", 1, 8 } +}; + +// Example: custom-key: custom-header +const static struct { + char* raw_string; + uint32_t raw_string_len; + uint8_t* encoded_field; + int encoded_field_len; +} string_test_case[] = { + { (char*)"custom-key", 10, (uint8_t*)"\xA" "custom-key", 11 }, + { (char*)"custom-key", 10, (uint8_t*)"\x88" "\x25\xa8\x49\xe9\x5b\xa9\x7d\x7f", 9 } +}; + +// D.2.4. Indexed Header Field +const static struct { + int index; + char* raw_name; + char* raw_value; + uint8_t* encoded_field; + int encoded_field_len; +} indexed_test_case[] = { + { 2, (char*)":method", (char*)"GET", (uint8_t*)"\x82", 1 } +}; + +// D.2. Header Field Representation Examples +const static struct { + char* raw_name; + char* raw_value; + int index; + HEADER_INDEXING_TYPE type; + uint8_t* encoded_field; + int encoded_field_len; +} literal_test_case[] = { + { (char*)"custom-key", (char*)"custom-header", 0, INC_INDEXING, (uint8_t*)"\x40\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)"custom-key", (char*)"custom-header", 0, WITHOUT_INDEXING, (uint8_t*)"\x00\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)"custom-key", (char*)"custom-header", 0, NEVER_INDEXED, (uint8_t*)"\x10\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)":path", (char*)"/sample/path", 4, INC_INDEXING, (uint8_t*)"\x44\x0c" "/sample/path", 14 }, + { (char*)":path", (char*)"/sample/path", 4, WITHOUT_INDEXING, (uint8_t*)"\x04\x0c" "/sample/path", 14 }, + { (char*)":path", (char*)"/sample/path", 4, NEVER_INDEXED, (uint8_t*)"\x14\x0c" "/sample/path", 14 }, + { (char*)"password", (char*)"secret", 0, INC_INDEXING, (uint8_t*)"\x40\x08" "password\x06" "secret", 17 }, + { (char*)"password", (char*)"secret", 0, WITHOUT_INDEXING, (uint8_t*)"\x00\x08" "password\x06" "secret", 17 }, + { (char*)"password", (char*)"secret", 0, NEVER_INDEXED, (uint8_t*)"\x10\x08" "password\x06" "secret", 17 } +}; + +// D.3. Request Examples without Huffman Coding - D.3.1. First Request +const static struct { + char* raw_name; + char* raw_value; +} raw_field_test_case[][MAX_TEST_FIELD_NUM] = { + { + { (char*)":method", (char*)"GET" }, + { (char*)":scheme", (char*)"http" }, + { (char*)":path", (char*)"/" }, + { (char*)":authority", (char*)"www.example.com" }, + { (char*)"", (char*)"" } // End of this test case + } +}; +const static struct { + uint8_t* encoded_field; + int encoded_field_len; +} encoded_field_test_case[] = { + { + (uint8_t*)"\x40" "\x7:method" "\x3GET" + "\x40" "\x7:scheme" "\x4http" + "\x40" "\x5:path" "\x1/" + "\x40" "\xa:authority" "\xfwww.example.com", + 64 + } +}; + +/*********************************************************************************** + * * + * Regression test codes * + * * + ***********************************************************************************/ + +REGRESSION_TEST(HPACK_EncodeInteger)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + + for (unsigned int i=0; i<sizeof(integer_test_case)/sizeof(integer_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + int len = encode_integer(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, integer_test_case[i].raw_integer, integer_test_case[i].prefix); + + box.check(len == integer_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(memcmp(buf, integer_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeString)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + int len; + + // FIXME Current encoder don't support huffman conding. + for (unsigned int i=0; i<1; i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + len = encode_string(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, string_test_case[i].raw_string, string_test_case[i].raw_string_len); + + box.check(len == string_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(memcmp(buf, string_test_case[i].encoded_field, len) == 0, "encoded string was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeIndexedHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + + for (unsigned int i=0; i<sizeof(indexed_test_case)/sizeof(indexed_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + int len = encode_indexed_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, indexed_test_case[i].index); + + box.check(len == indexed_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, indexed_test_case[i].encoded_field_len); + box.check(memcmp(buf, indexed_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeLiteralHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + int len; + + for (unsigned int i=0; i<sizeof(literal_test_case)/sizeof(literal_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_RESPONSE); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + header.value_set(literal_test_case[i].raw_value, strlen(literal_test_case[i].raw_value)); + if (literal_test_case[i].index > 0) { + len = encode_literal_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, header, literal_test_case[i].index, literal_test_case[i].type); + } else { + header.name_set(literal_test_case[i].raw_name, strlen(literal_test_case[i].raw_name)); + len = encode_literal_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, header, literal_test_case[i].type); + } + + box.check(len == literal_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", len, literal_test_case[i].encoded_field_len); + box.check(memcmp(buf, literal_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } + +} + +REGRESSION_TEST(HPACK_Encode)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + Http2HeaderTable header_table; + + // FIXME Current encoder don't support indexing. + for (unsigned int i=0; i<sizeof(encoded_field_test_case)/sizeof(encoded_field_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + + for (unsigned int j=0; j<sizeof(raw_field_test_case[i])/sizeof(raw_field_test_case[i][0]); j++) { + const char* expected_name = raw_field_test_case[i][j].raw_name; + const char* expected_value = raw_field_test_case[i][j].raw_value; + if (strlen(expected_name) == 0) break; + + MIMEField* field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + mime_field_name_value_set(headers->m_heap, headers->m_http->m_fields_impl, field, -1, + expected_name, strlen(expected_name), expected_value, strlen(expected_value), + true, strlen(expected_name) + strlen(expected_value), 1); + mime_hdr_field_attach(headers->m_http->m_fields_impl, field, 1, NULL); + } + + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + int len = convert_from_1_1_to_2_header(headers, buf, BUFSIZE_FOR_REGRESSION_TEST, header_table); + + box.check(len == encoded_field_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, encoded_field_test_case[i].encoded_field_len); + box.check(memcmp(buf, encoded_field_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_DecodeInteger)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint32_t actual; + + for (unsigned int i=0; i<sizeof(integer_test_case)/sizeof(integer_test_case[0]); i++) { + int len = decode_integer(actual, integer_test_case[i].encoded_field, + integer_test_case[i].encoded_field + integer_test_case[i].encoded_field_len, + integer_test_case[i].prefix); + + box.check(len == integer_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(actual == integer_test_case[i].raw_integer, "decoded value was %d, expected %d", + actual, integer_test_case[i].raw_integer); + } +} + +REGRESSION_TEST(HPACK_DecodeString)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + char* actual; + uint32_t actual_len; + + hpack_huffman_init(); + + for (unsigned int i=0; i<sizeof(string_test_case)/sizeof(string_test_case[0]); i++) { + int len = decode_string(&actual, actual_len, string_test_case[i].encoded_field, + string_test_case[i].encoded_field + string_test_case[i].encoded_field_len); + + box.check(len == string_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, string_test_case[i].encoded_field_len); + box.check(actual_len == string_test_case[i].raw_string_len, "length of decoded string was %d, expecting %d", + actual_len, string_test_case[i].raw_string_len); + box.check(memcmp(actual, string_test_case[i].raw_string, actual_len) == 0, "decoded string was invalid"); + + ats_free(actual); + } +} + +REGRESSION_TEST(HPACK_DecodeIndexedHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(indexed_test_case)/sizeof(indexed_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + int len = decode_indexed_header_field(header, indexed_test_case[i].encoded_field, + indexed_test_case[i].encoded_field+indexed_test_case[i].encoded_field_len, header_table); + + box.check(len == indexed_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, indexed_test_case[i].encoded_field_len); + + int name_len; + const char* name = header.name_get(&name_len); + box.check(memcmp(name, indexed_test_case[i].raw_name, name_len) == 0, + "decoded header name was invalid"); + + int actual_value_len; + const char* actual_value = header.value_get(&actual_value_len); + box.check(memcmp(actual_value, indexed_test_case[i].raw_value, actual_value_len) == 0, + "decoded header value was invalid"); + } +} + +REGRESSION_TEST(HPACK_DecodeLiteralHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(literal_test_case)/sizeof(literal_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + int len = decode_literal_header_field(header, literal_test_case[i].encoded_field, + literal_test_case[i].encoded_field+literal_test_case[i].encoded_field_len, header_table); + + box.check(len == literal_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, literal_test_case[i].encoded_field_len); + + int name_len; + const char* name = header.name_get(&name_len); + box.check(memcmp(name, literal_test_case[i].raw_name, name_len) == 0, + "decoded header name was invalid"); + + int actual_value_len; + const char* actual_value = header.value_get(&actual_value_len); + box.check(memcmp(actual_value, literal_test_case[i].raw_value, actual_value_len) == 0, + "decoded header value was invalid"); + } +} + +REGRESSION_TEST(HPACK_Decode)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(encoded_field_test_case)/sizeof(encoded_field_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + + headers->hpack_parse_req(encoded_field_test_case[i].encoded_field, + encoded_field_test_case[i].encoded_field + encoded_field_test_case[i].encoded_field_len, + true, header_table); + + for (unsigned int j=0; j<sizeof(raw_field_test_case[i])/sizeof(raw_field_test_case[i][0]); j++) { + const char* expected_name = raw_field_test_case[i][j].raw_name; + const char* expected_value = raw_field_test_case[i][j].raw_value; + if (strlen(expected_name) == 0) break; + + MIMEField* field = headers->field_find(expected_name, strlen(expected_name)); + box.check(field != NULL, "A MIMEField that has \"%s\" as name doesn't exist", expected_name); + + int actual_value_len; + const char* actual_value = field->value_get(&actual_value_len); + box.check(strncmp(expected_value, actual_value, actual_value_len) == 0, "A MIMEField that has \"%s\" as value doesn't exist", expected_value); + } + } +} + +#endif /* TS_HAS_TESTS */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HPACK.h ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HPACK.h b/proxy/hdrs/HPACK.h new file mode 100644 index 0000000..341023a --- /dev/null +++ b/proxy/hdrs/HPACK.h @@ -0,0 +1,120 @@ +/** @file + + A brief file description + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __HPACK_H__ +#define __HPACK_H__ + +#include "libts.h" +#include "HTTP.h" + +enum HEADER_INDEXING_TYPE { + INC_INDEXING, + WITHOUT_INDEXING, + NEVER_INDEXED, +}; + +class MIMEFieldWrapper +{ +public: + + MIMEFieldWrapper(MIMEField * f, HdrHeap * hh, MIMEHdrImpl * impl) + : _field(f), _heap(hh), _mh(impl) { + } + + void name_set(const char * name, int name_len) { + _field->name_set(_heap, _mh, name, name_len); + } + + void value_set(const char * value, int value_len) { + _field->value_set(_heap, _mh, value, value_len); + } + + const char * name_get(int * length) const { + return _field->name_get(length); + } + + const char * value_get(int * length) const { + return _field->value_get(length); + } + + const MIMEField * field_get() const { + return _field; + } + +private: + MIMEField * _field; + HdrHeap * _heap; + MIMEHdrImpl * _mh; +}; + +// 3.2 Header Table +class Http2HeaderTable +{ +public: + + Http2HeaderTable() : _current_size(0), _settings_header_table_size(4096) { + _mhdr = new MIMEHdr(); + _mhdr->create(); + } + + ~Http2HeaderTable() { + _headers.clear(); + _mhdr->fields_clear(); + } + + void add_header_field(const MIMEField * field); + int get_header_from_indexing_tables(uint32_t index, MIMEFieldWrapper& header_field) const; + void set_header_table_size(uint32_t new_size); + +private: + + const MIMEField * get_header(uint32_t index) const { + return _headers.get(index-1); + } + + const uint32_t get_current_entry_num() const { + return _headers.length(); + } + + uint32_t _current_size; + uint32_t _settings_header_table_size; + + MIMEHdr * _mhdr; + Vec<MIMEField *> _headers; +}; + +int64_t +encode_indexed_header_field(uint8_t *buf_start, const uint8_t *buf_end, uint32_t index); +int64_t +encode_literal_header_field(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper& header, uint32_t index, HEADER_INDEXING_TYPE type); +int64_t +encode_literal_header_field(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper& header, HEADER_INDEXING_TYPE type); + +int64_t +decode_indexed_header_field(MIMEFieldWrapper& header, const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table); +int64_t +decode_literal_header_field(MIMEFieldWrapper& header, const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table); +int64_t +update_header_table_size(const uint8_t *buf_start, const uint8_t *buf_end, Http2HeaderTable& header_table); + +#endif /* __HPACK_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HPACKHuffman.cc ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HPACKHuffman.cc b/proxy/hdrs/HPACKHuffman.cc new file mode 100644 index 0000000..02706ed --- /dev/null +++ b/proxy/hdrs/HPACKHuffman.cc @@ -0,0 +1,388 @@ +/** @file + + A brief file description + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#include "HPACKHuffman.h" +#include "libts.h" + +const size_t HUFFMAN_TABLE_ENTRY_NUM = 257; + +const static struct { + uint32_t code_as_hex; + uint32_t bit_len; +} huffman_table[] = { + {0x1ff8, 13}, + {0x7fffd8, 23}, + {0xfffffe2, 28}, + {0xfffffe3, 28}, + {0xfffffe4, 28}, + {0xfffffe5, 28}, + {0xfffffe6, 28}, + {0xfffffe7, 28}, + {0xfffffe8, 28}, + {0xffffea, 24}, + {0x3ffffffc, 30}, + {0xfffffe9, 28}, + {0xfffffea, 28}, + {0x3ffffffd, 30}, + {0xfffffeb, 28}, + {0xfffffec, 28}, + {0xfffffed, 28}, + {0xfffffee, 28}, + {0xfffffef, 28}, + {0xffffff0, 28}, + {0xffffff1, 28}, + {0xffffff2, 28}, + {0x3ffffffe, 30}, + {0xffffff3, 28}, + {0xffffff4, 28}, + {0xffffff5, 28}, + {0xffffff6, 28}, + {0xffffff7, 28}, + {0xffffff8, 28}, + {0xffffff9, 28}, + {0xffffffa, 28}, + {0xffffffb, 28}, + {0x14, 6}, + {0x3f8, 10}, + {0x3f9, 10}, + {0xffa, 12}, + {0x1ff9, 13}, + {0x15, 6}, + {0xf8, 8}, + {0x7fa, 11}, + {0x3fa, 10}, + {0x3fb, 10}, + {0xf9, 8}, + {0x7fb, 11}, + {0xfa, 8}, + {0x16, 6}, + {0x17, 6}, + {0x18, 6}, + {0x0, 5}, + {0x1, 5}, + {0x2, 5}, + {0x19, 6}, + {0x1a, 6}, + {0x1b, 6}, + {0x1c, 6}, + {0x1d, 6}, + {0x1e, 6}, + {0x1f, 6}, + {0x5c, 7}, + {0xfb, 8}, + {0x7ffc, 15}, + {0x20, 6}, + {0xffb, 12}, + {0x3fc, 10}, + {0x1ffa, 13}, + {0x21, 6}, + {0x5d, 7}, + {0x5e, 7}, + {0x5f, 7}, + {0x60, 7}, + {0x61, 7}, + {0x62, 7}, + {0x63, 7}, + {0x64, 7}, + {0x65, 7}, + {0x66, 7}, + {0x67, 7}, + {0x68, 7}, + {0x69, 7}, + {0x6a, 7}, + {0x6b, 7}, + {0x6c, 7}, + {0x6d, 7}, + {0x6e, 7}, + {0x6f, 7}, + {0x70, 7}, + {0x71, 7}, + {0x72, 7}, + {0xfc, 8}, + {0x73, 7}, + {0xfd, 8}, + {0x1ffb, 13}, + {0x7fff0, 19}, + {0x1ffc, 13}, + {0x3ffc, 14}, + {0x22, 6}, + {0x7ffd, 15}, + {0x3, 5}, + {0x23, 6}, + {0x4, 5}, + {0x24, 6}, + {0x5, 5}, + {0x25, 6}, + {0x26, 6}, + {0x27, 6}, + {0x6, 5}, + {0x74, 7}, + {0x75, 7}, + {0x28, 6}, + {0x29, 6}, + {0x2a, 6}, + {0x7, 5}, + {0x2b, 6}, + {0x76, 7}, + {0x2c, 6}, + {0x8, 5}, + {0x9, 5}, + {0x2d, 6}, + {0x77, 7}, + {0x78, 7}, + {0x79, 7}, + {0x7a, 7}, + {0x7b, 7}, + {0x7ffe, 15}, + {0x7fc, 11}, + {0x3ffd, 14}, + {0x1ffd, 13}, + {0xffffffc, 28}, + {0xfffe6, 20}, + {0x3fffd2, 22}, + {0xfffe7, 20}, + {0xfffe8, 20}, + {0x3fffd3, 22}, + {0x3fffd4, 22}, + {0x3fffd5, 22}, + {0x7fffd9, 23}, + {0x3fffd6, 22}, + {0x7fffda, 23}, + {0x7fffdb, 23}, + {0x7fffdc, 23}, + {0x7fffdd, 23}, + {0x7fffde, 23}, + {0xffffeb, 23}, + {0x7fffdf, 23}, + {0xffffec, 24}, + {0xffffed, 24}, + {0x3fffd7, 22}, + {0x7fffe0, 23}, + {0xffffee, 24}, + {0x7fffe1, 23}, + {0x7fffe2, 23}, + {0x7fffe3, 23}, + {0x7fffe4, 23}, + {0x1fffdc, 21}, + {0x3fffd8, 22}, + {0x7fffe5, 23}, + {0x3fffd9, 22}, + {0x7fffe6, 23}, + {0x7fffe7, 23}, + {0xffffef, 24}, + {0x3fffda, 22}, + {0x1fffdd, 21}, + {0xfffe9, 20}, + {0x3fffdb, 22}, + {0x3fffdc, 22}, + {0x7fffe8, 23}, + {0x7fffe9, 23}, + {0x1fffde, 21}, + {0x7fffde, 23}, + {0x3fffdd, 22}, + {0x3fffde, 22}, + {0xfffff0, 24}, + {0x1fffdf, 21}, + {0x3fffdf, 22}, + {0x7fffeb, 23}, + {0x7fffec, 23}, + {0x1fffe0, 21}, + {0x1fffe1, 21}, + {0x3fffe0, 22}, + {0x1fffe2, 21}, + {0x7fffed, 23}, + {0x3fffe1, 22}, + {0x7fffee, 23}, + {0x7fffef, 23}, + {0xfffea, 20}, + {0x3fffe2, 22}, + {0x3fffe3, 22}, + {0x3fffe4, 22}, + {0x7ffff0, 23}, + {0x3fffe5, 22}, + {0x3fffe6, 22}, + {0x7ffff1, 23}, + {0x3ffffe0, 26}, + {0x3ffffe1, 26}, + {0xfffeb, 20}, + {0x7fff1, 19}, + {0x3fffe7, 22}, + {0x7ffff2, 23}, + {0x3fffe8, 22}, + {0x1ffffec, 25}, + {0x3ffffe2, 26}, + {0x3ffffe3, 26}, + {0x3ffffe4, 26}, + {0x7ffffde, 27}, + {0x7ffffdf, 27}, + {0x3ffffe5, 26}, + {0xfffff1, 24}, + {0x1ffffed, 25}, + {0x7fff2, 19}, + {0x1fffe3, 21}, + {0x3ffffe6, 26}, + {0x7ffffe0, 27}, + {0x7ffffe1, 27}, + {0x3ffffe7, 26}, + {0x3ffffe2, 27}, + {0xfffff2, 24}, + {0x1fffe4, 21}, + {0x1fffe5, 21}, + {0x3ffffe8, 26}, + {0x3ffffe9, 26}, + {0xffffffd, 28}, + {0x7ffffe3, 27}, + {0x7ffffe4, 27}, + {0x7ffffe5, 27}, + {0xfffec, 20}, + {0xfffff3, 24}, + {0xfffed, 20}, + {0x1fffe6, 21}, + {0x3fffe9, 22}, + {0x1fffe7, 21}, + {0x1fffe8, 21}, + {0x7ffff3, 23}, + {0x3fffea, 22}, + {0x3fffeb, 22}, + {0x1ffffee, 25}, + {0x1ffffef, 25}, + {0xfffff4, 24}, + {0xfffff5, 24}, + {0x3ffffea, 26}, + {0x7ffff4, 23}, + {0x3ffffeb, 26}, + {0x7ffffe6, 27}, + {0x3ffffec, 26}, + {0x3ffffed, 26}, + {0x7ffffe7, 27}, + {0x7ffffe8, 27}, + {0x7ffffe9, 27}, + {0x7ffffea, 27}, + {0x7ffffeb, 27}, + {0xffffffe, 28}, + {0x7ffffec, 27}, + {0x7ffffed, 27}, + {0x7ffffee, 27}, + {0x7ffffef, 27}, + {0x7fffff0, 27}, + {0x3ffffee, 26}, + {0x3fffffff, 30} +}; + +typedef struct node { + node *left, *right; + char ascii_code; +} Node; + +Node* HUFFMAN_TREE_ROOT; + +static Node* +make_huffman_tree_node() +{ + Node *n = static_cast<Node *>(ats_malloc(sizeof(Node))); + n->left = NULL; + n->right = NULL; + n->ascii_code = '\0'; + return n; +} + +static Node* +make_huffman_tree() +{ + Node* root = make_huffman_tree_node(); + Node* current; + uint32_t bit_len; + // insert leafs for each ascii code + for (unsigned i = 0; i < HUFFMAN_TABLE_ENTRY_NUM; i++){ + bit_len = huffman_table[i].bit_len; + current = root; + while (bit_len > 0){ + if (huffman_table[i].code_as_hex & (1 << (bit_len-1))) { + if (!current->right) + current->right = make_huffman_tree_node(); + current = current->right; + } else { + if (!current->left) + current->left = make_huffman_tree_node(); + current = current->left; + } + bit_len--; + } + current->ascii_code = i; + } + return root; +} + +static void +free_huffman_tree(Node* node) +{ + if (node->left) + free_huffman_tree(node->left); + if (node->right) + free_huffman_tree(node->right); + + ats_free(node); +} + +void hpack_huffman_init() +{ + if (!HUFFMAN_TREE_ROOT) + HUFFMAN_TREE_ROOT = make_huffman_tree(); +} + +void hpack_huffman_fin() +{ + if (HUFFMAN_TREE_ROOT) + free_huffman_tree(HUFFMAN_TREE_ROOT); +} + +int64_t +huffman_decode(char* dst_start, const uint8_t* src, uint32_t src_len) +{ + char* dst_end = dst_start; + uint8_t shift = 7; + Node* current = HUFFMAN_TREE_ROOT; + + while (src_len) { + if (*src & (1 << shift)) { + current = current->right; + } else { + current = current->left; + } + + if (current->ascii_code) { + *dst_end = current->ascii_code; + ++dst_end; + current = HUFFMAN_TREE_ROOT; + } + if (shift) { + --shift; + } else { + shift = 7; + ++src; + --src_len; + } + } + + return dst_end - dst_start; +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HPACKHuffman.h ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HPACKHuffman.h b/proxy/hdrs/HPACKHuffman.h new file mode 100644 index 0000000..0037a72 --- /dev/null +++ b/proxy/hdrs/HPACKHuffman.h @@ -0,0 +1,34 @@ +/** @file + + A brief file description + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __HPACK_HUFFMAN_H__ +#define __HPACK_HUFFMAN_H__ + +#include <stddef.h> +#include <stdint.h> + +void hpack_huffman_init(); +void hpack_huffman_fin(); +int64_t huffman_decode(char* dst_start, const uint8_t* src, uint32_t src_len); + +#endif /* __HPACK_Huffman_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HTTP.cc ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HTTP.cc b/proxy/hdrs/HTTP.cc index 5933381..cf00d71 100644 --- a/proxy/hdrs/HTTP.cc +++ b/proxy/hdrs/HTTP.cc @@ -30,7 +30,6 @@ #include "HdrToken.h" #include "Diags.h" - /*********************************************************************** * * * C O M P I L E O P T I O N S * @@ -146,6 +145,13 @@ int HTTP_LEN_S_MAXAGE; int HTTP_LEN_NEED_REVALIDATE_ONCE; int HTTP_LEN_100_CONTINUE; +// Constant strings for pseudo headers of HPACK +const static char* HPACK_HEADER_SCHEME_STRING = ":scheme"; +const static char* HPACK_HEADER_METHOD_STRING = ":method"; +const static char* HPACK_HEADER_AUTHORITY_STRING = ":authority"; +const static char* HPACK_HEADER_PATH_STRING = ":path"; +const static char* HPACK_HEADER_STATUS_STRING = ":status"; + Arena* const HTTPHdr::USE_HDR_HEAP_MAGIC = reinterpret_cast<Arena*>(1); /*********************************************************************** @@ -1089,6 +1095,148 @@ http_parser_parse_req(HTTPParser *parser, HdrHeap *heap, HTTPHdrImpl *hh, const return mime_parser_parse(&parser->m_mime_parser, heap, hh->m_fields_impl, start, end, must_copy_strings, eof); } +MIMEParseResult +convert_from_2_to_1_1_header(HTTPHdr* headers) +{ + MIMEField* field; + + ink_assert(http_hdr_type_get(headers->m_http) != HTTP_TYPE_UNKNOWN); + + if (http_hdr_type_get(headers->m_http) == HTTP_TYPE_REQUEST) { + const char *scheme, *authority, *path, *method; + int scheme_len, authority_len, path_len, method_len; + + // Get values of :scheme, :authority and :path to assemble requested URL + if ((field = headers->field_find(HPACK_HEADER_SCHEME_STRING, strlen(HPACK_HEADER_SCHEME_STRING))) != NULL) { + scheme = field->value_get(&scheme_len); + } else { + return PARSE_ERROR; + } + if ((field = headers->field_find(HPACK_HEADER_AUTHORITY_STRING, strlen(HPACK_HEADER_AUTHORITY_STRING))) != NULL) { + authority = field->value_get(&authority_len); + } else { + return PARSE_ERROR; + } + if ((field = headers->field_find(HPACK_HEADER_PATH_STRING, strlen(HPACK_HEADER_PATH_STRING))) != NULL) { + path = field->value_get(&path_len); + } else { + return PARSE_ERROR; + } + + // Parse URL + Arena arena; + size_t url_length = scheme_len + 3 + authority_len + path_len; + char* url = arena.str_alloc(url_length); + const char* url_start = url; + strncpy(url, scheme, scheme_len); + strncpy(url+scheme_len, "://", 3); + strncpy(url+scheme_len+3, authority, authority_len); + strncpy(url+scheme_len+3+authority_len, path, path_len); + url_parse(headers->m_heap, headers->m_http->u.req.m_url_impl, &url_start, url + url_length, 1); + arena.str_free(url); + + // Get value of :method + if ((field = headers->field_find(HPACK_HEADER_METHOD_STRING, strlen(HPACK_HEADER_METHOD_STRING))) != NULL) { + method = field->value_get(&method_len); + + int method_wks_idx = hdrtoken_tokenize(method, method_len); + http_hdr_method_set(headers->m_heap, headers->m_http, + method, method_wks_idx, method_len, 0); + } else { + return PARSE_ERROR; + } + + // Convert HTTP version to 1.1 + int32_t version = HTTP_VERSION(1, 1); + http_hdr_version_set(headers->m_http, version); + + // Remove HTTP/2 style headers + headers->field_delete(HPACK_HEADER_SCHEME_STRING, strlen(HPACK_HEADER_SCHEME_STRING)); + headers->field_delete(HPACK_HEADER_METHOD_STRING, strlen(HPACK_HEADER_METHOD_STRING)); + headers->field_delete(HPACK_HEADER_AUTHORITY_STRING, strlen(HPACK_HEADER_AUTHORITY_STRING)); + headers->field_delete(HPACK_HEADER_PATH_STRING, strlen(HPACK_HEADER_PATH_STRING)); + } else { + int status_len; + const char* status; + + if ((field = headers->field_find(HPACK_HEADER_STATUS_STRING, strlen(HPACK_HEADER_STATUS_STRING))) != NULL) { + status = field->value_get(&status_len); + headers->status_set(http_parse_status(status, status + status_len)); + } else { + return PARSE_ERROR; + } + + // Remove HTTP/2 style headers + headers->field_delete(HPACK_HEADER_STATUS_STRING, strlen(HPACK_HEADER_STATUS_STRING)); + } + + return PARSE_DONE; +} + +int64_t +convert_from_1_1_to_2_header(HTTPHdr* in, uint8_t* out, uint64_t out_len, Http2HeaderTable& /* header_table */) +{ + uint8_t *p = out; + uint8_t *end = out + out_len; + int64_t len; + + ink_assert(http_hdr_type_get(in->m_http) != HTTP_TYPE_UNKNOWN); + + // TODO Get a index value from the tables for the header field, and then choose a representation type. + // TODO Each indexing types per field should be passed by a caller, HTTP/2 implementation. + + MIMEField* field; + MIMEFieldIter field_iter; + for (field = in->iter_get_first(&field_iter); field != NULL; field = in->iter_get_next(&field_iter)) { + do { + MIMEFieldWrapper header(field, in->m_heap, in->m_http->m_fields_impl); + if ((len = encode_literal_header_field(p, end, header, INC_INDEXING)) == -1) { + return -1; + } + p += len; + } while (field->has_dups() && (field = field->m_next_dup) != NULL); + } + + return p - out; +} + +MIMEParseResult +http2_parse_req(HdrHeap *heap, HTTPHdrImpl *hh, uint8_t* buf_start, uint8_t* buf_end, bool /* eof */, Http2HeaderTable& header_table) +{ + uint8_t* cursor = buf_start; + + do { + int64_t read_bytes = 0; + + if ((read_bytes = update_header_table_size(cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + + // decode a header field encoded by HPACK + MIMEField *field = mime_field_create(heap, hh->m_fields_impl); + MIMEFieldWrapper header(field, heap, hh->m_fields_impl); + if (*cursor & 0x80) { + if ((read_bytes = decode_indexed_header_field(header, cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + cursor += read_bytes; + } else { + if ((read_bytes = decode_literal_header_field(header, cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + cursor += read_bytes; + } + + // Store to HdrHeap + mime_hdr_field_attach(hh->m_fields_impl, field, 1, NULL); + } while (cursor < buf_end); + + // XXX I think that we need to check the eof flag so we can accurately report whether we parsed the whole + // header, though perhaps that's better done at the framing layer .. jpeach + + return PARSE_DONE; +} + /*------------------------------------------------------------------------- -------------------------------------------------------------------------*/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/HTTP.h ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HTTP.h b/proxy/hdrs/HTTP.h index 1605165..d531e83 100644 --- a/proxy/hdrs/HTTP.h +++ b/proxy/hdrs/HTTP.h @@ -24,12 +24,12 @@ #ifndef __HTTP_H__ #define __HTTP_H__ - #include <assert.h> #include "Arena.h" #include "INK_MD5.h" #include "MIME.h" #include "URL.h" +#include "HPACK.h" #include "ink_apidefs.h" @@ -37,6 +37,7 @@ #define HTTP_MINOR(v) ((v) & 0xFFFF) #define HTTP_MAJOR(v) (((v) >> 16) & 0xFFFF) +class Http2HeaderTable; enum HTTPStatus { @@ -470,6 +471,9 @@ MIMEParseResult http_parser_parse_req(HTTPParser *parser, HdrHeap *heap, MIMEParseResult http_parser_parse_resp(HTTPParser *parser, HdrHeap *heap, HTTPHdrImpl *hh, const char **start, const char *end, bool must_copy_strings, bool eof); + +MIMEParseResult http2_parse_req(HdrHeap *heap, HTTPHdrImpl *hh, uint8_t* buf_start, uint8_t* buf_end, bool eof, Http2HeaderTable& header_table); + HTTPStatus http_parse_status(const char *start, const char *end); int32_t http_parse_version(const char *start, const char *end); @@ -655,6 +659,8 @@ public: MIMEParseResult parse_req(HTTPParser *parser, IOBufferReader *r, int *bytes_used, bool eof); MIMEParseResult parse_resp(HTTPParser *parser, IOBufferReader *r, int *bytes_used, bool eof); + MIMEParseResult hpack_parse_req(uint8_t* start, uint8_t* end, bool eof, Http2HeaderTable& header_table); + public: // Utility routines bool is_cache_control_set(const char *cc_directive_wks); @@ -1220,6 +1226,21 @@ HTTPHdr::parse_req(HTTPParser *parser, const char **start, const char *end, bool /*------------------------------------------------------------------------- -------------------------------------------------------------------------*/ +/* + * Parse HTTP/2 headers encoded by HPACK and convert to HTTPHdr object + */ +inline MIMEParseResult +HTTPHdr::hpack_parse_req(uint8_t* start, uint8_t* end, bool eof, Http2HeaderTable& header_table) +{ + ink_assert(valid()); + ink_assert(m_http->m_polarity == HTTP_TYPE_REQUEST); + + return http2_parse_req(m_heap, m_http, start, end, eof, header_table); +} + +/*------------------------------------------------------------------------- + -------------------------------------------------------------------------*/ + inline MIMEParseResult HTTPHdr::parse_resp(HTTPParser *parser, const char **start, const char *end, bool eof) { @@ -1522,4 +1543,10 @@ HTTPInfo::get_frag_offset_count() { } +MIMEParseResult +convert_from_2_to_1_1_header(HTTPHdr* header); + +int64_t +convert_from_1_1_to_2_header(HTTPHdr* in, uint8_t* out, uint64_t out_len, Http2HeaderTable& header_table); + #endif /* __HTTP_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0711dc2a/proxy/hdrs/Makefile.am ---------------------------------------------------------------------- diff --git a/proxy/hdrs/Makefile.am b/proxy/hdrs/Makefile.am index a5be335..6a05299 100644 --- a/proxy/hdrs/Makefile.am +++ b/proxy/hdrs/Makefile.am @@ -41,7 +41,9 @@ libhdrs_a_SOURCES = \ MIME.cc \ MIME.h \ URL.cc \ - URL.h + URL.h \ + HPACKHuffman.cc \ + HPACK.cc if BUILD_TESTS libhdrs_a_SOURCES += \
