Issue 243514
Summary [OpenMP][libomp] After a hot team shrinks, a worker can steal a task from the reused task team and crash in `__kmp_push_task`
Labels new issue
Assignees
Reporter ACSimon33
    ## Summary

A program that runs parallel regions with tasks and changes the number of threads between them can crash with a SIGSEGV in `__kmp_push_task` (or `__kmp_task_alloc`).

The cause is a race condition between the primary thread and a worker. A worker that is still looking for tasks when its region ends keeps a pointer to that region's task team. When the next region has fewer threads, the runtime removes the worker from the team without waiting for it, and later reuses the same task team for another region. The worker then steals a task through its old pointer, although it does not take part in that task's region.

It only goes wrong if the worker is descheduled for a whole region, from before the shrink until the task team receives new tasks. That makes it rare, and oversubscription makes it more likely.

```mermaid
sequenceDiagram
 participant P as Primary thread
    participant T as Task team T
 participant W as Worker W
    Note over P,W: Region R runs its tasks on task team T
    W->>T: looks for tasks, keeps a local pointer to T
    Note over P,W: Region R ends
    P->>W: reduce team size: th_task_team = NULL, W goes to the thread pool
    Note over P,T: New region R+2 reactivates T
    Note over W: W is still in the pool (th_team == NULL)
    Note over W: resumes
 W->>T: steals a task of region R+2 through the stale pointer
    Note over W: runs the task with th_task_team == NULL: SIGSEGV
```

The steps in the code (`main` at 319bd32d):

