23

When I try to implement the C string library myself, I found that glibc and the Linux kernel have a different way to implement some functions. For instance, glibc memchr and glibc strchr use some trick to speed up the function but the kernel memchr and the kernel strchr don't. Why aren't the Linux kernel functions optimized like glibc?

40

The kernel does have optimised versions of some of these functions, in the arch-specific directories; see for example the x86 implementation of memchr (see all the memchr definitions, and all the strchr definitions). The versions you found are the fallback generic versions; you can spot these by looking for the protective check, #ifndef __HAVE_ARCH_MEMCHR for memchr and #ifndef __HAVE_ARCH_STRCHR for strchr.

The C library’s optimised versions do tend to used more sophisticated code, so the above doesn’t explain why the kernel doesn’t go to such great lengths to go fast. If you can find scenarios where the kernel would benefit from a more optimised version of one of these functions, I imagine a patch would be welcome (with appropriate supporting evidence, and as long as the optimised function is still understandable — see this old discussion regarding memcpy). But I suspect the kernel’s uses of these functions often won’t make it worth it; for example memcpy and related functions tend to be used on small buffers in the kernel. And never discount the speed gains from a short function which fits in cache or can be inlined...

In addition, as mentioned by Iwillnotexist Idonotexist, MMX and SSE can’t easily be used in the kernel, and many optimised versions of memory-searching or copying functions rely on those.

In many cases, the version used ends up being the compiler’s built-in version anyway, and these are heavily optimised, much more so than even the C library’s can be (for example, memcpy will often be converted to a register load and store, or even a constant store).

  • 9
    Do note that in some circumstances these functions might be intentionally less performant in order to attain goals other that performance (e.g. binary size as mentioned, but also timings/security against side channel attacks, portability, ...), so just making a pull request "this is more performant (on arch X)" might be rejected because of those reasons. – hoffmale Feb 12 at 1:11
  • 10
    The kernel version of many functions, perhaps including *chr(), may also deliberately avoid using vector registers because it would require enabling them and/or saving their state, which might not yet have been done and/or may increase latency. – Iwillnotexist Idonotexist Feb 12 at 2:57
  • 3
    Another thing: the glibc functions are technically illegal code as per the C standard, because they contain a deliberate read-in buffer overrun (due to the fact they read in 4-byte chunks, and then think about what happens if the string length is not a multiple of 4) which is Undefined Behavior (UB) according to the C standard, but because this is the compiler, one can "get away" with it because it can be programmed to let this one slide - in effect, forming a non-standard "dialect" specifically for writing its own standard facility libraries in a performant way. – The_Sympathizer Feb 12 at 11:58
  • 2
    @The_Sympathizer Linux uses the same trick; it's not meant to be able to work with any compiler, only GCC with specific flags. – user253751 Feb 12 at 13:27
  • 1
    @Shadur 99% of known cases is not really acceptable in glibc, if it was 100% before. – user253751 Feb 12 at 14:23
6

I remember that I had to fix a kernel core dump bug in Solaris in 2006 that was triggered with a ISO-9660 + Rock Ridge file system created by something other than mkisofs.

That ISO formatting software did not include the Rock Ridge file name in the middle of the ISO-9660 directory entry (as done by mkisofs) but at the end of the ISO-9660 directory entry. Now you need to know that the Rock Ridge filenames are not terminated by a null byte...

What happened was that the (at that time too much optimized) string routines in the Solaris kernel could overshoot by one in some cases and if the Rock Ridge file name ended exactly at the end of a 2k sector and that sector ended just at the end of a 4k kernel memory page, this overshoot access caused a kernel panic due to an illegal memory access.

We needed to rewrite the access code to be very conservative in order to prevent this kernel panic in the future.

As you see, it is sometimes much harder to write safe code for the kernel and such code is sometimes a bit slower just in order to avoid a kernel panic.

BTW: the problem with a potentially unpredictable prefetch from the CPU in user space programs can be handled by letting the linker add a few bytes after the segments if there is the potential to hit the end of a MMU page. This does not work in a kernel that depends om mmaping areas.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.