Solaris: Slab allocator

La gestión de memoria que hace el Kernel de un sistema operativo no se diferencia mucho de la que se debería hacer con cualquier otro software, excepto en una cosa, es difícil realizar una predicción sobre las necesidades de memoria que van a tener los distintos procesos que se estén ejecutando en el sistema, para ellos el Kernel debe estar continuamente reservando pedazos de memoria para la gestión del sistema, dicha memoria se empleará para mantener las distintas estructuras de datos necesarias, por ejemplo, cuando se crea un nuevo proceso, el Kernel debe reservar un espacio de memoria para almacenar una estructura de datos de tipo proc_t, o cuando se crea un fichero, se debe reservar memoria para almacenar la información del fichero en una estructura de tipo inode_t. De la misma forma, cuando un proceso muere, la información que mantiene el Kernel sobre dicho proceso ya no es necesaria por lo que puede ser eliminada de memoria, liberado el espacio que ocupa.

Que el Kernel trabaje con este tipo de información presente dos inconvenientes considerables:

  • La cantidad de información que se crea y se destruye es bastante elevada y cada vez será mayor en tanto en cuanto los procesadores se hagan más rápidos y se gestione más cantidad de memoria, lo que permitirá que una mayor cantidad de procesos podrán ejecutarse en el sistema, asignandoles cada vez más cantidad de recursos.
  • La cantidad de memoria necesaria para almacenar mucha de la información con la que trabaja el Kernel es mucho menor que el tamaño de una página física, por lo tanto el utilizar unidades de un tamaño fijo como son las página, supone un aumento de la fragmentación de la memoria.

Para resolver estos y otros problemas en la versión de Solaris 2.4 se implementó un nuevo método para la asignación del memoria conocido como “slab allocator” (asignación de losa). Este asignador de memoria trabaja con los siguientes elementos:

  • Objetos, de esta forma se designa a una unidad de memoria asignada a un elemento, su tamaño es variable dependiendo del tipo dato.
  • Slab, consiste en una o más páginas de memoria, las cuales están divididas en huecos del mismo tamaño y que se utilizan para almacenar un tipo de objeto, disponen de un contador que informa sobre la cantidad de objetos que han sido asignados.
  • Cache, consiste en uno o varios slabs.
  • Magazines, son arrays de punteros a objetos.

Cachear objetos

Entre las operaciones más realizadas por el Kernel están la asignación de memoria para un objeto nuevo que se ha solicitado y la posterior liberación de dicha memoria. El cacheado de los objetos es un técnica que permite ahorrar tiempo intentando no ejecutar los pasos de construcción y destrucción de un objeto, para ello se basa en la reutilización de los objetos, no en su creación y destrucción.

Cuando se realizar una petición para crear un objeto, este dispone normalmente de un método constructor que se encarga de reservar memoria, inicializar variables, etc. Una vez el objeto ha terminado su función, debería ser destruido, para entre otras cosas liberar la memoria que está ocupando, en vez de esto, el Kernel no lo elimina sino que lo marca con el estado de libre, de esta forma si se vuelve a solicitar la creación de un objeto del mismo tipo, el sistema ya no tiene que ejecutar el paso de su construcción porque el objeto ya existe. Este método se basa en disponer de una serie de caches, en las cuales se almacenan los objetos para poder ser reutilizados.

Es importante entender que en el sistema habrá tantos tipos de cache, como tipos de objetos maneje el sistema. El uso de un sistema de cache para los objetos con los que trabaja el Kernel aumenta considerablemente el rendimiento, evitando los 2 pasos más costosos, la creación del objeto y su destrucción.

Cuando el sistema necesite memoria, el asignador puede llamar a los destructores de todos los objetos que están marcados como libre y de esta forma liberar la memoria que ocupan.

Slabs

Un slab está formado por una o varias páginas continuas de memoria virtual, divididas en espacios de igual tamaño, utilizados para almacenar objetos, el slab dispone de un contador que indica la cantidad de objetos asignados al slab. Es por tanto la unidad mínima con la que trabaja el Asignador.

Cuando el contador de un slab está a 0, dicho slabs puede ser destruido para liberar la memoria que tiene asignada.

El uso de slabs reduce la fragmentación de la memoria, ya que aunque los objetos son menores que el tamaño de la página, al utilizar varias páginas para almacenar objetos del mismo tamaño y que la unidad de memoria para el Asignador sea el slabs y no el objeto, permite que el sistema pueda almacenar muchos objetos de pequeño tamaño en una o varias páginas de memoria.

La definición de la estructura kmem_slab la puedes encontrar en el portal de OpenSolaris

    214 typedef struct kmem_slab {
    215 	struct kmem_cache	*slab_cache;	/* controlling cache */
    216 	void			*slab_base;	/* base of allocated memory */
    217 	avl_node_t		slab_link;	/* slab linkage */
    218 	struct kmem_bufctl	*slab_head;	/* first free buffer */
    219 	long			slab_refcnt;	/* outstanding allocations */
    220 	long			slab_chunks;	/* chunks (bufs) in this slab */
    221 	uint32_t		slab_stuck_offset; /* unmoved buffer offset */
    222 	uint16_t		slab_later_count; /* cf KMEM_CBRC_LATER */
    223 	uint16_t		slab_flags;	/* bits to mark the slab */
    224 } kmem_slab_t;

