Multitasking in the Linux kernel: interrupts and tasklets

In my previous article I addressed the topic of multithreading. It dealt with basic concepts: types of multitasking, a scheduler, scheduling strategies, a stream state machine, and so on.

This time I want to approach the question of planning from the other side. Namely, now I will try to tell about planning not streams, but their “younger brothers”. Since the article was quite voluminous, at the last moment I decided to break it into several parts:

1. Multitasking in the Linux kernel: interrupts and tasklets
2. Multitasking in the Linux kernel: workqueue
3. Protothread and cooperative multitasking

In the third part, I will also try to compare all these, at first glance, different entities and extract some useful ideas. And after a while I will talk about how we managed to put these ideas into practice in the Embox project , and about how we started our OS on a small handkerchief with almost full-fledged multitasking.

I will try to tell you in detail, describing the main API and sometimes delving into the implementation, especially focusing on the planning task.

Interrupts and their processing

A hardware interrupt ( IRQ ) is an external asynchronous event that comes from the hardware, suspends the program run, and transfers control to the processor to handle this event. The hardware interrupt is processed as follows:

1. The current control flow is suspended, the context information is saved to return to the flow.
2. The handler function ( ISR ) is executed in the context of disabled hardware interrupts. The handler must perform the actions necessary for the interrupt.
3. The equipment is informed that the interrupt has been processed. Now it can generate new interrupts.
4. The context is restored to exit the interrupt.

The handler function can be quite large, which is impermissible given that it is executed in the context of disabled hardware interrupts. Therefore, it was decided to divide the interrupt handling into two parts (in Linux, they are called top-half and bottom-half):

• Directly ISR, which is called upon interruption, performs only the most minimal work that cannot be put off until later: it collects interruption information necessary for subsequent processing, somehow interacts with the equipment, for example, blocks or clears the IRQ from the device (thanks to jcmvbkbc and Zyoma for clarification ) and plans the second part.
• The second part, where the main processing is performed, is launched in a different processor context, where hardware interrupts are enabled. The call to this part of the handler will be made later.

So we approached deferred interrupt handling. In Linux, the tasklet and workqueue are used for this purpose.
')

Tasklet

In short, a tasklet is something like a very small thread that does not have its own stack or context. Such “streams” are worked out quickly and completely. The main features of tasklets:

• tasklets are atomic, so one cannot use sleep () and such synchronization primitives as mutexes, semaphores, and so on. But, for example, spinlock (spinning or looping) can be used;
• called in a softer context than the ISR. In this context, hardware interrupts are enabled that force out tasklets for the duration of an ISR. In the Linux kernel, this context is called softirq, and in addition to running tasklets, it is used by several other subsystems;
• tasklet runs on the same core as its plans. Or rather, managed to plan it first, calling softirq, the handlers of which are always tied to the calling kernel;
• different tasklets can be executed in parallel, but at the same time it cannot be called to itself at the same time, since it is executed only on one core, the first to schedule its execution;
• tasklets are executed according to the principle of non-displacing planning, one after the other, in turn. You can plan with two different priorities: normal and high.

Let's take a look now “under the hood” and see how they work. First, the tasklet structure itself (defined in <linux / interrupt.h> ):

struct tasklet_struct { struct tasklet_struct *next; /*  tasklet     */ unsigned long state; /* TASKLET_STATE_SCHED  TASKLET_STATE_RUN */ atomic_t count; /*   ,  tasklet   */ void (*func)(unsigned long); /*   tasklet' */ unsigned long data; /* ,    func */ }; 

Before using a tasklet, you first need to initialize it:

 /*   tasklet  */ void tasklet_init(struct tasklet_struct *t, void (*func)(unsigned long), unsigned long data); DECLARE_TASKLET(name, func, data); DECLARE_TASKLET_DISABLED(name, func, data); /*  tasklet */ 

