Kernel Traffic #214 For 28 Apr 2003

Ok, I checked the archives and found some interesting mails:

http://www.ussg.iu.edu/hypermail/linux/kernel/0105.1/1170.html
http://www.ussg.iu.edu/hypermail/linux/kernel/0105.1/1180.html
http://www.ussg.iu.edu/hypermail/linux/kernel/0105.1/1072.html
http://www.ussg.iu.edu/hypermail/linux/kernel/0105.1/1310.html
http://www.ussg.iu.edu/hypermail/linux/kernel/0105.1/1348.html

This is from the last dev_t discussion I was able to find and my apologies to Linus for dragging him into this, personally I prefer a discussion based on arguments, but you want to feel the whip of authority. (There are also some juicy mails from Al, but you can look for these yourself.)

Linus argues here for dynamic numbers and I was not able to find a single mail, where he completely changed his mind since then. If you know something I don't, I'd be really happy to hear about it (actually I found 9 (nine!) year old mails, where he argues for a more dynamic system).

In above discussion, Alan was one of the few who actually came up with reasonable arguments, some of his concerns were:

• he needed a solution for 2.4:
  we are at 2.5 now and the kernel is mostly ready for dynamic device numbers
• compatibility:
  it's trivial to preserve dev numbers below 0x10000, new drivers start above this
• hardcoded ioctl knowledge:
  this is partly a compatibility problem and in the meantime it's generally accepted that they are a bad idea most of the time and drivers should use e.g. sysfs instead.

Am I now worthy of an answer, so you could please explain "why dynamic numbers are broken for nearly all applications"? What were I supposed to learn from the archives? Maybe you should read them yourself, because I didn't found a single discussion with a clear outcome.

the biggest problem I see with dynamic numbers is that it needs a userspace devfs type solution for creating and maintaining the device nodes that are then used. While this isn't rocket science it's also somthing that is hard to get people to agree to (remember the devfs names that everyone gripes about are not what richard started with it's what he switched to to get things into the kernel, they changed many times during that process)

I don't think many people will argue that dynamic assignments are evil, but I think you will find a lot of people very nervous about switching to them and the risk involved with doing so.

So far, *none* of the schemes used for dynamics have gotten it right. They just ignore a fair number of the problems. People keep focusing on disks, and they are nearly uniformly the almost-trivial case in comparison with especially character devices, where you don't have the layer of indirection called /etc/fstab, persistent labels, etc.

It is also independent of the need to switch to a larger dev_t. Claiming that we can squeeze more out of the existing device scheme if we have an ideal-world dynamic scheme is unrealistic because:

a) There are, genuinely, systems with more than 65,536 devices or anonymous mounts. That rules out the current dev_t just by itself.

b) Despite the fact that people have tried since the mid-90's, we still don't have a sane way to manage such dynamicity.

c) We are now in what pretty much amounts to a crisis situation. We have needed to enlarge dev_t for well over half a decade. Therefore, it is too late to say "well, given X we wouldn't need it." We need something done in *this* kernel cycle.

Given that it has taken, literally, 8 years to get to this point, and based on collective global experience with numberspaces, I'm arguing for enlarging it far more than anyone can currently imagine being necessary.

dev_t is already 64 bits in glibc, and the glibc<->kernel interface needs to be fixed *anyway*. We have to take the pain of migration, we might as well go all the way.

There are a couple things being discussed here. One is the size of dev_t. The other is dynamic numbers. It would seem that most folks agree with a larger dev_t and a more dynamic numbering system. Let's assume we want both for now (folks who don't, please keep out for a second). There are three courses of action that seem to be advocated.

1. Ship 2.6 with 16bit dev_t, work on a larger dev_t and perfect dynamic devices in 2.7.
2. Ship 2.6 with a (32|64)bit dev_t, work on a perfect dynamic scheme in 2.7.
3. Hold 2.6 until it can ship with (32|64)bit dev_t and perfect dynamic devices.

Many folks, Peter and myself included, are claiming that choice (1) is absolutely untenable. We need more device space today, not in 3 years when 2.7 becomes 2.8.

If I understand you correctly (and here is why I mailed), you feel that choice (2) is the worst of the choices. You feel that we should either choose course (1) or course (3). I'm not sure which of those you prefer.

That misunderstanding is hopefully easy to resolve:

(4) Ship 2.6 with a (32|64)bit dev_t with an experimental dynamic scheme and keep the device numbers below 0x10000 as they are now.

As I told a while ago, I'm forking radeonfb for now, at least until Ani (current maintainer) either give me maintainership or gets all that stuff in the official version.

