Memory Manager -----------------------------------------------------------------
ID: 3674227 • Letter: M
Question
Memory Manager
------------------------------------------------------------------------------
Your assignment is to create a Memory Manager which will allow the user to allocate and release memory. Your program also needs to keep track of how much memory is available, how much has been used, where the next available memory area is, etc.
Solution Requirements
---------------------
Your solution should compile and be capable of managing a variable number of
allocations and deallocations, with no requirements for deallocations to be in
the same order as the allocations. However, a pointer will never be deallocated
more than once.
You should provide implementations of the five functions within
MemoryManager.cpp.
!! DO NOT MODIFY MemoryManager.h !!
You can define additional functions within MemoryManager.cpp as necessary,
but do not change the MemoryManager interface.
Please do not include any other header files. If you need to do this for
development, please remove it before submission. For example if you include
<stdio.h> for printf, please remove the printf (or comment them out) as well
as the #include.
Memory Restrictions
-------------------
- No memory dynamically allocated during program execution (new, malloc, etc.).
- All data must fit inside MM_pool[]
- No other static or global variables
Common Cases
------------
On average while your system is running, there will be allocations that range
in size from 2 bytes to 16k. You may expect 10% of the allocations will be
8 bytes or smaller. Note that despite the average case you may be asked to
satisfy any sized allocation
Error Handling
--------------
If you are unable to satisfy a request due to lack of memory your code should
call the provided failure function (which will not return):
namespace MemoryManager
{
void onOutOfMemory();
}
If the caller makes any illegal request your code should call the provided
failure function (which will not return):
namespace MemoryManager
{
void onIllegalOperation(const char* fmt = 0, ... );
}
Compilation and Sample Output
-----------------------------
Please compile your implementation of MemoryManger.cpp against the provided
MemoryManager.h and main.cpp.
The output of the provided main() should be close to:
Free memory = 65530
Free memory = 65259
Scope of Problem
----------------
This test is intended to take a reasonable amount of time (3-4 hours), it will
be run against a test harness that is more extensive than the main loop provided.
Should you find that you have more time, consider testing the different edge
cases that the problem description leads you to anticipate.
Additional Documentation Requirements
-------------------------------------
Please include a description of your implementation. You should outline areas
in which you feel your solution could be improved given additional time and/or
resources. If you were unable to complete a valid solution in a reasonable
amount of time (3-4 hours), list the areas you felt gave you the most trouble
and some thoughts on what you've learned that you would apply to the problem
on a second pass. Be sure to include citations for any reference materials
(including any discussions with other people regarding the problem) you used
to assist you.
Notes
-----
People talk, we know you don't exist in a vacuum and friends and
colleagues can often be an invaluable resource when facing challenging
problems. However, be honest with yourself, if you feel you couldn't have
come close to solving this problem without someone else's help, would you be
happy working in an environment where you'd be called on to solve even more
complex problems on a regular basis?
// MemoryManager.h ----------------------
#pragma once
#ifndef __MEMORY_MANAGER_H__
#define __MEMORY_MANAGER_H__
// IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
//
// DO NOT CHANGE THIS HEADER FILE
//
// IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
namespace MemoryManager
{
//---
//--- CORE Functions, these will need to be completed by the applicant
//---
// Initialize any data needed to manage the memory pool
void initializeMemoryManager(void);
// return a pointer inside the memory pool
// If no chunk can accommodate aSize call OnAllocFail()
void* allocate(int aSize);
// Free up a chunk previously allocated
void deallocate(void* aPointer);
//---
//--- support routines
//---
// Will scan the memory pool and return the total free space remaining
int freeRemaining(void);
// Will scan the memory pool and return the largest free space remaining
int largestFree(void);
// will scan the memory pool and return the smallest free space remaining
int smallestFree(void);
//---
//--- error conditions. None of these functions will return
//--- These routines do not need to be implemented by the candidate
//---
// Call if no space is left for the allocation request
void onOutOfMemory(void);
// If the caller makes any illegal request your code should call this
// provided failure function (which will not return):
void onIllegalOperation(const char* fmt,...);
// eg:
// int errorCode;
// ...
// onIllegalOperation("Error in createQueue: %d", errorCode);
};
#endif // __MEMORY_MANAGER_H__
// MemoryManager.cpp ----------------------
#include "MemoryManager.h"
namespace MemoryManager
{
// IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
//
// This is the only static memory that you may use, no other global variables may be
// created, if you need to save data make it fit in MM_pool
//
// IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
const int MM_POOL_SIZE = 65536;
char MM_pool[MM_POOL_SIZE];
// Initialize set up any data needed to manage the memory pool
void initializeMemoryManager(void)
{
// TODO : IMPLEMENT ME
}
// return a pointer inside the memory pool
// If no chunk can accommodate aSize call onOutOfMemory()
void* allocate(int aSize)
{
// TODO: IMPLEMENT
return ((void*) 0);
}
// Free up a chunk previously allocated
void deallocate(void* aPointer)
{
// TODO: IMPLEMENT
}
//---
//--- support routines
//---
// Will scan the memory pool and return the total free space remaining
int freeRemaining(void)
{
// TODO: IMPLEMENT
return 0;
}
// Will scan the memory pool and return the largest free space remaining
int largestFree(void)
{
// TODO: IMPLEMENT
return 0;
}
// will scan the memory pool and return the smallest free space remaining
int smallestFree(void)
{
// TODO: IMPLEMENT
return 0;
}
}
// Main.CPP ----------------------
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <iostream>
#include "MemoryManager.h"
int main(void)
{
using namespace MemoryManager;
initializeMemoryManager();
long* int_pointer;
char* string_pointer;
std::cout << "Free memory = " << freeRemaining() << std::endl;
int_pointer = (long *) allocate(sizeof(long));
string_pointer = (char*) allocate(255);
*int_pointer = 0xDEADBEEF;
strcpy(string_pointer,"It was the best of times, it was the worst of times");
std::cout << "Free memory = " << freeRemaining() << std::endl;
deallocate(int_pointer);
deallocate(string_pointer);
}
namespace MemoryManager
{
void onOutOfMemory(void)
{
std::cerr << "Memory pool out of memory" << std::endl;
exit( 1 );
}
// call for any other error condition, providing meaningful error messages are appreciated
void onIllegalOperation(const char* fmt,...)
{
if ( fmt == NULL )
{
std::cerr << "Unknown illegal operation" << std::endl;
exit( 1 );
}
else
{
char buf[8192];
va_list argptr;
va_start (argptr,fmt);
vsprintf (buf,fmt,argptr);
va_end (argptr);
std::cerr << "Illegal operation: "" << buf << """ << std::endl;
exit( 1 );
}
}
}
Explanation / Answer
main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <iostream>
#include "MemoryManager.h"
int main(void)
{
using namespace MemoryManager;
initializeMemoryManager();
long* int_pointer;
char* string_pointer;
std::cout << "Free memory = " << freeRemaining() << std::endl;
std::cout << "L Free: " << largestFree();
int_pointer = (long *) allocate(sizeof(long));
string_pointer = (char*) allocate(255);
*int_pointer = 0xDEADBEEF;
strcpy(string_pointer,"It was the best of times, it was the worst of times");
std::cout << "Free memory = " << freeRemaining() << std::endl;
std::cout << "L Free: " << largestFree();
deallocate(int_pointer);
deallocate(string_pointer);
std::cout << "Free Memory = " << freeRemaining() << std::endl;
int i;
std::cin >> i;
}
namespace MemoryManager
{
void onOutOfMemory(void)
{
std::cerr << "Memory pool out of memory" << std::endl;
exit( 1 );
}
// Call if a pointer over run condition is detected
void onOverrunDetected(void)
{
std::cerr << "Pointer overrun detected" << std::endl;
exit( 1 );
}
// call for any other error condition, providing meaningful error messages are appreciated
void onIllegalOperation(const char* fmt,...)
{
if ( fmt == NULL )
{
std::cerr << "Unknown illegal operation" << std::endl;
exit( 1 );
}
else
{
char buf[8192];
va_list argptr;
va_start (argptr,fmt);
vsprintf (buf,fmt,argptr);
va_end (argptr);
std::cerr << "Illegal operation: "" << buf << """ << std::endl;
exit( 1 );
}
}
}
MemoryManager.cpp
#include "MemoryManager.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
namespace MemoryManager {
const int MM_POOL_SIZE = 65536;
char MM_pool[MM_POOL_SIZE];
using namespace std;
void initializeMemoryManager(void) {
char* temp = MM_pool;
temp = (char*) malloc(MM_POOL_SIZE * sizeof(char));
int* t = (int*) MM_pool;
*t = -65531;
}
// return a pointer inside the memory pool
// If no chunk can accommodate aSize call onOutOfMemory()
void* allocate(int aSize) {
int MM_Index = 0;
//convert memory to int pointer to store integers
int* int_pointer = (int*) MM_pool;
//get the chunk size at that index
int chunkSize = int_pointer[MM_Index];
char* returnPointer;
//Initialize the pointer to return
returnPointer = &MM_pool[MM_Index];
//while it is in the memory pool
while (MM_Index < MM_POOL_SIZE) {
/*
* if chunk size is -ve, it is free
*/
if (chunkSize < 0) {
//get the free size +ve
chunkSize = -chunkSize;
//if we can accomodate the input
if ((chunkSize - 4) >= aSize) {
//assign chunk size
int_pointer = (int*) &MM_pool[MM_Index];
//assign chunk size
*int_pointer = aSize;
//go to the chuck
MM_Index = MM_Index + 4;
//return address
returnPointer = &MM_pool[MM_Index];
//update next chunk which is unoccupied
MM_Index = MM_Index + aSize;
int_pointer = (int*) &MM_pool[MM_Index];
*int_pointer = aSize - chunkSize;
return (void*) returnPointer;
} else if (chunkSize == aSize) {
//if chunk size perfectly fits in no need to update next chunk size
int_pointer = (int*) &MM_pool[MM_Index];
//update the size of chunk in memory loop
*int_pointer = aSize;
MM_Index = MM_Index + 4;
returnPointer = &MM_pool[MM_Index + 4];
return (void*) returnPointer;
} else {
//if chuck size is smaller, go to next chunk
MM_Index = MM_Index + 4;
MM_Index = MM_Index + chunkSize;
}
} else {
//if filled memory, go to next chunk
MM_Index = MM_Index + 4;
MM_Index = MM_Index + chunkSize;
}
//recalculate the values of next chunk
int_pointer = (int*) &MM_pool[MM_Index];
chunkSize = *int_pointer;
}
//should not come here
cout << "outof memory " << endl;
//return garbage
return (void*) returnPointer;
}
// Free up a chunk previously allocated
void deallocate(void* aPointer) {
int MM_index = 0;
int* chunk_pointer = (int*) MM_pool;
int chuck_size = *chunk_pointer;
int* to_deallocate = (int*) aPointer;
int* previous_chuck=0;
while (MM_index < MM_POOL_SIZE) {
//if chuck is allocated
if (chuck_size > 0) {
//the chuck
chunk_pointer = (int*) &MM_pool[MM_index + 4];
//if they are same
if (to_deallocate == chunk_pointer) {
chunk_pointer = (int*) &MM_pool[MM_index];
//make it free
*chunk_pointer = -(*chunk_pointer);
//free the pointer
free(aPointer);
//if next and/or previous chunk is free (recalculate size)
MM_index = MM_index + 4;
MM_index = MM_index + chuck_size;
//next chuck
int* next_chuck = (int *) &MM_pool[MM_index];
if (MM_index < MM_POOL_SIZE && *next_chuck < 0) {
//update chuck size
*chunk_pointer = *chunk_pointer + *next_chuck;
}
//if previous chuck is available
if(previous_chuck){
if(*previous_chuck<0){
//update the chuck size
*previous_chuck=*previous_chuck+*chunk_pointer;
}
}
return;
} else {
//if it is not the chunk to deallocate,go to next chunk
MM_index = MM_index + 4;
MM_index = MM_index + chuck_size;
//update the values
previous_chuck=chunk_pointer;
chunk_pointer = (int*) &MM_pool[MM_index];
chuck_size = *chunk_pointer;
}
} else {
//if the chuck is free, go to the next chunk
chuck_size = -chuck_size;
MM_index = MM_index + 4;
MM_index = MM_index + chuck_size;
//update the values
previous_chuck=chunk_pointer;
chunk_pointer = (int*) &MM_pool[MM_index];
chuck_size = *chunk_pointer;
}
}
//control should never come to this point
cout << "should not come here" << endl;
}
// Will scan the memory pool and return the total free space remaining
int freeRemaining(void) {
//initialize the variables
int free_memory = 0;
int MM_index= 0;
//chunk pointer
int* chunk = (int*) MM_pool;
//initial chunk size
int chunk_size = *chunk;
while (MM_index < MM_POOL_SIZE) {
//if the chunk is deallocated
if (chunk_size < 0) {
chunk_size = -chunk_size;
//update the free memory size
free_memory = free_memory + chunk_size;
}
//go to next chunk
MM_index = MM_index + 4;
MM_index = MM_index + chunk_size;
//update the pointer to next chunk and its size
chunk = (int*) &MM_pool[MM_index];
chunk_size = *chunk;
}
return free_memory;
}
// Will scan the memory pool and return the largest free space remaining
int largestFree(void) {
//index
int MM_index = 0;
//1st chunk pointer
int* chunk = (int*) MM_pool;
//initial chunk size
int chunk_size = *chunk;
//largest chunk free , let it be 0
int largest_free = 0;
while (MM_index < MM_POOL_SIZE) {
//if chunk is free
if (chunk_size < 0) {
chunk_size = -chunk_size;
//if the size is greater than the largest chunk size so far
if (largest_free < chunk_size) {
//update it
largest_free = chunk_size;
}
}
//go to next chunk
MM_index = MM_index + 4;
MM_index = MM_index + chunk_size;
//update the pointer to the next chunk
chunk = (int*) &MM_pool[MM_index];
chunk_size = *chunk;
}
return largest_free;
}
// will scan the memory pool and return the smallest free space remaining
int smallestFree(void) {
//index to memory pool
int MM_index = 0;
//first chunk
int* chunk = (int*) MM_pool;
//initial chunk size
int chunk_size = *chunk;
//let smallest be whole chunk
int smallest_free = 65536;
while (MM_index < MM_POOL_SIZE) {
//if chunk is available
if (chunk_size < 0) {
chunk_size = -chunk_size;
//if smallest chunk is greater than the current chunk
if (smallest_free > chunk_size) {
//update it
smallest_free = chunk_size;
}
}
//next chunk
MM_index = MM_index + 4;
MM_index = MM_index + chunk_size;
//update pointer to the next chunk
chunk = (int*) &MM_pool[MM_index];
chunk_size = *chunk;
}
return smallest_free;
}
}
MemoryManager.h
#pragma once
#ifndef __MEMORY_MANAGER_H__
#define __MEMORY_MANAGER_H__
namespace MemoryManager
{
// Initialize any data needed to manage the memory pool
void initializeMemoryManager(void);
// return a pointer inside the memory pool
// If no chunk can accommodate aSize call OnAllocFail()
void* allocate(int aSize);
// Free up a chunk previously allocated
void deallocate(void* aPointer);
// Will scan the memory pool and return the total free space remaining
int freeRemaining(void);
// Will scan the memory pool and return the largest free space remaining
int largestFree(void);
// will scan the memory pool and return the smallest free space remaining
int smallestFree(void);
// Call if no space is left for the allocation request
void onOutOfMemory(void);
// Call if a pointer over run condition is detected
void onOverrunDetected(void);
// If the caller makes any illegal request your code should call this
// provided failure function (which will not return):
void onIllegalOperation(const char* fmt,...);
};
#endif // __MEMORY_MANAGER_H__