Esta semana se me ocurrió volver a hacer una tarea de la universidad que me gusta mucho. Crear un programa en el que se pueda sub-administrar un pedazo de memoria.

My Image

Este programa debe ser capaz de manejar lo siguiente:

  • Iniciar (N): pedir al sistema operativo un pedazo de memoria de tamaño N bytes, donde N es potencia de 2.
  • Reservar espacio (X): sub-reservar un espacio dentro de nuestra memoria, de tamaño X | X <= N
  • Liberar espacio (objeto): liberar espacio dónde está el objeto.
  • Terminar: Liberar todo el espacio, para poder ejecutar desde el inicio una vez mas.

Sabiendo esto podemos empezar con algunas definiciones:

// memoria.h
#include <stdlib.h>

void iniciar(u_int64_t tamano);
void *reservar_memoria(u_int64_t n);
void liberar_memoria(void *objeto);
void finalizar(void);

Es importante minimizar el desperdicio, no queremos 512 bytes para guardar un número entero. Por eso es necesario hacer divisiones en la memoria. Teniendo esto en cuenta podemos plantear un diseño, en el que la memoria se divida entre 2, hasta encontrar el tamaño más cercano al solicitado. Si tenemos una memoria de 512 bytes, y queremos solamente usar 256, podemos partir en 2 nuestra memoria, usar 256 y dejar 256 bytes libres. Si quisiéramos guardar 100 bytes, tendríamos algo de desperdicio, pero la idea es la misma, dividimos en dos la memoria, 256 y 256. Tomamos la primer mitad y la volvemos a partir en dos, teniendo 128, 128 y 256, de los cuales nos quedan libres un pedazo de 128 y uno de 256. También, al liberar pedazos más pequeños, la memoria debe de juntarse en las mitades de las que proviene, así al liberar toda la memoria, tenemos nuevamente un solo pedazo con todo el espacio disponible.

Si ponemos esas ideas en un diagrama seria algo así: Diagrama de Memoria

Lo siguiente a definir es cómo le vamos a hacer para saber donde empieza un pedazo y termina otro, cuál esta reservado y cuál disponible. Para lograr esto probablemente hay miles de caminos diferentes, sin embargo, cuando hice esta tarea por primera vez, el tema central eran las listas ligadas.

Creamos una lista ligada con la información que necesitamos en cada nodo: identificador del programa al que pertenece, tamaño del segmento de memoria y un apuntador al siguiente pedazo de memoria.

// memoria.h

typedef struct _header Cabecera;
typedef struct _header{
    u_int64_t id;
    u_int64_t tamano;
    Cabecera *siguiente;
}header;

Con esta lista, nosotros podemos conectar cada uno de los segmentos de memoria, solamente es necesario que en los primeros bytes de cada segmento escribamos el nodo de nuestra lista (Cabecera) y que siempre mantengamos los segmentos conectados correctamente con los apuntadores. Para el propósito de este ejercicio, los pedazos libres los represento con el id 0x0 y los ocupados, con id de una aplicación ficticia, cualquier número diferente que 0x0. Diagrama de Memoria

Con estas últimas ideas, lo único que falta es rellenar las funciones, cuidando un detalle más, el espacio que ocupa la cabecera. Si solicitamos 64 bytes, debemos reservar al menos esos 64 bytes más el tamaño de la cabecera, por lo tanto, sabiendo que nuestra cabecera mide 24 bytes, al solicitar 64 bytes, realmente se solicitan 64 + 24, resultando en un espacio de 128 al seguir el método de fragmentación que decidimos usar. El tamaño de la cabecera lo podemos obtener de esta forma:

u_int64_t TAMANO_CABECERA = 2 * sizeof(u_int64_t) + sizeof(Cabecera*);

Como correr pruebas

Al probar el programa me di cuenta de varias cosas, C permite acceder a direcciones de memoria que no hemos reservado, sin marcar ningún error. Al usar aritmética de apuntadores es fácil que estemos accediendo a una dirección equivocada, con la bandera -fsanitize=address al compilar, el programa nos avisa si estamos leyendo o escribiendo en una dirección que no nos corresponde. Además de esa bandera, es bueno usar -Wall -Werror, para tratar a todos los warnings como errores.

