TaskScheduler: Atomic operations in TaskTracker

base/task_scheduler/task_tracker.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/task_scheduler/task_tracker.h"
 
+#include "base/atomicops.h"
 #include "base/callback.h"
 #include "base/debug/task_annotator.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/threading/sequenced_task_runner_handle.h"
 #include "base/threading/thread_restrictions.h"
 #include "base/threading/thread_task_runner_handle.h"
 #include "base/trace_event/trace_event.h"
 
 namespace base {
 namespace internal {
@@ skipping 12 matching lines @@
 
 void RecordNumBlockShutdownTasksPostedDuringShutdown(
     HistogramBase::Sample value) {
   UMA_HISTOGRAM_CUSTOM_COUNTS(
       "TaskScheduler.BlockShutdownTasksPostedDuringShutdown", value, 1,
       kMaxBlockShutdownTasksPostedDuringShutdown, 50);
 }
 
 }  // namespace
 
-TaskTracker::TaskTracker() = default;
+class TaskTracker::State {
+ public:
+  State() = default;
+
+  // Sets a flag indicating that shutdown has started. Returns true if there are
+  // tasks blocking shutdown. Can only be called once.
+  bool StartShutdown() {
+    const auto new_value =
+        subtle::Barrier_AtomicIncrement(&bits_, kShutdownHasStartedMask);

[gab, 2016/06/20 21:06:51]

NoBarrier?

[robliao, 2016/06/20 21:32:20]

Do we have a sense of how much a barrier slows the code down? If it's not much,
keeping it will certainly make the code more robust.

OTOH, agreed that in the current usage, we can get away without a barrier.

[fdoray, 2016/06/29 18:22:37]

Done. The Barrier is not required here because there is no state other than the
atomic variable that needs to be synchronized with other threads.

+
+    // Check that the "shutdown has started" bit isn't zero. This would happen
+    // if it was incremented twice.
+    DCHECK(new_value & kShutdownHasStartedMask);
+
+    const auto num_tasks_blocking_shutdown =
+        new_value / kNumTasksBlockingShutdownIncrement;
+    return num_tasks_blocking_shutdown != 0;
+  }
+
+  // Returns true if shutdown has started.
+  bool ShutdownHasStarted() const {
+    return subtle::NoBarrier_Load(&bits_) & kShutdownHasStartedMask;
+  }
+
+  // Returns true if there are tasks blocking shutdown.
+  bool TasksAreBlockingShutdown() const {
+    const auto num_tasks_blocking_shutdown =
+        subtle::NoBarrier_Load(&bits_) / kNumTasksBlockingShutdownIncrement;
+    DCHECK_GE(num_tasks_blocking_shutdown, 0);
+    return num_tasks_blocking_shutdown != 0;
+  }
+
+  // Increments the number of tasks blocking shutdown. Returns true if shutdown
+  // has started.
+  bool IncrementNumTasksBlockingShutdown() {
+    const auto new_bits = subtle::NoBarrier_AtomicIncrement(
+        &bits_, kNumTasksBlockingShutdownIncrement);
+
+    // Verify that there is no overflow.
+    const auto num_tasks_blocking_shutdown =

[gab, 2016/06/20 21:06:51]

#if DCHECK_IS_ON()

[fdoray, 2016/06/29 18:22:37]

Done.

+        new_bits / kNumTasksBlockingShutdownIncrement;
+    DCHECK_GE(num_tasks_blocking_shutdown, 0);
+
+    const bool shutdown_has_started = new_bits & kShutdownHasStartedMask;
+    return shutdown_has_started;
+  }
+
+  // Decrements the number of tasks blocking shutdown. Returns true if shutdown
+  // has started and the number of tasks blocking shutdown becomes zero.
+  bool DecrementNumTasksBlockingShutdown() {
+    const auto new_bits = subtle::NoBarrier_AtomicIncrement(
+        &bits_, -kNumTasksBlockingShutdownIncrement);
+    const bool shutdown_has_started = new_bits & kShutdownHasStartedMask;
+    const auto num_tasks_blocking_shutdown =
+        new_bits / kNumTasksBlockingShutdownIncrement;
+    DCHECK_GE(num_tasks_blocking_shutdown, 0);
+    return shutdown_has_started && num_tasks_blocking_shutdown == 0;
+  }
+
+ private:
+  static constexpr subtle::Atomic32 kShutdownHasStartedMask = 1;
+  static constexpr subtle::Atomic32 kNumTasksBlockingShutdownIncrement = 2;

[gab, 2016/06/20 21:06:51]

s/2/1 << kShutdownHasStartedMask/ to make it clearer?

And then above perhaps also:

"new_bits / kNumTasksBlockingShutdownIncrement" => "new_bits >> 
kShutdownHasStartedMask" ?

I prefer shift over division since this is really what it is (reading all bits
but the mask).

[fdoray, 2016/06/29 18:22:37]

Done.

[gab, 2016/06/29 21:38:47]

Actually now that I look at the updated code, shifting by a mask looks wrong
(sorry!). I.e. if the mask was instead say 00001111 we would need to shift by 4
not 15.

I still prefer shifting but shifting by the mask is wrong, The required shift is
really log_2(kShutdownHasStartedMask)+1 but that sounds overcomplicated to
derive an offset in this simple case.

Maybe simply define:

kNumTasksBlockingShutdownBitOffset = 1

and then use it to shift and you can increment by (1 <<
kNumTasksBlockingShutdownBitOffset)?

Up to you.

[fdoray, 2016/07/04 20:53:11]

Done.

+
+  // The LSB indicates whether shutdown has started. The other bits count the
+  // number of tasks blocking shutdown.
+  subtle::Atomic32 bits_ = 0;

[robliao, 2016/06/20 21:32:20]

Comment on the structure of the lack of barriers depends on a single value here.
Adding another atomic variable and reading from it with bits_ means the the
atomic behavior needs to be reassessed. 

[fdoray, 2016/06/29 18:22:37]

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(State);
+};
+
+TaskTracker::TaskTracker() : state_(new State) {}
 TaskTracker::~TaskTracker() = default;
 
 void TaskTracker::Shutdown() {
-  AutoSchedulerLock auto_lock(lock_);
+  {
+    AutoSchedulerLock auto_lock(shutdown_lock_);
 
-  // This method should only be called once.
-  DCHECK(!shutdown_completed_);
-  DCHECK(!shutdown_cv_);
+    // This method can only be called once.
+    DCHECK(!shutdown_event_);
+    DCHECK(!num_block_shutdown_tasks_posted_during_shutdown_);
 
-  shutdown_cv_ = lock_.CreateConditionVariable();
+    shutdown_event_.reset(
+        new WaitableEvent(WaitableEvent::ResetPolicy::MANUAL,
+                          WaitableEvent::InitialState::NOT_SIGNALED));
 
-  // Wait until the number of tasks blocking shutdown is zero.
-  while (num_tasks_blocking_shutdown_ != 0)
-    shutdown_cv_->Wait();
+    const bool tasks_are_blocking_shutdown = state_->StartShutdown();
 
-  shutdown_cv_.reset();
-  shutdown_completed_ = true;
+    // From now, if a thread causes the number of tasks blocking shutdown to
+    // become zero, it will call OnBlockingShutdownTasksComplete().
 
-  // Record the TaskScheduler.BlockShutdownTasksPostedDuringShutdown if less
-  // than |kMaxBlockShutdownTasksPostedDuringShutdown| BLOCK_SHUTDOWN tasks were
-  // posted during shutdown. Otherwise, the histogram has already been recorded
-  // in BeforePostTask().
-  if (num_block_shutdown_tasks_posted_during_shutdown_ <
-      kMaxBlockShutdownTasksPostedDuringShutdown) {
-    RecordNumBlockShutdownTasksPostedDuringShutdown(
-        num_block_shutdown_tasks_posted_during_shutdown_);
+    if (!tasks_are_blocking_shutdown) {
+      shutdown_event_->Signal();
+      return;
+    }
+  }
+
+  // It is safe to access |shutdown_event_| without holding |lock_| because the
+  // pointer never changes after being set above.
+  shutdown_event_->Wait();
+
+  {
+    AutoSchedulerLock auto_lock(shutdown_lock_);
+
+    // Record TaskScheduler.BlockShutdownTasksPostedDuringShutdown if less than
+    // |kMaxBlockShutdownTasksPostedDuringShutdown| BLOCK_SHUTDOWN tasks were
+    // posted during shutdown. Otherwise, the histogram has already been
+    // recorded in BeforePostTask().
+    if (num_block_shutdown_tasks_posted_during_shutdown_ <
+        kMaxBlockShutdownTasksPostedDuringShutdown) {
+      RecordNumBlockShutdownTasksPostedDuringShutdown(
+          num_block_shutdown_tasks_posted_during_shutdown_);
+    }
   }
 }
 
 bool TaskTracker::WillPostTask(const Task* task) {
   DCHECK(task);
 
   if (!BeforePostTask(task->traits.shutdown_behavior()))
     return false;
 
   debug::TaskAnnotator task_annotator;
@@ skipping 33 matching lines @@
 
     TRACE_TASK_EXECUTION(kRunFunctionName, *task);
 
     debug::TaskAnnotator task_annotator;
     task_annotator.RunTask(kQueueFunctionName, *task);
   }
 
   AfterRunTask(shutdown_behavior);
 }
 
+bool TaskTracker::ShutdownCompleted() const {
+  AutoSchedulerLock auto_lock(shutdown_lock_);
+  return shutdown_event_ && shutdown_event_->IsSignaled();
+}
+
 bool TaskTracker::IsShuttingDownForTesting() const {
-  AutoSchedulerLock auto_lock(lock_);
-  return !!shutdown_cv_;
+  AutoSchedulerLock auto_lock(shutdown_lock_);
+  return shutdown_event_ && !shutdown_event_->IsSignaled();
 }
 
 bool TaskTracker::BeforePostTask(TaskShutdownBehavior shutdown_behavior) {
-  AutoSchedulerLock auto_lock(lock_);
-
-  if (shutdown_completed_) {
-    // A BLOCK_SHUTDOWN task posted after shutdown has completed is an ordering
-    // bug. This DCHECK aims to catch those early.
-    DCHECK_NE(shutdown_behavior, TaskShutdownBehavior::BLOCK_SHUTDOWN);
-
-    // No task is allowed to be posted after shutdown.
-    return false;
-  }
-
   if (shutdown_behavior == TaskShutdownBehavior::BLOCK_SHUTDOWN) {
     // BLOCK_SHUTDOWN tasks block shutdown between the moment they are posted
     // and the moment they complete their execution.
-    ++num_tasks_blocking_shutdown_;
+    const bool shutdown_started = state_->IncrementNumTasksBlockingShutdown();
 
-    if (shutdown_cv_) {
+    if (shutdown_started) {
+      AutoSchedulerLock auto_lock(shutdown_lock_);
+
+      // A BLOCK_SHUTDOWN task posted after shutdown has completed is an
+      // ordering bug. This aims to catch those early.
+      DCHECK(shutdown_event_);
+      DCHECK(!shutdown_event_->IsSignaled());
+
       ++num_block_shutdown_tasks_posted_during_shutdown_;
 
       if (num_block_shutdown_tasks_posted_during_shutdown_ ==
           kMaxBlockShutdownTasksPostedDuringShutdown) {
         // Record the TaskScheduler.BlockShutdownTasksPostedDuringShutdown
         // histogram as soon as its upper bound is hit. That way, a value will
         // be recorded even if an infinite number of BLOCK_SHUTDOWN tasks are
         // posted, preventing shutdown to complete.
         RecordNumBlockShutdownTasksPostedDuringShutdown(
             num_block_shutdown_tasks_posted_during_shutdown_);
       }
     }
 
-    // A BLOCK_SHUTDOWN task is allowed to be posted iff shutdown hasn't
-    // completed.
     return true;
   }
 
   // A non BLOCK_SHUTDOWN task is allowed to be posted iff shutdown hasn't
   // started.
-  return !shutdown_cv_;
+  return !state_->ShutdownHasStarted();
 }
 
 bool TaskTracker::BeforeRunTask(TaskShutdownBehavior shutdown_behavior) {
-  AutoSchedulerLock auto_lock(lock_);
+  switch (shutdown_behavior) {
+    case TaskShutdownBehavior::BLOCK_SHUTDOWN: {
+      // The number of tasks blocking shutdown has been incremented when the
+      // task was posted.
+      DCHECK(state_->TasksAreBlockingShutdown());
 
-  if (shutdown_completed_) {
-    // Trying to run a BLOCK_SHUTDOWN task after shutdown has completed is
-    // unexpected as it either shouldn't have been posted if shutdown completed
-    // or should be blocking shutdown if it was posted before it did.
-    DCHECK_NE(shutdown_behavior, TaskShutdownBehavior::BLOCK_SHUTDOWN);
+      // Trying to run a BLOCK_SHUTDOWN task after shutdown has completed is
+      // unexpected as it either shouldn't have been posted if shutdown
+      // completed or should be blocking shutdown if it was posted before it
+      // did.
+      DCHECK(!state_->ShutdownHasStarted() || !ShutdownCompleted());
 
-    // A WorkerThread might extract a non BLOCK_SHUTDOWN task from a
-    // PriorityQueue after shutdown. It shouldn't be allowed to run it.
-    return false;
-  }
+      return true;
+    }
 
-  switch (shutdown_behavior) {
-    case TaskShutdownBehavior::BLOCK_SHUTDOWN:
-      DCHECK_GT(num_tasks_blocking_shutdown_, 0U);
+    case TaskShutdownBehavior::SKIP_ON_SHUTDOWN: {
+      // SKIP_ON_SHUTDOWN tasks block shutdown while they are running.
+      const bool shutdown_started = state_->IncrementNumTasksBlockingShutdown();
+
+      if (shutdown_started) {
+        // The SKIP_ON_SHUTDOWN task isn't allowed to run during shutdown.
+        // Decrement the number of tasks blocking shutdown that was wrongly
+        // incremented.
+        const bool shutdown_started_and_no_tasks_block_shutdown =
+            state_->DecrementNumTasksBlockingShutdown();
+        if (shutdown_started_and_no_tasks_block_shutdown)
+          OnBlockingShutdownTasksComplete();
+
+        return false;
+      }
+
       return true;
+    }
 
-    case TaskShutdownBehavior::SKIP_ON_SHUTDOWN:
-      if (shutdown_cv_)
-        return false;
-
-      // SKIP_ON_SHUTDOWN tasks block shutdown while they are running.
-      ++num_tasks_blocking_shutdown_;
-      return true;
-
-    case TaskShutdownBehavior::CONTINUE_ON_SHUTDOWN:
-      return !shutdown_cv_;
+    case TaskShutdownBehavior::CONTINUE_ON_SHUTDOWN: {
+      return !state_->ShutdownHasStarted();
+    }
   }
 
   NOTREACHED();
   return false;
 }
 
 void TaskTracker::AfterRunTask(TaskShutdownBehavior shutdown_behavior) {
   if (shutdown_behavior == TaskShutdownBehavior::BLOCK_SHUTDOWN ||
       shutdown_behavior == TaskShutdownBehavior::SKIP_ON_SHUTDOWN) {
-    AutoSchedulerLock auto_lock(lock_);
-    DCHECK_GT(num_tasks_blocking_shutdown_, 0U);
-    --num_tasks_blocking_shutdown_;
-    if (num_tasks_blocking_shutdown_ == 0 && shutdown_cv_)
-      shutdown_cv_->Signal();
+    const bool shutdown_started_and_no_tasks_block_shutdown =
+        state_->DecrementNumTasksBlockingShutdown();
+    if (shutdown_started_and_no_tasks_block_shutdown)
+      OnBlockingShutdownTasksComplete();
   }
 }
 
+void TaskTracker::OnBlockingShutdownTasksComplete() {
+  AutoSchedulerLock auto_lock(shutdown_lock_);
+
+  // This method can only be called after shutdown has started.
+  DCHECK(state_->ShutdownHasStarted());
+  DCHECK(shutdown_event_);
+
+  shutdown_event_->Signal();
+}
+
 }  // namespace internal
 }  // namespace base