Is this a viable page frame allocation algorithm?

[IsaccBarker]

Hello! I'm currently writing a page frame allocator in Rust for my kernel. So far, it's been going great (after a rewrite ). Taking after one of the pages on the wiki, I planned out how my memory was going to be allocated. I came up with a solution that works pretty well and is decently performant, but I'm unsure how it will scale in the future. I haven't heard of this before, which probably means I'm Googling for the wrong thing, or it's obviously terrible and I'm missing something. Here is how I've laid things out.

• At boot, the kernel gets the memory area, reclaims what can be reclaimed, and passes that data to a function initializing the page frame (pf) allocator. The initializer calculates the number of page frames per area and sets a struct member that holds the index of the page at the start of the greatest free page frame extent in the area to 0.
• When malloc is called (or realloc, calloc, etc...), it looks through each memory area (there are only 6 on my bare metal machine) and decides on the first one with free space. It then allocates the correct amount of memory starting from the index of the greatest free page frame extent in the area. It increments that index by the number of pages requested. This obviously doesn't get the accurate value, but it's close enough until we run out of memory.
• If no memory areas can spare the requested space, a full recalculation to get the actual index is performed. This doesn't have to be performed very often at all, and with some optimization I think I can get it to be reasonably fast.
• Freeing memory is done by consulting an allocation header at the start of the allocated memory, and then doing simple subtraction on the index.

Here's a visual description.

Code: Select all

Assume one memory area. The marker 'A' shows what the allocator thinks the index of the start
of the maximum consecutive page range is.

After initialization:
|-------------------------------------------------------|
|                    Free Memory                        |
|-------------------------------------------------------|
^
A

After some malloc(n)s:
|-------------------------------------------------------|
| Data |  Data  |  Data |  Data  | Data |  Free Memory  |
|-------------------------------------------------------|
                                        ^
                                        A

After freeing all most of the existing allocations.

|-------------------------------------------------------|
| Data |        Free Memory      | Data |  Free Memory  |
|-------------------------------------------------------|
                                        ^
                                        A

Note how the marker is out of date, there is a larger amount of free memory behind it. Imagine this
continues, but in the future, allocation fails because the marker has reached the end. This
triggers a recalculation to see if the problem can be fixed. The result is this:

|-------------------------------------------------------|
| Data |        Free Memory      | Data |  Free Memory  |
|-------------------------------------------------------|
        ^
        A

More allocations can now be preformed.

If I'm not mistaken, very often, when allocating memory, it can be allocated O(1) (it's just looking up an index, doing some pointer arithmetic, and writing a simple allocation header). In the worst case, it's O(n), where n is the number of pages in a memory area.

It seems weird I haven't come across this approach. Is it inherently flawed? The closest thing I could find is the watermark allocator, but this is obviously different and respects page frame boundaries.

[Octocontrabass]

It sounds like you're not using paging at all. Most designs would consider that to be a pretty big flaw.

Even a single address space OS can take advantage of paging to work around physical memory fragmentation.

[IsaccBarker]

Woops, sorry, I guess I used the term page frame incorrectly then.

Most designs would consider that to be a pretty big flaw.

How so? I thought using paging was discouraged inside a kernel (e.g. the physical memory manager works just on physical memory, and the virtual memory manager is solely for userspace processes).

[Octocontrabass]

So this is actually your kernel heap allocator, and it works at page granularity? That makes more sense. If you already map all physical memory somewhere your kernel can access, it's reasonable to use the already-mapped memory instead of dynamically mapping the memory a second time just for kernel allocations.

How does this interoperate with userspace allocations?

I thought using paging was discouraged inside a kernel

I... haven't heard of this.

the physical memory manager works just on physical memory

The physical memory manager keeps track of physical memory, but typically doesn't access it to avoid cache pollution.

[IsaccBarker]

Yep, this is the heap allocator. I've started implementing hardware paging support, and it seems the existing allocator will work quite nicely, just with the multiple memory area logic removed.

I... haven't heard of this.

I must have misremembered. I did two weeks or so of planning and researching, so I must have read it somewhere. Sorry!

How does this interoperate with userspace allocations?

Memory is mapped into the process address space by the virtual memory manager, and then it's further managed by whatever allocator the program decides to use. My original plan was to allocate memory at page granularity and then map it into user space, but the new approach is much better, so thank you

Regardless, with the multiple memory area logic removed from the allocator, is it a decent approach?

[Octocontrabass]

The reason I ask about interactions with userspace is that this heap allocator relies on a header in the allocated block, and page frames that have been allocated by userspace won't have those headers. It sounds like you already have a solution for that, though!

So, from a functionality perspective, I think you've come up with a variation of a linked list allocator. It's a perfectly usable allocator, and it may work fine depending on your workload. However, it's pretty susceptible to free space fragmentation, and I'm not sure how well it can scale up to multiple hardware threads.

[IsaccBarker]

Yeah, fragmentation is something I'm worried about. If it turns out to be a large issue, I'll try and write a different allocator. Everything's already behind an implementation agnostic layer. Because of fragmentation and possible performance reasons (as well as it sounds cool), I'm going to try and do something like this:

However, it is theoretically possible for a microkernel to be designed so that all memory structures are exactly the same size (the Process struct, Thread struct, Message struct, etc). This would be very fast and efficient.

As for the page frames allocated in userspace not having these headers, as far as I can gather, this is fine. The kernel shouldn't have to care about the userspace memory allocator running on top of it, and can just manage the memory blindly.
Thanks for your help!!