Heap/Paging Questions

[Creature]

Hello,

I have some questions about the heap and paging in general. I have searched the wiki and Googled some of it (but for some reason didn't manage to find what I actually sought) so I decided (since I have more than one question and issue) to post it here.

So basically, after having used a clone of JamesM's tutorial heap for quite some time, I decided to write my own (with a first-fit algorithm for allocation). I know a binary tree can be more efficient and such, but this isn't really what I'm worried about (as it's actually the first time I got further than trashing my heap ). So now with my own heap, I'm experiencing some issues and have some questions. Before I ask any of them, I'll give you the link to my SVN repository so you can browse the source files:

SVN Repository (with the memory headers)

Either way, as far as I understand paging, (physical) memory is divided into pages of 4 kB each and addresses must be page-aligned. So does this mean I must page-align every address in the heap? I'm already aligning the start address of the heap, so I'm wondering about whether to align the end-address and each heap header's position too?

The second thing I wanted help with is a problem I'm experiencing. I was really happy when I noticed my allocation function was doing fine (which doesn't mean it doesn't contain any serious flaws or bugs) and even more happy when I saw that my Heap::_Expand function worked... at least that is what I thought. It seems that the heap expands correctly, but after a certain amount of expanding, it simply ends up with a page-fault. I find this strange because the heap manages to expand a while and then comes to a sudden end with a page-fault. Though since I'm confused about how to use paging exactly in the heap, this might very well be what's causing my problem.

Am I missing something obvious here, did I make a stupid mistake or is there some hard-to-fix bug somewhere in my code?

Thanks,
Creature

[frank]

Pages from your physical and virtual memory manager are going to be page aligned. Memory returned by the heap does not have to be. The start address and end address of the heap are going to be page aligned however. Think of the heap as a large chunk of memory at a certain memory address with a certain size. Your malloc functions are then free to divide up the memory as they see fit.

About your page fault issue, my problems with my allocator always came from my free function and not my malloc function. It's also possible that your virtual memory manager is not mapping pages properly or that you are even running out of free pages to map.

[Creature]

That can indeed be what is happening. What I've done now is make sure the heap start-and end-address are both page-aligned. Then I've updated the Expand en Contract code to ensure the new end-address is page-aligned as well and that the Alloc code takes this into account. This still seems to give me the same problem, however I'm not getting a little more information from the page-fault. Previously I just got notified of a page-fault, but now it says that there is no page present, which obviously means something isn't being mapped correctly. I've checked most of the functions that are directly related to it again, but still can't seem to find the problem. I can try placing the heap at another location or changing some of its values, but I sincerely doubt if that will be of any help.

It's also impossible that it's the free function since it's not even being used (I already wrote it but haven't used it or excessively tested it yet because I wanted allocation and expansion to work decently first).

[frank]

Code: Select all

/* Set the new size. */
unsigned i((unsigned) this->_EndAddress);
unsigned NewEndAddress = ((unsigned) this->_StartAddress + newSize);

I didn't really see where you are storing the headers for the memory blocks but if you are storing the header in the heap as is commonly done (in front of the allocated memory block) then you need to make sure that the new block of memory you get also includes the size of the header.

EDIT: I found this so it seems that's not the problem.

Code: Select all

/* Include the size of a header. */
size += sizeof(Header);

Can you post the test case?

[Creature]

If you're referring to my testing code that makes it crash, here it is:

Code: Select all

void TestMem()
{
	for(;;)
	{
		/* This redirects to Alloc from Paging.cpp which, when the heap is ready, redirects to KernelHeap->Alloc. */
		byte *p = new byte[8096];

		/* Simply something that stops when something failed (I made Bochs output a message in the console on failure with BX_WriteStr). */
		if(!p)
		{
			__asm__ __volatile__("cli");
			for(;;) ; //Endless loop so I can carefully see what's wrong.
		}

		/* This was used to test free and then it won't crash (which is obvious since every allocated block is immediatly freed). */
		//delete[] p;

		/* Print the amount of memory in use (in bytes). */
		BX_WriteInt(KernelHeap->GetUsedMemory());
		BX_WriteChar('\n');
	}
}

I quickly wrote this and I know it will crash/stop/mess up after a certain time, but that shouldn't be after having allocated around only 4 - 5 MB as my Bochs is set up to have 32 MB. I'm aware that around 1 MB is reserved and about 0.5 MB is taken up by a memory pointer 'CurAddress' which is simply an integer being incremented, the heap should then be able to take over everything or at least a big part of the memory that's left, shouldn't it?

[frank]

If you set the size of the Bochs memory to say 64mb does the amount of memory that gets allocated before it messes up increase or does it get locked at around 5mb?

