Zephyr: Soft real-time "tasklets" in kernel

[carlescufi]

The way the Zephyr kernel schedules today is:

• ISRs have the highest priority, they execute always before any threads
• If no ISRs are pending, ready cooperative threads are run
• If no cooperative threads are ready, ready preemptible threads are run

The problem is when one wants to design a "soft real-time" protocol stack with this architecture is that one cannot use cooperative threads because those might hold the CPU for too long and are not pre-emptible at all except by an ISR, but the desire here is to run the "bottom-half" in thread mode.
A good example is the Host/Controller split in the BLE subsystem:

• The Host runs as a set of cooperative threads, but it's much lower priority than the Controller
• The Controller currently runs entirely on ISRs (both hardware interrupts and software interrupts), but we'd like for parts of it to be able to run in thread mode. To enable this the Controller thread-mode parts need to be able to preempt the Host's cooperative threads.

What we would require to avoid having to use software interrupts for soft real-time is:

• Pre-emptible "tasklets" that run in thread mode but are scheduled before the cooperative threads
• These tasklets can preempt a cooperative thread and can only be preempted by another tasklet or by an ISR
• These tasklets can block indefinitely on a kernel object since they run in thread mode

[carlescufi]

@cvinayak @Vudentz @jhedberg FYI

[SebastianBoe]

What is the reason for not making the host's threads into preemtible threads?

Then the controller would be able to preempt the host, wouldn't it?

[carlescufi]

@SebastianBoe for one it would increase the complexity of the Host, since it would have to add locking in several places. But it would also put the host below the TCP/IP stack and any other coop threads that the system runs, which is not a good idea given that the Host is a "system service".

[carlescufi]

@andrewboie Could you give us some early feedback on what you think about this? Thanks!

[sundar-subramaniyan]

Hi, I'd also like to have tasklets in the kernel. In my case, I need a tasklet in usb driver to offload stuff from ISR basically which would run time critical code. Currently I'm using a FIFO to offload work from ISR to a work handler. But while the work handler is running other threads should not get scheduled as it would break the USB bus read/write sequence. We can use k_sched_lock() and k_sched_unlock() while executing the work handler but this has to be handled properly by developers which adds more complexity. With tasklets (or DSRs in other words), things will be rather simpler.

[andyross]

Just now taking a look:

So... doing this is actually easy. We'd just augment the scheduler to recognize a "TASKLET" bit on the thread (or a specific numeric priority), which says that it should be placed into the run queue cache slot even if the current highest-priority thread is cooperative. Unless I've missed something, none of the architecture code needs to change, it's all in the scheduler.

That said: if we allow "cooperative" threads to be preempted, we're making a total hash out of the idea of cooperative threads in the first place. Code that is correctly written to rely on priority and non-preemption to elide the use of irq_lock() will suddenly break when a tasklet is introduced.

I'm not sure this is a great API choice.

Consider also that it's a turtles-all-the-way-down problem. What happens when you have two subsystems with tasklets? Should they preempt each other? Can they be relied on to cooperatively work together?

So, for API sanity, should we maybe structure this feature so that "tasklet" priority is available only when cooperative priorities are disabled? And if we do: don't threads at cooperative priorities become our tasklets and we need no code changes?

Bottom line: how do we square the promises we make about cooperative scheduling with tasklets? I don't see that we can. Maybe the real bug here is that Zephyr made cooperative scheduling the "default"...

[carlescufi]

Hey @andyross thanks for the input, this is really helpful.

That said: if we allow "cooperative" threads to be preempted, we're making a total hash out of the idea of cooperative threads in the first place. Code that is correctly written to rely on priority and non-preemption to elide the use of irq_lock() will suddenly break when a tasklet is introduced.

I might be missing something, but I think this must not necessarily be the case. If tasklets are treated as such, and not as "preemptive thread with higher prios than coop ones" then I think there's the opportunity to consider them a hybrid of thread and ISR. They obviously wouldn't be able to directly share data with a cooperative thread, and instead would use FIFOs and any other synchronization primitive to achieve data sharing. By avoiding calling them "threads" we make users aware that they are not, so I don't see how we break existing code that is written to rely on priority and non-preemption. That code was doing things like fifo_get() and expecting an ISR to do the k_fifo_put(), but now it will be a tasklet producing the data instead.

What happens when you have two subsystems with tasklets? Should they preempt each other?

My original expectation is that they would work exactly like interrupts, so yes, they would have a priority and they could preempt each other. I don't see this as an issue, but again I might be missing something.

So, for API sanity, should we maybe structure this feature so that "tasklet" priority is available only when cooperative priorities are disabled?

I think it's too late for something like this. Big, complex subsystems rely on cooperative threads and porting them to work on preemptive threads is a massive effort.

Bottom line: how do we square the promises we make about cooperative scheduling with tasklets?

By treating tasklets as interrupts that happen to run in thread mode (ARM lingo sorry) instead of interrupt mode.

[andyross]

