Estouro assinado em C ++ e comportamento indefinido (UB)

56

Eu estou pensando sobre o uso de código como o seguinte

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Se o loop for iterado ao longo do ntempo, factorserá multiplicado 10exatamente pelo ntempo. No entanto, factorsó é usado depois de multiplicado pelo 10total de n-1vezes. Se assumirmos que factornunca estouramos, exceto na última iteração do loop, mas podemos estourar na última iteração do loop, esse código deve ser aceitável? Nesse caso, o valor de factorprovavelmente nunca seria usado após o estouro.

Estou discutindo se códigos como esse devem ser aceitos. Seria possível colocar a multiplicação dentro de uma instrução if e simplesmente não fazer a multiplicação na última iteração do loop, quando ele pode transbordar. A desvantagem é que ele atrapalha o código e adiciona uma ramificação desnecessária que precisaria verificar todas as iterações anteriores do loop. Eu também poderia iterar o loop menos uma vez e replicar o corpo do loop uma vez após o loop, novamente, isso complica o código.

O código real em questão é usado em um loop interno rígido que consome grande parte do tempo total da CPU em um aplicativo gráfico em tempo real.

del
fonte
5
Estou votando para encerrar esta questão como off-topic, porque ela deve estar em codereview.stackexchange.com, não aqui.
Kevin Anderson
31
@ KevinAnderson, não, é válido aqui, pois o código de exemplo deve ser corrigido, não apenas melhorado.
Bate-Seba
11
@harold Eles estão perto.
Lightness Races em órbita
11
@LightnessRaceswithMonica: Os autores do Padrão pretendiam e esperavam que as implementações destinadas a várias plataformas e propósitos estendessem a semântica disponível para os programadores, processando significativamente várias ações de maneiras úteis para essas plataformas e propósitos, independentemente de o Padrão exigir ou não, e também declararam que não desejavam menosprezar o código não portátil. Assim, a semelhança entre as perguntas depende de quais implementações precisam apoiar.
Supercat
2
@supercat Para comportamentos definidos pela implementação, com certeza, e se você sabe que sua cadeia de ferramentas tem alguma extensão, você pode usar (e não se importa com a portabilidade), tudo bem. Para UB? Duvidoso.
Lightness Races em órbita

Respostas:

51

Compiladores assumem que um programa C ++ válido não contém UB. Considere, por exemplo:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Se, x == nullptrentão, derreferenciá-lo e atribuir um valor é UB. Portanto, a única maneira de isso terminar em um programa válido é quando x == nullptrnunca produzirá true e o compilador pode assumir a regra como se, o acima é equivalente a:

*x = 5;

Agora no seu código

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

A última multiplicação de factornão pode acontecer em um programa válido (o estouro assinado é indefinido). Daí também a tarefa de resultnão poder acontecer. Como não há como ramificar antes da última iteração, a iteração anterior também não pode acontecer. Eventualmente, a parte do código correta (ou seja, nenhum comportamento indefinido acontece) é:

// nothing :(
idclev 463035818
fonte
6
"Comportamento indefinido" é uma expressão que ouvimos muito nas respostas do SO, sem explicar claramente como isso pode afetar um programa como um todo. Essa resposta torna as coisas muito mais claras.
Gilles-Philippe Paillé
11
E isso pode até ser uma "otimização útil" se a função for chamada apenas em destinos com INT_MAX >= 10000000000, com uma função diferente chamada no caso em que INT_MAXfor menor.
R .. GitHub Pare de ajudar o gelo
2
@ Gilles-PhilippePaillé Há momentos em que eu gostaria de poder escrever um post sobre isso. Benign Data Races é um dos meus favoritos para capturar o quão desagradável eles podem ser. Também há um ótimo relatório de erro no MySQL que parece que não consigo encontrar novamente - uma verificação de estouro de buffer que acidentalmente invocou o UB. Uma versão específica de um compilador específico simplesmente assumiu que o UB nunca ocorre e otimizou toda a verificação de estouro.
Cort Ammon
11
@SolomonSlow: As principais situações em que a UB é controversa são aquelas em que partes da documentação da Norma e implementações descrevem o comportamento de alguma ação, mas alguma outra parte da Norma a caracteriza como UB. A prática comum antes da redação do Padrão era para que os escritores do compilador processassem essas ações de maneira significativa, exceto quando seus clientes se beneficiariam deles fazendo outra coisa, e eu não acho que os autores do Padrão jamais imaginaram que os escritores do compilador fizessem voluntariamente qualquer outra coisa. .
Supercat
2
@ Gilles-PhilippePaillé: O que todo programador de C deve saber sobre o comportamento indefinido do blog do LLVM também é bom. Ele explica como, por exemplo, o UB com excesso de número inteiro assinado pode permitir que os compiladores provem que os i <= nloops são sempre não infinitos, como i<nloops. E promova int ia largura do ponteiro em um loop, em vez de precisar refazer a assinatura para possível indexação da matriz de agrupamento aos primeiros elementos da matriz 4G.
Peter Cordes
34

