On the 2.6.x kernels there are four main frontend programs: config, menuconfig, and xconfig.
config is the least user-friendly option as it merely presents a series of questions that must be answered sequentially. Alas, if an error is made you must begin the process from the top. Pressing Enter will accept the default entry which is in upper case.
oldconfig will read the defaults from an existing .config and rewrite necessary links and files. Use this option if you've made minor changes to source files or need to script the rebuild process.
menuconfig is an ncurses based frontend. Your system must have the ncurses-devel libraries installed in order to use this utility. As the help text at the top of the screen indicates, use the arrow keys to navigate the menu. Press Enter to select sub-menus. Press the highlighted letter on each option to jump directly to that option. To build an option directly into the kernel, press Y. To disable an option entirely, press N. To build an option as a loadable module, press M. You can also access content-specific help screens by pressing ? on each page or selecting HELP from the lower menu. Figure 1 in the Section called Configuring the 2.4.x kernels shows an example screen from the 2.4.x kernel series.
xconfig is a graphical frontend using qconf by Roman Zippel. It requires the qt and X libraries to build and use. The interface is intuitive and customizable. Online help is automatically shown for each kernel configuration option. It also can show dependency information for each module which can help diagnose build errors. Figure 3 shows an example of the xconfig screen. From the online help:
For each option, a blank box indicates the feature is disabled, a check
indicates it is enabled, and a dot indicates that it is to be compiled
as a module. Clicking on the box will cycle through the three states.
If you do not see an option (e.g., a device driver) that you believe
should be present, try turning on Show All Options under the Options menu.
Although there is no cross reference yet to help you figure out what other
options must be enabled to support the option you are interested in, you can
still view the help of a grayed-out option.
--qconf help
Figure 3. make xconfig
Once you have decided which configuration option to use, start the process with make followed by either config, menuconfig, or xconfig. For example:
$ make menuconfig
The system will take a few moments to build the configuration utility. Next you will be presented with the configuration menus. Though similar to the 2.4.x series, the 2.6.x menu is more logically organized with better grouping of sub-modules. Following are some of the top level configuration options in the 2.6 kernel.
Code Maturity Level Options
This option allows configuration of alpha-quality software or obsoleted drivers. It is best to disable this option if the kernel is intended for a stable production system. If you require an experimental feature in the kernel, such as a driver for new hardware, then enable this option but be aware that it "may not meet the normal level of reliability" as more rigorously tested code.
General Setup
This section contains options for sysctl support, a feature allowing run-time configuration of the kernel. A new feature, kernel .config support, allows the complete kernel configuration to be viewed during run-time. This addresses many requests to be able to see what features were compiled into the kernel.
Loadable Module Support
You will almost certainly want to enable module support. If you will need third-party kernel modules you will also need to enable Set Version Information on All Module Symbols.
Processor Type and Features
This is perhaps the most important configuration choice. we determin our processor type by examining /proc/cpuinfo and we use that information here to select the appropriate processor. Included in this submenu are features such as Preemptible Kernel which can improve desktop responsiveness, Symmetric Multi-processing Support for machines with multiple CPUs, and High Memory Support for machines with more than 1G of RAM.
Power Management Options
Found here are options for ACPI and CPU Frequency Scaling which can dramatically improve laptop power usage. Read the Documentation/power file for more information.
Bus Options ( PCI, PCMCIA, EISA, MCA, ISA)
Here are found options for all system bus devices. On modern machines the ISA and MCA support can often be disabled.
Executable File Formats
Interesting features here include the kernel support for miscellaneous binaries, which can allow seamless operation of non-Linux binaries with a little userland help.
Device Drivers
All the device-driver configuration options that were previously scattered throughout the 2.4.x menus are now neatly organized under this option. Features such as SCSI support, graphic card optimizations, sound, USB and other hardware are configured here.
File Systems
Found here are options for filesystems which are supported by the kernel, such as EXT2 and ReiserFS. It is best to build support for the root filesystems directly into the kernel rather than as a module.
Security Options
Interesting options here include support for NSA Security Enhanced Linux and other, somewhat experimental, features to increase security.
Wednesday, July 25, 2007
Tuesday, July 24, 2007
Dynamic Kernels: Modularized Device Drivers
Although this is very old article, gives u lot of knowledge about the device drivers.
Some of the things mentioned here changed by this day.
By Alessandro Rubini on Fri, 1996-03-01 02:00. SysAdmin
This is the first in a series of four articles co-authored by Alessandro Rubini and Georg Zezchwitz which present a practical approach to writing Linux device drivers as kernel loadable modules. This installment presents and introduction to thte topic, preparing the reader to understand next month's installment.
Kernel modules are a great feature of recent Linux kernels. Although most users feel modules are only a way to free some memory by keeping the floppy driver out of the kernel most of the time, the real benefit of using modules is support for adding additional devices without patching the kernel source. In the next few Kernel Korners Georg Zezschwitz and I will try to introduce the ``art'' of writing a powerful module---while avoiding common design errors.
What is a device?
A device driver is the lowest level of the software that runs on a computer, as it is directly bound to the hardware features of the device.
The concept of ``device driver'' is quite abstract, actually, and the kernel can be considered like it was a big device driver for a device called ``computer''. Usually, however, you don't consider your computer a monolithic entity, but rather a CPU equipped with peripherals. The kernel can thus be considered as an application running on top of the device drivers: each driver manages a single part of the computer, while the kernel-proper builds process scheduling and file-system access on top of the available devices.
See Figure 1.
A few mandatory drivers are ``hardwired'' in the kernel, such as the processor driver and the the memory driver; the others are optional, and the computer is usable both with and without them---although a kernel with neither the console driver nor the network driver is pointless for a conventional user.
The description above is somehow a simplistic one, and slightly philosophical too. Real drivers interact in a complex way and a clean distinction among them is sometimes difficult to achieve.
In the Unix world things like the network driver and a few other complex drivers belong to the kernel, and the name of device driver is reserved to the low-level software interface to devices belonging to the following three groups:
character devices
Those which can be considered files, in that they can be read-from and/or written-to. The console (i.e. monitor and keyboard) and the serial/parallel ports are examples of character devices. Files like /dev/tty0 and /dev/cua0 provide user access to the device. A char device usually can only be accessed sequentially.
block devices
Historically: devices which can be read and written only in multiples of the block-size, often 512 or 1024 bytes. These are devices on which you can mount a filesystem, most notably disks. Files like /dev/hda1 provide access to the devices. Blocks of block devices are cached by the buffer cache. Unix provides uncached character devices corresponding to block devices, but Linux does not.
network interfaces
Network interfaces don't fall in the device-file abstraction. Network interfaces are identified by means of a name (such as eth0 or plip1) but they are not mapped to the filesystem. It would be theoretically possible, but it is impractical from a programming and performance standpoint; a network interface can only transfer packets, and the file abstraction does not efficiently manage structured data like packets.
The description above is rather sketchy, and each flavour of Unix differs in some details about what is a block device. It doesn't make too much a difference, actually, because the distinction is only relevant inside the kernel, and we aren't going to talk about block drivers in detail.
What is missing in the previous representation is that the kernel also acts as a library for device drivers; drivers request services from the kernel. Your module will be able to call functions to perform memory allocation, filesystem access, and so on.
As far as loadable modules are concerned, any of the three driver-types can be constructed as a module. You can also build modules to implement filesystems, but this is outside of our scope.
These columns will concentrate on character device drivers, because special (or home-built) hardware fits the character device abstraction most of the time. There are only a few differences between the three types, and so to avoid confusion, we'll only cover the most common type.
You can find an introduction to block drivers in issues 9, 10, and 11 of Linux Journal, as well as in the Linux Kernel Hackers' Guide. Although both are slightly outdated, taken together with these columns, they should give you enough information to get started.
What is a module?
A module is a code segment which registers itself with the kernel as a device driver, is called by the kernel in order to communicate with the device, and in turn invokes other kernel functions to accomplish its tasks. Modules utilize a clean interface between the ``kernel proper'' and the device, which both makes the modules easy to write and keeps the kernel source code from being cluttered.
The module must be compiled to object code (no linking; leave the compiled code in .o files), and then loaded into the running kernel with insmod. The insmod program is a runtime linker, which resolves any undefined symbols in the module to addresses in the running kernel by means of the kernel symbol table.
This means that you can write a module much like a conventional C-language program, and you can call functions you don't define, in the same way you usually call printf() and fopen() in your application. However, you can count only on a minimal set of external functions, which are the public functions provided by the kernel. insmod will put the right kernel-space addresses in your compiled module wherever your code calls a kernel function, then insert the module into the running Linux kernel.
If you are in doubt whether a kernel-function is public or not, you can look for its name either in the source file /usr/src/linux/kernel/ksyms.c or in the run-time table /proc/ksyms.
To use make to compile your module, you'll need a Makefile as simple as the following one:
TARGET = myname
ifdef DEBUG
# -O is needed, because of "extern inline"
# Add -g if your gdp is patched and can use it
CFLAGS = -O -DDEBUG_$(TARGET) -D__KERNEL__ -Wall
else
CFLAGS = -O3 -D__KERNEL__ -fomit-frame-pointer
endif
all: $(TARGET).o
As you see, no special rule is needed to build a module, only the correct value for CFLAGS. I recommend that you include debugging support in your code, because without patches, gdb isn't able to take advantage of the symbol information provided by the -g flag to a module while it is part of the running kernel.
Debugging support will usually mean extra code to print messages from within the driver. Using printk() for debugging is powerful, and the alternatives are running a debugger on the kernel, peeking in /dev/mem, and other extremely low-level techniques. There are a few tools available on the Internet to help use these other techniques, but you need to be conversant with gdb and be able to read real kernel code in order to benefit from them. The most interesting tool at time of writing is kdebug-1.1, which lets you use gdb on a running kernel, examining or even changing kernel data structures (including those in loaded kernel modules) while the kernel is running. Kdebug is available for ftp from sunsite.unc.edu and its mirrors under /pub/Linux/kernel.
Just to make things a little harder, the kernel equivalent of the standard printf() function is called printk(), because it does not work exactly the same as printf(). Before 1.3.37, conventional printk()'s generated lines in /var/adm/messages, while later kernels will dump them to the console. If you want quiet logging (only within the messages file, via syslogd) you must prepend the symbol KERN_DEBUG to the format string. KERN_DEBUG and similar symbols are simply strings, which get concatenated to your format string by the compiler. This means that you must not put a comma between KERN_DEBUG and the format string. These symbols can be found in, and are documented there. Also, printk() does not support floating point formats.
Remember, that syslog write to the messages file as soon as possible, in order to save all messages on disk in case of a system crash. This means that an over-printk-ed module will slow down perceptibly, and will fill your disk in a short time.
Almost any module misbehaviour will generate an [cw]Oops[ecw] message from the kernel. An Oops is what happens when the kernel gets an exception from kernel code. In other words, Oopses are the equivalent of segmentation faults in user space, though no core file is generated. The result is usually the sudden destruction of the responsible process, and a few lines of low-level information in the messages file. Most Oops messages are the result of dereferencing a NULL pointer.
This way to handle disasters is a friendly one, and you'll enjoy it whenever your code is faulty: most other Unices produce a kernel panic instead. This does not mean that Linux never panics. You must be prepared to generate panics whenever you write functions that operate outside of a process context, such as within interrupt handlers and timer callbacks.
The scarce, nearly unintelligible information included with the [cw]Oops[ecw] message represents the processor state when the code faulted, and can be used to understand where the error is. A tool called ksymoops is able to print more readable information out of the oops, provided you have a kernel map handy. The map is what is left in /usr/src/linux/System.map after a kernel compilation. Ksymoops was distributed within util-linux-2.4, but was removed in 2.5 because it has been included in the kernel distribution during the linux-1.3 development.
If you really understand the Oops message, you can use it as you want, like invoking gdb off-line to disassemble the whole responsible function. if you understand neither the Oops nor the ksymoops output, you'd better add some more debugging printk() code, recompile, and reproduce the bug.
The following code can ease management of debugging messages. It must reside in the module's public include file, and will work for both kernel code (the module) and user code (applications). Note however that this code is gcc-specific. Not too big a problem for a kernel module, which is gcc-dependent anyway. This code was suggested by Linus Torvalds, as an enhancement over my previous ansi-compliant approach.
#ifndef PDEBUG
# ifdef DEBUG_modulename
# ifdef __KERNEL__
# define PDEBUG(fmt, args...) printk (KERN_DEBUG fmt , ## args)
# else
# define PDEBUG(fmt, args...) fprintf (stderr, fmt , ## args)
# endif
# else
# define PDEBUG(fmt, args...)
# endif
#endif
#ifndef PDEBUGG
# define PDEBUGG(fmt, args...)
#endif
After this code, every PDEBUG("any %i or %s...\n", i, s); in the module will result in a printed message only if the code is compiled with -DDEBUG_modulename, while PDEBUGG() with the same arguments will expand to nothing. In user mode applications, it works the same, except that the message is printed to stderr instead of the messages file.
Using this code, you can enable or disable any message by removing or adding a single G character.
Writing Code
Let's look at what kind of code must go inside the module. The simple answer is ``whatever you need''. In practice, you must remember that the module is kernel code, and must fit a well-defined interface with the rest of Linux.
Usually, you start with header inclusion. And you begin to have contraints: you must always define the __KERNEL__ symbol before including any header unless it is defined in your makefile, and you must only include files pertaining to the and hierarchies. Sure, you can include your module-specific header, but never, ever, include library specific files, such as or .
The code fragment in Listing 1 represents the first lines of source of a typical character driver. If you are going to write a module, it will be easier to cut and paste these lines from existing source rather than copying them by hand from this article.
#define __KERNEL__ /* kernel code */
#define MODULE /* always as a module */
#include /* can't do without it */
#include /* and this too */
/*
* Then include whatever header you need.
* Most likely you need the following:
*/
#include /* ulong and friends */
#include /* current, task_struct, other goodies */
#include /* O_NONBLOCK etc. */
#include /* return values */
#include /* request_region() */
#include /* system name and global items */
#include /* kmalloc, kfree */
#include /* inb() inw() outb() ... */
#include /* unreadable, but useful */
#include "modulename.h" /* your own material */
After including the headers, there comes actual code. Before talking about specific driver functionality---most of the code---it is worth noting that there exist two module-specific functions, which must be defined in order for the module to be loaded:
int init_module (void);
void cleanup_module (void);
The first is in charge of module initialization (looking for the related hardware and registering the driver in the appropriate kernel tables), while the second is in charge of releasing any resources the module has allocated and deregistering the driver from the kernel tables.
If these functions are not there, insmod will fail to load your module.
The init_module() function returns 0 on success and a negative value on failure. The cleanup_module() function returns void, because it only gets invoked when the module is known to be unloadable. A kernel module keeps a usage count, and cleanup_module() is only called when that counter's value is 0 (more on this later on).
Skeletal code for these two functions will be presented in the next installment. Their design is fundamental for proper loading and unloading of the module, and a few details must dealt with. So here, I'll introduce you to each of the details, so that next month I can present the structure without explaining all the details.
contd....
Some of the things mentioned here changed by this day.
By Alessandro Rubini on Fri, 1996-03-01 02:00. SysAdmin
This is the first in a series of four articles co-authored by Alessandro Rubini and Georg Zezchwitz which present a practical approach to writing Linux device drivers as kernel loadable modules. This installment presents and introduction to thte topic, preparing the reader to understand next month's installment.
Kernel modules are a great feature of recent Linux kernels. Although most users feel modules are only a way to free some memory by keeping the floppy driver out of the kernel most of the time, the real benefit of using modules is support for adding additional devices without patching the kernel source. In the next few Kernel Korners Georg Zezschwitz and I will try to introduce the ``art'' of writing a powerful module---while avoiding common design errors.
What is a device?
A device driver is the lowest level of the software that runs on a computer, as it is directly bound to the hardware features of the device.
The concept of ``device driver'' is quite abstract, actually, and the kernel can be considered like it was a big device driver for a device called ``computer''. Usually, however, you don't consider your computer a monolithic entity, but rather a CPU equipped with peripherals. The kernel can thus be considered as an application running on top of the device drivers: each driver manages a single part of the computer, while the kernel-proper builds process scheduling and file-system access on top of the available devices.
See Figure 1.
A few mandatory drivers are ``hardwired'' in the kernel, such as the processor driver and the the memory driver; the others are optional, and the computer is usable both with and without them---although a kernel with neither the console driver nor the network driver is pointless for a conventional user.
The description above is somehow a simplistic one, and slightly philosophical too. Real drivers interact in a complex way and a clean distinction among them is sometimes difficult to achieve.
In the Unix world things like the network driver and a few other complex drivers belong to the kernel, and the name of device driver is reserved to the low-level software interface to devices belonging to the following three groups:
character devices
Those which can be considered files, in that they can be read-from and/or written-to. The console (i.e. monitor and keyboard) and the serial/parallel ports are examples of character devices. Files like /dev/tty0 and /dev/cua0 provide user access to the device. A char device usually can only be accessed sequentially.
block devices
Historically: devices which can be read and written only in multiples of the block-size, often 512 or 1024 bytes. These are devices on which you can mount a filesystem, most notably disks. Files like /dev/hda1 provide access to the devices. Blocks of block devices are cached by the buffer cache. Unix provides uncached character devices corresponding to block devices, but Linux does not.
network interfaces
Network interfaces don't fall in the device-file abstraction. Network interfaces are identified by means of a name (such as eth0 or plip1) but they are not mapped to the filesystem. It would be theoretically possible, but it is impractical from a programming and performance standpoint; a network interface can only transfer packets, and the file abstraction does not efficiently manage structured data like packets.
The description above is rather sketchy, and each flavour of Unix differs in some details about what is a block device. It doesn't make too much a difference, actually, because the distinction is only relevant inside the kernel, and we aren't going to talk about block drivers in detail.
What is missing in the previous representation is that the kernel also acts as a library for device drivers; drivers request services from the kernel. Your module will be able to call functions to perform memory allocation, filesystem access, and so on.
As far as loadable modules are concerned, any of the three driver-types can be constructed as a module. You can also build modules to implement filesystems, but this is outside of our scope.
These columns will concentrate on character device drivers, because special (or home-built) hardware fits the character device abstraction most of the time. There are only a few differences between the three types, and so to avoid confusion, we'll only cover the most common type.
You can find an introduction to block drivers in issues 9, 10, and 11 of Linux Journal, as well as in the Linux Kernel Hackers' Guide. Although both are slightly outdated, taken together with these columns, they should give you enough information to get started.
What is a module?
A module is a code segment which registers itself with the kernel as a device driver, is called by the kernel in order to communicate with the device, and in turn invokes other kernel functions to accomplish its tasks. Modules utilize a clean interface between the ``kernel proper'' and the device, which both makes the modules easy to write and keeps the kernel source code from being cluttered.
The module must be compiled to object code (no linking; leave the compiled code in .o files), and then loaded into the running kernel with insmod. The insmod program is a runtime linker, which resolves any undefined symbols in the module to addresses in the running kernel by means of the kernel symbol table.
This means that you can write a module much like a conventional C-language program, and you can call functions you don't define, in the same way you usually call printf() and fopen() in your application. However, you can count only on a minimal set of external functions, which are the public functions provided by the kernel. insmod will put the right kernel-space addresses in your compiled module wherever your code calls a kernel function, then insert the module into the running Linux kernel.
If you are in doubt whether a kernel-function is public or not, you can look for its name either in the source file /usr/src/linux/kernel/ksyms.c or in the run-time table /proc/ksyms.
To use make to compile your module, you'll need a Makefile as simple as the following one:
TARGET = myname
ifdef DEBUG
# -O is needed, because of "extern inline"
# Add -g if your gdp is patched and can use it
CFLAGS = -O -DDEBUG_$(TARGET) -D__KERNEL__ -Wall
else
CFLAGS = -O3 -D__KERNEL__ -fomit-frame-pointer
endif
all: $(TARGET).o
As you see, no special rule is needed to build a module, only the correct value for CFLAGS. I recommend that you include debugging support in your code, because without patches, gdb isn't able to take advantage of the symbol information provided by the -g flag to a module while it is part of the running kernel.
Debugging support will usually mean extra code to print messages from within the driver. Using printk() for debugging is powerful, and the alternatives are running a debugger on the kernel, peeking in /dev/mem, and other extremely low-level techniques. There are a few tools available on the Internet to help use these other techniques, but you need to be conversant with gdb and be able to read real kernel code in order to benefit from them. The most interesting tool at time of writing is kdebug-1.1, which lets you use gdb on a running kernel, examining or even changing kernel data structures (including those in loaded kernel modules) while the kernel is running. Kdebug is available for ftp from sunsite.unc.edu and its mirrors under /pub/Linux/kernel.
Just to make things a little harder, the kernel equivalent of the standard printf() function is called printk(), because it does not work exactly the same as printf(). Before 1.3.37, conventional printk()'s generated lines in /var/adm/messages, while later kernels will dump them to the console. If you want quiet logging (only within the messages file, via syslogd) you must prepend the symbol KERN_DEBUG to the format string. KERN_DEBUG and similar symbols are simply strings, which get concatenated to your format string by the compiler. This means that you must not put a comma between KERN_DEBUG and the format string. These symbols can be found in
Remember, that syslog write to the messages file as soon as possible, in order to save all messages on disk in case of a system crash. This means that an over-printk-ed module will slow down perceptibly, and will fill your disk in a short time.
Almost any module misbehaviour will generate an [cw]Oops[ecw] message from the kernel. An Oops is what happens when the kernel gets an exception from kernel code. In other words, Oopses are the equivalent of segmentation faults in user space, though no core file is generated. The result is usually the sudden destruction of the responsible process, and a few lines of low-level information in the messages file. Most Oops messages are the result of dereferencing a NULL pointer.
This way to handle disasters is a friendly one, and you'll enjoy it whenever your code is faulty: most other Unices produce a kernel panic instead. This does not mean that Linux never panics. You must be prepared to generate panics whenever you write functions that operate outside of a process context, such as within interrupt handlers and timer callbacks.
The scarce, nearly unintelligible information included with the [cw]Oops[ecw] message represents the processor state when the code faulted, and can be used to understand where the error is. A tool called ksymoops is able to print more readable information out of the oops, provided you have a kernel map handy. The map is what is left in /usr/src/linux/System.map after a kernel compilation. Ksymoops was distributed within util-linux-2.4, but was removed in 2.5 because it has been included in the kernel distribution during the linux-1.3 development.
If you really understand the Oops message, you can use it as you want, like invoking gdb off-line to disassemble the whole responsible function. if you understand neither the Oops nor the ksymoops output, you'd better add some more debugging printk() code, recompile, and reproduce the bug.
The following code can ease management of debugging messages. It must reside in the module's public include file, and will work for both kernel code (the module) and user code (applications). Note however that this code is gcc-specific. Not too big a problem for a kernel module, which is gcc-dependent anyway. This code was suggested by Linus Torvalds, as an enhancement over my previous ansi-compliant approach.
#ifndef PDEBUG
# ifdef DEBUG_modulename
# ifdef __KERNEL__
# define PDEBUG(fmt, args...) printk (KERN_DEBUG fmt , ## args)
# else
# define PDEBUG(fmt, args...) fprintf (stderr, fmt , ## args)
# endif
# else
# define PDEBUG(fmt, args...)
# endif
#endif
#ifndef PDEBUGG
# define PDEBUGG(fmt, args...)
#endif
After this code, every PDEBUG("any %i or %s...\n", i, s); in the module will result in a printed message only if the code is compiled with -DDEBUG_modulename, while PDEBUGG() with the same arguments will expand to nothing. In user mode applications, it works the same, except that the message is printed to stderr instead of the messages file.
Using this code, you can enable or disable any message by removing or adding a single G character.
Writing Code
Let's look at what kind of code must go inside the module. The simple answer is ``whatever you need''. In practice, you must remember that the module is kernel code, and must fit a well-defined interface with the rest of Linux.
Usually, you start with header inclusion. And you begin to have contraints: you must always define the __KERNEL__ symbol before including any header unless it is defined in your makefile, and you must only include files pertaining to the
The code fragment in Listing 1 represents the first lines of source of a typical character driver. If you are going to write a module, it will be easier to cut and paste these lines from existing source rather than copying them by hand from this article.
#define __KERNEL__ /* kernel code */
#define MODULE /* always as a module */
#include
#include
/*
* Then include whatever header you need.
* Most likely you need the following:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "modulename.h" /* your own material */
After including the headers, there comes actual code. Before talking about specific driver functionality---most of the code---it is worth noting that there exist two module-specific functions, which must be defined in order for the module to be loaded:
int init_module (void);
void cleanup_module (void);
The first is in charge of module initialization (looking for the related hardware and registering the driver in the appropriate kernel tables), while the second is in charge of releasing any resources the module has allocated and deregistering the driver from the kernel tables.
If these functions are not there, insmod will fail to load your module.
The init_module() function returns 0 on success and a negative value on failure. The cleanup_module() function returns void, because it only gets invoked when the module is known to be unloadable. A kernel module keeps a usage count, and cleanup_module() is only called when that counter's value is 0 (more on this later on).
Skeletal code for these two functions will be presented in the next installment. Their design is fundamental for proper loading and unloading of the module, and a few details must dealt with. So here, I'll introduce you to each of the details, so that next month I can present the structure without explaining all the details.
contd....
Saturday, July 21, 2007
Hardware and Software IRQs
Hardware Interrupts (Hard IRQs)
Timer ticks, network cards and keyboard are examples of real hardware which produce interrupts at any time. The kernel runs interrupt handlers, which services the hardware. The kernel guarantees that this handler is never re-entered: if another interrupt arrives, it is queued (or dropped). Because it disables interrupts, this handler has to be fast: frequently it simply acknowledges the interrupt, marks a `software interrupt' for execution and exits.
You can tell you are in a hardware interrupt, because in_irq() returns true.
Software Interrupt Context: Bottom Halves, Tasklets, softirqs
Whenever a system call is about to return to userspace, or a hardware interrupt handler exits, any `software interrupts' which are marked pending (usually by hardware interrupts) are run (kernel/softirq.c).
Much of the real interrupt handling work is done here. Early in the transition to SMP, there were only `bottom halves' (BHs), which didn't take advantage of multiple CPUs. Shortly after we switched from wind-up computers made of match-sticks and snot, we abandoned this limitation.
include/linux/interrupt.h lists the different BH's. No matter how many CPUs you have, no two BHs will run at the same time. This made the transition to SMP simpler, but sucks hard for scalable performance. A very important bottom half is the timer BH (include/linux/timer.h): you can register to have it call functions for you in a given length of time.
2.3.43 introduced softirqs, and re-implemented the (now deprecated) BHs underneath them. Softirqs are fully-SMP versions of BHs: they can run on as many CPUs at once as required. This means they need to deal with any races in shared data using their own locks. A bitmask is used to keep track of which are enabled, so the 32 available softirqs should not be used up lightly. (Yes, people will notice).
tasklets (include/linux/interrupt.h) are like softirqs, except they are dynamically-registrable (meaning you can have as many as you want), and they also guarantee that any tasklet will only run on one CPU at any time, although different tasklets can run simultaneously (unlike different BHs).
You can tell you are in a softirq (or bottom half, or tasklet) using the in_softirq() macro (include/asm/softirq.h).
Timer ticks, network cards and keyboard are examples of real hardware which produce interrupts at any time. The kernel runs interrupt handlers, which services the hardware. The kernel guarantees that this handler is never re-entered: if another interrupt arrives, it is queued (or dropped). Because it disables interrupts, this handler has to be fast: frequently it simply acknowledges the interrupt, marks a `software interrupt' for execution and exits.
You can tell you are in a hardware interrupt, because in_irq() returns true.
Software Interrupt Context: Bottom Halves, Tasklets, softirqs
Whenever a system call is about to return to userspace, or a hardware interrupt handler exits, any `software interrupts' which are marked pending (usually by hardware interrupts) are run (kernel/softirq.c).
Much of the real interrupt handling work is done here. Early in the transition to SMP, there were only `bottom halves' (BHs), which didn't take advantage of multiple CPUs. Shortly after we switched from wind-up computers made of match-sticks and snot, we abandoned this limitation.
include/linux/interrupt.h lists the different BH's. No matter how many CPUs you have, no two BHs will run at the same time. This made the transition to SMP simpler, but sucks hard for scalable performance. A very important bottom half is the timer BH (include/linux/timer.h): you can register to have it call functions for you in a given length of time.
2.3.43 introduced softirqs, and re-implemented the (now deprecated) BHs underneath them. Softirqs are fully-SMP versions of BHs: they can run on as many CPUs at once as required. This means they need to deal with any races in shared data using their own locks. A bitmask is used to keep track of which are enabled, so the 32 available softirqs should not be used up lightly. (Yes, people will notice).
tasklets (include/linux/interrupt.h) are like softirqs, except they are dynamically-registrable (meaning you can have as many as you want), and they also guarantee that any tasklet will only run on one CPU at any time, although different tasklets can run simultaneously (unlike different BHs).
You can tell you are in a softirq (or bottom half, or tasklet) using the in_softirq() macro (include/asm/softirq.h).
Wednesday, July 11, 2007
GCC Optimization
Here's what the O options mean in GCC, why some optimizations aren't optimal after all and how you can make specialized optimization choices for your application.
In this article, we explore the optimization levels provided by the GCC compiler toolchain, including the specific optimizations provided in each. We also identify optimizations that require explicit specifications, including some with architecture dependencies. This discussion focuses on the 3.2.2 version of gcc (released February 2003), but it also applies to the current release, 3.3.2.
Levels of Optimization
Let's first look at how GCC categorizes optimizations and how a developer can control which are used and, sometimes more important, which are not. A large variety of optimizations are provided by GCC. Most are categorized into one of three levels, but some are provided at multiple levels. Some optimizations reduce the size of the resulting machine code, while others try to create code that is faster, potentially increasing its size. For completeness, the default optimization level is zero, which provides no optimization at all. This can be explicitly specified with option -O or -O0.
Level 1 (-O1)
The purpose of the first level of optimization is to produce an optimized image in a short amount of time. These optimizations typically don't require significant amounts of compile time to complete. Level 1 also has two sometimes conflicting goals. These goals are to reduce the size of the compiled code while increasing its performance. The set of optimizations provided in -O1 support these goals, in most cases. These are shown in Table 1 in the column labeled -O1. The first level of optimization is enabled as:
gcc -O1 -o test test.c
Table 1. GCC optimizations and the levels at which they are enabled.
Any optimization can be enabled outside of any level simply by specifying its name with the -f prefix, as:
gcc -fdefer-pop -o test test.c
We also could enable level 1 optimization and then disable any particular optimization using the -fno- prefix, like this:
gcc -O1 -fno-defer-pop -o test test.c
This command would enable the first level of optimization and then specifically disable the defer-pop optimization.
Level 2 (-O2)
The second level of optimization performs all other supported optimizations within the given architecture that do not involve a space-speed trade-off, a balance between the two objectives. For example, loop unrolling and function inlining, which have the effect of increasing code size while also potentially making the code faster, are not performed. The second level is enabled as:
gcc -O2 -o test test.c
Table 1 shows the level -O2 optimizations. The level -O2 optimizations include all of the -O1 optimizations, plus a large number of others.
Level 2.5 (-Os)
The special optimization level (-Os or size) enables all -O2 optimizations that do not increase code size; it puts the emphasis on size over speed. This includes all second-level optimizations, except for the alignment optimizations. The alignment optimizations skip space to align functions, loops, jumps and labels to an address that is a multiple of a power of two, in an architecture-dependent manner. Skipping to these boundaries can increase performance as well as the size of the resulting code and data spaces; therefore, these particular optimizations are disabled. The size optimization level is enabled as:
gcc -Os -o test test.c
In gcc 3.2.2, reorder-blocks is enabled at -Os, but in gcc 3.3.2 reorder-blocks is disabled.
Level 3 (-O3)
The third and highest level enables even more optimizations (Table 1) by putting emphasis on speed over size. This includes optimizations enabled at -O2 and rename-register. The optimization inline-functions also is enabled here, which can increase performance but also can drastically increase the size of the object, depending upon the functions that are inlined. The third level is enabled as:
gcc -O3 -o test test.c
Although -O3 can produce fast code, the increase in the size of the image can have adverse effects on its speed. For example, if the size of the image exceeds the size of the available instruction cache, severe performance penalties can be observed. Therefore, it may be better simply to compile at -O2 to increase the chances that the image fits in the instruction cache.
Architecture Specification
The optimizations discussed thus far can yield significant improvements in software performance and object size, but specifying the target architecture also can yield meaningful benefits. The -march option of gcc allows the CPU type to be specified (Table 2).
Table 2. x86 Architectures
Target CPU Types -march= Type
i386 DX/SX/CX/EX/SL i386
i486 DX/SX/DX2/SL/SX2/DX4 i486
487 i486
Pentium pentium
Pentium MMX pentium-mmx
Pentium Pro pentiumpro
Pentium II pentium2
Celeron pentium2
Pentium III pentium3
Pentium 4 pentium4
Via C3 c3
Winchip 2 winchip2
Winchip C6-2 winchip-c6
AMD K5 i586
AMD K6 k6
AMD K6 II k6-2
AMD K6 III k6-3
AMD Athlon athlon
AMD Athlon 4 athlon
AMD Athlon XP/MP athlon
AMD Duron athlon
AMD Tbird athlon-tbird
The default architecture is i386. GCC runs on all other i386/x86 architectures, but it can result in degraded performance on more recent processors. If you're concerned about portability of an image, you should compile it with the default. If you're more interested in performance, pick the architecture that matches your own.
Let's now look at an example of how performance can be improved by focusing on the actual target. Let's build a simple test application that performs a bubble sort over 10,000 elements. The elements in the array have been reversed to force the worst-case scenario. The build and timing process is shown in Listing 1.
Listing 1. Effects of Architecture Specification on a Simple Application
[mtj@camus]$ gcc -o sort sort.c -O2
[mtj@camus]$ time ./sort
real 0m1.036s
user 0m1.030s
sys 0m0.000s
[mtj@camus]$ gcc -o sort sort.c -O2 -march=pentium2
[mtj@camus]$ time ./sort
real 0m0.799s
user 0m0.790s
sys 0m0.010s
[mtj@camus]$
By specifying the architecture, in this case a 633MHz Celeron, the compiler can generate instructions for the particular target as well as enable other optimizations available only to that target. As shown in Listing 1, by specifying the architecture we see a time benefit of 237ms (23% improvement).
Although Listing 1 shows an improvement in speed, the drawback is that the image is slightly larger. Using the size command (Listing 2), we can identify the sizes of the various sections of the image.
Listing 2. Size Change of the Application from Listing 1
[mtj@camus]$ gcc -o sort sort.c -O2
[mtj@camus]$ size sort
text data bss dec hex filename
842 252 4 1098 44a sort
[mtj@camus]$ gcc -o sort sort.c -O2 -march=pentium2
[mtj@camus]$ size sort
text data bss dec hex filename
870 252 4 1126 466 sort
[mtj@camus]$
From Listing 2, we can see that the instruction size (text section) of the image increased by 28 bytes. But in this example, it's a small price to pay for the speed benefit.
Math Unit Optimizations
Some specialized optimizations require explicit definition by the developer. These optimizations are specific to the i386 and x86 architectures. A math unit, for one, can be specified, although in many cases it is automatically defined based on the specification of a target architecture. Possible units for the -mfpmath= option are shown in Table 3.
Table 3. Math Unit Optimizations
Option Description
387 Standard 387 Floating Point Coprocessor
sse Streaming SIMD Extensions (Pentium III, Athlon 4/XP/MP)
sse2 Streaming SIMD Extensions II (Pentium 4)
The default choice is -mfpmath=387. An experimental option is to specify both sse and 387 (-mfpmath=sse,387), which attempts to use both units.
Alignment Optimizations
In the second optimization level, we saw that a number of alignment optimizations were introduced that had the effect of increasing performance but also increasing the size of the resulting image. Three additional alignment optimizations specific to this architecture are available. The -malign-int option allows types to be aligned on 32-bit boundaries. If you're running on a 16-bit aligned target, -mno-align-int can be used. The -malign-double controls whether doubles, long doubles and long-longs are aligned on two-word boundaries (disabled with -mno-align-double). Aligning doubles provides better performance on Pentium architectures at the expense of additional memory.
Stacks also can be aligned by using the option -mpreferred-stack-boundary. The developer specifies a power of two for alignment. For example, if the developer specified -mpreferred-stack-boundary=4, the stack would be aligned on a 16-byte boundary (the default). On the Pentium and Pentium Pro targets, stack doubles should be aligned on 8-byte boundaries, but the Pentium III performs better with 16-byte alignment.
Speed Optimizations
For applications that utilize standard functions, such as memset, memcpy or strlen, the -minline-all-stringops option can increase performance by inlining string operations. This has the side effect of increasing the size of the image.
Loop unrolling occurs in the process of minimizing the number of loops by doing more work per iteration. This process increases the size of the image, but it also can increase its performance. This option can be enabled using the -funroll-loops option. For cases in which it's difficult to understand the number of loop iterations, a prerequisite for -funroll-loops, all loops can be unrolled using the -funroll-all-loops optimization.
A useful option that has the disadvantage of making an image difficult to debug is -momit-leaf-frame-pointer. This option keeps the frame pointer out of a register, which means less setup and restore of this value. In addition, it makes the register available for the code to use. The optimization -fomit-frame-pointer also can be useful.
When operating at level -O3 or having -finline-functions specified, the size limit of the functions that may be inlined can be specified through a special parameter interface. The following command illustrates capping the size of the functions to inline at 40 instructions:
gcc -o sort sort.c --param max-inline-insns=40
This can be useful to control the size by which an image is increased using -finline-functions.
Code Size Optimizations
The default stack alignment is 4, or 16 words. For space-constrained systems, the default can be minimized to 8 bytes by using the option -mpreferred-stack-boundary=2. When constants are defined, such as strings or floating-point values, these independent values commonly occupy unique locations in memory. Rather than allow each to be unique, identical constants can be merged together to reduce the space that's required to hold them. This particular optimization can be enabled with -fmerge-constants.
Graphics Hardware Optimizations
Depending on the specified target architecture, certain other extensions are enabled. These also can be enabled or disabled explicitly. Options such as -mmmx and -m3dnow are enabled automatically for architectures that support them.
Other Possibilities
We've discussed many optimizations and compiler options that can increase performance or decrease size. Let's now look at some fringe optimizations that may provide a benefit to your application.
The -ffast-math optimization provides transformations likely to result in correct code but it may not adhere strictly to the IEEE standard. Use it, but test carefully.
When global common sub-expression elimination is enabled (-fgcse, level -O2 and above), two other options may be used to minimize load and store motions. Optimizations -fgcse-lm and -fgcse-sm can migrate loads and stores outside of loops to reduce the number of instructions executed within the loop, therefore increasing the performance of the loop. Both -fgcse-lm (load-motion) and -fgcse-sm (store-motion) should be specified together.
The -fforce-addr optimization forces the compiler to move addresses into registers before performing any arithmetic on them. This is similar to the -fforce-mem option, which is enabled automatically in optimization levels -O2, -Os and -O3.
A final fringe optimization is -fsched-spec-load, which works with the -fschedule-insns optimization, enabled at -O2 and above. This optimization permits the speculative motion of some load instructions to minimize execution stalls due to data dependencies.
In this article, we explore the optimization levels provided by the GCC compiler toolchain, including the specific optimizations provided in each. We also identify optimizations that require explicit specifications, including some with architecture dependencies. This discussion focuses on the 3.2.2 version of gcc (released February 2003), but it also applies to the current release, 3.3.2.
Levels of Optimization
Let's first look at how GCC categorizes optimizations and how a developer can control which are used and, sometimes more important, which are not. A large variety of optimizations are provided by GCC. Most are categorized into one of three levels, but some are provided at multiple levels. Some optimizations reduce the size of the resulting machine code, while others try to create code that is faster, potentially increasing its size. For completeness, the default optimization level is zero, which provides no optimization at all. This can be explicitly specified with option -O or -O0.
Level 1 (-O1)
The purpose of the first level of optimization is to produce an optimized image in a short amount of time. These optimizations typically don't require significant amounts of compile time to complete. Level 1 also has two sometimes conflicting goals. These goals are to reduce the size of the compiled code while increasing its performance. The set of optimizations provided in -O1 support these goals, in most cases. These are shown in Table 1 in the column labeled -O1. The first level of optimization is enabled as:
gcc -O1 -o test test.c
Table 1. GCC optimizations and the levels at which they are enabled.
Any optimization can be enabled outside of any level simply by specifying its name with the -f prefix, as:
gcc -fdefer-pop -o test test.c
We also could enable level 1 optimization and then disable any particular optimization using the -fno- prefix, like this:
gcc -O1 -fno-defer-pop -o test test.c
This command would enable the first level of optimization and then specifically disable the defer-pop optimization.
Level 2 (-O2)
The second level of optimization performs all other supported optimizations within the given architecture that do not involve a space-speed trade-off, a balance between the two objectives. For example, loop unrolling and function inlining, which have the effect of increasing code size while also potentially making the code faster, are not performed. The second level is enabled as:
gcc -O2 -o test test.c
Table 1 shows the level -O2 optimizations. The level -O2 optimizations include all of the -O1 optimizations, plus a large number of others.
Level 2.5 (-Os)
The special optimization level (-Os or size) enables all -O2 optimizations that do not increase code size; it puts the emphasis on size over speed. This includes all second-level optimizations, except for the alignment optimizations. The alignment optimizations skip space to align functions, loops, jumps and labels to an address that is a multiple of a power of two, in an architecture-dependent manner. Skipping to these boundaries can increase performance as well as the size of the resulting code and data spaces; therefore, these particular optimizations are disabled. The size optimization level is enabled as:
gcc -Os -o test test.c
In gcc 3.2.2, reorder-blocks is enabled at -Os, but in gcc 3.3.2 reorder-blocks is disabled.
Level 3 (-O3)
The third and highest level enables even more optimizations (Table 1) by putting emphasis on speed over size. This includes optimizations enabled at -O2 and rename-register. The optimization inline-functions also is enabled here, which can increase performance but also can drastically increase the size of the object, depending upon the functions that are inlined. The third level is enabled as:
gcc -O3 -o test test.c
Although -O3 can produce fast code, the increase in the size of the image can have adverse effects on its speed. For example, if the size of the image exceeds the size of the available instruction cache, severe performance penalties can be observed. Therefore, it may be better simply to compile at -O2 to increase the chances that the image fits in the instruction cache.
Architecture Specification
The optimizations discussed thus far can yield significant improvements in software performance and object size, but specifying the target architecture also can yield meaningful benefits. The -march option of gcc allows the CPU type to be specified (Table 2).
Table 2. x86 Architectures
Target CPU Types -march= Type
i386 DX/SX/CX/EX/SL i386
i486 DX/SX/DX2/SL/SX2/DX4 i486
487 i486
Pentium pentium
Pentium MMX pentium-mmx
Pentium Pro pentiumpro
Pentium II pentium2
Celeron pentium2
Pentium III pentium3
Pentium 4 pentium4
Via C3 c3
Winchip 2 winchip2
Winchip C6-2 winchip-c6
AMD K5 i586
AMD K6 k6
AMD K6 II k6-2
AMD K6 III k6-3
AMD Athlon athlon
AMD Athlon 4 athlon
AMD Athlon XP/MP athlon
AMD Duron athlon
AMD Tbird athlon-tbird
The default architecture is i386. GCC runs on all other i386/x86 architectures, but it can result in degraded performance on more recent processors. If you're concerned about portability of an image, you should compile it with the default. If you're more interested in performance, pick the architecture that matches your own.
Let's now look at an example of how performance can be improved by focusing on the actual target. Let's build a simple test application that performs a bubble sort over 10,000 elements. The elements in the array have been reversed to force the worst-case scenario. The build and timing process is shown in Listing 1.
Listing 1. Effects of Architecture Specification on a Simple Application
[mtj@camus]$ gcc -o sort sort.c -O2
[mtj@camus]$ time ./sort
real 0m1.036s
user 0m1.030s
sys 0m0.000s
[mtj@camus]$ gcc -o sort sort.c -O2 -march=pentium2
[mtj@camus]$ time ./sort
real 0m0.799s
user 0m0.790s
sys 0m0.010s
[mtj@camus]$
By specifying the architecture, in this case a 633MHz Celeron, the compiler can generate instructions for the particular target as well as enable other optimizations available only to that target. As shown in Listing 1, by specifying the architecture we see a time benefit of 237ms (23% improvement).
Although Listing 1 shows an improvement in speed, the drawback is that the image is slightly larger. Using the size command (Listing 2), we can identify the sizes of the various sections of the image.
Listing 2. Size Change of the Application from Listing 1
[mtj@camus]$ gcc -o sort sort.c -O2
[mtj@camus]$ size sort
text data bss dec hex filename
842 252 4 1098 44a sort
[mtj@camus]$ gcc -o sort sort.c -O2 -march=pentium2
[mtj@camus]$ size sort
text data bss dec hex filename
870 252 4 1126 466 sort
[mtj@camus]$
From Listing 2, we can see that the instruction size (text section) of the image increased by 28 bytes. But in this example, it's a small price to pay for the speed benefit.
Math Unit Optimizations
Some specialized optimizations require explicit definition by the developer. These optimizations are specific to the i386 and x86 architectures. A math unit, for one, can be specified, although in many cases it is automatically defined based on the specification of a target architecture. Possible units for the -mfpmath= option are shown in Table 3.
Table 3. Math Unit Optimizations
Option Description
387 Standard 387 Floating Point Coprocessor
sse Streaming SIMD Extensions (Pentium III, Athlon 4/XP/MP)
sse2 Streaming SIMD Extensions II (Pentium 4)
The default choice is -mfpmath=387. An experimental option is to specify both sse and 387 (-mfpmath=sse,387), which attempts to use both units.
Alignment Optimizations
In the second optimization level, we saw that a number of alignment optimizations were introduced that had the effect of increasing performance but also increasing the size of the resulting image. Three additional alignment optimizations specific to this architecture are available. The -malign-int option allows types to be aligned on 32-bit boundaries. If you're running on a 16-bit aligned target, -mno-align-int can be used. The -malign-double controls whether doubles, long doubles and long-longs are aligned on two-word boundaries (disabled with -mno-align-double). Aligning doubles provides better performance on Pentium architectures at the expense of additional memory.
Stacks also can be aligned by using the option -mpreferred-stack-boundary. The developer specifies a power of two for alignment. For example, if the developer specified -mpreferred-stack-boundary=4, the stack would be aligned on a 16-byte boundary (the default). On the Pentium and Pentium Pro targets, stack doubles should be aligned on 8-byte boundaries, but the Pentium III performs better with 16-byte alignment.
Speed Optimizations
For applications that utilize standard functions, such as memset, memcpy or strlen, the -minline-all-stringops option can increase performance by inlining string operations. This has the side effect of increasing the size of the image.
Loop unrolling occurs in the process of minimizing the number of loops by doing more work per iteration. This process increases the size of the image, but it also can increase its performance. This option can be enabled using the -funroll-loops option. For cases in which it's difficult to understand the number of loop iterations, a prerequisite for -funroll-loops, all loops can be unrolled using the -funroll-all-loops optimization.
A useful option that has the disadvantage of making an image difficult to debug is -momit-leaf-frame-pointer. This option keeps the frame pointer out of a register, which means less setup and restore of this value. In addition, it makes the register available for the code to use. The optimization -fomit-frame-pointer also can be useful.
When operating at level -O3 or having -finline-functions specified, the size limit of the functions that may be inlined can be specified through a special parameter interface. The following command illustrates capping the size of the functions to inline at 40 instructions:
gcc -o sort sort.c --param max-inline-insns=40
This can be useful to control the size by which an image is increased using -finline-functions.
Code Size Optimizations
The default stack alignment is 4, or 16 words. For space-constrained systems, the default can be minimized to 8 bytes by using the option -mpreferred-stack-boundary=2. When constants are defined, such as strings or floating-point values, these independent values commonly occupy unique locations in memory. Rather than allow each to be unique, identical constants can be merged together to reduce the space that's required to hold them. This particular optimization can be enabled with -fmerge-constants.
Graphics Hardware Optimizations
Depending on the specified target architecture, certain other extensions are enabled. These also can be enabled or disabled explicitly. Options such as -mmmx and -m3dnow are enabled automatically for architectures that support them.
Other Possibilities
We've discussed many optimizations and compiler options that can increase performance or decrease size. Let's now look at some fringe optimizations that may provide a benefit to your application.
The -ffast-math optimization provides transformations likely to result in correct code but it may not adhere strictly to the IEEE standard. Use it, but test carefully.
When global common sub-expression elimination is enabled (-fgcse, level -O2 and above), two other options may be used to minimize load and store motions. Optimizations -fgcse-lm and -fgcse-sm can migrate loads and stores outside of loops to reduce the number of instructions executed within the loop, therefore increasing the performance of the loop. Both -fgcse-lm (load-motion) and -fgcse-sm (store-motion) should be specified together.
The -fforce-addr optimization forces the compiler to move addresses into registers before performing any arithmetic on them. This is similar to the -fforce-mem option, which is enabled automatically in optimization levels -O2, -Os and -O3.
A final fringe optimization is -fsched-spec-load, which works with the -fschedule-insns optimization, enabled at -O2 and above. This optimization permits the speculative motion of some load instructions to minimize execution stalls due to data dependencies.
Tuesday, June 12, 2007
PMTU DIscovery
Summary
Internet computers, mostly servers, sometimes send packets too large for part of a given path. Not handling this correctly can make the server unusable for some people.
Correct handling of oversize packets is by one of two means, as chosen by the sending computer (the server):
* Permitting Packet fragmentation - used mostly by older systems
* Path MTU discovery - asking for ICMP notification when fragmentation would be needed
By default, modern servers disable fragmentation and try to use path MTU discovery, but sometimes the system administrators block the ICMP notifications. Overall, these servers ask for ICMP notification of packets that are too large and then refuse to accept the notifications they ask for.
Unable to learn that they are sending packets are too big for some paths, the servers are unable to send data to some users. To overcome this they need to accept appropriate ICMP types or allow fragmentation.
Path MTU Discovery
Every network link has a maximum packet size called the link's MTU (Maximum Transmission Unit). The full path from one computer to another may travel across many links with different MTUs. The smallest MTU for all the links in a path is the path MTU.
If a packet starts out on a network segment with a large MTU, it may arrive at a link with a smaller MTU and be too big to fit. Most servers are on segments with large MTUs, but it is increasingly common for internet users to be connected via links with reduced MTUs, so it is becoming common for some packets to be too big.
How the problem of oversize packets has been handled has evolved considerably over time. The original approach was to send only small packets corresponding to the TCP/IP default MTU (576 bytes). (To this day, a sending system needs permission from the receiving system to send larger packets, but that permisssion is given as a matter of routine.)
For some packets, especially those sent by older equipment, an oversize packet can be sent by breaking it into fragments and sending the fragments as smaller packets. The fragments can be reassembled downstream to reconstruct the original large packet, but this packet fragmentation has several problems involving both efficiency and security.
Newer servers try to optimize their transmissions by discovering the path MTU and sending packets of the maximum size when there's enough data to fill them. The procedure for doing this was standardized and published as RFC 1191 in 1990, but it did not become widely deployed until years later. By mid 2002, 80% to 90% of computers on the internet used path MTU discovery.
The basic procedure is simple - send the largest packet you can, and if it won't fit through some link get back a notification saying what size will fit. The notifications arrive as ICMP (Internet Control Message Protocol) packets known as "fragmentation needed" ICMPs (ICMP type 3, subtype 4). The notifications are requested by setting the "do not fragment" (DF) bit in packets that are sent out.
Some network and system administrators view all ICMPs as risky and block them all, disabling path MTU discovery, usually without even realizing it. Of the several dozen ICMP types and subtypes, some do pose some risk, but the risk is mostly mild and is of the "denial of service" nature. That is, an attacker can use them to interfere with service on and from the network.
By blocking all ICMPs the administrator himself interferes with service on and from his own network. Unless he also turns off path MTU discovery on his network's servers, he makes his servers unusable by users with reduced-MTU links in their paths. Because service is affected only in relatively unusual cases, it can be difficult to convince the administrator that a problem exists. The prevalence of such "unusual" cases is growing rapidly though.
Administrators who want to block all ICMPs should disable path MTU discovery on their computers, especially on their servers. It makes no sense to ask for ICMP notifications and then refuse to accept them. In addition, doing so opens the server to a special type of distributed denial of service attack based on resource exhaustion from a large number of fully-open connections.
Cisco's website has summary instructions for disabling path MTU discovery for these systems:
* Windows 95/98/ME
* Windows NT 3.1/3.51 and 4.0
* Windows 2000/XP
* Solaris
* HP-UX
Elsewhere on Cisco's site they recommend using the Dr. TCP utility for Windows.
Disabling path MTU on Windows systems requires modifying the Windows Registry. Microsoft's support website has information and cautions about the Registry.
Path MTU discovery can be turned off
* Under Linux, with the command
echo 1 >/proc/sys/net/ipv4/ip_no_pmtu_disc
* Under FreeBSD, by using sysctl(8) to zero
tcp.path_mtu_discovery
* On Cisco routers,with the configuration command
no ip tcp mtu-path discovery
Example Path MTU Discovery Failure Scenario
Joe User has a DSL line. Like many DSL lines, Joe's line actually comes from a large DSL wholesaler and uses PPPoE (PPP over Ethernet) to create a logical channel between Joe and his favorite ISP. The DSL line physically connects to a small PPPoE router with a built-in hub, which Joe uses as the basis for his home network.
The MTU on Joe's network is Ethernet's usual 1500 bytes. The MTU on his DSL line is also 1500 bytes, but PPPoE uses 8 of these bytes for an 8-byte PPPoE header, so the MTU of his PPPoE channel to his ISP is only 1492 bytes.
A computer on Joe's Ethernet doesn't know about the PPPoE channel. The largest packet it can receive is a 1500-byte Ethernet packet, so when Joe uses his computer to connect to a remote server, his computer tells the server it's ok to send packets up to 1500 bytes.[*]
Establishing connections uses only very small packets, so Joe can connect to the server without any MTU issues, but as soon as Joe asks for enough data to fill a 1500-byte packet, the server sends a 1500-byte packet. When that packet gets to Joe's ISP, it doesn't fit down the PPPoE channel. The packet has the DF bit set, telling Joe's ISP to drop the packet and send the server an ICMP saying what packet size will fit. The ISP sends an ICMP saying the largest size is 1492 bytes.
If the server gets that ICMP, it re-sends the first 1492 bytes as a new packet. This new packets fits down the PPPoE channel, so Joe's computer gets it and sends back an acknowledgement. The server continues sending 1492-byte packets until Joe has what he asked for. In most cases the server will remember the reduced path MTU, typically for ten minutes, and use it for future connections from Joe's computer.
However, if the server does not get that ICMP, things go downhill fast. The server is expecting an acknowledgement from Joe's computer, but Joe's computer didn't get the packet, so the acknowledgment never comes. After awhile, the server gives up waiting and sends the same 1500-byte packet again. Joe's ISP sends back another ICMP. The server doesn't get it again and tries sending the 1500-byte packet a third time, then a fourth, a fifth, and so on.
Meanwhile Joe's computer can't tell this is happening and is waiting for a response from the server. Eventually, it gives up and sends the server a connection reset. It reports a network failure to Joe, who is left wondering what happened. He may soon discover he can access nearly all other sites, just not the one he wanted.
If the server he's trying to access is a web server, he may get part of the website, such as getting the ads but not the main page content. This happens because the pages normally displayed for many websites are assembled from data obtained from multiple servers on a variety of networks. The networks dispensing the ads all support path MTU discovery.
If Joe complains to the server operator, they may tell him the problem has to be his ISP because other users can view their server. However, Joe's ISP is not doing anything wrong, but the server operator is. PPPoE and other connections with reduced MTUs are perfectly legitimate and increasingly common. Having a server ask for ICMP noptification that it refuses to accept is what's broken behavior. Some later day, when the server site has gotten enough complaints from people like Joe to believe something is wrong, it may either stop asking for the ICMPs or start accepting the useful ones. Then Joe will be able to access it.
[*] What Joe's computer actually tells the remote server is that the largest payload it can send in any packet is 1460 bytes, which is the 1500-byte maximum Ethernet packet size minus 40 bytes of overhead. This maximum payload is called the MSS (Maximum Segment Size).
Internet computers, mostly servers, sometimes send packets too large for part of a given path. Not handling this correctly can make the server unusable for some people.
Correct handling of oversize packets is by one of two means, as chosen by the sending computer (the server):
* Permitting Packet fragmentation - used mostly by older systems
* Path MTU discovery - asking for ICMP notification when fragmentation would be needed
By default, modern servers disable fragmentation and try to use path MTU discovery, but sometimes the system administrators block the ICMP notifications. Overall, these servers ask for ICMP notification of packets that are too large and then refuse to accept the notifications they ask for.
Unable to learn that they are sending packets are too big for some paths, the servers are unable to send data to some users. To overcome this they need to accept appropriate ICMP types or allow fragmentation.
Path MTU Discovery
Every network link has a maximum packet size called the link's MTU (Maximum Transmission Unit). The full path from one computer to another may travel across many links with different MTUs. The smallest MTU for all the links in a path is the path MTU.
If a packet starts out on a network segment with a large MTU, it may arrive at a link with a smaller MTU and be too big to fit. Most servers are on segments with large MTUs, but it is increasingly common for internet users to be connected via links with reduced MTUs, so it is becoming common for some packets to be too big.
How the problem of oversize packets has been handled has evolved considerably over time. The original approach was to send only small packets corresponding to the TCP/IP default MTU (576 bytes). (To this day, a sending system needs permission from the receiving system to send larger packets, but that permisssion is given as a matter of routine.)
For some packets, especially those sent by older equipment, an oversize packet can be sent by breaking it into fragments and sending the fragments as smaller packets. The fragments can be reassembled downstream to reconstruct the original large packet, but this packet fragmentation has several problems involving both efficiency and security.
Newer servers try to optimize their transmissions by discovering the path MTU and sending packets of the maximum size when there's enough data to fill them. The procedure for doing this was standardized and published as RFC 1191 in 1990, but it did not become widely deployed until years later. By mid 2002, 80% to 90% of computers on the internet used path MTU discovery.
The basic procedure is simple - send the largest packet you can, and if it won't fit through some link get back a notification saying what size will fit. The notifications arrive as ICMP (Internet Control Message Protocol) packets known as "fragmentation needed" ICMPs (ICMP type 3, subtype 4). The notifications are requested by setting the "do not fragment" (DF) bit in packets that are sent out.
Some network and system administrators view all ICMPs as risky and block them all, disabling path MTU discovery, usually without even realizing it. Of the several dozen ICMP types and subtypes, some do pose some risk, but the risk is mostly mild and is of the "denial of service" nature. That is, an attacker can use them to interfere with service on and from the network.
By blocking all ICMPs the administrator himself interferes with service on and from his own network. Unless he also turns off path MTU discovery on his network's servers, he makes his servers unusable by users with reduced-MTU links in their paths. Because service is affected only in relatively unusual cases, it can be difficult to convince the administrator that a problem exists. The prevalence of such "unusual" cases is growing rapidly though.
Administrators who want to block all ICMPs should disable path MTU discovery on their computers, especially on their servers. It makes no sense to ask for ICMP notifications and then refuse to accept them. In addition, doing so opens the server to a special type of distributed denial of service attack based on resource exhaustion from a large number of fully-open connections.
Cisco's website has summary instructions for disabling path MTU discovery for these systems:
* Windows 95/98/ME
* Windows NT 3.1/3.51 and 4.0
* Windows 2000/XP
* Solaris
* HP-UX
Elsewhere on Cisco's site they recommend using the Dr. TCP utility for Windows.
Disabling path MTU on Windows systems requires modifying the Windows Registry. Microsoft's support website has information and cautions about the Registry.
Path MTU discovery can be turned off
* Under Linux, with the command
echo 1 >/proc/sys/net/ipv4/ip_no_pmtu_disc
* Under FreeBSD, by using sysctl(8) to zero
tcp.path_mtu_discovery
* On Cisco routers,with the configuration command
no ip tcp mtu-path discovery
Example Path MTU Discovery Failure Scenario
Joe User has a DSL line. Like many DSL lines, Joe's line actually comes from a large DSL wholesaler and uses PPPoE (PPP over Ethernet) to create a logical channel between Joe and his favorite ISP. The DSL line physically connects to a small PPPoE router with a built-in hub, which Joe uses as the basis for his home network.
The MTU on Joe's network is Ethernet's usual 1500 bytes. The MTU on his DSL line is also 1500 bytes, but PPPoE uses 8 of these bytes for an 8-byte PPPoE header, so the MTU of his PPPoE channel to his ISP is only 1492 bytes.
A computer on Joe's Ethernet doesn't know about the PPPoE channel. The largest packet it can receive is a 1500-byte Ethernet packet, so when Joe uses his computer to connect to a remote server, his computer tells the server it's ok to send packets up to 1500 bytes.[*]
Establishing connections uses only very small packets, so Joe can connect to the server without any MTU issues, but as soon as Joe asks for enough data to fill a 1500-byte packet, the server sends a 1500-byte packet. When that packet gets to Joe's ISP, it doesn't fit down the PPPoE channel. The packet has the DF bit set, telling Joe's ISP to drop the packet and send the server an ICMP saying what packet size will fit. The ISP sends an ICMP saying the largest size is 1492 bytes.
If the server gets that ICMP, it re-sends the first 1492 bytes as a new packet. This new packets fits down the PPPoE channel, so Joe's computer gets it and sends back an acknowledgement. The server continues sending 1492-byte packets until Joe has what he asked for. In most cases the server will remember the reduced path MTU, typically for ten minutes, and use it for future connections from Joe's computer.
However, if the server does not get that ICMP, things go downhill fast. The server is expecting an acknowledgement from Joe's computer, but Joe's computer didn't get the packet, so the acknowledgment never comes. After awhile, the server gives up waiting and sends the same 1500-byte packet again. Joe's ISP sends back another ICMP. The server doesn't get it again and tries sending the 1500-byte packet a third time, then a fourth, a fifth, and so on.
Meanwhile Joe's computer can't tell this is happening and is waiting for a response from the server. Eventually, it gives up and sends the server a connection reset. It reports a network failure to Joe, who is left wondering what happened. He may soon discover he can access nearly all other sites, just not the one he wanted.
If the server he's trying to access is a web server, he may get part of the website, such as getting the ads but not the main page content. This happens because the pages normally displayed for many websites are assembled from data obtained from multiple servers on a variety of networks. The networks dispensing the ads all support path MTU discovery.
If Joe complains to the server operator, they may tell him the problem has to be his ISP because other users can view their server. However, Joe's ISP is not doing anything wrong, but the server operator is. PPPoE and other connections with reduced MTUs are perfectly legitimate and increasingly common. Having a server ask for ICMP noptification that it refuses to accept is what's broken behavior. Some later day, when the server site has gotten enough complaints from people like Joe to believe something is wrong, it may either stop asking for the ICMPs or start accepting the useful ones. Then Joe will be able to access it.
[*] What Joe's computer actually tells the remote server is that the largest payload it can send in any packet is 1460 bytes, which is the 1500-byte maximum Ethernet packet size minus 40 bytes of overhead. This maximum payload is called the MSS (Maximum Segment Size).
Wednesday, June 6, 2007
Wait Queues
When a process requests the kernel to do something which is currently impossible but that may become possible later, the process is put to sleep and is woken up when the request is more likely to be satisfied. One of the kernel mechanisms used for this is called a 'wait queue'.
Linux implementation allows wake-on semantics using TASK_EXCLUSIVE flag. With waitqueues, you can either use a well-known queue and then simply sleep_on/sleep_on_timeout/interruptible_sleep_on/interruptible_sleep_on_timeout, or you can define your own waitqueue and use add/remove_wait_queue to add and remove yourself from it and wake_up/wake_up_interruptible to wake up when needed.
An example of the first usage of waitqueues is interaction between the page allocator (in mm/page_alloc.c:__alloc_pages()) and the kswapd kernel daemon (in mm/vmscan.c:kswap()), by means of wait queue kswapd_wait, declared in mm/vmscan.c; the kswapd daemon sleeps on this queue, and it is woken up whenever the page allocator needs to free up some pages.
An example of autonomous waitqueue usage is interaction between user process requesting data via read(2) system call and kernel running in the interrupt context to supply the data. An interrupt handler might look like (simplified drivers/char/rtc_interrupt()):
static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);
void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
spin_lock(&rtc_lock);
rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
spin_unlock(&rtc_lock);
wake_up_interruptible(&rtc_wait);
}
So, the interrupt handler obtains the data by reading from some device-specific I/O port (CMOS_READ() macro turns into a couple outb/inb) and then wakes up whoever is sleeping on the rtc_wait wait queue.
Now, the read(2) system call could be implemented as:
ssize_t rtc_read(struct file file, char *buf, size_t count, loff_t *ppos)
{
DECLARE_WAITQUEUE(wait, current);
unsigned long data;
ssize_t retval;
add_wait_queue(&rtc_wait, &wait);
current->state = TASK_INTERRUPTIBLE;
do {
spin_lock_irq(&rtc_lock);
data = rtc_irq_data;
rtc_irq_data = 0;
spin_unlock_irq(&rtc_lock);
if (data != 0)
break;
if (file->f_flags & O_NONBLOCK) {
retval = -EAGAIN;
goto out;
}
if (signal_pending(current)) {
retval = -ERESTARTSYS;
goto out;
}
schedule();
} while(1);
retval = put_user(data, (unsigned long *)buf);
if (!retval)
retval = sizeof(unsigned long);
out:
current->state = TASK_RUNNING;
remove_wait_queue(&rtc_wait, &wait);
return retval;
}
What happens in rtc_read() is this:
1. We declare a wait queue element pointing to current process context.
2. We add this element to the rtc_wait waitqueue.
3. We mark current context as TASK_INTERRUPTIBLE which means it will not be rescheduled after the next time it sleeps.
4. We check if there is no data available; if there is we break out, copy data to user buffer, mark ourselves as TASK_RUNNING, remove ourselves from the wait queue and return
5. If there is no data yet, we check whether the user specified non-blocking I/O and if so we fail with EAGAIN (which is the same as EWOULDBLOCK)
6. We also check if a signal is pending and if so inform the "higher layers" to restart the system call if necessary. By "if necessary" I meant the details of signal disposition as specified in sigaction(2) system call.
7. Then we "switch out", i.e. fall asleep, until woken up by the interrupt handler. If we didn't mark ourselves as TASK_INTERRUPTIBLE then the scheduler could schedule us sooner than when the data is available, thus causing unneeded processing.
It is also worth pointing out that, using wait queues, it is rather easy to implement the poll(2) system call:
static unsigned int rtc_poll(struct file *file, poll_table *wait)
{
unsigned long l;
poll_wait(file, &rtc_wait, wait);
spin_lock_irq(&rtc_lock);
l = rtc_irq_data;
spin_unlock_irq(&rtc_lock);
if (l != 0)
return POLLIN | POLLRDNORM;
return 0;
}
All the work is done by the device-independent function poll_wait() which does the necessary waitqueue manipulations; all we need to do is point it to the waitqueue which is woken up by our device-specific interrupt handler.
Linux implementation allows wake-on semantics using TASK_EXCLUSIVE flag. With waitqueues, you can either use a well-known queue and then simply sleep_on/sleep_on_timeout/interruptible_sleep_on/interruptible_sleep_on_timeout, or you can define your own waitqueue and use add/remove_wait_queue to add and remove yourself from it and wake_up/wake_up_interruptible to wake up when needed.
An example of the first usage of waitqueues is interaction between the page allocator (in mm/page_alloc.c:__alloc_pages()) and the kswapd kernel daemon (in mm/vmscan.c:kswap()), by means of wait queue kswapd_wait, declared in mm/vmscan.c; the kswapd daemon sleeps on this queue, and it is woken up whenever the page allocator needs to free up some pages.
An example of autonomous waitqueue usage is interaction between user process requesting data via read(2) system call and kernel running in the interrupt context to supply the data. An interrupt handler might look like (simplified drivers/char/rtc_interrupt()):
static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);
void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
spin_lock(&rtc_lock);
rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
spin_unlock(&rtc_lock);
wake_up_interruptible(&rtc_wait);
}
So, the interrupt handler obtains the data by reading from some device-specific I/O port (CMOS_READ() macro turns into a couple outb/inb) and then wakes up whoever is sleeping on the rtc_wait wait queue.
Now, the read(2) system call could be implemented as:
ssize_t rtc_read(struct file file, char *buf, size_t count, loff_t *ppos)
{
DECLARE_WAITQUEUE(wait, current);
unsigned long data;
ssize_t retval;
add_wait_queue(&rtc_wait, &wait);
current->state = TASK_INTERRUPTIBLE;
do {
spin_lock_irq(&rtc_lock);
data = rtc_irq_data;
rtc_irq_data = 0;
spin_unlock_irq(&rtc_lock);
if (data != 0)
break;
if (file->f_flags & O_NONBLOCK) {
retval = -EAGAIN;
goto out;
}
if (signal_pending(current)) {
retval = -ERESTARTSYS;
goto out;
}
schedule();
} while(1);
retval = put_user(data, (unsigned long *)buf);
if (!retval)
retval = sizeof(unsigned long);
out:
current->state = TASK_RUNNING;
remove_wait_queue(&rtc_wait, &wait);
return retval;
}
What happens in rtc_read() is this:
1. We declare a wait queue element pointing to current process context.
2. We add this element to the rtc_wait waitqueue.
3. We mark current context as TASK_INTERRUPTIBLE which means it will not be rescheduled after the next time it sleeps.
4. We check if there is no data available; if there is we break out, copy data to user buffer, mark ourselves as TASK_RUNNING, remove ourselves from the wait queue and return
5. If there is no data yet, we check whether the user specified non-blocking I/O and if so we fail with EAGAIN (which is the same as EWOULDBLOCK)
6. We also check if a signal is pending and if so inform the "higher layers" to restart the system call if necessary. By "if necessary" I meant the details of signal disposition as specified in sigaction(2) system call.
7. Then we "switch out", i.e. fall asleep, until woken up by the interrupt handler. If we didn't mark ourselves as TASK_INTERRUPTIBLE then the scheduler could schedule us sooner than when the data is available, thus causing unneeded processing.
It is also worth pointing out that, using wait queues, it is rather easy to implement the poll(2) system call:
static unsigned int rtc_poll(struct file *file, poll_table *wait)
{
unsigned long l;
poll_wait(file, &rtc_wait, wait);
spin_lock_irq(&rtc_lock);
l = rtc_irq_data;
spin_unlock_irq(&rtc_lock);
if (l != 0)
return POLLIN | POLLRDNORM;
return 0;
}
All the work is done by the device-independent function poll_wait() which does the necessary waitqueue manipulations; all we need to do is point it to the waitqueue which is woken up by our device-specific interrupt handler.
Tuesday, June 5, 2007
Semaphores and read/write Semaphores
Sometimes, while accessing a shared data structure, one must perform operations that can block, for example copy data to userspace. The locking primitive available for such scenarios under Linux is called a semaphore. There are two types of semaphores: basic and read-write semaphores. Depending on the initial value of the semaphore, they can be used for either mutual exclusion (initial value of 1) or to provide more sophisticated type of access.
Read-write semaphores differ from basic semaphores in the same way as read-write spinlocks differ from basic spinlocks: one can have multiple readers at a time but only one writer and there can be no readers while there are writers - i.e. the writer blocks all readers and new readers block while a writer is waiting.
Also, basic semaphores can be interruptible - just use the operations down/up_interruptible() instead of the plain down()/up() and check the value returned from down_interruptible(): it will be non zero if the operation was interrupted.
Using semaphores for mutual exclusion is ideal in situations where a critical code section may call by reference unknown functions registered by other subsystems/modules, i.e. the caller cannot know apriori whether the function blocks or not.
A simple example of semaphore usage is in kernel/sys.c, implementation of gethostname(2)/sethostname(2) system calls.
asmlinkage long sys_sethostname(char *name, int len)
{
int errno;
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
if (len < 0 || len > __NEW_UTS_LEN)
return -EINVAL;
down_write(&uts_sem);
errno = -EFAULT;
if (!copy_from_user(system_utsname.nodename, name, len)) {
system_utsname.nodename[len] = 0;
errno = 0;
}
up_write(&uts_sem);
return errno;
}
asmlinkage long sys_gethostname(char *name, int len)
{
int i, errno;
if (len < 0)
return -EINVAL;
down_read(&uts_sem);
i = 1 + strlen(system_utsname.nodename);
if (i > len)
i = len;
errno = 0;
if (copy_to_user(name, system_utsname.nodename, i))
errno = -EFAULT;
up_read(&uts_sem);
return errno;
}
The points to note about this example are:
1. The functions may block while copying data from/to userspace in copy_from_user()/copy_to_user(). Therefore they could not use any form of spinlock here.
2. The semaphore type chosen is read-write as opposed to basic because there may be lots of concurrent gethostname(2) requests which need not be mutually exclusive.
Although Linux implementation of semaphores and read-write semaphores is very sophisticated, there are possible scenarios one can think of which are not yet implemented, for example there is no concept of interruptible read-write semaphores. This is obviously because there are no real-world situations which require these exotic flavours of the primitives.
Read-write semaphores differ from basic semaphores in the same way as read-write spinlocks differ from basic spinlocks: one can have multiple readers at a time but only one writer and there can be no readers while there are writers - i.e. the writer blocks all readers and new readers block while a writer is waiting.
Also, basic semaphores can be interruptible - just use the operations down/up_interruptible() instead of the plain down()/up() and check the value returned from down_interruptible(): it will be non zero if the operation was interrupted.
Using semaphores for mutual exclusion is ideal in situations where a critical code section may call by reference unknown functions registered by other subsystems/modules, i.e. the caller cannot know apriori whether the function blocks or not.
A simple example of semaphore usage is in kernel/sys.c, implementation of gethostname(2)/sethostname(2) system calls.
asmlinkage long sys_sethostname(char *name, int len)
{
int errno;
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
if (len < 0 || len > __NEW_UTS_LEN)
return -EINVAL;
down_write(&uts_sem);
errno = -EFAULT;
if (!copy_from_user(system_utsname.nodename, name, len)) {
system_utsname.nodename[len] = 0;
errno = 0;
}
up_write(&uts_sem);
return errno;
}
asmlinkage long sys_gethostname(char *name, int len)
{
int i, errno;
if (len < 0)
return -EINVAL;
down_read(&uts_sem);
i = 1 + strlen(system_utsname.nodename);
if (i > len)
i = len;
errno = 0;
if (copy_to_user(name, system_utsname.nodename, i))
errno = -EFAULT;
up_read(&uts_sem);
return errno;
}
The points to note about this example are:
1. The functions may block while copying data from/to userspace in copy_from_user()/copy_to_user(). Therefore they could not use any form of spinlock here.
2. The semaphore type chosen is read-write as opposed to basic because there may be lots of concurrent gethostname(2) requests which need not be mutually exclusive.
Although Linux implementation of semaphores and read-write semaphores is very sophisticated, there are possible scenarios one can think of which are not yet implemented, for example there is no concept of interruptible read-write semaphores. This is obviously because there are no real-world situations which require these exotic flavours of the primitives.
Monday, June 4, 2007
Spinlocks, Read-write Spinlocks and Big-Reader Spinlocks
Since the early days of Linux support (early 90s, this century), developers were faced with the classical problem of accessing shared data between different types of context (user process vs interrupt) and different instances of the same context from multiple cpus.
SMP support was added to Linux 1.3.42 on 15 Nov 1995 (the original patch was made to 1.3.37 in October the same year).
If the critical region of code may be executed by either process context and interrupt context, then the way to protect it using cli/sti instructions on UP is:
unsigned long flags;
save_flags(flags);
cli();
/* critical code */
restore_flags(flags);
While this is ok on UP, it obviously is of no use on SMP because the same code sequence may be executed simultaneously on another cpu, and while cli() provides protection against races with interrupt context on each CPU individually, it provides no protection at all against races between contexts running on different CPUs. This is where spinlocks are useful for.
There are three types of spinlocks: vanilla (basic), read-write and big-reader spinlocks. Read-write spinlocks should be used when there is a natural tendency of 'many readers and few writers'. Example of this is access to the list of registered filesystems (see fs/super.c). The list is guarded by the file_systems_lock read-write spinlock because one needs exclusive access only when registering/unregistering a filesystem, but any process can read the file /proc/filesystems or use the sysfs(2) system call to force a read-only scan of the file_systems list. This makes it sensible to use read-write spinlocks. With read-write spinlocks, one can have multiple readers at a time but only one writer and there can be no readers while there is a writer. Btw, it would be nice if new readers would not get a lock while there is a writer trying to get a lock, i.e. if Linux could correctly deal with the issue of potential writer starvation by multiple readers. This would mean that readers must be blocked while there is a writer attempting to get the lock. This is not currently the case and it is not obvious whether this should be fixed - the argument to the contrary is - readers usually take the lock for a very short time so should they really be starved while the writer takes the lock for potentially longer periods?
Big-reader spinlocks are a form of read-write spinlocks heavily optimised for very light read access, with a penalty for writes. There is a limited number of big-reader spinlocks - currently only two exist, of which one is used only on sparc64 (global irq) and the other is used for networking. In all other cases where the access pattern does not fit into any of these two scenarios, one should use basic spinlocks. You cannot block while holding any kind of spinlock.
Spinlocks come in three flavours: plain, _irq() and _bh().
1. Plain spin_lock()/spin_unlock(): if you know the interrupts are always disabled or if you do not race with interrupt context (e.g. from within interrupt handler), then you can use this one. It does not touch interrupt state on the current CPU.
2. spin_lock_irq()/spin_unlock_irq(): if you know that interrupts are always enabled then you can use this version, which simply disables (on lock) and re-enables (on unlock) interrupts on the current CPU. For example, rtc_read() uses spin_lock_irq(&rtc_lock) (interrupts are always enabled inside read()) whilst rtc_interrupt() uses spin_lock(&rtc_lock) (interrupts are always disabled inside interrupt handler). Note that rtc_read() uses spin_lock_irq() and not the more generic spin_lock_irqsave() because on entry to any system call interrupts are always enabled.
3. spin_lock_irqsave()/spin_unlock_irqrestore(): the strongest form, to be used when the interrupt state is not known, but only if interrupts matter at all, i.e. there is no point in using it if our interrupt handlers don't execute any critical code.
The reason you cannot use plain spin_lock() if you race against interrupt handlers is because if you take it and then an interrupt comes in on the same CPU, it will busy wait for the lock forever: the lock holder, having been interrupted, will not continue until the interrupt handler returns.
The most common usage of a spinlock is to access a data structure shared between user process context and interrupt handlers:
spinlock_t my_lock = SPIN_LOCK_UNLOCKED;
my_ioctl()
{
spin_lock_irq(&my_lock);
/* critical section */
spin_unlock_irq(&my_lock);
}
my_irq_handler()
{
spin_lock(&lock);
/* critical section */
spin_unlock(&lock);
}
There are a couple of things to note about this example:
1. The process context, represented here as a typical driver method - ioctl() (arguments and return values omitted for clarity), must use spin_lock_irq() because it knows that interrupts are always enabled while executing the device ioctl() method.
2. Interrupt context, represented here by my_irq_handler() (again arguments omitted for clarity) can use plain spin_lock() form because interrupts are disabled inside an interrupt handler.
SMP support was added to Linux 1.3.42 on 15 Nov 1995 (the original patch was made to 1.3.37 in October the same year).
If the critical region of code may be executed by either process context and interrupt context, then the way to protect it using cli/sti instructions on UP is:
unsigned long flags;
save_flags(flags);
cli();
/* critical code */
restore_flags(flags);
While this is ok on UP, it obviously is of no use on SMP because the same code sequence may be executed simultaneously on another cpu, and while cli() provides protection against races with interrupt context on each CPU individually, it provides no protection at all against races between contexts running on different CPUs. This is where spinlocks are useful for.
There are three types of spinlocks: vanilla (basic), read-write and big-reader spinlocks. Read-write spinlocks should be used when there is a natural tendency of 'many readers and few writers'. Example of this is access to the list of registered filesystems (see fs/super.c). The list is guarded by the file_systems_lock read-write spinlock because one needs exclusive access only when registering/unregistering a filesystem, but any process can read the file /proc/filesystems or use the sysfs(2) system call to force a read-only scan of the file_systems list. This makes it sensible to use read-write spinlocks. With read-write spinlocks, one can have multiple readers at a time but only one writer and there can be no readers while there is a writer. Btw, it would be nice if new readers would not get a lock while there is a writer trying to get a lock, i.e. if Linux could correctly deal with the issue of potential writer starvation by multiple readers. This would mean that readers must be blocked while there is a writer attempting to get the lock. This is not currently the case and it is not obvious whether this should be fixed - the argument to the contrary is - readers usually take the lock for a very short time so should they really be starved while the writer takes the lock for potentially longer periods?
Big-reader spinlocks are a form of read-write spinlocks heavily optimised for very light read access, with a penalty for writes. There is a limited number of big-reader spinlocks - currently only two exist, of which one is used only on sparc64 (global irq) and the other is used for networking. In all other cases where the access pattern does not fit into any of these two scenarios, one should use basic spinlocks. You cannot block while holding any kind of spinlock.
Spinlocks come in three flavours: plain, _irq() and _bh().
1. Plain spin_lock()/spin_unlock(): if you know the interrupts are always disabled or if you do not race with interrupt context (e.g. from within interrupt handler), then you can use this one. It does not touch interrupt state on the current CPU.
2. spin_lock_irq()/spin_unlock_irq(): if you know that interrupts are always enabled then you can use this version, which simply disables (on lock) and re-enables (on unlock) interrupts on the current CPU. For example, rtc_read() uses spin_lock_irq(&rtc_lock) (interrupts are always enabled inside read()) whilst rtc_interrupt() uses spin_lock(&rtc_lock) (interrupts are always disabled inside interrupt handler). Note that rtc_read() uses spin_lock_irq() and not the more generic spin_lock_irqsave() because on entry to any system call interrupts are always enabled.
3. spin_lock_irqsave()/spin_unlock_irqrestore(): the strongest form, to be used when the interrupt state is not known, but only if interrupts matter at all, i.e. there is no point in using it if our interrupt handlers don't execute any critical code.
The reason you cannot use plain spin_lock() if you race against interrupt handlers is because if you take it and then an interrupt comes in on the same CPU, it will busy wait for the lock forever: the lock holder, having been interrupted, will not continue until the interrupt handler returns.
The most common usage of a spinlock is to access a data structure shared between user process context and interrupt handlers:
spinlock_t my_lock = SPIN_LOCK_UNLOCKED;
my_ioctl()
{
spin_lock_irq(&my_lock);
/* critical section */
spin_unlock_irq(&my_lock);
}
my_irq_handler()
{
spin_lock(&lock);
/* critical section */
spin_unlock(&lock);
}
There are a couple of things to note about this example:
1. The process context, represented here as a typical driver method - ioctl() (arguments and return values omitted for clarity), must use spin_lock_irq() because it knows that interrupts are always enabled while executing the device ioctl() method.
2. Interrupt context, represented here by my_irq_handler() (again arguments omitted for clarity) can use plain spin_lock() form because interrupts are disabled inside an interrupt handler.
Friday, May 25, 2007
Linux Linked List Implementation
Before we go on to examine implementation of wait queues, we must acquaint ourselves with the Linux standard doubly-linked list implementation. Wait queues (as well as everything else in Linux) make heavy use of them and they are called in jargon "list.h implementation" because the most relevant file is include/linux/list.h.
The fundamental data structure here is struct list_head:
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
The first three macros are for initialising an empty list by pointing both next and prev pointers to itself. It is obvious from C syntactical restrictions which ones should be used where - for example, LIST_HEAD_INIT() can be used for structure's element initialisation in declaration, the second can be used for static variable initialising declarations and the third can be used inside a function.
The macro list_entry() gives access to individual list element, for example (from fs/file_table.c:fs_may_remount_ro()):
struct super_block {
...
struct list_head s_files;
...
} *sb = &some_super_block;
struct file {
...
struct list_head f_list;
...
} *file;
struct list_head *p;
for (p = sb->s_files.next; p != &sb->s_files; p = p->next) {
struct file *file = list_entry(p, struct file, f_list);
do something to 'file'
}
A good example of the use of list_for_each() macro is in the scheduler where we walk the runqueue looking for the process with highest goodness:
static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
Here, p->run_list is declared as struct list_head run_list inside task_struct structure and serves as anchor to the list. Removing an element from the list and adding (to head or tail of the list) is done by list_del()/list_add()/list_add_tail() macros. The examples below are adding and removing a task from runqueue:
static inline void del_from_runqueue(struct task_struct * p)
{
nr_running--;
list_del(&p->run_list);
p->run_list.next = NULL;
}
static inline void add_to_runqueue(struct task_struct * p)
{
list_add(&p->run_list, &runqueue_head);
nr_running++;
}
static inline void move_last_runqueue(struct task_struct * p)
{
list_del(&p->run_list);
list_add_tail(&p->run_list, &runqueue_head);
}
static inline void move_first_runqueue(struct task_struct * p)
{
list_del(&p->run_list);
list_add(&p->run_list, &runqueue_head);
}
The fundamental data structure here is struct list_head:
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
The first three macros are for initialising an empty list by pointing both next and prev pointers to itself. It is obvious from C syntactical restrictions which ones should be used where - for example, LIST_HEAD_INIT() can be used for structure's element initialisation in declaration, the second can be used for static variable initialising declarations and the third can be used inside a function.
The macro list_entry() gives access to individual list element, for example (from fs/file_table.c:fs_may_remount_ro()):
struct super_block {
...
struct list_head s_files;
...
} *sb = &some_super_block;
struct file {
...
struct list_head f_list;
...
} *file;
struct list_head *p;
for (p = sb->s_files.next; p != &sb->s_files; p = p->next) {
struct file *file = list_entry(p, struct file, f_list);
do something to 'file'
}
A good example of the use of list_for_each() macro is in the scheduler where we walk the runqueue looking for the process with highest goodness:
static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
Here, p->run_list is declared as struct list_head run_list inside task_struct structure and serves as anchor to the list. Removing an element from the list and adding (to head or tail of the list) is done by list_del()/list_add()/list_add_tail() macros. The examples below are adding and removing a task from runqueue:
static inline void del_from_runqueue(struct task_struct * p)
{
nr_running--;
list_del(&p->run_list);
p->run_list.next = NULL;
}
static inline void add_to_runqueue(struct task_struct * p)
{
list_add(&p->run_list, &runqueue_head);
nr_running++;
}
static inline void move_last_runqueue(struct task_struct * p)
{
list_del(&p->run_list);
list_add_tail(&p->run_list, &runqueue_head);
}
static inline void move_first_runqueue(struct task_struct * p)
{
list_del(&p->run_list);
list_add(&p->run_list, &runqueue_head);
}
Wednesday, May 16, 2007
Interrupts
Interrupts Exceptions and Traps
Normally, processes are asleep, waiting on some event. When that event happens, these processes are called into action. Remember, it is the responsibility of the sched process to free memory when a process runs short of it. So, it is not until memory is needed that sched starts up.
How does sched know that memory is needed? When a process makes reference to a place in its virtual memory space that does not yet exist in physical memory, a page fault occurs. Faults belong to a group of system events called exceptions. An exception is simply something that occurs outside of what is normally expected. Faults (exceptions) can occur either before or during the execution of an instruction.
For example, if an instruction that is not yet in memory needs to be read, the exception (page fault) occurs before the instruction starts being executed. On the other hand, if the instruction is supposed to read data from a virtual memory location that isn't in physical memory, the exception occurs during the execution of the instruction. In cases like these, once the missing memory location is loaded into physical memory, the CPU can start the instruction.
Traps are exceptions that occur after an instruction has been executed. For example, attempting to divide by zero generates an exception. However, in this case it doesn't make sense to restart the instruction because every time we to try to run that instruction, it still comes up with a Divide-by-Zero exception. That is, all memory references are read before we start to execute the command.
It is also possible for processes to generate exceptions intentionally. These programmed exceptions are called software interrupts.
When any one of these exceptions occurs, the system must react to the exception. To react, the system will usually switch to another process to deal with the exception, which means a context switch. In our discussion of process scheduling, I mentioned that at every clock tick the priority of every process is recalculated. To make those calculations, something other than those processes have to run.
In Linux, the system timer (or clock) is programmed to generate a hardware interrupt 100 times a second (as defined by the HZ system parameter). The interrupt is accomplished by sending a signal to a special chip on the motherboard called an interrupt controller. (We go into more detail about these in the section on hardware.) The interrupt controller then sends an interrupt to the CPU. When the CPU receives this signal, it knows that the clock tick has occurred and it jumps to a special part of the kernel that handles the clock interrupt. Scheduling priorities are also recalculated within this same section of code.
Because the system might be doing something more important when the clock generates an interrupt, you can turn interrupts off using "masking". In other words, there is a way to mask out interrupts. Interrupts that can be masked out are called maskable interrupts. An example of something more important than the clock would be accepting input from the keyboard. This is why clock ticks are lost on systems with a lot of users inputting a lot of data. As a result, the system clock appears to slow down over time.
Sometimes events occur on the system that you want to know about no matter what. Imagine what would happen if memory was bad. If the system was in the middle of writing to the hard disk when it encountered the bad memory, the results could be disastrous. If the system recognizes the bad memory, the hardware generates an interrupt to alert the CPU. If the CPU is told to ignore all hardware interrupts, it would ignore this one. Instead, the hardware has the ability to generate an interrupt that cannot be ignored, or "masked out", called a non-maskable interrupt. Non-maskable interrupts are generically referred to as NMIs.
When an interrupt or an exception occurs, it must be dealt with to ensure the integrity of the system. How the system reacts depends on whether it was an exception or interrupt. In addition, what happens when the hard disk generates an interrupt is going to be different than when the clock generates one.
Within the kernel is the Interrupt Descriptor Table (IDT), which is a list of descriptors (pointers) that point to the functions that handle the particular interrupt or exception. These functions are called the interrupt or exception handlers. When an interrupt or exception occurs, it has a particular value, called an identifier or vector. Table 0-2 contains a list of the defined interrupt vectors.
Table Interrupt Vectors
Id Description
0 Divide error
1 Debug exception
2 Non-maskable interrupt
3 Breakpoint
4 Overflow
5 Bounds check
6 Invalid opcode
7 Coprocessor not available
8 Double fault
9 (reserved)
10 Invalid TSS
11 Segment not present
12 Stack exception
13 General protection fault
14 Page fault
15 (reserved)
16 Coprocessor error
17 alignment error (80486)
18-31 (reserved)
32-255 External (HW) interrupts
These numbers are actually indices into the IDT. When an interrupt, exception, or trap occurs, the system knows which number corresponds to that event. It then uses that number as an index into the IDT, which in turn points to the appropriate area of memory for handling the event.
It is possible for devices to share interrupts; that is, multiple devices on the system can be (and ofter are) configured to use the same interrupt. In fact, certain kinds of computers are designed to allow devices to share interrupts (I'll talk about them in the hardware section). If the interrupt number is an offset into a table of pointers to interrupt routines, how does the kernel know which one to call?
As it turns out, there are two IDTs: one for shared interrupts and one for non-shared interrupts. During a kernel rebuild (more on that later), the kernel determines whether the interrupt is shared. If it is, it places the pointer to that interrupt routine into the shared IDT. When an interrupt is generated, the interrupt routine for each of these devices is called. It is up to the interrupt routine to check whether the associated device really generated an interrupt. The order in which they are called is the order in which they are linked.
When an exception happens in user mode, the process passes through a trap gate. At this point, the CPU no longer uses the process' user stack, but rather the system stack within that process' task structure. (each task structure has a portion set aside for the system stack.) At this point, that process is operating in system (kernel) mode; that is, at the highest privilege level, 0.
The kernel treats interrupts very similarly to the way it treats exceptions: all the general purpose registers are pushed onto the system stack and a common interrupt handler is called. The current interrupt priority is saved and the new priority is loaded. This prevents interrupts at lower priority levels from interrupting the kernel while it handles this interrupt. Then the real interrupt handler is called.
Because an exception is not fatal, the process will return from whence it came. It is possible that a context switch occurs immediately on return from kernel mode. This might be the result of an exception with a lower priority. Because it could not interrupt the process in kernel mode, it had to wait until it returned to user mode. Because the exception has a higher priority than the process when it is in user mode, a context switch occurs immediately after the process returns to user mode.
It is abnormal for another exception to occur while the process is in kernel mode. Even a page fault can be considered a software event. Because the entire kernel is in memory all the time, a page fault should not happen. When a page fault does happen when in kernel mode, the kernel panics. Special routines have been built into the kernel to deal with the panic to help the system shut down as gracefully as possible. Should something else happen to cause another exception while the system is trying to panic, a double panic occurs.
This may sound confusing because I just said that a context switch could occur as the result of another exception. What this means is that the exception occurred in user mode, so there must be a jump to kernel mode. This does not mean that the process continues in kernel mode until it is finished. It may (depending on what it is doing) be context-switched out. If another process has run before the first one gets its turn on the CPU again, that process may generate the exception.
Unlike exceptions, another interrupt could possibly occur while the kernel is handling the first one (and therefore is in kernel mode). If the second interrupt has a higher priority than the first, a context switch will occur and the new interrupt will be handled. If the second interrupt has the same or lower priority, then the kernel will "put it on hold." These are not ignored, but rather saved (queued) to be dealt with later.
Normally, processes are asleep, waiting on some event. When that event happens, these processes are called into action. Remember, it is the responsibility of the sched process to free memory when a process runs short of it. So, it is not until memory is needed that sched starts up.
How does sched know that memory is needed? When a process makes reference to a place in its virtual memory space that does not yet exist in physical memory, a page fault occurs. Faults belong to a group of system events called exceptions. An exception is simply something that occurs outside of what is normally expected. Faults (exceptions) can occur either before or during the execution of an instruction.
For example, if an instruction that is not yet in memory needs to be read, the exception (page fault) occurs before the instruction starts being executed. On the other hand, if the instruction is supposed to read data from a virtual memory location that isn't in physical memory, the exception occurs during the execution of the instruction. In cases like these, once the missing memory location is loaded into physical memory, the CPU can start the instruction.
Traps are exceptions that occur after an instruction has been executed. For example, attempting to divide by zero generates an exception. However, in this case it doesn't make sense to restart the instruction because every time we to try to run that instruction, it still comes up with a Divide-by-Zero exception. That is, all memory references are read before we start to execute the command.
It is also possible for processes to generate exceptions intentionally. These programmed exceptions are called software interrupts.
When any one of these exceptions occurs, the system must react to the exception. To react, the system will usually switch to another process to deal with the exception, which means a context switch. In our discussion of process scheduling, I mentioned that at every clock tick the priority of every process is recalculated. To make those calculations, something other than those processes have to run.
In Linux, the system timer (or clock) is programmed to generate a hardware interrupt 100 times a second (as defined by the HZ system parameter). The interrupt is accomplished by sending a signal to a special chip on the motherboard called an interrupt controller. (We go into more detail about these in the section on hardware.) The interrupt controller then sends an interrupt to the CPU. When the CPU receives this signal, it knows that the clock tick has occurred and it jumps to a special part of the kernel that handles the clock interrupt. Scheduling priorities are also recalculated within this same section of code.
Because the system might be doing something more important when the clock generates an interrupt, you can turn interrupts off using "masking". In other words, there is a way to mask out interrupts. Interrupts that can be masked out are called maskable interrupts. An example of something more important than the clock would be accepting input from the keyboard. This is why clock ticks are lost on systems with a lot of users inputting a lot of data. As a result, the system clock appears to slow down over time.
Sometimes events occur on the system that you want to know about no matter what. Imagine what would happen if memory was bad. If the system was in the middle of writing to the hard disk when it encountered the bad memory, the results could be disastrous. If the system recognizes the bad memory, the hardware generates an interrupt to alert the CPU. If the CPU is told to ignore all hardware interrupts, it would ignore this one. Instead, the hardware has the ability to generate an interrupt that cannot be ignored, or "masked out", called a non-maskable interrupt. Non-maskable interrupts are generically referred to as NMIs.
When an interrupt or an exception occurs, it must be dealt with to ensure the integrity of the system. How the system reacts depends on whether it was an exception or interrupt. In addition, what happens when the hard disk generates an interrupt is going to be different than when the clock generates one.
Within the kernel is the Interrupt Descriptor Table (IDT), which is a list of descriptors (pointers) that point to the functions that handle the particular interrupt or exception. These functions are called the interrupt or exception handlers. When an interrupt or exception occurs, it has a particular value, called an identifier or vector. Table 0-2 contains a list of the defined interrupt vectors.
Table Interrupt Vectors
Id Description
0 Divide error
1 Debug exception
2 Non-maskable interrupt
3 Breakpoint
4 Overflow
5 Bounds check
6 Invalid opcode
7 Coprocessor not available
8 Double fault
9 (reserved)
10 Invalid TSS
11 Segment not present
12 Stack exception
13 General protection fault
14 Page fault
15 (reserved)
16 Coprocessor error
17 alignment error (80486)
18-31 (reserved)
32-255 External (HW) interrupts
These numbers are actually indices into the IDT. When an interrupt, exception, or trap occurs, the system knows which number corresponds to that event. It then uses that number as an index into the IDT, which in turn points to the appropriate area of memory for handling the event.
It is possible for devices to share interrupts; that is, multiple devices on the system can be (and ofter are) configured to use the same interrupt. In fact, certain kinds of computers are designed to allow devices to share interrupts (I'll talk about them in the hardware section). If the interrupt number is an offset into a table of pointers to interrupt routines, how does the kernel know which one to call?
As it turns out, there are two IDTs: one for shared interrupts and one for non-shared interrupts. During a kernel rebuild (more on that later), the kernel determines whether the interrupt is shared. If it is, it places the pointer to that interrupt routine into the shared IDT. When an interrupt is generated, the interrupt routine for each of these devices is called. It is up to the interrupt routine to check whether the associated device really generated an interrupt. The order in which they are called is the order in which they are linked.
When an exception happens in user mode, the process passes through a trap gate. At this point, the CPU no longer uses the process' user stack, but rather the system stack within that process' task structure. (each task structure has a portion set aside for the system stack.) At this point, that process is operating in system (kernel) mode; that is, at the highest privilege level, 0.
The kernel treats interrupts very similarly to the way it treats exceptions: all the general purpose registers are pushed onto the system stack and a common interrupt handler is called. The current interrupt priority is saved and the new priority is loaded. This prevents interrupts at lower priority levels from interrupting the kernel while it handles this interrupt. Then the real interrupt handler is called.
Because an exception is not fatal, the process will return from whence it came. It is possible that a context switch occurs immediately on return from kernel mode. This might be the result of an exception with a lower priority. Because it could not interrupt the process in kernel mode, it had to wait until it returned to user mode. Because the exception has a higher priority than the process when it is in user mode, a context switch occurs immediately after the process returns to user mode.
It is abnormal for another exception to occur while the process is in kernel mode. Even a page fault can be considered a software event. Because the entire kernel is in memory all the time, a page fault should not happen. When a page fault does happen when in kernel mode, the kernel panics. Special routines have been built into the kernel to deal with the panic to help the system shut down as gracefully as possible. Should something else happen to cause another exception while the system is trying to panic, a double panic occurs.
This may sound confusing because I just said that a context switch could occur as the result of another exception. What this means is that the exception occurred in user mode, so there must be a jump to kernel mode. This does not mean that the process continues in kernel mode until it is finished. It may (depending on what it is doing) be context-switched out. If another process has run before the first one gets its turn on the CPU again, that process may generate the exception.
Unlike exceptions, another interrupt could possibly occur while the kernel is handling the first one (and therefore is in kernel mode). If the second interrupt has a higher priority than the first, a context switch will occur and the new interrupt will be handled. If the second interrupt has the same or lower priority, then the kernel will "put it on hold." These are not ignored, but rather saved (queued) to be dealt with later.
Thread Library changes between 2.4 and 2.6 Linux Kernels
Notes:
For most application developers, the majority of the changes made to the Linux kernel between the 2.4 and 2.6 kernel families have little direct impact. Most kernel changes only manifest themselves through increased system performance and capacity. Kernel and system changes that affect how applications spawn and manage other processes and threads are a significant exception to this rule.
The 2.6 Linux kernel introduces a new, improved threading model that is implemented through the NPTL. The adoption of a new threading model has significant implications for developers, system run-time libraries such as the GNU C library (glibc), shared application libraries, and so on. This white paper provides an overview of basic threading concepts, discusses new and existing Linux threading models, and then highlights the sorts of application changes that you might have to make to existing multi-threaded applications in order to enable them to work correctly with NPTL under the 2.6 Linux kernel.
Threading 101
On multi-processing systems such as Linux, the concept of one process creating another is fundamental. The most obvious example is a shell such as the Bash shell, the standard Linux command interpreter. The shell executes applications in response to user commands, and can either start commands and wait for them to finish or execute them as separate, concurrent processes (commonly referred to as "running in the background").
One process typically creates another through a set of fork() and exec() function calls. The initial process calls the fork() function, creating a clone of itself (known as a child process) that inherits the entire execution environment of the process that created it. The fork() call returns the child's process identifier (PID) in the parent process, and a PID of 0 in the child process. The child process then uses the exec() call to execute some other command, which totally replaces its existing execution context with that of the exec()'d command. At the same time, the parent process typically either exits immediately or waits until the child process returns its status. A simple example of this is the following:
int pid;
if (pid=fork()) {
/* parent code */
exit(1);
} else {
/* child code */
execl( "command", "arg1", "arg2", ...);
printf("Should never get here...\n");
exit (-1);
}
This model for process creation is simple and easy to use, but requires substantial system overhead. Child processes inherit a separate copy of the complete state of their parent, including its address space, global variables, open file descriptors, and so on. This consumes a fair amount of system resources, makes it relatively complex for child processes to share resources or communicate with each other, and is extremely resource-intensive for use at the operating system level.
Threads are similar to processes, but with some notable exceptions that make them far more suitable for use in complex, modern systems. Threads are essentially sub-processes that share the majority of the resources of their parent process, and thus require a lesser amount of system resources. A traditional way of thinking about threads is by referring to them as lightweight processes. All of the threads created by a process share the same address space, global variables, open file descriptors, pending alarms, signals and signal handlers, and system accounting information. Each thread maintains its own program counter, registers, stack, and state information.
A key differentiator between different thread implementations is the interaction between kernel threads, user-space processes, and user-space threads. This will be discussed in more detail later in this white paper.
Linux Threading Models
The standard Linux threading library in all stable versions of Linux prior to 2.6 is known as LinuxThreads. This library has been supported for use with the GNU C library, glibc, since glibc 2.0, and is largely POSIX-compliant.
NOTE: The primary libraries produced when compiling the LinuxThreads and Native POSIX Thread Library source code are libpthread.so and libpthread.a (for POSIX thread library). For this reasons, the terms LinuxThreads and pthreads have historically been used interchangeably, which confusing in light of the adoption of the NPTL. This whitepaper uses the term LinuxThreads and NPTL to clearly differentiate between the two threading libraries and their capabilities. The actual library names were preserved to minimize changes to existing Makefiles and linking commands.
LinuxThreads has a variety of performance, scalability, and usability limitations. It uses a compile-time setting for the number of threads that a single process can create, and uses a per-process manager thread to create and coordinate between all threads owned by each process. This significantly increases the overhead of creating and destroying threads. Signal handling is done on a per-process, rather than a per-thread, basis, though each thread has a separate process ID. Issues such as these, in combination with design issues such as an asymmetric relationship between kernel and user-space threads, and the lack of per-thread synchronization primitives for inter-thread communication and resource sharing, places some fundamental limitations on the number of threads that can simultaneously be created and do meaningful work in a LinuxThreads implementation.
The next threading model introduced for Linux was IBM's Next Generation POSIX Threads (NGPT) project. This was an external threading library that worked in conjunction with the LinuxThreads package, but provided additional POSIX compliance and better performance than the standard LinuxThreads package. This threading package is still available for use with 2.4 and earlier Linux kernels, but is no longer actively being worked on due to the new threading model introduced with the 2.5 and kernel series and made publicly available in the 2.6 kernel tree.
The Native POSIX Threading Library replaces LinuxThreads and NGPT in the 2.5 and later kernels. NPTL brings high-performance threading support to Linux, and provides the foundation required by multi-threaded enterprise applications such as database systems, high-capacity and high-load web and mail servers, and so on. NPTL was developed as part of the 2.5 kernel development process and was integrated with Linux run-time elements such as glibc at that time. NPTL is the strategic direction for Linux threading in the future.
Some Linux vendors, such as later versions of Red Hat Linux, have backported NPTL to earlier kernels and have even made the threading environment for specific processes selectable through an environment variable (LD_ASSUME_KERNEL). On systems that support this feature, the variable is set via a command such as the following:
# export LD_ASSUME_KERNEL=2.4.1
This is a clever way to enable some existing applications that rely on LinuxThreads to continue to work in an NPTL environment, but is a short-term solution. To make the most of the design and performance benefits provided by NPTL, you should update the code for any existing applications that use threading.
The next sections discuss the implications of the changes between the LinuxThreads and NPTL threading implementations as far as your applications are concerned. The first section discusses development changes related to the updated toolchains used with the 2.6 kernel highlights. A subsequent section highlights aspects of your applications that you must change due to differences between the LinuxThreads and NPTL implementations, in order to make the most of the increased power and performance of NPTL.
Recompiling Applications for 2.6 and NPTL
Though many applications will migrate from Linux 2.4 to 2.6 without recompilation, the addition of Native POSIX Thread Library technology will require minor modifications in most threaded applications. A subsequent section of this whitepaper, "Updating Applications for NPTL", discusses the primary situations where recompilation may be required.
Those applications that do require recompilation may be affected by the updated compilers included with distributions such as TimeSys Linux that are based around a 2.6-based kernel. TimeSys ships its 2.6 Reference Distributions with version 3.3.2 of the C and C++ compilers from the GNU Compiler Collection (GCC), and uses an updated version of the binutils package that makes up the remainder of a standard Linux toolchain (providing the assembler, linker, library archiver, and so).
Simply using a 2.6 based kernel does not mean that you are automatically using the NPTL. To determine the threading library that a system uses, you can execute the getconf command (part of the glibc package), to examine the GNU_LIBPTHREAD_VERSION environment variable, as in the following command example:
# getconf GNU_LIBPTHREAD_VERSION
linuxthreads-0.10
If your system uses the NPTL, the command would return the value of NPTL that your system was using, as in the following example:
# getconf GNU_LIBPTHREAD_VERSION
nptl-0.60
If you are building your own toolchain to work with a 2.6 system you must, of course, make sure that you've built the toolchain on a 2.6 system, and that you have enabled NPTL support in the version of the C library used by your toolchain. You will also need recent source codeyou're your C library. For example, if you are building glibc with NPTL support, version 2.3.3 or better of the glibc source is recommended. Enabling NPTL support when building a C library, such as glibc, is analogous to the mechanism used for enabling LinuxThreads support for glibc. This is done by using the configuration option --enable-add-ons=nptl when configuring glibc, rather than --enable-add-ons=linuxthreads. The latest NPTL source code is available here. You will also need a recent version of GCC (3.3.2 or better suggested for x86 platforms, 3.4 suggested for PPC platforms), and a version of binutils that supports the Call Frame Information (CFI) directive (2.14.90.0.7 or better suggested; available here).
In general, if your applications were compiled with earlier versions of GCC, you may notice changes in warning messages, code size, and changes to the options provided by the GCC compiler and the rest of the toolchain. It is especially important to be aware of the potential for increased code size when you are recompiling embedded applications. You may need to take advantage of additional or new optimization options in order to continue to fit your existing applications in resource-constrained environments. Newer versions of GCC are also increasingly conformant to various C and C++ specifications, and are therefore likely to complain about aspects of your application code that earlier versions of these compilers ignored. In general, new warnings from updated compilers should be seen as an opportunity to weed out latent defects.
Newer versions of GCC have also deprecated some machine-specific options (specified using -m) in favor of more general optimization options (specified using -f). This may require that you update values such as the CFLAGS options specified in application Makefiles.
Finally, newer versions of GCC implement optimizations that require them to notice possible alias situations that may have been ignored by earlier compilers. The aliasing issues can be resolved (at some performance cost) by using the no strict aliasing compiler option (-fno-strict-aliasing).
Updating Applications for NPTL
The changes between 2.4's threading support and NPTL provide significant design and performance improvements. NPTL is far more compliant with the POSIX specification than the LinuxThreads package was under 2.4. NPTL also supports useful features such as mutexes that are shared among threads, simplifying resource sharing, conflict prevention, and increasing parallelism. Finally, NPTL is vastly more efficient than 2.4's threading support. Some of the standard performance metrics used at TimeSys have shown NPTL implementations to be up to three orders of magnitude faster than the same code using LinuxThreads.
Some of the more complex changes that you may have to make in your application logic when moving to NPTL are changes related to NPTL's improved support for POSIX signals and signal handling. LinuxThreads implemented generic Unix-style threads, but were limited by various implementation details. NPTL is a POSIX-compliant threading implementation, and therefore handles signals better both between processes and between all threads within those processes. With the NPTL, signals can now be sent from one thread to another, rather than simply on a per-process basis. Signals can also use arguments to transfer information from one thread to another.
Using the NPTL also requires that you make changes to existing code that needs to be able to uniquely identify specific threads. Under LinuxThreads, each thread had a unique process ID (PID). Each thread now shares the PID of its parent process, and the getpid() function therefore returns the same process ID for all threads in a process. With NPTL, a thread's Thread ID must be used to uniquely identify individual threads.
Changes to thread and process IDs also mean that the processes that are traditionally used to spawn processes must now be thread-aware. For example, the exec() functions are now thread-aware, so that a thread inherits the PID of its caller. However, any application that depended on having all threads survive an exec() will need some modification. The parent of a multi-threaded process is notified of a child's termination only when the entire process terminates. Thread-related changes have also been made to the behavior of related fork() calls. For example, functions registered with the pthread_at_fork() function are no longer run when a vfork() occurs.
In addition to changing the internals of thread identification, NPTL does away with the LinuxThreads notion of a manager thread, simplifying the process/thread relationship and eliminating what was essentially administrative overhead under LinuxThreads. This may require application changes if, for example, your application kept track of the number of threads running on its behalf or looked for the manager thread as a signal target.
Finally, using a new threading library means that certain threading functions that were available under LinuxThreads are no longer supported under the NPTL. For example, the pthread_kill_other_threads_np() function is no longer available. This function was used to simulate POSIX-conformant exec() functions. Since the exec() functions themselves are now POSIX conformant, the helper function is not necessary.
For additional information about the design and implementation of the NPTL, a general design and philosophy document is available here.
Conclusion
Changing the kernel that your computer system runs is not necessarily an easy task, but is eminently doable. The white papers in this series have highlighted the issue in configuring the 2.6 kernel, updating device drivers, migrating desktop and custom systems, and updating applications. Certified 2.6-based distributions targeted for embedded use are already available from vendors such as TimeSys, whose 2.6 reference distribution was the first 2.6-based distribution for PPC systems. High-quality commercial software such as TimeSys TimeStorm IDE and TimeStorm Linux Developers Suite (LDS) is designed to help you migrate any Linux kernel, device driver, application, or deployed system to take advantage of the power of the 2.6 kernel and updated packages, threading methodology, and so on.
Linux is a shining example of the power of the Open Source movement as a positive force for change in the software industry. The Linux kernel, the core of any Linux distribution, is constantly evolving to incorporate new technologies and improve performance, scalability, support, and usability. The 2.6 kernel increases the spectrum of systems for which Linux is well-suited, from PDAs, process control systems, and set-top boxes all the way to enterprise servers. The cost, power, and supportability advantages by Linux are more obvious than ever in today's business market and fast-paced technical environment.
For most application developers, the majority of the changes made to the Linux kernel between the 2.4 and 2.6 kernel families have little direct impact. Most kernel changes only manifest themselves through increased system performance and capacity. Kernel and system changes that affect how applications spawn and manage other processes and threads are a significant exception to this rule.
The 2.6 Linux kernel introduces a new, improved threading model that is implemented through the NPTL. The adoption of a new threading model has significant implications for developers, system run-time libraries such as the GNU C library (glibc), shared application libraries, and so on. This white paper provides an overview of basic threading concepts, discusses new and existing Linux threading models, and then highlights the sorts of application changes that you might have to make to existing multi-threaded applications in order to enable them to work correctly with NPTL under the 2.6 Linux kernel.
Threading 101
On multi-processing systems such as Linux, the concept of one process creating another is fundamental. The most obvious example is a shell such as the Bash shell, the standard Linux command interpreter. The shell executes applications in response to user commands, and can either start commands and wait for them to finish or execute them as separate, concurrent processes (commonly referred to as "running in the background").
One process typically creates another through a set of fork() and exec() function calls. The initial process calls the fork() function, creating a clone of itself (known as a child process) that inherits the entire execution environment of the process that created it. The fork() call returns the child's process identifier (PID) in the parent process, and a PID of 0 in the child process. The child process then uses the exec() call to execute some other command, which totally replaces its existing execution context with that of the exec()'d command. At the same time, the parent process typically either exits immediately or waits until the child process returns its status. A simple example of this is the following:
int pid;
if (pid=fork()) {
/* parent code */
exit(1);
} else {
/* child code */
execl( "command", "arg1", "arg2", ...);
printf("Should never get here...\n");
exit (-1);
}
This model for process creation is simple and easy to use, but requires substantial system overhead. Child processes inherit a separate copy of the complete state of their parent, including its address space, global variables, open file descriptors, and so on. This consumes a fair amount of system resources, makes it relatively complex for child processes to share resources or communicate with each other, and is extremely resource-intensive for use at the operating system level.
Threads are similar to processes, but with some notable exceptions that make them far more suitable for use in complex, modern systems. Threads are essentially sub-processes that share the majority of the resources of their parent process, and thus require a lesser amount of system resources. A traditional way of thinking about threads is by referring to them as lightweight processes. All of the threads created by a process share the same address space, global variables, open file descriptors, pending alarms, signals and signal handlers, and system accounting information. Each thread maintains its own program counter, registers, stack, and state information.
A key differentiator between different thread implementations is the interaction between kernel threads, user-space processes, and user-space threads. This will be discussed in more detail later in this white paper.
Linux Threading Models
The standard Linux threading library in all stable versions of Linux prior to 2.6 is known as LinuxThreads. This library has been supported for use with the GNU C library, glibc, since glibc 2.0, and is largely POSIX-compliant.
NOTE: The primary libraries produced when compiling the LinuxThreads and Native POSIX Thread Library source code are libpthread.so and libpthread.a (for POSIX thread library). For this reasons, the terms LinuxThreads and pthreads have historically been used interchangeably, which confusing in light of the adoption of the NPTL. This whitepaper uses the term LinuxThreads and NPTL to clearly differentiate between the two threading libraries and their capabilities. The actual library names were preserved to minimize changes to existing Makefiles and linking commands.
LinuxThreads has a variety of performance, scalability, and usability limitations. It uses a compile-time setting for the number of threads that a single process can create, and uses a per-process manager thread to create and coordinate between all threads owned by each process. This significantly increases the overhead of creating and destroying threads. Signal handling is done on a per-process, rather than a per-thread, basis, though each thread has a separate process ID. Issues such as these, in combination with design issues such as an asymmetric relationship between kernel and user-space threads, and the lack of per-thread synchronization primitives for inter-thread communication and resource sharing, places some fundamental limitations on the number of threads that can simultaneously be created and do meaningful work in a LinuxThreads implementation.
The next threading model introduced for Linux was IBM's Next Generation POSIX Threads (NGPT) project. This was an external threading library that worked in conjunction with the LinuxThreads package, but provided additional POSIX compliance and better performance than the standard LinuxThreads package. This threading package is still available for use with 2.4 and earlier Linux kernels, but is no longer actively being worked on due to the new threading model introduced with the 2.5 and kernel series and made publicly available in the 2.6 kernel tree.
The Native POSIX Threading Library replaces LinuxThreads and NGPT in the 2.5 and later kernels. NPTL brings high-performance threading support to Linux, and provides the foundation required by multi-threaded enterprise applications such as database systems, high-capacity and high-load web and mail servers, and so on. NPTL was developed as part of the 2.5 kernel development process and was integrated with Linux run-time elements such as glibc at that time. NPTL is the strategic direction for Linux threading in the future.
Some Linux vendors, such as later versions of Red Hat Linux, have backported NPTL to earlier kernels and have even made the threading environment for specific processes selectable through an environment variable (LD_ASSUME_KERNEL). On systems that support this feature, the variable is set via a command such as the following:
# export LD_ASSUME_KERNEL=2.4.1
This is a clever way to enable some existing applications that rely on LinuxThreads to continue to work in an NPTL environment, but is a short-term solution. To make the most of the design and performance benefits provided by NPTL, you should update the code for any existing applications that use threading.
The next sections discuss the implications of the changes between the LinuxThreads and NPTL threading implementations as far as your applications are concerned. The first section discusses development changes related to the updated toolchains used with the 2.6 kernel highlights. A subsequent section highlights aspects of your applications that you must change due to differences between the LinuxThreads and NPTL implementations, in order to make the most of the increased power and performance of NPTL.
Recompiling Applications for 2.6 and NPTL
Though many applications will migrate from Linux 2.4 to 2.6 without recompilation, the addition of Native POSIX Thread Library technology will require minor modifications in most threaded applications. A subsequent section of this whitepaper, "Updating Applications for NPTL", discusses the primary situations where recompilation may be required.
Those applications that do require recompilation may be affected by the updated compilers included with distributions such as TimeSys Linux that are based around a 2.6-based kernel. TimeSys ships its 2.6 Reference Distributions with version 3.3.2 of the C and C++ compilers from the GNU Compiler Collection (GCC), and uses an updated version of the binutils package that makes up the remainder of a standard Linux toolchain (providing the assembler, linker, library archiver, and so).
Simply using a 2.6 based kernel does not mean that you are automatically using the NPTL. To determine the threading library that a system uses, you can execute the getconf command (part of the glibc package), to examine the GNU_LIBPTHREAD_VERSION environment variable, as in the following command example:
# getconf GNU_LIBPTHREAD_VERSION
linuxthreads-0.10
If your system uses the NPTL, the command would return the value of NPTL that your system was using, as in the following example:
# getconf GNU_LIBPTHREAD_VERSION
nptl-0.60
If you are building your own toolchain to work with a 2.6 system you must, of course, make sure that you've built the toolchain on a 2.6 system, and that you have enabled NPTL support in the version of the C library used by your toolchain. You will also need recent source codeyou're your C library. For example, if you are building glibc with NPTL support, version 2.3.3 or better of the glibc source is recommended. Enabling NPTL support when building a C library, such as glibc, is analogous to the mechanism used for enabling LinuxThreads support for glibc. This is done by using the configuration option --enable-add-ons=nptl when configuring glibc, rather than --enable-add-ons=linuxthreads. The latest NPTL source code is available here. You will also need a recent version of GCC (3.3.2 or better suggested for x86 platforms, 3.4 suggested for PPC platforms), and a version of binutils that supports the Call Frame Information (CFI) directive (2.14.90.0.7 or better suggested; available here).
In general, if your applications were compiled with earlier versions of GCC, you may notice changes in warning messages, code size, and changes to the options provided by the GCC compiler and the rest of the toolchain. It is especially important to be aware of the potential for increased code size when you are recompiling embedded applications. You may need to take advantage of additional or new optimization options in order to continue to fit your existing applications in resource-constrained environments. Newer versions of GCC are also increasingly conformant to various C and C++ specifications, and are therefore likely to complain about aspects of your application code that earlier versions of these compilers ignored. In general, new warnings from updated compilers should be seen as an opportunity to weed out latent defects.
Newer versions of GCC have also deprecated some machine-specific options (specified using -m) in favor of more general optimization options (specified using -f). This may require that you update values such as the CFLAGS options specified in application Makefiles.
Finally, newer versions of GCC implement optimizations that require them to notice possible alias situations that may have been ignored by earlier compilers. The aliasing issues can be resolved (at some performance cost) by using the no strict aliasing compiler option (-fno-strict-aliasing).
Updating Applications for NPTL
The changes between 2.4's threading support and NPTL provide significant design and performance improvements. NPTL is far more compliant with the POSIX specification than the LinuxThreads package was under 2.4. NPTL also supports useful features such as mutexes that are shared among threads, simplifying resource sharing, conflict prevention, and increasing parallelism. Finally, NPTL is vastly more efficient than 2.4's threading support. Some of the standard performance metrics used at TimeSys have shown NPTL implementations to be up to three orders of magnitude faster than the same code using LinuxThreads.
Some of the more complex changes that you may have to make in your application logic when moving to NPTL are changes related to NPTL's improved support for POSIX signals and signal handling. LinuxThreads implemented generic Unix-style threads, but were limited by various implementation details. NPTL is a POSIX-compliant threading implementation, and therefore handles signals better both between processes and between all threads within those processes. With the NPTL, signals can now be sent from one thread to another, rather than simply on a per-process basis. Signals can also use arguments to transfer information from one thread to another.
Using the NPTL also requires that you make changes to existing code that needs to be able to uniquely identify specific threads. Under LinuxThreads, each thread had a unique process ID (PID). Each thread now shares the PID of its parent process, and the getpid() function therefore returns the same process ID for all threads in a process. With NPTL, a thread's Thread ID must be used to uniquely identify individual threads.
Changes to thread and process IDs also mean that the processes that are traditionally used to spawn processes must now be thread-aware. For example, the exec() functions are now thread-aware, so that a thread inherits the PID of its caller. However, any application that depended on having all threads survive an exec() will need some modification. The parent of a multi-threaded process is notified of a child's termination only when the entire process terminates. Thread-related changes have also been made to the behavior of related fork() calls. For example, functions registered with the pthread_at_fork() function are no longer run when a vfork() occurs.
In addition to changing the internals of thread identification, NPTL does away with the LinuxThreads notion of a manager thread, simplifying the process/thread relationship and eliminating what was essentially administrative overhead under LinuxThreads. This may require application changes if, for example, your application kept track of the number of threads running on its behalf or looked for the manager thread as a signal target.
Finally, using a new threading library means that certain threading functions that were available under LinuxThreads are no longer supported under the NPTL. For example, the pthread_kill_other_threads_np() function is no longer available. This function was used to simulate POSIX-conformant exec() functions. Since the exec() functions themselves are now POSIX conformant, the helper function is not necessary.
For additional information about the design and implementation of the NPTL, a general design and philosophy document is available here.
Conclusion
Changing the kernel that your computer system runs is not necessarily an easy task, but is eminently doable. The white papers in this series have highlighted the issue in configuring the 2.6 kernel, updating device drivers, migrating desktop and custom systems, and updating applications. Certified 2.6-based distributions targeted for embedded use are already available from vendors such as TimeSys, whose 2.6 reference distribution was the first 2.6-based distribution for PPC systems. High-quality commercial software such as TimeSys TimeStorm IDE and TimeStorm Linux Developers Suite (LDS) is designed to help you migrate any Linux kernel, device driver, application, or deployed system to take advantage of the power of the 2.6 kernel and updated packages, threading methodology, and so on.
Linux is a shining example of the power of the Open Source movement as a positive force for change in the software industry. The Linux kernel, the core of any Linux distribution, is constantly evolving to incorporate new technologies and improve performance, scalability, support, and usability. The 2.6 kernel increases the spectrum of systems for which Linux is well-suited, from PDAs, process control systems, and set-top boxes all the way to enterprise servers. The cost, power, and supportability advantages by Linux are more obvious than ever in today's business market and fast-paced technical environment.
Monday, May 14, 2007
Linux kernel threads in Device Drivers
Purpose
This examples shows how to create and stop a kernel thread.
The driver is implemented as a loadable module. In the init_module() routine five kernel threads are created. This kernel threads sleep one second, wake up, print a message and fall asleep again. On unload of the module (cleanup_module), the kernel threads are killed.
The example has been tested with Linux kernel 2.4.2 on Intel (uni processor only) and Alpha platform (COMPAQ Personal Workstation 500au (uni processor), DS20 and ES40 (SMP).
A version for the 2.2 kernel can be found here. Note: depending on the context of the creator of the threads the new threads may inherit properties from the parent you do not want to have. The new version avoids this by having keventd create the threads. The 2.2. kernel do not have a keventd, so this approach is not implementable there.
Functions in example
* start_kthread: creates a new kernel thread. Can be called from any process context but not from interrupt. The functions blocks until the thread started.
* stop_kthread: stop the thread. Can be called from any process context but the thread to be terminated. Cannot be called from interrupt context. The function blocks until the thread terminated.
* init_kthread: sets the environment of the new threads. Is to be called out of the created thread.
* exit_kthread: needs to be called by the thread to be terminated on exit
Creation of new Thread
A new thread is created with kernel_thread(). The thread inherits properties from its parents. To make sure that we do not get any weired properties, we let keventd create the new thread.
The new thread is created with start_kthread(). It uses a semaphore to block until the new thread is running. A down() blocks the start_kthread() routine until the corresponding up() call in init_kthread() is executed.
The new thread must call init_kthread() in order to let the creator continue.
Stop of new Thread
stop_kthread() sets a flag that the thread uses to determine whether do die or not and sends a SIGKILL to the thread. This signal causes the thread to be woken up. On wakeup it will check for the flag and then terminate itself by calling exit_kthread and returning from the thread function. With a semaphore the stop_kthread() function blocks until the thread terminated.
Initialization of new Thread
Within the new created thread, init_kthread() needs to be called. This function sets a signal mask, initialises a wait queue, the termination flag and sets a new name for the thread. With a up() call it notifies the creator that the setup is done.
Exit of new Thread
When the thread receives the notification to terminate itself, is calls the exit_kthread() function. It notifies the stop_kthread() function that it terminated with an up() call.
The new Thread itself
The new thread is implemented in the example_thread() function. It runs an endless loop (for(;;)). In the loop it falls asleep with the interruptible_sleep_on_timeout() function. It comes out of this function either when the timeout expires or when a signal got caught.
The "work" in the thread is to print out a message with printk.
Kernel Versions
The example has been tested on 2.4.2.
Example Device Driver Code
The example consists of four files: kthread.h, kthread.c, thread_drv.c and a Makefile
kthread.h
#ifndef _KTHREAD_H
#define _KTHREAD_H
#include
#include
#include
#include
#include
#include
#include
#include
/* a structure to store all information we need
for our thread */
typedef struct kthread_struct
{
/* private data */
/* Linux task structure of thread */
struct task_struct *thread;
/* Task queue need to launch thread */
struct tq_struct tq;
/* function to be started as thread */
void (*function) (struct kthread_struct *kthread);
/* semaphore needed on start and creation of thread. */
struct semaphore startstop_sem;
/* public data */
/* queue thread is waiting on. Gets initialized by
init_kthread, can be used by thread itself.
*/
wait_queue_head_t queue;
/* flag to tell thread whether to die or not.
When the thread receives a signal, it must check
the value of terminate and call exit_kthread and terminate
if set.
*/
int terminate;
/* additional data to pass to kernel thread */
void *arg;
} kthread_t;
/* prototypes */
/* start new kthread (called by creator) */
void start_kthread(void (*func)(kthread_t *), kthread_t *kthread);
/* stop a running thread (called by "killer") */
void stop_kthread(kthread_t *kthread);
/* setup thread environment (called by new thread) */
void init_kthread(kthread_t *kthread, char *name);
/* cleanup thread environment (called by thread upon receiving termination signal) */
void exit_kthread(kthread_t *kthread);
#endif
kthread.c
#include
#include
#if defined(MODVERSIONS)
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include "kthread.h"
/* private functions */
static void kthread_launcher(void *data)
{
kthread_t *kthread = data;
kernel_thread((int (*)(void *))kthread->function, (void *)kthread, 0);
}
/* public functions */
/* create a new kernel thread. Called by the creator. */
void start_kthread(void (*func)(kthread_t *), kthread_t *kthread)
{
/* initialize the semaphore:
we start with the semaphore locked. The new kernel
thread will setup its stuff and unlock it. This
control flow (the one that creates the thread) blocks
in the down operation below until the thread has reached
the up() operation.
*/
init_MUTEX_LOCKED(&kthread->startstop_sem);
/* store the function to be executed in the data passed to
the launcher */
kthread->function=func;
/* create the new thread my running a task through keventd */
/* initialize the task queue structure */
kthread->tq.sync = 0;
INIT_LIST_HEAD(&kthread->tq.list);
kthread->tq.routine = kthread_launcher;
kthread->tq.data = kthread;
/* and schedule it for execution */
schedule_task(&kthread->tq);
/* wait till it has reached the setup_thread routine */
down(&kthread->startstop_sem);
}
/* stop a kernel thread. Called by the removing instance */
void stop_kthread(kthread_t *kthread)
{
if (kthread->thread == NULL)
{
printk("stop_kthread: killing non existing thread!\n");
return;
}
/* this function needs to be protected with the big
kernel lock (lock_kernel()). The lock must be
grabbed before changing the terminate
flag and released after the down() call. */
lock_kernel();
/* initialize the semaphore. We lock it here, the
leave_thread call of the thread to be terminated
will unlock it. As soon as we see the semaphore
unlocked, we know that the thread has exited.
*/
init_MUTEX_LOCKED(&kthread->startstop_sem);
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
/* set flag to request thread termination */
kthread->terminate = 1;
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
kill_proc(kthread->thread->pid, SIGKILL, 1);
/* block till thread terminated */
down(&kthread->startstop_sem);
/* release the big kernel lock */
unlock_kernel();
/* now we are sure the thread is in zombie state. We
notify keventd to clean the process up.
*/
kill_proc(2, SIGCHLD, 1);
}
/* initialize new created thread. Called by the new thread. */
void init_kthread(kthread_t *kthread, char *name)
{
/* lock the kernel. A new kernel thread starts without
the big kernel lock, regardless of the lock state
of the creator (the lock level is *not* inheritated)
*/
lock_kernel();
/* fill in thread structure */
kthread->thread = current;
/* set signal mask to what we want to respond */
siginitsetinv(¤t->blocked, sigmask(SIGKILL)|sigmask(SIGINT)|sigmask(SIGTERM));
/* initialise wait queue */
init_waitqueue_head(&kthread->queue);
/* initialise termination flag */
kthread->terminate = 0;
/* set name of this process (max 15 chars + 0 !) */
sprintf(current->comm, name);
/* let others run */
unlock_kernel();
/* tell the creator that we are ready and let him continue */
up(&kthread->startstop_sem);
}
/* cleanup of thread. Called by the exiting thread. */
void exit_kthread(kthread_t *kthread)
{
/* we are terminating */
/* lock the kernel, the exit will unlock it */
lock_kernel();
kthread->thread = NULL;
mb();
/* notify the stop_kthread() routine that we are terminating. */
up(&kthread->startstop_sem);
/* the kernel_thread that called clone() does a do_exit here. */
/* there is no race here between execution of the "killer" and real termination
of the thread (race window between up and do_exit), since both the
thread and the "killer" function are running with the kernel lock held.
The kernel lock will be freed after the thread exited, so the code
is really not executed anymore as soon as the unload functions gets
the kernel lock back.
The init process may not have made the cleanup of the process here,
but the cleanup can be done safely with the module unloaded.
*/
}
thread_drv.c
#include
#include
#include
#if defined(MODVERSIONS)
#include
#endif
#include
#include
#include
#include
#include "kthread.h"
#define NTHREADS 5
/* the variable that contains the thread data */
kthread_t example[NTHREADS];
/* prototype for the example thread */
static void example_thread(kthread_t *kthread);
/* load the module */
int init_module(void)
{
int i;
/* create new kernel threads */
for (i=0; i
return(0);
}
/* remove the module */
void cleanup_module(void)
{
int i;
/* terminate the kernel threads */
for (i=0; i
return;
}
/* this is the thread function that we are executing */
static void example_thread(kthread_t *kthread)
{
/* setup the thread environment */
init_kthread(kthread, "example thread");
printk("hi, here is the kernel thread\n");
/* an endless loop in which we are doing our work */
for(;;)
{
/* fall asleep for one second */
interruptible_sleep_on_timeout(&kthread->queue, HZ);
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
/* here we are back from sleep, either due to the timeout
(one second), or because we caught a signal.
*/
if (kthread->terminate)
{
/* we received a request to terminate ourself */
break;
}
/* this is normal work to do */
printk("example thread: thread woke up\n");
}
/* here we go only in case of termination of the thread */
/* cleanup the thread, leave */
exit_kthread(kthread);
/* returning from the thread here calls the exit functions */
}
Makefile
# set to your kernel tree
KERNEL = /usr/src/linux
# get the Linux architecture. Needed to find proper include file for CFLAGS
ARCH=$(shell uname -m | sed -e s/i.86/i386/ -e s/sun4u/sparc64/ -e s/arm.*/arm/ -e s/sa110/arm/)
# set default flags to compile module
CFLAGS = -D__KERNEL__ -DMODULE -I$(KERNEL)/include
CFLAGS+= -Wall -Wstrict-prototypes -O2 -fomit-frame-pointer -fno-strict-aliasing
all: thread_mod.o
# get configuration of kernel
include $(KERNEL)/.config
# modify CFLAGS with architecture specific flags
include $(KERNEL)/arch/${ARCH}/Makefile
# enable the module versions, if configured in kernel source tree
ifdef CONFIG_MODVERSIONS
CFLAGS+= -DMODVERSIONS -include $(KERNEL)/include/linux/modversions.h
endif
# enable SMP, if configured in kernel source tree
ifdef CONFIG_SMP
CFLAGS+= -D__SMP__
endif
# note: we are compiling the driver object file and then linking
# we link it into the module. With just one object file as in
# this example this is not needed. We can just load the object
# file produced by gcc
# link the thread driver module
thread_mod.o: thread_drv.o kthread.o
ld -r -o thread_mod.o thread_drv.o kthread.o
# compile the kthread object file
kthread.o: kthread.c kthread.h
gcc $(CFLAGS) -c kthread.c
# compile the thread driver
thread_drv.o: thread_drv.c kthread.h
gcc $(CFLAGS) -c thread_drv.c
clean:
rm -f *.o
Bugs
The code assumes that keventd is running with PID 2.
This examples shows how to create and stop a kernel thread.
The driver is implemented as a loadable module. In the init_module() routine five kernel threads are created. This kernel threads sleep one second, wake up, print a message and fall asleep again. On unload of the module (cleanup_module), the kernel threads are killed.
The example has been tested with Linux kernel 2.4.2 on Intel (uni processor only) and Alpha platform (COMPAQ Personal Workstation 500au (uni processor), DS20 and ES40 (SMP).
A version for the 2.2 kernel can be found here. Note: depending on the context of the creator of the threads the new threads may inherit properties from the parent you do not want to have. The new version avoids this by having keventd create the threads. The 2.2. kernel do not have a keventd, so this approach is not implementable there.
Functions in example
* start_kthread: creates a new kernel thread. Can be called from any process context but not from interrupt. The functions blocks until the thread started.
* stop_kthread: stop the thread. Can be called from any process context but the thread to be terminated. Cannot be called from interrupt context. The function blocks until the thread terminated.
* init_kthread: sets the environment of the new threads. Is to be called out of the created thread.
* exit_kthread: needs to be called by the thread to be terminated on exit
Creation of new Thread
A new thread is created with kernel_thread(). The thread inherits properties from its parents. To make sure that we do not get any weired properties, we let keventd create the new thread.
The new thread is created with start_kthread(). It uses a semaphore to block until the new thread is running. A down() blocks the start_kthread() routine until the corresponding up() call in init_kthread() is executed.
The new thread must call init_kthread() in order to let the creator continue.
Stop of new Thread
stop_kthread() sets a flag that the thread uses to determine whether do die or not and sends a SIGKILL to the thread. This signal causes the thread to be woken up. On wakeup it will check for the flag and then terminate itself by calling exit_kthread and returning from the thread function. With a semaphore the stop_kthread() function blocks until the thread terminated.
Initialization of new Thread
Within the new created thread, init_kthread() needs to be called. This function sets a signal mask, initialises a wait queue, the termination flag and sets a new name for the thread. With a up() call it notifies the creator that the setup is done.
Exit of new Thread
When the thread receives the notification to terminate itself, is calls the exit_kthread() function. It notifies the stop_kthread() function that it terminated with an up() call.
The new Thread itself
The new thread is implemented in the example_thread() function. It runs an endless loop (for(;;)). In the loop it falls asleep with the interruptible_sleep_on_timeout() function. It comes out of this function either when the timeout expires or when a signal got caught.
The "work" in the thread is to print out a message with printk.
Kernel Versions
The example has been tested on 2.4.2.
Example Device Driver Code
The example consists of four files: kthread.h, kthread.c, thread_drv.c and a Makefile
kthread.h
#ifndef _KTHREAD_H
#define _KTHREAD_H
#include
#include
#include
#include
#include
#include
#include
#include
/* a structure to store all information we need
for our thread */
typedef struct kthread_struct
{
/* private data */
/* Linux task structure of thread */
struct task_struct *thread;
/* Task queue need to launch thread */
struct tq_struct tq;
/* function to be started as thread */
void (*function) (struct kthread_struct *kthread);
/* semaphore needed on start and creation of thread. */
struct semaphore startstop_sem;
/* public data */
/* queue thread is waiting on. Gets initialized by
init_kthread, can be used by thread itself.
*/
wait_queue_head_t queue;
/* flag to tell thread whether to die or not.
When the thread receives a signal, it must check
the value of terminate and call exit_kthread and terminate
if set.
*/
int terminate;
/* additional data to pass to kernel thread */
void *arg;
} kthread_t;
/* prototypes */
/* start new kthread (called by creator) */
void start_kthread(void (*func)(kthread_t *), kthread_t *kthread);
/* stop a running thread (called by "killer") */
void stop_kthread(kthread_t *kthread);
/* setup thread environment (called by new thread) */
void init_kthread(kthread_t *kthread, char *name);
/* cleanup thread environment (called by thread upon receiving termination signal) */
void exit_kthread(kthread_t *kthread);
#endif
kthread.c
#include
#include
#if defined(MODVERSIONS)
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include "kthread.h"
/* private functions */
static void kthread_launcher(void *data)
{
kthread_t *kthread = data;
kernel_thread((int (*)(void *))kthread->function, (void *)kthread, 0);
}
/* public functions */
/* create a new kernel thread. Called by the creator. */
void start_kthread(void (*func)(kthread_t *), kthread_t *kthread)
{
/* initialize the semaphore:
we start with the semaphore locked. The new kernel
thread will setup its stuff and unlock it. This
control flow (the one that creates the thread) blocks
in the down operation below until the thread has reached
the up() operation.
*/
init_MUTEX_LOCKED(&kthread->startstop_sem);
/* store the function to be executed in the data passed to
the launcher */
kthread->function=func;
/* create the new thread my running a task through keventd */
/* initialize the task queue structure */
kthread->tq.sync = 0;
INIT_LIST_HEAD(&kthread->tq.list);
kthread->tq.routine = kthread_launcher;
kthread->tq.data = kthread;
/* and schedule it for execution */
schedule_task(&kthread->tq);
/* wait till it has reached the setup_thread routine */
down(&kthread->startstop_sem);
}
/* stop a kernel thread. Called by the removing instance */
void stop_kthread(kthread_t *kthread)
{
if (kthread->thread == NULL)
{
printk("stop_kthread: killing non existing thread!\n");
return;
}
/* this function needs to be protected with the big
kernel lock (lock_kernel()). The lock must be
grabbed before changing the terminate
flag and released after the down() call. */
lock_kernel();
/* initialize the semaphore. We lock it here, the
leave_thread call of the thread to be terminated
will unlock it. As soon as we see the semaphore
unlocked, we know that the thread has exited.
*/
init_MUTEX_LOCKED(&kthread->startstop_sem);
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
/* set flag to request thread termination */
kthread->terminate = 1;
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
kill_proc(kthread->thread->pid, SIGKILL, 1);
/* block till thread terminated */
down(&kthread->startstop_sem);
/* release the big kernel lock */
unlock_kernel();
/* now we are sure the thread is in zombie state. We
notify keventd to clean the process up.
*/
kill_proc(2, SIGCHLD, 1);
}
/* initialize new created thread. Called by the new thread. */
void init_kthread(kthread_t *kthread, char *name)
{
/* lock the kernel. A new kernel thread starts without
the big kernel lock, regardless of the lock state
of the creator (the lock level is *not* inheritated)
*/
lock_kernel();
/* fill in thread structure */
kthread->thread = current;
/* set signal mask to what we want to respond */
siginitsetinv(¤t->blocked, sigmask(SIGKILL)|sigmask(SIGINT)|sigmask(SIGTERM));
/* initialise wait queue */
init_waitqueue_head(&kthread->queue);
/* initialise termination flag */
kthread->terminate = 0;
/* set name of this process (max 15 chars + 0 !) */
sprintf(current->comm, name);
/* let others run */
unlock_kernel();
/* tell the creator that we are ready and let him continue */
up(&kthread->startstop_sem);
}
/* cleanup of thread. Called by the exiting thread. */
void exit_kthread(kthread_t *kthread)
{
/* we are terminating */
/* lock the kernel, the exit will unlock it */
lock_kernel();
kthread->thread = NULL;
mb();
/* notify the stop_kthread() routine that we are terminating. */
up(&kthread->startstop_sem);
/* the kernel_thread that called clone() does a do_exit here. */
/* there is no race here between execution of the "killer" and real termination
of the thread (race window between up and do_exit), since both the
thread and the "killer" function are running with the kernel lock held.
The kernel lock will be freed after the thread exited, so the code
is really not executed anymore as soon as the unload functions gets
the kernel lock back.
The init process may not have made the cleanup of the process here,
but the cleanup can be done safely with the module unloaded.
*/
}
thread_drv.c
#include
#include
#include
#if defined(MODVERSIONS)
#include
#endif
#include
#include
#include
#include
#include "kthread.h"
#define NTHREADS 5
/* the variable that contains the thread data */
kthread_t example[NTHREADS];
/* prototype for the example thread */
static void example_thread(kthread_t *kthread);
/* load the module */
int init_module(void)
{
int i;
/* create new kernel threads */
for (i=0; i
return(0);
}
/* remove the module */
void cleanup_module(void)
{
int i;
/* terminate the kernel threads */
for (i=0; i
return;
}
/* this is the thread function that we are executing */
static void example_thread(kthread_t *kthread)
{
/* setup the thread environment */
init_kthread(kthread, "example thread");
printk("hi, here is the kernel thread\n");
/* an endless loop in which we are doing our work */
for(;;)
{
/* fall asleep for one second */
interruptible_sleep_on_timeout(&kthread->queue, HZ);
/* We need to do a memory barrier here to be sure that
the flags are visible on all CPUs.
*/
mb();
/* here we are back from sleep, either due to the timeout
(one second), or because we caught a signal.
*/
if (kthread->terminate)
{
/* we received a request to terminate ourself */
break;
}
/* this is normal work to do */
printk("example thread: thread woke up\n");
}
/* here we go only in case of termination of the thread */
/* cleanup the thread, leave */
exit_kthread(kthread);
/* returning from the thread here calls the exit functions */
}
Makefile
# set to your kernel tree
KERNEL = /usr/src/linux
# get the Linux architecture. Needed to find proper include file for CFLAGS
ARCH=$(shell uname -m | sed -e s/i.86/i386/ -e s/sun4u/sparc64/ -e s/arm.*/arm/ -e s/sa110/arm/)
# set default flags to compile module
CFLAGS = -D__KERNEL__ -DMODULE -I$(KERNEL)/include
CFLAGS+= -Wall -Wstrict-prototypes -O2 -fomit-frame-pointer -fno-strict-aliasing
all: thread_mod.o
# get configuration of kernel
include $(KERNEL)/.config
# modify CFLAGS with architecture specific flags
include $(KERNEL)/arch/${ARCH}/Makefile
# enable the module versions, if configured in kernel source tree
ifdef CONFIG_MODVERSIONS
CFLAGS+= -DMODVERSIONS -include $(KERNEL)/include/linux/modversions.h
endif
# enable SMP, if configured in kernel source tree
ifdef CONFIG_SMP
CFLAGS+= -D__SMP__
endif
# note: we are compiling the driver object file and then linking
# we link it into the module. With just one object file as in
# this example this is not needed. We can just load the object
# file produced by gcc
# link the thread driver module
thread_mod.o: thread_drv.o kthread.o
ld -r -o thread_mod.o thread_drv.o kthread.o
# compile the kthread object file
kthread.o: kthread.c kthread.h
gcc $(CFLAGS) -c kthread.c
# compile the thread driver
thread_drv.o: thread_drv.c kthread.h
gcc $(CFLAGS) -c thread_drv.c
clean:
rm -f *.o
Bugs
The code assumes that keventd is running with PID 2.
Subscribe to:
Posts (Atom)