Algoritmos de procesamiento rápido de cadenas HTTP

Controlador de entrega de aplicaciones

Actuación

Problema

HTTP

Características HTTP / 2

• Necesita programar rápidamente la máquina de estado.
• Necesita procesar rápidamente líneas consecutivas.

Perfil Nginx

Cómo se codifican los analizadores HTTP normales

Analizador HTTP Nginx

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;
    ...

Gcc

$ 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: validación de cadenas de cadenas 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

Referencias directas de FSM

Rendimiento de conversión directa

$ 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

¿Por qué las transiciones directas pueden ser más lentas?

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

El compilador cambia el orden del código.

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)

Redacta el código a tu manera

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:
...

Ambiguo -O3

Autovectorización

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

Alineación: ¿cómo comparar una cadena con GET?

#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

¿Por qué las cadenas HTTP son importantes para nosotros?

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: comprueba el alfabeto, los caracteres disponibles en una cadena, compila dinámicamente un alfabeto válido, aunque se conoce en la etapa de compilación del programa.
• strcasecmp(). No hay necesidad de convertir el caso de comparar xcon Foo:. En la mayoría de los casos strcasecmp(), solo se requiere cumplimiento / incumplimiento, y no es necesario conocer la posición en la línea.

Analizadores rápidos

Tempesta Matcher es más rápido y más preciso

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;

Los ataques

strcasecmp ()

__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);

Rendimiento strcasecmp ()

Linux kernel FPU

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

AVX y SSE

FPU

Intelpocalypse

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

• Máquina de estado finito rápido para análisis HTTP
• Procesamiento de cadenas HTTP usando C, SSE4.2 y AVX2

• El deleite del hacker

• Documentos de ataques Meltdown y Spectre

• Intelpocalypse: goodbye fast system calls

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

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