Linux Kernel Primer
The Linux kernel source is an excellent case study for a modern, used, and tested operating system design. It was not, however, created as a teaching tool. The source is often not commented and provides very little hand holding. That said, there are a great many places and things to learn. A full description of the linux kernel source could span multiple books.
Obtaining the Source
http://www.kernel.org is the major source for all that is the linux kernel source code. http://lxr.free-electrons.com lets you browse the source online. It also has a very nice search engine.
Version Numbers
Basic history of the major functional changes:
- 1.0 and prior — x86 only, a.out binary format
- 1.2 — adds support for a few more CPU types, ELF binary format, modules
- 2.0 — adds SMP support
At 2.2 functionality reached a point where improvements became much more iterative. The 2.2 kernel implements most of the major features required of a modern kernel. Using anything below 2.2 as a reference or basis for a fork could easily result in serious architectural challenges for your derived code or design. Core improvements to the kernel have been made after 2.2, and the kernel developers had good reason for them.
The size of the kernel can be attributed to the plethora of file systems, device drivers, architecture supports, and kernel services and features. While 2.6 is a massive code base, removing the non-core parts reduces the size. Drivers take up over 100MB, non-i386 architectures, around 50MB, file systems, around 20MB. As a general rule, you won’t need to venture into the various subsystems and drivers that you are not using.
Browsing and Using The Source
It’s better to not try and follow the whole of the Linux kernel source as a single process flow. Different architectures start in different ways, but the generic portions can be found in init/. Keep in mind that an operating system kernel is very different from a user space program — the kernel is responding and servicing to user space requests.
Instead of trying to figure out a process flow for the entire kernel, try to figure out what’s going on for a single event or system call. System calls can easily be found by searching the code for functions beginning with «sys_». These generally have descriptive names that correspond to the kernel requirements for a C library call.
Looking at a driver source in Linux can tell you a great deal about a given piece of hardware functionality. Keep in mind that the Linux kernel source isn’t always «correct» about how it handles specific hardware. Many drivers were written with little or no documentation or standards information.
Unless you modify large portions of your kernel to use the same names and conventions of the Linux kernel, Linux kernel source is not easily ported away from Linux. Also, the source is GPL, so your kernel source is going to require proper licensing if you use anything. There are some exceptions to this rule, mostly in code shared between projects located in the Linux kernel tree.
The amount of infrastructure in Linux for basic system tasks — interrupt handlers, virtual memory, swap, block io — will make a lot of that code difficult to read if you are just starting. It might be better to read other tutorials here before looking at how a «real» kernel does things, so that you can recognize what is infrastructure setup and what is required to perform a given task. The interesting side effect is that big picture kernel logic, obscured in other small example kernels, becomes very clear in Linux. The scheduler algorithm, for instance, is fairly visible and easy to read in a single source file with little of the task swapping details obscuring how it works.
As the Linux kernel already provides tested mechanisms for many different tasks, creating a kernel module can allow you test your own kernel code. The downside to attempting this is that you’ll have to figure out how to «play nicely» with the portions of Linux you are trying to use.
Important Source Files
This list is by no means complete. These files provide common functionality likely to be required in any operating system kernel.
- Locking, Synchronization
- kernel/mutex.c, include/linux/mutex.h — kernel space mutex implementation
- kernel/futex.c — kernel level support for ‘fast’ userspace mutual exclusion
- kernel/spinlock.c, include/linux/spinlock.h — kernel spinlock implementation
- block/elevator.c — support for the various IO scheduling algorithms
- block/noop-iosched.c — the easiest to read and understand IO scheduler (noop)
- block/ll_rw_blk.c — where block requests meet a block device queue
- fs/read_write.c — read, write system calls
- fs/file.c — management of file handles
- fs/inode.c — functionality for inodes (file information structs, sometimes like kernel file handles)
- fs/open.c — contains several of the major file operations
- fs/cramfs/inode.c, fs/cramfs/uncompress.c — a very small filesystem with easy to read/find code*
- kernel/sched.c — the linux scheduler, schedule() is the function to look at here
- kernel/workqueue.c — a workqueue that provides a means for doing work
- arch/i386/kernel/process.c — large portion of process handling for x86
- fs/binfmt_elf.c — ELF loading
- mm/slab.c — slab allocator, also home for kmalloc
- mm/vmalloc.c — virtual contiguous memory allocator
- mm/page_alloc.c — buddy allocation
Finding what you are looking for
The arch/ directory contains architecture dependent files. If you want to learn about x86 development, the best place to look is arch/i386. Most any hardware specific functionality is contained in drivers/. Keep in mind that things like PCI are used by multiple architectures, and so they are located under drivers/ as well. Sound and Networking are treated differently and reside under their own directory sound/ and net/ with drivers in subdirectories there. Core kernel functionality lives in kernel/, and lib/.
There is «Documentation» in the Documentation directory. This directory is not what you think it is. It is more of a collection of tidbits of knowledge than any decent information on the kernel.
Resources
- https://kernelnewbies.org/ — guides for new Linux kernel developers
- http://www.tldp.org/HOWTO/KernelAnalysis-HOWTO.html — guide to the Linux kernel organized by subsystems
- https://syscalls.kernelgrok.com/ — a reference list of Linux syscalls
- Linux Kernel Development, by Robert Love — a very decent ‘overview’ book of the Linux kernel. It doesn’t go into too much detail, but provides enough of a big picture and detail view to really get started on a Linux kernel project.
- Understanding the Linux Kernel, David Bovet — more detailed than Linux Kernel Development. If you want to do more work than browsing the kernel, this has more of the detail required.
What is linux kernel porting
Sometimes, people show up with useful kernel-side things that were originally written for other systems and try to put them into Linux as (GPLv2) donations. Often these have been filesystems (SGI and XFS, IBM and JFS), but there have been other attempts at code drops. Most recently, Oracle made DTrace available under GPLv2 and integrated it into their kernel. I’ve said before that this is not an easy thing to do and can take years to actually get the code in to the Linux kernel (eg, XFS). Part of that is that the Linux kernel developers are picky about the code that they accept and require it to follow Linux kernel conventions (because they’ll be supporting it for years), but part of that is because joining up code written for another environment with the Linux kernel is a hard, long process, with lots of subtle issues that can be overlooked despite very good people with the best of intentions.
As it happens, I have an illustration of this. Before I start, I want to say explicitly that I think ZFS on Linux is a very solid and well done project. In fact, that it’s so solid and well done makes this case all the more useful as an illustration, because it shows how a bunch of very good people, working very hard (and for a long time) and doing a very good job, can still have something slip by in the interface between the Linux kernel and outside code. So here is the story.
Recently, someone on the ZFS on Linux mailing list reported a kernel panic related to snapshots (and also and the ZoL issue report). The first background detail required is that under some circumstances, accessing snapshots can get ELOOP from the kernel’s general filesystem code. The specific crash happened because when the kernel converted a NFS filehandle that was (apparently) for a file in a ZFS snapshot into a kernel dentry, the dentry pointer it got back from ZFS had the value of 0x28 (decimal 40). Although very low faulting addresses usually have causes related to NULL pointers, 40 happens to be the errno value for ELOOP , which is suspicious.
Internally, the Linux kernel has a somewhat odd way of handling errors. Probably in order to avoid confusing them with valid values that might be returned normally, errors are usually returned from functions as negative errno values; for example, if a pathname lookup fails because there’s no such name in the directory, the relevant functions will return -ENOENT (and there’s a whole infrastructure to smuggle these negative errno values in and out of what are normally pointers). Much of the rest of the world has kernel functions that return positive errnos to signal errors, and in particular the original Solaris/Illumos ZFS code uses positive errnos to return errors, so a ZFS function that wants to signal ‘no such name’ will return ENOENT .
The ZFS on Linux code tries to stay as close to the upstream Illumos ZFS code as possible to make it easier to port fixes and changes back and forth. As part of this, it has not changed to using Linux style negative errnos internally; instead, it converts from ZFS positive errnos (in its own code) to Linux kernel negative errnos when it returns results to the kernel, such as when it is converting a NFS filehandle into a ZFS dnode and then a kernel dentry, which may fail with errors like ESTALE . This conversion is done by negating the internal ZFS errno, turning a positive ZFS errno into a negative kernel errno (which is then smuggled inside a pointer).
All of this is fine except that there turns out to be a point in converting NFS filehandles where the ZFS on Linux code calls a kernel function to do path lookups and returns its error result unaltered. Since this is a kernel function, it returns negative errnos, which are passed up through the ZFS on Linux call stack and then carefully negated by ZoL before it returns them to the kernel. This careful negation turns what was a negative kernel errno into a positive number that the kernel thinks is not an error, but a dentry pointer. Things do not go well from here.
All of the code involved looks innocent and good on a normal inspection; you’re calling functions, you’re checking for errors, you’re returning errors if there are any, everything looks normal and standard. You need a bunch of contextual knowledge to know that this one function call is special and returns a dangerously different result from everything else (if it encounters an error at all, which it usually doesn’t), and it needs special handling. The commit that added this code is over a year old and was reviewed by one of the most experienced ZoL developers, and the code has passed tests and been used in production (where it worked because errors from this kernel function are very rare in this context).
This error is not in ZFS code and it is not in kernel code; it’s at the seam between the two, where one world must be carefully converted to the other. Here, one little spot was missed and joined imperfectly, and the result was a kernel panic a year later. And that’s part of why porting outside code into the Linux kernel is hard and takes a long time, one way or another.
(It also makes a good illustration of why the Linux kernel developers generally insist that outside code be converted over to use kernel idioms before they’ll accept it into the kernel tree.)