x86 paging virtual-memory

¿Cómo funciona la búsqueda x86?



paging virtual-memory (2)

Esta pregunta está destinada a llenar el vacío de buena información gratuita sobre el tema.

Creo que una buena respuesta cabrá en una gran respuesta SO o al menos en algunas respuestas.

El objetivo principal es proporcionar a los principiantes suficientes información suficiente para que puedan tomar el manual por su cuenta y sean capaces de comprender los conceptos básicos del sistema operativo relacionados con la búsqueda.

Pautas sugeridas:

  • las respuestas deben ser amigables para principiantes:
    • ejemplos concretos, pero posiblemente simplificados, son muy importantes
    • aplicaciones de los conceptos mostrados son bienvenidos
  • citando recursos útiles es bueno
  • pequeñas digresiones sobre cómo los sistemas operativos usan características de búsqueda son bienvenidos
  • Las explicaciones de PAE y PSE son bienvenidas
  • pequeñas digresiones en x86_64 son bienvenidas

Preguntas relacionadas y por qué creo que no son tontos:

Aquí hay una respuesta muy breve y de alto nivel:

Un procesador x86 funciona en uno de varios modos posibles (aproximadamente: real, protegido, 64 bits). Cada modo puede usar uno de varios modelos posibles de direccionamiento de memoria (pero no todos los modos pueden usar todos los modelos), a saber: direccionamiento en modo real, direccionamiento segmentado y direccionamiento plano-lineal.

En el mundo moderno, solo el direccionamiento lineal plano en modo protegido o de 64 bits es relevante, y los dos modos son esencialmente los mismos, con la diferencia principal del tamaño de la palabra de la máquina y, por lo tanto, la cantidad de memoria direccionable.

Ahora, el modo de direccionamiento de memoria da significado a los operandos de memoria de las instrucciones de la máquina (como mov DWORD PTR [eax], 25 , que almacena un entero de 32 bits (aka dword ) de valor 25 en la memoria cuya dirección se almacena en el registro eax 32 bits). En el direccionamiento plano-lineal, este número en eax puede ejecutarse en un único rango contiguo, desde cero hasta el valor máximo (en nuestro caso eso es 2 32 - 1).

Sin embargo, el direccionamiento lineal plano puede ser paginado o no paginado . Sin paginación, la dirección se refiere directamente a la memoria física. Con la paginación, la unidad de administración de memoria (o MMU) del procesador transmite de manera transparente la dirección deseada (ahora llamada dirección virtual ) a un mecanismo de búsqueda, las llamadas tablas de página , y obtiene un nuevo valor, que se interpreta como una dirección física. La operación original ahora opera en esta nueva dirección traducida en la memoria física, aunque el usuario solo vea la dirección virtual.

El beneficio clave de la paginación es que las tablas de páginas son administradas por el sistema operativo. Por lo tanto, el sistema operativo puede modificar y reemplazar las tablas de páginas arbitrariamente, como cuando se "cambia tareas". Puede mantener una colección completa de tablas de páginas, una para cada "proceso", y siempre que decida que un proceso en particular se ejecutará en una CPU determinada, carga las tablas de páginas del proceso en la MMU de esa CPU (cada CPU tiene su propia conjunto de tablas de páginas). El resultado es que cada proceso ve su propio espacio de direcciones virtuales que se ve igual independientemente de las páginas físicas que estaban libres cuando el sistema operativo tenía que asignar memoria para ello. Nunca sabe acerca de la memoria de ningún otro proceso, ya que no puede acceder directamente a la memoria física.

Las tablas de páginas son estructuras de datos similares a un árbol anidadas almacenadas en la memoria normal, escritas por el sistema operativo pero leídas directamente por hardware, por lo que el formato es fijo. Se "cargan" en la MMU configurando un registro de control de CPU especial para apuntar a la tabla de nivel superior. La CPU usa un caché llamado TLB para recordar las búsquedas, por lo que los accesos repetidos a las mismas pocas páginas son mucho más rápidos que los accesos dispersos, por razones de fallas TLB así como por los motivos usuales de caché de datos. Es común ver el término "entrada TLB" utilizado para referirse a las entradas de la tabla de páginas, incluso cuando no están almacenadas en caché en el TLB.

