OSDev.org

Posted: **Sat Jan 03, 2009 5:38 pm**

I've implemented malloc() and free() but surprisingly free() isn't working properly.
Basically, for memory allocating, I save the information into a struct which I can go back and free it later.
I think it is the unmapping which goes wrong:
My tests:

Code: Select all

int *a = (int *)malloc(4);
*a = 5;
free(a);
*a = 5; // NO PAGE FAULT!! why? :O im unmapping it!
putdec((unsigned int)a)); // it prints a's old address while i changed in in free() to 0xFFFFFFFF...why?! but anyways, while i holds the previous address of a, it should be giving me a page fault!

My code (looks long but you can skip most of the parts):

Code: Select all

#include <common.h>
#include <list.h>
#include <screen.h>
#include <page.h>

extern unsigned int *kernel_directory;
unsigned int page_list_num_nodes = 0, malloc_recorder_num_nodes = 0;
unsigned int current_addr, first_page_marked = 0;
extern void mark_page_in_bitmap(unsigned int addr);
struct node current_page_head, *page_indexer;
struct node malloc_records_head, *malloc_r_indexer;

void initialize_new_list(void)
{
	current_page_head.size = 0;
	current_page_head.next = 0;
	current_page_head.addr = 0;
	page_list_num_nodes = 0;
	page_indexer = (struct node *)&current_page_head;
}

void initialize_malloc_recorder(void)
{
	malloc_records_head.size = 0;
	malloc_records_head.next = 0;
	malloc_records_head.addr = 0;
	malloc_recorder_num_nodes = 0;
	malloc_r_indexer = (struct node *)&malloc_records_head;
}

struct node *find_addr_in_malloc_recorder(unsigned int addr)
{
	struct node *tmp = (struct node *)&malloc_records_head;
	unsigned int i = 0;
	while(i <= malloc_recorder_num_nodes)
	{
		if(tmp->addr == addr)
			return tmp;
		tmp = tmp->next;
		i++;
	}
	return 0;
}

int is_current_page_full(struct node *current_page_head, unsigned int size_to_be_added) // 1 == full, 0 == not full
{
	unsigned int sum = 0, counter = 0;
	struct node *tmp = current_page_head;
	while(counter <= page_list_num_nodes)
	{
		sum += tmp->size;
		tmp = tmp->next;
		counter++;
	}
	return ((sum + size_to_be_added) > PAGE_SIZE)?1:0;
}

