Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 1 | /* |
| 2 | * HPACK header table management (RFC7541) - type definitions and prototypes |
| 3 | * |
| 4 | * Copyright (C) 2014-2017 Willy Tarreau <willy@haproxy.org> |
| 5 | * Copyright (C) 2017 HAProxy Technologies |
| 6 | * |
| 7 | * Permission is hereby granted, free of charge, to any person obtaining |
| 8 | * a copy of this software and associated documentation files (the |
| 9 | * "Software"), to deal in the Software without restriction, including |
| 10 | * without limitation the rights to use, copy, modify, merge, publish, |
| 11 | * distribute, sublicense, and/or sell copies of the Software, and to |
| 12 | * permit persons to whom the Software is furnished to do so, subject to |
| 13 | * the following conditions: |
| 14 | * |
| 15 | * The above copyright notice and this permission notice shall be |
| 16 | * included in all copies or substantial portions of the Software. |
| 17 | * |
| 18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 19 | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
| 20 | * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 21 | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| 22 | * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| 23 | * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 24 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| 25 | * OTHER DEALINGS IN THE SOFTWARE. |
| 26 | */ |
| 27 | #ifndef _COMMON_HPACK_TBL_H |
| 28 | #define _COMMON_HPACK_TBL_H |
| 29 | |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 30 | #include <stdlib.h> |
Willy Tarreau | 4c7e4b7 | 2020-05-27 12:58:42 +0200 | [diff] [blame] | 31 | #include <haproxy/api.h> |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 32 | #include <common/http-hdr.h> |
Willy Tarreau | eb6f701 | 2020-05-27 16:21:26 +0200 | [diff] [blame] | 33 | #include <import/ist.h> |
Willy Tarreau | 2bdcc70 | 2020-05-19 11:31:11 +0200 | [diff] [blame] | 34 | #include <common/memory.h> |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 35 | |
| 36 | /* Dynamic Headers Table, usable for tables up to 4GB long and values of 64kB-1. |
| 37 | * The model can be improved by using offsets relative to the table entry's end |
| 38 | * or to the end of the area, or by moving the descriptors at the end of the |
| 39 | * table and the data at the beginning. This entry is 8 bytes long, which is 1/4 |
| 40 | * of the bookkeeping planned by the HPACK spec. Thus it saves 24 bytes per |
| 41 | * header field, meaning that even with a single header, 24 extra bytes can be |
| 42 | * stored (ie one such descriptor). At 29.2 average bytes per header field as |
| 43 | * found in the hpack test case, that's slightly more than 1.5kB of space saved |
| 44 | * from a 4kB block, resulting in contiguous space almost always being |
| 45 | * available. |
| 46 | * |
| 47 | * Principle: the table is stored in a contiguous array containing both the |
| 48 | * descriptors and the contents. Descriptors are stored at the beginning of the |
| 49 | * array while contents are stored starting from the end. Most of the time there |
| 50 | * is enough room left in the table to insert a new header field, thanks to the |
| 51 | * savings on the descriptor size. Thus by inserting headers from the end it's |
| 52 | * possible to maximize the delay before a collision of DTEs and data. In order |
| 53 | * to always insert from the right, we need to keep a reference to the latest |
| 54 | * inserted element and look before it. The last inserted cell's address defines |
Ilya Shipitsin | 77e3b4a | 2020-03-10 12:06:11 +0500 | [diff] [blame] | 55 | * the lowest known address still in use, unless the area wraps in which case |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 56 | * the available space lies between the end of the tail and the beginning of the |
| 57 | * head. |
| 58 | * |
| 59 | * In order to detect collisions between data blocks and DTEs, we also maintain |
| 60 | * an index to the lowest element facing the DTE table, called "front". This one |
| 61 | * is updated each time an element is inserted before it. Once the buffer wraps, |
| 62 | * this element doesn't have to be updated anymore until it is released, in |
| 63 | * which case the buffer doesn't wrap anymore and the front element becomes the |
| 64 | * head again. |
| 65 | * |
| 66 | * Various heuristics are possible concerning the opportunity to wrap the |
| 67 | * entries to limit the risk of collisions with the DTE, but experimentation |
| 68 | * shows that thanks to the important savings made on the descriptors, the |
| 69 | * likeliness of finding a large amount of free space at the end of the area is |
| 70 | * much higher than the risk of colliding, so in the end the most naive |
| 71 | * algorithms work pretty fine. Typical ratios of 1 collision per 2000 requests |
| 72 | * have been observed. |
| 73 | * |
| 74 | * The defragmentation should be rare ; a study on live data shows on average |
| 75 | * 29.2 bytes used per header field. This plus the 32 bytes overhead fix an |
| 76 | * average of 66.9 header fields per 4kB table. This brings a 1606 bytes saving |
| 77 | * using the current storage description, ensuring that oldest headers are |
| 78 | * linearly removed by the sender before fragmentation occurs. This means that |
| 79 | * for all smaller header fields there will not be any requirement to defragment |
| 80 | * the area and most of the time it will even be possible to copy the old values |
| 81 | * directly within the buffer after creating a new entry. On average within the |
| 82 | * available space there will be enough room to store 1606/(29.2+8)=43 extra |
| 83 | * header fields without switching to another place. |
| 84 | * |
| 85 | * The table header fits in the table itself, it only takes 16 bytes, so in the |
| 86 | * worst case (1 single header) it's possible to store 4096 - 16 - 8 = 4072 |
| 87 | * data bytes, which is larger than the 4064 the protocol requires (4096 - 32). |
| 88 | */ |
| 89 | |
| 90 | /* One dynamic table entry descriptor */ |
| 91 | struct hpack_dte { |
| 92 | uint32_t addr; /* storage address, relative to the dte address */ |
| 93 | uint16_t nlen; /* header name length */ |
| 94 | uint16_t vlen; /* header value length */ |
| 95 | }; |
| 96 | |
| 97 | /* Note: the table's head plus a struct hpack_dte must be smaller than or equal to 32 |
| 98 | * bytes so that a single large header can always fit. Here that's 16 bytes for |
| 99 | * the header, plus 8 bytes per slot. |
| 100 | * Note that when <used> == 0, front, head, and wrap are undefined. |
| 101 | */ |
| 102 | struct hpack_dht { |
| 103 | uint32_t size; /* allocated table size in bytes */ |
| 104 | uint32_t total; /* sum of nlen + vlen in bytes */ |
| 105 | uint16_t front; /* slot number of the first node after the idx table */ |
| 106 | uint16_t wrap; /* number of allocated slots, wraps here */ |
| 107 | uint16_t head; /* last inserted slot number */ |
| 108 | uint16_t used; /* number of slots in use */ |
| 109 | struct hpack_dte dte[0]; /* dynamic table entries */ |
| 110 | }; |
| 111 | |
| 112 | /* supported hpack encoding/decoding errors */ |
| 113 | enum { |
| 114 | HPACK_ERR_NONE = 0, /* no error */ |
| 115 | HPACK_ERR_ALLOC_FAIL, /* memory allocation error */ |
| 116 | HPACK_ERR_UNKNOWN_OPCODE, /* invalid first byte */ |
| 117 | HPACK_ERR_TRUNCATED, /* truncated stream */ |
| 118 | HPACK_ERR_HUFFMAN, /* huffman decoding error */ |
| 119 | HPACK_ERR_INVALID_PHDR, /* invalid pseudo header field name */ |
| 120 | HPACK_ERR_MISPLACED_PHDR, /* pseudo header field after a regular header field */ |
| 121 | HPACK_ERR_DUPLICATE_PHDR, /* duplicate pseudo header field */ |
| 122 | HPACK_ERR_DHT_INSERT_FAIL, /* failed to insert into DHT */ |
| 123 | HPACK_ERR_TOO_LARGE, /* decoded request/response is too large */ |
| 124 | HPACK_ERR_MISSING_METHOD, /* :method is missing */ |
| 125 | HPACK_ERR_MISSING_SCHEME, /* :scheme is missing */ |
| 126 | HPACK_ERR_MISSING_PATH, /* :path is missing */ |
| 127 | HPACK_ERR_MISSING_AUTHORITY, /* :authority is missing with CONNECT */ |
| 128 | HPACK_ERR_SCHEME_NOT_ALLOWED, /* :scheme not allowed with CONNECT */ |
| 129 | HPACK_ERR_PATH_NOT_ALLOWED, /* :path not allowed with CONNECT */ |
Willy Tarreau | 1e7d444 | 2019-01-24 10:47:10 +0100 | [diff] [blame] | 130 | HPACK_ERR_INVALID_ARGUMENT, /* an invalid argument was passed */ |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 131 | }; |
| 132 | |
| 133 | /* static header table as in RFC7541 Appendix A. [0] unused. */ |
| 134 | #define HPACK_SHT_SIZE 62 |
| 135 | extern const struct http_hdr hpack_sht[HPACK_SHT_SIZE]; |
Willy Tarreau | 2bdcc70 | 2020-05-19 11:31:11 +0200 | [diff] [blame] | 136 | extern struct pool_head *pool_head_hpack_tbl; |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 137 | |
Willy Tarreau | 0ff9b3d | 2020-05-22 12:05:27 +0200 | [diff] [blame] | 138 | /* when built outside of haproxy, HPACK_STANDALONE must be defined, and |
| 139 | * pool_head_hpack_tbl->size must be set to the DHT size. |
| 140 | */ |
| 141 | #ifndef HPACK_STANDALONE |
| 142 | #define hpack_alloc(pool) pool_alloc(pool) |
| 143 | #define hpack_free(pool, ptr) pool_free(pool, ptr) |
| 144 | #else |
| 145 | #define hpack_alloc(pool) malloc(pool->size) |
| 146 | #define hpack_free(pool, ptr) free(ptr) |
| 147 | #endif |
| 148 | |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 149 | extern int __hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed); |
| 150 | extern int hpack_dht_insert(struct hpack_dht *dht, struct ist name, struct ist value); |
| 151 | |
| 152 | /* return a pointer to the entry designated by index <idx> (starting at 1) or |
| 153 | * NULL if this index is not there. |
| 154 | */ |
| 155 | static inline const struct hpack_dte *hpack_get_dte(const struct hpack_dht *dht, uint16_t idx) |
| 156 | { |
| 157 | idx--; |
| 158 | |
| 159 | if (idx >= dht->used) |
| 160 | return NULL; |
| 161 | |
| 162 | if (idx <= dht->head) |
| 163 | idx = dht->head - idx; |
| 164 | else |
| 165 | idx = dht->head - idx + dht->wrap; |
| 166 | |
| 167 | return &dht->dte[idx]; |
| 168 | } |
| 169 | |
Willy Tarreau | d85ba4e | 2017-12-03 12:12:17 +0100 | [diff] [blame] | 170 | /* returns non-zero if <idx> is valid for table <dht> */ |
Willy Tarreau | 7f2a44d | 2018-09-17 14:07:33 +0200 | [diff] [blame] | 171 | static inline int hpack_valid_idx(const struct hpack_dht *dht, uint32_t idx) |
Willy Tarreau | d85ba4e | 2017-12-03 12:12:17 +0100 | [diff] [blame] | 172 | { |
| 173 | return idx < dht->used + HPACK_SHT_SIZE; |
| 174 | } |
| 175 | |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 176 | /* return a pointer to the header name for entry <dte>. */ |
| 177 | static inline struct ist hpack_get_name(const struct hpack_dht *dht, const struct hpack_dte *dte) |
| 178 | { |
| 179 | struct ist ret = { |
| 180 | .ptr = (void *)dht + dte->addr, |
| 181 | .len = dte->nlen, |
| 182 | }; |
| 183 | return ret; |
| 184 | } |
| 185 | |
| 186 | /* return a pointer to the header value for entry <dte>. */ |
| 187 | static inline struct ist hpack_get_value(const struct hpack_dht *dht, const struct hpack_dte *dte) |
| 188 | { |
| 189 | struct ist ret = { |
| 190 | .ptr = (void *)dht + dte->addr + dte->nlen, |
| 191 | .len = dte->vlen, |
| 192 | }; |
| 193 | return ret; |
| 194 | } |
| 195 | |
| 196 | /* takes an idx, returns the associated name */ |
Willy Tarreau | 7f2a44d | 2018-09-17 14:07:33 +0200 | [diff] [blame] | 197 | static inline struct ist hpack_idx_to_name(const struct hpack_dht *dht, uint32_t idx) |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 198 | { |
| 199 | const struct hpack_dte *dte; |
| 200 | |
| 201 | if (idx < HPACK_SHT_SIZE) |
| 202 | return hpack_sht[idx].n; |
| 203 | |
| 204 | dte = hpack_get_dte(dht, idx - HPACK_SHT_SIZE + 1); |
| 205 | if (!dte) |
| 206 | return ist("### ERR ###"); // error |
| 207 | |
| 208 | return hpack_get_name(dht, dte); |
| 209 | } |
| 210 | |
| 211 | /* takes an idx, returns the associated value */ |
Willy Tarreau | 7f2a44d | 2018-09-17 14:07:33 +0200 | [diff] [blame] | 212 | static inline struct ist hpack_idx_to_value(const struct hpack_dht *dht, uint32_t idx) |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 213 | { |
| 214 | const struct hpack_dte *dte; |
| 215 | |
| 216 | if (idx < HPACK_SHT_SIZE) |
| 217 | return hpack_sht[idx].v; |
| 218 | |
| 219 | dte = hpack_get_dte(dht, idx - HPACK_SHT_SIZE + 1); |
| 220 | if (!dte) |
| 221 | return ist("### ERR ###"); // error |
| 222 | |
| 223 | return hpack_get_value(dht, dte); |
| 224 | } |
| 225 | |
| 226 | /* Purges table dht until a header field of <needed> bytes fits according to |
| 227 | * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero |
| 228 | * on failure (ie: table empty but still not sufficient). |
| 229 | */ |
| 230 | static inline int hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed) |
| 231 | { |
Willy Tarreau | 6c71e46 | 2017-12-04 17:58:37 +0100 | [diff] [blame] | 232 | if (dht->used * 32 + dht->total + needed + 32 <= dht->size) |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 233 | return 1; |
Willy Tarreau | 6c71e46 | 2017-12-04 17:58:37 +0100 | [diff] [blame] | 234 | else if (!dht->used) |
| 235 | return 0; |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 236 | |
| 237 | return __hpack_dht_make_room(dht, needed); |
| 238 | } |
| 239 | |
| 240 | /* allocate a dynamic headers table of <size> bytes and return it initialized */ |
| 241 | static inline void hpack_dht_init(struct hpack_dht *dht, uint32_t size) |
| 242 | { |
| 243 | dht->size = size; |
| 244 | dht->total = 0; |
| 245 | dht->used = 0; |
| 246 | } |
| 247 | |
Willy Tarreau | 2bdcc70 | 2020-05-19 11:31:11 +0200 | [diff] [blame] | 248 | /* allocate a dynamic headers table from the pool and return it initialized */ |
| 249 | static inline struct hpack_dht *hpack_dht_alloc() |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 250 | { |
| 251 | struct hpack_dht *dht; |
| 252 | |
Willy Tarreau | 2bdcc70 | 2020-05-19 11:31:11 +0200 | [diff] [blame] | 253 | if (unlikely(!pool_head_hpack_tbl)) |
| 254 | return NULL; |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 255 | |
Willy Tarreau | 0ff9b3d | 2020-05-22 12:05:27 +0200 | [diff] [blame] | 256 | dht = hpack_alloc(pool_head_hpack_tbl); |
Willy Tarreau | 2bdcc70 | 2020-05-19 11:31:11 +0200 | [diff] [blame] | 257 | if (dht) |
| 258 | hpack_dht_init(dht, pool_head_hpack_tbl->size); |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 259 | return dht; |
| 260 | } |
| 261 | |
| 262 | /* free a dynamic headers table */ |
| 263 | static inline void hpack_dht_free(struct hpack_dht *dht) |
| 264 | { |
Willy Tarreau | 0ff9b3d | 2020-05-22 12:05:27 +0200 | [diff] [blame] | 265 | hpack_free(pool_head_hpack_tbl, dht); |
Willy Tarreau | ce04094 | 2017-05-30 18:46:58 +0200 | [diff] [blame] | 266 | } |
| 267 | |
| 268 | #endif /* _COMMON_HPACK_TBL_H */ |