[clangd] Introduce memory dumping to FileIndex, FileSymbols and BackgroundIndex

[kadircet]

Summary

File-granular information is considered details.

Depends on D88411

[kadircet]

• Rebase

[sammccall]

clang-tools-extra/clangd/index/Background.cpp

420

Hmm, we should be careful now, estimateMemoryUsage() is "total" while addUsage takes "self".

We're not overriding estimateMemoryUsage here to include IndexedSymbols, but this is probably just an oversight. Consider calling SwapIndex::estimateMemoryUsage() explicitly to guard/communicate against this.

In the long-run, we should put attachMemoryUsage on SymbolIndex and either remove estimateMemoryUsage() or make it non-virtual (MemoryTree R; attachMemoryUsage(R); return R.total())

clang-tools-extra/clangd/index/Background.h

177

As a conventional name for these, profile() or so might be slightly more evocative. And I think we should push this into progressively more places (that currently have ad-hoc "estimate" accessors) so the brevity is reasonable I think.

(If not, I'd even slightly prefer "record"/"measure" over "attach" as emphasizing the high-level operation rather than the data structure used can help readability)

clang-tools-extra/clangd/index/FileIndex.cpp

380

addChild("symbols"/"refs"/"relations")?
This seems like really useful information

466

addChild("preamble").addChild("symbols")?

[kadircet]

• Rename attachMemoryUsage to profile
• Split file symbols into symbols/refs/relations granularity
• Rebase

[sammccall]

Now there's lots of usage (which looks good!) i'm finding it a bit hard to keep track of what the tree will look like overall.

At some point it'd be great to:
a) bind this to an LSP extension so we can see it in editors
b) add a lit test that calls that extension method and includes a dump of the output

[kadircet]

In D88414#2317106, @sammccall wrote:

Now there's lots of usage (which looks good!) i'm finding it a bit hard to keep track of what the tree will look like overall.

At some point it'd be great to:
a) bind this to an LSP extension so we can see it in editors

i was also thinking about it and couldn't decide between a "custom command" vs "code action".

• the former gives a richer interaction, but requires every editor plugin to implement support.
• the latter is a little bit more restrictive but doesn't require a bunch of extra work.

I am happy to go with the "code action" approach initially. WDYT? (not in the scope of this patch)

[kadircet]

• Fix a bug in FileSymbols profiling.
• Add unittests to ensure tree structure is as expected.

[sammccall]

In D88414#2319161, @kadircet wrote:

In D88414#2317106, @sammccall wrote:

Now there's lots of usage (which looks good!) i'm finding it a bit hard to keep track of what the tree will look like overall.

At some point it'd be great to:
a) bind this to an LSP extension so we can see it in editors

i was also thinking about it and couldn't decide between a "custom command" vs "code action".

• the former gives a richer interaction, but requires every editor plugin to implement support.
• the latter is a little bit more restrictive but doesn't require a bunch of extra work.

I am happy to go with the "code action" approach initially. WDYT? (not in the scope of this patch)

I'm pretty leery about code action because it's not at all context-sensitive (not even per-file).
That also doesn't give us any way to specify detail vs summary if we want that.
I'd suggest a custom LSP method (unless there's some reason to prefer executeCommand? Seems like additional indirection for no benefit).

[sammccall]

In D88414#2320859, @sammccall wrote:

In D88414#2319161, @kadircet wrote:

In D88414#2317106, @sammccall wrote:

Now there's lots of usage (which looks good!) i'm finding it a bit hard to keep track of what the tree will look like overall.

At some point it'd be great to:
a) bind this to an LSP extension so we can see it in editors

i was also thinking about it and couldn't decide between a "custom command" vs "code action".

• the former gives a richer interaction, but requires every editor plugin to implement support.
• the latter is a little bit more restrictive but doesn't require a bunch of extra work.

I am happy to go with the "code action" approach initially. WDYT? (not in the scope of this patch)

I'm pretty leery about code action because it's not at all context-sensitive (not even per-file).