void *malloc(unsigned int size)
{
	if(first_page_marked == 0)
	{
		current_addr = 0xC0000000; // starting to allocate from this address
		initialize_malloc_recorder();
		initialize_new_list();
		if(is_page_free(current_addr))
			mark_page_in_bitmap(current_addr);
		first_page_marked = 1;
	}
	
	if(is_current_page_full(&current_page_head, size))
	{
		initialize_new_list();
		
		unsigned int num_pages = size/PAGE_SIZE;
		unsigned int i = 0, k;
		
		if(current_addr & 0xFFF/*if a page aligment is needed*/)
		{
			PAGE_ALIGN(&current_addr);
			k = current_addr;
		}
		else
			k = current_addr += 0x1000;
		for(;i<num_pages;i++, k += 0x1000) // allocate and map a new page/s (depends on how big is `size`) for the next malloc calls
		{
			mark_page_in_bitmap(k);
			unsigned int *pt = (unsigned int *)((unsigned int)kernel_directory[k/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
			pt[(k/PAGE_SIZE)%1024] = k | KPAGE_ENTRY_ATTR;
		}
				
		add_to_list(&current_page_head, page_indexer, (size-((int)(size/PAGE_SIZE))*PAGE_SIZE), 0, &page_list_num_nodes);
	}
	else
	{
		unsigned int *pt = (unsigned int *)((unsigned int)kernel_directory[current_addr/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
		pt[(current_addr/PAGE_SIZE)%1024] = current_addr | KPAGE_ENTRY_ATTR;
		putdec((unsigned int)(pt[(current_addr/PAGE_SIZE)%1024] & ~KPAGE_ENTRY_ATTR));
		add_to_list(&current_page_head, page_indexer, size, 0, &malloc_recorder_num_nodes);
	}
	
	add_to_list(&malloc_records_head, malloc_r_indexer, size, current_addr, &malloc_recorder_num_nodes);
	
	malloc_r_indexer = malloc_r_indexer->next;
	page_indexer = page_indexer->next;
	
	enable_paging(kernel_directory);
	
	// allocate new space now:
	unsigned int ret = current_addr;
	current_addr += size;
	return (void *)ret;
}


void free(void *ptr)
{
	if(is_page_free((unsigned int)ptr)) // it is not allocated
		return;
	struct node *mem_to_del = find_addr_in_malloc_recorder((unsigned int)ptr);
	if(mem_to_del == (struct node *)0)
		return;
	unsigned int num_pages = (mem_to_del->size/PAGE_SIZE+1), i = 0, page = mem_to_del->addr;
	unsigned int *pt;
	while(i < num_pages)
	{	
		pt = (unsigned int *)((unsigned int)kernel_directory[page/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
		pt[(page/PAGE_SIZE)%1024] = 0; // unmap the address
		delete_page_from_bitmap(page);
		
		page += 0x1000;
		i++;
	}
	remove_from_list(&malloc_records_head, mem_to_del, &malloc_recorder_num_nodes);
        ptr = (void *)0xFFFFFFFF;
	enable_paging(kernel_directory);
}

Posted: **Sat Jan 03, 2009 5:48 pm**

You need to use INVLPG to invalidate the TLB entry for the page after you remove it. Otherwise, the processor still thinks its there.

Posted: **Sat Jan 03, 2009 5:55 pm**

Also that is a very inefficient way of implementing malloc. I suggest you research the Doug Lea malloc algorithm and rewrite this code to do lower level memory management.

Posted: **Sun Jan 04, 2009 5:17 am**

Code: Select all

putdec((unsigned int)a)); // it prints a's old address while i changed in in free() to 0xFFFFFFFF...why?! but anyways, while i holds the previous address of a, it should be giving me a page fault!

Does your free function take a void pointer? If it does, then I believe setting the pointer to for example '0' in the function won't work (it works that way in C++, but I believe C is the same for that matter). In C++, to set an actual pointer to 0 in a function, this won't work:

Code: Select all

void SetToNull(void *p)
{
   //This pointer will not point to the address 0x000000 after the function exits.
    p = 0;

   //Supposing p is a pointer to an integer, you can however set the value at the memory address of p to another integer.
   //This will work.
   (*((int *) p)) = 5;
}

If you want to set the actual pointer p to point to the address 0x000000, you'd have to do something like this (but I believe it's not possible in C since it doesn't support references):

Code: Select all

void SetToNull(void *& p)
{
   //p now points to the address 0x000000 after exiting the function.
   p = 0;
}

This can be used assuming you're using C++, in C, you might need to use alternative ways.

Code: Select all

*a = 5; // NO PAGE FAULT!! why? :O im unmapping it!

As I explained, the pointer is not set to 0, but the memory IS now seen as 'free' if your free function works correctly and can be reallocated using malloc.

Code: Select all

putdec((unsigned int)a)); // it prints a's old address while i changed in in free() to 0xFFFFFFFF...why?! but anyways, while i holds the previous address of a, it should be giving me a page fault!

Also remember that when the computer boots, the memory is full of 'garbage' (I believe Bochs clears the memory before the OS executes but a real computer doesn't, however). After freeing a variable, the memory where the variable was located might not have changed because all your free function does is say "This memory space is now free again, and the malloc function will be able to use it to allocate new memory." but it doesn't actually clear anything. You can however implement something that sets garbage memory to 0 or something (I did in my free function).

Please correct me if I am wrong.

Posted: **Sun Jan 04, 2009 9:36 am**

thepowersgang wrote:Also that is a very inefficient way of implementing malloc. I suggest you research the Doug Lea malloc algorithm and rewrite this code to do lower level memory management.

Why inefficient?
Creature, C doesn't support references, it's a "new" future in C++.

But I am enabling paging, AFTER I unmap the address, why I'm not getting a page fault?

Invalidating the TLB Entry for the page I want to remove is just more effective then updating the CR0 but still does the same effect.

Posted: **Sun Jan 04, 2009 9:39 am**

C can do the same thing, but you need to make it explicit:

Code: Select all

void SetToNull(void *& p)
{...}

// implicity make reference (C++)
SetToNull(pointer);

becomes

Code: Select all

void SetToNull(void ** p)
{...}

// explicitly make reference (C)
SetToNull(&pointer);

Posted: **Sun Jan 04, 2009 10:45 am**

Combuster wrote:C can do the same thing, but you need to make it explicit:
Code: Select all
void SetToNull(void *& p)
{...}

// implicity make reference (C++)
SetToNull(pointer);
becomes
Code: Select all
void SetToNull(void ** p)
{...}

// explicitly make reference (C)
SetToNull(&pointer);

It's still not working this way either and a is pointing to the same address that was before.

BTW, about the efficiency...
Well, basically, I could have skipped on the page linked list, and just implement the very same thing with an integer just like this:

Code: Select all

if(sum + size > 0x1000) // create a new page/s
     ...
else // no extra page/s needed
       ...
sum += size;

My algorithm doesn't have any efficiency problems at all except for 2 which are "sufferable" I guess.
It's all running on O(1) (if I use a sum variable and not a page linked list) except 2 things: page allocating when (sum+size)>0x1000 and in free when I look for this address which then it is O(n).

Posted: **Sun Jan 04, 2009 10:58 am**

Combuster wrote:C can do the same thing, but you need to make it explicit:
Code: Select all
void SetToNull(void *& p)
{...}

// implicity make reference (C++)
SetToNull(pointer);
becomes
Code: Select all
void SetToNull(void ** p)
{...}

// explicitly make reference (C)
SetToNull(&pointer);

I knew there was a way of doing it in C, but I just couldn't come up with it at the time of my post. The only disadvantage of the void ** or void *& way is that you (standard) can't apply them to new and/or delete as the compiler will complain. Making a custom version (should) work(s) though.

Another question: why do you enable paging each time malloc or free is called?

Posted: **Sun Jan 04, 2009 11:15 am**

Creature wrote:
Combuster wrote:C can do the same thing, but you need to make it explicit:
Code: Select all
void SetToNull(void *& p)
{...}

// implicity make reference (C++)
SetToNull(pointer);
becomes
Code: Select all
void SetToNull(void ** p)
{...}

// explicitly make reference (C)
SetToNull(&pointer);
I knew there was a way of doing it in C, but I just couldn't come up with it at the time of my post. The only disadvantage of the void ** or void *& way is that you (standard) can't apply them to new and/or delete as the compiler will complain. Making a custom version (should) work(s) though.

Another question: why do you enable paging each time malloc or free is called?

I should call enable_paging() anytime I call malloc() or free() because I'm mapping&unmapping addresses. (btw, in case you haven't noticed, I'm identity mapping, my physical addresses = my virtual addresses)
my enable_paging() function, all it does is updating the cr3 with the new directory and ORing the cr0 with 0x800000000.
I could just invalidate the TLB entry for the page I want to update (because updating the page directory in the cr3 is a long process) but this is not the point here.

Well, I'm moving a pointer to pointer into free and that's working, thanks guys.

BTW, conceptual question:

Code: Select all

int *a = (int *)malloc(4);
*a = 5;
free(&a);
int *b = (int *)malloc(4); // should this point to a's last address or to a+4 address?

EDIT:
Another problem..

Code: Select all

	puts("Testing malloc() and free()...\n");
	
	puts("Allocating 4 bytes:\n");
	int *a = (int *)malloc(4);
	*a = 5;
	puts("a = malloc(4), a = ");
	putdec(*a);
	
	puts("\nFreeing a...");
	free(&a);
	puts("a freed.\n");
	
	puts("Allocating 4100 bytes for:\n");
	int *b = (int *)malloc(4100); // b is supposed to be pointing at a+4
	unsigned int *pt = (unsigned int *)((unsigned int)kernel_directory[(unsigned int)b/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
	putdec((unsigned int)(pt[((unsigned int)b/PAGE_SIZE)%1024] & ~KPAGE_ENTRY_ATTR)); // while this shows the real address of b which means that i was mapped successfully.
	*b = 200; // THIS CAUSES A PAGE FAULT!!
	puts("b = malloc(4100), b = ");
	putdec(*b);

Posted: **Wed Jan 07, 2009 6:33 am**

I rewrote the code and now it works perfectly, thanks guys.
My solution (had to rewrite some parts of it):

Code: Select all

#include <common.h>
#include <list.h>
#include <screen.h>
#include <page.h>

extern unsigned int *kernel_directory;
unsigned int page_list_num_nodes = 0, malloc_recorder_num_nodes = 0;
unsigned int current_addr, first_page_marked = 0;
extern void mark_page_in_bitmap(unsigned int addr);
unsigned int current_page_taken;
struct node malloc_records_head, *malloc_r_indexer;

void initialize_malloc_recorder(void)
{
	malloc_records_head.size = 0;
	malloc_records_head.next = 0;
	malloc_records_head.addr = 0;
	malloc_recorder_num_nodes = 0;
	malloc_records_head.is_free = 0; // the first spot of the memory records linked list is always taken
	malloc_r_indexer = (struct node *)&malloc_records_head;
}

struct node *look_for_first_free_spot(struct node *p)
{
	struct node *temp = p;
	unsigned int counter = 0;
	while(counter < malloc_recorder_num_nodes)
	{
		if(temp->is_free == 1)
			return temp;
		temp = temp->next;
		counter++;
	}
	
	return 0;
}

// debugging purpose:
void print_linked_list()
{
	struct node *temp = &malloc_records_head;
	unsigned int counter = 0;
	while(counter <= malloc_recorder_num_nodes)
	{
		putdec(temp->size);
		puts("->");
		temp = temp->next;
		counter++;
	}
	puts("\n");
}

struct node *find_addr_in_malloc_recorder(unsigned int addr)
{
	struct node *tmp = (struct node *)&malloc_records_head;
	unsigned int i = 0;
	while(i < malloc_recorder_num_nodes)
	{
		if(tmp->addr == addr)
			return tmp;
		tmp = tmp->next;
		i++;
	}
	return 0;
}

void *malloc(unsigned int size)
{
	if(size == 0) return (void *)0xFFFFFFFF;
	if(first_page_marked == 0)
	{
		current_addr = 0xC0000000; // starting to allocate from this address
		initialize_malloc_recorder();
		current_page_taken = 0;
		if(is_page_free(current_addr))
			mark_page_in_bitmap(current_addr);
		first_page_marked = 1;
		unsigned int *pt = (unsigned int *)((unsigned int)kernel_directory[current_addr/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
		pt[(current_addr/PAGE_SIZE)%1024] = current_addr | KPAGE_ENTRY_ATTR;
		enable_paging(kernel_directory);
	}
	
	struct node *first_free_alloc = &malloc_records_head;
	unsigned int counter = 0;
	while(counter < malloc_recorder_num_nodes)
	{
		first_free_alloc = look_for_first_free_spot(first_free_alloc);
		if(first_free_alloc != (struct node *)0 && first_free_alloc->size >= size)
			break;
		counter++;
	}
	
	if(counter < malloc_recorder_num_nodes)
	{
		first_free_alloc->size = size;
		first_free_alloc->is_free = 0;
		return (void *)(first_free_alloc->addr);
	}
		
	if((current_page_taken+size)>0x1000)
	{
		current_page_taken = 0;	
		unsigned int num_pages = size/PAGE_SIZE;
		unsigned int i = 0, k;
		if(current_addr & 0xFFF)
		{
			PAGE_ALIGN(&current_addr);
			k = current_addr;
		}
		else
			k = current_addr+0x1000;
		for(;i<num_pages;i++,k+=0x1000) // allocate and map a new page/s (depends on how big is `size`) for the next malloc calls
		{
			mark_page_in_bitmap(k);
			unsigned int *pt = (unsigned int *)((unsigned int)kernel_directory[k/(PAGE_SIZE*1024)] & ~KPAGE_ENTRY_ATTR);
			pt[(k/PAGE_SIZE)%1024] = k | KPAGE_ENTRY_ATTR;
		}
		
		enable_paging(kernel_directory);
		
		current_page_taken = (size-((int)(size/PAGE_SIZE))*PAGE_SIZE);
	}
	else
		current_page_taken += size;
	
	add_to_list(&malloc_records_head, malloc_r_indexer, size, current_addr, 0, &malloc_recorder_num_nodes);
	malloc_r_indexer = malloc_r_indexer->next;
	
	// allocate new space now:
	unsigned int ret = current_addr;
	current_addr += size;
	return (void *)ret;
}

void free(void **ptr)
{
	if(is_page_free((unsigned int)*ptr)) // it is not allocated
		return;
	struct node *mem_to_del = find_addr_in_malloc_recorder((unsigned int)*ptr);
	if(mem_to_del == (struct node *)0)
		return;
	*ptr = (void *)0xFFFFFFFF; // end of virtual memory (will cause a page fault if someone will try to access this address)
	mem_to_del->is_free = 1; // remove_from_list(&malloc_records_head, mem_to_del, &malloc_recorder_num_nodes);
}

OSDev.org

Memory allocating problems..

Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..

Re: Memory allocating problems..