Kernel Traffic #77 For 24 Jul 2000

since I've heard some rumours of you folks having come up with nice VM ideas at USENIX and since I've been working on various VM things (and experimental 2.5 things) for the last months, maybe it's a good idea to see which of your ideas have already been put into code and to see which ideas fit together or are mutually exclusive. :)

To start the discussion, here's my flameba^Wlist of ideas:

2.4:

1. re-introduce page aging, my small and simple experiments seem to indicate that page aging takes *less* cpu time than copying pages to/from highmem all the time (let alone making your applications wait for disk because we replaced the wrong page last time)
2. fix the latency problems of applications calling shrink_mmap and flushing infinite amounts of pages (mostly fixed)

3. separate page replacement (page aging) and page flushing, currently we'll happily free a referenced clean page just because the unreferenced pages haven't been flushed to disk yet ... this is very bad since the unreferenced pages often turn out to be things like executable code

   we could achieve this by augmenting the current MM subsystem with an inactive and scavenge list, in the process splitting shrink_mmap() into three better readable functions ... I have this mostly done

4. fix balance_dirty() to include inactive pages and have kflushd help kswapd by proactively flushing some of the inactive pages _before_ we run into trouble
5. implement some form of write throttling for VMAs so it'll be impossible for big mmap()s, etc, to competely fill memory with dirty pages

Other things to consider:

1. The page aging loops need to have early break-out when the number of free pages suddenly increases (exit, munmap, whatever);
2. The page stealer shouldn't block just because kswapd is blocked on synchronous swapping (this comes for free if we have separate page flushing)
3. shrink_dentry should probably skip inodes which have still got pages attached, as otherwise we get a lot of unnecessary cache flushes
4. We MUST quantify the current VM pressure as a way of controlling page aging. That way aging can be proactive under load, but we don't necessarily have to evict pages from memory too early (we can age pages without flushing them).
5. RSS accounting needs to be audited. Right now, the per-mm rss isn't an atomic type, and it doesn't seem to be consistently protected by the page table locks.

A few other ideas Ben and I threw about are much more long-term.

1. We think it should be possible to share page tables for large shared mmaps (think of libc and big sysv shm segments).
2. We can do reverse pte maps pretty cheaply by the following:
   1. Reverse maps for shared mmaps are easy enough by following the per-inode vma list
   2. The pte for unshared anon pages can be encoded in the page struct easily.
   3. Shared anon pages are the tricky ones; but it's simple to maintain a hash list of all such ptes, and there aren't many in a typical system. Fork() is, of course, the one place where lots of these occur, but we can minimise the number of shared anon pages over fork by implementing COW on page tables (that way, we share the page tables but NOT the pages!)
3. Think about having a list of all page tables in memory. With that, we can do aging in the VM without *EVER* having to walk through vmas at all: we can walk through the ptes in the system performing atomic bitops on the ptes and age counts without caring about the higher level layers until a given page's age reaches zero. Only at that point do we care about invoking the swapper for that page's vma.

Food for thought. 3) in particular seems to open up a whole new set of possibilities, but it's definitely something for an experimental post-2.4 branch. :-)

1. Make a ->flush method in the address_space operations, Rik mentioned it in some previous mail, it should return the number of pages that it has flushed. That would make shrink_mmap code (or its successor) more readable, as we don't have to add new code each time that we add a new type of page to the page cache.
2. This one is related with the FS, not MM specific, but FS people want to be able to allocate MultiPage buffers (see pagebuf from XFS) and people want similar functionality for other things. Perhaps we need to find some solution/who to do that in a clean way. For instance, if the FS told us that he wants a buffer of 4 pages, it is quite obvious how to do write clustering for a page in that buffer, we can use that information.
3. We need also to implement write clustering for fs/page cache/swap. Just now we have _not_ limit in the amount of IO that we start, that means that if we have all the memory full of dirty pages, we can have a _big_ stall while we wait for all the pages to be written to disk, and yes that happens with the actual code.

The following books contain some information on NTFS but this is not their primary focus:

Windows NT/2000 Native API Reference
by Gary Nebbett
Macmillan Technical Publishing USA
ISBN 1-57870-199-6

Inside Windows NT Second Edition
by David A. Solomon
Microsoft Press
ISBN 1-57231-677-2

The macmillan book is quite a handy reference if you are doing NT/2000 programming. The microsoft book is not too deeply technically involved but it is a good overview of how NTFS works.

The kernel OOM killing issue is never going to be solved properly because it would have to be sentient to do so. So no amount of argument/debate will yield the omnipotent killing algorithm, and as such it will always suffer from doing the wrong thing, and pissing people off.

Therefore, since some people WANT OOM killing to be done, and others such as myself do NOT want it to be done, could someone in the know of doing so, please make it a compile time or run time tunable option? I'd like to tell my kernel "If an OOM condition occurs, under absolutely *NO* circumstances are you to EVER kill a running process".

