[llvm] [Debuginfod] DebuginfodCollection and DebuginfodServer for tracking local debuginfo.

[noajshu]

Summary

This library implements the class DebuginfodCollection, which scans a set of directories for binaries, classifying them according to whether they contain debuginfo. This also provides the DebuginfodServer, an HTTPServer which serves debuginfod's /debuginfo and /executable endpoints. This is intended as the final new supporting library required for llvm-debuginfod.

As implemented here, DebuginfodCollection only finds ELF binaries and DWARF debuginfo. All other files are ignored. However, the class interface is format-agnostic. Generalizing to support other platforms will require refactoring of LLVM's object parsing libraries to eliminate use of report_fatal_error (e.g. when reading WASM files), so that the debuginfod daemon does not crash when it encounters a malformed file on the disk.

The DebuginfodCollection is tested by end-to-end tests of the debuginfod server (D114846).

[phosek]

llvm/lib/Debuginfod/Debuginfod.cpp

249

I expect this loop to be the performance bottleneck, so I think we should consider using a ThreadPool here as well to process files in parallel. That's the strategy used by elfutils' debuginfod as well.

This would likely require rethinking the API to allow sharing the thread pool between the file processing and request handling in D114846.

[noajshu]

Add DebuginfodServer class. Add multithreaded directory scanning (unstable).

[noajshu]

Add federation to other debuginfod servers.

llvm/lib/Debuginfod/Debuginfod.cpp

249

Good idea!
I've added this, but I find the behavior unstable when the concurrency is >1 and a large directory is scanned.
I've searched around for the bug in my code and no luck. I'm wondering if it's possible some of the supporting libraries I'm using are not thread-safe or are leaking memory. But it's more likely I'm missing something obvious. Anyways, going to upload as it's WIP and maybe there is a better task queue architecture you could recommend.
PS: the TaskQueue in LLVM is not appropriate as it is for serialized sequence of tasks.

[noajshu]

Fix concurrency bug and rebase against main.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

249

The concurrency bug has been fixed.

[fche2]

llvm/lib/Debuginfod/Debuginfod.cpp

336

Don't you need a mutex-guard on this operation?

351

Ditto re. mutex-guard?

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

336

Thanks so much for catching this!
I propose to switch to RW-Mutex so the readers can read without blocking each other.

[noajshu]

Use RWMutex to protect readers and writers of the debug binaries and binaries collections.

[mysterymath]

llvm/include/llvm/Debuginfod/Debuginfod.h

82

I don't think the = 1 does anything, since providing a constructor inhibits generation of a default one.

93

Since all members are public, this should be a struct. This also fits with how it's used, post-construction.

llvm/lib/Debuginfod/Debuginfod.cpp

228–229

This seems a bit odd to unconditionally put to stdout; is this necessary?

Otherwise, the whole routine just becomes

while (true) {
  if (Error Err = update())
    return Err;
  std::this_thread::sleep_for(Interval);
}
return Error::success();

236

llvm_unreachable()?

326–330

Is there an advantage for manually managing the concurrency here, over passing it as an argument to ThreadPool, std::min-ed with the hardware concurrency?
From a cursor look at ThreadPool's API, each async call after the thread pool is full should just more-or-less push a std::function<void()> onto a vector.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

228–229

Thanks, I agree this is awkward. The first update is logged to stdout is so the lit tests in D114846 can tell when it's safe to query the server for debuginfo. If the test client pinged the server before it had found the binary it will return a 404 and the test will flake.

An alternative is to add a time delay before the client pings the server. This is discouraged as there is timing variability across systems.

We could hide this output except for when "verbose" logging is enabled, or similar. Would this be good?

[fche2]

llvm/lib/Debuginfod/Debuginfod.cpp

228–229

(For reference, the elfutils debuginfod exports prometheus metrics about the progress of its operations, so that an external testsuite process can synchronize.)

[mysterymath]

llvm/lib/Debuginfod/Debuginfod.cpp

228–229

The first update is logged to stdout is so the lit tests in D114846 can tell when it's safe to query the server for debuginfo. If the test client pinged the server before it had found the binary it will return a 404 and the test will flake.

Ah, this sounds like it'd be something generally useful then; it's not uncommon for servers to print once they're ready to serve.

Maybe we could make the startup process more explicit: initialize the cache, then bring up HTTP server, print something like "Serving on ...", then set up the continuous updates.

304–306

I poked around, and it doesn't look like dbgs() offers any thread-safety guarantees. If not, these async jobs may have have oddly interleaved logs at best, and undefined behavior at worst.

[noajshu]

Replace inserts to dbgs() with use of synchronized logging class

