Duncan Coutts pushed to branch wip/io-manager-deadlock-detection at Glasgow Haskell Compiler / GHC Commits: 78bd27ee by Duncan Coutts at 2026-09-25T00:36:44+01:00 Add a long Note [Deadlock detection] It describes the historical and modern designs and their trade-offs. The point is we've now unified the code for deadlock detection between the threaded and non-threaded ways, by changing the non-threaded to follow the same design as the threaded. - - - - - d2fd72bc by Duncan Coutts at 2026-09-25T00:36:44+01:00 Refactor the utils providing the I/O timeout for different system APIs We have to provide a timeout in three different time formats (int milliseconds, struct timeval *, and struct timespec *). These are for platform APIs including poll, select, ppoll, pselect, epoll_wait, epoll_wait2 and in future kevent and io_uring. Previously we had one util for each format that both worked out what the timeout should be and converted it into the particular format. This duplicates some logic and it also makes it awkward to modify the timeout value (since there's no common format). Modifying the timeout value is exactly what we want to do, in a subsequent commit, where we want to adjust the timeout to take account of idle GC. - - - - - 6852893f by Duncan Coutts at 2026-09-25T00:36:44+01:00 Update the old select I/O manager to use the new timeout utils This will make it much easier to adjust the timeout to take account of idle GC. - - - - - b7396c21 by Duncan Coutts at 2026-09-25T12:11:25+01:00 Add opportunistic deadlock detection without idle GC Our general design is now that comprehensive deadlock detection relies on idle GC. This allows us to detect partial deadlocks that are not system deadlocks. But it's not prompt. It's a nice to have feature to be able to promptly detect the cases that are system deadlocks. There's no hope to do this in the threaded RTS with -N > 1, but it can be done for the non-threaded RTS and _could_ be done for the threaded RTS with -N1. We can integrate this feature into the general design without too many contortions. We just need the I/O managers to check before sleeping if they would be about to sleep indefinately with no I/O and no registered signal handlers. If so, they can notify the idle GC that we're deadlocked and we schedule and idle GC. - - - - - a5374fcb by Duncan Coutts at 2026-09-25T12:11:25+01:00 Add idle GC mode for !HAVE_PREEMPTION We have to do idle GC (and thus deadlock detection) differently when we do not have the ticker and the ability to interrupt the I/O manager when it's blocking. - - - - - e4b06281 by Duncan Coutts at 2026-09-25T12:11:25+01:00 Add and use USED_IF_PREEMPTION to avoid warnings - - - - - d9aa5a88 by Duncan Coutts at 2026-09-25T12:11:26+01:00 Add performDeadlockDetection and export via ghc-experimental When documenting the idle GC and deadlock detection behaviour in the user guide, it becomes obiovus that in some cases one would want manual control over deadlock detection. In particular, for applications that disable idle GC, for debugging or robustness, they may want to invoke deadlock detecting GC manually. Bind it in ghc-internal GHC.Internal.System.Mem and re-export via ghc-experimental in System.Mem.Experimental. It is clearly implementation specific behaviour, especially since in GHC the deadlock detection is tied to doing a major GC. - - - - - 3711b41a by Duncan Coutts at 2026-09-25T12:11:26+01:00 Add tests for deadlock detection, issue #26408 We have three tests: T26408a: make sure that we can detect a /partial deadlock/ that is not also a /system deadlock/ T26408b: make sure that we can detect a /system deadlock/ promptly without relying on idle GC T26408c: make sure that we do not falsely detect a deadlock when there is nothing to do except wait on signals - - - - - f3468063 by Duncan Coutts at 2026-09-25T12:11:26+01:00 Update the user guide with the revised idle GC behaviour It's now not just for the threaded RTS, but general. Add a new section in the RTS chapter: Idle GC and deadlock detection. Provide general documentation on both topics. In particular, document the behaviour of deadlock detection and how it depends on idle GC. Move the existing entries for -I and -Iw to this section. Add a changelog entry. - - - - - 29 changed files: - + changelog.d/idle-gc-and-deadlock-detection - docs/users_guide/profiling.rst - docs/users_guide/runtime_control.rst - libraries/ghc-experimental/src/System/Mem/Experimental.hs - libraries/ghc-internal/src/GHC/Internal/System/Mem.hs - rts/IdleGC.c - rts/IdleGC.h - rts/RtsFlags.c - rts/RtsSymbols.c - rts/Schedule.c - rts/Timer.c - rts/include/rts/OSThreads.h - rts/include/rts/storage/GC.h - rts/posix/Poll.c - rts/posix/Select.c - rts/posix/SelectBis.c - rts/posix/Timeout.c - rts/posix/Timeout.h - rts/win32/AsyncMIO.c - testsuite/tests/interface-stability/ghc-experimental-exports.stdout - testsuite/tests/interface-stability/ghc-experimental-exports.stdout-mingw32 - testsuite/tests/rts/Makefile - + testsuite/tests/rts/T26408a.hs - + testsuite/tests/rts/T26408a.stderr - + testsuite/tests/rts/T26408b.hs - + testsuite/tests/rts/T26408b.stderr - + testsuite/tests/rts/T26408c.hs - + testsuite/tests/rts/T26408c.stdout - testsuite/tests/rts/all.T Changes: ===================================== changelog.d/idle-gc-and-deadlock-detection ===================================== @@ -0,0 +1,22 @@ +section: rts +issues: #27040 #26408 +mrs: !14820 +synopsis: Idle GC and deadlock detection in the non-threaded RTS now behave the same as in the threaded RTS +description: { +Idle GC now works in the non-threaded RTS and is enabled by default. + +Deadlock detection in the non-threaded RTS now follows the same design and +behaviour as in the threaded RTS. In particular, it can detect partial +deadlocks where some but not all threads are deadlocked. The detection is no +longer prompt however, as the detection runs as part of idle GC, which (by +default) is performed 0.3 seconds after all capabilities become idle. + +The user guide now documents that deadlock detection relies on idle GC, +and thus turning off idle GC disables deadlock detection. This is true +of the threaded RTS in previous GHC releases but it was not previously +documented behaviour. + +Internally, the idle GC and deadlock detection now follow the same design and +use 99% the same code between the non-threaded and threaded RTS. Having a +single design improves the comprehension and maintainability of the RTS code. +} ===================================== docs/users_guide/profiling.rst ===================================== @@ -691,11 +691,13 @@ enclosed between ``+RTS ... -RTS`` as usual): order to increase the resolution of the time profiler. Using a value of zero disables the RTS clock completely, and has the - effect of disabling timers that depend on it: the context switch - timer and the heap profiling timer. Context switches will still - happen, but deterministically and at a rate much faster than normal. - Disabling the interval timer is useful for debugging, because it - eliminates a source of non-determinism at runtime. + effect of disabling the timers and features that depend on it: the context + switch timer, the heap profiling timer, the eventlog flush timer, and the + idle GC timer. Context switches will still happen, but deterministically + and at a rate much faster than normal. Disabling the interval timer is + useful for debugging, because it eliminates a source of non-determinism at + runtime. Note however that disabling the idle GC timer not only disables + idle GC but also deadlock detection (see rts-flag:`-I`). .. rts-flag:: -xc ===================================== docs/users_guide/runtime_control.rst ===================================== @@ -731,61 +731,6 @@ performance. the default small ``-A`` value is suboptimal, as it can be in programs that create large amounts of long-lived data. -.. rts-flag:: -I ⟨seconds⟩ - - :default: 0.3 seconds in the threaded runtime, 0 in the non-threaded runtime - - .. index:: - single: idle GC - - Set the amount of idle time which must pass before a idle GC is - performed. Setting ``-I0`` disables the idle GC. - - In the threaded and SMP versions of the RTS (see :ghc-flag:`-threaded`, - :ref:`options-linker`), a major GC is automatically performed if the - runtime has been idle (no Haskell computation has been running) for a - period of time. - - For an interactive application, it is probably a good idea to use - the idle GC, because this will allow finalizers to run and - deadlocked threads to be detected in the idle time when no Haskell - computation is happening. Also, it will mean that a GC is less - likely to happen when the application is busy, and so responsiveness - may be improved. However, if the amount of live data in the heap is - particularly large, then the idle GC can cause a significant delay, - and too small an interval could adversely affect interactive - responsiveness. - - The idle period timer only resets after some activity - by a Haskell thread. If your program is doing literally nothing then - after the first idle collection is triggered then no more future collections - will be scheduled until more work is performed. - - This is an experimental feature, please let us know if it causes - problems and/or could benefit from further tuning. - -.. rts-flag:: -Iw ⟨seconds⟩ - - :default: 0 seconds - - .. index:: - single: idle GC - - Set the minimum wait time between runs of the idle GC. - - By default, if idle GC is enabled in the threaded runtime, a major - GC will be performed every time the process goes idle for a - sufficiently long duration (see :rts-flag:`-I ⟨seconds⟩`). For - large server processes accepting regular but infrequent requests - (e.g., once per second), an expensive, major GC may run after - every request. As an alternative to shutting off idle GC entirely - (with ``-I0``), a minimum wait time between idle GCs can be - specified with this flag. For example, ``-Iw60`` will ensure that - an idle GC runs at most once per minute. - - This is an experimental feature, please let us know if it causes - problems and/or could benefit from further tuning. - .. rts-flag:: -ki ⟨size⟩ :default: 1k @@ -1011,6 +956,116 @@ performance. ``GHC.Stats.getRTSStats`` from Haskell. +Idle GC and deadlock detection +------------------------------ + +The RTS performs idle GC and deadlock detection. These features are more +closely related and dependent than one might expect. In particular, deadlock +detection relies on idle GC. + +The primary purpose of idle GC is to reclaim memory and return it to the system +when the application has been idle for a short time. It also gives an +opportunity for finalisers to run more promptly. See :rts-flag:`-I ⟨seconds⟩`. + +Deadlock detection is a debugging feature to try to discover when some or all +Haskell threads are deadlocked. For the purpose of this explanation we define: + + * a "partial deadlock" to be a set of threads that are deadlocked; and + * a "system deadlock" is when all threads are deadlocked. + +The deadlock detection is implemented by the GC, and it is capable of detecting +partial deadlocks. If a deadlock is discovered, the RTS will throw an +asynchronous exception to (some or all of) the blocked threads to enable +progress and enable better reporting of the problem. In particular it throws +the async exceptions ``BlockedIndefinitelyOnMVar`` or +``BlockedIndefinitelyOnSTM``, as appropriate. + +The deadlock detection can be run during a major GC, but it is more expensive +than a normal major GC so it is not run during normal major GCs. The deadlock +detection mode of GC is run by the idle GC. This is on the basis that when the +application is idle is when we are most likely to find a deadlock, and also +that the extra time cost is unlikely to be a problem because the application is +already idle. + +There are a few consequence of this: + + * Deadlock detection relies on idle GC and will not run if idle GC is disabled + with ``-I0``. + * Deadlock detection will not run if the application remains busy, and thus + idle GC is not invoked. + * Deadlock detection is not prompt: it will only occur after the idle GC + delay, depending on both :rts-flag:`-I ⟨seconds⟩` and + :rts-flag:`-Iw ⟨seconds⟩`. + +In the non-threaded RTS there is additional behaviour: system deadlocks will be +detected promptly, and this works even if idle GC is otherwise disabled. + +One cannot rely on deadlock detection as part of the normal program behaviour. +It should only be used for debugging. Firstly, deadlock detection can be +disabled or indefinately deferred due to activity. Secondly, the set of threads +that deadlock detection throws exceptions to is not guaranteed to be minimal: +a thread waiting on a deadlocked thread may also have an exception thrown to it +even if it could make progress after the deadlocked thread is terminated. + +Deadlock detection can be invoked manually using ``performDeadlockDetection`` +from ``System.Mem.Experimental``. + + +.. rts-flag:: -I ⟨seconds⟩ + + :default: 0.3 seconds + + .. index:: + single: idle GC + + A major GC is automatically performed if the runtime has been idle (no + Haskell computation has been running) for a period of time. Set the amount + of idle time which must pass before a idle GC is performed. + + Setting ``-I0`` disables the idle GC. This also has the unfortunate side + effect of disabling thread deadlock detection (the implementation of which + uses the idle GC). + + For an interactive application, it is probably a good idea to use + the idle GC, because this will allow finalizers to run and + deadlocked threads to be detected in the idle time when no Haskell + computation is happening. Also, it will mean that a GC is less + likely to happen when the application is busy, and so responsiveness + may be improved. However, if the amount of live data in the heap is + particularly large, then the idle GC can cause a significant delay, + and too small an interval could adversely affect interactive + responsiveness. + + The idle period timer only resets after some activity + by a Haskell thread. If your program is doing literally nothing then + after the first idle collection is triggered then no more future collections + will be scheduled until more work is performed. + + Please let us know if it causes problems and/or could benefit from further + tuning. + +.. rts-flag:: -Iw ⟨seconds⟩ + + :default: 0 seconds + + .. index:: + single: idle GC + + Set the minimum wait time between runs of the idle GC. + + By default (and if idle GC is not disabled) a major + GC will be performed every time the process goes idle for a + sufficiently long duration (see :rts-flag:`-I ⟨seconds⟩`). For + large server processes accepting regular but infrequent requests + (e.g., once per second), an expensive, major GC may run after + every request. As an alternative to shutting off idle GC entirely + (with ``-I0``), a minimum wait time between idle GCs can be + specified with this flag. For example, ``-Iw60`` will ensure that + an idle GC runs at most once per minute. + + This is an experimental feature, please let us know if it causes + problems and/or could benefit from further tuning. + .. _rts-options-statistics: ===================================== libraries/ghc-experimental/src/System/Mem/Experimental.hs ===================================== @@ -1,5 +1,10 @@ module System.Mem.Experimental - ( setGlobalAllocationLimitHandler + ( + -- * Garbage collection + performDeadlockDetection + + -- * Allocation counter and limits + , setGlobalAllocationLimitHandler , AllocationLimitKillBehaviour(..) , getAllocationCounterFor , setAllocationCounterFor @@ -8,3 +13,4 @@ module System.Mem.Experimental ) where import GHC.Internal.AllocationLimitHandler +import GHC.Internal.System.Mem ===================================== libraries/ghc-internal/src/GHC/Internal/System/Mem.hs ===================================== @@ -19,9 +19,10 @@ module GHC.Internal.System.Mem ( -- * Garbage collection performGC + , performMinorGC , performMajorGC , performBlockingMajorGC - , performMinorGC + , performDeadlockDetection -- * Allocation counter and limits , setAllocationCounter @@ -52,3 +53,16 @@ foreign import ccall "performBlockingMajorGC" performBlockingMajorGC :: IO () -- -- @since base-4.7.0.0 foreign import ccall "performGC" performMinorGC :: IO () + +-- | Triggers an immediate major garbage collection in deadlock detection mode. +-- This will detect any threads that are deadlocked and throw asynchronous +-- exceptions to them. +-- +-- Normally, deadlock detection is done automatically and it is rarely useful +-- to invoke manually. However, since deadlock detection in GHC is performed +-- by idle GC, which some applications disable, then it may be useful to +-- invoke deadlock detection manually for the purpose of debugging or +-- resilliance. +-- +-- @since ghc-internal-10.100.0 +foreign import ccall "performDeadlockDetection" performDeadlockDetection :: IO () ===================================== rts/IdleGC.c ===================================== @@ -54,6 +54,198 @@ automatic GCs. Both timers must expire before an automatic GC is triggered. See issue #11134 for additional detail. + + Historically, the non-threaded runtime did not perform idle GC at all, and + thus implemented deadlock detection differently. See Note [Deadlock detection] + for the current and historical designs. + + The design for idle GC is (now) the same for the threaded and non-threaded + RTS ways, with the only difference being in how wakeUpRts works. However, in + the non-threaded RTS mode without preemption there is a design difference in + how to schedule idle GC. See Note [Idle GC without preemption]. + + +Note [Idle GC without preemption] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +On non-threaded platforms without pre-emption, e.g. wasm, we have to use a +different design for scheduling idle GC (and thus deadlock detection, see +Note [Deadlock detection]). + +Instead of a ticker thread that interrupts the idle capability after some delay, +we arrange for the I/O manager to only sleep for a maximum of the idle GC delay +time. The function getNextIdleGcDelayTime() returns this time, accounting for +the interIdleGCWait. + +Then if that timeout is reached the I/O manager calls notifyIdleGcIdle(), +which schedules an idle GC (by seting the recent activity state). The I/O +manager must then behave as if it had been interrupted (as happens with the +threaded idle GC design). + +See adjustTimeoutForIdleGc() and handleIdleGcTimeout(), which are the helper +functions used by the in-RTS I/O managers on posix platforms to implement this. + +See Note [GC During Idle Time] for the general design. + + +Note [Deadlock detection] +~~~~~~~~~~~~~~~~~~~~~~~~~ + +For the purpose of this explanation we define: + * a /partial deadlock/ to be a set of threads that are deadlocked; and + * a /system deadlock/ is when all threads are deadlocked. + +Obviously, we can have a partial deadlock without having a system +deadlock. The design goal of deadlock detection is to guarantee to +detect (and resolve) system deadlock, but to also try to detect (and +resolve) partial deadlocks. + +There are two designs that the RTS has used for deadlock detection: a +simple historical design originally used in the non-threaded RTS and a +modern design for the threaded RTS. These days we use the modern design +in both the threaded and non-threaded RTS. + +A high level way to think about the two designs is as follows: + 1. the historical design looks for situations in which there *must* be + a system deadlock; whereas + 2. the modern design looks for partial deadlocks opportunistically, + with the guarantee that if the overall system is deadlocked that we + will *eventually* detect this. + +An advantage of the historical design is that it will detect system +deadlock promptly. A disadvantage is that it will never detect a +partial deadlock (that isn't also a system deadlock). + +The modern design can detect partial deadlock, but it is not guaranteed +to detect system deadlock promptly, just eventually. + +The mechanism for deadlock detection is garbage collection. GC can be +instructed to look for deadlocked threads and if it finds them to throw +exceptions to one or more threads involved in the deadlock. This +mechanism can find partial deadlocks. It is however expensive -- more +expensive than a normal major GC. So the difference in the historical +and modern designs is in when we do this expensive GC check. + +The historical design +--------------------- + +When there was just one capability, as in the single threaded RTS, it +is possible to follow a very simple design. When there are no runnable +threads, and no threads blocked on pending I/O or on timers then there +*must* be a deadlock. And thus running deadlock detection promptly in +this situation is guaranteed to find the deadlock and wake up one or +more threads. Thus we can guarantee afterwards that there are runnable +threads. + +There are a couple problems with this design, but the biggest problem +is that it cannot be extended to multiple capabilities. When there are +multiple capabilities then the fact that there are no runnable threads +on the current capability says nothing about runnable threads on other +capabilities. Runnable threads elsewhere might wake up threads on this +capability, and so there is no implication that there is a deadlock. + +The other problems with this design are: + 1. it cannot find genuine deadlocks when there are any unrelated + threads blocked on I/O or timers (see issue #26408); and + 2. it requires treating signals specially. + +The problem with signals is that they're a weird kind of I/O. Threads +do not block waiting on signals. Rather signals can have handlers such +that when a signal arrives, a new thread is started to execute the +handler. This means it doesn't neatly fit into the condition "no +threads blocked on pending I/O or on timers". And if we did shoehorn it +into that definition then we would not look for deadlocks if there were +any signal handlers registered, and we would still end up with no +runnable threads after skipping deadlock detection, which violates the +post-condition that there be runnable threads. So the solution was that +after deadlock detection, if there are still no runnable threads and +there are registered signal handlers then we conclude we must wait for +a signal to be received -- which will start a thread and thus we will +end up with runnable threads. But of course this is horrible: we have +entangled two features far too tightly: deadlock detection with a weird +-- and platform specific -- kind of I/O. + +The modern design +----------------- + +A change of perspective is required. Instead of thinking of conditions +in which there must be a deadlock, we simply look for deadlocks in such +a way in which we will eventually find deadlocks if they exist. A +benefit of this approach is that we can find deadlocks that the simple +approach cannot. For example we can find deadlocks when there are +unrelated threads blocked on I/O or timers (see issue #26408). + +The question is when to run GC in its more expensive deadlock detection +mode. We obviously do not want to do it too frequently. The design +choice is to do it during idle GC, at least sometimes. Idle GC is only +run some time after all capabilities go idle. This is a good +opportunity. We know there are no runnable threads on the capability, +so there *might* be a deadlock, and when there's nothing else to do is +also a good moment to do a more expensive GC. + +The idle GC is controlled by the RecentActivity status, which +progresses through 4 stages: yes, maybe_no, inactive, done_gc. We only +invoke a deadlock-detecting major GC in the inactive state. We get into +the inactive state when: + * the timer tick goes off + * we were already in the maybe_no state (which itself requires no + activity on any capability for a whole timer tick) + * idle GC is enabled + * it's been long enough since the most recent idle GC. +This timer tick also wakes up the I/O manager to ensue we get back to +the scheduler, and thus to scheduleDetectDeadlock. + +Note that this means that deadlock detection is disabled if users +disable idle GC (by setting +RTS -I0). Historically, idle GC was not +used by default in the non-threaded RTS, but the modern design relies +on it, so it is enabled by default in all cases. + +But if idle GC is enabled, then if there is a full system deadlock then +eventually we will run a major GC with deadlock detection and detect +and resolve the deadlock. It is not prompt. It must wait at least for +an idle GC, which by default is 0.3s after all capabilities go idle. + +Furthermore, there is no post-condition for scheduleDetectDeadlock, +because of the non-prompt "eventually" nature of the deadlock detection +design. In particular there can still be no runnable threads. In the +threaded RTS if there's no runnable threads after this we will yield the +capability, while in the non-threaded we will ask the I/O manager to +block and wait for I/O, timers or signals. + +See also Note [Deadlock detection under the nonmoving collector]. + + +Note [Deadlock detection without idle GC] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +In Note [Deadlock detection] above we noted that: + +> the historical design looks for situations in which there *must* be + a system deadlock. + +We can still take advantage of these situations, but instead of basing the +whole design around it, we use it opportunistically, and in a way that involves +minimal changes to the general design. + +Specifically, in the case of a single capability (so we have a global view), if +the I/O manager would be about to block indefinitely, with no I/O pending, then +we have a strong suspicion that there is a system deadlock. + +In this case, I/O manager informs the idle GC system via notifyIdleGcDeadlock. +Typically it will then behave as if the I/O manager had been interrupted and +return to the scheduler. We can do this promptly, and we can do so even if idle +GC in general is disabled (e.g. via -I0). This fits into the existing design +because it can behave just as if there had been an idle GC timeout. + +There is one very subtle case to note: we can have situations where there's no +deadlock detected but yet there are no runnable threads, no timers and no +pending I/O. There can also be signals with signal handlers that could wake up +and unblock things (e.g. if a handler closure has access to a TVar/MVar that +other threads are blocked on). To make this case work, the I/O manager has to +ask notifyIdleGcDeadlock if it should should return to the scheduler, or +continue and block. And notifyIdleGcDeadlock will tell it to continue if an +idle GC has already been completed (with no intervening activity) since this is +the situation where there is no deadlock. See test T26408c. */ @@ -112,6 +304,8 @@ bool isIdleGcPending(void) return (getRecentActivity() == ACTIVITY_INACTIVE); } +#if defined(THREADED_IDLEGC) + /* - countdown for minimum idle time before we start a GC (set by -I) */ static int idle_ticks_to_gc = 0; @@ -169,6 +363,58 @@ void handleIdleGcTick(void) } } +#else // !defined(THREADED_IDLEGC) + +static Time last_idle_gc_time = 0; + +Time getNextIdleGcDelayTime(void) +{ + if (getRecentActivity() == ACTIVITY_DONE_GC) return -1; // indefinite + + Time now = getProcessElapsedTime(); + Time delay = + stg_max (last_idle_gc_time + RtsFlags.GcFlags.interIdleGCWait - now, + RtsFlags.GcFlags.idleGCDelayTime); + ASSERT(delay >= 0); + return delay; +} + +void notifyIdleGcIdle(void) +{ + if (RtsFlags.GcFlags.doIdleGC && getRecentActivity() < ACTIVITY_INACTIVE) { + setRecentActivity(ACTIVITY_INACTIVE); + } +} + +#endif // defined(THREADED_IDLEGC) + +/* If the I/O manager can see that there is very likely a deadlock (no I/O and + * no timers) then it lets us know. If we have not already done an idle GC then + * we schedule one idle GC. If we did already do an idle GC and thus did not + * find a deadlock then we'll arrange to continue and block (waiting for signals + * only). + */ +bool notifyIdleGcDeadlock(void) +{ + /* We do this even if RtsFlags.GcFlags.doIdleGC is turned off. + * + * But if we've already done a GC and didn't detect anything, + * i.e. ACTIVITY_DONE_GC, then continue and block. This will + * wait for signals that could unwedge things. + * + * Caution: if we get this wrong we can loop doing deadlock detecting GCs + * that find nothing! See test T26408c that checks we get this right. + */ + if (getRecentActivity() < ACTIVITY_INACTIVE) { + setRecentActivity(ACTIVITY_INACTIVE); + /* Instruct to interrupt, return to scheduler and do idle GC. */ + return true; + } else { + /* Instruct not to interrupt, to continue and block on signals. */ + return false; + } +} + void notifyIdleGcActive(void) { switch (getRecentActivity()) @@ -208,6 +454,9 @@ void notifyIdleGcDone(bool force_major) setRecentActivity(ACTIVITY_DONE_GC); #if !defined(PROFILING) pauseTimer(); +#endif +#if !defined(THREADED_IDLEGC) + last_idle_gc_time = getProcessElapsedTime(); #endif break; } ===================================== rts/IdleGC.h ===================================== @@ -12,6 +12,15 @@ #include "BeginPrivate.h" +/* See Note [GC During Idle Time] */ + +#if defined(HAVE_PREEMPTION) +#define THREADED_IDLEGC +#else +/* See Note [Idle GC without preemption] */ +#endif + + /* Are we in a state where we are want an idle GC to occur? * Used in Capability globalWorkToDo() and Schedule scheduleDetectDeadlock. */ @@ -23,7 +32,24 @@ void notifyIdleGcActive(void); /* Called from schedule(), specifically scheduleDoGC() */ void notifyIdleGcDone(bool force_major); +/* Called from I/O managers before waiting if there is almost certainly + * a deadlock. + */ +bool notifyIdleGcDeadlock(void); + +#if defined(THREADED_IDLEGC) + /* Called from handle_tick() */ void handleIdleGcTick(void); +#else // !defined(THREADED_IDLEGC) + +/* Called from I/O managers before waiting */ +Time getNextIdleGcDelayTime(void); + +/* Called from I/O managers after waiting */ +void notifyIdleGcIdle(void); + +#endif + #include "EndPrivate.h" ===================================== rts/RtsFlags.c ===================================== @@ -1914,8 +1914,13 @@ static void normaliseRtsOpts (void) // If the master timer is disabled, turn off the other timers. if (RtsFlags.MiscFlags.tickInterval == 0) { RtsFlags.ConcFlags.ctxtSwitchTime = 0; +#if defined(HAVE_PREEMPTION) RtsFlags.GcFlags.idleGCDelayTime = 0; RtsFlags.GcFlags.doIdleGC = false; +#else + /* We use idleGCDelayTime and doIdleGC without timers. + * See Note [Idle GC without preemption] */ +#endif RtsFlags.ProfFlags.heapProfileInterval = 0; } @@ -1928,11 +1933,16 @@ static void normaliseRtsOpts (void) RtsFlags.MiscFlags.tickInterval); } +#if defined(HAVE_PREEMPTION) if (RtsFlags.GcFlags.idleGCDelayTime > 0) { RtsFlags.MiscFlags.tickInterval = stg_min(RtsFlags.GcFlags.idleGCDelayTime, RtsFlags.MiscFlags.tickInterval); } +#else + /* We use idleGCDelayTime and doIdleGC without timers. + * See Note [Idle GC without preemption] */ +#endif if (RtsFlags.ProfFlags.heapProfileInterval > 0) { RtsFlags.MiscFlags.tickInterval = ===================================== rts/RtsSymbols.c ===================================== @@ -696,6 +696,7 @@ extern char **environ; SymI_HasProto(performGC) \ SymI_HasProto(performMajorGC) \ SymI_HasProto(performBlockingMajorGC) \ + SymI_HasProto(performDeadlockDetection) \ SymI_HasProto(prog_argc) \ SymI_HasProto(prog_argv) \ SymI_HasDataProto(stg_putMVarzh) \ ===================================== rts/Schedule.c ===================================== @@ -298,6 +298,7 @@ schedule (Capability *initialCapability, Task *task) schedulePushWork(cap,task); if (emptyRunQueue(cap)) { + /* When we have no threads to run, we *might* have a deadlock. */ scheduleDetectDeadlock(&cap,task); } @@ -825,18 +826,19 @@ schedulePushWork(Capability *cap USED_IF_THREADS, } /* ---------------------------------------------------------------------------- - * Detect deadlock conditions and attempt to resolve them. + * Perform idle GC and deadlock detection. + * + * We don't make any decisions right here, we just invoke GC with deadlock + * detection if the idle GC tracking subsystem has decided that we're in + * a state where we should (via isIdleGcPending). + * + * See Note [Deadlock detection]. + * * ------------------------------------------------------------------------- */ static void scheduleDetectDeadlock (Capability **pcap, Task *task) { - /* - * Detect deadlock: when we have no threads to run, there are no - * threads blocked, waiting for I/O, or sleeping, and all the - * other tasks are waiting for work, we must have a deadlock of - * some description. - */ if (isIdleGcPending()) { debugTrace(DEBUG_sched, "maybe deadlocked, forcing major GC..."); @@ -2698,7 +2700,7 @@ freeScheduler( void ) -------------------------------------------------------------------------- */ static void -performGC_(bool force_major, bool nonconcurrent) +performGC_(bool force_major, bool deadlock_detect, bool nonconcurrent) { Task *task; Capability *cap = NULL; @@ -2711,7 +2713,7 @@ performGC_(bool force_major, bool nonconcurrent) // TODO: do we need to traceTask*() here? waitForCapability(&cap,task); - scheduleDoGC(&cap,task,force_major,false,false,nonconcurrent); + scheduleDoGC(&cap,task,force_major,false,deadlock_detect,nonconcurrent); releaseCapability(cap); exitMyTask(); } @@ -2719,19 +2721,33 @@ performGC_(bool force_major, bool nonconcurrent) void performGC(void) { - performGC_(false, false); + performGC_(false /*force_major*/, + false /*deadlock_detect*/, + false /*nonconcurrent*/); } void performMajorGC(void) { - performGC_(true, false); + performGC_(true /*force_major*/, + false /*deadlock_detect*/, + false /*nonconcurrent*/); } void performBlockingMajorGC(void) { - performGC_(true, true); + performGC_(true /*force_major*/, + false /*deadlock_detect*/, + true /*nonconcurrent*/); +} + +void +performDeadlockDetection(void) +{ + performGC_(true /*force_major*/, + true /*deadlock_detect*/, + false /*nonconcurrent*/); } /* --------------------------------------------------------------------------- ===================================== rts/Timer.c ===================================== @@ -68,7 +68,9 @@ handle_tick(int unused STG_UNUSED) } #endif +#if defined(THREADED_IDLEGC) handleIdleGcTick(); +#endif } void initTimer(void) ===================================== rts/include/rts/OSThreads.h ===================================== @@ -54,6 +54,12 @@ // however at the moment we cannot due to issue #27346. #endif +#if defined(HAVE_PREEMPTION) +#define USED_IF_PREEMPTION +#else +#define USED_IF_PREEMPTION STG_UNUSED +#endif + #if defined(HAVE_PTHREAD_H) && !defined(mingw32_HOST_OS) #if defined(CMINUSMINUS) ===================================== rts/include/rts/storage/GC.h ===================================== @@ -290,6 +290,7 @@ void setAllocLimitKill(bool, bool); void performGC(void); void performMajorGC(void); void performBlockingMajorGC(void); +void performDeadlockDetection(void); // Implemented as a mode of major GC /* ----------------------------------------------------------------------------- The CAF table - used to let us revert CAFs in GHCi ===================================== rts/posix/Poll.c ===================================== @@ -369,13 +369,14 @@ void pollCompletedTimeoutsOrIOPoll(CapIOManager *iomgr) if (!isEmptyClosureTable(&iomgr->aiop_table)) { + int n_aiops = sizeClosureTable(&iomgr->aiop_table); #if defined(HAVE_PREEMPTION) /* the full_poll_table includes interrupt_fd_r */ - nfds_t nfds = sizeClosureTable(&iomgr->aiop_table) + 1; + nfds_t nfds = n_aiops + 1; struct pollfd *poll_table = iomgr->full_poll_table; #else /* the aiop_poll_table does not include interrupt_fd_r */ - nfds_t nfds = sizeClosureTable(&iomgr->aiop_table) + 0; + nfds_t nfds = n_aiops + 0; struct pollfd *poll_table = iomgr->aiop_poll_table; #endif @@ -387,13 +388,13 @@ void pollCompletedTimeoutsOrIOPoll(CapIOManager *iomgr) int res = ppoll(poll_table, nfds, &tv, NULL); debugTrace(DEBUG_iomanager, - "ppoll(nfds = %lu, timeout.sec = 0, timeout.nsec = 0) = %d", + "ppoll(nfds = %lu, timeout = 0) = %d", (unsigned long) nfds, res); #else int res = poll(poll_table, nfds, 0); debugTrace(DEBUG_iomanager, - "poll(nfds = %lu, timeout_ms = 0) = %d", + "poll(nfds = %lu, timeout = 0) = %d", (unsigned long) nfds, res); #endif if (res == 0) { @@ -448,43 +449,54 @@ bool awaitCompletedTimeoutsOrIOPoll(CapIOManager *iomgr) */ bool wait = emptyRunQueue(iomgr->cap); + int n_aiops = sizeClosureTable(&iomgr->aiop_table); #if defined(HAVE_PREEMPTION) /* the full_poll_table includes interrupt_fd_r */ - nfds_t nfds = sizeClosureTable(&iomgr->aiop_table) + 1; + nfds_t nfds = n_aiops + 1; struct pollfd *poll_table = iomgr->full_poll_table; #else /* the aiop_poll_table does not include interrupt_fd_r */ - nfds_t nfds = sizeClosureTable(&iomgr->aiop_table) + 0; + nfds_t nfds = n_aiops + 0; struct pollfd *poll_table = iomgr->aiop_poll_table; #endif /* Decide if we are going to wait if no I/O is ready, either: * poll only, wait indefinitely, or wait until a timeout. */ -#if defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1 - struct timespec ts, *timeout_ns; - timeout_ns = timeoutInNanoseconds(iomgr, wait, now, &ts); -#else - int timeout_ms = timeoutInMilliseconds(iomgr, wait, now); + Time timeout = timeoutWaitTime(iomgr, wait, now); + + if (RTS_UNLIKELY(timeout == -1 && n_aiops == 0)) { + /* See Note [Deadlock detection without idle GC] */ + interrupt = notifyIdleGcDeadlock(); + if (interrupt) break; + } + +#if !defined(THREADED_IDLEGC) + /* Without threaded idle GC, poll() does not get interrupted for an + * idle GC. Instead we just limit our wait time to the idle gc delay + * time, and if that timeout is reached then we schedule an idle GC + * (see handleIdleGcTimeout below). + */ + bool any_pending_io = nfds > 0; + int timeout_idlegc_delay; + adjustTimeoutForIdleGc(any_pending_io, &timeout, &timeout_idlegc_delay); #endif /* Check for I/O readiness, possibly waiting. */ #if defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1 + struct timespec ts, *timeout_ns = timeoutAsTimespec(timeout, &ts); int res = ppoll(poll_table, nfds, timeout_ns, NULL); debugTrace(DEBUG_iomanager, - "ppoll(nfds = %lu, timeout.sec = %lld, timeout.nsec = %lld)" - " = %d", - (unsigned long) nfds, - (long long) (timeout_ns == NULL ? -1 : timeout_ns->tv_sec), - (long long) (timeout_ns == NULL ? 0 : timeout_ns->tv_nsec), - res); + "ppoll(nfds = %lu, timeout = %" FMT_Int64 " ns) = %d", + (unsigned long) nfds, timeout, res); #else + int timeout_ms = timeoutAsPollTimeout(timeout); int res = poll(poll_table, nfds, timeout_ms); debugTrace(DEBUG_iomanager, - "poll(nfds = %lu, timeout_ms = %d) = %d", - nfds, timeout_ms, res); + "poll(nfds = %lu, timeout = %d ms) = %d", + (unsigned long) nfds, timeout_ms, res); #endif if (res == 0) { @@ -493,10 +505,9 @@ bool awaitCompletedTimeoutsOrIOPoll(CapIOManager *iomgr) * occurred before any I/O became ready. Either way, the do-while * loop condition will handle it. */ -#if defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1 - ASSERT(timeout_ns != NULL); -#else - ASSERT(timeout_ms != -1); + ASSERT(timeout != -1); +#if !defined(THREADED_IDLEGC) + handleIdleGcTimeout(timeout_idlegc_delay, &interrupt); #endif } else if (res > 0) { @@ -554,7 +565,7 @@ static void reportPollError(int res, nfds_t nfds) } -void interruptIOManagerPoll(CapIOManager *iomgr) +void interruptIOManagerPoll(CapIOManager *iomgr USED_IF_PREEMPTION) { #if defined(HAVE_PREEMPTION) sendFdWakeup(iomgr->interrupt_fd_w); ===================================== rts/posix/Select.c ===================================== @@ -22,6 +22,7 @@ #include "Stats.h" #include "GetTime.h" #include "FdWakeup.h" +#include "Timeout.h" # if defined(HAVE_SYS_SELECT_H) # include <sys/select.h> @@ -73,14 +74,14 @@ void initCapabilityIOManagerSelect(CapIOManager *iomgr) #endif } -void freeCapabilityIOManagerSelect(CapIOManager *iomgr) +void freeCapabilityIOManagerSelect(CapIOManager *iomgr USED_IF_PREEMPTION) { #if defined(HAVE_PREEMPTION) closeFdWakeup(iomgr->interrupt_fd_r, iomgr->interrupt_fd_w); #endif } -void interruptIOManagerSelect(CapIOManager *iomgr) +void interruptIOManagerSelect(CapIOManager *iomgr USED_IF_PREEMPTION) { #if defined(HAVE_PREEMPTION) sendFdWakeup(iomgr->interrupt_fd_w); @@ -345,47 +346,38 @@ awaitCompletedTimeoutsOrIOSelect(CapIOManager *iomgr, bool wait) } } + Time timeout; if (!wait) { // just poll - tv.tv_sec = 0; - tv.tv_usec = 0; - ptv = &tv; + timeout = 0; } else if (iomgr->sleeping_queue != END_TSO_QUEUE) { - /* SUSv2 allows implementations to have an implementation defined - * maximum timeout for select(2). The standard requires - * implementations to silently truncate values exceeding this maximum - * to the maximum. Unfortunately, OSX and the BSD don't comply with - * SUSv2, instead opting to return EINVAL for values exceeding a - * timeout of 1e8. - * - * Select returning an error crashes the runtime in a bad way. To - * play it safe we truncate any timeout to 31 days, as SUSv2 requires - * any implementations maximum timeout to be larger than this. - * - * Truncating the timeout is not an issue, because if nothing - * interesting happens when the timeout expires, we'll see that the - * thread still wants to be blocked longer and simply block on a new - * iteration of select(2). - */ - const time_t max_seconds = 2678400; // 31 * 24 * 60 * 60 - - Time min = LowResTimeToTime( - iomgr->sleeping_queue->block_info.target - now - ); - tv.tv_sec = TimeToSeconds(min); - if (tv.tv_sec < max_seconds) { - tv.tv_usec = TimeToUS(min) % 1000000; - } else { - tv.tv_sec = max_seconds; - tv.tv_usec = 0; - } - ptv = &tv; + timeout = + LowResTimeToTime(iomgr->sleeping_queue->block_info.target - now); } else { - ptv = NULL; + timeout = -1; } + if (RTS_UNLIKELY(timeout == -1 && + iomgr->blocked_queue_hd == END_TSO_QUEUE)) { + /* See Note [Deadlock detection without idle GC] */ + interrupt = notifyIdleGcDeadlock(); + if (interrupt) break; + } + +#if !defined(THREADED_IDLEGC) + /* Without threaded idle GC, select() does not get interrupted for an + * idle GC. Instead we just limit our wait time to the idle gc delay + * time, and if that timeout is reached then we schedule an idle GC + * (see handleIdleGcTimeout below). + */ + bool any_pending_io = maxfd > 0; + int timeout_idlegc_delay; + adjustTimeoutForIdleGc(any_pending_io, &timeout, &timeout_idlegc_delay); +#endif + /* Check for any interesting events */ + ptv = timeoutAsTimeval(timeout, &tv); while ((numFound = select(maxfd+1, &rfd, &wfd, NULL, ptv)) < 0) { if (errno != EINTR) { if ( errno == EBADF ) { @@ -422,6 +414,10 @@ awaitCompletedTimeoutsOrIOSelect(CapIOManager *iomgr, bool wait) } } +#if !defined(THREADED_IDLEGC) + if (numFound == 0) handleIdleGcTimeout(timeout_idlegc_delay, &interrupt); +#endif + #if defined(HAVE_PREEMPTION) /* If the interrupt_fd_r is ready, collect it */ if (FD_ISSET(iomgr->interrupt_fd_r, &rfd)) { ===================================== rts/posix/SelectBis.c ===================================== @@ -361,6 +361,10 @@ void pollCompletedTimeoutsOrIOSelectBis(CapIOManager *iomgr) /* Poll for I/O readiness, without waiting. */ struct timeval tv = (struct timeval) { .tv_sec = 0, .tv_usec = 0 }; int res = select(maxfd+1, iomgr->rfds, iomgr->wfds, NULL, &tv); + debugTrace(DEBUG_iomanager, + "select(nfds = %lu, timeout = 0) = %d", + (unsigned long) maxfd+1, res); + if (res == 0) { /* There is no I/O ready. We'll return to the scheduler. */ @@ -422,19 +426,44 @@ bool awaitCompletedTimeoutsOrIOSelectBis(CapIOManager *iomgr) /* Decide if we are going to wait if no I/O is ready, either: * poll only, wait indefinitely, or wait until a timeout. */ - struct timeval tv, *timeout_us; - timeout_us = timeoutInMicroseconds(iomgr, wait, now, &tv); + Time timeout = timeoutWaitTime(iomgr, wait, now); + + if (RTS_UNLIKELY(timeout == -1 && + isEmptyClosureTable(&iomgr->aiop_table))) { + /* See Note [Deadlock detection without idle GC] */ + interrupt = notifyIdleGcDeadlock(); + if (interrupt) break; + } + +#if !defined(THREADED_IDLEGC) + /* Without threaded idle GC, select() does not get interrupted for an + * idle GC. Instead we just limit our wait time to the idle gc delay + * time, and if that timeout is reached then we schedule an idle GC + * (see handleIdleGcTimeout below). + */ + bool any_pending_io = maxfd >= 0; + int timeout_idlegc_delay; + adjustTimeoutForIdleGc(any_pending_io, &timeout, &timeout_idlegc_delay); +#endif /* Check for I/O readiness, possibly waiting. */ + struct timeval tv, *timeout_us = timeoutAsTimeval(timeout, &tv); int res = select(maxfd+1, iomgr->rfds, iomgr->wfds, NULL, timeout_us); + debugTrace(DEBUG_iomanager, + "select(nfds = %d, timeout = %" FMT_Int64 " us) = %d", + maxfd+1, TimeToUS(timeout), res); + if (res == 0) { /* Success but there is no I/O ready. This can happen either if we * were not blocking or were in a timed wait and the timeout * occurred before any I/O became ready. Either way, the do-while * loop condition will handle it. */ - ASSERT(timeout_us != NULL); + ASSERT(timeout != -1); +#if !defined(THREADED_IDLEGC) + handleIdleGcTimeout(timeout_idlegc_delay, &interrupt); +#endif } else if (res > 0) { int ncompletions = res; @@ -546,7 +575,7 @@ static void processBadFds(CapIOManager *iomgr) } -void interruptIOManagerSelectBis(CapIOManager *iomgr) +void interruptIOManagerSelectBis(CapIOManager *iomgr USED_IF_PREEMPTION) { #if defined(HAVE_PREEMPTION) sendFdWakeup(iomgr->interrupt_fd_w); ===================================== rts/posix/Timeout.c ===================================== @@ -135,11 +135,11 @@ static void notifyTimeoutCompletion(CapIOManager *iomgr, StgTimeout *timeout) } -/* poll() expect a timeout in milliseconds, with special - * values of -1 for indefinite wait, and 0 for no waiting. +/* Returns the duration until the next timeout, with special values 0 for + * no timeout and -1 for infinite timeout. Use one of the timeoutAs* functions + * to convert into the form expected by platform APIs. */ -#if !(defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1) -int timeoutInMilliseconds(CapIOManager *iomgr, bool wait, Time now) +Time timeoutWaitTime(CapIOManager *iomgr, bool wait, Time now) { if (!wait) { /* Don't wait, just poll. */ @@ -152,7 +152,22 @@ int timeoutInMilliseconds(CapIOManager *iomgr, bool wait, Time now) /* Any expired timeouts should have been cleared, so we must be waiting * for a timeout in the future. */ ASSERT(waittime > 0); + return waittime; + } else { + /* No timeouts, wait forever */ + return -1; + } +} + + +/* Convert the result of timeoutWaitTime into the timeout representation + * used by poll(). This representation uses millisecond precision with special + * values 0 and -1 for no wait and indefinite wait. + */ +int timeoutAsPollTimeout(Time waittime) +{ + if (waittime > 0) { /* SUSv2 allows implementations to have an implementation defined * maximum timeout for poll(2). It does not specify any limits on * this maximum however. It is safe to pick a low limit, because if @@ -170,38 +185,25 @@ int timeoutInMilliseconds(CapIOManager *iomgr, bool wait, Time now) return (waittime_ms < max_timeout_ms) ? waittime_ms : max_timeout_ms; } else { - /* No timeouts, wait forever */ - return -1; + /* We must be in the 0 or -1 special cases */ + ASSERT(waittime == 0 || waittime == -1); + return (int) waittime; } } -#endif -/* ppoll() expect a timeout in nanoseconds, using - * struct timespec * with special values of NULL for indefinite wait, - * and 0 for no waiting. +/* Convert the result of timeoutWaitTime into a 'struct timespec *' which is + * the timeout representation used by many modern APIs: ppoll(), pselect(), + * epoll_wait2(), kevent() and io_uring_enter2(). This representation uses + * nanosecond precision with NULL for indefinite wait, and 0 for no waiting. */ -#if (defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1) -struct timespec *timeoutInNanoseconds(CapIOManager *iomgr, bool wait, - Time now, struct timespec *tv) +struct timespec *timeoutAsTimespec(Time waittime, struct timespec *tv) { - if (!wait) { - /* Don't wait, just poll. */ - *tv = (struct timespec) { .tv_sec = 0, .tv_nsec = 0 }; - return tv; - - } else if (!isEmptyTimeoutQueue(iomgr->timeout_queue)) { - Time waketime = findMinWaketimeTimeoutQueue(iomgr->timeout_queue); - Time waittime = waketime - now; - - /* Any expired timeouts should have been cleared, so we must be waiting - * for a timeout in the future. */ - ASSERT(waittime > 0); - - /* See comments above in timeoutInMilliseconds about the max timeout */ + if (waittime > 0) { + /* See comments above about the max timeout */ const int64_t max_timeout_ms = INT_MAX / 1000; + const Time max_timeout_ns = MSToTime(max_timeout_ms); - const Time max_timeout_ns = MSToTime(max_timeout_ms); if (waittime < max_timeout_ns) { /* Time in nanoseconds to separate seconds and nanoseconds */ *tv = (struct timespec) { @@ -217,25 +219,26 @@ struct timespec *timeoutInNanoseconds(CapIOManager *iomgr, bool wait, return tv; } else { - /* No timeouts, wait forever */ - return NULL; + /* We must be in the 0 or -1 special cases */ + ASSERT(waittime == 0 || waittime == -1); + if (waittime == 0) { + /* Don't wait, just poll. */ + *tv = (struct timespec) { .tv_sec = 0, .tv_nsec = 0 }; + return tv; + } else { + /* No timeouts, wait forever */ + return NULL; + } } } -#endif -/* select() expect a timeout in microseconds, using struct timeval * with - * special values of NULL for indefinite wait, and 0 for no waiting. +/* Convert the result of timeoutWaitTime into a 'struct timeval *' which is + * the timeout representation used by select(). This representation uses + * microsecond precision with NULL for indefinite wait, and 0 for no waiting. */ -#if defined(IOMGR_ENABLED_SELECTBIS) -struct timeval *timeoutInMicroseconds(CapIOManager *iomgr, bool wait, - Time now, struct timeval *tv) +struct timeval *timeoutAsTimeval(Time waittime, struct timeval *tv) { - if (!wait) { - /* Don't wait, just poll. */ - *tv = (struct timeval) { .tv_sec = 0, .tv_usec = 0 }; - return tv; - - } else if (!isEmptyTimeoutQueue(iomgr->timeout_queue)) { + if (waittime > 0) { /* SUSv2 allows implementations to have an implementation defined * maximum timeout for select(2). The standard requires * implementations to silently truncate values exceeding this maximum @@ -254,13 +257,6 @@ struct timeval *timeoutInMicroseconds(CapIOManager *iomgr, bool wait, */ const time_t max_seconds = 2678400; // 31 * 24 * 60 * 60 - Time waketime = findMinWaketimeTimeoutQueue(iomgr->timeout_queue); - Time waittime = waketime - now; - - /* Any expired timeouts should have been cleared, so we must be waiting - * for a timeout in the future. */ - ASSERT(waittime > 0); - tv->tv_sec = TimeToSeconds(waittime); if (tv->tv_sec < max_seconds) { tv->tv_usec = TimeToUS(waittime) % 1000000; @@ -271,7 +267,60 @@ struct timeval *timeoutInMicroseconds(CapIOManager *iomgr, bool wait, return tv; } else { - return NULL; + /* We must be in the 0 or -1 special cases */ + ASSERT(waittime == 0 || waittime == -1); + + if (waittime == 0) { + /* Don't wait, just poll. */ + *tv = (struct timeval) { .tv_sec = 0, .tv_usec = 0 }; + return tv; + } else { + /* No timeouts, wait forever */ + return NULL; + } + } +} + + +#if !defined(THREADED_IDLEGC) +/* Utilities for handling the non-threaded idle GC variation. + * + * See Note [Idle GC without preemption] + * + * Before calling poll()/select() etc, adjust the timeout to account for the + * idle GC delay time. + * + * If the timeout occurs, call handleIdleGcTimeout, which will schedule an idle + * GC if the timeout was reached. + * + * The timeout_is_idlegc_delay must be passed from adjustTimeoutForIdleGc to + * handleIdleGcTimeout. + */ +void adjustTimeoutForIdleGc(bool any_pending_io, + Time *timeout, /* in/out */ + bool *timeout_is_idlegc_delay /* out */) +{ + Time idlegc_delay = getNextIdleGcDelayTime(); + /* Note that idlegc_delay can be -1 for indefinite wait, if we've already + * done an idle GC and there's been no activity since. + */ + + if (RtsFlags.GcFlags.doIdleGC && + (*timeout == -1 || (idlegc_delay > 0 && idlegc_delay < *timeout))) { + /* The idle GC delay will be the next timeout. */ + *timeout = idlegc_delay; + *timeout_is_idlegc_delay = true; + + } else { + *timeout_is_idlegc_delay = false; + } +} + +void handleIdleGcTimeout(int timeout_is_idlegc_delay, bool *interrupt) +{ + if (timeout_is_idlegc_delay) { + notifyIdleGcIdle(); + *interrupt = true; } } #endif ===================================== rts/posix/Timeout.h ===================================== @@ -10,6 +10,8 @@ #pragma once +#include "IdleGC.h" // To get definition of THREADED_IDLEGC + #include "BeginPrivate.h" bool syncDelayTimeout(CapIOManager *iomgr, StgTSO *tso, HsInt us_delay); @@ -26,34 +28,49 @@ void syncDelayCancelTimeout(CapIOManager *iomgr, StgTSO *tso); */ void processTimeoutCompletions(CapIOManager *iomgr, Time now); -/* Utility to compute the timeout wait time (in milliseconds) between now and - * the next timer expiry (if any), or no waiting (if !wait). +#if defined(IOMGR_ENABLED_POLL) \ + || defined(IOMGR_ENABLED_SELECTBIS) +/* Compute the timeout wait time between now and the next timer expiry (if any) + * using the given IOManager's timeout_queue. + * + * Use one of the timeoutAs* functions to convert into the form expected by + * particular platform APIs. * - * This is intended to be used with poll() which expect a - * timeout in milliseconds, with special values of -1 for indefinite wait, - * and 0 for no waiting. + * It returns the wait time duration as a Time (i.e. nanoseconds), but with + * special values 0 for no timeout and -1 for indefinite timeout. */ -#if !(defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1) -int timeoutInMilliseconds(CapIOManager *iomgr, bool wait, Time now); +Time timeoutWaitTime(CapIOManager *iomgr, bool wait, Time now); #endif -/* As above, but a timeout in nanoseconds. This is intended to be used with - * ppoll() which expect struct timespec *, with special - * values of NULL for indefinite wait, and 0 for no waiting. +/* Convert the result of timeoutWaitTime into the timeout representation + * used by poll(). This representation uses millisecond precision with special + * values 0 and -1 for no wait and indefinite wait. */ -#if (defined(HAVE_DECL_PPOLL) && HAVE_DECL_PPOLL == 1) -struct timespec *timeoutInNanoseconds(CapIOManager *iomgr, bool wait, - Time now, struct timespec *tv); -#endif +int timeoutAsPollTimeout(Time waittime); + +/* Convert the result of timeoutWaitTime into a 'struct timeval *' which is + * the timeout representation used by select(). This representation uses + * microsecond precision with NULL for indefinite wait, and 0 for no waiting. + */ +struct timeval *timeoutAsTimeval(Time waittime, struct timeval *tv); + +/* Convert the result of timeoutWaitTime into a 'struct timespec *' which is + * the timeout representation used by many modern APIs: ppoll(), pselect(), + * epoll_wait2(), kevent() and io_uring_enter2(). This representation uses + * nanosecond precision with NULL for indefinite wait, and 0 for no waiting. + */ +struct timespec *timeoutAsTimespec(Time waittime, struct timespec *tv); -/* As above, but a timeout in microseconds. This is intended to be used with - * select() which expect struct timespec *, with special values of NULL for - * indefinite wait, and 0 for no waiting. +#if !defined(THREADED_IDLEGC) +/* Utilities for handling the non-threaded idle GC variation. + * + * See Note [Idle GC without preemption] */ -#if defined(IOMGR_ENABLED_SELECTBIS) -struct timeval *timeoutInMicroseconds(CapIOManager *iomgr, bool wait, - Time now, struct timeval *tv); +void adjustTimeoutForIdleGc(bool any_pending_io, + Time *timeout, /* in/out */ + bool *timeout_is_idlegc_delay /* out */); +void handleIdleGcTimeout(int idlegc_status, bool *interrupt); #endif #include "EndPrivate.h" ===================================== rts/win32/AsyncMIO.c ===================================== @@ -231,6 +231,12 @@ awaitRequests(bool wait) { CapIOManager *iomgr = MainCapability.iomgr; + if (RTS_UNLIKELY(issued_reqs == 0)) { + /* See Note [Deadlock detection without idle GC] + * Note that the issued_reqs covers both I/O and timers. */ + if (notifyIdleGcDeadlock()) return false; + } + start: #if 0 fprintf(stderr, "awaitRequests(): %d %d %d\n", ===================================== testsuite/tests/interface-stability/ghc-experimental-exports.stdout ===================================== @@ -13642,6 +13642,7 @@ module System.Mem.Experimental where disableAllocationLimitFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () enableAllocationLimitFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () getAllocationCounterFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO GHC.Internal.Int.Int64 + performDeadlockDetection :: GHC.Internal.Types.IO () setAllocationCounterFor :: GHC.Internal.Int.Int64 -> GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () setGlobalAllocationLimitHandler :: AllocationLimitKillBehaviour -> GHC.Internal.Maybe.Maybe (GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO ()) -> GHC.Internal.Types.IO () ===================================== testsuite/tests/interface-stability/ghc-experimental-exports.stdout-mingw32 ===================================== @@ -13645,6 +13645,7 @@ module System.Mem.Experimental where disableAllocationLimitFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () enableAllocationLimitFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () getAllocationCounterFor :: GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO GHC.Internal.Int.Int64 + performDeadlockDetection :: GHC.Internal.Types.IO () setAllocationCounterFor :: GHC.Internal.Int.Int64 -> GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO () setGlobalAllocationLimitHandler :: AllocationLimitKillBehaviour -> GHC.Internal.Maybe.Maybe (GHC.Internal.Conc.Sync.ThreadId -> GHC.Internal.Types.IO ()) -> GHC.Internal.Types.IO () ===================================== testsuite/tests/rts/Makefile ===================================== @@ -157,3 +157,11 @@ HSC2HS_OPTS = --cc="$(TEST_CC)" $(addprefix --cflag=,$(TEST_CC_OPTS)) --ld=$(TES IOManager.hs: IOManager.hsc '$(HSC2HS)' $(HSC2HS_OPTS) $< + +.PHONY: T26408c +T26408c: + "$(TEST_HC)" $(TEST_HC_OPTS) -rtsopts T26408c.hs; \ + ./T26408c +RTS -I0 -T & \ + sleep 1; \ + kill -s USR1 $$!; \ + wait $$! ===================================== testsuite/tests/rts/T26408a.hs ===================================== @@ -0,0 +1,54 @@ +import Control.Concurrent +import Control.Concurrent.STM +import Control.Exception +import Control.Monad + +-- | Test to make sure that we can detect a /partial deadlock/ that is /not/ +-- also a /system deadlock/: that is we can detect a set of deadlocked threads +-- even when there are other unrelated threads that are waiting on I\/O or +-- timeouts. +-- +-- Historically this did not work in the non-threaded RTS which would only do +-- deadlock detection if there was a system deadlock: no runnable threads /and/ +-- no pending I\/O or timers. +-- +-- See Note [Deadlock detection] +-- +main :: IO () +main = do + + -- Set up two threads that are deadlocked on each other + aDone <- newTVarIO False + bDone <- newTVarIO False + let blockingThread theirDone ourDone = + atomically $ do + done <- readTVar theirDone + guard done + writeTVar ourDone True + _ <- forkIO (blockingThread bDone aDone) + _ <- forkIO (blockingThread aDone bDone) + + -- Set up another thread that is blocked on a long timeout. + -- + -- We use a timeout rather than I/O as it's more portable, whereas I/O waits + -- are different between posix and windows I/O managers. + -- + -- One gotcha is that when the timeout completes then the deadlock will be + -- detected again (since the bug is about I/O or timeouts masking deadlock + -- detection). So for a reliable test the timeout used here must be longer + -- than the test framework's own timeout. So we use maxBound, and we adjust + -- the test framework's timeout to be short (see run_timeout_multiplier). + _ <- forkIO (threadDelay maxBound) + + -- Wait on the two deadlocked threads to terminate. This is now a partial + -- deadlock but not a system deadlock (the main thread and the first two + -- threads are deadlocked, but the one waiting on the timeout is ok). + -- + -- We now expect that the threads that are deadlocked are detected as such + -- and an exception is thrown to some or all of them. + -- + -- Note that if this fails, the test itself will effectively deadlock and + -- will rely on the test framework's timeout. + atomically $ do + status <- mapM readTVar [aDone, bDone] + guard (or status) ===================================== testsuite/tests/rts/T26408a.stderr ===================================== @@ -0,0 +1,3 @@ +T26408a: Uncaught exception ghc-internal:GHC.Internal.IO.Exception.BlockedIndefinitelyOnSTM: + +thread blocked indefinitely in an STM transaction ===================================== testsuite/tests/rts/T26408b.hs ===================================== @@ -0,0 +1,43 @@ +import Control.Concurrent +import Control.Concurrent.STM +import Control.Exception +import Control.Monad + +import System.Posix.Signals + +-- | Test to make sure that we can detect a /system deadlock/ promptly which +-- means without relying on idle GC. To check this we have to turn off idle GC, +-- (+RTS -I0) which is what normally triggers deadlock detection. +-- +-- This is only expected to work in the non-threaded RTS. In principle this +-- test could also work with the threaded RTS when using only a single +-- capability, if the I\/O managers can support it. Currently that is not the +-- case. +-- +-- See Note [Deadlock detection] +-- +main :: IO () +main = do + + -- Set up two threads that are deadlocked on each other + aDone <- newTVarIO False + bDone <- newTVarIO False + let blockingThread theirDone ourDone = + atomically $ do + done <- readTVar theirDone + guard done + writeTVar ourDone True + _ <- forkIO (blockingThread bDone aDone) + _ <- forkIO (blockingThread aDone bDone) + + -- Wait on the two deadlocked threads to terminate. This is now a system + -- deadlock, involving all three threads (the main thread and the other two). + -- + -- We now expect that the threads that are deadlocked are detected as such + -- and an exception is thrown to some or all of them. + -- + -- Note that if this fails, the test itself will effectively deadlock and + -- will rely on the test framework's timeout. + atomically $ do + status <- mapM readTVar [aDone, bDone] + guard (or status) ===================================== testsuite/tests/rts/T26408b.stderr ===================================== @@ -0,0 +1,3 @@ +T26408b: Uncaught exception ghc-internal:GHC.Internal.IO.Exception.BlockedIndefinitelyOnSTM: + +thread blocked indefinitely in an STM transaction ===================================== testsuite/tests/rts/T26408c.hs ===================================== @@ -0,0 +1,61 @@ +import Control.Concurrent +import Control.Concurrent.STM +import Control.Exception +import Control.Monad + +import System.Posix.Signals +import GHC.Stats.Experimental + +-- | Test to make sure that we do not falsely detect a deadlock when there is +-- nothing to do except wait on signals. This is to make sure that our prompt +-- system deadlock detection is not too eager. +-- +-- We arrange a partial deadlock that can be broken if a signal arrives and +-- the signal handler can unblock things. +-- +-- This should /not/ result in any deadlock being detected, and no other odd +-- behaviour, like getting caught in a loop and doing too many idle GCs. So we +-- count and report the number of major GCs. +-- +main :: IO () +main = do + + -- Set up two threads that are deadlocked on each other + aDone <- newTVarIO False + bDone <- newTVarIO False + let blockingThread theirDone ourDone = + atomically $ do + done <- readTVar theirDone + guard done + writeTVar ourDone True + + installHandler userDefinedSignal1 + (Catch $ do + atomically $ writeTVar aDone True + >> writeTVar bDone True + putStrLn "caught SIGUSR1") + Nothing + + _ <- forkIO (blockingThread bDone aDone) + _ <- forkIO (blockingThread aDone bDone) + yield + + -- Wait on the deadlocked threads to terminate. We now expect that the threads + -- that are deadlocked are detected as such and an exception is raised. + -- Note that if this fails, the test itself will effectively deadlock and + -- will rely on the test framework's timeout. + putStrLn "waiting on deadlocked threads..." + atomically $ do + status <- mapM readTVar [aDone, bDone] + guard (or status) + + -- We expect exactly 1 major GC: the one triggered for deadlock detection + -- where we find no deadlock. We should then sleep without doing more GC. + -- An easy mistake would be looping: detecting probable deadlock, do idle GC. + -- See notifyIdleGcDeadlock(). + stats <- getRTSStats + putStrLn ("terminated normally, major GCs = " ++ show (major_gcs stats)) + -- This test _could_ be sensitive to changes in default heap sizes etc. If + -- this number ends up as 2 for example, then adjust the RTS opts (in the + -- makefile) so that the heap is big enough that normally no major GC would + -- be needed. ===================================== testsuite/tests/rts/T26408c.stdout ===================================== @@ -0,0 +1,5 @@ +[1 of 2] Compiling Main ( T26408c.hs, T26408c.o ) +[2 of 2] Linking T26408c +waiting on deadlocked threads... +caught SIGUSR1 +terminated normally, major GCs = 1 ===================================== testsuite/tests/rts/all.T ===================================== @@ -682,6 +682,20 @@ test('T22859', omit_ways(llvm_ways + ['nonmoving_thr', 'nonmoving_thr_sanity'])], compile_and_run, ['-with-rtsopts -A8K']) +# Deadlock detection testsL +# A: check we can detect a partial deadlock that is not a system deadlock +test('T26408a', [exit_code(1), run_timeout_multiplier(0.1)], compile_and_run, ['']) +# B: check we can detect system deadlock with idle GC turned off (+RTS -I0) +test('T26408b', [omit_ways(threaded_ways), extra_run_opts('+RTS -I0 -RTS'), + exit_code(1), run_timeout_multiplier(0.1)], + compile_and_run, ['-rtsopts']) +# C: check we do not falsely detect deadlock when blocked only on signals +test('T26408c', [run_timeout_multiplier(0.1)], makefile_test, ['T26408c']) +# TODO: change omit_ways(threaded_ways) above +# to all_io_managers_except['mio', 'winio'] +# and use +RTS -N1 with threaded ways. + + # These tests need access to the internal RTS headers. # TODO: there is probably some cleaner way to do this, and it should probably # be guarded for in-tree tests, since it cannot work against an arbitrary View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/c20f42b2694c5e470e3286be0ca9112... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/c20f42b2694c5e470e3286be0ca9112... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help