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