saltar al contenido

Asignador de memoria para RDM 14.2

Introducción

El asignador de memoria para RDM anterior a 14.2 se diseñó principalmente para ofrecer flexibilidad en lugar de velocidad. En ciertos casos, el rendimiento podría caer drásticamente. Una característica que hemos eliminado de este nuevo asignador de memoria es la capacidad de asignar memoria usando un identificador y luego liberar toda esa memoria asociada con el mismo identificador a la vez. Si bien esta característica facilitó evitar pérdidas de memoria dura (memoria que no se libera al finalizar), en su lugar, a menudo tendríamos pérdidas de memoria blanda (memoria que no se usa después de una determinada condición pero que eventualmente se liberará).

En RDM 14.2, diseñamos un nuevo asignador de memoria con el objetivo de resolver los problemas que teníamos con el antiguo asignador de memoria. Es un diseño completamente nuevo optimizado para la velocidad a costa de tener que reescribir gran parte de nuestro código que necesitaba asignaciones dinámicas. Para RDM 14.2, también hemos rehecho muchos subsistemas de tal manera que ya no hacemos agrupaciones de memoria, asegurándonos de usar la memoria de la pila del sistema o usando API que tienen el objeto asignado estáticamente dentro de otros objetos. 

Las principales características del asignador de memoria son, desde una vista de nivel superior:

  1. Las asignaciones y las liberaciones se realizan mediante identificadores.
  2. La memoria asignada debe liberarse explícitamente
  3. La mayoría de las asignaciones y liberaciones de memoria son del orden de ejecución O (1)
  4. Hay varias implementaciones alternativas
  5. Un asignador maestro está manejando asignaciones de páginas 4K
  6. Los subasignadores están manejando asignaciones menores a 2K
  7. Un asignador de pila
  8. Asignador de pila del sistema

Implementaciones alternativas

Nuestros asignadores de memoria tienen una serie de implementaciones alternativas que se pueden seleccionar en tiempo de compilación. Algunas de estas implementaciones difieren en las características de rendimiento, mientras que otras se utilizan con fines de depuración y control de calidad.

Por ejemplo, tenemos una implementación que se encuentra en la parte superior de malloc y es gratuita que se puede usar con herramientas de perfil de memoria para encontrar problemas que incluyen saturaciones de búfer, pérdidas de memoria y problemas de subprocesos. Purify (Windows), Memcheck (Unix), Helgrind (Unix) y efence (Unix) funcionan con esta implementación. También tenemos una implementación que está integrada con nuestro marco de prueba para realizar simulaciones de fallas de memoria. Por último, también hay una implementación que puede perfilar los tamaños de asignación. Estas tres implementaciones no se discutirán más en este documento.

Uso de asas

El nuevo asignador utiliza identificadores similares al asignador anterior. La gran diferencia es que el nuevo asignador es completamente reentrante. El antiguo asignador tenía un concepto similar al de nuestro subasignador, pero no había asignadores maestros. El antiguo asignador usaba algún estado global, donde la forma en que algunos de los diferentes subsistemas se configuraban y cerraban era desordenada y no fácil de revisar. El nuevo asignador y un rediseño de nuestra capa de soporte de plataforma (PSP) lo han hecho mucho más fácil.

Debido a este nuevo diseño de asignadores, ahora se pueden incrustar dos instancias de RDM en un proceso o espacio de direcciones sin que las asignaciones de una afecten las asignaciones de la otra. Ambas instancias crean una instancia de su propio asignador maestro, y esos identificadores se utilizan directa o indirectamente para cada asignación posterior. Esto también es lo que hacemos en nuestro marco de pruebas de control de calidad. Se utiliza un asignador maestro en el producto y otro en el marco de pruebas de control de calidad. Esto permite que los posibles problemas de memoria en el marco de pruebas de control de calidad no afecten al producto que se está probando o viceversa, y se pueden realizar perfiles de memoria incluso para las pruebas que utilizan el marco de pruebas de control de calidad.

Se pueden recuperar dos tipos de asignadores del asignador maestro: el asignador secundario y el asignador de pila. Estos asignadores también devuelven identificadores y sus implementaciones obtendrán su memoria del asignador maestro.

Enhebrar

