É seguro ler além do final de um buffer na mesma página em x86 e x64?

Muitos methods encontrados em algoritmos de alto desempenho poderiam ser (e são) simplificados se tivessem permissão para ler uma pequena quantidade após o fim dos buffers de input. Aqui, “pequena quantidade” geralmente significa até W - 1 bytes após o final, onde W é o tamanho da palavra em bytes do algoritmo (por exemplo, até 7 bytes para um algoritmo processando a input em blocos de 64 bits).

É claro que escrever antes do final de um buffer de input nunca é seguro, em geral, já que você pode estragar os dados além do buffer 1 . Também está claro que a leitura após o final de um buffer em outra página pode desencadear uma falha de segmentação / violação de access, uma vez que a próxima página pode não ser legível.

No caso especial de ler valores alinhados, no entanto, uma falha de página parece impossível, pelo menos no x86. Nessa plataforma, as páginas (e portanto os sinalizadores de proteção de memory) têm uma granularidade 4K (páginas maiores, por exemplo, 2MiB ou 1GiB, são possíveis, mas são múltiplos de 4K) e as leituras alinhadas só acessam bytes na mesma página que a válida parte do buffer.

Aqui está um exemplo canônico de algum loop que alinha sua input e lê até 7 bytes após o final do buffer:

 int processBytes(uint8_t *input, size_t size) { uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size); int res; if (size = 0) { return input + res; } // align pointer to the next 8-byte boundary input64 = (ptrdiff_t)(input64 + 1) & ~0x7; for (; input64  0) { return input + res < input + size ? input + res : -1; } } return -1; } 

A function interna int match(uint64_t bytes) não é mostrada, mas é algo que procura por um byte que corresponda a um determinado padrão, e retorna a menor posição (0-7) se encontrada ou -1 caso contrário.

Primeiro, os casos com tamanho <8 são penhorados para outra função pela simplicidade de exposição. Em seguida, uma única verificação é feita para os primeiros 8 (bytes desalinhados). Em seguida, um loop é feito para o bloco restante floor((size - 7) / 8) blocos de 8 bytes 2 . Esse loop pode ler até 7 bytes após o final do buffer (o caso de 7 bytes ocorre quando a input & 0xF == 1 ). No entanto, a chamada de retorno tem um cheque que exclui quaisquer correspondências falsas que ocorram além do final do buffer.

Praticamente falando, essa function é tão segura em x86 e x86-64?

Esses tipos de overreads são comuns no código de alto desempenho. Código de cauda especial para evitar tais overreads também é comum. Às vezes você vê o último tipo substituindo o primeiro para silenciar ferramentas como valgrind. Às vezes você vê uma proposta para fazer tal substituição, que é rejeitada com base em que o idioma é seguro e a ferramenta está errada (ou simplesmente muito conservadora) 3 .

Uma nota para advogados de idiomas:

Ler de um ponteiro além de seu tamanho alocado definitivamente não é permitido no padrão. Eu aprecio as respostas de um advogado de idiomas, e até mesmo ocasionalmente as escrevo, e eu até fico feliz quando alguém desenterra o capítulo e o verso que mostra que o código acima é um comportamento indefinido e, portanto, não seguro no sentido mais estrito os detalhes aqui). No final das contas, não é isso que eu estou procurando. Como uma questão prática, muitos idiomas comuns envolvendo conversão de pointers, estrutura de access através de tais pointers e, portanto, são tecnicamente indefinidos, mas são difundidos em código de alta qualidade e alto desempenho. Muitas vezes não há alternativa, ou a alternativa é executada a metade da velocidade ou menos.

Se desejar, considere uma versão modificada desta pergunta, que é:

