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