Y en caso de que te preocupe que un proceso simplemente deshabilite la búsqueda o intente modificar las tablas de páginas: Esto no está permitido, ya que x86 implementa niveles de privilegios (llamados "anillos") y el código de usuario es demasiado bajo para permitir para modificar las tablas de páginas de la CPU.

Versión de esta respuesta con un buen TOC y más contenido .

Corregiré cualquier error informado. Si desea hacer grandes modificaciones o agregar un aspecto que falta, hágalas con sus propias respuestas para obtener una reputación bien merecida. Las ediciones menores se pueden combinar directamente en.

Código de muestra

Ejemplo mínimo: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Como todo lo demás en la programación, la única forma de entender esto realmente es jugar con ejemplos mínimos.

Lo que lo convierte en un tema "difícil" es que el ejemplo mínimo es grande porque necesita crear su propio sistema operativo pequeño.

Manual de Intel

Aunque es imposible de entender sin tener en cuenta los ejemplos, trate de familiarizarse con los manuales lo antes posible.

Intel describe la búsqueda en la Guía de programación del sistema Intel Manual Volumen 3 - 325384-056ES Septiembre de 2015 Capítulo 4 "Megafonía".

Especialmente interesante es la Figura 4-4 "Formatos de CR3 y Entradas de estructura de paginación con paginación de 32 bits", que proporciona las estructuras de datos clave.

MMU

La paginación se realiza por la unidad de administración de memoria (MMU) de la CPU. Al igual que muchos otros (por ejemplo, el coprocesador x87 , APIC ), solía ser un chip separado en los primeros días, que luego se integró a la CPU. Pero el término todavía se usa.

Conceptos generales

Las direcciones lógicas son las direcciones de memoria utilizadas en el código de usuario-tierra "regular" (por ejemplo, los contenidos de rsi en mov eax, [rsi] ).

La primera segmentación los traduce en direcciones lineales y, a continuación, la paginación convierte las direcciones lineales en direcciones físicas.

(logical) ------------------> (linear) ------------> (physical) segmentation paging

La mayoría de las veces, podemos pensar que las direcciones físicas indexan las celdas de memoria de hardware RAM reales, pero esto no es 100% cierto debido a:

La paginación solo está disponible en modo protegido. El uso de paginación en modo protegido es opcional. La paginación está cr0 se establece el bit PG del registro cr0 .

Paginación vs segmentación

Una diferencia importante entre la paginación y la segmentación es que:

  • paginación divide RAM en trozos de igual tamaño llamadas páginas
  • la segmentación divide la memoria en fragmentos de tamaños arbitrarios

Esta es la principal ventaja de la búsqueda, ya que los trozos de igual tamaño hacen que las cosas sean más manejables.

La búsqueda se ha vuelto mucho más popular que el soporte para la segmentación se ha eliminado en x86-64 en el modo de 64 bits, el principal modo de operación para el nuevo software, donde solo existe en modo compatibilidad, que emula IA32.

Solicitud

La paginación se usa para implementar espacios de direcciones virtuales en el sistema operativo moderno. Con las direcciones virtuales, el SO puede caber dos o más procesos simultáneos en una sola RAM de una manera que:

  • ambos programas necesitan saber nada sobre el otro
  • la memoria de ambos programas puede crecer y reducirse según sea necesario
  • el cambio de programa es muy rápido
  • un programa nunca puede acceder a la memoria de otro proceso

La localización históricamente surgió después de la segmentación, y la reemplazó en gran parte por la implementación de memoria virtual en sistemas operativos modernos, como Linux, ya que es más fácil administrar trozos de memoria de tamaño fijo de páginas en lugar de segmentos de longitud variable.

Implementación de hardware

Al igual que la segmentación en modo protegido (donde modificar un registro de segmento desencadena una carga desde el GDT o LDT), el hardware de paginación usa estructuras de datos en la memoria para hacer su trabajo (tablas de páginas, directorios de páginas, etc.).

El hardware fija el formato de esas estructuras de datos, pero corresponde al sistema operativo configurar y administrar esas estructuras de datos en la RAM correctamente, y decirle al hardware dónde encontrarlas (a través de cr3 ).

