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