Implementing free page frame stack

[chbaker0]

Hi all,

I'm developing a physical memory manager for my kernel. I'd like to start with a free page stack scheme. However, I'm a little unsure about how to implement this. There's three options I can think of, but each have problems:

1. Have a linked list of free page frame addresses. When allocating or freeing frames, pop or push an element from/to the head of the list. However, how can I allocate nodes without the memory manager?
2. Have a linked list of free page frames, but use the frames themselves as list nodes. However, this requires directly accessing physical memory addresses which presents difficulties with paging. How can I access these frames from within a virtual address space?
3. Use a statically sized array of addresses as a stack. However, then I can only store a limited number of frames and would need a hybrid method.

I don't think (1) is feasible. For (2), maybe I could page in physical frames I need to access on demand? This sounds inefficient, but maybe it isn't. (3) sounds like the best to me but I want to start out with something simpler.

What are your opinions on these? Is there anything I haven't thought of? What implementations are you all using in your kernels?

Thanks,
Collin

[LtG]

I'm developing a physical memory manager for my kernel. I'd like to start with a free page stack scheme. However, I'm a little unsure about how to implement this. There's three options I can think of, but each have problems:

1. Have a linked list of free page frame addresses. When allocating or freeing frames, pop or push an element from/to the head of the list. However, how can I allocate nodes without the memory manager?
2. Have a linked list of free page frames, but use the frames themselves as list nodes. However, this requires directly accessing physical memory addresses which presents difficulties with paging. How can I access these frames from within a virtual address space?
3. Use a statically sized array of addresses as a stack. However, then I can only store a limited number of frames and would need a hybrid method.

I don't think (1) is feasible. For (2), maybe I could page in physical frames I need to access on demand? This sounds inefficient, but maybe it isn't. (3) sounds like the best to me but I want to start out with something simpler.

What are your opinions on these? Is there anything I haven't thought of? What implementations are you all using in your kernels?

There's at least the following options:
- Have a .bss section in your kernel, any size you like, which you use initially. This memory is reserved for your by your bootloader (GRUB or something else). You can use this memory to "bootstrap" your PMM.
- You _could_ have your PMM in a separate process (if you're planning a microkernel), though it's a bit extreme. Here the PMM could have 1:1 physical:virtual mapping, so it becomes trivial to access.
- You could alternatively, as you suggested, map the needed physical page frame on demand. I wouldn't worry about the performance, you can change it later. Besides, I wouldn't think there's any massive performance impact if you store 1024 (4KiB/4B) physical page frame addresses in a single page, so you only need to do the demand re-mapping when you cross over the boundary.

My suggestion would be to pick whatever is the easiest or most convenient and then later coming back to it for performance reasons, later, when you have some way of measuring actual performance. Microbenchmarks might suggest a "best" way, but the actual real-world use might prove otherwise. Due to the "unpredictability" of performance on the x86 I wouldn't suggest spending too much time worrying about the PMM performance until you have meaningful ways of measuring impact.