[noajshu]

Thanks @mysterymath and @fche2 for many very helpful comments!
@mysterymath suggested we could perform the first update manually, then print a message like "ready to accept connections". This way the test client knows when it can ask for artifacts. This seems logical so I will make this change in D114846.

Regarding logging:
@mysterymath pointed out that logging by inserting strings to dbgs() is thread-unsafe. @fche2 pointed out that elfutils' debuginfod exports Prometheus metrics. I would advocate for keeping some logging facility in the application if only because it is helpful for testing and debugging the code. I am not aware of an existing logging framework in LLVM, so I have created a simple std::queue-based logging class DebuginfodLog using a sys::Mutex to synchronize access. In the future this could be upgraded to support Prometheus exports or other features. Please let me know if you think this will suffice, or if you would prefer an alternative solution to the logging problem. Thanks a lot!

llvm/lib/Debuginfod/Debuginfod.cpp

326–330

As this is within a directory iterator loop, my concern was for when there is a large number of files within that directory. If we add tasks to the ThreadPool faster than they are completed, the memory usage of that vector of std::function<void()>s becomes unbounded. So I thought it best to manage the progress through the loop more manually. What do you think?

[mysterymath]

llvm/lib/Debuginfod/Debuginfod.cpp

326–330

I'm unsure whether or not the buildup would ever cause problems in practice; then again, I just finished cleaning up an unbounded memory usage problem that broke in production. I'll defer that determination to others with more experience.

Assuming we keep the semantics here, it seems like what we'd really want is a version of ThreadPool that blocks submission of additional requests if the thread pool is full. This would provide feedback to stop the iterator from producing additional entries that cannot yet be handled (and would thus need to be stored). This seems like a useful abstraction in its own right, and there's definitely prior art.

I'd suggest either wrapping ThreadPool to provide such an API (simplified for the purposes of this file) or adding it as an option to ThreadPool. The first would be a slight modification to the code you have to abstract out the management of NumTasksRemaining. It'd also probably be more elegant to have the blocking async call (s) wait on a condition variable, so that the next task that finishes can signal that there is now a thread available, rather than busy-waiting with sleep().

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

326–330

Thanks for these suggestions! I agree on all points.

It's only a small change to ThreadPool to let us wait for room in the queue with a condition variable:

bool queueEmptyUnlocked() { return Tasks.empty(); }

void ThreadPool::waitQueue() {
  // Wait for the queue to be empty
  std::unique_lock<std::mutex> LockGuard(QueueLock);
  CompletionCondition.wait(LockGuard, [&] { return queueEmptyUnlocked(); });
}

I also collected some data to find out when the unbounded memory usage of the queue of jobs could actually be a problem in production. From my measurements, each job in the pool's queue consumes approximately N + 320 bytes of memory, where N is the number of bytes in the file path. For the right system setup, this could indeed consume lots of memory. Briefly, filesystem caching could allow millions of file paths to be traversed in seconds, but actually reading those files could take longer, causing a queue buildup.

However, if these files are ELF binaries they will end up in our StringMap in memory anyways with the current implementation. So the unbounded memory usage will be a problem regardless for this user, if their files are mostly ELF binaries.

Therefore, only the user who has millions of non-ELF files mixed in with their smaller number of ELF binaries could meaningfully benefit from us waiting here to submit more jobs to the queue. For example, a developer user like myself with limited local memory and millions of files that are not ELF binaries. When I plug in the numbers for my own filesystem, I could fit one job for each file in my development directory with about .4 GB of total memory usage. This is a comfortable margin on my own system but I'm unsure about other users. So if it seems reasonable I will just make the small tweaks to ThreadPool API to be safe.

[noajshu]

Update ThreadPool API to allow waiting until the queue is empty, allowing Debuginfod to avoid unbounded queue size without manual concurrency management.

[mysterymath]

llvm/lib/Debuginfod/Debuginfod.cpp

335

If I'm reading this right, wouldn't this loop dispatch one item to the queue, wait for the queue to be empty, dispatch another item, wait for the queue to be empty, etc. It seems like this disables parallelism entirely.

I'd have expected this to wait until the queue was "not full"; then items would be dispatched until max concurrency was reached, and the next item dispatched the moment a thread becomes free.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

335

I don't think this should disable parallelism entirely as the queue will become empty as soon as the job starts processing in a worker thread, rather than when that job finishes. Let me double check this.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

335

On a closer look, you're right about it disabling parallelism. This is due to ThreadPool's internals! Further modification of the ThreadPool is required.

Also I think it would be simple enough to parametrize as waitQueueSize(size_t Size), blocking until the queue has at most Size tasks.

