xref: /unit/src/nxt_http_parse.c (revision 704:1fcac04f0a15)
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