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