Algunas otras arquitecturas dejan la búsqueda casi por completo en manos del software, por lo que una falla TLB ejecuta una función proporcionada por el sistema operativo para recorrer las tablas de página e insertar la nueva asignación en el TLB. Esto deja los formatos de tabla de páginas elegidos por el sistema operativo, pero hace que sea poco probable que el hardware se superponga a las caminatas de página con la ejecución fuera de orden de otras instrucciones, como lo hace x86 .

Ejemplo: esquema simplificado de paginación de un solo nivel

Este es un ejemplo de cómo funciona la paginación en una versión simplificada de la arquitectura x86 para implementar un espacio de memoria virtual.

Tablas de página

El sistema operativo podría darles las siguientes tablas de página:

Tabla de páginas dada al proceso 1 por el sistema operativo:

RAM location physical address present ----------------- ----------------- -------- PT1 + 0 * L 0x00001 1 PT1 + 1 * L 0x00000 1 PT1 + 2 * L 0x00003 1 PT1 + 3 * L 0 ... ... PT1 + 0xFFFFF * L 0x00005 1

Tabla de páginas dada al proceso 2 por el sistema operativo:

RAM location physical address present ----------------- ----------------- -------- PT2 + 0 * L 0x0000A 1 PT2 + 1 * L 0x0000B 1 PT2 + 2 * L 0 PT2 + 3 * L 0x00003 1 ... ... ... PT2 + 0xFFFFF * L 0x00004 1

Dónde:

  • PT1 y PT2 : posición inicial de la tabla 1 y 2 en la RAM.

    Valores de muestra: 0x00000000 , 0x12345678 , etc.

    Es el sistema operativo el que decide esos valores.

  • L : duración de una entrada de tabla de página.

  • present : indica que la página está presente en la memoria.

Las tablas de páginas están ubicadas en la RAM. Podrían, por ejemplo, ubicarse como:

--------------> 0xFFFFFFFF --------------> PT1 + 0xFFFFF * L Page Table 1 --------------> PT1 --------------> PT2 + 0xFFFFF * L Page Table 2 --------------> PT2 --------------> 0x0

Las ubicaciones iniciales en la RAM para ambas tablas de página son arbitrarias y están controladas por el sistema operativo. ¡Depende del SO garantizar que no se superpongan!

Cada proceso no puede tocar ninguna tabla de páginas directamente, aunque puede realizar solicitudes al sistema operativo que provocan la modificación de las tablas de páginas, por ejemplo, la solicitud de segmentos de pila o montón más grandes.

Una página es un fragmento de 4 KB (12 bits), y como las direcciones tienen 32 bits, solo se requieren 20 bits (20 + 12 = 32, por lo tanto, 5 caracteres en notación hexadecimal) para identificar cada página. Este valor es fijado por el hardware.

Entradas de la tabla de página

Una tabla de páginas es ... ¡una tabla de entradas de tablas de páginas!

El hardware corrige el formato exacto de las entradas de la tabla.

En este ejemplo simplificado, las entradas de la tabla de páginas contienen solo dos campos:

bits function ----- ----------------------------------------- 20 physical address of the start of the page 1 present flag

entonces en este ejemplo los diseñadores de hardware podrían haber elegido L = 21 .

La mayoría de las entradas de la tabla de páginas reales tienen otros campos.

No sería práctico alinear las cosas en 21 bytes, ya que la memoria es direccionable por bytes y no por bits. Por lo tanto, incluso en tan solo 21 bits son necesarios en este caso, los diseñadores de hardware probablemente elegirían L = 32 para hacer el acceso más rápido, y solo reservarán los bits restantes para su uso posterior. El valor real para L en x86 es de 32 bits.

Traducción de direcciones en esquema de un solo nivel

Una vez que el sistema operativo ha configurado las tablas de páginas, el hardware realiza la traducción de direcciones entre direcciones lineales y físicas.

Cuando el sistema operativo desea activar el proceso 1, establece cr3 en PT1 , el inicio de la tabla para el proceso uno.