[Creature]

It still locks up at around 5 MB.

[frank]

My next suggestion would be too sprinkle the code with lots of print outs for various things and try to figure out where it goes wrong. The fact that the amount of memory doesn't matter is significant. Try to figure out where the code decides its out of memory. In Heap::_Expand, Heap:Alloc, or AllocateFrame.

[Creature]

After adding some debug statements and changing some other things, I'm now encountering something very strange. I've put a debug string print at the beginning and through the entire Heap::Alloc function. Every debug string is printed correctly and when the 'crash-number' (around 5 MB) is reached, it prints the string at the start of the Heap::Alloc function about 20 times over again and then page-faults. I put this at the start of Heap::Alloc:

Code: Select all

BX_WriteStr("#0\n");

Which is then printed around 20 times in the Bochs console and then it page-faults, with instead of the "WARNING: Page-fault occurred" message I coded into my interrupt-handlers, the same message printed in crazy symbols. This makes me believe that something is reading too far somehow.



As you can see, the "#0" is printed over and over again for some reason.

[frank]

Are you marking all of the areas used by the kernel and all of the reserved memory as used in the memory bitmap? It could be that FindFirstFrame() is returning pages used by the kernel and then they are being overwritten.

This code sets all frames to free, the area used by the kernel could be allocated and could be overwritten.

Code: Select all

/* Physical memory size (GRUB detects this in kB, we use bytes). */
        FrameCount = GRUB_MEMORY_SIZE / PAGE_SIZE;
        Frames = (unsigned *) malloc(GET_ID_FROM_BIT(FrameCount));
        memset(Frames, 0, GET_ID_FROM_BIT(FrameCount));

[Creature]

I see what you mean, but I believe the location of the kernel and GRUB modules and such are already 'reserved' by this statement:

Code: Select all

/* Identity map. */
while(i < CurAddress + PAGE_SIZE)
{
	AllocateFrame(GetPage(i, true, KernelDir), false, false);
	i += PAGE_SIZE;
}

Which takes care of identity mapping and allocates frames so the heap shouldn't be able to overwrite these frames anymore (unless there is something else wrong). I'm really stumped of what this could be.

[frank]

void *Heap::Alloc(size_t size) doesn't page align addresses that are returned by it. So after a while of spitting out memory its going to return a non page aligned chunk for a new page table.

Also all of the memory given out by void *AllocEx(size_t size, bool alignAddress, unsigned *physAddressStorage) needs to be marked as used in the frame bitmap. Its possible that the heap is overwriting some of the page tables.

Post the value of CR2 when the page fault occurs and also the flags.

EDIT: After running the disk image I discovered that your code is not mapping in 0xC0200000 - 0xC0201000. The initial heap ends at 0xC01FFFFF so the expand routine must be skipping that page. Try checking the _expand routine and look at the _EndAddress and new end address, somehow this code

Code: Select all

/* Make sure there are pages present at the new addresses (start at the heap ending address). */
for( ; i < this->_EndAddress; i += PAGE_SIZE)
    AllocateFrame(GetPage(i, true, KernelDir), this->_SupervisorMode, !this->_ReadOnly);

is skipping the page immediately after the old heap end.

[Creature]

The frames for the heap are all allocated and set in the InitPaging() function. When expanding, Heap::Expand allocates frames for the new space. The value of CR2 is 0x00000000928500e9. Most of the code is still largely based off JamesM's code. But even while using James' heap I still had a similar issue. It still crashed after it expanded a while.

[ehenkes]

Code: Select all

          /* Is page-alignment on the address needed and isn't the address already aligned? */
                if(alignAddress && (CurAddress & 0xFFFFF000))
                {
                        CurAddress &= 0xFFFFF000;
                        CurAddress += PAGE_SIZE;
                }

JM's code wastes a PAGESIZE, when the address is "round" to 0x1000.

Better use:

Code: Select all

if( align == 1  )
{
    if( !(placement_address == (placement_address & 0xFFFFF000) ) )
    {
        placement_address &= 0xFFFFF000;
        placement_address += PAGESIZE;
    }
}

or

Code: Select all

if(align == 1 && (placement_address & 0x00000FFF))
{
   placement_address &= 0xFFFFF000;
   placement_address += PAGESIZE;
}

[frank]

ehenkes figured out why the code for expanding fails after a while. Either one of those changes should fix the "hole" problem I was just talking about, but why the page fault is at that address I can't exactly tell. Maybe fixing that problem will fix the other problem.

One way I like to debug code is by using Magic Breakpoints. If you include an xchg bx, bx in _expand and run the debugger you might be able to find it. If you still can't find it then could you post a disk image, the one in your SVN doesn't seem to be up to date.