mcb.c

Go to the documentation of this file.

#include <core/mcb.h>

heapLocationPtr_t heapLoc=0;

linkedList_t mcbFreeList;
linkedList_t mcbAllocList;

e_mcb_result_t lastMCBError = MCB_SUCCESS;


void initHeap(size_t initialHeapSize)
{

    initLinkedList(&mcbFreeList);
    initLinkedList(&mcbAllocList);

    setSearchComparisonFunction(&mcbFreeList, &mcbSearchCompFunc);
    setSearchComparisonFunction(&mcbAllocList, &mcbSearchCompFunc);
    setInsertComparisonFunction(&mcbAllocList, &mcbCompareFunc);
    setInsertComparisonFunction(&mcbFreeList, &mcbCompareFunc);
    setPrintFunction(&mcbAllocList, &printMCBFunc);
    setPrintFunction(&mcbFreeList, &printMCBFunc);

    heapLoc = (heapLocationPtr_t)kmalloc(initialHeapSize + sizeof(lmcb_t) + sizeof(cmcb_t));

    printf("Heap Loc Ptr %d :: total size %d\r\n", (int)heapLoc, ((int)((int)initialHeapSize + sizeof(lmcb_t) + sizeof(cmcb_t))));

    cmcb_t* heapCMCB = (cmcb_t*)heapLoc;
    heapCMCB->representingNode.data = (void*)heapCMCB;
    heapCMCB->associatedLMCB = (lmcb_t*)(heapLoc+initialHeapSize+sizeof(cmcb_t));

    heapCMCB->cmcbType = heapCMCB->associatedLMCB->lmcbType = MCB_FREE;

    heapCMCB->blockStartAddress = (mcbAddressPtr_t)(heapLoc+sizeof(cmcb_t));
    heapCMCB->associatedLMCB->blockStopAddress = (mcbAddressPtr_t) heapCMCB->associatedLMCB;
    heapCMCB->procName = "Initial Heap";
    heapCMCB->associatedLMCB->mcbBlockSize=heapCMCB->mcbBlockSize=initialHeapSize;
    heapCMCB->associatedLMCB->lmcbType=MCB_FREE;

    insertMCBIntoList(heapCMCB);
}

//implements first fit.
//remember, size_t is unsigned
void* allocateMemFromHeap(size_t requestedSize)
{
    lastMCBError=MCB_SUCCESS;
    if(!requestedSize) //if the size is greater than zero
    {
        lastMCBError=ERROR_BLOCK_NOT_ALLOCATED;
        return 0;
    }
    mcbSize_t totalBlockSize = requestedSize + sizeof(lmcb_t) + sizeof(cmcb_t);
    //requestedSize + sizeof(lmcb_t) + sizeof(cmcb_t)
    cmcb_t * allocatedCMCB = 0;
    node_t * itNode = mcbFreeList.head.next;
    for(; itNode != &(mcbFreeList.tail); itNode = itNode->next)
    {
        //should not do subtraction with unsigned types. < 0 IS > 0 because of wrap around

        if(((cmcb_t*)itNode->data)->mcbBlockSize >= totalBlockSize)
        {
            //we found a block large enough
            //printf("\r\nBlock size %d,  total block size %d\r\n", ((cmcb_t*)itNode->data)->mcbBlockSize, totalBlockSize);
            allocatedCMCB = ((cmcb_t*)itNode->data);
            break;
        }
    }
    if(!allocatedCMCB) //if there are no blocks large enough
    {
        lastMCBError=ERROR_NOT_ENOUGH_MEMORY;
        return 0;
    }

    (void)removeNode(&(allocatedCMCB->representingNode));
    //set the new sizes
    allocatedCMCB->cmcbType = MCB_ALLOCATED;
    allocatedCMCB->mcbBlockSize = requestedSize;

    //we have a pointer to a cmcb that is large enough.
    //first step is
        //to, firstly calculate the IMMEDIATE following cmcb offset from the cmcb block start

    cmcb_t* followCMCB = (cmcb_t*)((void*)allocatedCMCB + totalBlockSize);

    //setup the follow cmcb
    followCMCB->representingNode.data = (void*)followCMCB;
    followCMCB->cmcbType = MCB_FREE;
    //the following cmcb's lmcb is the allocatedCMCBs current lmcb
    followCMCB->associatedLMCB = allocatedCMCB->associatedLMCB;
    //calc block start offset
    followCMCB->blockStartAddress = ((void*)followCMCB)+sizeof(cmcb_t);
    //the block size is the lmcb's blockStop - cmcb's blockStart
    followCMCB->associatedLMCB->mcbBlockSize=
            followCMCB->mcbBlockSize=
                (followCMCB->associatedLMCB->blockStopAddress-followCMCB->blockStartAddress);
    followCMCB->procName = "";

    //setup the allocatedCMCB's new lmcb
    allocatedCMCB->associatedLMCB = (lmcb_t*)(((void*)allocatedCMCB->blockStartAddress)+allocatedCMCB->mcbBlockSize);
    allocatedCMCB->associatedLMCB->lmcbType = allocatedCMCB->cmcbType;
    allocatedCMCB->associatedLMCB->blockStopAddress = allocatedCMCB->associatedLMCB;

    //put the process's name pointer
    if(currentOperatingProcess && currentOperatingProcess->name)
    {
        allocatedCMCB->procName = currentOperatingProcess->name;
    }
    else
    {
        allocatedCMCB->procName = "init";
    }


    insertMCBIntoList(allocatedCMCB);
    insertMCBIntoList(followCMCB);


    return (void*)allocatedCMCB->blockStartAddress;

}

