drd/drd_barrier.c

   1 /*
   2   This file is part of drd, a thread error detector.
   3
   4   Copyright (C) 2006-2020 Bart Van Assche <bvanassche@acm.org>.
   5
   6   This program is free software; you can redistribute it and/or
   7   modify it under the terms of the GNU General Public License as
   8   published by the Free Software Foundation; either version 2 of the
   9   License, or (at your option) any later version.
  10
  11   This program is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14   General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, see <http://www.gnu.org/licenses/>.
  18
  19   The GNU General Public License is contained in the file COPYING.
  20 */
  21
  22
  23 #include "drd_barrier.h"
  24 #include "drd_clientobj.h"
  25 #include "drd_error.h"
  26 #include "drd_suppression.h"
  27 #include "pub_tool_errormgr.h"    // VG_(maybe_record_error)()
  28 #include "pub_tool_libcassert.h"  // tl_assert()
  29 #include "pub_tool_libcprint.h"   // VG_(printf)()
  30 #include "pub_tool_machine.h"     // VG_(get_IP)()
  31 #include "pub_tool_mallocfree.h"  // VG_(malloc)(), VG_(free)()
  32 #include "pub_tool_oset.h"
  33 #include "pub_tool_threadstate.h" // VG_(get_running_tid)()
  34
  35
  36 /* Type definitions. */
  37
  38 /** Information associated with one thread participating in a barrier. */
  39 struct barrier_thread_info
  40 {
  41    UWord       tid;           // A DrdThreadId declared as UWord because
  42                               // this member variable is the key of an OSet.
  43    Segment*    sg;            // Segment of the last pthread_barrier() call
  44                               // by thread tid.
  45    Segment*    post_wait_sg;  // Segment created after *_barrier_wait() finished
  46    ExeContext* wait_call_ctxt;// call stack for *_barrier_wait() call.
  47    Bool       thread_finished;// Whether thread 'tid' has finished.
  48 };
  49
  50
  51 /* Local functions. */
  52
  53 static void barrier_cleanup(struct barrier_info* p);
  54 static void barrier_delete_thread(struct barrier_info* const p,
  55                                   const DrdThreadId tid);
  56 static const HChar* barrier_get_typename(struct barrier_info* const p);
  57 static const HChar* barrier_type_name(const BarrierT bt);
  58 static
  59 void barrier_report_wait_delete_race(const struct barrier_info* const p,
  60                                      const struct barrier_thread_info* const q);
  61
  62
  63 /* Local variables. */
  64
  65 static Bool  s_trace_barrier = False;
  66 static ULong s_barrier_segment_creation_count;
  67
  68
  69 /* Function definitions. */
  70
  71 void DRD_(barrier_set_trace)(const Bool trace_barrier)
  72 {
  73    s_trace_barrier = trace_barrier;
  74 }
  75
  76 /**
  77  * Initialize the structure *p with the specified thread ID and iteration
  78  * information.
  79  */
  80 static
  81 void DRD_(barrier_thread_initialize)(struct barrier_thread_info* const p,
  82                                      const DrdThreadId tid)
  83 {
  84    p->tid             = tid;
  85    p->sg              = NULL;
  86    p->post_wait_sg    = 0;
  87    p->wait_call_ctxt  = 0;
  88    p->thread_finished = False;
  89 }
  90
  91 /**
  92  * Deallocate the memory that is owned by members of
  93  * struct barrier_thread_info.
  94  */
  95 static void DRD_(barrier_thread_destroy)(struct barrier_thread_info* const p)
  96 {
  97    tl_assert(p);
  98    DRD_(sg_put)(p->sg);
  99    DRD_(sg_put)(p->post_wait_sg);
 100 }
 101
 102 /**
 103  * Initialize the structure *p with the specified client-side barrier address,
 104  * barrier object size and number of participants in each barrier.
 105  */
 106 static
 107 void DRD_(barrier_initialize)(struct barrier_info* const p,
 108                               const Addr barrier,
 109                               const BarrierT barrier_type,
 110                               const Word count)
 111 {
 112    int i;
 113
 114    tl_assert(barrier != 0);
 115    tl_assert(barrier_type == pthread_barrier || barrier_type == gomp_barrier);
 116    tl_assert(p->a1 == barrier);
 117
 118    p->cleanup           = (void(*)(DrdClientobj*))barrier_cleanup;
 119    p->delete_thread
 120       = (void(*)(DrdClientobj*, DrdThreadId))barrier_delete_thread;
 121    p->barrier_type      = barrier_type;
 122    p->count             = count;
 123    p->pre_iteration     = 0;
 124    p->post_iteration    = 0;
 125    p->pre_waiters_left  = count;
 126    p->post_waiters_left = count;
 127
 128    tl_assert(sizeof(((struct barrier_thread_info*)0)->tid) == sizeof(Word));
 129    tl_assert(sizeof(((struct barrier_thread_info*)0)->tid)
 130              >= sizeof(DrdThreadId));
 131    for (i = 0; i < 2; i++) {
 132       p->oset[i] = VG_(OSetGen_Create)(0, 0, VG_(malloc), "drd.barrier.bi.1",
 133                                        VG_(free));
 134    }
 135 }
 136
 137 /**
 138  * Deallocate the memory owned by the struct barrier_info object and also
 139  * all the nodes in the OSet p->oset.
 140  *
 141  * Called by clientobj_destroy().
 142  */
 143 static void barrier_cleanup(struct barrier_info* p)
 144 {
 145    struct barrier_thread_info* q;
 146    Segment* latest_sg = 0;
 147    OSet* oset;
 148    int i;
 149
 150    tl_assert(p);
 151
 152    DRD_(thread_get_latest_segment)(&latest_sg, DRD_(thread_get_running_tid)());
 153    tl_assert(latest_sg);
 154
 155    if (p->pre_waiters_left != p->count) {
 156       BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), p->a1, 0, 0 };
 157       VG_(maybe_record_error)(VG_(get_running_tid)(),
 158                               BarrierErr,
 159                               VG_(get_IP)(VG_(get_running_tid)()),
 160                               "Destruction of barrier that is being waited"
 161                               " upon",
 162                               &bei);
 163    } else {
 164       oset = p->oset[1 - (p->pre_iteration & 1)];
 165       VG_(OSetGen_ResetIter)(oset);
 166       for ( ; (q = VG_(OSetGen_Next)(oset)) != 0; ) {
 167          if (q->post_wait_sg && !DRD_(vc_lte)(&q->post_wait_sg->vc,
 168                                               &latest_sg->vc))
 169          {
 170             barrier_report_wait_delete_race(p, q);
 171          }
 172          DRD_(barrier_thread_destroy)(q);
 173       }
 174    }
 175
 176    for (i = 0; i < 2; i++) {
 177       VG_(OSetGen_Destroy)(p->oset[i]);
 178       p->oset[i] = NULL;
 179    }
 180
 181    DRD_(sg_put)(latest_sg);
 182 }
 183
 184 /**
 185  * Look up the client-side barrier address barrier in s_barrier[]. If not
 186  * found, add it.
 187  */
 188 static
 189 struct barrier_info*
 190 DRD_(barrier_get_or_allocate)(const Addr barrier,
 191                               const BarrierT barrier_type, const Word count)
 192 {
 193    struct barrier_info *p;
 194
 195    tl_assert(barrier_type == pthread_barrier || barrier_type == gomp_barrier);
 196
 197    tl_assert(offsetof(DrdClientobj, barrier) == 0);
 198    p = &(DRD_(clientobj_get)(barrier, ClientBarrier)->barrier);
 199    if (p == 0)
 200    {
 201       p = &(DRD_(clientobj_add)(barrier, ClientBarrier)->barrier);
 202       DRD_(barrier_initialize)(p, barrier, barrier_type, count);
 203    }
 204    return p;
 205 }
 206
 207 /**
 208  * Look up the address of the struct barrier_info associated with the
 209  * client-side barrier object.
 210  */
 211 static struct barrier_info* DRD_(barrier_get)(const Addr barrier)
 212 {
 213    tl_assert(offsetof(DrdClientobj, barrier) == 0);
 214    return &(DRD_(clientobj_get)(barrier, ClientBarrier)->barrier);
 215 }
 216
 217 /**
 218  * Initialize a barrier with given client address, barrier type and number of
 219  * participants. The 'reinitialization' argument indicates whether a barrier
 220  * object is being initialized or reinitialized.
 221  *
 222  * Called before pthread_barrier_init().
 223  */
 224 void DRD_(barrier_init)(const Addr barrier,
 225                         const BarrierT barrier_type, const Word count,
 226                         const Bool reinitialization)
 227 {
 228    struct barrier_info* p;
 229
 230    tl_assert(barrier_type == pthread_barrier || barrier_type == gomp_barrier);
 231
 232    if (count == 0)
 233    {
 234       BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), barrier, 0, 0 };
 235       VG_(maybe_record_error)(VG_(get_running_tid)(),
 236                               BarrierErr,
 237                               VG_(get_IP)(VG_(get_running_tid)()),
 238                               "pthread_barrier_init: 'count' argument is zero",
 239                               &bei);
 240    }
 241
 242    if (! reinitialization && barrier_type == pthread_barrier)
 243    {
 244       p = DRD_(barrier_get)(barrier);
 245       if (p)
 246       {
 247          BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), barrier, 0, 0 };
 248          VG_(maybe_record_error)(VG_(get_running_tid)(),
 249                                  BarrierErr,
 250                                  VG_(get_IP)(VG_(get_running_tid)()),
 251                                  "Barrier reinitialization",
 252                                  &bei);
 253       }
 254    }
 255
 256    p = DRD_(barrier_get_or_allocate)(barrier, barrier_type, count);
 257
 258    if (s_trace_barrier) {
 259       if (reinitialization)
 260          DRD_(trace_msg)("[%u] barrier_reinit    %s 0x%lx count %ld -> %ld",
 261                          DRD_(thread_get_running_tid)(),
 262                          barrier_get_typename(p), barrier, p->count, count);
 263       else
 264          DRD_(trace_msg)("[%u] barrier_init      %s 0x%lx",
 265                          DRD_(thread_get_running_tid)(),
 266                          barrier_get_typename(p),
 267                          barrier);
 268    }
 269
 270    if (reinitialization && p->count != count)
 271    {
 272       if (p->pre_waiters_left != p->count || p->post_waiters_left != p->count)
 273       {
 274          BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), p->a1, 0, 0 };
 275          VG_(maybe_record_error)(VG_(get_running_tid)(),
 276                                  BarrierErr,
 277                                  VG_(get_IP)(VG_(get_running_tid)()),
 278                                  "Reinitialization of barrier with active"
 279                                  " waiters",
 280                                  &bei);
 281       }
 282       p->count = count;
 283    }
 284 }
 285
 286 /** Called after pthread_barrier_destroy() / gomp_barrier_destroy(). */
 287 void DRD_(barrier_destroy)(const Addr barrier, const BarrierT barrier_type)
 288 {
 289    struct barrier_info* p;
 290
 291    p = DRD_(barrier_get)(barrier);
 292
 293    if (s_trace_barrier)
 294       DRD_(trace_msg)("[%u] barrier_destroy   %s 0x%lx",
 295                       DRD_(thread_get_running_tid)(),
 296                       barrier_get_typename(p), barrier);
 297
 298    if (p == 0)
 299    {
 300       GenericErrInfo GEI = {
 301          .tid = DRD_(thread_get_running_tid)(),
 302          .addr = barrier,
 303       };
 304       VG_(maybe_record_error)(VG_(get_running_tid)(),
 305                               GenericErr,
 306                               VG_(get_IP)(VG_(get_running_tid)()),
 307                               "Not a barrier",
 308                               &GEI);
 309       return;
 310    }
 311
 312    if (p->pre_waiters_left != p->count || p->post_waiters_left != p->count)
 313    {
 314       BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), p->a1, 0, 0 };
 315       VG_(maybe_record_error)(VG_(get_running_tid)(),
 316                               BarrierErr,
 317                               VG_(get_IP)(VG_(get_running_tid)()),
 318                               "Destruction of a barrier with active waiters",
 319                               &bei);
 320    }
 321
 322    DRD_(clientobj_remove)(p->a1, ClientBarrier);
 323 }
 324
 325 /** Called before pthread_barrier_wait() / gomp_barrier_wait(). */
 326 void DRD_(barrier_pre_wait)(const DrdThreadId tid, const Addr barrier,
 327                             const BarrierT barrier_type)
 328 {
 329    struct barrier_info* p;
 330    struct barrier_thread_info* q;
 331    const UWord word_tid = tid;
 332    OSet* oset;
 333
 334    p = DRD_(barrier_get)(barrier);
 335    if (p == 0 && barrier_type == gomp_barrier) {
 336       /*
 337        * gomp_barrier_wait() call has been intercepted but gomp_barrier_init()
 338        * not. The only cause I know of that can trigger this is that libgomp.so
 339        * has been compiled with --enable-linux-futex.
 340        */
 341       BarrierErrInfo bei = { DRD_(thread_get_running_tid)(), 0, 0, 0 };
 342       VG_(maybe_record_error)(VG_(get_running_tid)(),
 343                               BarrierErr,
 344                               VG_(get_IP)(VG_(get_running_tid)()),
 345                               "Please verify whether gcc has been configured"
 346                               " with option --disable-linux-futex. See also"
 347                               " the section about OpenMP in the DRD manual.",
 348                               &bei);
 349    }
 350    tl_assert(p);
 351
 352    if (s_trace_barrier)
 353       DRD_(trace_msg)("[%u] barrier_pre_wait  %s 0x%lx iteration %ld",
 354                       DRD_(thread_get_running_tid)(),
 355                       barrier_get_typename(p), barrier, p->pre_iteration);
 356
 357    /* Clean up nodes associated with finished threads. */
 358    oset = p->oset[p->pre_iteration & 1];
 359    tl_assert(oset);
 360    VG_(OSetGen_ResetIter)(oset);
 361    for ( ; (q = VG_(OSetGen_Next)(oset)) != 0; ) {
 362       if (q->thread_finished) {
 363          void* r = VG_(OSetGen_Remove)(oset, &q->tid);
 364          tl_assert(r == q);
 365          DRD_(barrier_thread_destroy)(q);
 366          VG_(OSetGen_FreeNode)(oset, q);
 367          VG_(OSetGen_ResetIterAt)(oset, &word_tid);
 368       }
 369    }
 370    /* Allocate the per-thread data structure if necessary. */
 371    q = VG_(OSetGen_Lookup)(oset, &word_tid);
 372    if (q == NULL) {
 373       q = VG_(OSetGen_AllocNode)(oset, sizeof(*q));
 374       DRD_(barrier_thread_initialize)(q, tid);
 375       VG_(OSetGen_Insert)(oset, q);
 376       tl_assert(VG_(OSetGen_Lookup)(oset, &word_tid) == q);
 377    }
 378
 379    /* Record *_barrier_wait() call context. */
 380    q->wait_call_ctxt = VG_(record_ExeContext)(VG_(get_running_tid)(), 0);
 381
 382    /*
 383     * Store a pointer to the latest segment of the current thread in the
 384     * per-thread data structure.
 385     */
 386    DRD_(thread_get_latest_segment)(&q->sg, tid);
 387
 388    /*
 389     * If the same number of threads as the barrier count indicates have
 390     * called the pre *_barrier_wait() wrapper, toggle p->pre_iteration and
 391     * reset the p->pre_waiters_left counter.
 392     */
 393    if (--p->pre_waiters_left <= 0)
 394    {
 395       p->pre_iteration++;
 396       p->pre_waiters_left = p->count;
 397    }
 398 }
 399
 400 /** Called after pthread_barrier_wait() / gomp_barrier_wait(). */
 401 void DRD_(barrier_post_wait)(const DrdThreadId tid, const Addr barrier,
 402                              const BarrierT barrier_type, const Bool waited,
 403                              const Bool serializing)
 404 {
 405    struct barrier_info* p;
 406    const UWord word_tid = tid;
 407    struct barrier_thread_info* q;
 408    struct barrier_thread_info* r;
 409    OSet* oset;
 410
 411    p = DRD_(barrier_get)(barrier);
 412
 413    if (s_trace_barrier)
 414       DRD_(trace_msg)("[%u] barrier_post_wait %s 0x%lx iteration %ld%s",
 415                       tid, p ? barrier_get_typename(p) : "(?)",
 416                       barrier, p ? p->post_iteration : -1,
 417                       serializing ? " (serializing)" : "");
 418
 419    /*
 420     * If p == 0, this means that the barrier has been destroyed after
 421     * *_barrier_wait() returned and before this function was called. Just
 422     * return in that case -- race conditions between *_barrier_wait()
 423     * and *_barrier_destroy() are detected by the *_barrier_destroy() wrapper.
 424     */
 425    if (p == 0)
 426       return;
 427
 428    /* If the *_barrier_wait() call returned an error code, exit. */
 429    if (! waited)
 430       return;
 431
 432    oset = p->oset[p->post_iteration & 1];
 433    q = VG_(OSetGen_Lookup)(oset, &word_tid);
 434    if (q == NULL) {
 435       q = VG_(OSetGen_AllocNode)(oset, sizeof(*q));
 436       DRD_(barrier_thread_initialize)(q, tid);
 437       VG_(OSetGen_Insert)(oset, q);
 438       tl_assert(VG_(OSetGen_Lookup)(oset, &word_tid) == q);
 439       DRD_(thread_get_latest_segment)(&q->sg, tid);
 440    }
 441
 442    /* Create a new segment and store a pointer to that segment. */
 443    DRD_(thread_new_segment)(tid);
 444    DRD_(thread_get_latest_segment)(&q->post_wait_sg, tid);
 445    s_barrier_segment_creation_count++;
 446
 447    /*
 448     * Combine all vector clocks that were stored in the pre_barrier_wait
 449     * wrapper with the vector clock of the current thread.
 450     */
 451    {
 452       VectorClock old_vc;
 453
 454       DRD_(vc_copy)(&old_vc, DRD_(thread_get_vc)(tid));
 455       VG_(OSetGen_ResetIter)(oset);
 456       for ( ; (r = VG_(OSetGen_Next)(oset)) != 0; )
 457       {
 458          if (r != q)
 459          {
 460             tl_assert(r->sg);
 461             DRD_(vc_combine)(DRD_(thread_get_vc)(tid), &r->sg->vc);
 462          }
 463       }
 464       DRD_(thread_update_conflict_set)(tid, &old_vc);
 465       DRD_(vc_cleanup)(&old_vc);
 466    }
 467
 468    /*
 469     * If the same number of threads as the barrier count indicates have
 470     * called the post *_barrier_wait() wrapper, toggle p->post_iteration and
 471     * reset the p->post_waiters_left counter.
 472     */
 473    if (--p->post_waiters_left <= 0)
 474    {
 475       p->post_iteration++;
 476       p->post_waiters_left = p->count;
 477    }
 478 }
 479
 480 /** Called when thread tid stops to exist. */
 481 static void barrier_delete_thread(struct barrier_info* const p,
 482                                   const DrdThreadId tid)
 483 {
 484    struct barrier_thread_info* q;
 485    const UWord word_tid = tid;
 486    int i;
 487
 488    for (i = 0; i < 2; i++) {
 489       q = VG_(OSetGen_Lookup)(p->oset[i], &word_tid);
 490       if (q)
 491          q->thread_finished = True;
 492    }
 493 }
 494
 495 /**
 496  * Report that *_barrier_destroy() has been called but that this call was
 497  * not synchronized with the last *_barrier_wait() call on the same barrier.
 498  *
 499  * This topic has been discussed extensively on comp.programming.threads
 500  * (February 3, 2009). See also
 501  * <a href="http://groups.google.com/group/comp.programming.threads/browse_thread/thread/4f65535d6192aa50/a5f4bf1e3b437c4d">Immediately destroying pthread barriers</a>.
 502  */
 503 static
 504 void barrier_report_wait_delete_race(const struct barrier_info* const p,
 505                                      const struct barrier_thread_info* const q)
 506 {
 507    tl_assert(p);
 508    tl_assert(q);
 509
 510    {
 511       BarrierErrInfo bei
 512          = { DRD_(thread_get_running_tid)(), p->a1, q->tid, q->wait_call_ctxt };
 513       VG_(maybe_record_error)(VG_(get_running_tid)(),
 514                               BarrierErr,
 515                               VG_(get_IP)(VG_(get_running_tid)()),
 516                               "Destruction of barrier not synchronized with"
 517                               " barrier wait call",
 518                               &bei);
 519    }
 520 }
 521
 522 static const HChar* barrier_get_typename(struct barrier_info* const p)
 523 {
 524    tl_assert(p);
 525
 526    return barrier_type_name(p->barrier_type);
 527 }
 528
 529 static const HChar* barrier_type_name(const BarrierT bt)
 530 {
 531    switch (bt)
 532    {
 533    case pthread_barrier:
 534       return "pthread barrier";
 535    case gomp_barrier:
 536       return "gomp barrier";
 537    }
 538    return "?";
 539 }
 540
 541 ULong DRD_(get_barrier_segment_creation_count)(void)
 542 {
 543    return s_barrier_segment_creation_count;
 544 }