mcb.h File Reference

#include <system.h>
#include <mem/heap.h>
#include <core/pcb.h>
#include <linked_list.h>

Include dependency graph for mcb.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	s_cmcb
	The s_cmcb struct the struct type for cmcb's -> defines the properties. More...
struct	s_lmcb
	The s_lmcb struct defines the properties of lmcb's. More...

Typedefs
typedef struct s_cmcb	cmcb_t
typedef struct s_lmcb	lmcb_t
typedef void *	mcbAddressPtr_t
typedef size_t	mcbSize_t
typedef void *	heapLocationPtr_t

Enumerations
enum	e_mcb_result_t {   MCB_SUCCESS, ERROR_BLOCK_NOT_FOUND, ERROR_BLOCK_NOT_ALLOCATED, ERROR_GENERIC,   ERROR_NOT_ENOUGH_MEMORY, MCB_ERROR_ACCESS_DENIED }
	The e_mcb_result_t enum defines the return status of functions working with MCBs. More...
enum	e_mcb_type_t { MCB_FREE, MCB_ALLOCATED, MCB_NOT_FREE }
	The e_mcb_type_t enum defines the state of the MCBs. More...

Functions
struct s_cmcb	__attribute__ ((packed))
void	initHeap (size_t initialHeapSize)
	initHeap initializes the system heap by calling kmalloc with a valid byte size. Creates a CMCB at the beginning and an LMCB at the end. Note the total size is the given size + sizeof(CMCB) + sizeof(LMCB). More...
void *	allocateMemFromHeap (size_t requestedSize)
	allocateMemFromHeap takes the requested size and finds the first block that fits. Implements first fit. Size_t is unsigned. More...
int	freeHeapMem (void *blockAddress)
	freeHeapMem takes the block address and frees the memory from the CMCB start to the LMCB end location and calls reclaimFreeMem() function. More...
mcbSize_t	sizeOfHeapAllocated ()
mcbSize_t	sizeOfHeapFree ()
void	printAlloc ()
	printAlloc prints the allocated memory blocks. Traverses through the allocated mcb list. More...
void	printFree ()
	printFree prints the free memory blocks. Traverses through the free mcb list. More...
int	heapIsEmpty ()
	heapIsEmpty returns if the heap is empty. More...
const char *	mcbResultToString (e_mcb_result_t result)
const char *	mcbTypeToString (e_mcb_type_t type)
int	mcbCompareFunc (void *mcb, void *mcbToCompare)
	mcbCompareFunc compares the start addresses of two mcbs. More...
int	mcbSearchCompFunc (void *mcb, void *blockStartAddress)
	mcbSearchCompFunc searches for the mcb that you want to compare with. More...
void	insertMCBIntoList (cmcb_t *blockToInsert)
	insertMCBIntoList inserts the mcb into the list specified. More...
void	heapTest ()
	heapTest test function to create sample mcbs. More...
void	printMCBFunc (void *cmcb)
	printMCBFunc prints the type, block size, block pointer of the blocks in a given list. More...
void	reclaimFreeMem ()
	reclaimFreeMem groups free blocks together if they are adjacent. More...

Variables
linkedList_t	mcbFreeList
linkedList_t	mcbAllocList
e_mcb_result_t	lastMCBError
node_t	representingNode
e_mcb_type_t	cmcbType
mcbSize_t	mcbBlockSize
const char *	procName
lmcb_t *	associatedLMCB
mcbAddressPtr_t	blockStartAddress
mcbAddressPtr_t	blockStopAddress
e_mcb_type_t	lmcbType

Typedef Documentation

typedef struct s_cmcb cmcb_t

Definition at line 28 of file mcb.h.

typedef void* heapLocationPtr_t

Definition at line 36 of file mcb.h.

typedef struct s_lmcb lmcb_t

Definition at line 30 of file mcb.h.

typedef void* mcbAddressPtr_t

Definition at line 32 of file mcb.h.

typedef size_t mcbSize_t

Definition at line 34 of file mcb.h.

Enumeration Type Documentation

enum e_mcb_result_t

The e_mcb_result_t enum defines the return status of functions working with MCBs.

Enumerator
MCB_SUCCESS
ERROR_BLOCK_NOT_FOUND
ERROR_BLOCK_NOT_ALLOCATED
ERROR_GENERIC
ERROR_NOT_ENOUGH_MEMORY
MCB_ERROR_ACCESS_DENIED

