Is virtual memory becoming obsolete?

[Brendan]

Hi,

So the question is, what would you gain by shifting the VMM into user space?

The flexibility to implement different VMM policies for different apps in the same system. I guess you could characterize this as one of the main goals of an exokernel, but not necessarily of a microkernel. As I said myself recently, flexibility is only an end in itself if you're a gymnast.

You could seperate policy from the low level code and implement the low level code (functions to map a page, allocate/free a physical page, send a page to swap, etc) and a "default" policy in the kernel. That way software that cares can use it's own policy and the kernel's low level code, software that doesn't care can use the default policy, and the kernel itself can use it's own internal code for IPC, etc.

I'm not too convinced by the flexibility argument though. IMHO the only reasonable place for flexibility in a VMM is in the code that decides which page/s are swapped out. For e.g. a mostly inflexible VMM with default "select a page to swap out" code, where software that cares can use it's own policy for choosing pages to swap out.

Of course I haven't thought about this much - I guess my goal is help you to find and clearly define your "why"...


Cheers,

Brendan

[mystran]

As I see it, the problems that self-paging attempts to solve are twofold: [...]

Adding a swapping mechanism to a microkernel isn't really hard. What is hard, is trying to come up with a policy, that doesn't involve a pager in kernel, and doesn't require unbounded kernel memory usage. If you have unbounded memory usage, then you might need to free pages for kernel use, which is the real problem, if you try to avoid having a default pager in kernel.

Having a default pager in kernel is a problem, if you want to have your swap driver in userspace, 'cos while mandating that all processes must trust the default swap driver is fine, your kernel also needs to trust on an userspace process now, which is not nice.

While allowing apps the provide hints to VMM is one option, that doesn't solve certain problems. Suppose I have a database, which caches information in memory. Suppose futher that the in-memory cache uses a structure optimized for memory access, while the on-disk version is optimized for disk access, and conversion between the two is relatively cheap.

In such case, it makes no sense at all to use normal paging: if the in-memory version is written to page file, then it'll have to be loaded for memory later, just to store it again to disk in a different format. It might be cheaper to simply store to the on-disk format directly, and reconstruct the in-memory version later if necessary.

Or suppose I have a game, which stores models using spine-surfaces, but breaks them into regular polygon meshes with level-of-detail before use, and caches some amount of the processed meshes in memory to avoid disk access. Now there's little point to store the processes meshes to disk at all, and they are probably larger than the original on-disk version too. So if more memory is required, it's better to just throw them away, and reconstruct later. Since they are just cache, we might not even need them at all.

I can try to think of better examples too, if you want, but I think you get the point: applications know what is worth saving. Applications also know HOW the data should be saved. By forcing the use of a generalized pager, you might end up doing extra work.

In my OS, the difficulty I have with VMM in general is that I want to put most of the VMM policy outside the ukernel to keep the kernel simple, but I also want to support fast IPC via page mapping, which doesn't work since the VMM server is supposed to be aware of which process owns which pages at all times (but the kernel itself implements IPC).

Personally, I'm not really interested in trying to keep the ?kernel small to make it more simple; I'm more interested in trying to avoid forcing a certain policy. I want to be able to support several policies, running at the same time, at the same system, without kernel having to care.

I suspect that putting the VMM in the kernel is a better idea, but I want to keep my kernel as small as possible. Without swapping, that VMM policy would be much simpler and could easily go in the kernel, but I also suspect that the need for swapping is not going away any time soon.

Well, I'm going to keep my VMM in kernel, but after thinking about current directions and possibilities, I think I'm going to drop the idea of swapping too; just allocate physical memory (possibly with some quotas) as long as there's some. Once there's no more, just tell that to applications.

I am going to support some form of self-paging though, because it really doesn't need much support from kernel: you just need to let the process handle the page fault, and manage it's own mappings. So the only real questions are whether I'm going to somehow support process swap-out (reduce resident pages of inactive processes) and shared memory (which introduces a nasty amount of new problems).

Lot of systems seem to be moving away from shared memory lately, instead concentrating on efficient message passing. Things like copy-on-write are also easier to do fast, if shared memory need not be taken care of.

I'm thinking about dropping (logically) shared memory as well since it seems to be mostly trouble. I especially liked the point Singularity folks made:

A big problem with share memory is that if one process crashes, then the other process can't really tell what's the state of the memory, so in many cases the best it can do is just crash as well.

And thinking about it, in most cases that don't require crashing both processes at the same time, you'll be essentially using the shared memory as a fast substitute of message passing, in which case efficient copy-on-write optimized large messages would suffice just fine. In fact, I can think of several nice tricks that are easier to do with them than normal shared memory.

[mystran]

That's debatable... L4 does a pretty good job of keeping VMM policy in user-space without sacrificing too much performance.

The amount of performance L4 sacrifices is debatable. The IPC performance is pretty good, so running a monolith like Linux as a singleserver won't sacrifice too much performance. Or does it?

