[OpenMP] Fix hierarchical barrier

[tlwilmar]

Summary

Hierarchical barrier is an experimental barrier algorithm that uses aspects of machine hierarchy to define the barrier tree structure. This patch fixes offset calculation in hierarchical barrier. The offset is used to store info on a flag about sleeping threads waiting on a location stored in the flag. This commit also fixes a potential deadlock in hierarchical barrier when using infinite blocktime by adjusting the offset value of leaf kids so that it matches the value of leaf state. It also adds testing of default barriers with infinite blocktime, and also tests hierarchical barrier algorithm with both default and infinite blocktime.

Patch by Terry Wilmarth and Nawrin Sultana.

[Nawrin]

LGTM

openmp/runtime/src/kmp_barrier.cpp

if (!KMP_MASTER_TID(
       kmp_uint32 d = 0;
       while (d < thr_bar->depth) { // find parent based on level of thread in
         // hierarchy, and note level
         kmp_uint32 rem;
         if (d == thr_bar->depth - 2) { // reached level right below the master
           thr_bar->parent_tid = 0;
           thr_bar->my_level = d;
           break;
-        } else if ((rem = tid % thr_bar->skip_per_level[d + 1]) !=
-                   0) { // TODO: can we make this op faster?
+        } else if ((rem = tid % thr_bar->skip_per_level[d + 1]) != 0) {
+          // TODO: can we make the above op faster?
           // thread is not a subtree root at next level, so this is max
           thr_bar->parent_tid = tid - rem;
           thr_bar->my_level = d;
           break;
         }
         ++d;
       }
     }
-    __kmp_type_convert(7 - (tid - thr_bar->parent_tid - 1), &(thr_bar->offset));
+    __kmp_type_convert(7 - ((tid - thr_bar->parent_tid) /
+                            (thr_bar->skip_per_level[thr_bar->my_level])),
+                       &(thr_bar->offset));
     thr_bar->old_tid = tid;
     thr_bar->wait_flag = KMP_BARRIER_NOT_WAITING;
     thr_bar->team = team;
     thr_bar->parent_bar =
         &team->t.t_threads[thr_bar->parent_tid]->th.th_bar[bt].bb;
   }
   if (uninitialized || team_changed || tid_changed) {
     thr_bar->team = team;
if (thr_bar->my_level || __kmp_dflt_blocktime != KMP_MAX_BLOCKTIME ||
       // flag; release it
       ANNOTATE_BARRIER_BEGIN(this_thr);
       kmp_flag_64<> flag(&thr_bar->b_arrived,
                          other_threads[thr_bar->parent_tid]);
       flag.release();
     } else {
       // Leaf does special release on "offset" bits of parent's b_arrived flag
       thr_bar->b_arrived = team->t.t_bar[bt].b_arrived + KMP_BARRIER_STATE_BUMP;
-      kmp_flag_oncore flag(&thr_bar->parent_bar->b_arrived, thr_bar->offset);
+      kmp_flag_oncore flag(&thr_bar->parent_bar->b_arrived,
+                           thr_bar->offset + 1);
       flag.set_waiter(other_threads[thr_bar->parent_tid]);
       flag.release();
     }
   } else { // Master thread needs to update the team's b_arrived value
     team->t.t_bar[bt].b_arrived = new_state;
     KA_TRACE(20, ("__kmp_hierarchical_barrier_gather: T#%d(%d:%d) set team %d "
                   "arrived(%p) = %llu\n",
                   gtid, team->t.t_id, tid, team->t.t_id,
if (!thr_bar->use_oncore_barrier ||
       ANNOTATE_BARRIER_END(this_thr);
       TCW_8(thr_bar->b_go,
             KMP_INIT_BARRIER_STATE); // Reset my b_go flag for next time
     } else { // Thread barrier data is initialized, this is a leaf, blocktime is
       // infinite, not nested
       // Wait on my "offset" bits on parent's b_go flag
       thr_bar->wait_flag = KMP_BARRIER_PARENT_FLAG;
       kmp_flag_oncore flag(&thr_bar->parent_bar->b_go, KMP_BARRIER_STATE_BUMP,
-                           thr_bar->offset, bt,
+                           thr_bar->offset + 1, bt,
                            this_thr USE_ITT_BUILD_ARG(itt_sync_obj));
       flag.wait(this_thr, TRUE);
       if (thr_bar->wait_flag ==
           KMP_BARRIER_SWITCHING) { // Thread was switched to own b_go
         TCW_8(thr_bar->b_go,
               KMP_INIT_BARRIER_STATE); // Reset my b_go flag for next time
       } else { // Reset my bits on parent's b_go flag
         (RCAST(volatile char *,
-               &(thr_bar->parent_bar->b_go)))[thr_bar->offset] = 0;
+               &(thr_bar->parent_bar->b_go)))[thr_bar->offset + 1] = 0;
       }
     }
     thr_bar->wait_flag = KMP_BARRIER_NOT_WAITING;
     // Early exit for reaping threads releasing forkjoin barrier
     if (bt == bs_forkjoin_barrier && TCR_4(__kmp_global.g.g_done))
       return;
     // The worker thread may now assume that the team is valid.
     team = __kmp_threads[gtid]->th.th_team;

openmp/runtime/test/barrier/omp_barrier.c

 // RUN: %libomp-compile-and-run
+// RUN: %libomp-compile && env KMP_BLOCKTIME=infinite %libomp-run
+// RUN: %libomp-compile && env KMP_PLAIN_BARRIER_PATTERN='hierarchical,hierarchical' KMP_FORKJOIN_BARRIER_PATTERN='hierarchical,hierarchical' %libomp-run
+// RUN: %libomp-compile && env KMP_BLOCKTIME=infinite KMP_PLAIN_BARRIER_PATTERN='hierarchical,hierarchical' KMP_FORKJOIN_BARRIER_PATTERN='hierarchical,hierarchical' %libomp-run
 #include <stdio.h>
 #include "omp_testsuite.h"
 #include "omp_my_sleep.h"
 
 int test_omp_barrier()
 {
   int result1;
   int result2;