Kernel Traffic #76 For 17 Jul 2000

It can't be that hard to recompile the module for 2.4.0 even for L*cent engineers. There might be some slight changes necessary at the places where the module interfaces the kernel, but that should be a work of a couple of minutes. As they stole code from serial driver, probably only the changes there need to be redone ...

(And I wonder, whether they have a written statement by Ted that allows them to use the serial code with a license different from GPL?)

No, they don't have a such a statement from me, and I've already let them know that they're in violation of the GPL. Lucent was *supposed* to have split the propietary code into its own .o file, and kept released the Linux glue code as a .c. This solves the GPL problem, since the user is doing the linking....

I think they should have released a version that you should be able to compile for 2.4.0; I'm surprised that hasn't happened yet.

closing a file descriptor of another process context is a serious task - one could probably write a 200-page book about it and still not know how to do it quite yet.

Anyway, of course, your simple module has serious problems:

1. POSIX (and probably non-POSIX) locks subsystem needs rewrite before one can release locks from non-current context.
2. you bravely access p->files without any locking - that is broken
3. you need not emulate put_unused_fd() for non-current context - this is the *very* reason why I wrote __put_unused_fd() to allow passing p->files as a parameter (of course caller needs to lock files->file_lock) which you do not do, btw.

I spent about 3 weeks working on these (and related) issues and had to write a separate filesystem to overcome the various problems. It should be available late July.

You could write another module called munmap.o and another fchroot and another fchdir and another catch_rights_dgram_in_flight.o or if you see what I mean :)

I think the discussion circles around three problems, which are similar in appearance, but quite different in the possible solutions. Let me attempt a classification:

A) hide resource unavailability from a process

This is the "tell process to go elsewhere while ejecting the floppy" case. May be generalized (with some difficulty) to more general fd replacement. I think there are four possible cases:

1) process/fd is idle, can be removed/changed just by changing pointers

2) fd is busy (system call in progress) but we can just wait for the operation to terminate (maybe prod it a little)

3) fd is not busy, but process is doing something that may make it undesirable to mess with its fds (e.g. it's in the middle of exit(2) or close(2))

4) fd is in the middle of an operation that won't come back anytime soon

I'm afraid there aren't many cases of 2), and the prodding may get a little difficult for, say, NFS, so whenever the fd is busy, we probably must assume 4). 3) may simply mean that whenever the process is in the kernel, nothing should happen to it. 3) of course also covers 4), but one may special-case the latter. (After all, we may need this function just because we're in case 4). 1) is too good to be true and of little hack value.

For 4), I can imagine the following two approaches:

a) add a layer that allows a clean split between the process and the driver side of an fd, e.g. by handing all requests to some proxy process. May be slow.

b) hackish, but probably quite efficient: by splicing the thread of execution at the process/driver boundary: driver operation returns immediately, while the still-running driver operation gets a new return address that makes the result evaporate. I think it would be interesting to see if somebody could come up with a clean solution for such a beast ;-)

In both cases, it seems natural to hook the code that maintains the separation into VFS, as a new file system. This would limit things to regular files and directories, but that's probably okay at the beginning. Also, in either case, any access to "current" from the driver side would drastically complicate things.

B) de-access a resource (fd) to allow removal of device

There are again several flavours of this:

1) process is killable and nobody cares, so kill it

2) process should not be killed, so we have to try to close the fd (and hope it doesn't get angry), or replace it with something else

3) process stubbornly refuses to die (e.g. it's blocked in an access to the reource we want to get rid of)

4) like 3), but the block is because of something else (e.g. we want to umount the partition with the log file of the backup process that is currently hung in the tape driver)

For 2), any solution from A) should be suitable. 1) is again trivial. That leaves us with 3) and 4), which are essentially the same. The goal is simply to make that system call return.

