Kernel Traffic #25 For 1 Jul 1999

Hi Zack,

thanks for your work -- I find KT pretty useful when I don't have time to directly lurk lkml..

However, the last two week I *had* time to do so, and I find you somehow have totally censored the discussion on devfs issues. Now it's pratically extinct, but there have been quite a lot of shell exchanges between hpa, tytso and rgooch, with bits from Alan and others. Actually, some of the arguments in that discussion were pretty insightful. Was there a reason for you to censor that ? Are you one of the rigid anti-devfs people, and chose to silence that threads for this reason ? Or simply you lacked time for this (maybe in that case, it'd be better to say that you lacked time to follow this or that thread ; maybe that'll bring contributors in ! I understand following lkml is hard, making a good quality summary of it is much harder)

Anyway, thanks for the great work you're putting in KT.

--Cyrille

Anybody who is interested in FS performance should take a look at the latest pre-patch of 2.3.7 (only pre-6 and possibly later: do NOT get any earlier versions. pre-5 still causes file corruption, pre-6 looks good so far).

Careful, though: I fixed the problem that caused some corruption less than an hour ago, and while my tests indicate it all works fine, this is a very fundamental change. The difference to earlier kernels is:

• ext2 (and some other block device filesystems that have been taught about it) uses write-through from the page cache instead of having a separate buffer cache and the page cache to maintain dirty state. This means much less memory pressure in certain situations, and it also means that we can avoid unnecessary copies.
• the page cache has been threaded, so on SMP you can actually get noticeable speedups from processes that do concurrent file accesses.
• lower-latency read paths, especially the cached case.

Both of these are big, and fundamental changes. So don't mistake me when I say it is experimental: Ingo, David and I have been spending the last weeks (especialy Ingo, who deserves a _lot_ of credit for this all: I designed much of it, but Ingo made it a reality. Thanks Ingo) on making it do the right thing and be stable, but if you worry about not having backups you might not want to play with it even so. It took us this long just to make it work reliably enough that we can't find any obvious problems..

The interesting areas are things like

• writes to shared mappings now go blindingly fast. We're talking mondo cleanups here. We used to do really badly on this, now we do really well.
• does bdflush still do the right thing? There may be a _lot_ of tweaking to do to get everything working at full capacity.
• can people confirm that it is stable for everybody?
• if anybody has 8-way machines etc, scalability is interesting. It should scale to 8-way no problem. We used to scale to 1-way, barely. Numbers?
• fsync(). It doesn't work right now, but it should be easy to make it work well on big files etc - something we've never been able to do before (we used to lack the indexing from file to dirty blocks: now we have access to that quite automatically thanks to having the inode->page index in place, and the dirty blocks are right there)

and I'd really appreciate comments from people, as long as people are aware that it _looks_ stable but we don't guarantee anything at this point.

I dont think devfs *requires* to be mounted on /dev ... Someone correct me if im wrong.

1. If you want a physical /dev on the disk with 40,000 entries, disable the devfs compile option and create your physical /dev directory and populate it with 40,000 entries and all is well.
2. If you want a physical /dev dynamically populated by a userspace daemon, then compile devfs in, mount it on /devices and have a userspace daemon populate /dev and all is well.
3. If you want a fully dynamic devfs mounted on /dev, then compile it in and mount it on /dev and all is well.

Any questions?

I'm tired of going through the following routine:

1. Me: I think devfs should go in the kernel, because ...
2. DO: DEVFS SUCKS! It's a BAAAAAAD idea
3. Me: No, it allows you to do ...
4. DO: YOU CAN DO IT ALL IN USER SPACE
5. Me: Some things, yes, but not everything and not efficiently
6. DO: Put a small hack into the kernel and the rest in user space
7. Me: But then ... is hard/impossible
8. DO: Make the kernel hack bigger
9. Me: Now you've got something like devfs
10. DO: But you've got names and that's "policy", and I don't like yours
11. Me: So use devfsd and change them
12. DO: goto (4).

"DO" is Devfs Opponent.

Sigh. Over the past year and a half, I've noticed a distinct pattern. It seems impossible to make any progress in this argument, because so often, when I press on one point, demonstrating why devfs wins out, the argument is shifted to another point. After a while, the first point is suddenly popped up.

