kernel threads and kernel stacks deadlock in many scenarios

[jharris-intel]

Describe the bug

kernel threads and kernel stacks call shell_print in the callback of k_thread_foreach. shell_print attempts to take a mutex with a non-zero timeout. This can result in context switching while holding z_thread_monitor_lock, which results in incorrect behavior.

To Reproduce

n/a

Expected behavior

...I'm not actually sure what the desired behavior is, to be honest. At a high level, I suppose you could take the mutex outside the k_thread_foreach - but even then, API issues aside, you'd still have a problem if/when your shell backend backpressured.

I'm mainly opening this ticket as an invitation for discussion. Note that there are other issues discussing tangential topics, e.g. #13318, #14172, #20937, and #22841.

Impact

kernel threads and kernel stacks (and presumably any other k_thread_foreach user that does something that could block) sometimes deadlock if any of their calls to shell_print block. In particular:

• if the thread is resumed on a different core, you end up clobbering one core's interrupt state with the interrupt state of a different core. (Note: I'm going to be filing a question about this in a bit. The documented semantics do not work well in SMP.)
• If the callback to k_thread_foreach calls anything that ends up trying to take z_thread_monitor_lock, you deadlock (or assert).
• If any other task that gets context-switched in on the same core while you are in the k_thread_foreach ends up trying to take z_thread_monitor_lock, you deadlock (or assert).

Logs and console output

n/a

Additional context

Note that there appear to be multiple workarounds in place to use k_thread_foreach_unlocked instead, which results in different incorrect behavior (e.g. if anything in the system happens to delete/add a thread while you are in the call you can follow an invalid pointer off into the weeds.)

The only ways I can see kernel threads and kernel stacks working currently are either:

1. Allocate enough up front for every thread's information. In k_thread_foreach, copy all of the information out of kernel structures into allocated memory. Then print outside of k_thread_foreach and release allocated memory. Unfortunately, "enough for every thread's information" isn't particularly well-defined, and you can't allocate during the execution of k_thread_foreach.
2. Like 1, but done in multiple chunks, "abusing" k_thread_foreach and doing, say, the first 10 threads, then the 10 threads starting at the 10th, and so on. Less memory use, but has the potential to miss or duplicate threads, and is O(n^2) time w.r.t. the number of threads in the system (as you have to walk the linked list all the way from the front every time).
3. Change the shell to busywait and directly do the backend work instead of taking mutexes if called with a lock taken, and ensure that the shell backend cannot ever be interrupted by something that calls k_thread_foreach that in turn ends up calling shell print.
4. Change thread creation and deletion (or rather, anything that potentially updates next_thread/prev_thread) to be mutually exclusive with k_thread_foreach, and ensure that it's documented that e.g. logging backends can never dynamically spin up threads.

...none of which are exactly ideal.

I'm hoping there are other options I'm not seeing here, because the commands are rather useful in general.

[jakub-uC]

@jharris-intel You can always use z_shell_print which is not taking a mutex. This function is used internally by the shell. When text is printed by it the shell does not watch the order in which the characters are sent to the terminal by the shell and by users.
The only side effect is that in some narrow cases you will have incorrect text alignment or some artefact from escape codes.

I am not sure if the original problem should be fixed inside the shell module.

[andyross]

What's the code in question? The shell is an upper level subsystem and the kernel code shouldn't be calling into it, ever. I'm guessing you found a user of the thread enumeration API that is doing questionable things in the callback?

But yes: the thread and stack "foreach" enumerators are indeed problematic and encourage some really dangerous patterns. I wouldn't cry if they just disappeared, but they're popular. And without a always-available general heap, it's actually hard to provide anything but a giant locked callback for users.

[jharris-intel]

@jharris-intel You can always use z_shell_print which is not taking a mutex.

Sorry, I am confused. Could you please point me at z_shell_print? I can't find it.

There's e.g. z_shell_print_stream, but its documentation states explicitly "This function shall not be used directly". (And e.g. z_shell_fprintf - but again "This function can be called only within shell thread but not from command handlers.")

[jharris-intel]

What's the code in question?

Sorry about that - I forgot to actually link the code in question. It's the kernel_service.c shell module, kernel threads and kernel stacks commands in particular.

