1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2013 Tatsuhiro Tsujikawa
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 OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "nghttp2_hd.h"
26
27 #include <string.h>
28 #include <assert.h>
29 #include <stdio.h>
30
31 #include "nghttp2_helper.h"
32 #include "nghttp2_int.h"
33 #include "nghttp2_debug.h"
34
35 /* Make scalar initialization form of nghttp2_hd_entry */
36 #define MAKE_STATIC_ENT(N, V, T, H) \
37 { \
38 {NULL, NULL, (uint8_t *)(N), sizeof((N)) - 1, -1}, \
39 {NULL, NULL, (uint8_t *)(V), sizeof((V)) - 1, -1}, \
40 {(uint8_t *)(N), (uint8_t *)(V), sizeof((N)) - 1, sizeof((V)) - 1, 0}, \
41 T, H \
42 }
43
44 /* Generated by mkstatictbl.py */
45 /* 3rd parameter is nghttp2_token value for header field name. We use
46 first enum value if same header names are repeated (e.g.,
47 :status). */
48 static const nghttp2_hd_static_entry static_table[] = {
49 MAKE_STATIC_ENT(":authority", "", 0, 3153725150u),
50 MAKE_STATIC_ENT(":method", "GET", 1, 695666056u),
51 MAKE_STATIC_ENT(":method", "POST", 1, 695666056u),
52 MAKE_STATIC_ENT(":path", "/", 3, 3292848686u),
53 MAKE_STATIC_ENT(":path", "/index.html", 3, 3292848686u),
54 MAKE_STATIC_ENT(":scheme", "http", 5, 2510477674u),
55 MAKE_STATIC_ENT(":scheme", "https", 5, 2510477674u),
56 MAKE_STATIC_ENT(":status", "200", 7, 4000288983u),
57 MAKE_STATIC_ENT(":status", "204", 7, 4000288983u),
58 MAKE_STATIC_ENT(":status", "206", 7, 4000288983u),
59 MAKE_STATIC_ENT(":status", "304", 7, 4000288983u),
60 MAKE_STATIC_ENT(":status", "400", 7, 4000288983u),
61 MAKE_STATIC_ENT(":status", "404", 7, 4000288983u),
62 MAKE_STATIC_ENT(":status", "500", 7, 4000288983u),
63 MAKE_STATIC_ENT("accept-charset", "", 14, 3664010344u),
64 MAKE_STATIC_ENT("accept-encoding", "gzip, deflate", 15, 3379649177u),
65 MAKE_STATIC_ENT("accept-language", "", 16, 1979086614u),
66 MAKE_STATIC_ENT("accept-ranges", "", 17, 1713753958u),
67 MAKE_STATIC_ENT("accept", "", 18, 136609321u),
68 MAKE_STATIC_ENT("access-control-allow-origin", "", 19, 2710797292u),
69 MAKE_STATIC_ENT("age", "", 20, 742476188u),
70 MAKE_STATIC_ENT("allow", "", 21, 2930878514u),
71 MAKE_STATIC_ENT("authorization", "", 22, 2436257726u),
72 MAKE_STATIC_ENT("cache-control", "", 23, 1355326669u),
73 MAKE_STATIC_ENT("content-disposition", "", 24, 3889184348u),
74 MAKE_STATIC_ENT("content-encoding", "", 25, 65203592u),
75 MAKE_STATIC_ENT("content-language", "", 26, 24973587u),
76 MAKE_STATIC_ENT("content-length", "", 27, 1308181789u),
77 MAKE_STATIC_ENT("content-location", "", 28, 2302364718u),
78 MAKE_STATIC_ENT("content-range", "", 29, 3555523146u),
79 MAKE_STATIC_ENT("content-type", "", 30, 4244048277u),
80 MAKE_STATIC_ENT("cookie", "", 31, 2007449791u),
81 MAKE_STATIC_ENT("date", "", 32, 3564297305u),
82 MAKE_STATIC_ENT("etag", "", 33, 113792960u),
83 MAKE_STATIC_ENT("expect", "", 34, 2530896728u),
84 MAKE_STATIC_ENT("expires", "", 35, 1049544579u),
85 MAKE_STATIC_ENT("from", "", 36, 2513272949u),
86 MAKE_STATIC_ENT("host", "", 37, 2952701295u),
87 MAKE_STATIC_ENT("if-match", "", 38, 3597694698u),
88 MAKE_STATIC_ENT("if-modified-since", "", 39, 2213050793u),
89 MAKE_STATIC_ENT("if-none-match", "", 40, 2536202615u),
90 MAKE_STATIC_ENT("if-range", "", 41, 2340978238u),
91 MAKE_STATIC_ENT("if-unmodified-since", "", 42, 3794814858u),
92 MAKE_STATIC_ENT("last-modified", "", 43, 3226950251u),
93 MAKE_STATIC_ENT("link", "", 44, 232457833u),
94 MAKE_STATIC_ENT("location", "", 45, 200649126u),
95 MAKE_STATIC_ENT("max-forwards", "", 46, 1826162134u),
96 MAKE_STATIC_ENT("proxy-authenticate", "", 47, 2709445359u),
97 MAKE_STATIC_ENT("proxy-authorization", "", 48, 2686392507u),
98 MAKE_STATIC_ENT("range", "", 49, 4208725202u),
99 MAKE_STATIC_ENT("referer", "", 50, 3969579366u),
100 MAKE_STATIC_ENT("refresh", "", 51, 3572655668u),
101 MAKE_STATIC_ENT("retry-after", "", 52, 3336180598u),
102 MAKE_STATIC_ENT("server", "", 53, 1085029842u),
103 MAKE_STATIC_ENT("set-cookie", "", 54, 1848371000u),
104 MAKE_STATIC_ENT("strict-transport-security", "", 55, 4138147361u),
105 MAKE_STATIC_ENT("transfer-encoding", "", 56, 3719590988u),
106 MAKE_STATIC_ENT("user-agent", "", 57, 606444526u),
107 MAKE_STATIC_ENT("vary", "", 58, 1085005381u),
108 MAKE_STATIC_ENT("via", "", 59, 1762798611u),
109 MAKE_STATIC_ENT("www-authenticate", "", 60, 779865858u),
110 };
111
memeq(const void * s1,const void * s2,size_t n)112 static int memeq(const void *s1, const void *s2, size_t n) {
113 return memcmp(s1, s2, n) == 0;
114 }
115
116 /*
117 * This function was generated by genlibtokenlookup.py. Inspired by
118 * h2o header lookup. https://github.com/h2o/h2o
119 */
lookup_token(const uint8_t * name,size_t namelen)120 static int32_t lookup_token(const uint8_t *name, size_t namelen) {
121 switch (namelen) {
122 case 2:
123 switch (name[1]) {
124 case 'e':
125 if (memeq("t", name, 1)) {
126 return NGHTTP2_TOKEN_TE;
127 }
128 break;
129 }
130 break;
131 case 3:
132 switch (name[2]) {
133 case 'a':
134 if (memeq("vi", name, 2)) {
135 return NGHTTP2_TOKEN_VIA;
136 }
137 break;
138 case 'e':
139 if (memeq("ag", name, 2)) {
140 return NGHTTP2_TOKEN_AGE;
141 }
142 break;
143 }
144 break;
145 case 4:
146 switch (name[3]) {
147 case 'e':
148 if (memeq("dat", name, 3)) {
149 return NGHTTP2_TOKEN_DATE;
150 }
151 break;
152 case 'g':
153 if (memeq("eta", name, 3)) {
154 return NGHTTP2_TOKEN_ETAG;
155 }
156 break;
157 case 'k':
158 if (memeq("lin", name, 3)) {
159 return NGHTTP2_TOKEN_LINK;
160 }
161 break;
162 case 'm':
163 if (memeq("fro", name, 3)) {
164 return NGHTTP2_TOKEN_FROM;
165 }
166 break;
167 case 't':
168 if (memeq("hos", name, 3)) {
169 return NGHTTP2_TOKEN_HOST;
170 }
171 break;
172 case 'y':
173 if (memeq("var", name, 3)) {
174 return NGHTTP2_TOKEN_VARY;
175 }
176 break;
177 }
178 break;
179 case 5:
180 switch (name[4]) {
181 case 'e':
182 if (memeq("rang", name, 4)) {
183 return NGHTTP2_TOKEN_RANGE;
184 }
185 break;
186 case 'h':
187 if (memeq(":pat", name, 4)) {
188 return NGHTTP2_TOKEN__PATH;
189 }
190 break;
191 case 'w':
192 if (memeq("allo", name, 4)) {
193 return NGHTTP2_TOKEN_ALLOW;
194 }
195 break;
196 }
197 break;
198 case 6:
199 switch (name[5]) {
200 case 'e':
201 if (memeq("cooki", name, 5)) {
202 return NGHTTP2_TOKEN_COOKIE;
203 }
204 break;
205 case 'r':
206 if (memeq("serve", name, 5)) {
207 return NGHTTP2_TOKEN_SERVER;
208 }
209 break;
210 case 't':
211 if (memeq("accep", name, 5)) {
212 return NGHTTP2_TOKEN_ACCEPT;
213 }
214 if (memeq("expec", name, 5)) {
215 return NGHTTP2_TOKEN_EXPECT;
216 }
217 break;
218 }
219 break;
220 case 7:
221 switch (name[6]) {
222 case 'd':
223 if (memeq(":metho", name, 6)) {
224 return NGHTTP2_TOKEN__METHOD;
225 }
226 break;
227 case 'e':
228 if (memeq(":schem", name, 6)) {
229 return NGHTTP2_TOKEN__SCHEME;
230 }
231 if (memeq("upgrad", name, 6)) {
232 return NGHTTP2_TOKEN_UPGRADE;
233 }
234 break;
235 case 'h':
236 if (memeq("refres", name, 6)) {
237 return NGHTTP2_TOKEN_REFRESH;
238 }
239 break;
240 case 'r':
241 if (memeq("refere", name, 6)) {
242 return NGHTTP2_TOKEN_REFERER;
243 }
244 break;
245 case 's':
246 if (memeq(":statu", name, 6)) {
247 return NGHTTP2_TOKEN__STATUS;
248 }
249 if (memeq("expire", name, 6)) {
250 return NGHTTP2_TOKEN_EXPIRES;
251 }
252 break;
253 }
254 break;
255 case 8:
256 switch (name[7]) {
257 case 'e':
258 if (memeq("if-rang", name, 7)) {
259 return NGHTTP2_TOKEN_IF_RANGE;
260 }
261 break;
262 case 'h':
263 if (memeq("if-matc", name, 7)) {
264 return NGHTTP2_TOKEN_IF_MATCH;
265 }
266 break;
267 case 'n':
268 if (memeq("locatio", name, 7)) {
269 return NGHTTP2_TOKEN_LOCATION;
270 }
271 break;
272 case 'y':
273 if (memeq("priorit", name, 7)) {
274 return NGHTTP2_TOKEN_PRIORITY;
275 }
276 break;
277 }
278 break;
279 case 9:
280 switch (name[8]) {
281 case 'l':
282 if (memeq(":protoco", name, 8)) {
283 return NGHTTP2_TOKEN__PROTOCOL;
284 }
285 break;
286 }
287 break;
288 case 10:
289 switch (name[9]) {
290 case 'e':
291 if (memeq("keep-aliv", name, 9)) {
292 return NGHTTP2_TOKEN_KEEP_ALIVE;
293 }
294 if (memeq("set-cooki", name, 9)) {
295 return NGHTTP2_TOKEN_SET_COOKIE;
296 }
297 break;
298 case 'n':
299 if (memeq("connectio", name, 9)) {
300 return NGHTTP2_TOKEN_CONNECTION;
301 }
302 break;
303 case 't':
304 if (memeq("user-agen", name, 9)) {
305 return NGHTTP2_TOKEN_USER_AGENT;
306 }
307 break;
308 case 'y':
309 if (memeq(":authorit", name, 9)) {
310 return NGHTTP2_TOKEN__AUTHORITY;
311 }
312 break;
313 }
314 break;
315 case 11:
316 switch (name[10]) {
317 case 'r':
318 if (memeq("retry-afte", name, 10)) {
319 return NGHTTP2_TOKEN_RETRY_AFTER;
320 }
321 break;
322 }
323 break;
324 case 12:
325 switch (name[11]) {
326 case 'e':
327 if (memeq("content-typ", name, 11)) {
328 return NGHTTP2_TOKEN_CONTENT_TYPE;
329 }
330 break;
331 case 's':
332 if (memeq("max-forward", name, 11)) {
333 return NGHTTP2_TOKEN_MAX_FORWARDS;
334 }
335 break;
336 }
337 break;
338 case 13:
339 switch (name[12]) {
340 case 'd':
341 if (memeq("last-modifie", name, 12)) {
342 return NGHTTP2_TOKEN_LAST_MODIFIED;
343 }
344 break;
345 case 'e':
346 if (memeq("content-rang", name, 12)) {
347 return NGHTTP2_TOKEN_CONTENT_RANGE;
348 }
349 break;
350 case 'h':
351 if (memeq("if-none-matc", name, 12)) {
352 return NGHTTP2_TOKEN_IF_NONE_MATCH;
353 }
354 break;
355 case 'l':
356 if (memeq("cache-contro", name, 12)) {
357 return NGHTTP2_TOKEN_CACHE_CONTROL;
358 }
359 break;
360 case 'n':
361 if (memeq("authorizatio", name, 12)) {
362 return NGHTTP2_TOKEN_AUTHORIZATION;
363 }
364 break;
365 case 's':
366 if (memeq("accept-range", name, 12)) {
367 return NGHTTP2_TOKEN_ACCEPT_RANGES;
368 }
369 break;
370 }
371 break;
372 case 14:
373 switch (name[13]) {
374 case 'h':
375 if (memeq("content-lengt", name, 13)) {
376 return NGHTTP2_TOKEN_CONTENT_LENGTH;
377 }
378 break;
379 case 't':
380 if (memeq("accept-charse", name, 13)) {
381 return NGHTTP2_TOKEN_ACCEPT_CHARSET;
382 }
383 break;
384 }
385 break;
386 case 15:
387 switch (name[14]) {
388 case 'e':
389 if (memeq("accept-languag", name, 14)) {
390 return NGHTTP2_TOKEN_ACCEPT_LANGUAGE;
391 }
392 break;
393 case 'g':
394 if (memeq("accept-encodin", name, 14)) {
395 return NGHTTP2_TOKEN_ACCEPT_ENCODING;
396 }
397 break;
398 }
399 break;
400 case 16:
401 switch (name[15]) {
402 case 'e':
403 if (memeq("content-languag", name, 15)) {
404 return NGHTTP2_TOKEN_CONTENT_LANGUAGE;
405 }
406 if (memeq("www-authenticat", name, 15)) {
407 return NGHTTP2_TOKEN_WWW_AUTHENTICATE;
408 }
409 break;
410 case 'g':
411 if (memeq("content-encodin", name, 15)) {
412 return NGHTTP2_TOKEN_CONTENT_ENCODING;
413 }
414 break;
415 case 'n':
416 if (memeq("content-locatio", name, 15)) {
417 return NGHTTP2_TOKEN_CONTENT_LOCATION;
418 }
419 if (memeq("proxy-connectio", name, 15)) {
420 return NGHTTP2_TOKEN_PROXY_CONNECTION;
421 }
422 break;
423 }
424 break;
425 case 17:
426 switch (name[16]) {
427 case 'e':
428 if (memeq("if-modified-sinc", name, 16)) {
429 return NGHTTP2_TOKEN_IF_MODIFIED_SINCE;
430 }
431 break;
432 case 'g':
433 if (memeq("transfer-encodin", name, 16)) {
434 return NGHTTP2_TOKEN_TRANSFER_ENCODING;
435 }
436 break;
437 }
438 break;
439 case 18:
440 switch (name[17]) {
441 case 'e':
442 if (memeq("proxy-authenticat", name, 17)) {
443 return NGHTTP2_TOKEN_PROXY_AUTHENTICATE;
444 }
445 break;
446 }
447 break;
448 case 19:
449 switch (name[18]) {
450 case 'e':
451 if (memeq("if-unmodified-sinc", name, 18)) {
452 return NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE;
453 }
454 break;
455 case 'n':
456 if (memeq("content-dispositio", name, 18)) {
457 return NGHTTP2_TOKEN_CONTENT_DISPOSITION;
458 }
459 if (memeq("proxy-authorizatio", name, 18)) {
460 return NGHTTP2_TOKEN_PROXY_AUTHORIZATION;
461 }
462 break;
463 }
464 break;
465 case 25:
466 switch (name[24]) {
467 case 'y':
468 if (memeq("strict-transport-securit", name, 24)) {
469 return NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY;
470 }
471 break;
472 }
473 break;
474 case 27:
475 switch (name[26]) {
476 case 'n':
477 if (memeq("access-control-allow-origi", name, 26)) {
478 return NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN;
479 }
480 break;
481 }
482 break;
483 }
484 return -1;
485 }
486
nghttp2_hd_entry_init(nghttp2_hd_entry * ent,nghttp2_hd_nv * nv)487 void nghttp2_hd_entry_init(nghttp2_hd_entry *ent, nghttp2_hd_nv *nv) {
488 ent->nv = *nv;
489 ent->cnv.name = nv->name->base;
490 ent->cnv.namelen = nv->name->len;
491 ent->cnv.value = nv->value->base;
492 ent->cnv.valuelen = nv->value->len;
493 ent->cnv.flags = nv->flags;
494 ent->next = NULL;
495 ent->hash = 0;
496
497 nghttp2_rcbuf_incref(ent->nv.name);
498 nghttp2_rcbuf_incref(ent->nv.value);
499 }
500
nghttp2_hd_entry_free(nghttp2_hd_entry * ent)501 void nghttp2_hd_entry_free(nghttp2_hd_entry *ent) {
502 nghttp2_rcbuf_decref(ent->nv.value);
503 nghttp2_rcbuf_decref(ent->nv.name);
504 }
505
name_eq(const nghttp2_hd_nv * a,const nghttp2_nv * b)506 static int name_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
507 return a->name->len == b->namelen &&
508 memeq(a->name->base, b->name, b->namelen);
509 }
510
value_eq(const nghttp2_hd_nv * a,const nghttp2_nv * b)511 static int value_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
512 return a->value->len == b->valuelen &&
513 memeq(a->value->base, b->value, b->valuelen);
514 }
515
name_hash(const nghttp2_nv * nv)516 static uint32_t name_hash(const nghttp2_nv *nv) {
517 /* 32 bit FNV-1a: http://isthe.com/chongo/tech/comp/fnv/ */
518 uint32_t h = 2166136261u;
519 size_t i;
520
521 for (i = 0; i < nv->namelen; ++i) {
522 h ^= nv->name[i];
523 h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
524 }
525
526 return h;
527 }
528
hd_map_init(nghttp2_hd_map * map)529 static void hd_map_init(nghttp2_hd_map *map) {
530 memset(map, 0, sizeof(nghttp2_hd_map));
531 }
532
hd_map_insert(nghttp2_hd_map * map,nghttp2_hd_entry * ent)533 static void hd_map_insert(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
534 nghttp2_hd_entry **bucket;
535
536 bucket = &map->table[ent->hash & (HD_MAP_SIZE - 1)];
537
538 if (*bucket == NULL) {
539 *bucket = ent;
540 return;
541 }
542
543 /* lower index is linked near the root */
544 ent->next = *bucket;
545 *bucket = ent;
546 }
547
hd_map_find(nghttp2_hd_map * map,int * exact_match,const nghttp2_nv * nv,int32_t token,uint32_t hash,int name_only)548 static nghttp2_hd_entry *hd_map_find(nghttp2_hd_map *map, int *exact_match,
549 const nghttp2_nv *nv, int32_t token,
550 uint32_t hash, int name_only) {
551 nghttp2_hd_entry *p;
552 nghttp2_hd_entry *res = NULL;
553
554 *exact_match = 0;
555
556 for (p = map->table[hash & (HD_MAP_SIZE - 1)]; p; p = p->next) {
557 if (token != p->nv.token ||
558 (token == -1 && (hash != p->hash || !name_eq(&p->nv, nv)))) {
559 continue;
560 }
561 if (!res) {
562 res = p;
563 if (name_only) {
564 break;
565 }
566 }
567 if (value_eq(&p->nv, nv)) {
568 res = p;
569 *exact_match = 1;
570 break;
571 }
572 }
573
574 return res;
575 }
576
hd_map_remove(nghttp2_hd_map * map,nghttp2_hd_entry * ent)577 static void hd_map_remove(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
578 nghttp2_hd_entry **dst;
579
580 dst = &map->table[ent->hash & (HD_MAP_SIZE - 1)];
581
582 for (; *dst; dst = &(*dst)->next) {
583 if (*dst != ent) {
584 continue;
585 }
586
587 *dst = ent->next;
588 ent->next = NULL;
589 return;
590 }
591 }
592
hd_ringbuf_init(nghttp2_hd_ringbuf * ringbuf,size_t bufsize,nghttp2_mem * mem)593 static int hd_ringbuf_init(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
594 nghttp2_mem *mem) {
595 size_t size;
596 for (size = 1; size < bufsize; size <<= 1)
597 ;
598 ringbuf->buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
599 if (ringbuf->buffer == NULL) {
600 return NGHTTP2_ERR_NOMEM;
601 }
602 ringbuf->mask = size - 1;
603 ringbuf->first = 0;
604 ringbuf->len = 0;
605 return 0;
606 }
607
hd_ringbuf_get(nghttp2_hd_ringbuf * ringbuf,size_t idx)608 static nghttp2_hd_entry *hd_ringbuf_get(nghttp2_hd_ringbuf *ringbuf,
609 size_t idx) {
610 assert(idx < ringbuf->len);
611 return ringbuf->buffer[(ringbuf->first + idx) & ringbuf->mask];
612 }
613
hd_ringbuf_reserve(nghttp2_hd_ringbuf * ringbuf,size_t bufsize,nghttp2_mem * mem)614 static int hd_ringbuf_reserve(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
615 nghttp2_mem *mem) {
616 size_t i;
617 size_t size;
618 nghttp2_hd_entry **buffer;
619
620 if (ringbuf->mask + 1 >= bufsize) {
621 return 0;
622 }
623 for (size = 1; size < bufsize; size <<= 1)
624 ;
625 buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
626 if (buffer == NULL) {
627 return NGHTTP2_ERR_NOMEM;
628 }
629 for (i = 0; i < ringbuf->len; ++i) {
630 buffer[i] = hd_ringbuf_get(ringbuf, i);
631 }
632 nghttp2_mem_free(mem, ringbuf->buffer);
633 ringbuf->buffer = buffer;
634 ringbuf->mask = size - 1;
635 ringbuf->first = 0;
636 return 0;
637 }
638
hd_ringbuf_free(nghttp2_hd_ringbuf * ringbuf,nghttp2_mem * mem)639 static void hd_ringbuf_free(nghttp2_hd_ringbuf *ringbuf, nghttp2_mem *mem) {
640 size_t i;
641 if (ringbuf == NULL) {
642 return;
643 }
644 for (i = 0; i < ringbuf->len; ++i) {
645 nghttp2_hd_entry *ent = hd_ringbuf_get(ringbuf, i);
646
647 nghttp2_hd_entry_free(ent);
648 nghttp2_mem_free(mem, ent);
649 }
650 nghttp2_mem_free(mem, ringbuf->buffer);
651 }
652
hd_ringbuf_push_front(nghttp2_hd_ringbuf * ringbuf,nghttp2_hd_entry * ent,nghttp2_mem * mem)653 static int hd_ringbuf_push_front(nghttp2_hd_ringbuf *ringbuf,
654 nghttp2_hd_entry *ent, nghttp2_mem *mem) {
655 int rv;
656
657 rv = hd_ringbuf_reserve(ringbuf, ringbuf->len + 1, mem);
658
659 if (rv != 0) {
660 return rv;
661 }
662
663 ringbuf->buffer[--ringbuf->first & ringbuf->mask] = ent;
664 ++ringbuf->len;
665
666 return 0;
667 }
668
hd_ringbuf_pop_back(nghttp2_hd_ringbuf * ringbuf)669 static void hd_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) {
670 assert(ringbuf->len > 0);
671 --ringbuf->len;
672 }
673
hd_context_init(nghttp2_hd_context * context,nghttp2_mem * mem)674 static int hd_context_init(nghttp2_hd_context *context, nghttp2_mem *mem) {
675 int rv;
676 context->mem = mem;
677 context->bad = 0;
678 context->hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
679 rv = hd_ringbuf_init(
680 &context->hd_table,
681 context->hd_table_bufsize_max / NGHTTP2_HD_ENTRY_OVERHEAD, mem);
682 if (rv != 0) {
683 return rv;
684 }
685
686 context->hd_table_bufsize = 0;
687 context->next_seq = 0;
688
689 return 0;
690 }
691
hd_context_free(nghttp2_hd_context * context)692 static void hd_context_free(nghttp2_hd_context *context) {
693 hd_ringbuf_free(&context->hd_table, context->mem);
694 }
695
nghttp2_hd_deflate_init(nghttp2_hd_deflater * deflater,nghttp2_mem * mem)696 int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem) {
697 return nghttp2_hd_deflate_init2(
698 deflater, NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE, mem);
699 }
700
nghttp2_hd_deflate_init2(nghttp2_hd_deflater * deflater,size_t max_deflate_dynamic_table_size,nghttp2_mem * mem)701 int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
702 size_t max_deflate_dynamic_table_size,
703 nghttp2_mem *mem) {
704 int rv;
705 rv = hd_context_init(&deflater->ctx, mem);
706 if (rv != 0) {
707 return rv;
708 }
709
710 hd_map_init(&deflater->map);
711
712 if (max_deflate_dynamic_table_size < NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE) {
713 deflater->notify_table_size_change = 1;
714 deflater->ctx.hd_table_bufsize_max = max_deflate_dynamic_table_size;
715 } else {
716 deflater->notify_table_size_change = 0;
717 }
718
719 deflater->deflate_hd_table_bufsize_max = max_deflate_dynamic_table_size;
720 deflater->min_hd_table_bufsize_max = UINT32_MAX;
721
722 return 0;
723 }
724
nghttp2_hd_inflate_init(nghttp2_hd_inflater * inflater,nghttp2_mem * mem)725 int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem) {
726 int rv;
727
728 rv = hd_context_init(&inflater->ctx, mem);
729 if (rv != 0) {
730 goto fail;
731 }
732
733 inflater->settings_hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
734 inflater->min_hd_table_bufsize_max = UINT32_MAX;
735
736 inflater->nv_name_keep = NULL;
737 inflater->nv_value_keep = NULL;
738
739 inflater->opcode = NGHTTP2_HD_OPCODE_NONE;
740 inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
741
742 nghttp2_buf_init(&inflater->namebuf);
743 nghttp2_buf_init(&inflater->valuebuf);
744
745 inflater->namercbuf = NULL;
746 inflater->valuercbuf = NULL;
747
748 inflater->huffman_encoded = 0;
749 inflater->index = 0;
750 inflater->left = 0;
751 inflater->shift = 0;
752 inflater->index_required = 0;
753 inflater->no_index = 0;
754
755 return 0;
756
757 fail:
758 return rv;
759 }
760
hd_inflate_keep_free(nghttp2_hd_inflater * inflater)761 static void hd_inflate_keep_free(nghttp2_hd_inflater *inflater) {
762 nghttp2_rcbuf_decref(inflater->nv_value_keep);
763 nghttp2_rcbuf_decref(inflater->nv_name_keep);
764
765 inflater->nv_value_keep = NULL;
766 inflater->nv_name_keep = NULL;
767 }
768
nghttp2_hd_deflate_free(nghttp2_hd_deflater * deflater)769 void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater) {
770 hd_context_free(&deflater->ctx);
771 }
772
nghttp2_hd_inflate_free(nghttp2_hd_inflater * inflater)773 void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater) {
774 hd_inflate_keep_free(inflater);
775
776 nghttp2_rcbuf_decref(inflater->valuercbuf);
777 nghttp2_rcbuf_decref(inflater->namercbuf);
778
779 hd_context_free(&inflater->ctx);
780 }
781
entry_room(size_t namelen,size_t valuelen)782 static size_t entry_room(size_t namelen, size_t valuelen) {
783 return NGHTTP2_HD_ENTRY_OVERHEAD + namelen + valuelen;
784 }
785
emit_header(nghttp2_hd_nv * nv_out,nghttp2_hd_nv * nv)786 static void emit_header(nghttp2_hd_nv *nv_out, nghttp2_hd_nv *nv) {
787 DEBUGF("inflatehd: header emission: %s: %s\n", nv->name->base,
788 nv->value->base);
789 /* ent->ref may be 0. This happens if the encoder emits literal
790 block larger than header table capacity with indexing. */
791 *nv_out = *nv;
792 }
793
count_encoded_length(size_t n,size_t prefix)794 static size_t count_encoded_length(size_t n, size_t prefix) {
795 size_t k = (size_t)((1 << prefix) - 1);
796 size_t len = 0;
797
798 if (n < k) {
799 return 1;
800 }
801
802 n -= k;
803 ++len;
804
805 for (; n >= 128; n >>= 7, ++len)
806 ;
807
808 return len + 1;
809 }
810
encode_length(uint8_t * buf,size_t n,size_t prefix)811 static size_t encode_length(uint8_t *buf, size_t n, size_t prefix) {
812 size_t k = (size_t)((1 << prefix) - 1);
813 uint8_t *begin = buf;
814
815 *buf = (uint8_t)(*buf & ~k);
816
817 if (n < k) {
818 *buf = (uint8_t)(*buf | n);
819 return 1;
820 }
821
822 *buf = (uint8_t)(*buf | k);
823 ++buf;
824
825 n -= k;
826
827 for (; n >= 128; n >>= 7) {
828 *buf++ = (uint8_t)((1 << 7) | (n & 0x7f));
829 }
830
831 *buf++ = (uint8_t)n;
832
833 return (size_t)(buf - begin);
834 }
835
836 /*
837 * Decodes |prefix| prefixed integer stored from |in|. The |last|
838 * represents the 1 beyond the last of the valid contiguous memory
839 * region from |in|. The decoded integer must be less than or equal
840 * to UINT32_MAX.
841 *
842 * If the |initial| is nonzero, it is used as a initial value, this
843 * function assumes the |in| starts with intermediate data.
844 *
845 * An entire integer is decoded successfully, decoded, the |*fin| is
846 * set to nonzero.
847 *
848 * This function stores the decoded integer in |*res| if it succeed,
849 * including partial decoding (in this case, number of shift to make
850 * in the next call will be stored in |*shift_ptr|) and returns number
851 * of bytes processed, or returns -1, indicating decoding error.
852 */
decode_length(uint32_t * res,size_t * shift_ptr,int * fin,uint32_t initial,size_t shift,const uint8_t * in,const uint8_t * last,size_t prefix)853 static nghttp2_ssize decode_length(uint32_t *res, size_t *shift_ptr, int *fin,
854 uint32_t initial, size_t shift,
855 const uint8_t *in, const uint8_t *last,
856 size_t prefix) {
857 uint32_t k = (uint8_t)((1 << prefix) - 1);
858 uint32_t n = initial;
859 const uint8_t *start = in;
860
861 *shift_ptr = 0;
862 *fin = 0;
863
864 if (n == 0) {
865 if ((*in & k) != k) {
866 *res = (*in) & k;
867 *fin = 1;
868 return 1;
869 }
870
871 n = k;
872
873 if (++in == last) {
874 *res = n;
875 return (nghttp2_ssize)(in - start);
876 }
877 }
878
879 for (; in != last; ++in, shift += 7) {
880 uint32_t add = *in & 0x7f;
881
882 if (shift >= 32) {
883 DEBUGF("inflate: shift exponent overflow\n");
884 return -1;
885 }
886
887 if ((UINT32_MAX >> shift) < add) {
888 DEBUGF("inflate: integer overflow on shift\n");
889 return -1;
890 }
891
892 add <<= shift;
893
894 if (UINT32_MAX - add < n) {
895 DEBUGF("inflate: integer overflow on addition\n");
896 return -1;
897 }
898
899 n += add;
900
901 if ((*in & (1 << 7)) == 0) {
902 break;
903 }
904 }
905
906 *shift_ptr = shift;
907
908 if (in == last) {
909 *res = n;
910 return (nghttp2_ssize)(in - start);
911 }
912
913 *res = n;
914 *fin = 1;
915 return (nghttp2_ssize)(in + 1 - start);
916 }
917
emit_table_size(nghttp2_bufs * bufs,size_t table_size)918 static int emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
919 int rv;
920 uint8_t *bufp;
921 size_t blocklen;
922 uint8_t sb[16];
923
924 DEBUGF("deflatehd: emit table_size=%zu\n", table_size);
925
926 blocklen = count_encoded_length(table_size, 5);
927
928 if (sizeof(sb) < blocklen) {
929 return NGHTTP2_ERR_HEADER_COMP;
930 }
931
932 bufp = sb;
933
934 *bufp = 0x20u;
935
936 encode_length(bufp, table_size, 5);
937
938 rv = nghttp2_bufs_add(bufs, sb, blocklen);
939 if (rv != 0) {
940 return rv;
941 }
942
943 return 0;
944 }
945
emit_indexed_block(nghttp2_bufs * bufs,size_t idx)946 static int emit_indexed_block(nghttp2_bufs *bufs, size_t idx) {
947 int rv;
948 size_t blocklen;
949 uint8_t sb[16];
950 uint8_t *bufp;
951
952 blocklen = count_encoded_length(idx + 1, 7);
953
954 DEBUGF("deflatehd: emit indexed index=%zu, %zu bytes\n", idx, blocklen);
955
956 if (sizeof(sb) < blocklen) {
957 return NGHTTP2_ERR_HEADER_COMP;
958 }
959
960 bufp = sb;
961 *bufp = 0x80u;
962 encode_length(bufp, idx + 1, 7);
963
964 rv = nghttp2_bufs_add(bufs, sb, blocklen);
965 if (rv != 0) {
966 return rv;
967 }
968
969 return 0;
970 }
971
emit_string(nghttp2_bufs * bufs,const uint8_t * str,size_t len)972 static int emit_string(nghttp2_bufs *bufs, const uint8_t *str, size_t len) {
973 int rv;
974 uint8_t sb[16];
975 uint8_t *bufp;
976 size_t blocklen;
977 size_t enclen;
978 int huffman = 0;
979
980 enclen = nghttp2_hd_huff_encode_count(str, len);
981
982 if (enclen < len) {
983 huffman = 1;
984 } else {
985 enclen = len;
986 }
987
988 blocklen = count_encoded_length(enclen, 7);
989
990 DEBUGF("deflatehd: emit string str=%.*s, length=%zu, huffman=%d, "
991 "encoded_length=%zu\n",
992 (int)len, (const char *)str, len, huffman, enclen);
993
994 if (sizeof(sb) < blocklen) {
995 return NGHTTP2_ERR_HEADER_COMP;
996 }
997
998 bufp = sb;
999 *bufp = huffman ? 1 << 7 : 0;
1000 encode_length(bufp, enclen, 7);
1001
1002 rv = nghttp2_bufs_add(bufs, sb, blocklen);
1003 if (rv != 0) {
1004 return rv;
1005 }
1006
1007 if (huffman) {
1008 rv = nghttp2_hd_huff_encode(bufs, str, len);
1009 } else {
1010 assert(enclen == len);
1011 rv = nghttp2_bufs_add(bufs, str, len);
1012 }
1013
1014 return rv;
1015 }
1016
pack_first_byte(int indexing_mode)1017 static uint8_t pack_first_byte(int indexing_mode) {
1018 switch (indexing_mode) {
1019 case NGHTTP2_HD_WITH_INDEXING:
1020 return 0x40u;
1021 case NGHTTP2_HD_WITHOUT_INDEXING:
1022 return 0;
1023 case NGHTTP2_HD_NEVER_INDEXING:
1024 return 0x10u;
1025 default:
1026 assert(0);
1027 }
1028 /* This is required to compile with android NDK r10d +
1029 --enable-werror */
1030 return 0;
1031 }
1032
emit_indname_block(nghttp2_bufs * bufs,size_t idx,const nghttp2_nv * nv,int indexing_mode)1033 static int emit_indname_block(nghttp2_bufs *bufs, size_t idx,
1034 const nghttp2_nv *nv, int indexing_mode) {
1035 int rv;
1036 uint8_t *bufp;
1037 size_t blocklen;
1038 uint8_t sb[16];
1039 size_t prefixlen;
1040
1041 if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
1042 prefixlen = 6;
1043 } else {
1044 prefixlen = 4;
1045 }
1046
1047 DEBUGF("deflatehd: emit indname index=%zu, valuelen=%zu, indexing_mode=%d\n",
1048 idx, nv->valuelen, indexing_mode);
1049
1050 blocklen = count_encoded_length(idx + 1, prefixlen);
1051
1052 if (sizeof(sb) < blocklen) {
1053 return NGHTTP2_ERR_HEADER_COMP;
1054 }
1055
1056 bufp = sb;
1057
1058 *bufp = pack_first_byte(indexing_mode);
1059
1060 encode_length(bufp, idx + 1, prefixlen);
1061
1062 rv = nghttp2_bufs_add(bufs, sb, blocklen);
1063 if (rv != 0) {
1064 return rv;
1065 }
1066
1067 rv = emit_string(bufs, nv->value, nv->valuelen);
1068 if (rv != 0) {
1069 return rv;
1070 }
1071
1072 return 0;
1073 }
1074
emit_newname_block(nghttp2_bufs * bufs,const nghttp2_nv * nv,int indexing_mode)1075 static int emit_newname_block(nghttp2_bufs *bufs, const nghttp2_nv *nv,
1076 int indexing_mode) {
1077 int rv;
1078
1079 DEBUGF(
1080 "deflatehd: emit newname namelen=%zu, valuelen=%zu, indexing_mode=%d\n",
1081 nv->namelen, nv->valuelen, indexing_mode);
1082
1083 rv = nghttp2_bufs_addb(bufs, pack_first_byte(indexing_mode));
1084 if (rv != 0) {
1085 return rv;
1086 }
1087
1088 rv = emit_string(bufs, nv->name, nv->namelen);
1089 if (rv != 0) {
1090 return rv;
1091 }
1092
1093 rv = emit_string(bufs, nv->value, nv->valuelen);
1094 if (rv != 0) {
1095 return rv;
1096 }
1097
1098 return 0;
1099 }
1100
add_hd_table_incremental(nghttp2_hd_context * context,nghttp2_hd_nv * nv,nghttp2_hd_map * map,uint32_t hash)1101 static int add_hd_table_incremental(nghttp2_hd_context *context,
1102 nghttp2_hd_nv *nv, nghttp2_hd_map *map,
1103 uint32_t hash) {
1104 int rv;
1105 nghttp2_hd_entry *new_ent;
1106 size_t room;
1107 nghttp2_mem *mem;
1108
1109 mem = context->mem;
1110 room = entry_room(nv->name->len, nv->value->len);
1111
1112 while (context->hd_table_bufsize + room > context->hd_table_bufsize_max &&
1113 context->hd_table.len > 0) {
1114
1115 size_t idx = context->hd_table.len - 1;
1116 nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
1117
1118 context->hd_table_bufsize -=
1119 entry_room(ent->nv.name->len, ent->nv.value->len);
1120
1121 DEBUGF("hpack: remove item from header table: %s: %s\n",
1122 (char *)ent->nv.name->base, (char *)ent->nv.value->base);
1123
1124 hd_ringbuf_pop_back(&context->hd_table);
1125 if (map) {
1126 hd_map_remove(map, ent);
1127 }
1128
1129 nghttp2_hd_entry_free(ent);
1130 nghttp2_mem_free(mem, ent);
1131 }
1132
1133 if (room > context->hd_table_bufsize_max) {
1134 /* The entry taking more than NGHTTP2_HD_MAX_BUFFER_SIZE is
1135 immediately evicted. So we don't allocate memory for it. */
1136 return 0;
1137 }
1138
1139 new_ent = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry));
1140 if (new_ent == NULL) {
1141 return NGHTTP2_ERR_NOMEM;
1142 }
1143
1144 nghttp2_hd_entry_init(new_ent, nv);
1145
1146 rv = hd_ringbuf_push_front(&context->hd_table, new_ent, mem);
1147
1148 if (rv != 0) {
1149 nghttp2_hd_entry_free(new_ent);
1150 nghttp2_mem_free(mem, new_ent);
1151
1152 return rv;
1153 }
1154
1155 new_ent->seq = context->next_seq++;
1156 new_ent->hash = hash;
1157
1158 if (map) {
1159 hd_map_insert(map, new_ent);
1160 }
1161
1162 context->hd_table_bufsize += room;
1163
1164 return 0;
1165 }
1166
1167 typedef struct {
1168 nghttp2_ssize index;
1169 /* Nonzero if both name and value are matched. */
1170 int name_value_match;
1171 } search_result;
1172
search_static_table(const nghttp2_nv * nv,int32_t token,int name_only)1173 static search_result search_static_table(const nghttp2_nv *nv, int32_t token,
1174 int name_only) {
1175 search_result res = {token, 0};
1176 int i;
1177 const nghttp2_hd_static_entry *ent;
1178
1179 if (name_only) {
1180 return res;
1181 }
1182
1183 for (i = token;
1184 i <= NGHTTP2_TOKEN_WWW_AUTHENTICATE && static_table[i].token == token;
1185 ++i) {
1186 ent = &static_table[i];
1187 if (ent->value.len == nv->valuelen &&
1188 memcmp(ent->value.base, nv->value, nv->valuelen) == 0) {
1189 res.index = i;
1190 res.name_value_match = 1;
1191 return res;
1192 }
1193 }
1194 return res;
1195 }
1196
search_hd_table(nghttp2_hd_context * context,const nghttp2_nv * nv,int32_t token,int indexing_mode,nghttp2_hd_map * map,uint32_t hash)1197 static search_result search_hd_table(nghttp2_hd_context *context,
1198 const nghttp2_nv *nv, int32_t token,
1199 int indexing_mode, nghttp2_hd_map *map,
1200 uint32_t hash) {
1201 search_result res = {-1, 0};
1202 const nghttp2_hd_entry *ent;
1203 int exact_match;
1204 int name_only = indexing_mode == NGHTTP2_HD_NEVER_INDEXING;
1205
1206 exact_match = 0;
1207 ent = hd_map_find(map, &exact_match, nv, token, hash, name_only);
1208
1209 if (!exact_match && token >= 0 && token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
1210 return search_static_table(nv, token, name_only);
1211 }
1212
1213 if (ent == NULL) {
1214 return res;
1215 }
1216
1217 res.index = (nghttp2_ssize)(context->next_seq - 1 - ent->seq +
1218 NGHTTP2_STATIC_TABLE_LENGTH);
1219 res.name_value_match = exact_match;
1220
1221 return res;
1222 }
1223
hd_context_shrink_table_size(nghttp2_hd_context * context,nghttp2_hd_map * map)1224 static void hd_context_shrink_table_size(nghttp2_hd_context *context,
1225 nghttp2_hd_map *map) {
1226 nghttp2_mem *mem;
1227
1228 mem = context->mem;
1229
1230 while (context->hd_table_bufsize > context->hd_table_bufsize_max &&
1231 context->hd_table.len > 0) {
1232 size_t idx = context->hd_table.len - 1;
1233 nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
1234 context->hd_table_bufsize -=
1235 entry_room(ent->nv.name->len, ent->nv.value->len);
1236 hd_ringbuf_pop_back(&context->hd_table);
1237 if (map) {
1238 hd_map_remove(map, ent);
1239 }
1240
1241 nghttp2_hd_entry_free(ent);
1242 nghttp2_mem_free(mem, ent);
1243 }
1244 }
1245
nghttp2_hd_deflate_change_table_size(nghttp2_hd_deflater * deflater,size_t settings_max_dynamic_table_size)1246 int nghttp2_hd_deflate_change_table_size(
1247 nghttp2_hd_deflater *deflater, size_t settings_max_dynamic_table_size) {
1248 size_t next_bufsize = nghttp2_min_size(
1249 settings_max_dynamic_table_size, deflater->deflate_hd_table_bufsize_max);
1250
1251 deflater->ctx.hd_table_bufsize_max = next_bufsize;
1252
1253 deflater->min_hd_table_bufsize_max =
1254 nghttp2_min_size(deflater->min_hd_table_bufsize_max, next_bufsize);
1255
1256 deflater->notify_table_size_change = 1;
1257
1258 hd_context_shrink_table_size(&deflater->ctx, &deflater->map);
1259 return 0;
1260 }
1261
nghttp2_hd_inflate_change_table_size(nghttp2_hd_inflater * inflater,size_t settings_max_dynamic_table_size)1262 int nghttp2_hd_inflate_change_table_size(
1263 nghttp2_hd_inflater *inflater, size_t settings_max_dynamic_table_size) {
1264 switch (inflater->state) {
1265 case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
1266 case NGHTTP2_HD_STATE_INFLATE_START:
1267 break;
1268 default:
1269 return NGHTTP2_ERR_INVALID_STATE;
1270 }
1271
1272 inflater->settings_hd_table_bufsize_max = settings_max_dynamic_table_size;
1273
1274 /* It seems that encoder is not required to send dynamic table size
1275 update if the table size is not changed after applying
1276 SETTINGS_HEADER_TABLE_SIZE. RFC 7541 is ambiguous here, but this
1277 is the intention of the editor. If new maximum table size is
1278 strictly smaller than the current negotiated maximum size,
1279 encoder must send dynamic table size update. In other cases, we
1280 cannot expect it to do so. */
1281 if (inflater->ctx.hd_table_bufsize_max > settings_max_dynamic_table_size) {
1282 inflater->state = NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE;
1283 /* Remember minimum value, and validate that encoder sends the
1284 value less than or equal to this. */
1285 inflater->min_hd_table_bufsize_max = settings_max_dynamic_table_size;
1286
1287 inflater->ctx.hd_table_bufsize_max = settings_max_dynamic_table_size;
1288
1289 hd_context_shrink_table_size(&inflater->ctx, NULL);
1290 }
1291
1292 return 0;
1293 }
1294
1295 #define INDEX_RANGE_VALID(context, idx) \
1296 ((idx) < (context)->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH)
1297
get_max_index(nghttp2_hd_context * context)1298 static size_t get_max_index(nghttp2_hd_context *context) {
1299 return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH;
1300 }
1301
nghttp2_hd_table_get(nghttp2_hd_context * context,size_t idx)1302 nghttp2_hd_nv nghttp2_hd_table_get(nghttp2_hd_context *context, size_t idx) {
1303 assert(INDEX_RANGE_VALID(context, idx));
1304 if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
1305 return hd_ringbuf_get(&context->hd_table, idx - NGHTTP2_STATIC_TABLE_LENGTH)
1306 ->nv;
1307 } else {
1308 const nghttp2_hd_static_entry *ent = &static_table[idx];
1309 nghttp2_hd_nv nv = {(nghttp2_rcbuf *)&ent->name,
1310 (nghttp2_rcbuf *)&ent->value, ent->token,
1311 NGHTTP2_NV_FLAG_NONE};
1312 return nv;
1313 }
1314 }
1315
nghttp2_hd_table_get2(nghttp2_hd_context * context,size_t idx)1316 static const nghttp2_nv *nghttp2_hd_table_get2(nghttp2_hd_context *context,
1317 size_t idx) {
1318 assert(INDEX_RANGE_VALID(context, idx));
1319 if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
1320 return &hd_ringbuf_get(&context->hd_table,
1321 idx - NGHTTP2_STATIC_TABLE_LENGTH)
1322 ->cnv;
1323 }
1324
1325 return &static_table[idx].cnv;
1326 }
1327
hd_deflate_decide_indexing(nghttp2_hd_deflater * deflater,const nghttp2_nv * nv,int32_t token)1328 static int hd_deflate_decide_indexing(nghttp2_hd_deflater *deflater,
1329 const nghttp2_nv *nv, int32_t token) {
1330 if (token == NGHTTP2_TOKEN__PATH || token == NGHTTP2_TOKEN_AGE ||
1331 token == NGHTTP2_TOKEN_CONTENT_LENGTH || token == NGHTTP2_TOKEN_ETAG ||
1332 token == NGHTTP2_TOKEN_IF_MODIFIED_SINCE ||
1333 token == NGHTTP2_TOKEN_IF_NONE_MATCH || token == NGHTTP2_TOKEN_LOCATION ||
1334 token == NGHTTP2_TOKEN_SET_COOKIE ||
1335 entry_room(nv->namelen, nv->valuelen) >
1336 deflater->ctx.hd_table_bufsize_max * 3 / 4) {
1337 return NGHTTP2_HD_WITHOUT_INDEXING;
1338 }
1339
1340 return NGHTTP2_HD_WITH_INDEXING;
1341 }
1342
deflate_nv(nghttp2_hd_deflater * deflater,nghttp2_bufs * bufs,const nghttp2_nv * nv)1343 static int deflate_nv(nghttp2_hd_deflater *deflater, nghttp2_bufs *bufs,
1344 const nghttp2_nv *nv) {
1345 int rv;
1346 search_result res;
1347 nghttp2_ssize idx;
1348 int indexing_mode;
1349 int32_t token;
1350 nghttp2_mem *mem;
1351 uint32_t hash = 0;
1352
1353 DEBUGF("deflatehd: deflating %.*s: %.*s\n", (int)nv->namelen, nv->name,
1354 (int)nv->valuelen, nv->value);
1355
1356 mem = deflater->ctx.mem;
1357
1358 token = lookup_token(nv->name, nv->namelen);
1359 if (token == -1) {
1360 hash = name_hash(nv);
1361 } else if (token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
1362 hash = static_table[token].hash;
1363 }
1364
1365 /* Don't index authorization header field since it may contain low
1366 entropy secret data (e.g., id/password). Also cookie header
1367 field with less than 20 bytes value is also never indexed. This
1368 is the same criteria used in Firefox codebase. */
1369 indexing_mode =
1370 token == NGHTTP2_TOKEN_AUTHORIZATION ||
1371 (token == NGHTTP2_TOKEN_COOKIE && nv->valuelen < 20) ||
1372 (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX)
1373 ? NGHTTP2_HD_NEVER_INDEXING
1374 : hd_deflate_decide_indexing(deflater, nv, token);
1375
1376 res = search_hd_table(&deflater->ctx, nv, token, indexing_mode,
1377 &deflater->map, hash);
1378
1379 idx = res.index;
1380
1381 if (res.name_value_match) {
1382
1383 DEBUGF("deflatehd: name/value match index=%td\n", idx);
1384
1385 rv = emit_indexed_block(bufs, (size_t)idx);
1386 if (rv != 0) {
1387 return rv;
1388 }
1389
1390 return 0;
1391 }
1392
1393 if (res.index != -1) {
1394 DEBUGF("deflatehd: name match index=%td\n", res.index);
1395 }
1396
1397 if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
1398 nghttp2_hd_nv hd_nv;
1399
1400 if (idx != -1) {
1401 hd_nv.name = nghttp2_hd_table_get(&deflater->ctx, (size_t)idx).name;
1402 nghttp2_rcbuf_incref(hd_nv.name);
1403 } else {
1404 rv = nghttp2_rcbuf_new2(&hd_nv.name, nv->name, nv->namelen, mem);
1405 if (rv != 0) {
1406 return rv;
1407 }
1408 }
1409
1410 rv = nghttp2_rcbuf_new2(&hd_nv.value, nv->value, nv->valuelen, mem);
1411
1412 if (rv != 0) {
1413 nghttp2_rcbuf_decref(hd_nv.name);
1414 return rv;
1415 }
1416
1417 hd_nv.token = token;
1418 hd_nv.flags = NGHTTP2_NV_FLAG_NONE;
1419
1420 rv = add_hd_table_incremental(&deflater->ctx, &hd_nv, &deflater->map, hash);
1421
1422 nghttp2_rcbuf_decref(hd_nv.value);
1423 nghttp2_rcbuf_decref(hd_nv.name);
1424
1425 if (rv != 0) {
1426 return NGHTTP2_ERR_HEADER_COMP;
1427 }
1428 }
1429 if (idx == -1) {
1430 rv = emit_newname_block(bufs, nv, indexing_mode);
1431 } else {
1432 rv = emit_indname_block(bufs, (size_t)idx, nv, indexing_mode);
1433 }
1434 if (rv != 0) {
1435 return rv;
1436 }
1437
1438 return 0;
1439 }
1440
nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater * deflater,nghttp2_bufs * bufs,const nghttp2_nv * nv,size_t nvlen)1441 int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
1442 nghttp2_bufs *bufs, const nghttp2_nv *nv,
1443 size_t nvlen) {
1444 size_t i;
1445 int rv = 0;
1446
1447 if (deflater->ctx.bad) {
1448 return NGHTTP2_ERR_HEADER_COMP;
1449 }
1450
1451 if (deflater->notify_table_size_change) {
1452 size_t min_hd_table_bufsize_max;
1453
1454 min_hd_table_bufsize_max = deflater->min_hd_table_bufsize_max;
1455
1456 deflater->notify_table_size_change = 0;
1457 deflater->min_hd_table_bufsize_max = UINT32_MAX;
1458
1459 if (deflater->ctx.hd_table_bufsize_max > min_hd_table_bufsize_max) {
1460
1461 rv = emit_table_size(bufs, min_hd_table_bufsize_max);
1462
1463 if (rv != 0) {
1464 goto fail;
1465 }
1466 }
1467
1468 rv = emit_table_size(bufs, deflater->ctx.hd_table_bufsize_max);
1469
1470 if (rv != 0) {
1471 goto fail;
1472 }
1473 }
1474
1475 for (i = 0; i < nvlen; ++i) {
1476 rv = deflate_nv(deflater, bufs, &nv[i]);
1477 if (rv != 0) {
1478 goto fail;
1479 }
1480 }
1481
1482 DEBUGF("deflatehd: all input name/value pairs were deflated\n");
1483
1484 return 0;
1485 fail:
1486 DEBUGF("deflatehd: error return %d\n", rv);
1487
1488 deflater->ctx.bad = 1;
1489 return rv;
1490 }
1491
nghttp2_hd_deflate_hd(nghttp2_hd_deflater * deflater,uint8_t * buf,size_t buflen,const nghttp2_nv * nv,size_t nvlen)1492 ssize_t nghttp2_hd_deflate_hd(nghttp2_hd_deflater *deflater, uint8_t *buf,
1493 size_t buflen, const nghttp2_nv *nv,
1494 size_t nvlen) {
1495 return (ssize_t)nghttp2_hd_deflate_hd2(deflater, buf, buflen, nv, nvlen);
1496 }
1497
nghttp2_hd_deflate_hd2(nghttp2_hd_deflater * deflater,uint8_t * buf,size_t buflen,const nghttp2_nv * nv,size_t nvlen)1498 nghttp2_ssize nghttp2_hd_deflate_hd2(nghttp2_hd_deflater *deflater,
1499 uint8_t *buf, size_t buflen,
1500 const nghttp2_nv *nv, size_t nvlen) {
1501 nghttp2_bufs bufs;
1502 int rv;
1503 nghttp2_mem *mem;
1504
1505 mem = deflater->ctx.mem;
1506
1507 rv = nghttp2_bufs_wrap_init(&bufs, buf, buflen, mem);
1508
1509 if (rv != 0) {
1510 return rv;
1511 }
1512
1513 rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);
1514
1515 buflen = nghttp2_bufs_len(&bufs);
1516
1517 nghttp2_bufs_wrap_free(&bufs);
1518
1519 if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
1520 return NGHTTP2_ERR_INSUFF_BUFSIZE;
1521 }
1522
1523 if (rv != 0) {
1524 return rv;
1525 }
1526
1527 return (nghttp2_ssize)buflen;
1528 }
1529
nghttp2_hd_deflate_hd_vec(nghttp2_hd_deflater * deflater,const nghttp2_vec * vec,size_t veclen,const nghttp2_nv * nv,size_t nvlen)1530 ssize_t nghttp2_hd_deflate_hd_vec(nghttp2_hd_deflater *deflater,
1531 const nghttp2_vec *vec, size_t veclen,
1532 const nghttp2_nv *nv, size_t nvlen) {
1533 return (ssize_t)nghttp2_hd_deflate_hd_vec2(deflater, vec, veclen, nv, nvlen);
1534 }
1535
nghttp2_hd_deflate_hd_vec2(nghttp2_hd_deflater * deflater,const nghttp2_vec * vec,size_t veclen,const nghttp2_nv * nv,size_t nvlen)1536 nghttp2_ssize nghttp2_hd_deflate_hd_vec2(nghttp2_hd_deflater *deflater,
1537 const nghttp2_vec *vec, size_t veclen,
1538 const nghttp2_nv *nv, size_t nvlen) {
1539 nghttp2_bufs bufs;
1540 int rv;
1541 nghttp2_mem *mem;
1542 size_t buflen;
1543
1544 mem = deflater->ctx.mem;
1545
1546 rv = nghttp2_bufs_wrap_init2(&bufs, vec, veclen, mem);
1547
1548 if (rv != 0) {
1549 return rv;
1550 }
1551
1552 rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);
1553
1554 buflen = nghttp2_bufs_len(&bufs);
1555
1556 nghttp2_bufs_wrap_free(&bufs);
1557
1558 if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
1559 return NGHTTP2_ERR_INSUFF_BUFSIZE;
1560 }
1561
1562 if (rv != 0) {
1563 return rv;
1564 }
1565
1566 return (nghttp2_ssize)buflen;
1567 }
1568
nghttp2_hd_deflate_bound(nghttp2_hd_deflater * deflater,const nghttp2_nv * nva,size_t nvlen)1569 size_t nghttp2_hd_deflate_bound(nghttp2_hd_deflater *deflater,
1570 const nghttp2_nv *nva, size_t nvlen) {
1571 size_t n = 0;
1572 size_t i;
1573 (void)deflater;
1574
1575 /* Possible Maximum Header Table Size Change. Encoding (1u << 31) -
1576 1 using 4 bit prefix requires 6 bytes. We may emit this at most
1577 twice. */
1578 n += 12;
1579
1580 /* Use Literal Header Field without indexing - New Name, since it is
1581 most space consuming format. Also we choose the less one between
1582 non-huffman and huffman, so using literal byte count is
1583 sufficient for upper bound.
1584
1585 Encoding (1u << 31) - 1 using 7 bit prefix requires 6 bytes. We
1586 need 2 of this for |nvlen| header fields. */
1587 n += 6 * 2 * nvlen;
1588
1589 for (i = 0; i < nvlen; ++i) {
1590 n += nva[i].namelen + nva[i].valuelen;
1591 }
1592
1593 return n;
1594 }
1595
nghttp2_hd_deflate_new(nghttp2_hd_deflater ** deflater_ptr,size_t deflate_hd_table_bufsize_max)1596 int nghttp2_hd_deflate_new(nghttp2_hd_deflater **deflater_ptr,
1597 size_t deflate_hd_table_bufsize_max) {
1598 return nghttp2_hd_deflate_new2(deflater_ptr, deflate_hd_table_bufsize_max,
1599 NULL);
1600 }
1601
nghttp2_hd_deflate_new2(nghttp2_hd_deflater ** deflater_ptr,size_t deflate_hd_table_bufsize_max,nghttp2_mem * mem)1602 int nghttp2_hd_deflate_new2(nghttp2_hd_deflater **deflater_ptr,
1603 size_t deflate_hd_table_bufsize_max,
1604 nghttp2_mem *mem) {
1605 int rv;
1606 nghttp2_hd_deflater *deflater;
1607
1608 if (mem == NULL) {
1609 mem = nghttp2_mem_default();
1610 }
1611
1612 deflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_deflater));
1613
1614 if (deflater == NULL) {
1615 return NGHTTP2_ERR_NOMEM;
1616 }
1617
1618 rv = nghttp2_hd_deflate_init2(deflater, deflate_hd_table_bufsize_max, mem);
1619
1620 if (rv != 0) {
1621 nghttp2_mem_free(mem, deflater);
1622
1623 return rv;
1624 }
1625
1626 *deflater_ptr = deflater;
1627
1628 return 0;
1629 }
1630
nghttp2_hd_deflate_del(nghttp2_hd_deflater * deflater)1631 void nghttp2_hd_deflate_del(nghttp2_hd_deflater *deflater) {
1632 nghttp2_mem *mem;
1633
1634 mem = deflater->ctx.mem;
1635
1636 nghttp2_hd_deflate_free(deflater);
1637
1638 nghttp2_mem_free(mem, deflater);
1639 }
1640
hd_inflate_set_huffman_encoded(nghttp2_hd_inflater * inflater,const uint8_t * in)1641 static void hd_inflate_set_huffman_encoded(nghttp2_hd_inflater *inflater,
1642 const uint8_t *in) {
1643 inflater->huffman_encoded = (*in & (1 << 7)) != 0;
1644 }
1645
1646 /*
1647 * Decodes the integer from the range [in, last). The result is
1648 * assigned to |inflater->left|. If the |inflater->left| is 0, then
1649 * it performs variable integer decoding from scratch. Otherwise, it
1650 * uses the |inflater->left| as the initial value and continues to
1651 * decode assuming that [in, last) begins with intermediary sequence.
1652 *
1653 * This function returns the number of bytes read if it succeeds, or
1654 * one of the following negative error codes:
1655 *
1656 * NGHTTP2_ERR_HEADER_COMP
1657 * Integer decoding failed
1658 */
hd_inflate_read_len(nghttp2_hd_inflater * inflater,int * rfin,const uint8_t * in,const uint8_t * last,size_t prefix,size_t maxlen)1659 static nghttp2_ssize hd_inflate_read_len(nghttp2_hd_inflater *inflater,
1660 int *rfin, const uint8_t *in,
1661 const uint8_t *last, size_t prefix,
1662 size_t maxlen) {
1663 nghttp2_ssize rv;
1664 uint32_t out;
1665
1666 *rfin = 0;
1667
1668 rv = decode_length(&out, &inflater->shift, rfin, (uint32_t)inflater->left,
1669 inflater->shift, in, last, prefix);
1670
1671 if (rv == -1) {
1672 DEBUGF("inflatehd: integer decoding failed\n");
1673 return NGHTTP2_ERR_HEADER_COMP;
1674 }
1675
1676 if (out > maxlen) {
1677 DEBUGF("inflatehd: integer exceeded the maximum value %zu\n", maxlen);
1678 return NGHTTP2_ERR_HEADER_COMP;
1679 }
1680
1681 inflater->left = out;
1682
1683 DEBUGF("inflatehd: decoded integer is %u\n", out);
1684
1685 return rv;
1686 }
1687
1688 /*
1689 * Reads |inflater->left| bytes from the range [in, last) and performs
1690 * huffman decoding against them and pushes the result into the
1691 * |buffer|.
1692 *
1693 * This function returns the number of bytes read if it succeeds, or
1694 * one of the following negative error codes:
1695 *
1696 * NGHTTP2_ERR_NOMEM
1697 * Out of memory
1698 * NGHTTP2_ERR_HEADER_COMP
1699 * Huffman decoding failed
1700 */
hd_inflate_read_huff(nghttp2_hd_inflater * inflater,nghttp2_buf * buf,const uint8_t * in,const uint8_t * last)1701 static nghttp2_ssize hd_inflate_read_huff(nghttp2_hd_inflater *inflater,
1702 nghttp2_buf *buf, const uint8_t *in,
1703 const uint8_t *last) {
1704 nghttp2_ssize readlen;
1705 int fin = 0;
1706 if ((size_t)(last - in) >= inflater->left) {
1707 last = in + inflater->left;
1708 fin = 1;
1709 }
1710 readlen = nghttp2_hd_huff_decode(&inflater->huff_decode_ctx, buf, in,
1711 (size_t)(last - in), fin);
1712
1713 if (readlen < 0) {
1714 DEBUGF("inflatehd: huffman decoding failed\n");
1715 return readlen;
1716 }
1717 if (nghttp2_hd_huff_decode_failure_state(&inflater->huff_decode_ctx)) {
1718 DEBUGF("inflatehd: huffman decoding failed\n");
1719 return NGHTTP2_ERR_HEADER_COMP;
1720 }
1721
1722 inflater->left -= (size_t)readlen;
1723 return readlen;
1724 }
1725
1726 /*
1727 * Reads |inflater->left| bytes from the range [in, last) and copies
1728 * them into the |buffer|.
1729 *
1730 * This function returns the number of bytes read if it succeeds, or
1731 * one of the following negative error codes:
1732 *
1733 * NGHTTP2_ERR_NOMEM
1734 * Out of memory
1735 * NGHTTP2_ERR_HEADER_COMP
1736 * Header decompression failed
1737 */
hd_inflate_read(nghttp2_hd_inflater * inflater,nghttp2_buf * buf,const uint8_t * in,const uint8_t * last)1738 static nghttp2_ssize hd_inflate_read(nghttp2_hd_inflater *inflater,
1739 nghttp2_buf *buf, const uint8_t *in,
1740 const uint8_t *last) {
1741 size_t len = nghttp2_min_size((size_t)(last - in), inflater->left);
1742
1743 buf->last = nghttp2_cpymem(buf->last, in, len);
1744
1745 inflater->left -= len;
1746 return (nghttp2_ssize)len;
1747 }
1748
1749 /*
1750 * Finalize indexed header representation reception. The referenced
1751 * header is always emitted, and |*nv_out| is filled with that value.
1752 */
hd_inflate_commit_indexed(nghttp2_hd_inflater * inflater,nghttp2_hd_nv * nv_out)1753 static void hd_inflate_commit_indexed(nghttp2_hd_inflater *inflater,
1754 nghttp2_hd_nv *nv_out) {
1755 nghttp2_hd_nv nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1756
1757 emit_header(nv_out, &nv);
1758 }
1759
1760 /*
1761 * Finalize literal header representation - new name- reception. If
1762 * header is emitted, |*nv_out| is filled with that value and 0 is
1763 * returned.
1764 *
1765 * This function returns 0 if it succeeds, or one of the following
1766 * negative error codes:
1767 *
1768 * NGHTTP2_ERR_NOMEM
1769 * Out of memory
1770 */
hd_inflate_commit_newname(nghttp2_hd_inflater * inflater,nghttp2_hd_nv * nv_out)1771 static int hd_inflate_commit_newname(nghttp2_hd_inflater *inflater,
1772 nghttp2_hd_nv *nv_out) {
1773 nghttp2_hd_nv nv;
1774 int rv;
1775
1776 if (inflater->no_index) {
1777 nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1778 } else {
1779 nv.flags = NGHTTP2_NV_FLAG_NONE;
1780 }
1781
1782 nv.name = inflater->namercbuf;
1783 nv.value = inflater->valuercbuf;
1784 nv.token = lookup_token(inflater->namercbuf->base, inflater->namercbuf->len);
1785
1786 if (inflater->index_required) {
1787 rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);
1788
1789 if (rv != 0) {
1790 return rv;
1791 }
1792 }
1793
1794 emit_header(nv_out, &nv);
1795
1796 inflater->nv_name_keep = nv.name;
1797 inflater->nv_value_keep = nv.value;
1798
1799 inflater->namercbuf = NULL;
1800 inflater->valuercbuf = NULL;
1801
1802 return 0;
1803 }
1804
1805 /*
1806 * Finalize literal header representation - indexed name-
1807 * reception. If header is emitted, |*nv_out| is filled with that
1808 * value and 0 is returned.
1809 *
1810 * This function returns 0 if it succeeds, or one of the following
1811 * negative error codes:
1812 *
1813 * NGHTTP2_ERR_NOMEM
1814 * Out of memory
1815 */
hd_inflate_commit_indname(nghttp2_hd_inflater * inflater,nghttp2_hd_nv * nv_out)1816 static int hd_inflate_commit_indname(nghttp2_hd_inflater *inflater,
1817 nghttp2_hd_nv *nv_out) {
1818 nghttp2_hd_nv nv;
1819 int rv;
1820
1821 nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);
1822
1823 if (inflater->no_index) {
1824 nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
1825 } else {
1826 nv.flags = NGHTTP2_NV_FLAG_NONE;
1827 }
1828
1829 nghttp2_rcbuf_incref(nv.name);
1830
1831 nv.value = inflater->valuercbuf;
1832
1833 if (inflater->index_required) {
1834 rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);
1835 if (rv != 0) {
1836 nghttp2_rcbuf_decref(nv.name);
1837 return NGHTTP2_ERR_NOMEM;
1838 }
1839 }
1840
1841 emit_header(nv_out, &nv);
1842
1843 inflater->nv_name_keep = nv.name;
1844 inflater->nv_value_keep = nv.value;
1845
1846 inflater->valuercbuf = NULL;
1847
1848 return 0;
1849 }
1850
nghttp2_hd_inflate_hd(nghttp2_hd_inflater * inflater,nghttp2_nv * nv_out,int * inflate_flags,uint8_t * in,size_t inlen,int in_final)1851 ssize_t nghttp2_hd_inflate_hd(nghttp2_hd_inflater *inflater, nghttp2_nv *nv_out,
1852 int *inflate_flags, uint8_t *in, size_t inlen,
1853 int in_final) {
1854 return nghttp2_hd_inflate_hd2(inflater, nv_out, inflate_flags, in, inlen,
1855 in_final);
1856 }
1857
nghttp2_hd_inflate_hd2(nghttp2_hd_inflater * inflater,nghttp2_nv * nv_out,int * inflate_flags,const uint8_t * in,size_t inlen,int in_final)1858 ssize_t nghttp2_hd_inflate_hd2(nghttp2_hd_inflater *inflater,
1859 nghttp2_nv *nv_out, int *inflate_flags,
1860 const uint8_t *in, size_t inlen, int in_final) {
1861 return (nghttp2_ssize)nghttp2_hd_inflate_hd3(inflater, nv_out, inflate_flags,
1862 in, inlen, in_final);
1863 }
1864
nghttp2_hd_inflate_hd3(nghttp2_hd_inflater * inflater,nghttp2_nv * nv_out,int * inflate_flags,const uint8_t * in,size_t inlen,int in_final)1865 nghttp2_ssize nghttp2_hd_inflate_hd3(nghttp2_hd_inflater *inflater,
1866 nghttp2_nv *nv_out, int *inflate_flags,
1867 const uint8_t *in, size_t inlen,
1868 int in_final) {
1869 nghttp2_ssize rv;
1870 nghttp2_hd_nv hd_nv;
1871
1872 rv = nghttp2_hd_inflate_hd_nv(inflater, &hd_nv, inflate_flags, in, inlen,
1873 in_final);
1874
1875 if (rv < 0) {
1876 return rv;
1877 }
1878
1879 if (*inflate_flags & NGHTTP2_HD_INFLATE_EMIT) {
1880 nv_out->name = hd_nv.name->base;
1881 nv_out->namelen = hd_nv.name->len;
1882
1883 nv_out->value = hd_nv.value->base;
1884 nv_out->valuelen = hd_nv.value->len;
1885
1886 nv_out->flags = hd_nv.flags;
1887 }
1888
1889 return rv;
1890 }
1891
nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater * inflater,nghttp2_hd_nv * nv_out,int * inflate_flags,const uint8_t * in,size_t inlen,int in_final)1892 nghttp2_ssize nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater *inflater,
1893 nghttp2_hd_nv *nv_out,
1894 int *inflate_flags, const uint8_t *in,
1895 size_t inlen, int in_final) {
1896 nghttp2_ssize rv = 0;
1897 const uint8_t *first = in;
1898 const uint8_t *last = in + inlen;
1899 int rfin = 0;
1900 int busy = 0;
1901 nghttp2_mem *mem;
1902
1903 mem = inflater->ctx.mem;
1904
1905 if (inflater->ctx.bad) {
1906 return NGHTTP2_ERR_HEADER_COMP;
1907 }
1908
1909 DEBUGF("inflatehd: start state=%d\n", inflater->state);
1910 hd_inflate_keep_free(inflater);
1911 *inflate_flags = NGHTTP2_HD_INFLATE_NONE;
1912 for (; in != last || busy;) {
1913 busy = 0;
1914 switch (inflater->state) {
1915 case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
1916 if ((*in & 0xe0u) != 0x20u) {
1917 DEBUGF("inflatehd: header table size change was expected, but saw "
1918 "0x%02x as first byte",
1919 *in);
1920 rv = NGHTTP2_ERR_HEADER_COMP;
1921 goto fail;
1922 }
1923 /* fall through */
1924 case NGHTTP2_HD_STATE_INFLATE_START:
1925 case NGHTTP2_HD_STATE_OPCODE:
1926 if ((*in & 0xe0u) == 0x20u) {
1927 DEBUGF("inflatehd: header table size change\n");
1928 if (inflater->state == NGHTTP2_HD_STATE_OPCODE) {
1929 DEBUGF("inflatehd: header table size change must appear at the head "
1930 "of header block\n");
1931 rv = NGHTTP2_ERR_HEADER_COMP;
1932 goto fail;
1933 }
1934 inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1935 inflater->state = NGHTTP2_HD_STATE_READ_TABLE_SIZE;
1936 } else if (*in & 0x80u) {
1937 DEBUGF("inflatehd: indexed repr\n");
1938 inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
1939 inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1940 } else {
1941 if (*in == 0x40u || *in == 0 || *in == 0x10u) {
1942 DEBUGF("inflatehd: literal header repr - new name\n");
1943 inflater->opcode = NGHTTP2_HD_OPCODE_NEWNAME;
1944 inflater->state = NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN;
1945 } else {
1946 DEBUGF("inflatehd: literal header repr - indexed name\n");
1947 inflater->opcode = NGHTTP2_HD_OPCODE_INDNAME;
1948 inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
1949 }
1950 inflater->index_required = (*in & 0x40) != 0;
1951 inflater->no_index = (*in & 0xf0u) == 0x10u;
1952 DEBUGF("inflatehd: indexing required=%d, no_index=%d\n",
1953 inflater->index_required, inflater->no_index);
1954 if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
1955 ++in;
1956 }
1957 }
1958 inflater->left = 0;
1959 inflater->shift = 0;
1960 break;
1961 case NGHTTP2_HD_STATE_READ_TABLE_SIZE:
1962 rfin = 0;
1963 rv = hd_inflate_read_len(
1964 inflater, &rfin, in, last, 5,
1965 nghttp2_min_size(inflater->min_hd_table_bufsize_max,
1966 inflater->settings_hd_table_bufsize_max));
1967 if (rv < 0) {
1968 goto fail;
1969 }
1970 in += rv;
1971 if (!rfin) {
1972 goto almost_ok;
1973 }
1974 DEBUGF("inflatehd: table_size=%zu\n", inflater->left);
1975 inflater->min_hd_table_bufsize_max = UINT32_MAX;
1976 inflater->ctx.hd_table_bufsize_max = inflater->left;
1977 hd_context_shrink_table_size(&inflater->ctx, NULL);
1978 inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
1979 break;
1980 case NGHTTP2_HD_STATE_READ_INDEX: {
1981 size_t prefixlen;
1982
1983 if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
1984 prefixlen = 7;
1985 } else if (inflater->index_required) {
1986 prefixlen = 6;
1987 } else {
1988 prefixlen = 4;
1989 }
1990
1991 rfin = 0;
1992 rv = hd_inflate_read_len(inflater, &rfin, in, last, prefixlen,
1993 get_max_index(&inflater->ctx));
1994 if (rv < 0) {
1995 goto fail;
1996 }
1997
1998 in += rv;
1999
2000 if (!rfin) {
2001 goto almost_ok;
2002 }
2003
2004 if (inflater->left == 0) {
2005 rv = NGHTTP2_ERR_HEADER_COMP;
2006 goto fail;
2007 }
2008
2009 DEBUGF("inflatehd: index=%zu\n", inflater->left);
2010 if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
2011 inflater->index = inflater->left;
2012 --inflater->index;
2013
2014 hd_inflate_commit_indexed(inflater, nv_out);
2015
2016 inflater->state = NGHTTP2_HD_STATE_OPCODE;
2017 *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
2018 return (nghttp2_ssize)(in - first);
2019 } else {
2020 inflater->index = inflater->left;
2021 --inflater->index;
2022
2023 inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
2024 }
2025 break;
2026 }
2027 case NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN:
2028 hd_inflate_set_huffman_encoded(inflater, in);
2029 inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN;
2030 inflater->left = 0;
2031 inflater->shift = 0;
2032 DEBUGF("inflatehd: huffman encoded=%d\n", inflater->huffman_encoded != 0);
2033 /* Fall through */
2034 case NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN:
2035 rfin = 0;
2036 rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
2037 if (rv < 0) {
2038 goto fail;
2039 }
2040 in += rv;
2041 if (!rfin) {
2042 DEBUGF("inflatehd: integer not fully decoded. current=%zu\n",
2043 inflater->left);
2044
2045 goto almost_ok;
2046 }
2047
2048 if (inflater->huffman_encoded) {
2049 nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
2050
2051 inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF;
2052
2053 rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left * 2 + 1,
2054 mem);
2055 } else {
2056 inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAME;
2057 rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left + 1, mem);
2058 }
2059
2060 if (rv != 0) {
2061 goto fail;
2062 }
2063
2064 nghttp2_buf_wrap_init(&inflater->namebuf, inflater->namercbuf->base,
2065 inflater->namercbuf->len);
2066
2067 break;
2068 case NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF:
2069 rv = hd_inflate_read_huff(inflater, &inflater->namebuf, in, last);
2070 if (rv < 0) {
2071 goto fail;
2072 }
2073
2074 in += rv;
2075
2076 DEBUGF("inflatehd: %td bytes read\n", rv);
2077
2078 if (inflater->left) {
2079 DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);
2080
2081 goto almost_ok;
2082 }
2083
2084 *inflater->namebuf.last = '\0';
2085 inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);
2086
2087 inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
2088
2089 break;
2090 case NGHTTP2_HD_STATE_NEWNAME_READ_NAME:
2091 rv = hd_inflate_read(inflater, &inflater->namebuf, in, last);
2092 if (rv < 0) {
2093 goto fail;
2094 }
2095
2096 in += rv;
2097
2098 DEBUGF("inflatehd: %td bytes read\n", rv);
2099 if (inflater->left) {
2100 DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);
2101
2102 goto almost_ok;
2103 }
2104
2105 *inflater->namebuf.last = '\0';
2106 inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);
2107
2108 inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
2109
2110 break;
2111 case NGHTTP2_HD_STATE_CHECK_VALUELEN:
2112 hd_inflate_set_huffman_encoded(inflater, in);
2113 inflater->state = NGHTTP2_HD_STATE_READ_VALUELEN;
2114 inflater->left = 0;
2115 inflater->shift = 0;
2116 DEBUGF("inflatehd: huffman encoded=%d\n", inflater->huffman_encoded != 0);
2117 /* Fall through */
2118 case NGHTTP2_HD_STATE_READ_VALUELEN:
2119 rfin = 0;
2120 rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
2121 if (rv < 0) {
2122 goto fail;
2123 }
2124
2125 in += rv;
2126
2127 if (!rfin) {
2128 goto almost_ok;
2129 }
2130
2131 DEBUGF("inflatehd: valuelen=%zu\n", inflater->left);
2132
2133 if (inflater->huffman_encoded) {
2134 nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);
2135
2136 inflater->state = NGHTTP2_HD_STATE_READ_VALUEHUFF;
2137
2138 rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left * 2 + 1,
2139 mem);
2140 } else {
2141 inflater->state = NGHTTP2_HD_STATE_READ_VALUE;
2142
2143 rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left + 1, mem);
2144 }
2145
2146 if (rv != 0) {
2147 goto fail;
2148 }
2149
2150 nghttp2_buf_wrap_init(&inflater->valuebuf, inflater->valuercbuf->base,
2151 inflater->valuercbuf->len);
2152
2153 busy = 1;
2154
2155 break;
2156 case NGHTTP2_HD_STATE_READ_VALUEHUFF:
2157 rv = hd_inflate_read_huff(inflater, &inflater->valuebuf, in, last);
2158 if (rv < 0) {
2159 goto fail;
2160 }
2161
2162 in += rv;
2163
2164 DEBUGF("inflatehd: %td bytes read\n", rv);
2165
2166 if (inflater->left) {
2167 DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);
2168
2169 goto almost_ok;
2170 }
2171
2172 *inflater->valuebuf.last = '\0';
2173 inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);
2174
2175 if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
2176 rv = hd_inflate_commit_newname(inflater, nv_out);
2177 } else {
2178 rv = hd_inflate_commit_indname(inflater, nv_out);
2179 }
2180
2181 if (rv != 0) {
2182 goto fail;
2183 }
2184
2185 inflater->state = NGHTTP2_HD_STATE_OPCODE;
2186 *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
2187
2188 return (nghttp2_ssize)(in - first);
2189 case NGHTTP2_HD_STATE_READ_VALUE:
2190 rv = hd_inflate_read(inflater, &inflater->valuebuf, in, last);
2191 if (rv < 0) {
2192 DEBUGF("inflatehd: value read failure %td: %s\n", rv,
2193 nghttp2_strerror((int)rv));
2194 goto fail;
2195 }
2196
2197 in += rv;
2198
2199 DEBUGF("inflatehd: %td bytes read\n", rv);
2200
2201 if (inflater->left) {
2202 DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);
2203 goto almost_ok;
2204 }
2205
2206 *inflater->valuebuf.last = '\0';
2207 inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);
2208
2209 if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
2210 rv = hd_inflate_commit_newname(inflater, nv_out);
2211 } else {
2212 rv = hd_inflate_commit_indname(inflater, nv_out);
2213 }
2214
2215 if (rv != 0) {
2216 goto fail;
2217 }
2218
2219 inflater->state = NGHTTP2_HD_STATE_OPCODE;
2220 *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
2221
2222 return (nghttp2_ssize)(in - first);
2223 }
2224 }
2225
2226 assert(in == last);
2227
2228 DEBUGF("inflatehd: all input bytes were processed\n");
2229
2230 if (in_final) {
2231 DEBUGF("inflatehd: in_final set\n");
2232
2233 if (inflater->state != NGHTTP2_HD_STATE_OPCODE &&
2234 inflater->state != NGHTTP2_HD_STATE_INFLATE_START) {
2235 DEBUGF("inflatehd: unacceptable state=%d\n", inflater->state);
2236 rv = NGHTTP2_ERR_HEADER_COMP;
2237
2238 goto fail;
2239 }
2240 *inflate_flags |= NGHTTP2_HD_INFLATE_FINAL;
2241 }
2242 return (nghttp2_ssize)(in - first);
2243
2244 almost_ok:
2245 if (in_final) {
2246 DEBUGF("inflatehd: input ended prematurely\n");
2247
2248 rv = NGHTTP2_ERR_HEADER_COMP;
2249
2250 goto fail;
2251 }
2252 return (nghttp2_ssize)(in - first);
2253
2254 fail:
2255 DEBUGF("inflatehd: error return %td\n", rv);
2256
2257 inflater->ctx.bad = 1;
2258 return rv;
2259 }
2260
nghttp2_hd_inflate_end_headers(nghttp2_hd_inflater * inflater)2261 int nghttp2_hd_inflate_end_headers(nghttp2_hd_inflater *inflater) {
2262 hd_inflate_keep_free(inflater);
2263 inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
2264 return 0;
2265 }
2266
nghttp2_hd_inflate_new(nghttp2_hd_inflater ** inflater_ptr)2267 int nghttp2_hd_inflate_new(nghttp2_hd_inflater **inflater_ptr) {
2268 return nghttp2_hd_inflate_new2(inflater_ptr, NULL);
2269 }
2270
nghttp2_hd_inflate_new2(nghttp2_hd_inflater ** inflater_ptr,nghttp2_mem * mem)2271 int nghttp2_hd_inflate_new2(nghttp2_hd_inflater **inflater_ptr,
2272 nghttp2_mem *mem) {
2273 int rv;
2274 nghttp2_hd_inflater *inflater;
2275
2276 if (mem == NULL) {
2277 mem = nghttp2_mem_default();
2278 }
2279
2280 inflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_inflater));
2281
2282 if (inflater == NULL) {
2283 return NGHTTP2_ERR_NOMEM;
2284 }
2285
2286 rv = nghttp2_hd_inflate_init(inflater, mem);
2287
2288 if (rv != 0) {
2289 nghttp2_mem_free(mem, inflater);
2290
2291 return rv;
2292 }
2293
2294 *inflater_ptr = inflater;
2295
2296 return 0;
2297 }
2298
nghttp2_hd_inflate_del(nghttp2_hd_inflater * inflater)2299 void nghttp2_hd_inflate_del(nghttp2_hd_inflater *inflater) {
2300 nghttp2_mem *mem;
2301
2302 mem = inflater->ctx.mem;
2303 nghttp2_hd_inflate_free(inflater);
2304
2305 nghttp2_mem_free(mem, inflater);
2306 }
2307
nghttp2_hd_emit_indname_block(nghttp2_bufs * bufs,size_t idx,nghttp2_nv * nv,int indexing_mode)2308 int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t idx,
2309 nghttp2_nv *nv, int indexing_mode) {
2310
2311 return emit_indname_block(bufs, idx, nv, indexing_mode);
2312 }
2313
nghttp2_hd_emit_newname_block(nghttp2_bufs * bufs,nghttp2_nv * nv,int indexing_mode)2314 int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
2315 int indexing_mode) {
2316 return emit_newname_block(bufs, nv, indexing_mode);
2317 }
2318
nghttp2_hd_emit_table_size(nghttp2_bufs * bufs,size_t table_size)2319 int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
2320 return emit_table_size(bufs, table_size);
2321 }
2322
nghttp2_hd_decode_length(uint32_t * res,size_t * shift_ptr,int * fin,uint32_t initial,size_t shift,uint8_t * in,uint8_t * last,size_t prefix)2323 nghttp2_ssize nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr,
2324 int *fin, uint32_t initial, size_t shift,
2325 uint8_t *in, uint8_t *last,
2326 size_t prefix) {
2327 return decode_length(res, shift_ptr, fin, initial, shift, in, last, prefix);
2328 }
2329
hd_get_table_entry(nghttp2_hd_context * context,size_t idx)2330 static const nghttp2_nv *hd_get_table_entry(nghttp2_hd_context *context,
2331 size_t idx) {
2332 if (idx == 0) {
2333 return NULL;
2334 }
2335
2336 --idx;
2337
2338 if (!INDEX_RANGE_VALID(context, idx)) {
2339 return NULL;
2340 }
2341
2342 return nghttp2_hd_table_get2(context, idx);
2343 }
2344
nghttp2_hd_deflate_get_num_table_entries(nghttp2_hd_deflater * deflater)2345 size_t nghttp2_hd_deflate_get_num_table_entries(nghttp2_hd_deflater *deflater) {
2346 return get_max_index(&deflater->ctx);
2347 }
2348
2349 const nghttp2_nv *
nghttp2_hd_deflate_get_table_entry(nghttp2_hd_deflater * deflater,size_t idx)2350 nghttp2_hd_deflate_get_table_entry(nghttp2_hd_deflater *deflater, size_t idx) {
2351 return hd_get_table_entry(&deflater->ctx, idx);
2352 }
2353
2354 size_t
nghttp2_hd_deflate_get_dynamic_table_size(nghttp2_hd_deflater * deflater)2355 nghttp2_hd_deflate_get_dynamic_table_size(nghttp2_hd_deflater *deflater) {
2356 return deflater->ctx.hd_table_bufsize;
2357 }
2358
2359 size_t
nghttp2_hd_deflate_get_max_dynamic_table_size(nghttp2_hd_deflater * deflater)2360 nghttp2_hd_deflate_get_max_dynamic_table_size(nghttp2_hd_deflater *deflater) {
2361 return deflater->ctx.hd_table_bufsize_max;
2362 }
2363
nghttp2_hd_inflate_get_num_table_entries(nghttp2_hd_inflater * inflater)2364 size_t nghttp2_hd_inflate_get_num_table_entries(nghttp2_hd_inflater *inflater) {
2365 return get_max_index(&inflater->ctx);
2366 }
2367
2368 const nghttp2_nv *
nghttp2_hd_inflate_get_table_entry(nghttp2_hd_inflater * inflater,size_t idx)2369 nghttp2_hd_inflate_get_table_entry(nghttp2_hd_inflater *inflater, size_t idx) {
2370 return hd_get_table_entry(&inflater->ctx, idx);
2371 }
2372
2373 size_t
nghttp2_hd_inflate_get_dynamic_table_size(nghttp2_hd_inflater * inflater)2374 nghttp2_hd_inflate_get_dynamic_table_size(nghttp2_hd_inflater *inflater) {
2375 return inflater->ctx.hd_table_bufsize;
2376 }
2377
2378 size_t
nghttp2_hd_inflate_get_max_dynamic_table_size(nghttp2_hd_inflater * inflater)2379 nghttp2_hd_inflate_get_max_dynamic_table_size(nghttp2_hd_inflater *inflater) {
2380 return inflater->ctx.hd_table_bufsize_max;
2381 }
2382