Since we're likely in the middle of a driver and may have accumulated an unknown amount of state (e.g. locks, driver flags, etc.), this probably can't be solved from outside the driver. Since we should be in an uninterruptible sleep at this time (anything else would be a serious bug that needs to be fixed no matter what is done about the issues discussed here), the obvious solution seems to be to teach drivers to allow interruption of uninterruptible sleeps. Maybe with a special new signal and, sigh, a new task state.

C) counter denial of service attacks based on keeping devices busy This is a combination of B with counter-measures to keep hostile code from thwarting the initial counter-measure. Some scheduler or kill tricks may be the most efficient way to deal with all such kinds of arms races. (E.g. write a kill(2) that accepts a list of "good" processes, and atomically delivers the signal to all others.)

Of course, A) and B) could be combined. Also, some instrumentation could be added to A) to allow the process doing the replacement to retrieve the exact state of an fd.

A) seems to be the hardest thing to do, particularly if performance is an issue. If performance is a non-issue, one could use some kind of demon that looks like NFS, Coda, or such, and spawns a thread for each IO operation. If we want to revoke an fd, the demon could simply open the substitute, continue working on that, and discard the result of any pending operation as soon as it comes back (if ever). 100% user space.

Solving B) would solve a large class of user-visible problems. Since there may not be all that many TASK_UNINTERRUPTIBLE sleeps that cause problems in real life, it should be feasible just to put the infrastructure in place, and to fix things when a problem is found. I.e. no major code review required.

I'll leave C) to another thread ;-)

I have the damn 1999 ISO C draft. I know full well that a "legal" compiler can put 42 chars of padding after everything and, just for fun, make every type be 101 bits wide.

Moderately portable code assumes a sane compiler and sane hardware. You may assume:

1. The "char" type is 8 bits. It might be unsigned though. :-/
2. sizeof(short) == 2
3. sizeof(int) == 4 (for real Linux, not the 8088 hack)
4. sizeof(long) == sizeof(void *)
5. (sizeof(long) == 4) | (sizeof(long) == 8)
6. sizeof(long long) == 8 (good for 10 years at least)
7. You can freely cast between any two pointer types
8. You can freely cast between long and any pointer type
9. (long)(int*)(long)foo == (long)(char*)(int*)(long)foo
10. signed integers are represented in two's complement form
11. integers wrap around instead of causing faults
12. assuming "good" struct layout, padding only occurs at the end
13. ... that padding won't happen if you supply a multiple of 16 bytes

One can define "good" struct layout as being an order that puts items with the largest natural alignments first. For example, an array of 6 shorts has a natural alignment of 4 bytes. I suppose you could define natural alignment as gcd(16,sizeof(foo)).

Every day I work with a system that violates rule 9. From experience, I assure you that it is a mess to deal with. Casting gets really nasty. There is no hope of porting Linux to this system.

I've just tested your patch on 2.2.17pre9 + andrea's GFP-race-fix-3. It seems smart about which process to kill, and I can no longer hang my system with mmap. I even tried several simultaneous mmap + malloc (hang guaranted without the patch). I saw cool messages about mmap and malloc being killed, preserving other processes such as syslogd and init.

Although I'm not for killing hungry processes, I think in this case this is better than letting all the system die (or at least hang for hours). But I don't know what this will lead to for daemons which use lots of mmaps.

we are a group of programmers designing, writing and extending audio+MIDI (and in some cases, video) applications for Linux. As you could tell from the list of signees below, we represent the developers of many significant and substantial audio+MIDI applications for Linux, as well as members/employees of several well known music and audio research institutions and companies.

