En la publicación anterior de esta serie sobre la implementación de malloc() y free(), mostramos cómo es posible reutilizar bloques de memoria y reducir el montón liberando bloques más nuevos. Sin embargo, la función actual introduce un problema sutil: prioriza la reutilización de bloques más nuevos, lo que puede provocar un mayor consumo de memoria con el tiempo. ¿Por qué sucede esto? Analicémoslo.

Reducción del montón mediante la reutilización de bloques recientes

Considere el siguiente escenario. Primero, asignamos cuatro bloques de memoria:

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

La estructura de la memoria se puede visualizar así:

Ahora lanzamos el primer y tercer bloque…

abfree(ptr1);
abfree(ptr3);

…resultando en la siguiente estructura:

Luego asignamos otro bloque del mismo tamaño:

void *ptr5 = abmalloc(8);

Cuando la función abmalloc() comienza a buscar el bloque libre más reciente, reutiliza el bloque en la parte superior. Si ahora liberamos el último bloque:

Si ahora liberamos el último bloque…

abfree(ptr4);

…podemos reducir el tamaño del montón en solo un bloque de 8 bytes, ya que el bloque anterior ya no está libre:

Reutilización de bloques antiguos

Ahora, imagina el mismo escenario, pero con una modificación: nuestra función comienza a buscar bloques libres a partir del más antiguo. La estructura inicial será la misma…

…y nuevamente liberamos el primer y tercer bloque de memoria:

Esta vez, se reutilizará el primer bloque:

Ahora, cuando liberemos el último bloque, tendremos dos bloques libres en la parte superior, lo que nos permitirá reducir el montón en dos bloques de 8 bytes:

Este ejemplo ilustra cómo, al dar preferencia a bloques más nuevos, terminamos acumulando bloques antiguos no utilizados, desperdiciando memoria y generando un crecimiento innecesario del montón. La solución es modificar la estrategia de búsqueda, priorizando la reutilización de bloques más antiguos.

Implementación de preferencia por bloques antiguos.

Para resolver este problema, comenzaremos agregando un puntero al siguiente bloque en el encabezado. También crearemos un puntero global al primer bloque, para que podamos iniciar la búsqueda desde él:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

Crearemos bloques de memoria con encabezados en dos situaciones diferentes, así que hagamos una pequeña refactorización: extraeremos esta lógica a una función auxiliar que asigna e inicializa el encabezado (incluida la configuración del campo siguiente con NULL):

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

Con esta nueva función, podemos simplificar la lógica dentro de abmalloc():

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  Header *header = last; 
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->previous; 
  } 
  last = header_new(last, size, false); 
  return last   1; 
}

Ahora tenemos acceso al primer y último bloque, y dado un bloque, podemos conocer el anterior y el siguiente. También sabemos que cuando el puntero al primer bloque es nulo, todavía no se han asignado bloques. Entonces, en este caso, asignaremos el bloque inmediatamente e inicializaremos tanto el primero como el último:

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first   1; 
  }

Si primero ya no es NULL, ya hay bloques asignados, por lo que comenzaremos a buscar un bloque reutilizable. Continuaremos usando la variable headeras como iterador, pero en lugar de comenzar con el bloque más reciente, la búsqueda comenzará desde el más antiguo:

  Header *header = first;

En cada iteración, avanzaremos al siguiente bloque de la secuencia, en lugar de retroceder al bloque anterior:

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->next; 
  }

La lógica sigue siendo la misma: si encontramos un bloque disponible de tamaño suficiente, se devuelve. De lo contrario, si no se encuentra ningún bloque reutilizable después de recorrer la lista, se asigna un nuevo bloque:

  last = header_new(last, size, false);

Ahora, necesitamos ajustar el bloque que fue el último (después de la asignación, el penúltimo). Apuntó a NULL, pero ahora debería apuntar al nuevo bloque. Para hacer esto, configuramos el campo siguiente del bloque anterior en el nuevo último bloque:

  last->previous->next = last; 
  return last   1; 
}

Ajustes en abfree()

La función abfree() básicamente mantiene la misma estructura, pero ahora debemos manejar algunos casos extremos. Cuando liberamos bloques en la parte superior del montón, un nuevo bloque se convierte en el último, como ya hacemos en este fragmento:

    last = header->previous;
    brk(header)

Aquí, el encabezado del puntero hace referencia al último bloque no nulo disponible en la pila. Tenemos dos escenarios posibles:

1. el bloque actual tiene un bloque anterior, que se convertirá en el nuevo último bloque. En este caso, deberíamos establecer el puntero al lado de este bloque en NULL.
2. el bloque actual no tiene un bloque anterior (es decir, es el primer bloque y el más antiguo). Cuando se libera, la pila está vacía. En este caso, en lugar de intentar actualizar un campo de un bloque inexistente, simplemente lo configuramos primero en NULL, indicando que no hay más bloques asignados.

Así es como lo implementamos:

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

Conclusión

Nuestras funciones abmalloc() y abfree() ahora se ven así:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first   1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header   1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last   1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

Este cambio nos permite ahorrar considerablemente más memoria. Sin embargo, todavía quedan problemas por resolver. Por ejemplo, considere el siguiente escenario: solicitamos la asignación de un bloque de memoria de 8 bytes y abmalloc() reutiliza un bloque de, digamos, 1024 bytes. Claramente hay un desperdicio.

Veremos cómo solucionar esto en la próxima publicación.