OSDev.org

Dear Forum,

I am writing an OS for x86_64 just for fun and learning purpose. The kernel is booted via Limine and I have a question about memory management (Only if my understanding is correct).

As paging is required for long mode, Limine sets one up for me, maps my kernel to the virtual address and maps the entire first 4GiB into another address.

I am getting to a point now, that I need to implement my own paging and therfore also a memory manager. My first goal is to implement a manager that allocates physical addresses in 4KiB blocks - to conform with paging:

• Easiest solution would be a bitmap, but in long mode the possible amount of memory makes this wasting huge amounts of memory.
• Second thought was linked lists, similar to what a EFI Memory Map looks like. But if I store the data in my own allocated memory, i have the chicken egg problem - I need a page frame to store the initial free memory ranges, but to get one page frame I need to know the free ranges. Furthermore, as memory fragments, I need to expand this page frame by more.

So my thought was: "What if I store the information about a free memory range just in the first page frame of that range?"
I keep a pointer to the start, map it to a virtual address, load the data on that address and look, if it is enough. If no, get the next pointer and instead map this address to the same virtual address, loading the data again. If I find a big enough range, I return that address and put new data just to the page behind the returned address, updating the previous range->next pointer.

This can be done with just one virtual page mapped as needed. The Problem is only that I cannot know to where used memory belongs - if a process exits I have to trust it releases all its physical page frames. That may be a problem...

That do you think about it?

Best regards
Sebi

I don't think bitmaps are wasting a lot of memory. Eight 4k pages (32k) requires a one byte bitmap. That's 0.003%. The required structures for mapping memory waste a lot more (8 bytes per 4k frame), which is 0.2%.

However, the main reason to use bitmaps is that you can implement a lock-free physical memory manager, something that is impossible with linked lists.

sebihepp wrote: ↑Wed Oct 16, 2024 1:08 pm This can be done with just one virtual page mapped as needed. The Problem is only that I cannot know to where used memory belongs - if a process exits I have to trust it releases all its physical page frames. That may be a problem...

That do you think about it?

Best regards
Sebi

If you're writing the kernel, you're in control of each process and its memory, and when it exits, the kernel can clean up all its no longer required resources such as memory.

Typically, a process will have a virtual address space description, which will be something like a list of memory mappings. In those mappings, you should have a reference to every page currently mapped, so you can walk the mappings, walk each page in the mapping, removing references to physical pages as you go. For each page that was a unique reference (ie. Not a shared page) you know that page is now free, and it can be released back to the PFM.

A bitmap to manage available memory is not the best. As you say, it wastes memory, and large runs of available memory can be represented in the free memory itself. Also, finding memory to allocate is typically a linear scan of the bitmaps as well, though the scan size is not typically massive.

To be honest, most physical page allocations are probably done on a page by page basis, in response to memory mapping requests, so another option is to have a "stack" of free pages, with a pointer to the current "head" free page. In that "head" free page, you have a pointer to the next free page, and so on.

Freeing a memory page then becomes a matter of recording the current "head" free page in the page you're freeing, then storing the page number of the new free page in your "head" free page.

Allocating a memory page is then just the opposite. You use the "head" free page to map in the page to a temporary address, read the next free page and write that to the "head" free page, then unmap and use the newly allocated page.

Both simple, quick O(1) operations. And another benefit is that memory is reused in LIFO order, so there is still a chance that an allocated page contents are still in a CPU cache.

The downside being that allocating contiguous pages is a bit of a nightmare, as the free page stack will become a fragmented mess. But again, that tends to be not a problem, as the only likely use of contiguous memory is for data buffers to transfer to devices, and most devices these days provide scatter/gather DMA to handle non-contiguous buffers.

rdos wrote: ↑Thu Oct 17, 2024 1:31 am I don't think bitmaps are wasting a lot of memory. Eight 4k pages (32k) requires a one byte bitmap. That's 0.003%. The required structures for mapping memory waste a lot more (8 bytes per 4k frame), which is 0.2%.

However, the main reason to use bitmaps is that you can implement a lock-free physical memory manager, something that is impossible with linked lists.

I am in long mode and to be prepared for the future and the biggest memory amount my bitmap would need space for 2^64 Bytes. That's too big, even if the bitmap only uses 0.003%.

thewrongchristian wrote: ↑Thu Oct 17, 2024 2:41 am The downside being that allocating contiguous pages is a bit of a nightmare, as the free page stack will become a fragmented mess. But again, that tends to be not a problem, as the only likely use of contiguous memory is for data buffers to transfer to devices, and most devices these days provide scatter/gather DMA to handle non-contiguous buffers.

I think I like a split approach:
A bitmap for the lower 1MiB to be able to allocate continuous page frames for old ISA DMA devices
and a "stack" for the rest of the memory.

The Stack takes some time to setup initially, right? As one needs to go through all free page frames, setting the pointers to the next stack frame.

Your bitmap doesn’t have to be allocated at compile time. The OS can determine its size at boot and allocate just the memory required to account for actual physical memory.

I use a memblock allocator, but in the end, that is the same as an RLE encoded bitmap allocator. Advantage of that one is that it doesn't take more time to initialize it when you add more memory. I always felt weird about bitmaps and linked lists for that reason: Double the memory means double the initialization time. That just feels wrong. With a memblock allocator, double the memory just means double the number I write into the "length" part of the block descriptor.

The allocation problem also persists here. I solve it by adding "enough" descriptors into the data section so that I can probably save all the reserved regions where my kernel is (mustn't overwrite the kernel, after all) before allowing the allocator to itself allocate memory for more descriptors. So far, 32 regions for the reserved and free lists each have been enough everywhere.