Gitiles
Code Review Sign In
git01.mediatek.com / haproxy / d7b7e0df9a6859f2029b74e3e2be630840d1df06 / . / src / qpack-tbl.c
blob: 6713f6dd399312b9aa62b94bca277985bcc7eae7 [file] [log] [blame]
Frédéric Lécaille164096e2020-12-22 16:01:57 +0100[diff] [blame]1/*
2 * QPACK header table management (draft-ietf-quic-qpack-20)
3 *
Willy Tarreau3dfb7da2022-03-02 22:33:39 +0100[diff] [blame]4 * Copyright 2020 HAProxy Technologies, Frederic Lecaille <flecaille@haproxy.com>
Frédéric Lécaille164096e2020-12-22 16:01:57 +0100[diff] [blame]5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 */
26
Frédéric Lécailleb4672fb2021-03-03 16:13:10 +0100[diff] [blame]27#include <inttypes.h>
28#include <stdio.h>
29
Frédéric Lécaille164096e2020-12-22 16:01:57 +0100[diff] [blame]30#include <import/ist.h>
31#include <haproxy/http-hdr-t.h>
Frédéric Lécailleb4672fb2021-03-03 16:13:10 +0100[diff] [blame]32#include <haproxy/qpack-tbl.h>
Frédéric Lécaille164096e2020-12-22 16:01:57 +0100[diff] [blame]33
Amaury Denoyelle484317e2021-08-24 15:36:39 +0200[diff] [blame]34/* static header table as in draft-ietf-quic-qpack-20 Appendix A. */
Frédéric Lécaille164096e2020-12-22 16:01:57 +0100[diff] [blame]35const struct http_hdr qpack_sht[QPACK_SHT_SIZE] = {
36 [ 0] = { .n = IST(":authority"), .v = IST("") },
37 [ 1] = { .n = IST(":path"), .v = IST("/") },
38 [ 2] = { .n = IST("age"), .v = IST("0") },
39 [ 3] = { .n = IST("content-disposition"), .v = IST("") },
40 [ 4] = { .n = IST("content-length"), .v = IST("0") },
41 [ 5] = { .n = IST("cookie"), .v = IST("") },
42 [ 6] = { .n = IST("date"), .v = IST("") },
43 [ 7] = { .n = IST("etag"), .v = IST("") },
44 [ 8] = { .n = IST("if-modified-since"), .v = IST("") },
45 [ 9] = { .n = IST("if-none-match"), .v = IST("") },
46 [10] = { .n = IST("last-modified"), .v = IST("") },
47 [11] = { .n = IST("link"), .v = IST("") },
48 [12] = { .n = IST("location"), .v = IST("") },
49 [13] = { .n = IST("referer"), .v = IST("") },
50 [14] = { .n = IST("set-cookie"), .v = IST("") },
51 [15] = { .n = IST(":method"), .v = IST("CONNECT") },
52 [16] = { .n = IST(":method"), .v = IST("DELETE") },
53 [17] = { .n = IST(":method"), .v = IST("GET") },
54 [18] = { .n = IST(":method"), .v = IST("HEAD") },
55 [19] = { .n = IST(":method"), .v = IST("OPTIONS") },
56 [20] = { .n = IST(":method"), .v = IST("POST") },
57 [21] = { .n = IST(":method"), .v = IST("PUT") },
58 [22] = { .n = IST(":scheme"), .v = IST("http") },
59 [23] = { .n = IST(":scheme"), .v = IST("https") },
60 [24] = { .n = IST(":status"), .v = IST("103") },
61 [25] = { .n = IST(":status"), .v = IST("200") },
62 [26] = { .n = IST(":status"), .v = IST("304") },
63 [27] = { .n = IST(":status"), .v = IST("404") },
64 [28] = { .n = IST(":status"), .v = IST("503") },
65 [29] = { .n = IST("accept"), .v = IST("*/*") },
66 [30] = { .n = IST("accept"), .v = IST("application/dns-message") },
67 [31] = { .n = IST("accept-encoding"), .v = IST("gzip, deflate, br") },
68 [32] = { .n = IST("accept-ranges"), .v = IST("bytes") },
69 [33] = { .n = IST("access-control-allow-headers"), .v = IST("cache-control") },
70 [34] = { .n = IST("access-control-allow-headers"), .v = IST("content-type") },
71 [35] = { .n = IST("access-control-allow-origin"), .v = IST("*") },
72 [36] = { .n = IST("cache-control"), .v = IST("max-age=0") },
73 [37] = { .n = IST("cache-control"), .v = IST("max-age=2592000") },
74 [38] = { .n = IST("cache-control"), .v = IST("max-age=604800") },
75 [39] = { .n = IST("cache-control"), .v = IST("no-cache") },
76 [40] = { .n = IST("cache-control"), .v = IST("no-store") },
77 [41] = { .n = IST("cache-control"), .v = IST("public, max-age=31536000") },
78 [42] = { .n = IST("content-encoding"), .v = IST("br") },
79 [43] = { .n = IST("content-encoding"), .v = IST("gzip") },
80 [44] = { .n = IST("content-type"), .v = IST("application/dns-message") },
81 [45] = { .n = IST("content-type"), .v = IST("application/javascript") },
82 [46] = { .n = IST("content-type"), .v = IST("application/json") },
83 [47] = { .n = IST("content-type"), .v = IST("application/"
84 "x-www-form-urlencoded") },
85 [48] = { .n = IST("content-type"), .v = IST("image/gif") },
86 [49] = { .n = IST("content-type"), .v = IST("image/jpeg") },
87 [50] = { .n = IST("content-type"), .v = IST("image/png") },
88 [51] = { .n = IST("content-type"), .v = IST("text/css") },
89 [52] = { .n = IST("content-type"), .v = IST("text/html;"
90 " charset=utf-8") },
91 [53] = { .n = IST("content-type"), .v = IST("text/plain") },
92 [54] = { .n = IST("content-type"), .v = IST("text/plain;"
93 "charset=utf-8") },
94 [55] = { .n = IST("range"), .v = IST("bytes=0-") },
95 [56] = { .n = IST("strict-transport-security"), .v = IST("max-age=31536000") },
96 [57] = { .n = IST("strict-transport-security"), .v = IST("max-age=31536000;"
97 " includesubdomains") },
98 [58] = { .n = IST("strict-transport-security"), .v = IST("max-age=31536000;"
99 " includesubdomains;"
100 " preload") },
101 [59] = { .n = IST("vary"), .v = IST("accept-encoding") },
102 [60] = { .n = IST("vary"), .v = IST("origin") },
103 [61] = { .n = IST("x-content-type-options"), .v = IST("nosniff") },
104 [62] = { .n = IST("x-xss-protection"), .v = IST("1; mode=block") },
105 [63] = { .n = IST(":status"), .v = IST("100") },
106 [64] = { .n = IST(":status"), .v = IST("204") },
107 [65] = { .n = IST(":status"), .v = IST("206") },
108 [66] = { .n = IST(":status"), .v = IST("302") },
109 [67] = { .n = IST(":status"), .v = IST("400") },
110 [68] = { .n = IST(":status"), .v = IST("403") },
111 [69] = { .n = IST(":status"), .v = IST("421") },
112 [70] = { .n = IST(":status"), .v = IST("425") },
113 [71] = { .n = IST(":status"), .v = IST("500") },
114 [72] = { .n = IST("accept-language"), .v = IST("") },
115 [73] = { .n = IST("access-control-allow-credentials"), .v = IST("FALSE") },
116 [74] = { .n = IST("access-control-allow-credentials"), .v = IST("TRUE") },
117 [75] = { .n = IST("access-control-allow-headers"), .v = IST("*") },
118 [76] = { .n = IST("access-control-allow-methods"), .v = IST("get") },
119 [77] = { .n = IST("access-control-allow-methods"), .v = IST("get, post, options") },
120 [78] = { .n = IST("access-control-allow-methods"), .v = IST("options") },
121 [79] = { .n = IST("access-control-expose-headers"), .v = IST("content-length") },
122 [80] = { .n = IST("access-control-request-headers"), .v = IST("content-type") },
123 [81] = { .n = IST("access-control-request-method"), .v = IST("get") },
124 [82] = { .n = IST("access-control-request-method"), .v = IST("post") },
125 [83] = { .n = IST("alt-svc"), .v = IST("clear") },
126 [84] = { .n = IST("authorization"), .v = IST("") },
127 [85] = { .n = IST("content-security-policy"), .v = IST("script-src 'none';"
128 " object-src 'none';"
129 " base-uri 'none'") },
130 [86] = { .n = IST("early-data"), .v = IST("1") },
131 [87] = { .n = IST("expect-ct"), .v = IST("") },
132 [88] = { .n = IST("forwarded"), .v = IST("") },
133 [89] = { .n = IST("if-range"), .v = IST("") },
134 [90] = { .n = IST("origin"), .v = IST("") },
135 [91] = { .n = IST("purpose"), .v = IST("prefetch") },
136 [92] = { .n = IST("server"), .v = IST("") },
137 [93] = { .n = IST("timing-allow-origin"), .v = IST("*") },
138 [94] = { .n = IST("upgrade-insecure-requests"), .v = IST("1") },
139 [95] = { .n = IST("user-agent"), .v = IST("") },
140 [96] = { .n = IST("x-forwarded-for"), .v = IST("") },
141 [97] = { .n = IST("x-frame-options"), .v = IST("deny") },
142 [98] = { .n = IST("x-frame-options"), .v = IST("sameorigin") },
143};
144
Frédéric Lécailleb4672fb2021-03-03 16:13:10 +0100[diff] [blame]145struct pool_head *pool_head_qpack_tbl = NULL;
146
147#ifdef DEBUG_HPACK
148/* dump the whole dynamic header table */
149void qpack_dht_dump(FILE *out, const struct qpack_dht *dht)
150{
151 unsigned int i;
152 unsigned int slot;
153 char name[4096], value[4096];
154
155 for (i = HPACK_SHT_SIZE; i < HPACK_SHT_SIZE + dht->used; i++) {
156 slot = (qpack_get_dte(dht, i - HPACK_SHT_SIZE + 1) - dht->dte);
157 fprintf(out, "idx=%d slot=%u name=<%s> value=<%s> addr=%u-%u\n",
158 i, slot,
159 istpad(name, qpack_idx_to_name(dht, i)).ptr,
160 istpad(value, qpack_idx_to_value(dht, i)).ptr,
161 dht->dte[slot].addr, dht->dte[slot].addr+dht->dte[slot].nlen+dht->dte[slot].vlen-1);
162 }
163}
164
165/* check for the whole dynamic header table consistency, abort on failures */
166void qpack_dht_check_consistency(const struct qpack_dht *dht)
167{
168 unsigned slot = qpack_dht_get_tail(dht);
169 unsigned used2 = dht->used;
170 unsigned total = 0;
171
172 if (!dht->used)
173 return;
174
175 if (dht->front >= dht->wrap)
176 abort();
177
178 if (dht->used > dht->wrap)
179 abort();
180
181 if (dht->head >= dht->wrap)
182 abort();
183
184 while (used2--) {
185 total += dht->dte[slot].nlen + dht->dte[slot].vlen;
186 slot++;
187 if (slot >= dht->wrap)
188 slot = 0;
189 }
190
191 if (total != dht->total) {
192 fprintf(stderr, "%d: total=%u dht=%u\n", __LINE__, total, dht->total);
193 abort();
194 }
195}
196#endif // DEBUG_HPACK
197
198/* rebuild a new dynamic header table from <dht> with an unwrapped index and
199 * contents at the end. The new table is returned, the caller must not use the
200 * previous one anymore. NULL may be returned if no table could be allocated.
201 */
202static struct qpack_dht *qpack_dht_defrag(struct qpack_dht *dht)
203{
204 struct qpack_dht *alt_dht;
205 uint16_t old, new;
206 uint32_t addr;
207
208 /* Note: for small tables we could use alloca() instead but
209 * portability especially for large tables can be problematic.
210 */
211 alt_dht = qpack_dht_alloc();
212 if (!alt_dht)
213 return NULL;
214
215 alt_dht->total = dht->total;
216 alt_dht->used = dht->used;
217 alt_dht->wrap = dht->used;
218
219 new = 0;
220 addr = alt_dht->size;
221
222 if (dht->used) {
223 /* start from the tail */
224 old = qpack_dht_get_tail(dht);
225 do {
226 alt_dht->dte[new].nlen = dht->dte[old].nlen;
227 alt_dht->dte[new].vlen = dht->dte[old].vlen;
228 addr -= dht->dte[old].nlen + dht->dte[old].vlen;
229 alt_dht->dte[new].addr = addr;
230
231 memcpy((void *)alt_dht + alt_dht->dte[new].addr,
232 (void *)dht + dht->dte[old].addr,
233 dht->dte[old].nlen + dht->dte[old].vlen);
234
235 old++;
236 if (old >= dht->wrap)
237 old = 0;
238 new++;
239 } while (new < dht->used);
240 }
241
242 alt_dht->front = alt_dht->head = new - 1;
243
244 memcpy(dht, alt_dht, dht->size);
245 qpack_dht_free(alt_dht);
246
247 return dht;
248}
249
250/* Purges table dht until a header field of <needed> bytes fits according to
251 * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero
252 * on failure (ie: table empty but still not sufficient). It must only be
253 * called when the table is not large enough to suit the new entry and there
254 * are some entries left. In case of doubt, use dht_make_room() instead.
255 */
256int __qpack_dht_make_room(struct qpack_dht *dht, unsigned int needed)
257{
258 unsigned int used = dht->used;
259 unsigned int wrap = dht->wrap;
260 unsigned int tail;
261
262 do {
263 tail = ((dht->head + 1U < used) ? wrap : 0) + dht->head + 1U - used;
264 dht->total -= dht->dte[tail].nlen + dht->dte[tail].vlen;
265 if (tail == dht->front)
266 dht->front = dht->head;
267 used--;
268 } while (used && used * 32 + dht->total + needed + 32 > dht->size);
269
270 dht->used = used;
271
272 /* realign if empty */
273 if (!used)
274 dht->front = dht->head = 0;
275
276 /* pack the table if it doesn't wrap anymore */
277 if (dht->head + 1U >= used)
278 dht->wrap = dht->head + 1;
279
280 /* no need to check for 'used' here as if it doesn't fit, used==0 */
281 return needed + 32 <= dht->size;
282}
283
284/* tries to insert a new header <name>:<value> in front of the current head. A
285 * negative value is returned on error.
286 */
287int qpack_dht_insert(struct qpack_dht *dht, struct ist name, struct ist value)
288{
289 unsigned int used;
290 unsigned int head;
291 unsigned int prev;
292 unsigned int wrap;
293 unsigned int tail;
294 uint32_t headroom, tailroom;
295
296 if (!qpack_dht_make_room(dht, name.len + value.len))
297 return 0;
298
299 /* Now there is enough room in the table, that's guaranteed by the
300 * protocol, but not necessarily where we need it.
301 */
302
303 used = dht->used;
304 if (!used) {
305 /* easy, the table was empty */
306 dht->front = dht->head = 0;
307 dht->wrap = dht->used = 1;
308 dht->total = 0;
309 head = 0;
310 dht->dte[head].addr = dht->size - (name.len + value.len);
311 goto copy;
312 }
313
314 /* compute the new head, used and wrap position */
315 prev = head = dht->head;
316 wrap = dht->wrap;
317 tail = qpack_dht_get_tail(dht);
318
319 used++;
320 head++;
321
322 if (head >= wrap) {
323 /* head is leading the entries, we either need to push the
324 * table further or to loop back to released entries. We could
325 * force to loop back when at least half of the allocatable
326 * entries are free but in practice it never happens.
327 */
328 if ((sizeof(*dht) + (wrap + 1) * sizeof(dht->dte[0]) <= dht->dte[dht->front].addr))
329 wrap++;
330 else if (head >= used) /* there's a hole at the beginning */
331 head = 0;
332 else {
333 /* no more room, head hits tail and the index cannot be
334 * extended, we have to realign the whole table.
335 */
336 if (!qpack_dht_defrag(dht))
337 return -1;
338
339 wrap = dht->wrap + 1;
340 head = dht->head + 1;
341 prev = head - 1;
342 tail = 0;
343 }
344 }
345 else if (used >= wrap) {
346 /* we've hit the tail, we need to reorganize the index so that
347 * the head is at the end (but not necessarily move the data).
348 */
349 if (!qpack_dht_defrag(dht))
350 return -1;
351
352 wrap = dht->wrap + 1;
353 head = dht->head + 1;
354 prev = head - 1;
355 tail = 0;
356 }
357
358 /* Now we have updated head, used and wrap, we know that there is some
359 * available room at least from the protocol's perspective. This space
360 * is split in two areas :
361 *
362 * 1: if the previous head was the front cell, the space between the
363 * end of the index table and the front cell's address.
364 * 2: if the previous head was the front cell, the space between the
365 * end of the tail and the end of the table ; or if the previous
366 * head was not the front cell, the space between the end of the
367 * tail and the head's address.
368 */
369 if (prev == dht->front) {
370 /* the area was contiguous */
371 headroom = dht->dte[dht->front].addr - (sizeof(*dht) + wrap * sizeof(dht->dte[0]));
372 tailroom = dht->size - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
373 }
374 else {
375 /* it's already wrapped so we can't store anything in the headroom */
376 headroom = 0;
377 tailroom = dht->dte[prev].addr - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
378 }
379
380 /* We can decide to stop filling the headroom as soon as there's enough
381 * room left in the tail to suit the protocol, but tests show that in
382 * practice it almost never happens in other situations so the extra
383 * test is useless and we simply fill the headroom as long as it's
384 * available and we don't wrap.
385 */
386 if (prev == dht->front && headroom >= name.len + value.len) {
387 /* install upfront and update ->front */
388 dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
389 dht->front = head;
390 }
391 else if (tailroom >= name.len + value.len) {
392 dht->dte[head].addr = dht->dte[tail].addr + dht->dte[tail].nlen + dht->dte[tail].vlen + tailroom - (name.len + value.len);
393 }
394 else {
395 /* need to defragment the table before inserting upfront */
396 dht = qpack_dht_defrag(dht);
397 wrap = dht->wrap + 1;
398 head = dht->head + 1;
399 dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
400 dht->front = head;
401 }
402
403 dht->wrap = wrap;
404 dht->head = head;
405 dht->used = used;
406
407 copy:
408 dht->total += name.len + value.len;
409 dht->dte[head].nlen = name.len;
410 dht->dte[head].vlen = value.len;
411
412 memcpy((void *)dht + dht->dte[head].addr, name.ptr, name.len);
413 memcpy((void *)dht + dht->dte[head].addr + name.len, value.ptr, value.len);
414 return 0;
415}