Memory Manager problem

[claesson92]

Hi, i'm making my first attempt at writing a simple memory manager. I don't follow any guide/tutorial so i might be writing a piece of junk.

memory.h

Code: Select all

#ifndef _MEMORY_H_
#define _MEMORY_H_

#include "_bool.h"
#include "types.h"

#define PAGE_SIZE 4096

struct mem_block
{
	unsigned int* start;
	unsigned int* end;
	size_t size;
	struct mem_block* next;
	struct mem_block* prev;
};

unsigned int* mem_start;
unsigned int* mem_end;
struct mem_block* mem_firstblock;
struct mem_block* mem_lastblock;
struct mem_block* mem_dead_firstblock;
struct mem_block* mem_dead_lastblock;

unsigned char *memcpy(void *dest, void *src, int count);
unsigned char *memset(void *dest, unsigned char val, int count);
unsigned short *memsetw(void *dest, unsigned short val, int count);

void memman_setup(unsigned int startaddr, unsigned int endaddr);
struct mem_block* memman_alloc(size_t size);
void memman_dealloc(struct mem_block* block);

#endif

memory.c

Code: Select all

#include "memory.h"
#include "io.h"

unsigned int* mem_start;
unsigned int* mem_end;
struct mem_block* mem_firstblock = NULL;
struct mem_block* mem_lastblock = NULL;
struct mem_block* mem_dead_firstblock = NULL;
struct mem_block* mem_dead_lastblock = NULL;

unsigned char *memcpy(void *dest, void *src, int count)
{
	char* dest8 = dest;
	char* src8 = src;
	
	while(count--)
	{
		*dest8++ = *src8++;
	}
	
	return dest;
}

unsigned char *memset(void *dest, unsigned char val, int count)
{
	char* dest8 = dest;

	while(count--)
	{
		*dest8++ = val;
	}
	
	return dest;
}

unsigned short *memsetw(void *dest, unsigned short val, int count)
{
	char* dest8 = dest;
	
	while(count--)
	{
		*dest8++ = val;
	}
	
	return dest;
}

void memman_setup(unsigned int startaddr, unsigned int endaddr)
{
	mem_start = (unsigned int*)startaddr;
	mem_end = (unsigned int*)endaddr;
	
	//Setup a dummy block
	mem_firstblock->start = mem_start;
	mem_firstblock->end = mem_start;
	mem_firstblock->size = 0;
	mem_firstblock->next = NULL;
	mem_firstblock->prev = NULL;
	mem_lastblock = mem_firstblock;
	
	panic("%p = %p", mem_lastblock, mem_firstblock);
	
	//Setup a dead dummy block
	mem_dead_firstblock->start = (unsigned int*)0;
	mem_dead_firstblock->end = (unsigned int*)0;
	mem_dead_firstblock->size = 0;
	mem_dead_firstblock->next = NULL;
	mem_dead_firstblock->prev = NULL;
	mem_dead_lastblock = mem_dead_firstblock;
}

struct mem_block* memman_alloc(size_t size)
{
	//Are there any dead block we can use instead?
	/*struct mem_block* this_dead = mem_dead_firstblock->next;
	while(this_dead != NULL)
	{
		//Is the block large enough?
		if(size <= (unsigned int)(this_dead->end - this_dead->start))
		{
			unsigned int dead = size - (this_dead->end - this_dead->start);
			//We can use the dead block
			
			//Resize the block
			this_dead->end = this_dead->start + size;
			this_dead->size = size;
			this_dead->prev = mem_lastblock;
			this_dead->next = NULL;
			this_dead->prev->next = this_dead->next;
			this_dead->next->prev = this_dead->prev;
			mem_lastblock = this_dead;
			
			//If the block was resized, we have another dead one
			struct mem_block* new_dead = NULL;
			new_dead->start = this_dead->end + 1;
			new_dead->end = new_dead->start + dead;
			new_dead->size = dead;
			new_dead->prev = mem_dead_lastblock;
			new_dead->next = NULL;
			mem_dead_lastblock = new_dead;
			
			return this_dead;
		}
	
		this_dead = this_dead->next;
	}*/
	panic("%p", mem_lastblock->end);
	struct mem_block* newblock = NULL;
	newblock->start = mem_lastblock->end + 1;
	newblock->end = newblock->start + size - 1;
	newblock->size = size;
	newblock->next = NULL;
	newblock->prev = mem_lastblock;
	
