1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/task_scheduler/priority_queue.h"
6
7 #include <memory>
8
9 #include "base/bind.h"
10 #include "base/bind_helpers.h"
11 #include "base/macros.h"
12 #include "base/memory/ptr_util.h"
13 #include "base/memory/ref_counted.h"
14 #include "base/synchronization/waitable_event.h"
15 #include "base/task_scheduler/sequence.h"
16 #include "base/task_scheduler/task.h"
17 #include "base/task_scheduler/task_traits.h"
18 #include "base/test/gtest_util.h"
19 #include "base/threading/platform_thread.h"
20 #include "base/threading/simple_thread.h"
21 #include "base/time/time.h"
22 #include "testing/gtest/include/gtest/gtest.h"
23
24 namespace base {
25 namespace internal {
26
27 namespace {
28
29 class ThreadBeginningTransaction : public SimpleThread {
30 public:
ThreadBeginningTransaction(PriorityQueue * priority_queue)31 explicit ThreadBeginningTransaction(PriorityQueue* priority_queue)
32 : SimpleThread("ThreadBeginningTransaction"),
33 priority_queue_(priority_queue) {}
34
35 // SimpleThread:
Run()36 void Run() override {
37 std::unique_ptr<PriorityQueue::Transaction> transaction =
38 priority_queue_->BeginTransaction();
39 transaction_began_.Signal();
40 }
41
ExpectTransactionDoesNotBegin()42 void ExpectTransactionDoesNotBegin() {
43 // After a few milliseconds, the call to BeginTransaction() should not have
44 // returned.
45 EXPECT_FALSE(
46 transaction_began_.TimedWait(TimeDelta::FromMilliseconds(250)));
47 }
48
49 private:
50 PriorityQueue* const priority_queue_;
51 WaitableEvent transaction_began_;
52
53 DISALLOW_COPY_AND_ASSIGN(ThreadBeginningTransaction);
54 };
55
56 } // namespace
57
TEST(TaskSchedulerPriorityQueueTest,PushPopPeek)58 TEST(TaskSchedulerPriorityQueueTest, PushPopPeek) {
59 // Create test sequences.
60 scoped_refptr<Sequence> sequence_a(new Sequence);
61 sequence_a->PushTask(Task(FROM_HERE, DoNothing(),
62 TaskTraits(TaskPriority::USER_VISIBLE),
63 TimeDelta()));
64 SequenceSortKey sort_key_a = sequence_a->GetSortKey();
65
66 scoped_refptr<Sequence> sequence_b(new Sequence);
67 sequence_b->PushTask(Task(FROM_HERE, DoNothing(),
68 TaskTraits(TaskPriority::USER_BLOCKING),
69 TimeDelta()));
70 SequenceSortKey sort_key_b = sequence_b->GetSortKey();
71
72 scoped_refptr<Sequence> sequence_c(new Sequence);
73 sequence_c->PushTask(Task(FROM_HERE, DoNothing(),
74 TaskTraits(TaskPriority::USER_BLOCKING),
75 TimeDelta()));
76 SequenceSortKey sort_key_c = sequence_c->GetSortKey();
77
78 scoped_refptr<Sequence> sequence_d(new Sequence);
79 sequence_d->PushTask(Task(FROM_HERE, DoNothing(),
80 TaskTraits(TaskPriority::BACKGROUND), TimeDelta()));
81 SequenceSortKey sort_key_d = sequence_d->GetSortKey();
82
83 // Create a PriorityQueue and a Transaction.
84 PriorityQueue pq;
85 auto transaction(pq.BeginTransaction());
86 EXPECT_TRUE(transaction->IsEmpty());
87
88 // Push |sequence_a| in the PriorityQueue. It becomes the sequence with the
89 // highest priority.
90 transaction->Push(sequence_a, sort_key_a);
91 EXPECT_EQ(sort_key_a, transaction->PeekSortKey());
92
93 // Push |sequence_b| in the PriorityQueue. It becomes the sequence with the
94 // highest priority.
95 transaction->Push(sequence_b, sort_key_b);
96 EXPECT_EQ(sort_key_b, transaction->PeekSortKey());
97
98 // Push |sequence_c| in the PriorityQueue. |sequence_b| is still the sequence
99 // with the highest priority.
100 transaction->Push(sequence_c, sort_key_c);
101 EXPECT_EQ(sort_key_b, transaction->PeekSortKey());
102
103 // Push |sequence_d| in the PriorityQueue. |sequence_b| is still the sequence
104 // with the highest priority.
105 transaction->Push(sequence_d, sort_key_d);
106 EXPECT_EQ(sort_key_b, transaction->PeekSortKey());
107
108 // Pop |sequence_b| from the PriorityQueue. |sequence_c| becomes the sequence
109 // with the highest priority.
110 EXPECT_EQ(sequence_b, transaction->PopSequence());
111 EXPECT_EQ(sort_key_c, transaction->PeekSortKey());
112
113 // Pop |sequence_c| from the PriorityQueue. |sequence_a| becomes the sequence
114 // with the highest priority.
115 EXPECT_EQ(sequence_c, transaction->PopSequence());
116 EXPECT_EQ(sort_key_a, transaction->PeekSortKey());
117
118 // Pop |sequence_a| from the PriorityQueue. |sequence_d| becomes the sequence
119 // with the highest priority.
120 EXPECT_EQ(sequence_a, transaction->PopSequence());
121 EXPECT_EQ(sort_key_d, transaction->PeekSortKey());
122
123 // Pop |sequence_d| from the PriorityQueue. It is now empty.
124 EXPECT_EQ(sequence_d, transaction->PopSequence());
125 EXPECT_TRUE(transaction->IsEmpty());
126 }
127
128 // Check that creating Transactions on the same thread for 2 unrelated
129 // PriorityQueues causes a crash.
TEST(TaskSchedulerPriorityQueueTest,IllegalTwoTransactionsSameThread)130 TEST(TaskSchedulerPriorityQueueTest, IllegalTwoTransactionsSameThread) {
131 PriorityQueue pq_a;
132 PriorityQueue pq_b;
133
134 EXPECT_DCHECK_DEATH(
135 {
136 std::unique_ptr<PriorityQueue::Transaction> transaction_a =
137 pq_a.BeginTransaction();
138 std::unique_ptr<PriorityQueue::Transaction> transaction_b =
139 pq_b.BeginTransaction();
140 });
141 }
142
143 // Check that it is possible to begin multiple Transactions for the same
144 // PriorityQueue on different threads. The call to BeginTransaction() on the
145 // second thread should block until the Transaction has ended on the first
146 // thread.
TEST(TaskSchedulerPriorityQueueTest,TwoTransactionsTwoThreads)147 TEST(TaskSchedulerPriorityQueueTest, TwoTransactionsTwoThreads) {
148 PriorityQueue pq;
149
150 // Call BeginTransaction() on this thread and keep the Transaction alive.
151 std::unique_ptr<PriorityQueue::Transaction> transaction =
152 pq.BeginTransaction();
153
154 // Call BeginTransaction() on another thread.
155 ThreadBeginningTransaction thread_beginning_transaction(&pq);
156 thread_beginning_transaction.Start();
157
158 // After a few milliseconds, the call to BeginTransaction() on the other
159 // thread should not have returned.
160 thread_beginning_transaction.ExpectTransactionDoesNotBegin();
161
162 // End the Transaction on the current thread.
163 transaction.reset();
164
165 // The other thread should exit after its call to BeginTransaction() returns.
166 thread_beginning_transaction.Join();
167 }
168
169 } // namespace internal
170 } // namespace base
171