Kernel Traffic #234 For 6Oct2003

/*
 * If you refuse to depend on closed software for a critical
 * part of your business, these links may be useful:
 *
 * rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
 * rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
 * http://www.cobite.com/cvsps/
 *
 * svn://svn.kernel.org/linux-2.6/trunk
 * svn://svn.kernel.org/linux-2.4/trunk
 */

We're providing the service which enables all of the below and without our good will that service is at risk. You're publicly slamming the providers of that service.

If you want to do that, that's your right, but that leads us to ask:

• wasn't the deal that we do the gateway and you stop whining?
• why should we provide this gateway service at all if there is whining?
• why shouldn't we firewall you off since you are whining?
• or if firewalling fails, put in a day or two delay in the gateway?

Other people may not agree with your view on this one Pavel. Most people read that signature and saw it as a negative comment about BitKeeper.

People have told me they believe that if BitMover isn't getting benefit from the free use of BK, free BK will go away. People don't want to have to depend on my goodwill, they want BitMover to derive benefit so that my goodwill doesn't matter, it's just smart business to give BK away.

If that is really what people here think then that means there has to be some benefit for BitMover. One of the benefits is that we get to say that the kernel team uses it and get some marketing advantage out of that. But that benefit diminishes if what people are saying is negative.

It makes sense that people are uneasy about depending on BK given the amount of work it takes to provide it and the amount of grief we take for providing it. I don't know why I didn't see that earlier, it's an unstable situation.

I know there are some people who will never be happy until everything is GPLed, I can't help those people other than provide the gateway. In return, those people need to stop whining, the gateway has to be enough.

For the rest of the people, I'm looking for suggestions on how to make this situation more stable. It took me a while but I can see why you are nervous, I'd be nervous in your position. I'm nervous about doing any real marketing of the kernel's use of BK because I figured it would lead to more flame wars. I'm starting to think that if we were doing that it might actually lead to less flames, based on the theory that we would then need you so you continue to get BK for free. If you have an opinion on that I'd like to know it.

Continuing my yearly tradition of posting just one long novel to LKML every year, here is the literary update on the Prefetch Errata that the early 2.6 Kernels hit on AMD Athlon Processors.

This previously published errata can occur infrequently and is present in all AMD Athlon processors and earlier AMD Opteron/Athlon64 processors. See [1] and [2].

The full details are below, but the key point is that under certain circumstances, prefetch instructions can get memory management faults for addresses which would fault if they were accessed by a load or store instruction. We plan to revise our published errata with the new information below.

The errata requires a kernel workaround, but the good news is that it is:

• Harmless in most cases where it could occur. Most of the time the prefetch will be targeting memory that is accessible under the current privilege mode. So the page will simply be "faulted in" slightly earlier than needed.
• Rare and Infrequent. AMD Athlon processors have been available for years running numerous Operating Systems and only recently have we hit this errata outside of code specifically designed to target the errata -- requiring tens of thousands of iterations to cause it.
• It can be worked around. Andi Kleen has a 2.6 and a 2.4 Kernel patches that we have tested at AMD on a large number of AMD Athlon processors and AMD Opteron/Athlon64 processors (both legacy x86 and x86-64 long mode). It works just fine. (Andi will be posting them soon when he wakes up ;-)
• AMD is fixing this in future revisions of AMD Opteron/Athlon64 processors.
• Andi's kernel patches will not be needed on future AMD processors but it is forward compatible and so won't break on them either.

The Details

Software prefetch instructions are defined to ignore page faults. Under highly specific and detailed internal circumstances, the following conditions may cause the PREFETCH instruction to report a page fault.

• The target address of the PREFETCH would cause a page fault if the address was accessed by an actual memory load or store instruction under the current privilege mode.

• The instruction is a PREFETCH or PREFETCHNTA/0/1/2 followed in execution-order by an actual or speculative byte-sized load to the same address.

  In this case, the page fault exception error code bits for the faulting PREFETCH would be identical to that for a byte-sized load to the same address.

• The instruction is a PREFETCHW followed in execution-order by an actual or speculative byte-sized store to the same address.

  In this case, the page fault exception error code bits for the faulting PREFETCHW would be identical to that for a byte-sized store to the same address.

Note that some misaligned accesses can be broken up by the processor into multiple accesses where at least one of the accesses is a byte-sized access.

If the target address of the subsequent memory load or store is aligned and not byte-sized, this errata does not occur and no work-around is needed.

So the net effect is that an unexpected page fault may occur infrequently on a PREFETCH instruction.

Kernel Work-around

The kernel can work around the errata by modifying the Page Fault Handler in the following way. This is what Andi Kleen's patches do. Because the actual errata is infrequent it does not produce an excessive number of page faults that affect system performance.

