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_traps_e; 51 52 53 static const uint8_t nxt_http_target_chars[256] nxt_aligned(64) = { 54 /* \0 \n \r */ 55 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 4, 0, 0, 56 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 57 58 /* \s ! " # $ % & ' ( ) * + , - . / */ 59 1, 0, 0, 2, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 6, 5, 60 61 /* 0 1 2 3 4 5 6 7 8 9 : ; < = > ? */ 62 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 63 }; 64 65 66 nxt_inline nxt_http_target_traps_e 67 nxt_http_parse_target(u_char **pos, u_char *end) 68 { 69 u_char *p; 70 nxt_uint_t trap; 71 72 p = *pos; 73 74 while (nxt_fast_path(end - p >= 10)) { 75 76 #define nxt_target_test_char(ch) \ 77 \ 78 trap = nxt_http_target_chars[ch]; \ 79 \ 80 if (nxt_slow_path(trap != 0)) { \ 81 *pos = &(ch); \ 82 return trap; \ 83 } 84 85 /* enddef */ 86 87 nxt_target_test_char(p[0]); 88 nxt_target_test_char(p[1]); 89 nxt_target_test_char(p[2]); 90 nxt_target_test_char(p[3]); 91 92 nxt_target_test_char(p[4]); 93 nxt_target_test_char(p[5]); 94 nxt_target_test_char(p[6]); 95 nxt_target_test_char(p[7]); 96 97 nxt_target_test_char(p[8]); 98 nxt_target_test_char(p[9]); 99 100 p += 10; 101 } 102 103 while (p != end) { 104 nxt_target_test_char(*p); p++; 105 } 106 107 return NXT_HTTP_TARGET_AGAIN; 108 } 109 110 111 nxt_int_t 112 nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp) 113 { 114 rp->mem_pool = mp; 115 116 rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t)); 117 if (nxt_slow_path(rp->fields == NULL)) { 118 return NXT_ERROR; 119 } 120 121 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; 122 123 return NXT_OK; 124 } 125 126 127 nxt_int_t 128 nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b) 129 { 130 nxt_int_t rc; 131 132 if (rp->handler == NULL) { 133 rp->handler = &nxt_http_parse_request_line; 134 } 135 136 do { 137 rc = rp->handler(rp, &b->pos, b->free); 138 } while (rc == NXT_OK); 139 140 return rc; 141 } 142 143 144 nxt_int_t 145 nxt_http_parse_fields(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b) 146 { 147 nxt_int_t rc; 148 149 if (rp->handler == NULL) { 150 rp->handler = &nxt_http_parse_field_name; 151 } 152 153 do { 154 rc = rp->handler(rp, &b->pos, b->free); 155 } while (rc == NXT_OK); 156 157 return rc; 158 } 159 160 161 static nxt_int_t 162 nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos, 163 u_char *end) 164 { 165 u_char *p, ch, *after_slash, *args; 166 nxt_int_t rc; 167 nxt_bool_t rest; 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 args = NULL; 259 rest = 0; 260 261 continue_target: 262 263 for ( ;; ) { 264 p++; 265 266 trap = nxt_http_parse_target(&p, end); 267 268 switch (trap) { 269 case NXT_HTTP_TARGET_SLASH: 270 if (nxt_slow_path(after_slash == p)) { 271 rp->complex_target = 1; 272 goto rest_of_target; 273 } 274 275 after_slash = p + 1; 276 continue; 277 278 case NXT_HTTP_TARGET_DOT: 279 if (nxt_slow_path(after_slash == p)) { 280 rp->complex_target = 1; 281 goto rest_of_target; 282 } 283 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_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 || rp->quoted_target != 0) { 438 rc = nxt_http_parse_complex_target(rp); 439 440 if (nxt_slow_path(rc != NXT_OK)) { 441 return rc; 442 } 443 444 return nxt_http_parse_field_name(rp, pos, end); 445 } 446 447 rp->path.start = rp->target_start; 448 449 if (args != NULL) { 450 rp->path.length = args - rp->target_start - 1; 451 452 rp->args.length = rp->target_end - args; 453 rp->args.start = args; 454 455 } else { 456 rp->path.length = rp->target_end - rp->target_start; 457 } 458 459 return nxt_http_parse_field_name(rp, pos, end); 460 } 461 462 if (nxt_memcmp(ver.s.prefix, "HTTP/", 5) == 0 463 && ver.s.major >= '0' && ver.s.major <= '9' 464 && ver.s.point == '.' 465 && ver.s.minor >= '0' && ver.s.minor <= '9') 466 { 467 rp->version.ui64 = ver.ui64; 468 return NXT_HTTP_PARSE_UNSUPPORTED_VERSION; 469 } 470 471 return NXT_HTTP_PARSE_INVALID; 472 } 473 474 475 static nxt_int_t 476 nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos, 477 u_char *end) 478 { 479 u_char *p, ch; 480 481 p = *pos; 482 483 ch = *p; 484 485 if (ch == ' ') { 486 /* skip surplus spaces before target */ 487 488 do { 489 p++; 490 491 if (nxt_slow_path(p == end)) { 492 return NXT_AGAIN; 493 } 494 495 ch = *p; 496 497 } while (ch == ' '); 498 499 if (ch == '/') { 500 *pos = p; 501 return NXT_OK; 502 } 503 } 504 505 /* absolute path or '*' */ 506 507 /* TODO */ 508 509 return NXT_HTTP_PARSE_INVALID; 510 } 511 512 513 static nxt_int_t 514 nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos, 515 u_char *end) 516 { 517 u_char *p, c; 518 size_t len; 519 uint32_t hash; 520 521 static const u_char normal[256] nxt_aligned(64) = 522 "\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" 523 "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0" 524 525 /* These 64 bytes should reside in one cache line. */ 526 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0_" 527 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0" 528 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 "\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" 531 "\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" 532 "\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"; 533 534 p = *pos + rp->field_name.length; 535 hash = rp->field_hash; 536 537 while (nxt_fast_path(end - p >= 8)) { 538 539 #define nxt_field_name_test_char(ch) \ 540 \ 541 c = normal[ch]; \ 542 \ 543 if (nxt_slow_path(c == '\0')) { \ 544 p = &(ch); \ 545 goto name_end; \ 546 } \ 547 \ 548 hash = nxt_http_field_hash_char(hash, c); 549 550 /* enddef */ 551 552 nxt_field_name_test_char(p[0]); 553 nxt_field_name_test_char(p[1]); 554 nxt_field_name_test_char(p[2]); 555 nxt_field_name_test_char(p[3]); 556 557 nxt_field_name_test_char(p[4]); 558 nxt_field_name_test_char(p[5]); 559 nxt_field_name_test_char(p[6]); 560 nxt_field_name_test_char(p[7]); 561 562 p += 8; 563 } 564 565 while (nxt_fast_path(p != end)) { 566 nxt_field_name_test_char(*p); p++; 567 } 568 569 len = p - *pos; 570 571 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { 572 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 573 } 574 575 rp->field_hash = hash; 576 rp->field_name.length = len; 577 578 rp->handler = &nxt_http_parse_field_name; 579 580 return NXT_AGAIN; 581 582 name_end: 583 584 if (nxt_fast_path(*p == ':')) { 585 if (nxt_slow_path(p == *pos)) { 586 return NXT_HTTP_PARSE_INVALID; 587 } 588 589 len = p - *pos; 590 591 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) { 592 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 593 } 594 595 rp->field_hash = hash; 596 597 rp->field_name.length = len; 598 rp->field_name.start = *pos; 599 600 *pos = p + 1; 601 602 return nxt_http_parse_field_value(rp, pos, end); 603 } 604 605 if (nxt_slow_path(p != *pos)) { 606 return NXT_HTTP_PARSE_INVALID; 607 } 608 609 return nxt_http_parse_field_end(rp, pos, end); 610 } 611 612 613 static nxt_int_t 614 nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos, 615 u_char *end) 616 { 617 u_char *p, *start, ch; 618 size_t len; 619 620 p = *pos; 621 622 for ( ;; ) { 623 if (nxt_slow_path(p == end)) { 624 *pos = p; 625 rp->handler = &nxt_http_parse_field_value; 626 return NXT_AGAIN; 627 } 628 629 ch = *p; 630 631 if (ch != ' ' && ch != '\t') { 632 break; 633 } 634 635 p++; 636 } 637 638 start = p; 639 640 p += rp->field_value.length; 641 642 for ( ;; ) { 643 p = nxt_http_lookup_field_end(p, end); 644 645 if (nxt_slow_path(p == end)) { 646 *pos = start; 647 648 len = p - start; 649 650 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 651 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 652 } 653 654 rp->field_value.length = len; 655 rp->handler = &nxt_http_parse_field_value; 656 return NXT_AGAIN; 657 } 658 659 ch = *p; 660 661 if (nxt_fast_path(ch == '\r' || ch == '\n')) { 662 break; 663 } 664 665 if (ch != '\t') { 666 return NXT_HTTP_PARSE_INVALID; 667 } 668 669 p++; 670 } 671 672 *pos = p; 673 674 if (nxt_fast_path(p != start)) { 675 676 while (p[-1] == ' ' || p[-1] == '\t') { 677 p--; 678 } 679 } 680 681 len = p - start; 682 683 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 684 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 685 } 686 687 rp->field_value.length = len; 688 rp->field_value.start = start; 689 690 return nxt_http_parse_field_end(rp, pos, end); 691 } 692 693 694 static u_char * 695 nxt_http_lookup_field_end(u_char *p, u_char *end) 696 { 697 while (nxt_fast_path(end - p >= 16)) { 698 699 #define nxt_field_end_test_char(ch) \ 700 \ 701 if (nxt_slow_path((ch) < 0x20)) { \ 702 return &(ch); \ 703 } 704 705 /* enddef */ 706 707 nxt_field_end_test_char(p[0]); 708 nxt_field_end_test_char(p[1]); 709 nxt_field_end_test_char(p[2]); 710 nxt_field_end_test_char(p[3]); 711 712 nxt_field_end_test_char(p[4]); 713 nxt_field_end_test_char(p[5]); 714 nxt_field_end_test_char(p[6]); 715 nxt_field_end_test_char(p[7]); 716 717 nxt_field_end_test_char(p[8]); 718 nxt_field_end_test_char(p[9]); 719 nxt_field_end_test_char(p[10]); 720 nxt_field_end_test_char(p[11]); 721 722 nxt_field_end_test_char(p[12]); 723 nxt_field_end_test_char(p[13]); 724 nxt_field_end_test_char(p[14]); 725 nxt_field_end_test_char(p[15]); 726 727 p += 16; 728 } 729 730 while (nxt_fast_path(end - p >= 4)) { 731 732 nxt_field_end_test_char(p[0]); 733 nxt_field_end_test_char(p[1]); 734 nxt_field_end_test_char(p[2]); 735 nxt_field_end_test_char(p[3]); 736 737 p += 4; 738 } 739 740 switch (end - p) { 741 case 3: 742 nxt_field_end_test_char(*p); p++; 743 /* Fall through. */ 744 case 2: 745 nxt_field_end_test_char(*p); p++; 746 /* Fall through. */ 747 case 1: 748 nxt_field_end_test_char(*p); p++; 749 /* Fall through. */ 750 case 0: 751 break; 752 default: 753 nxt_unreachable(); 754 } 755 756 return p; 757 } 758 759 760 static nxt_int_t 761 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, 762 u_char *end) 763 { 764 u_char *p; 765 nxt_http_field_t *field; 766 767 p = *pos; 768 769 if (nxt_fast_path(*p == '\r')) { 770 p++; 771 772 if (nxt_slow_path(p == end)) { 773 rp->handler = &nxt_http_parse_field_end; 774 return NXT_AGAIN; 775 } 776 } 777 778 if (nxt_fast_path(*p == '\n')) { 779 *pos = p + 1; 780 781 if (rp->field_name.length != 0) { 782 field = nxt_list_add(rp->fields); 783 784 if (nxt_slow_path(field == NULL)) { 785 return NXT_ERROR; 786 } 787 788 field->hash = nxt_http_field_hash_end(rp->field_hash); 789 field->skip = 0; 790 791 field->name_length = rp->field_name.length; 792 field->value_length = rp->field_value.length; 793 field->name = rp->field_name.start; 794 field->value = rp->field_value.start; 795 796 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; 797 798 rp->field_name.length = 0; 799 rp->field_value.length = 0; 800 801 rp->handler = &nxt_http_parse_field_name; 802 return NXT_OK; 803 } 804 805 return NXT_DONE; 806 } 807 808 return NXT_HTTP_PARSE_INVALID; 809 } 810 811 812 #define \ 813 nxt_http_is_normal(c) \ 814 (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0)) 815 816 817 static const uint8_t nxt_http_normal[32] nxt_aligned(32) = { 818 819 /* \0 \r \n */ 820 0xFE, 0xDB, 0xFF, 0xFF, /* 1111 1110 1101 1011 1111 1111 1111 1111 */ 821 822 /* '&%$ #"! /.-, |*)( 7654 3210 ?>=< ;:98 */ 823 0xD6, 0x37, 0xFF, 0x7F, /* 1101 0110 0011 0111 1111 1111 0111 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 /* gfed cba` onml kjih wvut srqp ~}| {zyx */ 829 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 830 831 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 832 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 833 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 834 0xFF, 0xFF, 0xFF, 0xFF, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 835 }; 836 837 838 static nxt_int_t 839 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp) 840 { 841 u_char *p, *u, c, ch, high, *args; 842 843 enum { 844 sw_normal = 0, 845 sw_slash, 846 sw_dot, 847 sw_dot_dot, 848 sw_quoted, 849 sw_quoted_second, 850 } state, saved_state; 851 852 nxt_prefetch(nxt_http_normal); 853 854 state = sw_normal; 855 saved_state = sw_normal; 856 p = rp->target_start; 857 858 u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1); 859 if (nxt_slow_path(u == NULL)) { 860 return NXT_ERROR; 861 } 862 863 rp->path.length = 0; 864 rp->path.start = u; 865 866 high = '\0'; 867 args = NULL; 868 869 while (p < rp->target_end) { 870 871 ch = *p++; 872 873 again: 874 875 switch (state) { 876 877 case sw_normal: 878 879 if (nxt_http_is_normal(ch)) { 880 *u++ = ch; 881 continue; 882 } 883 884 switch (ch) { 885 case '/': 886 state = sw_slash; 887 *u++ = ch; 888 continue; 889 case '%': 890 saved_state = state; 891 state = sw_quoted; 892 continue; 893 case '?': 894 args = p; 895 goto args; 896 case '#': 897 goto done; 898 default: 899 *u++ = ch; 900 continue; 901 } 902 903 break; 904 905 case sw_slash: 906 907 if (nxt_http_is_normal(ch)) { 908 state = sw_normal; 909 *u++ = ch; 910 continue; 911 } 912 913 switch (ch) { 914 case '/': 915 continue; 916 case '.': 917 state = sw_dot; 918 *u++ = ch; 919 continue; 920 case '%': 921 saved_state = state; 922 state = sw_quoted; 923 continue; 924 case '?': 925 args = p; 926 goto args; 927 case '#': 928 goto done; 929 default: 930 state = sw_normal; 931 *u++ = ch; 932 continue; 933 } 934 935 break; 936 937 case sw_dot: 938 939 if (nxt_http_is_normal(ch)) { 940 state = sw_normal; 941 *u++ = ch; 942 continue; 943 } 944 945 switch (ch) { 946 case '/': 947 state = sw_slash; 948 u--; 949 continue; 950 case '.': 951 state = sw_dot_dot; 952 *u++ = ch; 953 continue; 954 case '%': 955 saved_state = state; 956 state = sw_quoted; 957 continue; 958 case '?': 959 u--; 960 args = p; 961 goto args; 962 case '#': 963 u--; 964 goto done; 965 default: 966 state = sw_normal; 967 *u++ = ch; 968 continue; 969 } 970 971 break; 972 973 case sw_dot_dot: 974 975 if (nxt_http_is_normal(ch)) { 976 state = sw_normal; 977 *u++ = ch; 978 continue; 979 } 980 981 switch (ch) { 982 983 case '/': 984 case '?': 985 case '#': 986 u -= 5; 987 988 for ( ;; ) { 989 if (u < rp->path.start) { 990 return NXT_HTTP_PARSE_INVALID; 991 } 992 993 if (*u == '/') { 994 u++; 995 break; 996 } 997 998 u--; 999 } 1000 1001 if (ch == '?') { 1002 args = p; 1003 goto args; 1004 } 1005 1006 if (ch == '#') { 1007 goto done; 1008 } 1009 1010 state = sw_slash; 1011 break; 1012 1013 case '%': 1014 saved_state = state; 1015 state = sw_quoted; 1016 continue; 1017 1018 default: 1019 state = sw_normal; 1020 *u++ = ch; 1021 continue; 1022 } 1023 1024 break; 1025 1026 case sw_quoted: 1027 rp->quoted_target = 1; 1028 1029 if (ch >= '0' && ch <= '9') { 1030 high = (u_char) (ch - '0'); 1031 state = sw_quoted_second; 1032 continue; 1033 } 1034 1035 c = (u_char) (ch | 0x20); 1036 if (c >= 'a' && c <= 'f') { 1037 high = (u_char) (c - 'a' + 10); 1038 state = sw_quoted_second; 1039 continue; 1040 } 1041 1042 return NXT_HTTP_PARSE_INVALID; 1043 1044 case sw_quoted_second: 1045 if (ch >= '0' && ch <= '9') { 1046 ch = (u_char) ((high << 4) + ch - '0'); 1047 1048 if (ch == '%') { 1049 state = sw_normal; 1050 *u++ = '%'; 1051 1052 if (rp->encoded_slashes) { 1053 *u++ = '2'; 1054 *u++ = '5'; 1055 } 1056 1057 continue; 1058 } 1059 1060 if (ch == '#') { 1061 state = sw_normal; 1062 *u++ = '#'; 1063 continue; 1064 } 1065 1066 if (ch == '\0') { 1067 return NXT_HTTP_PARSE_INVALID; 1068 } 1069 1070 state = saved_state; 1071 goto again; 1072 } 1073 1074 c = (u_char) (ch | 0x20); 1075 if (c >= 'a' && c <= 'f') { 1076 ch = (u_char) ((high << 4) + c - 'a' + 10); 1077 1078 if (ch == '?') { 1079 state = sw_normal; 1080 *u++ = ch; 1081 continue; 1082 } 1083 1084 if (ch == '/' && rp->encoded_slashes) { 1085 state = sw_normal; 1086 *u++ = '%'; 1087 *u++ = '2'; 1088 *u++ = p[-1]; /* 'f' or 'F' */ 1089 continue; 1090 } 1091 1092 state = saved_state; 1093 goto again; 1094 } 1095 1096 return NXT_HTTP_PARSE_INVALID; 1097 } 1098 } 1099 1100 if (state >= sw_dot) { 1101 if (state >= sw_quoted) { 1102 return NXT_HTTP_PARSE_INVALID; 1103 } 1104 1105 /* "/." and "/.." must be normalized similar to "/./" and "/../". */ 1106 ch = '/'; 1107 goto again; 1108 } 1109 1110 args: 1111 1112 for (/* void */; p < rp->target_end; p++) { 1113 if (*p == '#') { 1114 break; 1115 } 1116 } 1117 1118 if (args != NULL) { 1119 rp->args.length = p - args; 1120 rp->args.start = args; 1121 } 1122 1123 done: 1124 1125 rp->path.length = u - rp->path.start; 1126 1127 return NXT_OK; 1128 } 1129 1130 1131 const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = { 1132 NXT_LVLHSH_BUCKET_SIZE(64), 1133 { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 }, 1134 nxt_http_field_hash_test, 1135 nxt_http_field_hash_alloc, 1136 nxt_http_field_hash_free, 1137 }; 1138 1139 1140 static nxt_int_t 1141 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data) 1142 { 1143 nxt_http_field_proc_t *field; 1144 1145 field = data; 1146 1147 if (nxt_strcasestr_eq(&lhq->key, &field->name)) { 1148 return NXT_OK; 1149 } 1150 1151 return NXT_DECLINED; 1152 } 1153 1154 1155 static void * 1156 nxt_http_field_hash_alloc(void *pool, size_t size) 1157 { 1158 return nxt_mp_align(pool, size, size); 1159 } 1160 1161 1162 static void 1163 nxt_http_field_hash_free(void *pool, void *p) 1164 { 1165 nxt_mp_free(pool, p); 1166 } 1167 1168 1169 static nxt_int_t 1170 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data) 1171 { 1172 return NXT_OK; 1173 } 1174 1175 1176 nxt_int_t 1177 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1178 nxt_http_field_proc_t items[], nxt_uint_t count) 1179 { 1180 u_char ch; 1181 uint32_t key; 1182 nxt_str_t *name; 1183 nxt_int_t ret; 1184 nxt_uint_t i, j; 1185 nxt_lvlhsh_query_t lhq; 1186 1187 lhq.replace = 0; 1188 lhq.proto = &nxt_http_fields_hash_proto; 1189 lhq.pool = mp; 1190 1191 for (i = 0; i < count; i++) { 1192 key = NXT_HTTP_FIELD_HASH_INIT; 1193 name = &items[i].name; 1194 1195 for (j = 0; j < name->length; j++) { 1196 ch = nxt_lowcase(name->start[j]); 1197 key = nxt_http_field_hash_char(key, ch); 1198 } 1199 1200 lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF; 1201 lhq.key = *name; 1202 lhq.value = &items[i]; 1203 1204 ret = nxt_lvlhsh_insert(hash, &lhq); 1205 1206 if (nxt_slow_path(ret != NXT_OK)) { 1207 return NXT_ERROR; 1208 } 1209 } 1210 1211 return NXT_OK; 1212 } 1213 1214 1215 nxt_uint_t 1216 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1217 nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level) 1218 { 1219 u_char ch; 1220 uint32_t key, mask; 1221 nxt_str_t *name; 1222 nxt_uint_t colls, i, j; 1223 nxt_lvlhsh_proto_t proto; 1224 nxt_lvlhsh_query_t lhq; 1225 1226 proto = nxt_http_fields_hash_proto; 1227 proto.test = nxt_http_field_hash_collision; 1228 1229 lhq.replace = 0; 1230 lhq.proto = &proto; 1231 lhq.pool = mp; 1232 1233 mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF; 1234 1235 colls = 0; 1236 1237 for (i = 0; i < count; i++) { 1238 key = NXT_HTTP_FIELD_HASH_INIT; 1239 name = &items[i].name; 1240 1241 for (j = 0; j < name->length; j++) { 1242 ch = nxt_lowcase(name->start[j]); 1243 key = nxt_http_field_hash_char(key, ch); 1244 } 1245 1246 lhq.key_hash = nxt_http_field_hash_end(key) & mask; 1247 lhq.value = &items[i]; 1248 1249 if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) { 1250 colls++; 1251 } 1252 } 1253 1254 return colls; 1255 } 1256 1257 1258 nxt_int_t 1259 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx) 1260 { 1261 nxt_int_t ret; 1262 nxt_http_field_t *field; 1263 1264 nxt_list_each(field, fields) { 1265 1266 ret = nxt_http_field_process(field, hash, ctx); 1267 if (nxt_slow_path(ret != NXT_OK)) { 1268 return ret; 1269 } 1270 1271 } nxt_list_loop; 1272 1273 return NXT_OK; 1274 } 1275