Cómo funciona la RAM (I): SRAM y DRAM

En un artículo anterior (en inglés) comenté sobre La cache de CPU y cuellos de botella de memoria y cuánto me fascina el artículo de What Every Programmer Should Know About Memory. Esta vez voy a hacer un extracto de ese artículo para la parte de la memoria para que lo podáis disfrutar sin tener que comerse 100 páginas en inglés bastante densas.

El error más común es creer que leer de la RAM es un ciclo de CPU o que siempre tarda lo mismo. Éstas creencias se ven reforzadas porque cuando transformamos un programa de C a Ensamblador, la carga de RAM toma únicamente una instrucción de CPU. Por ejemplo:

char test() {
    const char *addr = (const char*)0x1000;
    char val = *addr;
    return val;
}

Al compilar nos da:

test():                               # @test()
        mov     al, byte ptr [4096]
        ret

Podéis probar vosotros mismos aquí: https://godbolt.org/z/rNtBs9

De la compilación podemos ver que básicamente hay dos instrucciones:

  1. Copiar los datos del byte 4096 de la memoria al registro “al”
  2. Salir de la función (El valor en “al” es el valor de retorno)

¿Si sólo toma una instrucción cómo es que no tarda un ciclo de CPU? Es gracioso, el lenguaje ensamblador o incluso los binarios compilados son de demasiado alto nivel para ver lo que está pasando realmente. A nivel eléctrico las cosas son muy distintas, la CPU tiene que considerar si esa memoria está en cache o tirar de RAM. En cualquier caso, la CPU realiza operaciones varias veces más rápido que la cache y que la RAM, por lo que tiene que esperar. Es trabajo de la controladora de memoria del chip gestionar esto y avisar a la CPU cuando la memoria esté cargada. (Expliqué esto con mas detalle en el otro artículo)

No caigamos en el error de pensar que simplemente cada acceso RAM tarda X. La realidad es que se parece más a un disco duro de lo que parece a simple vista. Los accesos secuenciales son más rápidos y los aleatorios son muy lentos.

Para entender cómo funciona la RAM hay que bajar al nivel eléctrico, cómo está hecha y cómo se lee, escribe y se mantienen los datos guardados en ella. Vamos a ello.

Tipos de RAM

El concepto de Random Access Memory cubre un espectro bastante amplio de componentes, aunque vamos a ver sólo dos: los clásicos sticks de RAM son Dynamic RAM (DRAM) y la caché del procesador es Static RAM (SRAM).

La SRAM es mucho más rápida pero también mucho más cara. La DRAM por otro lado es muy barata de producir, y aún siendo más lenta, sigue siendo tremendamente rápida.

SRAM (Cache de CPU)

Ésta memoria usa únicamente transistores y almacena la información con circuitos flip-flop. Aquí un ejemplo básico:

File:Transistor Bistable interactive animated-en.svg
Flip-flop. Haz click en la imagen para demo interactiva (Wikipedia)

Los circuitos para SRAM usan seis transistores (y no dos). Por cada bit que quieres almacenar necesitas de un circuito de estos, por lo que cada byte require de 48 transistores. Requieren de alimentación contínua, si la pierden aunque sea por un nanosegundo, pierden la información.

Para mejor referencia, el circuito típico es el siguiente:

File:SRAM Cell (6 Transistors).svg

WL es “Word Line” y es el selector del byte, fila o región que se quiere leer; se activa a la vez en todas las celdas contiguas de la misma región. En BL aparece el bit (1 o 0) y Q sirve para escribir. Los BL y Q de la izquierda son exactamente lo mismo pero con el valor invertido.

DRAM (Memoria DDR y similares)

La RAM dinámica es mucho más simple en comparación. Simplemente tiene un condensador y un transistor:

Ocho bits de memoria DRAM

Esto explica la gran diferencia de coste entre las dos. Además, se puede apreciar en el esquema que puede crecer con mucha facilidad hacia la derecha y hacia abajo, sólo copiando y pegando los mismos componentes una y otra vez.

El estado se almacena en un condensador. Los condensadores son capaces de almacenar carga, como baterías que puedes cargar y descargar, pero el funcionamiento es puramente electromagnético y las baterías son químicas. Para comprender lo que sucede en esta memoria basta con imaginar pequeñas pilas recargables, pero si queréis un mayor detalle, recomiendo el video de ElectroBOOM en Youtube:

Lo que hace el circuito es habilitar un bloque de condensadores al activar la señal “Word Line” (en rojo) y la carga del condensador de puede leer en las líneas de bit (en azul). Si queremos escribir un “uno” sólo tenemos que dar tensión por esta línea y el condensador se cargará. Si queremos escribir un “cero”, simplemente cortocircuitamos y se descarga.

Resultado de imagen de charge discharge capacitor

Como se puede apreciar en el gráfico, la carga y descarga no es instantánea sino que toma un tiempo, aunque pequeño, es muchísimo más que lo que tarda la SRAM en escribir.

Los condensadores pierden carga con el tiempo y para el minúsculo tamaño usado en la RAM las pérdidas son enormes, por lo que cada poco hay que leer y reescribir la memoria para evitar que las cargas bajen tanto que sean ilegibles. Esta operación se le llama memory refresh y suele ser cada 64 milisegundos. Mientras una parte de la memoria está siendo refrescada ésta no se puede usar.

Otro problema es que para leer la memoria hay que conectar el condensador, por lo que se descarga. Ésto se soluciona reescribiendo el dato leído mientras sucede la operación de lectura. Esto implica tiempo adicional para recargar el condensador cuando se lee.

Pero todos estos problemas son pocos comparado con su mayor ventaja, el tamaño. Las celdas usadas son muy pequeñas y es posible colocar muchos bits de memoria dónde en SRAM sólo cabe uno. Las celdas SRAM también necesitan de alimentación constante, cosa que no es necesaria en DRAM (sólo con el refresh cada 64ms es suficiente). El esquema de la DRAM también es más sencillo y fácil de repetir, lo que significa que empaquetar muchas celdas más juntas con menos espaciado es más sencillo.

