drd/drd_vc.h

   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 #ifndef __DRD_VC_H
  24 #define __DRD_VC_H
  25
  26
  27 /*
  28  * DRD vector clock implementation:
  29  * - One counter per thread.
  30  * - A vector clock is implemented as multiple pairs of (thread id, counter).
  31  * - Pairs are stored in an array sorted by thread id.
  32  *
  33  * Semantics:
  34  * - Each time a thread performs an action that implies an ordering between
  35  *   intra-thread events, the counter of that thread is incremented.
  36  * - Vector clocks are compared by comparing all counters of all threads.
  37  * - When a thread synchronization action is performed that guarantees that
  38  *   new actions of the current thread are executed after the actions of the
  39  *   other thread, the vector clock of the synchronization object and the
  40  *   current thread are combined (by taking the component-wise maximum).
  41  * - A vector clock is incremented during actions such as
  42  *   pthread_create(), pthread_mutex_unlock(), sem_post(). (Actions where
  43  *   an inter-thread ordering "arrow" starts).
  44  */
  45
  46
  47 #include "pub_tool_basics.h"     /* Addr, SizeT */
  48 #include "drd_basics.h"          /* DrdThreadId */
  49 #include "pub_tool_libcassert.h" /* tl_assert() */
  50
  51
  52 #define VC_PREALLOCATED 8
  53
  54
  55 /** Vector clock element. */
  56 typedef struct
  57 {
  58    DrdThreadId threadid;
  59    UInt        count;
  60 } VCElem;
  61
  62 typedef struct
  63 {
  64    unsigned capacity; /**< number of elements allocated for array vc. */
  65    unsigned size;     /**< number of elements used of array vc. */
  66    VCElem*  vc;       /**< vector clock elements. */
  67    VCElem   preallocated[VC_PREALLOCATED];
  68 } VectorClock;
  69
  70
  71 void DRD_(vc_init)(VectorClock* const vc,
  72                    const VCElem* const vcelem,
  73                    const unsigned size);
  74 void DRD_(vc_cleanup)(VectorClock* const vc);
  75 void DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs);
  76 void DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs);
  77 void DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid);
  78 static __inline__
  79 Bool DRD_(vc_lte)(const VectorClock* const vc1,
  80                   const VectorClock* const vc2);
  81 Bool DRD_(vc_ordered)(const VectorClock* const vc1,
  82                       const VectorClock* const vc2);
  83 void DRD_(vc_min)(VectorClock* const result,
  84                   const VectorClock* const rhs);
  85 void DRD_(vc_combine)(VectorClock* const result,
  86                       const VectorClock* const rhs);
  87 void DRD_(vc_print)(const VectorClock* const vc);
  88 HChar* DRD_(vc_aprint)(const VectorClock* const vc);
  89 void DRD_(vc_check)(const VectorClock* const vc);
  90 void DRD_(vc_test)(void);
  91
  92
  93
  94 /**
  95  * @return True if all thread id's that are present in vc1 also exist in
  96  *    vc2, and if additionally all corresponding counters in v2 are higher or
  97  *    equal.
  98  */
  99 static __inline__
 100 Bool DRD_(vc_lte)(const VectorClock* const vc1, const VectorClock* const vc2)
 101 {
 102    unsigned i;
 103    unsigned j = 0;
 104
 105    for (i = 0; i < vc1->size; i++)
 106    {
 107       while (j < vc2->size && vc2->vc[j].threadid < vc1->vc[i].threadid)
 108          j++;
 109       if (j >= vc2->size || vc2->vc[j].threadid > vc1->vc[i].threadid)
 110          return False;
 111 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 112       /*
 113        * This assert statement has been commented out because of performance
 114        * reasons.
 115        */
 116       tl_assert(j < vc2->size && vc2->vc[j].threadid == vc1->vc[i].threadid);
 117 #endif
 118       if (vc1->vc[i].count > vc2->vc[j].count)
 119          return False;
 120    }
 121    return True;
 122 }
 123
 124
 125 #endif /* __DRD_VC_H */