drd/drd_vc.c

   1 /*
   2   This file is part of drd, a thread error detector.
   3
   4   Copyright (C) 2006-2020 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, see <http://www.gnu.org/licenses/>.
  18
  19   The GNU General Public License is contained in the file COPYING.
  20 */
  21
  22
  23 #include "drd_vc.h"
  24 #include "pub_tool_basics.h"      // Addr, SizeT
  25 #include "pub_tool_libcassert.h"  // tl_assert()
  26 #include "pub_tool_libcbase.h"    // VG_(memcpy)
  27 #include "pub_tool_libcprint.h"   // VG_(printf)
  28 #include "pub_tool_mallocfree.h"  // VG_(malloc), VG_(free)
  29
  30
  31 /* Local function declarations. */
  32
  33 static
  34 void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity);
  35
  36
  37 /* Function definitions. */
  38
  39 /**
  40  * Initialize the memory 'vc' points at as a vector clock with size 'size'.
  41  * If the pointer 'vcelem' is not null, it is assumed to be an array with
  42  * 'size' elements and it becomes the initial value of the vector clock.
  43  */
  44 void DRD_(vc_init)(VectorClock* const vc,
  45                    const VCElem* const vcelem,
  46                    const unsigned size)
  47 {
  48    tl_assert(vc);
  49    vc->size = 0;
  50    vc->capacity = 0;
  51    vc->vc = 0;
  52    DRD_(vc_reserve)(vc, size);
  53    tl_assert(size == 0 || vc->vc != 0);
  54    if (vcelem)
  55    {
  56       VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0]));
  57       vc->size = size;
  58    }
  59 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
  60    DRD_(vc_check)(vc);
  61 #endif
  62 }
  63
  64 /** Reset vc to the empty vector clock. */
  65 void DRD_(vc_cleanup)(VectorClock* const vc)
  66 {
  67    DRD_(vc_reserve)(vc, 0);
  68 }
  69
  70 /** Copy constructor -- initializes *new. */
  71 void 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. */
  77 void 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'. */
  84 void 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  */
 116 Bool 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. */
 123 void 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  */
 164 void 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'. */
 238 void DRD_(vc_print)(const VectorClock* const vc)
 239 {
 240    HChar* 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  */
 253 HChar* DRD_(vc_aprint)(const VectorClock* const vc)
 254 {
 255    unsigned i;
 256    unsigned reserved;
 257    unsigned size;
 258    HChar* 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 %u: %u", 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  */
 296 void DRD_(vc_check)(const VectorClock* const vc)
 297 {
 298    unsigned i;
 299
 300    tl_assert(vc->size <= vc->capacity);
 301
 302    for (i = 1; i < vc->size; i++)
 303       tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid);
 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  */
 311 static
 312 void 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 }