• Continue to allow the page fault handler to satisfy the page fault. If the faulting instruction is permitted access to the page, return to it as usual.
• If the faulting instruction is not permitted access to the page, scan the instruction stream bytes at the faulting Instruction Pointer to determine if the instruction is a PREFETCH.
• If it is not a PREFETCH instruction, generate the appropriate memory access control violation as appropriate.
• If the faulting instruction is a PREFETCH instruction, simply return back to it; the internal hardware conditions that caused the PREFETCH to fault should be removed and operation should continue normally.

General Work-around

If the page-fault handler for a kernel can be patched as described above, no further action by software is required. The following general work-arounds should only be considered for kernels where the page-fault handler can not be patched and a PREFETCH instruction could end up targeting an address in an "inaccessible" page. (An "inaccessible" page is one for which memory accesses are not allowed under the current privilege mode.)

Because the actual errata is infrequent, it does not produce an excessive number of page faults that affect system performance. Therefore a page fault from a PREFETCH instruction for an address within an "accessible" page does not require any general work-around. (An "accessible" page is one for which memory accesses are allowed under the current privilege mode once the page is resident in memory)

Software can minimize the occurrence of the errata by issuing only one PREFETCH instruction per cache-line (a naturally-aligned 64-byte quantity on AMD Athlon and AMD Opteron/Athlon64) and ensuring one of the following:

• In many cases, if a particular target address of a prefetch is known to encounter this errata, simply change the prefetch to target the next byte.
• Avoid prefetching inaccessible memory locations, when possible.
• In the general case, ensure that the address used by the PREFETCH is offset into the middle of an aligned quadword near the end of the cache-line. For example, if the address desired to be prefetched is "ADDR", use an offset of 0x33 to compute the address used by the actual PREFETCH instruction as: "(ADDR & ~0x3f) + 0x33"

Footnotes

[1] AMD Athlon(tm) Processor Model 6 Revision Guide 24332F June 2003.

www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24332.pdf

[2] Revision Guide for AMD Opteron(tm) Processors 25759 Rev. 3.07 Aug 2003

www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25759.PDF

Here is a patch to detect a prefect exception for 2.6.0test5/i386

I'm posting the versions for 2.4.22/x86-64 and 2.4.22/i386 in separate mail. 2.6/x86-64 is not done yet, but will be in my next merge.

The patches only change the slow path in the page fault handler - PREFETCH is only checked for when the kernel would send a signal anyways or print an oops. The check is also rather cheap so it is unconditionally enabled.

It handles SSE2 prefetches and 3dnow! style prefetches.

The only tricky bit is that it has to be careful to avoid recursive segfaults. The prefetch checker can cause another page fault when it does __get_user, but these should not recurse more than once.

This is insured by the placement of the checks in the page fault handler and only checking for prefetches if the fault came from user space or the exception tables have been already checked. To make this work without a per task exception nest counter I had to change the SIGBUS handling path slightly. Now when an get/put_user in kernel causes a SIGBUS it is not delivered to user space. Instead you just get the standard EFAULT back.

It also removed Andrew's old workaround for the problem.

My understanding is that it will never be fixed on the K7 (current Athlons), And these will be with us for a long time; more or less forever, just like the f00f bug :-)

I would agree with you if the patch had some bad impact on common paths, but I don't think that's the case here. It merely adds a cheap check to an already slow path.

On the other hand the errata is so unlikely that I doubt it will be frequently hit anyways. 2.6 kernel hitting it was just very very unlucky, and it only did so very infrequently.

Just to fix the kernel we could have chosen a different workaround, like adding an exception table entry to each prefetch and jumping back (I did that on the x86-64 port originally). But this way is also not that bad and it fixes hypothetical user space programs that could maybe hit it too.

Of course they may want to also fix it in a different way to run on older kernels (e.g. handling the signal in user space or avoiding the conditions). But doing it centrally in the kernel is a bit cleaner and at some point people have to update their kernels anyways.

My reading of the boilerplate is that I can't use their code in another GPL program, because their patent grant doesn't extend to other programs.

Even if that's permitted by the GPL, it doesn't mean you have to accept it into the kernel like that.

If that's just a misunderstanding of the legalese on my part, then IMHO the text needs to be clarified to ensure that everyone knows they may take the code and use it in other GPL projects.

We request that the following patch for additional kernel event notifications be included in the upcoming 2.6.x kernel.

The current profiling hooks provide notifications at the end of a task's lifetime (i.e., task exit, mmap exit, and exec unmap). We would like to have additional notifications on the start of a task (i.e., fork, execve, kernel image loads, and user image loads).