Definition at line 16 of file mcb.h.

             { MCB_SUCCESS, ERROR_BLOCK_NOT_FOUND, ERROR_BLOCK_NOT_ALLOCATED, ERROR_GENERIC, ERROR_NOT_ENOUGH_MEMORY,
                MCB_ERROR_ACCESS_DENIED }

enum e_mcb_type_t

The e_mcb_type_t enum defines the state of the MCBs.

Enumerator
MCB_FREE
MCB_ALLOCATED
MCB_NOT_FREE

Definition at line 23 of file mcb.h.

{ MCB_FREE, MCB_ALLOCATED, MCB_NOT_FREE }

Function Documentation

struct s_cmcb __attribute__

(

(packed)

)

void* allocateMemFromHeap

(

size_t

requestedSize

)

allocateMemFromHeap takes the requested size and finds the first block that fits. Implements first fit. Size_t is unsigned.

Parameters

requestedSize

size in bytes to the allocated from the heap.

Returns

a pointer to the beginning of the block of memory requested.

Definition at line 45 of file mcb.c.

References s_cmcb::associatedLMCB, s_cmcb::blockStartAddress, s_lmcb::blockStopAddress, s_cmcb::cmcbType, currentOperatingProcess, ERROR_BLOCK_NOT_ALLOCATED, ERROR_NOT_ENOUGH_MEMORY, insertMCBIntoList(), lastMCBError, s_lmcb::lmcbType, MCB_ALLOCATED, MCB_FREE, MCB_SUCCESS, s_cmcb::mcbBlockSize, s_lmcb::mcbBlockSize, s_cmcb::procName, removeNode(), and s_cmcb::representingNode.

Referenced by heapTest(), and kmain().

{
    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;

}

int freeHeapMem

(

void *

blockAddress

)

freeHeapMem takes the block address and frees the memory from the CMCB start to the LMCB end location and calls reclaimFreeMem() function.

Parameters

blockAddress

pointer to the memory address to be freed.

Returns

the error code if any exists.

Definition at line 154 of file mcb.c.

References s_cmcb::associatedLMCB, s_cmcb::cmcbType, currentOperatingProcess, ERROR_BLOCK_NOT_FOUND, insertMCBIntoList(), lastMCBError, s_lmcb::lmcbType, MCB_ERROR_ACCESS_DENIED, MCB_FREE, MCB_SUCCESS, printMCBFunc(), s_cmcb::procName, reclaimFreeMem(), removeNode(), s_cmcb::representingNode, and searchList().

Referenced by heapTest(), and kmain().

{
    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;
}

int heapIsEmpty

(

)

heapIsEmpty returns if the heap is empty.

Returns

an integer, if heap is empty -> returns 0, if heap is not empty -> returns 1.

Definition at line 229 of file mcb.c.

References lastMCBError, and MCB_SUCCESS.

{
    lastMCBError=MCB_SUCCESS;
    if(mcbAllocList.head.next == &mcbAllocList.tail) return 0;
    return 1;
}

void heapTest

(

)

heapTest test function to create sample mcbs.

Definition at line 286 of file mcb.c.

References allocateMemFromHeap(), freeHeapMem(), lastMCBError, MCB_SUCCESS, mcbResultToString(), printf, and printList().

Referenced by mcbFunc().

{
    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);
}

void initHeap

(

size_t

initialHeapSize

)

initHeap initializes the system heap by calling kmalloc with a valid byte size. Creates a CMCB at the beginning and an LMCB at the end. Note the total size is the given size + sizeof(CMCB) + sizeof(LMCB).

Parameters

initialHeapSize

the size in bytes of the heap to be created

Definition at line 11 of file mcb.c.

References s_cmcb::associatedLMCB, s_cmcb::blockStartAddress, s_lmcb::blockStopAddress, s_cmcb::cmcbType, heapLoc, initLinkedList(), insertMCBIntoList(), kmalloc(), s_lmcb::lmcbType, MCB_FREE, s_cmcb::mcbBlockSize, s_lmcb::mcbBlockSize, mcbCompareFunc(), mcbSearchCompFunc(), printf, printMCBFunc(), s_cmcb::procName, s_cmcb::representingNode, setInsertComparisonFunction(), setPrintFunction(), and setSearchComparisonFunction().

Referenced by kmain().

{

    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);
}

void insertMCBIntoList

(

cmcb_t *

blockToInsert

)

insertMCBIntoList inserts the mcb into the list specified.

Parameters

blockToInsert

the mcb block to insert into.