Al final, DRAM es mucho mejor en términos de coste y excepto en algunos casos especializados, lo normal es que nuestros programas corran sobre éste tipo de memoria.

En el pŕoximo episodio…

Veremos cómo funciona el acceso a la RAM, los diferentes tiempos de acceso RAS y CAS y cómo se transmiten los datos. Suscribíos al blog o a mi cuenta en Twitter @deavidsedice para no perderos las siguientes entregas!

Cpu cache and memory bottleneck

Nowadays most programmers are coding in some kind of scripted language, Python, JavaScript, PHP, Bash, and so on. Even for those that still work with stricter languages it might be still unknown how a CPU Cache works, what is its purpose and how programmers should be aware of it.

Time ago I read a paper in PDF titled “What every programmer should know about memory”, and blew my mind. First, because what they think everyone should know I bet 99.9% of developers don’t want or don’t care. The paper was way too technical into details for regular mortals. But secondly, it demonstrated that you can use this knowledge to make programs run several times faster.

But not only programmers should know how memory works in a computer. Also System Engineers and even people that is purchasing servers should be aware more or less on how it works because it affects how fast the system runs.

Simple understanding of cache and memory

The CPU runs way faster than memory, around 300 times faster. So from CPU perspective, RAM memory is quite slow. To speed things up the CPU contains its own memory, mainly used for caching RAM. This speeds things up a lot because CPU cache is really fast and it’s really close to the actual computing unit.

Because being closer is crucial to get blazing speeds, the majority of CPU splits this memory in three layers:

  • L1: The fastest and closest to the chip and the smallest, with only 32kB. If there are multiple cores on the CPU, each one has its own L1.
  • L2: A middle ground between L1 and L3, with 512kB. Also is per core on most chips. Not as fast as L1, but still blazing fast.
  • L3: The largest cache on the chip and the slowest with 8MB. On some systems L3 is shared, in others is per core.

The sizes I just described are just for reference so you get an idea. Each CPU model has its own sizes and speeds for cache. For example some Threadrippers have 40MB of L3 Cache.

Don’t be fooled thinking that L3 is slow. It actually is 15 times faster than RAM. It’s slow compared to L2 that is 40 times faster than RAM. And L1 is 170 times faster.

The CPU Core also has another memory type which is even faster than L1: registers. These operate twice as fast as L1 and their only role is to hold the temporary data for the operations. This is architecture dependent, so different CPU models have the same amount of registers. Even if they have more, the programs need to be compiled differently to be aware and make use of those.

Why we should care

Usually we buy chips just by its performance, how many cores it has, which frequency and so. Cache size is usually omitted and is a critical aspect of a CPU performance.

Almost all operations that can be done by a CPU require memory access; even adding two numbers (A+B) requires reading “A” and “B” from memory and storing the result back to memory. So those are three memory operations in a single instruction.

Resultado de imagen de AMD ThreadRipper"

Without any cache at all, the CPU would work 100 times slower or more. But once the cache is big enough adding more does not add more speed. Running a normal program on an AMD ThreadRipper 3990X that has 288MB of cache will not use all that memory available on the CPU.

The cache enables the CPU to read and write to RAM in the background. Yes, you’ve read it right: The CPU itself does some multitask even having a single core. It inspects the program ahead and predicts which data you’re likely to read and starts pulling it to cache before you actually want to read it. On writes does the reverse, stores on cache and on the background starts writing to RAM without costing any CPU cycles at all. The CPU is quite smart, right?

So if your cache is big enough your system won’t suffer the slowness of RAM at all. But cache is one of the most expensive parts of a CPU, if you try to buy a model with bigger caches it will cost you way more. So it is important to know which sizes are good enough for the system you want to build.

For a regular desktop where basically there is one active program (as the user is only capable of managing one program at once) it should suffice with 8-16MB of cache. Unless, of course, one of those programs requires a big working set of memory.

For servers, usually we put tons of services inside all running at the same time. In this case the size of cache matters a lot, as all the programs will be fighting for resources in cache. Unless is a small server for a handful of users, where there is low chance of actively using all services at once, we should also look for a CPU with a bigger cache.

What is the working set of a program

You might be wondering what I mean by working set. Is the memory that a program uses? Well no, the working set is the size of the memory that the program uses really frequently.

Let’s say we have a stupid program that puts a 4GB file on memory and wants to compute the SUM of all its numbers. To perform this, at any given time, you only need to have in hand 3 numbers (because A+B=C only has 3 variables). Because each number is 64 bits or 8 bytes, the working set is more or less 24 bytes.

Of course this program is reading left to right, so it benefits from having the numbers already on cache, but the CPU is smart and will pull the next numbers ahead of time as long they’re contiguous in RAM. Because the cache usually pulls from RAM in blocks of 1kB, this program only requires 2kB of cache; one for the program’s use and another to fill ahead of time.

So despite this theoretical program uses 4GB of memory, it only benefits of 2kB of cache.

Other programs, like video encoding, might benefit from any cache size smaller than the memory used by the process. This is because video encoders tend to load into memory only the data that is processing and drops afterwards, and as a very least, they need to do complex computations on a full frame, so having the video frame in cache will help a lot.

In the other hand, file compression tends to have a quite small working set for fast compression, but when asked to do the best compression it may grow to 8MB. This is because compression works by remembering parts of the file, and for better compression you’ll need big parts of the file to achieve the best compression ratio possible.

In short: The working set can be as low as 2kB and as big as the memory used by the process. It depends on the actual operation that is trying to do.

Bottlenecks on memory

Speaking of things that get overseen, the computer has a memory bus that connects the CPU and RAM together, and it has a finite bandwidth. RAM in the other hand does not have the same bandwidth in all conditions. Like disks do, sequential access is much faster than random.

When writing programs we need to take these things in account, packing similar stuff together so it can be pulled from memory together in a sequential manner.

For system administrators, this affects context switching. If too many programs are running at once the cache will not work well if not big enough and too much request will go to actual memory. And also the memory access could be less sequential as we add more context switches per second.

