Sobre los HEAP en Windows

Ver el tema anterior Ver el tema siguiente Ir abajo

Sobre los HEAP en Windows

Mensaje  r32 el Sáb Oct 15, 2011 7:54 pm

* Referencias:

+ http://msdn.microsoft.com/en-us/library/aa366711%28v=vs.85%29.aspx

+ http://msdn.microsoft.com/en-us/library/aa366750%28v=vs.85%29.aspx

+ http://en.wikipedia.org/wiki/Dynamic_memory_allocation

Introduccion al heap de Windows:


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.

Fuente: 48bits
avatar
r32
Admin
Admin

Mensajes : 81
Puntos : 1696
Fecha de inscripción : 21/02/2011

https://www.elhacker.net/

Volver arriba Ir abajo

Ver el tema anterior Ver el tema siguiente Volver arriba

- Temas similares

 
Permisos de este foro:
No puedes responder a temas en este foro.