blob: d35b7e51cb63671df886a24a81e96af0d9857205 [file] [log] [blame]
bartbedfd232009-03-26 19:07:15 +00001/* -*- mode: C; c-basic-offset: 3; -*- */
sewardjaf44c822007-11-25 14:01:38 +00002/*
bart86562bd2009-02-16 19:43:56 +00003 This file is part of drd, a thread error detector.
sewardjaf44c822007-11-25 14:01:38 +00004
bart86562bd2009-02-16 19:43:56 +00005 Copyright (C) 2006-2009 Bart Van Assche <bart.vanassche@gmail.com>.
sewardjaf44c822007-11-25 14:01:38 +00006
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
bart41b226c2009-02-14 16:55:19 +000030/*
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
bart31b983d2010-02-21 14:52:59 +000042 * other thread, the vector clock of the synchronization object and the
bart41b226c2009-02-14 16:55:19 +000043 * 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 */
sewardjaf44c822007-11-25 14:01:38 +000048
49
bart8f822af2009-06-08 18:20:42 +000050#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
sewardjaf44c822007-11-25 14:01:38 +000056
57
bart41b226c2009-02-14 16:55:19 +000058/** Vector clock element. */
sewardjaf44c822007-11-25 14:01:38 +000059typedef struct
60{
bartbedfd232009-03-26 19:07:15 +000061 DrdThreadId threadid;
62 UInt count;
sewardjaf44c822007-11-25 14:01:38 +000063} VCElem;
64
65typedef struct
66{
bartbedfd232009-03-26 19:07:15 +000067 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. */
bart8f822af2009-06-08 18:20:42 +000070 VCElem preallocated[VC_PREALLOCATED];
sewardjaf44c822007-11-25 14:01:38 +000071} VectorClock;
72
73
bart41b226c2009-02-14 16:55:19 +000074void DRD_(vc_init)(VectorClock* const vc,
75 const VCElem* const vcelem,
76 const unsigned size);
77void DRD_(vc_cleanup)(VectorClock* const vc);
78void DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs);
79void DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs);
bart41b226c2009-02-14 16:55:19 +000080void DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid);
bartfa1b2932008-06-22 13:05:00 +000081static __inline__
bart41b226c2009-02-14 16:55:19 +000082Bool DRD_(vc_lte)(const VectorClock* const vc1,
83 const VectorClock* const vc2);
84Bool DRD_(vc_ordered)(const VectorClock* const vc1,
85 const VectorClock* const vc2);
86void DRD_(vc_min)(VectorClock* const result,
87 const VectorClock* const rhs);
88void DRD_(vc_combine)(VectorClock* const result,
89 const VectorClock* const rhs);
bart41b226c2009-02-14 16:55:19 +000090void DRD_(vc_print)(const VectorClock* const vc);
bart8f822af2009-06-08 18:20:42 +000091char* DRD_(vc_aprint)(const VectorClock* const vc);
bart41b226c2009-02-14 16:55:19 +000092void DRD_(vc_check)(const VectorClock* const vc);
93void DRD_(vc_test)(void);
sewardjaf44c822007-11-25 14:01:38 +000094
95
bartfa1b2932008-06-22 13:05:00 +000096
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 */
102static __inline__
bart41b226c2009-02-14 16:55:19 +0000103Bool DRD_(vc_lte)(const VectorClock* const vc1, const VectorClock* const vc2)
bartfa1b2932008-06-22 13:05:00 +0000104{
bartbedfd232009-03-26 19:07:15 +0000105 unsigned i;
106 unsigned j = 0;
bartfa1b2932008-06-22 13:05:00 +0000107
bartbedfd232009-03-26 19:07:15 +0000108 for (i = 0; i < vc1->size; i++)
109 {
110 while (j < vc2->size && vc2->vc[j].threadid < vc1->vc[i].threadid)
bartbedfd232009-03-26 19:07:15 +0000111 j++;
bartbedfd232009-03-26 19:07:15 +0000112 if (j >= vc2->size || vc2->vc[j].threadid > vc1->vc[i].threadid)
113 return False;
bartfa1b2932008-06-22 13:05:00 +0000114#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
bart468947b2010-03-07 20:00:18 +0000115 /*
116 * This assert statement has been commented out because of performance
117 * reasons.
118 */
bartbedfd232009-03-26 19:07:15 +0000119 tl_assert(j < vc2->size && vc2->vc[j].threadid == vc1->vc[i].threadid);
bartfa1b2932008-06-22 13:05:00 +0000120#endif
bartbedfd232009-03-26 19:07:15 +0000121 if (vc1->vc[i].count > vc2->vc[j].count)
122 return False;
123 }
124 return True;
bartfa1b2932008-06-22 13:05:00 +0000125}
126
127
sewardjaf44c822007-11-25 14:01:38 +0000128#endif /* __DRD_VC_H */