src/kernel/activity/MutexImpl.hpp

   1 /* Copyright (c) 2012-2023. 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 #ifndef SIMGRID_KERNEL_ACTIVITY_MUTEX_HPP
   7 #define SIMGRID_KERNEL_ACTIVITY_MUTEX_HPP
   8
   9 #include "simgrid/s4u/Mutex.hpp"
  10 #include "src/kernel/activity/ActivityImpl.hpp"
  11 #include "src/kernel/actor/ActorImpl.hpp"
  12 #include <boost/intrusive/list.hpp>
  13
  14 namespace simgrid::kernel::activity {
  15
  16 /** Mutex Acquisition: the act / process of acquiring the mutex.
  17  *
  18  * You can declare some interest on a mutex without being blocked waiting if it's already occupied.
  19  * If it gets freed by its current owned, you become the new owner, even if you're still not blocked on it.
  20  * Nobody can lock it behind your back or overpass you in the queue in any way, even if you're still not blocked on it.
  21  *
  22  * Afterward, when you do consider the lock, the test() or wait() operations are both non-blocking since you're the
  23  * owner. People who declared interest in the mutex after you get stuck in the queue behind you.
  24  *
  25  *
  26  * Splitting the locking process this way is interesting for symmetry with the other activities such as exec or
  27  * communication that do have an async variant and could be mildly interesting to the users once exposed in S4U, but
  28  * that's not the only reason. It's also very important to the MC world: the Mutex::lock_async() is always enabled
  29  * (nothing can prevent you from adding yourself to the queue of potential owners) while Acquisition::wait() is
  30  * persistent: it's not always enabled but once it gets enabled (because you're the owner), it remains enabled for ever.
  31  *
  32  * Mutex::lock() is not persistent: sometimes it's enabled if the mutex is free, and then it gets disabled if
  33  * someone else locks the mutex, and then it becomes enabled again once the mutex is freed. This is why Mutex::lock()
  34  * is not used in our MC computational model: we ban non-persistent transitions because they would make some
  35  * computations much more complex.
  36  *
  37  * In particular, computing the extension of an unfolding's configuration is polynomial when you only have persistent
  38  * transitions while it's O(2^n) when some of the transitions are non-persistent (you have to consider again all subsets
  39  * of a set if some transitions may become disabled in between, while you don't have to reconsider them if you can reuse
  40  * your previous computations).
  41  */
  42 class XBT_PUBLIC MutexAcquisitionImpl : public ActivityImpl_T<MutexAcquisitionImpl> {
  43   actor::ActorImpl* issuer_ = nullptr;
  44   MutexImpl* mutex_         = nullptr;
  45   int recursive_depth_      = 1;
  46   // TODO: use granted_ this instead of owner_ == self to test().
  47   // This is mandatory to get double-lock on non-recursive locks to properly deadlock
  48   bool granted_ = false;
  49
  50   friend MutexImpl;
  51
  52 public:
  53   MutexAcquisitionImpl(actor::ActorImpl* issuer, MutexImpl* mutex) : issuer_(issuer), mutex_(mutex) {}
  54   MutexImplPtr get_mutex() { return mutex_; }
  55   actor::ActorImpl* get_issuer() { return issuer_; }
  56   void grant() { granted_ = true; }
  57
  58   bool test(actor::ActorImpl* issuer = nullptr) override;
  59   void wait_for(actor::ActorImpl* issuer, double timeout) override;
  60   void finish() override;
  61   void set_exception(actor::ActorImpl* issuer) override
  62   { /* nothing to do */
  63   }
  64 };
  65
  66 class XBT_PUBLIC MutexImpl {
  67   std::atomic_int_fast32_t refcount_{1};
  68   s4u::Mutex piface_;
  69   actor::ActorImpl* owner_ = nullptr;
  70   std::deque<MutexAcquisitionImplPtr> ongoing_acquisitions_;
  71   static unsigned next_id_;
  72   unsigned id_ = next_id_++;
  73   bool is_recursive_  = false;
  74   int recursive_depth = 0;
  75
  76   friend MutexAcquisitionImpl;
  77
  78 public:
  79   MutexImpl(bool recursive = false) : piface_(this), is_recursive_(recursive) {}
  80   MutexImpl(MutexImpl const&) = delete;
  81   MutexImpl& operator=(MutexImpl const&) = delete;
  82
  83   MutexAcquisitionImplPtr lock_async(actor::ActorImpl* issuer);
  84   bool try_lock(actor::ActorImpl* issuer);
  85   void unlock(actor::ActorImpl* issuer);
  86   unsigned get_id() const { return id_; }
  87
  88   actor::ActorImpl* get_owner() const { return owner_; }
  89
  90   // boost::intrusive_ptr<Mutex> support:
  91   friend void intrusive_ptr_add_ref(MutexImpl* mutex)
  92   {
  93     XBT_ATTRIB_UNUSED auto previous = mutex->refcount_.fetch_add(1);
  94     xbt_assert(previous != 0);
  95   }
  96
  97   friend void intrusive_ptr_release(MutexImpl* mutex)
  98   {
  99     if (mutex->refcount_.fetch_sub(1) == 1)
 100       delete mutex;
 101   }
 102
 103   s4u::Mutex& mutex() { return piface_; }
 104 };
 105 } // namespace simgrid::kernel::activity
 106 #endif