Definition at line 271 of file mcb.c.

References s_cmcb::cmcbType, insertNode(), lastMCBError, MCB_ALLOCATED, MCB_FREE, MCB_SUCCESS, and s_cmcb::representingNode.

Referenced by allocateMemFromHeap(), freeHeapMem(), and initHeap().

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

int mcbCompareFunc	(	void *	mcb,
		void *	mcbToCompare
	)

mcbCompareFunc compares the start addresses of two mcbs.

Parameters

mcb	pointer to mcb
mcbToCompare	pointer to mcb to compare with.

Returns

Definition at line 135 of file mcb.c.

References blockStartAddress.

Referenced by initHeap().

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

const char* mcbResultToString

(

e_mcb_result_t

result

)

Definition at line 235 of file mcb.c.

References ERROR_BLOCK_NOT_ALLOCATED, ERROR_BLOCK_NOT_FOUND, ERROR_GENERIC, ERROR_NOT_ENOUGH_MEMORY, MCB_ERROR_ACCESS_DENIED, and MCB_SUCCESS.

Referenced by heapTest().

{
    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";
}

int mcbSearchCompFunc	(	void *	mcb,
		void *	blockStartAddress
	)

mcbSearchCompFunc searches for the mcb that you want to compare with.

Parameters

mcb	pointer to mcb.
blockStartAddress	start address of memory.

Returns

Definition at line 144 of file mcb.c.

Referenced by initHeap().

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

const char* mcbTypeToString

(

e_mcb_type_t

type

)

Definition at line 257 of file mcb.c.

References MCB_ALLOCATED, and MCB_FREE.

Referenced by printMCBFunc().

{
    switch(type)
    {
        case MCB_FREE:
            return "FREE     ";
        case MCB_ALLOCATED:
            return "ALLOCATED";
        default:
            break;
    }
            return "UNKNOWN  ";
}

void printAlloc

(

)

printAlloc prints the allocated memory blocks. Traverses through the allocated mcb list.

Definition at line 123 of file mcb.c.

References printf, and printList().

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

void printFree

(

)

printFree prints the free memory blocks. Traverses through the free mcb list.

Definition at line 129 of file mcb.c.

References printf, and printList().

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

void printMCBFunc

(

void *

cmcb

)

printMCBFunc prints the type, block size, block pointer of the blocks in a given list.

Parameters

cmcb	CMCB to be printed out.

Definition at line 223 of file mcb.c.

References blockStartAddress, cmcbType, mcbBlockSize, mcbTypeToString(), printf, and procName.

Referenced by freeHeapMem(), and initHeap().

{
    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);
}

void reclaimFreeMem

(

)

reclaimFreeMem groups free blocks together if they are adjacent.

Definition at line 184 of file mcb.c.

References s_cmcb::associatedLMCB, s_cmcb::blockStartAddress, s_lmcb::blockStopAddress, s_cmcb::mcbBlockSize, s_lmcb::mcbBlockSize, removeNode(), and s_cmcb::representingNode.

Referenced by freeHeapMem().

{
    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);
            }
        }
    }
}

mcbSize_t sizeOfHeapAllocated

(

)

mcbSize_t sizeOfHeapFree

(

)

Variable Documentation

lmcb_t* associatedLMCB

Definition at line 45 of file mcb.h.

mcbAddressPtr_t blockStartAddress

Definition at line 47 of file mcb.h.

Referenced by mcbCompareFunc(), and printMCBFunc().

mcbAddressPtr_t blockStopAddress

Definition at line 37 of file mcb.h.

e_mcb_type_t cmcbType

Definition at line 39 of file mcb.h.

Referenced by printMCBFunc().

e_mcb_result_t lastMCBError

Definition at line 8 of file mcb.c.

Referenced by allocateMemFromHeap(), freeHeapMem(), heapIsEmpty(), heapTest(), and insertMCBIntoList().

e_mcb_type_t lmcbType

Definition at line 41 of file mcb.h.

linkedList_t mcbAllocList

Definition at line 6 of file mcb.c.

Referenced by mcbFunc().

mcbSize_t mcbBlockSize

Definition at line 41 of file mcb.h.

Referenced by printMCBFunc().

linkedList_t mcbFreeList

Definition at line 5 of file mcb.c.

Referenced by mcbFunc().

const char* procName

Definition at line 43 of file mcb.h.

Referenced by pcbFunc(), and printMCBFunc().

node_t representingNode

Definition at line 37 of file mcb.h.