ELF Relocation!

[Brynet-Inc]

No offence pcmattman, but your CVS & SVN repository is incredibly messy lol..

You have like.. 3/4 different "branches" going on in random locations..

I think you should post a map!

[pcmattman]

I think it's time I removed SVN

Yes, it is a total mess, and I really have to fix that sometime soon...

Although, I do like the map idea

[Brynet-Inc]

Remove SVN?

I prefer it over CVS myself.. but whatever you think is best.

[pcmattman]

I had CVS first

[Alboin]

I had CVS first

Git, perhaps?

[Kevin McGuire]

What do you mean by physical memory manager? Do you mean the page allocator or actual paging?

The page allocator; uses the GRUB memory map (or a memory map) and hands out free pages when needed, or turns used pages back into free ones for usage later.

[pcmattman]

Once I have a page allocator, the actual paging stuff should be simple... If you're willing to do something like that (don't go to much effort) that's fine with me

[Kevin McGuire]

Alright. I will make a very simplistic but flexible one tomorrow; if the ever ticking clock is on my side.

[Kevin McGuire]

I tried to keep it as simple as possible, but unfortunately it is not a one liner for coding. It is however quite flexible and helpful with diagnostics through the usage of kprintf when enabled. You can enable the messages inside of syscore/pm.h. I also included a simple but small test to try to ensure that it is working correctly to a limited extent.

You will notice I make a call to pm_set which allows the range of memory occupied by the kernel to be removed. Luckily, you also include the stack in this range so it makes it easier to implement. The next is a call to a specialized function with the arguments of the GRUB memory map. During initialization information from the calls to pm_set are referenced so it is important to perform that before calling the initialize with GRUB memory map function. Afterwards a call is made to pm_set_flush which actually enacts the previous calls.

After that you can use the pmm_alloc and pmm_free functions as you like.

Here is the difference from existing source files:

Code: Select all