Another slighty silly reason: because of layering, a code action is going to have a hard time getting at ClangdLSPServer's profile (or even ClangdServer's).
Whereas a custom method will be implemented at that layer.

(We could work around this in various ways, but I think we'll create a bit of a mess)

clang-tools-extra/clangd/index/Background.h

 
 #include "GlobalCompilationDatabase.h"
 #include "SourceCode.h"
 #include "index/BackgroundRebuild.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/Serialization.h"
 #include "support/Context.h"
+#include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "support/Threading.h"
 #include "support/ThreadsafeFS.h"
+#include "support/Trace.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Threading.h"
 #include <atomic>
 #include <condition_variable>
 #include <deque>
 #include <mutex>
 #include <queue>
public:
   }
 
   // Wait until the queue is empty, to allow deterministic testing.
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10) {
     return Queue.blockUntilIdleForTest(TimeoutSeconds);
   }
 
+  void profile(MemoryTree &MT) const;
+
 private:
   /// Represents the state of a single file when indexing was performed.
   struct ShardVersion {
     FileDigest Digest{{0}};
     bool HadErrors = false;
   };
 
   /// Given index results from a TU, only update symbols coming from files with

clang-tools-extra/clangd/index/Background.cpp

 #include "Config.h"
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "SourceCode.h"
 #include "Symbol.h"
 #include "URI.h"
 #include "index/BackgroundIndexLoader.h"
 #include "index/FileIndex.h"
+#include "index/Index.h"
 #include "index/IndexAction.h"
 #include "index/MemIndex.h"
 #include "index/Ref.h"
 #include "index/Relation.h"
 #include "index/Serialization.h"
 #include "index/SymbolCollector.h"
 #include "support/Context.h"
 #include "support/Logger.h"
for (auto &LS : Result) {
     // FIXME: Try looking at other TUs if no compile commands are available
     // for this TU, i.e TU was deleted after we performed indexing.
     TUsToIndex.insert(TUForFile);
   }
 
   return {TUsToIndex.begin(), TUsToIndex.end()};
 }
 
+void BackgroundIndex::profile(MemoryTree &MT) const {
+  IndexedSymbols.profile(MT.child("symbols"));
+  // We don't want to mix memory used by index and symbols, so call base class.
+  MT.child("index").addUsage(SwapIndex::estimateMemoryUsage());
+}
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/FileIndex.h

 #include "Index.h"
 #include "MemIndex.h"
 #include "Merge.h"
 #include "index/CanonicalIncludes.h"
 #include "index/Ref.h"
 #include "index/Relation.h"
 #include "index/Serialization.h"
 #include "index/Symbol.h"
+#include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
public:
   /// Will count Symbol::References based on number of references in the main
   /// files, while building the index with DuplicateHandling::Merge option.
   /// Version is populated with an increasing sequence counter.
   std::unique_ptr<SymbolIndex>
   buildIndex(IndexType,
              DuplicateHandling DuplicateHandle = DuplicateHandling::PickOne,
              size_t *Version = nullptr);
 
+  void profile(MemoryTree &MT) const;
+
 private:
   struct RefSlabAndCountReferences {
     std::shared_ptr<RefSlab> Slab;
     bool CountReferences = false;
   };
   mutable std::mutex Mutex;
 
   size_t Version = 0;
public:
   void updatePreamble(PathRef Path, llvm::StringRef Version, ASTContext &AST,
                       std::shared_ptr<Preprocessor> PP,
                       const CanonicalIncludes &Includes);
 
   /// Update symbols and references from main file \p Path with
   /// `indexMainDecls`.
   void updateMain(PathRef Path, ParsedAST &AST);
 
+  void profile(MemoryTree &MT) const;
+
 private:
   bool UseDex; // FIXME: this should be always on.
   bool CollectMainFileRefs;
 
   // Contains information from each file's preamble only. Symbols and relations
   // are sharded per declaration file to deduplicate multiple symbols and reduce
   // memory usage.
   // Missing information:

