diff options
Diffstat (limited to 'src/hpack-tbl.c')
| -rw-r--r-- | src/hpack-tbl.c | 372 |
1 files changed, 372 insertions, 0 deletions
diff --git a/src/hpack-tbl.c b/src/hpack-tbl.c new file mode 100644 index 0000000..990d2f7 --- /dev/null +++ b/src/hpack-tbl.c @@ -0,0 +1,372 @@ +/* + * HPACK header table management (RFC7541) + * + * Copyright (C) 2014-2017 Willy Tarreau <willy@haproxy.org> + * Copyright (C) 2017 HAProxy Technologies + * + * 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 <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <import/ist.h> +#include <haproxy/hpack-huff.h> +#include <haproxy/hpack-tbl.h> + +/* static header table as in RFC7541 Appendix A. [0] unused. */ +const struct http_hdr hpack_sht[HPACK_SHT_SIZE] = { + [ 1] = { .n = IST(":authority"), .v = IST("") }, + [ 2] = { .n = IST(":method"), .v = IST("GET") }, + [ 3] = { .n = IST(":method"), .v = IST("POST") }, + [ 4] = { .n = IST(":path"), .v = IST("/") }, + [ 5] = { .n = IST(":path"), .v = IST("/index.html") }, + [ 6] = { .n = IST(":scheme"), .v = IST("http") }, + [ 7] = { .n = IST(":scheme"), .v = IST("https") }, + [ 8] = { .n = IST(":status"), .v = IST("200") }, + [ 9] = { .n = IST(":status"), .v = IST("204") }, + [10] = { .n = IST(":status"), .v = IST("206") }, + [11] = { .n = IST(":status"), .v = IST("304") }, + [12] = { .n = IST(":status"), .v = IST("400") }, + [13] = { .n = IST(":status"), .v = IST("404") }, + [14] = { .n = IST(":status"), .v = IST("500") }, + [15] = { .n = IST("accept-charset"), .v = IST("") }, + [16] = { .n = IST("accept-encoding"), .v = IST("gzip, deflate") }, + [17] = { .n = IST("accept-language"), .v = IST("") }, + [18] = { .n = IST("accept-ranges"), .v = IST("") }, + [19] = { .n = IST("accept"), .v = IST("") }, + [20] = { .n = IST("access-control-allow-origin"), .v = IST("") }, + [21] = { .n = IST("age"), .v = IST("") }, + [22] = { .n = IST("allow"), .v = IST("") }, + [23] = { .n = IST("authorization"), .v = IST("") }, + [24] = { .n = IST("cache-control"), .v = IST("") }, + [25] = { .n = IST("content-disposition"), .v = IST("") }, + [26] = { .n = IST("content-encoding"), .v = IST("") }, + [27] = { .n = IST("content-language"), .v = IST("") }, + [28] = { .n = IST("content-length"), .v = IST("") }, + [29] = { .n = IST("content-location"), .v = IST("") }, + [30] = { .n = IST("content-range"), .v = IST("") }, + [31] = { .n = IST("content-type") , .v = IST("") }, + [32] = { .n = IST("cookie"), .v = IST("") }, + [33] = { .n = IST("date"), .v = IST("") }, + [34] = { .n = IST("etag"), .v = IST("") }, + [35] = { .n = IST("expect"), .v = IST("") }, + [36] = { .n = IST("expires"), .v = IST("") }, + [37] = { .n = IST("from"), .v = IST("") }, + [38] = { .n = IST("host"), .v = IST("") }, + [39] = { .n = IST("if-match"), .v = IST("") }, + [40] = { .n = IST("if-modified-since"), .v = IST("") }, + [41] = { .n = IST("if-none-match"), .v = IST("") }, + [42] = { .n = IST("if-range"), .v = IST("") }, + [43] = { .n = IST("if-unmodified-since"), .v = IST("") }, + [44] = { .n = IST("last-modified"), .v = IST("") }, + [45] = { .n = IST("link"), .v = IST("") }, + [46] = { .n = IST("location"), .v = IST("") }, + [47] = { .n = IST("max-forwards"), .v = IST("") }, + [48] = { .n = IST("proxy-authenticate"), .v = IST("") }, + [49] = { .n = IST("proxy-authorization"), .v = IST("") }, + [50] = { .n = IST("range"), .v = IST("") }, + [51] = { .n = IST("referer"), .v = IST("") }, + [52] = { .n = IST("refresh"), .v = IST("") }, + [53] = { .n = IST("retry-after"), .v = IST("") }, + [54] = { .n = IST("server"), .v = IST("") }, + [55] = { .n = IST("set-cookie"), .v = IST("") }, + [56] = { .n = IST("strict-transport-security"), .v = IST("") }, + [57] = { .n = IST("transfer-encoding"), .v = IST("") }, + [58] = { .n = IST("user-agent"), .v = IST("") }, + [59] = { .n = IST("vary"), .v = IST("") }, + [60] = { .n = IST("via"), .v = IST("") }, + [61] = { .n = IST("www-authenticate"), .v = IST("") }, +}; + +struct pool_head *pool_head_hpack_tbl __read_mostly = NULL; + +#ifdef DEBUG_HPACK +/* dump the whole dynamic header table */ +void hpack_dht_dump(FILE *out, const struct hpack_dht *dht) +{ + unsigned int i; + unsigned int slot; + char name[4096], value[4096]; + + for (i = HPACK_SHT_SIZE; i < HPACK_SHT_SIZE + dht->used; i++) { + slot = (hpack_get_dte(dht, i - HPACK_SHT_SIZE + 1) - dht->dte); + fprintf(out, "idx=%u slot=%u name=<%s> value=<%s> addr=%u-%u\n", + i, slot, + istpad(name, hpack_idx_to_name(dht, i)).ptr, + istpad(value, hpack_idx_to_value(dht, i)).ptr, + dht->dte[slot].addr, dht->dte[slot].addr+dht->dte[slot].nlen+dht->dte[slot].vlen-1); + } +} + +/* check for the whole dynamic header table consistency, abort on failures */ +void hpack_dht_check_consistency(const struct hpack_dht *dht) +{ + unsigned slot = hpack_dht_get_tail(dht); + unsigned used2 = dht->used; + unsigned total = 0; + + if (!dht->used) + return; + + if (dht->front >= dht->wrap) + abort(); + + if (dht->used > dht->wrap) + abort(); + + if (dht->head >= dht->wrap) + abort(); + + while (used2--) { + total += dht->dte[slot].nlen + dht->dte[slot].vlen; + slot++; + if (slot >= dht->wrap) + slot = 0; + } + + if (total != dht->total) { + fprintf(stderr, "%d: total=%u dht=%u\n", __LINE__, total, dht->total); + abort(); + } +} +#endif // DEBUG_HPACK + +/* rebuild a new dynamic header table from <dht> with an unwrapped index and + * contents at the end. The new table is returned, the caller must not use the + * previous one anymore. NULL may be returned if no table could be allocated. + */ +static struct hpack_dht *hpack_dht_defrag(struct hpack_dht *dht) +{ + struct hpack_dht *alt_dht; + uint16_t old, new; + uint32_t addr; + + /* Note: for small tables we could use alloca() instead but + * portability especially for large tables can be problematic. + */ + alt_dht = hpack_dht_alloc(); + if (!alt_dht) + return NULL; + + alt_dht->total = dht->total; + alt_dht->used = dht->used; + alt_dht->wrap = dht->used; + + new = 0; + addr = alt_dht->size; + + if (dht->used) { + /* start from the tail */ + old = hpack_dht_get_tail(dht); + do { + alt_dht->dte[new].nlen = dht->dte[old].nlen; + alt_dht->dte[new].vlen = dht->dte[old].vlen; + addr -= dht->dte[old].nlen + dht->dte[old].vlen; + alt_dht->dte[new].addr = addr; + + memcpy((void *)alt_dht + alt_dht->dte[new].addr, + (void *)dht + dht->dte[old].addr, + dht->dte[old].nlen + dht->dte[old].vlen); + + old++; + if (old >= dht->wrap) + old = 0; + new++; + } while (new < dht->used); + } + + alt_dht->front = alt_dht->head = new - 1; + + memcpy(dht, alt_dht, dht->size); + hpack_dht_free(alt_dht); + + return dht; +} + +/* Purges table dht until a header field of <needed> bytes fits according to + * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero + * on failure (ie: table empty but still not sufficient). It must only be + * called when the table is not large enough to suit the new entry and there + * are some entries left. In case of doubt, use dht_make_room() instead. + */ +int __hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed) +{ + unsigned int used = dht->used; + unsigned int wrap = dht->wrap; + unsigned int tail; + + do { + tail = ((dht->head + 1U < used) ? wrap : 0) + dht->head + 1U - used; + dht->total -= dht->dte[tail].nlen + dht->dte[tail].vlen; + if (tail == dht->front) + dht->front = dht->head; + used--; + } while (used && used * 32 + dht->total + needed + 32 > dht->size); + + dht->used = used; + + /* realign if empty */ + if (!used) + dht->front = dht->head = 0; + + /* pack the table if it doesn't wrap anymore */ + if (dht->head + 1U >= used) + dht->wrap = dht->head + 1; + + /* no need to check for 'used' here as if it doesn't fit, used==0 */ + return needed + 32 <= dht->size; +} + +/* tries to insert a new header <name>:<value> in front of the current head. A + * negative value is returned on error. + */ +int hpack_dht_insert(struct hpack_dht *dht, struct ist name, struct ist value) +{ + unsigned int used; + unsigned int head; + unsigned int prev; + unsigned int wrap; + unsigned int tail; + uint32_t headroom, tailroom; + + if (!hpack_dht_make_room(dht, name.len + value.len)) + return 0; + + /* Now there is enough room in the table, that's guaranteed by the + * protocol, but not necessarily where we need it. + */ + + used = dht->used; + if (!used) { + /* easy, the table was empty */ + dht->front = dht->head = 0; + dht->wrap = dht->used = 1; + dht->total = 0; + head = 0; + dht->dte[head].addr = dht->size - (name.len + value.len); + goto copy; + } + + /* compute the new head, used and wrap position */ + prev = head = dht->head; + wrap = dht->wrap; + tail = hpack_dht_get_tail(dht); + + used++; + head++; + + if (head >= wrap) { + /* head is leading the entries, we either need to push the + * table further or to loop back to released entries. We could + * force to loop back when at least half of the allocatable + * entries are free but in practice it never happens. + */ + if ((sizeof(*dht) + (wrap + 1) * sizeof(dht->dte[0]) <= dht->dte[dht->front].addr)) + wrap++; + else if (head >= used) /* there's a hole at the beginning */ + head = 0; + else { + /* no more room, head hits tail and the index cannot be + * extended, we have to realign the whole table. + */ + if (!hpack_dht_defrag(dht)) + return -1; + + wrap = dht->wrap + 1; + head = dht->head + 1; + prev = head - 1; + tail = 0; + } + } + else if (used >= wrap) { + /* we've hit the tail, we need to reorganize the index so that + * the head is at the end (but not necessarily move the data). + */ + if (!hpack_dht_defrag(dht)) + return -1; + + wrap = dht->wrap + 1; + head = dht->head + 1; + prev = head - 1; + tail = 0; + } + + /* Now we have updated head, used and wrap, we know that there is some + * available room at least from the protocol's perspective. This space + * is split in two areas : + * + * 1: if the previous head was the front cell, the space between the + * end of the index table and the front cell's address. + * 2: if the previous head was the front cell, the space between the + * end of the tail and the end of the table ; or if the previous + * head was not the front cell, the space between the end of the + * tail and the head's address. + */ + if (prev == dht->front) { + /* the area was contiguous */ + headroom = dht->dte[dht->front].addr - (sizeof(*dht) + wrap * sizeof(dht->dte[0])); + tailroom = dht->size - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen; + } + else { + /* it's already wrapped so we can't store anything in the headroom */ + headroom = 0; + tailroom = dht->dte[prev].addr - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen; + } + + /* We can decide to stop filling the headroom as soon as there's enough + * room left in the tail to suit the protocol, but tests show that in + * practice it almost never happens in other situations so the extra + * test is useless and we simply fill the headroom as long as it's + * available and we don't wrap. + */ + if (prev == dht->front && headroom >= name.len + value.len) { + /* install upfront and update ->front */ + dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len); + dht->front = head; + } + else if (tailroom >= name.len + value.len) { + dht->dte[head].addr = dht->dte[tail].addr + dht->dte[tail].nlen + dht->dte[tail].vlen + tailroom - (name.len + value.len); + } + else { + /* need to defragment the table before inserting upfront */ + dht = hpack_dht_defrag(dht); + wrap = dht->wrap + 1; + head = dht->head + 1; + dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len); + dht->front = head; + } + + dht->wrap = wrap; + dht->head = head; + dht->used = used; + + copy: + dht->total += name.len + value.len; + dht->dte[head].nlen = name.len; + dht->dte[head].vlen = value.len; + + memcpy((void *)dht + dht->dte[head].addr, name.ptr, name.len); + memcpy((void *)dht + dht->dte[head].addr + name.len, value.ptr, value.len); + return 0; +} |