[OpenMP] Fix a race in task queue reallocation

[protze.joachim]

Summary

__kmp_realloc_task_deque implicitly assumes, that the task queue is full (ntasks == size), therefore tail = size in line 319.
I added an assertion to document this assumption.

The first check for a full queue is before the locking and might not hold when the lock is taken. So, we need to check again for this condition when we have the lock.

This fixes the issue for the simple reproducer provided by Raul on openmp-dev, but also my issue with a more complex code.

[AndreyChurbanov]

openmp/runtime/src/kmp_tasking.cpp

384–385

Move comment under the if.

3666–3670

Could you please add same check here as well. Though it is harder to reproduce the problem here, the pattern is the same - "get lock + realloc" without re-checking the size of deque under the lock.

[AndreyChurbanov]

Also may worth adding the test just in case.

[protze.joachim]

Addressed Andrey's comment.

I was thinking about a test. The problem I see is that this only manifests under rare circumstances or in complex code.
The best I could think of is adding additional assertions: (head + ntasks) & (size-1) == tail

[AndreyChurbanov]

LGTM

openmp/runtime/src/kmp_tasking.cpp

 
 // __kmp_realloc_task_deque:
 // Re-allocates a task deque for a particular thread, copies the content from
 // the old deque and adjusts the necessary data structures relating to the
 // deque. This operation must be done with the deque_lock being held
 static void __kmp_realloc_task_deque(kmp_info_t *thread,
                                      kmp_thread_data_t *thread_data) {
   kmp_int32 size = TASK_DEQUE_SIZE(thread_data->td);
+  KMP_DEBUG_ASSERT(TCR_4(thread_data->td.td_deque_ntasks) == size);
   kmp_int32 new_size = 2 * size;
 
   KE_TRACE(10, ("__kmp_realloc_task_deque: T#%d reallocating deque[from %d to "
                 "%d] for thread_data %p\n",
                 __kmp_gtid_from_thread(thread), size, new_size, thread_data));
 
   kmp_taskdata_t **new_deque =
       (kmp_taskdata_t **)__kmp_allocate(new_size * sizeof(kmp_taskdata_t *));
if (__kmp_enable_task_throttling &&
         __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
                               thread->th.th_current_task)) {
       KA_TRACE(20, ("__kmp_push_task: T#%d deque is full; returning "
                     "TASK_NOT_PUSHED for task %p\n",
                     gtid, taskdata));
       return TASK_NOT_PUSHED;
     } else {
       __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
       locked = 1;
+      if (TCR_4(thread_data->td.td_deque_ntasks) >=
+          TASK_DEQUE_SIZE(thread_data->td)) {
         // expand deque to push the task which is not allowed to execute
         __kmp_realloc_task_deque(thread, thread_data);
       }
     }
+  }
   // Lock the deque for the task push operation
   if (!locked) {
     __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
     // Need to recheck as we can get a proxy task from thread outside of OpenMP
     if (TCR_4(thread_data->td.td_deque_ntasks) >=
         TASK_DEQUE_SIZE(thread_data->td)) {
       if (__kmp_enable_task_throttling &&
           __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
KA_TRACE(
          taskdata, tid));
 
     // if this deque is bigger than the pass ratio give a chance to another
     // thread
     if (TASK_DEQUE_SIZE(thread_data->td) / INITIAL_TASK_DEQUE_SIZE >= pass)
       return result;
 
     __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
+    if (TCR_4(thread_data->td.td_deque_ntasks) >=
+        TASK_DEQUE_SIZE(thread_data->td)) {
+      // expand deque to push the task which is not allowed to execute
       __kmp_realloc_task_deque(thread, thread_data);
+    }
 
   } else {
 
     __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
 
     if (TCR_4(thread_data->td.td_deque_ntasks) >=
         TASK_DEQUE_SIZE(thread_data->td)) {
       KA_TRACE(30, ("__kmp_give_task: queue is full while giving task %p to "