viernes, 22 de octubre de 2010

Como el kernel administra la memoria.

Me demoré como un mes entretenido en otras cosas (a veces estás como perro con dos huesos delante ..... con muchos de hecho), pero aquí está la tercera entrega de los internals de Duarte. Para los que leyeron las dos primeras (primera y segunda) esta es la parte de la administración de la memoria por el kernel. El artículo original lo pueden encontrar aquí, y para los que llegan ahora si les interesa dar con el autor lo pueden hacer aquí. Listo, ahí les va, es muy buen material, al igual que las primeras creo que es utilísimo para estudiantes de ingenierías afines, el próximo sale en un par de días.... viene FreeBSD. 


Como el kernel administra la memoria.
Después de examinar el esquema de direcciones virtuales de un proceso, nos vamos al kernel y su mecanismo de administración de memoria. Aquí va de nuevo gonzo:




Los procesos en Linux son implementados en el kernel como instancias de task_struct, el descriptor de procesos. El campo mm en task_struct apunta al descriptor de memoria, mm_struct, es cual es un resumen ejecutivo de la memoria del programa. Almacena los inicios y los finales de los segmentos de memoria como se muestra arriba, el número de páginas de memoria física usadas por el proceso (rss viene de Resident Set Size, en el código enlazado arriba), la cantidad de espacio de memoria virtual utilizado y otras golosinas. Dentro del descriptor de memoria también encontramos los dos caballos de batalla para la administración de la memoria de un programa: el conjunto de áreas de memoria virtual y la tabla de páginas. Las áreas de memoria de gonzo se muestran abajo:




Cada Área Virtual de Memoria (AVM) es un rango continuo de direcciones virtuales; estas áreas nunca se solapan. Una instancia de vm_area_struct describe completamente un área de memoria, incluidas sus direcciones de inicio y final, las banderas (flags en el original) que determinan sus comportamientos y permisos de accesos, y el campo vm_file que especifica que archivo esta siendo mapeado por el área si existe alguno. Un AVM que no mapea un archivo es anónima. Cada segmento de memoria arriba (por ejemplo, el heap, el stack para los que llegan por primera vez los términos están explicados en entradas anteriores, enlazadas arriba) corresponde a una AVM única, con la excepción de los segmentos de mapeo de memoria. Esto no es un requerimiento, pero es usual en maquinas x86. A las AVMs no les importa en que segmento se encuentran.
El AVM de un programa se almacena en su descriptor de memoria de dos modos, primero como una lista enlazada en el campo mmap, ordenado por direcciones virtuales de inicio y segundo como un arbol rojo-negro con raíces en el campo mm_rb. El arbol rojo-negro le pérmite al kernel búsquedas rápidas de áreas de memoria que cubren una direccián virtual determinada. Cuando lees /proc/pid_of_process/maps, el kernel solo esta leyendo las listas enlazadas de AVM para el proceso e imprimiendo cada una de ellas.
En Windows, el bloque EPROCESS es aproximandamente una mezcla de task_struct y mm_struct. El equivalente en Windows de AVM es el Descriptor Virtual de Direcciones o DVD; y son almacenados en un arbol AVL. Saben que es lo gracioso de Windows y Linux? lo poco que difieren.
El espacio virtual de direcciones de 4Gb es dividido en páginas. Los procesadores en modos de 32 bits soportan tamaños de páginas de 4Kb, 2Mb y 4Mb. Ambos, Linux y Windows mapean la parte del espacio de direcciones virtuales del usuario usando páginas de 4Kb. Los bytes del 0-4095 caen en la página cero, entre 4096-8191 caen en la página 1 y así. El tamaño del AVM debe ser un multiplo del tamaño de página. Aquí muestro un espacio de usuario de 3Gb dividido en páginas de 4Kb:






