← Back to branch summary

~bkerensa/ubuntu/raring/valgrind/merge-from-deb

« back to all changes in this revision

Viewing changes to exp-drd/drd_vc.c

  • Committer: Bazaar Package Importer
  • Author(s): Andrés Roldán
  • Date: 2008-06-13 02:31:40 UTC
  • mto: (1.4.1 upstream) (2.2.1 squeeze)
  • mto: This revision was merged to the branch mainline in revision 24.
  • Revision ID: james.westby@ubuntu.com-20080613023140-iwk33rz9rhvfkr96
Import upstream version 3.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
exp-drd/drd_vc.c
 
1
/*
 
2
  This file is part of drd, a data race detector.
 
3
 
 
4
  Copyright (C) 2006-2007 Bart Van Assche
 
5
  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_(memset), VG_(memmove)
 
30
#include "pub_tool_libcprint.h"   // VG_(printf)
 
31
#include "pub_tool_mallocfree.h"  // VG_(malloc), VG_(free)
 
32
#include "pub_tool_threadstate.h" // VG_(get_running_tid)
 
33
 
 
34
 
 
35
static
 
36
void vc_reserve(VectorClock* const vc, const unsigned new_capacity);
 
37
 
 
38
 
 
39
void vc_init(VectorClock* const vc,
 
40
             const VCElem* const vcelem,
 
41
             const unsigned size)
 
42
{
 
43
  tl_assert(vc);
 
44
  vc->size = 0;
 
45
  vc->capacity = 0;
 
46
  vc->vc = 0;
 
47
  vc_reserve(vc, size);
 
48
  tl_assert(size == 0 || vc->vc != 0);
 
49
  if (vcelem)
 
50
  {
 
51
    VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0]));
 
52
    vc->size = size;
 
53
  }
 
54
}
 
55
 
 
56
void vc_cleanup(VectorClock* const vc)
 
57
{
 
58
  vc_reserve(vc, 0);
 
59
}
 
60
 
 
61
/**
 
62
 * Copy constructor -- initializes 'new'.
 
63
 */
 
64
void vc_copy(VectorClock* const new,
 
65
             const VectorClock* const rhs)
 
66
{
 
67
  vc_init(new, rhs->vc, rhs->size);
 
68
}
 
69
 
 
70
void vc_increment(VectorClock* const vc, ThreadId const threadid)
 
71
{
 
72
  unsigned i;
 
73
  for (i = 0; i < vc->size; i++)
 
74
  {
 
75
    if (vc->vc[i].threadid == threadid)
 
76
    {
 
77
      typeof(vc->vc[i].count) const oldcount = vc->vc[i].count;
 
78
      vc->vc[i].count++;
 
79
      // Check for integer overflow.
 
80
      tl_assert(oldcount < vc->vc[i].count);
 
81
      return;
 
82
    }
 
83
  }
 
84
 
 
85
  // The specified thread ID does not yet exist in the vector clock
 
86
  // -- insert it.
 
87
  {
 
88
    VCElem vcelem = { threadid, 1 };
 
89
    VectorClock vc2;
 
90
    vc_init(&vc2, &vcelem, 1);
 
91
    vc_combine(vc, &vc2);
 
92
    vc_cleanup(&vc2);
 
93
  }
 
94
}
 
95
 
 
96
/**
 
97
 * @return True if all thread id's that are present in vc1 also exist in
 
98
 *    vc2, and if additionally all corresponding counters in v2 are higher or
 
99
 *    equal.
 
100
 */
 
101
Bool vc_lte(const VectorClock* const vc1,
 
102
            const VectorClock* const vc2)
 
103
{
 
104
  unsigned i;
 
105
  unsigned j = 0;
 
106
  for (i = 0; i < vc1->size; i++)
 
107
  {
 
108
    while (j < vc2->size && vc2->vc[j].threadid < vc1->vc[i].threadid)
 
109
    {
 
110
      j++;
 
111
    }
 
112
    if (j >= vc2->size || vc2->vc[j].threadid > vc1->vc[i].threadid)
 
113
      return False;
 
114
    tl_assert(j < vc2->size && vc2->vc[j].threadid == vc1->vc[i].threadid);
 
115
    if (vc1->vc[i].count > vc2->vc[j].count)
 
116
      return False;
 
117
  }
 
118
  return True;
 
119
}
 
120
 
 
121
/**
 
122
 * @return True if vector clocks vc1 and vc2 are ordered, and false otherwise.
 
123
 * Order is as imposed by thread synchronization actions ("happens before").
 
124
 */
 
125
Bool vc_ordered(const VectorClock* const vc1,
 
126
                const VectorClock* const vc2)
 
127
{
 
128
  return vc_lte(vc1, vc2) || vc_lte(vc2, vc1);
 
129
}
 
130
 
 
131
/**
 
132
 * Compute elementwise minimum.
 
133
 */
 
134
void vc_min(VectorClock* const result,
 
135
            const VectorClock* const rhs)
 
