SERVER-21533 Lock manager should not starve requests

This change makes the lock manager granting code skip granting compatible
requests if the first entry on the queue is a conflict.

2 files changed, 59 insertions, 8 deletions

diff --git a/src/mongo/db/concurrency/lock_manager.cpp b/src/mongo/db/concurrency/lock_manager.cpp
index d8758752259..b2b04e788ef 100644
--- a/src/mongo/db/concurrency/lock_manager.cpp
+++ b/src/mongo/db/concurrency/lock_manager.cpp
@@ -736,15 +736,20 @@ void LockManager::_onLockModeChanged(LockHead* lock, bool checkConflictQueue) {
     }
 
     // Grant any conflicting requests, which might now be unblocked. Note that the loop below
-    // slightly violates fairness in that it will grant *all* compatible requests on the line
-    // even though there might be conflicting ones interspersed between them. For example,
-    // consider an X lock was just freed and the conflict queue looked like this:
+    // slightly violates fairness in that it will grant *all* compatible requests on the line even
+    // though there might be conflicting ones interspersed between them. For example, assume that an
+    // X lock was just freed and the conflict queue looks like this:
     //
     //      IS -> IS -> X -> X -> S -> IS
     //
-    // In strict FIFO, we should grant the first two IS modes and then stop when we reach the
-    // first X mode (the third request on the queue). However, the loop below would actually
-    // grant all IS + S modes and once they all drain it will grant X.
+    // In strict FIFO, we should grant the first two IS modes and then stop when we reach the first
+    // X mode (the third request on the queue). However, the loop below would actually grant all IS
+    // + S modes and once they all drain it will grant X. The reason for this behaviour is
+    // increasing system throughput in the scenario where mutually compatible requests are
+    // interspersed with conflicting ones. For example, this would be a worst-case scenario for
+    // strict FIFO, because it would make the execution sequential:
+    //
+    //      S -> X -> S -> X -> S -> X
 
     LockRequest* iterNext = NULL;
 
@@ -757,6 +762,13 @@ void LockManager::_onLockModeChanged(LockHead* lock, bool checkConflictQueue) {
         iterNext = iter->next;
 
         if (conflicts(iter->mode, lock->grantedModes)) {
+            // If iter doesn't have a previous pointer, this means that it is at the front of the
+            // queue. If we continue scanning the queue beyond this point, we will starve it by
+            // granting more and more requests.
+            if (!iter->prev) {
+                break;
+            }
+
             continue;
         }
 
@@ -783,8 +795,8 @@ void LockManager::_onLockModeChanged(LockHead* lock, bool checkConflictQueue) {
 
     // This is a convenient place to check that the state of the two request queues is in sync
     // with the bitmask on the modes.
-    invariant((lock->grantedModes == 0) ^ (lock->grantedList._front != NULL));
-    invariant((lock->conflictModes == 0) ^ (lock->conflictList._front != NULL));
+    dassert((lock->grantedModes == 0) ^ (lock->grantedList._front != NULL));
+    dassert((lock->conflictModes == 0) ^ (lock->conflictList._front != NULL));
 }
 
 LockManager::LockBucket* LockManager::_getBucket(ResourceId resId) const {
diff --git a/src/mongo/db/concurrency/lock_manager_test.cpp b/src/mongo/db/concurrency/lock_manager_test.cpp
index ce722b6f572..aa2edef04b4 100644
--- a/src/mongo/db/concurrency/lock_manager_test.cpp
+++ b/src/mongo/db/concurrency/lock_manager_test.cpp
@@ -816,4 +816,43 @@ TEST(LockManager, CompatibleFirstCancelWaiting) {
     ASSERT(lockMgr.unlock(&requestX));
 }
 
+TEST(LockManager, Fairness) {
+    LockManager lockMgr;
+    const ResourceId resId(RESOURCE_GLOBAL, 0);
+
+    // Start with some 'regular' intent locks
+    MMAPV1LockerImpl lockerIS;
+    LockRequestCombo requestIS(&lockerIS);
+    ASSERT(LOCK_OK == lockMgr.lock(resId, &requestIS, MODE_IS));
+
+    MMAPV1LockerImpl lockerIX;
+    LockRequestCombo requestIX(&lockerIX);
+    ASSERT(LOCK_OK == lockMgr.lock(resId, &requestIX, MODE_IX));
+
+    // Now a conflicting lock comes
+    MMAPV1LockerImpl lockerX;
+    LockRequestCombo requestX(&lockerX);
+    ASSERT(LOCK_WAITING == lockMgr.lock(resId, &requestX, MODE_X));
+
+    // Now, whoever comes next should be blocked
+    MMAPV1LockerImpl lockerIX1;
+    LockRequestCombo requestIX1(&lockerIX1);
+    ASSERT(LOCK_WAITING == lockMgr.lock(resId, &requestIX1, MODE_IX));
+
+    // Freeing the first two locks should grant the X lock
+    ASSERT(lockMgr.unlock(&requestIS));
+    ASSERT(lockMgr.unlock(&requestIX));
+    ASSERT_EQ(LOCK_OK, requestX.lastResult);
+    ASSERT_EQ(1, requestX.numNotifies);
+    ASSERT_EQ(LOCK_INVALID, requestIX1.lastResult);
+    ASSERT_EQ(0, requestIX1.numNotifies);
+
+    ASSERT(lockMgr.unlock(&requestX));
+    ASSERT_EQ(LOCK_OK, requestIX1.lastResult);
+    ASSERT_EQ(1, requestIX1.numNotifies);
+
+    // Unlock all locks so we don't assert for leaked locks
+    ASSERT(lockMgr.unlock(&requestIX1));
+}
+
 }  // namespace mongo