I need testers, and I'd appreciate any patches people may have for it as well since I know a bunch of ppl have been spreading various radeonfb patches around, I want to take over all of these and see what is worth getting in. For 2.5, I'm working on a complete rewrite (& split) of the driver.

So far, I already have something to play with that fixes a bunch of issues. Patches against 2.4.20 and 2.4.21-pre7 can be found here: (too big to inline). Note that I also bring in various other pci_ids.h updates but that shouldn't harm you and is easier that way for me ;)

http://penguinppc.org/~benh/radeonfb-040603-2.4.20.diff

http://penguinppc.org/~benh/radeonfb-040603-2.4.21-pre7.diff

NOTE: It's known that radeonfb is incompatible with ATI binary GL drivers (at least it crashes the machine on a friend's r300), I'm investigating.

I got a couple of requests for a function which isn't support on Linux so far. Also not supportable, i.e., cannot be emulated at userlevel. It has some history in other systems (QNX I think), though, and helps with some security issues. It really not adding much new functionality and I hope I got it right with my "monkey see, monkey do" technique of looking up other places doing similar things.

The syscall I mean is

int flink (int fd, const char *newname)

Similar to link(), but the first parameter is a file decsriptor. Using the file descriptor helps to avoid races in some situation.

As others have pointed out, there is no way in HELL we can do this securely without major other incursions.

In particular, both flink() and funlink() require that you do all the same permission checks that a real link() or unlink() would do. And as some of them are done on the _source_ of the file, that implies that they have to be done at open() time.

One check in particular is "is the opener willing to let this be linked anywhere else in the namespace". Since the opener isn't necessarily the same agent as the one doing the flink().

If you really really think you need this (and not just do it because some random idiot-customer doesn't understand security), then I would suggest you add a O_CANLINK flag to open, and require that that flag is set in the file descriptor.

That way you get "flink()" behaviour, but you require that the opener be aware of the fact that the file may be linked into another position. That will fix the glaring security hole.

there are two or three ways I can see:

• add safelink() instead of flink()

  int safelink (const char *oldname, int fd, const char *newname)

  As Jakub explained, this syscall would check that the file referenced by oldname really corresponds to fd before making the link.

  If you need an example, take the linker. The linking can take a long time. The temporary output file has to be created early and there is sometimes enough time before the linking finished for even a human to figure out the temporary file's name and replace the file. If then the final file is installed as root (since the linking succeeds) you'll have problems.

  There is of course the possibility that one compares the ino/dev of the temporary file and the file after the link (or rename, btw) but this means the wrong output file existed for some time and all that is left to do is to remove the file which might be critical if the system depends on the file always being present.

• add the O_CANLINK. Sure it's possible. But see the next variant

• add an open() flag to create files which are not present in the filesystem (Hurd has something like this). open() would get as the filename the name of a directory. Such a feature can be used for all kinds of temporary files:

  • files which never need names, i.e., don't have to be accessed through the filesystem; the advantage is that there would never be stray files in the filesystem if the program forgets to clean them up
  • temp files which have to be completed first before renamed. Here flink() and frename() would introduce the name in the filesystem. This is obviously useful in many many places, e.g., the linker scenario. There is no way to attack the linker while it is doing its work since the output file isn't visible until it is installed under the final name.

  Maybe the O_CANLINK flag idea is also necessary for this, don't know. The O_ANONYMOUS flag might include setting O_CANLINK.

I'm certainly not qualified to say whether this is viable or not. The safelink() idea certainly is implementable, just 3-4 more lines on top of the flink() patch. But this wouldn't be necessary if we'd have the more complete support with the new open() flag(s). Al mentioned to me some problems with network filesystem in the context of flink(). So somebody who understands these issues might want to comment. It seems there is some interest in this.

Some days ago, I've started a -je ("just embedded") tree which will focus on memory reduction for the linux kernel.

The RATIONALE is that on a ppc with some flash, memory, network and nothing much else, I don't feel like parsing MS-DOS partitions, offering IPX networking etc., but that junk is still included in 2.[45].current - unconditionally. And there is more...

My first GOAL is to add config options that rip the code out for any platform that doesn't need, yet keeps it in for everyone that does. If I don't know what the code is needed for, I'll just rip it out and wait for bug reports - hopefully.

If I feel that any particular patch is clean enough for mainline, I'll forward it to Linus/Marcello.

WHO should use this tree:

• Anyone concerned about memory footprint of the linux kernel, both of the image and during runtime. This will mainly be embedded developers, I guess.
• Anyone. :)

