[OpenMP] Fix deadlock for detachable task with child tasks

[protze.joachim]

Summary

This patch fixes https://bugs.llvm.org/show_bug.cgi?id=49066.

For detachable tasks, the assumption breaks that the proxy task cannot have remaining child tasks when the proxy completes.
In stead of increment/decrement the incomplete task count, a high order bit is flipped to mark and wait for the incomplete proxy task.

[protze.joachim]

I still have issues with this patch and I think, it's not the right solution. I wonder, why __kmp_bottom_half_finish_proxy is necessary at all - see the inline comment.
If it's necessary, I tend to change the "imaginary children" code to td_incomplete_child_tasks |= 0x4000000 and td_incomplete_child_tasks &= !0x4000000. Then wait while (td_incomplete_child_tasks & 0x4000000) != 0

Even with that change, for a testcase creating thousands of tasks, the execution gets stuck at some point with no task being executed and all threads trying to steal.

@AndreyChurbanov is there any good way to find all remaining tasks with open dependencies in a debugger?

openmp/runtime/src/kmp_tasking.cpp

3874–3876

Why can't this be part of __kmp_bottom_half_finish_proxy? Is the proxy task supposed to be completed, before the __kmp_bottom_half_finish_proxy task executes?

[protze.joachim]

The initial fix broke in some cases. I missed the difference between the incomplete and allocated task counters.
This updated patch should fix the issue, but I still run into starvation issues. I'll attach another reproducer in the bug.

[AndreyChurbanov]

openmp/runtime/src/kmp_tasking.cpp

3879

This statement zeroes the taskdata->td_incomplete_child_tasks.
Proper operation would be to clear the set bit only, that is

KMP_ATOMIC_AND(&taskdata->td_incomplete_child_tasks, PROXY_TASK_FLAG-1);

Once the PROXY_TASK_FLAG is the degree of 2, minus one should fill all bits but the highest one.

[protze.joachim]

openmp/runtime/src/kmp_tasking.cpp

3879

Good catch. This might explain the issues I saw with this patch.

I intended to make this ~PROXY_TASK_FLAG confused logical and bit-wise not.

[protze.joachim]

Address the issue raised by @AndreyChurbanov

Also rebased to current main

[AndreyChurbanov]

LGTM

[protze.joachim]

As a result of testing with different compilers before pushing, I added support-level information to the testcase following other detached task tests and removed the event from firstprivate clause, because gcc thinks that it is illegal.

openmp/runtime/src/kmp_tasking.cpp

KA_TRACE(30, ("__kmp_give_task: successfully gave task %p to thread %d.\n",
                 taskdata, tid));
 
 release_and_exit:
   __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
 
   return result;
 }
 
+#define PROXY_TASK_FLAG 0x40000000
 /* The finish of the proxy tasks is divided in two pieces:
     - the top half is the one that can be done from a thread outside the team
     - the bottom half must be run from a thread within the team
 
    In order to run the bottom half the task gets queued back into one of the
    threads of the team. Once the td_incomplete_child_task counter of the parent
    is decremented the threads can leave the barriers. So, the bottom half needs
    to be queued before the counter is decremented. The top half is therefore
static void __kmp_first_top_half_finish_proxy(kmp_taskdata_t *taskdata) {
 
   taskdata->td_flags.complete = 1; // mark the task as completed
 
   if (taskdata->td_taskgroup)
     KMP_ATOMIC_DEC(&taskdata->td_taskgroup->count);
 
   // Create an imaginary children for this task so the bottom half cannot
   // release the task before we have completed the second top half
-  KMP_ATOMIC_INC(&taskdata->td_incomplete_child_tasks);
+  KMP_ATOMIC_OR(&taskdata->td_incomplete_child_tasks, PROXY_TASK_FLAG);
 }
 
 static void __kmp_second_top_half_finish_proxy(kmp_taskdata_t *taskdata) {
   kmp_int32 children = 0;
 
   // Predecrement simulated by "- 1" calculation
   children =
       KMP_ATOMIC_DEC(&taskdata->td_parent->td_incomplete_child_tasks) - 1;
   KMP_DEBUG_ASSERT(children >= 0);
 
   // Remove the imaginary children
-  KMP_ATOMIC_DEC(&taskdata->td_incomplete_child_tasks);
+  KMP_ATOMIC_AND(&taskdata->td_incomplete_child_tasks, ~PROXY_TASK_FLAG);
 }
 
 static void __kmp_bottom_half_finish_proxy(kmp_int32 gtid, kmp_task_t *ptask) {
   kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
   kmp_info_t *thread = __kmp_threads[gtid];
 
   KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
   KMP_DEBUG_ASSERT(taskdata->td_flags.complete ==
                    1); // top half must run before bottom half
 
   // We need to wait to make sure the top half is finished
   // Spinning here should be ok as this should happen quickly
-  while (KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks) > 0)
+  while ((KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks) &
+          PROXY_TASK_FLAG) > 0)
     ;
 
   __kmp_release_deps(gtid, taskdata);
   __kmp_free_task_and_ancestors(gtid, taskdata, thread);
 }
 
 /*!
 @ingroup TASKING

openmp/runtime/test/tasking/detach_nested_task.c

+// RUN: %libomp-compile-and-run
+
+// Checked gcc 10.1 still does not support detach clause on task construct.
+// UNSUPPORTED: gcc-4, gcc-5, gcc-6, gcc-7, gcc-8, gcc-9, gcc-10
+// gcc 11 introduced detach clause, but gomp interface in libomp has no support
+// XFAIL: gcc-11, gcc-12
+// clang supports detach clause since version 11.
+// UNSUPPORTED: clang-10, clang-9, clang-8, clang-7
+// icc compiler does not support detach clause.
+// UNSUPPORTED: icc
+
+// The outer detachable task creates multiple child tasks with dependencies
+// when the last inner task incremented ret, the task calls omp_fulfill_event
+// to release the outer task.
+
+#include <omp.h>
+#include <stdio.h>
+
+int *buf;
+
+int foo(int n)
+{
+  int ret = 0;
+  for (int i = 0; i < n; ++i) {
+    omp_event_handle_t event;
+    #pragma omp task detach(event) firstprivate(i,n) shared(ret) default(none)
+    {
+      for (int j = 0; j < n; ++j) {
+        #pragma omp task firstprivate(event,i,j,n) shared(ret) default(none) depend(out:ret)
+        {
+          //printf("Task %i, %i: %i\n", i, j, omp_get_thread_num());
+          #pragma omp atomic
+            ret++;
+#if _OPENMP
+          if (j == n-1) {
+            //printf("Task %i, %i: omp_fulfill_event()\n", i, j);
+            omp_fulfill_event(event);
+          }
+#endif
+        }
+      }
+    }
+  }
+  // the taskwait only guarantees the outer tasks to complete.
+  #pragma omp taskwait
+
+  return ret;
+}
+
+
+int main()
+{
+  int ret;
+#pragma omp parallel
+#pragma omp master
+  {
+    ret = foo(8);
+  }
+  printf("%i\n", ret);
+  //CHECK: 64
+  return 0;
+}