El procesador consulta las tablas de páginas para traducir el espacio virtual en direcciones físicas de memoria. Cada proceso mantiene su propio conjunto de tablas de páginas; cada que ocurre una conmutación de procesos, las tablas de páginas del usuario son conmutadas igualmente. Linux almacena un puntero a la tabla de páginas del proceso en el campo pgd del descriptor de memoria. A cada página virtual le corresponde una entrada en la tabla de páginas (Page Table Entry en el original y en lo adelante PTE), las cuales en el paginado regular x86 no es mas que una entrada de 4 bytes, como se muestra debajo.



Linux tiene funciones para leer o setear (uso normalmente los términos setear (para poner a uno lógico) y resetear (para poner a cero lógico)) cada bandera en un PTE. El bit P le dice al procesador si la página virtual est'a presente en memoria f'ísica. Si esta a cero, el acceso a la página disparará un error de página. Tenga presente que cuando este bit esta a cero el kernel puede hacer lo que quiera con los campos restantes. La bandera R/W significa lectura(R)/escritura(W), si está a cero la página es de solo lectura. La bandera U/S significa usuario(U)/supervisor(S); si está a cero la página solo puede ser accedida por el kernel. Estas banderas se usan para implementar la memoria de solo lectura y el espacio protegido del kernel que ya vimos.
Los bits D y A son para dirty (sucio) y accesado. Una página sucia ha sido escrita, mientras que una página accesada ha sido escrita o leída. Ambos bits son pegajosos (sticky en el original, el uso del término es similar al sticky bit del set de permisos regular de un filesystem de Unix, de ahí la traducción de pegajoso): el procesador solo puede setearlos y deben ser limpiados (puestos a cero) por el kernel. finalmente el PTE almacena la dirección física de inicio que corresponde a la página, alineada a 4 Kb. Este campo de aspecto ingenuo es origen de algunos problemas, debido al límite de memoria direccionable de 4Gb. El resto de los campos PTE los veremos otro día así como la Extensión Fisica de Memoria (PAE).
Una página virtual es una unidad de protección de memoria porque todos sus bytes comparten las baderas de U/S y R/W. De todas formas la misma memoria física puede ser mapeada por diferentes páginas, posiblemente con diferentes banderas de protección. Nótese que en el PTE no existen permisos de ejecución. Es por esto que el paginado clásico x86 permite que se ejecute código en la pila, haciendo mas fácil los exploits de desbordamiento del buffer de la pila (todavia es posible explotar pilas no ejecutables usando return-to-libc y otras técnicas). Esta carencia de banderas de no ejecución en el PTE ilustra un hecho mas amplio: las banderas de permisos en la AVM pueden o no ser traducidas de maneras limpias en protección de hardware. El kernel hace lo que puede, pero al final la arquitectura pone los límites de lo que es posible.
La memoria virtual no almacena nada, solo mapea el espacio de direcciones de un programa en la memoria física subyacente, la cual es accedida por el procesador como un gran bloque llamado espacio de direcciones físicas. Aun cuando las operaciones de memoria en el bus están involucradas de alguna manera, las podemos ignorar de momento y asumir el rango de direcciones físicas  desde cero hasta el tope de la memoria disponible en incrementos de un byte. Este espacio de direcciones físicas es dividido por el kernel en cuadros de memoria. Al procesador ni le importa ni sabe de cuadros, aun cuando son cruciales para el kernel a causa de que el cuadro de páginas es la unidad de administración de memoria física. Ambos, Linux y Windows usan cuadros de páginas de 4kB en modo de 32 bits; aquí hay un ejemplo de una máquina con 2 Gb de RAM:



En Linux, cada cuadro de páginas es atendido por un descriptor y varias banderas. Juntos estos descriptores administran toda la memoria en la computadora; el estado preciso de cada cuadro de página siempre es conocido. La memoria física es administrada mediante la técnica de localización de memoria amiga (buddy memory allocation en el original), de modo que un cuadro de página esta libre si esta disponible para localización a traves del sistema mencionado (buddy system). Un cuadro de página localizado puede ser anónimo, almacenando datos de programa o puede estar en la cache de páginas, almacenando datos de un archivo o un dispositivo de bloques. Existen otros usos exóticos de los cuadros de páginas pero dejémoslos descansar por ahora. Windows tiene una base de datos de Número de Cuadro de Página análogo para administrar la memoria fisica.
Pongamos juntas las áreas de memoria virtual, las entradas de la tabla de páginas y los cuadros de páginas para enteder como funciona todo. Debajo hay un ejemplo del heap del usuario:



