O'Reilly logo

Linux Device Drivers, Second Edition by Alessandro Rubini, Jonathan Corbet

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Task Queues

One feature many drivers need is the ability to schedule execution of some tasks at a later time without resorting to interrupts. Linux offers three different interfaces for this purpose: task queues, tasklets (as of kernel 2.3.43), and kernel timers. Task queues and tasklets provide a flexible utility for scheduling execution at a later time, with various meanings for “later”; they are most useful when writing interrupt handlers, and we’ll see them again in Section 9.5, in Chapter 9. Kernel timers are used to schedule a task to run at a specific time in the future and are dealt with in Section 6.5, later in this chapter.

A typical situation in which you might use task queues or tasklets is to manage hardware that cannot generate interrupts but still allows blocking read. You need to poll the device, while taking care not to burden the CPU with unnecessary operations. Waking the reading process at fixed time intervals (for example, using current->timeout) isn’t a suitable approach, because each poll would require two context switches (one to run the polling code in the reading process, and one to return to a process that has real work to do), and often a suitable polling mechanism can be implemented only outside of a process’s context.

A similar problem is giving timely input to a simple hardware device. For example, you might need to feed steps to a stepper motor that is directly connected to the parallel port—the motor needs to be moved by single steps on a timely basis. In this case, the controlling process talks to your device driver to dispatch a movement, but the actual movement should be performed step by step at regular intervals after returning from write.

The preferred way to perform such floating operations quickly is to register a task for later execution. The kernel supports task queues, where tasks accumulate to be “consumed” when the queue is run. You can declare your own task queue and trigger it at will, or you can register your tasks in predefined queues, which are run (triggered) by the kernel itself.

This section first describes task queues, then introduces predefined task queues, which provide a good start for some interesting tests (and hang the computer if something goes wrong), and finally introduces how to run your own task queues. Following that, we look at the new tasklet interface, which supersedes task queues in many situations in the 2.4 kernel.

The Nature of Task Queues

A task queue is a list of tasks, each task being represented by a function pointer and an argument. When a task is run, it receives a single void * argument and returns void. The pointer argument can be used to pass along a data structure to the routine, or it can be ignored. The queue itself is a list of structures (the tasks) that are owned by the kernel module declaring and queueing them. The module is completely responsible for allocating and deallocating the structures, and static structures are commonly used for this purpose.

A queue element is described by the following structure, copied directly from <linux/tqueue.h>:

struct tq_struct {
    struct tq_struct *next;         /* linked list of active bh's */
    int sync;                       /* must be initialized to zero */
    void (*routine)(void *);        /* function to call */
    void *data;                     /* argument to function */
};

The “bh” in the first comment means bottom half. A bottom half is “half of an interrupt handler”; we’ll discuss this topic thoroughly when we deal with interrupts in Section 9.5, in Chapter 9. For now, suffice it to say that a bottom half is a mechanism provided by a device driver to handle asynchronous tasks which, usually, are too large to be done while handling a hardware interrupt. This chapter should make sense without an understanding of bottom halves, but we will, by necessity, refer to them occasionally.

The most important fields in the data structure just shown are routine and data. To queue a task for later execution, you need to set both these fields before queueing the structure, while next and sync should be cleared. The sync flag in the structure is used by the kernel to prevent queueing the same task more than once, because this would corrupt the next pointer. Once the task has been queued, the structure is considered “owned” by the kernel and shouldn’t be modified until the task is run.

The other data structure involved in task queues is task_queue, which is currently just a pointer to struct tq_struct; the decision to typedef this pointer to another symbol permits the extension of task_queue in the future, should the need arise. task_queue pointers should be initialized to NULL before use.

The following list summarizes the operations that can be performed on task queues and struct tq_structs.

DECLARE_TASK_QUEUE(name);

This macro declares a task queue with the given name, and initializes it to the empty state.

int queue_task(struct tq_struct *task, task_queue *list);

As its name suggests, this function queues a task. The return value is 0 if the task was already present on the given queue, nonzero otherwise.

void run_task_queue(task_queue *list);