(If you want to get an overview of the current state for audio+MIDI under Linux, there is no better source than Dave Phillip's magnificently comprehensive web site http://www.bright.net/~dlphilp/linuxsound/).

One member of our group, Benno Senoner, did a lot of work last year in investigating and documenting problems involved in using Linux for real-time audio applications. Others, such as Juhana Sadeharju, had long noted problems using Linux for hard disk recording of audio data. Partly as a result of Benno's work, Ingo Molnar did a fantastic job of coming up with a patch for the 2.2 series that dramatically improved the latencies that could be obtained from Linux.

How good? Well, good enough that members of our community who were convinced that RTLinux was needed to do a professional job with audio changed their minds. Good enough that we were close to (or sometimes better than) BeOS, an OS that has had a lot of excellent press in the audio world as a replacement for the known-to-be-problematic Windows and MacOS systems. Good enough that in some cases, Linux is as good as dedicated hardware solutions, offering latencies in the realm of 2-3ms for our applications.

There was a lot of excitement that 2.4 might include a version of the low latency patches. The excitement came from the possibility that the next release of the various distributions of Linux would represent a set of "desktops" that were ready for excellent, "real-time" audio and MIDI applications. CPU and disk performance has improved to the point where we are on the threshold of a revolution in the way that sound synthesis and processing is done, and many of us want to ride Linux into the heart of that revolution.

However, it turns out, as best we can gather, that you were not happy with the basic structure of some or all of Ingo's low latency work. Our impression is that you want to see more careful code design that avoids interrupt disabling or holding high level locks for too long, rather than using preemption points. So, as far as we can tell right now, 2.4 will represent more of the same as far as low latency limitations, and for us, more of the same means performance much worse than Windows or MacOS present.

How much worse ? Linux currently offers worst-cases latencies that are *10-15* times worse than Windows or MacOS. Developers for those platforms still complain about their performance with respect to latency - imagine their response to the situation with Linux as it stands today!

We understand that we could try to maintain a version of Ingo's low latency patches in parallel to the current kernel. But this is not a good situation for us. We would like to persuade several companies that produce applications and API's for audio+MIDI work to make their code, designs and programs available for Linux. We would like to be able to produce our own "real-time" applications and not have to tell users (who will likely know nothing about Linux, or computers in general) that they need to patch their kernel before using them. Neither of these goals are realistic given the current state of low latency support in the emerging 2.4.

We would like to know:

• what are your general feelings on modifying Linux to support the kind of applications we are concerned with ?
• what kinds of compromises, if any, you might accept in order to get good low latency performance into the kernel sooner, rather than later ?
• what design goals you have in mind when you talk about doing low latency "right", rather than "wrong, as in Ingo's approach" ?
• to what extent are you willing to enter into a debate about the merits of a preemption-point-based approach to lowering kernel latency ?

Above all, we are all interested in having fun with Linux and audio/music/MIDI. We would invite you to come tour a professional studio, watch the cool and wonderful stuff that can be done right now (with lots of annoying problems) on machines that runs Windows and MacOS, and get a sense of the extent to which general purpose computers are about to replace a whole bunch of expensive stuff sitting around in a typical studio. We want to see penguins there, and soon!

Several of the signees below have noted that lowering latency improves the quality of games, most kinds of multimedia and many non-hard-real-time automated systems. Incorporating a low-latency patch could be seen as extremely helpful in providing competitive performance in areas outside of audio as well.

Thank you for your consideration, for Linux and your benign dictatorship.

*I* was unhappy with the structure of that patch to begin with. The patch is ugly and unacceptable (read: a kludge) for inclusion into the mainstream kernel, period. I also said that i'll send a similar patch for 2.4 as well, once the 2.4 codebase stabilizes. (right now we still have a high flux of fixes coming in - but i'll soon port the patch to 2.4)

so please, do not make this appear as some 'fault' of Linus. Linus is rightfully (and thankfully) watching the quality of the mainstream kernel, and ugly patches are simply not accepted, regardless of the usefulness of a given patch. In fact it's my fault of not submitting those patches in a saner way. I'll fix this in the coming weeks.

Paul and the others in favor of the low latency fixes are fond of pointing out that they must be good because this is how IRIX and BeOS solve the problem. That's never a good reason to do anything - fortunately for all of us, Linus evaluates things on their technical merits. And "IRIX does it" has no technical merit whatsoever.

I and others have pointed out that if you need hard real time then what you do is use RT Linux and you can get exactly what you need. I've heard two arguments against this:

