TaskScheduler [4/9] Priority Queue

base/task_scheduler/priority_queue.cc

Index: base/task_scheduler/priority_queue.cc
diff --git a/base/task_scheduler/priority_queue.cc b/base/task_scheduler/priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..25326c07966947917c82002c3660b29304c1516b
--- /dev/null
+++ b/base/task_scheduler/priority_queue.cc
@@ -0,0 +1,100 @@
+// 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/priority_queue.h"
+
+#include <utility>
+
+#include "base/logging.h"
+
+namespace base {
+namespace internal {
+
+PriorityQueue::SequenceAndSortKey::SequenceAndSortKey(
+    scoped_refptr<Sequence> sequence,
+    SequenceSortKey sort_key)
+    : sequence(sequence), sort_key(sort_key) {}
+
+PriorityQueue::SequenceAndSortKey::~SequenceAndSortKey() = default;
+
+PriorityQueue::SequenceAndSortKey PriorityQueue::SequenceAndSortKey::Null() {
+  return SequenceAndSortKey(scoped_refptr<Sequence>(),
+                            SequenceSortKey(TaskPriority::LOWEST, TimeTicks()));
+}
+
+bool PriorityQueue::SequenceAndSortKey::is_null() const {
+  return sequence.get() == nullptr;
+}
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback)
+    : sequence_inserted_callback_(sequence_inserted_callback) {
+  DCHECK(!sequence_inserted_callback_.is_null());
+}
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback,
+                             PriorityQueue* predecessor_priority_queue)
+    : lock_(&predecessor_priority_queue->lock_),
+      sequence_inserted_callback_(sequence_inserted_callback) {
+  DCHECK(!sequence_inserted_callback_.is_null());
+  DCHECK(predecessor_priority_queue);

[robliao, 2016/02/23 21:00:35]

Remove DCHECK(predecessory_priorit_queue) since we'll crash before this line
(initializer list).

[fdoray, 2016/02/24 15:03:53]

On my machine, there is no crash when the address of
predecessor_priority_queue->lock_ is taken with predecessor_priority_queue_ ==
nullptr. The DCHECK is useful to guarantee a crash.

[gab, 2016/02/24 18:07:38]

Interesting, @ Rob maybe this goes to show that explicit DCHECKs are good to
have even when a deref implicitly documents expectation of pointer being
non-null (ref. discussion on other CL).

DCHECK will always fire, but perhaps deref may not based on some weird compiler
optimizations I don't understand?

[fdoray, 2016/02/24 18:18:42]

explanation from etienneb@: It doesn't crash because the pointer isn't
dereferenced. We take the address of predecessor_priority_queue->lock_ but we
don't try to read its value.

[robliao, 2016/02/24 18:46:33]

This sounds wrong to me. We are dereferencing the predecessor_priority_queue on
a nullptr. That should immediately cause a crash, since 
predecessor_priority_queue->lock_ = (*predecessor_priority_queue)->lock

For example, this results in an immediate access violation for me:

int main(int argc, char* argv[]) {
  class A {
   public:
    A() : value_(42) {}
    A(int placeholder, A* outer) : value_(outer->value_) {}
   
   private:
    int value_;
  };

  A instance1;
  A instance2(0, &instance1);
  A instance3(0, nullptr); <----- AV on this line
}

Do you have exceptions suppressed on your machine by any chance?

[robliao, 2016/02/24 20:04:52]

Alright. Looks like I get to stand corrected here :-) and learned something new.
tl;dr - Because of some subtle dereferencing rules, the DCHECK stands.

New snippet!

class Copyable {
 public:
  Copyable() = default;
  Copyable(const Copyable* other) {}
  void Print() {}
};

class A {
 public:
  A() = default;
  A(int placeholder, A* outer) : copyable_(&outer->copyable_) {
outer->copyable_.Print(); }
  A(float placeholder, A* outer) : pointer_(outer->pointer_) {}
  