[noajshu]

Fix incorrect waiting for queue size in ThreadPool.

[noajshu]

Simplify implementation of ThreadPool::waitQueueSize

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

335

I corrected the implementation of waitQueueSize. Thank you for catching this!

Although it takes a Size parameter, I leave it as the default of 0 here.

[noajshu]

Update comments in Debuginfod.cpp and remove declaration of functions getCachedOrDownloadSource and getCachedOrDownloadExecutable from Debuginfod.h as they are only used internally by the debuginfod client.

[noajshu]

Thank you to all of the reviewers for your extremely helpful comments!

I believe there are no unresolved comments at this point, however I have two questions:

First, I wonder if it wouldn't hurt to add a /source endpoint, which doesn't check the local DebuginfodCollection at all but simply skips straight to using the client.
This way, users who run a local debuginfod server would only have to set all their known public servers in the DEBUGINFOD_URLS variable once when they start llvm-debuginfod. When they use a client tool (like llvm-symbolizer) it would suffice to point to their local server only, as all requests would be federated.

Second, I was wondering if there is any desire to split this out into two or more diffs. For example, although the changes to ThreadPool and Symbolize are quite small I'm happy to separate them out if desired.

Thank you!

[noajshu]

Add updateIfStale to safely update Collection if it is stale (possibly before a periodic update), and add locking to update() to prevent races with other callers.

[mysterymath]

It looks like something went a bit screwy with the last patch; the diff from that patch to the previous deletes a bunch of code, including waitQueueSize, which is still called. Would you try re-uploading the latest changes?

[mysterymath]

In D114845#3487357, @noajshu wrote:

First, I wonder if it wouldn't hurt to add a /source endpoint, which doesn't check the local DebuginfodCollection at all but simply skips straight to using the client.
This way, users who run a local debuginfod server would only have to set all their known public servers in the DEBUGINFOD_URLS variable once when they start llvm-debuginfod. When they use a client tool (like llvm-symbolizer) it would suffice to point to their local server only, as all requests would be federated.

Seems to me like we'd eventually want the source endpoint to behave like the other endpoints: first try looking things up locally, then federate. Both behaviors would be naturally supported when we get around to implementing the source endpoint. The behavior you describe would be the one you'd get if you provide an empty list of paths to scan.

Second, I was wondering if there is any desire to split this out into two or more diffs. For example, although the changes to ThreadPool and Symbolize are quite small I'm happy to separate them out if desired.

IMO, the symbolize change seems safe enough, but ThreadPool is a pretty foundational library. It seems wise to separate this out and loop in the folks who've tended to touch the thread pool; they may have more specific opinions.

[noajshu]

Add back accidentally-deleted changes (thanks @mysterymath !)

[noajshu]

Seems to me like we'd eventually want the source endpoint to behave like the other endpoints: first try looking things up locally, then federate. Both behaviors would be naturally supported when we get around to implementing the source endpoint.

I agree. In this case I won't add it here, but leave this for future revisions.

IMO, the symbolize change seems safe enough, but ThreadPool is a pretty foundational library. It seems wise to separate this out and loop in the folks who've tended to touch the thread pool; they may have more specific opinions.

Ok, I will split out those changes separately!

[mysterymath]

llvm/include/llvm/Debuginfod/Debuginfod.h

88

Since the Message is commonly formed by concatenation, making this take const Twine& Message instead should save some heap allocations when logging.

93

From how this is used, it looks like it'd be simpler to make pop() blocking and non-Optional.

llvm/lib/Debuginfod/Debuginfod.cpp

242

Prefer StringRef over auto, since the type is obvious and concrete.

249

const std::string& over auto; I think as written this will even copy the string.

305

EC, from the LLVM variable naming convention

307

I and E, from the LLVM variable naming convention

341

std::lock_guard should work with RWMutexes for exclusive locking, and it's easier to read than doing it manually.

356

364

nit: remove empty line

385

nit: remove empty line

406

412–413

This path will always usually cause a "collection was not stale" error message if the binary was not found, which isn't as good as just "binary not found." It's also surprising that updateIfStale() will throw an error if the collection was not stale; usually methods with that naming convention do nothing, since the name suggests that it's not an error to violate the precondition.

414

424

429

435

443

453

477

This return doesn't do anything; remove.

[noajshu]

Remove changes to ThreadPool, which were moved to D126815.

[noajshu]

Replace manual locking of RWMutex with RAII locks throughout, incorporate other suggested changes.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

341

Thanks! Since we're `std::shared_lock<RWMutex> lock(write);

412–413