[jakub-uC]

@jharris-intel : Sorry for the spelling mistake. The function I am thinking about is z_shell_fprintf. Indeed it is marked as internal because if you will call it outside of the shell thread you can have problems with the correct text display. It is a hack but I do not see any other way to help you.
It is still the caller's task to ensure there will be no lock conflicts so in my opinion these kinds of problems shall not be solved inside the shell.

You can also consider using printk?

[jharris-intel]

Sorry, to be clear, this is a builtin Zephyr module.

Are you comfortable with a builtin Zephyr module using an API in a fashion that's explicitly against its specification?

I am concerned that an API is brittle enough that even the builtins that are using it are using it incorrectly. That's generally a bad sign.

But yes: the thread and stack "foreach" enumerators are indeed problematic and encourage some really dangerous patterns. I wouldn't cry if they just disappeared, but they're popular. And without a always-available general heap, it's actually hard to provide anything but a giant locked callback for users.

Yep, it's an interesting issue.

The following may help, although mainly by making the issue "loud" instead of silent:

1. Add a flag to k_thread that's, essentially, "this thread needs to be alive".
2. Each iteration of k_thread_foreach_unlocked does the following, in the following order:
   1. Read the current thread's next pointer
   2. Set the next thread's "this thread needs to be alive" flag
   3. Clear the current thread's "this thread needs to be alive" flag
   4. Release the spinlock
   5. Do the callback
   6. Grab the spinlock
   7. Set current thread to the value read in step 1
3. Have z_thread_monitor_exit return an error if the thread's "this thread needs to be alive" flag is set. (Note: this may very well need to be inside z_thread_single_abort instead, and there are considerations about which spinlock it should be protected by. Now that I look at things it may end up being a flag in thread_state, in which case it'd be protected by sched_spinlock.)

The net effect of this, assuming I understand correctly how this'd work:

1. Due to the dance with reading the next pointer before the callback, aborting the thread provided to the callback is safe, and won't result in following stale pointers. (And in general, doing operations with the current thread inside the callback is safe.)
2. Most (all?) usages of k_thread_foreach can now be replaced with k_thread_foreach_unlocked.
3. Concurrent thread creation is safe.
4. Concurrent thread deletion is "safe", in the sense that it can't result in memory corruption. However, it can now fail if there is a concurrent k_thread_foreach_unlocked call.
5. API change to k_thread_abort / z_thread_single_abort, which isn't ideal. Mostly backwards-compatible, but not entirely (adding a return value to a function previously returning void). (There are wrinkles here where kernel-internal callers of z_thread_single_abort need to comprehend the new return value, but at a quick look they should be doable.)

Still nowhere near good, but at least replaces previous "jumps off into the weeds" behavior with something that keeps the kernel alive.

The only other alternative I can see (that still retains any of the functionality of the API at least) is for thread deletion to be deferred until after the k_thread_foreach, but this has other issues (FreeRTOS does this - but FreeRTOS has a different thread allocation model, where the RTOS does the TCB allocation. Zephyr can't assume that the thread stays alive until after the k_thread_foreach because the struct k_thread may have been freed (and maybe even reused) in the meantime.)

[andyross]

Just to be clear: obviously we need to fix in-tree bugs. My reference to "the kernel" was parochial and about which promise by which API was being violated and by whom. (And, of course, whether or not this is on my plate to fix, heh). We're a big project with a lot of subsystems working at different levels of abstraction, so this kind of collision isn't uncommon.

[github-actions]

This issue has been marked as stale because it has been open (more than) 60 days with no activity. Remove the stale label or add a comment saying that you would like to have the label removed otherwise this issue will automatically be closed in 14 days. Note, that you can always re-open a closed issue at any time.

[luchnikov]

The specific issue is still standing in top-of-tree, it is 100% reproducible for me with SMP enabled (hits the "Context switching while holding lock!" assertion).

I think it is much better to switch to cmd_kernel_threads/cmd_kernel_stacks to calling k_thread_foreach_unlocked for SMP case. The probability of hitting the corner-case of manual execution of shell command colliding with thread creation/deletion is small and the temporary incorrect output that might result from that is benign compared to an assertion