TaskScheduler [2/9] Scheduler Lock

base/task_scheduler/scheduler_lock_impl.cc

Index: base/task_scheduler/scheduler_lock_impl.cc
diff --git a/base/task_scheduler/scheduler_lock_impl.cc b/base/task_scheduler/scheduler_lock_impl.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c8580945ddf0a24d9bc2509a144d4d1f7f680dac
--- /dev/null
+++ b/base/task_scheduler/scheduler_lock_impl.cc
@@ -0,0 +1,132 @@
+// 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/scheduler_lock_impl.h"
+
+#include <algorithm>
+#include <unordered_map>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/memory/singleton.h"
+#include "base/synchronization/condition_variable.h"
+#include "base/threading/platform_thread.h"
+
+namespace base {
+namespace internal {
+
+namespace {
+
+class SafeAcquisitionTracker {
+ public:
+  static SafeAcquisitionTracker* GetInstance() {
+    return base::Singleton<SafeAcquisitionTracker>::get();

[gab, 2016/02/18 16:58:06]

Instead of a Singleton, can we use a LazyInstance::Leaky?

e.g. below this class definition add:

LazyInstance<SafeAcquisitionTracker>::Leaky safe_acquisition_tracker = 
    LAZY_INSTANCE_INITIALIZER;

One of the major differences is that base::Singleton is a global registration --
although no one else could get it per not having a the SafeAcquisitionTracker
type definition -- whereas LazyInstance keeps everything local for real. Plus
Singleton is generally frowned upon in and not necessary here I think.

[robliao, 2016/02/18 21:59:37]

Works for me. Done.

+  }
+
+  void RegisterLock(
+      const SchedulerLockImpl* const lock,
+      const SchedulerLockImpl* const predecessor) {
+    // Reentrant locks are unexpected.

[gab, 2016/02/18 16:58:06]

s/unexpected/unsupported/

[robliao, 2016/02/18 21:59:37]

Done.

+    CHECK(lock != predecessor);

[gab, 2016/02/18 16:58:06]

DCHECK 

(equivalent since this code ever runs in DCHECK-enabled mode but avoids giving a
sense to the reader that it does run in non-DCHECK-mode)

[robliao, 2016/02/18 21:59:37]

Done.

+    AutoLock auto_lock(metadata_lock_);
+    allowed_predecessors_[lock] = predecessor;
+    AssertSafePredecessor(lock);
+  }
+
+  void UnregisterLock(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);
+    allowed_predecessors_.erase(lock);
+  }
+
+  void RecordAcquisition(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);
+    const PlatformThreadId id = PlatformThread::CurrentId();
+    AssertSafeAcquire(id, lock);
+    LockVector& thread_locks = acquired_locks_[id];
+    thread_locks.push_back(lock);

[gab, 2016/02/18 16:58:06]

Merge above two lines into:

acquired_locks_[id].push_back(lock);

?

I guess with the two lines it's more explicit and closer to RecordRelease().
Given that, I'm okay either way, WDYT?

[robliao, 2016/02/18 21:59:37]

Symmetry is nice, but it's still the same code. Merged.

+  }
+
+  void RecordRelease(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);
+    const PlatformThreadId id = PlatformThread::CurrentId();
+    LockVector& thread_locks = acquired_locks_[id];
+    const auto iter =
+        std::find(thread_locks.begin(), thread_locks.end(), lock);
+    DCHECK(iter != thread_locks.end());
+    thread_locks.erase(iter);
+  }
+
+ private:
+  friend struct base::DefaultSingletonTraits<SafeAcquisitionTracker>;
+  using LockVector = std::vector<const SchedulerLockImpl*>;
+  using PredecessorMap = std::unordered_map<
+      const SchedulerLockImpl*, const SchedulerLockImpl*>;
+  using AcquisitionMap =
+      std::unordered_map<base::PlatformThreadId, LockVector>;

[gab, 2016/02/18 16:58:06]

How about using ThreadLocalStorage here instead of a map with a PlatformThreadId
as key? Would that allow less |metadata_lock_| locking in this class?

[robliao, 2016/02/18 21:59:37]

We would only be able to save on the release. Acquisitions still need to check
the allowed_predecessor_map.

I'm not sure how much this buys us for an extra gotcha in the class. Releases
should run fairly quickly. acquired locks lookups should be O(1) and the number
of locks held by a thread should be very small.

[gab, 2016/02/19 16:08:02]

To avoid this being a "gotcha -- only lock here not there" we could make the
lock specific to the allowed_predecessor_map. It just feels to me
ThreadLocalStorage is meant for exactly this (thread specific state) and that
using a thread-safe map for which every thread only accesses its own entry is
wrong.

[gab, 2016/02/19 22:05:24]

ping ^^

[robliao, 2016/02/19 23:51:11]

Oops. Missed this one. Done.

+
+  SafeAcquisitionTracker() = default;
+
+  void AssertSafeAcquire(PlatformThreadId id,

[gab, 2016/02/18 16:58:06]

Add a comment + mention that this must be called before |lock| is registered in
|acquired_locks_|.

(or just inline this in RecordAcquisition since it's its only caller)

[robliao, 2016/02/18 21:59:37]

This keeps both RecordAcquisition and RecordRelease as booking. Added the
comment.

+                         const SchedulerLockImpl* const lock) {
+    metadata_lock_.AssertAcquired();
+    const LockVector& thread_locks = acquired_locks_[id];
+
+    // If the thread hasn't ever acquired a lock, this is inherently safe.

[gab, 2016/02/18 16:58:06]

// If the thread doesn't currently own a lock, this is inherently safe.

(i.e. "hasn't ever" is pushing it, it could have held some in the past)

[robliao, 2016/02/18 21:59:37]

Fixed.

+    if (thread_locks.empty())
+      return;
+
+    // Otherwise, make sure that the previous lock acquired is an allowed
+    // predecessor.
+    const SchedulerLockImpl* allowed_predecessor =
+        allowed_predecessors_[lock];
+    DCHECK(thread_locks.back() == allowed_predecessor);
+  }
+
+  void AssertSafePredecessor(const SchedulerLockImpl* lock) {
+    metadata_lock_.AssertAcquired();
+    for (const SchedulerLockImpl* predecessor = allowed_predecessors_[lock];
+         predecessor != nullptr;
+         predecessor = allowed_predecessors_[predecessor]) {
+      if (predecessor == lock)
+        NOTREACHED();

[gab, 2016/02/18 16:58:06]

So is this method only verifying that we do not get a bidirectional
registration? If so this is impossible per the registration happening at
construction time.

So I think it's safe to remove this method and instead specify this in the API
meta comment as already mentioned above.

[robliao, 2016/02/18 21:59:37]

There's actually a unit test for this :-). It is indeed possible.

+    }
+  }
+
+  // Synchronizes everything in SafeAcquisitionTracker.
+  base::Lock metadata_lock_;
+
+  PredecessorMap allowed_predecessors_;

[gab, 2016/02/18 16:58:07]

Whenever I saw this in code the plural form made me think that each lock had
multiple predecessors instead of this being a map of multiple one-off
predecessor registrations.

How about |allowed_predecessor_map| or |predecessor_registrations|?

[robliao, 2016/02/18 21:59:37]

Went with allowed_predecessor_map.

+  AcquisitionMap acquired_locks_;
+
+  DISALLOW_COPY_AND_ASSIGN(SafeAcquisitionTracker);
+};
+
+}  // namespace
+
+SchedulerLockImpl::SchedulerLockImpl() : SchedulerLockImpl(nullptr) {}