1. ``Other operating systems offer "soft realtime" and we don't want to port our code from that to the RT Linux model.'' Translation: ``other operating systems have made poor design decisions, let's try and pressure Linus into doing the same thing with Linux.'' That's a poor approach to the problem. Just saying that NT does it does not make it right. Linux has a large, quickly growing, market share. In my opinion, it is better to do the right thing, wait until Linux is the market leader, and then laugh at the screwed up systems that made the wrong choices. Screwing up Linux so it has the same problems that other systems have in the name of portablility is not the Linux way.
2. ``If we take the RT Linux path then Linus will never add the low latency features we want.'' I love this argument. It implies knowledge that there is a better way, that if you use the better way then there is no need to do what Linus doesn't really want to do. Exactly.

In fairness to the low latency application people, I think that the RT Linux folks need to provide skeleton "apps" that show how to solve problems in the RT Linux space. Whether that happens or not, the RT Linux approach is really brilliant and it is the right approach to the problem space, and I'm more than a little sick of hearing people avoid using it. Get with the program, folks, use the best tool for the job. No matter what Ingo does, it is a _fact_ that you can not get both good performance for a multi user time sharing operating system and real time applications.

Please understand that it might be that some of Ingo's work is a good thing and that it will go into the kernel. I am not sure about that one way or the other. What I am sure about is that putting features into the kernel for the benefit of real time applications is a slippery slope that just leads to bad change on top of bad change. It effects the scheduler, the I/O paths, the interrupt handling, and probably a bunch of other places I'm forgetting. The changes are at direct odds with time sharing performance and the proponents of the changes will argue each one in isolation, rather than looking at the effects of all of them.

My advice, heeded or not, is to just say no. We have an excellent answer for realtime, it's called RT Linux. Go use it - it's better than any other answer.

Just to clear up my opinion a bit:

• I'm definitely not against low latency. I think latency is hugely important, mostly more so than throughput (within reason, of course: all this is very much a balancing issue).
• I'm not even against well-defined and well-thought-out "scheduling points". They are hackish, but if there is one or two of them to cover some specific behaviour then that's ok. Not a big deal.
• I _am_ against patches whose only purpose in life is to run some arbitrary benchmark, and try to make that benchmark look good.

Most of the low-latency patches I've seen have been of the third kind, I'm afraid.

For example, I would probably accept a patch that adds a simple

if (current->need_resched) schedule();

to the case of generic_file_write/generic_file_read. Why? Because that case is a real-world case where it's obvious that with huge caches a normal user can quite simply cause bad latencies, and this is not an issue that needs all that much discussion - it's an obvious hack, but is't also equally obvious why it's there, and what the point of it is. We've had a few of these before: I think the /dev/null driver already does exactly this.

In fact, because we should look at the "UP threading code" for 2.5.x anyway (ie using the spinlocks on UP to generate a fairly well-threaded UP kernel without any source modifications), the one-liner if-statement should probably be a #define with a simple-to-grep-for name so that it can be easily removed.

Why just "probably"? A few reasons:

• I suspect that especially if we generate such a macro, people will start sprinkling it around at various random places. And I do not want such a simple hack to spread out any more than necessary. One or two places are fine. So is four. Numerous places in the networking code, device drivers and filesystems doing it is _not_. At that point it has gone from a very specific and slightly tasteless hack to an ugly architecture.

  This could probably be avoided by giving it a clear comment and a discouraging name.

• I do think the "copy_to/from_user()" case is the cleaner one, but I'd hate to do the test in-line, and I'd hate to do it all over the place. And if we do it in copy_to/from_user(), we don't do it _anywhere_ else: again the difference is one between a slightly tasteless hack, and a ugly rule of life.

  This is the more complex case, and requires more careful code in <asm/uaccess.h>. The "generic" arbitrarily-sized functions should probably be moved out-of-line into arch/xxx/lib/uaccess.c, because that test is no longer worth doing inline. Together with benchmark runs.

See? "slightly tasteless" and "strictly localized" are ok. Anything more hackish than that is not.

