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