TP2: Manejo del heap

Índice

• Introducción
• Implementación
  • Parte 1: Administrador de bloques
  • Parte 2: Agregando más bloques
  • Parte 3: Mejorando la búsqueda de regiones libres
  • Parte 4: Agrandar/Achicar regiones
• Manejo de errores
• Esqueleto y compilación
• Bibliografía útil

Introducción

AVISO: antes de comenzar, verificar que se tiene instalado el software necesario.

REQUERIDO: para las entregas es condición necesaria que el check del formato de código esté en verde a la hora de realizar el PR (pull request). Para ello, se puede ejecutar make format localmente, comitear y subir esos cambios.

En este trabajo se desarrollará una librería de usuario que implementará las funciones malloc(3), calloc(3), realloc(3) y free(3). La librería se encargará de solicitar la memoria que requiera, y la administrará de forma transparente para el usuario. Además debería poder utilizarse de forma normal en cualquier programa de C.

Implementación

Llamaremos bloque a una sección contigua de memoria virtual que es administrada por la librería (puede haber más de un bloque). Asimismo, llamaremos región a aquella sección contigua de memoria virtual que es devuelta por la librería para el usuario; o bien que se encuentra disponible para ser fraccionada o devuelta. Entonces, la librería administrará bloques dividiéndolos en regiones.

Al final de este trabajo, la librería tendrá las siguientes funcionalidades:

• Las firmas de malloc(), calloc(), realloc y free() han de ser las mismas que las de la librería estándar de C.
• Se debe poder reutilizar la memoria liberada en tanto sea posible.
• Se debe poder escalar en la cantidad de memoria que se le pide al kernel.
• Se podrá compilar la librería para utilizar diferentes estrategias de búsqueda de espacio libre.
• La implementación debe estar protegida contra double free y invalid free.

Para simplificar, tendremos en cuenta las siguientes limitaciones y sugerencias:

• usar mmap(2) para la obtención de memoria, no brk(2) ni sbrk(2)
• definir un tamaño mínimo que siempre se va a devolver, incluso cuando el usuario pida menos memoria (máximo 256 bytes)

IMPORTANTE: registrar todas los respuestas a las preguntas y cualquier explicación adicional sobre los detalles del diseño en el archivo malloc.md

Parte 1: Administrador de bloques

En esta parte se van a implementar las estructuras de datos, y aplicar a un único bloque de memoria solicitado al kernel.

Será necesario definir un header para la abstracción de la región, incorporando una forma de marcarlas como ocupadas y libres. Conceptualmente, se debería tener algo como lo siguiente:

1
2
3
4
5
6
 --------------------------------------------------------------------
 |   header0   |   ...   |   header1   |   ...        |   header2   |
 | - free: 1   |         | - free: 0   |              | - free: 1   |
 --------------------------------------------------------------------
 <------------->         <-------------->             <------------->
  sizeof(Header)          sizeof(Header)               sizeof(Header) 

La librería reservará un bloque de 16Kib utilizando mmap(2), durante el primer llamado a malloc(), y mantendrá ese bloque hasta que finalice el programa, administrándolo eficientemente. Si en algún momento llega un pedido que supera la cantidad de memoria disponible en el bloque, se recomienda fallar (para esta primera parte).

Además, que en ningún momento (incluso cuando se puedan tener más de un bloque) se podrá solicitar una gran cantidad de memoria y administrarla desde el comienzo. La memoria debe pedirse de forma escalonada y a medida que sea necesaria.

También habrá que asegurarse que los pedidos de memoria se registran correctamente, y que la lista de regiones libres siempre está actualizada, introduciendo lógica necesaria para combinar regiones libres (coalescing).

Parte 2: Agregando más bloques

Extender la lógica anterior para que la librería pueda administrar más de un bloque de memoria a la vez. Se definirán bloques de distintos tamaños y así permitiremos alocamientos de mayor tamaño.