I personally would rather see that nobody ever needed RTlinux at all. I think hard realtime is a waste of time, myself, and only to be used for the case where the CPU speed is not overwhelmingly fast enough (and these days, for most problems the CPU _is_ so overwhelmingly "fast enough" that hard realtime should be a non-issue).

I definitely agree with low-latency requirements even in a standard Linux. I just disagree violently with doing them with horrible cludges instead of working on doing it right.

_if_ there are truly hard guarantee requirements, RTLinux is the way to go.

The number of problems that really need RT-linux is practically zero for normal uses. This is, btw, why I've never applied the RTLinux patches to the standard kernel tree. My personal opinion is that the RTLinux patches should _not_ be available by default, so that only people who really need the functionality start using it.

Having non-hard-RT users start using the RTLinux functionality would be a disaster, in my opinion. The programming-interfaces are much more cumbersome, and the ways of making the system lock up hard are many and varied.

If you do a computer-controlled radiation-dose machine for treating patients, and the latency guarantees have to be in the sub-100ms range, THEN you should use RTLinux.

If you're doing just audio that needs approximately 1% fo the CPU resources, and you have to use hard-realtime, the system needs work. Using RTLinux is a way of saying "oh, we can't fix this properly".

NOTE: I'm fully aware of the fact that Linux needs improvment in this area. I've tried to explain that my beef with the low-latency patches has never been that I don't believe it is a worthy goal. It's just that I also firmly believe that there are right ways of doing this. Without ugly patches that add random stuff to random places.

I guess the problem I have is that I don't see a clean way to make sure that no high latency events ever creep into the kernel. I'm 100% in agreement with the idea that all code paths through the kernel should be short and sweet, but that isn't always the case. All it takes is one misbehaving driver that hangs onto the CPU too long and you missed your deadline.

I'm not a fan of realtime either but I hate half assed realtime creeping into a time sharing kernel - everything I know personally or have read about says that this is a bad idea.

Given all that, if you want to take a Linux box and use it to drive a pile of devices with hard guarentees (think factory floor, CNC devices, mixers, lots of stuff that is currently done in ASICs), then you need a better answer than Linux gives, even with the Ingo patches.

I can apply the obvious stuff today. But it would need to be a clean patch, and I suspect that the only part that I would consider truly obvious would be the user copy part. And adding a test for "need_resched" does imply not inlining them any more, it's already border-line, and the re-scheduling makes it obviously so (by the time you can potentially call "schedule()", the compiler has to save/restore all the call-clobbered registers anyway, so 90% of the advantages of inlining have been destroyed, making the disadvantages like icache footprint etc clear).

Note that regardless of _what_ the problem is, I always prefer incremental patches anyway. Maybe people in the end can convince me that every single scheduling point makes 100% sense, and is not a hack at all but a natural thing. Even if that were the case, I'd like to get the thing in smaller and explainable pieces..

Maybe its just that I'm too philosophical and you're too pragmatic. I can see 2 possibilities from here:

1. your revulsion at "random" scheduling points is a really strong belief that would likely make convincing you of the value of each particular point impossible,
2. you you accept the idea that there may need to be a bunch of "random" scheduling points for this to work, and whilst you consider this ugly, you accept that there isn't much of an alternative. people will have to have a lot of good numbers to convince you to apply a patch that adds a scheduling point.

Do either of these sound like a reasonable summary of your position, or is there some other precis?

I _am_ pragmatic. That which works, works, and theory can go screw itself.

However, my pragmatism also extends to maintainability, which is why I also want it done well.

I want more than an explanation like "I ran our latency tester, and this point seemed to be really bad, so I added a scheduling point here".

For example, for the specific read/write user-copy code, I don't even need to get numbers. It's clear that with a machine that has tons of memory, and where the data is cached, we can generate a "read()" system call that spends quite a lot of time without needing any active re-scheduling. This is not a random point: it's something that can be clearly explained from the sources, and a case where there clearly is no better solution unless you fully thread the thing.

This patch does:

