JMolloy tutorial heap problem

[Enerccio]

Hello, I am trying to learn how to make a kernel with the tutorial on http://www.jamesmolloy.co.uk and I currently hit a lot of tripple faults/other errors at chapter 9. I traced down the problem being related to the allocation. Here is my allocation function

Code: Select all

void* EKERNEL alloc(uint32_t size, boolean_t page_align, heap_t* heap){

	uint32_t new_size = size + sizeof(header_t) + sizeof(footer_t);
	int32_t iterator = find_smallest_hole(new_size, page_align, heap);

	if (iterator == -1){

		uint32_t old_length = heap->end_address - heap->start_address;
		uint32_t old_end_address = heap->end_address;

		expand_heap(old_length+new_size, heap);
		uint32_t new_length = heap->end_address - heap->start_address;

		iterator = 0;
		int32_t idx = -1, value = 0x0;
		while (iterator < heap->index.size){
			uint32_t tmp = (uint32_t) lookup_ordered_array(iterator, &heap->index);
			if (tmp > value){
				value = tmp;
				idx = iterator;
			}
			iterator++;
		}

		if (idx == -1){
			header_t* header = (header_t*) old_end_address;
			header->magic = HEAP_MAGIC;
			header->size = new_length - old_length;
			header->is_hole = true;
			footer_t* footer = (footer_t*) (old_end_address + header->size - sizeof(footer_t));
			footer->magic = HEAP_MAGIC;
			footer->header = header;
			insert_ordered_array((type_t) header, &heap->index);
		} else {
			header_t* header = lookup_ordered_array(idx, &heap->index);
			header->size += new_length - old_length;
			footer_t* footer = (footer_t*) ((uint32_t) header + header->size - sizeof(footer_t));
			footer->magic = HEAP_MAGIC;
			footer->header = header;
		}

		return alloc(size, page_align, heap);
	}

	header_t* orig_hole_header = (header_t*)lookup_ordered_array(iterator, &heap->index);
	uint32_t orig_hole_pos = (uint32_t) orig_hole_header;
	uint32_t orig_hole_size = orig_hole_header->size;

	if (orig_hole_size-new_size < (sizeof(header_t)+sizeof(footer_t))){
		size += orig_hole_size - new_size;
		new_size = orig_hole_size;
	}

	if (page_align && (orig_hole_pos & 0xFFFFF000)){
		uint32_t new_location = orig_hole_pos + 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t);
		header_t* hole_header = (header_t *) orig_hole_pos;
		hole_header->is_hole = true;
		hole_header->magic = HEAP_MAGIC;
		hole_header->size = 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t);
		footer_t* hole_footer = (footer_t*) ((uint32_t)new_location-sizeof(footer_t));
		hole_footer->magic = HEAP_MAGIC;
		hole_footer->header = hole_header;

		orig_hole_pos = new_location;
		orig_hole_size = orig_hole_size - hole_header->size;
	} else
		remove_ordered_array(iterator, &heap->index);

	header_t *block_header  = (header_t *)orig_hole_pos;
	block_header->magic     = HEAP_MAGIC;
	block_header->is_hole   = false;
	block_header->size      = new_size;

	// ...And the footer
	footer_t *block_footer  = (footer_t *) (orig_hole_pos + sizeof(header_t) + size);
	block_footer->magic     = HEAP_MAGIC;
	block_footer->header    = block_header;

	if (orig_hole_size - new_size > 0){
		header_t* hole_header = (header_t*) (orig_hole_pos + sizeof(header_t) + size + sizeof(footer_t));
		hole_header->magic = HEAP_MAGIC;
		hole_header->is_hole = true;
		hole_header->size = orig_hole_size - new_size;
		footer_t* hole_footer = (footer_t*) ((uint32_t)hole_header + orig_hole_size - new_size - sizeof(footer_t));
		if ((uint32_t)hole_footer < heap->end_address){
			hole_footer->magic = HEAP_MAGIC;
			hole_footer->header = hole_header;
		}
		insert_ordered_array((type_t) hole_header, &heap->index);
	}

	memset((void*) ((uint32_t) block_header + sizeof(header_t)), 0, size);  // to ensure that memory is empty
	return (void*) ((uint32_t) block_header + sizeof(header_t));
}

The problem is that sometimes the memset at the end will overwrite the footer of the block, and sometimes it wont.
I am not sure where the problem is, but if I remove memset (which I only added to test this), then some structures such as task_t later on will have MAGIC number as the last member (I know that this can happen voluntarily because headers/footers are not cleaning themselves but still).

In any case, here is my (dumbed down to test it) version of memset:

Code: Select all

void* EKERNEL memset(void* pointer, uint8_t value, size_t n){
	uint8_t* ptr = (uint8_t*) pointer;
	int i;
	for (i=0; i<n; i++)
		ptr[i] = value;
	return pointer;
}

EDIT:: Fixed the footer removal, but it will still fail when I request page aligned memory for get_page() in move_stack() function at that memset... If I skip page aligning, for any case ie (&& false added to that page align check in alloc), it will never tripple fault ever.

[eryjus]

Hi,

For starters, check the page alignment in the if conditions. It is incorrect from the tutorial.

With that said, I would also recommend that you make sure you completely understand any code you copy in -- even to the point of and the ability to create your own algorithms. Friendly tip: Not everyone in this forum looks kindly on simply copying code and wondering why it might not work.

[eino]

The big secret is that JamesM's tutorial is not copy pasteable... You should be able to download the sourcecode thou if you want to use it directly.

[JamesM]

The big secret is that JamesM's tutorial is not copy pasteable... You should be able to download the sourcecode thou if you want to use it directly.

Indeed, after feedback I decided to keep it that way.

My rewrite won't have deliberate mistakes by the way...

[Enerccio]

The big secret is that JamesM's tutorial is not copy pasteable... You should be able to download the sourcecode thou if you want to use it directly.

actually, this doesnt matter in this case, the bug is even in the source

Code: Select all

if (page_align && orig_hole_pos&0xFFFFF000)

in kheap should have been

Code: Select all

if (page_align && orig_hole_pos + (sizeof(header_t)) &0xFFFFF000)

because we want page aligned data, not header, so if header is page aligned, by any means, it will skip the code altogether, leaving data unaligned....