HTTP स्ट्रिंग फास्ट प्रोसेसिंग एल्गोरिदम

आवेदन वितरण नियंत्रक

प्रदर्शन

मुसीबत

एचटीटीपी

HTTP / 2 सुविधाएँ

• आपको राज्य मशीन को जल्दी से प्रोग्राम करने की आवश्यकता है।
• आपको लगातार लाइनों को जल्दी से संसाधित करने की आवश्यकता है।

Nginx प्रोफ़ाइल

HTTP पार्सर नियमित रूप से कैसे एनकोड किए जाते हैं

Nginx HTTP पार्सर

for (p = b->pos; p < b->last; p++) {
    ...
    switch (state) {
    ...
    case sw_method:
        if (ch == ' ') {
            m = r->request_start;
            switch (p - m) {         // switch on token length!
            case 3:
                if (ngx_str3_cmp(m, 'G', 'E', 'T', ' ')) {
                ...
            }
            if ((ch < 'A' || ch > 'Z') && ch != '_' && ch != '-')
                return NGX_HTTP_PARSE_INVALID_METHOD;
            break;
    ...

जीसीसी

$ nm -S /opt/nginx-1.11.5/sbin/nginx
| grep http_parse | cut -d' ' -f 2
| perl -le '$a += hex($_) while (<>); print $a'
9220

$ getconf LEVEL1_ICACHE_SIZE
32768

$ grep -c 'case sw_' src/http/ngx_http_parse.c
84

Tempesta FW: HTTP स्ट्रिंग्स का स्ट्रिंग सत्यापन

$ grep -c '__FSM_STATE\|__FSM_TX\|__FSM_METH_MOVE\|__TFW_HTTP_PARSE_' http_parser.c
520
    7.64% [tempesta_fw]     [k] tfw_http_parse_req
    2.79% [e1000]           [k] e1000_xmit_frame
    2.32% [tempesta_fw]     [k] __tfw_strspn_simd
    2.31% [tempesta_fw]     [k] __tfw_http_msg_add_str_data
    1.60% [tempesta_fw]     [k] __new_pgfrag
    1.58% [kernel]          [k] skb_release_data
    1.55% [tempesta_fw]     [k] __str_grow_tree
    1.41% [kernel]          [k] __inet_lookup_established
    1.35% [tempesta_fw]     [k] tfw_cache_do_action
    1.35% [tempesta_fw]     [k] __tfw_strcmpspn

एफएसएम डायरेक्ट रेफरल

प्रत्यक्ष रूपांतरण प्रदर्शन

$ grep -m 2 'model name\|bugs' /proc/cpuinfo
model name : Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz
bugs       : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf

$ gcc --version|head -1
gcc (GCC) 8.2.1 20181105 (Red Hat 8.2.1-5)

States     Switch-driven automaton     Goto-driven automaton
     7     header_line:      139ms     header_line:          156ms
    27     request_line:     210ms     request_line:         186ms
   406     big_header_line: 1406ms     goto_big_header_line: 727ms

क्यों प्रत्यक्ष संक्रमण धीमा हो सकता है

perf record -e branch-misses -g ./http_benchmark
406 states:    switch       - 38% on switch(),
               direct jumps - 13% on header value parsing
			   
7,27 states:   switch       - <18% switch(), up to 40% for()
               direct jumps – up to 46% on header & URI parsing

perf stat -e L1-icache-load-misses ./http_benchmark

                       Switch-driven automaton  Goto-driven automaton
big FSM code size:                       29156                  49202
L1-icache-load-misses:                      4M                     2M

संकलक कोड का क्रम बदलता है

STATE(sw_method) {
    ... // the most frequent states
    MATCH(NGX_HTTP_GET, "GET ");
    MATCH(NGX_HTTP_POST, "POST");
    
    __asm__ __volatile__("": : :"memory");
    ... // many other states
    
    // Improbable states
    METH_MOVE(Req_MethU, 'N', Req_MethUn);
    METH_MOVE(Req_MethUn, 'L', Req_MethUnl);
    METH_MOVE(Req_MethUnl, 'O', Req_MethUnlo);
    METH_MOVE(Req_MethUnlo, 'C', Req_MethUnloc);
    METH_MOVE_finish(Req_MethUnloc, 'K', NGX_HTTP_UNLOCK)

कोड को अपने तरीके से लिखें

Req_Method: {
    if (likely(PI(p) == CHAR4_INT('G', 'E', 'T', ' '))) {
        ...
        goto Req_Uri;
    }
    if (likely(PI(p) == CHAR4_INT('P', 'O', 'S', 'T'))) {
        ...
        goto Req_UriSpace;
    }
    goto Req_Meth_SlowPath;
}
... // other methods: POST, PUT etc.
Req_Uri:
    ... // URI processing
Req_Meth_SlowPath:
...

अस्पष्ट -ओ ३

Autovectorization

int a[256], b[256], c[256];
void foo () {
    for (int i = 0; i < 256; i++)
        a[i] = b[i] + c[i];
}

संरेखण: जीईटी के साथ स्ट्रिंग की तुलना कैसे करें?

#define CHAR4_INT(a, b, c, d)    ((d << 24) | (c << 16) | (b << 8) | a)
if (p == CHAR4_INT('G', 'E', 'T', ' ')))
    // we have GET as method

$ ./int_align
Unaligned access = 6.20482
Aligned access = 2.87012
Read four bytes = 2.45249

 (((long)(p) & 3)
  ? ((unsigned int)((p)[0]) | ((unsigned int)((p)[1]) << 8)
  | ((unsigned int)((p)[2]) << 16) | ((unsigned int)((p)[3]) << 24))
  : *(unsigned int *)(p));

full request line:     no difference
method only:           unaligned      - 214ms
                       aligned        - 231ms
                       bytes          - 216ms

HTTP स्ट्रिंग्स हमारे लिए महत्वपूर्ण क्यों हैं?

case sw_check_uri:
    if (usual[ch >> 5] & (1U << (ch & 0x1f)))
        break;
    switch (ch) {
    case '/':
        r->uri_ext = NULL;
        state = sw_after_slash_in_uri;
        break;
    case '.':
        r->uri_ext = p + 1;
        break;
    case ' ':
        r->uri_end = p;
        state = sw_check_uri_http_09;
        break;
    case CR:
        r->uri_end = p;
        r->http_minor = 9;
        state = sw_almost_done;
        break;
    case LF:
        r->uri_end = p;
        r->http_minor = 9;
        goto done;
    case '%':
    r->quoted_uri = 1;
    ...

8.62%  nginx         [.] ngx_http_parse_request_line
2.52%  nginx         [.] ngx_http_parse_header_line
1.42%  nginx         [.] ngx_palloc
0.90%  [kernel]      [k] copy_user_enhanced_fast_string
0.85%  nginx         [.] ngx_strstrn
0.78%  libc-2.24.so  [.] _int_malloc
0.69%  nginx         [.] ngx_hash_find
0.66%  [kernel]      [k] tcp_recvmsg

• strspn: वर्णमाला की जाँच करता है, एक स्ट्रिंग में उपलब्ध वर्ण, गतिशील रूप से एक वैध वर्णमाला का संकलन करता है, हालाँकि यह कार्यक्रम के संकलन के चरण में जाना जाता है।
• strcasecmp()। परिवर्तित मामले की कोई जरूरत नहीं तुलना करने के लिए नहीं है xके साथ Foo:। ज्यादातर मामलों में strcasecmp(), केवल अनुपालन / गैर-अनुपालन की आवश्यकता होती है , और आपको लाइन में स्थिति जानने की आवश्यकता नहीं है।

त्वरित पार्सर

Tempesta मिलान तेज और अधिक सटीक है

static const unsigned char uri_a[] __attribute__((aligned(64))) = {
        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,
        0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        ...
        // Branch misprediction is more crucial for short strings
        if (likely(len <= 4)) {
                switch (len) {
                case 0:
                    return 0;
                case 4:
                    c3 = uri_a[s[3]];
                    // fall through to process other chars
                case 3:
                    c2 = uri_a[s[2]];
                case 2:
                    c1 = uri_a[s[1]];
                case 1:
                    c0 = uri_a[s[0]];
                }
                return (c0 & c1) == 0 ? c0 : 2 + (c2 ? c2 + c3 : 0);
        }

for ( ; unlikely(s + 128 <= end); s += 128) {
        n = match_symbols_mask128_c(__C.URI_BM, s);
        if (n < 128)
                return s - (unsigned char *)str + n;
}

if (unlikely(s + 64 <= end)) {
        n = match_symbols_mask64_c(__C.URI_BM, s);
        if (n < 64)
                return s - (unsigned char *)str + n;
        s += 64;
}

if (unlikely(s + 32 <= end)) {
        n = match_symbols_mask32_c(__C.URI_BM, s);
        if (n < 32)
                return s - (unsigned char *)str + n;
        s += 32;
}

if (unlikely(s + 16 <= end)) {
        n = match_symbols_mask16_c(__C.URI_BM128, s);
        if (n < 16)
                return s - (unsigned char *)str + n;
        s += 16;
}

while (s + 4 <= end) {
        c0 = uri_a[s[0]];
        c1 = uri_a[s[1]];
        c2 = uri_a[s[2]];
        c3 = uri_a[s[3]];
        if (!(c0 & c1 & c2 & c3)) {
                n = s - (unsigned char *)str;
                return !(c0 & c1) ? n + c0 : n + 2 + (c2 ? c2 + c3 : 0);
        }
        s += 4;
}

c0 = c1 = c2 = 0;
switch (end - s) {
        case 3:
                c2 = uri_a[s[2]];
        case 2:
                c1 = uri_a[s[1]];
        case 1:
                c0 = uri_a[s[0]];
}

n = s - (unsigned char *)str;
return !(c0 & c1) ? n + c0 : n + 2 + c2;

आक्रमण

स्ट्रैसेकम्प ()

__m256i CASE = _mm256_set1_epi8(0x20);

// Hacker’s Delight for signed comparison: -0x80 for both operands
__m256i A = _mm256_set1_epi8('A' – 0x80);
__m256i D = _mm256_set1_epi8('Z' - 'A' + 1 – 0x80);

// Hacker’s Delight: 'a' <= v <= 'z' to
// v - ('a' – 0x80) < 'z' - 'a' + 1 - 0x80
__m256i sub = _mm256_sub_epi8(str1, A);
__m256i cmp_r = _mm256_cmpgt_epi8(D, sub);
__m256i lc = _mm256_and_si256(cmp_r, CASE);
__m256i vl = _mm256_or_si256(str1, lc);
__m256i eq = _mm256_cmpeq_epi8(vl, str2);
return ~_mm256_movemask_epi8(eq);

प्रदर्शन strcasecmp ()

लिनक्स कर्नेल FPU

__kernel_fpu_begin_bh();
memcpy_avx(dst, src, n);
__kernel_fpu_end_bh();

एवीएक्स और एस.एस.ई.

एफपीयू

Intelpocalypse

jmp *%r11 
    call l1
l0: pause
    lfence
    jmp l0
l1: mov %r11, (%rsp)
    ret

• HTTP पार्सिंग के लिए फास्ट फिनाइट स्टेट मशीन
• HTTP स्ट्रिंग्स प्रोसेसिंग सी, SSE4.2 और AVX2 का उपयोग करना

• हैकर की खुशी

• मेल्टडाउन और स्पेक्टर डॉक्स पर हमला करता है

• Intelpocalypse: goodbye fast system calls

Saint HighLoad++ . , 6 -- ( , Saint HighLoad++) , web .

PHP Russia: 13 , . — KnowledgeConf, ++ TechLead Conf — . , , .