drd/drd_vc.h

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