To clarify the first point: if the action of TasletA having interrupted thread Coop0 is to wake up Coop1 which is a higher priority thread, then we'll end up returning into Coop1 in a context where Coop0 doesn't expect. These are application threads, and may have races when used in a preemptive context that we can't fix.

Now... we could try to fix this in the scheduler by keeping a "last preempted coop thread" pointer somewhere to which we return, I guess. Actually that would have to be a stack, because preempted tasklets would (for the same reasons) need to be unwound in the order they were preempted too. Maybe this trick would address my concerns with "cooperative assumption breakage" at the cost of more complicated scheduling...

[carlescufi]

To clarify the first point: if the action of TasletA having interrupted thread Coop0 is to wake up Coop1 which is a higher priority thread, then we'll end up returning into Coop1 in a context where Coop0 doesn't expect. These are application threads, and may have races when used in a preemptive context that we can't fix.

OK, now I understand your reasoning. IMHO this should be seen as an interrupt having taken action to wake up Coop1, meaning that indeed Coop0 would need to run to completion before Coop1 is scheduled. How that is achieved within the scheduler I must admit is beyond my knowledge at this point, but @cvinayak can maybe give his opinion about the stacks you propose, since I believe he has implemented something similar in the past.

[nashif]

are we looking for something like this: https://www.freertos.org/xTimerPendFunctionCallFromISR.html ?

[carlescufi]

are we looking for something like this: https://www.freertos.org/xTimerPendFunctionCallFromISR.html ?

Sort of, but I'd rather not have this processed by a central RTOS daemon because there might be the need later on to have different priorities with tasklets, not just a common FIFO of task items that a single daemon processes. Maybe I'm over-engineering though, the current necessity comes from BLE and USB.

[nashif]

One thing to note here is the fact that tasklets have an unfortunate name, basically they have nothing to do with schedulable tasks, based on my understanding, tasklets are functions doing followup work that an ISR requests for its interrupt servicing. The tasklet runs with interrupts enabled. Just like the ISR that has requested it, a tasklet would run outside the context of a particular task/thread. So, when you ask for:

Pre-emptible "tasklets" that run in thread mode but are scheduled before the cooperative threads

It can be confusing, especially the "thread mode" bit. Are you just saying that the tasklet would run with interrupts enabled here?

[carlescufi]

One thing to note here is the fact that tasklets have an unfortunate name, basically they have nothing to do with schedulable tasks, based on my understanding, tasklets are functions doing followup work that an ISR requests for its interrupt servicing.

Well that's a good point you bring up. I think we can go both ways: either we consider them "lightweight threads above coop that run forever" or we go the Linux tasklet way with deferred work that is not executed in ISR. For the particular case of the BLE stack I believe we were really looking for something that runs forever, a lightweight thread above coop threads, @cvinayak can you confirm?

The tasklet runs with interrupts enabled.

I'm not sure I understand this. At least on ARM, everything runs with interrupts enabled in Zephyr, including ISRs. The exception of course is the small sections where one locks/unlocks interrupts.

It can be confusing, especially the "thread mode" bit. Are you just saying that the tasklet would run with interrupts enabled here?

Maybe there's some misunderstanding related to architectures here. On ARM you can be in "Thread Mode" (running a thread, all ISRs preempt you) or in "Handler Mode" (running an ISR, only ISRs of higher priority can preempt you). Again everything runs with interrupts enabled, we never disable interrupts for longer than a short irq_lock() / irq_unlock() sections where you really need a critical section.

[nashif]

I'm not sure I understand this. At least on ARM, everything runs with interrupts enabled in Zephyr, including ISRs.

Meaning that in the tasklet, we allow higher priority interrupts to occur and be processed when servicing lower priority interrupts.

[carlescufi]

we allow higher priority interrups to occur

Yep, we allow all interrupts to occur in fact. Tasklets run on thread mode, which allows all and any interrupt to preempt the tasklet. This is by design.

[cvinayak]

@andyross

So... doing this is actually easy. We'd just augment the scheduler to recognize a "TASKLET" bit on the thread (or a specific numeric priority), which says that it should be placed into the run queue cache slot even if the current highest-priority thread is cooperative. Unless I've missed something, none of the architecture code needs to change, it's all in the scheduler.

That said: if we allow "cooperative" threads to be preempted, we're making a total hash out of the idea of cooperative threads in the first place. Code that is correctly written to rely on priority and non-preemption to elide the use of irq_lock() will suddenly break when a tasklet is introduced.

I do not see a tasklet as a thread, but rather similar to an ISR, a software generated and scheduled ISR like handlers executed one after another.

Consider also that it's a turtles-all-the-way-down problem. What happens when you have two subsystems with tasklets? Should they preempt each other? Can they be relied on to cooperatively work together?

Tasklets at same priorities queue after each other until completion. Tasklets at a higher priority level interrupt lower priority tasklets, and return back to lower priority tasklet queue on completion of tasklets higher in priority level.

So, for API sanity, should we maybe structure this feature so that "tasklet" priority is available only when cooperative priorities are disabled? And if we do: don't threads at cooperative priorities become our tasklets and we need no code changes?