gcc -Wall -Werror -fsanitize=address memoria.c -o memoria
./memoria

Aritmética de apuntadores

Al inicializar nuestro programa, pediremos al sistema que nos reserve cualquier cantidad de bytes. Para hacer esto creé un tipo de dato byte, que a final de cuentas es un entero de 8 bits sin signo. Y para almacenar la dirección de inicio de nuestro segmento, creé un apuntador de tipo byte, memoria.

// memoria.h
typedef uint8_t byte;

//memoria.c
#include <stdio.h>
#include "memoria.h"

static byte *memoria = NULL;
.
.
.
u_int64_t N = 512;
memoria = malloc(N);

Al ejecutar la última linea del código de arriba, malloc, estará reservando N veces el tipo de nuestra variable a la que la asignamos. En este caso el tipo de nuestra variable es byte, así que estamos reservando 512 bytes. Si fuera de tipo entero de 32 bits nuestro apuntador memoria, estaríamos reservando 32 * 512 bits o 2048 bytes.

Como cada dirección en la memoria almacena 1 byte. Podemos decir que cada variable de tipo byte que creamos ocupa una sola dirección de la memoria y que cada dirección de la memoria puede contener únicamente una sola variable de tipo byte. Sabiendo esto podemos decir que si la dirección a la que nuestro apuntador memoria apunta es la 0, nuestro segmento de memoria termina en la dirección 512. Volviendo al ejemplo de reservar enteros de 32 bits, si la primera dirección es 0 y reservamos 512 enteros de 32 bits, la última dirección del arreglo es 2047. Si lo escribimos en C, usando las variables que definimos en el anterior bloque, queda esto:

u_int64_t inicio = (u_int64_t)memoria;
u_int64_t fin = (u_int64_t)&memoria[N-1];

printf("Direccion inicio: %llu\n", inicio);
printf("Direccion fin: %llu\n", fin);

// Direccion inicio: 106996225278080
// Direccion fin: 106996225278591

Entonces si quisiéramos crear un apuntador a la mitad de nuestro segmento de memoria, lo podríamos hacer así:

byte * mitad_memoria = memoria + N/2;

Siempre cuidando que los apuntadores que usemos sean tipo byte, para que cada unidad que incrementemos, solo avance una dirección de la memoria.

Y si hacemos lo siguiente, podemos forzar a escribir nuestra Cabecera en los 24 bytes que más nos acomoden, en este caso a la mitad del segmento de memoria:

byte * mitad_memoria = memoria + N/2;

Cabecera *bloque_nuevo = (Cabecera*)mitad_memoria;
bloque_nuevo->siguiente = NULL;
bloque_nuevo->id = 0;
bloque_nuevo->tamano = N/2;

Particiones y uniones

Este es esquema de memoria apareció por primera vez en el artículo A fast storage allocator, por Kenneth C. Knowlton, publicado en 1965.

En nuestra implementación, debemos de aplicar divisiones cuando reservamos espacio y uniones cuando liberamos espacio ocupado, para siempre tener el menor número posible de particiones. Para que todo esto funcione, siempre tenemos que mantener un apuntador al inicio de nuestra memoria: static byte *memoria;. Para reservar espacio, primero hay que encontrar memoria libre suficientemente grande, iterando por la lista, hasta encontrar un espacio con id 0. Al encontrar algo, es necesario ver si podemos dividirla entre dos, o si la dejamos del tamaño que está.

Encontrar espacio vacío con un tamaño de al menos (n + TAMANO_CABECERA):

Cabecera * indice_memoria = (Cabecera*)memoria;
while (indice_memoria != NULL){
    if (indice_memoria->id == 0){

        if (indice_memoria->tamano >= (n + TAMANO_CABECERA)){
            break;
        }
    }
    indice_memoria = indice_memoria->siguiente;
}