This function is used to consume a queue of accumulated tasks. You won’t need to call it yourself unless you declare and maintain your own queue.

Before getting into the details of using task queues, we need to pause for a moment to look at how they work inside the kernel.

How Task Queues Are Run

A task queue, as we have already seen, is in practice a linked list of functions to call. When run_task_queue is asked to run a given queue, each entry in the list is executed. When you are writing functions that work with task queues, you have to keep in mind when the kernel will call run_task_queue; the exact context imposes some constraints on what you can do. You should also not make any assumptions regarding the order in which enqueued tasks are run; each of them must do its task independently of the other ones.

And when are task queues run? If you are using one of the predefined task queues discussed in the next section, the answer is “when the kernel gets around to it.” Different queues are run at different times, but they are always run when the kernel has no other pressing work to do.

Most important, they almost certainly are not run when the process that queued the task is executing. They are, instead, run asynchronously. Until now, everything we have done in our sample drivers has run in the context of a process executing system calls. When a task queue runs, however, that process could be asleep, executing on a different processor, or could conceivably have exited altogether.

This asynchronous execution resembles what happens when a hardware interrupt happens (which is discussed in detail in Chapter 9). In fact, task queues are often run as the result of a “software interrupt.” When running in interrupt mode (or interrupt time) in this way, your code is subject to a number of constraints. We will introduce these constraints now; they will be seen again in several places in this book. Repetition is called for in this case; the rules for interrupt mode must be followed or the system will find itself in deep trouble.

A number of actions require the context of a process in order to be executed. When you are outside of process context (i.e., in interrupt mode), you must observe the following rules:

  • No access to user space is allowed. Because there is no process context, there is no path to the user space associated with any particular process.

  • The current pointer is not valid in interrupt mode, and cannot be used.

  • No sleeping or scheduling may be performed. Interrupt-mode code may not call schedule or sleep_on; it also may not call any other function that may sleep. For example, calling kmalloc(..., GFP_KERNEL) is against the rules. Semaphores also may not be used since they can sleep.

Kernel code can tell if it is running in interrupt mode by calling the function in_interrupt(), which takes no parameters and returns nonzero if the processor is running in interrupt time.

One other feature of the current implementation of task queues is that a task can requeue itself in the same queue from which it was run. For instance, a task being run from the timer tick can reschedule itself to be run on the next tick by calling queue_task to put itself on the queue again. Rescheduling is possible because the head of the queue is replaced with a NULL pointer before consuming queued tasks; as a result, a new queue is built once the old one starts executing.

Although rescheduling the same task over and over might appear to be a pointless operation, it is sometimes useful. For example, consider a driver that moves a pair of stepper motors one step at a time by rescheduling itself on the timer queue until the target has been reached. Another example is the jiq module, where the printing function reschedules itself to produce its output—the result is several iterations through the timer queue.

Predefined Task Queues

The easiest way to perform deferred execution is to use the queues that are already maintained by the kernel. There are a few of these queues, but your driver can use only three of them, described in the following list. The queues are declared in <linux/tqueue.h>, which you should include in your source.

The scheduler queue

The scheduler queue is unique among the predefined task queues in that it runs in process context, implying that the tasks it runs have a bit more freedom in what they can do. In Linux 2.4, this queue runs out of a dedicated kernel thread called keventd and is accessed via a function called schedule_task. In older versions of the kernel, keventd was not used, and the queue (tq_scheduler) was manipulated directly.

tq_timer

This queue is run by the timer tick. Because the tick (the function do_timer) runs at interrupt time, any task within this queue runs at interrupt time as well.

tq_immediate

The immediate queue is run as soon as possible, either on return from a system call or when the scheduler is run, whichever comes first. The queue is consumed at interrupt time.

Other predefined task queues exist as well, but they are not generally of interest to driver writers.

The timeline of a driver using a task queue is represented in Figure 6-1. The figure shows a driver that queues a function in tq_immediate from an interrupt handler.

Timeline of task-queue usage

Figure 6-1. Timeline of task-queue usage

How the examples work

Examples of deferred computation are available in the jiq (“Just In Queue”) module, from which the source in this section has been extracted. This module creates /proc files that can be read using dd or other tools; this is similar to jit.