Los rectángulos azules representan páginas en el rango de AVM, mientras que las flechas representan entradas en la tabla de páginas mapeando páginas en los cuadros de páginas. Algunas páginas virtuales carecen de flechas; lo que significa que los PTEs correspondientes tiene la bandera de present (P) a cero. Esto puede suceder porque la página no ha sido tocada nunca o porque su contenido ha sido bajado a disco (swaped out en el original,  el equivalente de la swap de Unix en Windows es (aproximadamente) la Memoria Virtual, es decir, espacio en disco, los términos  swap-in y swap-out refieren respectivamente los procesos de subir o bajar datos desde el disco). En cualquiera de los dos casos, el acceso a estas páginas generara un fallo de página, aún cuando están dentro de la AVM. Puede paracer extraño que el AVM y las tablas de páginas no estén de acuerdo pero sucede a menudo.
El AVM es como un contrato entre tu programa y el kernel. Tu solicitas que algo se ejecute (localizar memoria, mapear un archivo, etc), el kernel dice "ok", y crea o actualiza el AVM apropiada. Pero esto no ejecuta la solicitud de inmediato, sino que espera hasta que haya un fallo de páginas para hacer el trabajo en realidad. El kernel es un perezoso saco de escoria, este es el principio fundamental de la memoria virtual. Es aplicable en la mayoría de las situaciones, algunas familiares algunas sorprendentes, pero la regla es que las entradas de AVM reflejan lo que ha sido acordado, mientras que los PTEs reflejan lo que en realidad ha hecho el perezoso kernel. Estas dos estructuras de datos en conjunto administran la memoria de un programa; ambas hacen su parte resolviendo fallos de páginas, liberando memoria, swapeando memoria y así. Veamos un caso simple de localización de memoria:



Cuando el programa solicita más memoria a través de la llamada al sistema brk(), el kernel simplemente actualiza el AVM del heap y la marca como válida. Hasta este punto no se ha localizado ningun cuadro de páginas y las páginas nuevas no están presentes en memoria física. Una vez que el programa trata de acceder las páginas, el procesador invoca un page-fault y llama a do_page_fault(). Este busca el AVM que cubre la dirección virtual fallada usando find_vam(). Si la encuentra, también revisa los permisos de AVM contra el acceso intentado (de lectura o escritura). Si no hay AVM disponible, ningun contrato está cubriendo el intento de acceso a memoria y el proceso es castigado con un fallo de segmentación.
Cuando si encuentra un AVM el kernel debe manejar el fallo buscando en el contenido del PTE y el tipo de AVM. En nuestro caso el PTE muestra que la página no esta presente. De hecho nuestro PTE esta completamente en blanco (todo cero), lo que en Linux significa que la página virtual nunca ha sido mapeada. Toda vez que es una AVM anónima, tenemos un asunto puramente de RAM, que debe ser manejado por do_anonymous_page(), el cual localiza un cuadro de memoria y hace que el PTE mapee la página virtual fallada en el cuadro recién localizado.
Las cosas podrían haber sido diferentes. El PTE para una página swapeada, por ejemplo, tendría un cero en la bandera de present pero no estaría vacio, en vez de eso, almacena la localización de la swap que almacena el contenido de la página, el cual deberá ser leído desde el disco y cargado al cuadro de páginas por do_swap_page() en lo que es conocido como una fallo mayor.
Esto concluye la primera mitad de nuestro recorrido por la administración de memoria de usuario por el kernel. En el próximo post, vamos a incluir los archivos en la mezcla para tener una imagen completa de los fundamentos de la memoria, incluido las consecuencias en el rendimiento.