Index: linker.ld
===================================================================
--- linker.ld	(revision 5)
+++ linker.ld	(working copy)
@@ -3,29 +3,29 @@
 SECTIONS 
 {
 	. = 0x00100000;
+	__start = .; 
 	.text :
 	{ 
 		*(.text)
 		*(.text.*)
Index: syscore/mem.cc
===================================================================
--- syscore/mem.cc	(revision 5)
+++ syscore/mem.cc	(working copy)
@@ -12,6 +12,7 @@
 #include <system.h>
 #include <multiboot.h>
 #include <stdio.h>
+#include <pm.h> 				// -- kmcguire 6/10/2007
 
 // memset, sets a range of memory
 void memset( void* ptr, unsigned char dat, int len )
@@ -84,12 +85,16 @@
 	// is there a heap?
 	if( kheap == (MemBlock*) NULL )
 	{
-		// set it to the end of the image
-		kheap = mblk = (MemBlock*) &end;
-		
+		// -- kmcguire 6/10/2007
+		// --- allocate space from the physical page manager (pm.cc/pm.h) 
+		// --- 10 pages on the IA32 right now is 10KB of memory.
+		// --- old: set it to the end of the image
+		// --- old: kheap = mblk = (MemBlock*) &end;
+		kheap = mblk = (MemBlock*)pm_alloc(10);
 		// set it up properly
 		mblk->used = 0;
-		mblk->size = ( ( MultiBootHeader->mem_upper + MultiBootHeader->mem_lower ) * 1024 ) - sizeof( MemBlock ) - (uint_t) &end; // we allocate within the full memory available
+		mblk->size = 10 * 4096;
+		// --- old: mblk->size = ( ( MultiBootHeader->mem_upper + MultiBootHeader->mem_lower ) * 1024 ) - sizeof( MemBlock ) - (uint_t) &end; // we allocate within the full memory available
 		mblk->next = (MemBlock*) NULL;
 	}
 	
Index: kernel.cc
===================================================================
--- kernel.cc	(revision 5)
+++ kernel.cc	(working copy)
@@ -25,7 +25,38 @@
 #include <paging.h>
 #include <stddef.h>
 #include <io.h>
+#include <pm.h>				// -- kmcguire 6/10/2007
  
@@ -186,14 +217,61 @@
 // global multiboot info pointer
 multiboot_info_t* MultiBootHeader;
 
+extern unsigned char __end;
+extern unsigned char __start;
 // kernel entry point
 int main( multiboot_info_t* mb, unsigned int magic_number )
 {	
 	// turn on debugging
 	cons.ToggleDebugMode();
 	
 	// clear the screen
 	cons.ClearScreen();
+
+	// -- kmcguire 6/10/2007
+	// --- tell (pm.cc/pm.h) ahead of time where regions of memory are that WE are using! (including the kernel)
+	pm_set((unsigned long)&__start, ((unsigned long)&__end - (unsigned long)&__start) >> 12 + 1, PM_VALID | PM_USED);
+	// --- initialize the physical page manager with the GRUB memory map (pm.cc/pm.h) 
+	pm_init_with_grub_mmap(mb->mmap_addr, mb->mmap_length);
+	// --- actually flush our information for the pm_set(...) calls.
+	pm_set_flush();
+
+	/// ---------------------- remove this -------------------
+	kprintf("TESTING PHYSICAL PAGE ALLOCATOR\n");
+	kprintf("---testing single allocate and free...");
+	for(unsigned int x = 0, y; x < 10; ++x)
+	{
+		y = pm_alloc();
+		pm_free(y);
+		if(pm_alloc() != y)
+		{
+			kprintf("test failed, allocated memory not returned.\n");
+			for(;;);
+		}
+		pm_free(y);
+	}
+	kprintf("passed!\n");
+	kprintf("---testing staggered range allocate and free...");
+	unsigned int list[20];
+	for(unsigned int x = 0; x < 20; ++x)
+	{
+		list[x] = pm_alloc(15);
+	}
+	for(unsigned int x = 0; x < 10; ++x)
+	{
+		pm_free(list[x*2], 15);
+	}
+	for(unsigned int x = 0; x < 10; ++x)
+	{
+		if(pm_alloc(15) != list[x*2])
+		{
+			kprintf("test failed, allocated memory not returned.\n");
+			for(;;);
+		}
+	}
+	kprintf("passed!\n");
+	/// --------------------------------------------------------
+	for(;;);
 	
 	// kill interrupts
 	__asm__ __volatile__ ( "cli" );

Here are the two source files for the physical page allocator:
syscore/pm.h

Code: Select all

#ifndef PM_H
#define PM_H
#define PM_FLAG_MASK 0xFFF						/// allows extra information to be tagged to entires that does not affect us.
#define PM_VALID 0x001							/// if page exists in system; the state might be otherwise.
#define PM_USED 0x002							/// the state of this page is used!

#define DEBUG_INFO
#define DEBUG_WARN
#define DEBUG_ERROR

/// allocate specified number of pages starting at 'from' and ending at 'to', and add tag to pages on success.
unsigned long pm_alloc(unsigned long from, unsigned long to, unsigned long count, unsigned long tag);
/// allocate specified number of pages starting at 'from' and ending at 'to'.
unsigned long pm_alloc(unsigned long from, unsigned long to, unsigned long count);
/// allocate specified number of pages.
unsigned long pm_alloc(unsigned long count);
/// allocate one page
unsigned long pm_alloc();
/// free specified number of contigious pages starting at page.
int pm_free(unsigned long page, unsigned long count);
/// free one page.
int pm_free(unsigned long page);

/// @internal control
void pm_set(unsigned long page, unsigned long count, unsigned long code);
void pm_set_flush();

/// @common initialization
void pm_init(unsigned long page, unsigned long count);
/// @specialized initialization
struct pm_tmbmm{
	unsigned long	size;
	unsigned long	base_low;
	unsigned long	base_high;
	unsigned long	size_low;
	unsigned long	size_high;
	unsigned long	type;
};
int pm_init_with_grub_mmap(unsigned long mmap_addr, unsigned long mmap_length);
#endif

syscore/pm.cc

Code: Select all

#include "pm.h"
#include "stdio.h"

unsigned long *pm_dir = 0;
unsigned long ____pm_slack = 0;

#ifdef DEBUG_INFO
#define KDBGINFO kprintf("%s:%s:%u:", __FILE__, __FUNCTION__, __LINE__); kprintf
#else
#define KDBGINFO //
#endif
#ifdef DEBUG_WARN
#define KDBGWARN kprintf("%s:%s:%u:", __FILE__, __FUNCTION__, __LINE__); kprintf
#else
#define KDBGWARN //
#endif
#ifdef DEBUG_ERROR
#define KDBGERROR kprintf("%s:%s:%u:", __FILE__, __FUNCTION__, __LINE__); kprintf
#else
#define KDBGERROR //
#endif


#define PM_TES_MAX 4
struct pm_tes
{
	unsigned long page;
	unsigned long count;
	unsigned long code;
};

pm_tes ____pm_tes[PM_TES_MAX];
unsigned char ____pm_tes_cnt = 0;

/// specialized initialization function
int pm_init_with_grub_mmap(unsigned long mmap_addr, unsigned long mmap_length)
{
	KDBGINFO("Called; mmap_addr:%x mmap_length:%x\n", mmap_addr, mmap_length);
	if((mmap_addr | mmap_length) == 0)
	{
		KDBGERROR("No memory map found.\n");
		// problems!
		return -1;
	}
	pm_tmbmm *mm = (pm_tmbmm*)mmap_addr;
	for(; ((unsigned long)mm) < (mmap_addr + mmap_length); mm = (pm_tmbmm*)((unsigned int)mm + mm->size + 4))
	{
		KDBGINFO("base:%x size:%x type:%x\n", mm->base_low, mm->size_low, mm->type);
		if(mm->type == 0x1){
			// hand range to pm_init function. (we should always get whole pages; if not oh well..)
			if(mm->size_low > 4095)
			{
				pm_init(mm->base_low & 0xFFFFF000, mm->size_low >> 12);
			}else{
				KDBGWARN("memory region size below required 4096 byte; memory not accounted.\n");
			}
		}
	}
	KDBGINFO("initialization complete.\n");
	return 1;
}

/// build dynamic tree to track 4GB of memory.
void pm_init(unsigned long page, unsigned long count)
{
	unsigned long *tbl;
	if(count == 1)
	{
		KDBGWARN("mem region ignored because of size.\n");
		return;
	}
	if(page == 0)
	{
		++page;
		--count;
	}
	if(pm_dir == 0)
	{
		pm_dir = (unsigned long*)page;
		for(unsigned int x = 0; x < 1024; ++x)
		{
			pm_dir[x] = 0;
		}
		--page;
		--count;
	}
	for(unsigned int x = 0; x < count; ++x)
	{
		for(unsigned int y = 0; y < ____pm_tes_cnt; ++y)
		{
			if(((page + (x * 4096)) >= ____pm_tes[y].page) && ((page + (x * 4096)) < (____pm_tes[y].page + (____pm_tes[y].count * 4096))))
			{
				// page is protected by ____pm_tes at this moment..
				continue;
			}
		}
		if(!____pm_slack)
		{
			____pm_slack = page + (x * 4096);
		}else{
			if(!pm_dir[(page + (x * 4096))>>22])
			{
				pm_dir[(page + (x * 4096))>>22] = ____pm_slack;
				tbl = (unsigned long*)____pm_slack;
				for(unsigned int y = 0; y < 1024; ++y)
				{
					tbl[y] = 0;
				}
			}else{
				tbl = (unsigned long*)(pm_dir[(page + (x * 4096))>>22] & 0xFFFFF000);
			}
			tbl[(page + (x * 4096))<<10>>10>>12] = PM_VALID;
		}
	}
	return;
}

int pm_free(unsigned long page)
{
	unsigned long *tbl;
	if(!pm_dir[page>>22])
	{
		KDBGINFO("page never existed: %x\n", page);
		// this page must have never been in this system to begin with, a bug causing this bad call?
		return -1;
	}
	tbl = (unsigned long*)(pm_dir[page>>22] & 0xFFFFF000);
	if(!tbl[page<<10>>10>>12])
	{
		KDBGINFO("page never existed: %x\n", page);
		// this page must have never been in this system to begin with, a bug causing this bad call?
		return -1;
	}
	// clear all bits, but the valid one.
	tbl[page<<10>>10>>12] = PM_VALID;
	return 1;
}
int pm_free(unsigned long page, unsigned long count)
{
	int result;
	for(unsigned int x = 0; x < count; ++x)
	{
		result |= pm_free(page + (x * 4096));
	}
	return result;
}
void pm_set_flush()
{
	if(!pm_dir)
	{
		KDBGWARN("can not flush with no accounted memory.\n");
		return;
	}
	for(unsigned int x = 0; x < ____pm_tes_cnt; ++x)
	{
		KDBGINFO("flushed cmd in tes (%x,%x,%x)\n", ____pm_tes[x].page, ____pm_tes[x].count, ____pm_tes[x].code);
		pm_set(____pm_tes[x].page, ____pm_tes[x].count, ____pm_tes[x].code);
	}
	____pm_tes_cnt = 0;
}
void pm_set(unsigned long page, unsigned long count, unsigned long code)
{
	unsigned long *tbl;
	if(!pm_dir)
	{
		KDBGINFO("saved cmd in tes (%x,%x,%x)\n", page, count, code);
		// save command for during initialization and after.
		____pm_tes[____pm_tes_cnt].page = page;
		____pm_tes[____pm_tes_cnt].count = count;
		____pm_tes[____pm_tes_cnt].code = code;
		++____pm_tes_cnt;
		if(____pm_tes_cnt > PM_TES_MAX)
		{
			// display error, and halt machine hopefully! (should happen in early boot stages)
			KDBGERROR("____pm_tes_cnt exceeded PE_TES_MAX\n");
			for(;;);
		}
		return;
	}
	for(unsigned long x = 0; x < count; ++x)
	{
		if(!pm_dir[page>>22])
		{
			pm_dir[page>>22] = pm_alloc(1);
			if(pm_dir[page>>22] == 0)
			{
				KDBGWARN("____pm_tes cmd failed; no memory.\n");
				continue;
			}
			tbl = (unsigned long*)(pm_dir[page>>22] & 0xFFFFF000);
			for(unsigned int y = 0; y < 1024; ++y)
			{
				tbl[y] = 0;	
			}
		}else{
			tbl = (unsigned long*)(pm_dir[page>>22] & 0xFFFFF000);
		}
		tbl[(page + (x * 4096))<<10>>10>>12] = code;
	}
	return;
}
unsigned long pm_alloc(unsigned long from, unsigned long to, unsigned long count, unsigned long tag)
{
	unsigned long origin;
	unsigned long *tbl;
	unsigned long found = 0;
	to += 4096;
	origin = from;
	// keep bugs and bad calls from screwing us up..hopefully.
	tag = tag & (~PM_FLAG_MASK);
	from = from & 0xFFFFF000;
	to = to & 0xFFFFF000;
	// search for free pages.
	for(unsigned long page = from; page <= to; page += 4096)
	{
		if(pm_dir[page>>22])
		{
			tbl = (unsigned long*)(pm_dir[page>>22] & 0xFFFFF000);
			//kprintf("[%x:%x]", page, tbl[page<<10>>10>>12]);
			if(
				(tbl[page<<10>>10>>12] & PM_VALID) &&
				!(tbl[page<<10>>10>>12] & PM_USED)
				)
			{
				++found;
				if(found >= count)
				{
					// allocate pages, now.
					for(page = origin; page < (origin + (4096 * count)); page += 4096)
					{
						tbl = (unsigned long*)(pm_dir[page>>22] & 0xFFFFF000);
						tbl[page<<10>>10>>12] = PM_VALID | PM_USED | tag;
					}
					return origin;
				}
			}else{
				found = 0;
				// if next page is valid and free then we already have it's address instead of adding
				// a additional if (above) to check the value of origin.
				origin = page + 0x1000;
			}
		}else{
			// skip the 4mb table (it does not exist - not worth continually checking again and again)
			page = page + (4096 * 1024);
		}
	}
	// we just never allocate page address zero; use it for something else such as: gdt, idt ...
	return 0;
}
unsigned long pm_alloc(unsigned long from, unsigned long to, unsigned long count)
{
	// no tag.
	return pm_alloc(from, to, count, 0);
}
unsigned long pm_alloc(unsigned long count)
{
	// no range specification.
	return pm_alloc(0x1000, 0xEFFFF000, count);
}
unsigned long pm_alloc()
{
	// no count specified.
	return pm_alloc(1);
}

[pcmattman]

Wow, thanks so much!

I'll be able to integrate this seamlessly, you're a legend

I'll have to put your name into some list when I get around to the next release.

[Kevin McGuire]

Hey. How about you make me a member of your project so I can help out and play with the SVN some? We can call it even.

[pcmattman]

What's your SourceForge username?

If you do work in SVN, make sure you work in a branch so that your work isn't lost when I commit new changes

[Kevin McGuire]

That will work. I just logged in my account with the user name kmcguire3413.

[pcmattman]

Done...

Now I have to figure out why on earth I can't patch this stuff in via Cygwin ("can't find patch")... Even though I have patch installed.

[Kevin McGuire]

If you update the SVN I can commit back to it just the changed files. Then you can revert if problems come up that are not trivial?
svn help revert

Or, applying the changes by hand is not too bad. Only existing files I have modified are link.ld, mem.cc, kernel.cc.

So after you commit and I commit, to revert or restore before my commit:
svn revert link.ld
svn revert mem.cc
svn revert kernel.cc