diff options
| -rw-r--r-- | libbuild2/scheduler.cxx | 146 | ||||
| -rw-r--r-- | libbuild2/scheduler.hxx | 13 |
2 files changed, 103 insertions, 56 deletions
diff --git a/libbuild2/scheduler.cxx b/libbuild2/scheduler.cxx index 8ac2b97..437f904 100644 --- a/libbuild2/scheduler.cxx +++ b/libbuild2/scheduler.cxx @@ -106,7 +106,7 @@ namespace build2 active_--; waiting_++; - progress_++; + progress_.fetch_add (1, memory_order_relaxed); if (waiting_ > stat_max_waiters_) stat_max_waiters_ = waiting_; @@ -122,60 +122,16 @@ namespace build2 { activate_helper (l); } - // @@ TODO: Redo as a separate "monitoring" thread. - // - // This still doesn't work for the phase lock case where we call - // deactivate and then go wait on a condition variable: we are doing - // deadlock detection while holding the lock that prevents other - // threads from making progress! - // -#if 0 else if (active_ == 0) { - // We may have a deadlock which can happen because of dependency cycles. + // Note that we tried to handle this directly in this thread but that + // wouldn't work for the phase lock case where we cal; deactivate and + // then go wait on a condition variable: we would be doing deadlock + // detection while holding the lock that prevents other threads from + // making progress! So it has to be a separate monitoring thread. // - // Relying on the active_ count alone is not precise enough, however: - // some threads might be transitioning between the active/waiting/ready - // states. Carefully accounting for this is not trivial, to say the - // least (especially in the face of spurious wakeups). So we are going - // to do a "fuzzy" deadlock detection by measuring "progress". The idea - // is that those transitions should be pretty short-lived and so if we - // wait for a couple of hundreds context switches, then we should be - // able to distinguish a real deadlock from the transition case. - // - size_t p (progress_); - - for (size_t i (0); i != 100; ++i) - { - l.unlock (); - this_thread::yield () is not enough. - l.lock (); - - if (p != progress_) - break; - } - - if (p == progress_) - { - // Reactivate and fail. - // - waiting_--; - active_++; - - // Shutting things down cleanly is tricky: we could have handled it in - // the scheduler (e.g., by setting a flag and then waking everyone up, - // similar to shutdown). But there could also be "external waiters" - // that have called deactivate() -- we have no way to wake those up. - // So for now we are going to abort (the nice thing about abort is if - // this is not a dependency cycle, then we have a core to examine). - // - error << "deadlock detected, can be caused by a dependency cycle" << - info << "re-run with -s to diagnose dependency cycles"; - - std::terminate (); - } + dead_condv_.notify_one (); } -#endif } void scheduler:: @@ -194,14 +150,14 @@ namespace build2 // waiting_--; ready_++; - progress_++; + progress_.fetch_add (1, memory_order_relaxed); while (!shutdown_ && active_ >= max_active_) ready_condv_.wait (l); ready_--; active_++; - progress_++; + progress_.fetch_add (1, memory_order_relaxed); if (shutdown_) throw_generic_error (ECANCELED); @@ -419,17 +375,23 @@ namespace build2 stat_max_waiters_ = 0; stat_wait_collisions_ = 0; - progress_ = 0; + progress_.store (0, memory_order_relaxed); for (size_t i (0); i != wait_queue_size_; ++i) wait_queue_[i].shutdown = false; shutdown_ = false; + + if (max_active_ != 1) + dead_thread_ = thread (deadlock_monitor, this); } void scheduler:: tune (size_t max_active) { + // Note that if we tune a parallel scheduler to run serially, we will + // still have the deadlock monitoring thread running. + if (max_active == 0) max_active = orig_max_active_; @@ -503,6 +465,15 @@ namespace build2 l.lock (); } + // Wait for the deadlock monitor (the only remaining thread). + // + if (orig_max_active_ != 1) // See tune() for why not max_active_. + { + l.unlock (); + dead_condv_.notify_one (); + dead_thread_.join (); + } + // Free the memory. // wait_queue_.reset (); @@ -783,10 +754,13 @@ namespace build2 s.active_--; - // While executing the tasks a thread might have become ready. + // While executing the tasks a thread might have become ready + // (equivalent logic to deactivate()). // if (s.ready_ != 0) s.ready_condv_.notify_one (); + else if (s.active_ == 0) + s.dead_condv_.notify_one (); } // Become idle and wait for a notification. @@ -817,4 +791,66 @@ namespace build2 queue (tq); return *tq; } + + void* scheduler:: + deadlock_monitor (void* d) + { + scheduler& s (*static_cast<scheduler*> (d)); + + lock l (s.mutex_); + while (!s.shutdown_) + { + s.dead_condv_.wait (l); + + while (s.active_ == 0 && !s.shutdown_) + { + // We may have a deadlock which can happen because of dependency + // cycles. + // + // Relying on the active_ count alone is not precise enough, however: + // some threads might be transitioning between active/waiting/ready + // states. Carefully accounting for this is not trivial, to say the + // least (especially in the face of spurious wakeups). So we are going + // to do a "fuzzy" deadlock detection by measuring "progress". The + // idea is that those transitions should be pretty short-lived and so + // if we wait for a few thousand context switches, then we should be + // able to distinguish a real deadlock from the transition case. + // + size_t op (s.progress_.load (memory_order_relaxed)), np (op); + + l.unlock (); + for (size_t i (0); op == np && i != 10000; ++i) + { + // We don't really need consume, but let's keep it to slow things + // down in case yield() is a noop. + // + this_thread::yield (); + np = s.progress_.load (memory_order_consume); + } + l.lock (); + + // Re-check active count for good measure (maybe spinning too fast). + // + if (np == op && s.active_ == 0 && !s.shutdown_) + { + // Shutting things down cleanly is tricky: we could have handled it + // in the scheduler (e.g., by setting a flag and then waking + // everyone up, similar to shutdown). But there could also be + // "external waiters" that have called deactivate() -- we have no + // way to wake those up. So for now we are going to abort (the nice + // thing about abort is if this is not a dependency cycle, then we + // have a core to examine). + // + error << "detected deadlock that could be caused by a dependency " + << "cycle" << + info << "re-run with -s to diagnose dependency cycles" << + info << "if not a dependency cycle, please report"; + + std::terminate (); + } + } + } + + return nullptr; + } } diff --git a/libbuild2/scheduler.hxx b/libbuild2/scheduler.hxx index 09c9e02..af1deba 100644 --- a/libbuild2/scheduler.hxx +++ b/libbuild2/scheduler.hxx @@ -440,7 +440,18 @@ namespace build2 // We increment it for each active->waiting->ready->active transition // and it is used for deadlock detection (see deactivate()). // - size_t progress_; + // Note that it still serves our purpose even if the value wraps around + // (e.g., on a 32-bit platform). + // + atomic_count progress_; + + // Deadlock detection. + // + std::thread dead_thread_; + std::condition_variable dead_condv_; + + static void* + deadlock_monitor (void*); // Wait queue. // |