Bugreports of any kind will help me to clean up the patches and get them included in mainline. I personally run them on my PIII notebook, right now, and things didn't break. (Yet?)

HOW can you help:

1. Any patch that reduces the memory footprint on _any_ platform is welcome. Even the worst hacks should be cleaned up over time to work for everyone.
2. Test the patches and:
• Send bugreports. They will help to clean up the patches.
• Send works-for-me reports with a rough outline of the hardware used. When things start to work for many people on many platforms, it may be time for mainline.
3. Send any other patches and convince me that they help embedded people by my definition (whichever that may be at that time).

WHAT patches will I ignore/reject:

• Anything that does not help embedded (my definition, see above). That stuff should go into -ac, -dj, -mm, -aa or whereever.

Finallly, WHERE can you get it:

http://wh.fh-wedel.de/~joern/software/kernel/je/24/patch-2.4.20-je1

http://wh.fh-wedel.de/~joern/software/kernel/je/25/patch-2.5.66-je1

DISCLAIMER:

No, the server does not support directory browsing, there is no mailing list and there are currently only three patches in the 2.4 tree and two in the 2.5 tree. 2.5 is untested, looks broken and I should put some work in it.

These patches may cost you time, money and precious hardware, I don't guarantee for anything and IANAL. Anything else?

I prefer a short and clean actual kernel source, and long historical explanations somewhere else, for example in Documentation/ioctl_list.

(Michael Elizabeth Chastain made ioctl_list.2 a man page, but nobody keeps it up-to-date. The current version is from 1.3.27. I am updating it and expect to submit it for the Documentation directory. Maybe more people will update it there.)

They have never been enabled. The "goal" is to imlement fragments as a type of extended attribute, so that they can be packed into a single block or inline in a larger inode (along with other EA data) instead of being fixed-size hunks.

The first thing that needs doing is fixing the current ext2/3 EA sharing scheme, which currently only shares blocks if they are identical and is therefore only really useful for ACLs.

The best proposal so far for EA sharing is to put them into a directory-like structure (maybe one dir per block group or something) and have the EA type and data be packed inline into the directory (like the inode number and filename are done with regular directories). Each inode would also have a "catalog" of the EAs that it has (itself an EA, either inline in a larger inode or in the directory pointed to by, say, i_faddr). Shared entries would be like hard links pointed to by mutliple catalogs, with a refcount.

This was discussed on ext2-devel about a year ago, but no takers on the implementation yet (I might eventually need to implement it this year if nobody beats me to it, because we need better EAs than one per 4kB of disk).

To be brief, the idea I came up with was to identify the 128 most common words in kernel messages and replace them with single character values above 127 which printk would decode on the way out. Once the list was determined, there would be a header file people could use, at their leisure, to make stubstitutions. So, for instance, instead of having this:

printk("invalid: ...");

We would have this:

#define MSG_INVALID "\200"
...
prink(MSG_INVALID "...");

To judge the practicality of this, I used 'strings' on an uncompressed kernel image (2.4.20, IIRC) and then ran it through this:

tr '[:lower:]' '[:upper:]' | tr '[:blank:]' '\n' | sort | uniq -c | tr ' ' 0

This gave me a list of all words found in the kernel along with their counts. Then I ran it through a positively awful little C program which I wrote to determine not the 128 most frequent, but rather, the 128 that would result in the maximum shrinkage (maximize count * (length-1)). The results of that run are given below. The results of the test are that this approach might save up to 62424 bytes of kernel space which is only about 3% of the kernel image size I got the strings from, but it's nearly 27% of the total output I got from 'strings'. Is it worth it? Maybe not yet, but then again, there may be an even more intelligent approach to this compression that we could use, hopefully one which wouldn't require any more effort to use.

I'd like to finally announce the previously vapor-ware udev program that I've talked a lot about with a lot of people over the past months. The first, very rough cut is at:

kernel.org/pub/linux/utils/kernel/hotplug/udev-0.1.tar.gz

But what is it? I've included an initial design document below that was originally written by Dan Stekloff, and hacked up a bit by me. But in short, udev is a userspace replacement for devfs. It will create and destroy /dev entries based on the current system configuration. It does this by watching the /sbin/hotplug events on the system, and reading information about these events from sysfs.

Right now the program is only in 1 piece, not the 3 pieces that the design document talks about, but it does work with the default Linux /dev naming scheme that almost everyone uses. It can only work for devices that create a dev file in sysfs, exposing their major/minor number, so this is limited (currently only block and usb-serial devices do this.)