1. small fix to microcode driver - the "cc clobber" directive is not needed for cpuid instruction as it doesn't change EFLAGS. Neither it is needed in general in asm-i386/processor.h:cpuid() inline (this was pointet out by Philipp Rumpf but for some reason didn't appear in test3-preX)
2. amended comment in fs/inode.c:iput() to reflect the truth, i.e. it is not a "magic nfs path" but the fact that anonymous inodes are not put on unused list
3. documented the fact that for FS_SINGLE filesystems the driver must call kern_mount() after register_filesystem(). This already confused others (e.g. Richard Gooch) so imho it is worth pointing out.
4. kern_mount() is supposed to be used only with FS_SINGLE filesystems but the code doesn't enforce it. This patch makes kern_mount() fail with EINVAL on attempt to call it on non-FS_SINGLE filesystems.

I have spent the past five and one half weeks chasing down a severe memory corruption problem in the NWFS LRU. The problem I am reporting is what has caused ALL the bugs folks have seen over the past couple of months in NWFS with memory corruption. It's what's held up our next release by over two months. Despite screaming customers, I have held off on posting the next release until I understood clearly what was going on -- now I know -- Linux spinlocks() don't work when used by kernel modules in linux that include spinlock.h.

NWFS is fully multi-threaded and uses fine grained locking. Much of Linux is not fine grained, which would explain why I may be one of the few folks to first see this problem. Initially, I was under the assumption that the spinlocks() in Linux worked, and because of this, focused my attention on my own code rather than scrutinize the code in Linux. I rewrote large sections of NWFS, put in traps, and checks, list consistency routines, etc. It was not until I put in a check for multiple users being inside the same lock that I located the problem. Well, I have completed a very thorough analysis of generated IA32 code, and I have discovered something rather shocking, which is that the spinlock code in Linux is severely broken, and this is not due to a coding error, but a problem with the GCC compiler apparently generating garbage. There's also several issues with using "lock bts" instead of "xchg eax, 1", which is the recommended method for implementing spinlocks() on IA32 intel systems.

What's really scary here is that a great deal of new code has been written that depends on this spinlock code, and once the spinlock code gets fixed properly, we may see tons of deadlocks and lockups all over the place since this code has been there for a very long time.

The I/O bandwidth has greatly improved and I'm still trying to understand how can patch this simple be so effective. :)

Great work Roger!

I see this as the first (and most critical) step of returning my faith in good performing 2.4.0-final.

I have been following the latency issue for some time now and I am happy to report great strides have been taken in improving latency in the Linux 2.4.0-test2-pre? series of patches.

Here is a snapshot of some results that show promise! I hope to repeat them on an SMP system soon.

Benno Senoner's (sbenno at gardena dot net) latencytest used for these charts: See http://www.gardena.net/benno/linux/audio/latencytest-0.42.tar.gz for the source.

http://www.tux.org/~chessman/bench/latencytest/ has preliminary results with charts showing the differences when hdparm unmaskirq and 32bit are toggled.

I varied the hdparm 16/32 bit I/O and interrupt unmasking, and got a non intuitive result, better results for 16 bit I/O, unmasking disabled. Tonight I will run the test with the other two cases and see if it correlates to one of them.

System under test is a Dell GX1 400MHz PII IDE disk, running

• linux-2.4.0-test2-pre5
• mm/filemap.c patches from Andrew Morton dated Thu Jul 06 2000 - 23:21:48 EDT
• ALSA-driver 0.5.8b
• XFree86 Version 3.3.6 w/ Mach64, glx.o, agpart kernel module

All tests are showing greater than 99% +/- 2ms for the disk tests. The overruns appear to be mm related, Andrew's patch indicated sys_close() and sys_exit() still need attention.

This is getting close to usable for my purposes!

• Linus......... linux-2.4.0-test1
• Alan Cox...... linux-2.4.0test1-ac22-riel
• Rik van Riel.. mail sent to linux-kernel and linux-mm with a subject of "[PATCH] -ac22-riel++"