Good point, how about this? We return an Expected<bool> where if there are no errors during update(), returns whether the collection got updated. If it's not stale, we don't bother checking for the path again.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

341

Good idea, I switched everything to use std:: raii locks and it's much cleaner.

[mysterymath]

LGTM, but please wait until at least sometime next week to submit, so there's space for any last-chance comments on this one.

[noajshu]

Add back declaration of getDefaultDebuginfodUrls, as it is used by llvm-symbolizer.

[noajshu]

Correct usage of Timer

[noajshu]

Per the discussion on D126815, we switch the concurrency model to one in which workers directly advance the shared (lock-protected) directory iterator.

We add a condition variable to notify the main update thread when the iteration is complete and all workers have returned. We have removed the dependency on waitQueueSize so that we can proceed without D126815.

[mysterymath]

llvm/lib/Debuginfod/Debuginfod.cpp

371–377

Since each async call exits as soon as I == E || EC, this block can be replaced with just ThreadPool.wait(), and there's no need to maintain a separate condition variable. (ThreadPool maintains one internally for this purpose.)
It also looks like the decrements of NumActiveWorkers and the outer loop are interleaved in a way that adds some complexity to the situation; this would remove the need for NumActiveWorkers, which clears that up too.

[noajshu]

Rebase against main and replace NumActiveThreads counting with use of ThreadPoolTaskGroup.

[noajshu]

llvm/lib/Debuginfod/Debuginfod.cpp

371–377

great idea!

Since the first draft of this revision, ThreadPoolTaskGroup was merged into LLVM. It nicely fits our use case, here we just use IteratorGroup.wait();.

(now that I am aware of the new Task Group feature, I propose to close D126815 altogether, as it does appear quite ad-hoc in light of the clean alternative of using a task group)

[thakis]

This doesn't build: http://45.33.8.238/linux/80459/step_4.txt

[thakis]

In D114845#3633730, @thakis wrote:

This doesn't build: http://45.33.8.238/linux/80459/step_4.txt

(fixed in 39ed08f8d452)

[Meinersbur]

I think this causes link errors in shared library builds:

https://lab.llvm.org/buildbot/#/builders/207/builds/8193
https://lab.llvm.org/buildbot/#/builders/181/builds/5860

[noajshu]

In D114845#3633866, @Meinersbur wrote:

I think this causes link errors in shared library builds:

https://lab.llvm.org/buildbot/#/builders/207/builds/8193
https://lab.llvm.org/buildbot/#/builders/181/builds/5860

Thanks, I'm trying to reproduce this with a local build to see what the problem is.

[noajshu]

I have a fix, pushing now.

[hubert.reinterpretcast]

It's been 6 hours since https://lab.llvm.org/buildbot/#/builders/57/builds/19588 started failing with

FAILED: lib/libLLVMDebuginfod.so.15git

[noajshu]

In D114845#3634447, @hubert.reinterpretcast wrote:

It's been 6 hours since https://lab.llvm.org/buildbot/#/builders/57/builds/19588 started failing with

FAILED: lib/libLLVMDebuginfod.so.15git

Sorry about this, I'll fix this right away.

[noajshu]

In D114845#3634447, @hubert.reinterpretcast wrote:

It's been 6 hours since https://lab.llvm.org/buildbot/#/builders/57/builds/19588 started failing with

FAILED: lib/libLLVMDebuginfod.so.15git

fixed by 819a7f98cd6d

[hubert.reinterpretcast]

In D114845#3634557, @noajshu wrote:

fixed by 819a7f98cd6d

Thanks!

llvm/include/llvm/DebugInfo/Symbolize/Symbolize.h

public:
 
   size_t size() { return Bin.getBinary()->getData().size(); }
 
 private:
   OwningBinary<Binary> Bin;
   std::function<void()> Evictor;
 };
 
+Optional<ArrayRef<uint8_t>> getBuildID(const ELFObjectFileBase *Obj);
+
 } // end namespace symbolize
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_SYMBOLIZE_SYMBOLIZE_H

llvm/include/llvm/Debuginfod/Debuginfod.h

 //===-- llvm/Debuginfod/Debuginfod.h - Debuginfod client --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
-/// This file contains the declarations of getCachedOrDownloadArtifact and
-/// several convenience functions for specific artifact types:
+/// This file contains several declarations for the debuginfod client and
+/// server. The client functions are getCachedOrDownloadArtifact and several
+/// convenience functions for specific artifact types:
 /// getCachedOrDownloadSource, getCachedOrDownloadExecutable, and
