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