Currently (correct me), coop threads cannot be preempted by higher priority threads (coop or preemptable), hence coop threads with priority hierarchy does not satisfy a tasklet definition.

Bottom line: how do we square the promises we make about cooperative scheduling with tasklets? I don't see that we can. Maybe the real bug here is that Zephyr made cooperative scheduling the "default"...

Co-operative scheduling as default is not a bug, its seen as system services in the OS.
An architecture I envision is, in decreasing priority levels of execution contexts:

• ISRs, exceptions with priority levels, scheduled by hardware interrupt controller and hard real-time deterministic latencies.
• Tasklets (Bottom halves, or mayfly as I call in BLE controller subsys), thread mode execution with priority levels, interrupt-able by ISRs, but not-preempt-able due to ISRs (mayfly is executing in s/w ISRs, piggy back).
• Co-operative threads with priorities, OS thread mode services, ex. BLE Host.
• Pre-emptive threads with priorities, thread mode user applications.

To clarify the first point: if the action of TasletA having interrupted thread Coop0 is to wake up Coop1 which is a higher priority thread, then we'll end up returning into Coop1 in a context where Coop0 doesn't expect. These are application threads, and may have races when used in a preemptive context that we can't fix.

Correct me; Coop1 at higher priority cannot prempt Coop0 (full stop). TaskletA interrupting Coop0, waking up Coop1, returns to Coop0. Yes, subsystems designed today will break, coop thread are not preemptable, they only yield (or swap at deterministic locations in design).

@carlescufi

By treating tasklets as interrupts that happen to run in thread mode (ARM lingo sorry) instead of interrupt mode.

Yes. I call them mayflies, as in wikipedia:

Often, all the mayflies in a population mature at once (a hatch), and for a day or two in the spring or autumn, mayflies are everywhere, dancing around each other in large groups, or resting on every available surface.

^^ this is how mayflies in BLE controller is used, h/w ISRs enqueue "functions" from any ISR priority (includes coop thread mode as an unique single caller priority level) to any mayfly priority level (today, implemented as software interrupts at h/w priority levels). Pending a s/w IRQ leads to a "hatch" of enqueued "functions" one after the other, if any when the s/w IRQ is enabled (aka spring or autumn in the mayfly analogy). The execution will be all over the place, interrupting lower priority ISRs, coop and preemptive threads, and uses ISR program stack (in todays mayfly implementation).

@nashif

Meaning that in the tasklet, we allow higher priority interrupts to occur and be processed when servicing lower priority interrupts.

Yes, h/w interrupts are enabled at all time, to ensure deterministic ISR latencies. See my mayfly explanation in above discussions.

All this said, I used to use the word "work" before renaming to "mayfly" in BLE controller, I dont use the term tasklet, just so as to avoid any confusion with original tasklet that others may have been familiar with in other OSes.

@andyross @carlescufi @nashif
I have a working ARM bare metal prototype of something I call "injection", wherein a scheduler in ISR exit would "inject" a function call that executes and returns back to interrupted thread. This was sometime back before I got busy in Zephyr, it was WIP back then. The implementation did have some setbacks needing me to disable interrupts to achieve the "injection" to avoid a new ISR exit interrupting the "injecting" code. All I wanted was to be able run everything in thread mode, be able to move mayfly concept down into thread mode, and "injection" acting as ISR in thread mode.

[nashif]

Someone else calls those LSRs http://www.smxrtos.com/articles/lsr_art/lsr_art.htm

[hongshui3000]

It looks like this kernel ：http://www.state-machine.com/qpc/group__qk.html

[skordal]

I was thinking about this from a usage perspective, and there seem to be two different ways to support tasklets.

Driver/subsystem managed tasklets:
A driver that wants to delegate processing from an ISR to a tasklet creates its own tasklet threads, using k_thread_create() with a special K_TASKLET option flag. This allows drivers more control over the code that is run in tasklet threads and over the resources consumed by the threads (for instance, stack size). Letting drivers/subsystems manage tasklet threads in this way allows using tasklets with existing APIs.

OS managed tasklets:
The OS creates a set of tasklet threads, one for each tasklet priority. Drivers/subsystems can register functions while processing an IRQ, which are run by a tasklet thread after the IRQ handler returns. If multiple drivers need to offload IRQ processing, having a common set of tasklet threads that execute enqueued functions can reduce overhead as compared to each driver having its own threads. It does, however, require some new API functions (probably something like the existing mayfly API) and config options.

PS: since everyone uses different naming for tasklets, I propose calling them "zephlets" in Zephyr :)

[carlescufi]

@andyross Can we consider this closed with the new Meta IRQ priorities or is there still work to be done there?

[andyross]

I'd consider this requierment closed. There are directions the API could go in the future, for example allowing metairq threads to share the IRQ stack instead of having their own, or adding a queueing API on top of it that looks more like a linux tasklet. But the scheduling requirement has been met.

[carlescufi]

@andyross thanks! @cvinayak will test this shortly