Windows XP Heap Manager

¿Qué es la administración de heap en Windows?

Es un subsistema usado por Windows para proveer la asignación de memoria dinámicamente. Esta se almacena en la parte superior de la memoria virtual provista por el kernel. Esta memoria puede ser manipulada por medio de las APIs VirtualAlloc() y VirtualFree(). Básicamente Heap Manager es responsable de proporcionar una capa de software de alto rendimiento para que el software pueda solicitar y liberar memoria utilizando malloc() y free(). RtlAllocateHeap() / RtlFreeHeap() y NtAllocateVirtualMemory() / NtFreeVirtualMemory() son las funciones que realmente forman la interface alrededor del Heap Manager.

Arquitectura del heap

Cada proceso comúnmente tiene múltiples heaps, y el programa puede crear nuevos heaps cuando sea requerido. Existe un heap por defecto del proceso, el cual es llamado como process heap, el puntero de este heap es almacenado en la estructura PEB (Process Environment Block). Todos los heaps de un proceso se almacenan en una lista enlazada en el PEB.

Administrador Front-End

El administrador Front-End se encarga del servicio de asignación y de las solicitudes de des-asignación de memoria.

Existen tres opciones para un administrador Front-End en Windows XP SP3:

  • Ninguno
  • LAL (Look-aside List)
  • LFH (Low-Fragmentation Heap)

El LAL front-end es el responsable de procesar las solicitudes de memoria inferiores a 1024 bytes. Utiliza una serie de estructuras de datos de listas únicas para realizar un seguimiento de varios trozos libres entre los tamaños 0 – 1024 bytes. El LFH front-end maneja solicitudes entre 0 – 16000 bytes, los tamaños mayores o iguales a 16000 son manejados por administrador Back-End.

Los administradores Front-End existen para optimizar el rendimiento del heap.

Administrador Back-End

El administrador Back-End se utiliza cuando el administrador Front-End no está presente, o no se puede realizar una solicitud. Esto puede ocurrir cuando el Front-End no tiene un trozo (chunk) apropiado para atender una solicitud específica, o si el sistema determina mediante heurística que las ventajas de rendimiento del Front-End pueden ser superadas. El administrador Back-End también es responsable de la asignación de grandes cantidades de memoria (> 1024 bytes cuando LAL está activado, > 16000 cuando LFH está activado).

Reservar y Comprometer (Commitment)

Windows distingue entre reservar memoria y comprometer memoria.

Lógicamente, un proceso primero reserva un rango de memoria, lo que hace que el kernel marque ese rango de direcciones de memoria virtual como no disponible. Reservar memoria no correlaciona nada con las direcciones virtuales, por lo que las escrituras, lecturas y ejecuciones de la memoria reservada seguirán causando una violación de acceso. El kernel tampoco intenta garantizar o preorganizar la memoria de respaldo para la memoria reservada. La reserva es esencialmente solo un mecanismo para proteger un rango de direcciones de la asignación desde el usuario.

Después de reservar una parte del espacio de direcciones, el proceso es libre de comprometer y des-comprometer la memoria dentro de él. La memoria comprometida es el acto de mapear y respaldar la memoria virtual. Los procesos pueden comprometer y des-comprometer libremente la memoria dentro de un trozo de memoria reservada sin tener que reservar la memoria (lo que se llama liberación de memoria).

Heap Base

Cada heap que es creado contiene una estructura de datos vital la cual es llamada heap base. El heap base contiene varios datos que son usados para administrar el seguimiento de los trozos libres u ocupados. El siguiente ejemplo muestra el contenido de la estructura _HEAP en un proceso creado bajo Windows XP SP3:

Para listar un sumario de los heaps existentes en el proceso, se debe usar el comando:

!heap -s
Administración de memoria

El Heap Manager organiza la memoria virtual usando heap segments y UCR segments para rastrear memoria des-cromprometida.

Heap Segments

El Back-End Heap Manager organiza su memoria por segmentos, donde cada segmento es un bloque contiguo de memoria virtual que es administrado por el sistema (Esta es una estructura de datos interna de Heap Manager y no está relacionada con la segmentación x86). Cuando es posible, el sistema utilizará la memoria comprometida para las solicitudes del servicio, pero si no hay suficiente memoria, el Heap Manager intentará reservar la memoria comprometida dentro de los segmentos existentes del heap para cumplir con la solicitud. Esto podría implicar la asignación de memoria al final del segmento o la asignación de memoria reservada al medio de los segmentos, estos agujeros se crearían al des-comprometer previamente la memoria.

De forma predeterminada, el sistema reserva un mínimo de 0x10000 bytes de memoria al crear un nuevo segmento de heap y compromete al menos 0x1000 bytes de memoria a la vez. El sistema crea nuevos segmentos de heap según sea necesario y los agrega a un array administrado en la base del heap. Cada vez que el heap crea un nuevo segmento, duplica su tamaño de reserva, haciendo que reserven secciones de memoria cada vez más grandes.

