En Windows vista el tipo de heap que las aplicaciones usan por defecto es el llamado low-fragmentation heap. Esta situacion es diferente a la que nos podemos encontrar en otras versiones de Windows. Pero, ¿Que es esto del low-fragmentation heap?¿Que beneficios aporta?

En este post voy a intentar despejar estas incognitas al mismo tiempo que doy una vision global de como funciona el Heap de Windows.

En Windows el heap tiene dos niveles bien diferenciados. El primero de ellos se llama el back end Allocator, mientras que el segundo nivel se denomina front end Allocator.

El back end Allocator proporciona una implementacion sencilla y flexible. Estableciendo un paralelismo con el campo de la algoritmica podriamos decir que el back end allocator es una especie de «Uninformed allocator» en el sentido de que no trata de dar ventaja a unas situaciones respecto a otras.

El back end allocator organiza la memoria que gestiona en diferentes segmentos que reserva a traves de las funciones del sistema operativo destinadas al tratamiento de la memoria virtual (vg. ZwAllocateVirtualMemory). Estos segmentos contienen las diferentes reservas de memoria que los usuarios requieren. El heap tiene una granularidad (normalmente de ocho bytes, lo que quiere decir que toda reserva de memoria en el heap sera necsariamente de tamaño multiplo de ocho) que asegura el alineamiento y simplifica la gestion. Para cada bloque existe una cabecera con diversa informacion. La cabecera indica el tamaño del bloque y el tamaño del bloque anterior. De esta forma los bloques contiguos estan enlazados entre si. La cabecera tambien indica si un bloque de memoria esta en uso o libre. Con esta informacion el back end allocator es capaz de unir los bloques libres contiguos para formar bloques mas grandes y para de esta forma combatir la fragmentacion. El back end allocator gestiona otras dos estructuras de importancia. Un array de listas doblemente enlazadas que agrupan bloques libres de igual tamaño y un bitmap que indica si para una entrada del array anterior la lista doblemente enlazada contiene o no bloques disponibles. Con estas dos estructuras el back end allocator es capaz de mantener el heap sin una fragmentacion excesiva, puesto que es capaz de elegir el mejor bloque de los libres disponibles para satisfacer la demanda de un usuario. Hay peticiones de memoria que por ser demasiado grandes no son gestionadas por este sistema de listas. En estos casos la peticion de memoria se satisface directamente a traves de las funciones de gestion de memoria virtual del sistema operativo.

Ademas de los aspectos basicos sobre la algoritmia del back end allocator que he descrito antes, este allocator permite diferentes modos de funcionamiento dependiendo de los flags usados en la creacion del heap y en el momento de una reserva concreta por parte del usuario. Por ejemplo, el heap puede ser inicializado con sincronia interna o sin sincronia en caso de que el usuario gestione la sincronia por su cuenta. El heap tambien puede crecer segun sus necesidades o tener un tamaño fijo. Puede tener activadas diferentes opciones de depuracion. O puede tener asignada una direccion fija asignada por el usuario. Este ultimo caso de uso muy poco comun pero muy util para mapear heaps sobre ficheros mapeados en memoria, pudiendo compartir el heap entre varios procesos. Esta es la tecnica usada por muchos componentes de Windows para el paso de mensajes de gran tamaño. El ejemplo mas clasico es la comunicacion que se establece entre el CSRSS y los procesos del subsistema. Otras de las funcionalidades no demasiado conocidas que proporciona algunas implementaciones del heap de windows es la posibilidad de encriptar las cabeceras de los heaps mediante un XOR con un numero aleatorio obtenido en el momento de creacion del propio heap.

El front end Allocator es una capa por encima del back end allocator que pretende proporcionar algoritmos que se adapten a las necesidades especificas de diferentes aplicaciones. Windows proporciona dos front end allocators diferentes. El primero de ellos se denomina Look Aside List allocator y el segundo se denominar Low Fragmentation allocator. Tambien se puede dedicir no usar ninguno de los dos Frond End Allocators disponibles. La mayor parte de las versiones de Windows usan el Look Aside List Allocator como Front end allocator por defecto, pero Windows vista usa el Low Fragmentation heap como Front end Allocator, y parece que las sucesivas versiones de sistemas operativos NT seguiran esta misma linea.

De los dos front end allocators disponibles, el Look Aside list allocator es el mas sencillo. El Look Aside list allocator cuenta con un array de listas enlazadas que son thread-safe. Estas listas se basan en una estructura de datos de caracter general conocida como «sequenced singly linked list». Cuando un usuario lleva a cabo la peticion de un nuevo bloque, el look aside list allocator trata de satisfacer la peticion usando estas listas. Si la peticion no se puede satisfacer entonces se intenta satisfar a traves del back end allocator. Cuando el usuario libera un bloque de memoria, el look aside list allocator guarda el bloque para poder atender posteriormente nuevas peticiones. Si el front end allocator no puede gestionar el bloque en sus listas, entonces pide al back end allocator su liberacion. Este allocator proporciona algunas ventajas respecto al uso del back end allocator, pero tambien plantea algunos problemas. La principal de las ventajas es que para satisfacer una peticion de reserva a traves del Look Aside List allocator no es necesario bloquear el heap, puesto que las listas que usa son seguras. Esto nos proporciona un mayor rendimiento en entornos multithread, puesto que el back end allocator serializaria las peticiones de los usuarios. La principal desventaja es que los bloques gestionados por el look aside list allocator no son liberados y permanencen en uso desde el punto de vista del back end allocator. En esta situacion los bloques libres contiguos no pueden ser unidos. Por tanto, el look aside list allocator proporciona un rendimiento mayor pero tambien provoca una mayor fragmentacion del heap.

