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