If you want to test this with block devices, you will need the kobject hotplug patches previously posted here for 2.5.67, which are also available at:

kernel.org/pub/linux/kernel/people/gregkh/misc/kobject-hotplug-?-2.5.67.patch

Anyway, this works for me, on my machines, and I am very interested in feedback from everyone about both this concept, and the implementation of this. I've cced a lot of different lists, as they have all expressed interest in this project.

Yes, I know there's still a lot of work to do (serialization, symlinks, hooking hotplug so that others can also use it, etc.) but it's a first step :)

I'd like to thank Dan Stekloff for constantly badgering me about this project and for writing lots of good design documentation, it is greatly appreciated. Also, thanks to Pat Mochel for coming up with sysfs which allows this project to be able to work at all.

We've got a couple goals for udev:

1. dynamic replacement for /dev
2. device naming
3. API to access info about current system devices

Splitting these goals into separate subsystems:

1. udev - dynamic replacement for /dev
2. namedev - device naming
3. libsysfs - a standard library for accessing device information on the system.

Udev
------

Udev will be responsible for responding to /sbin/hotplug on device events. It will receive the device class information along with device's sysfs directory. Udev will call the name_device function from the naming device subsystem with that information and receive a unique device name in return. Udev will then query sysfs through the libsysfs for specific device information required for creating the /dev node like major and minor number. Once it has the important information, udev will create a /dev entry for the device, add the device to the in memory table of current devices, and send notification of the successful event through a D-BUS message. On a remove call, udev will remove the /dev entry, remove the device from the in memory table, and send notification.

Udev will consist of a command udev - to be called from /sbin/hotplug. It will require the in memory dynamic database/table for keeping track of current system devices, and a library of routines for accessing that database/table. Udev will not care about "how" devices are named, that will be separated into the device naming subsystem. It's presented a common device naming API by the device naming subsystem to use for naming devices.

namedev
----------

From comments people have made, the device naming part of udev has been pushed into its own "subsystem". The reason is to make this as flexible and pluggable as possible. The device naming subsystem, or namedev, will present a standard interface for udev to call for naming a particular device. Under that interface, system administrators can plug in their own methods for device naming.

We would provide a default naming scheme. The first prototype implementation could simply take the sysfs directory passed in with the device name function, query sysfs for the major and minor numbers, and then look up in a static device name mapping file the name of the device. The static device naming file could look just like devices.txt in the Linux kernel's Documentation directory. Obviously, this isn't a great implementation because eventually we'd like major an minor numbers to be dynamic.

The default naming scheme in the future would have a set of policies to go through in order to determine the name of the device. The device naming subsystem would get the sysfs directory of the to be named device and would use the following information in order to map the device's name:

1. Label info - like SCSI's UUID
2. Bus Device Number
3. Topology on Bus
4. Kernel Name - DEFAULT

System administrators could use the default naming system or enterprise computing environments could plug in their Universal Unique Identifier (UUID) policies. The idea is to make the device naming as flexible and pluggable as possible.

The device naming subsystem would require accessing sysfs for device information. It will receive the device's sysfs directory in the call from udev and use it to get more information to determine naming. The namedev subsystem will include a standard naming API for udev to use. The default naming scheme will include a set of functions and a static device naming file, which will reside in /etc or /var.

libsysfs
--------

There is a need for a common API to access device information in sysfs. The device naming subsystem and the udev subsystem need to take the sysfs directory path and query device information. Instead of copying code so each one will have to readdir, etc., splitting this logic of sysfs calls into a separate library that will sit atop sysfs makes more sense. Sysfs callbacks aren't standard across devices, so this is another reason for creating a common and standard library interface for querying device information.

I did some searching of the kernel archives and the only things related to the forthcoming idea had to do with compressing pages when writing to swap and doing compressed disks. Here's a different idea...

Inspired by my recent experiments in compressing kernel messages, I started to wonder what else might benefit from compression, and the following idea occurred to me:

Given the hideous amount of time required to access a disk, especially when something else wants to access it, could there be a benefit to "swapping" pages by compressing them to somewhere else in memory? If we could achieve, even say, 30% compression on pages, on average, then we could free up RAM without having to do any I/O. This would be the first line of defense against a low-memory situation, finally resorting to actual disk access when that becomes unworkable or for pages which can't be compressed enough for it to help (which has a penalty worse than just writing to disk). And furthermore, if we were to swap first memory containing compressed pages, we can reduce the total amount of I/O for swapping.