Effectively this means that is preferable to run programs at a lower priority than higher. Lower priority schedules the programs with less frequency. If all major running programs have equally low priority, the system will switch less time between them, reducing context switches.

If you like rebuilding the kernel, there is a parameter called tick frequency that by default is set to 250Hz. Increasing this value to 1000Hz causes the system to feel snappier and more responsive, but creates a lot of context switches. On the other end, if it gets lowered to 100Hz, there is less CPU load, less context switches and in the end, more performance delivered. This is the preferred value for servers.

Cpu Cache size matters

I hope I got my point across without being too technical. The paper is great, but it takes a lot to digest. But if you have time and want the real knowledge, I encourage you to give it a read:

What every programmer should know about memory

Linux Overcommit (VII): ¿a favor o en contra?

Ya hemos visto toda la teoría a lo largo de esta serie de artículos:

Ahora vamos a usar todo ese conocimiento para formar una opinión más educada de qué es el overcommit y si tiene sentido o no.

Overcommit ¿sí o no?

Habiendo visto cómo funciona la memoria en sistemas operativos modernos supongo que empieza a estar más claro que ciertas preguntas que parecen tan sencillas no lo son nada en realidad.

Por ejemplo, en un sistema con zswap activo donde una docena de procesos han hecho fork y mmap entre ellos, ¿cuánta memoria ha usado cada proceso? ¿cuánta memoria queda libre? ¿funcionará un malloc de 1GB? ¿y si se hace otro mmap?

La mayoría de éstas preguntas no tienen una única respuesta, depende de muchos factores, consideraciones y de cómo se diseñe el sistema operativo en sí mismo.

Lo que sí es más fácil de contestar es si hay X páginas de memoria libre en RAM o cuántas páginas de memoria caché se pueden reclamar.

Desactivar overcommit equivale a contabilizar la memoria usada desde la llamada a malloc y dar error cuando reserve más de la memoria disponible en el sistema, pero puede que no sea la mejor idea:

  1. malloc reserva memoria en la región de memoria virtual. Quedarse sin espacio en este contexto significa realmente quedarse sin páginas virtuales para el proceso. Esto es lo que ocurre si intentas reservar más de 4GB en un proceso de 32bits. Si el proceso quiere saber el estado del sistema en su conjunto tal vez debería usar las llamadas al kernel apropiadas para esto y dejar de depender de malloc. (Véase Memoria virtual)
  2. Al haber lazy allocation no tiene mucho sentido contabilizar aquello que en la práctica no consume. Si no estamos asociando las páginas al proceso, ¿porqué le hacemos pagar por ellas? (Explicado en el artículo de Memoria virtual)
  3. Los programas reservan más memoria de la que usan. Por ejemplo el stack suele reservar entre 8MB y 20MB que raramente se usan por completo. Sin overcommit caben menos programas en memoria que si lo activamos. (Ver Porqué abortan los programas para más detalle)
  4. Es prácticamente lo mismo que un programa se cierre al no tener memoria, que el sistema operativo lo cierre porque no hay memoria. Con algunas excepciones, la mayoría de programas se van a cerrar cuando malloc devuelve NULL. (Explicado en Porqué abortan los programas)
  5. Si el programa activo no tiene bastante memoria es preferible cerrar otras aplicaciones que no se están usando a cerrar la que está trabajando. Por ejemplo, si intentas abrir darle play a un vídeo en Youtube y no hay memoria, sería mejor cerrar programas que no están en uso a cerrar el navegador. (Más detalle en Qué es el overcommit)
  6. oom_killer se puede configurar de muchas maneras distintas. Por ejemplo se le puede decir que nunca cierre ciertas aplicaciones que consideramos críticas. (Explicado en Qué es el overcommit)

Por otro lado, deshabilitar overcommit puede ser buena idea en ciertos casos.

Por ejemplo, cuando los programas que corren en el servidor sabemos que pueden gestionar correctamente que malloc devuelva NULL sin efectos adversos, el no tener overcommit facilita que las aplicaciones puedan ocupar toda la memoria disponible sin que el sistema empiece a caerse. Esto normalmente también implica que el sistema debería tener partición swap o como mucho una muy pequeña, ya que de lo contrario se ralentizaría muchísimo en estas condiciones.

Es un caso bastante específico, pero se da en algunos casos. Los programas no usarán toda la memoria realmente, porque no usan toda la memoria que reservan. Pero gracias al lazy allocation, esas páginas nunca se llegan a reservar y pueden ser usadas para caché. Esto quiere decir que incluso cuando un malloc de 4kB devuelve NULL, el sistema va a tener un poco de memoria libre que va a usar para cachear ficheros.

Windows se queda solo

Un argumento que he leído recientemente es que Windows es mejor porque no tiene overcommit. Tristemente, Windows es inferior al resto de sistemas operativos. Prácticamente todos tienen overcommit excepto éste; y es una de tantas características que le faltan.

  • Windows: no tiene overcommit
  • MacOSX: overcommit activado por defecto
  • Linux: overcommit activado por defecto
  • FreeBSD: overcommit activado por defecto

Si bien el overcommit de Linux es el que más problemas da, ésto ya no es culpa de tener o no tener overcommit, sino de la implementación específica de Linux.

Cómo funciona idealmente un sistema sin overcommit

Para que realmente un equipo sin overcommit funcione mejor que otro con overcommit, los programas tienen que reservar por adelantado la memoria que necesitarán de forma crítica. Por ejemplo si hay un error de memoria, es posible que necesite deshacer la operación y deshacer el stack. Esto requiere memoria extra, que si no se ha reservado de antemano, fallará también.

Además, todos los programas tienen que estar programados en lenguajes que reserven correctamente la memoria crítica para la aplicación; por ejemplo en Java, en ciertos casos donde se consumió hasta la última página aparecen errores inesperados y el programa se cierra.

Por lo tanto la selección de software en estos sistemas tiene que ser muy cuidadosa y testear correctamente su estabilidad en estos casos. PostgreSQL es uno de éstos dónde no tener overcommit puede ser beneficioso, siempre y cuando no haya otros programas críticos que se puedan ver afectados.