The kernel always has and always will dictate some policy. And we've always been able to build a structure on top of that which follows a different policy. Devfs+devfsd actually makes that easier.

And there's a lot to be said for the kernel providing a decent, human-friendly policy that is guaranteed to be there. It allows portable programmes to be written, without having to worry about what a particular distribution maintainer has put in /dev.

With devfs+devfsd a distribution can provide a structure which they think is logical and works well for them, and get compatibility for free.

I repeat (again):

The kernel provides access to devices, the kernel sets policy. To claim otherwise is folly.

The policy that devfs allows is:

1. more flexible
2. more robust
3. easier on troubleshooters
4. reliant on kernel code in fewer places
5. more elegant (IMHO)
6. independent of the root filesystem type

You may disagree with me on any of these particulars, but I want to see some sort of hard evidence that there is a better way. Like running code.

Just say no to it in the configuration and you get what you had before. devfs fits a lot of sizes very well, and you can turn it off if you dont like it.

Thats hardly some "you must obey" single enforced policy

The issue is not virtual FS versus some other kernel interface. The issue is what appears in /dev, and whether the kernel code should be hard coding what happears in /dev. It shouldn't. That's policy. The kernel shouldn't be dictating policy.

Instead, the kernel should be exporting sufficient information so that a user-mode daemon can provide whatever interesting naming scheme (and that naming scheme might include device names based on the UUID or the fslabel in the ext2 device, or something else far more general than what kernel-space code can provide.)

How do you manage permissions on this cleanly? It has to be persistent (no "OK, after we boot this tiny script fixes up the whole mess")? How do you propose to manage default permissions for devices that might suddenly appear out of nowhere (i.e., USB or hot-pluggable PCI or PCMCIA or...)? No, "one size fits all" won't do.

I'm not against some devfs type scheme per se, but this is important, and devfs makes this problem _worse_ without solving much of the other problems that are there. The current way of populating /dev with everything there might ever be is broken, but gives you a clean, uniform way of setting persistent permissions using standard tools.

Gents and ladies, I believe I have may have seen what comes after Unix. Not a half-step like Plan 9, but an advance in OS architecture as fundamental at Multics or Unix was in its day.

As an old Unix hand myself, I don't make this claim lightly; I've been wrestling with it for a couple of weeks now. Nor am I suggesting we ought to drop what we're doing and hare off in a new direction. What I am suggesting is that Linus and the other kernel architects should be taking a hard look at this stuff and thinking about it. It may take a while for all the implications to sink in. They're huge.

What comes after Unix will, I now believe, probably resemble at least in concept an experimental operating system called EROS. Full details are available at <http://www.eros-os.org/>, but for the impatient I'll review the high points here.

EROS is built around two fundamental and intertwined ideas. One is that all data and code persistence is handled directly by the OS. There is no file system. Yes, I said *no file system*. Instead, everything is structures built in virtual memory and checkpointed out to disk every so often (every five minutes in EROS). Want something? Chase a pointer to it; EROS memory management does the rest.

The second fundamental idea is that of a pure capability architecture with provably correct security. This is something like ACLs, except that an OS with ACLs on a file system has a hole in it; programs can communicate (in ways intended or unintended) through the file system that everybody shares access to.

Capabilities plus checkpointing is a combination that turns out to have huge synergies. Obviously programming is a lot simpler -- no more hours and hours spent writing persistence/pickling/marshalling code. The OS kernel is a lot simpler too; I can't find the figure to be sure, but I believe EROS's is supposed to clock in at about 50K of code.

Here's another: All disk I/O is huge sequential BLTs done as part of checkpoint operations. You can actually use close to 100% of your controller's bandwidth, as opposed to the 30%-50% typical for explicit-I/O operating systems that are doing seeks a lot of the time. This means the maximum I/O throughput the OS can handle effectively more than doubles. With simpler code. You could even afford the time to verify each checkpoint write...

Here's a third: Had a crash or power-out? On reboot, the system simply picks up pointers to the last checkpointed state. Your OS, and all your applications, are back in thirty seconds. No fscks, ever again!

