OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Mar 19, 2024 1:19 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 10:28 am 
Offline
Member
Member
User avatar

Joined: Fri Jul 16, 2010 7:46 am
Posts: 61
Location: Chicago
I discussed this on IRC briefly, but was still unsure about a few details with it.

I am trying to work out the merits and the disadvantages of having page frame allocation be handled by a userland process instead of by the kernel.

Off the top of my head, I would imagine that I would need a system call that would allow a process to invalidate a page/the page table, at minimum. It would also let the kernel be much smaller, and make memory handling within the kernel far simpler.

Does anyone have any input as to the advantages/disadvantages of this approach?


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 12:13 pm 
Offline
Member
Member
User avatar

Joined: Fri Jul 16, 2010 7:46 am
Posts: 61
Location: Chicago
One issue I do foresee is if the page manager needs another page, it would need to call itself... I suppose you could check to see if it is the page manager calling itself, and perhaps use static memory to handle its own allocations, though.


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 12:50 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

When you say "page frame allocation be handled by a userland process" do you mean the physical memory manager is implemented as a process in user-space; and each time anything else wants to allocate a physical page it costs you a minimum of 2 task switches (potentially including the "TLB trashing" overhead, etc)?

Do you mean the virtual memory manager is implemented as a process in user-space; and each time anything else wants to allocate a virtual page it costs you a minimum of 2 task switches (potentially including the "TLB trashing" overhead, etc plus the cost/hassle of mapping the paging structures into the virtual memory manager's address space)?

Or, did you mean "page frame allocation be handled in userland by each process"? In this case, if you mean physical memory management then it creates a huge synchronisation problem (how does each process know if/when each physical pages is free/allocated?).

If you mean each process handles it's own virtual memory management, then you'd need to figure out some way of making good "global" decisions. For example, if the OS is running out of memory, then you'd need to decide which page in any process is the best page to send to swap, which can be hard to do when each process only cares about itself.

Anyway, I'm not too sure what you're asking (and the IRC log didn't help me much - I only found "<Ameisen> i wonder if I can offload page allocation to a userland process")...


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 12:58 pm 
Offline
Member
Member
User avatar

Joined: Fri Jul 16, 2010 7:46 am
Posts: 61
Location: Chicago
I am referring to physical memory management, assigning actual physical memory to applications. For virtual memory, are you referring to things such as malloc, or are you referring to things like swapping and page tables? As for the former, of course the application can handle that as it sees fit. For the latter, that would be handled by this same module.

I am also referring to a single system process to handle this, not physical memory management per-process.


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 2:12 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Ameise wrote:
I am referring to physical memory management, assigning actual physical memory to applications. For virtual memory, are you referring to things such as malloc, or are you referring to things like swapping and page tables? As for the former, of course the application can handle that as it sees fit. For the latter, that would be handled by this same module.

I am also referring to a single system process to handle this, not physical memory management per-process.


I break "memory management" into 3 layers.

The first (lowest) layer is physical memory management, and includes allocating and freeing individual physical pages (but may also include support for allocating/freeing contiguous physical pages for DMA buffers, managing which areas of the physical address space are used for which memory mapped PCI devices, handling MTRRs, etc).

The next layer is virtual memory management, and includes allocating/freeing virtual pages and mapping/unmapping other stuff, and uses the physical memory manager as a "back-end". This can include support for swap space and memory mapped files, handling shared memory areas, managing PAT, creating/destroying virtual address spaces, etc.

The last (highest) layer is heap management. This is your "malloc()" and "free()" (or new/delete, or garbage collection, or whatever a process wants), and belongs in user-space (such that each process does it's own heap management, and different processes can do their own heap management in completely different ways). It uses the virtual memory manager as it's "back-end".

So, you're talking about a single system process that does both physical memory management and virtual memory management (and not heap). In that case, you're looking at a minimum of 2 task switches (potentially including the "TLB trashing" overhead, etc plus the cost/hassle of mapping the paging structures into the virtual memory manager's address space).

Other disadvantages would include scalability problems - e.g. imagine 32 CPUs all trying to use the same (multi-threaded?) single system process to allocate or free memory at the same time, possibly with expensive user-space re-entrancy locking (e.g. mutexes/futexes rather than spinlocks, because the process can't easily tell the scheduler "disable task switching until I release this lock").

I also think that "It would also let the kernel be much smaller, and make memory handling within the kernel far simpler." is misguided. It's exactly the same code shifted to a different place, with extra communication/isolation hassles. Basically, the kernel may be smaller and simpler, but the "sum of the parts" is larger and more complex.

The normal advantage of shifting things to user-space is that you can minimise risk (e.g. if it crashes in user-space you don't need to worry about kernel-space or the rest of the OS being trashed), but if your virtual and physical memory management crashes the OS is going to be screwed anyway, so "minimised risk" isn't an advantage in this case.

There's only 2 advantages I can think of. The first is that it'd be easier to debug (for e.g. if it tries to use an uninitialised pointer or something you've got a better chance of detecting the problem). The other advantage is that it'd be more flexible. For example, you wouldn't need to implement "kernel modules" and/or make the kernel open source to allow other people to change the physical/virtual memory manager.

Of course without knowing more about the OS it's hard to estimate how good/bad these advantages/disadvantages are. For example, for something like a single address space OS where everything runs at CPL=0, you wouldn't have the "TLB trashing" disadvantage (or the "easier debugging" advantage).

Also note that for the "heap management" stuff that is on top of this; most software pre-allocates a pool of memory to use and uses the pre-allocated pool for allocations; where the size of the pool is increased when the heap manager runs out of pre-allocated virtual memory and is decreased when there's "lots" of allocated virtual memory that isn't being used anymore. Usually the size of this "pool of pre-allocated virtual memory" is a compromise between wasting memory and the overhead of increasing/decreasing the size of the pool. Basically, if the virtual memory manager is fast then the size of the pool (for each process) can be small; and if the virtual memory manager has a lot of overhead then people writing user-space code will compensate by increasing the size of their pool (to reduce overhead by reducing the number of times they need to allocate/free virtual memory). The end result is that if the OS's virtual memory management is a lot slower, then it might have no effect on performance but increase the amount of RAM allocated/wasted instead.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 5:15 pm 
Offline
Member
Member
User avatar

Joined: Tue Jun 02, 2009 4:35 pm
Posts: 737
Location: Supporting the cause: Use \tabs to indent code. NOT \x20 spaces.
Ameise wrote:
One issue I do foresee is if the page manager needs another page, it would need to call itself... I suppose you could check to see if it is the page manager calling itself, and perhaps use static memory to handle its own allocations, though.


Everyone encounters this problem in one way or another: the solution is re-entrant locks. What happens if the frame allocator calls on the escrow service and the escrow just serviced another CPU, or some other thing happened and it was unable to reload?

A re-entrant lock allows the same thread to re-acquire the same lock as many times as it needs to. You can then have the frame allocator re-enter its own code to allocate a frame and return that to itself, and then life goes on as usual from there.

--All the best
gravaera

_________________
17:56 < sortie> Paging is called paging because you need to draw it on pages in your notebook to succeed at it.


Top
 Profile  
 
 Post subject: Re: Page Frame Allocation in Userland
PostPosted: Tue Mar 22, 2011 5:51 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
My memory manager looks like a 'normal process' to the kernel. It has a main, has access most of the c lib, makes system calls and calls normal posix 'open' and 'pread' to load executables and perform mmap, however it runs in the higher half in kernel space at ring 1. This provides some of the benefits that Brendan mentioned w.r.t debugging and ease of design (in my opinion) however it's not necessary to flush the TLB when switching from a user process to the the mm process because the mm (like the vfs and kernel) is mapped into every memory context.

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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 21 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