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