Home | History | Annotate | Download | only in drd 
      1 /* -*- mode: C; c-basic-offset: 3; -*- */
      2 /*
      3   This file is part of drd, a thread error detector.
      4 
      5   Copyright (C) 2006-2010 Bart Van Assche <bvanassche (at) acm.org>.
      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_(memcpy)
     30 #include "pub_tool_libcprint.h"   // VG_(printf)
     31 #include "pub_tool_mallocfree.h"  // VG_(malloc), VG_(free)
     32 
     33 
     34 /* Local function declarations. */
     35 
     36 static
     37 void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity);
     38 
     39 
     40 /* Function definitions. */
     41 
     42 /**
     43  * Initialize the memory 'vc' points at as a vector clock with size 'size'.
     44  * If the pointer 'vcelem' is not null, it is assumed to be an array with
     45  * 'size' elements and it becomes the initial value of the vector clock.
     46  */
     47 void DRD_(vc_init)(VectorClock* const vc,
     48                    const VCElem* const vcelem,
     49                    const unsigned size)
     50 {
     51    tl_assert(vc);
     52    vc->size = 0;
     53    vc->capacity = 0;
     54    vc->vc = 0;
     55    DRD_(vc_reserve)(vc, size);
     56    tl_assert(size == 0 || vc->vc != 0);
     57    if (vcelem)
     58    {
     59       VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0]));
     60       vc->size = size;
     61    }
     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    char* 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 char* DRD_(vc_aprint)(const VectorClock* const vc)
    254 {
    255    unsigned i;
    256    unsigned reserved;
    257    unsigned size;
    258    char* 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 %d: %d", 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    tl_assert(vc->size <= vc->capacity);
    300    for (i = 1; i < vc->size; i++)
    301    {
    302       tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid);
    303    }
    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 }
    375