Si el Proceso 1 desea acceder a la dirección lineal 0x00000001 , el circuito de hardware de búsqueda hará lo siguiente para el sistema operativo:

  • divide la dirección lineal en dos partes:

    | page (20 bits) | offset (12 bits) |

    Entonces, en este caso, tendríamos:

    • página = 0x00000
    • offset = 0x001

  • mira en la tabla de la página 1 porque cr3 apunta a ella.

  • mira la entrada 0x00000 porque esa es la parte de la página.

    El hardware sabe que esta entrada se encuentra en la dirección de la RAM PT1 + 0 * L = PT1 .

  • ya que está presente, el acceso es válido

  • por la tabla de la página, la ubicación del número de página 0x00000 está en 0x00001 * 4K = 0x00001000 .

  • para encontrar la dirección física final solo necesitamos agregar el desplazamiento:

    00001 000 + 00000 001 ----------- 00001 001

    porque 00001 es la dirección física de la página buscada en la tabla y 001 es la compensación.

    Como su nombre indica, el desplazamiento siempre se agrega simplemente a la dirección física de la página.

  • el hardware luego obtiene la memoria en esa ubicación física.

De la misma manera, las siguientes traducciones sucederían para el proceso 1:

linear physical --------- --------- 00000 002 00001 002 00000 003 00001 003 00000 FFF 00001 FFF 00001 000 00000 000 00001 001 00000 001 00001 FFF 00000 FFF 00002 000 00002 000 FFFFF 000 00005 000

Por ejemplo, al acceder a la dirección 00001000 , la parte de la página es 00001 el hardware sabe que su entrada en la tabla de páginas está ubicada en la dirección de la RAM: PT1 + 1 * L ( 1 debido a la parte de la página), y ahí lo buscará .

Cuando el sistema operativo quiere cambiar al proceso 2, todo lo que tiene que hacer es hacer que cr3 apunte a la página 2. ¡Es así de simple!

Ahora las siguientes traducciones sucederían para el proceso 2:

linear physical --------- --------- 00000 002 00001 002 00000 003 00001 003 00000 FFF 00001 FFF 00001 000 00000 000 00001 001 00000 001 00001 FFF 00000 FFF 00003 000 00003 000 FFFFF 000 00004 000

La misma dirección lineal se traduce en diferentes direcciones físicas para diferentes procesos , dependiendo solo del valor dentro de cr3 .

De esta forma, cada programa puede esperar que sus datos comiencen en 0 y terminen en FFFFFFFF , sin preocuparse por las direcciones físicas exactas.

Error de página

¿Qué sucede si el Proceso 1 intenta acceder a una dirección dentro de una página que no está presente?

El hardware notifica al software a través de una excepción de error de página.

Por lo general, corresponde al sistema operativo registrar un manejador de excepciones para decidir qué se debe hacer.

Es posible que acceder a una página que no está sobre la mesa sea un error de programación:

int is[1]; is[2] = 1;

pero puede haber casos en los que sea aceptable, por ejemplo en Linux cuando:

  • el programa quiere aumentar su stack

    Simplemente intenta acceder a un determinado byte en un rango posible, y si el sistema operativo está contento, agrega esa página al espacio de direcciones del proceso.

  • la página fue intercambiada al disco.

    El sistema operativo necesitará hacer algo de trabajo detrás de los procesos para que la página regrese a la memoria RAM.

    El SO puede descubrir que este es el caso basado en el contenido del resto de la entrada de la tabla de páginas, ya que si el indicador actual es claro, las demás entradas de la entrada de la tabla de páginas se dejan completamente para el OS a lo que quiere.

    En Linux, por ejemplo, cuando presente = 0:

    • si todos los campos de la entrada de la tabla de páginas son 0, dirección inválida.

    • de lo contrario, la página ha sido intercambiada al disco, y los valores reales de esos campos codifican la posición de la página en el disco.

En cualquier caso, el sistema operativo necesita saber qué dirección generó la falla de página para poder tratar el problema. Esta es la razón por la cual los buenos desarrolladores de IA32 establecen el valor de cr2 en esa dirección cada vez que ocurre una falla de página. El manejador de excepciones solo puede mirar cr2 para obtener la dirección.

Simplificaciones

