src/kernel/actor/SimcallObserver.cpp

   1 /* Copyright (c) 2019-2022. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/kernel/actor/SimcallObserver.hpp"
   7 #include "simgrid/s4u/Host.hpp"
   8 #include "src/kernel/activity/CommImpl.hpp"
   9 #include "src/kernel/activity/MutexImpl.hpp"
  10 #include "src/kernel/actor/ActorImpl.hpp"
  11 #include "src/mc/mc_config.hpp"
  12
  13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_observer, mc, "Logging specific to MC simcall observation");
  14
  15 namespace simgrid {
  16 namespace kernel {
  17 namespace actor {
  18
  19 bool SimcallObserver::depends(SimcallObserver* other)
  20 {
  21   THROW_UNIMPLEMENTED;
  22 }
  23 /* Random is only dependent when issued by the same actor (ie, always independent) */
  24 bool RandomSimcall::depends(SimcallObserver* other)
  25 {
  26   return get_issuer() == other->get_issuer();
  27 }
  28 bool MutexSimcall::depends(SimcallObserver* other)
  29 {
  30   if (dynamic_cast<RandomSimcall*>(other) != nullptr)
  31     return other->depends(this); /* Other is random, that is very permissive. Use that relation instead. */
  32
  33 #if 0 /* This code is currently broken and shouldn't be used. We must implement asynchronous locks before */
  34   MutexSimcall* that = dynamic_cast<MutexSimcall*>(other);
  35   if (that == nullptr)
  36     return true; // Depends on anything we don't know
  37
  38   /* Theorem 4.4.7: Any pair of synchronization actions of distinct actors concerning distinct mutexes are independent */
  39   if (this->get_issuer() != that->get_issuer() && this->get_mutex() != that->get_mutex())
  40     return false;
  41
  42   /* Theorem 4.4.8 An AsyncMutexLock is independent with a MutexUnlock of another actor */
  43   if (((dynamic_cast<MutexLockSimcall*>(this) != nullptr && dynamic_cast<MutexUnlockSimcall*>(that)) ||
  44        (dynamic_cast<MutexLockSimcall*>(that) != nullptr && dynamic_cast<MutexUnlockSimcall*>(this))) &&
  45       get_issuer() != other->get_issuer())
  46     return false;
  47 #endif
  48   return true; // Depend on things we don't know for sure that they are independent
  49 }
  50
  51 std::string SimcallObserver::to_string(int /*times_considered*/) const
  52 {
  53   return simgrid::xbt::string_printf("[(%ld)%s (%s)] ", issuer_->get_pid(), issuer_->get_host()->get_cname(),
  54                                      issuer_->get_cname());
  55 }
  56
  57 std::string SimcallObserver::dot_label(int /*times_considered*/) const
  58 {
  59   if (issuer_->get_host())
  60     return xbt::string_printf("[(%ld)%s] ", issuer_->get_pid(), issuer_->get_host()->get_cname());
  61   return xbt::string_printf("[(%ld)] ", issuer_->get_pid());
  62 }
  63
  64 std::string RandomSimcall::to_string(int times_considered) const
  65 {
  66   return SimcallObserver::to_string(times_considered) + "MC_RANDOM(" + std::to_string(times_considered) + ")";
  67 }
  68
  69 std::string RandomSimcall::dot_label(int times_considered) const
  70 {
  71   return SimcallObserver::dot_label(times_considered) + "MC_RANDOM(" + std::to_string(next_value_) + ")";
  72 }
  73
  74 void RandomSimcall::prepare(int times_considered)
  75 {
  76   next_value_ = min_ + times_considered;
  77   XBT_DEBUG("MC_RANDOM(%d, %d) will return %d after %d times", min_, max_, next_value_, times_considered);
  78 }
  79
  80 int RandomSimcall::get_max_consider() const
  81 {
  82   return max_ - min_ + 1;
  83 }
  84
  85 std::string MutexUnlockSimcall::to_string(int times_considered) const
  86 {
  87   return SimcallObserver::to_string(times_considered) + "Mutex UNLOCK";
  88 }
  89
  90 std::string MutexUnlockSimcall::dot_label(int times_considered) const
  91 {
  92   return SimcallObserver::dot_label(times_considered) + "Mutex UNLOCK";
  93 }
  94
  95 std::string MutexLockSimcall::to_string(int times_considered) const
  96 {
  97   auto mutex      = get_mutex();
  98   std::string res = SimcallObserver::to_string(times_considered) + (blocking_ ? "Mutex LOCK" : "Mutex TRYLOCK");
  99   res += "(locked = " + std::to_string(mutex->is_locked());
 100   res += ", owner = " + std::to_string(mutex->get_owner() ? mutex->get_owner()->get_pid() : -1);
 101   res += ", sleeping = n/a)";
 102   return res;
 103 }
 104
 105 std::string MutexLockSimcall::dot_label(int times_considered) const
 106 {
 107   return SimcallObserver::dot_label(times_considered) + (blocking_ ? "Mutex LOCK" : "Mutex TRYLOCK");
 108 }
 109
 110 bool MutexLockSimcall::is_enabled() const
 111 {
 112   return not blocking_ || get_mutex()->get_owner() == nullptr || get_mutex()->get_owner() == get_issuer();
 113 }
 114
 115 std::string ConditionWaitSimcall::to_string(int times_considered) const
 116 {
 117   std::string res = SimcallObserver::to_string(times_considered) + "Condition WAIT";
 118   res += "(" + (timeout_ == -1.0 ? "" : std::to_string(timeout_)) + ")";
 119   return res;
 120 }
 121
 122 std::string ConditionWaitSimcall::dot_label(int times_considered) const
 123 {
 124   return SimcallObserver::dot_label(times_considered) + "Condition WAIT";
 125 }
 126
 127 bool ConditionWaitSimcall::is_enabled() const
 128 {
 129   static bool warned = false;
 130   if (not warned) {
 131     XBT_INFO("Using condition variables in model-checked code is still experimental. Use at your own risk");
 132     warned = true;
 133   }
 134   return true;
 135 }
 136
 137 std::string SemAcquireSimcall::to_string(int times_considered) const
 138 {
 139   std::string res = SimcallObserver::to_string(times_considered) + "Sem ACQUIRE";
 140   res += "(" + (timeout_ == -1.0 ? "" : std::to_string(timeout_)) + ")";
 141   return res;
 142 }
 143
 144 std::string SemAcquireSimcall::dot_label(int times_considered) const
 145 {
 146   return SimcallObserver::dot_label(times_considered) + "Sem ACQUIRE";
 147 }
 148
 149 bool SemAcquireSimcall::is_enabled() const
 150 {
 151   static bool warned = false;
 152   if (not warned) {
 153     XBT_INFO("Using semaphore in model-checked code is still experimental. Use at your own risk");
 154     warned = true;
 155   }
 156   return true;
 157 }
 158
 159 int ActivityTestanySimcall::get_max_consider() const
 160 {
 161   // Only Comms are of interest to MC for now. When all types of activities can be consider, this function can simply
 162   // return the size of activities_.
 163   int count = 0;
 164   for (const auto& act : activities_)
 165     if (dynamic_cast<activity::CommImpl*>(act) != nullptr)
 166       count++;
 167   return count;
 168 }
 169
 170 void ActivityTestanySimcall::prepare(int times_considered)
 171 {
 172   next_value_ = times_considered;
 173 }
 174
 175 std::string ActivityTestanySimcall::to_string(int times_considered) const
 176 {
 177   std::string res = SimcallObserver::to_string(times_considered);
 178   if (times_considered == -1) {
 179     res += "TestAny FALSE(-)";
 180   } else {
 181     res += "TestAny(" + xbt::string_printf("(%d of %zu)", times_considered + 1, activities_.size());
 182   }
 183
 184   return res;
 185 }
 186
 187 std::string ActivityTestanySimcall::dot_label(int times_considered) const
 188 {
 189   std::string res = SimcallObserver::dot_label(times_considered) + "TestAny ";
 190   if (times_considered == -1) {
 191     res += "FALSE";
 192   } else {
 193     res += xbt::string_printf("TRUE [%d of %zu]", times_considered + 1, activities_.size());
 194   }
 195   return res;
 196 }
 197
 198 bool ActivityTestSimcall::depends(SimcallObserver* other)
 199 {
 200   if (get_issuer() == other->get_issuer())
 201     return false;
 202
 203   if (dynamic_cast<ActivityTestSimcall*>(other))
 204     return true;
 205
 206   const auto* comm1 = dynamic_cast<activity::CommImpl*>(activity_);
 207   if (comm1 == nullptr)
 208     return false;
 209
 210   if (dynamic_cast<ActivityWaitSimcall*>(other) != nullptr &&
 211       (comm1->src_actor_.get() == nullptr || comm1->dst_actor_.get() == nullptr))
 212     return false;
 213
 214   if (comm1->src_buff_ == nullptr || comm1->dst_buff_ == nullptr)
 215     return false;
 216
 217   if (const auto* test = dynamic_cast<ActivityTestSimcall*>(other)) {
 218     const auto* comm2 = dynamic_cast<activity::CommImpl*>(test->get_activity());
 219     if (comm2 == nullptr)
 220       return false;
 221     else if (comm2->src_buff_ == nullptr || comm2->dst_buff_ == nullptr)
 222       return false;
 223   }
 224
 225   if (auto* wait = dynamic_cast<ActivityWaitSimcall*>(other)) {
 226     auto* comm2 = dynamic_cast<activity::CommImpl*>(wait->get_activity());
 227     if (comm2 == nullptr)
 228       return false;
 229     if (comm1->src_buff_ == comm2->src_buff_ && comm1->dst_buff_ == comm2->dst_buff_)
 230       return false;
 231     if (comm1->src_buff_ != nullptr && comm1->dst_buff_ != nullptr && comm2->src_buff_ != nullptr &&
 232         comm2->dst_buff_ != nullptr && comm1->dst_buff_ != comm2->src_buff_ && comm1->dst_buff_ != comm2->dst_buff_ &&
 233         comm2->dst_buff_ != comm1->src_buff_)
 234       return false;
 235   }
 236
 237   return true;
 238 }
 239
 240 std::string ActivityTestSimcall::to_string(int times_considered) const
 241 {
 242   std::string res = SimcallObserver::to_string(times_considered) + "Test ";
 243   auto* comm      = dynamic_cast<activity::CommImpl*>(activity_);
 244   if (comm) {
 245     if (comm->src_actor_.get() == nullptr || comm->dst_actor_.get() == nullptr) {
 246       res += "FALSE(comm=";
 247       res += XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p)", comm)
 248                                                                       : "(verbose only))";
 249     } else {
 250       res += "TRUE(comm=";
 251
 252       auto src = comm->src_actor_;
 253       auto dst = comm->dst_actor_;
 254       res +=
 255           XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p", comm) : "(verbose only) ";
 256       res += xbt::string_printf("[(%ld)%s (%s) ", src->get_pid(), src->get_host()->get_cname(), src->get_cname()) +
 257              "-> " +
 258              xbt::string_printf("(%ld)%s (%s)])", dst->get_pid(), dst->get_host()->get_cname(), dst->get_cname());
 259     }
 260   } else
 261     xbt_die("Only Comms are supported here for now");
 262   return res;
 263 }
 264
 265 std::string ActivityTestSimcall::dot_label(int times_considered) const
 266 {
 267   std::string res  = SimcallObserver::dot_label(times_considered) + "Test ";
 268   const auto* comm = dynamic_cast<activity::CommImpl*>(activity_);
 269   if (comm && (comm->src_actor_.get() == nullptr || comm->dst_actor_.get() == nullptr)) {
 270     res += "FALSE";
 271   } else {
 272     res += "TRUE";
 273   }
 274   return res;
 275 }
 276
 277 bool ActivityWaitSimcall::is_enabled() const
 278 {
 279   /* FIXME: check also that src and dst processes are not suspended */
 280   const auto* comm = dynamic_cast<activity::CommImpl*>(activity_);
 281   if (comm == nullptr)
 282     xbt_die("Only Comms are supported here for now");
 283
 284   if (comm->src_timeout_ || comm->dst_timeout_) {
 285     /* If it has a timeout it will be always be enabled (regardless of who declared the timeout),
 286      * because even if the communication is not ready, it can timeout and won't block. */
 287     if (_sg_mc_timeout == 1)
 288       return true;
 289   }
 290   /* On the other hand if it hasn't a timeout, check if the comm is ready.*/
 291   else if (comm->detached() && comm->src_actor_ == nullptr && comm->get_state() == activity::State::READY)
 292     return (comm->dst_actor_ != nullptr);
 293   return (comm->src_actor_ && comm->dst_actor_);
 294 }
 295
 296 bool ActivityWaitSimcall::depends(SimcallObserver* other)
 297 {
 298   if (get_issuer() == other->get_issuer())
 299     return false;
 300
 301   if (auto* isend = dynamic_cast<CommIsendSimcall*>(other))
 302     return isend->depends(this);
 303
 304   if (auto* irecv = dynamic_cast<CommIrecvSimcall*>(other))
 305     return irecv->depends(this);
 306
 307   /* Timeouts in wait transitions are not considered by the independence theorem, thus assumed dependent */
 308   if (const auto* wait = dynamic_cast<ActivityWaitSimcall*>(other)) {
 309     if (timeout_ > 0 || wait->get_timeout() > 0)
 310       return true;
 311     const auto* comm1 = dynamic_cast<activity::CommImpl*>(activity_);
 312     const auto* comm2 = dynamic_cast<activity::CommImpl*>(wait->get_activity());
 313
 314     if (comm1 == nullptr || comm2 == nullptr) // One wait at least in not on a Comm
 315       return true;
 316
 317     if (comm1->src_buff_ == comm2->src_buff_ && comm1->dst_buff_ == comm2->dst_buff_)
 318       return false;
 319     if (comm1->src_buff_ != nullptr && comm1->dst_buff_ != nullptr && comm2->src_buff_ != nullptr &&
 320         comm2->dst_buff_ != nullptr && comm1->dst_buff_ != comm2->src_buff_ && comm1->dst_buff_ != comm2->dst_buff_ &&
 321         comm2->dst_buff_ != comm1->src_buff_)
 322       return false;
 323   }
 324
 325   return true;
 326 }
 327
 328 std::string ActivityWaitSimcall::to_string(int times_considered) const
 329 {
 330   std::string res = SimcallObserver::to_string(times_considered);
 331   auto* comm      = dynamic_cast<activity::CommImpl*>(activity_);
 332   if (comm == nullptr) {
 333     res += "ActivityWait on non-Comm (FIXME)"; // FIXME
 334     return res;
 335   }
 336
 337   if (times_considered == -1) {
 338     res += "WaitTimeout(comm=" + (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose)
 339                                       ? xbt::string_printf("%p)", comm)
 340                                       : "(verbose only))");
 341   } else {
 342     res += "Wait(comm=";
 343
 344     auto src = comm->src_actor_;
 345     auto dst = comm->dst_actor_;
 346     res +=
 347         XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p", comm) : "(verbose only) ";
 348     res += xbt::string_printf("[(%ld)%s (%s) ", src->get_pid(), src->get_host()->get_cname(), src->get_cname()) +
 349            "-> " + xbt::string_printf("(%ld)%s (%s)])", dst->get_pid(), dst->get_host()->get_cname(), dst->get_cname());
 350   }
 351   return res;
 352 }
 353
 354 std::string ActivityWaitSimcall::dot_label(int times_considered) const
 355 {
 356   std::string res = SimcallObserver::dot_label(times_considered);
 357   res += (times_considered == -1) ? "WaitTimeout " : "Wait ";
 358
 359   const auto* comm = dynamic_cast<activity::CommImpl*>(activity_);
 360   if (comm) {
 361     auto src = comm->src_actor_;
 362     auto dst = comm->dst_actor_;
 363     res += " [(" + std::to_string(src ? src->get_pid() : 0) + ")";
 364     res += "->(" + std::to_string(dst ? dst->get_pid() : 0) + ")]";
 365   } else
 366     xbt_die("Only Comms are supported here for now");
 367   return res;
 368 }
 369
 370 std::string ActivityWaitanySimcall::dot_label(int times_considered) const
 371 {
 372   return SimcallObserver::dot_label(times_considered) +
 373          xbt::string_printf("WaitAny [%d of %zu]", times_considered + 1, activities_.size());
 374 }
 375
 376 bool ActivityWaitanySimcall::is_enabled() const
 377 {
 378   // FIXME: deal with other kind of activities (Exec and I/Os)
 379   // FIXME: Can be factored with ActivityWaitSimcall::is_enabled()
 380   const auto* comm = dynamic_cast<activity::CommImpl*>(activities_[next_value_]);
 381   if (comm == nullptr)
 382     xbt_die("Only Comms are supported here for now");
 383   if (comm->src_timeout_ || comm->dst_timeout_) {
 384     /* If it has a timeout it will be always be enabled (regardless of who declared the timeout),
 385      * because even if the communication is not ready, it can timeout and won't block. */
 386     if (_sg_mc_timeout == 1)
 387       return true;
 388   }
 389   /* On the other hand if it hasn't a timeout, check if the comm is ready.*/
 390   else if (comm->detached() && comm->src_actor_ == nullptr && comm->get_state() == activity::State::READY)
 391     return (comm->dst_actor_ != nullptr);
 392   return (comm->src_actor_ && comm->dst_actor_);
 393 }
 394
 395 int ActivityWaitanySimcall::get_max_consider() const
 396 {
 397   return static_cast<int>(activities_.size());
 398 }
 399
 400 void ActivityWaitanySimcall::prepare(int times_considered)
 401 {
 402   next_value_ = times_considered;
 403 }
 404
 405 std::string ActivityWaitanySimcall::to_string(int times_considered) const
 406 {
 407   std::string res = SimcallObserver::to_string(times_considered) + "WaitAny(";
 408   size_t count    = activities_.size();
 409   if (count > 0) {
 410     if (auto* comm = dynamic_cast<kernel::activity::CommImpl*>(activities_[times_considered]))
 411       res += "comm=" +
 412              (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p", comm)
 413                                                                        : "(verbose only)") +
 414              xbt::string_printf("(%d of %zu))", times_considered + 1, count);
 415     else
 416       xbt_die("Only Comms are supported here for now");
 417   } else
 418     res += "comm at idx " + std::to_string(times_considered) + ")";
 419   return res;
 420 }
 421
 422 bool CommIsendSimcall::depends(SimcallObserver* other)
 423 {
 424   if (get_issuer() == other->get_issuer())
 425     return false;
 426
 427   if (const auto* other_isend = dynamic_cast<CommIsendSimcall*>(other))
 428     return mbox_ == other_isend->get_mailbox();
 429
 430   // FIXME: Not in the former dependency check because of the ordering but seems logical to add it
 431   if (dynamic_cast<CommIrecvSimcall*>(other) != nullptr)
 432     return false;
 433
 434 #if SIMGRID_HAVE_MC // FIXME needed to access mbox_cpy
 435   if (const auto* wait = dynamic_cast<ActivityWaitSimcall*>(other)) {
 436     if (const auto* comm2 = dynamic_cast<activity::CommImpl*>(wait->get_activity())) { // this is a Comm::wait_for
 437       const auto* mbox1 = mbox_;
 438       const auto* mbox2 = comm2->mbox_cpy;
 439
 440       if (mbox1 != mbox2 && wait->get_timeout() <= 0)
 441         return false;
 442
 443       if ((get_issuer() != comm2->src_actor_.get()) && (get_issuer() != comm2->dst_actor_.get()) &&
 444           wait->get_timeout() <= 0)
 445         return false;
 446
 447       if (comm2->type_ == activity::CommImpl::Type::SEND && comm2->src_buff_ != src_buff_ && wait->get_timeout() <= 0)
 448         return false;
 449     }
 450   }
 451 #endif
 452   /* FIXME: the following rule assumes that the result of the isend/irecv call is not stored in a buffer used in the
 453    * test call. */
 454 #if 0
 455   if (dynamic_cast<ActivityTestSimcall*>(other))
 456     return false;
 457 #endif
 458
 459   return true;
 460 }
 461
 462 std::string CommIsendSimcall::to_string(int times_considered) const
 463 {
 464   std::string res = SimcallObserver::to_string(times_considered) + "iSend(";
 465   res += xbt::string_printf("src=(%ld)%s (%s)", get_issuer()->get_pid(), get_issuer()->get_host()->get_cname(),
 466                             get_issuer()->get_cname());
 467   res += ", buff=" + (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p", src_buff_)
 468                                                                                : "(verbose only)");
 469   res += ", size=" +
 470          (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? std::to_string(src_buff_size_) : "(verbose only)");
 471   res += ")";
 472   return res;
 473 }
 474
 475 bool CommIrecvSimcall::depends(SimcallObserver* other)
 476 {
 477   if (get_issuer() == other->get_issuer())
 478     return false;
 479
 480   if (const auto* other_irecv = dynamic_cast<CommIrecvSimcall*>(other))
 481     return mbox_ == other_irecv->get_mailbox();
 482
 483   if (auto* isend = dynamic_cast<CommIsendSimcall*>(other))
 484     return isend->depends(this);
 485
 486 #if SIMGRID_HAVE_MC // FIXME needed to access mbox_cpy
 487   if (auto* wait = dynamic_cast<ActivityWaitSimcall*>(other)) {
 488     if (auto* comm2 = dynamic_cast<activity::CommImpl*>(wait->get_activity())) { // this is a Comm::wait_for
 489       const auto* mbox1 = mbox_;
 490       const auto* mbox2 = comm2->mbox_cpy;
 491
 492       if (mbox1 != mbox2 && wait->get_timeout() <= 0)
 493         return false;
 494
 495       if ((get_issuer() != comm2->src_actor_.get()) && (get_issuer() != comm2->dst_actor_.get()) &&
 496           wait->get_timeout() <= 0)
 497         return false;
 498
 499       if (comm2->type_ == activity::CommImpl::Type::RECEIVE && comm2->dst_buff_ != dst_buff_ &&
 500           wait->get_timeout() <= 0)
 501         return false;
 502     }
 503   }
 504 #endif
 505   /* FIXME: the following rule assumes that the result of the isend/irecv call is not stored in a buffer used in the
 506    * test call. */
 507 #if 0
 508   if (dynamic_cast<ActivityTestSimcall*>(other))
 509     return false;
 510 #endif
 511
 512   return true;
 513 }
 514
 515 std::string CommIrecvSimcall::to_string(int times_considered) const
 516 {
 517   std::string res = SimcallObserver::to_string(times_considered) + "iRecv(";
 518   res += xbt::string_printf("dst=(%ld)%s (%s)", get_issuer()->get_pid(), get_issuer()->get_host()->get_cname(),
 519                             get_issuer()->get_cname());
 520   res += ", buff=" + (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? xbt::string_printf("%p", dst_buff_)
 521                                                                                : "(verbose only)");
 522   res += ", size=" + (XBT_LOG_ISENABLED(mc_observer, xbt_log_priority_verbose) ? std::to_string(*dst_buff_size_)
 523                                                                                : "(verbose only)");
 524   res += ")";
 525   return res;
 526 }
 527
 528 } // namespace actor
 529 } // namespace kernel
 530 } // namespace simgrid