	mem_lastblock = newblock;
	return newblock;
}

void memman_dealloc(struct mem_block* block)
{
	//Remove the block from the list
	block->next->prev = block->prev;
	block->prev->next = block->next;
	
	//Now we have a dead block.
	mem_dead_lastblock->next = block;
	block->prev = mem_dead_lastblock;
	block->next = NULL;
	mem_dead_lastblock = block;
}

Is this at the right track at all? Should i do it a completely different way?

I have a problem as well. What i do in memman_setup() like setting the mem_firstblock->end is not stored when the function is exited. Shouldn't the values be "permanently" stored as the variable is global?

[gerryg400]

mem_firstblock is a pointer to a structure. You initialise it to NULL, but you never allocate any memory to it. As far as I can see it remains a NULL pointer. Have I missed something?

Elsewhere you have this

Code: Select all

   struct mem_block* newblock = NULL;
   newblock->start = mem_lastblock->end + 1;

Looks like you are dereferencing NULL pointers all over the place.

[claesson92]

mem_firstblock is a pointer to a structure. You initialise it to NULL, but you never allocate any memory to it. As far as I can see it remains a NULL pointer. Have I missed something?

Elsewhere you have this

Code: Select all

   struct mem_block* newblock = NULL;
   newblock->start = mem_lastblock->end + 1;

Looks like you are dereferencing NULL pointers all over the place.

Here is a slightly modified version of memory.c:

Code: Select all

#include "memory.h"
#include "io.h"

unsigned int* mem_start;
unsigned int* mem_end;
struct mem_block* mem_firstblock;
struct mem_block* mem_lastblock;
struct mem_block* mem_dead_firstblock;
struct mem_block* mem_dead_lastblock;

unsigned char *memcpy(void *dest, void *src, int count)
{
	char* dest8 = dest;
	char* src8 = src;
	
	while(count--)
	{
		*dest8++ = *src8++;
	}
	
	return dest;
}

unsigned char *memset(void *dest, unsigned char val, int count)
{
	char* dest8 = dest;

	while(count--)
	{
		*dest8++ = val;
	}
	
	return dest;
}

unsigned short *memsetw(void *dest, unsigned short val, int count)
{
	char* dest8 = dest;
	
	while(count--)
	{
		*dest8++ = val;
	}
	
	return dest;
}

void memman_setup(unsigned int startaddr, unsigned int endaddr)
{
	mem_start = (unsigned int*)startaddr;
	mem_end = (unsigned int*)endaddr;
	
	//Setup a dummy block
	struct mem_block dummy;
	dummy.start = mem_start;
	dummy.end = mem_start;
	dummy.size = 0;
	dummy.next = NULL;
	dummy.prev = NULL;
	mem_firstblock = &dummy;
	mem_lastblock = mem_firstblock;
	
	//Setup a dead dummy block
	struct mem_block dead_dummy;
	dead_dummy.start = (unsigned int*)0;
	dead_dummy.end = (unsigned int*)0;
	dead_dummy.size = 0;
	dead_dummy.next = NULL;
	dead_dummy.prev = NULL;
	mem_dead_firstblock = &dead_dummy;
	mem_dead_lastblock = mem_dead_firstblock;
}

struct mem_block* memman_alloc(size_t size)
{
	//Are there any dead block we can use instead?
	/*struct mem_block* this_dead = mem_dead_firstblock->next;
	while(this_dead != NULL)
	{
		//Is the block large enough?
		if(size <= (unsigned int)(this_dead->end - this_dead->start))
		{
			unsigned int dead = size - (this_dead->end - this_dead->start);
			//We can use the dead block
			
			//Resize the block
			this_dead->end = this_dead->start + size;
			this_dead->size = size;
			this_dead->prev = mem_lastblock;
			this_dead->next = NULL;
			this_dead->prev->next = this_dead->next;
			this_dead->next->prev = this_dead->prev;
			mem_lastblock = this_dead;
			
			//If the block was resized, we have another dead one
			struct mem_block* new_dead = NULL;
			new_dead->start = this_dead->end + 1;
			new_dead->end = new_dead->start + dead;
			new_dead->size = dead;
			new_dead->prev = mem_dead_lastblock;
			new_dead->next = NULL;
			mem_dead_lastblock = new_dead;
			
			return this_dead;
		}
	
		this_dead = this_dead->next;
	}*/
	struct mem_block newblock;
	newblock.start = mem_lastblock->end + 1;
	newblock.end = newblock.start + size - 1;
	newblock.size = size;
	newblock.next = NULL;
	newblock.prev = mem_lastblock;
	