Partir cuantas veces podamos la memoria para minimizar desperdicio:

if (indice_memoria != NULL){
    while (indice_memoria->tamano / 2 >= (n + TAMANO_CABECERA)){
        indice_memoria->tamano = indice_memoria->tamano / 2;
        byte * ptr = (byte*)indice_memoria + indice_memoria->tamano;

        Cabecera *bloque_nuevo = (Cabecera*)ptr;
        bloque_nuevo->siguiente = indice_memoria->siguiente;
        bloque_nuevo->id = 0;
        bloque_nuevo->tamano = indice_memoria->tamano;
        indice_memoria->siguiente = bloque_nuevo;
    }
    // id programa ficticio
    indice_memoria->id = 0x12345678;
}

El proceso para liberar memoria es más simple, tan solo basta con cambiar el id de la cabecera a 0x0:

void *objeto_liberar = reservar_memoria(x_bytes)
Cabecera*bloque_memoria = (Cabecera*)objeto_liberar;
bloque_memoria->id = 0;

Unir los bloques vacíos me tomó un poco más pensarla. ¿Cómo podemos saber si un par de bloques consecutivos del mismo tamaño se pueden unir o no? La solución fue recursiva. Empezando por el bloque cero, lo tratamos de unir con el consecutivo. Si el bloque consecutivo es más chico, entonces ese siguiente bloque lo tomamos como el bloque cero, y hacemos lo mismo lo tratamos de unir al bloque consecutivo. Si se logran unir, entonces solo hace falta cambiar los apuntadores y seguir con el siguiente bloque.

El resultado es una función recursiva con 3 casos:

  1. El bloque actual llega hasta el final del segmento, entonces termina la función.
  2. El bloque consecutivo es del mismo tamaño y se encuentra vacío, entonces juntamos los bloque y volvemos a aplicar la función sobre el nuevo bloque.
  3. El siguiente bloque es más pequeño, entonces hay que aplicar la función sobre ese bloque y el siguiente.
void unir_espacio(byte *inicio){
    Cabecera*info = (Cabecera*)inicio;
    if(inicio + info->tamano >= memoria + tamano_total){

        return;
    }
    else if(info->siguiente->tamano == info->tamano && info->siguiente->id == 0){
        info->tamano = info->tamano * 2;
        info->siguiente = info->siguiente->siguiente;

        unir_espacio(inicio);
    }
    else {
        byte * siguiente = inicio + info->tamano;
        unir_espacio(siguiente);
    }
}

Código fuente

memoria.h

memoria.c

Todo lo anterior en un programa. Para compilar:

gcc -Wall -Werror -fsanitize=address memoria.c -o memoria

Para ejecutar:

./memoria

Todo el código esta pensado para una computadora de 64 bits, en un sistema de 32 bit puede tener un comportamiento extraño, debido a la diferencia de tamaño de los apuntadores.

Ejemplo de ejecución reservando 8 bytes, 100 bytes, 200 bytes y 32 bytes, en un espacio de 1KB:

      NULL
       |
------------------
ID: 0x12345678
Tamaño: 32
Direccion inicio: 0x619000000080
Direccion fin: 0x61900000009f
------------------
       |
------------------
ID: 0x0
Tamaño: 32
Direccion inicio: 0x6190000000a0
Direccion fin: 0x6190000000bf
------------------
       |
------------------
ID: 0x12345678
Tamaño: 64
Direccion inicio: 0x6190000000c0
Direccion fin: 0x6190000000ff
------------------
       |
------------------
ID: 0x12345678
Tamaño: 128
Direccion inicio: 0x619000000100
Direccion fin: 0x61900000017f
------------------
       |
------------------
ID: 0x12345678
Tamaño: 256
Direccion inicio: 0x619000000180
Direccion fin: 0x61900000027f
------------------
       |
------------------
ID: 0x0
Tamaño: 512
Direccion inicio: 0x619000000280
Direccion fin: 0x61900000047f
------------------
       |
      NULL