Kernel Traffic #42 For 8 Nov 1999

ASUS P2B-DS w/ 2 x 500Mhz. PIII
IBM 9LZX U2 LVD SCSI disk on built-in Adaptec 7890/1 controller
256 MB PC-100 non-ECC Dimm
Viper 550 AGP video w/ 16 Meg

Kernel 2.2.13 + valinux nfs patches

AMD K6-233
TMC Via MVP3 board
Buslogic Multimaster.
Seagate Cheetah, IBM DDRS, IBM DGHS.
Errors occured on the DGHS, other drives are scratch space.

Machine patched with latest RAID and knfsd 1.4. NFS server to a couple of
other machines, 1 of which mounts /usr.

Yes, but my reply was to another user with another fault.

This is exactly why this problem is so hard to track down --- when something random goes wrong in the OS, users often notice it first as filesystem corruption (I saw exactly the same thing when working on VMS filesystem internals for DEC).

In this case we have a known knfsd fault which explains some of the problems. The bulk of the other reports have been traced to hardware problems, or to memory scribbles caused by other bits of the kernel in certain specific kernel versions.

If you are only seeing the problem on a specific complex LV volume, then that suggests that either you are getting data corruption from one of the drives on that LV (over-long IDE cables, for example, or drives with known firmware bugs have all shown it in the past), or that there is an LV bug somewhere.

Unfortunately, a problem develops here, and this is where we would like some advice. We want the md5sum to run in the kernel because we are thinking of kernel mode as "safe" and anything in user mode as "unsafe". But the relocation of the module happens in insmod in (untrusted) user mode. Naturally, modules relocated to different addresses have different md5sums. There are several possible work arounds:

1. Try to guess the most likely eventual module relocation locations and allow the md5sum of the relocated module to match any one of the possibilities.

   - messy and likely to fail to work.

2. Shift module relocation into kernel mode doing the md5sum as soon as it is seen.

   - feasible but a fairly large change in the way things are done. All of a sudden the create_module syscall is useless.

3. Make create_module pass back a dummy relocation (0x00000000?) then complete the relocation in kernel mode if the module passes an md5sum.

   - inelegant, but maintains backwards compatibility

4. Try to just do an md5sum on unrelocated portions of the module

   - nasty and it's unclear that this is "safe".

Are there other methods? What's best?

Yes, John forgot to mention that we're assuming boot from a read-only media such as a write-protected floppy or CD-ROM. We also assume that the rc scripts, kernel, and all modules to be loaded at boot time (before of course the sealing module) also reside on that medium.

About your last point, yes, root can do a lot of nasty things, but by sealing the kernel at least they are constrained to what's available through kernel services. That may help presumably by disabling a lot of stuff in the running kernel.

This is a revision of my original proposal to take in information since received, not a duplicate, but I've revised it to state what appears to be the current requirements:

1. The serial port will provide a flag field to indicate its state, with the following states being defined:
   1. NOT-HERE - This port is not present. This is the default state for all ports in the kernel before any probes occur, and is the only valid state for ports that are not found to be present.
   2. FULL-DUPLEX - This port is currently operating in full duplex mode. This is the default state for all ports for which the hardware has been detected.
   3. FULL-TO-RX - This port is in the process of switching from full duplex mode to half duplex receiving mode.
   4. RECEIVING - This port is currently receiving data in half duplex mode, so anything to transmit is just queued until reception finishes.
   5. RX-TO-TX - This port is in the process of switching from reception to transmission of data in half duplex mode. This would only occur when the receiver has been idle for a predefined length of time AND the transmit buffer is not empty.
   6. TRANSMITTING - This port is currently transmitting data in half duplex mode, so is not able to receive anything.
   7. TX-TO-RX - This port is in the process of switching from transmission to reception of data in half duplex mode.
   8. RX-TO-FULL - This port is in the process of switching from half duplex reception to full duplex mode.
2. The following hooks should be implemented:
   1. A routine to be called to say "Time sufficient for X bytes to be received has passed without reception of any bytes, and the port is in the RECEIVING mode" (as defined above). The default is for this routine to be called only if X (an unsigned quantity) is non-zero.
   2. A routine to be called to say "This port is in the TRANSMITTING mode and has run out of data to send".
   3. A routine to be called to switch the transmitter when any of the transitions (1.3), (1.5), (1.7) or (1.8) need to occur.
3. The following additional IOCTL's should be implemented:
   1. One to specify the value of X as referred to in (2.1) above.
   2. One to specify that the port should switch to state Y (as defined in (1) above) now.

From an implementation viewpoint:

2.1 could be implemented along the lines of "On receipt of each byte, set a timeout to expire when the time needed for X bytes to be received has passed, resetting any such timeout that is currently in progress for this port. Should this timeout actually occur, call the specified routine."

2.2 would be implemented fairly easily, and the default response in the absence of any other would be to cause transition (1.7) to occur.

2.3 would be specific to the individual line disciplines.

I don't remember exactly what you proposed for this, but if you are intending to replace the inode structure with a generic one which has a pointer to a separately allocated per-fs structure then here's a warning. Digital UNIX used to that but had to change it exactly the opposite way for performance reasons. Its vnode structure used to have a v_data pointer to a separately allocated per-fs "private" structure. However, performance was bad because of the pointer following and the extra fragmentation. They ended up reuniting the two so that they could allocate the whole (generic + private) structure in one chunk and then made v_data point to directly after the generic part (i.e. the start of the no-longer-separate private part).

