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 366