Y como comentaba antes, esto provoca que haya memoria que no se usará jamás; pero el sistema operativo verá las páginas libres y aunque los programas no puedan usarla, sí se puede aprovechar como memoria caché.

En la mayoría de casos, es indiferente

Seamos realistas, la mayoría de sistemas llevan swap. Antes de que se agote toda la memoria la swap se tiene que llenar y al hacerlo, el equipo se va a ralentizar bastante. En estos casos, como la memoria aún no se ha agotado la diferencia entre activarlo o no es nula (con la excepción de que con overcommit usa un poquito menos de swap).

Cuando sí se agota, la diferencia está entre que se cierren los procesos que estén pidiendo memoria o se cierren los que el kernel crea más conveniente. Para un servidor, que cualquier proceso se muera es igual de malo independientemente del proceso.

Conclusión

Tener overcommit activado tal y como viene por defecto trae más ventajas que desventajas para la gran mayoría de casos.

No solo no degrada el rendimiento, sino que posibilita un mejor uso de la memoria RAM del equipo. En la documentación del kernel indica que incluso reduce el uso de la swap, lo que tendría un efecto positivo sobre el rendimiento del sistema.

La función malloc se creó muchísimo antes de que los procesos estuviesen aislados y crea bastante confusión a día de hoy. Tal y como leí en Reddit “La culpa es del estándar POSIX que se hizo pensando que el proceso era el único manejando memoria del sistema”; con la diferencia que el estándar ANSI, en el que POSIX se basa, cae exactamente en el mismo error.

Aunque creo que está bien justificado y no hay nada más que agregar respecto al overcommit, sé que a muchos les parecerá insuficiente. Por eso mismo estoy preparando algunos artículos para explicar mejor la ralentización de los equipos y cómo mitigarla, así como los límites de memoria y cómo configurarlos.

Con ésto espero no sólo desmitificar el overcommit, sino también poder explicar cómo hacer que el sistema funcione correctamente, que es la raíz del problema. Pero para eso, tendréis que esperar al próximo artículo.

Suscribíos o seguidme en Twitter @deavidsedice para recibir las actualizaciones del blog

Linux Overcommit (VI): Memoria compartida

En el artículo anterior expliqué cómo funciona la memoria virtual y cómo los procesos están completamente desconectados de la memoria RAM. Si no lo has leído, sería recomendable que le dieras un vistazo antes de seguir.

Memoria compartida entre procesos

Los procesos al estar ahora completamente aislados entre sí ya no pueden acceder a la memoria de otro, pero resulta que poder escribir en la memoria de otro proceso tiene sus ventajas en cuanto a velocidad y eficiencia.

Si dos procesos pueden compartir una misma región de memoria, pueden compartir datos de forma mucho más eficiente, ya que usar canales de comunicación tradicionales conlleva unas penalizaciones muy fuertes en rendimiento. Tener que serializar, enviar, recibir y deserializar implica mucha CPU. En casos donde la velocidad es crítica, compartir la memoria es el método más rápido para comunicar dos procesos entre sí.

También, si hay un conjunto de datos que dos o más procesos necesitan acceder, si pueden compartir la memoria, los datos se pueden usar por ambos procesos estando en memoria una sola vez.

Estas ventajas también se pueden conseguir si en vez de procesos usamos hilos, sin tener que usar extras del sistema operativo para conseguirlo. Pero los procesos ofrecen un aislamiento muy bueno entre ellos, para que en el caso de fallo de una parte del programa no nos tumbe todo el servicio.

Como resultado, el problema ahora es que no hay forma de saber cuánta memoria está usando un proceso en particular. Cuando la memoria es compartida, ¿a cual de los procesos le achacamos su uso? Al primero? Al último? A todos a la vez? ¿Dividimos la cantidad de memoria por el número de procesos que la comparten?

Esto dificulta el cómputo de la memoria usada. Veamos un par de ejemplos prácticos de cómo se comparte.

fork() y la memoria CoW

En los sistemas operativos tipo Unix existe una función del kernel llamada “fork”. Ésta función lo que hace es clonar el proceso que la llama, creando efectivamente un duplicado. El proceso duplicado es capaz de distinguirse del original porque la llamada a fork() le devuelve un código distinto. Por todo lo demás, son idénticos. Todos los recursos, permisos, memoria e incluso el stack del programa son replicados perfectamente. El duplicado resume la ejecución exactamente en el mismo punto.

Esto es extremadamente útil para servidores como Apache o PostgreSQL, que tienen un proceso maestro y conforme reciben nuevas conexiones son capaces de lanzar nuevos procesos hijo (child processes) que están listos para procesar la petición inmediatamente.

La principal ventaja de hacer esto y no usar hilos (aunque los fork() siempre pueden crear sus hilos a su vez) es que si un hilo da un fallo que aborta el programa, todo el servidor se va al garete con todos los hilos detrás. En cambio, si tienes la carga distribuida en distintos procesos, pongamos por ejemplo doce, el que un proceso aborte sólo te reduce un doceavo la capacidad de proceso. Y como el proceso padre sigue vivo, puede detectar esta condición y reponer el proceso que falta rápidamente.

Cuando un proceso hace fork, ambos padre e hijo verán la misma memoria; pero la memoria no se copia para hacer fork. Se consigue con memoria Copy On Write”.

La idea detrás del CoW es que cuando uno de los procesos intenta escribir sobre la memoria, entonces es cuando se copia y el proceso pasa a escribir esa página en lugar de la original.

Para conseguir esto se modifican las páginas de la MMU para que sean sólo lectura y se captura la excepción que ocurre cuando el proceso intenta escribir. Se copia la página, se actualiza la MMU y se resume el proceso.

Esto tiene dos grandes ventajas:

  1. Hacer fork es prácticamente instantáneo y tanto el proceso padre como hijo pueden operar sin retraso alguno.
  2. Al no duplicar la memoria, efectivamente estamos ahorrando memoria de los programas ya que de otro modo estaríamos almacenando varias copias.

