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