-/// getCachedOrDownloadDebuginfo. This file also declares
-/// getDefaultDebuginfodUrls and getDefaultDebuginfodCacheDirectory.
-///
+/// getCachedOrDownloadDebuginfo. For the server, this file declares the
+/// DebuginfodLogEntry and DebuginfodServer structs, as well as the
+/// DebuginfodLog, DebuginfodCollection classes.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFOD_DEBUGINFOD_H
 #define LLVM_DEBUGINFOD_DEBUGINFOD_H
 
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Debuginfod/HTTPServer.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Mutex.h"
+#include "llvm/Support/RWMutex.h"
+#include "llvm/Support/Timer.h"
 
 #include <chrono>
+#include <queue>
 
 namespace llvm {
 
 typedef ArrayRef<uint8_t> BuildIDRef;
 
 typedef SmallVector<uint8_t, 10> BuildID;
 
-/// Finds default array of Debuginfod server URLs by checking DEBUGINFOD_URLS
-/// environment variable.
-Expected<SmallVector<StringRef>> getDefaultDebuginfodUrls();
-
-/// Finds a default local file caching directory for the debuginfod client,
-/// first checking DEBUGINFOD_CACHE_PATH.
-Expected<std::string> getDefaultDebuginfodCacheDirectory();
-
 /// Finds a default timeout for debuginfod HTTP requests. Checks
 /// DEBUGINFOD_TIMEOUT environment variable, default is 90 seconds (90000 ms).
 std::chrono::milliseconds getDefaultDebuginfodTimeout();
 
 /// Fetches a specified source file by searching the default local cache
 /// directory and server URLs.
 Expected<std::string> getCachedOrDownloadSource(BuildIDRef ID,
                                                 StringRef SourceFilePath);

 
 /// Fetches any debuginfod artifact using the specified local cache directory,
 /// server URLs, and request timeout (in milliseconds). If the artifact is
 /// found, uses the UniqueKey for the local cache file.
 Expected<std::string> getCachedOrDownloadArtifact(
     StringRef UniqueKey, StringRef UrlPath, StringRef CacheDirectoryPath,
     ArrayRef<StringRef> DebuginfodUrls, std::chrono::milliseconds Timeout);
 
+class ThreadPool;
+
+struct DebuginfodLogEntry {
+  std::string Message;
+  DebuginfodLogEntry() = default;
+  DebuginfodLogEntry(StringRef Message);
+};
+
+class DebuginfodLog {
+  std::mutex QueueMutex;
+  std::condition_variable QueueCondition;
+  std::queue<DebuginfodLogEntry> LogEntryQueue;
+
+public:
+  // Adds a log entry to end of the queue.
+  void push(DebuginfodLogEntry Entry);
+  // Adds a log entry to end of the queue.
+  void push(StringRef Message);
+  // If there are log entries in the queue, pops and returns the first one.
+  // Otherwise returns None.
+  Optional<DebuginfodLogEntry> pop();
+  /// Blocking wait for the log entry queue to have a message.
+  void wait();
+};
+
+/// Tracks a collection of debuginfod artifacts on the local filesystem.
+class DebuginfodCollection {
+  SmallVector<std::string, 1> Paths;
+  sys::RWMutex BinariesMutex;
+  StringMap<std::string> Binaries;
+  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, double MinInterval);
+  Error update();
+  Error updateForever(std::chrono::milliseconds Interval);
+  Expected<std::string> findDebugBinaryPath(BuildIDRef);
+  Expected<std::string> findBinaryPath(BuildIDRef);
+};
+
+struct DebuginfodServer {
+  HTTPServer Server;
+  DebuginfodLog &Log;
+  DebuginfodCollection &Collection;
+  DebuginfodServer(DebuginfodLog &Log, DebuginfodCollection &Collection);
+};
+
 } // end namespace llvm
 
 #endif

llvm/include/llvm/Support/ThreadPool.h

public:
   auto async(Func &&F) -> std::shared_future<decltype(F())> {
     return asyncImpl(std::function<decltype(F())()>(std::forward<Func>(F)));
   }
 
   /// Blocking wait for all the threads to complete and the queue to be empty.
   /// It is an error to try to add new tasks while blocking on this call.
   void wait();
 
+  /// Blocking wait for the queue to have size at most Size.
+  void waitQueueSize(size_t Size = 0);
+
   // TODO: misleading legacy name warning!
   // Returns the maximum number of worker threads in the pool, not the current
   // number of threads!
   unsigned getThreadCount() const { return MaxThreadCount; }
 
   /// Returns true if the current thread is a worker thread of this thread pool.
   bool isWorkerThread() const;
 