Simplificaciones a la realidad que hacen que este ejemplo sea más fácil de entender:

  • todos los circuitos de megafonía reales usan la megafonía multinivel para ahorrar espacio, pero esto mostraba un esquema simple de un solo nivel.

  • las tablas de páginas contenían solo dos campos: una dirección de 20 bits y una bandera de 1 bit presente.

    Las tablas de páginas reales contienen un total de 12 campos y, por lo tanto, otras características que se han omitido.

Ejemplo: esquema de paginación multinivel

El problema con un esquema de paginación de un solo nivel es que ocuparía demasiada RAM: 4G / 4K = 1M de entradas por proceso. Si cada entrada tiene 4 bytes de longitud, eso haría 4M por proceso , que es demasiado incluso para una computadora de escritorio: ps -A | wc -l ps -A | wc -l dice que estoy ejecutando 244 procesos en este momento, ¡así que tomaría alrededor de 1GB de mi RAM!

Por esta razón, los desarrolladores de x86 decidieron usar un esquema de niveles múltiples que reduce el uso de RAM.

La desventaja de este sistema es que tiene un tiempo de acceso ligeramente superior.

En el esquema simple de paginación de 3 niveles utilizado para procesadores de 32 bits sin PAE, los 32 bits de dirección se dividen de la siguiente manera:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Cada proceso debe tener un solo directorio de página asociado, de modo que contendrá al menos 2^10 = 1K entradas de directorio de página, mucho mejor que el mínimo de 1M requerido en un esquema de un solo nivel.

Las tablas de páginas solo se asignan según sea necesario para el sistema operativo. Cada tabla de páginas tiene 2^10 = 1K entradas de directorio de página de 2^10 = 1K

Los directorios de página contienen ... entradas de directorio de página! Las entradas del directorio de la página son las mismas que las entradas de la tabla de la página, excepto que apuntan a las direcciones de la RAM de las tablas de páginas en lugar de a las direcciones físicas de las tablas . Dado que esas direcciones tienen solo 20 bits de ancho, las tablas de páginas deben estar al principio de las páginas de 4 KB.

cr3 ahora apunta a la ubicación en la RAM del directorio de página del proceso actual en lugar de las tablas de página.

Las entradas de las tablas de página no cambian para nada de un esquema de un solo nivel.

Las tablas de páginas cambian de un esquema de un solo nivel porque:

  • cada proceso puede tener hasta 1K tablas de página, una por entrada de directorio de página.
  • cada tabla de página contiene exactamente 1K entradas en lugar de 1M entradas.

La razón para usar 10 bits en los dos primeros niveles (y no, por ejemplo, 12 | 8 | 12 ) es que cada entrada de la tabla de páginas tiene una longitud de 4 bytes. Entonces las 2 ^ 10 entradas de los directorios de página y las tablas de páginas encajarán perfectamente en las páginas de 4 Kb. Esto significa que es más rápido y simple asignar y desasignar páginas para ese fin.

Traducción de direcciones en esquema de niveles múltiples

Directorio de páginas dado al proceso 1 por el sistema operativo:

RAM location physical address present --------------- ----------------- -------- PD1 + 0 * L 0x10000 1 PD1 + 1 * L 0 PD1 + 2 * L 0x80000 1 PD1 + 3 * L 0 ... ... PD1 + 0x3FF * L 0

Tablas de página asignadas al proceso 1 por el SO en PT1 = 0x10000000 ( 0x10000 * 4K):

RAM location physical address present --------------- ----------------- -------- PT1 + 0 * L 0x00001 1 PT1 + 1 * L 0 PT1 + 2 * L 0x0000D 1 ... ... PT1 + 0x3FF * L 0x00005 1

Tablas de página asignadas al proceso 1 por el sistema operativo en PT2 = 0x80000000 ( 0x80000 * 4K):

RAM location physical address present --------------- ----------------- -------- PT2 + 0 * L 0x0000A 1 PT2 + 1 * L 0x0000C 1 PT2 + 2 * L 0 ... ... PT2 + 0x3FF * L 0x00003 1

dónde:

  • PD1 : posición inicial del directorio de página del proceso 1 en la RAM.
  • PT1 y PT2 : posición inicial de la tabla de páginas 1 y tabla de páginas 2 para el proceso 1 en la RAM.