[gab, 2016/02/18 16:58:06]

Seems this will call RegisterLock with a nullptr predecessor, should that method
check for nullptr or do you think it's not a big deal to register a null
predecessor regardless?

[robliao, 2016/02/18 21:59:37]

In invariant here is that all locks are registered with a predecessor, allowing
us to form a predecessor chain. nullptr forms a nice end to the chain.

+
+SchedulerLockImpl::SchedulerLockImpl(const SchedulerLockImpl* predecessor) {
+  SafeAcquisitionTracker::GetInstance()->RegisterLock(this, predecessor);
+}
+
+SchedulerLockImpl::~SchedulerLockImpl() {
+  SafeAcquisitionTracker::GetInstance()->UnregisterLock(this);
+}
+
+void SchedulerLockImpl::Acquire() {
+  lock_.Acquire();
+  SafeAcquisitionTracker::GetInstance()->RecordAcquisition(this);
+}
+
+void SchedulerLockImpl::Release() {
+  lock_.Release();
+  SafeAcquisitionTracker::GetInstance()->RecordRelease(this);
+}
+
+scoped_ptr<ConditionVariable> SchedulerLockImpl::CreateConditionVariable() {
+  return scoped_ptr<ConditionVariable>(new ConditionVariable(&lock_));
+}
+
+}  // namespace internal
+}  // base