Depois que o código acima foi compilado para o assembly x86 / x86-64, e o usuário verificou que ele é compilado da maneira esperada (ou seja, o compilador não usou um access provável parcialmente fora dos limites para fazer algo realmente inteligente , está executando o programa compilado seguro?

A esse respeito, essa questão é uma pergunta C e uma questão de assembly x86. A maior parte do código usando este truque que eu vi está escrito em C, e C ainda é a linguagem dominante para bibliotecas de alto desempenho, facilmente eclipsando coisas de baixo nível como asm, e coisas de nível mais alto como . Pelo menos fora do nicho numérico onde o FORTRAN ainda joga bola. Então eu estou interessado na visão C-compilador-e-abaixo da questão, e é por isso que eu não a formulei como uma questão de assembly x86 pura.

Tudo o que disse, enquanto eu estou apenas moderadamente interessado em um link para o padrão mostrando isso é UD, estou muito interessado em quaisquer detalhes de implementações reais que podem usar este UD particular para produzir código inesperado. Agora, não acho que isso possa acontecer sem uma profunda análise cruzada profunda, mas o excesso de gcc surpreendeu muita gente também …


1 Mesmo em casos aparentemente inofensivos, por exemplo, onde o mesmo valor é gravado, ele pode quebrar o código concorrente .

2 Nota para esta sobreposição de trabalho requer que esta function e function match() se comporte de uma forma idempotente específica – em particular que o valor de retorno suporta verificações sobrepostas. Portanto, um “padrão de correspondência de primeiro byte” funciona, pois todas as chamadas match() ainda estão em ordem. No entanto, um método de “contagem de padrões de correspondência de bytes” não funcionaria, pois alguns bytes poderiam ser contados duas vezes. Como um aparte: algumas funções como “retornar o byte mínimo” funcionariam mesmo sem a restrição em ordem, mas precisariam examinar todos os bytes.

3 Vale a pena notar aqui que, para o Memcheck de valgrind, há uma flag --partial-loads-ok que controla se tais leituras são de fato relatadas como um erro. O padrão é sim , significa que em geral tais cargas não são tratadas como erros imediatos, mas é feito um esforço para rastrear o uso subseqüente de bytes carregados, alguns dos quais são válidos e outros não, com um erro sendo sinalizado se os bytes fora do intervalo forem usados . Em casos como o exemplo acima, em que toda a palavra é acessada em match() , essa análise concluirá que os bytes são acessados, mesmo que os resultados sejam descartados. Valgrind não pode em geral determinar se bytes inválidos de uma carga parcial são realmente usados ​​(e a detecção em geral é provavelmente muito difícil).

Sim, é seguro em x86 asm e implementações libc strlen(3) tiram proveito disso.

Também é seguro em C compilado para x86, até onde eu sei. Ler fora de um object é, obviamente, Undefined Behavior em C, mas é bem definido para C-targeting-x86. Eu acho que não é o tipo de UB que os compiladores agressivos assumirão que não pode acontecer durante a otimização , mas a confirmação de um compilador-writer nesse ponto seria boa, especialmente para casos em que é facilmente provavel em tempo de compilation que um access se apaga do passado o fim de um object. (Veja a discussão nos comentários com @RossRidge: uma versão anterior desta resposta afirmava que era absolutamente seguro, mas esse post no blog do LLVM realmente não lia dessa forma).

Os dados que você recebe são lixo imprevisível, mas não haverá outros efeitos colaterais em potencial. Contanto que o seu programa não seja afetado pelos bytes de lixo, tudo bem. (por exemplo, use bithacks para descobrir se um dos bytes de um uint64_t é zero e , em seguida, um loop de bytes para encontrar o primeiro byte zero, independentemente do lixo que esteja além dele.)


Da mesma forma, a criação de pointers desalinhados com uma conversão é UB no padrão C (mesmo que você não os desreferencie). É bem definido em todos os compiladores C conhecidos ao direcionar x86. Os intrínsicos de SSE da Intel exigem isso; Por exemplo, __m128i _mm_loadu_si128 (__m128i const* mem_addr) pega um ponteiro para um __m128i 16 bytes __m128i .

(Para o AVX512, eles finalmente mudaram essa opção de design inconveniente para void* para novos intrínsecos como __m512i _mm512_loadu_si512 (void const* mem_addr) ).

Mesmo desreferenciando um uint64_t* ou int* não alinhado é seguro (e tem comportamento bem definido) em C compilado para x86. No entanto, desreferenciar um __m128i* diretamente (em vez de usar intrinsics de load / store) usará movdqa , que falha em pointers não alinhados.


Normalmente, loops como esse evitam tocar em nenhuma linha de cache extra que eles não precisem tocar, não apenas páginas, por motivos de desempenho.

É extremamente improvável que houvesse registradores de E / S mapeados na memory na mesma página que um buffer que você desejasse fazer um loop com cargas largas, ou especialmente a mesma linha de cache de 64B, mesmo se estiver chamando funções como essa de um driver de dispositivo (ou um programa de espaço do usuário como um servidor X que mapeou algum espaço MMIO).

Se você estiver processando um buffer de 60 bytes e precisar evitar a leitura de um registro MMIO de 4 bytes, você saberá disso. Esse tipo de situação não acontece no código normal.


strlen é o exemplo canônico de um loop que processa um buffer de comprimento implícito e, portanto, não pode vetorizar sem ler além do final de um buffer. Se você precisar evitar a leitura após o byte 0 final, você poderá ler apenas um byte de cada vez.

Por exemplo, a implementação da glibc usa um prólogo para manipular dados até o primeiro limite de alinhamento de 64B. Em seguida, no loop principal (link gitweb para a origem asm) , ele carrega toda a linha de cache de 64B usando quatro cargas alinhadas SSE2. Ele os funde para um vetor com pminub (min de bytes não assinados), então o vetor final terá um elemento zero somente se qualquer um dos quatro vetores tiver um zero. Depois de descobrir que o final da string estava em algum lugar naquela linha de cache, ele verifica novamente cada um dos quatro vetores separadamente para ver onde. (Usando o pcmpeqb típico contra um vetor de all-zero, e pmovmskb / bsf para encontrar a posição dentro do vetor.) Glibc costumava ter um par de strlen estratégias diferentes para escolher , mas o atual é bom em todos os x86-64 CPUs.


Carregar 64B de cada vez, é claro, apenas seguro de um ponteiro alinhado com 64B, uma vez que os accesss naturalmente alinhados não podem cruzar os limites da linha de cache ou da linha de página .


Se você souber o comprimento de um buffer antes do tempo, poderá evitar a leitura após o final manipulando os bytes além do último vetor alinhado usando um carregamento não alinhado que termina no último byte do buffer. (Novamente, isso só funciona com algoritmos idempotentes, como memcpy, que não se importam se eles fazem sobreposição de armazenamentos no destino. Geralmente, os algoritmos modificados no local não podem fazer isso, exceto com algo como converter uma cadeia de caracteres em superior. caso com SSE2 , onde não há problema em reprocessar dados que já foram atualizados, além do bloqueio de encaminhamento de loja, se você fizer um carregamento não alinhado que se sobreponha ao último armazenamento alinhado.)

Se você permitir a consideração de dispositivos sem CPU, um exemplo de uma operação potencialmente insegura é acessar regiões fora do limite de páginas de memory mapeadas por PCI . Não há garantia de que o dispositivo de destino esteja usando o mesmo tamanho ou alinhamento de página que o subsistema de memory principal. Tentar acessar, por exemplo, o endereço [cpu page base]+0x800 pode acionar uma falha na página do dispositivo se o dispositivo estiver em um modo de página de 2 KiB. Isso geralmente causará uma verificação de bug no sistema.