z_unpend1_no_timeout non-atomic

[jharris-intel]

Describe the bug

The implementation of z_unpend1_no_timeout is non-atomic, and can result in threads in an inconsistent state.

To Reproduce

Inspect

Expected behavior

z_unpend1_no_timeout should leave threads in a consistent state.

Impact

Usages of z_unpend1_no_timeout in preemptive threads, threads and interrupts, or in SMP mode can result in catastrophic system-level behavior (chasing stale/null pointers, threads not being scheduled, threads being scheduled on multiple cores at once, etc.)

Logs and console output

n/a

Environment (please complete the following information):

• OS: Ubuntu 18.04.5 LTS
• Toolchain (e.g Zephyr SDK, ...)
• Commit SHA or Version used: based off of /u/MrVan's AArch64 SMP branch (ARM64 SMP support #30676) with some additional fixes that I'm in the process of upstreaming. That being said, the references below are from trunk.

Additional context

The current implementation of z_unpend1_no_timeout is as follows.

	struct k_thread *thread = z_find_first_thread_to_unpend(wait_q, NULL);
	if (thread != NULL) {
		z_unpend_thread_no_timeout(thread);
	}

Unfortunately, although both of these individual calls are protected internally by sched_spinlock, there is no guarantee that the combination of the two calls are atomic.

This can result in catastrophic system-level behavior. For one (rather contrived) example:

(some_timer currently is expired, with thread D waiting on it)
A: starts k_timer_stop(&some_timer)
B: starts k_timer_stop(&some_timer)
A: calls into z_abort_timeout(&timer->timeout) -> success, so keep going
C: starts k_timer_start(&some_timer, very_small_duration)
C: runs all the way through k_timer_start, including adding a new timeout
B: calls into z_abort_timeout(&timer->timeout) -> success, so keep going
A: starts z_unpend1_no_timeout
A: calls z_find_first_thread_to_unpend -> returns D
B: starts z_unpend1_no_timeout
B: calls z_find_first_thread_to_unpend -> returns D
A: thread != NULL, so calls _priq_wait_remove which calls z_priq_dumb_remove
A: calls sys_dlist_remove(&thread->base.qnode_dlist);
A: sys_dlist_remove follows thread D.next and thread D.prev
A: sys_dlist_remove sets thread D.next == thread D.prev == NULL
B: thread != NULL, so calls _priq_wait_remove which calls z_priq_dumb_remove
B: calls sys_dlist_remove(&thread->base.qnode_dlist);
B: sys_dlist_remove follows thread D.next and thread D.prev
B: null pointer dereference

The simplest option here that I can see is to change z_unpend1_no_timeout from a function calling two functions which each lock into a function that locks sched_lock and then call two functions that each don't lock (akin to e.g. z_unpend_thread_no_timeout and unpend_thread_no_timeout, where e.g. z_thread_timeout locks then calls unpend_thread_no_timeout and does other things); I haven't examined if the non-atomicity in e.g. z_impl_k_timer_stop is a problem; if so this interface may need to be rethought.

...of course, it's also entirely possible I'm missing something obvious here.

(P.S. there is also a rather suspect comment in z_timer_expiration_handler:

	/*
	 * Interrupts _DO NOT_ have to be locked in this specific
	 * instance of thread unpending because a) this is the only
	 * place a thread can be taken off this pend queue, and b) the
	 * only place a thread can be put on the pend queue is at
	 * thread level, which of course cannot interrupt the current
	 * context.
	 */

...is this actually the case in SMP mode? On a single core, sure, but this comment's logic does not apply if there are multiple cores so far as I can tell. At least not without additional considerations (e.g. if there's a lock in this chain that I'm missing that would prevent a concurrent call to z_impl_k_timer_start). In addition, z_impl_k_timer_stop also potentially takes items off of the pend queue, contradicting a), if I understand the code correctly.)

[carlocaione]

following

[andyross]

That's all pretty much exactly right. The unsynchronized waitq unpending calls are clearly a mistake that should be fixed before the release. But really the API here is sort of a tangled mess, owing to too many older calls that don't really have value anymore. All the "no_timeout" variants, for example, are for the most part just performance worry about not wanting to double-remove a timeout object (but that's just a lock and a list removal now).

And that comment in k_timer is indeed stale and predates SMP. To be honest the k_timer code itself seems find to me, though. All it needs to rely on is that the underlying kernel timeout and wait_q APIs are correctly synchronized (which, yeah, they aren't, but they should be).

I'll see about getting a refactoring of the internal waitq API in for next release. In the immediate term (given that the release is this week) I think the best we can do is a targetted lock around the calls we have.

[jharris-intel]

Sounds good, thank you for the response!

To be honest the k_timer code itself seems find to me, though.

Yep, that was mainly intended to be just an example showcasing that you could hit this issue using externally-visible APIs.

That being said, I do have a lingering concern there about something else in the system seeing the thread in a state where the thread has been removed from wait_q but hadn't yet been readied or scheduled:

	struct k_thread *pending_thread = z_unpend1_no_timeout(&timer->wait_q);
        // another thread comes in at this point in the flow. Any issues if it, oh, I don't know, tries to abort the thread?
	if (pending_thread != NULL) {
		z_ready_thread(pending_thread);
		z_reschedule_unlocked();
	}

Most of the other cases I see change thread states all while under a single lock of the spinlock, so I do wonder if anything in the system required that those update sequences be atomic.

[andyross]

Enhancement added at #32148 to track the rework needed. Feel free to elevate that to to a "Bug" post-release, I just don't want to mess up the bug counts at the last minute with work I'd never be able to finish.

Will have a targetted fix for this submitted as soon as my local twister run completes.