El slab es controlado por la estructura de datos kmem_slab, la cual contiene un puntero a la cache a la que pertenece el slab, la dirección base del slab, un puntero al siguiente slab en la lista freelist de la cache, un puntero al slab previo en la lista freelist de la cache, un puntero al primer buffer libre del slab, el contador de objetos en el slab y el número de objetos que tiene este slab.

buffer buffer buffer no usado Slab información

Un slab formado por varias páginas está divido en tres tipos de información, al final del slab se almacena la estructura de datos kmem_slab que contiene la información necesaria para trabajar con el slab, el resto del espacio se divide entre el tamaño del objeto para el que se ha creado el slab y el espacio restante es espacio no utilizado. Como curiosidad decir que el slab solo almacena información sobre la lista de buffers libres y no de los ocupados, esto es porque el objeto ocupado tiene una dirección de memoria que obligatoriamente debe coincidir con alguno de los buffer del slab, cuando un objeto es liberado se realiza una petición a la cache, esta localiza el slab al que pertenece mediante la dirección del objeto, añade al buffer al que pertenezca el objeto a la lista de buffers libres y decrementa el contador de objetos del slab.

Cache

La cache consiste en un pool de un tipo de objeto en concreto, es decir, se pueden crear tantas caches como tipos de objetos utilice el sistema. Todas las caches dispones de dos interfaces, un interfaz de frontend que es utilizado para asignar/liberar objetos y un interfaz de backend que se utiliza para reclamar o liberar slabs.

Cuando todos los slabs de una cache están llenos, se realiza una petición mediante el interfaz de bakend para que se asigne otro slab, una vez se ha asignado, se inicializan todos los objetos del slabs y se marcan como libres para que la siguiente petición a la cache pueda asignar un objeto. Cuando el sistema dispone de poca memoria, se avisa a las caches para que liberen toda la memoria que les sea posible, para ello, comprueban en la lista de slabs libres todos aquellos que no tienen ocupado ninguno de sus espacios y llaman a los destructores de los objetos del slabs, en ese momento se libera la memoria ocupada por todo un slab.

Magazines

El método de cacheado de objetos presenta una serie de ventajas que permiten aumentar el rendimiento del sistema, en tanto en cuanto ya no se pierde tiempo en la creación y destrucción de objetos, los cuales en caso de que sean muy utilizados, supondría un consumo en ciclos de CPU.

Frente a las ventajas existe un inconveniente, es que si el método de cachear objetos funcionase tal como se ha descrito, no solo no serviría para aumentar el rendimiento, sino todo lo contrario en sistemas que utilizasen varios procesadores, ya que se daría el caso de que varios procesadores luchasen por obtener un objeto de la cache, provocando un bloqueo de la misma y dejando a los procesadores en un estado de espera. Para evitar que los procesadores tengan que luchar por un objeto de algunas de las caches, cada uno de los procesadores tendrán asignadas sus propias caches, evitando de esta forma los bloqueos.

Se ha implementado un sistema de tres capas:

  • Capa de CPU.
  • Capa de depósito.
  • Capa de SLAB

Las dos primeras capas organizan los objetos en arrays de un número N de objetos, dichos arrays se conocen como Magazine y son secillamente, arrays de punteros a objetos. La capa de CPU asigna una serie de Magazines a cada una de las CPUs del sistema, dichos Magazines garantizan que una CPU puede realizar al menos N operaciones de asignación o liberación de un objeto.

El número de objetos por magazine varía dinámicamente dependiendo de la cantidad de peticiones que se realizan a la capa de depósito

NOTA – El uso del termino Magazine se debe al uso que se realiza en Inglés de esta palábra para referirse a los cargadores de las armas automáticas, por lo que debemos entenderla como un cargador, donde las objetos se corresponderían con las balas.

Cuando una CPU necesita un objeto lo solicita a la cache que tiene asignada, esta cache dispone de dos magazines, llamados “magazine cargado” y “magazine previamente cargado”, el objeto solicitado es extraido del “magazine cargado”. Los magazines funcionan como una pila de objetos, manteniendo información sobre el tipo de objeto y el número de objetos disponibles en el magazine. Si la CPU solicita un objeto al magazine y éste se encuentra vacio, pero se puede utilizar un objeto del “magazine previamente cargado“ entonces se realiza un intercambio entre estos 2 magazines. Si ninguno de los magazines se pueden utilizar para satisfacer la necesidad de un objeto por parte de la CPU, en este caso el “magazine cargado” es pasado al “previamente cargado” y se solicita un magazine a la capa inferior, la capa de depósito.