#endif
 
   /// Locking and signaling for accessing the Tasks queue.
   std::mutex QueueLock;
   std::condition_variable QueueCondition;
 
   /// Signaling for job completion
   std::condition_variable CompletionCondition;
 
+  /// Signaling for queue size decreases
+  std::condition_variable QueueSizeDecreaseCondition;
+
   /// Keep track of the number of thread actually busy
   unsigned ActiveThreads = 0;
 
 #if LLVM_ENABLE_THREADS // avoids warning for unused variable
   /// Signal for the destruction of the pool, asking thread to exit.
   bool EnableFlag = true;
 #endif
 
   const ThreadPoolStrategy Strategy;
 
   /// Maximum number of threads to potentially grow this pool to.
   const unsigned MaxThreadCount;
 };
 }
 
 #endif // LLVM_SUPPORT_THREADPOOL_H

llvm/lib/DebugInfo/Symbolize/Symbolize.cpp

for (auto N : Obj.notes(P, Err))
       if (N.getType() == ELF::NT_GNU_BUILD_ID &&
           N.getName() == ELF::ELF_NOTE_GNU)
         return N.getDesc();
     consumeError(std::move(Err));
   }
   return {};
 }
 
+} // end anonymous namespace
+
 Optional<ArrayRef<uint8_t>> getBuildID(const ELFObjectFileBase *Obj) {
   Optional<ArrayRef<uint8_t>> BuildID;
   if (auto *O = dyn_cast<ELFObjectFile<ELF32LE>>(Obj))
     BuildID = getBuildID(O->getELFFile());
   else if (auto *O = dyn_cast<ELFObjectFile<ELF32BE>>(Obj))
     BuildID = getBuildID(O->getELFFile());
   else if (auto *O = dyn_cast<ELFObjectFile<ELF64LE>>(Obj))
     BuildID = getBuildID(O->getELFFile());
   else if (auto *O = dyn_cast<ELFObjectFile<ELF64BE>>(Obj))
     BuildID = getBuildID(O->getELFFile());
   else
     llvm_unreachable("unsupported file format");
   return BuildID;
 }
 
