net/base/prioritized_dispatcher_unittest.cc

   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
  16 namespace net {
  17
  18 namespace {
  19
  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 &&
  24                IDLE < LOWEST &&
  25                LOWEST < HIGHEST &&
  26                HIGHEST <= MAXIMUM_PRIORITY,
  27                priority_indexes_incompatible);
  28
  29 class 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
 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);
 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
 204 TEST_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
 226 TEST_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
 250 TEST_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
 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;
 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
 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;
 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
 356 TEST_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
 381 TEST_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
 404 TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
 405   PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
 406   Prepare(limits);
 407   EXPECT_TRUE(dispatcher_->EvictOldestLowest() == NULL);
 408 }
 409
 410 TEST_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
 438 TEST_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
 482 TEST_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
 511 TEST_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)
 532 TEST_F(PrioritizedDispatcherTest, CancelNull) {
 533   PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
 534   Prepare(limits);
 535   EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), "");
 536 }
 537
 538 TEST_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
 551 TEST_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