Linux Kernel Maintainability: Bees Can't Fly

but a Hurd of them might go Mach speed...

From Beth Richardson

Answered By Jim Dennis, Jason Creigton, Benjamin A. Okopnik, Kapil Hari Paranjape, Dan Wilder, Pradeep Padala, Heather Stern

Hello,

I am a Linux fan and user (although a newbie). Recently I read the paper entitled "Maintainability of the Linux Kernel" (http://www.isse.gmu.edu/faculty/ofut/rsrch/papers/linux-maint.pdf) in a course I am enrolled in at Colorado State University. The paper is essentially saying that the Linux kernel is growing linearly, but that common coupling (if you are like me and cannot remember what kind of coupling is what - think global variables here.) is increasing at an exponential rate. Side note, for what it is worth - the paper was published in what I have been told is one of the "most respected" software journals.

I have searched around on the web and have been unable to find any kind of a reply to this paper from a knowledgeable Linux supporter. I would be very interested in hearing the viewpoint from the "other side" of this issue!

Thanks for your time, Beth Richardson

[JimD] Basically it sounds like they're trying to prove that bees can't fly.

(Traditional aerodynamic theories and the Bernoulli principle can't be used to explain how bees and houseflies can remain aloft; this is actually proof of some limitations in those theories. In reality the weight of a bee or a fly relative to air density means that insect can do something a little closer to "swimming" through the air --- their mass makes air relatively viscous to them. Traditional aerodynamic formulae are written to cover the case where the mass of the aircraft is so high vs. air density that some factors can be ignored.).

I glanced at the article, which is written in typically opaque academic style. In other words, it's hard to read. I'll admit that I didn't have the time to analyze (decipher) it; and I don't have the stature of any of these researchers. However, you've asked me, so I'll give my unqualified opinion.

Basically they're predicting that maintainance of the Linux kernel will grow increasing difficult over time because a large number of new developments (modules, device drivers, etc) are "coupled" (depend on) a core set of global variables.

[Jason] Wouldn't this affect any OS? I view modules/device drives depending on a core as a good thing, when compared to the alterative, which is depending on a wide range on varibles. (Or perheps the writers have a different idea in mind. But what other alterative to depending a core would there be other than depending on a lot of things?)

[Ben] You said it yourself further down; "micro-kernel". It seems to be the favorite rant of the ivory-tower CS academic (by their maunderings shall ye know them...), although proof of this world-shattering marvel seems to be long in coming. Hurd's Mach kernel's been out, what, a year and more?

[Kapil] Here comes a Hurd of skeletons out of my closet! Being a very marginal Hurd hacker myself, I couldn't let some of the remarks about the Hurd pass. Most of the things below have been better written of elsewhere by more competent people (the Hurd Wiki for example, http://hurd.gnufans.org) but here goes anyway...

The Mach micro-kernel is what the Hurd runs on the top of. In some ways Hurd/Mach is more like Apache/Linux. Mach is not a part of the Hurd. The newer Hurd runs over the top of a version of Mach built using Utah's "oskit". Others have run the "Hurd" over "L-4" and other micro-kernels.

The lack of hardware and other support in the existing micro-kernels is certainly one of things that is holding back the common acceptance of the Hurd. (For example neither "mach" nor "oskit" have support for my video card--i810--for which support came late in the Linux 2.2 series).

Now, if only Linux was written in a sufficiently "de-coupled" way to allow the stripping away of the file-system and execution system, we would have a good micro-kernel already! The way things are, the "oskit" guys are perenially playing catch-up to incorporate Linux kernel drivers. Since these drivers are not sufficiently de-coupled they are harder to incorporate.

[JimD] This suggests that the programming models are too divergent in some ways. For each class of device there are a small number of operations (fops, bops, ioctl()s) that have to be supported (open, seek, close, read, write, etc). There are relatively few interactions with the rest of the kernel for most of this (which is why simple device driver coding is in a different class from other forms of kernel hacking).

The hardest part of device driver coding is getting enough information from a vendor to actually implement each required operation. In some cases there are significant complications for some very complex devices (particularly in the case of video drivers; which, under Linux sans framebuffer drivers, are often implemented in user space by XFree86.)

It's hard to imagine that any one device driver would be that difficult to port from Linux to any other reasonable OS. Of course the fact that there are THOUSANDS of device drivers and variants within each device driver does make it more difficult. It suggestst the HURD needs thousands (or at least hundreds) of people working on the porting. Obiviously, if five hundred HURD hackers could crank out a device driver every 2 months for about a year --- they'd probably be caught up with Linux device driver support.

Of course I've only written one device driver for Linux (and that was a dirt simple watchdog driver NAS system motherboard) and helped on a couple more (MTD/flash drivers, same hardware). It's not so much "writing a driver" as plugging a few new values into someone else's driver, and reworking a few bits here or there.

One wonders if many device drivers could be consolidated into some form of very clever table-driven code. (Undoubtedly what the UDDI movement of a few years ago was trying to foist on everyone).

[Kapil] One the other side Linux "interferes too much" with user processes making Hurd/Linux quite hard and probably impossible---but one can dream...

[JimD] Linux was running on Mach (mkLinux) about 5 years ago. I seem to recall that someone was running a port of Linux (or mkLinux) on an L4 microkernel about 4 years ago (on a PA RISC system if I recall correctly).

It's still not HURD/Linux --- but, as you say, it could (eventually) be.

Linux isn't really monolithic, but it certainly isn't a microkernel. This bothers purists; but it works.

Future releases of Linux might focus considerably more on restructing the code, providing greater modularity and massively increasing the number of build-time configuration options. Normal users (server and workstation) don't want more kernel configuration options. However, embedded systems and hardware engineers (especially for the big NUMA machines and clustering system) need them. So the toolchain and build environment for the Linux kernel will have to be refined.

As for features we don't have yet (in the mainstream Linux kernel): translucent/overlay/union filesystems, transparent process checkpoint and restore, true swapping (in addition to paging, might come naturally out of checkpointing), network console, SSI (system system image) HA clustering (something like VAX clusters would be nice from what I hear), and the crashdump, interactive debuggers, trace toolkit, dprobes and other stuff that was "left out" of 2.5 in the later stages before the feature freeze last year.

I'm sure there are things I'm forgetting and others that I've never even thought of. With all the journaling, EAs and ACLs, and the LSM hooks and various MAC (mandatory access contol) mechanisms in LIDS, SELinux, LOMAC, RSBAC and other patches, we aren't missing much that was ever available in other forms of UNIX or other server operating systems. (The new IPSec and crypto code will also need considerable refinement).

After that, maybe Linux really will settle down to maintenance; to optimization, restructuring, consolidation, and dead code removal. Linus will might find that stuff terminally boring and move on to some new project.

[JimD] What else is there to add the kernel?

[Pradeep] Like my advisor says, Every thing that is never thought before. Lot of people feel the same about systems research. I am planning to specialize in systems. What do you guys think about systems research? Is is as pessimistic as Rob Pike sounds? http://www.cs.bell-labs.com/who/rob/utah2000.pdf

[Dan] Some would say, "streams". (he ducks!)

[JimD] LiS is there for those that really need it. It'll probably never be in the mainstream kernel. However, I envision something a like a cross between the Debian APT system and the FreeBSD ports system (or LNX-BBCs Gar or Gentoo's source/package systems) for the kernel.

In this case some niche, non-mainstream kernel patches would not be included in Linus' tarball, but hooks would be found in a vendor augmented kbuild (and/or Makefile collection) that could present options for many additional patches (like the FOLK/WOLK {Fully,Working} OverLoaded Kernel). If you selected any of these enhancements then the appropriate set of patches would be automatically fetched and applied, and any submenus to the configuration dialog would appear.

Such a system would have the benefit of allowing Linus to keep working exactly as he does now, keeping pristine kernels, while making it vastly easier for sysadmins and developers to incorporate those patches that they want to try.

If it was done right it would be part of UnitedLinux, Red Hat, and Debian. There would be a small independent group that would maintain the augmented build system.

The biggest technical hurdle would be patch ordering. In some cases portions of some patches might have to be consolidated into one or more patches that exist solely to prevent unintended dependency loops. We see this among Debian GNU/Linux patches fairly often --- though those are binary package dependencies rather than source code patch dependencies. We'd never want a case where you had to include LiS patches because the patch maintainer applied it first in his/her sequence and one of its changes became the context for another patch --- some patch that didn't functionally depend on LiS but only seemed to for context.

I think something like this was part of Eric S. Raymond's vision for his ill-fated CML2. However, ESR's work wasn't in vain; a kbuild system in C was written and will be refined over time. Eventually it may develop into something with the same features that he wanted to see (though it will take longer).

As examples of more radical changes that some niches might need or want in their kernels: there used to be a suite of 'ps' utilities that worked without needing /proc. The traditional ps utils worked by walking through /dev/kmem traversing a couple of data structures there. I even remember seeing another "devps" suite, which provided a simple device interface alternative to proc. The purpose of this was to allow deeply embedded, tightly memory constrained kernels to work in a smaller footprint. These run applications that have little or no need for some of the introspection that is provided by /proc trees, and have only the most minimal process control needs. It may be that /proc has become so interwoven into the Linux internals that a kernel simply can't be built with out it (that the build option simply affects whether /proc is visible from userspace). These embedded systems engineers might still want to introduce a fair number of #defines to optionally trim out large parts of /proc. Another example is the patch I read about that effectively refines the printk macro as a C comment; thus making a megabyte (uncompressed) of prink()' calls disappear in the pre-processor pass.

These are things that normal users (general purpose servers and workstations) should NOT mess with. Things that would break a variety of general purpose programs. However, they can be vital to some niches. I doubt we'll ever see Linux compete with eCOS on the low end; but having a healthy overlap would be good.

[JimD] Are there any major 32 or 64 bit processors to which Linux has not been ported?

[Ben] I don't mean to denigrate the effort of the folks that wrote Hurd, but... so what? Linux serenely rolls on (though how something as horrible, antiquated, and useless as a monolithic kernel can hold its head up given the existence of The One True Kernel is a puzzle), and cooked spaghetti still sticks to the ceiling. All is (amazingly) still right with the world.

[Jason] You know, every time I get to thinking about what the Linux kernel should have, I find out it's in 2.5. Really. I was thinking, Linux is great but it needs better security, more than just standard linux permissions. Then I look at 2.5: Linux Security Modules. Well, we need a generic was to assign attributes to files, other then the permission bits. 2.5 has extened attribues (name:value pairs at the inode level) and extended POSIX ACLs.

[Ben] That's the key, AFAIC; a 99% solution that's being worked on by thousands of people is miles better than a 100% solution that's still under development. It's one of the things I love most about Linux; the amazing roiling, boiling cauldron of creative ideas I see implemented in each new kernel and presented on Freshmeat. The damn thing's alive, I tell ya.

[Kapil] What you are saying is true and is (according to me) the reason why people will be running the Hurd a few years from now!

The point is that many features of micro-kernels (such as a user-process running it's own filesystem and execution system a la user-mode-linux) are becoming features of Linux. At some point folks will say "Wait a minute! I'm only using the (micro) kernel part of Linux as root. Why don't I move all the other stuff into user space?" At this point they will be running the Hurd/Linux or something like it.

Think of the situation in 89-91 when folks on DOS or Minix were jumping through hoops in order to make their boxes run gcc and emacs. Suddenly, the hoops could be removed because of Linux. The same way the "coupled" parts of Linux are preventing some people from doing things they would like to do with their system. As more people are obstructed by those parts---voila Linux becomes (or gives way to) a micro-kernel based system.

Didn't someone say "... and the state shall wither away".

[Heather] Yes, but it's been said:

"Do not confuse the assignment of blame with the solution to the problem. In space, it is far more vital to fix your air leak than to find the man with the pin." - Fiona L. Zimmer

Problems as experienced by sysadmins and users are not solely the fault of designs or languages selected to write our code in.

...and also:

"Established technology tends to persist in the face of new technology." - G. Blaauw, one of the designers of System 360

...not coincidentally, at least in our world, likely to persist inside "new" technology, as well, possibly in the form of "intuitive" keystrokes and "standard" protocols which would not be the results if designs were started fresh. Of course truly fresh implementations take a while to complete, which brings us back to the case of the partially completed Hurd environment very neatly.

[JimD] Thus any change to the core requires an explosion of changes to all the modules which depended upon it. They are correct (to a degree). However they gloss over a few points (lying with statistics).

First point: no one said that maintaining and developing kernels should be easy. It is recognized as one of the most difficult undertakings in programming (whether it's an operating system kernel or an RDBMS "engine" --- kernel). "Difficult" is subjective. It falls far short of "impossible."

Second point: They accept it as already proven that "common" coupling leads to increasing numbers of regression faults (giving references to other documents that allege to prove this) and then they provide metrics about what they are calling common coupling. Nowhere do they give an example of one variable that is "common coupled" and explain how different things are coupled to it. Nor do they show an example of how the kernel might be "restructured with common coupling reduced to a bare minimum" (p.13).

So, it's a research paper that was funded by the NSF (National Science Foundation). I'm sure the authors got good grades on it. However, like too much academic "work" it is of little consequence to the rest of us. They fail to show a practical alternative and fail to enlighten us.

Mostly this paper sounds like the periodic whining that used to come up on the kernel mailing list: "Linux should be re-written in C++ and should be based on an object-oriented design." The usual response amounts to: go to it; come back when you want to show us a working prototype.

[Jason] Couldn't parts of the kernel be written in C, and others in C++? (okay, technically it would probably all be C++ if such a shift did occur, but you can write C in a C++ compiler just fine. Right? Or maybe I just don't know what I'm talking about.)

[Pradeep] There are many view points to this. But why would you want to rewrite parts of it in C++?

Popular answer is: C++ is object-oriented, it has polymorphism, inheritance etc. Umm, I can do all that in C and kernel folks have used those methods extensively. The function pointers, gotos may not be as clean as real virtual functions and exception handling. But those C++ features come with a price. The compilers haven't progressed enough to deliver the performance equivalent to hand-written C code.

[Dan] At one point, oh, maybe it was in the 1.3 kernel days, Linus proposed moving kernel development to C++.

The developer community roundly shot down the idea. What you say about C++ compilers was true in spades with respect to the g++ of those days.

[Pradeep] What is the status of g++ today? I still see a performance hit when I compile my C programs with g++. Compilation time is also a major factor. g++ takes lot of time to compile especially with templates.

[JimD] I'm sure that the authors would argue that "better programming and design techniques" (undoubtedly on their aggenda for their next NSF grant proposal) would result in less of this "common" coupling and more of the "elite" coupling. (Personally I have no problem coupling with commoners --- just do it safely!)

As for writing "parts" of Linux in C++ --- there is the rather major issue of identifier mangling. In order to support polymorphism and especially function overloading and over-riding, C++ compilers have to modify the identifiers in their symbol tables in ways that C compiler never have to do. As a consequence of this it is very difficult to link C and C++ modules. Remember, loadable modules in Linux are linkable .o files. It just so happens that they are dynmically loaded (a little like some .so files in user space, through the dlopen() API --- but different because this is kernel space and you can't use dlopen() or anything like it).

I can only guess about how bad this issue would be but a quick perusal of the first C++ FAQ that could find on the topic:

http://users.utu.fi/sisasa/oasis/cppfaq/mixing-c-and-cpp.html

... doesn't sound promising.

[JimD] I'm also disappointed that the only quotations in this paper were the ones of Ken Thompson claiming that Linux will "not be very successful in the long run" (repeated TWICE in their 15 page paper) and that Linux is less reliable (in his experience) than MS Windows.

[Jason] I'm reminded of a quote: "Linux is obsolete" -- Andrew Tanenbaum. He said this in the (now) famous flame-war between himself and Linus Torvalds. His main argument was the micro-kernels are better than monolithic kernels and thus Linux was terribly outdated. (His other point was that linux wasn't portable.) BTW, I plan to get my hands on some Debian/hurd (Or is that "GNU/hurd"? ) CDs so I can see for myself what the fuss over micro-kernels is all about.

[JimD] Run MacOS X --- it's a BSD 4.4 personality over a Mach microkernel.

(And is more mature than HURD --- in part because a significant amount of the underpinnings of MacOS X are NeXT Step which was first released in the late '80s even before Linux).

[Ben] To quote Debian's Hurd page,

Do toss out a few bytes of info if you do download and install it. I'm not against micro-kernels at all; I'm just slightly annoyed by people whose credentials don't include the Hard Knocks U. screaming "Your kernel sucks! You should stab yourself with a plastic fork!" My approach is sorta like the one reported in c.o.l.: "Let's see the significant benefits."

[JimD] These were anecdotal comments in an press interview --- they were not intended to be delivered with scholastic rigor. I think it weakens the paper considerably (for reasons quite apart from my disagreement with the statements themselves).

What is "the Long run?" Unix is a hair over 30 years old. The entire field of electronic computing is about 50 or 60 years old. Linux is about 12 years old. Linux is still growing rapidly and probably won't peak in marketshare for at last 5 to 10 years. Thus Linux could easily last longer than proprietary forms of UNIX did. (This is not to say that Linux is the ultimate operating system. In 5 to 10 years there is likely to be an emerging contender like EROS (http://www.eros-os.org ) or something I've never heard of. In 15 to 20 years we might be discussing a paper that quotes Linus Torvalds as saying: "I've read some of the EROS code, and it's not going to be a success in the long run."

(We won't even get into the criteria for "success" in Ken Thompson's comment --- because I think that Linux' current status is already been a huge success by the standards of it's advocates and to the chagrin of it's detractors. By many accounts Linux is already more "successful" than UNIX --- having been installed on more systems than all UNIX predecessors combined --- an installation base that is only recently rivaled by MacOS X in the UNIX world)

Meet the Gang   1   2   3