We believe that profiling tools such as Oprofile, Perfmon, and VTune would benefit from the additional hooks by improving the accuracy and completeness of the performance data, especially when working in environments that can dynamically create and destroy executable code (such as Java). Furthermore, these hooks could be used to measure different types of performance data (e.g., "forks per second") which are currently not available any other way.

Our patch follows the conventions used by the current profiling hooks, and is relatively small.

We would appreciate comments/feedback on our proposal.

Our sampling driver kernel module which uses these hooks is GPL and could be included in the kernel.org tree.

The current version of the driver (also GPL, but which hooks the sys_call_table for 2.4.x-based kernels) is posted at,

http://www.intel.com/software/products/opensource/vdk/

We plan to post our new driver for kernel 2.6.0-test5 (with the event notification patch applied) on both IA-32 and IA-64 to the above site early next week.

That code seems to have a lot of infrastructure for buffering samples, transferring it to userspace, etc.

Have you looked into using the infrastructure in drivers/oprofile/ for this? In other words: is it possible to augment the kernel's existing oprofile capabilities so they meet VTune requirements?

As everyone knows it is a bad idea to let the kernel guess whether there is a partition table on a given block device, and if so, of what type. Nevertheless this is what almost everybody does.

Until now the philosophy was: floppies do not have a partition table, disks do have one, and for ZIP drives nobody knows. With USB we get more types of block device that may or may not have a partition table (and if they have none, usually there is a FAT filesystem with bootsector). In such cases the kernel assumes a partition table, and creates a mess if there was none. Some heuristics are needed.

Many checks are possible (for a DOS-type partition table: boot indicator must be 0 or 0x80, partitions are not larger than the disk, non-extended partitions are mutually disjoint; for a boot sector: it starts with a jump, the number of bytes per sector is 512 or at least a power of two, the number of sectors per cluster is 1 or at least a power of two, the number of reserved sectors is 1 or 32, the number of FAT copies is 2, ...).

I tried a minimal test, and the below is good enough for the boot sectors and DOS-type partition tables that I have here.

So, question: are there people with DOS-type partition tables or FAT fs bootsectors where the below gives the wrong answer? I would be interested in a copy of the sector.

I expect to submit some sanity check to DOS-type partition table parsing, and hope to recognize with high probability the presence of a full disk FAT filesystem.

So you say, and so you've said for a long time, but claiming that "everybody knows it" is clearly not true.

In particular, I think that a kernel that doesn't do partitioning is quite fundamentally broken. I'm sure others will agree.

If you have unusual cases (and let's face it, they don't much happen - we have traditionally had _very_ few problems with getting things partitioned) then you should be able to override them from user space and have user space be able to tell the kernel about special partitions.

And hey, surprise surprise, you can do exactly that.

Also, surprise surprise, pretty much nobody actually does it. Because the defaults are so sane.

Repeat after me: make the defaults so sane that most people don't even have to think about it.

In short, I think your first sentence (upon which the rest of the argument depends) is just quite _fundamentally_ flawed.

First, if the kernel comes up with a bogus partition table, this will confuse users (and user space) greatly. It is not harmless, even though you would know how to survive.

Second, if the kernel reads random stuff from flash media that may yield I/O errors. Such media do often not have blocks at a fixed place, but have at the start a table that says where on the media a given block lives. Blocks that have never been written do not occur in the table, and attempts to read them give an I/O error. (And our famous SCSI error handling may want to retry a few times, reset the device and retry, reset the bus and retry .. I have seen boot times of a quarter of an hour because the kernel was busy retrying SmartMedia accesses.) In short - we should not read random blocks from a disk on flash media.

The _worst_ thing that can happen is that you have four extra (totally bogus) partitions, and you end up using the whole device.

That's my point about partitioning - not that it's necessarily perfect, but even when it _isn't_ perfect, it's no worse than not partitioning at all.

Letting mount or the kernel guess the type of the filesystem to mount is bad. If the kernel or mount guesses wrong the result can be fs corruption and kernel crash. So the right approach is to always give a -t option to mount and a rootfstype= boot option to the kernel.

But most people don't, and survive. And I maintain mount and over time a system of heuristics has been built into mount to make it rather likely that a guess will be correct.

The partition situation is similar but a bit worse. We have the second half: likely guesses, but we lack the first half: correctness with certainty.

What probably will happen as a result of this episode is that the likelihood of certain guesses is improved a bit. But I wouldnt mind the option of having certainty instead of probability. Userspace that tells the kernel, instead of letting the kernel probe.

DSI development team would like to announce the release 0.2 of digsig.

This kernel module (for 2.5.66 and higher) checks the signature of the binary before running it. The main goal is to insert digital signatures inside the ELF binary and verify this signature before loading the binary. It is based on the Linux Security Module hooks.

