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