Implementacion de malloc basado en sbrk

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.