clang-tools-extra/clangd/index/FileIndex.cpp

 #include "index/Ref.h"
 #include "index/Relation.h"
 #include "index/Serialization.h"
 #include "index/Symbol.h"
 #include "index/SymbolID.h"
 #include "index/SymbolOrigin.h"
 #include "index/dex/Dex.h"
 #include "support/Logger.h"
+#include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
return std::make_unique<dex::Dex>(
         std::move(AllRelations),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                         std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   }
   llvm_unreachable("Unknown clangd::IndexType");
 }
 
+void FileSymbols::profile(MemoryTree &MT) const {
+  std::lock_guard<std::mutex> Lock(Mutex);
+  for (const auto &SymSlab : SymbolsSnapshot) {
+    MT.detail(SymSlab.first())
+        .child("symbols")
+        .addUsage(SymSlab.second->bytes());
+  }
+  for (const auto &RefSlab : RefsSnapshot) {
+    MT.detail(RefSlab.first())
+        .child("references")
+        .addUsage(RefSlab.second.Slab->bytes());
+  }
+  for (const auto &RelSlab : RelationsSnapshot) {
+    MT.detail(RelSlab.first())
+        .child("relations")
+        .addUsage(RelSlab.second->bytes());
+  }
+}
+
 FileIndex::FileIndex(bool UseDex, bool CollectMainFileRefs)
     : MergedIndex(&MainFileIndex, &PreambleIndex), UseDex(UseDex),
       CollectMainFileRefs(CollectMainFileRefs),
       PreambleIndex(std::make_unique<MemIndex>()),
       MainFileIndex(std::make_unique<MemIndex>()) {}
 
 void FileIndex::updatePreamble(PathRef Path, llvm::StringRef Version,
                                ASTContext &AST,
auto NewIndex = MainFileSymbols.buildIndex(
     MainFileIndex.reset(std::move(NewIndex));
     vlog(
         "Build dynamic index for main-file symbols with estimated memory usage "
         "of {0} bytes",
         MainFileIndex.estimateMemoryUsage());
   }
 }
 
+void FileIndex::profile(MemoryTree &MT) const {
+  PreambleSymbols.profile(MT.child("preamble").child("symbols"));
+  MT.child("preamble")
+      .child("index")
+      .addUsage(PreambleIndex.estimateMemoryUsage());
+  MainFileSymbols.profile(MT.child("main_file").child("symbols"));
+  MT.child("main_file")
+      .child("index")
+      .addUsage(MainFileIndex.estimateMemoryUsage());
+}
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp

 #include <deque>
 #include <thread>
 
 using ::testing::_;
 using ::testing::AllOf;
 using ::testing::Contains;
 using ::testing::ElementsAre;
 using ::testing::Not;
