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.
4
5#include <ctype.h>
6#include <string>
7
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"
15
16namespace net {
17
18namespace {
19
20// We rely on the priority enum values being sequential having starting at 0,
21// and increasing for higher priorities.
22COMPILE_ASSERT(MINIMUM_PRIORITY == 0u &&
23               MINIMUM_PRIORITY == IDLE &&
24               IDLE < LOWEST &&
25               LOWEST < HIGHEST &&
26               HIGHEST <= MAXIMUM_PRIORITY,
27               priority_indexes_incompatible);
28
29class PrioritizedDispatcherTest : public testing::Test {
30 public:
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 {
36   public:
37    TestJob(PrioritizedDispatcher* dispatcher,
38            char tag,
39            Priority priority,
40            std::string* log)
41        : dispatcher_(dispatcher),
42          tag_(tag),
43          priority_(priority),
44          running_(false),
45          log_(log) {}
46
47    bool running() const {
48      return running_;
49    }
50
51    const PrioritizedDispatcher::Handle handle() const {
52      return handle_;
53    }
54
55    void Add(bool at_head) {
56      CHECK(handle_.is_null());
57      CHECK(!running_);
58      size_t num_queued = dispatcher_->num_queued_jobs();
59      size_t num_running = dispatcher_->num_running_jobs();
60
61      if (!at_head) {
62        handle_ = dispatcher_->Add(this, priority_);
63      } else {
64        handle_ = dispatcher_->AddAtHead(this, priority_);
65      }
66
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());
71      } else {
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());
76      }
77    }
78
79    void ChangePriority(Priority priority) {
80      CHECK(!handle_.is_null());
81      CHECK(!running_);
82      size_t num_queued = dispatcher_->num_queued_jobs();
83      size_t num_running = dispatcher_->num_running_jobs();
84
85      handle_ = dispatcher_->ChangePriority(handle_, priority);
86
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());
91      } else {
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());
97      }
98    }
99
100    void Cancel() {
101      CHECK(!handle_.is_null());
102      CHECK(!running_);
103      size_t num_queued = dispatcher_->num_queued_jobs();
104
105      dispatcher_->Cancel(handle_);
106
107      EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
108      handle_ = PrioritizedDispatcher::Handle();
109    }
110
111    void Finish() {
112      CHECK(running_);
113      running_ = false;
114      log_->append(1u, '.');
115
116      dispatcher_->OnJobFinished();
117    }
118
119    // PriorityDispatch::Job interface
120    virtual void Start() OVERRIDE {
121      EXPECT_FALSE(running_);
122      handle_ = PrioritizedDispatcher::Handle();
123      running_ = true;
124      log_->append(1u, tag_);
125    }
126
127   private:
128    PrioritizedDispatcher* dispatcher_;
129
130    char tag_;
131    Priority priority_;
132
133    PrioritizedDispatcher::Handle handle_;
134    bool running_;
135
136    std::string* log_;
137  };
138
139 protected:
140  void Prepare(const PrioritizedDispatcher::Limits& limits) {
141    dispatcher_.reset(new PrioritizedDispatcher(limits));
142  }
143
144  TestJob* AddJob(char data, Priority priority) {
145    TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_);
146    jobs_.push_back(job);
147    job->Add(false);
148    return job;
149  }
150
151  TestJob* AddJobAtHead(char data, Priority priority) {
152    TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_);
153    jobs_.push_back(job);
154    job->Add(true);
155    return job;
156  }
157
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_);
162    log_.clear();
163  }
164
165  std::string log_;
166  scoped_ptr<PrioritizedDispatcher> dispatcher_;
167  ScopedVector<TestJob> jobs_;
168};
169
170TEST_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);
176
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;
182       ++priority) {
183    EXPECT_EQ(original_limits.reserved_slots[priority],
184              retrieved_limits.reserved_slots[priority]);
185  }
186
187  // Set new limits.
188  PrioritizedDispatcher::Limits new_limits(NUM_PRIORITIES, 6);
189  new_limits.reserved_slots[MEDIUM] = 3;
190  new_limits.reserved_slots[LOWEST] = 1;
191  Prepare(new_limits);
192
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;
198       ++priority) {
199    EXPECT_EQ(new_limits.reserved_slots[priority],
200              retrieved_limits.reserved_slots[priority]);
201  }
202}
203
204TEST_F(PrioritizedDispatcherTest, AddAFIFO) {
205  // Allow only one running job.
206  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
207  Prepare(limits);
208
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);
213
214  ASSERT_TRUE(job_a->running());
215  job_a->Finish();
216  ASSERT_TRUE(job_b->running());
217  job_b->Finish();
218  ASSERT_TRUE(job_c->running());
219  job_c->Finish();
220  ASSERT_TRUE(job_d->running());
221  job_d->Finish();
222
223  Expect("a.b.c.d.");
224}
225
226TEST_F(PrioritizedDispatcherTest, AddPriority) {
227  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
228  Prepare(limits);
229
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);
235
236  ASSERT_TRUE(job_a->running());
237  job_a->Finish();
238  ASSERT_TRUE(job_c->running());
239  job_c->Finish();
240  ASSERT_TRUE(job_d->running());
241  job_d->Finish();
242  ASSERT_TRUE(job_b->running());
243  job_b->Finish();
244  ASSERT_TRUE(job_e->running());
245  job_e->Finish();
246
247  Expect("a.c.d.b.e.");
248}
249
250TEST_F(PrioritizedDispatcherTest, AddAtHead) {
251  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
252  Prepare(limits);
253
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);
260
261  ASSERT_TRUE(job_a->running());
262  job_a->Finish();
263  ASSERT_TRUE(job_d->running());
264  job_d->Finish();
265  ASSERT_TRUE(job_c->running());
266  job_c->Finish();
267  ASSERT_TRUE(job_e->running());
268  job_e->Finish();
269  ASSERT_TRUE(job_b->running());
270  job_b->Finish();
271  ASSERT_TRUE(job_f->running());
272  job_f->Finish();
273
274  Expect("a.d.c.e.b.f.");
275}
276
277TEST_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;
283  Prepare(limits);
284
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.
293
294  EXPECT_EQ(5u, dispatcher_->num_running_jobs());
295  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
296
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.
304  job_f->Finish();
305  job_a->Finish();
306  job_g->Finish();  // Releases e.
307  job_d->Finish();
308  ASSERT_TRUE(job_e->running());
309  ASSERT_TRUE(job_h->running());
310  // h, e are running.
311  job_e->Finish();  // Releases c.
312  ASSERT_TRUE(job_c->running());
313  job_c->Finish();
314  job_h->Finish();
315
316  Expect("abdfg.h...e..c..");
317}
318
319TEST_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;
323  Prepare(limits);
324
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);
330
331  ASSERT_FALSE(job_b->running());
332  ASSERT_FALSE(job_c->running());
333  job_b->ChangePriority(MEDIUM);
334  job_c->ChangePriority(LOW);
335
336  ASSERT_TRUE(job_a->running());
337  job_a->Finish();
338  ASSERT_TRUE(job_d->running());
339  job_d->Finish();
340
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());
346  job_e->Finish();
347
348  ASSERT_TRUE(job_b->running());
349  job_b->Finish();
350  ASSERT_TRUE(job_c->running());
351  job_c->Finish();
352
353  Expect("a.d.be..c.");
354}
355
356TEST_F(PrioritizedDispatcherTest, Cancel) {
357  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
358  Prepare(limits);
359
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);
365
366  ASSERT_FALSE(job_b->running());
367  ASSERT_FALSE(job_d->running());
368  job_b->Cancel();
369  job_d->Cancel();
370
371  ASSERT_TRUE(job_a->running());
372  job_a->Finish();
373  ASSERT_TRUE(job_c->running());
374  job_c->Finish();
375  ASSERT_TRUE(job_e->running());
376  job_e->Finish();
377
378  Expect("a.c.e.");
379}
380
381TEST_F(PrioritizedDispatcherTest, Evict) {
382  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
383  Prepare(limits);
384
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);
390
391  EXPECT_EQ(job_b, dispatcher_->EvictOldestLowest());
392  EXPECT_EQ(job_d, dispatcher_->EvictOldestLowest());
393
394  ASSERT_TRUE(job_a->running());
395  job_a->Finish();
396  ASSERT_TRUE(job_c->running());
397  job_c->Finish();
398  ASSERT_TRUE(job_e->running());
399  job_e->Finish();
400
401  Expect("a.c.e.");
402}
403
404TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
405  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
406  Prepare(limits);
407  EXPECT_TRUE(dispatcher_->EvictOldestLowest() == NULL);
408}
409
410TEST_F(PrioritizedDispatcherTest, AddWhileZeroLimits) {
411  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
412  Prepare(limits);
413
414  dispatcher_->SetLimitsToZero();
415  TestJob* job_a = AddJob('a', LOW);
416  TestJob* job_b = AddJob('b', MEDIUM);
417  TestJob* job_c = AddJobAtHead('c', MEDIUM);
418
419  EXPECT_EQ(0u, dispatcher_->num_running_jobs());
420  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
421
422  dispatcher_->SetLimits(limits);
423  EXPECT_EQ(2u, dispatcher_->num_running_jobs());
424  EXPECT_EQ(1u, dispatcher_->num_queued_jobs());
425
426  ASSERT_TRUE(job_b->running());
427  job_b->Finish();
428
429  ASSERT_TRUE(job_c->running());
430  job_c->Finish();
431
432  ASSERT_TRUE(job_a->running());
433  job_a->Finish();
434
435  Expect("cb.a..");
436}
437
438TEST_F(PrioritizedDispatcherTest, ReduceLimitsWhileJobQueued) {
439  PrioritizedDispatcher::Limits initial_limits(NUM_PRIORITIES, 2);
440  Prepare(initial_limits);
441
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);
447
448  EXPECT_EQ(2u, dispatcher_->num_running_jobs());
449  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
450
451  // Reduce limits to just allow one job at a time.  Running jobs should not
452  // be affected.
453  dispatcher_->SetLimits(PrioritizedDispatcher::Limits(NUM_PRIORITIES, 1));
454
455  EXPECT_EQ(2u, dispatcher_->num_running_jobs());
456  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
457
458  // Finishing a job should not result in another job starting.
459  ASSERT_TRUE(job_a->running());
460  job_a->Finish();
461  EXPECT_EQ(1u, dispatcher_->num_running_jobs());
462  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
463
464  ASSERT_TRUE(job_b->running());
465  job_b->Finish();
466  EXPECT_EQ(1u, dispatcher_->num_running_jobs());
467  EXPECT_EQ(2u, dispatcher_->num_queued_jobs());
468
469  // Increasing the limits again should let c start.
470  dispatcher_->SetLimits(initial_limits);
471
472  ASSERT_TRUE(job_c->running());
473  job_c->Finish();
474  ASSERT_TRUE(job_d->running());
475  job_d->Finish();
476  ASSERT_TRUE(job_e->running());
477  job_e->Finish();
478
479  Expect("ab..cd.e..");
480}
481
482TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenCancel) {
483  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
484  Prepare(limits);
485
486  TestJob* job_a = AddJob('a', IDLE);
487  TestJob* job_b = AddJob('b', IDLE);
488  TestJob* job_c = AddJob('c', IDLE);
489  dispatcher_->SetLimitsToZero();
490
491  ASSERT_TRUE(job_a->running());
492  EXPECT_FALSE(job_b->running());
493  EXPECT_FALSE(job_c->running());
494  job_a->Finish();
495
496  EXPECT_FALSE(job_b->running());
497  EXPECT_FALSE(job_c->running());
498
499  // Cancelling b shouldn't start job c.
500  job_b->Cancel();
501  EXPECT_FALSE(job_c->running());
502
503  // Restoring the limits should start c.
504  dispatcher_->SetLimits(limits);
505  ASSERT_TRUE(job_c->running());
506  job_c->Finish();
507
508  Expect("a.c.");
509}
510
511TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenIncreasePriority) {
512  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
513  limits.reserved_slots[HIGHEST] = 1;
514  Prepare(limits);
515
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();
521
522  job_b->ChangePriority(HIGHEST);
523  EXPECT_FALSE(job_b->running());
524  job_a->Finish();
525  EXPECT_FALSE(job_b->running());
526
527  job_b->Cancel();
528  Expect("a.");
529}
530
531#if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
532TEST_F(PrioritizedDispatcherTest, CancelNull) {
533  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
534  Prepare(limits);
535  EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), "");
536}
537
538TEST_F(PrioritizedDispatcherTest, CancelMissing) {
539  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
540  Prepare(limits);
541  AddJob('a', IDLE);
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), "");
547}
548
549// TODO(szym): Fix the PriorityQueue::Pointer check to die here.
550// http://crbug.com/130846
551TEST_F(PrioritizedDispatcherTest, DISABLED_CancelIncompatible) {
552  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
553  Prepare(limits);
554  AddJob('a', IDLE);
555  TestJob* job_b = AddJob('b', IDLE);
556  PrioritizedDispatcher::Handle handle = job_b->handle();
557  ASSERT_FALSE(handle.is_null());
558
559  // New dispatcher.
560  Prepare(limits);
561  AddJob('a', IDLE);
562  AddJob('b', IDLE);
563  EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), "");
564}
565#endif  // GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
566
567}  // namespace
568
569}  // namespace net
570