And I haven't even talked about the advantages of capabilities over userids yet. I would, but I just realized I'm running out of time -- gotta get ready to fly to Seattle tomorrow to upset some stomachs at Microsoft.

www.eros-os.org. Eric sez check it out. Mind-blowing stuff once you've had a few days to digest it.

That's a classic thing said by "OS Research People".

And it's complete crap and idiocy, and I'm finally going to stand up and ask people to THINK instead of repeating the old and stinking dogma.

It's _much_ better to have stand-alone appliances that can work well in a networked environment than to have a networked appliance.

I don't understand people who think that "distribution" implies "collective". A distributed system should _not_ be composed of mindless worker ants that only work together with other mindless worker ants.

A distributed system should be composed of individual stand-alone systems that can work together. They should be real systems in their own right, and have the power to make their own decisions. Too many distributed OS projects are thinking "bees in a hive" - while what you should aim for is "humans in society".

I'll take humans over bees any day. Real OS's, with real operating systems. Monolithic, because they CAN stand alone, and in fact do most of their stuff without needing hand-holding every single minute. General-purpose instead of being able to do just one thing.

I will tell you anything based on message passing is stupid. It's very simple:

• if you end up doing remote communication, the largest overhead is in the communication, not in how you initiate it. This is only going to be more true with mobile computing, not less.
• Ergo: optimizing for message passing is stupid. You should _always_ optimize for the local case, because it's the only case where the calling protocol really matters - once you go remote you have time to massage the arguments any which way you like.
• Most operations are going to be local. Any operating system that starts out from the notion that most operations are going to be remote is going to die off as computers get more and more powerful.
• Things may start off distributed, but in the end network bandwidth is always going to be more expensive than CPU power.
• Truly mobile computing implies that a noticeable portion of the time you do _not_ want to be in contact with any other computers. Your computer had better be a very capable one even on its own. Anybody who thinks anything else is just unbelievably misguided.

This implies that your computer had better have a local filesystem, and had better be designed to work as well without any connectivity as it does _with_ connectivity. It can't communicate, but that shouldn't mean that it can't work.

So right now people are pointing at PDA's, and saying that they should be running a "light" OS, all based on message passing, because obviously all the real work would be done on a server. It makes sense, no?

NO. It does NOT make sense. People used to say the same thing about workstations: workstations used to be expensive and not quite powerful enough, and people wanted to have more than one. Where are those people today? Face it, the hardware just got so much better that suddenly REAL operating systems didn't have any of the alledged downsides, and while you obviously want the ability to communicate, you should not think that that is what you optimize for.

The same is going to happen in the PDA space. Right now we have PalmOS. It's already doing internet connectivity, how much do you want to bet that in the not too distant future they'll want to offer more and more? There is no technical reason why a Palm in a few years won't have a few hundred megs of RAM and a CPU that is quite equipped to handle a real OS. (If they had selected the strongarm instead of a cut-down 68k it would already).

In short: message passing as the fundamental operation of the OS is just an excercise in computer science masturbation. It may feel good, but you don't actually get anything DONE. Nobody has ever shown that it made sense in the real world. It's basically just much simpler and saner to have a function call interface, and for operations that are non-local it gets transparently _promoted_ to a message. There's no reason why it should be considered to be a message when it starts out.

Note that the Linux VFS layer was pretty much _designed_ with something like this in mind. From very early on, I decided that the VFS layer should not make too much of a distinction between a directory and a regular file: both have "lookup" properties, and both have "read" properties.

Some of that has been corrupted over time, and some of it was never done because nobody actually used it - so there's a few places where the VFS layer does things like "if (!S_ISDIR(d_inode->i_imode))" etc and thus "knows" about the difference between a directory and a regular file, but that was never really meant to be a design goal, and I'd be happy to try to clean it up.

So basically it all should be doable today: if a low-level filesystem wants to export directories both as regular files and as pathname components, it can be done. The low-level FS can look at the O_DIRECTORY flag to know whether somebody wants to read the thing as a directory or not (ie "readdir()" obviously opens the directory, while normal operations open the default file), and it should all work pretty much today.

