1af44c8236f7a73e71b16b707bba56f33af4d01cesewardj/* 286562bd89ac23ce795d19c71fabcb9d1c8f956d3bart This file is part of drd, a thread error detector. 3af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 4b3a1e4bffbdbbf38304f216af405009868f43628sewardj Copyright (C) 2006-2015 Bart Van Assche <bvanassche@acm.org>. 5af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 6af44c8236f7a73e71b16b707bba56f33af4d01cesewardj This program is free software; you can redistribute it and/or 7af44c8236f7a73e71b16b707bba56f33af4d01cesewardj modify it under the terms of the GNU General Public License as 8af44c8236f7a73e71b16b707bba56f33af4d01cesewardj published by the Free Software Foundation; either version 2 of the 9af44c8236f7a73e71b16b707bba56f33af4d01cesewardj License, or (at your option) any later version. 10af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 11af44c8236f7a73e71b16b707bba56f33af4d01cesewardj This program is distributed in the hope that it will be useful, but 12af44c8236f7a73e71b16b707bba56f33af4d01cesewardj WITHOUT ANY WARRANTY; without even the implied warranty of 13af44c8236f7a73e71b16b707bba56f33af4d01cesewardj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14af44c8236f7a73e71b16b707bba56f33af4d01cesewardj General Public License for more details. 15af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 16af44c8236f7a73e71b16b707bba56f33af4d01cesewardj You should have received a copy of the GNU General Public License 17af44c8236f7a73e71b16b707bba56f33af4d01cesewardj along with this program; if not, write to the Free Software 18af44c8236f7a73e71b16b707bba56f33af4d01cesewardj Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 19af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 02111-1307, USA. 20af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 21af44c8236f7a73e71b16b707bba56f33af4d01cesewardj The GNU General Public License is contained in the file COPYING. 22af44c8236f7a73e71b16b707bba56f33af4d01cesewardj*/ 23af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 24af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 25af44c8236f7a73e71b16b707bba56f33af4d01cesewardj#include "drd_vc.h" 26af44c8236f7a73e71b16b707bba56f33af4d01cesewardj#include "pub_tool_basics.h" // Addr, SizeT 27af44c8236f7a73e71b16b707bba56f33af4d01cesewardj#include "pub_tool_libcassert.h" // tl_assert() 2841b226c0a9c60c7dc10b09b6d71138f1993259d8bart#include "pub_tool_libcbase.h" // VG_(memcpy) 29af44c8236f7a73e71b16b707bba56f33af4d01cesewardj#include "pub_tool_libcprint.h" // VG_(printf) 30af44c8236f7a73e71b16b707bba56f33af4d01cesewardj#include "pub_tool_mallocfree.h" // VG_(malloc), VG_(free) 31af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 32af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 3341b226c0a9c60c7dc10b09b6d71138f1993259d8bart/* Local function declarations. */ 3441b226c0a9c60c7dc10b09b6d71138f1993259d8bart 35af44c8236f7a73e71b16b707bba56f33af4d01cesewardjstatic 3641b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity); 3741b226c0a9c60c7dc10b09b6d71138f1993259d8bart 38af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 3941b226c0a9c60c7dc10b09b6d71138f1993259d8bart/* Function definitions. */ 40af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 4141b226c0a9c60c7dc10b09b6d71138f1993259d8bart/** 4241b226c0a9c60c7dc10b09b6d71138f1993259d8bart * Initialize the memory 'vc' points at as a vector clock with size 'size'. 4341b226c0a9c60c7dc10b09b6d71138f1993259d8bart * If the pointer 'vcelem' is not null, it is assumed to be an array with 4441b226c0a9c60c7dc10b09b6d71138f1993259d8bart * 'size' elements and it becomes the initial value of the vector clock. 4541b226c0a9c60c7dc10b09b6d71138f1993259d8bart */ 4641b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_init)(VectorClock* const vc, 4741b226c0a9c60c7dc10b09b6d71138f1993259d8bart const VCElem* const vcelem, 4841b226c0a9c60c7dc10b09b6d71138f1993259d8bart const unsigned size) 49af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 50bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc); 51bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->size = 0; 52bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->capacity = 0; 53bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->vc = 0; 54bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_reserve)(vc, size); 55bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(size == 0 || vc->vc != 0); 56bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (vcelem) 57bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 58bedfd237fbdc80d0c917cfcb85a94b5561c92633bart VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0])); 59bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->size = size; 60bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 6152048382ad36b96f505e46a5e6ca9bef795551e9bart#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 6252048382ad36b96f505e46a5e6ca9bef795551e9bart DRD_(vc_check)(vc); 6352048382ad36b96f505e46a5e6ca9bef795551e9bart#endif 64af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 65af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 6641b226c0a9c60c7dc10b09b6d71138f1993259d8bart/** Reset vc to the empty vector clock. */ 6741b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_cleanup)(VectorClock* const vc) 68af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 69bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_reserve)(vc, 0); 70af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 71af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 72c46c232c2e5901eb23d6033cd55c2f6c6d081166bart/** Copy constructor -- initializes *new. */ 7341b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs) 74af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 75bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_init)(new, rhs->vc, rhs->size); 76af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 77af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 78c46c232c2e5901eb23d6033cd55c2f6c6d081166bart/** Assignment operator -- *lhs is already a valid vector clock. */ 7941b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs) 80c46c232c2e5901eb23d6033cd55c2f6c6d081166bart{ 81bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_cleanup)(lhs); 82bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_copy)(lhs, rhs); 83c46c232c2e5901eb23d6033cd55c2f6c6d081166bart} 84c46c232c2e5901eb23d6033cd55c2f6c6d081166bart 8541b226c0a9c60c7dc10b09b6d71138f1993259d8bart/** Increment the clock of thread 'tid' in vector clock 'vc'. */ 8641b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid) 87af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 88bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned i; 89bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (i = 0; i < vc->size; i++) 90bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 91bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (vc->vc[i].threadid == tid) 92bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 93bedfd237fbdc80d0c917cfcb85a94b5561c92633bart typeof(vc->vc[i].count) const oldcount = vc->vc[i].count; 94bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->vc[i].count++; 95bedfd237fbdc80d0c917cfcb85a94b5561c92633bart // Check for integer overflow. 96bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(oldcount < vc->vc[i].count); 97bedfd237fbdc80d0c917cfcb85a94b5561c92633bart return; 98bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 99bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 100bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 101bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* 102bedfd237fbdc80d0c917cfcb85a94b5561c92633bart * The specified thread ID does not yet exist in the vector clock 103bedfd237fbdc80d0c917cfcb85a94b5561c92633bart * -- insert it. 104bedfd237fbdc80d0c917cfcb85a94b5561c92633bart */ 105bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 106bedfd237fbdc80d0c917cfcb85a94b5561c92633bart const VCElem vcelem = { tid, 1 }; 107bedfd237fbdc80d0c917cfcb85a94b5561c92633bart VectorClock vc2; 108bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_init)(&vc2, &vcelem, 1); 109bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_combine)(vc, &vc2); 110bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_cleanup)(&vc2); 111bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 112af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 113af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 114af44c8236f7a73e71b16b707bba56f33af4d01cesewardj/** 115af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * @return True if vector clocks vc1 and vc2 are ordered, and false otherwise. 116af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * Order is as imposed by thread synchronization actions ("happens before"). 117af44c8236f7a73e71b16b707bba56f33af4d01cesewardj */ 11841b226c0a9c60c7dc10b09b6d71138f1993259d8bartBool DRD_(vc_ordered)(const VectorClock* const vc1, 11941b226c0a9c60c7dc10b09b6d71138f1993259d8bart const VectorClock* const vc2) 120af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 121bedfd237fbdc80d0c917cfcb85a94b5561c92633bart return DRD_(vc_lte)(vc1, vc2) || DRD_(vc_lte)(vc2, vc1); 122af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 123af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 1245bd9f2d42ba9440b528b1f926dd57b4652cb0583bart/** Compute elementwise minimum. */ 12541b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_min)(VectorClock* const result, const VectorClock* const rhs) 126af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 127bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned i; 128bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned j; 129bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 130bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(result); 131bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(rhs); 132bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 133bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_check)(result); 134bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 135bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* Next, combine both vector clocks into one. */ 136bedfd237fbdc80d0c917cfcb85a94b5561c92633bart i = 0; 137bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (j = 0; j < rhs->size; j++) 138bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 139bedfd237fbdc80d0c917cfcb85a94b5561c92633bart while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid) 140af44c8236f7a73e71b16b707bba56f33af4d01cesewardj { 141bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* Thread ID is missing in second vector clock. Clear the count. */ 142bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[i].count = 0; 143bedfd237fbdc80d0c917cfcb85a94b5561c92633bart i++; 144af44c8236f7a73e71b16b707bba56f33af4d01cesewardj } 145bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (i >= result->size) 146bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 147bedfd237fbdc80d0c917cfcb85a94b5561c92633bart break; 148bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 149bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (result->vc[i].threadid <= rhs->vc[j].threadid) 150bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 151bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* The thread ID is present in both vector clocks. Compute the */ 152bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* minimum of vc[i].count and vc[j].count. */ 153bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(result->vc[i].threadid == rhs->vc[j].threadid); 154bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (rhs->vc[j].count < result->vc[i].count) 155bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 156bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[i].count = rhs->vc[j].count; 157bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 158bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 159bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 160bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_check)(result); 161af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 162af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 163af44c8236f7a73e71b16b707bba56f33af4d01cesewardj/** 164af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * Compute elementwise maximum. 165af44c8236f7a73e71b16b707bba56f33af4d01cesewardj */ 16641b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_combine)(VectorClock* const result, const VectorClock* const rhs) 167af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 168bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned i; 169bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned j; 170bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned shared; 171bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned new_size; 172bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 173bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(result); 174bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(rhs); 175bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 176bedfd237fbdc80d0c917cfcb85a94b5561c92633bart // First count the number of shared thread id's. 177bedfd237fbdc80d0c917cfcb85a94b5561c92633bart j = 0; 178bedfd237fbdc80d0c917cfcb85a94b5561c92633bart shared = 0; 179bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (i = 0; i < result->size; i++) 180bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 181bedfd237fbdc80d0c917cfcb85a94b5561c92633bart while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid) 182bedfd237fbdc80d0c917cfcb85a94b5561c92633bart j++; 183bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (j >= rhs->size) 184bedfd237fbdc80d0c917cfcb85a94b5561c92633bart break; 185bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (result->vc[i].threadid == rhs->vc[j].threadid) 186bedfd237fbdc80d0c917cfcb85a94b5561c92633bart shared++; 187bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 188bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 189bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_check)(result); 190bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 191bedfd237fbdc80d0c917cfcb85a94b5561c92633bart new_size = result->size + rhs->size - shared; 192bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (new_size > result->capacity) 193bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_reserve)(result, new_size); 194bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 195bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_check)(result); 196bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 197bedfd237fbdc80d0c917cfcb85a94b5561c92633bart // Next, combine both vector clocks into one. 198bedfd237fbdc80d0c917cfcb85a94b5561c92633bart i = 0; 199bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (j = 0; j < rhs->size; j++) 200bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 201bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* First of all, skip those clocks in result->vc[] for which there */ 202bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* is no corresponding clock in rhs->vc[]. */ 203bedfd237fbdc80d0c917cfcb85a94b5561c92633bart while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid) 204fbbac093a53913450580a8cc195e3bba932e3eb6bart { 205bedfd237fbdc80d0c917cfcb85a94b5561c92633bart i++; 206fbbac093a53913450580a8cc195e3bba932e3eb6bart } 207bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* If the end of *result is met, append rhs->vc[j] to *result. */ 208bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (i >= result->size) 209af44c8236f7a73e71b16b707bba56f33af4d01cesewardj { 210bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->size++; 211bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[i] = rhs->vc[j]; 212af44c8236f7a73e71b16b707bba56f33af4d01cesewardj } 213bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* If clock rhs->vc[j] is not in *result, insert it. */ 214bedfd237fbdc80d0c917cfcb85a94b5561c92633bart else if (result->vc[i].threadid > rhs->vc[j].threadid) 215fbbac093a53913450580a8cc195e3bba932e3eb6bart { 216bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned k; 217bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (k = result->size; k > i; k--) 218bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 219bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[k] = result->vc[k - 1]; 220bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 221bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->size++; 222bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[i] = rhs->vc[j]; 223fbbac093a53913450580a8cc195e3bba932e3eb6bart } 224bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* Otherwise, both *result and *rhs have a clock for thread */ 225bedfd237fbdc80d0c917cfcb85a94b5561c92633bart /* result->vc[i].threadid == rhs->vc[j].threadid. Compute the maximum. */ 226bedfd237fbdc80d0c917cfcb85a94b5561c92633bart else 227fbbac093a53913450580a8cc195e3bba932e3eb6bart { 228bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(result->vc[i].threadid == rhs->vc[j].threadid); 229bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (rhs->vc[j].count > result->vc[i].count) 230bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 231bedfd237fbdc80d0c917cfcb85a94b5561c92633bart result->vc[i].count = rhs->vc[j].count; 232bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 233fbbac093a53913450580a8cc195e3bba932e3eb6bart } 234bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 235bedfd237fbdc80d0c917cfcb85a94b5561c92633bart DRD_(vc_check)(result); 236bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(result->size == new_size); 237af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 238af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 23941b226c0a9c60c7dc10b09b6d71138f1993259d8bart/** Print the contents of vector clock 'vc'. */ 24041b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_print)(const VectorClock* const vc) 241af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 24219f91bbaedb4caef8a60ce94b0f507193cc0bc10florian HChar* str; 243bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 2448f822af9b234e7c553c408eba65a641c4773457fbart if ((str = DRD_(vc_aprint)(vc)) != NULL) 245bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 2468f822af9b234e7c553c408eba65a641c4773457fbart VG_(printf)("%s", str); 2478f822af9b234e7c553c408eba65a641c4773457fbart VG_(free)(str); 248bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 249af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 250af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 25141b226c0a9c60c7dc10b09b6d71138f1993259d8bart/** 2528f822af9b234e7c553c408eba65a641c4773457fbart * Print the contents of vector clock 'vc' to a newly allocated string. 2538f822af9b234e7c553c408eba65a641c4773457fbart * The caller must call VG_(free)() on the return value of this function. 25441b226c0a9c60c7dc10b09b6d71138f1993259d8bart */ 25519f91bbaedb4caef8a60ce94b0f507193cc0bc10florianHChar* DRD_(vc_aprint)(const VectorClock* const vc) 256af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 257bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned i; 2588f822af9b234e7c553c408eba65a641c4773457fbart unsigned reserved; 2598f822af9b234e7c553c408eba65a641c4773457fbart unsigned size; 26019f91bbaedb4caef8a60ce94b0f507193cc0bc10florian HChar* str = 0; 261bedfd237fbdc80d0c917cfcb85a94b5561c92633bart 262bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc); 2638f822af9b234e7c553c408eba65a641c4773457fbart reserved = 64; 2648f822af9b234e7c553c408eba65a641c4773457fbart size = 0; 2658f822af9b234e7c553c408eba65a641c4773457fbart str = VG_(realloc)("drd.vc.aprint.1", str, reserved); 2668f822af9b234e7c553c408eba65a641c4773457fbart if (! str) 2678f822af9b234e7c553c408eba65a641c4773457fbart return str; 2688f822af9b234e7c553c408eba65a641c4773457fbart size += VG_(snprintf)(str, reserved, "["); 269bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (i = 0; i < vc->size; i++) 270bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 271bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc->vc); 2728f822af9b234e7c553c408eba65a641c4773457fbart if (VG_(strlen)(str) + 32 > reserved) 273bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 2748f822af9b234e7c553c408eba65a641c4773457fbart reserved *= 2; 2758f822af9b234e7c553c408eba65a641c4773457fbart str = VG_(realloc)("drd.vc.aprint.2", str, reserved); 2768f822af9b234e7c553c408eba65a641c4773457fbart if (! str) 2778f822af9b234e7c553c408eba65a641c4773457fbart return str; 278bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 2798f822af9b234e7c553c408eba65a641c4773457fbart size += VG_(snprintf)(str + size, reserved - size, 280ea71ffb08eccc0869c5b9421160fef4052e35c23florian "%s %u: %u", i > 0 ? "," : "", 2818f822af9b234e7c553c408eba65a641c4773457fbart vc->vc[i].threadid, vc->vc[i].count); 282bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 2838f822af9b234e7c553c408eba65a641c4773457fbart size += VG_(snprintf)(str + size, reserved - size, " ]"); 2848f822af9b234e7c553c408eba65a641c4773457fbart 2858f822af9b234e7c553c408eba65a641c4773457fbart return str; 286af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 287af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 288af44c8236f7a73e71b16b707bba56f33af4d01cesewardj/** 289af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * Invariant test. 29041b226c0a9c60c7dc10b09b6d71138f1993259d8bart * 29141b226c0a9c60c7dc10b09b6d71138f1993259d8bart * The function below tests whether the following two conditions are 29241b226c0a9c60c7dc10b09b6d71138f1993259d8bart * satisfied: 29341b226c0a9c60c7dc10b09b6d71138f1993259d8bart * - size <= capacity. 29441b226c0a9c60c7dc10b09b6d71138f1993259d8bart * - Vector clock elements are stored in thread ID order. 29541b226c0a9c60c7dc10b09b6d71138f1993259d8bart * 29641b226c0a9c60c7dc10b09b6d71138f1993259d8bart * If one of these conditions is not met, an assertion failure is triggered. 297af44c8236f7a73e71b16b707bba56f33af4d01cesewardj */ 29841b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_check)(const VectorClock* const vc) 299af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 300bedfd237fbdc80d0c917cfcb85a94b5561c92633bart unsigned i; 30152048382ad36b96f505e46a5e6ca9bef795551e9bart 302bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc->size <= vc->capacity); 30352048382ad36b96f505e46a5e6ca9bef795551e9bart 304bedfd237fbdc80d0c917cfcb85a94b5561c92633bart for (i = 1; i < vc->size; i++) 305bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid); 306af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 307af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 308af44c8236f7a73e71b16b707bba56f33af4d01cesewardj/** 309af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * Change the size of the memory block pointed at by vc->vc. 310af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * Changes capacity, but does not change size. If the size of the memory 311af44c8236f7a73e71b16b707bba56f33af4d01cesewardj * block is increased, the newly allocated memory is not initialized. 312af44c8236f7a73e71b16b707bba56f33af4d01cesewardj */ 313af44c8236f7a73e71b16b707bba56f33af4d01cesewardjstatic 31441b226c0a9c60c7dc10b09b6d71138f1993259d8bartvoid DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity) 315af44c8236f7a73e71b16b707bba56f33af4d01cesewardj{ 316bedfd237fbdc80d0c917cfcb85a94b5561c92633bart tl_assert(vc); 3178f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->capacity > VC_PREALLOCATED 3188f822af9b234e7c553c408eba65a641c4773457fbart || vc->vc == 0 3198f822af9b234e7c553c408eba65a641c4773457fbart || vc->vc == vc->preallocated); 3208f822af9b234e7c553c408eba65a641c4773457fbart 321bedfd237fbdc80d0c917cfcb85a94b5561c92633bart if (new_capacity > vc->capacity) 322bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 3238f822af9b234e7c553c408eba65a641c4773457fbart if (vc->vc && vc->capacity > VC_PREALLOCATED) 324bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 3258f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->vc 3268f822af9b234e7c553c408eba65a641c4773457fbart && vc->vc != vc->preallocated 3278f822af9b234e7c553c408eba65a641c4773457fbart && vc->capacity > VC_PREALLOCATED); 328bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->vc = VG_(realloc)("drd.vc.vr.1", 329bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->vc, new_capacity * sizeof(vc->vc[0])); 330bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 3318f822af9b234e7c553c408eba65a641c4773457fbart else if (vc->vc && new_capacity > VC_PREALLOCATED) 332bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 3338f822af9b234e7c553c408eba65a641c4773457fbart tl_assert((vc->vc == 0 || vc->vc == vc->preallocated) 3348f822af9b234e7c553c408eba65a641c4773457fbart && new_capacity > VC_PREALLOCATED 3358f822af9b234e7c553c408eba65a641c4773457fbart && vc->capacity <= VC_PREALLOCATED); 336bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->vc = VG_(malloc)("drd.vc.vr.2", 337bedfd237fbdc80d0c917cfcb85a94b5561c92633bart new_capacity * sizeof(vc->vc[0])); 3388f822af9b234e7c553c408eba65a641c4773457fbart VG_(memcpy)(vc->vc, vc->preallocated, 3398f822af9b234e7c553c408eba65a641c4773457fbart vc->capacity * sizeof(vc->vc[0])); 3408f822af9b234e7c553c408eba65a641c4773457fbart } 3418f822af9b234e7c553c408eba65a641c4773457fbart else if (vc->vc) 3428f822af9b234e7c553c408eba65a641c4773457fbart { 3438f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->vc == vc->preallocated 3448f822af9b234e7c553c408eba65a641c4773457fbart && new_capacity <= VC_PREALLOCATED 3458f822af9b234e7c553c408eba65a641c4773457fbart && vc->capacity <= VC_PREALLOCATED); 3468f822af9b234e7c553c408eba65a641c4773457fbart } 3478f822af9b234e7c553c408eba65a641c4773457fbart else if (new_capacity > VC_PREALLOCATED) 3488f822af9b234e7c553c408eba65a641c4773457fbart { 3498f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->vc == 0 3508f822af9b234e7c553c408eba65a641c4773457fbart && new_capacity > VC_PREALLOCATED 3518f822af9b234e7c553c408eba65a641c4773457fbart && vc->capacity == 0); 3528f822af9b234e7c553c408eba65a641c4773457fbart vc->vc = VG_(malloc)("drd.vc.vr.3", 3538f822af9b234e7c553c408eba65a641c4773457fbart new_capacity * sizeof(vc->vc[0])); 354bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 355bedfd237fbdc80d0c917cfcb85a94b5561c92633bart else 356bedfd237fbdc80d0c917cfcb85a94b5561c92633bart { 3578f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->vc == 0 3588f822af9b234e7c553c408eba65a641c4773457fbart && new_capacity <= VC_PREALLOCATED 3598f822af9b234e7c553c408eba65a641c4773457fbart && vc->capacity == 0); 3608f822af9b234e7c553c408eba65a641c4773457fbart vc->vc = vc->preallocated; 361bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 362bedfd237fbdc80d0c917cfcb85a94b5561c92633bart vc->capacity = new_capacity; 363bedfd237fbdc80d0c917cfcb85a94b5561c92633bart } 36448fcfc637d883e24ddc10233b17a5198d352eddebart else if (new_capacity == 0 && vc->vc) 36548fcfc637d883e24ddc10233b17a5198d352eddebart { 3668f822af9b234e7c553c408eba65a641c4773457fbart if (vc->capacity > VC_PREALLOCATED) 3678f822af9b234e7c553c408eba65a641c4773457fbart VG_(free)(vc->vc); 36848fcfc637d883e24ddc10233b17a5198d352eddebart vc->vc = 0; 3698f822af9b234e7c553c408eba65a641c4773457fbart vc->capacity = 0; 37048fcfc637d883e24ddc10233b17a5198d352eddebart } 371af44c8236f7a73e71b16b707bba56f33af4d01cesewardj 3728f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(new_capacity == 0 || vc->vc != 0); 3738f822af9b234e7c553c408eba65a641c4773457fbart tl_assert(vc->capacity > VC_PREALLOCATED 3748f822af9b234e7c553c408eba65a641c4773457fbart || vc->vc == 0 3758f822af9b234e7c553c408eba65a641c4773457fbart || vc->vc == vc->preallocated); 376af44c8236f7a73e71b16b707bba56f33af4d01cesewardj} 377