xref: /unit/src/nxt_http_parse.c (revision 1214:c3666b232602)
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 
38 typedef enum {
39     NXT_HTTP_TARGET_SPACE = 1,   /* \s  */
40     NXT_HTTP_TARGET_HASH,        /*  #  */
41     NXT_HTTP_TARGET_AGAIN,
42     NXT_HTTP_TARGET_BAD,         /* \0\r\n */
43 
44     /* traps below are used for extended check only */
45 
46     NXT_HTTP_TARGET_SLASH = 5,   /*  /  */
47     NXT_HTTP_TARGET_DOT,         /*  .  */
48     NXT_HTTP_TARGET_ARGS_MARK,   /*  ?  */
49     NXT_HTTP_TARGET_QUOTE_MARK,  /*  %  */
50 } nxt_http_target_traps_e;
51 
52 
53 static const uint8_t  nxt_http_target_chars[256] nxt_aligned(64) = {
54     /* \0                               \n        \r       */
55         4, 0, 0, 0,  0, 0, 0, 0,   0, 0, 4, 0,  0, 4, 0, 0,
56         0, 0, 0, 0,  0, 0, 0, 0,   0, 0, 0, 0,  0, 0, 0, 0,
57 
58     /* \s  !  "  #   $  %  &  '    (  )  *  +   ,  -  .  / */
59         1, 0, 0, 2,  0, 8, 0, 0,   0, 0, 0, 0,  0, 0, 6, 5,
60 
61     /*  0  1  2  3   4  5  6  7    8  9  :  ;   <  =  >  ? */
62         0, 0, 0, 0,  0, 0, 0, 0,   0, 0, 0, 0,  0, 0, 0, 7,
63 };
64 
65 
66 nxt_inline nxt_http_target_traps_e
67 nxt_http_parse_target(u_char **pos, u_char *end)
68 {
69     u_char      *p;
70     nxt_uint_t  trap;
71 
72     p = *pos;
73 
74     while (nxt_fast_path(end - p >= 10)) {
75 
76 #define nxt_target_test_char(ch)                                              \
77                                                                               \
78         trap = nxt_http_target_chars[ch];                                     \
79                                                                               \
80         if (nxt_slow_path(trap != 0)) {                                       \
81             *pos = &(ch);                                                     \
82             return trap;                                                      \
83         }
84 
85 /* enddef */
86 
87         nxt_target_test_char(p[0]);
88         nxt_target_test_char(p[1]);
89         nxt_target_test_char(p[2]);
90         nxt_target_test_char(p[3]);
91 
92         nxt_target_test_char(p[4]);
93         nxt_target_test_char(p[5]);
94         nxt_target_test_char(p[6]);
95         nxt_target_test_char(p[7]);
96 
97         nxt_target_test_char(p[8]);
98         nxt_target_test_char(p[9]);
99 
100         p += 10;
101     }
102 
103     while (p != end) {
104         nxt_target_test_char(*p); p++;
105     }
106 
107     return NXT_HTTP_TARGET_AGAIN;
108 }
109 
110 
111 nxt_int_t
112 nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp)
113 {
114     rp->mem_pool = mp;
115 
116     rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t));
117     if (nxt_slow_path(rp->fields == NULL)) {
118         return NXT_ERROR;
119     }
120 
121     rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
122 
123     return NXT_OK;
124 }
125 
126 
127 nxt_int_t
128 nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
129 {
130     nxt_int_t  rc;
131 
132     if (rp->handler == NULL) {
133         rp->handler = &nxt_http_parse_request_line;
134     }
135 
136     do {
137         rc = rp->handler(rp, &b->pos, b->free);
138     } while (rc == NXT_OK);
139 
140     return rc;
141 }
142 
143 
144 nxt_int_t
145 nxt_http_parse_fields(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
146 {
147     nxt_int_t  rc;
148 
149     if (rp->handler == NULL) {
150         rp->handler = &nxt_http_parse_field_name;
151     }
152 
153     do {
154         rc = rp->handler(rp, &b->pos, b->free);
155     } while (rc == NXT_OK);
156 
157     return rc;
158 }
159 
160 
161 static nxt_int_t
162 nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
163     u_char *end)
164 {
165     u_char                   *p, ch, *after_slash, *args;
166     nxt_int_t                rc;
167     nxt_bool_t               rest;
168     nxt_http_ver_t           ver;
169     nxt_http_target_traps_e  trap;
170 
171     static const nxt_http_ver_t  http11 = { "HTTP/1.1" };
172     static const nxt_http_ver_t  http10 = { "HTTP/1.0" };
173 
174     p = *pos;
175 
176     rp->method.start = p;
177 
178     for ( ;; ) {
179 
180         while (nxt_fast_path(end - p >= 8)) {
181 
182 #define nxt_method_test_char(ch)                                              \
183                                                                               \
184             if (nxt_slow_path((ch) < 'A' || (ch) > 'Z')) {                    \
185                 p = &(ch);                                                    \
186                 goto method_unusual_char;                                     \
187             }
188 
189 /* enddef */
190 
191             nxt_method_test_char(p[0]);
192             nxt_method_test_char(p[1]);
193             nxt_method_test_char(p[2]);
194             nxt_method_test_char(p[3]);
195 
196             nxt_method_test_char(p[4]);
197             nxt_method_test_char(p[5]);
198             nxt_method_test_char(p[6]);
199             nxt_method_test_char(p[7]);
200 
201             p += 8;
202         }
203 
204         while (p != end) {
205             nxt_method_test_char(*p); p++;
206         }
207 
208         rp->method.length = p - rp->method.start;
209 
210         return NXT_AGAIN;
211 
212     method_unusual_char:
213 
214         ch = *p;
215 
216         if (nxt_fast_path(ch == ' ')) {
217             rp->method.length = p - rp->method.start;
218             break;
219         }
220 
221         if (ch == '_' || ch == '-') {
222             p++;
223             continue;
224         }
225 
226         if (rp->method.start == p && (ch == '\r' || ch == '\n')) {
227             rp->method.start++;
228             p++;
229             continue;
230         }
231 
232         rp->method.length = p - rp->method.start;
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     args = NULL;
259     rest = 0;
260 
261 continue_target:
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             continue;
277 
278         case NXT_HTTP_TARGET_DOT:
279             if (nxt_slow_path(after_slash == p)) {
280                 rp->complex_target = 1;
281                 goto rest_of_target;
282             }
283 
284             continue;
285 
286         case NXT_HTTP_TARGET_ARGS_MARK:
287             args = p + 1;
288             goto rest_of_target;
289 
290         case NXT_HTTP_TARGET_SPACE:
291             rp->target_end = p;
292             goto space_after_target;
293 
294         case NXT_HTTP_TARGET_QUOTE_MARK:
295             rp->quoted_target = 1;
296             goto rest_of_target;
297 
298         case NXT_HTTP_TARGET_HASH:
299             rp->complex_target = 1;
300             goto rest_of_target;
301 
302         case NXT_HTTP_TARGET_AGAIN:
303             rp->target_end = p;
304             return NXT_AGAIN;
305 
306         case NXT_HTTP_TARGET_BAD:
307             rp->target_end = p;
308             return NXT_HTTP_PARSE_INVALID;
309         }
310 
311         nxt_unreachable();
312     }
313 
314 rest_of_target:
315 
316     rest = 1;
317 
318     for ( ;; ) {
319         p++;
320 
321         trap = nxt_http_parse_target(&p, end);
322 
323         switch (trap) {
324         case NXT_HTTP_TARGET_SPACE:
325             rp->target_end = p;
326             goto space_after_target;
327 
328         case NXT_HTTP_TARGET_HASH:
329             rp->complex_target = 1;
330             continue;
331 
332         case NXT_HTTP_TARGET_AGAIN:
333             rp->target_end = p;
334             return NXT_AGAIN;
335 
336         case NXT_HTTP_TARGET_BAD:
337             rp->target_end = p;
338             return NXT_HTTP_PARSE_INVALID;
339 
340         default:
341             continue;
342         }
343 
344         nxt_unreachable();
345     }
346 
347 space_after_target:
348 
349     if (nxt_slow_path(end - p < 10)) {
350 
351         do {
352             p++;
353 
354             if (p == end) {
355                 return NXT_AGAIN;
356             }
357 
358         } while (*p == ' ');
359 
360         if (nxt_memcmp(p, "HTTP/", nxt_min(end - p, 5)) == 0) {
361 
362             switch (end - p) {
363             case 8:
364                 if (p[7] < '0' || p[7] > '9') {
365                     break;
366                 }
367                 /* Fall through. */
368             case 7:
369                 if (p[6] != '.') {
370                     break;
371                 }
372                 /* Fall through. */
373             case 6:
374                 if (p[5] < '0' || p[5] > '9') {
375                     break;
376                 }
377                 /* Fall through. */
378             default:
379                 return NXT_AGAIN;
380             }
381         }
382 
383         rp->space_in_target = 1;
384 
385         if (rest) {
386             goto rest_of_target;
387         }
388 
389         goto continue_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 
404         if (rest) {
405             goto rest_of_target;
406         }
407 
408         goto continue_target;
409     }
410 
411     nxt_memcpy(ver.str, &p[1], 8);
412 
413     if (nxt_fast_path(ver.ui64 == http11.ui64
414                       || ver.ui64 == http10.ui64
415                       || (nxt_memcmp(ver.str, "HTTP/1.", 7) == 0
416                           && ver.s.minor >= '0' && ver.s.minor <= '9')))
417     {
418         rp->version.ui64 = ver.ui64;
419 
420         if (nxt_fast_path(p[9] == '\r')) {
421             p += 10;
422 
423             if (nxt_slow_path(p == end)) {
424                 return NXT_AGAIN;
425             }
426 
427             if (nxt_slow_path(*p != '\n')) {
428                 return NXT_HTTP_PARSE_INVALID;
429             }
430 
431             *pos = p + 1;
432 
433         } else {
434             *pos = p + 10;
435         }
436 
437         if (rp->complex_target != 0 || rp->quoted_target != 0) {
438             rc = nxt_http_parse_complex_target(rp);
439 
440             if (nxt_slow_path(rc != NXT_OK)) {
441                 return rc;
442             }
443 
444             return nxt_http_parse_field_name(rp, pos, end);
445         }
446 
447         rp->path.start = rp->target_start;
448 
449         if (args != NULL) {
450             rp->path.length = args - rp->target_start - 1;
451 
452             rp->args.length = rp->target_end - args;
453             rp->args.start = args;
454 
455         } else {
456             rp->path.length = rp->target_end - rp->target_start;
457         }
458 
459         return nxt_http_parse_field_name(rp, pos, end);
460     }
461 
462     if (nxt_memcmp(ver.s.prefix, "HTTP/", 5) == 0
463         && ver.s.major >= '0' && ver.s.major <= '9'
464         && ver.s.point == '.'
465         && ver.s.minor >= '0' && ver.s.minor <= '9')
466     {
467         rp->version.ui64 = ver.ui64;
468         return NXT_HTTP_PARSE_UNSUPPORTED_VERSION;
469     }
470 
471     return NXT_HTTP_PARSE_INVALID;
472 }
473 
474 
475 static nxt_int_t
476 nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos,
477     u_char *end)
478 {
479     u_char  *p, ch;
480 
481     p = *pos;
482 
483     ch = *p;
484 
485     if (ch == ' ') {
486         /* skip surplus spaces before target */
487 
488         do {
489             p++;
490 
491             if (nxt_slow_path(p == end)) {
492                 return NXT_AGAIN;
493             }
494 
495             ch = *p;
496 
497         } while (ch == ' ');
498 
499         if (ch == '/') {
500             *pos = p;
501             return NXT_OK;
502         }
503     }
504 
505     /* absolute path or '*' */
506 
507     /* TODO */
508 
509     return NXT_HTTP_PARSE_INVALID;
510 }
511 
512 
513 static nxt_int_t
514 nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
515     u_char *end)
516 {
517     u_char    *p, c;
518     size_t    len;
519     uint32_t  hash;
520 
521     static const u_char  normal[256]  nxt_aligned(64) =
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" "0123456789\0\0\0\0\0\0"
524 
525         /* These 64 bytes should reside in one cache line. */
526         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0_"
527         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
528 
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         "\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 
534     p = *pos + rp->field_name.length;
535     hash = rp->field_hash;
536 
537     while (nxt_fast_path(end - p >= 8)) {
538 
539 #define nxt_field_name_test_char(ch)                                          \
540                                                                               \
541         c = normal[ch];                                                       \
542                                                                               \
543         if (nxt_slow_path(c == '\0')) {                                       \
544             p = &(ch);                                                        \
545             goto name_end;                                                    \
546         }                                                                     \
547                                                                               \
548         hash = nxt_http_field_hash_char(hash, c);
549 
550 /* enddef */
551 
552         nxt_field_name_test_char(p[0]);
553         nxt_field_name_test_char(p[1]);
554         nxt_field_name_test_char(p[2]);
555         nxt_field_name_test_char(p[3]);
556 
557         nxt_field_name_test_char(p[4]);
558         nxt_field_name_test_char(p[5]);
559         nxt_field_name_test_char(p[6]);
560         nxt_field_name_test_char(p[7]);
561 
562         p += 8;
563     }
564 
565     while (nxt_fast_path(p != end)) {
566         nxt_field_name_test_char(*p); p++;
567     }
568 
569     len = p - *pos;
570 
571     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
572         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
573     }
574 
575     rp->field_hash = hash;
576     rp->field_name.length = len;
577 
578     rp->handler = &nxt_http_parse_field_name;
579 
580     return NXT_AGAIN;
581 
582 name_end:
583 
584     if (nxt_fast_path(*p == ':')) {
585         if (nxt_slow_path(p == *pos)) {
586             return NXT_HTTP_PARSE_INVALID;
587         }
588 
589         len = p - *pos;
590 
591         if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
592             return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
593         }
594 
595         rp->field_hash = hash;
596 
597         rp->field_name.length = len;
598         rp->field_name.start = *pos;
599 
600         *pos = p + 1;
601 
602         return nxt_http_parse_field_value(rp, pos, end);
603     }
604 
605     if (nxt_slow_path(p != *pos)) {
606         return NXT_HTTP_PARSE_INVALID;
607     }
608 
609     return nxt_http_parse_field_end(rp, pos, end);
610 }
611 
612 
613 static nxt_int_t
614 nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
615     u_char *end)
616 {
617     u_char  *p, *start, ch;
618     size_t  len;
619 
620     p = *pos;
621 
622     for ( ;; ) {
623         if (nxt_slow_path(p == end)) {
624             *pos = p;
625             rp->handler = &nxt_http_parse_field_value;
626             return NXT_AGAIN;
627         }
628 
629         ch = *p;
630 
631         if (ch != ' ' && ch != '\t') {
632             break;
633         }
634 
635         p++;
636     }
637 
638     start = p;
639 
640     p += rp->field_value.length;
641 
642     for ( ;; ) {
643         p = nxt_http_lookup_field_end(p, end);
644 
645         if (nxt_slow_path(p == end)) {
646             *pos = start;
647 
648             len = p - start;
649 
650             if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
651                 return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
652             }
653 
654             rp->field_value.length = len;
655             rp->handler = &nxt_http_parse_field_value;
656             return NXT_AGAIN;
657         }
658 
659         ch = *p;
660 
661         if (nxt_fast_path(ch == '\r' || ch == '\n')) {
662             break;
663         }
664 
665         if (ch != '\t') {
666             return NXT_HTTP_PARSE_INVALID;
667         }
668 
669         p++;
670     }
671 
672     *pos = p;
673 
674     if (nxt_fast_path(p != start)) {
675 
676         while (p[-1] == ' ' || p[-1] == '\t') {
677             p--;
678         }
679     }
680 
681     len = p - start;
682 
683     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
684         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
685     }
686 
687     rp->field_value.length = len;
688     rp->field_value.start = start;
689 
690     return nxt_http_parse_field_end(rp, pos, end);
691 }
692 
693 
694 static u_char *
695 nxt_http_lookup_field_end(u_char *p, u_char *end)
696 {
697     while (nxt_fast_path(end - p >= 16)) {
698 
699 #define nxt_field_end_test_char(ch)                                           \
700                                                                               \
701         if (nxt_slow_path((ch) < 0x20)) {                                     \
702             return &(ch);                                                     \
703         }
704 
705 /* enddef */
706 
707         nxt_field_end_test_char(p[0]);
708         nxt_field_end_test_char(p[1]);
709         nxt_field_end_test_char(p[2]);
710         nxt_field_end_test_char(p[3]);
711 
712         nxt_field_end_test_char(p[4]);
713         nxt_field_end_test_char(p[5]);
714         nxt_field_end_test_char(p[6]);
715         nxt_field_end_test_char(p[7]);
716 
717         nxt_field_end_test_char(p[8]);
718         nxt_field_end_test_char(p[9]);
719         nxt_field_end_test_char(p[10]);
720         nxt_field_end_test_char(p[11]);
721 
722         nxt_field_end_test_char(p[12]);
723         nxt_field_end_test_char(p[13]);
724         nxt_field_end_test_char(p[14]);
725         nxt_field_end_test_char(p[15]);
726 
727         p += 16;
728     }
729 
730     while (nxt_fast_path(end - p >= 4)) {
731 
732         nxt_field_end_test_char(p[0]);
733         nxt_field_end_test_char(p[1]);
734         nxt_field_end_test_char(p[2]);
735         nxt_field_end_test_char(p[3]);
736 
737         p += 4;
738     }
739 
740     switch (end - p) {
741     case 3:
742         nxt_field_end_test_char(*p); p++;
743         /* Fall through. */
744     case 2:
745         nxt_field_end_test_char(*p); p++;
746         /* Fall through. */
747     case 1:
748         nxt_field_end_test_char(*p); p++;
749         /* Fall through. */
750     case 0:
751         break;
752     default:
753         nxt_unreachable();
754     }
755 
756     return p;
757 }
758 
759 
760 static nxt_int_t
761 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos,
762     u_char *end)
763 {
764     u_char            *p;
765     nxt_http_field_t  *field;
766 
767     p = *pos;
768 
769     if (nxt_fast_path(*p == '\r')) {
770         p++;
771 
772         if (nxt_slow_path(p == end)) {
773             rp->handler = &nxt_http_parse_field_end;
774             return NXT_AGAIN;
775         }
776     }
777 
778     if (nxt_fast_path(*p == '\n')) {
779         *pos = p + 1;
780 
781         if (rp->field_name.length != 0) {
782             field = nxt_list_add(rp->fields);
783 
784             if (nxt_slow_path(field == NULL)) {
785                 return NXT_ERROR;
786             }
787 
788             field->hash = nxt_http_field_hash_end(rp->field_hash);
789             field->skip = 0;
790 
791             field->name_length = rp->field_name.length;
792             field->value_length = rp->field_value.length;
793             field->name = rp->field_name.start;
794             field->value = rp->field_value.start;
795 
796             rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
797 
798             rp->field_name.length = 0;
799             rp->field_value.length = 0;
800 
801             rp->handler = &nxt_http_parse_field_name;
802             return NXT_OK;
803         }
804 
805         return NXT_DONE;
806     }
807 
808     return NXT_HTTP_PARSE_INVALID;
809 }
810 
811 
812 #define                                                                       \
813 nxt_http_is_normal(c)                                                         \
814     (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
815 
816 
817 static const uint8_t  nxt_http_normal[32]  nxt_aligned(32) = {
818 
819                              /*        \0   \r  \n                         */
820     0xFE, 0xDB, 0xFF, 0xFF,  /* 1111 1110  1101 1011  1111 1111  1111 1111 */
821 
822                              /* '&%$ #"!   /.-, |*)(  7654 3210  ?>=< ;:98 */
823     0xD6, 0x37, 0xFF, 0x7F,  /* 1101 0110  0011 0111  1111 1111  0111 1111 */
824 
825                              /* GFED CBA@  ONML KJIH  WVUT SRQP  _^]\ [ZYX */
826     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
827 
828                              /* gfed cba`  onml kjih  wvut srqp   ~}| {zyx */
829     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
830 
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     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 };
836 
837 
838 static nxt_int_t
839 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp)
840 {
841     u_char  *p, *u, c, ch, high, *args;
842 
843     enum {
844         sw_normal = 0,
845         sw_slash,
846         sw_dot,
847         sw_dot_dot,
848         sw_quoted,
849         sw_quoted_second,
850     } state, saved_state;
851 
852     nxt_prefetch(nxt_http_normal);
853 
854     state = sw_normal;
855     saved_state = sw_normal;
856     p = rp->target_start;
857 
858     u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1);
859     if (nxt_slow_path(u == NULL)) {
860         return NXT_ERROR;
861     }
862 
863     rp->path.length = 0;
864     rp->path.start = u;
865 
866     high = '\0';
867     args = NULL;
868 
869     while (p < rp->target_end) {
870 
871         ch = *p++;
872 
873     again:
874 
875         switch (state) {
876 
877         case sw_normal:
878 
879             if (nxt_http_is_normal(ch)) {
880                 *u++ = ch;
881                 continue;
882             }
883 
884             switch (ch) {
885             case '/':
886                 state = sw_slash;
887                 *u++ = ch;
888                 continue;
889             case '%':
890                 saved_state = state;
891                 state = sw_quoted;
892                 continue;
893             case '?':
894                 args = p;
895                 goto args;
896             case '#':
897                 goto done;
898             default:
899                 *u++ = ch;
900                 continue;
901             }
902 
903             break;
904 
905         case sw_slash:
906 
907             if (nxt_http_is_normal(ch)) {
908                 state = sw_normal;
909                 *u++ = ch;
910                 continue;
911             }
912 
913             switch (ch) {
914             case '/':
915                 continue;
916             case '.':
917                 state = sw_dot;
918                 *u++ = ch;
919                 continue;
920             case '%':
921                 saved_state = state;
922                 state = sw_quoted;
923                 continue;
924             case '?':
925                 args = p;
926                 goto args;
927             case '#':
928                 goto done;
929             default:
930                 state = sw_normal;
931                 *u++ = ch;
932                 continue;
933             }
934 
935             break;
936 
937         case sw_dot:
938 
939             if (nxt_http_is_normal(ch)) {
940                 state = sw_normal;
941                 *u++ = ch;
942                 continue;
943             }
944 
945             switch (ch) {
946             case '/':
947                 state = sw_slash;
948                 u--;
949                 continue;
950             case '.':
951                 state = sw_dot_dot;
952                 *u++ = ch;
953                 continue;
954             case '%':
955                 saved_state = state;
956                 state = sw_quoted;
957                 continue;
958             case '?':
959                 u--;
960                 args = p;
961                 goto args;
962             case '#':
963                 u--;
964                 goto done;
965             default:
966                 state = sw_normal;
967                 *u++ = ch;
968                 continue;
969             }
970 
971             break;
972 
973         case sw_dot_dot:
974 
975             if (nxt_http_is_normal(ch)) {
976                 state = sw_normal;
977                 *u++ = ch;
978                 continue;
979             }
980 
981             switch (ch) {
982 
983             case '/':
984             case '?':
985             case '#':
986                 u -= 5;
987 
988                 for ( ;; ) {
989                     if (u < rp->path.start) {
990                         return NXT_HTTP_PARSE_INVALID;
991                     }
992 
993                     if (*u == '/') {
994                         u++;
995                         break;
996                     }
997 
998                     u--;
999                 }
1000 
1001                 if (ch == '?') {
1002                     args = p;
1003                     goto args;
1004                 }
1005 
1006                 if (ch == '#') {
1007                     goto done;
1008                 }
1009 
1010                 state = sw_slash;
1011                 break;
1012 
1013             case '%':
1014                 saved_state = state;
1015                 state = sw_quoted;
1016                 continue;
1017 
1018             default:
1019                 state = sw_normal;
1020                 *u++ = ch;
1021                 continue;
1022             }
1023 
1024             break;
1025 
1026         case sw_quoted:
1027             rp->quoted_target = 1;
1028 
1029             if (ch >= '0' && ch <= '9') {
1030                 high = (u_char) (ch - '0');
1031                 state = sw_quoted_second;
1032                 continue;
1033             }
1034 
1035             c = (u_char) (ch | 0x20);
1036             if (c >= 'a' && c <= 'f') {
1037                 high = (u_char) (c - 'a' + 10);
1038                 state = sw_quoted_second;
1039                 continue;
1040             }
1041 
1042             return NXT_HTTP_PARSE_INVALID;
1043 
1044         case sw_quoted_second:
1045             if (ch >= '0' && ch <= '9') {
1046                 ch = (u_char) ((high << 4) + ch - '0');
1047 
1048                 if (ch == '%') {
1049                     state = sw_normal;
1050                     *u++ = '%';
1051 
1052                     if (rp->encoded_slashes) {
1053                         *u++ = '2';
1054                         *u++ = '5';
1055                     }
1056 
1057                     continue;
1058                 }
1059 
1060                 if (ch == '#') {
1061                     state = sw_normal;
1062                     *u++ = '#';
1063                     continue;
1064                 }
1065 
1066                 if (ch == '\0') {
1067                     return NXT_HTTP_PARSE_INVALID;
1068                 }
1069 
1070                 state = saved_state;
1071                 goto again;
1072             }
1073 
1074             c = (u_char) (ch | 0x20);
1075             if (c >= 'a' && c <= 'f') {
1076                 ch = (u_char) ((high << 4) + c - 'a' + 10);
1077 
1078                 if (ch == '?') {
1079                     state = sw_normal;
1080                     *u++ = ch;
1081                     continue;
1082                 }
1083 
1084                 if (ch == '/' && rp->encoded_slashes) {
1085                     state = sw_normal;
1086                     *u++ = '%';
1087                     *u++ = '2';
1088                     *u++ = p[-1];  /* 'f' or 'F' */
1089                     continue;
1090                 }
1091 
1092                 state = saved_state;
1093                 goto again;
1094             }
1095 
1096             return NXT_HTTP_PARSE_INVALID;
1097         }
1098     }
1099 
1100     if (state >= sw_dot) {
1101         if (state >= sw_quoted) {
1102             return NXT_HTTP_PARSE_INVALID;
1103         }
1104 
1105         /* "/." and "/.." must be normalized similar to "/./" and "/../". */
1106         ch = '/';
1107         goto again;
1108     }
1109 
1110 args:
1111 
1112     for (/* void */; p < rp->target_end; p++) {
1113         if (*p == '#') {
1114             break;
1115         }
1116     }
1117 
1118     if (args != NULL) {
1119         rp->args.length = p - args;
1120         rp->args.start = args;
1121     }
1122 
1123 done:
1124 
1125     rp->path.length = u - rp->path.start;
1126 
1127     return NXT_OK;
1128 }
1129 
1130 
1131 const nxt_lvlhsh_proto_t  nxt_http_fields_hash_proto  nxt_aligned(64) = {
1132     NXT_LVLHSH_BUCKET_SIZE(64),
1133     { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 },
1134     nxt_http_field_hash_test,
1135     nxt_http_field_hash_alloc,
1136     nxt_http_field_hash_free,
1137 };
1138 
1139 
1140 static nxt_int_t
1141 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data)
1142 {
1143     nxt_http_field_proc_t  *field;
1144 
1145     field = data;
1146 
1147     if (nxt_strcasestr_eq(&lhq->key, &field->name)) {
1148         return NXT_OK;
1149     }
1150 
1151     return NXT_DECLINED;
1152 }
1153 
1154 
1155 static void *
1156 nxt_http_field_hash_alloc(void *pool, size_t size)
1157 {
1158     return nxt_mp_align(pool, size, size);
1159 }
1160 
1161 
1162 static void
1163 nxt_http_field_hash_free(void *pool, void *p)
1164 {
1165     nxt_mp_free(pool, p);
1166 }
1167 
1168 
1169 static nxt_int_t
1170 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data)
1171 {
1172     return NXT_OK;
1173 }
1174 
1175 
1176 nxt_int_t
1177 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1178     nxt_http_field_proc_t items[], nxt_uint_t count)
1179 {
1180     u_char              ch;
1181     uint32_t            key;
1182     nxt_str_t           *name;
1183     nxt_int_t           ret;
1184     nxt_uint_t          i, j;
1185     nxt_lvlhsh_query_t  lhq;
1186 
1187     lhq.replace = 0;
1188     lhq.proto = &nxt_http_fields_hash_proto;
1189     lhq.pool = mp;
1190 
1191     for (i = 0; i < count; i++) {
1192         key = NXT_HTTP_FIELD_HASH_INIT;
1193         name = &items[i].name;
1194 
1195         for (j = 0; j < name->length; j++) {
1196             ch = nxt_lowcase(name->start[j]);
1197             key = nxt_http_field_hash_char(key, ch);
1198         }
1199 
1200         lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF;
1201         lhq.key = *name;
1202         lhq.value = &items[i];
1203 
1204         ret = nxt_lvlhsh_insert(hash, &lhq);
1205 
1206         if (nxt_slow_path(ret != NXT_OK)) {
1207             return NXT_ERROR;
1208         }
1209     }
1210 
1211     return NXT_OK;
1212 }
1213 
1214 
1215 nxt_uint_t
1216 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1217     nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level)
1218 {
1219     u_char              ch;
1220     uint32_t            key, mask;
1221     nxt_str_t           *name;
1222     nxt_uint_t          colls, i, j;
1223     nxt_lvlhsh_proto_t  proto;
1224     nxt_lvlhsh_query_t  lhq;
1225 
1226     proto = nxt_http_fields_hash_proto;
1227     proto.test = nxt_http_field_hash_collision;
1228 
1229     lhq.replace = 0;
1230     lhq.proto = &proto;
1231     lhq.pool = mp;
1232 
1233     mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF;
1234 
1235     colls = 0;
1236 
1237     for (i = 0; i < count; i++) {
1238         key = NXT_HTTP_FIELD_HASH_INIT;
1239         name = &items[i].name;
1240 
1241         for (j = 0; j < name->length; j++) {
1242             ch = nxt_lowcase(name->start[j]);
1243             key = nxt_http_field_hash_char(key, ch);
1244         }
1245 
1246         lhq.key_hash = nxt_http_field_hash_end(key) & mask;
1247         lhq.value = &items[i];
1248 
1249         if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) {
1250             colls++;
1251         }
1252     }
1253 
1254     return colls;
1255 }
1256 
1257 
1258 nxt_int_t
1259 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx)
1260 {
1261     nxt_int_t         ret;
1262     nxt_http_field_t  *field;
1263 
1264     nxt_list_each(field, fields) {
1265 
1266         ret = nxt_http_field_process(field, hash, ctx);
1267         if (nxt_slow_path(ret != NXT_OK)) {
1268             return ret;
1269         }
1270 
1271     } nxt_list_loop;
1272 
1273     return NXT_OK;
1274 }
1275