It's going to confuse a lot of UNIX applications, but at the same time a reasonable number of them won't ever really have to know.

Before we go running into a deep technical discussion about how to design different streams inside a file, we should first stop ask ourselves how they will be *used*.

Something that folks should keep in mind is that as far as I have been able to determine, Microsoft isn't actually planning on using streams for anything. As near as I can tell it was added so that their SMB servers could replace Appleshare servers more efficiently, but that's really about it. I don't believe, for example, that MS Office 2000 is going to be using the streams functionality at all, and this is for a very good reason.

Streams really lose when you need to send them across the internet. How do you send a multifork file across FTP? Or HTTP? What if you want to put the multifork file on a diskette that's formatted with a FAT filesystem for transport to another OS? What if you want to tar a multifork file? Or use a system utility like /bin/cp or /usr/bin/mc that doesn't know about multifork files?

One of the reasons why the Apple resource-fork was a really sucky idea in practice was that executables stored dialog boxes, buttons, text, all in resources --- which would get lost if you tried to ftp the file unless you binhexed or otherwise prepped the file for transfer first.

So I question the whole practical utility of file streams in the first place. The only place where they don't screw the user is if the alternate streams are used to store non-critical information where it doesn't matter if the information gets lost when you ftp the file or copy the file using a non-multi-fork aware application. For example, the icon of the file, so the display manager can more easily figure out what icon to associate with the file --- and of course, some people would argue with the notion that the icon isn't critical information, and that it should be preserved, in which case putting it in a alternate stream may not be such a hot idea.

However, for speed reasons, a graphical file manager might do better to have a single file that has all of the icons cached in a few dot files (for security reasons, you will need a different dot file for each user who owns files in a directory). Said dot file would have information associating the name of the file, the inode number and mod time with the icon. If the icon cache is out of date, and an file appears in a directory without also updating the icon cache, the graphical file manager will have to find some way of determining the right icon to associate with the file. (But, this is a problem the graphical file manager would have to deal with anyway). The advantage of using a few dot files in each directory is that it will result in a lot fewer system calls and files needs that need read and touched than if the graphical file manager has to open the icon resource fork in each file just to determine which icon to display for that one file. So I don't even buy the argument multifork files are required to make graphical file managers faster; a few dot files in each directory would actually be more efficient, and would work across non-multi-fork aware remote filesystems like NFS. I don't think a graphical file manager that only worked on specialized filesystems would be all that well received!

So before we design filesystems that support multi-forks, let's please think about how they will be used, and how they will interact with current systems that don't really support multiple forks, and in fact are quite hostile to the whole concept. What's the point of being able to treat a filesystem object as both directory and a file if none of the system utilities, file formats (like tar) and internet protocols don't really support it? Does it really buy us enough to be worth the effort? And if we don't know exactly how it will be used, how will we know what sort of performace/feature tradeoffs we need to make before it will be useful?

So, here's a quick back-of-the-envelope design for a completely user-space solution for folks who have been asking for multi-fork files. It's not intended to be a completely polished design, but I believe it's worth at least considering before rushing off and deciding that the only way to do things is to extend Linux's filesystem semantics.

I write this up this because people have accused me of just being a conservative "Dr. No" who always thinks their great new ideas are always bad. On the contrary, if application writers (especially office suite application writers) are demanding certain sets of functionality, we should take such requests seriously, and weigh the costs and benefits of what they ask for. It's just that I very strongly believe in trying to offer a user-space solution first before resorting to making in-kernel solutions. Especially if they are hacks that will only work on Linux systems! (Using one's OS market share as a club against interoperability is a despicable Microsoft tactic, and not one I want to encourage.)

Requirements analysis

So, let's try this as an exercise. Since no one has actually bothered to write down a list of requirements before galloping off to a solution, let me try to offer some:

