Index: llvm/include/llvm/Debuginfod/Debuginfod.h
===================================================================
--- llvm/include/llvm/Debuginfod/Debuginfod.h
+++ llvm/include/llvm/Debuginfod/Debuginfod.h
@@ -28,6 +28,7 @@
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Mutex.h"
 #include "llvm/Support/RWMutex.h"
+#include "llvm/Support/Timer.h"
 
 #include <chrono>
 #include <queue>
@@ -100,16 +101,25 @@
   sys::RWMutex DebugBinariesMutex;
   StringMap<std::string> DebugBinaries;
   Error findBinaries(StringRef Path);
+  Expected<Optional<std::string>> getDebugBinaryPath(BuildIDRef);
+  Expected<Optional<std::string>> getBinaryPath(BuildIDRef);
+  Error updateIfStale();
   DebuginfodLog &Log;
   ThreadPool &Pool;
+  Timer UpdateTimer;
+  sys::Mutex UpdateMutex;
+
+  // Minimum update interval, in seconds, for on-demand updates triggered when a
+  // build-id is not found.
+  double MinInterval;
 
 public:
   DebuginfodCollection(ArrayRef<StringRef> Paths, DebuginfodLog &Log,
-                       ThreadPool &Pool);
+                       ThreadPool &Pool, double MinInterval);
   Error update();
   Error updateForever(std::chrono::milliseconds Interval);
