20/7/2013 18:25 Lucas Ontivero

Creando nuestro propio administrador de memoria en c#

Cuando comencé a programar en c# pensé que nunca más iba a volver a divertirme con algoritmos como los de administración de memoria, pero estaba equivocado! El hecho es que estoy trabajando en un proyecto ‘mascota’ en el que potencialmente cientos de sockets pueden estar enviando y recibiendo datos de manera asíncrona, potencialmente cientos o miles de veces por segundo. Posiblemente te preguntarás qué tiene que ver eso con la administración de la memoria, o más precisamente por qué necesitaría alguien administrar manualmente la memoria al viejo estilo (allocate/free) en un entorno administrado que cuenta con una maravilla como el Garbage Collector?

Por qué no dejarle esto al Garbage Collector?

Bien, la razón es que en este caso particular, el GC no puede hacerlo tan bien. Antes de poder avanzar en la explicación del por qué ‘este caso’ es especial, primero debo explicarles brevemente qué es lo que el GC hace cuando corre. Básicamente, en la siguiente imagen tenemos 15 bloques de memoria (por bloque entiéndase lo que vos quieras, bytes, words, o lo que sea) de los cuales 12 están asignados y 3 están disponibles, en un momento, el GC bloquea todos los threads de la aplicación e identifica aquellas porciones de memoria que han dejado de estar referenciadas y las libera (simplemente un tema administrativo), y así llegamos al paso 3. Ahora bien, se han liberado 4 bloques de memoria los que, sumados a los 3 restantes, nos da un total de 7 bloques libres, no obstante si la aplicación solicitara 4 bloques continuos (para alojar un array o una instancia de alguna clase) el sistema no sería capaz de asignarle nada ya que no dispone de 4 bloques continuos. En otras palabras, la memoria está disponible pero no te la puedo dar ;) A este problema se le llama fragmentación.

Garbage Collector y la fragmentación

Para resolver ese problema el GC ejecuta la compactación de la memoria como se puede ver en el paso 4, pero no solo eso, también actualizar las referencias de todos los objetos! Es decir, por ejemplo, en el paso 3 podemos ver que en la posición 4 (base 0) hay un bloque de memoria asignado, supongamos que está referenciado por una variable X, entonces mientras que antes de la compactación teníamos referencia(X) = 4, luego tenemos que referencia(X) = 2. Está de más decir que si el GC no actualizara las referencias luego de mover los bloques de memoria, las referencias apuntarían a cualquier parte dejándolo todo un desastre.

image

Entonces, ¿por qué administrar nosotros mismos?

Ahora si, por fin vamos a lo que veníamos: responder a la pregunta ¿por qué administrar manualmente la memoria en .NET en este caso? Para ello veamos el siguiente código:

image

Ese array buffer es una variable administrada, no obstante, el método BeginReceive invoca una función del sistema operativo indicándole la dirección de memoria del buffer para que cuando arriben datos a ese socket el sistema los almacene en esa dirección de memoria. Ahora imaginate que el GC decide liberar la memoria no usada y compactarla #@$%!…. El sistema operativo terminaría escribiendo en la dirección de memoria que se le indicó, la cual estaba referenciada por la variable buffer, pero esos bloques se pueden haber movido y la referencia haberse actualizado!!! Obviamente el SO no sabe nada de eso y terminaría escribiendo (y sobreescribiendo) en una dirección incorrecta.

El problema de los objetos ‘fijos’

Para que esto no suceda, antes de pasarle una dirección de memoria al sistema operativo (u a otro software que requiera una dirección de memoria para leer/escribir) necesitamos fijar esa referencia. Esto es, avisarle al GC que esos bloques no pueden ser movidos durante una compactación. Pero esto trae consecuencias, veamos la siguiente imagen:

image

Como vemos, los bloques 9 y 11 están fijos (no se mueven durante la compactación) por lo que si bien ahora tenemos nuevamente 7 bloques libres, no disponemos de más de 3 bloques continuos, es decir, si nos piden 4, 5, 6 o 7 bloques continuos no podemos dárselos. Esto es incluso más complejo de lo que muestro en el gráfico ya que cuando existen bloques fijos, la compactación se dificulta muchísimo porque ya no basta con simplemente mover los bloques de manera que ocupen direcciones contiguas sino que además hay que calcular cuales conjuntos de bloques (imaginemos un objeto que ocupe varios bloques) pueden ser movidos a donde. Complejo, no!?

