semaphore.hpp (15968B)
1 /* Relacy Race Detector 2 * Copyright (c) 2008-2013, Dmitry S. Vyukov 3 * All rights reserved. 4 * This software is provided AS-IS with no warranty, either express or implied. 5 * This software is distributed under a license and may not be copied, 6 * modified or distributed except as expressly authorized under the 7 * terms of the license contained in the file LICENSE in this distribution. 8 */ 9 10 #ifndef RL_SEMAPHORE_HPP 11 #define RL_SEMAPHORE_HPP 12 #ifdef _MSC_VER 13 # pragma once 14 #endif 15 16 #include "../base.hpp" 17 #include "../context_base.hpp" 18 #include "../sync_var.hpp" 19 #include "../waitset.hpp" 20 #include "../signature.hpp" 21 22 23 namespace rl 24 { 25 26 enum sema_wakeup_reason 27 { 28 sema_wakeup_reason_success, 29 sema_wakeup_reason_failed, 30 sema_wakeup_reason_timeout, 31 sema_wakeup_reason_spurious, 32 }; 33 34 struct win_object 35 { 36 virtual void deinit(debug_info_param info) = 0; 37 virtual ~win_object() {} 38 }; 39 40 struct win_waitable_object : win_object 41 { 42 virtual sema_wakeup_reason wait(bool try_wait, bool is_timed, debug_info_param info) = 0; 43 virtual bool signal(debug_info_param info) = 0; 44 45 virtual bool is_signaled(debug_info_param info) = 0; 46 virtual void memory_acquire(debug_info_param info) = 0; 47 virtual void* prepare_wait(debug_info_param info) = 0; 48 }; 49 50 51 52 53 struct sema_data 54 { 55 virtual sema_wakeup_reason wait(bool try_wait, bool is_timed, debug_info_param info) = 0; 56 virtual bool post(unsigned count, unsigned& prev_count, debug_info_param info) = 0; 57 virtual int get_value(debug_info_param info) = 0; 58 virtual bool is_signaled(debug_info_param info) = 0; 59 virtual void memory_acquire(debug_info_param info) = 0; 60 virtual void* prepare_wait(debug_info_param info) = 0; 61 virtual ~sema_data() {} // just to calm down gcc 62 }; 63 64 65 66 67 template<thread_id_t thread_count> 68 class sema_data_impl : public sema_data 69 { 70 public: 71 sema_data_impl(bool spurious_wakeups, unsigned initial_count, unsigned max_count) 72 : spurious_wakeups_(spurious_wakeups) 73 , count_(initial_count) 74 , max_count_(max_count) 75 { 76 RL_VERIFY(max_count <= INT_MAX); 77 } 78 79 ~sema_data_impl() 80 { 81 //!!! detect destruction with waiters 82 } 83 84 struct wait_event 85 { 86 sema_data_impl* addr_; 87 bool try_wait_; 88 bool is_timed_; 89 unsigned count_; 90 sema_wakeup_reason reason_; 91 92 void output(std::ostream& s) const 93 { 94 s << "<" << std::hex << addr_ << std::dec << "> semaphore: "; 95 if (try_wait_) 96 s << "try_wait "; 97 else if (is_timed_) 98 s << "timed wait "; 99 else 100 s << "wait "; 101 102 if (reason_ == sema_wakeup_reason_success) 103 s << "succeeded "; 104 else if (reason_ == sema_wakeup_reason_failed) 105 s << "failed "; 106 else if (reason_ == sema_wakeup_reason_timeout) 107 s << "timed out "; 108 else if (reason_ == sema_wakeup_reason_spurious) 109 s << "spuriously failed "; 110 111 s << "new_count=" << count_; 112 } 113 }; 114 115 struct post_event 116 { 117 sema_data_impl* addr_; 118 unsigned value_; 119 unsigned count_; 120 bool result_; 121 thread_id_t unblocked_; 122 123 void output(std::ostream& s) const 124 { 125 s << "<" << std::hex << addr_ << std::dec << "> semaphore: "; 126 if (result_) 127 s << "post "; 128 else 129 s << "post FAILED "; 130 131 s << "value=" << value_; 132 s << " new_count=" << count_; 133 s << " unblocked=" << unblocked_; 134 } 135 }; 136 137 struct get_value_event 138 { 139 sema_data_impl* addr_; 140 unsigned count_; 141 142 void output(std::ostream& s) const 143 { 144 s << "<" << std::hex << addr_ << std::dec << "> semaphore: "; 145 s << "get_value count=" << count_; 146 } 147 }; 148 149 virtual sema_wakeup_reason wait(bool try_wait, 150 bool is_timed, 151 debug_info_param info) 152 { 153 context& c = ctx(); 154 c.sched(); 155 sign_.check(info); 156 157 sema_wakeup_reason reason = sema_wakeup_reason_success; 158 for (;;) 159 { 160 if (count_) 161 { 162 count_ -= 1; 163 sync_.acq_rel(c.threadx_); 164 reason = sema_wakeup_reason_success; 165 break; 166 } 167 168 if (try_wait) 169 { 170 sync_.acquire(c.threadx_); 171 reason = sema_wakeup_reason_failed; 172 break; 173 } 174 175 unpark_reason wr = ws_.park_current(c, is_timed, spurious_wakeups_, true, info); 176 if (unpark_reason_timeout == wr) 177 { 178 RL_VERIFY(is_timed); 179 sync_.acquire(c.threadx_); 180 reason = sema_wakeup_reason_timeout; 181 break; 182 } 183 else if (unpark_reason_spurious == wr) 184 { 185 RL_VERIFY(spurious_wakeups_); 186 sync_.acquire(c.threadx_); 187 reason = sema_wakeup_reason_spurious; 188 break; 189 } 190 else if (unpark_reason_normal == wr) 191 { 192 RL_VERIFY(count_ > 0); 193 count_ -= 1; 194 sync_.acq_rel(c.threadx_); 195 c.switch_back(info); 196 reason = sema_wakeup_reason_success; 197 break; 198 } 199 RL_VERIFY(false); 200 } 201 202 RL_HIST(wait_event) {this, try_wait, is_timed, count_, reason} RL_HIST_END(); 203 return reason; 204 } 205 206 virtual bool post(unsigned count, unsigned& prev_count, debug_info_param info) 207 { 208 context& c = ctx(); 209 c.sched(); 210 sign_.check(info); 211 212 bool result = false; 213 prev_count = count_; 214 thread_id_t unblocked = 0; 215 if (false == (count >= INT_MAX || count + count_ > max_count_)) 216 { 217 result = true; 218 count_ += count; 219 sync_.acq_rel(c.threadx_); 220 for (unsigned i = 0; i != count; ++i) 221 { 222 if (false == ws_.unpark_one(c, info)) 223 break; 224 unblocked += 1; 225 } 226 } 227 else 228 { 229 sync_.acquire(c.threadx_); 230 } 231 RL_HIST(post_event) {this, count, count_, result, unblocked} RL_HIST_END(); 232 return result; 233 } 234 235 virtual int get_value(debug_info_param info) 236 { 237 context& c = ctx(); 238 c.sched(); 239 sign_.check(info); 240 241 RL_VERIFY(count_ <= INT_MAX); 242 int result = (int)count_ - ws_.size(); 243 sync_.acquire(c.threadx_); 244 245 RL_HIST(get_value_event) {this, (unsigned)result} RL_HIST_END(); 246 return result; 247 } 248 249 private: 250 signature<0xaabb6634> sign_; 251 bool const spurious_wakeups_; 252 unsigned count_; 253 unsigned const max_count_; 254 waitset<thread_count> ws_; 255 sync_var<thread_count> sync_; 256 257 virtual bool is_signaled(debug_info_param info) 258 { 259 (void)info; 260 return count_ > 0; 261 } 262 263 virtual void memory_acquire(debug_info_param info) 264 { 265 (void)info; 266 sync_.acquire(ctx().threadx_); 267 } 268 269 virtual void* prepare_wait(debug_info_param info) 270 { 271 (void)info; 272 return &ws_; 273 } 274 275 RL_NOCOPY(sema_data_impl); 276 }; 277 278 279 280 template<typename tag_t> 281 class semaphore : public win_waitable_object 282 { 283 public: 284 semaphore() 285 : impl_() 286 { 287 } 288 289 semaphore(semaphore const&) 290 : impl_() 291 { 292 } 293 294 semaphore& operator = (semaphore const&) 295 { 296 return *this; 297 } 298 299 void init(bool spurious_wakeups, unsigned initial_count, unsigned max_count, debug_info_param info) 300 { 301 context& c = ctx(); 302 RL_ASSERT_IMPL(0 == impl_, test_result_double_initialization_of_semaphore, "", info); 303 sign_.check(info); 304 impl_ = c.sema_ctor(spurious_wakeups, initial_count, max_count); 305 } 306 307 void deinit(debug_info_param info) 308 { 309 context& c = ctx(); 310 check(info); 311 c.sema_dtor(impl_); 312 impl_ = 0; 313 } 314 315 virtual sema_wakeup_reason wait(bool try_wait, bool is_timed, debug_info_param info) 316 { 317 check(info); 318 return impl_->wait(try_wait, is_timed, info); 319 } 320 321 virtual bool signal(debug_info_param info) 322 { 323 unsigned prev_count = 0; 324 return post(1, prev_count, info); 325 } 326 327 bool post(unsigned count, unsigned& prev_count, debug_info_param info) 328 { 329 check(info); 330 return impl_->post(count, prev_count, info); 331 } 332 333 int get_value(debug_info_param info) 334 { 335 check(info); 336 return impl_->get_value(info); 337 } 338 339 private: 340 sema_data* impl_; 341 signature<0x228855dd> sign_; 342 343 sema_data* check(debug_info_param info) 344 { 345 RL_ASSERT_IMPL(impl_, test_result_usage_of_non_initialized_semaphore, "", info); 346 sign_.check(info); 347 return impl_; 348 } 349 350 virtual bool is_signaled(debug_info_param info) 351 { 352 return check(info)->is_signaled(info); 353 } 354 355 virtual void memory_acquire(debug_info_param info) 356 { 357 check(info)->memory_acquire(info); 358 } 359 360 virtual void* prepare_wait(debug_info_param info) 361 { 362 return check(info)->prepare_wait(info); 363 } 364 }; 365 366 367 368 struct wfmo_event 369 { 370 unsigned long count_; 371 bool wait_all_; 372 bool try_wait_; 373 bool is_timed_; 374 sema_wakeup_reason result_; 375 size_t signaled_; 376 377 void output(std::ostream& s) const 378 { 379 s << "WFMO: " 380 << "count=" << count_ 381 << ", wait_all=" << wait_all_ 382 << ", try_wait=" << try_wait_ 383 << ", is_timed=" << is_timed_ 384 << ", result="; 385 if (sema_wakeup_reason_success == result_) 386 { 387 s << "success"; 388 if (wait_all_ == false) 389 s << ", object=" << signaled_; 390 } 391 else 392 { 393 s << "timeout"; 394 } 395 } 396 }; 397 398 size_t const wfmo_max_objects = 32; 399 400 inline sema_wakeup_reason wait_for_multiple_objects( 401 size_t& signaled, 402 size_t count, 403 win_waitable_object** wo, 404 bool wait_all, 405 bool try_wait, 406 bool is_timed, 407 debug_info_param info) 408 { 409 context& c = ctx(); 410 c.sched(); 411 412 RL_VERIFY(count <= wfmo_max_objects); 413 void* ws [wfmo_max_objects]; 414 415 sema_wakeup_reason result = sema_wakeup_reason_failed; 416 signaled = 0; 417 418 if (wait_all) 419 { 420 for (;;) 421 { 422 unsigned long i = 0; 423 for (i = 0; i != count; ++i) 424 { 425 if (false == wo[i]->is_signaled(info)) 426 break; 427 } 428 if (i == count) 429 { 430 preemption_disabler pd (c); 431 for (i = 0; i != count; ++i) 432 { 433 sema_wakeup_reason r = wo[i]->wait(true, false, info); 434 RL_VERIFY(r == sema_wakeup_reason_success); 435 (void)r; 436 } 437 result = sema_wakeup_reason_success; 438 break; 439 } 440 else if (try_wait) 441 { 442 for (i = 0; i != count; ++i) 443 wo[i]->memory_acquire(info); 444 result = sema_wakeup_reason_timeout; 445 break; 446 } 447 else 448 { 449 for (i = 0; i != count; ++i) 450 { 451 ws[i] = wo[i]->prepare_wait(info); 452 } 453 unpark_reason reason = c.wfmo_park(ws, wo, (unsigned)count, !!wait_all, is_timed, info); 454 RL_VERIFY(unpark_reason_spurious != reason); 455 if (unpark_reason_timeout == reason) 456 { 457 for (i = 0; i != count; ++i) 458 wo[i]->memory_acquire(info); 459 result = sema_wakeup_reason_timeout; 460 break; 461 } 462 else if (unpark_reason_normal == reason) 463 { 464 { 465 preemption_disabler pd (c); 466 for (unsigned long i = 0; i != count; ++i) 467 { 468 RL_VERIFY(wo[i]->is_signaled(info)); 469 sema_wakeup_reason r = wo[i]->wait(true, false, info); 470 RL_VERIFY(r == sema_wakeup_reason_success); 471 (void)r; 472 } 473 } 474 c.switch_back(info); 475 result = sema_wakeup_reason_success; 476 break; 477 } 478 RL_VERIFY(false); 479 } 480 } 481 } 482 else 483 { 484 for (;;) 485 { 486 unsigned long i = 0; 487 for (i = 0; i != count; ++i) 488 { 489 if (true == wo[i]->is_signaled(info)) 490 break; 491 } 492 if (i != count) 493 { 494 preemption_disabler pd (c); 495 sema_wakeup_reason r = wo[i]->wait(true, false, info); 496 RL_VERIFY(r == sema_wakeup_reason_success); 497 (void)r; 498 signaled = i; 499 result = sema_wakeup_reason_success; 500 break; 501 } 502 else if (try_wait) 503 { 504 for (i = 0; i != count; ++i) 505 wo[i]->memory_acquire(info); 506 result = sema_wakeup_reason_timeout; 507 break; 508 } 509 else 510 { 511 for (i = 0; i != count; ++i) 512 { 513 ws[i] = wo[i]->prepare_wait(info); 514 } 515 unpark_reason reason = c.wfmo_park(ws, wo, (unsigned)count, !!wait_all, is_timed, info); 516 RL_VERIFY(unpark_reason_spurious != reason); 517 if (unpark_reason_timeout == reason) 518 { 519 for (i = 0; i != count; ++i) 520 wo[i]->memory_acquire(info); 521 result = sema_wakeup_reason_timeout; 522 break; 523 } 524 else if (unpark_reason_normal == reason) 525 { 526 unsigned long i = 0; 527 for (i = 0; i != count; ++i) 528 { 529 if (true == wo[i]->is_signaled(info)) 530 break; 531 } 532 RL_VERIFY(i != count); 533 { 534 preemption_disabler pd (c); 535 sema_wakeup_reason r = wo[i]->wait(true, false, info); 536 RL_VERIFY(r == sema_wakeup_reason_success); 537 (void)r; 538 } 539 c.switch_back(info); 540 signaled = i; 541 result = sema_wakeup_reason_success; 542 break; 543 } 544 RL_VERIFY(false); 545 } 546 } 547 } 548 549 RL_HIST(wfmo_event) {(unsigned)count, wait_all, try_wait, is_timed, result, signaled} RL_HIST_END(); 550 return result; 551 } 552 553 554 } 555 556 557 #endif 558