Los nuevos asignadores de memoria se han diseñado teniendo en cuenta los subprocesos. El asignador maestro es el único asignador que se puede utilizar desde varios subprocesos. Los subasignadores no tienen protección de subprocesos incorporada. Cada subasignador normalmente solo debe usarse de un subproceso a la vez. También se supone que las asignaciones de memoria y el uso de las mismas es local para un hilo para ayudar con la localidad.

Una excepción es cuando un subasignador se ocupa de asignaciones superiores a 2K. En este caso, es seguro asignarlo y liberarlo de varios subprocesos al mismo tiempo, ya que esas asignaciones están diseñadas para ser manejadas por el asignador maestro.

Paginación e intercambio de páginas a disco

Para los sistemas con memoria virtual, es importante evitar la distribución aleatoria de las asignaciones en más páginas de memoria de las necesarias. Esto se hace haciendo que el asignador maestro divida la memoria en páginas que estén exactamente alineadas a 4K. El asignador principal conserva los metadatos de las páginas que administra por separado. De esa forma, no es necesario tocar una página que se está liberando. En el caso de que la página haya sido paginada, permanecerá paginada. Un subasignador también utilizará varias páginas exclusivamente. Se supone que este enfoque ayuda a evitar el uso excesivo de la memoria virtual (aunque sea solo un poquito).

Rendimiento de la caché

El asignador maestro alinea las asignaciones de memoria a 4K y el subasignador tiene la capacidad de alinear los datos a 64 bytes (según el perfil compilado). Esto asegura que las asignaciones crucen la menor cantidad posible de líneas de caché de 64 bytes. Algunos de nuestros algoritmos se basan en esto, por lo que podemos garantizar como máximo una pérdida de caché.

Mitigar las pérdidas de memoria

En el caso de que haya pérdidas de memoria, las afirmaciones en el código se activarán cuando esté en modo de depuración. En el modo de liberación, todas las asignaciones derivadas del asignador maestro se liberarán cuando se destruya un subasignador, un asignador de pila o el asignador maestro.

El asignador maestro

El asignador principal, como hemos descrito anteriormente, es responsable de la asignación de páginas. Cuando se han asignado varias páginas, solo se necesita el identificador del asignador maestro y un puntero al inicio de la memoria para liberar las páginas.

El asignador maestro solicita grandes bloques de memoria del sistema operativo. Cada uno de estos grandes bloques tiene un encabezado. Para cada página de 4K, hay una pieza de memoria correspondiente en el encabezado que se utiliza para administrar la página. Si la página es la cabeza o la cola de una asignación o una región de memoria libre, hay información sobre esto, así como su tamaño. Esta información se utiliza a medida que se liberan las páginas, donde podemos combinar de manera eficiente regiones de memoria en regiones más grandes. El invariante para esto es que nunca hay dos regiones de memoria libres una al lado de la otra, y que toda la memoria fuera del encabezado está libre o asignada con información para cada página principal, y cada página final para cada asignación y región libre que muestra tal . Todas las demás páginas entre una cabeza y una cola están marcadas como sin cabeza o cola.

La información correspondiente en el encabezado también tiene espacio para un nodo de árbol de búsqueda binaria (AVL) autoequilibrado que se usa para mantener un AVL de todas las regiones de memoria libres ordenadas por tamaño. Usando este AVL, podemos encontrar un tamaño de ajuste con un orden de O (log n) donde n es el número de regiones de memoria libres. Dado que combinamos memoria libre en regiones, y siempre usamos la región libre más pequeña que se ajusta a una asignación, se supone que n es pequeño en comparación con el número de páginas.

La asignación y liberación de páginas solo usa memoria en el encabezado y, por lo tanto, se asume que es caché y especialmente eficiente en la paginación. Si el sistema asigna y libera páginas con frecuencia, la parte correspondiente del encabezado estará activa y no es probable que se elimine del caché de la CPU o se pague. Sin embargo, si el sistema se vuelve estático con respecto a las asignaciones de páginas, esas páginas pueden eliminarse de la memoria caché de la CPU o incluso paginarse.

Con las consideraciones anteriores en su diseño, se supone que nuestro asignador de páginas es muy eficiente. Sin embargo, algunos casos de uso podrían conducir a la fragmentación. Puede ser una buena idea mantener las asignaciones más estáticas separadas de las más dinámicas. En un sistema de memoria virtual donde la paginación ocurre con regularidad, esto es menos preocupante ya que solo conduce a que algunas páginas no se utilicen y pueden terminar siendo paginadas (y nunca más paginadas).

