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