They did the same with their ungodly mixture of BSD and Mach structures for tasks and threads: they had separate struct task, struct proc and struct utask which they combined into a single struct super_task (though still with pointers between the supposedly "separate" bits) and they had separate struct thread and struct np_uthread which they combined into struct super_thread.

I think duplicating that #ifdef is bad because now there are two places where a maintainer would have to change it.

I recommend just putting a comment in front of NS8390_trigger_send and letting this problem go.

I tried another fix, which is to make EI_SHIFT(x) always reference its argument (I was inspired by #define spin_lock in include/linux/spinlock.h). This fixes the 8390.c warning but breaks pcnet_cs.c.

This little warning isn't worth the trouble.

First I modified the kernel such that I could dump the active buffer head state into user space at any point in time. I created a new procfs node, /proc/bcache, which allow this. It dumped raw structures which presented, for each currently active buffer head, only the elements of the buffer head structure which the hash function cares about.

Next, using this kernel, I configured several block device configurations to get a decent mix of block device numbers. For the most part the configurations were composed of varying ratio'd combinations of SCSI disks, IDE disks, and RAID volumes of the previous two.

On the configurations mentioned I would run two sets of tests to fill up the buffer cache. The first set would be to fill the disks up with tons of directories and other metadata, then run a "find -type f" to fill as much of main memory with buffer cache data as I could. The second test used "dbench X" where X was chosen such that 2.2.x (which doesn't have your LRU changes nor the new page cache stuff) only got minimal memory pressure and main memory held most of the written dirty data and metadata created by the benchmark.

During 1 second intervals, and also right after each test set, buffer cache snapshots were taken using my /proc/bcache interface and stored into files.

Next using this test data acquired from the machines I wrote a simulator. Into which various hash functions could be plugged in and various statistics about the distribution of the hash input bits could be obtained.

The simulator would simply use the hash function you selected, the hash table size you tell it, and build a hash table from the dump file to get a snapshot of buffer cache hash table state for any one of the dumps obtained during the test runs done above. It would print out all sorts of useful statistics such as longest hash chain length, shortest, average length, etc.

At this point I had all of the data and tools necessary to perform the analysis.

The next task of course was hash function experimentation and trying to quantize something about the behavior of the bits in the hash input values.

The simulator was first given the old buffer cache hash function, plus another function which just took the device/blocknr and jumbled all of the bits around evenly into the hash modulo bits. The latter was found to act better than the existing hash, but still left a few medium to long sized chains during the simulations.

To come up with the final hash function seen in the code right now I analyzed the bit changing distribution of each bit in each hash function input value from all the buffer cache state dumps.

Each bit in each of the two inputs was assigned a "changing priority" by the simulator. A bit which changed more often was assigned a higher priority. So for example a bit which was 0 half of the time and 1 half of the time would have the highest possible priority.

Bits which changed rarely or not at all are of no use to the hash, since they will not change the value much if at all. Bits which have a high rate of change, if possitioned in non-conflicting spots within the hash, will aide the distribution of the hash function.

With that in mind, and my bit changing priorities, I decided upon the positions where block encompassing high priority bit sets belonged within the hash modulo encompassing bits. This is how the hash function you see was derived.

Finally, I took this new hash function and plugged it into the simulator. It performed better than the other two test hash functions, and had the best distribution for all hash table size selections. On average the distribution was at worst %92 off of an ideal perfect even distribution. No hash function is perfect, and perfection was not what was strived for here.

I enclose below the dump hash analysis program in it's utter RAW form I left it in when I finished my buffer cache hash function tuning.

The hash table size is chosen by the HSHIFT macro, and the hash function is controlled by the HASH macro. Like I said this thing is in a very RAW form, which was fine for me since I had this constantly recompiled and in an editor during my work which is all I needed. I could turn on and off various forms of statistics as I needed them using preprossor directives.

Yes I most certainly did, I count processor cycles for a living in the work I do. Anyone who knows me well will tell you that I'll completely rearchitect the trap handling on UltraSparc from scratch just to save 2 processor cycles in the trap entry/exit code for that platform.

The computational cost in real life means:

1. Some _constant_ number of processor cycles
2. Some _constant_ set of instruction cache lines to hold to hash computation code

Compare this (in real life) to the cost of:

1. _Non-constant_ extra traversals through the main hash chain loop
2. _Non-constant_ memory references assosciated with touching significantly more than (nr_buffer_heads / nr_hash_chains) buffer heads.

And furthermore, I did not use any multiplications or other multi-cycle operations in the hash function.

Furthermore, if the hash table is almost empty, there isn't much buffer cache activity is there? So whatever small added cost my new hash function has is lost on the profiling radar compared to whatever other things the system must be doing.

I used UFS, MINIX, and ISO9660 file systems in my tests. I did not explicitly list the filesystem types I had used in my initial response, for this I apologize.

If it is impossible to generate a perfect hash for all input values, then some data set must be chosen to act as one which is representative of the data upon which the hash function can be expected to act.

I believe the data sets I chose to use are something a bit more than "empirical" as you have described it, and are a good representation of the data sets which will be seen by the general populace of Linux users.