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