Home | History | Annotate | Download | only in drd
      1 /*
      2   This file is part of drd, a thread error detector.
      3 
      4   Copyright (C) 2006-2012 Bart Van Assche <bvanassche (at) 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 }
    374