Consider that for true benefits from having a microkernel, you want to run a multiserver system on top of it, not just a port of a monolith. When you build multiserver on top of L4, you'll notice that you need to add a lot of application level overhead to implement any form of security into the system.

Slightly slowing down the IPC path by adding a capability based security system there, would greatly reduce application level overhead, and thus improve system performance. I think some of the later L4 versions do this.

Also, L4 native model doesn't really scale, because synchronous IPC doesn't really scale. You need a separate thread for each outstanding operation. This isn't such a problem for clients, but it's potentially a huge problem with servers. Threads are heavyweight enough that you don't want a few thousand threads simply because you have a few thousand client requests blocked on local resources.

Ofcourse you can simulate asynchronous IPC with synchronous one, but it introduces again more overhead, and can be problematic if there's issues of mutual trust.

Finally, L4 memory management doesn't really scale either: the hierarchical scheme has the problem that once the kernel runs out of the memory reserved for maintaining such mappings, it must refuce futher mappings, since it can't reclaim memory (which was all given to sigma0).

This isn't a fatal problem though, because there's an easy way out: require that applications know how to rebuild mappings later, and simply destroy older mappings. But it does introduce some overhead anyway. I've never bothered to check whether L4 does use this method.

So there are quite a few things about L4, which seem beatiful at first, but do have performance consequence external to the kernel itself.

[Colonel Kernel]

IMHO the only reasonable place for flexibility in a VMM is in the code that decides which page/s are swapped out. For e.g. a mostly inflexible VMM with default "select a page to swap out" code, where software that cares can use it's own policy for choosing pages to swap out.

I agree in principle, but I have a hard time seeing the boundary between mechanism and policy when it comes to virtual memory management. If you view virtual memory systems as a kind of cache, then it makes sense that the only real policy decision is which items to evict from the cache when it gets full. However, this analogy only goes so far because of the existence of multiple processes. Suddenly you have the distinction between "global" and "local" replacement policies, which then affects the mechanisms themselves in a big way.

For example, NT uses page buffering in its memory manager, and basically has a local replacement policy based on a working set model with periodic adjustments of the process working set sizes. This goes far beyond the fact that it uses the "clock" algorithm to select pages to evict. I can easily imagine how to encapsulate something like the "clock" algorithm, but the "local replacement + working set" thing is policy tightly entwined with mechanism. I see no easy way to encapsulate these kind of details, short of an external VMM (not just an external swapper).

In other words, I see this flexibility issue as almost an all-or-nothing proposition -- either you've got it, or you don't. The question then becomes -- how much is this flexibility worth in the real world? I certainly don't know. :-\

[Colonel Kernel]

Adding a swapping mechanism to a microkernel isn't really hard.

Maybe not "hard" like "NP-complete"-hard, but more like "it's not obvious to me at the time I wrote my post"-hard.

While allowing apps the provide hints to VMM is one option, that doesn't solve certain problems.

I have my doubts about this... see below.

Suppose I have a database, which caches information in memory. Suppose futher that the in-memory cache uses a structure optimized for memory access, while the on-disk version is optimized for disk access, and conversion between the two is relatively cheap.

You're stepping into quicksand because I work on database engines for a living.

In such case, it makes no sense at all to use normal paging: if the in-memory version is written to page file, then it'll have to be loaded for memory later, just to store it again to disk in a different format. It might be cheaper to simply store to the on-disk format directly, and reconstruct the in-memory version later if necessary.

This is a non-problem, as a DBMS will typically lock the pages of its cache in memory. I suppose this implies that the DBMS has more permissions than a typical application, but that's not unreasonable since DB boxes tend to be dedicated to that purpose (as long as things like custom stored procedures run in a different security context ).

Or suppose I have a game, which stores models using spine-surfaces, but breaks them into regular polygon meshes with level-of-detail before use, and caches some amount of the processed meshes in memory to avoid disk access. Now there's little point to store the processes meshes to disk at all, and they are probably larger than the original on-disk version too. So if more memory is required, it's better to just throw them away, and reconstruct later. Since they are just cache, we might not even need them at all.

This is solveable with conventional virtual memory. Take a look at the VirtualAlloc() function in Win32. One of the flags you can pass to it is MEM_RESET, which basically clears the dirty bits of any PTEs in a given region. You can store these "transient" data structures in such a region and reset it when they are not in use. That way, the region will never be written out to the page file, but if the OS needs more memory it may take the pages in that region. The next time you read the region, you'd get all zeroes, and then you'd know to rebuild your data structures.

I can try to think of better examples too, if you want, but I think you get the point: applications know what is worth saving. Applications also know HOW the data should be saved. By forcing the use of a generalized pager, you might end up doing extra work.

As I've shown, this extra work can be avoided with locking and resetting of VM regions. I can also think of plenty of mundane examples of apps that are perfectly happy with a default paging policy -- word processors, spreadsheets, web browsers, etc... In other words, the stuff that regular users run 99% of the time.

