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 args = p; 974 goto args; 975 case '#': 976 goto done; 977 default: 978 state = sw_normal; 979 *u++ = ch; 980 continue; 981 } 982 983 break; 984 985 case sw_dot_dot: 986 987 if (nxt_http_is_normal(ch)) { 988 state = sw_normal; 989 *u++ = ch; 990 continue; 991 } 992 993 switch (ch) { 994 case '/': 995 state = sw_slash; 996 u -= 5; 997 for ( ;; ) { 998 if (u < rp->path.start) { 999 return NXT_HTTP_PARSE_INVALID; 1000 } 1001 if (*u == '/') { 1002 u++; 1003 break; 1004 } 1005 u--; 1006 } 1007 break; 1008 1009 case '%': 1010 saved_state = state; 1011 state = sw_quoted; 1012 continue; 1013 case '?': 1014 args = p; 1015 goto args; 1016 case '#': 1017 goto done; 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_quoted) { 1101 return NXT_HTTP_PARSE_INVALID; 1102 } 1103 1104 args: 1105 1106 for (/* void */; p < rp->target_end; p++) { 1107 if (*p == '#') { 1108 break; 1109 } 1110 } 1111 1112 if (args != NULL) { 1113 rp->args.length = p - args; 1114 rp->args.start = args; 1115 } 1116 1117 done: 1118 1119 rp->path.length = u - rp->path.start; 1120 1121 if (exten) { 1122 rp->exten.length = u - exten; 1123 rp->exten.start = exten; 1124 } 1125 1126 return NXT_OK; 1127 } 1128 1129 1130 const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = { 1131 NXT_LVLHSH_BUCKET_SIZE(64), 1132 { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 }, 1133 nxt_http_field_hash_test, 1134 nxt_http_field_hash_alloc, 1135 nxt_http_field_hash_free, 1136 }; 1137 1138 1139 static nxt_int_t 1140 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data) 1141 { 1142 nxt_http_field_proc_t *field; 1143 1144 field = data; 1145 1146 if (nxt_strcasestr_eq(&lhq->key, &field->name)) { 1147 return NXT_OK; 1148 } 1149 1150 return NXT_DECLINED; 1151 } 1152 1153 1154 static void * 1155 nxt_http_field_hash_alloc(void *pool, size_t size) 1156 { 1157 return nxt_mp_align(pool, size, size); 1158 } 1159 1160 1161 static void 1162 nxt_http_field_hash_free(void *pool, void *p) 1163 { 1164 nxt_mp_free(pool, p); 1165 } 1166 1167 1168 static nxt_int_t 1169 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data) 1170 { 1171 return NXT_OK; 1172 } 1173 1174 1175 nxt_int_t 1176 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1177 nxt_http_field_proc_t items[], nxt_uint_t count) 1178 { 1179 u_char ch; 1180 uint32_t key; 1181 nxt_str_t *name; 1182 nxt_int_t ret; 1183 nxt_uint_t i, j; 1184 nxt_lvlhsh_query_t lhq; 1185 1186 lhq.replace = 0; 1187 lhq.proto = &nxt_http_fields_hash_proto; 1188 lhq.pool = mp; 1189 1190 for (i = 0; i < count; i++) { 1191 key = NXT_HTTP_FIELD_HASH_INIT; 1192 name = &items[i].name; 1193 1194 for (j = 0; j < name->length; j++) { 1195 ch = nxt_lowcase(name->start[j]); 1196 key = nxt_http_field_hash_char(key, ch); 1197 } 1198 1199 lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF; 1200 lhq.key = *name; 1201 lhq.value = &items[i]; 1202 1203 ret = nxt_lvlhsh_insert(hash, &lhq); 1204 1205 if (nxt_slow_path(ret != NXT_OK)) { 1206 return NXT_ERROR; 1207 } 1208 } 1209 1210 return NXT_OK; 1211 } 1212 1213 1214 nxt_uint_t 1215 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1216 nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level) 1217 { 1218 u_char ch; 1219 uint32_t key, mask; 1220 nxt_str_t *name; 1221 nxt_uint_t colls, i, j; 1222 nxt_lvlhsh_proto_t proto; 1223 nxt_lvlhsh_query_t lhq; 1224 1225 proto = nxt_http_fields_hash_proto; 1226 proto.test = nxt_http_field_hash_collision; 1227 1228 lhq.replace = 0; 1229 lhq.proto = &proto; 1230 lhq.pool = mp; 1231 1232 mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF; 1233 1234 colls = 0; 1235 1236 for (i = 0; i < count; i++) { 1237 key = NXT_HTTP_FIELD_HASH_INIT; 1238 name = &items[i].name; 1239 1240 for (j = 0; j < name->length; j++) { 1241 ch = nxt_lowcase(name->start[j]); 1242 key = nxt_http_field_hash_char(key, ch); 1243 } 1244 1245 lhq.key_hash = nxt_http_field_hash_end(key) & mask; 1246 lhq.value = &items[i]; 1247 1248 if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) { 1249 colls++; 1250 } 1251 } 1252 1253 return colls; 1254 } 1255 1256 1257 nxt_int_t 1258 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx) 1259 { 1260 nxt_int_t ret; 1261 nxt_http_field_t *field; 1262 1263 nxt_list_each(field, fields) { 1264 1265 ret = nxt_http_field_process(field, hash, ctx); 1266 if (nxt_slow_path(ret != NXT_OK)) { 1267 return ret; 1268 } 1269 1270 } nxt_list_loop; 1271 1272 return NXT_OK; 1273 } 1274