drd_vc.c revision 9eecbbb9a9cbbd30b903c09a9e04d8efc20bda33 
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 <bart.vanassche@gmail.com>.
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
36static
37void 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 */
47void 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. */
65void DRD_(vc_cleanup)(VectorClock* const vc)
66{
67   DRD_(vc_reserve)(vc, 0);
68}
69
70/** Copy constructor -- initializes *new. */
71void 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. */
77void 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'. */
84void 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 */
116Bool 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. */
123void 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 */
164void 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'. */
238void 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 */
253char* 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 */
296void 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 */
311static
312void 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