To me, there is a difference between the intents of virtual memory and self paging -- virtual memory is supposed to be truly invisible (hence the virtual), while self-paging is supposed to give these special-case applications more control over their own physical memory usage. I don't believe that it's necessary or even sensible to make the such special-case resource management as transparent as regular virtual memory.

[earlz]

I voted no

I think that it would be useful if their was a way to like have kernel level paging but be able to override/modify it at the application level
like maybe have something that you could say DoNotSwap(..) and Swap(..) and Neutral(..) with neutral being like, it don't matter as far as speed so if you need memory you can take it from there
and DoNotSwap being lowest priority for swapping but actually still swappable like say if you were running something in the foreground and it needed memory for DoNotSwap data or just any data it would take priority over the less used background task


but anyway thats my 2 cents

[mystran]

Colonel Kernel:

If you are locking all pages in to the memory, you are essentially disabling the virtual memory. So then you need no VMM at all, and if there's any, it's overhead at best.

And special settings like "locked" or "resetable" introduce quite a bit of speculative overhead if you try to use them for dynamic policies. If you can statically mark certain set of pages once, then it's ok, but if your predictions can change several times each second, or more often...

I could think of reasons to use special paging in a word processor as well, btw, but those aren't important because everybody's gonna use Word independent of how well it works.

Personally I think the most boring way to use paging hardware is to use it for giving everybody an "essentially infinite address space". Such things are really non-goals for my kernel in any case. Libraries solve them if they're really needed.

[Colonel Kernel]

If you are locking all pages in to the memory, you are essentially disabling the virtual memory. So then you need no VMM at all, and if there's any, it's overhead at best.

That's a strange argument. We were talking about a particular example -- a DBMS. In this case, the only pages that it would lock would be in its data cache. There's no reason to lock pages in the other running processes, with one exception...

In a ukernel drivers need to lock pages for DMA anyway. I don't see what the big deal is about it. Pretty much every OS in use today has this feature.

And special settings like "locked" or "resetable" introduce quite a bit of speculative overhead if you try to use them for dynamic policies. If you can statically mark certain set of pages once, then it's ok, but if your predictions can change several times each second, or more often...

Can you give examples of such dynamic policies? My textbooks basically stop at the "clock" algorithm.

I could think of reasons to use special paging in a word processor as well, btw, but those aren't important because everybody's gonna use Word independent of how well it works.

Are word processors really that performance-critical like databases and games are...? Just because you can optimize the heck out of something doesn't mean you should.

[earlz]

actually I use openoffice with great joy

[JoeKayzA]

If you are locking all pages in to the memory, you are essentially disabling the virtual memory. So then you need no VMM at all, and if there's any, it's overhead at best.

And what about offering a seperate allocator for 'cache memory'? This could be basically the same that can be used for software disk caches, for example. The only difference to a 'traditional' page-level allocator is that you allocate reclaimable memory, and the system will notify an application when it needs memory back, so the app can do some quick steps to free it and the give it back. This would be perfectly suitable for caching in your game-engine example, and it could also be used for implementing a user level paging mechanism. What do you think?

cheers Joe

[mystran]

Can you give examples of such dynamic policies? My textbooks basically stop at the "clock" algorithm.

I can think of a few that benefit from application level knowledge.

Garbage collectors are one classic example. The garbage collector typically touches a lot more memory than is really the working set, and typically touches it in a somewhat unrelated order too. For compacting collector, it would be beneficial to collect and compact first, then only page out the compacted heap if more memory is still required. You'd want to keep resetable anything that doesn't currently have any important data. This is much cheaper to do in the collector than in the VMM system.

I'm also going to argue again, that DBMS is only one example of where the best way to manage cache is to forget about general VMM. Basicly any application that optimizes performance with caches, is potentially going to do a better job by just dealing it's own memory, insteading of having a general VMM to interfere.

And yes, there are other reasons to lock pages too: basicly anything that is trying to meet any kinds of realtime goals is going to want to lock it's pages into memory.

[mystran]

And what about offering a seperate allocator for 'cache memory'? This could be basically the same that can be used for software disk caches, for example. The only difference to a 'traditional' page-level allocator is that you allocate reclaimable memory, and the system will notify an application when it needs memory back, so the app can do some quick steps to free it and the give it back.

Well, most self paging systems where system does reclaim space, basicly works by system notifying the process that it needs some memory, and giving it a deadline by which it must free something. Sure, you can have system tell the application "I think this is good page to free".

[earlz]

intresting find....
in the EXE document i found these intresting flags for sections

Code: Select all

IMAGE_SCN_MEM_DISCARDABLE 0x02000000 Section can be discarded as needed.
IMAGE_SCN_MEM_NOT_CACHED 0x04000000 Section cannot be cached.
IMAGE_SCN_MEM_NOT_PAGED 0x08000000 Section is not pageable.

so i won't need to implement special functions after all into the application library/kernel interface