Bueno, ahora imaginemos una situación con cientos o miles de bloques fijados, tendríamos un muy serio problema en las manos por la alta fragmentación que generaría. Es entonces cuando debemos pensar la conveniencia de administrar nosotros mismos la memoria, y no estoy hablando de manejar puntero en código no seguro; claro que no.

Cómo lo resolvemos

Una vez que reconocemos que tenemos este problema (la aplicación misma, el cliente, o el profiler, nos lo hacen saber) debemos implementar nuestro propio manejador. No voy a escribir demasiado sobre esto porque puede encontrarse en cualquier libro de sistemas operativos (yo lo aprendí en su momento del libro de SO de Andrew Tanenbaum, dicho sea de paso: un groso absoluto) pero si voy a comentar el algoritmo que he implementado.

La idea básica consiste en solicitar un bloque de memoria, el cual será administrado por nosotros. ¿Cómo se hace esto? Muy fácil, si necesito 1Mb de RAM para administrarla yo mismo, lo hago así:

image

Ahora bien, esta memoria no es distinta a ninguna otra, es decir, puede ser movida por el GC ya que nada se lo impide, o no? ummm… veamos… si y no. Tal como lo vemos podría parecer que sí, que puede ser relocalizada sin más, pero existen algunas maneras de impedirlo, la primera es no haciendo nada en lo absoluto, porque un array como ese (10MB) se considera un objeto grande por lo que se aloja en el LOH (Large Objects Heap) que no se compacta ya que es sumamente costoso. Otra alternativa es continuar haciendo nada y esperar, a medida que el tiempo pasa sin que se pierda la referencia el objeto memory el GC va compactando la memoria y los objetos más antiguos van decantando de a poco, así luego de algún tiempo, nuestro objeto memory se encontrará en la parte baja de heap y no volverá a moverse en las sucesivas compactaciones (o lo hará con muchísima menor frecuencia). Por último, podemos simplemente fijarla nosotros como sigue:

image 

Mi recomendación es no hacer nada en lo absoluto.

¿Solo sirve para arrays de bytes?

No, la idea sirve para todo tipo de objetos solo que puesto que los arrays (de bytes en especial) son uno de los casos más comunes, me he centrado más en ellos pero si por ejemplo, tengo objetos que representan coordenadas (x,y) que se pasan a otro sistema (digamos OpenGL) y por lo tanto van a ser fijados por las llamadas PInvoke, entonces los que nos conviene es crear un pool de instancias y reutilizarlas. El punto es que al reutilizarlas no las dejamos morir, de modo que como ya dije, van a ir decantando hacia la parte baja del heap en donde las relocalizaciones son mucho menos frecuentes y puesto que la segmentación es menor.

Volvamos a los arrays

Ya sea porque no dejamos morir la referencia (scope), porque el array es muy grande (y por lo tanto se aloja en el LOH), o porque la fijamos nosotros mismos mediante GCHandle.Alloc, el punto es que tenemos un array de bytes disponible para nosotros. Ahora bien, cuando necesitamos un buffer para nuestro socket almacene los datos que recibe nosotros podemos simplemente asignarle una porción (segment) de ese gran array. Por ejemplo, si quisiésemos asignarle el primer 1KB a partir de la posición 512, lo haríamos así (La línea realmente importante es la primera):

image

Ahora bien, eso fue fácil, el problema que tenemos ahora es cómo saber cuales segmentos están disponibles y cuales están siendo utilizados como buffers por algún socket. Eso es simplemente un problema de administración y para ello existen varios algoritmos.

Administrar la memoria

La administración de memoria consiste básicamente en llevar un registro de los espacios ocupados y libres, esa es toda la ciencia, no obstante es un tema complejo y existen muchos algoritmos (y sus variantes; algunos mejores para ciertos escenarios que otros) y probablemente el más utilizado sea el de tener una lista enlazada en la que se registran los bloques usados y libres mediante sus direcciones { Begin, End }. La ventaja aquí es que cuando necesitamos un bloque de N bytes solo tenemos que recorrer la lista de espacios libres chequeando si tenemos un segmento lo suficientemente grande para asignar (existen diferentes estrategias para esto). Lo malo es que cuando se libera memoria, la carga administrativa es mayor puesto que podemos tener un espacio de N bytes contiguos disponibles pero los tenemos registrados como 2 segmentos de N/2 bytes por lo que cuando nos piden N bytes, no encontraremos un segmento lo suficientemente grande aunque exista (fragmentación lógica). Entonces es necesario mergear los bloques libres adyacentes y eso consume procesador (tengamos en cuenta que la asignación/liberación de memoria ocurren con una frecuencia altísima).

