Olá Habr! Apresento a você a tradução do artigo "Os ponteiros são complicados ou: o que há em um byte?" autoria de Ralf Jung.
Neste verão, eu estou trabalhando no Rust em tempo integral novamente, e vou trabalhar novamente (entre outras coisas) no “modelo de memória” para o Rust / MIR. No entanto, antes de falar sobre minhas idéias, finalmente preciso dissipar o mito de que "os ponteiros são simples: são apenas números". Ambas as partes desta declaração são errôneas, pelo menos em idiomas com recursos inseguros, como Rust ou C: os ponteiros não podem ser chamados de números primos ou (comuns).
Eu também gostaria de discutir a parte do modelo de memória que precisa ser tratada antes de podermos falar sobre as partes mais complexas: de que forma os dados são armazenados na memória? A memória consiste em bytes, unidades endereçáveis mínimas e os menores elementos que podem ser acessados (pelo menos na maioria das plataformas), mas quais são os possíveis valores de bytes? Mais uma vez, verifica-se que "é apenas um número de 8 bits" não é adequado como resposta.
Espero que, depois de ler este post, você concorde comigo em relação a ambas as declarações.
Ponteiros são complicados
Qual é o problema com "ponteiros são números regulares"? Vejamos o exemplo a seguir: (Eu uso C ++ aqui, uma vez que escrever código inseguro em C ++ é mais fácil do que escrever em Rust, e código inseguro é apenas o local onde os problemas aparecem. Rust inseguro e C têm os mesmos problemas que e C ++).
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; int i = ; auto x_ptr = &x[i]; *x_ptr = 23; return y[0]; }
Otimizar a última leitura de y [0] com um retorno de 42 é sempre muito benéfico. A lógica dessa otimização é que alterar x_ptr que aponta para x não pode alterar y.
No entanto, ao lidar com linguagens de baixo nível como C ++, podemos violar essa suposição atribuindo i o valor yx. Como & x [i] é o mesmo que x + i, escrevemos 23 em & y [0].
Obviamente, isso não impede que os compiladores C ++ realizem essas otimizações. Para resolver isso, o padrão diz que nosso código possui UB .
Primeiramente, não é permitido executar operações aritméticas em ponteiros (como no caso de & x [i]), se neste caso o ponteiro ultrapassar qualquer um dos limites da matriz . Nosso programa viola esta regra: x [i] vai além de x, então é UB. Em outras palavras, até o cálculo do valor x_ptr é UB, portanto, nem chegamos ao local em que queremos usar esse ponteiro.
(Acontece que i = yx também é UB, pois apenas os ponteiros apontando para a mesma alocação de memória podem ser subtraídos . No entanto, poderíamos escrever i = ((size_t) y - (size_t) x) / sizeof (int) para ignorar isso é uma limitação.)
Mas ainda não terminamos: essa regra tem a única exceção que podemos usar a nosso favor. Se a operação aritmética calcular o valor do ponteiro para o endereço exatamente após o final da matriz, tudo estará em ordem. (Essa exceção é necessária para calcular vec.end () para os loops mais comuns no C ++ 98.)
Vamos mudar um pouco o exemplo:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
Agora imagine que xey foram alocados um após o outro , com y tendo um endereço maior. Então x_ptr aponta para o início de y! Então a condição é verdadeira e a atribuição ocorre. Ao mesmo tempo, não há UB devido à saída do ponteiro para o exterior.
Parece que isso não permitirá otimização. No entanto, o padrão C ++ tem outro ás na manga para ajudar os criadores de compiladores: na verdade, ele não nos permite usar o x_ptr. De acordo com o que o padrão diz sobre como adicionar números aos ponteiros , x_ptr aponta para o endereço após o último elemento da matriz. Não aponta para um elemento específico de outro objeto, mesmo que eles tenham o mesmo endereço . (Pelo menos, essa é uma interpretação comum do padrão com base na qual o LLVM otimiza esse código .)
E mesmo que x_ptr e & y [0] aponte para o mesmo endereço , isso não os torna o mesmo ponteiro , ou seja, eles não podem ser usados de forma intercambiável: & y [0] aponta para o primeiro elemento de y; x_ptr aponta para o endereço após x. Se substituirmos * x_ptr = 23 pela string * & y [0] = 0, alteraremos o valor do programa, mesmo que os dois ponteiros tenham sido verificados quanto à igualdade.
Vale a pena repetir:
Só porque dois ponteiros apontam para o mesmo endereço não significa que eles são iguais e podem ser usados de forma intercambiável.
Sim, essa diferença é ilusória. De fato, isso ainda causa diferenças nos programas compilados com LLVM e GCC.
Observe também que essa regra única não é o único lugar no C / C ++ em que podemos observar esse efeito. Outro exemplo é a palavra-chave restringir em C, que pode ser usada para expressar que os ponteiros não se sobrepõem (não são iguais):
int foo(int *restrict x, int *restrict y) { *x = 42; if (x == y) { *y = 23; } return *x; } int test() { int x; return foo(&x, &x); }
A chamada test () chama UB, pois dois acessos à memória em foo não devem ocorrer no mesmo endereço. Substituindo * y por * x em foo, alteraremos o valor do programa e ele não chamará mais UB. Mais uma vez: embora x e y tenham o mesmo endereço, eles não podem ser usados de forma intercambiável.
Os ponteiros definitivamente não são apenas números.
Modelo de ponteiro simples
Então, o que é um ponteiro? Eu não sei a resposta completa. De fato, esta é uma área aberta para pesquisa.
Um ponto importante: aqui estamos olhando para um modelo de ponteiro abstrato . Obviamente, em um computador real, ponteiros são números. Mas um computador real não realiza as otimizações que os compiladores C ++ modernos fazem. Se escrevêssemos os programas acima no assembler, não haveria UB, nem otimizações. C ++ e Rust adotam uma abordagem mais "de nível superior" para memória e ponteiros, limitando o programador ao compilador. Quando é necessário descrever formalmente o que um programador pode ou não fazer nessas linguagens, o modelo de ponteiros como números é quebrado, por isso precisamos encontrar outra coisa. Este é outro exemplo de uso de uma "máquina virtual" diferente de um computador real para fins de especificação - uma ideia sobre a qual escrevi anteriormente .
Aqui está uma frase simples (de fato, este modelo de ponteiros é usado pelo CompCert e meu trabalho pela RustBelt , bem como a maneira como o interpretador miri implementa ponteiros ): um ponteiro é um par de algum ID que identifica exclusivamente uma área de memória (alocação) e o deslocamento é relativo a nesta área. Se você escrever isso em Rust:
struct Pointer { alloc_id: usize, offset: isize, }
As operações de adição (subtração) de um número a um ponteiro (de um ponteiro) afetam apenas o deslocamento e, portanto, o ponteiro nunca pode sair da área de memória. Subtrair ponteiros só é possível se eles pertencerem à mesma área de memória (de acordo com C ++ ).
(Como podemos ver, o padrão C ++ aplica essas regras a matrizes, não a áreas de memória. No entanto, o LLVM as aplica no nível da área .)
Acontece (e miri mostra a mesma coisa) que esse modelo pode nos servir bem. Sempre lembramos a que região da memória o ponteiro pertence, para que possamos distinguir o ponteiro único de uma região da memória do ponteiro para o início de outra região. Assim, miri pode achar que nosso segundo exemplo (com & x [8]) tem UB.
Nosso modelo está caindo aos pedaços
Em nosso modelo, os ponteiros, embora não sejam números, são pelo menos simples. No entanto, esse modelo começará a desmoronar diante de nossos olhos, assim que você se lembrar da conversão de ponteiros em números. Em miri, converter um ponteiro para um número realmente não faz nada, apenas obtemos uma variável numérica (ou seja, seu tipo diz que é um número) cujo valor é um ponteiro (ou seja, um par de área de memória e deslocamento). No entanto, multiplicar esse número por 2 leva a um erro, pois não está claro o que significa "multiplicar esse ponteiro abstrato por 2".
Devo esclarecer: essa não é uma boa solução quando se trata de definir a semântica de uma linguagem. No entanto, isso funciona bem para o intérprete. Essa é a abordagem mais simples, e a escolhemos porque não está claro como isso pode ser feito de outra forma (exceto para não oferecer suporte a essas reduções - mas com o suporte delas, o miri pode executar mais programas): em nossa máquina abstrata, não existe um "espaço de endereço" único, em que todas as áreas de memória alocadas estariam localizadas e todos os ponteiros foram mapeados para números diferentes específicos. Cada área de memória é identificada por um ID (oculto). Agora podemos começar a adicionar dados adicionais ao nosso modelo, como o endereço base de cada área de memória, e de alguma forma usá-lo para trazer o número de volta ao ponteiro ... e, nesse ponto, o processo se torna realmente muito complicado e, em qualquer caso, uma discussão sobre isso. Modelos não têm o objetivo de escrever uma postagem. Seu objetivo é discutir a necessidade desse modelo. Se você estiver interessado, recomendo que você leia este documento , que analisa mais de perto a idéia acima de adicionar um endereço base.
Em resumo, as projeções de ponteiros e números entre si são confusas e difíceis de determinar formalmente, dadas as otimizações discutidas acima. Existe um conflito entre a abordagem de alto nível necessária para otimizações e a abordagem de baixo nível necessária para descrever a conversão de indicadores para números e vice-versa. Na maioria das vezes, simplesmente ignoramos esse problema no miri e, sempre que possível, tentamos fazer o máximo possível usando o modelo simples com o qual trabalhamos. Uma definição completa de linguagens como C ++ ou Rust, é claro, não pode ser tão simples, deve explicar o que realmente está acontecendo. Até onde eu sei, não há solução adequada, mas a pesquisa acadêmica está se aproximando da verdade .
É por isso que os ponteiros também não são simples.
De ponteiros para bytes
Espero ter apresentado um argumento convincente de que os números não são o único tipo de dados a considerar se queremos descrever formalmente linguagens de baixo nível como C ++ ou a parte (insegura) do Rust. No entanto, isso significa que uma operação simples como ler um byte da memória não pode apenas retornar u8. Imagine que implementamos o memcpy lendo cada byte da origem em alguma variável local v e, em seguida, armazene esse valor no local de destino. Mas e se esse byte fizer parte de um ponteiro? Se o ponteiro for um par de ID de área de memória e deslocamento, qual será o seu primeiro byte? Precisamos dizer qual é o valor de v, portanto teremos que responder de alguma forma a essa pergunta. (E esse é um problema completamente diferente do problema da multiplicação, que estava na seção anterior. Apenas assumimos que existe algum tipo abstrato de Ponter.)
Não podemos representar o byte do ponteiro como um valor do intervalo 0..256 (nota: a seguir 0 é ativado, 256 não é). Em geral, se usarmos um modelo de representação de memória ingênuo, a parte extra "oculta" do ponteiro (a que o torna mais do que apenas um número) será perdida quando o ponteiro for gravado na memória e reler a partir dele. Teremos que corrigir isso e, para isso, teremos que expandir nosso conceito de "byte" para representar esse estado adicional. Portanto, o byte agora é o valor do intervalo 0..256 ("bits brutos") ou o enésimo byte de algum ponteiro abstrato. Se tivéssemos que implementar nosso modelo de memória no Rust, poderia ser assim:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
Por exemplo, PtrFragment (ptr, 0) representa o primeiro byte do ponteiro ptr. Assim, o memcpy pode "quebrar" o ponteiro em bytes separados que representam esse ponteiro na memória e copiá-los individualmente. Em uma arquitetura de 32 bits, a representação ptr completa conterá 4 bytes:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
Essa representação suporta todas as operações de movimentação de dados sobre ponteiros no nível de bytes, o que é suficiente para o memcry. Operações aritméticas ou de bits não são totalmente suportadas; como observado acima, isso exigiria uma representação mais complexa dos ponteiros.
Memória não inicializada
No entanto, ainda não concluímos nossa definição de "byte". Para descrever completamente o comportamento do programa, precisamos considerar outra opção: um byte na memória pode ser não inicializado . A última definição de byte terá esta aparência (suponha que tenhamos um tipo de ponteiro para ponteiros):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
Usamos o valor Uninit para todos os bytes na memória alocada na qual ainda não escrevemos nenhum valor. É possível ler a memória não inicializada sem problemas, mas quaisquer outras ações com esses bytes (por exemplo, aritmética numérica) levam ao UB.
Isso é muito semelhante às regras do LLVM com relação ao valor de veneno especial. Observe que o LLVM também possui um valor undef, que é usado para memória não inicializada e funciona de maneira um pouco diferente. No entanto, compilar nosso Uninit para undef está correto (undef é, de certa forma, "mais fraco"), e há sugestões para remover undef do LLVM e usar veneno .
Você pode se perguntar por que temos um valor Uninit especial. Por que não escolher um b: u8 arbitrário para cada novo byte e depois usar Bits (b) como valor inicial? Esta é realmente uma opção. No entanto, primeiro de tudo, todos os compiladores chegaram à abordagem usando um valor especial para memória não inicializada. Não seguir essa abordagem significa não apenas causar problemas de compilação por meio do LLVM, mas também revisar todas as otimizações e garantir que elas funcionem corretamente com esse modelo modificado. O ponto principal aqui: você sempre pode substituir com segurança o Uninit por qualquer outro valor: qualquer operação que receba esse valor, em qualquer caso, levará ao UB.
Por exemplo, esse código C é mais fácil de otimizar com o Uninit:
int test() { int x; if (condA()) x = 1;
Com o Uninit, podemos facilmente dizer que x tem um valor Uninit ou 1, e desde que a substituição do Uninit por 1 funciona, a otimização é facilmente explicada. Sem o Uninit, x é "algum tipo de padrão de bits arbitrário" ou 1, e a mesma otimização é mais difícil de explicar.
(Podemos argumentar que podemos trocar operações quando fazemos uma escolha não determinística, mas precisamos provar que o código difícil de analisar não usa x de forma alguma. O Uninit evita esse problema com evidências desnecessárias.)
Finalmente, o Uninit é a melhor escolha para intérpretes como miri. Esses intérpretes têm problemas com operações como “basta selecionar qualquer um desses valores” (ou seja, operações não determinísticas), pois tendem a percorrer todos os caminhos possíveis da execução do programa, o que significa que precisam tentar todos os valores possíveis. Usar Uninit em vez de um padrão de bits arbitrário significa que o miri pode informar após um programa ser executado se seu programa usa valores não inicializados incorretamente.
Conclusão
Vimos que em linguagens como C ++ e Rust (ao contrário de computadores reais) os ponteiros podem ser diferentes, mesmo que apontem para o mesmo endereço, e que um byte seja mais do que apenas um número no intervalo de 0 a 255. Portanto, se em 1978 a linguagem C poderia ser "assembler portátil", agora é uma afirmação incrivelmente errônea.