void printAlloc()
{
    printf("%s", "\r\nAllocated Memory Blocks\r\n");
    printList(&mcbAllocList);
}

void printFree()
{
    printf("%s", "\r\nFree Memory Blocks\r\n");
    printList(&mcbFreeList);
}

int mcbCompareFunc(void* mcb,  void* mcbToCompare)
{
    if(((cmcb_t*)mcb)->blockStartAddress == ((cmcb_t*)mcbToCompare)->blockStartAddress)
    {
        return 0;
    }
    return (((cmcb_t*)mcb)->blockStartAddress < ((cmcb_t*)mcbToCompare)->blockStartAddress)?-1:1;
}

int mcbSearchCompFunc(void* mcb,  void* blockStartAddress)
{
    if(((cmcb_t*)mcb)->blockStartAddress == blockStartAddress)
    {
        return 0;
    }
    return (((cmcb_t*)mcb)->blockStartAddress < blockStartAddress)?-1:1;
}


int freeHeapMem(void* blockAddress)
{
    lastMCBError=MCB_SUCCESS;
    node_t* foundNode = searchList(&mcbAllocList, blockAddress);
    cmcb_t* foundCMCB = (foundNode)?(cmcb_t*)foundNode->data:0;
    if(!foundCMCB)
    {
        lastMCBError=ERROR_BLOCK_NOT_FOUND;
        return lastMCBError;
    }
    if(currentOperatingProcess->name != foundCMCB->procName)
    {
        lastMCBError=MCB_ERROR_ACCESS_DENIED;
        return lastMCBError;
    }

    //printf("\r\nin free%s","\r\n");
    printMCBFunc(foundCMCB);

    (void)removeNode(&(foundCMCB->representingNode));
    foundCMCB->procName = "";
    foundCMCB->cmcbType=foundCMCB->associatedLMCB->lmcbType=MCB_FREE;
    insertMCBIntoList(foundCMCB);

    reclaimFreeMem();
    reclaimFreeMem();

    return lastMCBError;
}

void reclaimFreeMem()
{
    cmcb_t* foundCMCB=(cmcb_t*)mcbFreeList.head.next;
    for(; &(foundCMCB->representingNode) != &(mcbFreeList.tail); foundCMCB=(cmcb_t*)foundCMCB->representingNode.next)
    {
        //check if not beginning of list
        if(foundCMCB->representingNode.prev != &(mcbFreeList.head))
        {
            //chek if contiguous memory
            if(((void*)((cmcb_t*)foundCMCB->representingNode.prev)->associatedLMCB)+sizeof(lmcb_t*) == foundCMCB)
            {
                //cmcbs are contiguous, combine

                ((cmcb_t*)foundCMCB->representingNode.prev)->associatedLMCB=foundCMCB->associatedLMCB;
                foundCMCB=((cmcb_t*)foundCMCB->representingNode.prev);
                foundCMCB->mcbBlockSize=foundCMCB->associatedLMCB->mcbBlockSize=
                        ((void*)foundCMCB->associatedLMCB->blockStopAddress)-
                            ((void*)foundCMCB->blockStartAddress); //set the new mcb block size

                (void)removeNode(foundCMCB->representingNode.next);
            }
        }
        //check if not end of list
        if(foundCMCB->representingNode.next != &(mcbFreeList.tail))
        {
            //chek if contiguous memory
            if(((void*)(((cmcb_t*)foundCMCB->representingNode.next)))==(((void*)foundCMCB->associatedLMCB)+sizeof(lmcb_t)))
            {
                foundCMCB->associatedLMCB=((cmcb_t*)foundCMCB->representingNode.next)->associatedLMCB;
                foundCMCB->mcbBlockSize=foundCMCB->associatedLMCB->mcbBlockSize=
                        ((void*)foundCMCB->associatedLMCB->blockStopAddress)-
                            ((void*)foundCMCB->blockStartAddress);

                (void)removeNode(foundCMCB->representingNode.next);
            }
        }
    }
}

