1 2 /* 3 * Copyright (C) NGINX, Inc. 4 * Copyright (C) Valentin V. Bartenev 5 */ 6 7 #include <nxt_main.h> 8 9 10 static nxt_int_t nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, 11 u_char **pos, u_char *end); 12 static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp, 13 u_char **pos, u_char *end); 14 static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp, 15 u_char **pos, u_char *end); 16 static nxt_int_t nxt_http_parse_field_value(nxt_http_request_parse_t *rp, 17 u_char **pos, u_char *end); 18 static u_char *nxt_http_lookup_field_end(u_char *p, u_char *end); 19 static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp, 20 u_char **pos, u_char *end); 21 22 static nxt_int_t nxt_http_parse_complex_target(nxt_http_request_parse_t *rp); 23 24 static nxt_int_t nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data); 25 static void *nxt_http_field_hash_alloc(void *pool, size_t size); 26 static void nxt_http_field_hash_free(void *pool, void *p); 27 28 static nxt_int_t nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, 29 void *data); 30 31 32 #define NXT_HTTP_MAX_FIELD_NAME 0xFF 33 #define NXT_HTTP_MAX_FIELD_VALUE NXT_INT32_T_MAX 34 35 #define NXT_HTTP_FIELD_LVLHSH_SHIFT 5 36 37 38 typedef enum { 39 NXT_HTTP_TARGET_SPACE = 1, /* \s */ 40 NXT_HTTP_TARGET_HASH, /* # */ 41 NXT_HTTP_TARGET_AGAIN, 42 NXT_HTTP_TARGET_BAD, /* \0\r\n */ 43 44 /* traps below are used for extended check only */ 45 46 NXT_HTTP_TARGET_SLASH = 5, /* / */ 47 NXT_HTTP_TARGET_DOT, /* . */ 48 NXT_HTTP_TARGET_ARGS_MARK, /* ? */ 49 NXT_HTTP_TARGET_QUOTE_MARK, /* % */ 50 NXT_HTTP_TARGET_PLUS, /* + */ 51 } nxt_http_target_traps_e; 52 53 54 static const uint8_t nxt_http_target_chars[256] nxt_aligned(64) = { 55 /* \0 \n \r */ 56 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 4, 0, 0, 57 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 58 59 /* \s ! " # $ % & ' ( ) * + , - . / */ 60 1, 0, 0, 2, 0, 8, 0, 0, 0, 0, 0, 9, 0, 0, 6, 5, 61 62 /* 0 1 2 3 4 5 6 7 8 9 : ; < = > ? */ 63 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 64 }; 65 66 67 nxt_inline nxt_http_target_traps_e 68 nxt_http_parse_target(u_char **pos, u_char *end) 69 { 70 u_char *p; 71 nxt_uint_t trap; 72 73 p = *pos; 74 75 while (nxt_fast_path(end - p >= 10)) { 76 77 #define nxt_target_test_char(ch) \ 78 \ 79 trap = nxt_http_target_chars[ch]; \ 80 \ 81 if (nxt_slow_path(trap != 0)) { \ 82 *pos = &(ch); \ 83 return trap; \ 84 } 85 86 /* enddef */ 87 88 nxt_target_test_char(p[0]); 89 nxt_target_test_char(p[1]); 90 nxt_target_test_char(p[2]); 91 nxt_target_test_char(p[3]); 92 93 nxt_target_test_char(p[4]); 94 nxt_target_test_char(p[5]); 95 nxt_target_test_char(p[6]); 96 nxt_target_test_char(p[7]); 97 98 nxt_target_test_char(p[8]); 99 nxt_target_test_char(p[9]); 100 101 p += 10; 102 } 103 104 while (p != end) { 105 nxt_target_test_char(*p); p++; 106 } 107 108 return NXT_HTTP_TARGET_AGAIN; 109 } 110 111 112 nxt_int_t 113 nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp) 114 { 115 rp->mem_pool = mp; 116 117 rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t)); 118 if (nxt_slow_path(rp->fields == NULL)) { 119 return NXT_ERROR; 120 } 121 122 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; 123 124 return NXT_OK; 125 } 126 127 128 nxt_int_t 129 nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b) 130 { 131 nxt_int_t rc; 132 133 if (rp->handler == NULL) { 134 rp->handler = &nxt_http_parse_request_line; 135 } 136 137 do { 138 rc = rp->handler(rp, &b->pos, b->free); 139 } while (rc == NXT_OK); 140 141 return rc; 142 } 143 144 145 nxt_int_t 146 nxt_http_parse_fields(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b) 147 { 148 nxt_int_t rc; 149 150 if (rp->handler == NULL) { 151 rp->handler = &nxt_http_parse_field_name; 152 } 153 154 do { 155 rc = rp->handler(rp, &b->pos, b->free); 156 } while (rc == NXT_OK); 157 158 return rc; 159 } 160 161 162 static nxt_int_t 163 nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos, 164 u_char *end) 165 { 166 u_char *p, ch, *after_slash, *exten, *args; 167 nxt_int_t rc; 168 nxt_http_ver_t ver; 169 nxt_http_target_traps_e trap; 170 171 static const nxt_http_ver_t http11 = { "HTTP/1.1" }; 172 static const nxt_http_ver_t http10 = { "HTTP/1.0" }; 173 174 p = *pos; 175 176 rp->method.start = p; 177 178 for ( ;; ) { 179 180 while (nxt_fast_path(end - p >= 8)) { 181 182 #define nxt_method_test_char(ch) \ 183 \ 184 if (nxt_slow_path((ch) < 'A' || (ch) > 'Z')) { \ 185 p = &(ch); \ 186 goto method_unusual_char; \ 187 } 188 189 /* enddef */ 190 191 nxt_method_test_char(p[0]); 192 nxt_method_test_char(p[1]); 193 nxt_method_test_char(p[2]); 194 nxt_method_test_char(p[3]); 195 196 nxt_method_test_char(p[4]); 197 nxt_method_test_char(p[5]); 198 nxt_method_test_char(p[6]); 199 nxt_method_test_char(p[7]); 200 201 p += 8; 202 } 203 204 while (p != end) { 205 nxt_method_test_char(*p); p++; 206 } 207 208 rp->method.length = p - rp->method.start; 209 210 return NXT_AGAIN; 211 212 method_unusual_char: 213 214 ch = *p; 215 216 if (nxt_fast_path(ch == ' ')) { 217 rp->method.length = p - rp->method.start; 218 break; 219 } 220 221 if (ch == '_' || ch == '-') { 222 p++; 223 continue; 224 } 225 226 if (rp->method.start == p && (ch == '\r' || ch == '\n')) { 227 rp->method.start++; 228 p++; 229 continue; 230 } 231 232 rp->method.length = p - rp->method.start; 233 234 return NXT_HTTP_PARSE_INVALID; 235 } 236 237 p++; 238 239 if (nxt_slow_path(p == end)) { 240 return NXT_AGAIN; 241 } 242 243 /* target */ 244 245 ch = *p; 246 247 if (nxt_slow_path(ch != '/')) { 248 rc = nxt_http_parse_unusual_target(rp, &p, end); 249 250 if (nxt_slow_path(rc != NXT_OK)) { 251 return rc; 252 } 253 } 254 255 rp->target_start = p; 256 257 after_slash = p + 1; 258 exten = NULL; 259 args = NULL; 260 261 for ( ;; ) { 262 p++; 263 264 trap = nxt_http_parse_target(&p, end); 265 266 switch (trap) { 267 case NXT_HTTP_TARGET_SLASH: 268 if (nxt_slow_path(after_slash == p)) { 269 rp->complex_target = 1; 270 goto rest_of_target; 271 } 272 273 after_slash = p + 1; 274 exten = NULL; 275 continue; 276 277 case NXT_HTTP_TARGET_DOT: 278 if (nxt_slow_path(after_slash == p)) { 279 rp->complex_target = 1; 280 goto rest_of_target; 281 } 282 283 exten = p + 1; 284 continue; 285 286 case NXT_HTTP_TARGET_ARGS_MARK: 287 args = p + 1; 288 goto rest_of_target; 289 290 case NXT_HTTP_TARGET_SPACE: 291 rp->target_end = p; 292 goto space_after_target; 293 294 case NXT_HTTP_TARGET_QUOTE_MARK: 295 rp->quoted_target = 1; 296 goto rest_of_target; 297 298 case NXT_HTTP_TARGET_PLUS: 299 rp->plus_in_target = 1; 300 continue; 301 302 case NXT_HTTP_TARGET_HASH: 303 rp->complex_target = 1; 304 goto rest_of_target; 305 306 case NXT_HTTP_TARGET_AGAIN: 307 rp->target_end = p; 308 return NXT_AGAIN; 309 310 case NXT_HTTP_TARGET_BAD: 311 rp->target_end = p; 312 return NXT_HTTP_PARSE_INVALID; 313 } 314 315 nxt_unreachable(); 316 } 317 318 rest_of_target: 319 320 for ( ;; ) { 321 p++; 322 323 trap = nxt_http_parse_target(&p, end); 324 325 switch (trap) { 326 case NXT_HTTP_TARGET_SPACE: 327 rp->target_end = p; 328 goto space_after_target; 329 330 case NXT_HTTP_TARGET_HASH: 331 rp->complex_target = 1; 332 continue; 333 334 case NXT_HTTP_TARGET_AGAIN: 335 rp->target_end = p; 336 return NXT_AGAIN; 337 338 case NXT_HTTP_TARGET_BAD: 339 rp->target_end = p; 340 return NXT_HTTP_PARSE_INVALID; 341 342 default: 343 continue; 344 } 345 346 nxt_unreachable(); 347 } 348 349 space_after_target: 350 351 if (nxt_slow_path(end - p < 10)) { 352 353 do { 354 p++; 355 356 if (p == end) { 357 return NXT_AGAIN; 358 } 359 360 } while (*p == ' '); 361 362 if (nxt_memcmp(p, "HTTP/", nxt_min(end - p, 5)) == 0) { 363 364 switch (end - p) { 365 case 8: 366 if (p[7] < '0' || p[7] > '9') { 367 break; 368 } 369 /* Fall through. */ 370 case 7: 371 if (p[6] != '.') { 372 break; 373 } 374 /* Fall through. */ 375 case 6: 376 if (p[5] < '0' || p[5] > '9') { 377 break; 378 } 379 /* Fall through. */ 380 default: 381 return NXT_AGAIN; 382 } 383 } 384 385 rp->space_in_target = 1; 386 goto rest_of_target; 387 } 388 389 /* " HTTP/1.1\r\n" or " HTTP/1.1\n" */ 390 391 if (nxt_slow_path(p[9] != '\r' && p[9] != '\n')) { 392 393 if (p[1] == ' ') { 394 /* surplus space after tartet */ 395 p++; 396 goto space_after_target; 397 } 398 399 rp->space_in_target = 1; 400 goto rest_of_target; 401 } 402 403 nxt_memcpy(ver.str, &p[1], 8); 404 405 if (nxt_fast_path(ver.ui64 == http11.ui64 406 || ver.ui64 == http10.ui64 407 || (nxt_memcmp(ver.str, "HTTP/1.", 7) == 0 408 && ver.s.minor >= '0' && ver.s.minor <= '9'))) 409 { 410 rp->version.ui64 = ver.ui64; 411 412 if (nxt_fast_path(p[9] == '\r')) { 413 p += 10; 414 415 if (nxt_slow_path(p == end)) { 416 return NXT_AGAIN; 417 } 418 419 if (nxt_slow_path(*p != '\n')) { 420 return NXT_HTTP_PARSE_INVALID; 421 } 422 423 *pos = p + 1; 424 425 } else { 426 *pos = p + 10; 427 } 428 429 if (rp->complex_target != 0 || rp->quoted_target != 0) { 430 rc = nxt_http_parse_complex_target(rp); 431 432 if (nxt_slow_path(rc != NXT_OK)) { 433 return rc; 434 } 435 436 return nxt_http_parse_field_name(rp, pos, end); 437 } 438 439 rp->path.start = rp->target_start; 440 441 if (args != NULL) { 442 rp->path.length = args - rp->target_start - 1; 443 444 rp->args.length = rp->target_end - args; 445 rp->args.start = args; 446 447 } else { 448 rp->path.length = rp->target_end - rp->target_start; 449 } 450 451 if (exten != NULL) { 452 rp->exten.length = (rp->path.start + rp->path.length) - exten; 453 rp->exten.start = exten; 454 } 455 456 return nxt_http_parse_field_name(rp, pos, end); 457 } 458 459 if (nxt_memcmp(ver.s.prefix, "HTTP/", 5) == 0 460 && ver.s.major >= '0' && ver.s.major <= '9' 461 && ver.s.point == '.' 462 && ver.s.minor >= '0' && ver.s.minor <= '9') 463 { 464 rp->version.ui64 = ver.ui64; 465 return NXT_HTTP_PARSE_UNSUPPORTED_VERSION; 466 } 467 468 return NXT_HTTP_PARSE_INVALID; 469 } 470 471 472 static nxt_int_t 473 nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos, 474 u_char *end) 475 { 476 u_char *p, ch; 477 478 p = *pos; 479 480 ch = *p; 481 482 if (ch == ' ') { 483 /* skip surplus spaces before target */ 484 485 do { 486 p++; 487 488 if (nxt_slow_path(p == end)) { 489 return NXT_AGAIN; 490 } 491 492 ch = *p; 493 494 } while (ch == ' '); 495 496 if (ch == '/') { 497 *pos = p; 498 return NXT_OK; 499 } 500 } 501 502 /* absolute path or '*' */ 503 504 /* TODO */ 505 506 return NXT_HTTP_PARSE_INVALID; 507 } 508 509 510 static nxt_int_t 511 nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos, 512 u_char *end) 513 { 514 u_char *p, c; 515 size_t len; 516 uint32_t hash; 517 518 static const u_char normal[256] nxt_aligned(64) = 519 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 520 "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0" 521 522 /* These 64 bytes should reside in one cache line. */ 523 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0_" 524 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0" 525 526 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 527 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 528 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 529 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"; 530 531 p = *pos + rp->field_name.length; 532 hash = rp->field_hash; 533 534 while (nxt_fast_path(end - p >= 8)) { 535 536 #define nxt_field_name_test_char(ch) \ 537 \ 538 c = normal[ch]; \ 539 \ 540 if (nxt_slow_path(c == '\0')) { \ 541 p = &(ch); \ 542 goto name_end; \ 543 } \ 544 \ 545 hash = nxt_http_field_hash_char(hash, c); 546 547 /* enddef */ 548 549 nxt_field_name_test_char(p[0]); 550 nxt_field_name_test_char(p[1]); 551 nxt_field_name_test_char(p[2]); 552 nxt_field_name_test_char(p[3]); 553 554 nxt_field_name_test_char(p[4]); 555 nxt_field_name_test_char(p[5]); 556 nxt_field_name_test_char(p[6]); 557 nxt_field_name_test_char(p[7]); 558 559 p += 8; 560 } 561 562 while (nxt_fast_path(p != end)) { 563 nxt_field_name_test_char(*p); p++; 564 } 565 566 len = p - *pos; 567 568 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { 569 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 570 } 571 572 rp->field_hash = hash; 573 rp->field_name.length = len; 574 575 rp->handler = &nxt_http_parse_field_name; 576 577 return NXT_AGAIN; 578 579 name_end: 580 581 if (nxt_fast_path(*p == ':')) { 582 if (nxt_slow_path(p == *pos)) { 583 return NXT_HTTP_PARSE_INVALID; 584 } 585 586 len = p - *pos; 587 588 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { 589 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 590 } 591 592 rp->field_hash = hash; 593 594 rp->field_name.length = len; 595 rp->field_name.start = *pos; 596 597 *pos = p + 1; 598 599 return nxt_http_parse_field_value(rp, pos, end); 600 } 601 602 if (nxt_slow_path(p != *pos)) { 603 return NXT_HTTP_PARSE_INVALID; 604 } 605 606 return nxt_http_parse_field_end(rp, pos, end); 607 } 608 609 610 static nxt_int_t 611 nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos, 612 u_char *end) 613 { 614 u_char *p, *start, ch; 615 size_t len; 616 617 p = *pos; 618 619 for ( ;; ) { 620 if (nxt_slow_path(p == end)) { 621 *pos = p; 622 rp->handler = &nxt_http_parse_field_value; 623 return NXT_AGAIN; 624 } 625 626 ch = *p; 627 628 if (ch != ' ' && ch != '\t') { 629 break; 630 } 631 632 p++; 633 } 634 635 start = p; 636 637 p += rp->field_value.length; 638 639 for ( ;; ) { 640 p = nxt_http_lookup_field_end(p, end); 641 642 if (nxt_slow_path(p == end)) { 643 *pos = start; 644 645 len = p - start; 646 647 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 648 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 649 } 650 651 rp->field_value.length = len; 652 rp->handler = &nxt_http_parse_field_value; 653 return NXT_AGAIN; 654 } 655 656 ch = *p; 657 658 if (nxt_fast_path(ch == '\r' || ch == '\n')) { 659 break; 660 } 661 662 if (ch != '\t') { 663 return NXT_HTTP_PARSE_INVALID; 664 } 665 666 p++; 667 } 668 669 *pos = p; 670 671 if (nxt_fast_path(p != start)) { 672 673 while (p[-1] == ' ' || p[-1] == '\t') { 674 p--; 675 } 676 } 677 678 len = p - start; 679 680 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 681 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 682 } 683 684 rp->field_value.length = len; 685 rp->field_value.start = start; 686 687 return nxt_http_parse_field_end(rp, pos, end); 688 } 689 690 691 static u_char * 692 nxt_http_lookup_field_end(u_char *p, u_char *end) 693 { 694 while (nxt_fast_path(end - p >= 16)) { 695 696 #define nxt_field_end_test_char(ch) \ 697 \ 698 if (nxt_slow_path((ch) < 0x20)) { \ 699 return &(ch); \ 700 } 701 702 /* enddef */ 703 704 nxt_field_end_test_char(p[0]); 705 nxt_field_end_test_char(p[1]); 706 nxt_field_end_test_char(p[2]); 707 nxt_field_end_test_char(p[3]); 708 709 nxt_field_end_test_char(p[4]); 710 nxt_field_end_test_char(p[5]); 711 nxt_field_end_test_char(p[6]); 712 nxt_field_end_test_char(p[7]); 713 714 nxt_field_end_test_char(p[8]); 715 nxt_field_end_test_char(p[9]); 716 nxt_field_end_test_char(p[10]); 717 nxt_field_end_test_char(p[11]); 718 719 nxt_field_end_test_char(p[12]); 720 nxt_field_end_test_char(p[13]); 721 nxt_field_end_test_char(p[14]); 722 nxt_field_end_test_char(p[15]); 723 724 p += 16; 725 } 726 727 while (nxt_fast_path(end - p >= 4)) { 728 729 nxt_field_end_test_char(p[0]); 730 nxt_field_end_test_char(p[1]); 731 nxt_field_end_test_char(p[2]); 732 nxt_field_end_test_char(p[3]); 733 734 p += 4; 735 } 736 737 switch (end - p) { 738 case 3: 739 nxt_field_end_test_char(*p); p++; 740 /* Fall through. */ 741 case 2: 742 nxt_field_end_test_char(*p); p++; 743 /* Fall through. */ 744 case 1: 745 nxt_field_end_test_char(*p); p++; 746 /* Fall through. */ 747 case 0: 748 break; 749 default: 750 nxt_unreachable(); 751 } 752 753 return p; 754 } 755 756 757 static nxt_int_t 758 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, 759 u_char *end) 760 { 761 u_char *p; 762 nxt_http_field_t *field; 763 764 p = *pos; 765 766 if (nxt_fast_path(*p == '\r')) { 767 p++; 768 769 if (nxt_slow_path(p == end)) { 770 rp->handler = &nxt_http_parse_field_end; 771 return NXT_AGAIN; 772 } 773 } 774 775 if (nxt_fast_path(*p == '\n')) { 776 *pos = p + 1; 777 778 if (rp->field_name.length != 0) { 779 field = nxt_list_add(rp->fields); 780 781 if (nxt_slow_path(field == NULL)) { 782 return NXT_ERROR; 783 } 784 785 field->hash = nxt_http_field_hash_end(rp->field_hash); 786 field->skip = 0; 787 788 field->name_length = rp->field_name.length; 789 field->value_length = rp->field_value.length; 790 field->name = rp->field_name.start; 791 field->value = rp->field_value.start; 792 793 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; 794 795 rp->field_name.length = 0; 796 rp->field_value.length = 0; 797 798 rp->handler = &nxt_http_parse_field_name; 799 return NXT_OK; 800 } 801 802 return NXT_DONE; 803 } 804 805 return NXT_HTTP_PARSE_INVALID; 806 } 807 808 809 #define \ 810 nxt_http_is_normal(c) \ 811 (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0)) 812 813 814 static const uint8_t nxt_http_normal[32] nxt_aligned(32) = { 815 816 /* \0 \r \n */ 817 0xFE, 0xDB, 0xFF, 0xFF, /* 1111 1110 1101 1011 1111 1111 1111 1111 */ 818 819 /* '&%$ #"! /.-, |*)( 7654 3210 ?>=< ;:98 */ 820 0xD6, 0x37, 0xFF, 0x7F, /* 1101 0110 0011 0111 1111 1111 0111 1111 */ 821 822 /* GFED CBA@ ONML KJIH WVUT SRQP _^]\ [ZYX */ 823 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 824 825 /* gfed cba` onml kjih wvut srqp ~}| {zyx */ 826 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 827 828 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 829 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 830 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 831 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 832 }; 833 834 835 static nxt_int_t 836 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp) 837 { 838 u_char *p, *u, c, ch, high, *exten, *args; 839 840 enum { 841 sw_normal = 0, 842 sw_slash, 843 sw_dot, 844 sw_dot_dot, 845 sw_quoted, 846 sw_quoted_second, 847 } state, saved_state; 848 849 nxt_prefetch(nxt_http_normal); 850 851 state = sw_normal; 852 saved_state = sw_normal; 853 p = rp->target_start; 854 855 u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1); 856 if (nxt_slow_path(u == NULL)) { 857 return NXT_ERROR; 858 } 859 860 rp->path.length = 0; 861 rp->path.start = u; 862 863 high = '\0'; 864 exten = NULL; 865 args = NULL; 866 867 while (p < rp->target_end) { 868 869 ch = *p++; 870 871 again: 872 873 switch (state) { 874 875 case sw_normal: 876 877 if (nxt_http_is_normal(ch)) { 878 *u++ = ch; 879 continue; 880 } 881 882 switch (ch) { 883 case '/': 884 exten = NULL; 885 state = sw_slash; 886 *u++ = ch; 887 continue; 888 case '%': 889 saved_state = state; 890 state = sw_quoted; 891 continue; 892 case '?': 893 args = p; 894 goto args; 895 case '#': 896 goto done; 897 case '.': 898 exten = u + 1; 899 *u++ = ch; 900 continue; 901 case '+': 902 rp->plus_in_target = 1; 903 /* Fall through. */ 904 default: 905 *u++ = ch; 906 continue; 907 } 908 909 break; 910 911 case sw_slash: 912 913 if (nxt_http_is_normal(ch)) { 914 state = sw_normal; 915 *u++ = ch; 916 continue; 917 } 918 919 switch (ch) { 920 case '/': 921 continue; 922 case '.': 923 state = sw_dot; 924 *u++ = ch; 925 continue; 926 case '%': 927 saved_state = state; 928 state = sw_quoted; 929 continue; 930 case '?': 931 args = p; 932 goto args; 933 case '#': 934 goto done; 935 case '+': 936 rp->plus_in_target = 1; 937 /* Fall through. */ 938 default: 939 state = sw_normal; 940 *u++ = ch; 941 continue; 942 } 943 944 break; 945 946 case sw_dot: 947 948 if (nxt_http_is_normal(ch)) { 949 state = sw_normal; 950 *u++ = ch; 951 continue; 952 } 953 954 switch (ch) { 955 case '/': 956 state = sw_slash; 957 u--; 958 continue; 959 case '.': 960 state = sw_dot_dot; 961 *u++ = ch; 962 continue; 963 case '%': 964 saved_state = state; 965 state = sw_quoted; 966 continue; 967 case '?': 968 args = p; 969 goto args; 970 case '#': 971 goto done; 972 case '+': 973 rp->plus_in_target = 1; 974 /* Fall through. */ 975 default: 976 state = sw_normal; 977 *u++ = ch; 978 continue; 979 } 980 981 break; 982 983 case sw_dot_dot: 984 985 if (nxt_http_is_normal(ch)) { 986 state = sw_normal; 987 *u++ = ch; 988 continue; 989 } 990 991 switch (ch) { 992 case '/': 993 state = sw_slash; 994 u -= 5; 995 for ( ;; ) { 996 if (u < rp->path.start) { 997 return NXT_HTTP_PARSE_INVALID; 998 } 999 if (*u == '/') { 1000 u++; 1001 break; 1002 } 1003 u--; 1004 } 1005 break; 1006 1007 case '%': 1008 saved_state = state; 1009 state = sw_quoted; 1010 continue; 1011 case '?': 1012 args = p; 1013 goto args; 1014 case '#': 1015 goto done; 1016 case '+': 1017 rp->plus_in_target = 1; 1018 /* Fall through. */ 1019 default: 1020 state = sw_normal; 1021 *u++ = ch; 1022 continue; 1023 } 1024 1025 break; 1026 1027 case sw_quoted: 1028 rp->quoted_target = 1; 1029 1030 if (ch >= '0' && ch <= '9') { 1031 high = (u_char) (ch - '0'); 1032 state = sw_quoted_second; 1033 continue; 1034 } 1035 1036 c = (u_char) (ch | 0x20); 1037 if (c >= 'a' && c <= 'f') { 1038 high = (u_char) (c - 'a' + 10); 1039 state = sw_quoted_second; 1040 continue; 1041 } 1042 1043 return NXT_HTTP_PARSE_INVALID; 1044 1045 case sw_quoted_second: 1046 if (ch >= '0' && ch <= '9') { 1047 ch = (u_char) ((high << 4) + ch - '0'); 1048 1049 if (ch == '%') { 1050 state = sw_normal; 1051 *u++ = '%'; 1052 1053 if (rp->encoded_slashes) { 1054 *u++ = '2'; 1055 *u++ = '5'; 1056 } 1057 1058 continue; 1059 } 1060 1061 if (ch == '#') { 1062 state = sw_normal; 1063 *u++ = '#'; 1064 continue; 1065 } 1066 1067 if (ch == '\0') { 1068 return NXT_HTTP_PARSE_INVALID; 1069 } 1070 1071 state = saved_state; 1072 goto again; 1073 } 1074 1075 c = (u_char) (ch | 0x20); 1076 if (c >= 'a' && c <= 'f') { 1077 ch = (u_char) ((high << 4) + c - 'a' + 10); 1078 1079 if (ch == '?') { 1080 state = sw_normal; 1081 *u++ = ch; 1082 continue; 1083 } 1084 1085 if (ch == '/' && rp->encoded_slashes) { 1086 state = sw_normal; 1087 *u++ = '%'; 1088 *u++ = '2'; 1089 *u++ = p[-1]; /* 'f' or 'F' */ 1090 continue; 1091 } 1092 1093 if (ch == '+') { 1094 rp->plus_in_target = 1; 1095 } 1096 1097 state = saved_state; 1098 goto again; 1099 } 1100 1101 return NXT_HTTP_PARSE_INVALID; 1102 } 1103 } 1104 1105 if (state >= sw_quoted) { 1106 return NXT_HTTP_PARSE_INVALID; 1107 } 1108 1109 args: 1110 1111 for (/* void */; p < rp->target_end; p++) { 1112 if (*p == '#') { 1113 break; 1114 } 1115 } 1116 1117 if (args != NULL) { 1118 rp->args.length = p - args; 1119 rp->args.start = args; 1120 } 1121 1122 done: 1123 1124 rp->path.length = u - rp->path.start; 1125 1126 if (exten) { 1127 rp->exten.length = u - exten; 1128 rp->exten.start = exten; 1129 } 1130 1131 return NXT_OK; 1132 } 1133 1134 1135 const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = { 1136 NXT_LVLHSH_BUCKET_SIZE(64), 1137 { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 }, 1138 nxt_http_field_hash_test, 1139 nxt_http_field_hash_alloc, 1140 nxt_http_field_hash_free, 1141 }; 1142 1143 1144 static nxt_int_t 1145 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data) 1146 { 1147 nxt_http_field_proc_t *field; 1148 1149 field = data; 1150 1151 if (nxt_strcasestr_eq(&lhq->key, &field->name)) { 1152 return NXT_OK; 1153 } 1154 1155 return NXT_DECLINED; 1156 } 1157 1158 1159 static void * 1160 nxt_http_field_hash_alloc(void *pool, size_t size) 1161 { 1162 return nxt_mp_align(pool, size, size); 1163 } 1164 1165 1166 static void 1167 nxt_http_field_hash_free(void *pool, void *p) 1168 { 1169 nxt_mp_free(pool, p); 1170 } 1171 1172 1173 static nxt_int_t 1174 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data) 1175 { 1176 return NXT_OK; 1177 } 1178 1179 1180 nxt_int_t 1181 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1182 nxt_http_field_proc_t items[], nxt_uint_t count) 1183 { 1184 u_char ch; 1185 uint32_t key; 1186 nxt_str_t *name; 1187 nxt_int_t ret; 1188 nxt_uint_t i, j; 1189 nxt_lvlhsh_query_t lhq; 1190 1191 lhq.replace = 0; 1192 lhq.proto = &nxt_http_fields_hash_proto; 1193 lhq.pool = mp; 1194 1195 for (i = 0; i < count; i++) { 1196 key = NXT_HTTP_FIELD_HASH_INIT; 1197 name = &items[i].name; 1198 1199 for (j = 0; j < name->length; j++) { 1200 ch = nxt_lowcase(name->start[j]); 1201 key = nxt_http_field_hash_char(key, ch); 1202 } 1203 1204 lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF; 1205 lhq.key = *name; 1206 lhq.value = &items[i]; 1207 1208 ret = nxt_lvlhsh_insert(hash, &lhq); 1209 1210 if (nxt_slow_path(ret != NXT_OK)) { 1211 return NXT_ERROR; 1212 } 1213 } 1214 1215 return NXT_OK; 1216 } 1217 1218 1219 nxt_uint_t 1220 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1221 nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level) 1222 { 1223 u_char ch; 1224 uint32_t key, mask; 1225 nxt_str_t *name; 1226 nxt_uint_t colls, i, j; 1227 nxt_lvlhsh_proto_t proto; 1228 nxt_lvlhsh_query_t lhq; 1229 1230 proto = nxt_http_fields_hash_proto; 1231 proto.test = nxt_http_field_hash_collision; 1232 1233 lhq.replace = 0; 1234 lhq.proto = &proto; 1235 lhq.pool = mp; 1236 1237 mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF; 1238 1239 colls = 0; 1240 1241 for (i = 0; i < count; i++) { 1242 key = NXT_HTTP_FIELD_HASH_INIT; 1243 name = &items[i].name; 1244 1245 for (j = 0; j < name->length; j++) { 1246 ch = nxt_lowcase(name->start[j]); 1247 key = nxt_http_field_hash_char(key, ch); 1248 } 1249 1250 lhq.key_hash = nxt_http_field_hash_end(key) & mask; 1251 lhq.value = &items[i]; 1252 1253 if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) { 1254 colls++; 1255 } 1256 } 1257 1258 return colls; 1259 } 1260 1261 1262 nxt_int_t 1263 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx) 1264 { 1265 nxt_int_t ret; 1266 nxt_http_field_t *field; 1267 1268 nxt_list_each(field, fields) { 1269 1270 ret = nxt_http_field_process(field, hash, ctx); 1271 if (nxt_slow_path(ret != NXT_OK)) { 1272 return ret; 1273 } 1274 1275 } nxt_list_loop; 1276 1277 return NXT_OK; 1278 } 1279