OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Nov 21, 2019 5:34 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 93 posts ]  Go to page Previous  1, 2, 3, 4, 5 ... 7  Next
Author Message
 Post subject: Re: Article on physical memory management
PostPosted: Sun Aug 14, 2011 10:30 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
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).


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 2:11 am 
Offline
Member
Member

Joined: Mon Jul 05, 2010 4:15 pm
Posts: 539
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.


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:03 am 
Offline
Member
Member

Joined: Thu Jul 05, 2007 8:58 am
Posts: 222
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.


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:08 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9287
Location: On the balcony, watching the Swedish Chef
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.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:08 am 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
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.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:10 am 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
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. :D

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:38 am 
Offline
Member
Member

Joined: Thu Jul 05, 2007 8:58 am
Posts: 222
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.


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:57 am 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
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.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 4:01 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
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).


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 4:33 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9287
Location: On the balcony, watching the Swedish Chef
Quote:
But with this argumentation is every algorithm (which runs on a pc with memory which is not endless)
Quote:
a fixed predefined maximum height that does *not* depend on the actual amount of memory present


Quote:
Combuster, perhaps you should have said O(22) then.
Quote:
O(address bits) = constant


Something about reading?

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 5:21 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
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.


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:23 pm 
Offline
Member
Member
User avatar

Joined: Tue Feb 08, 2011 1:58 pm
Posts: 496
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.

Quote:
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.

Quote:
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.

Quote:
...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.

Quote:
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.


Last edited by turdus on Mon Aug 15, 2011 3:42 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:34 pm 
Offline
Member
Member
User avatar

Joined: Tue Feb 08, 2011 1:58 pm
Posts: 496
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.


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 3:42 pm 
Offline
Member
Member

Joined: Tue Aug 21, 2007 1:41 am
Posts: 207
Location: Germany
And I always thought page and frame were equivalent in this context #-o :roll:


Top
 Profile  
 
 Post subject: Re: Article on physical memory management
PostPosted: Mon Aug 15, 2011 4:14 pm 
Offline
Member
Member
User avatar

Joined: Tue Feb 08, 2011 1:58 pm
Posts: 496
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 93 posts ]  Go to page Previous  1, 2, 3, 4, 5 ... 7  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group