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 < NUM_PRIORITIES,
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() {
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      handle_ = dispatcher_->Add(this, priority_);
62
63      if (handle_.is_null()) {
64        EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
65        EXPECT_TRUE(running_);
66        EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
67      } else {
68        EXPECT_FALSE(running_);
69        EXPECT_EQ(priority_, handle_.priority());
70        EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
71        EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
72      }
73    }
74
75    void ChangePriority(Priority priority) {
76      CHECK(!handle_.is_null());
77      CHECK(!running_);
78      size_t num_queued = dispatcher_->num_queued_jobs();
79      size_t num_running = dispatcher_->num_running_jobs();
80
81      handle_ = dispatcher_->ChangePriority(handle_, priority);
82
83      if (handle_.is_null()) {
84        EXPECT_TRUE(running_);
85        EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
86        EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
87      } else {
88        EXPECT_FALSE(running_);
89        EXPECT_EQ(priority, handle_.priority());
90        EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
91        EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
92        EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
93      }
94    }
95
96    void Cancel() {
97      CHECK(!handle_.is_null());
98      CHECK(!running_);
99      size_t num_queued = dispatcher_->num_queued_jobs();
100
101      dispatcher_->Cancel(handle_);
102
103      EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
104      handle_ = PrioritizedDispatcher::Handle();
105    }
106
107    void Finish() {
108      CHECK(running_);
109      running_ = false;
110      log_->append(1u, '.');
111
112      dispatcher_->OnJobFinished();
113    }
114
115    // PriorityDispatch::Job interface
116    virtual void Start() OVERRIDE {
117      EXPECT_FALSE(running_);
118      handle_ = PrioritizedDispatcher::Handle();
119      running_ = true;
120      log_->append(1u, tag_);
121    }
122
123   private:
124    PrioritizedDispatcher* dispatcher_;
125
126    char tag_;
127    Priority priority_;
128
129    PrioritizedDispatcher::Handle handle_;
130    bool running_;
131
132    std::string* log_;
133  };
134
135 protected:
136  void Prepare(const PrioritizedDispatcher::Limits& limits) {
137    dispatcher_.reset(new PrioritizedDispatcher(limits));
138  }
139
140  TestJob* AddJob(char data, Priority priority) {
141    TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_);
142    jobs_.push_back(job);
143    job->Add();
144    return job;
145  }
146
147  void Expect(std::string log) {
148    EXPECT_EQ(0u, dispatcher_->num_queued_jobs());
149    EXPECT_EQ(0u, dispatcher_->num_running_jobs());
150    EXPECT_EQ(log, log_);
151    log_.clear();
152  }
153
154  std::string log_;
155  scoped_ptr<PrioritizedDispatcher> dispatcher_;
156  ScopedVector<TestJob> jobs_;
157};
158
159TEST_F(PrioritizedDispatcherTest, AddAFIFO) {
160  // Allow only one running job.
161  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
162  Prepare(limits);
163
164  TestJob* job_a = AddJob('a', IDLE);
165  TestJob* job_b = AddJob('b', IDLE);
166  TestJob* job_c = AddJob('c', IDLE);
167  TestJob* job_d = AddJob('d', IDLE);
168
169  ASSERT_TRUE(job_a->running());
170  job_a->Finish();
171  ASSERT_TRUE(job_b->running());
172  job_b->Finish();
173  ASSERT_TRUE(job_c->running());
174  job_c->Finish();
175  ASSERT_TRUE(job_d->running());
176  job_d->Finish();
177
178  Expect("a.b.c.d.");
179}
180
181TEST_F(PrioritizedDispatcherTest, AddPriority) {
182  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
183  Prepare(limits);
184
185  TestJob* job_a = AddJob('a', IDLE);
186  TestJob* job_b = AddJob('b', MEDIUM);
187  TestJob* job_c = AddJob('c', HIGHEST);
188  TestJob* job_d = AddJob('d', HIGHEST);
189  TestJob* job_e = AddJob('e', MEDIUM);
190
191  ASSERT_TRUE(job_a->running());
192  job_a->Finish();
193  ASSERT_TRUE(job_c->running());
194  job_c->Finish();
195  ASSERT_TRUE(job_d->running());
196  job_d->Finish();
197  ASSERT_TRUE(job_b->running());
198  job_b->Finish();
199  ASSERT_TRUE(job_e->running());
200  job_e->Finish();
201
202  Expect("a.c.d.b.e.");
203}
204
205TEST_F(PrioritizedDispatcherTest, EnforceLimits) {
206  // Reserve 2 for HIGHEST and 1 for LOW or higher.
207  // This leaves 2 for LOWEST or lower.
208  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 5);
209  limits.reserved_slots[HIGHEST] = 2;
210  limits.reserved_slots[LOW] = 1;
211  Prepare(limits);
212
213  TestJob* job_a = AddJob('a', IDLE);    // Uses unreserved slot.
214  TestJob* job_b = AddJob('b', IDLE);    // Uses unreserved slot.
215  TestJob* job_c = AddJob('c', LOWEST);  // Must wait.
216  TestJob* job_d = AddJob('d', LOW);     // Uses reserved slot.
217  TestJob* job_e = AddJob('e', MEDIUM);  // Must wait.
218  TestJob* job_f = AddJob('f', HIGHEST); // Uses reserved slot.
219  TestJob* job_g = AddJob('g', HIGHEST); // Uses reserved slot.
220  TestJob* job_h = AddJob('h', HIGHEST); // Must wait.
221
222  EXPECT_EQ(5u, dispatcher_->num_running_jobs());
223  EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
224
225  ASSERT_TRUE(job_a->running());
226  ASSERT_TRUE(job_b->running());
227  ASSERT_TRUE(job_d->running());
228  ASSERT_TRUE(job_f->running());
229  ASSERT_TRUE(job_g->running());
230  // a, b, d, f, g are running. Finish them in any order.
231  job_b->Finish();  // Releases h.
232  job_f->Finish();
233  job_a->Finish();
234  job_g->Finish();  // Releases e.
235  job_d->Finish();
236  ASSERT_TRUE(job_e->running());
237  ASSERT_TRUE(job_h->running());
238  // h, e are running.
239  job_e->Finish();  // Releases c.
240  ASSERT_TRUE(job_c->running());
241  job_c->Finish();
242  job_h->Finish();
243
244  Expect("abdfg.h...e..c..");
245}
246
247TEST_F(PrioritizedDispatcherTest, ChangePriority) {
248  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
249  Prepare(limits);
250
251  TestJob* job_a = AddJob('a', IDLE);
252  TestJob* job_b = AddJob('b', MEDIUM);
253  TestJob* job_c = AddJob('c', HIGHEST);
254  TestJob* job_d = AddJob('d', HIGHEST);
255
256  ASSERT_FALSE(job_b->running());
257  ASSERT_FALSE(job_c->running());
258  job_b->ChangePriority(HIGHEST);
259  job_c->ChangePriority(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_b->running());
266  job_b->Finish();
267  ASSERT_TRUE(job_c->running());
268  job_c->Finish();
269
270  Expect("a.d.b.c.");
271}
272
273TEST_F(PrioritizedDispatcherTest, Cancel) {
274  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
275  Prepare(limits);
276
277  TestJob* job_a = AddJob('a', IDLE);
278  TestJob* job_b = AddJob('b', IDLE);
279  TestJob* job_c = AddJob('c', IDLE);
280  TestJob* job_d = AddJob('d', IDLE);
281  TestJob* job_e = AddJob('e', IDLE);
282
283  ASSERT_FALSE(job_b->running());
284  ASSERT_FALSE(job_d->running());
285  job_b->Cancel();
286  job_d->Cancel();
287
288  ASSERT_TRUE(job_a->running());
289  job_a->Finish();
290  ASSERT_TRUE(job_c->running());
291  job_c->Finish();
292  ASSERT_TRUE(job_e->running());
293  job_e->Finish();
294
295  Expect("a.c.e.");
296}
297
298TEST_F(PrioritizedDispatcherTest, Evict) {
299  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
300  Prepare(limits);
301
302  TestJob* job_a = AddJob('a', IDLE);
303  TestJob* job_b = AddJob('b', LOW);
304  TestJob* job_c = AddJob('c', HIGHEST);
305  TestJob* job_d = AddJob('d', LOW);
306  TestJob* job_e = AddJob('e', HIGHEST);
307
308  EXPECT_EQ(job_b, dispatcher_->EvictOldestLowest());
309  EXPECT_EQ(job_d, dispatcher_->EvictOldestLowest());
310
311  ASSERT_TRUE(job_a->running());
312  job_a->Finish();
313  ASSERT_TRUE(job_c->running());
314  job_c->Finish();
315  ASSERT_TRUE(job_e->running());
316  job_e->Finish();
317
318  Expect("a.c.e.");
319}
320
321TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
322  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
323  Prepare(limits);
324  EXPECT_TRUE(dispatcher_->EvictOldestLowest() == NULL);
325}
326
327#if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
328TEST_F(PrioritizedDispatcherTest, CancelNull) {
329  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
330  Prepare(limits);
331  EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), "");
332}
333
334TEST_F(PrioritizedDispatcherTest, CancelMissing) {
335  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
336  Prepare(limits);
337  AddJob('a', IDLE);
338  TestJob* job_b = AddJob('b', IDLE);
339  PrioritizedDispatcher::Handle handle = job_b->handle();
340  ASSERT_FALSE(handle.is_null());
341  dispatcher_->Cancel(handle);
342  EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), "");
343}
344
345// TODO(szym): Fix the PriorityQueue::Pointer check to die here.
346// http://crbug.com/130846
347TEST_F(PrioritizedDispatcherTest, DISABLED_CancelIncompatible) {
348  PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
349  Prepare(limits);
350  AddJob('a', IDLE);
351  TestJob* job_b = AddJob('b', IDLE);
352  PrioritizedDispatcher::Handle handle = job_b->handle();
353  ASSERT_FALSE(handle.is_null());
354
355  // New dispatcher.
356  Prepare(limits);
357  AddJob('a', IDLE);
358  AddJob('b', IDLE);
359  EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), "");
360}
361#endif  // GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
362
363}  // namespace
364
365}  // namespace net
366