| Linux is a multitasking system. This means that several application processes can be active, and several applications can be used, simultaneously. In multiprocessor systems, which have been supported since kernel Version 2.0, even several applications or their processes can be processed in parallel. However, a process is not the only form of activity you can execute in the Linux kernel. 2.2.1 Processes and System Calls Processes are normally activities that are started to run a specific application, and they are terminated once the application is through. Creating, controlling, and destroying of processes are tasks handled by the kernel of an operating system. Processes operate exclusively in the user address space (i.e., in unprotected mode) of a processor, where they can access only the memory section allocated to them. An attempt to access memory sections of other processes or the kernel address space leads to an exception, which has to be dealt with by the kernel. However, when a process wants to access devices or use a functionality of the operating-system kernel, it has to use a system call to do this. A system call causes the processor to change to the protected mode, and access to the kernel address space is a function of the system call. All devices and memory sections can be accessed in protected mode, but only with methods of the kernel. The work of processes and system calls can be interrupted by other activities. In such a case, their current state (contents of CPU registers, MMU registers, etc.) is saved; then it is restored when the interrupted process or system call resumes its work. Processes and system calls can be stopped voluntarily or involuntarily. In the first case, they cede processing voluntarily for example, when they wait for a system resource (external device, semaphore, etc.) and go to sleep until that resource becomes available. Involuntary cession of processing is caused by interrupts, which tell the kernel that an important action has taken place, one that the kernel should be dealing with. This could be a notification about availability of a previously busy resource. In addition to normal processes and to processes within a system call, we distinguish between further forms of activity in the Linux kernel. These forms of activity are of decisive importance for the Linux network architecture, because the network functionality is handled in the kernel. We will explain the following forms of activity in more detail in the next sections, when we will be discussing mainly their tasks within the Linux network architecture: When thinking of the different forms of activity in the kernel (except processes in the system call and kernel threads), an important point will be the parallel execution of the respective form of activity. On the one hand, this concerns the question of whether the instance of a form of activity can be executed concurrently on several processors; on the other hand, of whether two different instances of one form of activity can be executed concurrently on several processors. Table 2-2 shows an overview of these possibilities. Table 2-2. Concurrent execution of same activities on several processors.| | Same Activity | Different Activities |
|---|
HW IRQ | ?/P> | • | Soft IRQ | • | • | Tasklet | ?/P> | • | Bottom half | ?/P> | ?/P> |
Another interesting thing about the individual forms of activity is to know by what other forms of activity they can be interrupted; Table 2-3 gives an overview. This information is important mainly for protection from undesired side effects caused by concurrent or overlapping operations of two activities on a jointly used data structure. This problem and possible solutions are discussed in detail in Section 2.3. That section will introduce locking mechanisms that, though offering protection against undesired side effects, can reduce a system's performance when used too cautiously. For this reason, it is important to know when which locking mechanisms are required. Note that the possible parallelism and interruptability of different forms of activity play an important role. Table 2-3. Interruption of activities by other forms of kernel activities.| | HW-IRQ | Soft-IRQ | Tasklet | Bottom Half |
|---|
HW IRQ | +/?sup>[1] | ?/P> | ?/P> | ?/P> | Soft IRQ | + | ?/P> | ?/P> | ?/P> | Tasklet | + | ?/P> | ?/P> | ?/P> | Bottom half | + | ?/P> | ?/P> | ?/P> | System call | + | + | + | + | Process | + | + | + | + |
[1] Only slow interrupts can be interrupted by other interrupts, as we will see in Section 2.2.2.
2.2.2 Hardware Interrupts Peripherals use hardware interrupts (often abbreviated as HW IRQs) to inform an operating system about important events (e.g., that the mouse has been moved, a key has been pressed, or a packet has arrived in the network adapter). Hardware interrupts interrupt the current activity in one of the processors and execute the pertinent interrupt-handling routine. The handling routine for a specific interrupt can be registered at runtime by using the function request_irq(). Details about the registration and management of interrupts are described in [RuCo01]. free_irq() is used to release the handling routine of an interrupt, so that it is no longer executed. We distinguish between two types of interrupts in the Linux kernel: Fast interrupts are characterized by the fact that they have a very short interrupt-handling routine and so interrupt the current activity only very briefly. One characteristic of fast interrupts is that all other interrupts in the local CPU are locked while it is executed, so that the interrupt-handling routine cannot be interrupted. Fast interrupts are designated by the flag SA_INTERRUPT when they are registered with request_irq(). Slow interrupts can be interrupted by other interrupts during their execution. They normally have a much longer-interrupt handling routing than fast interrupts and so would claim the processor for too long. This is the reason why only the repeated execution of that interrupt is stopped when a slow interrupt is executed.
Interrupts can generally stop all other activities when they are executed. (See Table 2-3.) At the same time, various interrupts in several CPUs can be handled concurrently, but the interrupt-handling routine of a specific interrupt can be executed only in one CPU at a time. You can call the function in_irq() (include/asm/hardirq.h) to check whether the current activity is an interrupt-handling routine (see details in [Russ00b]). Top Halfs and Bottom Halfs Interrupt-handling routines should be executed as soon as possible after the interrupt was triggered and interrupt the current activity only briefly. But not every task can be executed by few instructions. For example, handling of a packet arrived in a network adapter requires several thousand ticks, until the packet can be passed on to the relevant process in the user address space. Though it is triggered by an interrupt, this task cannot be done in an interrupt-handling routine. To keep interrupt handling as short as possible, such time-consuming tasks are divided into two parts: The so-called top half runs only the most important tasks after a triggered interrupt. The top half corresponds to the interrupt-handling routine. As we will see in Chapter 6, for example, the interrupt-handling routine of a network adapter might just copy the arrived packet to the kernel, where it will be buffered in a queue pending detailed handling by the corresponding protocol instances. The bottom half runs all operations that are not time-critical and which could not be executed within the interrupt-handling routine for time reasons. The bottom half is scheduled for execution while the top half is running, and, as soon as the scheduler is called again upon completion of the interrupt, it will most likely run the bottom half (depending on the bottom half's type).
For example, if a packet arrives, then the tasks of the bottom half are run by the software interrupt NET_RX_SOFTIRQ. (See Chapter 6.) The following sections introduce three possible activities that can be used as the bottom half in the interrupt-handling process. 2.2.3 Software Interrupts Software interrupts (or soft IRQs for short) are actually a form of activity that can be scheduled for later execution rather than real interrupts. Software and hardware interrupts differ mainly in that a hardware interrupt actively interrupts another form of activity: Triggering the interrupt causes the (immediate) interruption of the running activity (but, of course, only if the triggering of interrupts is currently allowed). In contrast, a software interrupt is scheduled for execution by an activity of the kernel and has to wait until it is called by the scheduler. Software interrupts scheduled for execution are started by the function do_softirq() (kernel/softirq.c). This means that the running activity is not interrupted when a soft IRQ is activated by __cpu_raise_softirq(). The corresponding handling routine is triggered when do_softirq() is called. This occurs currently only when a system call (in schedule()) or a hardware interrupt (in do_IRQ()) terminates. A maximum of 32 software interrupts can be defined in the Linux kernel. Note that only four were defined in the Versions 2.4.x. This includes the soft IRQs NET_RX_SOFTIRQ and NET_TX_SOFTIRQ, which have ensured efficient protocol handling since kernel Version 2.4, and the soft IRQ TASKLET_SOFTIRQ, which is used to implement the concept of tasklets, further described later in this chapter. Software interrupts differ clearly from the tasklet and bottom half forms of activity, as we have seen in Tables 2-2 and 2-3. The most important properties of software interrupts are the following: A software interrupt can run concurrently in several processors. This means that the handling routine has to be implemented reentrantly (e.g., with net_rx_action). If critical sections exist in a software interrupt (e.g., any global variable it accesses), then these have to be protected by locks. A software interrupt cannot interrupt itself while running on a processor. A software interrupt can be interrupted during its handling on a processor only by a hardware interrupt.
Calling in_softirq() (include/asm/softirq.h) causes a function to check immediately on whether it is currently in a software interrupt; see details in [Russ00b]. 2.2.4 Tasklets Tasklets are a combination of parallel executable (but lock-intensive) software interrupts and the old bottom halfs,[1] where we can talk neither of parallelism nor of performance. Tasklets were introduced to replace the old bottom halfs. [1] In this connection, we have to differentiate between the general concept of a bottom half that can be implemented by a tasklet (a soft IRQ) and a bottom half in the Linux kernel. In contrast, the form of activity of a bottom half is Linux-specific and denoted by sans-serif font in this text.
Tasklets have the following properties: The function tasklet_schedule(&tasklet_struct) can be used to schedule a tasklet for execution. A tasklet is run only once, even if it was scheduled for execution several times. A tasklet can run on one processor only at any given time. Different tasklets can run on several processors concurrently.
The macro DECLARE_TASKLET(name, func, data) can be used to define a new tasklet, where name denotes a name for the tasklet_struct data structure and func denotes the tasklet's handling routine. When the tasklet is to run, then the pointer data, pointing to private data, if applicable, are passed to the function func(). Tasklet_schedule() is used to schedule a tasklet for execution; tasklet_disable() can be used to stop a tasklet from running, even when it is scheduled for execution. It remains scheduled for execution or can be rescheduled. Tasklet_enable() is used to reactivate a deactivated tasklet. However, if that tasklet was not scheduled for execution, it will not run when you activate it. The following example shows how easy it is to define and activate a new tasklet: #include <linux/interrupt.h> /* Handling routine of new tasklet */ void test_func(unsigned long); /* Data of new tasklet */ char test_data[] = "Hello, I am a test tasklet"; /* Definition of tasklet_struct structure of tasklet */ DECLARE_TASKLET (test_tasklet, test_func, (unsigned long) &test_data); void test_func(unsigned long data) { /*Do here what you think you have to do, e.g.:*/ printk(KERN_DEBUG "%s\n", (char *) data); } . . . /* Use an activity to activate the tasklet */ tasklet_schedule(&test_tasklet);
2.2.5 Bottom Halfs Bottom halfs (BHs) had been the main form of activity in the kernel in early kernels. For example, NET_BH was responsible for handling of network protocols and sending of packets. There can be a maximum of 32 BHs, which are scheduled for execution by the mark_bh() function. BHs are the form of activity with the smallest parallelism in the kernel, as mentioned in previous sections. The following property shows the major drawback of BHs: Because BHs are inflexible and because they are to be replaced by tasklets or software interrupts in future Linux kernel versions, we will not discuss them further here. Information on BHs is found in the literature (e.g., [RuCo01], [BBDK+01] or [BoCe00]). | 