136
{
 
137
  unsigned i;
 
138
  unsigned j;
 
139
  unsigned shared;
 
140
  unsigned new_size;
 
141
 
 
142
  tl_assert(result);
 
143
  tl_assert(rhs);
 
144
 
 
145
  // First count the number of shared thread id's.
 
146
  j = 0;
 
147
  shared = 0;
 
148
  for (i = 0; i < result->size; i++)
 
149
  {
 
150
    while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid)
 
151
      j++;
 
152
    if (j >= rhs->size)
 
153
      break;
 
154
    if (result->vc[i].threadid == rhs->vc[j].threadid)
 
155
      shared++;
 
156
  }
 
157
 
 
158
  vc_check(result);
 
159
 
 
160
  new_size = result->size + rhs->size - shared;
 
161
  if (new_size > result->capacity)
 
162
    vc_reserve(result, new_size);
 
163
 
 
164
  vc_check(result);
 
165
 
 
166
  // Next, combine both vector clocks into one.
 
167
  i = 0;
 
168
  for (j = 0; j < rhs->size; j++)
 
169
  {
 
170
    vc_check(result);
 
171
 
 
172
    while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
 
173
      i++;
 
174
    if (i >= result->size)
 
175
    {
 
176
      result->size++;
 
177
      result->vc[i] = rhs->vc[j];
 
178
      vc_check(result);
 
179
    }
 
180
    else if (result->vc[i].threadid > rhs->vc[j].threadid)
 
181
    {
 
182
      unsigned k;
 
183
      for (k = result->size; k > i; k--)
 
184
      {
 
185
        result->vc[k] = result->vc[k - 1];
 
186
      }
 
187
      result->size++;
 
188
      result->vc[i] = rhs->vc[j];
 
189
      vc_check(result);
 
190
    }
 
191
    else
 
192
    {
 
193
      tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
 
194
      if (rhs->vc[j].count < result->vc[i].count)
 
195
      {
 
196
        result->vc[i].count = rhs->vc[j].count;
 
197
      }
 
198
      vc_check(result);
 
199
    }
 
200
  }
 
201
  vc_check(result);
 
202
  tl_assert(result->size == new_size);
 
203
}
 
204
 
 
205
/**
 
206
 * Compute elementwise maximum.
 
207
 */
 
208
void vc_combine(VectorClock* const result,
 
209
                const VectorClock* const rhs)
 
210
{
 
211
  unsigned i;
 
212
  unsigned j;
 
213
  unsigned shared;
 
214
  unsigned new_size;
 
215
 
 
216
  tl_assert(result);
 
217
  tl_assert(rhs);
 
218
 
 
219
  // First count the number of shared thread id's.
 
220
  j = 0;
 
221
  shared = 0;
 
222
  for (i = 0; i < result->size; i++)
 
223
  {
 
224
    while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid)
 
225
      j++;
 
226
    if (j >= rhs->size)
 
227
      break;
 
228
    if (result->vc[i].threadid == rhs->vc[j].threadid)
 
229
      shared++;
 
230
  }
 
231
 
 
232
  vc_check(result);
 
233
 
 
234
  new_size = result->size + rhs->size - shared;
 
235
  if (new_size > result->capacity)
 
236
    vc_reserve(result, new_size);
 
237
 
 
238
  vc_check(result);
 
239
 
 
240
  // Next, combine both vector clocks into one.
 
241
  i = 0;
 
242
  for (j = 0; j < rhs->size; j++)
 
243
  {
 
244
    vc_check(result);
 
245
 
 
246
    while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
 
247
      i++;
 
248
    if (i >= result->size)
 
249
    {
 
250
      result->size++;
 
251
      result->vc[i] = rhs->vc[j];
 
252
      vc_check(result);
 
253
    }
 
254
    else if (result->vc[i].threadid > rhs->vc[j].threadid)
 
255
    {
 
256
      unsigned k;
 
257
      for (k = result->size; k > i; k--)
 
258
      {
 
259
        result->vc[k] = result->vc[k - 1];
 
260
      }
 
261
      result->size++;
 
262
      result->vc[i] = rhs->vc[j];
 
263
      vc_check(result);
 
264
    }
 
265
    else
 
266
    {
 
267
      tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
 
268
      if (rhs->vc[j].count > result->vc[i].count)
 
269
      {
 
270
        result->vc[i].count = rhs->vc[j].count;
 
271
      }
 
272
      vc_check(result);
 
273
    }
 
274
  }
 
275
  vc_check(result);
 
276
  tl_assert(result->size == new_size);
 
277
}
 
278
 
 
279
void vc_print(const VectorClock* const vc)
 
280
{
 
281
  unsigned i;
 
282
 
 
283
  tl_assert(vc);
 
284
  VG_(printf)("[");
 
285
  for (i = 0; i < vc->size; i++)
 
286
  {
 
287
    tl_assert(vc->vc);
 
288
    VG_(printf)("%s %d: %d", i > 0 ? "," : "",
 
289
                vc->vc[i].threadid, vc->vc[i].count);
 
290
  }
 
291
  VG_(printf)(" ]");
 
292
}
 
