1 // Copyright (c) 2012 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.
8 #include "base/compiler_specific.h"
9 #include "base/logging.h"
10 #include "base/memory/scoped_ptr.h"
11 #include "base/memory/scoped_vector.h"
12 #include "net/base/prioritized_dispatcher.h"
13 #include "net/base/request_priority.h"
14 #include "testing/gtest/include/gtest/gtest.h"
20 // We rely on the priority enum values being sequential having starting at 0,
21 // and increasing for higher priorities.
22 COMPILE_ASSERT(MINIMUM_PRIORITY == 0u &&
23 MINIMUM_PRIORITY == IDLE &&
26 HIGHEST <= MAXIMUM_PRIORITY,
27 priority_indexes_incompatible);
29 class PrioritizedDispatcherTest : public testing::Test {
31 typedef PrioritizedDispatcher::Priority Priority;
32 // A job that appends |tag| to |log| when started and '.' when finished.
33 // This is intended to confirm the execution order of a sequence of jobs added
34 // to the dispatcher. Note that finishing order of jobs does not matter.
35 class TestJob : public PrioritizedDispatcher::Job {
37 TestJob(PrioritizedDispatcher* dispatcher,
41 : dispatcher_(dispatcher),
47 bool running() const {
51 const PrioritizedDispatcher::Handle handle() const {
55 void Add(bool at_head) {
56 CHECK(handle_.is_null());
58 size_t num_queued = dispatcher_->num_queued_jobs();
59 size_t num_running = dispatcher_->num_running_jobs();
62 handle_ = dispatcher_->Add(this, priority_);
64 handle_ = dispatcher_->AddAtHead(this, priority_);
67 if (handle_.is_null()) {
68 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
69 EXPECT_TRUE(running_);
70 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
72 EXPECT_FALSE(running_);
73 EXPECT_EQ(priority_, handle_.priority());
74 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
75 EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
79 void ChangePriority(Priority priority) {
80 CHECK(!handle_.is_null());
82 size_t num_queued = dispatcher_->num_queued_jobs();
83 size_t num_running = dispatcher_->num_running_jobs();
85 handle_ = dispatcher_->ChangePriority(handle_, priority);
87 if (handle_.is_null()) {
88 EXPECT_TRUE(running_);
89 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
90 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
92 EXPECT_FALSE(running_);
93 EXPECT_EQ(priority, handle_.priority());
94 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
95 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
96 EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
101 CHECK(!handle_.is_null());
103 size_t num_queued = dispatcher_->num_queued_jobs();
105 dispatcher_->Cancel(handle_);
107 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
108 handle_ = PrioritizedDispatcher::Handle();
114 log_->append(1u, '.');
116 dispatcher_->OnJobFinished();
119 // PriorityDispatch::Job interface
120 virtual void Start() OVERRIDE {
121 EXPECT_FALSE(running_);
122 handle_ = PrioritizedDispatcher::Handle();
124 log_->append(1u, tag_);
128 PrioritizedDispatcher* dispatcher_;
133 PrioritizedDispatcher::Handle handle_;
140 void Prepare(const PrioritizedDispatcher::Limits& limits) {
141 dispatcher_.reset(new PrioritizedDispatcher(limits));
144 TestJob* AddJob(char data, Priority priority) {
145 TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_);
146 jobs_.push_back(job);
151 TestJob* AddJobAtHead(char data, Priority priority) {
152 TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_);
153 jobs_.push_back(job);
158 void Expect(std::string log) {
159 EXPECT_EQ(0u, dispatcher_->num_queued_jobs());
160 EXPECT_EQ(0u, dispatcher_->num_running_jobs());
161 EXPECT_EQ(log, log_);
166 scoped_ptr<PrioritizedDispatcher> dispatcher_;
167 ScopedVector<TestJob> jobs_;
170 TEST_F(PrioritizedDispatcherTest, GetLimits) {
171 // Set non-trivial initial limits.
172 PrioritizedDispatcher::Limits original_limits(NUM_PRIORITIES, 5);
173 original_limits.reserved_slots[HIGHEST] = 1;
174 original_limits.reserved_slots[LOW] = 2;
175 Prepare(original_limits);
177 // Get current limits, make sure the original limits are returned.
178 PrioritizedDispatcher::Limits retrieved_limits = dispatcher_->GetLimits();
179 ASSERT_EQ(original_limits.total_jobs, retrieved_limits.total_jobs);
180 ASSERT_EQ(NUM_PRIORITIES, retrieved_limits.reserved_slots.size());
181 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
183 EXPECT_EQ(original_limits.reserved_slots[priority],
184 retrieved_limits.reserved_slots[priority]);
188 PrioritizedDispatcher::Limits new_limits(NUM_PRIORITIES, 6);
189 new_limits.reserved_slots[MEDIUM] = 3;
190 new_limits.reserved_slots[LOWEST] = 1;
193 // Get current limits, make sure the new limits are returned.
194 retrieved_limits = dispatcher_->GetLimits();
195 ASSERT_EQ(new_limits.total_jobs, retrieved_limits.total_jobs);
196 ASSERT_EQ(NUM_PRIORITIES, retrieved_limits.reserved_slots.size());
197 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
199 EXPECT_EQ(new_limits.reserved_slots[priority],
200 retrieved_limits.reserved_slots[priority]);
204 TEST_F(PrioritizedDispatcherTest, AddAFIFO) {
205 // Allow only one running job.
206 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
209 TestJob* job_a = AddJob('a', IDLE);
210 TestJob* job_b = AddJob('b', IDLE);
211 TestJob* job_c = AddJob('c', IDLE);
212 TestJob* job_d = AddJob('d', IDLE);
214 ASSERT_TRUE(job_a->running());
216 ASSERT_TRUE(job_b->running());
218 ASSERT_TRUE(job_c->running());
220 ASSERT_TRUE(job_d->running());
226 TEST_F(PrioritizedDispatcherTest, AddPriority) {
227 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
230 TestJob* job_a = AddJob('a', IDLE);
231 TestJob* job_b = AddJob('b', MEDIUM);
232 TestJob* job_c = AddJob('c', HIGHEST);
233 TestJob* job_d = AddJob('d', HIGHEST);
234 TestJob* job_e = AddJob('e', MEDIUM);
236 ASSERT_TRUE(job_a->running());
238 ASSERT_TRUE(job_c->running());
240 ASSERT_TRUE(job_d->running());
242 ASSERT_TRUE(job_b->running());
244 ASSERT_TRUE(job_e->running());
247 Expect("a.c.d.b.e.");
250 TEST_F(PrioritizedDispatcherTest, AddAtHead) {
251 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
254 TestJob* job_a = AddJob('a', MEDIUM);
255 TestJob* job_b = AddJobAtHead('b', MEDIUM);
256 TestJob* job_c = AddJobAtHead('c', HIGHEST);
257 TestJob* job_d = AddJobAtHead('d', HIGHEST);
258 TestJob* job_e = AddJobAtHead('e', MEDIUM);
259 TestJob* job_f = AddJob('f', MEDIUM);
261 ASSERT_TRUE(job_a->running());
263 ASSERT_TRUE(job_d->running());
265 ASSERT_TRUE(job_c->running());
267 ASSERT_TRUE(job_e->running());
269 ASSERT_TRUE(job_b->running());
271 ASSERT_TRUE(job_f->running());
274 Expect("a.d.c.e.b.f.");
277 TEST_F(PrioritizedDispatcherTest, EnforceLimits) {
278 // Reserve 2 for HIGHEST and 1 for LOW or higher.
279 // This leaves 2 for LOWEST or lower.
280 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 5);
281 limits.reserved_slots[HIGHEST] = 2;
282 limits.reserved_slots[LOW] = 1;
285 TestJob* job_a = AddJob('a', IDLE); // Uses unreserved slot.
286 TestJob* job_b = AddJob('b', IDLE); // Uses unreserved slot.
287 TestJob* job_c = AddJob('c', LOWEST); // Must wait.
288 TestJob* job_d = AddJob('d', LOW); // Uses reserved slot.
289 TestJob* job_e = AddJob('e', MEDIUM); // Must wait.
290 TestJob* job_f = AddJob('f', HIGHEST); // Uses reserved slot.
291 TestJob* job_g = AddJob('g', HIGHEST); // Uses reserved slot.
292 TestJob* job_h = AddJob('h', HIGHEST); // Must wait.
294 EXPECT_EQ(5u, dispatcher_->num_running_jobs());
295 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
297 ASSERT_TRUE(job_a->running());
298 ASSERT_TRUE(job_b->running());
299 ASSERT_TRUE(job_d->running());
300 ASSERT_TRUE(job_f->running());
301 ASSERT_TRUE(job_g->running());
302 // a, b, d, f, g are running. Finish them in any order.
303 job_b->Finish(); // Releases h.
306 job_g->Finish(); // Releases e.
308 ASSERT_TRUE(job_e->running());
309 ASSERT_TRUE(job_h->running());
311 job_e->Finish(); // Releases c.
312 ASSERT_TRUE(job_c->running());
316 Expect("abdfg.h...e..c..");
319 TEST_F(PrioritizedDispatcherTest, ChangePriority) {
320 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
321 // Reserve one slot only for HIGHEST priority requests.
322 limits.reserved_slots[HIGHEST] = 1;
325 TestJob* job_a = AddJob('a', IDLE);
326 TestJob* job_b = AddJob('b', LOW);
327 TestJob* job_c = AddJob('c', MEDIUM);
328 TestJob* job_d = AddJob('d', MEDIUM);
329 TestJob* job_e = AddJob('e', IDLE);
331 ASSERT_FALSE(job_b->running());
332 ASSERT_FALSE(job_c->running());
333 job_b->ChangePriority(MEDIUM);
334 job_c->ChangePriority(LOW);
336 ASSERT_TRUE(job_a->running());
338 ASSERT_TRUE(job_d->running());
341 EXPECT_FALSE(job_e->running());
342 // Increasing |job_e|'s priority to HIGHEST should result in it being
343 // started immediately.
344 job_e->ChangePriority(HIGHEST);
345 ASSERT_TRUE(job_e->running());
348 ASSERT_TRUE(job_b->running());
350 ASSERT_TRUE(job_c->running());
353 Expect("a.d.be..c.");
356 TEST_F(PrioritizedDispatcherTest, Cancel) {
357 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
360 TestJob* job_a = AddJob('a', IDLE);
361 TestJob* job_b = AddJob('b', IDLE);
362 TestJob* job_c = AddJob('c', IDLE);
363 TestJob* job_d = AddJob('d', IDLE);
364 TestJob* job_e = AddJob('e', IDLE);
366 ASSERT_FALSE(job_b->running());
367 ASSERT_FALSE(job_d->running());
371 ASSERT_TRUE(job_a->running());
373 ASSERT_TRUE(job_c->running());
375 ASSERT_TRUE(job_e->running());
381 TEST_F(PrioritizedDispatcherTest, Evict) {
382 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
385 TestJob* job_a = AddJob('a', IDLE);
386 TestJob* job_b = AddJob('b', LOW);
387 TestJob* job_c = AddJob('c', HIGHEST);
388 TestJob* job_d = AddJob('d', LOW);
389 TestJob* job_e = AddJob('e', HIGHEST);
391 EXPECT_EQ(job_b, dispatcher_->EvictOldestLowest());
392 EXPECT_EQ(job_d, dispatcher_->EvictOldestLowest());
394 ASSERT_TRUE(job_a->running());
396 ASSERT_TRUE(job_c->running());
398 ASSERT_TRUE(job_e->running());
404 TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
405 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
407 EXPECT_TRUE(dispatcher_->EvictOldestLowest() == NULL);
410 TEST_F(PrioritizedDispatcherTest, AddWhileZeroLimits) {
411 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
414 dispatcher_->SetLimitsToZero();
415 TestJob* job_a = AddJob('a', LOW);
416 TestJob* job_b = AddJob('b', MEDIUM);
417 TestJob* job_c = AddJobAtHead('c', MEDIUM);
419 EXPECT_EQ(0u, dispatcher_->num_running_jobs());
420 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
422 dispatcher_->SetLimits(limits);
423 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
424 EXPECT_EQ(1u, dispatcher_->num_queued_jobs());
426 ASSERT_TRUE(job_b->running());
429 ASSERT_TRUE(job_c->running());
432 ASSERT_TRUE(job_a->running());
438 TEST_F(PrioritizedDispatcherTest, ReduceLimitsWhileJobQueued) {
439 PrioritizedDispatcher::Limits initial_limits(NUM_PRIORITIES, 2);
440 Prepare(initial_limits);
442 TestJob* job_a = AddJob('a', MEDIUM);
443 TestJob* job_b = AddJob('b', MEDIUM);
444 TestJob* job_c = AddJob('c', MEDIUM);
445 TestJob* job_d = AddJob('d', MEDIUM);
446 TestJob* job_e = AddJob('e', MEDIUM);
448 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
449 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
451 // Reduce limits to just allow one job at a time. Running jobs should not
453 dispatcher_->SetLimits(PrioritizedDispatcher::Limits(NUM_PRIORITIES, 1));
455 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
456 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
458 // Finishing a job should not result in another job starting.
459 ASSERT_TRUE(job_a->running());
461 EXPECT_EQ(1u, dispatcher_->num_running_jobs());
462 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
464 ASSERT_TRUE(job_b->running());
466 EXPECT_EQ(1u, dispatcher_->num_running_jobs());
467 EXPECT_EQ(2u, dispatcher_->num_queued_jobs());
469 // Increasing the limits again should let c start.
470 dispatcher_->SetLimits(initial_limits);
472 ASSERT_TRUE(job_c->running());
474 ASSERT_TRUE(job_d->running());
476 ASSERT_TRUE(job_e->running());
479 Expect("ab..cd.e..");
482 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenCancel) {
483 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
486 TestJob* job_a = AddJob('a', IDLE);
487 TestJob* job_b = AddJob('b', IDLE);
488 TestJob* job_c = AddJob('c', IDLE);
489 dispatcher_->SetLimitsToZero();
491 ASSERT_TRUE(job_a->running());
492 EXPECT_FALSE(job_b->running());
493 EXPECT_FALSE(job_c->running());
496 EXPECT_FALSE(job_b->running());
497 EXPECT_FALSE(job_c->running());
499 // Cancelling b shouldn't start job c.
501 EXPECT_FALSE(job_c->running());
503 // Restoring the limits should start c.
504 dispatcher_->SetLimits(limits);
505 ASSERT_TRUE(job_c->running());
511 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenIncreasePriority) {
512 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
513 limits.reserved_slots[HIGHEST] = 1;
516 TestJob* job_a = AddJob('a', IDLE);
517 TestJob* job_b = AddJob('b', IDLE);
518 EXPECT_TRUE(job_a->running());
519 EXPECT_FALSE(job_b->running());
520 dispatcher_->SetLimitsToZero();
522 job_b->ChangePriority(HIGHEST);
523 EXPECT_FALSE(job_b->running());
525 EXPECT_FALSE(job_b->running());
531 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
532 TEST_F(PrioritizedDispatcherTest, CancelNull) {
533 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
535 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), "");
538 TEST_F(PrioritizedDispatcherTest, CancelMissing) {
539 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
542 TestJob* job_b = AddJob('b', IDLE);
543 PrioritizedDispatcher::Handle handle = job_b->handle();
544 ASSERT_FALSE(handle.is_null());
545 dispatcher_->Cancel(handle);
546 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), "");
549 // TODO(szym): Fix the PriorityQueue::Pointer check to die here.
550 // http://crbug.com/130846
551 TEST_F(PrioritizedDispatcherTest, DISABLED_CancelIncompatible) {
552 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
555 TestJob* job_b = AddJob('b', IDLE);
556 PrioritizedDispatcher::Handle handle = job_b->handle();
557 ASSERT_FALSE(handle.is_null());
563 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), "");
565 #endif // GTEST_HAS_DEATH_TEST && !defined(NDEBUG)