[llvm][Support] Add ExponentialBackoff helper (#81206)

This provides a simple way to implement exponential backoff using a do
while loop.

Usage example (also see the change to LockFileManager.cpp):
```
ExponentialBackoff Backoff(10s);
do {
  if (tryToDoSomething())
    return ItWorked;
} while (Backoff.waitForNextAttempt());
return Timeout;
```

Abstracting this out of `LockFileManager` as the module build daemon
will need it.

1 files changed, 7 insertions, 31 deletions

diff --git a/llvm/lib/Support/LockFileManager.cpp b/llvm/lib/Support/LockFileManager.cpp
index a2b0fe8c..34c7a16 100644
--- a/llvm/lib/Support/LockFileManager.cpp
+++ b/llvm/lib/Support/LockFileManager.cpp
@@ -11,6 +11,7 @@
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/ExponentialBackoff.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Process.h"
@@ -20,7 +21,6 @@
 #include <chrono>
 #include <ctime>
 #include <memory>
-#include <random>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <system_error>
@@ -295,29 +295,15 @@ LockFileManager::waitForUnlock(const unsigned MaxSeconds) {
     return Res_Success;
 
   // Since we don't yet have an event-based method to wait for the lock file,
-  // implement randomized exponential backoff, similar to Ethernet collision
+  // use randomized exponential backoff, similar to Ethernet collision
   // algorithm. This improves performance on machines with high core counts
   // when the file lock is heavily contended by multiple clang processes
-  const unsigned long MinWaitDurationMS = 10;
-  const unsigned long MaxWaitMultiplier = 50; // 500ms max wait
-  unsigned long WaitMultiplier = 1;
-  unsigned long ElapsedTimeSeconds = 0;
+  using namespace std::chrono_literals;
+  ExponentialBackoff Backoff(std::chrono::seconds(MaxSeconds), 10ms, 500ms);
 
-  std::random_device Device;
-  std::default_random_engine Engine(Device());
-
-  auto StartTime = std::chrono::steady_clock::now();
-
-  do {
+  // Wait first as this is only called when the lock is known to be held.
+  while (Backoff.waitForNextAttempt()) {
     // FIXME: implement event-based waiting
-
-    // Sleep for the designated interval, to allow the owning process time to
-    // finish up and remove the lock file.
-    std::uniform_int_distribution<unsigned long> Distribution(1,
-                                                              WaitMultiplier);
-    unsigned long WaitDurationMS = MinWaitDurationMS * Distribution(Engine);
-    std::this_thread::sleep_for(std::chrono::milliseconds(WaitDurationMS));
-
     if (sys::fs::access(LockFileName.c_str(), sys::fs::AccessMode::Exist) ==
         errc::no_such_file_or_directory) {
       // If the original file wasn't created, somone thought the lock was dead.
@@ -329,17 +315,7 @@ LockFileManager::waitForUnlock(const unsigned MaxSeconds) {
     // If the process owning the lock died without cleaning up, just bail out.
     if (!processStillExecuting((*Owner).first, (*Owner).second))
       return Res_OwnerDied;
-
-    WaitMultiplier *= 2;
-    if (WaitMultiplier > MaxWaitMultiplier) {
-      WaitMultiplier = MaxWaitMultiplier;
-    }
-
-    ElapsedTimeSeconds = std::chrono::duration_cast<std::chrono::seconds>(
-                             std::chrono::steady_clock::now() - StartTime)
-                             .count();
-
-  } while (ElapsedTimeSeconds < MaxSeconds);
+  }
 
   // Give up.
   return Res_Timeout;