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). */ 48static 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 112static 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 */ 120static 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 487void 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 501void nghttp2_hd_entry_free(nghttp2_hd_entry *ent) { 502 nghttp2_rcbuf_decref(ent->nv.value); 503 nghttp2_rcbuf_decref(ent->nv.name); 504} 505 506static 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 511static 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 516static 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 529static void hd_map_init(nghttp2_hd_map *map) { 530 memset(map, 0, sizeof(nghttp2_hd_map)); 531} 532 533static 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 548static 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 577static 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 593static 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 608static 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 614static 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 639static 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 653static 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 669static void hd_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) { 670 assert(ringbuf->len > 0); 671 --ringbuf->len; 672} 673 674static 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 692static void hd_context_free(nghttp2_hd_context *context) { 693 hd_ringbuf_free(&context->hd_table, context->mem); 694} 695 696int 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 701int 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 725int 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 757fail: 758 return rv; 759} 760 761static 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 769void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater) { 770 hd_context_free(&deflater->ctx); 771} 772 773void 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 782static size_t entry_room(size_t namelen, size_t valuelen) { 783 return NGHTTP2_HD_ENTRY_OVERHEAD + namelen + valuelen; 784} 785 786static 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 794static 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 811static 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 */ 853static 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 917static 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 945static 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 971static 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 1016static 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 1032static 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 1074static 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 1100static 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 1166typedef struct { 1167 ssize_t index; 1168 /* Nonzero if both name and value are matched. */ 1169 int name_value_match; 1170} search_result; 1171 1172static 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 1196static 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 1223static 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 1245int 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 1261int 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 1297static size_t get_max_index(nghttp2_hd_context *context) { 1298 return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH; 1299} 1300 1301nghttp2_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 1315static 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 1327static 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 1342static 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 1440int 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; 1484fail: 1485 DEBUGF("deflatehd: error return %d\n", rv); 1486 1487 deflater->ctx.bad = 1; 1488 return rv; 1489} 1490 1491ssize_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 1523ssize_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 1556size_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 1583int 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 1589int 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 1618void 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 1628static 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 */ 1646static 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 */ 1687static 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 */ 1724static 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 */ 1738static 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 */ 1756static 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 */ 1801static 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 1836ssize_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 1843ssize_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 1869ssize_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 2221almost_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 2231fail: 2232 DEBUGF("inflatehd: error return %zd\n", rv); 2233 2234 inflater->ctx.bad = 1; 2235 return rv; 2236} 2237 2238int 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 2244int nghttp2_hd_inflate_new(nghttp2_hd_inflater **inflater_ptr) { 2245 return nghttp2_hd_inflate_new2(inflater_ptr, NULL); 2246} 2247 2248int 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 2276void 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 2285int 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 2291int 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 2296int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size) { 2297 return emit_table_size(bufs, table_size); 2298} 2299 2300ssize_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 2306static 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 2321size_t nghttp2_hd_deflate_get_num_table_entries(nghttp2_hd_deflater *deflater) { 2322 return get_max_index(&deflater->ctx); 2323} 2324 2325const nghttp2_nv * 2326nghttp2_hd_deflate_get_table_entry(nghttp2_hd_deflater *deflater, size_t idx) { 2327 return hd_get_table_entry(&deflater->ctx, idx); 2328} 2329 2330size_t 2331nghttp2_hd_deflate_get_dynamic_table_size(nghttp2_hd_deflater *deflater) { 2332 return deflater->ctx.hd_table_bufsize; 2333} 2334 2335size_t 2336nghttp2_hd_deflate_get_max_dynamic_table_size(nghttp2_hd_deflater *deflater) { 2337 return deflater->ctx.hd_table_bufsize_max; 2338} 2339 2340size_t nghttp2_hd_inflate_get_num_table_entries(nghttp2_hd_inflater *inflater) { 2341 return get_max_index(&inflater->ctx); 2342} 2343 2344const nghttp2_nv * 2345nghttp2_hd_inflate_get_table_entry(nghttp2_hd_inflater *inflater, size_t idx) { 2346 return hd_get_table_entry(&inflater->ctx, idx); 2347} 2348 2349size_t 2350nghttp2_hd_inflate_get_dynamic_table_size(nghttp2_hd_inflater *inflater) { 2351 return inflater->ctx.hd_table_bufsize; 2352} 2353 2354size_t 2355nghttp2_hd_inflate_get_max_dynamic_table_size(nghttp2_hd_inflater *inflater) { 2356 return inflater->ctx.hd_table_bufsize_max; 2357} 2358