1. "Common" file manipulations operations should treat an "application logical bundle of data" (albod) as if it were a single file. (Forgive me for inventing a new acronym here, but "application logical bundle of data" is too long to type each time, and I don't want to bias people's thinking about how it is actually implemented.)
2. Applications should be able to quickly and efficiently manipulate (read, modify, replace, delete, etc.) individual streams of data within an albod. This should be done without the file bloat and inefficiencies found in MS Office 97 format files.
3. There should be standard file streams inside the albod whose semantics and data format are standardized, so that programs such as graphical file managers can determine basic information about an albod, such as which icon to use, who created it, which application should be invoked when the albod is activated, etc. quickly and easily. (Using file(1) on a data file to determine which application can interpret it is considered barbaric.)
4. It should be easy to send these albod's across standard Internet protocols using standard, commonly available tools (ftp, http, rcp, scp, etc.).

Am I missing any other requirements?

Other solutions

Now then, which approaches have been used to address this problem in the past? In the NTFS and the Macintosh, this was done by adding specialized (but non-standard) semantics and new formats in the filesystem. This satisfied the first three requirements, but failed on the last.

The NeXT used a directory containing individual files, which satisfied requirements #2 and #3, but didn't satisfy #1 (except if you only used their graphical file manager) and #4 (unless you explicitly tar'ed stuff up first).

My proposed straw-man proposal

I now offer to you a design for a potential solution which is purely implemented in userspace, and has the advantage that it will work across all existing filesystems, include NFS, AFS, Coda, ext2, and doesn't require any linux-specific kernel hacks (which is important, since last time I checked, the GNOME and KDE folks weren't interested in solutions that only worked on Linux). The solution is a directory-based solution, like NeXT, but tries to address the rest of the requirements.

First of all, we need some way of distinguishing an "albod" from a normal directory. This can either be done using a filesystem specific flag, which is probably more efficient, but we would also like a filesystem independent way of doing this. So instead of (or perhaps in addition to) using a filesystem-provided flag, let's posit a magic dotfile in the directory which, if present, marks it has an albod bundle.

Now let's assume that we have a hacked libc (or a system-wide LD_PRELOAD) which intercepts the open system call. If an application does not declare itself (via some API call) to be albod knowledgeable, an attempt to open and read the albod results in the user-mode library emulation of open()/read() to return a tar-file-like flat-file representation of the albod. This allows cp, ftp, httpd, mimeencode, etc. to be able to treat an albod as if it were a single "bag of bits".

If the application declares itself to be albod-aware, it can then treat the albod as a directory hierarchy, and manipulate the various subcomponents of the albod as named streams, just like NTFS5 allows --- except that we can have hierarchical named streams, and not just a flat namespace!

How are albod's written? Well, an albod-aware application simply writes the appropriate component directories and files as if they were normal Unix files (which in fact, they are). If an non-albod-aware application such as /bin/cp writes it, there are two design choices. It's not clear which one is better, so let me outline both of them. One is to have the user-mode library notice that it is a albod flat-file representation by looking at its header, and then automatically unpacking it into its directory format as it is writing it out.

The other design choice is to simply allow the albod to be written out as a flat file, and when an albod-aware application tries to modify it, only then does the albod-flat-file-package get exploded into its directory-based form. If the flat-file format is compressed (which would be a great idea since applications would now get compression for free) then only expanding an albod when it is necessary to read it will save disk space for albod's which are only getting access occasionally in read-only fashion.

Problems with this approach

What are the downsides of this approach? Since by default, a non-albod-aware application gets the entire packaged albod as a single flat-byte-stream representation, /bin/cp, etc. work fine. This is great if the albod contains some new application data format, such as a Word or an Excel or a Powerpoint competitor, since the actual application code which manipulates the application document is albod-aware.

However, if the albod contains a .gif, .mp3, etc. file, where the already-existing applications that know how to process the .gif or .mp3 file aren't albod-aware (think: xv), then having open() return a flat-file contents of the entire albod is the wrong behavior. Instead, you want to return the default data-fork contents in that case. So what we can do is to have a second magic .dotfile or flag which indicates that for this albod, when it is opened and read, the default data file should be returned instead of a flat-file representation of the albod. The tradeoff for using this optional mode is that a naive /bin/cp or Midnight Commander program which doesn't know about albod files won't know how to copy or move the entire albod. So an attempt to ftp or mail this alternate form of the albod will just result in the data fork being sent. But if all of the application-specific data (i.e., the .gif or the .au data) is in the default data fork, losing the other metadata format might not be a disaster, and so this might be the approprach tradeoff. It depends on what extra metadata extensions GNOME or KDE wants to store in the albod alongside the .gif or .mp3 data.