void printMCBFunc(void* cmcb)
{
    printf("Type: %s || Associ Proc: %s || Block Size: %d || block ptr: %d\r\n", mcbTypeToString(((cmcb_t*)cmcb)->cmcbType),
                                    ((cmcb_t*)cmcb)->procName, ((cmcb_t*)cmcb)->mcbBlockSize, (int)((cmcb_t*)cmcb)->blockStartAddress);
}

int heapIsEmpty()
{
    lastMCBError=MCB_SUCCESS;
    if(mcbAllocList.head.next == &mcbAllocList.tail) return 0;
    return 1;
}
const char* mcbResultToString(e_mcb_result_t result)
{
    switch(result)
    {
        case MCB_SUCCESS:
            return "SUCCESS";
        case ERROR_BLOCK_NOT_FOUND:
            return "ERROR_BLOCK_NOT_FOUND";
        case ERROR_BLOCK_NOT_ALLOCATED:
            return "ERROR_BLOCK_NOT_ALLOCATED";
        case ERROR_NOT_ENOUGH_MEMORY:
            return "ERROR_NOT_ENOUGH_MEMORY";
        case MCB_ERROR_ACCESS_DENIED:
            return "ACCESS_DENIED";

        case ERROR_GENERIC:
        default:
            return "ERROR_UNKNOWN";
    }
    return "ERROR_UNKNOWN";
}

const char* mcbTypeToString(e_mcb_type_t type)
{
    switch(type)
    {
        case MCB_FREE:
            return "FREE     ";
        case MCB_ALLOCATED:
            return "ALLOCATED";
        default:
            break;
    }
            return "UNKNOWN  ";
}

void insertMCBIntoList(cmcb_t* blockToInsert)
{
    lastMCBError=MCB_SUCCESS;
    switch (blockToInsert->cmcbType) {
    case MCB_FREE:
        insertNode(&mcbFreeList, &(blockToInsert->representingNode));
        break;
    case MCB_ALLOCATED:
        insertNode(&mcbAllocList, &(blockToInsert->representingNode));
        break;
    default:
        break;
    }
}

void heapTest()
{
    printf("HEAP TEST%s","\r\n");
    printf("%s", "Alloc list\r\n")
    printList(&mcbAllocList);
    printf("%s", "free list\r\n")
    printList(&mcbFreeList);
    printf("%s","\r\n\r\n");
    int* test = (int*)allocateMemFromHeap(20);
    if(lastMCBError!=MCB_SUCCESS)
    {
        printf("MCB Error! %s\r\n",mcbResultToString(lastMCBError));
    }
    printf("test int ptr %d\r\n",(int)test);
    int *blocks[5];
    for(*test = 0; *test < 5; (*test)++)
    {
        blocks[*test] = (int*)allocateMemFromHeap(20);
        if(lastMCBError!=MCB_SUCCESS)
        {
            printf("MCB Error! %s\r\n",mcbResultToString(lastMCBError));
        }
    }
    printf("%s", "\r\nAlloc list\r\n")
    printList(&mcbAllocList);
    printf("%s", "\r\nfree list\r\n")
    printList(&mcbFreeList);
    for(*test = 0; *test < 5; (*test)++)
    {
        freeHeapMem(blocks[*test]);
        if(lastMCBError!=MCB_SUCCESS)
        {
            printf("MCB Error! %s\r\n",mcbResultToString(lastMCBError));
        }
    }
    freeHeapMem(test);
    printf("%s", "\r\nAlloc list\r\n")
    printList(&mcbAllocList);
    printf("%s", "\r\nfree list\r\n")
    printList(&mcbFreeList);
}