Comportamento indefinido e verdade não definida

O termo "comportamento indefinido" na linguagem C e C ++ designa uma situação na qual literalmente "o que simplesmente não acontece". Historicamente, os casos em que os compiladores C anteriores (e as arquiteturas nele) se comportavam de maneira incompatível eram atribuídos a um comportamento indefinido, e o comitê para desenvolver o padrão, em sua sabedoria ilimitada, decidiu não decidir nada sobre isso (ou seja, não dar preferência) algumas das implementações concorrentes). O comportamento indefinido também foi chamado de situações possíveis nas quais o padrão, geralmente tão exaustivo, não prescreveu nenhum comportamento específico. Esse termo tem um terceiro significado, que em nosso tempo está se tornando cada vez mais relevante: comportamento indefinido - essa é a oportunidade de otimização. E os desenvolvedores em C e C ++ adoram otimizações; eles exigem insistentemente que os compiladores façam todos os esforços para acelerar o código.

Este artigo foi publicado pela primeira vez no site de serviços de criptografia. A tradução é publicada com permissão do autor Thomas Pornin.

Aqui está um exemplo clássico:

void foo(double *src, int *dst) { int i; for (i = 0; i < 4; i ++) { dst[i] = (int)src[i]; } } 

Compilaremos esse código GCC em uma plataforma x86 de 64 bits para Linux (eu trabalho na versão mais recente do Ubuntu 18.04, versão GCC - 7.3.0). Ativamos a otimização total e, em seguida, analisamos a lista do assembler, para a qual usamos as teclas "-W -Wall -O9 -S " (o argumento " -O9 " define o nível máximo de otimização do GCC, que na prática é equivalente a " -O3 ", embora em alguns garfos Níveis definidos e mais altos do CCG). Temos o seguinte resultado:

  .file "zap.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc movupd (%rdi), %xmm0 movupd 16(%rdi), %xmm1 cvttpd2dq %xmm0, %xmm0 cvttpd2dq %xmm1, %xmm1 punpcklqdq %xmm1, %xmm0 movups %xmm0, (%rsi) ret .cfi_endproc .LFE0: .size foo, .-foo .ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0" .section .note.GNU-stack,"",@progbits 

Cada uma das duas primeiras instruções movupd move dois valores duplos para o registro SSE2 de 128 bits (o dobro tem um tamanho de 64 bits, para que o registro SSE2 possa armazenar dois valores duplos ). Em outras palavras, quatro valores iniciais são lidos primeiro e somente depois são convertidos para int (operação cvttpd2dq ). A operação punpcklqdq move os quatro números inteiros de 32 bits recebidos em um registro SSE2 (% xmm0 ), cujo conteúdo é gravado na RAM ( movimentos ). E agora o principal: nosso programa C exige formalmente que o acesso à memória ocorra na seguinte ordem:

• Leia o primeiro valor duplo de src [0] .
• Escreva o primeiro valor do tipo int em dst [0] .
• Leia o segundo valor duplo de src [1] .
• Escreva o segundo valor do tipo int em dst [1] .
• Leia o terceiro valor duplo de src [2] .
• Escreva o terceiro valor do tipo int para dst [2] .
• Leia o quarto valor duplo de src [3] .
• Escreva o quarto valor do tipo int em dst [3] .

No entanto, todos esses requisitos fazem sentido apenas no contexto de uma máquina abstrata, que o padrão C define; o procedimento em uma máquina real pode variar. O compilador é livre para reorganizar ou modificar operações, desde que seu resultado não contradiga a semântica da máquina abstrata (a chamada regra como se é "como se"). No nosso exemplo, a ordem de ação é apenas diferente:

• Leia o primeiro valor duplo de src [0] .
• Leia o segundo valor duplo de src [1] .
• Leia o terceiro valor duplo de src [2] .
• Leia o quarto valor duplo de src [3] .
• Escreva o primeiro valor do tipo int em dst [0] .
• Escreva o segundo valor do tipo int em dst [1] .
• Escreva o terceiro valor do tipo int para dst [2] .
• Escreva o quarto valor do tipo int em dst [3] .