	mem_lastblock = &newblock;
	return mem_lastblock;
}

void memman_dealloc(struct mem_block* block)
{
	//Remove the block from the list
	block->next->prev = block->prev;
	block->prev->next = block->next;
	
	//Now we have a dead block.
	mem_dead_lastblock->next = block;
	block->prev = mem_dead_lastblock;
	block->next = NULL;
	mem_dead_lastblock = block;
}

It still gives me the same problems as earlier.

[JamesM]

Hi,

How much do you actually know about the C language? You're assigning a global pointer to the address of a local variable. It'll go out of scope and get overwritten as soon as the function exits.

This is C 101...

James

[gerryg400]

Code: Select all

   struct mem_block newblock;
   newblock.start = mem_lastblock->end + 1;
   newblock.end = newblock.start + size - 1;
   newblock.size = size;
   newblock.next = NULL;
   newblock.prev = mem_lastblock;
   
   mem_lastblock = &newblock;
   return mem_lastblock;

This doesn't work. You know that local variables are created on the stack ? And you know what happens when the function exits ?

The problem is of course that to implement a memory manager, it's actually very useful to already have a memory manager. This is a very interesting problem that must be solved when designing an O/S.

[qw]

Code: Select all

   struct mem_block newblock;
   newblock.start = mem_lastblock->end + 1;
   newblock.end = newblock.start + size - 1;
   newblock.size = size;
   newblock.next = NULL;
   newblock.prev = mem_lastblock;
   
   mem_lastblock = &newblock;
   return mem_lastblock;

This doesn't work. You know that local variables are created on the stack ? And you know what happens when the function exits ?

As a matter of fact I have seen this mistake quite often. How nice if it would actually work... It would make memory management a lot easier!

[gravaera]

Hi:

Hi, i'm making my first attempt at writing a simple memory manager. I don't follow any guide/tutorial so i might be writing a piece of junk.

That's not a bad thing. In fact I'd say it's a good thing. And would actually encourage you to continue doing that. What you need is a notebook and a large supply of pens/pencils and time to read, research and think things through. Write your ideas into your notebook and refine them. I never used any tutorials or consulted the OSDev.org wiki either.

My biggest problem is that I can't tell whether this is a physical Memory Manager or a Virtual Memory Manager. But I'll assume it's physical. About memory managers in general: Physical memory managers are generally written using data structures that do not dynamically re-size or require dynamic memory. The data structures are spawned once and then they remain the same size pretty much throughout life. So whether you use a stack, or a bitmap, your PMM metadata will be statically sized.

You want to keep information on which frames in RAM are unused. To an extent you needn't care about which ones are used until much later on, for certain operations like frame-reclaim, and hotplug memory (process migration), etc, etc. So for now, a bitmap will more than suffice. Take into consideration DMA/constrained pmem allocation requirements. If you intend to write a portable kernel, think a bit more deeply than "one bitmap for 0-16MB, and another for the rest of RAM".

Also, depending on how scrupulous you are about memory usage, you may decide that you want to make sure that when you spawn the PMM metadata, it is not beyond the needed size to cover the actual physical memory on the machine. That is, you could decide to spawn a bitmap to cover all 4GB of possible RAM for all situations, then mask off all bits beyond the actual memory size. Or you could decide to have your Virtual (and a stub physical) Memory Manager up and working before you have your "real" Physical Memory Manager working, so that you can dynamically allocate the PMM metadata at runtime, then discard the "stub" PMM metadata and "switch over" to the "real" PMM. However you solve this circular dependency (dynamically allocate the PMM when the PMM doesn't exist) is up to you.

As a rule, PMM is "one set of metadata for the whole machine". Virtual Memory Management is "one set of metadata per process". When designing your VMM, you may decide to just spawn a new bitmap for each process, of a fixed size covering 4GB. That's a total of 128KB per process right off the bat, never going away. Or you could choose a linked list/dynamically resizing approach, in which case again, you'll encounter circular dependencies. All up to you. The main idea while designing a Memory Management subsystem is: choose the fastest algorithm, while using the smallest amount of space on metadata.

Apart from that, your code is your code, and it's kind of difficult to read a wall of code, so...

EDIT: Ah, I see that gerryg400 already mentioned the thing about optimally having an MM working before you get your MM working

--Good luck
gravaera