Pero los magazines de la CPU no solo se sustituyen cuando están vacios sino tambien cuando se llenan, ya que en caso de que la CPU desee liberar un objeto, este debe volver al magazine, al igual que ocurre con la operación de retirada de un objeto, si se intenta devolver un objeto y el magazine “cargado” está lleno y se puede utilizar el magazine “previamente cargado”, se realiza un intercambio entre ambos, para que se puede dejar el objeto. En caso de que no se pueda utilizar ninguno de los magazines, se debe solicitar a la capa de depósito un nuevo magazine que esté vacio.

La capa de depósito dispone de dos listas, las cuales contienen los magazines, llenos y vacios.

Parámetros del Kernel

De todos los parámetros del Kernel disponible, existen 3 que son interesante que conozcamos si vamos a modificar el comportamiento del Kernel a la hora de trabajar con los objetos de los distintos magazines.

kmem_reap_interval Intervalo de ejecución del thread, su valor por defecto es 15*hz (unos 15segundos)
kmem_depot_contention El número máximo de fallos sobre la capa DEPOT, contados desde la última vez que se ejecutó el thread. Si se supera el valor por defecto 3, se incrementa el tamaño del magazine.
kmem_reapahead La función schedpaging() del Pageout utiliza este parámetro para que en caso de que la memoria libre sea menor que la suma(lotsfree + needfree + kmem_reapahead) llama a la función kmem_reap() que se encargará de liberar toda la memoria que pueda de los distintos slabs disponibles.

Con mdb podemos echar un vistazo a los valores de estos 3 parámetros:

root@host # mdb -k
Loading modules: [ unix genunix specfs dtrace ufs sd mpt px ldc ip hook neti sctp arp usba fcp fctl emlxs nca lofs zfs
random nfs sppp crypto ptm md cpc fcip logindmux ipc ]
> kmem_reap_interval/D
kmem_reap_interval:
kmem_reap_interval:             0
>
> kmem_depot_contention/D
kmem_depot_contention:
kmem_depot_contention:          3
>
> kmem_reapahead/D
kmem_reapahead:
kmem_reapahead: 0
>

Con el comando ::kmastat de mdb, podemos ver el uso que está haciendo el sistema de los distintos magazines que se han creado.

root@host # mdb -k
Loading modules: [ unix genunix specfs dtrace ufs sd mpt px ldc ip hook neti sctp arp usba fcp fctl emlxs nca lofs zfs
random nfs sppp crypto ptm md cpc fcip logindmux ipc ]
> ::kmastat
cache                        buf    buf    buf    memory     alloc alloc
name                        size in use  total    in use   succeed  fail
------------------------- ------ ------ ------ --------- --------- -----
kmem_magazine_1               16   3703  26416    425984    117757     0
kmem_magazine_3               32  11865  36068   1163264    187112     0
kmem_magazine_7               64  14718  52070   3358720    246824     0
kmem_magazine_15             128  17824  38997   5070848    298984     0
kmem_magazine_31             256   2484  10695   2826240     57060     0
kmem_magazine_47             384   2120   2373    925696     18681     0
kmem_magazine_63             512      0    330    180224      3168     0
kmem_magazine_95             768    544   1370   1122304      4421     0
kmem_magazine_143           1152  17513  17521  20504576     74371     0
kmem_slab_cache               56 141733 170230   9617408    194782     0
kmem_bufctl_cache             24 368335 399681   9658368    438525     0
kmem_bufctl_audit_cache      128      0      0         0         0     0
kmem_va_8192                8192 158463 186656 1529085952    258293     0
kmem_va_16384              16384   2159   2512  41156608      7103     0
kmem_va_24576              24576    968    980  25690112      1180     0
kmem_va_32768              32768   2139   2144  70254592      3540     0
kmem_va_40960              40960     65     72   3145728        72     0
kmem_va_49152              49152      0      0         0         0     0
kmem_va_57344              57344     66     68   4456448        66     0
kmem_va_65536              65536      0      0         0         0     0
kmem_alloc_8                   8 127593 132210   1064960 192956965     0
kmem_alloc_16                 16  44304  48768    786432 154080669     0
kmem_alloc_24                 24  59889  71868   1736704  47239399     0
kmem_alloc_32                 32  24623  66294   2138112 126889256     0
kmem_alloc_40                 40  18312  40194   1622016  54706405     0
kmem_alloc_48                 48  57996  96330   4669440  38173148     0
kmem_alloc_56                 56  51772  74240   4194304  85700241     0
kmem_alloc_64                 64  33247 145161   9363456 678235324     0
kmem_alloc_80                 80 135877 225836  18317312 111788983     0
kmem_alloc_96                 96  95371 157836  15392768  46351102     0
kmem_alloc_112               112  51425  73800   8396800  13371716     0
kmem_alloc_128               128  81531 118881  15458304  27763230     0
>> More [, , q, n, c, a] ?

De la salida anterior, una de las columnas importantes es alloc fail, esta columna debería estar en 0, ya que en caso contrario tendríamos un problema de memoria disponible, el sistema estaría intentando reserver memoria, la cual no está disponible y por lo tanto se produciría un problema en la gestión de los objetos de una magazine