1 /* 2 This file is part of drd, a thread error detector. 3 4 Copyright (C) 2006-2012 Bart Van Assche <bvanassche (at) 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 char* 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 */ 128