-} // end anonymous namespace
-
 ObjectFile *LLVMSymbolizer::lookUpDsymFile(const std::string &ExePath,
                                            const MachOObjectFile *MachExeObj,
                                            const std::string &ArchName) {
   // On Darwin we may find DWARF in separate object file in
   // resource directory.
   std::vector<std::string> DsymPaths;
   StringRef Filename = sys::path::filename(ExePath);
   DsymPaths.push_back(

llvm/lib/Debuginfod/CMakeLists.txt

add_llvm_library(LLVMDebuginfod
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Debuginfod
 
   LINK_LIBS
   ${imported_libs}
 
   LINK_COMPONENTS
   Support
   Symbolize
+  DebugInfoDWARF
   )

llvm/lib/Debuginfod/Debuginfod.cpp

 //===-- llvm/Debuginfod/Debuginfod.cpp - Debuginfod client library --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 ///
-/// This file defines the fetchInfo function, which retrieves
-/// any of the three supported artifact types: (executable, debuginfo, source
-/// file) associated with a build-id from debuginfod servers. If a source file
-/// is to be fetched, its absolute path must be specified in the Description
-/// argument to fetchInfo.
+/// This file contains several definitions for the debuginfod client and server.
+/// For the client, this file defines the fetchInfo function. For the server,
+/// this file defines the DebuginfodLogEntry and DebuginfodServer structs, as
+/// well as the DebuginfodLog, DebuginfodCollection classes. The fetchInfo
+/// function retrieves any of the three supported artifact types: (executable,
+/// debuginfo, source file) associated with a build-id from debuginfod servers.
+/// If a source file is to be fetched, its absolute path must be specified in
+/// the Description argument to fetchInfo. The DebuginfodLogEntry,
+/// DebuginfodLog, and DebuginfodCollection are used by the DebuginfodServer to
+/// scan the local filesystem for binaries and serve the debuginfod protocol.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Debuginfod/Debuginfod.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/BinaryFormat/Magic.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/DebugInfo/Symbolize/Symbolize.h"
 #include "llvm/Debuginfod/HTTPClient.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/Caching.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileUtilities.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/xxhash.h"
 
+#include <atomic>
+
+#define DEBUG_TYPE "Debuginfod"
+
 namespace llvm {
 static std::string uniqueKey(llvm::StringRef S) { return utostr(xxHash64(S)); }
 
 // Returns a binary BuildID as a normalized hex string.
 // Uses lowercase for compatibility with common debuginfod servers.
 static std::string buildIDToString(BuildIDRef ID) {
   return llvm::toHex(ID, /*LowerCase=*/true);
 }
 
+/// Finds default array of Debuginfod server URLs by checking DEBUGINFOD_URLS
+/// environment variable.
 Expected<SmallVector<StringRef>> getDefaultDebuginfodUrls() {
   const char *DebuginfodUrlsEnv = std::getenv("DEBUGINFOD_URLS");
   if (DebuginfodUrlsEnv == nullptr)
     return SmallVector<StringRef>();
 
   SmallVector<StringRef> DebuginfodUrls;
   StringRef(DebuginfodUrlsEnv).split(DebuginfodUrls, " ");
   return DebuginfodUrls;
 }
 
+Expected<SmallVector<StringRef>> getDefaultDebuginfodUrls();
+
+/// Finds a default local file caching directory for the debuginfod client,
+/// first checking DEBUGINFOD_CACHE_PATH.
 Expected<std::string> getDefaultDebuginfodCacheDirectory() {
   if (const char *CacheDirectoryEnv = std::getenv("DEBUGINFOD_CACHE_PATH"))
     return CacheDirectoryEnv;
 
   SmallString<64> CacheDirectory;
   if (!sys::path::cache_directory(CacheDirectory))
     return createStringError(
         errc::io_error, "Unable to determine appropriate cache directory.");
*FileStream->OS << StringRef(Response.Body->getBufferStart(),
                                  Response.Body->getBufferSize());
 
     // Return the path to the artifact on disk.
     return std::string(AbsCachedArtifactPath);
   }
 
   return createStringError(errc::argument_out_of_domain, "build id not found");
 }
+
+DebuginfodLogEntry::DebuginfodLogEntry(StringRef Message) : Message(Message) {}
+
+void DebuginfodLog::push(StringRef Message) {
+  push(DebuginfodLogEntry(Message));
+}
+
+void DebuginfodLog::push(DebuginfodLogEntry Entry) {
+  {
+    std::lock_guard<std::mutex> Guard(QueueMutex);
+    LogEntryQueue.push(Entry);
+  }
+  QueueCondition.notify_one();
+}
+
+void DebuginfodLog::wait() {
+  std::unique_lock<std::mutex> Guard(QueueMutex);
+  // Wait for messages to be pushed into the queue
+  QueueCondition.wait(Guard, [&] { return !LogEntryQueue.empty(); });
+}
+
+Optional<DebuginfodLogEntry> DebuginfodLog::pop() {
+  std::lock_guard<std::mutex> Guard(QueueMutex);
+  if (!LogEntryQueue.size())
+    return None;
+  DebuginfodLogEntry Entry = LogEntryQueue.front();
+  LogEntryQueue.pop();
+  return Entry;
+}
+
+DebuginfodCollection::DebuginfodCollection(ArrayRef<StringRef> PathsRef,
+                                           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))
+      return Err;
+  }
+  Log.push("Updated collection");
+  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())
+      return Err;
+    std::this_thread::sleep_for(Interval);
+  }
+  llvm_unreachable("updateForever loop should never end");
+}
+
+static bool isDebugBinary(object::ObjectFile *Object) {
+  // TODO: handle PDB debuginfo
+  std::unique_ptr<DWARFContext> Context = DWARFContext::create(
+      *Object, DWARFContext::ProcessDebugRelocations::Process);
+  const DWARFObject &DObj = Context->getDWARFObj();
+  unsigned NumSections = 0;
+  DObj.forEachInfoSections([&](const DWARFSection &S) { NumSections++; });
+  return NumSections;
+}
+
+static bool hasELFMagic(StringRef FilePath) {
+  file_magic Type;
+  std::error_code EC = identify_magic(FilePath, Type);
+  if (EC)
+    return false;
+  switch (Type) {
+  case file_magic::elf:
+  case file_magic::elf_relocatable:
+  case file_magic::elf_executable:
+  case file_magic::elf_shared_object:
+  case file_magic::elf_core:
+    return true;
+  default:
+    return false;
+  }
+}
+
+Error DebuginfodCollection::findBinaries(StringRef Path) {
+  std::error_code ec;
+
+  for (sys::fs::recursive_directory_iterator i(Twine(Path), ec), e; i != e;
+       i.increment(ec)) {
+    if (ec)
+      return errorCodeToError(ec);
+
+    std::string FilePath = i->path();
+
+    Pool.async([FilePath, this]() -> void {
+      if (!hasELFMagic(FilePath))
+        return;
+
+      Expected<object::OwningBinary<object::Binary>> BinOrErr =
+          object::createBinary(FilePath);
+
+      if (!BinOrErr) {
+        consumeError(BinOrErr.takeError());
+        return;
+      }
+      object::Binary *Bin = std::move(BinOrErr.get().getBinary());
+      if (!Bin->isObject())
+        return;
+
+      // TODO: Support non-ELF binaries
+      object::ELFObjectFileBase *Object =
+          dyn_cast<object::ELFObjectFileBase>(Bin);
+      if (!Object)
+        return;
+
+      Optional<BuildIDRef> ID = symbolize::getBuildID(Object);
+      if (!ID)
+        return;
+
+      std::string IDString = buildIDToString(ID.getValue());
+      if (isDebugBinary(Object)) {
+        bool LockSucceeded = DebugBinariesMutex.lock();
+        assert(LockSucceeded && "Failed to acquire writer lock.");
+        DebugBinaries[IDString] = FilePath;
+        LockSucceeded = DebugBinariesMutex.unlock();
+        assert(LockSucceeded && "Failed to release writer lock.");
+      } else {
+        bool LockSucceeded = BinariesMutex.lock();
+        assert(LockSucceeded && "Failed to acquire writer lock.");
+        Binaries[IDString] = FilePath;
+        LockSucceeded = BinariesMutex.unlock();
+        assert(LockSucceeded && "Failed to release writer lock.");
+      }
+      return;
+    });
+    // Wait for empty queue before proceeding to the next file to avoid
+    // unbounded memory usage
+    Pool.waitQueueSize();
+  }
+  return Error::success();
+}
+
+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()) {
+    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.");
+  return None;
+}
+
+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()) {
+    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
+  return getCachedOrDownloadDebuginfo(ID);
+}
+
+DebuginfodServer::DebuginfodServer(DebuginfodLog &Log,
+                                   DebuginfodCollection &Collection)
+    : Log(Log), Collection(Collection) {
+  cantFail(
+      Server.get(R"(/buildid/(.*)/debuginfo)", [&](HTTPServerRequest Request) {
+        Log.push("GET " + Request.UrlPath);
+        std::string IDString;
+        if (!tryGetFromHex(Request.UrlPathMatches[0], IDString)) {
+          Request.setResponse(
+              {404, "text/plain", "Build ID is not a hex string\n"});
+          return;
+        }
+        BuildID ID(IDString.begin(), IDString.end());
+        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"});
+          return;
+        }
+        streamFile(Request, *PathOrErr);
+        return;
+      }));
+  cantFail(
+      Server.get(R"(/buildid/(.*)/executable)", [&](HTTPServerRequest Request) {
+        Log.push("GET " + Request.UrlPath);
+        std::string IDString;
+        if (!tryGetFromHex(Request.UrlPathMatches[0], IDString)) {
+          Request.setResponse(
+              {404, "text/plain", "Build ID is not a hex string\n"});
+          return;
+        }
+        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"});
+          return;
+        }
+        streamFile(Request, *PathOrErr);
+      }));
+}
+
 } // namespace llvm