Tasklets are planned simply: tasklet is placed in one of two queues, depending on priority. Queues are organized as single-linked lists. Moreover, each CPU has its own queues. This is done using functions:

 void tasklet_schedule(struct tasklet_struct *t); /*    */ void tasklet_hi_schedule(struct tasklet_struct *t); /*    */ void tasklet_hi_schedule_first(struct tasklet_struct *t); /*   */ 

When a tasklet is scheduled, it is set to TASKLET_STATE_SCHED , and it is added to the queue. While he is in this state, to schedule it again will not work - in this case, nothing will happen. The tasklet cannot be in several places in the planning queue at once, which is organized through the next field of the tasklet_struct structure. This, however, is true for any lists linked through an object field, such as <linux / list.h> .
At runtime, the tasklet is assigned the status TASKLET_STATE_RUN . By the way, the tasklet gets out of the queue before its execution, and the TASKLET_STATE_SCHED state is removed, that is, it can be scheduled again during its execution. This can be done either by himself or, for example, by an interrupt on another core. In the latter case, however, he will be called only after he finishes his execution on the first core.

Interestingly enough, the tasklet can be activated and deactivated, recursively. The following functions are responsible for this:

 void tasklet_disable_nosync(struct tasklet_struct *t); /*  */ void tasklet_disable(struct tasklet_struct *t); /*     tasklet' */ void tasklet_enable(struct tasklet_struct *t); /*  */ 

If the tasklet is deactivated, you can still add it to the planning queue, but it will not run on the processor until it is activated again. Moreover, if the tasklet has been deactivated several times, then it must be activated exactly the same time, the count field in the structure is just for this.

And tasklets can be killed. Like this:

 void tasklet_kill(struct tasklet_struct *t); 

Moreover, it will be killed only after the tasklet is completed, if it is already planned. If suddenly the tasklet is planning itself, then you need to remember to prevent it from doing this before calling this function - this is on the programmer’s conscience.

The most interesting features that play the role of the scheduler:

 static void tasklet_action(struct softirq_action *a); static void tasklet_hi_action(struct softirq_action *a); 

Since they are almost the same, it makes no sense to provide the code for both functions. But here it is worth looking at one of them in order to find out in more detail:

 static void tasklet_action(struct softirq_action *a) { struct tasklet_struct *list; local_irq_disable(); list = __this_cpu_read(tasklet_vec.head); __this_cpu_write(tasklet_vec.head, NULL); __this_cpu_write(tasklet_vec.tail, &__get_cpu_var(tasklet_vec).head); local_irq_enable(); while (list) { struct tasklet_struct *t = list; list = list->next; if (tasklet_trylock(t)) { if (!atomic_read(&t->count)) { if (!test_and_clear_bit(TASKLET_STATE_SCHED, &t->state)) BUG(); t->func(t->data); tasklet_unlock(t); continue; } tasklet_unlock(t); } local_irq_disable(); t->next = NULL; *__this_cpu_read(tasklet_vec.tail) = t; __this_cpu_write(tasklet_vec.tail, &(t->next)); __raise_softirq_irqoff(TASKLET_SOFTIRQ); local_irq_enable(); } } 

Note the call to the tasklet_trylock () and tasklet_lock () functions. tasklet_trylock () sets the tasklet to TASKLET_STATE_RUN status and thus blocks the tasklet, which prevents the execution of the same tasklet on different CPUs.

These planner functions, in essence, implement cooperative multitasking, which I discussed in detail in my article . Functions are registered as softirq handlers, which is initiated when scheduling tasklets.

The implementation of all the above functions can be found in the include / linux / interrupt.h and kernel / softirq.c files .

To be continued

In the next part I will talk about a much more powerful mechanism - workqueue, which is also often used for deferred interrupt handling.

PS For publicity. I also want to invite everyone who is interested in our project, to a meeting organized by codefreeze.ru ( announcement on Habré ). On it you can talk live, ask questions to the main villain abondarev and criticize in the face , in the end :)