Los programas se aprovechan de esto haciendo que el proceso maestro se prepare y lea a memoria todos los datos que los hijos puedan necesitar. Se prepara todo y se deja el fork() para el último momento. Como resultado, cada proceso hijo puede ahorrar fácilmente 200MB; que al multiplicar por varios procesos es una cantidad muy importante de memoria.

Windows no tiene fork() ni mucho menos memoria copy on write. Para hacer lo mismo con Windows hay que crear un proceso nuevo, la memoria termina duplicada y el proceso empieza desde cero, teniendo que inicializar todos los recursos que necesite.

Compartiendo memoria con mmap

Si dos procesos hacen mmap contra el mismo fichero lo pueden usar como memoria compartida, lo que escribe uno lo puede leer el otro. Como esto lo organiza el kernel con Page Faults, a la práctica es como una región de memoria compartida que se puede hacer swap de forma independiente (escribiendo a disco el fichero) que además puede ser leída y escrita por ambos programas.

Además mmap soporta el concepto de mapear memoria sin fichero que lo resguarde (básicamente un mmap a /dev/null). Esto se usa principalmente para compartir regiones de memoria no muy grandes entre varios procesos.

El funcionamiento es exactamente igual al mmap que expliqué anteriormente, solo que ahora se complica más con bloqueos de escritura y demás. No creo que sea necesario entrar en más detalle.

Windows soporta algo similar a el mmap clásico, pero compartir memoria con él no funciona. Básicamente dos procesos haciendo un mmap a un fichero tienen las regiones de memoria duplicadas y no comunican. Compartir memoria entre dos procesos es posible, pero mediante rutinas específicas para ello.

El fin de la teoría

Si has leído toda la serie de artículos hasta aquí y has entendido todo, felicidades. Ahora sólo nos queda aplicar todo lo aprendido para razonar si el overcommit tiene sentido o no.

Lo veremos en el siguiente artículo, así que estad atentos que sale el lunes que viene!

Linux Overcommit (V): La memoria virtual

En el artículo anterior vimos las razones de que los programas simplemente se cierran cuando falla la reserva de memoria y seguramente pensabas que ya lo había explicado casi todo ¿a que sí? Pues hasta ahora sólo ha sido una explicación superficial del overcommit. Prepárate que ahora empieza de verdad.

Qué cambió con los 32 bits

El principal error al pensar que el overcommit es horrible es que creemos que cuando reservamos memoria en un programa estamos reservando RAM. Esto es falso desde los 32bits (el 80386 aparece en 1985) y es básicamente una mentirijilla que nos dicen cuando nos explican programación. La realidad es bastante más complicada.

La arquitectura de 16bits era muy limitada y los procesos reservaban memoria directamente en RAM. Las llamadas a malloc devolvían punteros a la RAM, es decir, si el proceso escribía en 0x0A0000 el procesador escribía en la RAM en esa misma dirección. Es más, si un programa quería leer o escribir una región de la memoria que no era suya, simplemente podía hacerlo. Por esto, un programa podía corromper otro o hurtar sus datos.

En aquel momento teníamos el infierno de los punteros near y far, porque las direcciones sólo cubrían 64kB y los ordenadores tenían desde 640kB hasta varios megabytes de memoria. Pero por suerte esto es agua pasada.

Con la entrada de los 32bits obtuvimos la memoria plana (flat memory) que básicamente eliminaba los punteros near y far, y hacía que todo fuese mucho más sencillo. Pero también nos dio la memoria virtual que nos ha permitido aislar los procesos entre sí, impidiendo que un proceso pueda escribir sobre otro.

Resultado de imagen de windows 95 memory

Si recordáis Windows 95 y Windows 98, supongo que también os acordaréis de los habituales cuelgues y de que la memoria libre tendía a desaparecer conforme se usaban distintos programas. Si un programa no liberaba memoria, al cerrarse éste programa se quedaba perdida hasta el siguiente reinicio. Esto cambió con Windows NT y la memoria virtual.

Cómo funciona la memoria virtual

Pensemos un poco. Si un proceso crea un puntero manualmente a la dirección 0x0A000000 e intenta escribir, ¿no debería ir a la RAM al byte numero 167.772.160 y escribir? La mayoría de sistemas tienen más de 256MB de RAM, por lo que esto debería funcionar sin problema alguno. Sin embargo, falla, y el programa se cierra al intentar escribir.

Los procesadores son bastante tontos y no pueden pararse a valorar si una operación es válida o no. Simplemente las ejecutan. El sistema operativo no puede revisar el programa instrucción a instrucción mientras se ejecuta, sería muy lento. ¿Cómo es posible entonces que ante una instrucción así el sistema lo detecte y cierre la aplicación?

Esto es porque los procesadores son tontos, pero no tanto. La arquitectura de 32bits tiene la capacidad de coordinarse con el sistema operativo para ofrecer unas garantías de seguridad.

Cuando el sistema operativo “planifica” (scheduler) un programa carga también una tabla que traduce las direcciones de memoria desde el punto de vista del programa a la memoria RAM del equipo.

Resultado de imagen de virtual memory

Esto quiere decir que cuando el proceso accede a la dirección 0x0A000000 no está accediendo necesariamente a la misma dirección en el sistema. Ésta tabla de traducción de direcciones cambia la dirección a la que realmente accede.

Si el programa accede a una dirección que el sistema no ha previsto, se produce un “Page Fault” en la CPU porque no hay entrada en la tabla y el sistema operativo puede en ese momento cerrar el programa. De este modo los procesos no pueden de ningún modo corromper o leer los datos que no son suyos.

Al cerrarse un programa, el sistema operativo ahora sabe qué partes de la memoria estaba usando y puede liberarla. Así se evita que el sistema pierda memoria cuando los programas se cierran incorrectamente o si se les olvida liberar su memoria al cerrar.

Los Page Faults y la memoria swap

Para terminar de entender la memoria virtual hay que dar un vistazo a los Page Faults porque son cruciales en el proceso. Sé que estoy profundizando demasiado para mucha gente, pero creedme que vale la pena.

