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