Se definirán tres tamaños de bloque: pequeño (16Kib), mediano (1Mib) y grande (32Mib); y la librería deberá administrar múltiples instancias de cada tamaño de bloque.

El procedimiento debería pasar a ser el siguiente: empezar, como en la parte 1, con un único bloque (el más pequeño requerido). Mientras sea posible, trabajar con éste devolviendo regiones contenidas en él. Si nos quedamos sin memoria en ese bloque, alocar otro bloque, cuyo tamaño sea tan pequeño como sea posible, dentro de las opciones definidas. Es decir, buscar el tamaño de bloque más pequeño en el cual cabe el pedido del usuario.

Si se pidiera más memoria que el bloque de tamaño más grande; entonces la librería debería fallar. Se puede además definir un tamaño máximo para toda la librería (i.e. la suma de todos los bloques administrados nunca podrá exceder tal valor).

A la hora de recibir un pedido de malloc(), la librería debería entonces iterar sobre todos los bloques que esté administrando, comenzando por los más pequeños hasta encontrar uno que posea una región apropiada.

Cuando se reciba un free() que libere completamente un bloque (i.e. termine conteniendo una única región que englobe el bloque completo), debería ocasionar un munmap() de tal bloque; devolviendo así la memoria al sistema.

Parte 3: Mejorando la búsqueda de regiones libres

En esta sección, se implementará una nueva estrategia de búsqueda denominada “best fit”. La misma consiste en poder encontrar la “mejor” región disponible para el tamaño pedido.

Para facilitar la corrección y poder compilar contra ambas implementaciones, el esqueleto y el Makefile proveen lo siguiente:

1
2
3
4
5
6
7
#ifdef FIRST_FIT
   // implementación "First Fit"
#endif

#ifdef BEST_FIT
   // implementación "Best Fit"
#endif

Parte 4: Agrandar/Achicar regiones

En esta parte, finalmente, se agregará el soporte para la función realloc(3) la cual permite, agrandar o reducir una región previamente reservada.

Conceptualmente, el algoritmo para esta función es:

1
2
3
4
5
6
7
8
9
10
void* realloc(void* ptr, size_t size)
{
    void* res = malloc(size);

    memcpy(res, ptr, old_size);

    free(ptr);

    return res;
}

Aunque esta implementación debería funcionar correctamente, no es eficiente en cuanto a la administración de las regiones y bloques libres. Por ejemplo, podría ser que la región actual, tuviera un tamaño real compatible con el nuevo tamaño, siendo la solución óptima, la de reutilizar dicha región. Pero, siguiendo el pseudocódigo se estaría utilizando una nueva región (incluso hasta un nuevo bloque).

Manejo de errores

El manejo de errores para las funciones a implementar, debería ser consistente con lo detallando en las páginas de manual. En este sentido, se tiene lo siguiente:

• malloc(3), calloc(3) y realloc(3) devuelven NULL
• free(3) no devuelve nada

Todas deben setear la variable global errno(3) con el valor ENOMEM.

Esqueleto y compilación

AVISO: El esqueleto se encuentra disponible en fisop/malloc.

IMPORTANTE: leer el archivo README.md que se encuentra en la raíz del proyecto. Contiene información sobre cómo realizar la compilación de los archivos, y cómo ejecutar el formateo de código.

Se provee un esqueleto mínimo con una implementación funcional utilizando sbrk(2) la cual puede ser compilada en cualquier programa en C que utilice la librería estándar.

Para compilar la librería se puede ejecutar:

1
make

Para correr las pruebas basta con:

1
make test

Bibliografía útil

A continuación se presentan algunos enlaces y bibliografía útiles como referencia.

• OSTEP, capítulo 17: Free-Space Management (PDF)
• The Linux Prgramming Interface, capítulo 7: Memory Allocation
• Doug Lea: A Memory Allocator
• Dan Luu: A Malloc tutorial
• Marwan Burelle: A Malloc Tutorial (PDF)