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 < NUM_PRIORITIES,
  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() {
  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
 159 TEST_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
 181 TEST_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
 205 TEST_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
 247 TEST_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
 273 TEST_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
 298 TEST_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
 321 TEST_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)
 328 TEST_F(PrioritizedDispatcherTest, CancelNull) {
 329   PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
 330   Prepare(limits);
 331   EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), "");
 332 }
 333
 334 TEST_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
 347 TEST_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