Mapa de Bits (a lo bruto)

La primera implementación del BufferAllocator fue utilizando un mapa de bits, pero a lo bruto (en lugar de utilizar bits utilicé chars). Esto es, supongamos que la unidad mínima de memoria que vamos a asiganr es de 128 bytes, así que por cada 128 bytes utilizamos un char con un valor ‘-’ indicando que el bloque está asignado o con un valor ‘f’ indicando que el bloque está libre y puede ser asignado. La siguienet image es bastante clara:

image                        

Entonces si nos piden 200 bytes, lo primero que hacemos es calcular cuantos bloques de 128 bytes necesitamos, en este caso sería dos. Luego buscamos en un en el mapa ese espacio y si está disponible, luego de marcarlo como asignado, lo retonamos. En código sería más o menos así:

image

Si bien a este código le faltan todos los tipos de validaciones, como el qué hacer cuando blockOffset es –1 (no se encontró el patron, es decir, no tenemos un segmento libre lo suficientemente grande para asignar), es solo ilustrativo.  hay que decir que la liberación de la memoria es incluso más sencilla. Veamos:

image

Aunque funciana, no deja de ser una implementación de juguete. La siguiente ímplementación fue con listas enlazadas, simplemente copiada de Minix: https://github.com/minix3/minix/blob/3399c2c966a57b6e50225330417f7577fd5d04ba/sys/lib/libsa/alloc.c

Binary Buddy System

La implementación actual que utiliza mi proyecto es Binary Buddy allocator este sistema se basa dividir la memoria (en nuestro caso sería, nuestro array de bytes) en 2 porciones y luego dividir cada uno de los sub bloques en 2, y así suscesivamente. Para ello, recurrimos a un arbol binario en el caul el valor de cada nodo representa la cantidad de bloques de memoria disponibles en su hijo con mayor capacidad. La imagen de abajo muestra un arbol para administrar un máximo de ocho bloques de memoria.

image

La búsqueda de un bloque se realiza recorriendo el arbol ‘in-order’ hasta encontrar un nodo del tamaño adecuado, así por ejemplo, si nuestros bloques son de 128 bytes y necesitamos 200 bytes de espacio, sabemos que serán necesarios 2 bloques y entonces recorremos el arbol ‘in-order’ hasta que Math.Pow(2, nodo.value) == blockCount. Por último, debemos eliminar ese nodo y actualizar hacia arriba los padres. Entonces, luego de asignar los dos nodos de memoria, nuestro arbol quedaría así:

image 

Luego, si pedimos 3 o 4 bloques, tendríamos lo siguiente:

image

Lo que me gusta de este algoritmo es su elegancia y velocidad, aunque desperdicia memoria por la fragmentación interna que genera, pero bueno, a mi me gusta y es la implementación que pienso dejar, o al menos hasta que encuentre la necesidad de cambiarlo. El código de esto puede verse aquí:

https://github.com/lontivero/P2PNet/blob/master/P2PNet/BufferManager/BuddyBufferAllocator.cs

Conclusión

Si bien el Garbage Collector del framework .NET es algo maravilloso, existen muchas ocasiones en las que por tener segmentos de memoria ‘fijos’, este no puede hacer su trabajo tan bien como lo haría si esos segmentos no existieran y, es ahí cuando nosotros podemos tomar acciones para facilitar el manejo de la memoria. Básicamente, lo más sencillo es crear un pool de objetos sencibles a ser fijados para reutilizarlos.

Cuando se trata de buffers de bytes e tamaño fijo, el pool suele ser la solución más adecuada también. No obstante, cuando no conocemos los tamanos de los buffers que nos va a solicitar la aplicación, lo mejor es implementar un buffer allocator como los que mostré. Otra posible alternativa es tener distintos pools (o pooles?) con buffers de distintos tamaños, por ejemplo, un pool de buffers chicos, otro con buffers medianos y uno con buffers grandes, y entonces cuando nos piden un buffer de X bytes podemos tomar un buffer del pool adecuado y retornárselo a la aplicación

 

Archivado en: ,,,,,,
Comparte este post:

# Peer2.net

Saturday, August 17, 2013 5:08 AM by Lucas Ontivero

Peer2.net ( github.com/.../peer2net ) es una librería muy liviana y sencilla de