Linux kernel multitasking: interrupts and tasklets

    Koteyka and younger brothersIn my previous article, I touched on the topic of multithreading. It dealt with basic concepts: types of multitasking, a scheduler, scheduling strategies, a thread state machine, and more.

    This time I want to approach the issue of planning from a different perspective. Namely, now I will try to talk about planning not flows, but their “younger brothers”. Since the article turned out to be quite voluminous, at the last moment I decided to break it into several parts:
    1. Linux kernel multitasking: interrupts and tasklets
    2. Linux kernel multitasking: 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’ll talk about how we managed to put these ideas into practice in the Embox project , and how we launched our OS with almost full multitasking on a small scarf.

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

    Interrupts and their processing


    A hardware interrupt ( IRQ ) is an external asynchronous event that comes from the hardware, pauses the program, and transfers control to the processor to handle this event. Hardware interrupt processing is as follows:
    1. The current control flow is suspended, contextual information is stored for returning 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 this interrupt.
    3. The equipment is informed that the interrupt is processed. Now it will be able to generate new interrupts.
    4. The context is restored to exit the interrupt.

    The handler function can be large enough, which is not permissible given that it is executed in the context of disabled hardware interrupts. Therefore, we came up with the idea of ​​dividing interrupt handling into two parts (on Linux they are called top-half and bottom-half):
    • The ISR itself, which is called upon interruption, does only the most minimal work, which cannot be postponed until later: it collects information about the interruption necessary for subsequent processing, somehow interacts with the hardware, for example, blocks or clears the IRQ from the device (thanks to jcmvbkbc and Zyoma for clarification ) and plans for the second part.
    • The second part, where the main processing is performed, starts in a different processor context, where hardware interrupts are enabled. This part of the handler will be called later.

    So we come to the delayed interrupt handling. Linux uses the tasklet and workqueue for this purpose.

    Tasklet


    In short, the tasklet is a bit of a very small thread that has neither its own stack nor context. Such "flows" work out quickly and completely. Key features of tasklets:
    • tasklets are atomic, so you cannot use sleep () and synchronization primitives such as mutexes, semaphores, and so on. But, for example, spinlock (spinning or cyclic locking) can be used;
    • called in a softer context than ISRs. In this context, hardware interrupts are allowed that displace tasklets for the duration of the ISR. In the Linux kernel, this context is called softirq, and in addition to launching tasklets, it is used by several other subsystems;
    • tasklet runs on the same kernel as it plans it. More precisely, I managed to plan it first by calling softirq, whose handlers are always tied to the calling kernel;
    • different tasklets can be executed in parallel, but at the same time it is not called with itself at the same time, since it is executed on only one core, the first to schedule its execution;
    • tasklets are performed according to the principle of non-preemptive planning, one after the other, in the order of the queue. You can plan with two different priorities: normal and high.

    Let us now look “under the hood” and see how they work. First, the tasklet structure itself (defined in):
    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 must first 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 */
    

    It is easy to schedule tasklets: a tasklet is placed in one of two queues, depending on priority. Queues are organized as singly linked lists. Moreover, each CPU has its own queues. This is done using the 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, planning it again will not work - in this case, nothing will happen. Tasklet cannot be in several places at once in the planning queue, which is organized through the next field of the tasklet_struct structure. This, however, is true for any lists linked through the object field, such as.
    For execution, the tasklet is assigned the state 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 both by himself, and, for example, interruption 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, moreover, 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, it can still be added to the planning queue, but it will not be executed on the processor until it is activated again. Moreover, if the tasklet has been deactivated several times, then it should be activated exactly the same number of times, the count field in the structure is just for this.

    You can also kill tasklets. Like this:
    void tasklet_kill(struct tasklet_struct *t);
    

    Moreover, he will be killed only after the tasklet is executed, if it is already planned. If suddenly the tasklet plans itself, then before calling this function, one must remember to prohibit him from doing this - this is on the conscience of the programmer.

    Most interesting are the functions that play the role of a scheduler:
    static void tasklet_action(struct softirq_action *a);
    static void tasklet_hi_action(struct softirq_action *a);
    

    Since they are almost identical, it makes no sense to give the code of both functions. But here is one of them worth a look to understand 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();
    	}
    }
    

    Pay attention to the call to the tasklet_trylock () and tasklet_lock () functions. tasklet_trylock () sets the tasklet to TASKLET_STATE_RUN and thereby blocks the tasklet, which prevents the execution of the same tasklet on different CPUs.

    These scheduler functions, in fact, implement cooperative multitasking, which I examined in detail in my article . Functions are registered as softirq handlers, which is triggered when scheduling tasklets.

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

    To be continued


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

    PS For advertising. I also want to invite everyone who is interested in our project to a meeting organized by codefreeze.ru ( announcement on the hub ). It will be possible to chat live, ask interesting questions to the main villain abondarev and criticize in person , in the end :)

    Also popular now: