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