The process reading a jiq file is put to sleep until the buffer is full.[28] This sleeping is handled with a simple wait queue, declared as

DECLARE_WAIT_QUEUE_HEAD (jiq_wait);

The buffer is filled by successive runs of a task queue. Each pass through the queue appends a text string to the buffer being filled; each string reports the current time (in jiffies), the process that is current during this pass, and the return value of in_interrupt.

The code for filling the buffer is confined to the jiq_print_tq function, which executes at each run through the queue being used. The printing function is not interesting and is not worth showing here; instead, let’s look at the initialization of the task to be inserted in a queue:

struct tq_struct jiq_task; /* global: initialized to zero */

    /* these lines are in jiq_init() */
    jiq_task.routine = jiq_print_tq;
    jiq_task.data = (void *)&jiq_data;

There’s no need to clear the sync and next fields of jiq_task because static variables are initialized to 0 by the compiler.

The scheduler queue

The scheduler queue is, in some ways, the easiest to use. Because tasks executed from this queue do not run in interrupt mode, they can do more things; in particular, they can sleep. Many parts of the kernel use this queue to accomplish a wide variety of tasks.

As of kernel 2.4.0-test11, the actual task queue implementing the scheduler queue is hidden from the rest of the kernel. Rather than use queue_task directly, code using this queue must call schedule_task to put a task on the queue:

 int schedule_task(struct tq_struct *task);

task, of course, is the task to be scheduled. The return value is directly from queue_task: nonzero if the task was not already on the queue.

Again, as of 2.4.0-test11, the kernel runs a special process, called keventd, whose sole job is running tasks from the scheduler queue. keventd provides a predictable process context for the tasks it runs (unlike the previous implementation, which would run tasks under an essentially random process’s context).

There are a couple of implications to the keventd implementation that are worth keeping in mind. The first is that tasks in this queue can sleep, and some kernel code takes advantage of that freedom. Well-behaved code, however, should take care to sleep only for very short periods of time, since no other tasks will be run from the scheduler queue while keventd is sleeping. It is also a good idea to keep in mind that your task shares the scheduler queue with others, which can also sleep. In normal situations, tasks placed in the scheduler queue will run very quickly (perhaps even before schedule_task returns). If some other task sleeps, though, the time that elapses before your tasks execute could be significant. Tasks that absolutely have to run within a narrow time window should use one of the other queues.

/proc/jiqsched is a sample file that uses the scheduler queue. The read function for the file dispatches everything to the task queue in the following way:

int jiq_read_sched(char *buf, char **start, off_t offset,
                   int len, int *eof, void *data)
{

    jiq_data.len = 0;               /* nothing printed, yet */
    jiq_data.buf = buf;             /* print in this place */
    jiq_data.jiffies = jiffies;     /* initial time */

    /* jiq_print will queue_task() again in jiq_data.queue */
    jiq_data.queue = SCHEDULER_QUEUE;

    schedule_task(&jiq_task);             /* ready to run */
    interruptible_sleep_on(&jiq_wait);    /* sleep till completion */

    *eof = 1;
    return jiq_data.len;
}

Reading /proc/jiqsched produces output like the following:

 time  delta interrupt  pid cpu command
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd
601687   0        0       2   1 keventd

In this output, the time field is the value of jiffies when the task is run, delta is the change in jiffies since the last time the task ran, interrupt is the output of the in_interrupt function, pid is the ID of the running process, cpu is the number of the CPU being used (always 0 on uniprocessor systems), and command is the command being run by the current process.

In this case, we see that the task is always running under the keventd process. It also runs very quickly—a task that resubmits itself to the scheduler queue can run hundreds or thousands of times within a single timer tick. Even on a very heavily loaded system, the latency in the scheduler queue is quite small.

The timer queue

The timer queue is different from the scheduler queue in that the queue (tq_timer) is directly available. Also, of course, tasks run from the timer queue are run in interrupt mode. Additionally, you’re guaranteed that the queue will run at the next clock tick, thus eliminating latency caused by system load.