The code is GPL and available from: http://sourceforge.net/projects/disec/, download digsig-0.2.

I hope that it'll be useful to you. All bug reports and feature requests or general feedback are welcome (please CC me in your answer or feedback to the mailing list).

overview

Instead of writing a long detailed explication, I rather give you an example of how you can use it.

A Very simple scenraio to show how to use it

1) Generate gpg key and export your public key in order to use it for signature verification.

$gpg --gen-key

=> careful generate RSA key

$gpg --export >> my_public_key.pub

2) Sign your binaries using Bsign

Before using bsign to sign all your binaries, try out with a simple example.

$cp `which ps` ps-test
$bsign -s ps-test / sign the binary
$bsign -v ps-test / be sure that the signature is valid

3) Make the digsig module

From ./digsig, do make -C /usr/src/linux-2.5.66 SUBDIRS=$PWD modules. You need rw acess to /usr/src/linux-2.5.66.

CAREFULL: we advice you to compile the module in debug mode at your first tries (see -DDSI_DEBUG -DDSI_DIGSIG_DEBUG in the Makefile). In this mode, the module verifies the signatures but does not enforce the security (if not any signature present in your binary, you'll have a message in /var/log/messages but the execution is not aborted.). However, the execution of the bianaries with invalid signatures is aborted. Once, you're sure of your binary signature procedure you can recompile the whole on non-debug mode.

4) load digsig, use the public key exported in step 1 as argument

root@colby digsig-dev]# ./digsig.init start pubkey.pub
Loading Digsig module.
Making device for communication with the module.
Loading public key.
Done.
root@colby digsig-dev]#

5) In debug mode:

$./ps-test

$tail -f /var/log/messages
Sep 16 15:49:16 colby kernel: DSI-LSM MODULE - binary is ./ps-test
Sep 16 15:49:16 colby kernel: DSI-LSM MODULE - dsi_bprm_compute_creds:
Found signature section
Sep 16 15:49:16 colby kernel: DSI-LSM MODULE - dsi_bprm_compute_creds:
Signature verification successful

$ps

/ no check for not signed binaries
$tail -f /var/log/messages
Sep 16 15:49:16 colby kernel: DSI-LSM MODULE - binary is ./ps

6) In restrictive mode, normal mode

You need to use bsign to sign all binaries that you want to run in normal mode.

/ signed binary
[lmcmpou@reblochon lmcmpou]$ ps
 PID TTY          TIME CMD
6897 pts/2    00:00:00 bash
6941 pts/2    00:00:00 ps

/ not signed binary
[lmcmpou@reblochon lmcmpou]$ ./ps-makan-1
bash: ./ps-makan: cannot execute binary file

/ binary with wrong signature
[lmcmpou@reblochon lmcmpou]$ ./ps-makan-2
bash: ./ps-makan-colby: Operation not permitted

7) Unload the module.

[root@colby digsig-dev]# ./digsig.init stop
Unloading Digsig.

Performances

This is release 0.2. We have done some benchmarks.

We ran lmbench on a Pentium IV, 2.4 GHz, 500 mega bytes of memory, running Linux 2.5.66. Our benchmarks show that the execution time (exec function call) multiplies by a factor of 4 when the module is loaded (no changes for fork call, as the binary is not loaded into memory).

Some details

The module is independent from DSI (parent project) and you don't need to download the whole dsi tar ball to play with the digsig module (even if we'll be more than happy to have your feedback about dsi project :-)).

Our approach has been to use the existing solutions like gpg and bsign rather than reinventing the whole thing from scratch.

However, in order to reduce the overhead in the kernel, we took only the minimum code necessary from GPG. We took only the MPI (Multi Precision Integer) source code and the RSA crypto source code. This helped much to reduce the amount of code imported to the kernel in sourc code of the original (only 1/10 of the original gnupg 1.2.2 sourc code has been imported to the kernel module). On the other hand, we avoided OpenSSL source code for the fact that the licensing was not clear to us. We did some tests at user level and found out that OpenSSL is 4 times faster than GPG regarding RSA verification. As a future direction, we plan to clarify this licensing issue and use OpenSSL instead of GPG.

Requirements:

Linux OS kernel 2.5.66 or higher. We tested against 2.5.66 and 2.6.0-test5.

Bsign version 0.4.5. (http://packages.debian.org/unstable/admin/bsign.html)

GPG 1.2.2 or higher.

Merits

This work has been done by (alphabetical order)

A Apvrille ([email protected]),
D Gordon ([email protected]),
M Pourzandi ([email protected]),
V Roy ([email protected]).

Special merits go to David who wrote big chunks of the source code.

Thanks to Radu Filip ([email protected]) which has done the initial study for this work.

Thanks also to Marc Singer who helped us in using Bsign.