Hey Guys,

It's been a while since I posted on these forums but I am here hoping I can get some advice. I am trying to create a simple memory allocator for practice and I am having a hard time with the concept and was wondering if anyone had any advice or good resources on how I can learn more.

The goal I have been challenged with is to create a memory manager that will be given a contiguous block of memory. Using this block of memory the allocator will be able to allocate and deallocate from that given block of memory. The allocator is not allowed to dynamically allocate any memory of it's own.

Any advice is appreciated and let me know if you need more information.

Thank you for such a fast reply. I am going to take some time and analyze the example you gave so I can pick it apart and see how much further I can get. Most of my confusion comes from how to mark memory as in use and it's size so that when I go to deallocate I can be sure to deallocate the proper amount of memory.

I also want to be able to use the in use marker search for a contiguous block of memory within the chunk in a scenario where multiple blocks have been given out and some random blocks were freed and I need to find the best match for the size I need to allocate but that is something I will get to when I figure out the above. Baby steps .

This is a really crude example and its entirely unfinished but it's the code I have created to play around in while I figure this out.

class MemoryManager
{
public:
	MemoryManager(void* chunk, size_t size);
	~MemoryManager();

	void* allocate(size_t size);
	void deallocate(void* deleted);

private:
	struct Free
	{
		bool inUse;
		unsigned char size;
		Free* next;
	};
	void* mHead;
	size_t mBytes;
};

MemoryManager::MemoryManager(void* chunk, size_t bytes)
{
	std::cout << "init" << std::endl;
	mHead = chunk;
	mBytes = bytes;

	for (size_t i = 0; i < mBytes; i++)
	{
		char* head = reinterpret_cast<char*>(mHead)+i;
		
		*head = 'a';
	}
}

MemoryManager::~MemoryManager()
{
	std::cout << "uninit" << std::endl;
}

void* MemoryManager::allocate(size_t size)
{	
	if (!mHead && size < mBytes) return NULL;
	
	char* bytes = reinterpret_cast<char*>(mHead);
	void* head = reinterpret_cast<char*>(mHead)+1;
	mHead = reinterpret_cast<char*>(head)+size;
	*bytes = size;

	return head;
}

void MemoryManager::deallocate(void* deleted)
{
	std::cout << "dealloc " << std::endl;
}

This is a really crude example and its entirely unfinished but it's the code I have created to play around in while I figure this out.

With this in mind some comments regarding this early MemoryManager::allocate(size_t):

a) Please stop using the NULL macro. Use nullptr (C++11) instead if supported by your compiler.

b) Your condition guarding the method is wrong. You probably want to break if mHead is nullptr or requested size is greater than the available capacity, so

if (!mHead || size > mBytes) return nullptr;

c) You could avoid many of the nasty castings if mHead would be a char* (but continue reading).

d) The parameter size can be very big, but you store its value in a byte. So you need to break and return nullptr also in case that size is greater than 255 in this case. Otherwise you need to be able to store bigger values.

e) The method does not consider alignment other than 8 bit. This is okay if and only if the clients are guaranteed to use the returned memory pointer only to store byte values. As soon as they want to store 16, 32, 64, ... bit values, things may become inefficient (slow) in best case or terminate the program in worst case.

f) The available capacity mBytes is not decreased on allocation, so one can allocate memory behind the backing chunk.

g) Notice that changing mHead destroys your only one pointer to the very beginning of the backing memory chunk. That makes regular cleaning up impossible.

Thanks for all the feedback guys. I am still fairly new to this so it will take me a little bit to fully digest what you've posted when I have time but I'll definitely be posting back here once I play around a bit more. I did write my current thoughts on what you guys have said so far.

This is a really crude example and its entirely unfinished but it's the code I have created to play around in while I figure this out.

With this in mind some comments regarding this early MemoryManager::allocate(size_t):

a) Please stop using the NULL macro. Use nullptr (C++11) instead if supported by your compiler.

b) Your condition guarding the method is wrong. You probably want to break if mHead is nullptr or requested size is greater than the available capacity, so

if (!mHead || size > mBytes) return nullptr;

c) You could avoid many of the nasty castings if mHead would be a char* (but continue reading).

d) The parameter size can be very big, but you store its value in a byte. So you need to break and return nullptr also in case that size is greater than 255 in this case. Otherwise you need to be able to store bigger values.

e) The method does not consider alignment other than 8 bit. This is okay if and only if the clients are guaranteed to use the returned memory pointer only to store byte values. As soon as they want to store 16, 32, 64, ... bit values, things may become inefficient (slow) in best case or terminate the program in worst case.

f) The available capacity mBytes is not decreased on allocation, so one can allocate memory behind the backing chunk.

g) Notice that changing mHead destroys your only one pointer to the very beginning of the backing memory chunk. That makes regular cleaning up impossible.

Here is some of my feedback on what you've written.

a) Ya, I actually read about nullptr in the C++ Primer. Definitely a big no, no on my part.

b) Oh good catch, I didn't realize I put an && there. I need to create some variables to track that the current location + size < mBytes instead of size < mBytes. I also need a way to look through the rest of the block so I can looked for pieces that might have been freed that I can give out instead of always pulling it from the end.

c) That's a good point. I wasn't sure if it was better to declare it as a void pointer or make it a char pointer for clarity on my intention to anyone else who reads it.

d) I may try to take sizeof(size_t) instead of just incrementing by 1 so I can ensure that I have enough space to store the full size.

e) I would want to be able to allocate complex objects and not just 8 bit values so this is something I will need to keep in mind and research more. I am not sure slow is something I care about in this initial example.

f) I believe what I wrote for b covers this my thoughts on this.

g) I'll have to think about the best way to keep track of the beginning, end, and current location of the memory chunk. The goal is to make sure that this memory manager doesn't dynamically allocate any memory on it's own so I am trying to be conservative.

If I'm understanding what you're asking right you might want to look into something called a power of two allocator. I don't remember how complicated the implementation is but IIRC C implementations used to use this for malloc and its variants back in the day. (and maybe even now for all I know)

That sounds interesting I am going to spend some time looking into this and see if it helps lead me towards the solution.