El subasignador

El subasignador como se describe anteriormente es responsable de asignar y liberar memoria para un solo hilo o tarea. Un subasignador no está asociado directamente con ningún subproceso o tarea, pero nos aseguramos de que subprocesos separados en RDM usen su propio subasignador.

Hay tres tipos principales de asignaciones manejadas por el subasignador:

  1. Asignaciones inferiores a aproximadamente 2 K
  2. Asignaciones que puede gestionar el asignador principal
  3. Asignaciones que deben pasarse al sistema operativo

El enfoque principal de esta sección está en el primer caso anterior. Pero analicemos primero los otros dos casos brevemente. 

Asignaciones manejadas por el asignador maestro

Cada subasignador, cuando se crea una instancia, se asociará con un asignador maestro. Si una asignación es mayor de lo que el subasignador puede manejar por sí mismo, se puede pasar al asignador maestro. El asignador principal devolverá una cantidad de páginas de 4K que están alineadas con la página. Dado que estas asignaciones siempre están alineadas a una página, así es como el subasignador sabe que esta asignación fue manejada por el asignador maestro, y cuando esto se libera más tarde, se puede entregar directamente al asignador maestro.

Asignaciones pasadas al SO

Si una asignación es demasiado grande para el asignador principal (de forma predeterminada, alrededor de 650 K), el sistema operativo se encargará de la asignación. En este caso, se reserva un encabezado especial. Cuando esta asignación se libera más tarde, el encabezado especial le dice al subasignador que la entregue directamente al sistema operativo.

La parte principal del subasignador

Ahora estamos listos para entrar en los detalles del subasignador. Hay tres implementaciones principales además de lo que hemos mencionado antes. La implementación real que se utilizará se puede seleccionar en tiempo de compilación. Primero, discutiremos algunas características comunes a las tres implementaciones.

Como se mencionó anteriormente, el subasignador se crea una instancia de un asignador maestro. Obtendrá varias páginas del asignador maestro. Se solicita una página cuando se crea una instancia por primera vez. Se solicita una página adicional cada vez que recibe una solicitud de asignación que no puede caber en las páginas que ya tiene. Las páginas asignadas desde el asignador maestro nunca se devuelven al asignador maestro excepto cuando se destruye el asignador secundario.

La parte central del subasignador solo maneja tamaños particulares. Por lo general, hay dos tamaños para cada potencia de dos y el tamaño solicitado se redondeará al tamaño admitido más cercano. Exactamente qué tamaños son compatibles está determinado por el perfil utilizado. El perfil compilado de forma predeterminada está optimizado para el rendimiento de la caché, lo que significa que ninguna asignación cruzará más límites de 64 bytes de los necesarios.

Cada página administrada por la parte central del subasignador está reservada para un tamaño particular. Esto permite muy pocos gastos generales, ya que no se necesita un encabezado para cada asignación individual. Cuando se libera memoria, el encabezado de la página tiene toda la información necesaria para administrar la memoria de manera eficiente.

Asignación de tamaños fijos

Algunos de nuestros algoritmos realizan asignaciones pequeñas de tamaño fijo. Solíamos usar grupos de memoria, pero resultó que nuestro nuevo asignador es tan eficiente como los grupos de memoria que usamos antes. Al hacer también algo de código en línea usando macros, nuestro nuevo asignador de memoria supera la implementación anterior con el grupo de memoria. El uso del nuevo asignador de memoria también tiene la ventaja de que no es necesario asignar memoria para un propósito específico o cuánta memoria debe reservarse para ella.

Desventajas

Hay dos desventajas principales en este enfoque.

Primero, para las aplicaciones que asignan muchos fragmentos de memoria de un tamaño, libérelos y luego asigne muchos fragmentos de memoria de un tamaño diferente. Se supone que este podría ser el caso hasta cierto punto de RDM para ciertos casos de uso, pero se cree que no supera el beneficio de este enfoque en particular. El enfoque descrito permite algoritmos muy eficientes.

En segundo lugar, tener cada página solo maneja asignaciones de un tamaño particular significa que desperdiciaremos algo de memoria. A largo plazo, cuando solo se realizan asignaciones de diferentes tamaños en promedio, se desperdiciarán 2K por cada tamaño admitido. Para el perfil predeterminado, esto se acumula a 36K. Esto puede ser un problema para las aplicaciones que utilizan muy poca memoria, pero casi ningún problema para las aplicaciones que utilizan una cantidad relativamente grande de memoria.

