_Swap on ARM is nonatomic by design, can we fix that?

[andyross]

The way _Swap() is implemented on ARM is nonatomic, which while not incorrect has turned out to be very surprising. It's done with a PendSV exception whose priority sits below that of hardware interrupts, so it's possible for a process to decide to context switch based on atomic state that then gets changed under the interrupt handler before the context switch actually happens.

This trick has resulted in three moderatly excruciating bug hunts so far (c.f. commits 41070c3 and 6c95daf and the current work submitted in PR #12448). In all honestly I doubt that's going to be the last of them.

There's a framework now which will help keep the workarounds (which so far haven't been complicated) tidy, which should help some.

But basically: how wedded are we to this architecture? How hard would it be and what would it break to set the PendSV exception to the maximum interrupt priority such that it can't be interrupted like this? That would match ARM's behavior to that of other systems (who do context switching with more typical musical-chairs register swaps and not in an exception handler), albeit at the cost of higher worst case latencies for high priority interrupts.

IMHO it would make for better reliability on ARM in the long term, and certainly would make my life easier.

[andyross]

@agross-linaro @andrewboie and anyone you want to add who might be interested. Mostly I'm interested in whoever jumps in with "No! you can't do that because..."

[pabigot]

More background from material I prepared before I saw this had been opened:

PR #12248 enhances the sys_dlist_t data structure to support detecting and diagnosing API mis-use, in particular removing a node from the same list twice. With this change the gap in interrupt blocking present in the ARM context switch produces in a failure in the case where (a) the current thread is being swapped because it has been aborted and removed from the run queue, but (b) the timeslicing infrastructure wakes up and attempts to remove it from the queue a second time before the PendSV handler is invoked.

The data structure enhancements found at least one unknown API violation, and have been approved on their own, but before they can be merged a fix for the root fault they expose needs to be in place.

A previous observation of this issue was resolved through a workaround in #8126 by @mike-scott. It recurred in the testing of #12248. Through coordinated effort the root cause was identified. A similar workaround in that PR was rejected in favor of a more complete fix, a sentiment I agree with in principle, but not for something of this complexity and lack of visibility.

@andyross has provided a fix currently attached to #12248. I have some concerns, but github won't let me review it in that context because I submitted the PR. So I've marked that PR DNM until this issue is properly fixed, or the local workaround restored.

[agross-oss]

The pendsv has historically always been the lowest priority so that it ends up tail chaining on to any irqs that occur. This means that multiple swap() requests could occur before the swap actually occurs due to multiple irqs calling the swap() mechanism. The actual swap won't occur until all of the irqs are handled and the pendsv is then called last due to it being the lowest prio.

If you look at the irq code in swap_helper.S, it disables irqs, then does the list manipulations (per your change in 401073c . So there is an opportunity for it to be interrupted, but only right before it locks the irqs. Once that is done, you won't be interrupting until it completes the actual swap operation. Are you worried there is another race condition?

Do you have a concrete example of this that occurs today? [never mind, i just read through 12248 fully].

what is this framework of workarounds?

[agross-oss]

The pendsv is configurable. But if we are going to go this route, why even use pendsv for context switch?

[pabigot]

@agross-linaro The framework of workarounds would be the last three patches @andyross pushed onto that PR, the last being this one. It makes the tests run, as does my smaller patch, and was expected to be merged by now, but I requested a delay so they can be reviewed properly in a distinct PR.

I suspect I could come up with strained examples where having an outdated current_ causes issues with non-timer commits, so I don't think a change that only fixes problems with ISRs that go through z_clock_announce is enough. I might be wrong about that. Your point about chaining ISRs has merit; is that how this operates on non-ARM architectures?

[agross-oss]

@pabigot Ok, it sounded so formal that I thought there was something more than just a few patches. Given your issue I can see how this is occurring. This takes multiple events happening that 1) cause a swap and 2) change the conditions that precipitated the swap before the actual swap occurs.

And no, no other architecture has this tail chaining behavior. If you search around a little, you'll find the pendsv is the preferred method for context switching for ARM processors. That doesn't mean we are forced to use it or even use it with the lowest priority. However, if we were thinking of bumping the priority I would suggest we just abandon it and come up with something else.

@galak Do you have any thoughts on this?

[pabigot]

This paper might be useful. Their results (which I have not reviewed) show software switching is faster than PendSV on Cortex-M3, at least as they implemented each.

[agross-oss]

@pabigot i don't doubt the switching comes in faster. The cost is slightly higher irq latency, which they don't show. The issue at heart here is the fact that we have an expectation that a swap is atomic. I say this because of the things we have had to do to 'fix' issues related to the tail chaining.

[andyross]

The issue at heart here is the fact that we have an expectation that a swap is atomic

To be clear: we don't. But the fact that we don't causes bugs, and I think is likely to continue to do so.

I mean, if you think about it it's a lower level violation of the basic idea of a condition variable: you want to check if some condition is true and then decide to block if it isn't. So in a cvar API, the "release the lock" and "go to sleep" steps are guaranteed by the system to be atomic. And the _Swap() API, which takes a key argument received from irq_lock(), is piggy backing on the same metaphor.

But in Zephyr, that can't be guaranteed on ARM -- something else may run after you've checked the state and before you are put to sleep, so you're not guaranteed that state isn't going to change. And in a handful of cases it has.

Personally... I dunno, I have a hard time believing that a non-atomic context switch can ever really be a good thing. It's just too dangerous in the long term for the benefit. Apps with super-tight latency requirements can certainly work with this kind of PendSV priority magic on their own for their own interrupts, but right now the exception sits below everything in the kernel.

[pabigot]

I also think a non-atomic context switch is a perversion of nature. Regardless, I certainly have an expectation that Zephyr be consistent in whether context switch is atomic, so if ARM is the only architecture where it isn't I think that should be changed.

We should make sure stakeholders who really care about IRQ latency on ARM systems get involved. Things like Bluetooth or 6lowpan time-synchronized network transactions are one case. I know both Nordic and EFx32 have hardware-triggered events that reduce the risk of timing violations, but not how they might be affected by a change. @carlescufi?

[agross-oss]

@andyross We're talking about the condition changing multiple times before the pendsv fires. And the only way i can think this would work properly is to make the swap atomic and just accept the fact that you might have multiple save/restores of the stack frame + PSP switching instead of just a single hw assisted swap. That's all you get out of tail chaining the PENDSV.

[galak]

@andyross We're talking about the condition changing multiple times before the pendsv fires. And the only way i can think this would work properly is to make the swap atomic and just accept the fact that you might have multiple save/restores of the stack frame + PSP switching instead of just a single hw assisted swap. That's all you get out of tail chaining the PENDSV.

My general feel is having _Swap be atomic makes sense, but I think we should get input from the Nordic guys as I wonder if that will impact timing for Bluetooth on low end M0 devices were they already have pretty tight deadlines.

[agross-oss]

You guys want to discuss this in the API meeting tomorrow? or the earlier mmu/mpu meeting?