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