Entonces, en este ejemplo, el directorio de la página y la tabla de la página podrían almacenarse en la RAM algo así como:

----------------> 0xFFFFFFFF ----------------> PT2 + 0x3FF * L Page Table 1 ----------------> PT2 ----------------> PD1 + 0x3FF * L Page Directory 1 ----------------> PD1 ----------------> PT1 + 0x3FF * L Page Table 2 ----------------> PT1 ----------------> 0x0

Vamos a traducir la dirección lineal 0x00801004 paso a paso.

Suponemos que cr3 = PD1 , es decir, apunta al directorio de página que se acaba de describir.

En binario, la dirección lineal es:

0 0 8 0 1 0 0 4 0000 0000 1000 0000 0001 0000 0000 0100

Agrupando como 10 | 10 | 12 10 | 10 | 12 10 | 10 | 12 da:

0000000010 0000000001 000000000100 0x2 0x1 0x4

lo que da:

  • entrada de directorio de página = 0x2
  • entrada de la tabla de página = 0x1
  • desplazamiento = 0x4

Entonces el hardware busca la entrada 2 del directorio de la página.

La tabla del directorio de la página dice que la tabla de la página se encuentra en 0x80000 * 4K = 0x80000000 . Este es el primer acceso de RAM al proceso.

Como la entrada de la tabla de páginas es 0x1 , el hardware mira la entrada 1 de la tabla de páginas en 0x80000000 , que le dice que la página física está ubicada en la dirección 0x0000C * 4K = 0x0000C000 . Este es el segundo acceso RAM del proceso.

Finalmente, el hardware de búsqueda agrega el desplazamiento, y la dirección final es 0x0000C004 .

Otros ejemplos de direcciones traducidas son:

linear 10 10 12 split physical -------- --------------- ---------- 00000001 000 000 001 00001001 00001001 000 001 001 page fault 003FF001 000 3FF 001 00005001 00400000 001 000 000 page fault 00800001 002 000 001 0000A001 00801008 002 001 008 0000C008 00802008 002 002 008 page fault 00B00001 003 000 000 page fault

Las fallas de página ocurren si una entrada de directorio de página o una entrada de tabla de página no está presente.

Si el sistema operativo desea ejecutar otro proceso al mismo tiempo, le daría al segundo proceso un directorio de página separado y vincular ese directorio a tablas de página separadas.

Arquitecturas de 64 bits

64 bits sigue siendo demasiada dirección para los tamaños de RAM actuales, por lo que la mayoría de las arquitecturas usarán menos bits.

x86_64 usa 48 bits (256 TiB), y el PAE del modo heredado ya permite direcciones de 52 bits (4 PiB).

12 de esos 48 bits ya están reservados para el desplazamiento, lo que deja 36 bits.

Si se toma un enfoque de 2 niveles, la mejor división sería dos niveles de 18 bits.

Pero eso significaría que el directorio de la página tendría 2^18 = 256K entradas, lo que requeriría demasiada RAM: ¡cerca de una paginación de un solo nivel para las arquitecturas de 32 bits!

Por lo tanto, las arquitecturas de 64 bits crean niveles de página aún mayores, comúnmente 3 o 4.

x86_64 usa 4 niveles en un 9 | 9 | 9 | 12 9 | 9 | 9 | 12 9 | 9 | 9 | 12 esquema, por lo que el nivel superior solo ocupa solo 2^9 entradas de nivel superior.

PAE

Extensión de dirección física.

Con 32 bits, solo se pueden abordar 4 GB de RAM.

Esto comenzó a convertirse en una limitación para los servidores grandes, por lo que Intel introdujo el mecanismo PAE en Pentium Pro.

Para aliviar el problema, Intel agregó 4 nuevas líneas de dirección, de modo que se puedan abordar 64 GB.

La estructura de la tabla de página también se altera si PAE está activado. La forma exacta en que se modifica depende de si el PSE está encendido o apagado.

PAE se activa y desactiva mediante el bit PAE de cr4 .