Esta é a linguagem C: todo o conteúdo da memória é, em última instância, bytes (ou seja, slots com valores do tipo char não assinado , mas na prática, grupos de oito bits) e qualquer operação arbitrária de ponteiro é permitida. Em particular, os ponteiros src e dst podem ser usados ​​para acessar partes sobrepostas da memória quando chamadas (essa situação é chamada de "alias"). Portanto, a ordem de leitura e gravação pode ser importante se os bytes forem gravados e depois lidos novamente. Para que o comportamento real do programa corresponda ao resumo definido pelo padrão C, o compilador precisará alternar entre operações de leitura e gravação, fornecendo um ciclo completo de acessos à memória a cada iteração. O código resultante seria maior e funcionaria muito mais devagar. Para desenvolvedores C, isso seria uma tristeza.

Felizmente, aqui o comportamento indefinido vem em socorro. O padrão C indica que os valores não podem ser acessados ​​através de ponteiros cujo tipo não corresponde aos tipos atuais desses valores. Simplificando, se o valor for gravado em dst [0] , onde dst é um ponteiro int , os bytes correspondentes não poderão ser lidos via src [1] , onde src é um ponteiro duplo , pois nesse caso tentaríamos acessar value, que agora é do tipo int , usando um ponteiro de um tipo incompatível. Nesse caso, um comportamento indefinido ocorreria. Isso é afirmado no parágrafo 7 da seção 6.5 da norma ISO 9899: 1999 (“C99”) (na nova edição 9899: 2018 ou “C17”, a redação não mudou). Esse requisito é chamado de regra estrita de alias. Como resultado, o compilador C pode agir com base no pressuposto de que as operações de acesso à memória que levam a um comportamento indefinido devido à violação da regra estrita de alias não ocorrem. Portanto, o compilador pode reorganizar as operações de leitura e gravação em qualquer ordem, pois não deve acessar partes sobrepostas da memória. É disso que se trata a otimização de código.

O significado de comportamento indefinido, em resumo, é o seguinte: o compilador pode assumir que não haverá comportamento indefinido e gerar código com base nessa suposição. No caso da regra estrita de alias - desde que o alias ocorra, o comportamento indefinido permite otimizações importantes que seriam difíceis de implementar. De um modo geral, cada instrução nos procedimentos de geração de código usados ​​pelo compilador possui dependências que restringem o algoritmo de planejamento da operação: uma instrução não pode ser executada antes das instruções das quais depende ou após as instruções que dependem dela. Em nosso exemplo, o comportamento indefinido elimina as dependências entre operações de gravação nas operações dst [] e “subsequentes” de leitura do src [] : essa dependência pode existir apenas nos casos em que ocorre um comportamento indefinido ao acessar a memória. Da mesma forma, o conceito de comportamento indefinido permite que o compilador exclua simplesmente o código que não pode ser executado sem entrar em um estado de comportamento indefinido.

Tudo isso, é claro, é bom, mas esse comportamento às vezes é percebido como traição traiçoeira pelo compilador. Você costuma ouvir a frase: "O compilador usa o conceito de comportamento indefinido como uma desculpa para quebrar meu código". Suponha que alguém escreva um programa que adicione números inteiros e os medos excedam - lembre-se do caso do Bitcoin . Ele pode pensar assim: para representar números inteiros, o processador usa código adicional, o que significa que, se ocorrer um estouro, isso acontecerá porque o resultado será truncado para o tamanho do tipo, ou seja, 32 bit Isso significa que o resultado do estouro pode ser previsto e verificado com um teste.

Nosso desenvolvedor condicional escreverá isto:

 #include <stdio.h> #include <stdlib.h> int add(int x, int y, int *z) { int r = x + y; if (x > 0 && y > 0 && r < x) { return 0; } if (x < 0 && y < 0 && r > x) { return 0; } *z = r; return 1; } int main(int argc, char *argv[]) { int x, y, z; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); if (add(x, y, &z)) { printf("%d\n", z); } else { printf("overflow!\n"); } return 0; } 

