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