Incluso si la memoria direccionable total es de 64 GB, los procesos individuales solo pueden usar hasta 4 GB. Sin embargo, el sistema operativo puede poner diferentes procesos en diferentes fragmentos de 4 GB.

PSE

Extensión de tamaño de página.

Permite que las páginas sean 4M (o 2M si PAE está activado) en longitud en lugar de 4K.

PSE se activa y desactiva mediante el bit PAE de cr4 .

Esquemas de tablas de páginas PAE y PSE

Si PAE y PSE están activos, se utilizan diferentes esquemas de nivel de paginación:

  • sin PAE y sin PSE: 10 | 10 | 12 10 | 10 | 12

  • sin PAE y PSE: 10 | 22 10 | 22 .

    22 es el desplazamiento dentro de la página de 4Mb, ya que 22 bits dirigen 4Mb.

  • PAE y no PSE: 2 | 9 | 9 | 12 2 | 9 | 9 | 12

    La razón de diseño por la cual 9 se usa dos veces en vez de 10 es que ahora las entradas ya no caben en 32 bits, que fueron llenados por 20 bits de dirección y 12 bits de bandera significativos o reservados.

    La razón es que 20 bits ya no son suficientes para representar la dirección de las tablas de páginas: ahora se necesitan 24 bits debido a los 4 cables adicionales agregados al procesador.

    Por lo tanto, los diseñadores decidieron aumentar el tamaño de la entrada a 64 bits, y para que quepan en una sola tabla de páginas es necesario reducir el número de entradas a 2 ^ 9 en lugar de a 2 ^ 10.

    El inicio 2 es un nuevo nivel de página denominado Tabla de puntero del directorio de la página (PDPT), ya que apunta a los directorios de página y completa la dirección lineal de 32 bits. Los PDPT también tienen 64 bits de ancho.

    cr3 ahora apunta a PDPTs que deben estar en el cuarto cuatro 4GB de memoria y alineados en múltiplos de 32 bit para la eficiencia de direccionamiento. Esto significa que ahora cr3 tiene 27 bits significativos en lugar de 20: 2 ^ 5 para los 32 múltiplos * 2 ^ 27 para completar los 2 ^ 32 de los primeros 4GB.

  • PAE y PSE: 2 | 9 | 21 2 | 9 | 21

    Los diseñadores decidieron mantener un campo de 9 bits de ancho para que quepa en una sola página.

    Esto deja 23 bits. Al dejar 2 para el PDPT para mantener las cosas uniformes con el estuche PAE sin PSE, deja 21 para el desplazamiento, lo que significa que las páginas tienen un ancho de 2M en lugar de 4M.

TLB

La traducción Lookahead Buffer (TLB) es un caché para las direcciones de búsqueda.

Como es un caché, comparte muchos de los problemas de diseño del caché de la CPU, como el nivel de asociatividad.

Esta sección describirá un TLB totalmente asociativo simplificado con 4 entradas de dirección única. Tenga en cuenta que, al igual que otros cachés, los TLB reales no suelen ser totalmente asociativos.

Operación básica

Después de que ocurre una traducción entre dirección lineal y física, se almacena en el TLB. Por ejemplo, un TLB de 4 entradas se inicia en el siguiente estado:

valid linear physical ------ ------- --------- > 0 00000 00000 0 00000 00000 0 00000 00000 0 00000 00000

El > indica la entrada actual que se reemplazará.

y después de que una dirección lineal de página 00003 se traduce a una dirección física 00005 , el TLB se convierte en:

valid linear physical ------ ------- --------- 1 00003 00005 > 0 00000 00000 0 00000 00000 0 00000 00000

y después de una segunda traducción de 00007 a 00009 se convierte en:

valid linear physical ------ ------- --------- 1 00003 00005 1 00007 00009 > 0 00000 00000 0 00000 00000

Ahora, si es necesario volver a traducir 00003 , el hardware primero busca el TLB y descubre su dirección con una sola RAM acceso 00003 --> 00005 .

Por supuesto, 00000 no está en el TLB ya que ninguna entrada válida contiene 00000 como clave.

Política de reemplazo

