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