scheduleYield: avoid doing a GC again if we just did one

If we are interrupted to do a GC, then we do not immediately do another
one.  This avoids a starvation situation where one Capability keeps
forcing a GC and the other Capabilities make no progress at all.

3 files changed, 28 insertions, 14 deletions

diff --git a/rts/Capability.c b/rts/Capability.c
index b3b7629e54..8d211b5a61 100644
--- a/rts/Capability.c
+++ b/rts/Capability.c
@@ -679,18 +679,21 @@ waitForReturnCapability (Capability **pCap, Task *task)
  * yieldCapability
  * ------------------------------------------------------------------------- */
 
-void
-yieldCapability (Capability** pCap, Task *task)
+/* See Note [GC livelock] in Schedule.c for why we have gcAllowed
+   and return the rtsBool */
+rtsBool /* Did we GC? */
+yieldCapability (Capability** pCap, Task *task, rtsBool gcAllowed)
 {
     Capability *cap = *pCap;
 
-    if (pending_sync == SYNC_GC_PAR) {
+    if ((pending_sync == SYNC_GC_PAR) && gcAllowed) {
         traceEventGcStart(cap);
         gcWorkerThread(cap);
         traceEventGcEnd(cap);
         traceSparkCounters(cap);
         // See Note [migrated bound threads 2]
-        if (task->cap == cap) return;
+        if (task->cap == cap) {
+            return rtsTrue;
     }
 
 	debugTrace(DEBUG_sched, "giving up capability %d", cap->no);
@@ -756,7 +759,7 @@ yieldCapability (Capability** pCap, Task *task)
 
     ASSERT_FULL_CAPABILITY_INVARIANTS(cap,task);
 
-    return;
+    return rtsFalse;
 }
 
 // Note [migrated bound threads]
diff --git a/rts/Capability.h b/rts/Capability.h
index 1a2e7fd8bc..6c417160ad 100644
--- a/rts/Capability.h
+++ b/rts/Capability.h
@@ -257,7 +257,7 @@ EXTERN_INLINE void recordClosureMutated (Capability *cap, StgClosure *p);
 // On return: *pCap is NULL if the capability was released.  The
 // current task should then re-acquire it using waitForCapability().
 //
-void yieldCapability (Capability** pCap, Task *task);
+rtsBool yieldCapability (Capability** pCap, Task *task, rtsBool gcAllowed);
 
 // Acquires a capability for doing some work.
 //
diff --git a/rts/Schedule.c b/rts/Schedule.c
index fe346afe19..48293d0c9f 100644
--- a/rts/Schedule.c
+++ b/rts/Schedule.c
@@ -638,15 +638,24 @@ scheduleFindWork (Capability **pcap)
 
 #if defined(THREADED_RTS)
 STATIC_INLINE rtsBool
-shouldYieldCapability (Capability *cap, Task *task)
+shouldYieldCapability (Capability *cap, Task *task, rtsBool didGcLast)
 {
     // we need to yield this capability to someone else if..
-    //   - another thread is initiating a GC
+    //   - another thread is initiating a GC, and we didn't just do a GC
+    //     (see Note [GC livelock])
     //   - another Task is returning from a foreign call
     //   - the thread at the head of the run queue cannot be run
     //     by this Task (it is bound to another Task, or it is unbound
     //     and this task it bound).
-    return (pending_sync ||
+    //
+    // Note [GC livelock]
+    //
+    // If we are interrupted to do a GC, then we do not immediately do
+    // another one.  This avoids a starvation situation where one
+    // Capability keeps forcing a GC and the other Capabilities make no
+    // progress at all.
+
+    return ((pending_sync && !didGcLast) ||
             cap->returning_tasks_hd != NULL ||
             (!emptyRunQueue(cap) && (task->incall->tso == NULL
                                      ? cap->run_queue_hd->bound != NULL
@@ -667,20 +676,22 @@ static void
 scheduleYield (Capability **pcap, Task *task)
 {
     Capability *cap = *pcap;
+    int didGcLast = rtsFalse;
 
     // if we have work, and we don't need to give up the Capability, continue.
     //
-    if (!shouldYieldCapability(cap,task) && 
+    if (!shouldYieldCapability(cap,task,rtsFalse) && 
         (!emptyRunQueue(cap) ||
          !emptyInbox(cap) ||
-         sched_state >= SCHED_INTERRUPTING))
+         sched_state >= SCHED_INTERRUPTING)) {
         return;
+    }
 
     // otherwise yield (sleep), and keep yielding if necessary.
     do {
-        yieldCapability(&cap,task);
+        didGcLast = yieldCapability(&cap,task, !didGcLast);
     } 
-    while (shouldYieldCapability(cap,task));
+    while (shouldYieldCapability(cap,task,didGcLast));
 
     // note there may still be no threads on the run queue at this
     // point, the caller has to check.
@@ -1374,7 +1385,7 @@ static nat requestSync (Capability **pcap, Task *task, nat sync_type)
             debugTrace(DEBUG_sched, "someone else is trying to sync (%d)...",
                        prev_pending_sync);
             ASSERT(*pcap);
-            yieldCapability(pcap,task);
+            yieldCapability(pcap,task,rtsTrue);
         } while (pending_sync);
         return prev_pending_sync; // NOTE: task->cap might have changed now
     }