Su computadora no es una versi贸n r谩pida de PDP-11
Hola Habr!
Mi nombre es Anton Dovgal, soy desarrollador C (y no solo) en Badoo.
Me encontr茅 con un art铆culo de David Chiznell, investigador de la Universidad de Cambridge, en el que cuestiona la opini贸n generalmente aceptada de que el C es un lenguaje de bajo nivel, y sus argumentos me parecieron lo suficientemente interesantes.
A la luz de las vulnerabilidades descubiertas recientemente,
Meltdown y Spectre deber铆an tomarse el tiempo para descubrir las razones de su aparici贸n. Ambas vulnerabilidades explotaron la ejecuci贸n especulativa de instrucciones por parte de los procesadores y permitieron que un atacante recibiera resultados a trav茅s de canales de terceros. Se agregaron vulnerabilidades en los procesadores, junto con varios otros, para que los programadores de C contin煤en creyendo que programan en un lenguaje de bajo nivel, aunque este no ha sido el caso durante d茅cadas.
Los fabricantes de procesadores no est谩n solos en esto. Los desarrolladores del compilador C / C ++ tambi茅n han contribuido.
驴Qu茅 es un lenguaje de bajo nivel?
El inform谩tico estadounidense y primer ganador del Premio Turing, Alan Perlis, dio la siguiente definici贸n:
"Un lenguaje de programaci贸n es de bajo nivel si los programas escritos en 茅l requieren atenci贸n a lo no esencial".
Aunque esta definici贸n se refiere a C, no proporciona una comprensi贸n de lo que la gente quiere ver en un lenguaje de bajo nivel. Varias propiedades hacen que las personas consideren que el idioma es bajo. Imagine una escala de lenguajes de programaci贸n con ensamblador en un extremo y una interfaz para una computadora Enterprise en el otro. Los idiomas de bajo nivel est谩n m谩s cerca del hierro, mientras que los idiomas de alto nivel est谩n m谩s cerca de c贸mo piensan las personas.
Para estar "m谩s cerca del hardware", el lenguaje debe proporcionar abstracciones que coincidan con las abstracciones de la plataforma de destino. Es f谩cil demostrar que C era un lenguaje de bajo nivel en PDP-11. La ejecuci贸n secuencial de programas, un espacio de direcciones planas, incluso operadores de pre y post incremento, se adapta perfectamente a los modos de direccionamiento PDP-11.
Emuladores r谩pidos de PDP-11
La raz贸n clave de las vulnerabilidades de Spectre y Meltdown es que los creadores de los procesadores no solo fabricaron procesadores r谩pidos, sino que tambi茅n hicieron procesadores r谩pidos con la interfaz PDP-11. Esto es importante porque permite a los programadores de C seguir creyendo que su lenguaje est谩 cerca del hardware.
El c贸digo C proporciona un aut贸mata abstracto secuencial en su mayor铆a (hasta C11, es completamente secuencial, si se excluyen las extensiones no est谩ndar). Crear un nuevo hilo es una llamada a una funci贸n de biblioteca, una operaci贸n que es bastante costosa. Por lo tanto, los procesadores, que desean continuar ejecutando el c贸digo C, conf铆an en el paralelismo de nivel de instrucci贸n (ILP). Analizan las operaciones vecinas y realizan operaciones independientes en paralelo. Esto complica enormemente los procesadores y conduce a un mayor consumo de energ铆a, pero permite que los programadores escriban principalmente c贸digo secuencial. En contraste, los procesadores gr谩ficos (GPU) logran un alto rendimiento de otra manera: requieren escribir programas paralelos.
La alta concurrencia en el nivel de comando es la causa directa de Spectre y Meltdown. El procesador Intel moderno ejecuta hasta 180 instrucciones simult谩neamente (a diferencia de la m谩quina abstracta C secuencial, que espera que la instrucci贸n anterior se ejecute antes de que comience la siguiente). Una heur铆stica t铆pica del c贸digo C muestra que hay una rama en promedio por cada siete instrucciones. Si desea mantener completa la canalizaci贸n de instrucciones, debe adivinar las siguientes 25 ramas. Esto, a su vez, agrega complejidad: el procesador primero calcula la rama adivinada incorrectamente y luego arroja los resultados de los c谩lculos, lo que afecta negativamente el consumo de energ铆a. Estos datos arrojados tienen resultados indirectos visibles, que se utilizaron en los ataques Spectre y Meltdown.
Cambiar el nombre de los registros consume mucha energ铆a y 谩rea de chips en los procesadores modernos. No se puede apagar o reducir su consumo de energ铆a, lo que lo hace inconveniente en la era del
silicio oscuro , cuando los transistores son bajos, pero los transistores involucrados son un recurso valioso. Este dispositivo est谩 ausente en la GPU, donde la concurrencia se logra mediante el uso de subprocesos en lugar de intentar ejecutar en paralelo c贸digo inicialmente secuencial. Si las instrucciones no tienen dependencias que deban reconstruirse, entonces tampoco es necesario cambiar el nombre de los registros.
Considere otra parte fundamental del dise帽o de C: memoria plana. No ha existido en un par de d茅cadas. Un procesador moderno a menudo tiene tres niveles de almacenamiento en cach茅 entre registros y memoria principal, lo que reduce el tiempo que lleva acceder a este 煤ltimo.
El cach茅 est谩 oculto para el programador y, por lo tanto, es inaccesible desde C. El uso efectivo del cach茅 es una de las formas de acelerar la ejecuci贸n del c贸digo en un procesador moderno, sin embargo, est谩 completamente oculto de la m谩quina abstracta y los programadores se ven obligados a confiar en el conocimiento de los detalles de la implementaci贸n del cach茅 (por ejemplo, que dos alineados de 64 bits los valores pueden aparecer en una l铆nea de la cach茅) para escribir c贸digo eficiente.
Optimizaci贸n C
Una de las caracter铆sticas comunes atribuidas a los lenguajes de bajo nivel es la velocidad. En particular, deber铆an ser f谩ciles de traducir a c贸digo r谩pido sin un compilador complicado. Los defensores de C a menudo ignoran el argumento de que un compilador lo suficientemente inteligente puede acelerar el lenguaje cuando hablan de otros lenguajes.
Desafortunadamente, usando una traducci贸n simple, no puede obtener un c贸digo r谩pido de C.
Los arquitectos de procesadores hacen esfuerzos heroicos para crear chips que puedan ejecutar c贸digo C r谩pidamente. Pero los niveles de rendimiento que los programadores esperan ver se logran solo con la ayuda de optimizaciones incre铆blemente complejas realizadas por el compilador.
El compilador de Clang (incluidas las partes correspondientes de LLVM) tiene aproximadamente 2 millones de l铆neas de c贸digo. Para el an谩lisis y la transformaci贸n del c贸digo, que son necesarios para acelerar C, se necesitan alrededor de 200,000 l铆neas de c贸digo (excluyendo comentarios y l铆neas en blanco).
Por ejemplo, para procesar una gran cantidad de datos en C, debe escribir un bucle que procese cada elemento secuencialmente. Para la ejecuci贸n 贸ptima de este ciclo en un procesador moderno, el compilador debe determinar que las iteraciones del ciclo son independientes entre s铆. La palabra clave restrictiva puede ayudar en este caso: asegura que las escrituras en un puntero no interferir谩n con la lectura de otro puntero. Esta informaci贸n en C es mucho m谩s limitada que en un lenguaje como Fortran, que es la raz贸n principal por la que C no pudo sacarla de la inform谩tica de alto rendimiento.
Despu茅s de que el compilador determina que las iteraciones son independientes entre s铆, el siguiente paso es un intento de vectorizar el resultado, porque el rendimiento de los procesadores modernos es de cuatro a ocho veces mayor para el c贸digo vectorizado que para el c贸digo escalar. Un lenguaje de bajo nivel para tales procesadores tendr铆a sus propios tipos de vectores de longitud arbitraria. Tales tipos est谩n presentes en la representaci贸n LLVM intermedia, porque siempre es m谩s f谩cil dividir operaciones grandes con vectores en varias peque帽as que construir operaciones vectoriales m谩s grandes.
En este punto, los optimizadores tienen que lidiar con las reglas de memoria C. C asegura que las estructuras con el mismo prefijo se puedan usar indistintamente y proporciona acceso a campos de estructuras de campo compensado en el lenguaje. Esto significa que el compilador no puede cambiar el orden de los campos en la estructura o agregar una alineaci贸n para mejorar la vectorizaci贸n (por ejemplo, transformar una estructura de matrices en una matriz de estructuras o viceversa). Esto generalmente no es un problema en lenguajes de bajo nivel, donde es posible controlar la ubicaci贸n de los campos en la estructura, pero hace que la tarea de acelerar C. sea m谩s dif铆cil.
C tambi茅n requiere alineaci贸n al final de la estructura, ya que asegura que no haya alineaci贸n en las matrices. La alineaci贸n es una parte bastante compleja de la especificaci贸n C, que interact煤a pobremente con otras partes del lenguaje. Por ejemplo, deber铆a poder comparar dos estructuras utilizando el m茅todo de comparaci贸n sin tipo (es decir, la funci贸n memcmp ()), por lo que la copia de la estructura tambi茅n debe estar alineada. En algunos casos, copiar la alineaci贸n lleva un tiempo considerable.
Considere las dos optimizaciones b谩sicas que produce el compilador de C:
SROA (reemplazo escalar de agregados, reemplazo escalar de agregados) y
apertura de bucle .
SROA est谩 tratando de reemplazar estructuras y matrices de tama帽o fijo con variables separadas. Esto permite que el compilador procese el acceso a ellos independientemente uno del otro e ignore la operaci贸n, si es obvio que su resultado no se utiliza. En algunos casos, el efecto indirecto de esta optimizaci贸n es eliminar la alineaci贸n.
La segunda optimizaci贸n, abrir el bucle, convierte el bucle con la condici贸n en una condici贸n con diferentes bucles en ambas ramas. Esto cambia el orden de ejecuci贸n en oposici贸n a la afirmaci贸n de que el programador sabe lo que se ejecutar谩 en un lenguaje de bajo nivel. Y esto tambi茅n crea serios problemas con la forma en que C maneja las variables indefinidas y el comportamiento indefinido.
En C, una variable no inicializada tiene un valor indefinido, que puede ser diferente con cada llamada. Esto es importante porque le permite implementar el reciclaje diferido de las p谩ginas de memoria. Por ejemplo, en FreeBSD, la implementaci贸n de malloc () le dice al sistema que las p谩ginas ya no est谩n en uso, y el sistema usa la primera entrada de la p谩gina como prueba de que este no es el caso. Apelar a la memoria reci茅n asignada puede obtener el valor anterior, luego el sistema operativo puede reutilizar la p谩gina de memoria y luego reemplazarla con una p谩gina llena de ceros la pr贸xima vez que escriba en otro lugar de la p谩gina. La segunda llamada al mismo lugar en la p谩gina obtendr谩 un valor cero.
Si la condici贸n usa un valor indefinido, entonces el resultado tampoco est谩 definido; cualquier cosa puede suceder. Imagine una optimizaci贸n de bucle abierto donde un bucle se ejecuta cero veces. En el original, todo el bucle es c贸digo muerto. En la versi贸n abierta, ahora hay una condici贸n con una variable que puede no inicializarse.
Como resultado, el c贸digo muerto se puede convertir a un comportamiento indefinido. Esta es solo una de las muchas optimizaciones que, al explorar m谩s a fondo la sem谩ntica de C, resultan poco confiables.
Al final, puede hacer que el c贸digo C se ejecute r谩pidamente, pero solo despu茅s de pasar miles de a帽os hombre creando un compilador lo suficientemente inteligente. Pero esto solo es posible si se violan ciertas reglas del lenguaje. Los creadores del compilador permiten a los programadores de C imaginar que escriben c贸digo que est谩 "cerca del hardware", pero tienen que generar c贸digo de m谩quina que se comporte de manera diferente para que los programadores sigan creyendo que escriben en un lenguaje r谩pido.
Entendiendo C
Uno de los atributos b谩sicos de un lenguaje de bajo nivel es que los programadores pueden comprender f谩cilmente c贸mo se transfiere una m谩quina de lenguaje abstracto a una m谩quina f铆sica. Este fue definitivamente el caso en PDP-11, donde las expresiones C se tradujeron en una o dos instrucciones. Del mismo modo, el compilador coloc贸 variables en ranuras de pila y convirti贸 los tipos simples en comprensibles para PDP-11.
Desde entonces, las implementaciones de C se han vuelto mucho m谩s complicadas: para mantener la ilusi贸n de que C se transfiere f谩cilmente a una plataforma de hardware y se ejecuta r谩pidamente. En 2015, una encuesta entre programadores de C, autores de compiladores y miembros del comit茅 de estandarizaci贸n mostr贸 que hab铆a
problemas para comprender C. Por ejemplo, este lenguaje permite que una implementaci贸n agregue alineaci贸n a las estructuras (pero no a las matrices) para garantizar que todos los campos est茅n correctamente alineados para la plataforma de destino. Si llena esta estructura con ceros y luego especifica un valor para algunos campos, 驴habr谩 ceros en los bits de alineaci贸n? Seg煤n la encuesta, el 36% estaba seguro de que lo har铆a, y el 29% no sab铆a la respuesta. Dependiendo del compilador y el nivel de optimizaci贸n, esto puede ser cierto (o no).
Este es un ejemplo bastante trivial, pero muchos programadores dan la respuesta incorrecta o no pueden responder en absoluto.
Si agrega punteros, la sem谩ntica de C se vuelve a煤n m谩s confusa.
El modelo BCPL era bastante simple: todos los significados son palabras. Cada palabra es datos o una direcci贸n en la memoria. La memoria es una matriz plana de celdas indexadas por direcci贸n.
El Modelo C permite la implementaci贸n para diferentes plataformas, incluidas las arquitecturas segmentadas, donde el puntero puede consistir en ID de segmentos y compensaciones, as铆 como m谩quinas virtuales con un recolector de basura. La especificaci贸n C restringe las operaciones de puntero permitidas para evitar problemas con dichos sistemas. La respuesta al
Informe de defectos 260 menciona el origen del puntero:
鈥淟as implementaciones pueden seguir el origen de un conjunto de bits y manejar aquellos que contienen un valor indefinido de manera diferente a los que contienen uno espec铆fico. "Pueden manejar punteros de manera diferente dependiendo de su origen, incluso si son iguales en t茅rminos de su valor de bit".
Desafortunadamente, la palabra "origen" falta en la especificaci贸n C11, por lo que los compiladores deciden por s铆 mismos lo que significa. GCC y Clang, por ejemplo, difieren en si el puntero que se convirti贸 al entero y viceversa conserva su origen. Los compiladores pueden decidir que dos punteros a los resultados de malloc () siempre dan un resultado negativo al comparar, incluso si apuntan a la misma direcci贸n.
Estos malentendidos no son puramente acad茅micos. Por ejemplo, ya se han observado vulnerabilidades, que fueron el resultado de desbordar un entero con signo (comportamiento indefinido en C) o
desreferenciar un puntero antes de verificar si es NULL , a pesar de que se le dijo al compilador que el puntero no pod铆a ser NULL.
Si existen tales problemas, es dif铆cil esperar que un programador entienda completamente c贸mo un programa en C se traduce a la arquitectura apropiada.
Introducir un procesador no para C
Los parches propuestos para proteger contra Specter y Meltdown causan una degradaci贸n severa del rendimiento, anulando todos los logros de microarquitectura en la 煤ltima d茅cada. Quiz谩s sea hora de dejar de pensar en c贸mo hacer que el c贸digo C sea m谩s r谩pido y, en cambio, pensar en nuevos modelos de programaci贸n en procesadores dise帽ados para la velocidad.
Hay muchos ejemplos de arquitecturas que no se han centrado en el c贸digo C tradicional y de las cuales pueden inspirarse. Por ejemplo, los procesadores orientados a subprocesos m煤ltiples como Sun / Oracle UltraSPARC Tx no requieren tanta cach茅 para mantener ocupados sus actuadores. Los procesadores de investigaci贸n han ampliado este concepto a una gran cantidad de subprocesos planificados por hardware. La idea clave es que, con suficientes subprocesos, el procesador puede pausar aquellos subprocesos que est谩n esperando datos y llenar los actuadores con instrucciones de otros subprocesos. El problema es que los programas C generalmente tienen muy pocos hilos.
El SVE de ARM (Extensiones de vectores escalares, extensiones de vectores escalares) es otro trabajo similar de Berkeley, que ofrece un vistazo a la interfaz mejorada entre el programa y el hardware. Los bloques de vectorizaci贸n regulares implementan operaciones con vectores de un tama帽o fijo y esperan que el compilador adapte el algoritmo al tama帽o especificado. Por el contrario, la interfaz SVE solicita al programador que describa independientemente el nivel de paralelismo y espera que el hardware lo adapte a los actuadores disponibles. Usar esto en C es dif铆cil porque el vectorizador autom谩tico necesita calcular el paralelismo basado en los bucles del c贸digo.
Los cach茅s son grandes, pero esta no es la 煤nica raz贸n de su complejidad. El protocolo de soporte de
coherencia de cach茅 es uno de los componentes m谩s complejos de un procesador moderno. La mayor parte de la dificultad proviene de tener que mantener un lenguaje en el que los datos se puedan compartir y mutar. Como ejemplo opuesto, podemos usar una m谩quina abstracta de estilo Erlang, donde cada objeto es local o inmutable. El protocolo de coherencia de cach茅 para dicho sistema tendr铆a solo dos casos: datos mutables y datos compartidos. La memoria cach茅 de la secuencia del programa que se transfiri贸 a otro procesador debe deshabilitarse expl铆citamente, pero esta es una operaci贸n relativamente rara.
Los objetos inmutables pueden simplificar a煤n m谩s las memorias cach茅 y abaratar algunas operaciones. En un proyecto de Maxwell de Sun Labs, se observ贸 que los objetos en el cach茅 y los objetos creados recientemente son casi siempre los mismos. Si los objetos mueren antes de ser excluidos de la memoria cach茅, entonces no puede escribirlos en la memoria principal y, por lo tanto, ahorrar consumo de energ铆a. El proyecto Maxwell propuso un recolector de basura que funcionaba en el cach茅 y le permit铆a reciclar r谩pidamente la memoria. Con los objetos inmutables en el mont贸n y la pila mutable, el recolector de basura se convierte en una m谩quina de estado muy simple, que se implementa f谩cilmente en el hardware y le permite utilizar de manera eficiente un cach茅 relativamente peque帽o.
Un procesador que est茅 dise帽ado 煤nicamente para la velocidad, y no para el equilibrio entre velocidad y compatibilidad con C, probablemente deber铆a admitir una gran cantidad de subprocesos, tener grandes bloques de vectorizaci贸n y un modelo de memoria m谩s simple. Ser谩 dif铆cil ejecutar el c贸digo C en dicho procesador, por lo tanto, dado el volumen de c贸digo C antiguo en el mundo, es poco probable que tenga 茅xito comercial.
En el campo del desarrollo de software, existe el mito de que la programaci贸n paralela es dif铆cil. Alan Kay se sorprender铆a mucho al escuchar esto: les ense帽贸 a los ni帽os a usar el modelo de actor, con el que escribieron programas en m谩s de 200 transmisiones. Esto tambi茅n es desconocido para los programadores de Erlang, que a menudo escriben programas con miles de componentes paralelos. Es m谩s correcto decir que la programaci贸n paralela es dif铆cil en un lenguaje con una m谩quina abstracta como C. Y si prestas atenci贸n al predominio del hardware paralelo (desde procesadores multin煤cleo a GPU multin煤cleo), esta es solo otra forma de decir que C no es adecuado para hardware moderno proporcionando.