1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of drd, a thread error detector. 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 4436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2006-2013 Bart Van Assche <bvanassche@acm.org>. 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "drd_vc.h" 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_basics.h" // Addr, SizeT 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcassert.h" // tl_assert() 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcbase.h" // VG_(memcpy) 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcprint.h" // VG_(printf) 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_mallocfree.h" // VG_(malloc), VG_(free) 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Local function declarations. */ 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity); 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Function definitions. */ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Initialize the memory 'vc' points at as a vector clock with size 'size'. 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * If the pointer 'vcelem' is not null, it is assumed to be an array with 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 'size' elements and it becomes the initial value of the vector clock. 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_init)(VectorClock* const vc, 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const VCElem* const vcelem, 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const unsigned size) 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc); 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->size = 0; 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->capacity = 0; 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = 0; 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_reserve)(vc, size); 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(size == 0 || vc->vc != 0); 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vcelem) 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0])); 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->size = size; 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Reset vc to the empty vector clock. */ 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_cleanup)(VectorClock* const vc) 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_reserve)(vc, 0); 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Copy constructor -- initializes *new. */ 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs) 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_init)(new, rhs->vc, rhs->size); 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Assignment operator -- *lhs is already a valid vector clock. */ 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs) 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_cleanup)(lhs); 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_copy)(lhs, rhs); 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Increment the clock of thread 'tid' in vector clock 'vc'. */ 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid) 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < vc->size; i++) 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vc->vc[i].threadid == tid) 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown typeof(vc->vc[i].count) const oldcount = vc->vc[i].count; 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc[i].count++; 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check for integer overflow. 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(oldcount < vc->vc[i].count); 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * The specified thread ID does not yet exist in the vector clock 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * -- insert it. 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const VCElem vcelem = { tid, 1 }; 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VectorClock vc2; 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_init)(&vc2, &vcelem, 1); 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_combine)(vc, &vc2); 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_cleanup)(&vc2); 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @return True if vector clocks vc1 and vc2 are ordered, and false otherwise. 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Order is as imposed by thread synchronization actions ("happens before"). 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(vc_ordered)(const VectorClock* const vc1, 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const VectorClock* const vc2) 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(vc_lte)(vc1, vc2) || DRD_(vc_lte)(vc2, vc1); 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Compute elementwise minimum. */ 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_min)(VectorClock* const result, const VectorClock* const rhs) 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned j; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(result); 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(rhs); 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_check)(result); 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Next, combine both vector clocks into one. */ 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown i = 0; 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (j = 0; j < rhs->size; j++) 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid) 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Thread ID is missing in second vector clock. Clear the count. */ 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[i].count = 0; 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown i++; 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (i >= result->size) 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (result->vc[i].threadid <= rhs->vc[j].threadid) 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* The thread ID is present in both vector clocks. Compute the */ 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* minimum of vc[i].count and vc[j].count. */ 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(result->vc[i].threadid == rhs->vc[j].threadid); 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (rhs->vc[j].count < result->vc[i].count) 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[i].count = rhs->vc[j].count; 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_check)(result); 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Compute elementwise maximum. 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_combine)(VectorClock* const result, const VectorClock* const rhs) 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned j; 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned shared; 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned new_size; 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(result); 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(rhs); 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // First count the number of shared thread id's. 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown j = 0; 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown shared = 0; 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < result->size; i++) 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid) 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown j++; 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (j >= rhs->size) 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (result->vc[i].threadid == rhs->vc[j].threadid) 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown shared++; 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_check)(result); 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_size = result->size + rhs->size - shared; 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (new_size > result->capacity) 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_reserve)(result, new_size); 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_check)(result); 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Next, combine both vector clocks into one. 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown i = 0; 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (j = 0; j < rhs->size; j++) 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* First of all, skip those clocks in result->vc[] for which there */ 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* is no corresponding clock in rhs->vc[]. */ 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid) 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown i++; 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the end of *result is met, append rhs->vc[j] to *result. */ 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (i >= result->size) 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->size++; 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[i] = rhs->vc[j]; 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If clock rhs->vc[j] is not in *result, insert it. */ 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (result->vc[i].threadid > rhs->vc[j].threadid) 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned k; 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = result->size; k > i; k--) 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[k] = result->vc[k - 1]; 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->size++; 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[i] = rhs->vc[j]; 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Otherwise, both *result and *rhs have a clock for thread */ 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* result->vc[i].threadid == rhs->vc[j].threadid. Compute the maximum. */ 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(result->vc[i].threadid == rhs->vc[j].threadid); 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (rhs->vc[j].count > result->vc[i].count) 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result->vc[i].count = rhs->vc[j].count; 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(vc_check)(result); 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(result->size == new_size); 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Print the contents of vector clock 'vc'. */ 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_print)(const VectorClock* const vc) 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 239436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* str; 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((str = DRD_(vc_aprint)(vc)) != NULL) 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(printf)("%s", str); 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(free)(str); 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Print the contents of vector clock 'vc' to a newly allocated string. 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * The caller must call VG_(free)() on the return value of this function. 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 252436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* DRD_(vc_aprint)(const VectorClock* const vc) 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned reserved; 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned size; 257436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* str = 0; 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc); 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown reserved = 64; 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size = 0; 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str = VG_(realloc)("drd.vc.aprint.1", str, reserved); 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! str) 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return str; 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size += VG_(snprintf)(str, reserved, "["); 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < vc->size; i++) 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc); 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(strlen)(str) + 32 > reserved) 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown reserved *= 2; 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str = VG_(realloc)("drd.vc.aprint.2", str, reserved); 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! str) 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return str; 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size += VG_(snprintf)(str + size, reserved - size, 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown "%s %d: %d", i > 0 ? "," : "", 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc[i].threadid, vc->vc[i].count); 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size += VG_(snprintf)(str + size, reserved - size, " ]"); 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return str; 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Invariant test. 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * The function below tests whether the following two conditions are 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * satisfied: 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - size <= capacity. 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - Vector clock elements are stored in thread ID order. 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * If one of these conditions is not met, an assertion failure is triggered. 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_check)(const VectorClock* const vc) 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->size <= vc->capacity); 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < vc->size; i++) 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid); 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Change the size of the memory block pointed at by vc->vc. 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Changes capacity, but does not change size. If the size of the memory 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * block is increased, the newly allocated memory is not initialized. 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity) 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc); 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->capacity > VC_PREALLOCATED 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown || vc->vc == 0 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown || vc->vc == vc->preallocated); 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (new_capacity > vc->capacity) 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vc->vc && vc->capacity > VC_PREALLOCATED) 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->vc != vc->preallocated 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->capacity > VC_PREALLOCATED); 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = VG_(realloc)("drd.vc.vr.1", 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc, new_capacity * sizeof(vc->vc[0])); 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (vc->vc && new_capacity > VC_PREALLOCATED) 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert((vc->vc == 0 || vc->vc == vc->preallocated) 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && new_capacity > VC_PREALLOCATED 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->capacity <= VC_PREALLOCATED); 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = VG_(malloc)("drd.vc.vr.2", 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_capacity * sizeof(vc->vc[0])); 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)(vc->vc, vc->preallocated, 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->capacity * sizeof(vc->vc[0])); 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (vc->vc) 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc == vc->preallocated 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && new_capacity <= VC_PREALLOCATED 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->capacity <= VC_PREALLOCATED); 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (new_capacity > VC_PREALLOCATED) 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc == 0 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && new_capacity > VC_PREALLOCATED 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->capacity == 0); 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = VG_(malloc)("drd.vc.vr.3", 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_capacity * sizeof(vc->vc[0])); 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->vc == 0 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && new_capacity <= VC_PREALLOCATED 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && vc->capacity == 0); 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = vc->preallocated; 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->capacity = new_capacity; 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (new_capacity == 0 && vc->vc) 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vc->capacity > VC_PREALLOCATED) 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(free)(vc->vc); 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->vc = 0; 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vc->capacity = 0; 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(new_capacity == 0 || vc->vc != 0); 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(vc->capacity > VC_PREALLOCATED 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown || vc->vc == 0 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown || vc->vc == vc->preallocated); 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 374