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
35static
36void 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 */
46void 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. */
64void DRD_(vc_cleanup)(VectorClock* const vc)
65{
66   DRD_(vc_reserve)(vc, 0);
67}
68
69/** Copy constructor -- initializes *new. */
70void 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. */
76void 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'. */
83void 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 */
115Bool 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. */
122void 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 */
163void 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'. */
237void 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 */
252HChar* 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 */
295void 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 */
310static
311void 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