1 // Copyright 2012 The Chromium Authors
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 "net/base/prioritized_dispatcher.h"
6
7 #include <memory>
8 #include <string>
9
10 #include "base/check.h"
11 #include "base/compiler_specific.h"
12 #include "base/memory/raw_ptr.h"
13 #include "base/test/gtest_util.h"
14 #include "net/base/request_priority.h"
15 #include "testing/gtest/include/gtest/gtest.h"
16
17 namespace net {
18
19 namespace {
20
21 // We rely on the priority enum values being sequential having starting at 0,
22 // and increasing for higher priorities.
23 static_assert(MINIMUM_PRIORITY == 0u && MINIMUM_PRIORITY == THROTTLED &&
24 THROTTLED < IDLE &&
25 IDLE < LOWEST &&
26 LOWEST < HIGHEST &&
27 HIGHEST <= MAXIMUM_PRIORITY,
28 "priority indexes incompatible");
29
30 class PrioritizedDispatcherTest : public testing::Test {
31 public:
32 typedef PrioritizedDispatcher::Priority Priority;
33 // A job that appends |tag| to |log| when started and '.' when finished.
34 // This is intended to confirm the execution order of a sequence of jobs added
35 // to the dispatcher. Note that finishing order of jobs does not matter.
36 class TestJob : public PrioritizedDispatcher::Job {
37 public:
TestJob(PrioritizedDispatcher * dispatcher,char tag,Priority priority,std::string * log)38 TestJob(PrioritizedDispatcher* dispatcher,
39 char tag,
40 Priority priority,
41 std::string* log)
42 : dispatcher_(dispatcher), tag_(tag), priority_(priority), log_(log) {}
43
running() const44 bool running() const {
45 return running_;
46 }
47
handle() const48 const PrioritizedDispatcher::Handle handle() const {
49 return handle_;
50 }
51
Add(bool at_head)52 void Add(bool at_head) {
53 CHECK(handle_.is_null());
54 CHECK(!running_);
55 size_t num_queued = dispatcher_->num_queued_jobs();
56 size_t num_running = dispatcher_->num_running_jobs();
57
58 if (!at_head) {
59 handle_ = dispatcher_->Add(this, priority_);
60 } else {
61 handle_ = dispatcher_->AddAtHead(this, priority_);
62 }
63
64 if (handle_.is_null()) {
65 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
66 EXPECT_TRUE(running_);
67 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
68 } else {
69 EXPECT_FALSE(running_);
70 EXPECT_EQ(priority_, handle_.priority());
71 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
72 EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
73 }
74 }
75
ChangePriority(Priority priority)76 void ChangePriority(Priority priority) {
77 CHECK(!handle_.is_null());
78 CHECK(!running_);
79 size_t num_queued = dispatcher_->num_queued_jobs();
80 size_t num_running = dispatcher_->num_running_jobs();
81
82 handle_ = dispatcher_->ChangePriority(handle_, priority);
83
84 if (handle_.is_null()) {
85 EXPECT_TRUE(running_);
86 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
87 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
88 } else {
89 EXPECT_FALSE(running_);
90 EXPECT_EQ(priority, handle_.priority());
91 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
92 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
93 EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
94 }
95 }
96
Cancel()97 void Cancel() {
98 CHECK(!handle_.is_null());
99 CHECK(!running_);
100 size_t num_queued = dispatcher_->num_queued_jobs();
101
102 dispatcher_->Cancel(handle_);
103
104 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
105 handle_ = PrioritizedDispatcher::Handle();
106 }
107
Finish()108 void Finish() {
109 CHECK(running_);
110 running_ = false;
111 log_->append(1u, '.');
112
113 dispatcher_->OnJobFinished();
114 }
115
116 // PrioritizedDispatcher::Job interface
Start()117 void Start() override {
118 EXPECT_FALSE(running_);
119 handle_ = PrioritizedDispatcher::Handle();
120 running_ = true;
121 log_->append(1u, tag_);
122 }
123
124 private:
125 raw_ptr<PrioritizedDispatcher> dispatcher_;
126
127 char tag_;
128 Priority priority_;
129
130 PrioritizedDispatcher::Handle handle_;
131 bool running_ = false;
132
133 raw_ptr<std::string> log_;
134 };
135
136 protected:
Prepare(const PrioritizedDispatcher::Limits & limits)137 void Prepare(const PrioritizedDispatcher::Limits& limits) {
138 dispatcher_ = std::make_unique<PrioritizedDispatcher>(limits);
139 }
140
AddJob(char data,Priority priority)141 std::unique_ptr<TestJob> AddJob(char data, Priority priority) {
142 auto job =
143 std::make_unique<TestJob>(dispatcher_.get(), data, priority, &log_);
144 job->Add(false);
145 return job;
146 }
147
AddJobAtHead(char data,Priority priority)148 std::unique_ptr<TestJob> AddJobAtHead(char data, Priority priority) {
149 auto job =
150 std::make_unique<TestJob>(dispatcher_.get(), data, priority, &log_);
151 job->Add(true);
152 return job;
153 }
154
Expect(const std::string & log)155 void Expect(const std::string& log) {
156 EXPECT_EQ(0u, dispatcher_->num_queued_jobs());
157 EXPECT_EQ(0u, dispatcher_->num_running_jobs());
158 EXPECT_EQ(log, log_);
159 log_.clear();
160 }
161
162 std::string log_;
163 std::unique_ptr<PrioritizedDispatcher> dispatcher_;
164 };
165
TEST_F(PrioritizedDispatcherTest,GetLimits)166 TEST_F(PrioritizedDispatcherTest, GetLimits) {
167 // Set non-trivial initial limits.
168 PrioritizedDispatcher::Limits original_limits(NUM_PRIORITIES, 5);
169 original_limits.reserved_slots[HIGHEST] = 1;
170 original_limits.reserved_slots[LOW] = 2;
171 Prepare(original_limits);
172
173 // Get current limits, make sure the original limits are returned.
174 PrioritizedDispatcher::Limits retrieved_limits = dispatcher_->GetLimits();
175 ASSERT_EQ(original_limits.total_jobs, retrieved_limits.total_jobs);
176 ASSERT_EQ(static_cast<size_t>(NUM_PRIORITIES),
177 retrieved_limits.reserved_slots.size());
178 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
179 ++priority) {
180 EXPECT_EQ(original_limits.reserved_slots[priority],
181 retrieved_limits.reserved_slots[priority]);
182 }
183
184 // Set new limits.
185 PrioritizedDispatcher::Limits new_limits(NUM_PRIORITIES, 6);
186 new_limits.reserved_slots[MEDIUM] = 3;
187 new_limits.reserved_slots[LOWEST] = 1;
188 Prepare(new_limits);
189
190 // Get current limits, make sure the new limits are returned.
191 retrieved_limits = dispatcher_->GetLimits();
192 ASSERT_EQ(new_limits.total_jobs, retrieved_limits.total_jobs);
193 ASSERT_EQ(static_cast<size_t>(NUM_PRIORITIES),
194 retrieved_limits.reserved_slots.size());
195 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
196 ++priority) {
197 EXPECT_EQ(new_limits.reserved_slots[priority],
198 retrieved_limits.reserved_slots[priority]);
199 }
200 }
201
TEST_F(PrioritizedDispatcherTest,AddAFIFO)202 TEST_F(PrioritizedDispatcherTest, AddAFIFO) {
203 // Allow only one running job.
204 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
205 Prepare(limits);
206
207 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
208 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
209 std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
210 std::unique_ptr<TestJob> job_d = AddJob('d', IDLE);
211
212 ASSERT_TRUE(job_a->running());
213 job_a->Finish();
214 ASSERT_TRUE(job_b->running());
215 job_b->Finish();
216 ASSERT_TRUE(job_c->running());
217 job_c->Finish();
218 ASSERT_TRUE(job_d->running());
219 job_d->Finish();
220
221 Expect("a.b.c.d.");
222 }
223
TEST_F(PrioritizedDispatcherTest,AddPriority)224 TEST_F(PrioritizedDispatcherTest, AddPriority) {
225 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
226 Prepare(limits);
227
228 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
229 std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
230 std::unique_ptr<TestJob> job_c = AddJob('c', HIGHEST);
231 std::unique_ptr<TestJob> job_d = AddJob('d', HIGHEST);
232 std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM);
233
234 ASSERT_TRUE(job_a->running());
235 job_a->Finish();
236 ASSERT_TRUE(job_c->running());
237 job_c->Finish();
238 ASSERT_TRUE(job_d->running());
239 job_d->Finish();
240 ASSERT_TRUE(job_b->running());
241 job_b->Finish();
242 ASSERT_TRUE(job_e->running());
243 job_e->Finish();
244
245 Expect("a.c.d.b.e.");
246 }
247
TEST_F(PrioritizedDispatcherTest,AddAtHead)248 TEST_F(PrioritizedDispatcherTest, AddAtHead) {
249 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
250 Prepare(limits);
251
252 std::unique_ptr<TestJob> job_a = AddJob('a', MEDIUM);
253 std::unique_ptr<TestJob> job_b = AddJobAtHead('b', MEDIUM);
254 std::unique_ptr<TestJob> job_c = AddJobAtHead('c', HIGHEST);
255 std::unique_ptr<TestJob> job_d = AddJobAtHead('d', HIGHEST);
256 std::unique_ptr<TestJob> job_e = AddJobAtHead('e', MEDIUM);
257 std::unique_ptr<TestJob> job_f = AddJob('f', MEDIUM);
258
259 ASSERT_TRUE(job_a->running());
260 job_a->Finish();
261 ASSERT_TRUE(job_d->running());
262 job_d->Finish();
263 ASSERT_TRUE(job_c->running());
264 job_c->Finish();
265 ASSERT_TRUE(job_e->running());
266 job_e->Finish();
267 ASSERT_TRUE(job_b->running());
268 job_b->Finish();
269 ASSERT_TRUE(job_f->running());
270 job_f->Finish();
271
272 Expect("a.d.c.e.b.f.");
273 }
274
TEST_F(PrioritizedDispatcherTest,EnforceLimits)275 TEST_F(PrioritizedDispatcherTest, EnforceLimits) {
276 // Reserve 2 for HIGHEST and 1 for LOW or higher.
277 // This leaves 2 for LOWEST or lower.
278 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 5);
279 limits.reserved_slots[HIGHEST] = 2;
280 limits.reserved_slots[LOW] = 1;
281 Prepare(limits);
282
283 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE); // Uses unreserved slot.
284 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE); // Uses unreserved slot.
285 std::unique_ptr<TestJob> job_c = AddJob('c', LOWEST); // Must wait.
286 std::unique_ptr<TestJob> job_d = AddJob('d', LOW); // Uses reserved slot.
287 std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM); // Must wait.
288 std::unique_ptr<TestJob> job_f = AddJob('f', HIGHEST); // Uses reserved slot.
289 std::unique_ptr<TestJob> job_g = AddJob('g', HIGHEST); // Uses reserved slot.
290 std::unique_ptr<TestJob> job_h = AddJob('h', HIGHEST); // Must wait.
291
292 EXPECT_EQ(5u, dispatcher_->num_running_jobs());
293 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
294
295 ASSERT_TRUE(job_a->running());
296 ASSERT_TRUE(job_b->running());
297 ASSERT_TRUE(job_d->running());
298 ASSERT_TRUE(job_f->running());
299 ASSERT_TRUE(job_g->running());
300 // a, b, d, f, g are running. Finish them in any order.
301 job_b->Finish(); // Releases h.
302 job_f->Finish();
303 job_a->Finish();
304 job_g->Finish(); // Releases e.
305 job_d->Finish();
306 ASSERT_TRUE(job_e->running());
307 ASSERT_TRUE(job_h->running());
308 // h, e are running.
309 job_e->Finish(); // Releases c.
310 ASSERT_TRUE(job_c->running());
311 job_c->Finish();
312 job_h->Finish();
313
314 Expect("abdfg.h...e..c..");
315 }
316
TEST_F(PrioritizedDispatcherTest,ChangePriority)317 TEST_F(PrioritizedDispatcherTest, ChangePriority) {
318 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
319 // Reserve one slot only for HIGHEST priority requests.
320 limits.reserved_slots[HIGHEST] = 1;
321 Prepare(limits);
322
323 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
324 std::unique_ptr<TestJob> job_b = AddJob('b', LOW);
325 std::unique_ptr<TestJob> job_c = AddJob('c', MEDIUM);
326 std::unique_ptr<TestJob> job_d = AddJob('d', MEDIUM);
327 std::unique_ptr<TestJob> job_e = AddJob('e', IDLE);
328
329 ASSERT_FALSE(job_b->running());
330 ASSERT_FALSE(job_c->running());
331 job_b->ChangePriority(MEDIUM);
332 job_c->ChangePriority(LOW);
333
334 ASSERT_TRUE(job_a->running());
335 job_a->Finish();
336 ASSERT_TRUE(job_d->running());
337 job_d->Finish();
338
339 EXPECT_FALSE(job_e->running());
340 // Increasing |job_e|'s priority to HIGHEST should result in it being
341 // started immediately.
342 job_e->ChangePriority(HIGHEST);
343 ASSERT_TRUE(job_e->running());
344 job_e->Finish();
345
346 ASSERT_TRUE(job_b->running());
347 job_b->Finish();
348 ASSERT_TRUE(job_c->running());
349 job_c->Finish();
350
351 Expect("a.d.be..c.");
352 }
353
TEST_F(PrioritizedDispatcherTest,Cancel)354 TEST_F(PrioritizedDispatcherTest, Cancel) {
355 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
356 Prepare(limits);
357
358 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
359 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
360 std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
361 std::unique_ptr<TestJob> job_d = AddJob('d', IDLE);
362 std::unique_ptr<TestJob> job_e = AddJob('e', IDLE);
363
364 ASSERT_FALSE(job_b->running());
365 ASSERT_FALSE(job_d->running());
366 job_b->Cancel();
367 job_d->Cancel();
368
369 ASSERT_TRUE(job_a->running());
370 job_a->Finish();
371 ASSERT_TRUE(job_c->running());
372 job_c->Finish();
373 ASSERT_TRUE(job_e->running());
374 job_e->Finish();
375
376 Expect("a.c.e.");
377 }
378
TEST_F(PrioritizedDispatcherTest,Evict)379 TEST_F(PrioritizedDispatcherTest, Evict) {
380 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
381 Prepare(limits);
382
383 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
384 std::unique_ptr<TestJob> job_b = AddJob('b', LOW);
385 std::unique_ptr<TestJob> job_c = AddJob('c', HIGHEST);
386 std::unique_ptr<TestJob> job_d = AddJob('d', LOW);
387 std::unique_ptr<TestJob> job_e = AddJob('e', HIGHEST);
388
389 EXPECT_EQ(job_b.get(), dispatcher_->EvictOldestLowest());
390 EXPECT_EQ(job_d.get(), dispatcher_->EvictOldestLowest());
391
392 ASSERT_TRUE(job_a->running());
393 job_a->Finish();
394 ASSERT_TRUE(job_c->running());
395 job_c->Finish();
396 ASSERT_TRUE(job_e->running());
397 job_e->Finish();
398
399 Expect("a.c.e.");
400 }
401
TEST_F(PrioritizedDispatcherTest,EvictFromEmpty)402 TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
403 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
404 Prepare(limits);
405 EXPECT_TRUE(dispatcher_->EvictOldestLowest() == nullptr);
406 }
407
TEST_F(PrioritizedDispatcherTest,AddWhileZeroLimits)408 TEST_F(PrioritizedDispatcherTest, AddWhileZeroLimits) {
409 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
410 Prepare(limits);
411
412 dispatcher_->SetLimitsToZero();
413 std::unique_ptr<TestJob> job_a = AddJob('a', LOW);
414 std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
415 std::unique_ptr<TestJob> job_c = AddJobAtHead('c', MEDIUM);
416
417 EXPECT_EQ(0u, dispatcher_->num_running_jobs());
418 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
419
420 dispatcher_->SetLimits(limits);
421 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
422 EXPECT_EQ(1u, dispatcher_->num_queued_jobs());
423
424 ASSERT_TRUE(job_b->running());
425 job_b->Finish();
426
427 ASSERT_TRUE(job_c->running());
428 job_c->Finish();
429
430 ASSERT_TRUE(job_a->running());
431 job_a->Finish();
432
433 Expect("cb.a..");
434 }
435
TEST_F(PrioritizedDispatcherTest,ReduceLimitsWhileJobQueued)436 TEST_F(PrioritizedDispatcherTest, ReduceLimitsWhileJobQueued) {
437 PrioritizedDispatcher::Limits initial_limits(NUM_PRIORITIES, 2);
438 Prepare(initial_limits);
439
440 std::unique_ptr<TestJob> job_a = AddJob('a', MEDIUM);
441 std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
442 std::unique_ptr<TestJob> job_c = AddJob('c', MEDIUM);
443 std::unique_ptr<TestJob> job_d = AddJob('d', MEDIUM);
444 std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM);
445
446 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
447 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
448
449 // Reduce limits to just allow one job at a time. Running jobs should not
450 // be affected.
451 dispatcher_->SetLimits(PrioritizedDispatcher::Limits(NUM_PRIORITIES, 1));
452
453 EXPECT_EQ(2u, dispatcher_->num_running_jobs());
454 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
455
456 // Finishing a job should not result in another job starting.
457 ASSERT_TRUE(job_a->running());
458 job_a->Finish();
459 EXPECT_EQ(1u, dispatcher_->num_running_jobs());
460 EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
461
462 ASSERT_TRUE(job_b->running());
463 job_b->Finish();
464 EXPECT_EQ(1u, dispatcher_->num_running_jobs());
465 EXPECT_EQ(2u, dispatcher_->num_queued_jobs());
466
467 // Increasing the limits again should let c start.
468 dispatcher_->SetLimits(initial_limits);
469
470 ASSERT_TRUE(job_c->running());
471 job_c->Finish();
472 ASSERT_TRUE(job_d->running());
473 job_d->Finish();
474 ASSERT_TRUE(job_e->running());
475 job_e->Finish();
476
477 Expect("ab..cd.e..");
478 }
479
TEST_F(PrioritizedDispatcherTest,ZeroLimitsThenCancel)480 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenCancel) {
481 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
482 Prepare(limits);
483
484 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
485 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
486 std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
487 dispatcher_->SetLimitsToZero();
488
489 ASSERT_TRUE(job_a->running());
490 EXPECT_FALSE(job_b->running());
491 EXPECT_FALSE(job_c->running());
492 job_a->Finish();
493
494 EXPECT_FALSE(job_b->running());
495 EXPECT_FALSE(job_c->running());
496
497 // Cancelling b shouldn't start job c.
498 job_b->Cancel();
499 EXPECT_FALSE(job_c->running());
500
501 // Restoring the limits should start c.
502 dispatcher_->SetLimits(limits);
503 ASSERT_TRUE(job_c->running());
504 job_c->Finish();
505
506 Expect("a.c.");
507 }
508
TEST_F(PrioritizedDispatcherTest,ZeroLimitsThenIncreasePriority)509 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenIncreasePriority) {
510 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
511 limits.reserved_slots[HIGHEST] = 1;
512 Prepare(limits);
513
514 std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
515 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
516 EXPECT_TRUE(job_a->running());
517 EXPECT_FALSE(job_b->running());
518 dispatcher_->SetLimitsToZero();
519
520 job_b->ChangePriority(HIGHEST);
521 EXPECT_FALSE(job_b->running());
522 job_a->Finish();
523 EXPECT_FALSE(job_b->running());
524
525 job_b->Cancel();
526 Expect("a.");
527 }
528
529 #if GTEST_HAS_DEATH_TEST
TEST_F(PrioritizedDispatcherTest,CancelNull)530 TEST_F(PrioritizedDispatcherTest, CancelNull) {
531 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
532 Prepare(limits);
533 EXPECT_DCHECK_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()));
534 }
535
TEST_F(PrioritizedDispatcherTest,CancelMissing)536 TEST_F(PrioritizedDispatcherTest, CancelMissing) {
537 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
538 Prepare(limits);
539 AddJob('a', IDLE);
540 std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
541 PrioritizedDispatcher::Handle handle = job_b->handle();
542 ASSERT_FALSE(handle.is_null());
543 dispatcher_->Cancel(handle);
544 EXPECT_DCHECK_DEATH(dispatcher_->Cancel(handle));
545 }
546 #endif // GTEST_HAS_DEATH_TEST
547
548 } // namespace
549
550 } // namespace net
551