O comportamento do intestouro é indefinido.

Não importa se você lê factorfora do corpo do loop; se ele estourou até então, o comportamento do seu código foi depois, e um tanto paradoxalmente, antes que o estouro seja indefinido.

Um problema que pode surgir para manter esse código é que os compiladores estão ficando cada vez mais agressivos quando se trata de otimização. Em particular, eles estão desenvolvendo um hábito em que assumem que um comportamento indefinido nunca acontece. Para que isso aconteça, eles podem remover o forloop completamente.

Você não pode usar um unsignedtipo para factorembora então você precisa se preocupar com a conversão indesejada de intque unsignedem expressões contendo tanto?

Bathsheba
fonte
12
@nicomp; Por que não?
Bate-Seba
12
@ Gilles-PhilippePaillé: A minha resposta não diz que é problemático? Minha frase de abertura não existe necessariamente para o OP, mas para a comunidade mais ampla E factoré "usada" na tarefa de volta a si mesma.
Bate-Seba
8
@ Gilles-PhilippePaillé e essa resposta explica por que é problemático
idclev 463035818
11
@Bathsheba Você está certo, eu não entendi sua resposta.
Gilles-Philippe Paillé
4
Como um exemplo de comportamento indefinido, quando esse código é compilado com as verificações de tempo de execução ativadas, ele termina em vez de retornar um resultado. O código que exige que eu desative as funções de diagnóstico para poder funcionar está quebrado.
Simon Richter
23

Pode ser interessante considerar otimizadores do mundo real. Desenrolar o loop é uma técnica conhecida. A idéia básica de desenrolar o loop op é que

for (int i = 0; i != 3; ++i)
    foo()

pode ser melhor implementado nos bastidores como

 foo()
 foo()
 foo()

Este é o caso fácil, com um limite fixo. Mas os compiladores modernos também podem fazer isso por limites variáveis:

for (int i = 0; i != N; ++i)
   foo();

torna-se

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Obviamente isso só funciona se o compilador souber que N <= 3. E é aí que voltamos à pergunta original. Como o compilador sabe que o estouro assinado não ocorre , ele sabe que o loop pode executar no máximo 9 vezes em arquiteturas de 32 bits. 10^10 > 2^32. Portanto, ele pode fazer um loop de 9 iterações. Mas o máximo pretendido foi de 10 iterações! .

O que pode acontecer é que você obtenha um salto relativo em uma instrução de montagem (9-N) com N = 10, portanto, um deslocamento de -1, que é a própria instrução de salto. Opa Essa é uma otimização de loop perfeitamente válida para C ++ bem definido, mas o exemplo dado se transforma em um loop infinito apertado.

MSalters
fonte
9

Qualquer excesso de número inteiro assinado resulta em comportamento indefinido, independentemente de o valor excedido ser ou não lido ou não.

Talvez no seu caso de uso você possa tirar a primeira iteração do loop, transformando isso

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

nisso

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Com a otimização ativada, o compilador pode desenrolar o segundo loop acima em um salto condicional.

elbrunovsky
fonte
6
Isso pode ser um pouco técnico demais, mas "o excesso de sinal assinado é um comportamento indefinido" é simplificado demais. Formalmente, o comportamento de um programa com estouro assinado é indefinido. Ou seja, o padrão não informa o que esse programa faz. Não é apenas que haja algo errado com o resultado que transbordou; há algo errado com todo o programa.
Pete Becker
Observação justa, corrigi minha resposta.
Elbrunovsky
Ou mais simplesmente, descascar a última iteração e remover os mortosfactor *= 10;
Peter Cordes
9