The other downside with this solution is that it is admittedly pretty complex, and there are some subtle issues about how the LD_PRELOAD or hacked libc routines should actually work in practice. Some might even say that it is a kludge.

On the other hand, is it really that much worse than having kernel-mode "reparse points" that manipulaes application specific data in the kernel?!? I would argue that in contrast, having user-mode library hacks may actually cleaner, although admittedly both solutions aren't exactly pretty. Perhaps someone can come up with a yet more cleaner solution. I hope so!!

Summary

This is obviously not a fully fleshed out design proposal. There are obviously lots and lots of details that would need to be filled in first, before this could be used as a set of functional specs which an implementor could implement. I won't even claim that this is the best way to meet the stated requirements solely in user space. Someone may come up with a more clever user-space-only solution.

Rather, this was intended to serve as some food for thought, and a proof by example there is a way to do this in user-mode, without requiring Linux-specific filesystem hacks and extensions. While it requires some extra extensions to the libc, which might be considered kludgy, I believe it is no worse than the Microsoft NTFS-style "reparse points" suggestion which was offered to the kernel list in the last day or so.

The new and much improved fully page-cache based filesystem code is now apparently stable, and works wonderfully well performancewise. We fixed all known issues with the IO subsystem: it scales well in SMP, and it avoids unnecessary copies and unnecessary temporary buffers for write-out. The shared mapping code in particular is much cleaner and also a _lot_ faster.

In short, it's perfect. And we want as many people as possible out there testing out the new cool code, and bask in the success stories..

HOWEVER. _Just_ in case something goes wrong [ extremely unlikely of course. Sure. Sue me ], we want to indeminfy ourselves. There just might be a bug hiding there somewhere, and it might eat your filesystem while laughing in glee over you being naive and testing new code. So you have been warned.

In particular, there's some indication that it might have problems on sparc still (and/or other architectures), possibly due to the ext2fs byte order cleanups that have also been done in order to reach the afore-mentioned state of perfection.

I'd be especially interested in people running databases on top of Linux: Solid server in particular is very fsync-happy, and that's one of the operations that have been speeded up by orders of magnitude.

There's still something fishy going on, and David still has some problems on his sparc. So don't get all excited yet - we're steadily getting rid of bugs, but I want to have this stabilize over the next week or so before I start accepting seriously different patches.

(I've been dropping patches so far, I expect to drop patches for another week or so - I want this thing _stable_).

By the way, not to slam Linus or anything, but making the types of sweeping changes that were made between 2.0 and 2.2 in the file system architecturaly was unsound from an engineering perspective, although I do understand why it needed to change, most commercial software companies would have never allowed this to occur. The changes are what have broken Caldera's Netware clients and server software, and they are still working on it and getting it fixed.

Word of Advice -- these file system changes hurt Linux in the market because they delayed the commercial Linux vendors from getting key services up and running when customers needed them. In the future, we should not make such sweeping changes wuthout making certain there is still a method to support the old interfaces as well.

The dentries stuff was probably the hardest change to deal with though. Its not a simple proceedure to quickly fix up code without understanding the problem, which reduces the number of users who fix it. (and yes I do get patches from people that start 'I don't know C, but xyz wouldnt compile in the new 2.1.x release so I copied the change from this similar looking thing and now it works'.)

I don't claim we have the model right, but the rules are definitely different

I want to make it clear to everyone that I don't think Linux is doomed, however, this email thread is using my trademark (FENRIS) on the header of the email to "bitch" about every busted build in the last 5 years. If you folks want to complain to Linus or Alan about stuff getting busted, it's your right. If you want to use my Trademark name on the email header, think again. I don't want this email thread associated with our trademarks since we do not share your views to the same extreme as the folks in this email thread.

Please stop using my trademarks for your "bitch" list about Linux. Nothing in the world is perfect, including Linux, but it's getting better, and folks are working hard to improve it. If you want to simply title the email, "Why Linux is Doomed", then you certainly can do so -- without attempting to associate us with your personal views.