Agora vamos tentar compilar esse código usando o GCC:

 $ gcc -W -Wall -O9 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 overflow! 

Ok, parece funcionar. Agora tente outro compilador, por exemplo, Clang (eu tenho a versão 6.0.0):

 $ clang -W -Wall -O3 testadd.c $ ./a.out 17 42 59 $ ./a.out 2000000000 1500000000 -794967296 

O que?

Acontece que quando uma operação com tipos de números inteiros assinados leva a um resultado que não pode ser representado pelo tipo de destino, entramos no território de comportamento indefinido. Mas o compilador pode assumir que isso não acontece. Em particular, otimizando a expressão x> 0 && y> 0 && r <x , o compilador conclui que, como os valores de xey são estritamente positivos, a terceira verificação não pode ser verdadeira (a soma de dois valores não pode ser menor que qualquer um deles), e você pode pular toda essa operação. Em outras palavras, como o transbordamento é um comportamento indefinido, "não pode acontecer" do ponto de vista do compilador, e todas as instruções que dependem desse estado podem ser excluídas. O mecanismo para detectar comportamento indefinido simplesmente desapareceu.

O padrão nunca prescreveu a suposição de que “semântica assinada” (que é realmente usada nas operações do processador) é usada em cálculos com tipos assinados; isso aconteceu bastante pela tradição - mesmo naqueles dias em que os compiladores não eram inteligentes o suficiente para otimizar o código, concentrando-se em vários valores. Você pode forçar o Clang e o GCC a aplicar a semântica de quebra automática aos tipos assinados usando o sinalizador -fwrapv (no Microsoft Visual C, você pode usar -d2UndefIntOverflow-, conforme descrito aqui ). No entanto, essa abordagem não é confiável, o sinalizador pode desaparecer quando o código é transferido para outro projeto ou para outra arquitetura.

Poucas pessoas sabem que o excesso de tipos de caracteres envolve um comportamento indefinido. Isto é afirmado no parágrafo 5 da seção 6.5 das normas C99 e C17:

Se ocorrer uma exceção ao avaliar uma expressão (ou seja, se o resultado não estiver definido matematicamente ou estiver fora do intervalo de valores válidos de um determinado tipo), o comportamento será indefinido.

Para tipos não assinados, no entanto, a semântica modular é garantida. O parágrafo 9 da seção 6.2.5 diz o seguinte:

O estouro nunca ocorre nos cálculos com operandos não assinados, pois um resultado que não pode ser representado pelo tipo inteiro não assinado resultante é truncado no módulo um número que é um a mais que o valor máximo representado pelo tipo resultante.

Outro exemplo de comportamento indefinido em operações com tipos assinados é a operação de divisão. Como todos sabem, o resultado da divisão por zero não é matematicamente determinado; portanto, de acordo com o padrão, essa operação implica um comportamento indefinido. Se o divisor for zero na operação idiv no processador x86, uma exceção do processador será lançada. Como solicitações de interrupção, as exceções do processador são tratadas pelo sistema operacional. Em sistemas tipo Unix, como o Linux, a exceção do processador acionada pela operação idiv é convertida em um sinal SIGFPE , enviado ao processo e termina com o manipulador padrão (não se surpreenda que “FPE” represente “exceção de ponto flutuante” (exceção em operações de ponto flutuante), enquanto o idiv trabalha com números inteiros). Mas há outra situação que leva a um comportamento indefinido. Considere o seguinte código:

 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", x / y); return 0; }  : $ gcc -W -Wall -O testdiv.c $ ./a.out 42 17 2 $ ./a.out -2147483648 -1 zsh: floating point exception (core dumped) ./a.out -2147483648 -1 