+using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
 MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; }
 MATCHER(Declared, "") {
TEST(BackgroundQueueTest, Progress) {
   EXPECT_EQ(PingCount.load(), 1000);
   EXPECT_EQ(PongCount.load(), 1000);
   EXPECT_EQ(S.Active, 0u);
   EXPECT_EQ(S.Enqueued, 2000u);
   EXPECT_EQ(S.Completed, 2000u);
   EXPECT_EQ(S.LastIdle, 2000u);
 }
 
+TEST(BackgroundIndex, Profile) {
+  MockFS FS;
+  MockCompilationDatabase CDB;
+  BackgroundIndex Idx(FS, CDB, [](llvm::StringRef) { return nullptr; },
+                      /*Opts=*/{});
+
+  llvm::BumpPtrAllocator Alloc;
+  MemoryTree MT(&Alloc);
+  Idx.profile(MT);
+  ASSERT_THAT(MT.children(),
+              UnorderedElementsAre(Pair("symbols", _), Pair("index", _)));
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/FileIndexTests.cpp

 #include "URI.h"
 #include "index/CanonicalIncludes.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/Ref.h"
 #include "index/Relation.h"
 #include "index/Serialization.h"
 #include "index/Symbol.h"
+#include "index/SymbolID.h"
 #include "support/Threading.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/Utils.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Allocator.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <utility>
+#include <vector>
 
 using ::testing::_;
 using ::testing::AllOf;
 using ::testing::Contains;
 using ::testing::ElementsAre;
+using ::testing::Gt;
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 MATCHER_P(RefRange, Range, "") {
   return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(),
                          arg.Location.End.line(), arg.Location.End.column()) ==
          std::make_tuple(Range.start.line, Range.start.character,
std::unique_ptr<RefSlab> refSlab(const SymbolID &ID, const char *Path) {
   RefSlab::Builder Slab;
   Ref R;
   R.Location.FileURI = Path;
   R.Kind = RefKind::Reference;
   Slab.insert(ID, R);
   return std::make_unique<RefSlab>(std::move(Slab).build());
 }
 
+std::unique_ptr<RelationSlab> relSlab(llvm::ArrayRef<const Relation> Rels) {
+  RelationSlab::Builder RelBuilder;
+  for (auto &Rel : Rels)
+    RelBuilder.insert(Rel);
+  return std::make_unique<RelationSlab>(std::move(RelBuilder).build());
+}
+
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty());
 
   FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"), nullptr,
             false);
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
ASSERT_THAT(ShardedIndex.getAllSources(),
     EXPECT_THAT(*Shard->Relations, IsEmpty());
     ASSERT_THAT(Shard->Sources->keys(),
                 UnorderedElementsAre(BSourceUri, BHeaderUri));
     EXPECT_THAT(Shard->Sources->lookup(BSourceUri).DirectIncludes,
                 UnorderedElementsAre(BHeaderUri));
     EXPECT_TRUE(Shard->Cmd.hasValue());
   }
 }
+
+TEST(FileIndexTest, Profile) {
+  FileIndex FI;
+
+  auto FileName = testPath("foo.cpp");
+  auto AST = TestTU::withHeaderCode("int a;").build();
+  FI.updateMain(FileName, AST);
+  FI.updatePreamble(FileName, "v1", AST.getASTContext(),
+                    AST.getPreprocessorPtr(), AST.getCanonicalIncludes());
+
+  llvm::BumpPtrAllocator Alloc;
+  MemoryTree MT(&Alloc);
+  FI.profile(MT);
+  ASSERT_THAT(MT.children(),
+              UnorderedElementsAre(Pair("preamble", _), Pair("main_file", _)));
+
+  ASSERT_THAT(MT.child("preamble").children(),
+              UnorderedElementsAre(Pair("index", _), Pair("symbols", _)));
+  ASSERT_THAT(MT.child("main_file").children(),
+              UnorderedElementsAre(Pair("index", _), Pair("symbols", _)));
+
+  ASSERT_THAT(MT.child("preamble").child("index").total(), Gt(0U));
+  ASSERT_THAT(MT.child("main_file").child("index").total(), Gt(0U));
+}
+
+TEST(FileSymbolsTest, Profile) {
+  FileSymbols FS;
+  FS.update("f1", numSlab(1, 2), nullptr, nullptr, false);
+  FS.update("f2", nullptr, refSlab(SymbolID("1"), "f1"), nullptr, false);
+  FS.update("f3", nullptr, nullptr,
+            relSlab({{SymbolID("1"), RelationKind::BaseOf, SymbolID("2")}}),
+            false);
+  llvm::BumpPtrAllocator Alloc;
+  MemoryTree MT(&Alloc);
+  FS.profile(MT);
+  ASSERT_THAT(MT.children(), UnorderedElementsAre(Pair("f1", _), Pair("f2", _),
+                                                  Pair("f3", _)));
+  EXPECT_THAT(MT.child("f1").children(), ElementsAre(Pair("symbols", _)));
+  EXPECT_THAT(MT.child("f1").total(), Gt(0U));
+  EXPECT_THAT(MT.child("f2").children(), ElementsAre(Pair("references", _)));
+  EXPECT_THAT(MT.child("f2").total(), Gt(0U));
+  EXPECT_THAT(MT.child("f3").children(), ElementsAre(Pair("relations", _)));
+  EXPECT_THAT(MT.child("f3").total(), Gt(0U));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang