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