Este é UB; em termos de ISO C ++, todo o comportamento de todo o programa é completamente não especificado para uma execução que eventualmente atinge o UB. O exemplo clássico é que, na medida em que o padrão C ++ se importa, ele pode fazer com que os demônios voem do seu nariz. (Eu recomendo não usar uma implementação em que os demônios nasais são uma possibilidade real). Veja outras respostas para mais detalhes.

Os compiladores podem "causar problemas" em tempo de compilação para os caminhos de execução que eles podem ver levando a UB visível em tempo de compilação, por exemplo, suponha que esses blocos básicos nunca sejam atingidos.

Consulte também O que todo programador C deve saber sobre comportamento indefinido (blog do LLVM). Conforme explicado lá, o UB de estouro assinado permite que os compiladores provem que os for(... i <= n ...)loops não são infinitos, mesmo para desconhecidos n. Ele também permite que eles "promovam" contadores de loop int para a largura do ponteiro, em vez de refazer a extensão do sinal. (Portanto, a conseqüência do UB nesse caso poderia ser acessar fora dos elementos baixos de 64k ou 4G de uma matriz, se você estivesse esperando uma quebra automática assinada iem seu intervalo de valores.)

Em alguns casos, os compiladores emitem uma instrução ilegal como x86 ud2para um bloco que provavelmente causa o UB, se alguma vez for executado. (Observe que uma função nem sempre pode ser chamada, portanto, em geral, os compiladores não podem ficar furiosos e interromper outras funções, ou mesmo caminhos possíveis através de uma função que não atinge UB. todas as entradas que não levam ao UB.)


Provavelmente, a solução mais eficiente é descascar manualmente a última iteração para factor*=10evitar o desnecessário .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Ou se o corpo do loop for grande, considere simplesmente usar um tipo não assinado para factor. Em seguida, você pode deixar o multiplicador sem sinal estourar e ele fará um empacotamento bem definido com uma potência de 2 (o número de bits de valor no tipo não assinado).

Isso é bom mesmo se você usá-lo com tipos assinados, especialmente se sua conversão não assinada-> nunca exceder.

A conversão entre o complemento não assinado e o do 2 assinado é livre (o mesmo padrão de bits para todos os valores); o módulo para int -> unsigned especificado pelo padrão C ++ simplifica o uso do mesmo padrão de bits, diferente do complemento ou sinal / magnitude.

E não assinado-> assinado é igualmente trivial, embora seja definido pela implementação para valores maiores que INT_MAX. Se você não estiver usando o enorme resultado não assinado da última iteração, não terá com que se preocupar. Mas, se estiver, consulte A conversão de não assinado em assinado é indefinida? . O caso do valor não se encaixa é definido pela implementação , o que significa que uma implementação deve escolher algum comportamento; os sãos apenas truncam (se necessário) o padrão de bits não assinado e o usam como assinado, porque isso funciona para valores dentro do intervalo da mesma maneira, sem trabalho extra. E definitivamente não é UB. Assim, grandes valores não assinados podem se tornar inteiros com sinal negativo. por exemplo, depois de int x = u; gcc e clang não otimizarx>=0como sempre sendo verdade, mesmo sem -fwrapv, porque eles definiram o comportamento.

Peter Cordes
fonte
2
Eu não entendo o voto negativo aqui. Eu queria principalmente postar sobre a remoção da última iteração. Mas, para responder ainda à pergunta, juntei alguns pontos sobre como gritar UB. Veja outras respostas para mais detalhes.
Peter Cordes
5

Se você puder tolerar algumas instruções adicionais de montagem no loop, em vez de

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

você pode escrever:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

para evitar a última multiplicação. !factornão introduzirá um ramo:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Este código

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

também resulta em montagem sem ramificação após a otimização:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Compilado com o GCC 8.3.0 -O3)

Evg
fonte
11
É mais simples descascar a última iteração, a menos que o corpo do loop seja grande. Este é um truque inteligente, mas aumenta factorligeiramente a latência da cadeia de dependência transportada por loop . Ou não: quando ele compila para 2x LEA é quase tão eficiente quanto LEA + ADD fazer f *= 10como f*5*2, com testlatência escondida pelo primeiro LEA. Mas custa UOPs extras dentro do loop por isso há uma possível desvantagem rendimento (ou pelo menos uma questão hyperthreading de uso)
Peter Cordes
4

