Implementación de malloc basado en sbrk
La siguiente implementación de malloc basada en sbrk, no pretende ser un reemplazo de la función malloc, el propósito de esta implementación es didáctico y busca ampliar la compresión frente a los conceptos de asignación y liberación de memoria.
La implementación de malloc está basada en las siguientes premisas:
- Se asigna el primer bloque de memoria libre que se ajuste al requerimiento del programa.
- Si un bloque de memoria libre es considerablemente más grande que el requerimiento del programa, el bloque será dividido con el fin de ahorrar espacio.
- El tamaño de los bloques de memoria asignado deber ser múltiplos de 4.
La implementación de la función free está basada en las siguientes premisas:
- Si se encuentran dos bloques de memoria contiguos libres, estos serán fusionados para crear un solo bloque de memoria más grande.
- No se realizara una contracción del program break (brk) a no ser que toda la memoria requerida por el programa sea liberada.
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <stdlib.h>
/* Este macro define una formula para encontrar el multiplo
de cuatro mas cercano al valor requerido*/
#define align4(x) (((((x)-1)>>2)<<2)+4)
/* Define el tamaño del struct, esto es realizado para no usar malloc*/
#define BLOCK_SIZE 20
/* Struct que contiene la metadata relacionada con el bloque de memoria*/
struct memory_block
{
size_t size;
struct memory_block *next;
struct memory_block *prev;
int free;
void *pointer;
char data[1];
};
typedef struct memory_block *chunk;
chunk rootPointer= NULL;
chunk tailPointer= NULL;
/* Divide el bloque de memoria con el fin de realizar un mejor uso de este
recurso*/
void splitMemoryChunk(chunk memoryChunk, size_t size)
{
chunk newChunk;
newChunk= (chunk) (memoryChunk->data + size);
newChunk->size= memoryChunk->size - size - BLOCK_SIZE;
newChunk->next= memoryChunk->next;
newChunk->prev= memoryChunk;
newChunk->free= 1;
newChunk->pointer= newChunk->data;
memoryChunk->size= size;
memoryChunk->next= newChunk;
if(newChunk->next)
{
newChunk->next->prev= newChunk;
}
}
/* Imprime la metadata relacionada con el bloque de memoria*/
void printMemoryInfo(chunk memoryAddress)
{
printf("\n\t **** Memory Allocation Info ****\t\n");
printf("\t Memory Address: %10p", memoryAddress);
printf("\n\t Memory Size: %d", memoryAddress->size);
printf("\n\t Memory Free: %d", memoryAddress->free);
printf("\n\t Memory Data: %p", memoryAddress->data);
printf("\n\t Memory Pointer %p", memoryAddress->pointer);
printf("\n\t ******************************** \t\n");
}
/* Realiza la busqueda de un bloque de memoria que se ajuste
al tamaño requerido*/
chunk findFirstFit(chunk *lastChunk, size_t size)
{
chunk currentChunk= rootPointer;
while (currentChunk && !(currentChunk->free && currentChunk->size >= size))
{
*lastChunk= currentChunk;
currentChunk= currentChunk->next;
}
return currentChunk;
}
/* Crea un nuevo bloque de memoria */
chunk extendHeap(chunk lastChunk, size_t size)
{
chunk newChunk;
newChunk= sbrk(0);
if(sbrk(BLOCK_SIZE + size) == (void *) -1)
{
return NULL;
}
newChunk->size= size;
newChunk->next= NULL;
newChunk->prev= lastChunk;
newChunk->pointer= newChunk->data;
if(lastChunk)
{
lastChunk->next= newChunk;
}
newChunk->free= 0;
printMemoryInfo(newChunk);
return newChunk;
}
/* Imprime la metadata de todos los bloques de memoria*/
void printChunkList()
{
printf ("\n\t **** Print Memory Chunk List **** \t\n");
chunk memoryRunner= rootPointer;
while(memoryRunner != NULL)
{
printMemoryInfo(memoryRunner);
memoryRunner= memoryRunner->next;
}
printf ("\n\t **** End Chunk List **** \t\n");
}
/* Implemetacion de malloc que realiza la asignacion
de memoria*/
void *myMalloc(size_t size)
{
chunk lastChunk, memoryChunk;
size_t alignSize= align4(size);
if(rootPointer)
{
lastChunk= rootPointer;
memoryChunk= findFirstFit(&lastChunk, alignSize);
if(memoryChunk)
{
printf("\n\t **** Find Memory Chunk ****\t\n");
printMemoryInfo(memoryChunk);
if((memoryChunk->size - alignSize) >= (BLOCK_SIZE + 4))
{
splitMemoryChunk(memoryChunk, alignSize);
}
memoryChunk->free= 0;
}
else
{
memoryChunk= extendHeap(lastChunk, alignSize);
if(!memoryChunk)
{
return NULL;
}
}
}
else
{
memoryChunk= extendHeap(NULL, alignSize);
if (!memoryChunk)
{
return NULL;
}
rootPointer= memoryChunk;
}
return (memoryChunk->data);
}
/* Obtiene la direcccion de memoria que almacena la metadata
del bloque de memoria*/
chunk getMemoryChunk(void *chunkPointer)
{
char *tmp;
tmp= chunkPointer;
chunkPointer= tmp -= BLOCK_SIZE;
return chunkPointer;
}
/* Valida si la direccion de memoria que requiere ser liberada, en efecto fue entregada
mediante nuestra implementacion de malloc*/
int validMemoryAddress(void *chunkPointer)
{
if(rootPointer)
{
if (chunkPointer > (void *) rootPointer && chunkPointer < sbrk(0))
{
return (chunkPointer == (getMemoryChunk(chunkPointer))->pointer);
}
}
return 0;
}
/* Fusiona dos bloques de memoria libres*/
chunk mergeMemoryChunk(chunk memoryChunk)
{
if(memoryChunk->next && memoryChunk->next->free)
{
memoryChunk->size= memoryChunk->size + BLOCK_SIZE + memoryChunk->next->size;
memoryChunk->next= memoryChunk->next->next;
if(memoryChunk->next)
{
memoryChunk->next->prev= memoryChunk;
}
}
return memoryChunk;
}
/* Implementacion de la funcion free*/
void myFree(void *chunkPointer)
{
chunk memoryMetadata;
if(validMemoryAddress(chunkPointer))
{
memoryMetadata= getMemoryChunk(chunkPointer);
memoryMetadata->free= 1;
printf("\n\t **** Memory Free Info **** \t\n");
printMemoryInfo(memoryMetadata);
if (memoryMetadata->prev && memoryMetadata->prev->free)
{
memoryMetadata= mergeMemoryChunk(memoryMetadata->prev);
if(memoryMetadata->next)
{
mergeMemoryChunk(memoryMetadata);
}
else
{
if (memoryMetadata->prev)
{
memoryMetadata->prev->next= NULL;
}
else
{
rootPointer= NULL;
brk(memoryMetadata);
}
}
}
}
}
int main()
{
int *pointer1;
int *pointer2;
int *pointer3;
int *pointer4;
int *pointer5;
int *pointer6;
pointer1= myMalloc(10);
pointer2= myMalloc(10);
pointer3= myMalloc(100);
pointer4= myMalloc(10);
pointer5= myMalloc(10);
printChunkList();
myFree(pointer3);
myFree(pointer4);
printChunkList();
pointer6= myMalloc(15);
printChunkList();
return 0;
}
Notas
- En las funciones implementadas contienen algunas adiciones de la instrucción printf con l fin de visualizar los bloques de memoria manipulados por las operaciones.
- La implemetación esta basada en el texto proporcionado en texto Malloc Tutorial.
- La Implementación de este programa fue concebida con el fin de dar solución al problema propuesto en el capitulo 7 del libro Linux Programming Interface.
