[clangd] Fix race in background index rebuild, where index could stay stale.

[sammccall]

Summary

The BackgroundQueue worker that finishes the last task is responsible for
calling OnIdle(). However calling OnIdle itself may be the "last task"
necessitating another call to OnIdle!

Consider:

Main      +T1 +T2            +T3
Worker1      [---T1---]       [---T3---]
Worker2           [---T2---][---Idle1---]

Idle1 starts running before T3 has started, let alone finished.
So it doesn't satisfy the goal that OnIdle runs after other work.

On the other hand, Worker1 won't run OnIdle after T3, as Idle1 is still running.
Therefore Worker2 needs to run OnIdle again (Idle2) once Idle1 completes.
This patch does that.

An example test flake due to this oversight:
http://lab.llvm.org:8011/#/builders/100/builds/721/steps/7/logs/FAIL__Clangd_Unit_Tests__BackgroundIndexTest_Confi

[kadircet]

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

848

s/caute/cause

850

as discussed offline there are no guarantees on these newly pushed tasks finishing before the OnIdle.

[kadircet]

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

850

i suppose we can do something like:

• Count number of times OnIdle has been executed.
• Enqueue 2 more tasks with first OnIdle.
• Assert that OnIdle has run twice ? (once on initial idleness, and once after completing 2 newly introduced tasks)

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

public:
   void push(Task);
   void append(std::vector<Task>);
   // Boost priority of current and new tasks with matching Tag, if they are
   // lower priority.
   // Reducing the boost of a tag affects future tasks but not current ones.
   void boost(llvm::StringRef Tag, unsigned NewPriority);
 
   // Process items on the queue until the queue is stopped.
-  // If the queue becomes empty, OnIdle will be called (on one worker).
+  // Each time the queue becomes empty, OnIdle will be called (on one worker).
   void work(std::function<void()> OnIdle = nullptr);
 
   // Stop processing new tasks, allowing all work() calls to return soon.
   void stop();
 
   // Disables thread priority lowering to ensure progress on loaded systems.
   // Only affects tasks that run after the call.
   static void preventThreadStarvationInTests();

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

if (Task->ThreadPri != llvm::ThreadPriority::Default &&
       llvm::set_thread_priority(Task->ThreadPri);
     Task->Run();
     if (Task->ThreadPri != llvm::ThreadPriority::Default)
       llvm::set_thread_priority(llvm::ThreadPriority::Default);
 
     {
       std::unique_lock<std::mutex> Lock(Mu);
       ++Stat.Completed;
-      if (Stat.Active == 1 && Queue.empty()) {
-        // We just finished the last item, the queue is going idle.
+      // If we just finished the last item, the queue is going idle.
+      // Loop in case more items get scheduled and completed during OnIdle().
+      // (We treat this as going idle a second time).
+      while (Stat.Active == 1 && Queue.empty() &&
+             Stat.LastIdle != Stat.Completed) {
         assert(ShouldStop || Stat.Completed == Stat.Enqueued);
         Stat.LastIdle = Stat.Completed;
         if (OnIdle) {
           Lock.unlock();
           OnIdle();
           Lock.lock();
         }
       }

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

 #include "CompileCommands.h"
 #include "Config.h"
 #include "Headers.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "TestIndex.h"
 #include "TestTU.h"
 #include "index/Background.h"
 #include "index/BackgroundRebuild.h"
+#include "support/Threading.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Threading.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <deque>
 #include <thread>
Sequence.clear();
     BackgroundQueue Q;
     Q.append({A, B});
     Q.boost("A", 3);
     Q.work([&] { Q.stop(); });
     EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
   }
 }
 
+TEST(BackgroundQueueTest, Idle) {
+  std::atomic<unsigned> TaskCount(0), IdleCount(0);
+  BackgroundQueue::Task Task([&] { ++TaskCount; });
+
+  // Set up a queue initially with 10 tasks.
+  AsyncTaskRunner ThreadPool;
+  BackgroundQueue Q;
+  for (unsigned I = 0; I < 10; ++I)
+    Q.push(Task);
+  Notification Start;
+  for (unsigned I = 0; I < 5; ++I)
+    ThreadPool.runAsync("worker", [&] {
+      Start.wait();
+      Q.work(/*OnIdle=*/[&] {
+        // Should be nothing else running now, so this assertion isn't racy.
+        EXPECT_EQ(10u + 2u * IdleCount, TaskCount);
+
+        // The first two times the queue goes idle, add a couple more tasks.
+        // This should caute OnIdle to run again.
+        if (++IdleCount <= 2) {
+          Q.push(Task);
+          Q.push(Task);
+        }
+      });
+    });
+
+  Start.notify();
+  ASSERT_TRUE(Q.blockUntilIdleForTest(/*TimeoutSeconds=*/5));
+  Q.stop();
+  ASSERT_TRUE(ThreadPool.wait(timeoutSeconds(5)));
+
+  EXPECT_EQ(3u, IdleCount)
+      << "Queue exhausts original items, then the extra two (twice)";
+}
+
 TEST(BackgroundQueueTest, Progress) {
   using testing::AnyOf;
   BackgroundQueue::Stats S;
   BackgroundQueue Q([&](BackgroundQueue::Stats New) {
     // Verify values are sane.
     // Items are enqueued one at a time (at least in this test).
     EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
     // Items are completed one at a time.