1 /*
2 This file is part of drd, a thread error detector.
3
4 Copyright (C) 2006-2013 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 #include "drd_vc.h"
26 #include "pub_tool_basics.h" // Addr, SizeT
27 #include "pub_tool_libcassert.h" // tl_assert()
28 #include "pub_tool_libcbase.h" // VG_(memcpy)
29 #include "pub_tool_libcprint.h" // VG_(printf)
30 #include "pub_tool_mallocfree.h" // VG_(malloc), VG_(free)
31
32
33 /* Local function declarations. */
34
35 static
36 void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity);
37
38
39 /* Function definitions. */
40
41 /**
42 * Initialize the memory 'vc' points at as a vector clock with size 'size'.
43 * If the pointer 'vcelem' is not null, it is assumed to be an array with
44 * 'size' elements and it becomes the initial value of the vector clock.
45 */
DRD_(vc_init)46 void DRD_(vc_init)(VectorClock* const vc,
47 const VCElem* const vcelem,
48 const unsigned size)
49 {
50 tl_assert(vc);
51 vc->size = 0;
52 vc->capacity = 0;
53 vc->vc = 0;
54 DRD_(vc_reserve)(vc, size);
55 tl_assert(size == 0 || vc->vc != 0);
56 if (vcelem)
57 {
58 VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0]));
59 vc->size = size;
60 }
61 }
62
63 /** Reset vc to the empty vector clock. */
DRD_(vc_cleanup)64 void DRD_(vc_cleanup)(VectorClock* const vc)
65 {
66 DRD_(vc_reserve)(vc, 0);
67 }
68
69 /** Copy constructor -- initializes *new. */
DRD_(vc_copy)70 void DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs)
71 {
72 DRD_(vc_init)(new, rhs->vc, rhs->size);
73 }
74
75 /** Assignment operator -- *lhs is already a valid vector clock. */
DRD_(vc_assign)76 void DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs)
77 {
78 DRD_(vc_cleanup)(lhs);
79 DRD_(vc_copy)(lhs, rhs);
80 }
81
82 /** Increment the clock of thread 'tid' in vector clock 'vc'. */
DRD_(vc_increment)83 void DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid)
84 {
85 unsigned i;
86 for (i = 0; i < vc->size; i++)
87 {
88 if (vc->vc[i].threadid == tid)
89 {
90 typeof(vc->vc[i].count) const oldcount = vc->vc[i].count;
91 vc->vc[i].count++;
92 // Check for integer overflow.
93 tl_assert(oldcount < vc->vc[i].count);
94 return;
95 }
96 }
97
98 /*
99 * The specified thread ID does not yet exist in the vector clock
100 * -- insert it.
101 */
102 {
103 const VCElem vcelem = { tid, 1 };
104 VectorClock vc2;
105 DRD_(vc_init)(&vc2, &vcelem, 1);
106 DRD_(vc_combine)(vc, &vc2);
107 DRD_(vc_cleanup)(&vc2);
108 }
109 }
110
111 /**
112 * @return True if vector clocks vc1 and vc2 are ordered, and false otherwise.
113 * Order is as imposed by thread synchronization actions ("happens before").
114 */
DRD_(vc_ordered)115 Bool DRD_(vc_ordered)(const VectorClock* const vc1,
116 const VectorClock* const vc2)
117 {
118 return DRD_(vc_lte)(vc1, vc2) || DRD_(vc_lte)(vc2, vc1);
119 }
120
121 /** Compute elementwise minimum. */
DRD_(vc_min)122 void DRD_(vc_min)(VectorClock* const result, const VectorClock* const rhs)
123 {
124 unsigned i;
125 unsigned j;
126
127 tl_assert(result);
128 tl_assert(rhs);
129
130 DRD_(vc_check)(result);
131
132 /* Next, combine both vector clocks into one. */
133 i = 0;
134 for (j = 0; j < rhs->size; j++)
135 {
136 while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
137 {
138 /* Thread ID is missing in second vector clock. Clear the count. */
139 result->vc[i].count = 0;
140 i++;
141 }
142 if (i >= result->size)
143 {
144 break;
145 }
146 if (result->vc[i].threadid <= rhs->vc[j].threadid)
147 {
148 /* The thread ID is present in both vector clocks. Compute the */
149 /* minimum of vc[i].count and vc[j].count. */
150 tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
151 if (rhs->vc[j].count < result->vc[i].count)
152 {
153 result->vc[i].count = rhs->vc[j].count;
154 }
155 }
156 }
157 DRD_(vc_check)(result);
158 }
159
160 /**
161 * Compute elementwise maximum.
162 */
DRD_(vc_combine)163 void DRD_(vc_combine)(VectorClock* const result, const VectorClock* const rhs)
164 {
165 unsigned i;
166 unsigned j;
167 unsigned shared;
168 unsigned new_size;
169
170 tl_assert(result);
171 tl_assert(rhs);
172
173 // First count the number of shared thread id's.
174 j = 0;
175 shared = 0;
176 for (i = 0; i < result->size; i++)
177 {
178 while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid)
179 j++;
180 if (j >= rhs->size)
181 break;
182 if (result->vc[i].threadid == rhs->vc[j].threadid)
183 shared++;
184 }
185
186 DRD_(vc_check)(result);
187
188 new_size = result->size + rhs->size - shared;
189 if (new_size > result->capacity)
190 DRD_(vc_reserve)(result, new_size);
191
192 DRD_(vc_check)(result);
193
194 // Next, combine both vector clocks into one.
195 i = 0;
196 for (j = 0; j < rhs->size; j++)
197 {
198 /* First of all, skip those clocks in result->vc[] for which there */
199 /* is no corresponding clock in rhs->vc[]. */
200 while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
201 {
202 i++;
203 }
204 /* If the end of *result is met, append rhs->vc[j] to *result. */
205 if (i >= result->size)
206 {
207 result->size++;
208 result->vc[i] = rhs->vc[j];
209 }
210 /* If clock rhs->vc[j] is not in *result, insert it. */
211 else if (result->vc[i].threadid > rhs->vc[j].threadid)
212 {
213 unsigned k;
214 for (k = result->size; k > i; k--)
215 {
216 result->vc[k] = result->vc[k - 1];
217 }
218 result->size++;
219 result->vc[i] = rhs->vc[j];
220 }
221 /* Otherwise, both *result and *rhs have a clock for thread */
222 /* result->vc[i].threadid == rhs->vc[j].threadid. Compute the maximum. */
223 else
224 {
225 tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
226 if (rhs->vc[j].count > result->vc[i].count)
227 {
228 result->vc[i].count = rhs->vc[j].count;
229 }
230 }
231 }
232 DRD_(vc_check)(result);
233 tl_assert(result->size == new_size);
234 }
235
236 /** Print the contents of vector clock 'vc'. */
DRD_(vc_print)237 void DRD_(vc_print)(const VectorClock* const vc)
238 {
239 HChar* str;
240
241 if ((str = DRD_(vc_aprint)(vc)) != NULL)
242 {
243 VG_(printf)("%s", str);
244 VG_(free)(str);
245 }
246 }
247
248 /**
249 * Print the contents of vector clock 'vc' to a newly allocated string.
250 * The caller must call VG_(free)() on the return value of this function.
251 */
DRD_(vc_aprint)252 HChar* DRD_(vc_aprint)(const VectorClock* const vc)
253 {
254 unsigned i;
255 unsigned reserved;
256 unsigned size;
257 HChar* str = 0;
258
259 tl_assert(vc);
260 reserved = 64;
261 size = 0;
262 str = VG_(realloc)("drd.vc.aprint.1", str, reserved);
263 if (! str)
264 return str;
265 size += VG_(snprintf)(str, reserved, "[");
266 for (i = 0; i < vc->size; i++)
267 {
268 tl_assert(vc->vc);
269 if (VG_(strlen)(str) + 32 > reserved)
270 {
271 reserved *= 2;
272 str = VG_(realloc)("drd.vc.aprint.2", str, reserved);
273 if (! str)
274 return str;
275 }
276 size += VG_(snprintf)(str + size, reserved - size,
277 "%s %d: %d", i > 0 ? "," : "",
278 vc->vc[i].threadid, vc->vc[i].count);
279 }
280 size += VG_(snprintf)(str + size, reserved - size, " ]");
281
282 return str;
283 }
284
285 /**
286 * Invariant test.
287 *
288 * The function below tests whether the following two conditions are
289 * satisfied:
290 * - size <= capacity.
291 * - Vector clock elements are stored in thread ID order.
292 *
293 * If one of these conditions is not met, an assertion failure is triggered.
294 */
DRD_(vc_check)295 void DRD_(vc_check)(const VectorClock* const vc)
296 {
297 unsigned i;
298 tl_assert(vc->size <= vc->capacity);
299 for (i = 1; i < vc->size; i++)
300 {
301 tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid);
302 }
303 }
304
305 /**
306 * Change the size of the memory block pointed at by vc->vc.
307 * Changes capacity, but does not change size. If the size of the memory
308 * block is increased, the newly allocated memory is not initialized.
309 */
310 static
DRD_(vc_reserve)311 void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity)
312 {
313 tl_assert(vc);
314 tl_assert(vc->capacity > VC_PREALLOCATED
315 || vc->vc == 0
316 || vc->vc == vc->preallocated);
317
318 if (new_capacity > vc->capacity)
319 {
320 if (vc->vc && vc->capacity > VC_PREALLOCATED)
321 {
322 tl_assert(vc->vc
323 && vc->vc != vc->preallocated
324 && vc->capacity > VC_PREALLOCATED);
325 vc->vc = VG_(realloc)("drd.vc.vr.1",
326 vc->vc, new_capacity * sizeof(vc->vc[0]));
327 }
328 else if (vc->vc && new_capacity > VC_PREALLOCATED)
329 {
330 tl_assert((vc->vc == 0 || vc->vc == vc->preallocated)
331 && new_capacity > VC_PREALLOCATED
332 && vc->capacity <= VC_PREALLOCATED);
333 vc->vc = VG_(malloc)("drd.vc.vr.2",
334 new_capacity * sizeof(vc->vc[0]));
335 VG_(memcpy)(vc->vc, vc->preallocated,
336 vc->capacity * sizeof(vc->vc[0]));
337 }
338 else if (vc->vc)
339 {
340 tl_assert(vc->vc == vc->preallocated
341 && new_capacity <= VC_PREALLOCATED
342 && vc->capacity <= VC_PREALLOCATED);
343 }
344 else if (new_capacity > VC_PREALLOCATED)
345 {
346 tl_assert(vc->vc == 0
347 && new_capacity > VC_PREALLOCATED
348 && vc->capacity == 0);
349 vc->vc = VG_(malloc)("drd.vc.vr.3",
350 new_capacity * sizeof(vc->vc[0]));
351 }
352 else
353 {
354 tl_assert(vc->vc == 0
355 && new_capacity <= VC_PREALLOCATED
356 && vc->capacity == 0);
357 vc->vc = vc->preallocated;
358 }
359 vc->capacity = new_capacity;
360 }
361 else if (new_capacity == 0 && vc->vc)
362 {
363 if (vc->capacity > VC_PREALLOCATED)
364 VG_(free)(vc->vc);
365 vc->vc = 0;
366 vc->capacity = 0;
367 }
368
369 tl_assert(new_capacity == 0 || vc->vc != 0);
370 tl_assert(vc->capacity > VC_PREALLOCATED
371 || vc->vc == 0
372 || vc->vc == vc->preallocated);
373 }
374