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