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__
DRD_(vc_lte)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