El low fragmentation heap allocator pone sobre el tapete un algoritmo relativamente complejo que pretende aunar las ventajas tanto del Look Aside List allocator como del algoritmo expuesto por el back end allocator. Una de las primeras cosas que diferencia este allocator es la granularidad variable. Si en el back end allocator ( y por ende en el Look Aside allcoator) la granularidad del heap es normalmente de ocho bytes, y es asi independientemente de los tamaños de las reservas de los usuarios, el low fragmentation allocator tiene una granularidad variable, que aumenta gradualmente al aumentar los tamaños de las peticiones. Esto le permite gestionar mejor los bloques de memoria, haciendo a veces pequeños gastos extra de memoria, pero evitando la fragmentacion y acelerando el proceso de reserva. Este allocator gestiona las reservas de memoria de diferentes tamaños de forma indpendiente. De esta forma solo tiene que sincronizar el acceso para alojos del mismo tamaño. Pero esto tambien le obliga a implementar objetos mas complejos para satisfacer las peticiones de un mismo tamaño. Si alguno de los que han comenzado a leer esto ha llegado hasta aqui y ademas ha programado drivers para versiones antiguas de Windows, seguramente recuerde las estructuras del kernel conocidas como zonas. Una zona es, simplificando mucho, un heap en el que las reservas son de un tamaño fijo establecido en el momento de creacion de la zona. Bien, basicamente el low fragmentation heap redondea el tamaño de la peticion de reserva conforme a la granularidad que le toca y seguidamente lleva a cabo la reserva en una zona. Al definir zonas de memoria especificas para los diferentes tamaños de reserva intenta minimizar la fragmentacion aunque aumenta la cantida de memoria que necesita para las esturcturas de control. La granularidad variable permite minimizar el numero de tamaños de reserva minimizando asi el numero de zonas que es necesario gestionar. El ultimo punto clave que diferencia el low fragmentation heap es la gestion de la sincronia. El Look Aside List allocator basa su sincronia en las listas enlazadas que hemos comentado, que son una estructura de datos de uso general. El back end allocator basa su sincronia en un objeto de sincronia estandar, una seccion critica. En cambio, el low fragmentation heap implementa internamente su propia sincronia , no apoyandose en objetos proporcionados por el sistema operativo o en estructuras de datos genericas. Uno de los objetivos de esta implementacion es el poder saber si el hilo que lleva a cabo la reserva esta viendose obligado a esperar por otro hilo que esta llevando a cabo otra rerseva del mismo tamaño. Cuando un hilo se ve obligado a esperar por primera vez, entonces el low fragmentation heap generara una zona auxiliar para uso exclusivo de este hilo, evitando que en el futuro se vuelva a tener que esperar. Al disponer de una granularidad variable las posibilidades de colision aumentan pero disminuyen la cantidad de estructuras que potencialmente se podrian llegar a duplicar.

Uniendo todos los aspectos expuestos sobre el low fragmentation allocator, podemos ver que pretende minimizar la perdida de rendimiento debido a la serializacion en entornos multithread, y lo hace detectando las situaciones de colision y solucionandolas mediante estructuras auxilieras. Al mismo tiempo intenta minimizar la fragmentacion mediante el uso de zonas.

El low fragmentation heap plantea cosas interesantes pero es dificil saber a priori cual es el front end allocator adecuado para una aplicacion dada. En la practica los desarrolladores deberan probar los diferentes allocators para sus aplicaciones con el fin de averiguar cual es el que le proporciona mejores resultados. Una de las ventajas que he visto empiricamente es que este allocator suele comportarse mejor con aplicaciones cuyo uso de memoria es bastante determinista. Cuano el uso de memoria es herratico, entonces no parece haber una diferencia apreciable entre ninguno de los dos front end heaps. El low fragmentation heap hace mas visibles los bugs, pero tambien mas dificiles de analizar debido a que su funcionamiento es menos determinista. Por otro lado actualmente no existen (o al menos yo no las conozco) pruebas de concepto que exploten overlows u otro tipo de erroresen low fragmentation heaps. Claro que esta situacion se me antoja efimera, puesto que no he visto mayor problema en hacerlo.

Y aqui pongo el punto y final a esta pequeña introduccion al heap de windows. He intentando centrarme ligeramente en el punto de vista del programador. Pero si hay interes en el futurto puedo explicar algunos aspectos con mayor detalle o desde otros puntos de vista.

Salu2!!