drd/drd_vc.c

   1 /*
   2   This file is part of drd, a thread error detector.
   3
   4   Copyright (C) 2006-2011 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  */
  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 }
  62
  63 /** Reset vc to the empty vector clock. */
  64 void DRD_(vc_cleanup)(VectorClock* const vc)
  65 {
  66    DRD_(vc_reserve)(vc, 0);
  67 }
  68
  69 /** Copy constructor -- initializes *new. */
  70 void 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. */
  76 void 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'. */
  83 void 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  */
 115 Bool 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. */
 122 void 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  */
 163 void 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'. */
 237 void DRD_(vc_print)(const VectorClock* const vc)
 238 {
 239    char* 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  */
 252 char* DRD_(vc_aprint)(const VectorClock* const vc)
 253 {
 254    unsigned i;
 255    unsigned reserved;
 256    unsigned size;
 257    char* 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  */
 295 void 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  */
 310 static
 311 void 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 }