Segmento Base

Cada heap contiene un array de hasta 64 punteros a segmentos a +0x58 desde el heap base. Este array de 64 punteros de estructura _HEAP_SEGMENT contiene información sobre todos los segmentos asociados con un heap  dado. Cada segmento representa un bloque contiguo de memoria que es administrado por el sistema. Una estructura vacía se denota con NULL o 0x00000000 en el array. Para visualizar la estructura _HEAP_SEGMENT se debe usar el comando:

dt _HEAP_SEGMENT <dirección>
Como es posible observar, entre la información se incluye, información del heap asociada a este segmento, FirstEntry y LastValidEntry. Con esta información es posible recorrer el heap y obtener todos los metadatos para cada trozo (chunk) del heap.

Rastreo UCR

Cada heap tiene una porción de memoria reservada para rastrear rangos de memoria des-comprometidos. Estos son utilizados por los segmentos para rastrear todos los espacios en sus rangos de direcciones reservadas. Los segmentos rastrean esto con estructuras de datos pequeñas llamadas entradas UCR (rango des-comprometido, del inglés Un-committed Range). El heap mantiene una lista global de estructuras de entrada de UCR libres que pueden solicitar los segmentos de heap, crece dinámicamente para atender las necesidades. En el heap base, UnusedUnCommittedRanges es una lista enlazada de estructuras de UCR vacías que pueden ser utilizadas por los segmentos de heap. UCRSegments (heap base) es una lista enlazada de segmentos especiales UCR utilizados para contener las estructuras UCR. Cuando un segmento usa un UCR, lo elimina de la lista enlaza UnusedUnCommittedRanges del heap y lo coloca en una lista enlazada en la cabecera del segmento llamado UnCommittedRanges. Los segmentos especiales de UCR se asignan dinámicamente. El sistema comienza reservando 0x10000 bytes para cada segmento UCR y asigna 0x1000 bytes (una página) a la vez a medida que se necesitan entradas de seguimiento UCR adicionales. Si el segmento UCR está lleno y se utilizan los 0x10000 bytes, el administrador de heap creará otro segmento UCR y lo agregará a la lista UCRSegments.

Administrador Front-End
Look-Aside List (LAL)

La array de listas Look-Aside se puede encontrar típicamente en el propio trozo de heap en + 0x688 desde la base del heap, apuntado por FrontEndHeap. La estructura de datos LAL es un array de 128 entradas, cada una de tamaño 0x30 bytes. Cada entrada en el array contiene varias variables relacionadas con el rendimiento, que incluyen el tamaño actual, el tamaño máximo y, lo que es más importante, un puntero a la lista enlazada de trozos que corresponden al índice de segmento. Si no hay trozos libres para un segmento dado, el puntero es NULL. De forma similar, el final de la lista simplemente enlazada se denota mediante un puntero de enlace directo de NULL.

Si la solicitud de memoria de un usuario es menor que (1024-8) bytes, puede ser realizada por el front-end LAL. El siguiente diagrama muestra un front-end LAL que tiene una entrada para un tamaño de 1016. Este tamaño corresponde al número de segmento 127, que serviría una solicitud de usuario de un tamaño de 1008 bytes. El LAL no tiene trozos libres para el segmento de tamaño 544 (número de entrada 68). Se debe tener en cuenta que los segmentos para el tamaño 0 y el tamaño 1 no se utilizan porque cada fragmento requiere al menos 8 bytes para la cabecera del trozo.

Low Fragmentation Heap (LFH)

El LFH es un front-end de heap complicado que aborda la fragmentación del heap, así como el rendimiento simultáneo. Este código no está documentado, aunque tiene un rol más central en las versiones posteriores de Windows XP SP3. Incluso con el LFH activo, las solicitudes que involucran tamaños mayores a 16384 bytes deberían ir automáticamente al back-end del heap.

Administrador Back-End

El Back-end Heap Manager mantiene varias listas doblemente enlazadas para rastrear bloques libres en el heap. Estos residen en un array en la base del heap, comenzando en el desplazamiento + 0x178. Hay listas separadas para cada tamaño de bloque posible menores a 1024 bytes, lo que da un total de 128 listas libres (los bloques de heap se clasifican en múltiplos de 8.) Cada lista libre doblemente enlazada tiene un nodo central ubicado en el array en la base de el heap. Cada nodo principal contiene dos punteros: un enlace directo (FLink) y un enlace posterior (BLink).

FreeList[0] es especial, lo cual se discutirá en breve. FreeList[1] no se utiliza, y FreeList[2] hasta FreeList[127] se llaman listas libres dedicadas. Para estas listas dedicadas, todos los bloques libres en la lista son del mismo tamaño, lo que corresponde al índice de array * 8.

