blob: 454f55cb7349996d4944d3327c435a198ded09bb [file] [log] [blame]
Willy Tarreau679790b2017-05-30 19:09:44 +02001/*
2 * HPACK decompressor (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
28#include <stdint.h>
29#include <stdio.h>
30#include <stdlib.h>
31#include <string.h>
32
33#include <common/hpack-dec.h>
34#include <common/hpack-huff.h>
35#include <common/hpack-tbl.h>
Willy Tarreau59a10fb2017-11-21 20:03:02 +010036#include <common/chunk.h>
Willy Tarreau679790b2017-05-30 19:09:44 +020037#include <common/ist.h>
38
39#include <types/global.h>
40
Willy Tarreau679790b2017-05-30 19:09:44 +020041
42#if defined(DEBUG_HPACK)
43#define hpack_debug_printf printf
44#else
45#define hpack_debug_printf(...) do { } while (0)
46#endif
47
48/* reads a varint from <raw>'s lowest <b> bits and <len> bytes max (raw included).
49 * returns the 32-bit value on success after updating raw_in and len_in. Forces
50 * len_in to (uint32_t)-1 on truncated input.
51 */
52static uint32_t get_var_int(const uint8_t **raw_in, uint32_t *len_in, int b)
53{
54 uint32_t ret = 0;
55 int len = *len_in;
56 const uint8_t *raw = *raw_in;
57 uint8_t shift = 0;
58
59 len--;
60 ret = *(raw++) & ((1 << b) - 1);
61 if (ret != (uint32_t)((1 << b) - 1))
62 goto end;
63
64 while (1) {
65 if (!len)
66 goto too_short;
67 if (!(*raw & 128))
68 break;
69 ret += ((uint32_t)(*raw++) & 127) << shift;
70 shift += 7;
71 len--;
72 }
73
74 /* last 7 bits */
75 if (!len)
76 goto too_short;
77 len--;
78 ret += ((uint32_t)(*raw++) & 127) << shift;
79
80 end:
81 *raw_in = raw;
82 *len_in = len;
83 return ret;
84
85 too_short:
86 *len_in = (uint32_t)-1;
87 return 0;
88}
89
Willy Tarreau59a10fb2017-11-21 20:03:02 +010090/* returns the pseudo-header <idx> corresponds to among the following values :
91 * - 0 = unknown, the header's string needs to be used instead
92 * - 1 = ":authority"
93 * - 2 = ":method"
94 * - 3 = ":path"
95 * - 4 = ":scheme"
96 * - 5 = ":status"
Willy Tarreau679790b2017-05-30 19:09:44 +020097 */
98static inline int hpack_idx_to_phdr(uint32_t idx)
99{
100 if (idx > 14)
101 return 0;
102
103 idx >>= 1;
104 idx <<= 2;
105 return (0x55554321U >> idx) & 0xF;
106}
107
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100108/* If <idx> designates a static header, returns <in>. Otherwise allocates some
109 * room from chunk <store> to duplicate <in> into it and returns the string
110 * allocated there. In case of allocation failure, returns a string whose
111 * pointer is NULL.
Willy Tarreau679790b2017-05-30 19:09:44 +0200112 */
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100113static inline struct ist hpack_alloc_string(struct chunk *store, int idx, struct ist in)
Willy Tarreau679790b2017-05-30 19:09:44 +0200114{
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100115 struct ist out;
Willy Tarreau679790b2017-05-30 19:09:44 +0200116
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100117 if (idx < HPACK_SHT_SIZE)
118 return in;
Willy Tarreau679790b2017-05-30 19:09:44 +0200119
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100120 out.len = in.len;
121 out.ptr = chunk_newstr(store);
122 if (unlikely(!out.ptr))
123 return out;
Willy Tarreau679790b2017-05-30 19:09:44 +0200124
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100125 if (unlikely(store->len + out.len > store->size)) {
126 out.ptr = NULL;
127 return out;
Willy Tarreau679790b2017-05-30 19:09:44 +0200128 }
129
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100130 store->len += out.len;
131 memcpy(out.ptr, in.ptr, out.len);
132 return out;
Willy Tarreau679790b2017-05-30 19:09:44 +0200133}
134
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100135/* decode an HPACK frame starting at <raw> for <len> bytes, using the dynamic
136 * headers table <dht>, produces the output into list <list> of <list_size>
137 * entries max, and uses pre-allocated buffer <tmp> for temporary storage (some
138 * list elements will point to it). Some <list> name entries may be made of a
139 * NULL pointer and a len, in which case they will designate a pseudo header
140 * index according to the values returned by hpack_idx_to_phdr() above. The
141 * number of <list> entries used is returned on success, or <0 on failure, with
142 * the opposite one of the HPACK_ERR_* codes. A last element is always zeroed
143 * and is not counted in the number of returned entries. This way the caller
144 * can use list[].n.len == 0 as a marker for the end of list.
Willy Tarreau679790b2017-05-30 19:09:44 +0200145 */
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100146int hpack_decode_frame(struct hpack_dht *dht, const uint8_t *raw, uint32_t len,
147 struct http_hdr *list, int list_size, struct chunk *tmp)
Willy Tarreau679790b2017-05-30 19:09:44 +0200148{
149 uint32_t idx;
150 uint32_t nlen;
151 uint32_t vlen;
152 uint8_t huff;
Willy Tarreau679790b2017-05-30 19:09:44 +0200153 struct ist name;
154 struct ist value;
Willy Tarreau679790b2017-05-30 19:09:44 +0200155 int must_index;
156 int ret;
Willy Tarreau679790b2017-05-30 19:09:44 +0200157
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100158 chunk_reset(tmp);
159 ret = 0;
Willy Tarreau679790b2017-05-30 19:09:44 +0200160 while (len) {
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100161 int __maybe_unused code = *raw; /* first byte, only for debugging */
Willy Tarreau679790b2017-05-30 19:09:44 +0200162
163 must_index = 0;
164 if (*raw >= 0x80) {
165 /* indexed header field */
166 if (*raw == 0x80) {
167 hpack_debug_printf("unhandled code 0x%02x (raw=%p, len=%d)\n", *raw, raw, len);
168 ret = -HPACK_ERR_UNKNOWN_OPCODE;
169 goto leave;
170 }
171
172 hpack_debug_printf("%02x: p14: indexed header field : ", code);
173
174 idx = get_var_int(&raw, &len, 7);
175 if (len == (uint32_t)-1) { // truncated
176 ret = -HPACK_ERR_TRUNCATED;
177 goto leave;
178 }
179
Willy Tarreaud85ba4e2017-12-03 12:12:17 +0100180 if (!hpack_valid_idx(dht, idx)) {
181 ret = -HPACK_ERR_TOO_LARGE;
182 goto leave;
183 }
184
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100185 value = hpack_alloc_string(tmp, idx, hpack_idx_to_value(dht, idx));
186 if (!value.ptr) {
187 ret = -HPACK_ERR_TOO_LARGE;
188 goto leave;
189 }
Willy Tarreau679790b2017-05-30 19:09:44 +0200190
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100191 /* here we don't index so we can always keep the pseudo header number */
192 name = ist2(NULL, hpack_idx_to_phdr(idx));
Willy Tarreau679790b2017-05-30 19:09:44 +0200193
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100194 if (!name.len) {
195 name = hpack_alloc_string(tmp, idx, hpack_idx_to_name(dht, idx));
196 if (!name.ptr) {
197 ret = -HPACK_ERR_TOO_LARGE;
198 goto leave;
199 }
200 }
201 /* <name> and <value> are now set and point to stable values */
Willy Tarreau679790b2017-05-30 19:09:44 +0200202 }
203 else if (*raw >= 0x20 && *raw <= 0x3f) {
204 /* max dyn table size change */
Willy Tarreauc611e662017-12-03 18:09:21 +0100205 if (ret) {
206 /* 7541#4.2.1 : DHT size update must only be at the beginning */
207 ret = -HPACK_ERR_TOO_LARGE;
208 goto leave;
209 }
210
Willy Tarreau679790b2017-05-30 19:09:44 +0200211 idx = get_var_int(&raw, &len, 5);
212 if (len == (uint32_t)-1) { // truncated
213 ret = -HPACK_ERR_TRUNCATED;
214 goto leave;
215 }
216 continue;
217 }
218 else if (!(*raw & (*raw - 0x10))) {
219 /* 0x00, 0x10, and 0x40 (0x20 and 0x80 were already handled above) */
220
221 /* literal header field without/never/with incremental indexing -- literal name */
222 if (*raw == 0x00)
223 hpack_debug_printf("%02x: p17: literal without indexing : ", code);
224 else if (*raw == 0x10)
225 hpack_debug_printf("%02x: p18: literal never indexed : ", code);
226 else if (*raw == 0x40)
227 hpack_debug_printf("%02x: p16: literal with indexing : ", code);
228
229 if (*raw == 0x40)
230 must_index = 1;
231
232 raw++; len--;
233
234 /* retrieve name */
235 if (!len) { // truncated
236 ret = -HPACK_ERR_TRUNCATED;
237 goto leave;
238 }
239
240 huff = *raw & 0x80;
241 nlen = get_var_int(&raw, &len, 7);
242 if (len == (uint32_t)-1 || len < nlen) { // truncated
243 ret = -HPACK_ERR_TRUNCATED;
244 goto leave;
245 }
246
247 name = ist2(raw, nlen);
248
249 raw += nlen;
250 len -= nlen;
Willy Tarreau679790b2017-05-30 19:09:44 +0200251
252 if (huff) {
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100253 char *ntrash = chunk_newstr(tmp);
254 if (!ntrash) {
255 ret = -HPACK_ERR_TOO_LARGE;
256 goto leave;
257 }
258
259 nlen = huff_dec((const uint8_t *)name.ptr, name.len, ntrash, tmp->size - tmp->len);
Willy Tarreau679790b2017-05-30 19:09:44 +0200260 if (nlen == (uint32_t)-1) {
261 hpack_debug_printf("2: can't decode huffman.\n");
262 ret = -HPACK_ERR_HUFFMAN;
263 goto leave;
264 }
265 tmp->len += nlen; // make room for the value
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100266 name = ist2(ntrash, nlen);
Willy Tarreau679790b2017-05-30 19:09:44 +0200267 }
268
269 /* retrieve value */
270 if (!len) { // truncated
271 ret = -HPACK_ERR_TRUNCATED;
272 goto leave;
273 }
274
275 huff = *raw & 0x80;
276 vlen = get_var_int(&raw, &len, 7);
277 if (len == (uint32_t)-1 || len < vlen) { // truncated
278 ret = -HPACK_ERR_TRUNCATED;
279 goto leave;
280 }
281
282 value = ist2(raw, vlen);
283 raw += vlen;
284 len -= vlen;
285
286 if (huff) {
287 char *vtrash = chunk_newstr(tmp);
288 if (!vtrash) {
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100289 ret = -HPACK_ERR_TOO_LARGE;
Willy Tarreau679790b2017-05-30 19:09:44 +0200290 goto leave;
291 }
292
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100293 vlen = huff_dec((const uint8_t *)value.ptr, value.len, vtrash, tmp->size - tmp->len);
Willy Tarreau679790b2017-05-30 19:09:44 +0200294 if (vlen == (uint32_t)-1) {
295 hpack_debug_printf("3: can't decode huffman.\n");
296 ret = -HPACK_ERR_HUFFMAN;
297 goto leave;
298 }
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100299 tmp->len += vlen; // make room for the value
Willy Tarreau679790b2017-05-30 19:09:44 +0200300 value = ist2(vtrash, vlen);
301 }
302
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100303 /* <name> and <value> are correctly filled here */
Willy Tarreau679790b2017-05-30 19:09:44 +0200304 }
305 else {
306 /* 0x01..0x0f : literal header field without indexing -- indexed name */
307 /* 0x11..0x1f : literal header field never indexed -- indexed name */
308 /* 0x41..0x7f : literal header field with incremental indexing -- indexed name */
309
310 if (*raw <= 0x0f)
311 hpack_debug_printf("%02x: p16: literal without indexing -- indexed name : ", code);
312 else if (*raw >= 0x41)
313 hpack_debug_printf("%02x: p15: literal with indexing -- indexed name : ", code);
314 else
315 hpack_debug_printf("%02x: p16: literal never indexed -- indexed name : ", code);
316
317 /* retrieve name index */
318 if (*raw >= 0x41) {
319 must_index = 1;
320 idx = get_var_int(&raw, &len, 6);
321 }
322 else
323 idx = get_var_int(&raw, &len, 4);
324
325 if (len == (uint32_t)-1 || !len) { // truncated
326 ret = -HPACK_ERR_TRUNCATED;
327 goto leave;
328 }
329
Willy Tarreaud85ba4e2017-12-03 12:12:17 +0100330 if (!hpack_valid_idx(dht, idx)) {
331 ret = -HPACK_ERR_TOO_LARGE;
332 goto leave;
333 }
334
Willy Tarreau679790b2017-05-30 19:09:44 +0200335 /* retrieve value */
336 huff = *raw & 0x80;
337 vlen = get_var_int(&raw, &len, 7);
338 if (len == (uint32_t)-1 || len < vlen) { // truncated
339 ret = -HPACK_ERR_TRUNCATED;
340 goto leave;
341 }
342
343 value = ist2(raw, vlen);
344 raw += vlen;
345 len -= vlen;
346
347 if (huff) {
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100348 char *vtrash = chunk_newstr(tmp);
349 if (!vtrash) {
350 ret = -HPACK_ERR_TOO_LARGE;
351 goto leave;
352 }
353
354 vlen = huff_dec((const uint8_t *)value.ptr, value.len, vtrash, tmp->size - tmp->len);
Willy Tarreau679790b2017-05-30 19:09:44 +0200355 if (vlen == (uint32_t)-1) {
356 hpack_debug_printf("1: can't decode huffman.\n");
357 ret = -HPACK_ERR_HUFFMAN;
358 goto leave;
359 }
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100360 tmp->len += vlen; // make room for the value
361 value = ist2(vtrash, vlen);
Willy Tarreau679790b2017-05-30 19:09:44 +0200362 }
363
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100364 name = ist2(NULL, 0);
365 if (!must_index)
366 name.len = hpack_idx_to_phdr(idx);
Willy Tarreau679790b2017-05-30 19:09:44 +0200367
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100368 if (!name.len)
369 name = hpack_idx_to_name(dht, idx);
370 /* <name> and <value> are correctly filled here */
Willy Tarreau679790b2017-05-30 19:09:44 +0200371 }
Willy Tarreau679790b2017-05-30 19:09:44 +0200372
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100373 /* here's what we have here :
374 * - name.len > 0
375 * - value is filled with either const data or data allocated from tmp
376 * - name.ptr == NULL && !must_index : known pseudo-header #name.len
377 * - name.ptr != NULL || must_index : general header, unknown pseudo-header or index needed
378 */
379 if (ret >= list_size) {
Willy Tarreau679790b2017-05-30 19:09:44 +0200380 ret = -HPACK_ERR_TOO_LARGE;
381 goto leave;
382 }
383
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100384 list[ret].n = name;
385 list[ret].v = value;
386 ret++;
Willy Tarreau679790b2017-05-30 19:09:44 +0200387
388 if (must_index && hpack_dht_insert(dht, name, value) < 0) {
389 hpack_debug_printf("failed to find some room in the dynamic table\n");
390 ret = -HPACK_ERR_DHT_INSERT_FAIL;
391 goto leave;
392 }
393
Willy Tarreau679790b2017-05-30 19:09:44 +0200394 hpack_debug_printf("\e[1;34m%s\e[0m: ",
Willy Tarreau9e28f452017-12-03 09:43:38 +0100395 istpad(trash.str, name.ptr ? name : hpack_idx_to_name(dht, idx)).ptr);
Willy Tarreau679790b2017-05-30 19:09:44 +0200396
397 hpack_debug_printf("\e[1;35m%s\e[0m [idx=%d, used=%d]\n",
398 istpad(trash.str, value).ptr,
399 must_index, dht->used);
Willy Tarreau679790b2017-05-30 19:09:44 +0200400 }
401
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100402 if (ret >= list_size) {
Willy Tarreau679790b2017-05-30 19:09:44 +0200403 ret = -HPACK_ERR_TOO_LARGE;
404 goto leave;
405 }
406
Willy Tarreau59a10fb2017-11-21 20:03:02 +0100407 /* put an end marker */
408 list[ret].n = list[ret].v = ist2(NULL, 0);
409 ret++;
Willy Tarreau679790b2017-05-30 19:09:44 +0200410
Willy Tarreau679790b2017-05-30 19:09:44 +0200411 leave:
412 return ret;
413}