Você não mostrou o que está entre parênteses da fordeclaração, mas vou assumir que é algo como isto:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Você pode simplesmente mover a verificação do incremento do contador e da terminação do loop para o corpo:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

O número de instruções de montagem no loop permanecerá o mesmo.

Inspirado na apresentação de Andrei Alexandrescu "A velocidade é encontrada nas mentes das pessoas".

Oktalist
fonte
2

Considere a função:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

De acordo com a Justificativa publicado, os autores do padrão teria esperado que, se esta função foi chamado em (por exemplo) um computador de 32 bits comum com argumentos de 0xC000 e 0xC000, promovendo os operandos de *que signed intfaria com que a computação para produzir -0x10000000 , que quando convertidos em unsignedproduziriam 0x90000000u- a mesma resposta como se eles tivessem unsigned shortpromovido a unsigned. No entanto, o gcc às vezes otimiza essa função de maneiras que se comportariam sem sentido se ocorrer um estouro. Qualquer código em que alguma combinação de entradas possa causar um estouro deve ser processado com a -fwrapvopção, a menos que seja aceitável permitir que criadores de entrada malformada deliberadamente executem código arbitrário de sua escolha.

supercat
fonte
1

Por que não isso:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;
Sieunguoimay
fonte
Isso não executar o ...corpo do loop para factor = 1ou factor = 10, a apenas 100 e superior. Você precisaria descascar a primeira iteração e ainda começar factor = 1se quiser que isso funcione.
Peter Cordes
1

Existem muitas faces diferentes do comportamento indefinido e o aceitável depende do uso.

loop interno apertado que consome grande parte do tempo total da CPU em um aplicativo gráfico em tempo real

Isso, por si só, é um pouco incomum, mas, seja como for ... se esse for realmente o caso, o UB provavelmente estará dentro do domínio "permitido, aceitável" . A programação gráfica é notória por hacks e coisas feias. Desde que "funcione" e não demore mais que 16,6 ms para produzir um quadro, geralmente ninguém se importa. Mas, esteja ciente do que significa invocar o UB.

Primeiro, existe o padrão. Desse ponto de vista, não há nada para discutir e nenhuma maneira de justificar, seu código é simplesmente inválido. Não há ifs ou whens, apenas não é um código válido. Você também pode dizer que está com o dedo do meio levantado do seu ponto de vista e, em 95-99% das vezes, é bom que você vá.

Em seguida, há o lado do hardware. Existem algumas arquiteturas incomuns e estranhas , onde isso é um problema. Estou dizendo "incomum, estranho" porque, na única arquitetura que compõe 80% de todos os computadores (ou nas duas arquiteturas que juntas compõem 95% de todos os computadores), o estouro é um "sim, tanto faz, não importa" coisa no nível do hardware. Você com certeza consegue um resultado de lixo (embora ainda previsível), mas nada de ruim acontece.
Isso não éEm todas as arquiteturas, é bem possível que você fique preso em excesso (embora, vendo como você fala de um aplicativo gráfico, as chances de estar em uma arquitetura tão estranha sejam bastante pequenas). A portabilidade é um problema? Se for, você pode querer se abster.

Por último, existe o lado do compilador / otimizador. Uma razão pela qual o estouro é indefinido é que simplesmente deixá-lo como era mais fácil lidar com o hardware era uma vez. Mas outro motivo é que, por exemplo, x+1é garantido que sempre será maior que x, e o compilador / otimizador pode explorar esse conhecimento. Agora, no caso mencionado anteriormente, é sabido que os compiladores agem dessa maneira e simplesmente eliminam os blocos completos (existia uma exploração do Linux há alguns anos atrás, que se baseava no fato de o compilador ter retirado completamente algum código de validação por causa disso).
No seu caso, duvido seriamente que o compilador faça algumas otimizações especiais e ímpares. No entanto, o que você sabe, o que eu sei. Em caso de dúvida, experimente. Se funcionar, você está pronto para ir.

(E, finalmente, é claro que existe uma auditoria de código, você pode ter que perder seu tempo discutindo isso com um auditor, se tiver azar.)

Damon
fonte