E a verdade é: nesta máquina (o mesmo x86 para Linux), o tipo int representa um intervalo de valores de -2.147.483.648 a +2.147.483.647. Se você dividir -2.147.483.648 por -1, deverá obter +2.147.483.648 Mas esse número não está no intervalo de valores int . Portanto, o comportamento não está definido. Tudo pode acontecer. Nesse caso, o processo é encerrado à força. Em outro sistema, especialmente com um processador pequeno que não possui uma operação de divisão, o resultado pode variar. Nessas arquiteturas, a divisão é realizada programaticamente - com a ajuda do procedimento normalmente fornecido pelo compilador, e agora ele pode fazer o que bem entender com um comportamento indefinido, porque é exatamente isso que é.

Observo que o SIGFPE pode ser obtido nas mesmas condições e com a ajuda do operador do módulo ( % ). E, de fato: nela está a mesma operação de identificação , que calcula o quociente e o restante, de modo que a mesma exceção do processador é acionada. Curiosamente, o padrão C99 diz que a expressão INT_MIN% -1 não pode levar a um comportamento indefinido, pois o resultado é matematicamente definido (zero) e entra claramente no intervalo de valores do tipo de destino. Na versão C17, o texto do parágrafo 6 da seção 6.5.5 foi alterado e agora esse caso também é levado em consideração, o que aproxima o padrão da situação real em plataformas de hardware comuns.

Existem muitas situações não óbvias que também levam a um comportamento indefinido. Dê uma olhada neste código:

 #include <stdio.h> #include <stdlib.h> unsigned short mul(unsigned short x, unsigned short y) { return x * y; } int main(int argc, char *argv[]) { int x, y; if (argc != 3) { return EXIT_FAILURE; } x = atoi(argv[1]); y = atoi(argv[2]); printf("%d\n", mul(x, y)); return 0; } 

Você acha que um programa, seguindo o padrão C, deve ser impresso se passarmos os fatores 45.000 e 50.000 para a função?

• 18.048
• 2.250.000.000
• Deus salve a rainha!

A resposta correta ... sim, todas as opções acima! Você pode ter argumentado assim: como um curto não assinado é um tipo não assinado, ele deve suportar o módulo de semântica de empacotamento 65 536, porque em um processador x86 o tamanho desse tipo, via de regra, é exatamente de 16 bits (o padrão também permite um tamanho maior, mas na prática, esse ainda é um tipo de 16 bits). Como matematicamente o produto é 2.250.000.000, será truncado o módulo 65.536, que fornece uma resposta de 18.048. No entanto, pensando assim, esquecemos a extensão dos tipos inteiros. De acordo com o padrão C (seção 6.3.1.1, parágrafo 2), se os operandos são de um tipo cujo tamanho é estritamente menor que o tamanho de int , e os valores desse tipo podem ser representados pelo tipo int sem perda de bits (e apenas temos este caso: no meu x86 em O Linux tem um tamanho int de 32 bits e pode armazenar explicitamente valores de 0 a 65.535); então, os dois operandos são convertidos em int e a operação já é executada nos valores convertidos. A saber: o produto é calculado como um valor do tipo int e, somente ao retornar da função, é trazido de volta para um curto não assinado (isto é, neste momento ocorre o módulo de truncamento 65 536). O problema é que matematicamente o resultado antes da transformação inversa é de 2.250 milhões e esse valor excede o intervalo de int , que é um tipo assinado. Como resultado, temos um comportamento indefinido. Depois disso, tudo pode acontecer, incluindo ataques repentinos de patriotismo inglês.

No entanto, na prática, com compiladores comuns, o resultado é 18.048, uma vez que ainda não há otimização que possa tirar proveito do comportamento indefinido nesse programa em particular (pode-se imaginar cenários mais artificiais onde isso realmente causaria problemas).

Finalmente, outro exemplo, agora em C ++:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <array> int main(int argc, char *argv[]) { std::array<char, 16> tmp; int i; if (argc < 2) { return EXIT_FAILURE; } memset(tmp.data(), 0, 16); if (strlen(argv[1]) < 16) { strcpy(tmp.data(), argv[1]); } for (i = 0; i < 17; i ++) { printf(" %02x", tmp[i]); } printf("\n"); } 