This would, of course, suck a lot of CPU, and in the case of a server running many services where the CPU usage is pegged even when there's a lot of swapping, it would be better to just swap as normal. But in any case where swapping is causing an increase in idle time, I would expect a considerable benefit from being able to free up pages by making LRU pages simply take up less space in RAM when they're not being used.

Now that the kernel provides code user programs are executing directly (I mean the vsyscall code on x86) it is necessary to add unwind information for that code as well. The unwind information is used not only in C++ code. The new thread code also uses it for the cancellation handling. If we have no such information available we would have to resort to using int $0x80 for all syscalls which are also cancellation points (read, write, ...).

Providing the information from outside the kernel is problematic. First, we would have to recognize when a process starts which code is actually used and install the appropriate unwind table. Second, we would always have to keep libc and kernel in sync. There might be new code sequences in future and once the kernel is changed you'd need a new libc. Not good at all.

Instead the best way I've found is to provide the info in the kernel. Fortunately this is associated with almost no cost. The unwind table is just a block of static data which is copied at system boot time into the vsyscall page just like the normal vsyscall code.

To advertise the existence and location of the unwind table I've added one more AT_* constant. It might in theory be possible to reuse AT_SYSINFO and add a fixed offset but I'd rather not do this. If/When more code is added to the vsyscall page the unwind table gets larger and you want to have the liberty to move it out of the way.

This also brings up an important point: even if more entry points into the vsyscall page are defined, there will always have to be only one unwind table. It is not necessary to add more and more AT_* values to advertise more tables.

The attached patch just adds the AT_* value, makes sure the AT_* value is passed to applications, define the static data for the unwind blocks (two, one for int80 and the other for sysenter), and finally code to copy the data in place. Very simple and unintrusive. The patch is verified to work nicely and unwind now works even when I use vsyscall.

I've added documentation of all the unwind info but it might still be not easy to generate new data if the code sequences are changed or new sequences are added. If you want, you can add a comment somewhere which instructs people to contact me to make the changes.

The patch also includes a bonus: so far all the tables in the sysenter_setup() function will stay behing even if the function gets removed after startup. They are not marked appropriately. I've added __initdata marker, but actually it should be __initrodata if this would exist. Not that it makes much of a difference, the data is gone right away after booting.

Here's my latest patch against 2.5.67 which introduces a proper state machine into the PCMCIA layer for handling the sockets. Unfortunately, I fear that this isn't the answer for the following reasons:

• We create our own workqueue (which spawns N threads, one thread per CPU.) We need to use a separate thread from the keventd since we call PCI probe and remove methods from this thread, which are free to use flush_scheduled_work() - which would be another deadlock waiting to happen. I think we need to go to a per-socket thread instead.
• The state machine isn't as readable as it should be. To be quite frank, I think it was a mistake to code it as a state machine - IMO its completely unreadable.
• We allow cardbus cards to be suspended and reset as though they are normal PCMCIA cards. Unfortunately, PCI drivers have no knowledge that these operations occur. This also applies to older kernels, so this isn't really a problem that's created by this patch.
• This is even more true now that we have the capability to plug in a complete (possibly complex) PCI bus structure.

• There seems to be a whole bunch of setup stuff going on in pcmcia_register_client(). This is run each time a card device driver is inserted by cardmgr. Although this has buggy for the case where all drivers are built in, this patch makes it more buggy; if a card is inserted at the time ds.ko is loaded, we kick off the asynchronous state machine to process the card and carry on regardless.

  However, we can not wait here - if we do wait for the state machine to complete, we will hit the same deadlock in the device model which we're hitting today.

  It appears that it would mainly affect multi-function PCMCIA cards. Unfortunately, I don't have any to test.

That said, it seems to work for me.

The patch can be found at

http://patches.arm.linux.org.uk/pcmcia/pcmcia-1.diff

Now, thing is, I can't test this patch on its own; I can test it on ARM boxen with yenta cardbus bridges, or statically mapped PCMCIA-only sockets, but the former requires several other patches to the PCMCIA resource subsystem to be functional.

Hence I need other peoples feedback on this patch before I push it Linus-wards.

Theoretically possible on most CPUs, but it's not that simple.

• Some CPUs don't encode the necessary bits to tell you their current multiplier/FSB
• Some CPUs don't encode the necessary info to tell you the speed the CPU should be running at.

Which leaves those that do have the necessary info.. Which is different per vendor, per family, per model. That's a lot of tests, and it's not a walk in the park to get it all right, which is probably why no-one has done it yet.

Alan tried it in the 2.4.early-ac stage, but gave up on it after a while, after getting lots of reports of it not working out as planned..