La tabla de traducción de direcciones que comentaba es parte de la MMU (Memory Management Unit) del procesador y se le llama “tabla de paginación” (Page Table). La memoria se divide en páginas (normalmente de 4kB) y la MMU mantiene un mapeo (traducción 1:1) entre las páginas del proceso y la memoria del sistema con ésta tabla.

Como ya comentaba, al intentar acceder a una región que no está en la MMU se produce un Page Fault. Pero esto no es un error sino una excepción de tantas que tiene la CPU y de hecho es bastante habitual. El kernel la configura para que cuando ésto ocurra la CPU llame a un código determinado dentro del mismo kernel para manejar estos casos.

A partir de aquí, qué ocurre con el Page Fault depende enteramente del sistema operativo. Por ejemplo, podría perfectamente reservar en ese mismo momento una página de memoria en RAM, añadir la entrada en la MMU para que ese puntero resuelva ahora a esa región y resumir el programa. El programa ni se entera de lo que ha pasado y puede leer y escribir con normalidad, ajeno a la triquiñuela del kernel.

De hecho, así es cómo funciona el espacio de intercambio (Swap). El kernel cree que necesita más memoria para otras cosas y un proceso no se está usando. Entonces sólo tiene que borrar las entradas de la MMU que crea conveniente y copiar la memoria al disco duro. Si el proceso se ejecuta, pero no intenta acceder a esa memoria que se ha movido, todo funciona sin más. Si intenta leer esa memoria, la MMU no encuentra la página por lo que la CPU devuelve un Page Fault. En ese momento el kernel interviene, copia los datos del disco a la memoria (tal vez a otra región distinta) y crea las entradas de la MMU a la nueva región. El programa resume y todo funciona.

Para resumir, una dirección de memoria 0x0A000000 resuelve a direcciones de memoria distintas en distintos programas. Ambos creen estar accediendo al mismo sitio pero realmente son totalmente diferentes.

Cómo funciona el mmap

Ya que estoy explicaré qué es un mmap en Linux y cómo funciona. Memory MAPped file (mmap) es la idea de que un fichero grande del disco se pueda acceder como si fuese memoria. Es muy conveniente porque puedes acceder a cualquier parte del fichero sin tener que estar moviendo un cursor de lectura y escritura.

Normalmente tendríamos que leer todo el fichero en memoria para poder hacer esto, pero creando un mmap el kernel nos da una dirección de memoria y podemos leer y escribir la parte que queramos del fichero. Todo esto, sin necesidad de leer el fichero ni reservar memoria.

El mecanismo es muy similar a la swap pero contra un fichero que queramos. El kernel nos da una dirección de memoria que no existe. Llamemos a ésta dirección “F”. Nuestro programa puede intentar leer en “F+4000” para acceder al byte número 4000 del fichero:

char* F = mmap(...);
printf("%c\n", F[4000]);

Cuando ésto ocurre, se genera un Page Fault y el kernel procede a leer la región del fichero de interés, la carga en memoria y el proceso continúa, leyendo en esa región de memoria.

Como es el kernel el que maneja la carga y descarga de los datos, tiene total libertad para leer más de la cuenta cuando hay memoria de sobra, por si el programa pretende trabajar con los datos de esa zona, que es bastante común. O de liberar la memoria, aunque esté en uso, cuando la memoria escasea.

Es una estrategia bastante interesante porque deja en manos del kernel la presión de memoria del sistema, por lo que programas basados en mmap suelen poder manejar cantidades de datos muy grandes respetando los otros programas, sin apenas configuración. Una estrategia muy similar es usada por PostgreSQL para leer y escribir en la base de datos. MySQL por el contrario usa el clásico malloc, por lo que tienes que configurar exactamente cuánta memoria quieres que use; Si te pasas, saturará el sistema, si te quedas corto, irá lento.

Usar mmap facilita la convivencia de los distintos programas en un mismo sistema porque el kernel es consciente de todo el sistema, mientras que el proceso generalmente está aislado y no es consciente de que está ralentizando todos los demás programas.

Lazy memory allocation (reservando memoria en la práctica)

Ahora que ya entendemos cómo funciona la memoria virtual, vamos a temas más cercanos. En los 16bits, la llamada a malloc para reservar memoria, evidentemente reserva memoria RAM. Pero, ¿y en los 32bits?

Lo que el proceso ve como memoria es realmente memoria virtual por lo que una llamada a malloc, estrictamente hablando, está reservando memoria en la región de memoria virtual específica del proceso. Si esa memoria virtual acabada de reservar está respaldada o no por memoria RAM deja de ser de importancia para el proceso y pasa a ser responsabilidad específica del kernel, si cree conveniente o no asociar memoria real cuando un proceso llama a malloc.

Describí antes un supuesto dónde en 32bits un sistema operativo podría decidir que malloc no hace nada y reservar memoria al vuelo al acceder, es más real de lo que parece a primera vista.

A día de hoy todos los sistemas operativos (o casi todos) usan lo que se llama “lazy memory allocation”:

Cuando un programa llama a “malloc”, el sistema operativo básicamente ignora la llamada y toma nota para reservar en el espacio de memoria virtual, pero no toca la RAM, ni escribe ninguna entrada en la MMU. Cuando el proceso intenta acceder a esta memoria, se produce el PageFault, dónde el sistema operativo aprovecha para reservar la memoria en RAM conforme el proceso la va usando.

int bytes_reserved = 1024*1024*1024; // 1GB

// Esta llamada es instantánea:
char *mem = (char *) malloc(bytes_reserved); 

// La reserva de memoria en RAM ocurre aquí:
memset(mem, '_', bytes_reserved);  

// Y se libera aquí:
free(mem);

Antiguamente, en 16bits (o sistemas operativos antiguos de 32bits), la llamada a malloc tomaba cierto tiempo (muy poco, pero se notaba). Hoy en día, la llamada a malloc es instantánea y tarda tan poco como cualquier otra llamada básica al kernel.

La reserva de memoria en RAM ocurre por páginas, conforme los PageFaults van ocurriendo. Por supuesto, el kernel es libre de reservar bloques más grandes si cree que el proceso está intentando inicializar toda la memoria.

