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