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