OSDev.org

That´s the way I´m doing it. I have one stack per 4mb page and for 4kb pages I prefer the stacks which are not completely free (for doing this I´m using a bitmap).

Optimizing the page allocator is only half the truth. A page should be viewed as a token just moving from one place to another. Linux has preallocated all the page structures (that contains info who owns it, swap algorithm info and other associated data) and if most of pages are 4KB pages scattered around, this will not waste too much space. Because of this moving around pages, the stack is suitable. You can preallocate all the page frame stack nodes in a vector so that you quickly can find the node of the vector based on the page number.

All these page frame information structures consumes a lot of space and trying to memory optimize the page allocator itself will not gain that much because it is not the page allocator itself that consumes but more the structures needed when the page is out in the wild.

The fact is that there are a lot of 4k pages in your average system, even saving 4 bytes per 4k page can mean a difference of 4 MB in the memory usage of your kernel. Things add up real quickly when talking about storing info per page, and even though other parts of the MM have a bigger footprint than the allocator doesn't mean it isn't worth it looking very closely at how one can minimize it's memory usage for non-free pages.

FlashBurn wrote:Correct me if I´m wrong, but in a tree it is O(log n) and not constant, because it depends on the height and the height depends on the number of nodes. So your algorithm isn´t O(1).

The tree has a fixed predefined maximum height that does *not* depend on the actual amount of memory present (~22 on an i386), therefore it is technically valid to claim O(1) performance.

Observe that the height of 22 (= iterations) is actually smaller than the (also constant) table size suggested by the OP (= 512 more simple iterations), and is designed to support any MMU design out there, multiple page sizes, and to efficiently support larger allocations.

davidv1992 wrote:The fact is that there are a lot of 4k pages in your average system, even saving 4 bytes per 4k page can mean a difference of 4 MB in the memory usage of your kernel. Things add up real quickly when talking about storing info per page, and even though other parts of the MM have a bigger footprint than the allocator doesn't mean it isn't worth it looking very closely at how one can minimize it's memory usage for non-free pages.

Isn't that an argument for combining the 2 things together ? We certainly need some data for every used page. And we need a way to store info about free pages. Combine them into a single structure with lots of overloaded members.

Combuster wrote:

FlashBurn wrote:Correct me if I´m wrong, but in a tree it is O(log n) and not constant, because it depends on the height and the height depends on the number of nodes. So your algorithm isn´t O(1).

The tree has a fixed predefined maximum height that does *not* depend on the actual amount of memory present (~22 on an i386), therefore it is technically valid to claim O(1) performance.

Observe that the height of 22 (= iterations) is actually smaller than the (also constant) table size suggested by the OP (= 512 more simple iterations), and is designed to support any MMU design out there, multiple page sizes, and to efficiently support larger allocations.

Combuster, perhaps you should have said O(22) then.

gerryg400 wrote:

davidv1992 wrote:The fact is that there are a lot of 4k pages in your average system, even saving 4 bytes per 4k page can mean a difference of 4 MB in the memory usage of your kernel. Things add up real quickly when talking about storing info per page, and even though other parts of the MM have a bigger footprint than the allocator doesn't mean it isn't worth it looking very closely at how one can minimize it's memory usage for non-free pages.

Isn't that an argument for combining the 2 things together ? We certainly need some data for every used page. And we need a way to store info about free pages. Combine them into a single structure with lots of overloaded members.

Certainly one could store it in the same structure, perhaps in fields that are used for other things, though that should be thought out well in order to prevent debugging hell if something goes wrong. Besides that, if a page is free you basicly have 4k of space available to describe that, as long as you store it on the page, that memory isn't used anyway. What I wanted to point out in the original post is that it is worth it looking for ways to reduce the "permanent" footprint of the mechanism used for allocating pages. In the post before it it was suggested that since it is most likely small in comparison to other data stored by the memory manager it isn't worth looking at ways to reduce it, which is simply not true.

davidv1992 wrote:In the post before it it was suggested that since it is most likely small in comparison to other data stored by the memory manager it isn't worth looking at ways to reduce it, which is simply not true.

A Linux page struct is about 48 bytes, an OSX page struct is around 64 bytes per page. Considering that a bitmap requires 1 bit per page, a stack 4 bytes per page and a double-linked list 8 bytes per page it is unfortunately true.

If you can find some fields in the page struct to overload you can choose your allocation method without any regard for the amount of memory it uses. It comes for free. When memory use doesn't matter you only need to consider speed, fragmentation and other fun things.

Combuster wrote:

FlashBurn wrote:Correct me if I´m wrong, but in a tree it is O(log n) and not constant, because it depends on the height and the height depends on the number of nodes. So your algorithm isn´t O(1).

The tree has a fixed predefined maximum height that does *not* depend on the actual amount of memory present (~22 on an i386), therefore it is technically valid to claim O(1) performance.

But with this argumentation is every algorithm (which runs on a pc with memory which is not endless) O(1). At the point where you need a different number of steps for a different number of items to achieve your goal it can´t be O(1).

But with this argumentation is every algorithm (which runs on a pc with memory which is not endless)

a fixed predefined maximum height that does *not* depend on the actual amount of memory present

Combuster, perhaps you should have said O(22) then.

O(address bits) = constant

Something about reading?

Yeah, I read this, but you need a different number of steps for allocating/deallocating a page if the memory is fragmented and when it is not fragmented, aren´t you?

Look at your algorithm and see the many if´s, it can´t be O(1), because you need a different number of steps for different situations. A stack is O(1), because you always need the same number of steps.

davidv1992 wrote:The fact that it is in the kernel will guarantee that almost everything that isn't used on every interrupt will probably not reside in the cache on first access anyway, so the cache argument is moot

Allocating large amount of frames would. As you pop new values from stack, you're increasing the stack pointer constantly, it's most likely that you will cross a page border sooner or later.

The amount of memory you save because the amount of data on the stack is smaller is moot because that memory isn't used for anything else anyway.

I do not understand your point. "It isn't used for anything else"? Speak for yourself, I would rather use it for storage cache. And 1 page *is* smaller than 2^32*4 bytes.

Furthermore you make the argument that a maximum of 512 fragments on physical memory is enough.

Stated empirically. It's rare that I see more than 3 fragments. I'm testing it for a while.

...in which case your system fails horribly.

Where did you get that from?!? First: you can use more space for fifo, second: if this occurs, it calls defragmenter and/or swapper. If you can't write a swapper of your own, your implementation will fail horribly, I agree on that.

This all combined with the fact that it is a far more complex system than the other two I would strongly recommend against using it.

Don't like it, don't understand it, so don't use it.

FlashBurn wrote:Another problem is, how will you allocate 4mb or 2mb pages?

Write your own page allocator to solve, this has nothing to do with it, as it is a frame allocator (article on physical memory, remember?). It does not solve the problem of woc either. The page allocator rely on a frame allocator, not backwards.

And I always thought page and frame were equivalent in this context

cyr1x,OSwhatever: I apologize, our teacher at the university said too much times (names differ on purpose). I thought it's a well known thing, although I wasn't 100% sure, that's why I wrote "physical memory" instead of "frame" on title. Now that I read your comments, I reread the AMD64 and the Intel64 manuals again, and they do not refer physical page as frame. It was my university only thing I guess, sorry. I wonder what it's called in Nelson's book.

EDIT: checked other documents as well, and that's interesting: all that's in my native language refers physical pages as frames consistently (I mean with the english word "frame"). English documents don't, they mix them.