Replace the fancy, lockless, and incorrect BoundedMultisetSemaphore and with a boring naive synchronized implementation.

There's a race condition in my design of the lockless data structure. I haven't been able to come up with a lockless algorithm that actually works, and the naive one seems to be fine. In Blaze's usage, performance actually isn't super important so the naive implementation is fine.

Consider three threads and a MultisetSemaphore with 2 max unique values.

T1: acquireAll({a, b})
T2: acquireAll({a, c})
T3: acquireAll({a, d})

For the for-loop before the 'acquire' call, suppose:
-T1 wins the race to acquire 'a' [1] and also wants to acquire 'b' [1]
-T2 loses the race to acquire 'a' [2] and also wants to acquire 'c' [1]
-T3 loses the race to acquire 'a' [2] and also wants to acquire 'd' [1]

So then in [3] we have:
-T1 tries to acquire 2 permits
-T2 tries to acquire 1 permit
-T3 tries to acquire 1 permit

Suppose the execution order in [3] is T2, T3, T1. So that means we then have T1 still at [3] and both T2 and T3 at [4], which is a deadlock.

[1] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L184
[2] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L191
[3] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L199
[4] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L210

--
PiperOrigin-RevId: 148272171
MOS_MIGRATED_REVID=148272171

1 files changed, 3 insertions, 10 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/concurrent/MultisetSemaphoreTest.java b/src/test/java/com/google/devtools/build/lib/concurrent/MultisetSemaphoreTest.java
index 3c87569007..6e75c0d26b 100644
--- a/src/test/java/com/google/devtools/build/lib/concurrent/MultisetSemaphoreTest.java
+++ b/src/test/java/com/google/devtools/build/lib/concurrent/MultisetSemaphoreTest.java
@@ -41,7 +41,6 @@ public class MultisetSemaphoreTest {
   public void testSimple_Serial() throws Exception {
     // When we have a MultisetSemaphore
     MultisetSemaphore<String> multisetSemaphore = MultisetSemaphore.newBuilder()
-        .concurrencyLevel(1)
         // with 3 max num unique values,
         .maxNumUniqueValues(3)
         .build();
@@ -67,9 +66,7 @@ public class MultisetSemaphoreTest {
     Preconditions.checkState(m > n && m % n == 0, "M=%d N=%d", m, n);
     // When we have a MultisetSemaphore
     final MultisetSemaphore<String> multisetSemaphore = MultisetSemaphore.newBuilder()
-        // With a concurrency level of M
-        .concurrencyLevel(m)
-        // And N max num unique values,
+        // with N max num unique values,
         .maxNumUniqueValues(n)
         .build();
 
@@ -150,9 +147,7 @@ public class MultisetSemaphoreTest {
     int n = 100;
     // When we have a MultisetSemaphore
     final MultisetSemaphore<String> multisetSemaphore = MultisetSemaphore.newBuilder()
-        // With a concurrency level of N
-        .concurrencyLevel(n)
-        // And 2 max num unique values,
+        // with 2 max num unique values,
         .maxNumUniqueValues(2)
         .build();
     // And a ExecutorService with N threads,
@@ -216,9 +211,7 @@ public class MultisetSemaphoreTest {
     int numPermutations = permutations.size();
     // And we have a MultisetSemaphore
     final MultisetSemaphore<String> multisetSemaphore = MultisetSemaphore.newBuilder()
-        // With a concurrency level of N!
-        .concurrencyLevel(numPermutations)
-        // And with N max num unique values,
+        // with N max num unique values,
         .maxNumUniqueValues(n)
         .build();
     // And a ExecutorService with N! threads,