Home | History | Annotate | Download | only in drd 
      1 /*
      2   This file is part of drd, a thread error detector.
      3 
      4   Copyright (C) 2006-2017 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 #ifndef __DRD_VC_H
     26 #define __DRD_VC_H
     27 
     28 
     29 /*
     30  * DRD vector clock implementation:
     31  * - One counter per thread.
     32  * - A vector clock is implemented as multiple pairs of (thread id, counter).
     33  * - Pairs are stored in an array sorted by thread id.
     34  *
     35  * Semantics:
     36  * - Each time a thread performs an action that implies an ordering between
     37  *   intra-thread events, the counter of that thread is incremented.
     38  * - Vector clocks are compared by comparing all counters of all threads.
     39  * - When a thread synchronization action is performed that guarantees that
     40  *   new actions of the current thread are executed after the actions of the
     41  *   other thread, the vector clock of the synchronization object and the
     42  *   current thread are combined (by taking the component-wise maximum).
     43  * - A vector clock is incremented during actions such as
     44  *   pthread_create(), pthread_mutex_unlock(), sem_post(). (Actions where
     45  *   an inter-thread ordering "arrow" starts).
     46  */
     47 
     48 
     49 #include "pub_tool_basics.h"     /* Addr, SizeT */
     50 #include "drd_basics.h"          /* DrdThreadId */
     51 #include "pub_tool_libcassert.h" /* tl_assert() */
     52 
     53 
     54 #define VC_PREALLOCATED 8
     55 
     56 
     57 /** Vector clock element. */
     58 typedef struct
     59 {
     60    DrdThreadId threadid;
     61    UInt        count;
     62 } VCElem;
     63 
     64 typedef struct
     65 {
     66    unsigned capacity; /**< number of elements allocated for array vc. */
     67    unsigned size;     /**< number of elements used of array vc. */
     68    VCElem*  vc;       /**< vector clock elements. */
     69    VCElem   preallocated[VC_PREALLOCATED];
     70 } VectorClock;
     71 
     72 
     73 void DRD_(vc_init)(VectorClock* const vc,
     74                    const VCElem* const vcelem,
     75                    const unsigned size);
     76 void DRD_(vc_cleanup)(VectorClock* const vc);
     77 void DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs);
     78 void DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs);
     79 void DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid);
     80 static __inline__
     81 Bool DRD_(vc_lte)(const VectorClock* const vc1,
     82                   const VectorClock* const vc2);
     83 Bool DRD_(vc_ordered)(const VectorClock* const vc1,
     84                       const VectorClock* const vc2);
     85 void DRD_(vc_min)(VectorClock* const result,
     86                   const VectorClock* const rhs);
     87 void DRD_(vc_combine)(VectorClock* const result,
     88                       const VectorClock* const rhs);
     89 void DRD_(vc_print)(const VectorClock* const vc);
     90 HChar* DRD_(vc_aprint)(const VectorClock* const vc);
     91 void DRD_(vc_check)(const VectorClock* const vc);
     92 void DRD_(vc_test)(void);
     93 
     94 
     95 
     96 /**
     97  * @return True if all thread id's that are present in vc1 also exist in
     98  *    vc2, and if additionally all corresponding counters in v2 are higher or
     99  *    equal.
    100  */
    101 static __inline__
    102 Bool DRD_(vc_lte)(const VectorClock* const vc1, const VectorClock* const vc2)
    103 {
    104    unsigned i;
    105    unsigned j = 0;
    106 
    107    for (i = 0; i < vc1->size; i++)
    108    {
    109       while (j < vc2->size && vc2->vc[j].threadid < vc1->vc[i].threadid)
    110          j++;
    111       if (j >= vc2->size || vc2->vc[j].threadid > vc1->vc[i].threadid)
    112          return False;
    113 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
    114       /*
    115        * This assert statement has been commented out because of performance
    116        * reasons.
    117        */
    118       tl_assert(j < vc2->size && vc2->vc[j].threadid == vc1->vc[i].threadid);
    119 #endif
    120       if (vc1->vc[i].count > vc2->vc[j].count)
    121          return False;
    122    }
    123    return True;
    124 }
    125 
    126 
    127 #endif /* __DRD_VC_H */
    128