drd/drd_vc.c

   1 /*
   2   This file is part of drd, a thread error detector.
   3
   4   Copyright (C) 2006-2017 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 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
  62    DRD_(vc_check)(vc);
  63 #endif
  64 }
  65
  66 /** Reset vc to the empty vector clock. */
  67 void DRD_(vc_cleanup)(VectorClock* const vc)
  68 {
  69    DRD_(vc_reserve)(vc, 0);
  70 }
  71
  72 /** Copy constructor -- initializes *new. */
  73 void 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. */
  79 void 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'. */
  86 void 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  */
 118 Bool 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. */
 125 void 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  */
 166 void 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'. */
 240 void 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  */
 255 HChar* 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  */
 298 void 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  */
 313 static
 314 void 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 }