293
 
 
294
void vc_snprint(Char* const str, Int const size,
 
295
                const VectorClock* const vc)
 
296
{
 
297
  unsigned i;
 
298
 
 
299
  tl_assert(vc);
 
300
  VG_(snprintf)(str, size, "[");
 
301
  for (i = 0; i < vc->size; i++)
 
302
  {
 
303
    tl_assert(vc->vc);
 
304
    VG_(snprintf)(str + VG_(strlen)(str), size - VG_(strlen)(str),
 
305
                  "%s %d: %d", i > 0 ? "," : "",
 
306
                  vc->vc[i].threadid, vc->vc[i].count);
 
307
  }
 
308
  VG_(snprintf)(str + VG_(strlen)(str), size - VG_(strlen)(str), " ]");
 
309
}
 
310
 
 
311
/**
 
312
 * Invariant test.
 
313
 */
 
314
void vc_check(const VectorClock* const vc)
 
315
{
 
316
  unsigned i;
 
317
  tl_assert(vc->size <= vc->capacity);
 
318
  for (i = 1; i < vc->size; i++)
 
319
  {
 
320
    tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid);
 
321
  }
 
322
}
 
323
 
 
324
/**
 
325
 * Change the size of the memory block pointed at by vc->vc.
 
326
 * Changes capacity, but does not change size. If the size of the memory
 
327
 * block is increased, the newly allocated memory is not initialized.
 
328
 */
 
329
static
 
330
void vc_reserve(VectorClock* const vc, const unsigned new_capacity)
 
331
{
 
332
  tl_assert(vc);
 
333
  if (new_capacity > vc->capacity)
 
334
  {
 
335
    if (vc->vc)
 
336
    {
 
337
      vc->vc = VG_(realloc)(vc->vc, new_capacity * sizeof(vc->vc[0]));
 
338
    }
 
339
    else if (new_capacity > 0)
 
340
    {
 
341
      vc->vc = VG_(malloc)(new_capacity * sizeof(vc->vc[0]));
 
342
    }
 
343
    else
 
344
    {
 
345
      tl_assert(vc->vc == 0 && new_capacity == 0);
 
346
    }
 
347
    vc->capacity = new_capacity;
 
348
  }
 
349
  tl_assert(new_capacity == 0 || vc->vc != 0);
 
350
}
 
351
 
 
352
/**
 
353
 * Unit test.
 
354
 */
 
355
void vc_test(void)
 
356
{
 
357
  VectorClock vc1;
 
358
  VCElem vc1elem[] = { { 3, 7 }, { 5, 8 }, };
 
359
  VectorClock vc2;
 
360
  VCElem vc2elem[] = { { 1, 4 }, { 3, 9 }, };
 
361
  VectorClock vc3;
 
362
  VCElem vc4elem[] = { { 1, 3 }, { 2, 1 }, };
 
363
  VectorClock vc4;
 
364
  VCElem vc5elem[] = { { 1, 4 }, };
 
365
  VectorClock vc5;
 
366
 
 
367
  vc_init(&vc1, vc1elem, sizeof(vc1elem)/sizeof(vc1elem[0]));
 
368
  vc_init(&vc2, vc2elem, sizeof(vc2elem)/sizeof(vc2elem[0]));
 
369
  vc_init(&vc3, 0, 0);
 
370
  vc_init(&vc4, vc4elem, sizeof(vc4elem)/sizeof(vc4elem[0]));
 
371
  vc_init(&vc5, vc5elem, sizeof(vc5elem)/sizeof(vc5elem[0]));
 
372
 
 
373
  vc_combine(&vc3, &vc1);
 
374
  vc_combine(&vc3, &vc2);
 
375
 
 
376
  VG_(printf)("vc1: ");
 
377
  vc_print(&vc1);
 
378
  VG_(printf)("\nvc2: ");
 
379
  vc_print(&vc2);
 
380
  VG_(printf)("\nvc3: ");
 
381
  vc_print(&vc3);
 
382
  VG_(printf)("\n");
 
383
  VG_(printf)("vc_lte(vc1, vc2) = %d, vc_lte(vc1, vc3) = %d, vc_lte(vc2, vc3) = %d, vc_lte(", vc_lte(&vc1, &vc2), vc_lte(&vc1, &vc3), vc_lte(&vc2, &vc3));
 
384
  vc_print(&vc4);
 
385
  VG_(printf)(", ");
 
386
  vc_print(&vc5);
 
387
  VG_(printf)(") = %d sw %d\n", vc_lte(&vc4, &vc5), vc_lte(&vc5, &vc4));
 
388
              
 
389
  vc_cleanup(&vc1);
 
390
  vc_cleanup(&vc2);
 
391
  vc_cleanup(&vc3);
 
392
}