Una implementación de malloc

En este trabajo se propone una implementación guiada de las rutinas malloc(), free() y realloc() a partir de un heap generado con el equivalente de sbrk(2).

La implementación se realizará en cuatro fases:

1. Documentación por escrito de las estructuras de datos.
2. Descripción e implementación de un heap checker conforme a ese diseño.
3. Implementación de malloc(), realloc() y free() sin fusión de bloques (coalescing).
4. Implementación de fusión de bloques.

donde los tres primeros apartados son obligatorios, y el cuarto opcional.

Observaciones adicionales:

• la guía principal para la implementación es el capítulo §9.9 de [BRY15].

• los puntos 1 y 2 (heap checker y diseño) deben realizarse antes de comenzar la implementación, y así debe quedar reflejado en el repositorio de la entrega.¹

Índice

• Especificaciones
  • Requisitos
  • Esqueleto de código
  • Funciones a implementar
• Implementación
  • Fase 1: Diseño
  • Fase 2: Heap checker
  • Fase 3: Implementación básica
  • Fase 4: Fusión de bloques
• Observación final

Especificaciones

El código en C debe compilar sin warnings con las opciones -std=gnu99 -Wall -O2, y cumplir con los requisitos que se listan a continuación.

Requisitos

• la implementación debe funcionar en x86 de 64 bits; por tanto, tanto punteros como el campo tamaño serán de 8 bytes.

• la implementación debe devolver punteros alineados a 16 bytes, como hace glibc en Linux.

• las variables globales (que deberán ser marcadas como static) no debe superar los 256 bytes en conjunto.

• por supuesto, no se puede invocar a ninguna función de manejo de memoria en Linux, incluyendo mmap(2) y sbrk(2); en su lugar, debe usarse mem_sbrk() (descrita en la siguiente sección)

Esqueleto de código

En todos los repositorios hay ahora una nueva rama tp2 con el esqueleto para realizar el trabajo en el directorio malloc. Las instrucciones para la descarga y la entrega son las mismas que en labs anteriores. Solamente se modificarán los archivos README.md y mm.c.

Sobre el resto del esqueleto:

• el archivo mm.h contiene los prototipos de las funciones a implementar, descritas en la siguiente sección;

• el archivo memlib.h contiene el prototipo de la función mem_sbrk(), con la que se debe manejar el crecimiento del heap²;

• de ser necesario, se pueden usar otras funciones de memlib.h, en particular mem_heap_lo(), mem_heap_hi() y mem_heapsize().

Funciones a implementar

• mm_init(): antes de llamarse a malloc, free o realloc por primera vez, el programa de pruebas llama a esta función para permitir realizar inicializaciones por una vez (por ejemplo, reservar el heap inicial). La función debe devolver 0 en caso de error, 1 en caso contrario.

• mm_malloc(), mm_free(), mm_realloc(): funciones cuya semántica sea igual a las funciones equivalentes de la biblioteca estándar. Se puede asumir que los punteros pasados a mm_free() y mm_realloc() fueron anteriormente obtenidos con mm_malloc() o mm_realloc().

Implementación

Se describen a continuación las fases en que se debe estructurar la implementación el trabajo, y los requisitos particulares de cada una.

Fase 1: Diseño

Se debe documentar, en el archivo README.md del repositorio, el diseño elegido para la implementación. Se recomienda elegir uno de los dos diseños propuestos en la bibliografía:

• listas implícitas (implicit free lists, §9.9.6)
• listas explícitas (explicit free lists, §9.9.13)

El diseño debe incluir, al menos:

• la estructura de cada bloque, incluyendo diferenciación (si las hubiere) entre bloques reservados y bloques libres

• justificación del tamaño mínimo que puede tener un bloque

• los marcadores de comienzo y final de heap, incluyendo consideraciones sobre el manejo de alineamiento en la primera llamada a mem_sbrk(). (Si se va a implementar coalescing, se recomienda incluir bloques de prólogo y epílogo, tal y como se describe en §9.9.12.)

Eso a cuanto la estructuración de los datos. Se debe incluir, además, una descripción (en pseudo-código es suficiente) de las primitivas necesarias para el manejo de estos datos. En particular:

• primitivas para conocer el tamaño de un bloque, y su estado
• primitivas para encontrar los bloques siguiente y anterior
• en caso de usar listas explícitas, el código para navegar la lista de bloques libres

NOTA: En la parte 3, se recomienda implementar estas primitivas como funciones static, y no como macros.

Fase 2: Heap checker

Un heap checker, o detector de consistencia, es una función que recorre el heap verificando que su estado sea consistente con el diseño (esto es, que no haya incongruencias entre ambos).

En esta sección se pide:

1. enumerar (en el archivo README.md) la lista de inconsistencias que podrían detectarse (o, expresado en inverso, invariantes que se deben cumplir). Ejemplos:

   • invariante: el tamaño de bloque y estado en header y footer debe ser el mismo.

   • inconsistencia: encontrar un bloque en la lista de bloques libres que no esté libre

   • o, más ejemplos en forma de pregunta: ¿están todos los bloques reservados alineados a 16 bytes?

2. describir brevemente (en el mismo archivo README.md) cómo detectar cada caso

3. implementar una función mm_checkheap(int line), a la que se pueda invocar con mm_checkheap(__LINE__) de manera que pueda imprimir cualquier error detectado, junto con la línea desde donde se la invocó. (En caso de estar todo bien, no debería imprimirse nada.)

Fase 3: Implementación básica

Se deben implementar las funciones especificadas, sin necesidad de realizar fusión de bloques desde free. (Se recomienda, aunque no es obligatorio, intentar implementar al menos fusión de heaps, esto es, cuando mm_malloc() llama a mem_sbrk() para obtener más memoria, ya que la memoria obtenida es siempre contigua.)

En el esqueleto se incluye un programa de pruebas, mdriver, que se puede usar para verificar el comportamiento de la implementación con los dos archivos de trazas proporcionados: short1-bal.rep y short2-bal.rep. (No es necesario detenerse en el formato de estos archivos, pues ya los carga el programa mdriver.)

Nota sobre los algoritmos de emplazamiento: es suficiente con implementar first-fit, pero la implementación de algoritmos adicionales que se encuentren en la bibliografía contribuye a la nota. (Se pide mencionar en el archivo README.md cuáles se implementaron.)

Fase 4: Fusión de bloques

Tal y como se explica en §9.9.10, para evitar la fragmentación externa free() debería comprobar si los bloques adyacentes al bloque liberado también están libres, y en ese caso combinarlos en uno de mayor tamaño.

Para la implementación se recomienda el uso de boundary tags tal y como se explica en §9.9.11.

Observación final

La bibliografía incluye, en la sección §9.9.12, una implementación básica con listas implícitas, para tamano de palabra de 32 bits.

De querer hacer uso de ella, la recomendación es que este uso sea durante las partes 1 y 2, en las que una lectura atenta de código existente puede ayudar a entender cómo se transforma un heap en bloques.

No se recomienda hacer uso del código del libro para las partes 3 y 4, pues habría que tener extraordinario cuidado para ajustar el tamaño de palabra de 32 a 64 bits. (Tema aparte es el uso de macros vs. funciones estáticas, y en general la legibilidad del código.)