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..36d920d0caeee3a1fa6128b3ff186439ad078a1b
--- /dev/null
+++ b/base/task_scheduler/scheduler_lock_impl.cc
@@ -0,0 +1,150 @@
+// 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/lazy_instance.h"
+#include "base/logging.h"
+#include "base/synchronization/condition_variable.h"
+#include "base/threading/platform_thread.h"
+#include "base/threading/thread_local.h"
+
+namespace base {
+namespace internal {
+
+namespace {
+
+class SafeAcquisitionTracker {
+ public:
+  SafeAcquisitionTracker() = default;
+
+  void RegisterLock(
+      const SchedulerLockImpl* const lock,
+      const SchedulerLockImpl* const predecessor) {
+    // Reentrant locks are unsupported.
+    DCHECK(lock != predecessor);
+    AutoLock auto_lock(metadata_lock_);
+    allowed_predecessor_map_[lock] = predecessor;
+    AssertSafePredecessor(lock);
+  }
+
+  void UnregisterLock(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);
+    allowed_predecessor_map_.erase(lock);
+  }
+
+  void RecordAcquisition(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);

[gab, 2016/02/22 16:54:12]

Move AutoLock into AssertSafeAcquire (on the line where there is an
AssertAcquired()).

[robliao, 2016/02/22 18:38:09]

Done.

+    const PlatformThreadId id = PlatformThread::CurrentId();
+    AssertSafeAcquire(id, lock);
+    if (!tls_acquired_locks_.Get())
+      tls_acquired_locks_.Set(new LockVector);
+
+    tls_acquired_locks_.Get()->push_back(lock);
+  }
+
+  void RecordRelease(const SchedulerLockImpl* const lock) {
+    AutoLock auto_lock(metadata_lock_);

[gab, 2016/02/22 16:54:12]

No need to lock, right?

[robliao, 2016/02/22 18:38:09]

Indeed. It's all TLS only. Removed.

+    LockVector* acquired_locks = tls_acquired_locks_.Get();

[gab, 2016/02/22 16:54:12]

DCHECK(acquired_locks);

[robliao, 2016/02/22 18:38:09]

DCHECK isn't necessary here as we'll simply crash on the next line.

[gab, 2016/02/22 19:56:47]

Right but DCHECK explicitly documents expectations whereas crash is unexpected.
Hence I strongly prefer DCHECK here.

[robliao, 2016/02/22 20:22:51]

I used to be on the DCHECK pointers side as well until someone pointed out to me
in a CR that a DCHECK right before a pointer dereference doesn't really add
value to the code.

By immediately dereferencing the pointer after you get it, you already document
that you expect this pointer to be good. The DCHECK isn't adding any value
because on DCHECK_IS_ON builds, once you assert, you immediately crash on the
next line after you continue the DCHECK. On Release builds, you simply crash.
The DCHECK then becomes an unnecessarily line.

A DCHECK of a pointer provides value in cases when the pointer isn't immediately
dereferenced  but is dereferenced outside of the containing function.
Constructors that accept pointers for later use are excellent places for a
DCHECK of a pointer.

[gab, 2016/02/22 20:36:31]

To me it acts as explicit documentation whereas immediate deref is implicit
documentation (i.e. could be a developer/reviewer inattention whereas DCHECK
can't be accidental).

If the DCHECK hits, the developer immediately knows it's wrong. If it crashes on
deref, the developer has to read the rest of the code to figure out whether this
should never be the case.

tl;dr; to me a DCHECK is documentation that says "we're now going to deref right
away because this should never be null per the impl" without the reader having
to wonder whether that's true.

[robliao, 2016/02/22 21:21:02]

Discussed offline and rendered moot with the allowance for empty vectors.

+    const auto iter_at_lock =
+        std::find(acquired_locks->begin(), acquired_locks->end(), lock);
+    DCHECK(iter_at_lock != acquired_locks->end());
+    acquired_locks->erase(iter_at_lock);
+    if (acquired_locks->empty()) {
+      tls_acquired_locks_.Set(nullptr);
+      delete acquired_locks;

[gab, 2016/02/22 16:54:12]

Assuming this thread remains active, it will soon grab another lock so instead
of causing churn by deleting and re-allocating the LockVector. How about we
instead only clear it in ~SchedulerLockImp(), i.e. when the WorkerThread is
terminated.

[robliao, 2016/02/22 18:38:09]

The destruction of a lock does not necessarily correspond to an opportunity to
clean up the single thread local state because a lock may be acquired on
multiple threads. We would need to clean up the vectors for those other threads
as well.

We could create a map to hold all of these extra vectors and then verify that
the threads are alive before destroying the vector, but then we're back to a non
TLSed map.

What we really want is to destroy the vector on the destruction of a real thread
since that's where the TLS lives. We could modify ThreadLocalPointer to forward
on a destructor call to do this on our behalf if that sounds appropriate to you.

Alternatively, we can see if this alloc/free really causes a performance issue,
and if it does, then we perform the ThreadLocalPointer change.

[gab, 2016/02/22 19:56:47]

Duh of course, I did mean on destruction of thread but then somehow thought very
incorrectly that we could rely on lock destruction instead of introducing a
notification (clearly this makes no sense so not sure why I thought that!).

How about a static SchedulerLock::OnThreadDestruction()?

I'd rather not wait until we measure the impact, this feels suddle and hard to
measure but we have an easy way to make it better. WDYT?

[robliao, 2016/02/22 20:22:51]

The right way to do this is to introduce the destructor that already runs with
the TLS slot. I'll go ahead and add that in.

[robliao, 2016/02/22 20:37:34]

Looks like I incorrectly assumed that this API was using the ThreadLocalStorage
API, but it turns out this API was supposed to supersede that API, but it looks
like it was never removed!

https://chromium.googlesource.com/chromium/src/+/83a05ddf63cc5920ad04b0a6936f...

This will require a bit more cleanup than I expected.

+    }
+  }
+
+ private:
+  using LockVector = std::vector<const SchedulerLockImpl*>;
+  using PredecessorMap = std::unordered_map<
+      const SchedulerLockImpl*, const SchedulerLockImpl*>;
+  using AcquisitionMap =

[gab, 2016/02/22 16:54:12]

rm unused type

[robliao, 2016/02/22 18:38:09]

Done.

+      std::unordered_map<base::PlatformThreadId, LockVector>;

[fdoray, 2016/02/22 16:45:21]

not used anymore

[robliao, 2016/02/22 18:38:09]

Done.

+
+  // This asserts that the lock is safe to acquire. This means that this should
+  // be run before actually recording the acquisition.
+  void AssertSafeAcquire(PlatformThreadId id,
+                         const SchedulerLockImpl* const lock) const {
+    const LockVector* acquired_locks = GetThreadAcquiredLocks();
+
+    // If the thread currently holds no locks, this is inherently safe.
+    if (!acquired_locks)
+      return;
+
+    // We're getting ready to look at the allowed_predecessor_map_.

[gab, 2016/02/22 16:54:12]

When the line below is changed to an AutoLock as suggested above and the lock
renamed to be predecessor specific, I don't think a comment will be required
here as it will be implicit.

[robliao, 2016/02/22 18:38:09]

Done.

+    metadata_lock_.AssertAcquired();
+
+    // Otherwise, make sure that the previous lock acquired is an allowed
+    // predecessor.
+    const SchedulerLockImpl* allowed_predecessor =
+        allowed_predecessor_map_.at(lock);
+    DCHECK(acquired_locks->back() == allowed_predecessor);
+  }
+
+  void AssertSafePredecessor(const SchedulerLockImpl* lock) const {
+    metadata_lock_.AssertAcquired();
+    for (const SchedulerLockImpl* predecessor =
+             allowed_predecessor_map_.at(lock);
+         predecessor != nullptr;
+         predecessor = allowed_predecessor_map_.at(predecessor)) {
+      if (predecessor == lock)
+        NOTREACHED();
+    }
+  }
+
+  const LockVector* GetThreadAcquiredLocks() const {
+    // ThreadLocalPointer.Get() has no const version.
+    return const_cast<SafeAcquisitionTracker*>(this)->tls_acquired_locks_.Get();

[gab, 2016/02/22 16:54:12]

I'd prefer to inline this at single call site, otherwise there is an extra
indirection for the reader for a one-liner.

[robliao, 2016/02/22 18:38:09]

Done.

+  }
+
+  // Synchronizes everything in SafeAcquisitionTracker.
+  Lock metadata_lock_;

[gab, 2016/02/22 16:54:12]

// Synchronized access to |allowed_predecessor_map_|.
Lock allowed_predecessor_lock_;

// A map of allowed SchedulerLockImpl predecessors.
PredecessorMap allowed_predecessor_map_;

// A thread-local vector of currently acquired locks.
ThreadLocalPointer<LockVector> tls_acquired_locks_;


(i.e. rename the lock + suggestion for comments)

[robliao, 2016/02/22 18:38:09]

Done.

+
+  PredecessorMap allowed_predecessor_map_;
+  ThreadLocalPointer<LockVector> tls_acquired_locks_;
+
+  DISALLOW_COPY_AND_ASSIGN(SafeAcquisitionTracker);
+};
+
+LazyInstance<SafeAcquisitionTracker>::Leaky g_safe_acquisition_tracker =
+    LAZY_INSTANCE_INITIALIZER;
+
+}  // namespace
+
+SchedulerLockImpl::SchedulerLockImpl() : SchedulerLockImpl(nullptr) {}
+
+SchedulerLockImpl::SchedulerLockImpl(const SchedulerLockImpl* predecessor) {
+  g_safe_acquisition_tracker.Get().RegisterLock(this, predecessor);
+}
+
+SchedulerLockImpl::~SchedulerLockImpl() {
+  g_safe_acquisition_tracker.Get().UnregisterLock(this);
+}
+
+void SchedulerLockImpl::Acquire() {
+  lock_.Acquire();
+  g_safe_acquisition_tracker.Get().RecordAcquisition(this);
+}
+
+void SchedulerLockImpl::Release() {
+  lock_.Release();
+  g_safe_acquisition_tracker.Get().RecordRelease(this);
+}
+
+void SchedulerLockImpl::AssertAcquired() const {
+  lock_.AssertAcquired();
+}
+
+scoped_ptr<ConditionVariable> SchedulerLockImpl::CreateConditionVariable() {
+  return scoped_ptr<ConditionVariable>(new ConditionVariable(&lock_));
+}
+
+}  // namespace internal
+}  // base