 private:
  Copyable copyable_;
  Copyable* pointer_;
};


int main(int argc, char* argv[]) {
  A instance3(0, nullptr);
  A instance4(0.0f, nullptr);  
}

So why doesn't instance3 crash? Turns out, MSVC treats &outer->copyable_ as well
as outer->copyable_.Print() as a whole when it's a class and does not generate a
dereference of |outer| to get the value. Instead, it jumps straight to the
location regardless of the base address:

mov     eax,dword ptr [ebp+0Ch]      eax = other = 0 
mov     ecx,dword ptr [ebp-8]        ecx = this = instance3's Copyable
call    Sandbox!Copyable::Copyable 
mov     ecx,dword ptr [ebp+0Ch]      ecx = this = 0
call    Sandbox!Copyable::Print

However, if we have a piece of plain old data, then we run into trouble like in
instance4 as it generates

mov     ecx,dword ptr [ebp+0Ch]      <-- Code Example, ecx = 0
mov     edx,dword ptr [ecx+4]        <-- Dereferencing 4 to get the pointer
value

For the code in question, SchedulerLock never dereferences the predecessor lock,
so that's why we continue without a crash.

+}
+
+PriorityQueue::~PriorityQueue() = default;
+
+PriorityQueue::Transaction::~Transaction() {
+  DCHECK(CalledOnValidThread());
+
+  // Release the PriorityQueue's lock before running the sequence insertion
+  // callback to avoid holding multiple locks at the same time.

[gab, 2016/02/23 20:58:42]

s/to avoid holding multiple locks at the same time/to avoid imposing an
unnecessary lock dependency on |sequence_inserted_callback_|'s destination/

(i.e. this component's comment shouldn't assume anything about where this
callback lands in practice today)

[fdoray, 2016/02/24 15:03:53]

I did what you suggest in your next comment instead.

+  auto_lock_.reset();
+
+  // Run the sequence insertion callback once for each sequence that was
+  // inserted in the PriorityQueue during the lifetime of this Transaction.

[gab, 2016/02/23 20:58:42]

Actually I'd say append [1] to this comment and fold |auto_lock_.reset()| below
as it really goes together.

[1] "Perform this outside the scope of PriorityQueue's lock to avoid imposing an
unnecessary lock dependency on |sequence_inserted_callback_|'s destination."

[fdoray, 2016/02/24 15:03:53]

Done.

+  for (size_t i = 0; i < num_pushed_sequences_; ++i)
+    outer_->sequence_inserted_callback_.Run();
+}
+
+void PriorityQueue::Transaction::Push(
+    scoped_ptr<SequenceAndSortKey> sequence_and_sort_key) {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!sequence_and_sort_key->is_null());
+
+  outer_->container_.push(std::move(sequence_and_sort_key));
+  ++num_pushed_sequences_;
+}
+
+PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const {
+  DCHECK(CalledOnValidThread());
+
+  if (outer_->container_.empty())
+    return SequenceAndSortKey::Null();
+
+  return *outer_->container_.top();
+}
+
+void PriorityQueue::Transaction::Pop() {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!outer_->container_.empty());
+  outer_->container_.pop();
+}
+
+PriorityQueue::Transaction::Transaction(PriorityQueue* outer)
+    : outer_(outer),
+      auto_lock_(new AutoSchedulerLock(outer_->lock_)),
+      num_pushed_sequences_(0) {
+  DCHECK(CalledOnValidThread());
+}
+
+scoped_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() {
+  return make_scoped_ptr(new Transaction(this));
+}
+
+bool PriorityQueue::SequenceAndSortKeyComparator::operator()(
+    const scoped_ptr<SequenceAndSortKey>& left,
+    const scoped_ptr<SequenceAndSortKey>& right) const {
+  return left->sort_key < right->sort_key;
+}
+
+}  // namespace internal
+}  // namespace base