The sample code implements /proc/jiqtimer with the timer queue. For this queue, it must use queue_task to get things going:

int jiq_read_timer(char *buf, char **start, off_t offset,
                   int len, int *eof, void *data)
{

    jiq_data.len = 0;            /* nothing printed, yet */
    jiq_data.buf = buf;          /* print in this place */
    jiq_data.jiffies = jiffies;  /* initial time */
    jiq_data.queue = &tq_timer;  /* reregister yourself here */

    queue_task(&jiq_task, &tq_timer);     /* ready to run */
    interruptible_sleep_on(&jiq_wait);    /* sleep till completion */

    *eof = 1;
    return jiq_data.len;
}

The following is what head /proc/jiqtimer returned on a system that was compiling a new kernel:

    time  delta interrupt  pid cpu command
 45084845   1        1    8783   0 cc1
 45084846   1        1    8783   0 cc1
 45084847   1        1    8783   0 cc1
 45084848   1        1    8783   0 cc1
 45084849   1        1    8784   0 as
 45084850   1        1    8758   1 cc1
 45084851   1        1    8789   0 cpp
 45084852   1        1    8758   1 cc1
 45084853   1        1    8758   1 cc1
 45084854   1        1    8758   1 cc1
 45084855   1        1    8758   1 cc1

Note, this time, that exactly one timer tick goes by between each invocation of the task, and that an arbitrary process is running.

The immediate queue

The last predefined queue that can be used by modularized code is the immediate queue. This queue is run via the bottom-half mechanism, which means that one additional step is required to use it. Bottom halves are run only when the kernel has been told that a run is necessary; this is accomplished by “marking” the bottom half. In the case of tq_immediate, the necessary call is mark_bh(IMMEDIATE_BH). Be sure to call mark_bh after the task has been queued; otherwise, the kernel may run the task queue before your task has been added.

The immediate queue is the fastest queue in the system—it’s executed soonest and is run in interrupt time. The queue is consumed either by the scheduler or as soon as one process returns from its system call. Typical output can look like this:

    time  delta interrupt  pid cpu command
 45129449   0        1    8883   0 head
 45129453   4        1       0   0 swapper
 45129453   0        1     601   0 X
 45129453   0        1     601   0 X
 45129453   0        1     601   0 X
 45129453   0        1     601   0 X
 45129454   1        1       0   0 swapper
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X
 45129454   0        1     601   0 X

It’s clear that the queue can’t be used to delay the execution of a task—it’s an “immediate” queue. Instead, its purpose is to execute a task as soon as possible, but at a safe time. This feature makes it a great resource for interrupt handlers, because it offers them an entry point for executing program code outside of the actual interrupt management routine. The mechanism used to receive network packets, for example, is based on a similar mechanism.

Please note that you should not reregister your task in this queue (although we do it in jiqimmed for explanatory purposes). The practice gains nothing and may lock the computer hard if run on some version/platform pairs. Some implementations used to rerun the queue until it was empty. This was true, for example, for version 2.0 running on the PC platform.

Running Your Own Task Queues

Declaring a new task queue is not difficult. A driver is free to declare a new task queue, or even several of them; tasks are queued just as we’ve seen with the predefined queues discussed previously.

Unlike a predefined task queue, however, a custom queue is not automatically run by the kernel. The programmer who maintains a queue must arrange for a way of running it.

The following macro declares the queue and expands to a variable declaration. You’ll most likely place it at the beginning of your file, outside of any function:

 DECLARE_TASK_QUEUE(tq_custom);

After declaring the queue, you can invoke the usual functions to queue tasks. The call just shown pairs naturally with the following:

 queue_task(&custom_task, &tq_custom);

The following line will run tq_custom when it is time to execute the task-queue entries that have accumulated:

 run_task_queue(&tq_custom);

If you want to experiment with custom queues now, you need to register a function to trigger the queue in one of the predefined queues. Although this may look like a roundabout way to do things, it isn’t. A custom queue can be useful whenever you need to accumulate jobs and execute them all at the same time, even if you use another queue to select that “same time.”

Tasklets

