blob: ac6408c2c0ca28e7d1b134df55c905df686919cc [file] [log] [blame]
Willy Tarreauce040942017-05-30 18:46:58 +02001/*
2 * HPACK header table management (RFC7541)
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
Willy Tarreaua1bd1fa2019-03-29 17:26:33 +010028#include <inttypes.h>
Willy Tarreauce040942017-05-30 18:46:58 +020029#include <stdio.h>
30#include <stdlib.h>
31#include <string.h>
32
Willy Tarreaube327fa2020-06-03 09:09:57 +020033#include <haproxy/hpack-huff.h>
34#include <haproxy/hpack-tbl.h>
Willy Tarreaueb6f7012020-05-27 16:21:26 +020035#include <import/ist.h>
Willy Tarreauce040942017-05-30 18:46:58 +020036
Willy Tarreauce040942017-05-30 18:46:58 +020037/* static header table as in RFC7541 Appendix A. [0] unused. */
38const struct http_hdr hpack_sht[HPACK_SHT_SIZE] = {
39 [ 1] = { .n = IST(":authority"), .v = IST("") },
40 [ 2] = { .n = IST(":method"), .v = IST("GET") },
41 [ 3] = { .n = IST(":method"), .v = IST("POST") },
42 [ 4] = { .n = IST(":path"), .v = IST("/") },
43 [ 5] = { .n = IST(":path"), .v = IST("/index.html") },
44 [ 6] = { .n = IST(":scheme"), .v = IST("http") },
45 [ 7] = { .n = IST(":scheme"), .v = IST("https") },
46 [ 8] = { .n = IST(":status"), .v = IST("200") },
47 [ 9] = { .n = IST(":status"), .v = IST("204") },
48 [10] = { .n = IST(":status"), .v = IST("206") },
49 [11] = { .n = IST(":status"), .v = IST("304") },
50 [12] = { .n = IST(":status"), .v = IST("400") },
51 [13] = { .n = IST(":status"), .v = IST("404") },
52 [14] = { .n = IST(":status"), .v = IST("500") },
53 [15] = { .n = IST("accept-charset"), .v = IST("") },
54 [16] = { .n = IST("accept-encoding"), .v = IST("gzip, deflate") },
55 [17] = { .n = IST("accept-language"), .v = IST("") },
56 [18] = { .n = IST("accept-ranges"), .v = IST("") },
57 [19] = { .n = IST("accept"), .v = IST("") },
58 [20] = { .n = IST("access-control-allow-origin"), .v = IST("") },
59 [21] = { .n = IST("age"), .v = IST("") },
60 [22] = { .n = IST("allow"), .v = IST("") },
61 [23] = { .n = IST("authorization"), .v = IST("") },
62 [24] = { .n = IST("cache-control"), .v = IST("") },
63 [25] = { .n = IST("content-disposition"), .v = IST("") },
64 [26] = { .n = IST("content-encoding"), .v = IST("") },
65 [27] = { .n = IST("content-language"), .v = IST("") },
66 [28] = { .n = IST("content-length"), .v = IST("") },
67 [29] = { .n = IST("content-location"), .v = IST("") },
68 [30] = { .n = IST("content-range"), .v = IST("") },
69 [31] = { .n = IST("content-type") , .v = IST("") },
70 [32] = { .n = IST("cookie"), .v = IST("") },
71 [33] = { .n = IST("date"), .v = IST("") },
72 [34] = { .n = IST("etag"), .v = IST("") },
73 [35] = { .n = IST("expect"), .v = IST("") },
74 [36] = { .n = IST("expires"), .v = IST("") },
75 [37] = { .n = IST("from"), .v = IST("") },
76 [38] = { .n = IST("host"), .v = IST("") },
77 [39] = { .n = IST("if-match"), .v = IST("") },
78 [40] = { .n = IST("if-modified-since"), .v = IST("") },
79 [41] = { .n = IST("if-none-match"), .v = IST("") },
80 [42] = { .n = IST("if-range"), .v = IST("") },
81 [43] = { .n = IST("if-unmodified-since"), .v = IST("") },
82 [44] = { .n = IST("last-modified"), .v = IST("") },
83 [45] = { .n = IST("link"), .v = IST("") },
84 [46] = { .n = IST("location"), .v = IST("") },
85 [47] = { .n = IST("max-forwards"), .v = IST("") },
86 [48] = { .n = IST("proxy-authenticate"), .v = IST("") },
87 [49] = { .n = IST("proxy-authorization"), .v = IST("") },
88 [50] = { .n = IST("range"), .v = IST("") },
89 [51] = { .n = IST("referer"), .v = IST("") },
90 [52] = { .n = IST("refresh"), .v = IST("") },
91 [53] = { .n = IST("retry-after"), .v = IST("") },
92 [54] = { .n = IST("server"), .v = IST("") },
93 [55] = { .n = IST("set-cookie"), .v = IST("") },
94 [56] = { .n = IST("strict-transport-security"), .v = IST("") },
95 [57] = { .n = IST("transfer-encoding"), .v = IST("") },
96 [58] = { .n = IST("user-agent"), .v = IST("") },
97 [59] = { .n = IST("vary"), .v = IST("") },
98 [60] = { .n = IST("via"), .v = IST("") },
99 [61] = { .n = IST("www-authenticate"), .v = IST("") },
100};
101
Willy Tarreau2bdcc702020-05-19 11:31:11 +0200102struct pool_head *pool_head_hpack_tbl = NULL;
103
Willy Tarreauce040942017-05-30 18:46:58 +0200104/* returns the slot number of the oldest entry (tail). Must not be used on an
105 * empty table.
106 */
107static inline unsigned int hpack_dht_get_tail(const struct hpack_dht *dht)
108{
109 return ((dht->head + 1U < dht->used) ? dht->wrap : 0) + dht->head + 1U - dht->used;
110}
111
112#ifdef DEBUG_HPACK
113/* dump the whole dynamic header table */
Willy Tarreau4f034362017-12-30 17:08:46 +0100114static void hpack_dht_dump(FILE *out, const struct hpack_dht *dht)
Willy Tarreauce040942017-05-30 18:46:58 +0200115{
Willy Tarreau7f2a44d2018-09-17 14:07:33 +0200116 unsigned int i;
Willy Tarreauce040942017-05-30 18:46:58 +0200117 unsigned int slot;
118 char name[4096], value[4096];
119
120 for (i = HPACK_SHT_SIZE; i < HPACK_SHT_SIZE + dht->used; i++) {
121 slot = (hpack_get_dte(dht, i - HPACK_SHT_SIZE + 1) - dht->dte);
Willy Tarreau4f034362017-12-30 17:08:46 +0100122 fprintf(out, "idx=%d slot=%u name=<%s> value=<%s> addr=%u-%u\n",
Willy Tarreauce040942017-05-30 18:46:58 +0200123 i, slot,
124 istpad(name, hpack_idx_to_name(dht, i)).ptr,
125 istpad(value, hpack_idx_to_value(dht, i)).ptr,
126 dht->dte[slot].addr, dht->dte[slot].addr+dht->dte[slot].nlen+dht->dte[slot].vlen-1);
127 }
128}
129
130/* check for the whole dynamic header table consistency, abort on failures */
131static void hpack_dht_check_consistency(const struct hpack_dht *dht)
132{
133 unsigned slot = hpack_dht_get_tail(dht);
134 unsigned used2 = dht->used;
135 unsigned total = 0;
136
137 if (!dht->used)
138 return;
139
140 if (dht->front >= dht->wrap)
141 abort();
142
143 if (dht->used > dht->wrap)
144 abort();
145
146 if (dht->head >= dht->wrap)
147 abort();
148
149 while (used2--) {
150 total += dht->dte[slot].nlen + dht->dte[slot].vlen;
151 slot++;
152 if (slot >= dht->wrap)
153 slot = 0;
154 }
155
156 if (total != dht->total) {
157 fprintf(stderr, "%d: total=%u dht=%u\n", __LINE__, total, dht->total);
158 abort();
159 }
160}
161#endif // DEBUG_HPACK
162
163/* rebuild a new dynamic header table from <dht> with an unwrapped index and
164 * contents at the end. The new table is returned, the caller must not use the
165 * previous one anymore. NULL may be returned if no table could be allocated.
166 */
167static struct hpack_dht *hpack_dht_defrag(struct hpack_dht *dht)
168{
169 struct hpack_dht *alt_dht;
170 uint16_t old, new;
171 uint32_t addr;
172
173 /* Note: for small tables we could use alloca() instead but
174 * portability especially for large tables can be problematic.
175 */
Willy Tarreau2bdcc702020-05-19 11:31:11 +0200176 alt_dht = hpack_dht_alloc();
Willy Tarreauce040942017-05-30 18:46:58 +0200177 if (!alt_dht)
178 return NULL;
179
180 alt_dht->total = dht->total;
181 alt_dht->used = dht->used;
182 alt_dht->wrap = dht->used;
183
184 new = 0;
185 addr = alt_dht->size;
186
187 if (dht->used) {
188 /* start from the tail */
189 old = hpack_dht_get_tail(dht);
190 do {
191 alt_dht->dte[new].nlen = dht->dte[old].nlen;
192 alt_dht->dte[new].vlen = dht->dte[old].vlen;
193 addr -= dht->dte[old].nlen + dht->dte[old].vlen;
194 alt_dht->dte[new].addr = addr;
195
196 memcpy((void *)alt_dht + alt_dht->dte[new].addr,
197 (void *)dht + dht->dte[old].addr,
198 dht->dte[old].nlen + dht->dte[old].vlen);
199
200 old++;
201 if (old >= dht->wrap)
202 old = 0;
203 new++;
204 } while (new < dht->used);
205 }
206
207 alt_dht->front = alt_dht->head = new - 1;
208
209 memcpy(dht, alt_dht, dht->size);
210 hpack_dht_free(alt_dht);
211
212 return dht;
213}
214
215/* Purges table dht until a header field of <needed> bytes fits according to
216 * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero
217 * on failure (ie: table empty but still not sufficient). It must only be
218 * called when the table is not large enough to suit the new entry and there
219 * are some entries left. In case of doubt, use dht_make_room() instead.
220 */
221int __hpack_dht_make_room(struct hpack_dht *dht, unsigned int needed)
222{
223 unsigned int used = dht->used;
224 unsigned int wrap = dht->wrap;
225 unsigned int tail;
226
227 do {
228 tail = ((dht->head + 1U < used) ? wrap : 0) + dht->head + 1U - used;
229 dht->total -= dht->dte[tail].nlen + dht->dte[tail].vlen;
230 if (tail == dht->front)
231 dht->front = dht->head;
232 used--;
233 } while (used && used * 32 + dht->total + needed + 32 > dht->size);
234
235 dht->used = used;
236
237 /* realign if empty */
238 if (!used)
239 dht->front = dht->head = 0;
240
241 /* pack the table if it doesn't wrap anymore */
242 if (dht->head + 1U >= used)
243 dht->wrap = dht->head + 1;
244
245 /* no need to check for 'used' here as if it doesn't fit, used==0 */
246 return needed + 32 <= dht->size;
247}
248
249/* tries to insert a new header <name>:<value> in front of the current head. A
250 * negative value is returned on error.
251 */
252int hpack_dht_insert(struct hpack_dht *dht, struct ist name, struct ist value)
253{
254 unsigned int used;
255 unsigned int head;
256 unsigned int prev;
257 unsigned int wrap;
258 unsigned int tail;
259 uint32_t headroom, tailroom;
260
261 if (!hpack_dht_make_room(dht, name.len + value.len))
Willy Tarreau6c71e462017-12-04 17:58:37 +0100262 return 0;
Willy Tarreauce040942017-05-30 18:46:58 +0200263
Willy Tarreauce040942017-05-30 18:46:58 +0200264 /* Now there is enough room in the table, that's guaranteed by the
265 * protocol, but not necessarily where we need it.
266 */
267
Willy Tarreaua7394e12018-03-27 15:06:02 +0200268 used = dht->used;
Willy Tarreauce040942017-05-30 18:46:58 +0200269 if (!used) {
270 /* easy, the table was empty */
271 dht->front = dht->head = 0;
272 dht->wrap = dht->used = 1;
273 dht->total = 0;
274 head = 0;
275 dht->dte[head].addr = dht->size - (name.len + value.len);
276 goto copy;
277 }
278
279 /* compute the new head, used and wrap position */
Willy Tarreaua7394e12018-03-27 15:06:02 +0200280 prev = head = dht->head;
281 wrap = dht->wrap;
282 tail = hpack_dht_get_tail(dht);
283
Willy Tarreauce040942017-05-30 18:46:58 +0200284 used++;
285 head++;
286
287 if (head >= wrap) {
288 /* head is leading the entries, we either need to push the
289 * table further or to loop back to released entries. We could
290 * force to loop back when at least half of the allocatable
291 * entries are free but in practice it never happens.
292 */
293 if ((sizeof(*dht) + (wrap + 1) * sizeof(dht->dte[0]) <= dht->dte[dht->front].addr))
294 wrap++;
295 else if (head >= used) /* there's a hole at the beginning */
296 head = 0;
297 else {
298 /* no more room, head hits tail and the index cannot be
299 * extended, we have to realign the whole table.
300 */
301 if (!hpack_dht_defrag(dht))
302 return -1;
303
304 wrap = dht->wrap + 1;
305 head = dht->head + 1;
306 prev = head - 1;
307 tail = 0;
308 }
309 }
310 else if (used >= wrap) {
311 /* we've hit the tail, we need to reorganize the index so that
312 * the head is at the end (but not necessarily move the data).
313 */
314 if (!hpack_dht_defrag(dht))
315 return -1;
316
317 wrap = dht->wrap + 1;
318 head = dht->head + 1;
319 prev = head - 1;
320 tail = 0;
321 }
322
323 /* Now we have updated head, used and wrap, we know that there is some
324 * available room at least from the protocol's perspective. This space
325 * is split in two areas :
326 *
327 * 1: if the previous head was the front cell, the space between the
328 * end of the index table and the front cell's address.
329 * 2: if the previous head was the front cell, the space between the
330 * end of the tail and the end of the table ; or if the previous
331 * head was not the front cell, the space between the end of the
332 * tail and the head's address.
333 */
334 if (prev == dht->front) {
335 /* the area was contiguous */
336 headroom = dht->dte[dht->front].addr - (sizeof(*dht) + wrap * sizeof(dht->dte[0]));
337 tailroom = dht->size - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
338 }
339 else {
340 /* it's already wrapped so we can't store anything in the headroom */
341 headroom = 0;
342 tailroom = dht->dte[prev].addr - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
343 }
344
345 /* We can decide to stop filling the headroom as soon as there's enough
346 * room left in the tail to suit the protocol, but tests show that in
347 * practice it almost never happens in other situations so the extra
348 * test is useless and we simply fill the headroom as long as it's
Willy Tarreau5dfc5d52020-03-29 08:53:31 +0200349 * available and we don't wrap.
Willy Tarreauce040942017-05-30 18:46:58 +0200350 */
Willy Tarreau5dfc5d52020-03-29 08:53:31 +0200351 if (prev == dht->front && headroom >= name.len + value.len) {
Willy Tarreauce040942017-05-30 18:46:58 +0200352 /* install upfront and update ->front */
353 dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
354 dht->front = head;
355 }
356 else if (tailroom >= name.len + value.len) {
357 dht->dte[head].addr = dht->dte[tail].addr + dht->dte[tail].nlen + dht->dte[tail].vlen + tailroom - (name.len + value.len);
358 }
359 else {
360 /* need to defragment the table before inserting upfront */
361 dht = hpack_dht_defrag(dht);
362 wrap = dht->wrap + 1;
363 head = dht->head + 1;
364 dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
365 dht->front = head;
366 }
367
368 dht->wrap = wrap;
369 dht->head = head;
370 dht->used = used;
371
372 copy:
373 dht->total += name.len + value.len;
374 dht->dte[head].nlen = name.len;
375 dht->dte[head].vlen = value.len;
376
377 memcpy((void *)dht + dht->dte[head].addr, name.ptr, name.len);
378 memcpy((void *)dht + dht->dte[head].addr + name.len, value.ptr, value.len);
379 return 0;
380}