Podríamos permitir diferentes tamaños en cada página para mitigar los problemas anteriores. Sin embargo, eso requeriría almacenar más información en el encabezado y posiblemente requeriría un encabezado para cada asignación. Esto también aumentaría la sobrecarga de espacio, y se cree que es muy difícil encontrar un algoritmo que sea tan eficiente como nuestro asignador actual, especialmente porque la utilización del espacio y el rendimiento son excelentes en comparación con el asignador anterior.

Los tres algoritmos

En las siguientes subsecciones se describirán tres algoritmos alternativos.

Subasignador que usa una lista y un mapa de bits

Se supone que este enfoque es el mejor enfoque con respecto al rendimiento de la caché. Veamos cómo funciona.

Se mantiene una lista para cada tamaño admitido de páginas en las que podríamos tener espacio libre. Decimos "podría" aquí, porque cuando asignamos memoria en una página, no verificamos si estamos usando el último espacio libre en esa página. En su lugar, eliminamos la página de la lista más tarde cuando encontramos que no podemos asignar desde esta página. Este enfoque es un poco más eficiente en comparación con hacer siempre esta verificación y eliminarla antes.

Cada página tiene un encabezado, que contiene un mapa de bits que nos dice qué parte de la página está libre con respecto al tamaño real que admite esta página. Tenemos un algoritmo general para buscar en este mapa de bits, pero también tenemos implementaciones específicas para plataformas que pueden aprovechar las optimizaciones de hardware.

Dado que este algoritmo no toca la memoria que se está liberando, se asume que esto debería ser más amigable para el rendimiento de la caché. Sin embargo, requiere código que utilice este algoritmo para no tocar la memoria cuando está a punto de liberarla para poder aprovecharla al máximo. Además, algunos perfiles iniciales de nuestro producto han mostrado un mejor rendimiento con el último algoritmo que se presenta a continuación.

También se supone que este algoritmo es bueno para la paginación, ya que a menudo asignamos desde páginas a las que, en general, se ha accedido recientemente.

Subasignador con lista de listas

Este algoritmo es similar al algoritmo anterior, excepto que usamos una lista en lugar de un mapa de bits dentro de la página. Usamos la ubicación de la memoria que se está liberando para mantener un puntero a la siguiente ubicación libre dentro de la página. Se supone que este algoritmo no es óptimo para el rendimiento de la memoria caché de la CPU, pero probablemente sea más rápido cuando no hay soporte de hardware para la búsqueda en el mapa de bits.

Se supone que este algoritmo es tan bueno para la paginación como el primer algoritmo.

Subasignador con una sola lista

Esto es similar al algoritmo anterior, excepto que, para cada tamaño admitido, tenemos una única lista que llega a todas las ubicaciones libres. Este algoritmo parece ser el más eficiente de acuerdo con algunos perfiles iniciales que hicimos de RDM. Es el algoritmo utilizado por defecto. Se supone que no es el mejor para el rendimiento de la caché de la CPU y es el peor para la paginación. Este algoritmo probablemente supera a los otros algoritmos debido a su simplicidad. Sin embargo, esto puede no ser universalmente cierto. Sospechamos que puede haber diferencias basadas en la arquitectura o la aplicación de la CPU. En los casos en los que se espera que la aplicación pagine mucho debido al uso excesivo de la memoria virtual, se espera que este algoritmo funcione peor.

Asignador de pila

RDM tiene dos tipos de asignadores de pila.

Uno de ellos está diseñado principalmente para utilizar la pila del sistema. Las asignaciones se realizan sin un identificador. Este asignador solo debe usarse para asignaciones de tamaño limitado y se debe dar un tamaño máximo en el código fuente. El enfoque exacto, incluido si estas asignaciones realmente usan o no la pila del sistema, depende de la plataforma.

El otro asignador de pila es una implementación que usa el subasignador en su implementación. Este asignador de pila usa un identificador similar al subasignador. La principal ventaja de este tipo de asignador de pila sobre el subasignador es que evita administrar asignaciones más pequeñas, y se puede liberar una parte de la memoria liberando algo más abajo en la pila.