Dicho esto, hay dos puntos que hay que dejar bien claros respecto al “lazy memory allocation”:

  1. No tiene nada que ver con el overcommit. Lazy allocation maneja en qué momento reservamos RAM, mientras que el overcommit cambia cómo se contabiliza la memoria usada de un proceso.
  2. Windows también usa lazy memory allocation. Puedes realizar un millón de mallocs y va a tardar virtualmente cero y la RAM no se asocia al proceso hasta que éste no la usa. Sin overcommit, desde el malloc hasta el memset la memoria no está reservada, pero se contabiliza como consumida.

En resumen…

Hace mucho tiempo que los procesos sólo ven memoria virtual y no ven lo que está pasando en el sistema. La memoria ya no se reserva en RAM al hacer malloc ni en Windows.

La tarea recae completamente en el kernel y no es nada sencilla. En el próximo artículo veremos cómo se complica al agregar ciertas funcionalidades que no están en Windows.

Abrocháos el cinturón y seguid de cerca el blog, que el próximo artículo sale pronto!

Linux Gaming: Things have changed

Rust was first on dropping support and now Rocket League has recently followed its steps. What’s going on here? They both argue that there’s almost no player base in Linux and it’s not worth the hassle.

Something feels odd about that and I can’t tell what it is…

Wait a second…

Since when commercial games do support Linux?!

Just 10 years ago it was quite bad but no one cared. We had our FOSS games on Linux, small things I used to pass time like TORCS or Warzone 2100. Yes, graphically they were quite outdated but quite fun to play. Debian GNU/Linux had in their packages a huge collection of games. We also had closed source ones and some old engines had ports to Linux so it was possible to play games similar to Counter Strike on Linux.

Resultado de imagen de warzone 2100"

We also had Wine, which was mainly used to run Windows programs but it could also be used to run some Windows games. The support was horrible and most of the time you needed a very particular version and installation of Wine, making it almost impossible to use. Some Windows games on the era had slightly more performance using Linux even they were using a translation layer on top (wine).

In 2012 and 2013 Steam added Linux support and announced SteamOS, which was based on Linux itself. This attracted a few developers, but not quite.

Fast forward to 2018, Proton launched and this emulation layer which was like Wine but specific for games. They took it really seriously and they also tweak per game, meaning that new releases usually don’t make working titles to fail. Over the first year they managed to get a good portion of the games working.

Nowadays of the the top 100, 76 games are working properly on Linux, either natively or via Proton. Of the 24 remaining, 9 are generally playable with minor issues and other 4 work but some issues prevent from enjoying properly the game. Only 11 games of the top 100 are not playable at all under Linux; of which, only 3 are top 10 games.

Resultado de imagen de the witcher wild hunt"
Witcher is one of the games that are working pretty well on Linux with Proton

Proton ships with Steam, so even in Debian that things usually require some tweaks is really hassle free. I remember I installed Steam years ago and Proton simply works.

As can be seen in the graphs around 30% of games have native versions that do not require Proton. 3D Engines have simplified this process a lot and are offering the ability to do Linux builds quite easily.

One of the main drawbacks of games in Linux is every platform is different, every computer has its own customization, different desktop, different X Server, etc. This was really hard because sometimes commercial games didn’t know which flavor to support. When the game is FOSS it’s easy, build it and get it working for your system libraries. Still doesn’t work on a particular distro? They can easily patch the game to make it work. But when that’s not the case the libraries required by the game may not be in your system. Patching is not an option. So having a standard distribution helps a lot.

Ubuntu helped in this regard since the first moment. Being the most popular distribution for Linux and being used by new users to Linux, it was ideal to be the primary target. Also other distributions that are even more user friendly usually are derived from Ubuntu, so in beneath, there is a Ubuntu system.

Resultado de imagen de ubuntu"

Moreover, Ubuntu is based on Debian, and most distributions out there are based on it. So supporting Ubuntu is indeed one of the best options for a game. Still, Ubuntu releases new versions twice a year, and libraries may disappear or get newer versions that are binary incompatible. This was still a challenge.

But Steam has streamlined this a lot, their platform just works no matter what. I had some minor problems myself but basically because I uninstalled drivers on an upgrade; so this is my fault, and was on Debian. On Ubuntu, using the recommended methods shouldn’t happen at all.

For the reasons described, Steam does not support distribution other than Ubuntu; In fact they refer to an old LTS version. In non-Debian based distros it also works, but it requires a bit of knowledge and tinkering to get it working. Not much for the average Linux users, but is not as easy as on the supported one.

The future looks good for Linux

Games dropping support for Linux might be a good signal. It means several things:

  • Those games had support for Linux in the first place. Now they don’t care anymore.
  • This means they didn’t cared either when adding support back then, so it was pretty easy for a lot of creators.
  • That’s because engines are adding support for Linux and it’s quite easy to get it working.
Resultado de imagen de google stadia"

Also, don’t forget that Google Stadia runs on Linux servers. Either using Proton or native, the games have to actually work on this platform. Google has put a lot of effort on this, and it should create some noticeable pressure on developers and engines for supporting Linux.

So I truly believe gaming in Linux is going to be a thing in just another 5 years. As it is right now, it’s quite enjoyable already but the lack of some titles are still a problem.

That’s it for now! I’d like to write later on this topic again to explain why they are actually dropping support for Linux, but that’s for another day.

Linux Overcommit (IV): Porqué abortan los programas

Volviendo a temas más relacionados con el overcommit, quiero dar caña a ese concepto de que los programas deberían ser capaces de gestionar correctamente cuando el sistema se queda sin memoria.

En el artículo anterior expliqué la memoria caché y el swappiness. Si eres de los que piensa que la swap es mala, te recomiendo encarecidamente que leas el artículo.

Porqué los programas abortan cuando no pueden reservar memoria

Se dice mucho de que es un mal hábito de programadores, de que los programas están mal hechos, etcétera. Pero como todo, el diablo se esconde en los detalles.

Para que un proceso se pueda quedar sin memoria y sobreviva sin daños colaterales es necesario controlar todas las partes y todas las dependencias a la vez con mucho esmero.