1. Worker W waits in the fork barrier inside `__kmp_execute_tasks_template()`. It reads `th_task_team` once into a local variable ([kmp_tasking.cpp:3016](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3016)) and checks it again only after it has run a task or found nothing to steal ([lines 3160](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3160) and [3210](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3210)).
2. The hot team shrinks, by `omp_set_num_threads()` ([kmp_runtime.cpp:2829-2831](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_runtime.cpp#L2829-L2831)) or by a smaller `num_threads` ([lines 5253-5264](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_runtime.cpp#L5253-L5264)). The primary thread sets W's `th_task_team` to NULL and returns W to the pool. Nothing waits for W to leave the template.
3. A team has two task teams and alternates between them ([kmp_tasking.cpp:3836-3847](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3836-L3847)). So T is active again two regions later, or in the very next region after `omp_set_num_threads(1)`.
4. W resumes, steals a task from T ([line 3113](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3113)) and runs it. At that point W is in one of two states:
   - **Still in the pool**, if region R+2 is also smaller than R (e.g. 10, 2, 4 threads). Both `th_team` and `th_task_team` are NULL.
   - **Re-added to the team**, if region R+2 is large again (e.g. 8, 4, 8 threads). The primary thread has set `th_team`, but W sets its own `th_task_team` only after it has left the steal loop and been released from the fork barrier, so it is still NULL.

   When the task releases a successor, `__kmp_push_task()` dereferences the NULL `th_task_team` ([lines 270](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L270) and [299](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L299)): SIGSEGV at address 0x98. In the first state, a task that creates a task crashes earlier, in `__kmp_task_alloc()` on the NULL `th_team`.

An instrumented runtime confirmed this sequence before every crash: the stolen task was created in region N, W had last been part of the team in region N-2, and both states occurred.

A change of the team size is required. At a constant size the next join barrier waits for W, so W cannot miss a region. Nothing in the path is architecture-specific, but I have only seen it on Apple silicon, in an application that changes the number of threads between calls.

## Reproducer

[libomp_stale_worker_after_shrink.c](https://github.com/user-attachments/files/34979437/libomp_stale_worker_after_shrink.c)

Each region runs a small task graph with `depend` clauses, then `omp_set_num_threads(1)` shrinks the hot team. The tasks are created inside `task if(0)` + `taskwait`, so #226812 cannot occur.

```
clang -O1 -g -fopenmp libomp_stale_worker_after_shrink.c -o repro
./repro 10 10000 & ./repro 10 10000 & wait      # two copies make it fail sooner
```

Observed (Apple M1 Pro, 10 cores, macOS 27.2, two copies at a time with 10 threads each, three rounds):

| runtime | result |
|----------------------------------|------------------------------------------|
| `main` at 319bd32d (Release)     | 6 of 6 runs SIGSEGV, after 1.2 to 15.6 s |
| Homebrew libomp 23.1.4           | 6 of 6 runs SIGSEGV, after 0.4 to 12 s   |
| `main` at 319bd32d + patch below | 6 of 6 runs pass (10000 regions each)    |

The crashing thread:

```
__kmp_push_task <- __kmp_release_deps <- __kmp_task_finish<false> <- __kmp_execute_tasks_64
<- kmp_flag_64::wait <- __kmp_hyper_barrier_release <- __kmp_fork_barrier <- __kmp_launch_thread
```

To make it fail within a second, add a `usleep(100)` before the `__kmp_steal_task()` call at line 3113, in 1 of 50 attempts. With that delay on `main`, every run with changing team sizes crashed (5 of 5 in each configuration: `num_threads` and `omp_set_num_threads()` shrinks, `priority` tasks, `OMP_WAIT_POLICY=passive`, `KMP_BLOCKTIME=1`, `KMP_HOT_TEAMS_MODE=1`). The only exception was the distributed barrier, whose resize already waits for the workers. The patched runtime passed every run, including with the delay moved to the entry of `__kmp_execute_tasks_template()`.

## Proposed fix

When the hot team shrinks, wait until each removed worker has left the tasking code before detaching it, as `__kmp_free_team()` already does before it frees a team that is not hot. A worker reports this through `th_reap_state`: it sets `KMP_NOT_SAFE_TO_REAP` when it enters `__kmp_execute_tasks_template()` ([kmp_tasking.cpp:3035](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_tasking.cpp#L3035)), and `KMP_SAFE_TO_REAP` in the barrier wait once its task team is gone or inactive ([kmp_wait_release.h:541-560](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_wait_release.h#L541-L560)). The patch moves the wait loop of `__kmp_free_team()` into a helper, `__kmp_wait_reapable()`, and calls it in both shrink paths before `th_task_team` is cleared:

```diff
--- a/openmp/runtime/src/kmp_runtime.cpp
+++ b/openmp/runtime/src/kmp_runtime.cpp
@@ -2780,6 +2780,46 @@
 control->next = thread->th.th_team->t.t_control_stack_top;
 thread->th.th_team->t.t_control_stack_top = control;
     }
+ }
+}
+
+// Wait until a thread that leaves a team has left the tasking code
+// (KMP_SAFE_TO_REAP). A thread can still be inside
+// __kmp_execute_tasks_template() with the team's task team in a local variable;
+// the task team is reused by a later region of a hot team and freed with a
+// team that is not hot, so the thread must be out of it first.
+static void __kmp_wait_reapable(kmp_info_t *th) {
+  volatile kmp_uint32 *state = &th->th.th_reap_state;
+  int spins = 0;
+  while (*state != KMP_SAFE_TO_REAP) {
+#if KMP_OS_WINDOWS
+    DWORD ecode;
+ if (!__kmp_is_thread_alive(th, &ecode)) {
+      *state = KMP_SAFE_TO_REAP; // reset the flag for dead thread
+      break;
+    }
+#endif
+    // th_sleep_loc is a pointer to volatile, not a volatile pointer: read it
+ // through a volatile access, otherwise the load can be hoisted out of this
+    // loop and a thread that falls asleep later is never woken.
+ if (*(void *volatile *)&th->th.th_sleep_loc)
+ __kmp_null_resume_wrapper(th);
+    if (++spins > 100) // the thread may be descheduled: give up the CPU
+      __kmp_yield();
+    else
+ KMP_CPU_PAUSE();
+  }
+}
+
+// Wake the threads [lo, hi) of a team that sleep before reaching
+// KMP_SAFE_TO_REAP, so that __kmp_wait_reapable() waits for them in parallel
+// rather than one after the other.
+static void __kmp_wake_unreapable(kmp_team_t *team, int lo, int hi) {
+  for (int f = lo; f < hi; f++) {
+    kmp_info_t *th = team->t.t_threads[f];
+    if (TCR_4(th->th.th_reap_state) != KMP_SAFE_TO_REAP &&
+        *(void *volatile *)&th->th.th_sleep_loc)
+      __kmp_null_resume_wrapper(th);
 }
 }
 
@@ -2820,10 +2860,13 @@ void __kmp_set_num_threads(...)
     if (__kmp_barrier_release_pattern[bs_forkjoin_barrier] == bp_dist_bar) {
 __kmp_resize_dist_barrier(hot_team, hot_team->t.t_nproc, new_nth);
     }
+ if (__kmp_tasking_mode != tskm_immediate_exec)
+ __kmp_wake_unreapable(hot_team, new_nth, hot_team->t.t_nproc);
     // Release the extra threads we don't need any more.
     for (f = new_nth; f < hot_team->t.t_nproc; f++) {
       KMP_DEBUG_ASSERT(hot_team->t.t_threads[f] != NULL);
       if (__kmp_tasking_mode != tskm_immediate_exec) {
+ __kmp_wait_reapable(hot_team->t.t_threads[f]);
         // When decreasing team size, threads no longer in the team should unref
         // task team.
         hot_team->t.t_threads[f]->th.th_task_team = NULL;
@@ -5247,9 +5290,11 @@ kmp_team_t *__kmp_allocate_team(...)
       // When decreasing team size, threads no longer in the team should
       // unref task team.
 if (__kmp_tasking_mode != tskm_immediate_exec) {
+ __kmp_wake_unreapable(team, new_nproc, team->t.t_nproc);
         for (f = new_nproc; f < team->t.t_nproc; f++) {
           kmp_info_t *th = team->t.t_threads[f];
           KMP_DEBUG_ASSERT(th);
+ __kmp_wait_reapable(th);
           th->th.th_task_team = NULL;
 }
       }
@@ -5670,22 +5715,7 @@ void __kmp_free_team(...)
       // Wait for threads to reach reapable state
       for (f = 1; f < team->t.t_nproc; ++f) {
         KMP_DEBUG_ASSERT(team->t.t_threads[f]);
-        kmp_info_t *th = team->t.t_threads[f];
-        volatile kmp_uint32 *state = &th->th.th_reap_state;
-        while (*state != KMP_SAFE_TO_REAP) {
-#if KMP_OS_WINDOWS
-          // On Windows a thread can be killed at any time, check this
-          DWORD ecode;
-          if (!__kmp_is_thread_alive(th, &ecode)) {
-            *state = KMP_SAFE_TO_REAP; // reset the flag for dead thread
-            break;
- }
-#endif
-          // first check if thread is sleeping
- if (th->th.th_sleep_loc)
-            __kmp_null_resume_wrapper(th);
- KMP_CPU_PAUSE();
-        }
+ __kmp_wait_reapable(team->t.t_threads[f]);
       }
 
       // Delete task teams
--- a/openmp/runtime/src/kmp_tasking.cpp
+++ b/openmp/runtime/src/kmp_tasking.cpp
@@ -3141,6 +3141,9 @@ static inline int __kmp_execute_tasks_template(...)
       }
 #endif /* USE_ITT_BUILD && USE_ITT_NOTIFY */
       __kmp_invoke_task(gtid, task, current_task);
+ // A wait inside the task (e.g. in a nested parallel region) can have set
+ // KMP_SAFE_TO_REAP; this thread is still in the tasking code.
+ thread->th.th_reap_state = KMP_NOT_SAFE_TO_REAP;
 #if USE_ITT_BUILD
 if (itt_sync_obj != NULL)
 __kmp_itt_task_finished(itt_sync_obj);
```

After the wait, the removed worker has left `__kmp_execute_tasks_template()`, and it cannot get back in with T: only the thread itself sets its `th_task_team` to a non-NULL value, and the template reads it again on entry. This also covers other fields that might go stale, like the template's cached `threads_data` array and `current_task`, which can be freed when a team later grows.

Three details:

- The helper yields after 100 spins. `KMP_CPU_PAUSE()` does nothing on AArch64, and the worker it waits for may be descheduled.
- `__kmp_wake_unreapable()` wakes all removed workers first, so that with `OMP_WAIT_POLICY=passive`, where a worker can sleep before it is safe to reap, the primary thread does not wake and wait for them one after the other.
- The template marks the thread as not safe to reap again after each task, because a nested parallel region inside the task can set it to safe.

The helper also fixes an existing hang in `__kmp_free_team()`. Its wait loop reads `th->th.th_sleep_loc` to wake a sleeping worker ([kmp_runtime.cpp:5685](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp_runtime.cpp#L5685)). The field is declared `volatile void *` ([kmp.h:2956](https://github.com/llvm/llvm-project/blob/319bd32d5276bb9936db4d8f80b66b507a2aa681/openmp/runtime/src/kmp.h#L2956)), a plain pointer to volatile data, so the compiler may load it once before the loop. Apple clang 21 does: when the field is NULL on entry, the loop it emits is `ldr w9, [x22, #0x20c]; cmp w9, #0x1; b.ne` back to the `ldr`, which never reads `th_sleep_loc` again. A worker that falls asleep after the loop has started, before it is safe to reap, is then never woken. With `KMP_HOT_TEAMS_MAX_LEVEL=0` and `OMP_WAIT_POLICY=passive`, a test program with tasks hung in 10 of 10 runs on `main` built with Apple clang 21, at constant and at changing team sizes, with the primary thread spinning in `__kmp_free_team()` and every worker asleep in `__kmp_fork_barrier()`. The Homebrew libomp did not hang and does re-read the field. The helper reads the field through a volatile access, and with the patch the same test passes.

Workarounds for users: `KMP_HOT_TEAMS_MAX_LEVEL=0` (but not together with `OMP_WAIT_POLICY=passive` on a runtime built with Apple clang, see above), or an explicit `#pragma omp barrier` at the end of each region that creates tasks.

## Related issues

- D50651 (a4a9c48c784c, 2018) described steps 1 and 2 and added the `current_task == NULL` check at the entry of the template. That only covers a worker interrupted before the check.
- #94260 and PR #95823 relaxed an assertion in `__kmp_steal_task()`, because a thread in the pool can still index the task team. That is a symptom of the same situation.
- #156741 and #176451 (open) report rare SIGSEGVs in `tasking/issue-94260-2.c`, a test that shrinks and regrows a team with tasks. I'm fairly certain that they are caused by the same issue and would be fixed by the proposed patch.
- PR #187267 (open) notes the same missing re-check in the steal loop for proxy tasks.

## Environment

LLVM `main`<truncated>Please see the issue for the entire body.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to