I am *NOT* asking for this to be the default option, nor am I asking that everyone else use it. I *FULLY* understand the need to have a system like we have right now FOR SOME SYSTEMS, however my system does not need it, and I suspect many other desktop systems do not either. I'd rather have the application that is hogging memory DIE than everything on my system by some "smart" algorithm.

It's trivial for any user to bring the system to an unusable state:

for(;;) malloc(1);

...and boom! In 15 seconds there's no more inetd, logins, http, etc :(

Per-user resource limits will avoid monkeys from doing that stuff.

Unfortunately only 2.6 kernel will have this feature, but distribution vendors will probably use a backported version for 2.4.

Linux per-user resource limits are called "user beancounters", and you can find a development version at http://www.asplinux.com.sg/install/ubpatch.html. Currently there is only kernel-level code.

A userlevel PAM module is needed to make it usable for real systems.

SGI's CSA (http://oss.sgi.com/projects/csa, no code available yet) is a similar, but more complete per-user resource accouting scheme which will be ported to Linux in the future.

I wonder what happened of the AIX approach: define a new signal (they called it SIGDANGER AFAIK), ignored by default, and send this signal to _all_ processes a few seconds before starting to SIGKILL processes.

This moves the policy completely to user space (i.e. The Right Thing). You can either have a daemon listening to this signal and deciding by configuration what and how to kill, or you can implement a handler for graceful exit in suitable applications, or both. Make the "few seconds" tunable by sysctl and all is perfect. You can even implement the following: when a process explicitly ignores the special signal (and has an appropriate capability?), cause it to never be killed. That would be for X servers and session managers.

The first time your program asks for a little bit of memory, malloc() goes and asks the kernel for a bunch of memory: tens of K at least, maybe more. This is because it wants to minimize the number of memory blocks, the number of syscalls, and the amount of memory fragmentation.

