Physical (not virtual or heap) memory manager issue

[gusc]

Hello!

I'm struggling with the concept of physical memory management, as I want it to be clear an concise, but I can't wrap my head around the fact that physical memory is really scattered and in the midst of it all there's also code that you're currently executing. I posted some questions 2 weeks ago here as a reply to a similar question, but there's still no answer. So I wanted to lay out my problem more clearly.

1. I've written a boot loader that get's loaded by BIOS and it boots up to Long mode.
2. In protected mode I identity map the first 2 MB of RAM
3. In Long mode I map rest of the memory.
4. I've implemented my own heap allocator with segregated free lists and some sort of a search tree for larger objects (similar to JamesM tutorial with header magic and other data structures)
5. I've implemented similar lists and a tree for mapped, but unused pages that get "allocated" later on

It's all OK for now, but the problem remains - how can I manage the physical memory which is used and which isn't, and keep it nice and tidy. Should I use page frames (a bitset where 1 = block is used, 0 = block is free) or is there any better algorithm? I'm also concerned about the allocation speed too.

And also is it a good practice to ID map all the memory in your boot loader at the beginning or create some smarter allocation mechanism, that allocates new pages on the fly (which I think means keeping some 3 page look ahead buffer in case you need to create a new PML1, PML2 and PML3 tables)?

[Combuster]

Do you want to manage free memory, or do you want to manage used memory? How do you really need to manage them?

What reason is there in the first place to query if address X is being used?

[gusc]

Well, I just want to find next suitable frames/blocks that I could map some virtual address to so that I wouldn't be stuck with linear and scattered address space. I'd like to get rid of identity mapping and use some sensible virtual memory map of my own (something like 0-x for heap, x+1-7FFFFFFFFFFF for the stack and upper memory for instructions), but then I need to know which physical frame/block is free and which is used. And I also need to keep in mind that there will be processes with their own heaps, stacks and address spaces in general.

[mathematician]

One possibility is a bitmap, although that probably isn't the best option - especially with the size of memory nowadays. Another option would be a stack of page numbers or structures - one for each physical page. Initially the stack would contain page numbers for the whole of physical memory, with the exception of those reserved for things like memory mapped devices. When a page allocated you take it off the top of the stack, and when a page is freed you push it onto the stack.

Another possibility is some combination of the two, with a stack for 4mb blocks (say) and the structure relating to each block would contain a bitmap for the 4kb pages within that block.

If you need to have physically contiguous memory available for DMA devices, then you could have a few megabytes reserved especially for that purpose. They would have their own allocator which operated independently of the main page allocator.

Another option would be a buddy system such as that used in Linux. You can probably find that documented somewhere.

[madanra]

I would start of with just a free pages stack. When a page is requested, you pop its address off the stack, and when a page is freed, you push its address back on the stack.

[Combuster]

Well, I just want to find next suitable frames/blocks that I could map some virtual address to (...), but then I need to know which physical frame/block (...) is used.

You're still saying here that the memory you want to map must be used memory. Like alloc() returning memory being used by something else.

Really?

[zhiayang]

I remembered this article:
http://forum.osdev.org/viewtopic.php?t=23982

I implemented something like this in my kernel.
You can read the entire thread to decide what to use.

[gusc]

One possibility is a bitmap, although that probably isn't the best option - especially with the size of memory nowadays.

Yep that's what I am concerned + the free block look-up speed

Another possibility is some combination of the two, with a stack for 4mb blocks (say) and the structure relating to each block would contain a bitmap for the 4kb pages within that block.

This sounds interesting I could actually squeeze in up to 16Mb blocks with 4Kb paging - as the lowest 12 bits are free and it's enough to store information about how many contiguous pages (not bytes, and that is 4k * 4k = 16m) this address is pointing to.

Another option would be a buddy system such as that used in Linux. You can probably find that documented somewhere.

Yes, the buddy allocator - I read the Wiki page over and over and still can't wrap my head around that - it sounds like a some kind of a list structure, but the name confuses me.

You're still saying here that the memory you want to map must be used memory. Like alloc() returning memory being used by something else.
Really?

No, I need to know which block is free. I'm sorry for my misleading expressions. Although I might need to know which block is used when freeing them, so that I don't push a block on the stack twice (if I choose to use free page stack).

I remembered this article:
http://forum.osdev.org/viewtopic.php?t=23982

I implemented something like this in my kernel.
You can read the entire thread to decide what to use.

Thanks, I'll look into this one. Somehow this one slipped by while searching the forums.