Sin embargo, todos los bloques superiores o iguales al tamaño 1024 se mantienen en una sola lista libre en FreeList[0]. (Este espacio está disponible para su uso porque no hay bloques libres de tamaño 0). Los bloques libres en esta lista se ordenan desde el bloque más pequeño hasta el bloque más grande. Entonces, FreeList[0].Flink apunta al bloque libre más pequeño (de tamaño >= 1024), y FreeList[0].Blink apunta al bloque libre más grande (de tamaño >= 1024).

Freelist Bitmap

Las listas libres también tienen un mapa de bits correspondiente, llamado FreeListsInUseBitmap, que se usa para escanear rápidamente a través del array FreeList. Cada bit en el mapa de bits corresponde a una lista libre, y el bit se establece si hay bloques libres en la lista correspondiente. El mapa de bits está ubicado en + 0x158 desde la base del almacenamiento dinámico y proporciona una ruta optimizada para que el sistema dé servicio a una solicitud de asignación entrante de las listas libres dedicadas. Hay 128 bits en el mapa de bits (4 DWORDS), que corresponden a las 128 listas libres que manejan asignaciones de tamaño <1016.

Para una solicitud de asignación dada para un tamaño <1016, primero se le da la oportunidad al servicio de atenderlo. Suponiendo que LAL o LFH no existe o no sirve la solicitud, el sistema mira directamente a la lista enlazada FreeList[n] para el tamaño dado. Se debe tener en cuenta que en este caso, el mapa de bits no es consultado. Si la entrada FreeList[n] correspondiente al tamaño solicitado por el usuario está vacía, entonces el sistema procede a usar el mapa de bits. A partir de este punto, busca en el mapa de bits un bit establecido, lo que hará que encuentre el siguiente bloque libre más grande en las listas libres. Si el sistema se queda sin mapa de bits, intenta extraer un bloque de FreeList[0].

Por ejemplo, si un usuario solicita 32 bytes del heap y no hay un trozo en LAL[5], y FreeList[5] está vacío, el mapa de bits se utiliza para localizar un trozo >40 bytes en las listas libres dedicadas (iniciando la búsqueda del mapa de bits en FreeList[6]).

Heap Cache

Como ya se ha comentado, todos los bloques libres con un tamaño superior o igual a 1024 se almacenan en FreeList[0]. Esta es una lista doblemente enlazada, clasificada por tamaño, desde la más pequeña hasta la más grande, sin mejoras adicionales para la velocidad. En consecuencia, si FreeList[0] crece para contener un gran número de bloques, el heap manager tendrá que recorrer múltiples nodos de lista cada vez que busque en la lista.

El heap cache es una mejora del rendimiento que intenta minimizar el costo de recorridos frecuentes de FreeList[0]. Lo hace creando un índice externo para los bloques en FreeList[0]. Es importante tener en cuenta que el Heap Manager en realidad no mueve ningún bloque libre al caché. Los bloques libres todavía se conservan en FreeList[0], pero el caché contiene varios punteros en los nodos dentro de FreeList[0], que se utilizan como atajos para acelerar el recorrido.

La memoria caché es un array simple de segmentos, donde cada segmento tiene un tamaño de intptr_t bytes y contiene un puntero NULL o un puntero a un bloque en FreeList[0]. De forma predeterminada, el array contiene 896 segmentos, lo que representa cada tamaño de bloque posible entre 1024 y 8192. Este es un tamaño configurable, al que nos referiremos aquí como el índice máximo de caché.

Cada segmento contiene un único puntero al primer bloque en FreeList[0] con el tamaño representado por ese segmento. Si no hay ninguna entrada en FreeList[0] con ese tamaño exacto, el segmento contiene NULL. El último segmento en la memoria caché de almacenamiento dinámico es único: en lugar de representar el tamaño específico 8192, representa todos los tamaños superiores o iguales al índice máximo de caché. Por lo tanto, apuntará al primer bloque en FreeList[0] que sea más grande que el tamaño máximo. (por ejemplo, >= 8192 bytes).

La mayoría de los segmentos están vacíos, por lo que hay un mapa de bits adicional que se utiliza para realizar búsquedas rápidas en el array. Este mapa de bits funciona igual que el mapa de bits utilizado para acelerar la lista libre.

Virtual Alloc List

Cada heap tiene un límite de asignación virtual VirtualMemoryThreshold. Por defecto, esto es 0xfe00, correspondiente a trozos de memoria de tamaño 508k o superior. Los bloques ocupados y virtualmente asignados se mantienen en una lista doblemente enlazada en la base del heap. Cuando los bloques vuelven al sistema, son liberados directamente al kernel por el back-end Heap Manager. (VirtualAllocdBlocks a + 0x50 y + 0x54).

Fuente
Compartir

Agregar un comentario

Pwned Chile