Now when malloc() asks for that memory, the kernel doesn't mark it as in-use, and it doesn't assign it a place in real storage. Instead, it maps it into the VM tables as unwritable memory. When someone writes to the memory (first storage into the new memory), the kernel traps; it realizes that the memory is now _really_ in use, so it marks it as such. This optimization lets my piggy program ask for a megabyte of memory, only use a few bytes of it, and not waste a bunch of real RAM. (I do waste some VM, but that doesn't matter unless your system has real memory for all or nearly all of the addressable memory: 4 GB on ia32.)

Now imagine a running system: each program has a bunch of memory overcommitted. Right before the OOM event, RAM and swap are full with in-use pages. Now one program tries to access one of its allocated but unused pages. The kernel traps, tries to map the page into memory, and fails.

Now what process should the kernel kill? The naive answer is the one that caused the trap. But what if you've got a process with a memory leak that happens to eat all the memory, then just before it grabs the last bit of memory, the kernel schedules another process which touches one of its overcommitted pages. What if that unfortunate process is, say, syslogd or something critical like that?

System fall down go boom.

The right solution is resource accounting, which is coming to a kernel near you sometime next year.

If you look lower down in do_boot_cpu(), this is used as a diagnosis of a boot failure (the check at phys_to_virt(8192)). If we don't find the signature, we know the CPU failed to start, if we do find it, we know it started but got stuck somewhere after the switch to protected mode.

In the latter case, the CPU could happily have trashed the trampoline code before disappearing off into hyperspace, so it makes sense to set it up anew each time.

This was actually almost certainly due to a _really_ simple improvement.

As of test4-pre4, the default time-slice for a normal process is just 50ms, while it used to be 200ms.

200ms is way too long a timeslice when working with interactive things: it's easily noticeable. 50ms should be much better.

If people wondered why the "->priority" -> "->nice" change was done, now you know. "->priority" used to be a tick-based nice level, and it just wasn't able to handle UNIX semantics when the resolution of ticks dropped to just a few ticks.

Simple vulcan mind-trick. Switch them around, and instead of calculating "nice" from the number of ticks, we calculate ticks from the virtual nice value, making the problem go away and allowing for a shorter timeslice without having to do major surgery.

if (HZ < 200):

nice -20: 11 ticks
nice -19: 10 ticks
nice -18: 10 ticks
nice -17: 10 ticks
nice -16: 10 ticks
nice -15: 9 ticks
nice -14: 9 ticks
nice -13: 9 ticks
nice -12: 9 ticks
nice -11: 8 ticks
nice -10: 8 ticks
nice -9: 8 ticks
nice -8: 8 ticks
nice -7: 7 ticks
nice -6: 7 ticks
nice -5: 7 ticks
nice -4: 7 ticks
nice -3: 6 ticks
nice -2: 6 ticks
nice -1: 6 ticks
nice 0: 6 ticks
nice 1: 5 ticks
nice 2: 5 ticks
nice 3: 5 ticks
nice 4: 5 ticks
nice 5: 4 ticks
nice 6: 4 ticks
nice 7: 4 ticks
nice 8: 4 ticks
nice 9: 3 ticks
nice 10: 3 ticks
nice 11: 3 ticks
nice 12: 3 ticks
nice 13: 2 ticks
nice 14: 2 ticks
nice 15: 2 ticks
nice 16: 2 ticks
nice 17: 1 ticks
nice 18: 1 ticks
nice 19: 1 ticks

Same number of ticks. The nice 10 one gets scheduled more eagerly, though (ie the "nice" level does more than just determine the number of ticks: it is also used to determine relative priorities if two processes have the same number of ticks to run).

In 2.5.x we'll probably make the timer run at a higher rate, making this issue go away, but for 2.4.x this was the expedient way to maintain UNIX semantics and get good interactive behaviour.

I have to agree with Richard here. If we do this, it'll set back 2.4 by at least month (and I may be conservative here). There will *always* be more places where we can do more/better fine-grained locking. Where indeed do we draw the line, and do we really want to be doing this while we're at 2.4.0-test*?!?

If we were still accepting stuff like this, we shouldn't have moved the verison number to 2.3.99 or 2.4.0testn.

We'll end up living with 2.4.x for two years or more, judging by past performance, and we'll have especially driver writers that concentrate on the 2.4.x stuff for a long time.

Having driver interface inconsistencies like that is nasty, and the ones we _know_ that we'll have should be minimized.

This is another reason why the open/read/write/close series is particularly important to get done first: it's the stuff every driver tends to do. Things like "fasync" is less critical because even if it is used a lot by drivers, it tends to use the helper routines (so drivers often do not need to worry over-much about locking).

This shoul dhave been the last locking issue, though. We scale too well for words.

I agree.

This was what I wanted for the 2.2 -> 2.4 change too, and a much shorter development cycle would be wonderful. It obviously was not to be: 2.4 is already about 18 months out. We're not as bad as the 2.0 -> 2.2 cycle was, but it's painful.

It seems to be a lot harder than it should be to keep short development releases. I certainly haven't found the magic combination yet. 2.4.x is definitely all I hoped for (the big goal for me was to make sure that the mindcraft-like web-performance scalability problems would be gone, and we definitely fixed that), but it took much too long.

What would help would be more modular releases: smaller pieces of the kernel getting released independently, allowing for smaller and shorter release cycles. In Linux at least we don't have the "whole world" release issue that most other OS people have (including the free ones: I think the BSD "world" approach is horrible partly because of the release issues), but even just the kernel is so big that it would be nice to be able to see it as multiple independent projects.

At the same time it's obviously not true that there are independent projects, and especially drivers (which _sound_ independent) are very likely to be impacted quite a lot by infrastructure changes. There are no really clear lines to split development up by, and the cures are worse than the disease ("microkernels", I hear somebody shout. But that approach would just make it impossible to do the kinds of improvements we _have_ done and probably will continue to do).

a central kernel repository is so nice: most of the time when something changes, we can fix everything in one go, and people don't have to be all that aware of the changes. It's not always true: some of the VFS changes (namely the page cache write-through etc) were _so_ intrusive that it was hard to make the fix-ups available, and as a result a number of filesystems were left in a broken state.

And quite often the "grep for places to change" approach misses a few (this, btw, is why I've grown to love the new syntax for structure initializers: it's a h*ll of a lot easier to do a "grep 'release:' *.c" than it is to try to figure out where the different "release" entries are initialized).

But the fact that we need a big kernel repository right now does not necessarily mean that we'll need one forever. With good enough interfaces that people can truly feel happy about, it would be possible to split stuff up one day. That is, after all, how the system call interfaces work, and is what allows us to split the kernel from everything else.

Of course, usually what is "good enough" one day ends up being "really bad" the next when some clever bastard came up with the really good way of doing something..

In another five or ten years, we may be at the point where the fundamental interfaces _really_ don't change, and that we've handled all the scalability issues and that we have no need to add new interfaces. At THAT point we can just say "ok, drivers are truly independent".

It's not true today.

Basically, the thing that allows 2.4.x to scale as well as it does (and it does really well: look at the current SpecWeb99 world record numbers, and compare it to the also-ran second place), is exactly because we had all the source in one place, and we _could_ make fundamental changes. Claiming anything else is silly - if we had broken-up device drivers, we'd have been up shit creek without a paddle. End of story.

This is the thing that people don't understand. In theory it is wonderful to have modularization. It's the best thing on earth. But if that modularization means that you can't fix the module interfaces, then you're going to remain broken for all time.

This is why I rather fix module interfaces early and often. Make sure that we (a) have good interfaces that matches what the different parts of the kernel want to have and (b) make people used to the fact that a driver or a filesystem is not a static thing, and keep them aware of the fact that it depends on the kernel underneath it.

We're certainly getting closer to a good interface in many areas. The current VFS interfaces, for example, are pretty good - although many of the less important ones still depend on the kernel lock etc. But we're _not_ at the stage yet where we could just say "ok, a driver is a driver, and we don't need to worry about it".