Cuando se rellena el TLB, las direcciones anteriores se sobrescriben. Al igual que para la memoria caché de la CPU, la política de reemplazo es una operación potencialmente compleja, pero una heurística simple y razonable es eliminar la entrada utilizada menos recientemente (LRU).

Con LRU, comenzando desde el estado:

valid linear physical ------ ------- --------- > 1 00003 00005 1 00007 00009 1 00009 00001 1 0000B 00003

agregar 0000D -> 0000A daría:

valid linear physical ------ ------- --------- 1 0000D 0000A > 1 00007 00009 1 00009 00001 1 0000B 00003

LEVA

El uso de TLB hace que la traducción sea más rápida, porque la traducción inicial toma un acceso por nivel de TLB , lo que significa 2 en un esquema simple de 32 bits, pero 3 o 4 en arquitecturas de 64 bits.

El TLB generalmente se implementa como un tipo de RAM costosa llamada memoria direccionable por contenido (CAM). CAM implementa un mapa asociativo en hardware, es decir, una estructura que, dada una clave (dirección lineal), recupera un valor.

Las asignaciones también podrían implementarse en direcciones de RAM, pero las asignaciones de CAM pueden requerir muchas menos entradas que una asignación de RAM.

Por ejemplo, un mapa en el que:

  • ambas claves y valores tienen 20 bits (el caso de esquemas de paginación simples)
  • como máximo deben almacenarse 4 valores en cada momento

podría ser almacenado en un TLB con 4 entradas:

linear physical ------- --------- 00000 00001 00001 00010 00010 00011 FFFFF 00000

Sin embargo, para implementar esto con la RAM, sería necesario tener 2 ^ 20 direcciones :

linear physical ------- --------- 00000 00001 00001 00010 00010 00011 ... (from 00011 to FFFFE) FFFFF 00000

lo que sería aún más caro que usar un TLB.

Invalidar entradas

Cuando cr3 cambia, todas las entradas TLB son invalidadas, porque se usará una nueva tabla de página para un nuevo proceso, por lo que es poco probable que alguna de las entradas antiguas tenga algún significado.

El x86 también ofrece la instrucción invlpg que invalida explícitamente una sola entrada TLB. Otras arquitecturas ofrecen incluso más instrucciones para las entradas de TLB invalidadas, como la invalidación de todas las entradas en un rango determinado.

Algunas CPU x86 van más allá de los requisitos de la especificación x86 y proporcionan más coherencia de la que garantiza, entre modificar una entrada de tabla de páginas y usarla, cuando ya no estaba almacenada en caché en el TLB . Aparentemente, Windows 9x se basó en eso para ser correcto, pero las CPU modernas de AMD no ofrecen caminatas de página coherentes. Las CPU Intel lo hacen, a pesar de que tienen que detectar la mala especulación para hacerlo. Aprovechar esto probablemente sea una mala idea, ya que probablemente no haya mucho que ganar, y un gran riesgo de causar problemas sutiles sensibles al tiempo que será difícil de depurar.

Uso del kernel de Linux

El kernel de Linux hace un uso extensivo de las características de paginación de x86 para permitir switches de procesos rápidos con fragmentación de datos pequeños.

En v4.2 , mira debajo de arch/x86/ :

  • include/asm/pgtable*
  • include/asm/page*
  • mm/pgtable*
  • mm/page*

Parece que no hay estructuras definidas para representar las páginas, solo macros: include/asm/page_types.h es especialmente interesante. Extracto:

#define _PAGE_BIT_PRESENT 0 /* is present */ #define _PAGE_BIT_RW 1 /* writeable */ #define _PAGE_BIT_USER 2 /* userspace addressable */ #define _PAGE_BIT_PWT 3 /* page write through */

arch/x86/include/uapi/asm/processor-flags.h define CR0 , y en particular la posición del bit PG :

#define X86_CR0_PG_BIT 31 /* Paging */

Bibliografía

Gratis:

  • rutgers-pxk-416 "Gestión de memoria: notas de conferencia"

    Buena revisión histórica de las técnicas de organización de la memoria utilizadas por sistemas operativos anteriores.

No libre:

  • bovet05 capítulo "Direccionamiento de memoria"

    Introducción razonable al direccionamiento de memoria x86. Faltan algunos ejemplos buenos y simples.