Shortly before the release of the 2.4 kernel, the developers added a new mechanism for the deferral of kernel tasks. This mechanism, called tasklets, is now the preferred way to accomplish bottom-half tasks; indeed, bottom halves themselves are now implemented with tasklets.

Tasklets resemble task queues in a number of ways. They are a way of deferring a task until a safe time, and they are always run in interrupt time. Like task queues, tasklets will be run only once, even if scheduled multiple times, but tasklets may be run in parallel with other (different) tasklets on SMP systems. On SMP systems, tasklets are also guaranteed to run on the CPU that first schedules them, which provides better cache behavior and thus better performance.

Each tasklet has associated with it a function that is called when the tasklet is to be executed. The life of some kernel developer was made easier by giving that function a single argument of type unsigned long, which makes life a little more annoying for those who would rather pass it a pointer; casting the long argument to a pointer type is a safe practice on all supported architectures and pretty common in memory management (as discussed in Chapter 13). The tasklet function is of type void; it returns no value.

Software support for tasklets is part of <linux/interrupt.h>, and the tasklet itself must be declared with one of the following:

DECLARE_TASKLET(name, function, data);

Declares a tasklet with the given name; when the tasklet is to be executed (as described later), the given function is called with the (unsigned long) data value.

DECLARE_TASKLET_DISABLED(name, function, data);

Declares a tasklet as before, but its initial state is “disabled,” meaning that it can be scheduled but will not be executed until enabled at some future time.

The sample jiq driver, when compiled against 2.4 headers, implements /proc/jiqtasklet, which works like the other jiq entries but uses tasklets; we didn’t emulate tasklets for older kernel versions in sysdep.h. The module declares its tasklet as

void jiq_print_tasklet (unsigned long);
DECLARE_TASKLET (jiq_tasklet, jiq_print_tasklet, (unsigned long) 
   &jiq_data);

When your driver wants to schedule a tasklet to run, it calls tasklet_schedule:

 tasklet_schedule(&jiq_tasklet);

Once a tasklet is scheduled, it is guaranteed to be run once (if enabled) at a safe time. Tasklets may reschedule themselves in much the same manner as task queues. A tasklet need not worry about running against itself on a multiprocessor system, since the kernel takes steps to ensure that any given tasklet is only running in one place. If your driver implements multiple tasklets, however, it should be prepared for the possibility that more than one of them could run simultaneously. In that case, spinlocks must be used to protect critical sections of the code (semaphores, which can sleep, may not be used in tasklets since they run in interrupt time).

The output from /proc/jiqtasklet looks like this:

    time  delta interrupt  pid cpu command
 45472377   0        1    8904   0 head
 45472378   1        1       0   0 swapper
 45472379   1        1       0   0 swapper
 45472380   1        1       0   0 swapper
 45472383   3        1       0   0 swapper
 45472383   0        1     601   0 X
 45472383   0        1     601   0 X
 45472383   0        1     601   0 X
 45472383   0        1     601   0 X
 45472389   6        1       0   0 swapper

Note that the tasklet always runs on the same CPU, even though this output was produced on a dual-CPU system.

The tasklet subsystem provides a few other functions for advanced use of tasklets:

void tasklet_disable(struct tasklet_struct *t);

This function disables the given tasklet. The tasklet may still be scheduled with tasklet_schedule, but its execution will be deferred until a time when the tasklet has been enabled again.

void tasklet_enable(struct tasklet_struct *t);

Enables a tasklet that had been previously disabled. If the tasklet has already been scheduled, it will run soon (but not directly out of tasklet_enable).

void tasklet_kill(struct tasklet_struct *t);

This function may be used on tasklets that reschedule themselves indefinitely. tasklet_kill will remove the tasklet from any queue that it is on. In order to avoid race conditions with the tasklet rescheduling itself, this function waits until the tasklet executes, then pulls it from the queue. Thus, you can be sure that tasklets will not be interrupted partway through. If, however, the tasklet is not currently running and rescheduling itself, tasklet_kill may hang. tasklet_kill may not be called in interrupt time.



[28] The buffer of a /proc file is a page of memory, 4 KB, or whatever is appropriate for the platform you use.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required