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
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#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
62   DRD_(vc_check)(vc);
63#endif
64}
65
66/** Reset vc to the empty vector clock. */
67void DRD_(vc_cleanup)(VectorClock* const vc)
68{
69   DRD_(vc_reserve)(vc, 0);
70}
71
72/** Copy constructor -- initializes *new. */
73void 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. */
79void 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'. */
86void 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 */
118Bool 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. */
125void 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 */
166void 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'. */
240void 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 */
255HChar* 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 */
298void 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 */
313static
314void 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