Hola Habr! Le presento la traducción del artículo "Los punteros son complicados o: ¿qué hay en un byte?" autoría de Ralf Jung.
Este verano estoy trabajando en Rust a tiempo completo nuevamente, y nuevamente (entre otras cosas) trabajaré en un "modelo de memoria" para Rust / MIR. Sin embargo, antes de hablar sobre mis ideas, finalmente debo disipar el mito de que "los punteros son simples: son solo números". Ambas partes de esta declaración son erróneas, al menos en lenguajes con características inseguras, como Rust o C: los punteros no se pueden llamar números primos o (ordinarios).
También me gustaría discutir la parte del modelo de memoria que debe abordarse antes de que podamos hablar sobre las partes más complejas: ¿ de qué forma se almacenan los datos en la memoria? Una memoria consta de bytes, unidades direccionables mínimas y los elementos más pequeños a los que se puede acceder (al menos en la mayoría de las plataformas), pero ¿cuáles son los posibles valores de bytes? Nuevamente, resulta que "es solo un número de 8 bits" no es adecuado como respuesta.
Espero que después de leer esta publicación, estén de acuerdo conmigo con respecto a ambas declaraciones.
Los punteros son complicados
¿Cuál es el problema con "los punteros son números regulares"? Veamos el siguiente ejemplo: (Aquí uso C ++, ya que escribir código inseguro en C ++ es más fácil que escribir en Rust, y el código inseguro es el lugar donde aparecen los problemas. Rust inseguro y C tienen los mismos problemas que y 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]; }
Optimizar la última lectura de y [0] con un retorno de 42 siempre es muy beneficioso. La razón de esta optimización es que cambiar x_ptr que apunta a x no puede cambiar y.
Sin embargo, cuando se trata de lenguajes de bajo nivel como C ++, podemos violar esta suposición asignando i el valor yx. Como & x [i] es lo mismo que x + i, escribimos 23 en & y [0].
Por supuesto, esto no impide que los compiladores de C ++ hagan tales optimizaciones. Para resolver esto, el estándar dice que nuestro código tiene UB .
En primer lugar, no está permitido realizar operaciones aritméticas en punteros (como en el caso de & x [i]), si en este caso el puntero va más allá de cualquiera de los límites de la matriz . Nuestro programa viola esta regla: x [i] va más allá de x, por lo que es UB. En otras palabras, incluso calcular el valor x_ptr es UB, por lo que ni siquiera llegamos al lugar donde queremos usar este puntero.
(Resulta que i = yx también es UB, ya que solo se pueden restar los punteros que apuntan a la misma asignación de memoria . Sin embargo, podríamos escribir i = ((size_t) y - (size_t) x) / sizeof (int) para omitir esto es una limitación)
Pero aún no hemos terminado: esta regla tiene la única excepción que podemos usar para nuestro beneficio. Si la operación aritmética calcula el valor del puntero a la dirección exactamente después del final de la matriz, entonces todo está en orden. (Esta excepción es necesaria para calcular vec.end () para los bucles más comunes en C ++ 98.)
Cambiemos un poco el ejemplo:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
Ahora imagine que x e y fueron asignados uno tras otro , con y teniendo una dirección más grande. Entonces x_ptr apunta al comienzo de y! Entonces la condición es verdadera y ocurre la asignación. Al mismo tiempo, no hay UB debido a la salida del puntero al extranjero.
Parece que esto no permitirá la optimización. Sin embargo, el estándar C ++ tiene otro as bajo la manga para ayudar a los creadores del compilador: de hecho, no nos permite usar x_ptr. De acuerdo con lo que dice el estándar sobre agregar números a los punteros , x_ptr apunta a la dirección después del último elemento de la matriz. No apunta a un elemento específico de otro objeto, incluso si tienen la misma dirección . (Al menos, esta es una interpretación común del estándar basado en el cual LLVM optimiza este código ).
Y aunque x_ptr e & y [0] apuntan a la misma dirección , esto no los convierte en el mismo puntero , es decir, no pueden usarse indistintamente: & y [0] apunta al primer elemento de y; x_ptr apunta a la dirección después de x. Si reemplazamos * x_ptr = 23 con la cadena * & y [0] = 0, cambiaremos el valor del programa, aunque se haya verificado la igualdad de los dos punteros.
Vale la pena repetir esto:
El hecho de que dos punteros apunten a la misma dirección no significa que sean iguales y se puedan usar indistintamente.
Sí, esta diferencia es esquiva. De hecho, esto todavía causa diferencias en los programas compilados con LLVM y GCC.
También tenga en cuenta que esta regla de uno después no es el único lugar en C / C ++ donde podemos observar dicho efecto. Otro ejemplo es la palabra clave restringir en C, que se puede usar para expresar que los punteros no se superponen (no son iguales):
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); }
La llamada test () llama a UB, ya que dos accesos de memoria en foo no deberían ocurrir en la misma dirección. Reemplazando * y con * x en foo, cambiaremos el valor del programa y ya no llamará a UB. Una vez más: aunque x e y tienen la misma dirección, no se pueden usar indistintamente.
Los punteros definitivamente no son solo números.
Modelo de puntero simple
Entonces, ¿qué es un puntero? No sé la respuesta completa. De hecho, esta es un área abierta para la investigación.
Un punto importante: aquí estamos viendo un modelo de puntero abstracto . Por supuesto, en una computadora real, los punteros son números. Pero una computadora real no lleva a cabo las optimizaciones que hacen los compiladores de C ++ modernos. Si escribiéramos los programas anteriores en ensamblador, entonces no habría UB, ni optimizaciones. C ++ y Rust adoptan un enfoque más de "nivel superior" para la memoria y los punteros, limitando el programador al compilador. Cuando es necesario describir formalmente lo que un programador puede y no puede hacer en estos lenguajes, el modelo de punteros como números se rompe, por lo que necesitamos encontrar algo más. Este es otro ejemplo del uso de una "máquina virtual" diferente de una computadora real para fines de especificación, una idea sobre la que escribí anteriormente .
Aquí hay una oración simple (de hecho, este modelo de punteros es utilizado por CompCert y mi trabajo por RustBelt , así como la forma en que el intérprete miri implementa los punteros ): un puntero es un par de alguna ID que identifica de forma única un área de memoria (asignación), y el desplazamiento es relativo a esta zona Si escribes esto en Rust:
struct Pointer { alloc_id: usize, offset: isize, }
Las operaciones de sumar (restar) un número a un puntero (de un puntero) afectan solo el desplazamiento y, por lo tanto, el puntero nunca puede abandonar el área de memoria. Restar punteros solo es posible si pertenecen a la misma área de memoria (de acuerdo con C ++ ).
(Como podemos ver, el estándar C ++ aplica estas reglas a las matrices, no a las áreas de memoria. Sin embargo, LLVM las aplica a nivel de área ).
Resulta (y miri muestra lo mismo) que este modelo nos puede servir bien. Siempre recordamos a qué región de memoria pertenece el puntero, por lo que podemos distinguir el puntero de una región de memoria del puntero al comienzo de otra región. Por lo tanto, miri puede encontrar que nuestro segundo ejemplo (con & x [8]) tiene UB.
Nuestro modelo se está desmoronando
En nuestro modelo, los punteros, aunque no son números, son al menos simples. Sin embargo, este modelo comenzará a desmoronarse ante nuestros ojos, tan pronto como recuerde la conversión de punteros a números. En miri, lanzar un puntero a un número en realidad no hace nada, solo obtenemos una variable numérica (es decir, su tipo dice que es un número) cuyo valor es un puntero (es decir, un par de área de memoria y desplazamiento). Sin embargo, multiplicar este número por 2 conduce a un error, ya que no está completamente claro lo que significa "multiplicar un puntero abstracto de este tipo por 2".
Debo aclarar: esta no es una buena solución cuando se trata de definir la semántica de un lenguaje. Sin embargo, esto funciona bien para el intérprete. Este es el enfoque más simple, y lo elegimos porque no está claro cómo se puede hacer de otra manera (excepto para no admitir tales reducciones en absoluto, pero con su soporte miri puede ejecutar más programas): en nuestra máquina abstracta no hay un solo "espacio de direcciones", en el que se ubicarían todas las áreas de memoria asignadas, y todos los punteros se asignaron a números diferentes específicos. Cada área de memoria se identifica mediante una ID (oculta). Ahora podemos comenzar a agregar datos adicionales a nuestro modelo, como la dirección de base para cada área de memoria, y de alguna manera usarlo para devolver el número al puntero ... y en este punto el proceso se vuelve realmente muy complicado y, en cualquier caso, una discusión sobre esto Los modelos no tienen el propósito de escribir una publicación. Su propósito es discutir la necesidad de tal modelo. Si está interesado, le recomiendo que lea este documento , que analiza más de cerca la idea anterior de agregar una dirección base.
En resumen, los modelos de punteros y números entre sí son confusos y difíciles de determinar formalmente, dadas las optimizaciones discutidas anteriormente. Existe un conflicto entre el enfoque de alto nivel necesario para las optimizaciones y el enfoque de bajo nivel necesario para describir los indicadores de conversión a números y viceversa. En su mayor parte, simplemente ignoramos este problema en miri y, siempre que sea posible, intentamos hacer todo lo posible utilizando el modelo simple con el que trabajamos. Una definición completa de lenguajes como C ++ o Rust, por supuesto, no puede ser tan simple, debería explicar lo que realmente está sucediendo. Hasta donde yo sé, no hay una solución adecuada, pero la investigación académica se está acercando a la verdad .
Es por eso que los punteros tampoco son simples.
De punteros a bytes
Espero haber hecho un argumento razonablemente convincente de que los números no son el único tipo de datos a considerar si queremos describir formalmente lenguajes de bajo nivel como C ++ o la parte (insegura) de Rust. Sin embargo, esto significa que una operación simple como leer un byte de la memoria no puede devolver u8. Imagine que implementamos memcpy leyendo cada byte de la fuente a su vez en alguna variable local v, y luego almacenamos este valor en la ubicación de destino. Pero, ¿qué pasa si este byte es parte de un puntero? Si el puntero es un par de ID de área de memoria y desplazamiento, ¿cuál será su primer byte? Necesitamos decir cuál es el valor de v, por lo que tendremos que responder de alguna manera a esta pregunta. (Y este es un problema completamente diferente al problema con la multiplicación, que estaba en la sección anterior. Simplemente asumimos que hay algún tipo abstracto de Ponter).
No podemos representar el byte del puntero como un valor del rango 0..256 (nota: en adelante 0 está activado, 256 no lo está). En general, si usamos un modelo de representación de memoria ingenuo, la parte extra "oculta" del puntero (la que lo hace más que un simple número) se perderá cuando el puntero se escriba en la memoria y se vuelva a leer. Tendremos que arreglar esto, y para esto tendremos que expandir nuestro concepto de "byte" para representar este estado adicional. Por lo tanto, el byte es ahora el valor del rango 0..256 ("bits en bruto") o el enésimo byte de algún puntero abstracto. Si tuviéramos que implementar nuestro modelo de memoria en Rust, podría verse así:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
Por ejemplo, PtrFragment (ptr, 0) representa el primer byte del puntero ptr. Por lo tanto, memcpy puede "dividir" el puntero en bytes separados que representan este puntero en la memoria y copiarlos individualmente. En una arquitectura de 32 bits, la representación ptr completa contendrá 4 bytes:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
Esta representación admite todas las operaciones de mover datos sobre punteros a nivel de byte, lo cual es suficiente para memcry. Las operaciones aritméticas o de bits no son totalmente compatibles; como se señaló anteriormente, esto requeriría una representación más compleja de punteros.
Memoria no inicializada
Sin embargo, no hemos terminado con nuestra definición de "byte". Para describir completamente el comportamiento del programa, debemos considerar otra opción: un byte en la memoria puede no ser inicializado . La última definición de byte se verá así (supongamos que tenemos un tipo de puntero para punteros):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
Usamos el valor Uninit para todos los bytes en la memoria asignada en la que aún no hemos escrito ningún valor. Es posible leer la memoria no inicializada sin problemas, pero cualquier otra acción con estos bytes (por ejemplo, aritmética numérica) conduce a UB.
Esto es muy similar a las reglas de LLVM con respecto al valor de veneno especial. Tenga en cuenta que LLVM también tiene un valor undef, que se utiliza para la memoria no inicializada y funciona de manera un poco diferente. Sin embargo, compilar nuestro Uninit en undef es correcto (undef es de alguna manera "más débil"), y hay sugerencias para eliminar undef de LLVM y usar veneno en su lugar .
Quizás se pregunte por qué tenemos un valor especial de Uninit. ¿Por qué no elegir algunos b: u8 arbitrarios para cada nuevo byte y luego usar Bits (b) como valor inicial? Esta es realmente una opción. Sin embargo, en primer lugar, todos los compiladores llegaron al enfoque utilizando un valor especial para la memoria no inicializada. No seguir este enfoque significa no solo causar problemas de compilación a través de LLVM, sino también revisar todas las optimizaciones y asegurarse de que funcionen correctamente con este modelo modificado. El punto clave aquí: siempre puede reemplazar Uninit de forma segura con cualquier otro valor: cualquier operación que reciba este valor en cualquier caso conducirá a UB.
Por ejemplo, este código C es más fácil de optimizar con Uninit:
int test() { int x; if (condA()) x = 1;
Con Uninit, podemos decir fácilmente que x tiene un valor de Uninit o un valor de 1, y dado que reemplazar Uninit con 1 funciona, la optimización se explica fácilmente. Sin Uninit, x es "algún tipo de patrón de bits arbitrario" o 1, y la misma optimización es más difícil de explicar.
(Podemos argumentar que podemos intercambiar operaciones cuando hacemos una elección no determinista, pero luego tendremos que demostrar que el código que es difícil de analizar no usa x de ninguna manera. Uninit evita este problema con evidencia innecesaria).
Finalmente, Uninit es la mejor opción para intérpretes como miri. Dichos intérpretes tienen problemas con operaciones como "simplemente seleccione cualquiera de estos valores" (es decir, operaciones no deterministas), ya que tienden a recorrer todas las rutas posibles de ejecución del programa, lo que significa que necesitan probar todos los valores posibles. El uso de Uninit en lugar de un patrón de bits arbitrario significa que miri puede decirle después de la ejecución de un programa si su programa usa valores no inicializados incorrectamente.
Conclusión
Vimos que en lenguajes como C ++ y Rust (a diferencia de las computadoras reales) los punteros pueden ser diferentes incluso si apuntan a la misma dirección, y que un byte es más que solo un número en el rango 0..256. Por lo tanto, si en 1978 el lenguaje C podría ser "ensamblador portátil", ahora es una declaración increíblemente errónea.