En la mayoría de casos, no sale a cuenta. Al igual que antiguamente un juego podía correr en 100kB de memoria y hoy en día necesita 8GB, hacer que una aplicación gestione correctamente toda la memoria incluídas sus dependencias es casi imposible.

Pongamos por ejemplo un juego, y el jugador entra a una habitación y tienen que haber 100 enemigos. No hay memoria suficiente para todos, pero el error aparece al crear el enemigo número 75. ¿Qué haces?

  1. Cierras toda la aplicación y haces aparecer un error de memoria agotada. El usuario pierde los datos no guardados.
  2. Lo dejas con 74 enemigos y dejas que el jugador continúe. Cuando el usuario lanza una granada, ésta ya tampoco cabe. ¿Ahora qué?
  3. Implementas un sistema transaccional que es capaz de deshacer toda la carga de enemigos y restaura los valores a la última posición válida. Pero este sistema necesita de más memoria por lo que te falla también. Así que tienes que reservarla de antemano al cargar el juego, una cantidad al azar que te garantice que funcionará cuando pase. Así que consumes 100MB más sólo por si acaso. Después de todo el curro que te has pegado, resulta que no vale de nada porque el usuario termina en un bucle infinito: Se cargan 74 enemigos, se restaura la posición, el jugador vuelve a avanzar y falla de nuevo. Ad infinitum.

Ciertas aplicaciones tienen un único cometido y fallar es la única opción con sentido. Por ejemplo todas las utilidades tipo find, sed y grep si se quedan sin memoria lo mejor que pueden hacer es abortar. El problema es que otros scripts, por ejemplo de backup, dependen de ellas y que aborten puede implicar que falle un backup o que termine corrupto. Esto son las dependencias. Tu programa depende de otras librerías, de otros programas. Para que sobreviva correctamente debes tenerlas todas en cuenta y analizar cómo falla cada una de ellas.

Otras, como por ejemplo programas de edición de imagen, pueden predecir cuánta memoria van a usar con una operación, pueden preguntar al sistema la memoria libre y dar error incluso antes de empezar con ella.

Hay casos dónde la cantidad de memoria que se va a usar no se sabe ni en el mismo momento; por ejemplo si estás procesando un stream de datos por la red conforme viene. No puedes saber el tamaño hasta que termina. En algunos casos puede ser buena idea abortar el proceso del stream actual para poder seguir procesando los siguientes. Pero no siempre.

Finalmente, hay casos donde sale a cuenta. Las bases de datos suelen llevar ya sistemas de transacciones y están preparadas para fallar a medias (o deberían estarlo). En estos casos es posible gestionarlo correctamente siempre y cuando el lenguaje de programación usado ofrezca las herramientas adecuadas.

Entrando en más detalle

Como ya comenté en la primera entrada de esta saga, la función que se encarga de la reserva de memoria es malloc() en C. Todos los demás lenguajes, o bien están basados en C de algún modo, o implementan una llamada muy similar. Al final es una llamada al kernel, por lo que el sistema es el mismo independientemente del lenguaje de programación.

Como C es el lenguaje más próximo al kernel se ve muy claro lo que ocurre:

int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

Lenguajes como PHP o Python no tienen estos conceptos. En PHP lo normal es que la página web que estábamos cargando falle con un error; pero de normal PHP no aborta; aunque si el sistema está realmente sin recursos podría fallar el proceso entero. Esto implica que Apache pierde un proceso y lo tiene que crear de nuevo. Si PHP estuviese con Apache como hilos (que no es posible), Apache se cerraría por completo.

En el caso de Python devuelve una excepción, que deshace el stack hasta que encuentra un punto donde gestionamos el error; pero como normalmente no hay ninguno, cerrará el programa. En ciertos casos se ha reportado que incluso gestionando el error a veces Python se cierra abruptamente porque necesita memoria para gestionar la misma excepción.

Prepararse para un fallo de malloc tiene sentido principalmente en algoritmos que reservan cantidades ingentes de memoria de un solo golpe:

int *array = malloc(10000000 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

En estos casos es bastante viable recuperarse del error, porque quizá no hayan 100MB libres, pero sí 50MB. Por lo tanto el programa aún tiene espacio de maniobra para recuperarse.

Por otro lado, si esperamos que el programa pueda sobrevivir en operaciones tan simples como leer 4kB de un fichero tendríamos que reservar desde el principio toda la memoria que creemos que va a ser crítica y tener un sistema bastante complejo que sea capaz de usar una memoria u otra según las condiciones en las que estamos.

Hasta la pila de llamadas (stack) puede causar problemas; en principio es fija, pero puede crecer. Por eso también sería necesario tenerlo en cuenta y reservar esa memoria adicional por adelantado.

Algunos programadores se lo toman muy en serio, un ejemplo:

https://github.com/MIvanchev/NppEventExec/blob/a78a579921578c1d920946c9c498ecc0a7c3c380/queue_dlg.c#L647

En la mayor parte del código cuando no hay memoria permite un resultado a medias que es aceptable:

    if (!(entries = reallocStr(dlg->posEntries, newEntryCnt * POS_ENTRY_LEN)))
    {
        /* TODO warning
        **
        ** We cannot allocate enough entries, but that's not a fatal issue
        ** because a placeholder will be shown instead of the actual number.
        */

        return;
    }

Pero en otras es imposible:

    if (!(dlg = allocMem(sizeof *dlg)))
    {
        /* TODO error */
        goto fail_mem;
    }

En definitiva

Cuando el sistema se queda sin memoria, hasta las aplicaciones más preparadas van a empezar a hacer cosas raras. Errores en páginas web, diálogos que muestran datos a medias, transacciones fallidas que normalmente funcionan, etc.

La norma es abortar el programa en estos casos. Las excepciones son programas y librerías que tienen cometidos críticos, y en estos casos se maneja lo mejor que se puede. Pero aún así la aplicación no se va a comportar correctamente.

Entendido esto, vamos a ver la memoria virtual en el próximo capítulo. Suscribíos al blog y estad atentos!