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