#include <core/mcb.h>

Include dependency graph for mcb.c:

Functions
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...

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	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...

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...

void	reclaimFreeMem ()
	reclaimFreeMem groups free blocks together if they are adjacent. More...

void	printMCBFunc (void *cmcb)
	printMCBFunc prints the type, block size, block pointer of the blocks in a given 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)

void	insertMCBIntoList (cmcb_t *blockToInsert)
	insertMCBIntoList inserts the mcb into the list specified. More...

void	heapTest ()
	heapTest test function to create sample mcbs. More...

Variables
heapLocationPtr_t	heapLoc =0

linkedList_t	mcbFreeList

linkedList_t	mcbAllocList

e_mcb_result_t	lastMCBError = MCB_SUCCESS

Function Documentation

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

Variable Documentation

heapLocationPtr_t heapLoc =0

Definition at line 3 of file mcb.c.

Referenced by initHeap().

e_mcb_result_t lastMCBError = MCB_SUCCESS

Definition at line 8 of file mcb.c.

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

linkedList_t mcbAllocList

Definition at line 6 of file mcb.c.

Referenced by mcbFunc().

linkedList_t mcbFreeList

Definition at line 5 of file mcb.c.

Referenced by mcbFunc().

Functions

Variables

Function Documentation

Variable Documentation