Este não é o típico “péssimo péssimo strcpy () !” Para você. De fato, aqui a função strcpy () é executada apenas se o tamanho da string de origem, incluindo o terminal zero, for pequeno o suficiente. Além disso, os elementos da matriz são explicitamente inicializados como zero, portanto, todos os bytes da matriz têm um determinado valor, independentemente de uma cadeia grande ou pequena ser passada para a função. Ao mesmo tempo, o loop no final está incorreto: ele lê um byte a mais do que deveria.

Execute o código:

 $ g++ -W -Wall -O9 testvec.c $ ./a.out foo 66 6f 6f 00 00 00 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ff ffffac ffffffc0 55 00 00 00 ffffff80 71 34 ffffff99 07 ffffffba ff ffffea ffffffd0 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ffffffac ffffffc0 55 00 00 ffffff97 7b 12 1b ffffffa1 7f 00 00 02 00 00 00 00 00 00 00 ffffffd8 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 ffffff80 00 00 02 00 00 00 60 56 (...) 62 64 3d 30 30 zsh: segmentation fault (core dumped) ./a.out foo ++? 

Você pode objetar ingenuamente: bem, ele lê um byte extra além dos limites da matriz; mas isso não é tão assustador, porque na pilha esse byte ainda está lá, é mapeado para a memória, então o único problema aqui é o décimo sétimo elemento extra com um valor desconhecido. O ciclo ainda imprime exatamente 17 números inteiros (em formato hexadecimal) e termina sem nenhuma reclamação.

Mas o compilador tem sua própria opinião sobre esse assunto. Ele está ciente de que a décima sétima leitura provoca um comportamento indefinido. Segundo sua lógica, qualquer instrução subsequente está no limbo: não há exigência de que, após um comportamento indefinido, alguma coisa exista (formalmente até instruções anteriores podem estar sob ataque, pois o comportamento indefinido também funciona na direção oposta). No nosso caso, o compilador simplesmente ignorará a verificação da condição no loop e girará para sempre, ou melhor, até que comece a ler fora da memória alocada para a pilha, após a qual o sinal SIGSEGV funcionará.

É engraçado, mas se o GCC iniciar com configurações menos agressivas para otimizações, ele emitirá um aviso:

 $ g++ -W -Wall -O1 testvec.c testvec.c: In function 'int main(int, char**)': testvec.c:20:15: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations] printf(" %02x", tmp[i]); ~~~~~~^~~~~~~~~~~~~~~~~ testvec.c:19:19: note: within this loop for (i = 0; i < 17; i ++) { ~~^~~~ 

Em -O9, esse aviso desaparece de alguma forma. Talvez o fato seja que, em altos níveis de otimização, o compilador imponha mais agressivamente a implantação do loop. É possível (mas impreciso) que esse seja um bug do GCC (no sentido de uma perda de aviso; portanto, as ações do GCC em qualquer caso não contradizem o padrão, porque não requer a emissão de "diagnósticos" nessa situação).

Conclusão: se você estiver escrevendo código em C ou C ++, seja extremamente cuidadoso e evite situações que levem a um comportamento indefinido, mesmo quando parecer que está tudo bem.

Os tipos inteiros não assinados são um bom auxiliar nos cálculos aritméticos, uma vez que são semânticas modulares garantidas (mas você ainda pode obter problemas relacionados à extensão dos tipos inteiros). Outra opção - por algum motivo impopular - não é escrever em C e C ++. Por várias razões, essa solução nem sempre é adequada. Mas se você pode escolher em qual idioma gravar o programa, ou seja, quando você está apenas iniciando um novo projeto em uma plataforma que suporta Go, Rust, Java ou outras linguagens, pode ser mais rentável recusar usar C como a "linguagem padrão". A escolha de ferramentas, incluindo uma linguagem de programação, é sempre um compromisso. As armadilhas de C, especialmente o comportamento indefinido em operações com tipos assinados, levam a custos adicionais para manutenção adicional do código, que geralmente são subestimados.