llvm/lib/Support/ThreadPool.cpp

Threads.emplace_back([this, ThreadID] {
           // Yeah, we have a task, grab it and release the lock on the queue
 
           // We first need to signal that we are active before popping the queue
           // in order for wait() to properly detect that even if the queue is
           // empty, there is still a task in flight.
           ++ActiveThreads;
           Task = std::move(Tasks.front());
           Tasks.pop();
+
+          // Notify the condition variable that the queue size has decreased.
+          QueueSizeDecreaseCondition.notify_one();
         }
         // Run the task we just grabbed
         Task();
 
         bool Notify;
         {
           // Adjust `ActiveThreads`, in case someone waits on ThreadPool::wait()
           std::lock_guard<std::mutex> LockGuard(QueueLock);

 }
 
 void ThreadPool::wait() {
   // Wait for all threads to complete and the queue to be empty
   std::unique_lock<std::mutex> LockGuard(QueueLock);
   CompletionCondition.wait(LockGuard, [&] { return workCompletedUnlocked(); });
 }
 
+void ThreadPool::waitQueueSize(size_t Size) {
+  // Wait for the queue to have at most Size elements
+  std::unique_lock<std::mutex> LockGuard(QueueLock);
+  QueueSizeDecreaseCondition.wait(LockGuard,
+                                  [&] { return Tasks.size() <= Size; });
+}
+
 bool ThreadPool::isWorkerThread() const {
   std::unique_lock<std::mutex> LockGuard(ThreadsLock);
   llvm::thread::id CurrentThreadId = llvm::this_thread::get_id();
   for (const llvm::thread &Thread : Threads)
     if (CurrentThreadId == Thread.get_id())
       return true;
   return false;
 }