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 if (*p != ' ') { 622 break; 623 } 624 625 p++; 626 } 627 628 start = p; 629 630 p += rp->field_value.length; 631 632 for ( ;; ) { 633 p = nxt_http_lookup_field_end(p, end); 634 635 if (nxt_slow_path(p == end)) { 636 *pos = start; 637 638 len = p - start; 639 640 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 641 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 642 } 643 644 rp->field_value.length = len; 645 rp->handler = &nxt_http_parse_field_value; 646 return NXT_AGAIN; 647 } 648 649 ch = *p; 650 651 if (nxt_fast_path(ch == '\r' || ch == '\n')) { 652 break; 653 } 654 655 if (ch != '\t') { 656 return NXT_HTTP_PARSE_INVALID; 657 } 658 659 p++; 660 } 661 662 *pos = p; 663 664 if (nxt_fast_path(p != start)) { 665 while (p[-1] == ' ') { 666 p--; 667 } 668 } 669 670 len = p - start; 671 672 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) { 673 return NXT_HTTP_PARSE_TOO_LARGE_FIELD; 674 } 675 676 rp->field_value.length = len; 677 rp->field_value.start = start; 678 679 return nxt_http_parse_field_end(rp, pos, end); 680 } 681 682 683 static u_char * 684 nxt_http_lookup_field_end(u_char *p, u_char *end) 685 { 686 while (nxt_fast_path(end - p >= 16)) { 687 688 #define nxt_field_end_test_char(ch) \ 689 \ 690 /* Values below 0x20 become more than 0xdf. */ \ 691 if (nxt_slow_path((u_char) ((ch) - 0x20) > 0x5e)) { \ 692 return &(ch); \ 693 } 694 695 /* enddef */ 696 697 nxt_field_end_test_char(p[0]); 698 nxt_field_end_test_char(p[1]); 699 nxt_field_end_test_char(p[2]); 700 nxt_field_end_test_char(p[3]); 701 702 nxt_field_end_test_char(p[4]); 703 nxt_field_end_test_char(p[5]); 704 nxt_field_end_test_char(p[6]); 705 nxt_field_end_test_char(p[7]); 706 707 nxt_field_end_test_char(p[8]); 708 nxt_field_end_test_char(p[9]); 709 nxt_field_end_test_char(p[10]); 710 nxt_field_end_test_char(p[11]); 711 712 nxt_field_end_test_char(p[12]); 713 nxt_field_end_test_char(p[13]); 714 nxt_field_end_test_char(p[14]); 715 nxt_field_end_test_char(p[15]); 716 717 p += 16; 718 } 719 720 while (nxt_fast_path(end - p >= 4)) { 721 722 nxt_field_end_test_char(p[0]); 723 nxt_field_end_test_char(p[1]); 724 nxt_field_end_test_char(p[2]); 725 nxt_field_end_test_char(p[3]); 726 727 p += 4; 728 } 729 730 switch (end - p) { 731 case 3: 732 nxt_field_end_test_char(*p); p++; 733 /* Fall through. */ 734 case 2: 735 nxt_field_end_test_char(*p); p++; 736 /* Fall through. */ 737 case 1: 738 nxt_field_end_test_char(*p); p++; 739 /* Fall through. */ 740 case 0: 741 break; 742 default: 743 nxt_unreachable(); 744 } 745 746 return p; 747 } 748 749 750 static nxt_int_t 751 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos, 752 u_char *end) 753 { 754 u_char *p; 755 nxt_http_field_t *field; 756 757 p = *pos; 758 759 if (nxt_fast_path(*p == '\r')) { 760 p++; 761 762 if (nxt_slow_path(p == end)) { 763 rp->handler = &nxt_http_parse_field_end; 764 return NXT_AGAIN; 765 } 766 } 767 768 if (nxt_fast_path(*p == '\n')) { 769 *pos = p + 1; 770 771 if (rp->field_name.length != 0) { 772 field = nxt_list_add(rp->fields); 773 774 if (nxt_slow_path(field == NULL)) { 775 return NXT_ERROR; 776 } 777 778 field->hash = nxt_http_field_hash_end(rp->field_hash); 779 field->skip = 0; 780 781 field->name_length = rp->field_name.length; 782 field->value_length = rp->field_value.length; 783 field->name = rp->field_name.start; 784 field->value = rp->field_value.start; 785 786 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT; 787 788 rp->field_name.length = 0; 789 rp->field_value.length = 0; 790 791 rp->handler = &nxt_http_parse_field_name; 792 return NXT_OK; 793 } 794 795 return NXT_DONE; 796 } 797 798 return NXT_HTTP_PARSE_INVALID; 799 } 800 801 802 #define \ 803 nxt_http_is_normal(c) \ 804 (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0)) 805 806 807 static const uint8_t nxt_http_normal[32] nxt_aligned(32) = { 808 809 /* \0 \r \n */ 810 0xfe, 0xdb, 0xff, 0xff, /* 1111 1110 1101 1011 1111 1111 1111 1111 */ 811 812 /* '&%$ #"! /.-, |*)( 7654 3210 ?>=< ;:98 */ 813 0xd6, 0x37, 0xff, 0x7f, /* 1101 0110 0011 0111 1111 1111 0111 1111 */ 814 815 /* GFED CBA@ ONML KJIH WVUT SRQP _^]\ [ZYX */ 816 0xff, 0xff, 0xff, 0xff, /* 1111 1111 1111 1111 1111 1111 1111 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 0xff, 0xff, 0xff, 0xff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 822 0xff, 0xff, 0xff, 0xff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 823 0xff, 0xff, 0xff, 0xff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 824 0xff, 0xff, 0xff, 0xff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ 825 }; 826 827 828 static nxt_int_t 829 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp) 830 { 831 u_char *p, *u, c, ch, high; 832 enum { 833 sw_normal = 0, 834 sw_slash, 835 sw_dot, 836 sw_dot_dot, 837 sw_quoted, 838 sw_quoted_second, 839 } state, saved_state; 840 841 nxt_prefetch(nxt_http_normal); 842 843 state = sw_normal; 844 saved_state = sw_normal; 845 p = rp->target_start; 846 847 u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1); 848 849 if (nxt_slow_path(u == NULL)) { 850 return NXT_ERROR; 851 } 852 853 rp->path.length = 0; 854 rp->path.start = u; 855 856 high = '\0'; 857 rp->exten_start = NULL; 858 rp->args_start = NULL; 859 860 while (p < rp->target_end) { 861 862 ch = *p++; 863 864 again: 865 866 switch (state) { 867 868 case sw_normal: 869 870 if (nxt_http_is_normal(ch)) { 871 *u++ = ch; 872 continue; 873 } 874 875 switch (ch) { 876 case '/': 877 rp->exten_start = NULL; 878 state = sw_slash; 879 *u++ = ch; 880 continue; 881 case '%': 882 saved_state = state; 883 state = sw_quoted; 884 continue; 885 case '?': 886 rp->args_start = p; 887 goto args; 888 case '#': 889 goto done; 890 case '.': 891 rp->exten_start = u + 1; 892 *u++ = ch; 893 continue; 894 case '+': 895 rp->plus_in_target = 1; 896 /* Fall through. */ 897 default: 898 *u++ = ch; 899 continue; 900 } 901 902 break; 903 904 case sw_slash: 905 906 if (nxt_http_is_normal(ch)) { 907 state = sw_normal; 908 *u++ = ch; 909 continue; 910 } 911 912 switch (ch) { 913 case '/': 914 continue; 915 case '.': 916 state = sw_dot; 917 *u++ = ch; 918 continue; 919 case '%': 920 saved_state = state; 921 state = sw_quoted; 922 continue; 923 case '?': 924 rp->args_start = p; 925 goto args; 926 case '#': 927 goto done; 928 case '+': 929 rp->plus_in_target = 1; 930 /* Fall through. */ 931 default: 932 state = sw_normal; 933 *u++ = ch; 934 continue; 935 } 936 937 break; 938 939 case sw_dot: 940 941 if (nxt_http_is_normal(ch)) { 942 state = sw_normal; 943 *u++ = ch; 944 continue; 945 } 946 947 switch (ch) { 948 case '/': 949 state = sw_slash; 950 u--; 951 continue; 952 case '.': 953 state = sw_dot_dot; 954 *u++ = ch; 955 continue; 956 case '%': 957 saved_state = state; 958 state = sw_quoted; 959 continue; 960 case '?': 961 rp->args_start = p; 962 goto args; 963 case '#': 964 goto done; 965 case '+': 966 rp->plus_in_target = 1; 967 /* Fall through. */ 968 default: 969 state = sw_normal; 970 *u++ = ch; 971 continue; 972 } 973 974 break; 975 976 case sw_dot_dot: 977 978 if (nxt_http_is_normal(ch)) { 979 state = sw_normal; 980 *u++ = ch; 981 continue; 982 } 983 984 switch (ch) { 985 case '/': 986 state = sw_slash; 987 u -= 5; 988 for ( ;; ) { 989 if (u < rp->path.start) { 990 return NXT_HTTP_PARSE_INVALID; 991 } 992 if (*u == '/') { 993 u++; 994 break; 995 } 996 u--; 997 } 998 break; 999 1000 case '%': 1001 saved_state = state; 1002 state = sw_quoted; 1003 continue; 1004 case '?': 1005 rp->args_start = p; 1006 goto args; 1007 case '#': 1008 goto done; 1009 case '+': 1010 rp->plus_in_target = 1; 1011 /* Fall through. */ 1012 default: 1013 state = sw_normal; 1014 *u++ = ch; 1015 continue; 1016 } 1017 1018 break; 1019 1020 case sw_quoted: 1021 rp->quoted_target = 1; 1022 1023 if (ch >= '0' && ch <= '9') { 1024 high = (u_char) (ch - '0'); 1025 state = sw_quoted_second; 1026 continue; 1027 } 1028 1029 c = (u_char) (ch | 0x20); 1030 if (c >= 'a' && c <= 'f') { 1031 high = (u_char) (c - 'a' + 10); 1032 state = sw_quoted_second; 1033 continue; 1034 } 1035 1036 return NXT_HTTP_PARSE_INVALID; 1037 1038 case sw_quoted_second: 1039 if (ch >= '0' && ch <= '9') { 1040 ch = (u_char) ((high << 4) + ch - '0'); 1041 1042 if (ch == '%' || ch == '#') { 1043 state = sw_normal; 1044 *u++ = ch; 1045 continue; 1046 1047 } else if (ch == '\0') { 1048 return NXT_HTTP_PARSE_INVALID; 1049 } 1050 1051 state = saved_state; 1052 goto again; 1053 } 1054 1055 c = (u_char) (ch | 0x20); 1056 if (c >= 'a' && c <= 'f') { 1057 ch = (u_char) ((high << 4) + c - 'a' + 10); 1058 1059 if (ch == '?') { 1060 state = sw_normal; 1061 *u++ = ch; 1062 continue; 1063 1064 } else if (ch == '+') { 1065 rp->plus_in_target = 1; 1066 } 1067 1068 state = saved_state; 1069 goto again; 1070 } 1071 1072 return NXT_HTTP_PARSE_INVALID; 1073 } 1074 } 1075 1076 if (state >= sw_quoted) { 1077 return NXT_HTTP_PARSE_INVALID; 1078 } 1079 1080 args: 1081 1082 for (/* void */; p < rp->target_end; p++) { 1083 if (*p == '#') { 1084 break; 1085 } 1086 } 1087 1088 if (rp->args_start != NULL) { 1089 rp->args.length = p - rp->args_start; 1090 rp->args.start = rp->args_start; 1091 } 1092 1093 done: 1094 1095 rp->path.length = u - rp->path.start; 1096 1097 if (rp->exten_start) { 1098 rp->exten.length = u - rp->exten_start; 1099 rp->exten.start = rp->exten_start; 1100 } 1101 1102 return NXT_OK; 1103 } 1104 1105 1106 static const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = { 1107 NXT_LVLHSH_BUCKET_SIZE(64), 1108 { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 }, 1109 nxt_http_field_hash_test, 1110 nxt_http_field_hash_alloc, 1111 nxt_http_field_hash_free, 1112 }; 1113 1114 1115 static nxt_int_t 1116 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data) 1117 { 1118 nxt_http_field_proc_t *field; 1119 1120 field = data; 1121 1122 if (nxt_strcasestr_eq(&lhq->key, &field->name)) { 1123 return NXT_OK; 1124 } 1125 1126 return NXT_DECLINED; 1127 } 1128 1129 1130 static void * 1131 nxt_http_field_hash_alloc(void *pool, size_t size) 1132 { 1133 return nxt_mp_align(pool, size, size); 1134 } 1135 1136 1137 static void 1138 nxt_http_field_hash_free(void *pool, void *p) 1139 { 1140 nxt_mp_free(pool, p); 1141 } 1142 1143 1144 static nxt_int_t 1145 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data) 1146 { 1147 return NXT_OK; 1148 } 1149 1150 1151 nxt_int_t 1152 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1153 nxt_http_field_proc_t items[], nxt_uint_t count) 1154 { 1155 u_char ch; 1156 uint32_t key; 1157 nxt_str_t *name; 1158 nxt_int_t ret; 1159 nxt_uint_t i, j; 1160 nxt_lvlhsh_query_t lhq; 1161 1162 lhq.replace = 0; 1163 lhq.proto = &nxt_http_fields_hash_proto; 1164 lhq.pool = mp; 1165 1166 for (i = 0; i < count; i++) { 1167 key = NXT_HTTP_FIELD_HASH_INIT; 1168 name = &items[i].name; 1169 1170 for (j = 0; j < name->length; j++) { 1171 ch = nxt_lowcase(name->start[j]); 1172 key = nxt_http_field_hash_char(key, ch); 1173 } 1174 1175 lhq.key_hash = nxt_http_field_hash_end(key) & 0xffff; 1176 lhq.key = *name; 1177 lhq.value = &items[i]; 1178 1179 ret = nxt_lvlhsh_insert(hash, &lhq); 1180 1181 if (nxt_slow_path(ret != NXT_OK)) { 1182 return NXT_ERROR; 1183 } 1184 } 1185 1186 return NXT_OK; 1187 } 1188 1189 1190 nxt_uint_t 1191 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp, 1192 nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level) 1193 { 1194 u_char ch; 1195 uint32_t key, mask; 1196 nxt_str_t *name; 1197 nxt_uint_t colls, i, j; 1198 nxt_lvlhsh_proto_t proto; 1199 nxt_lvlhsh_query_t lhq; 1200 1201 proto = nxt_http_fields_hash_proto; 1202 proto.test = nxt_http_field_hash_collision; 1203 1204 lhq.replace = 0; 1205 lhq.proto = &proto; 1206 lhq.pool = mp; 1207 1208 mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xffff; 1209 1210 colls = 0; 1211 1212 for (i = 0; i < count; i++) { 1213 key = NXT_HTTP_FIELD_HASH_INIT; 1214 name = &items[i].name; 1215 1216 for (j = 0; j < name->length; j++) { 1217 ch = nxt_lowcase(name->start[j]); 1218 key = nxt_http_field_hash_char(key, ch); 1219 } 1220 1221 lhq.key_hash = nxt_http_field_hash_end(key) & mask; 1222 lhq.value = &items[i]; 1223 1224 if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) { 1225 colls++; 1226 } 1227 } 1228 1229 return colls; 1230 } 1231 1232 1233 nxt_int_t 1234 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx) 1235 { 1236 nxt_int_t ret; 1237 nxt_http_field_t *field; 1238 nxt_lvlhsh_query_t lhq; 1239 nxt_http_field_proc_t *proc; 1240 1241 lhq.proto = &nxt_http_fields_hash_proto; 1242 1243 nxt_list_each(field, fields) { 1244 1245 lhq.key_hash = field->hash; 1246 lhq.key.length = field->name_length; 1247 lhq.key.start = field->name; 1248 1249 if (nxt_lvlhsh_find(hash, &lhq) != NXT_OK) { 1250 continue; 1251 } 1252 1253 proc = lhq.value; 1254 1255 ret = proc->handler(ctx, field, proc->data); 1256 1257 if (nxt_slow_path(ret != NXT_OK)) { 1258 return ret; 1259 } 1260 1261 } nxt_list_loop; 1262 1263 return NXT_OK; 1264 } 1265