-  Expected<std::string> getDebugBinaryPath(BuildIDRef);
-  Expected<std::string> getBinaryPath(BuildIDRef);
+  Expected<std::string> findDebugBinaryPath(BuildIDRef);
+  Expected<std::string> findBinaryPath(BuildIDRef);
 };
 
 struct DebuginfodServer {
Index: llvm/lib/Debuginfod/Debuginfod.cpp
===================================================================
--- llvm/lib/Debuginfod/Debuginfod.cpp
+++ llvm/lib/Debuginfod/Debuginfod.cpp
@@ -236,13 +236,16 @@
 }
 
 DebuginfodCollection::DebuginfodCollection(ArrayRef<StringRef> PathsRef,
-                                           DebuginfodLog &Log, ThreadPool &Pool)
-    : Log(Log), Pool(Pool) {
+                                           DebuginfodLog &Log, ThreadPool &Pool,
+                                           double MinInterval)
+    : Log(Log), Pool(Pool), MinInterval(MinInterval) {
   for (auto Path : PathsRef)
     Paths.push_back(Path.str());
 }
 
 Error DebuginfodCollection::update() {
+  std::lock_guard<sys::Mutex> Guard(UpdateMutex);
+
   for (auto Path : Paths) {
     Log.push("Updating binaries at path " + Path);
     if (Error Err = findBinaries(Path))
@@ -252,6 +255,16 @@
   return Error::success();
 }
 
+Error DebuginfodCollection::updateIfStale() {
+  if (!UpdateTimer.isRunning() ||
+      UpdateTimer.getTotalTime().getWallTime() < MinInterval)
+    return createStringError(errc::device_or_resource_busy,
+                             "the collection is not stale");
+  if (Error Err = update())
+    return Err;
+  return Error::success();
+}
+
 Error DebuginfodCollection::updateForever(std::chrono::milliseconds Interval) {
   while (true) {
     if (Error Err = update())
@@ -346,42 +359,99 @@
   return Error::success();
 }
 
-Expected<std::string> DebuginfodCollection::getBinaryPath(BuildIDRef ID) {
+Expected<Optional<std::string>>
+DebuginfodCollection::getBinaryPath(BuildIDRef ID) {
+
   Log.push("getting binary path of ID " + buildIDToString(ID));
   if (!BinariesMutex.lock_shared())
     return createStringError(errc::resource_deadlock_would_occur,
                              "Failed to acquire reader lock.");
   auto Loc = Binaries.find(buildIDToString(ID));
   if (Loc != Binaries.end()) {
-    return Loc->getValue();
+    std::string Path = Loc->getValue();
+    if (!BinariesMutex.unlock_shared())
+      return createStringError(errc::resource_deadlock_would_occur,
+                               "Failed to release reader lock.");
+    return Path;
   }
   if (!BinariesMutex.unlock_shared())
     return createStringError(errc::resource_deadlock_would_occur,
                              "Failed to release reader lock.");
-  // federation
-  Expected<std::string> PathOrErr = getCachedOrDownloadExecutable(ID);
-  if (!PathOrErr)
-    return PathOrErr.takeError();
-
-  return getDebugBinaryPath(ID);
+  return None;
 }
 
-Expected<std::string> DebuginfodCollection::getDebugBinaryPath(BuildIDRef ID) {
+Expected<Optional<std::string>>
+DebuginfodCollection::getDebugBinaryPath(BuildIDRef ID) {
+
   Log.push("getting debug binary path of ID " + buildIDToString(ID));
   if (!DebugBinariesMutex.lock_shared())
     return createStringError(errc::resource_deadlock_would_occur,
                              "Failed to acquire reader lock.");
   auto Loc = DebugBinaries.find(buildIDToString(ID));
   if (Loc != DebugBinaries.end()) {
-    return Loc->getValue();
+    std::string Path = Loc->getValue();
+    if (!DebugBinariesMutex.unlock_shared())
+      return createStringError(errc::resource_deadlock_would_occur,
+                               "Failed to release reader lock.");
+    return Path;
   }
   if (!DebugBinariesMutex.unlock_shared())
     return createStringError(errc::resource_deadlock_would_occur,
                              "Failed to release reader lock.");
+  return None;
+}
+
+Expected<std::string> DebuginfodCollection::findBinaryPath(BuildIDRef ID) {
+  {
+    // check collection, perform on-demand update if stale
+    Expected<Optional<std::string>> PathOrErr = getBinaryPath(ID);
+    if (!PathOrErr)
+      return PathOrErr.takeError();
+    Optional<std::string> Path = *PathOrErr;
+    if (!Path) {
+      if (Error Err = updateIfStale())
+        return std::move(Err);
+      // try once more
+      PathOrErr = getBinaryPath(ID);
+      if (!PathOrErr)
+        return PathOrErr.takeError();
+      Path = *PathOrErr;
+    }
+    if (Path)
+      return Path.getValue();
+  }
+
+  // federation
+  Expected<std::string> PathOrErr = getCachedOrDownloadExecutable(ID);
+  if (!PathOrErr)
+    consumeError(PathOrErr.takeError());
+
+  // fall-back to debug binary
+  return findDebugBinaryPath(ID);
+}
+
+Expected<std::string> DebuginfodCollection::findDebugBinaryPath(BuildIDRef ID) {
+  {
+    // check collection, perform on-demand update if stale
+    Expected<Optional<std::string>> PathOrErr = getDebugBinaryPath(ID);
+    if (!PathOrErr)
+      return PathOrErr.takeError();
+    Optional<std::string> Path = *PathOrErr;
+    if (!Path) {
+      if (Error Err = updateIfStale())
+        return std::move(Err);
+      // try once more
+      PathOrErr = getDebugBinaryPath(ID);
+      if (!PathOrErr)
+        return PathOrErr.takeError();
+      Path = *PathOrErr;
+    }
+    if (Path)
+      return Path.getValue();
+  }
+
   // federation
-  Expected<std::string> PathOrErr = getCachedOrDownloadDebuginfo(ID);
-  return createStringError(errc::resource_deadlock_would_occur,
-                           "No matching binary available");
+  return getCachedOrDownloadDebuginfo(ID);
 }
 
 DebuginfodServer::DebuginfodServer(DebuginfodLog &Log,
@@ -397,7 +467,7 @@
           return;
         }
         BuildID ID(IDString.begin(), IDString.end());
-        Expected<std::string> PathOrErr = Collection.getDebugBinaryPath(ID);
+        Expected<std::string> PathOrErr = Collection.findDebugBinaryPath(ID);
         if (Error Err = PathOrErr.takeError()) {
           consumeError(std::move(Err));
           Request.setResponse({404, "text/plain", "Build ID not found\n"});
@@ -415,8 +485,8 @@
               {404, "text/plain", "Build ID is not a hex string\n"});
           return;
         }
-        Expected<std::string> PathOrErr =
-            Collection.getBinaryPath(BuildID(IDString.begin(), IDString.end()));
+        BuildID ID(IDString.begin(), IDString.end());
+        Expected<std::string> PathOrErr = Collection.findBinaryPath(ID);
         if (Error Err = PathOrErr.takeError()) {
           consumeError(std::move(Err));
           Request.setResponse({404, "text/plain", "Build ID not found\n"});