123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552 |
- // Copyright (c) 2012 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "net/base/prioritized_dispatcher.h"
- #include <ctype.h>
- #include <memory>
- #include <string>
- #include "base/check.h"
- #include "base/compiler_specific.h"
- #include "base/memory/raw_ptr.h"
- #include "base/test/gtest_util.h"
- #include "net/base/request_priority.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace net {
- namespace {
- // We rely on the priority enum values being sequential having starting at 0,
- // and increasing for higher priorities.
- static_assert(MINIMUM_PRIORITY == 0u && MINIMUM_PRIORITY == THROTTLED &&
- THROTTLED < IDLE &&
- IDLE < LOWEST &&
- LOWEST < HIGHEST &&
- HIGHEST <= MAXIMUM_PRIORITY,
- "priority indexes incompatible");
- class PrioritizedDispatcherTest : public testing::Test {
- public:
- typedef PrioritizedDispatcher::Priority Priority;
- // A job that appends |tag| to |log| when started and '.' when finished.
- // This is intended to confirm the execution order of a sequence of jobs added
- // to the dispatcher. Note that finishing order of jobs does not matter.
- class TestJob : public PrioritizedDispatcher::Job {
- public:
- TestJob(PrioritizedDispatcher* dispatcher,
- char tag,
- Priority priority,
- std::string* log)
- : dispatcher_(dispatcher), tag_(tag), priority_(priority), log_(log) {}
- bool running() const {
- return running_;
- }
- const PrioritizedDispatcher::Handle handle() const {
- return handle_;
- }
- void Add(bool at_head) {
- CHECK(handle_.is_null());
- CHECK(!running_);
- size_t num_queued = dispatcher_->num_queued_jobs();
- size_t num_running = dispatcher_->num_running_jobs();
- if (!at_head) {
- handle_ = dispatcher_->Add(this, priority_);
- } else {
- handle_ = dispatcher_->AddAtHead(this, priority_);
- }
- if (handle_.is_null()) {
- EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
- EXPECT_TRUE(running_);
- EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
- } else {
- EXPECT_FALSE(running_);
- EXPECT_EQ(priority_, handle_.priority());
- EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
- EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
- }
- }
- void ChangePriority(Priority priority) {
- CHECK(!handle_.is_null());
- CHECK(!running_);
- size_t num_queued = dispatcher_->num_queued_jobs();
- size_t num_running = dispatcher_->num_running_jobs();
- handle_ = dispatcher_->ChangePriority(handle_, priority);
- if (handle_.is_null()) {
- EXPECT_TRUE(running_);
- EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
- EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs());
- } else {
- EXPECT_FALSE(running_);
- EXPECT_EQ(priority, handle_.priority());
- EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_);
- EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs());
- EXPECT_EQ(num_running, dispatcher_->num_running_jobs());
- }
- }
- void Cancel() {
- CHECK(!handle_.is_null());
- CHECK(!running_);
- size_t num_queued = dispatcher_->num_queued_jobs();
- dispatcher_->Cancel(handle_);
- EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs());
- handle_ = PrioritizedDispatcher::Handle();
- }
- void Finish() {
- CHECK(running_);
- running_ = false;
- log_->append(1u, '.');
- dispatcher_->OnJobFinished();
- }
- // PrioritizedDispatcher::Job interface
- void Start() override {
- EXPECT_FALSE(running_);
- handle_ = PrioritizedDispatcher::Handle();
- running_ = true;
- log_->append(1u, tag_);
- }
- private:
- raw_ptr<PrioritizedDispatcher> dispatcher_;
- char tag_;
- Priority priority_;
- PrioritizedDispatcher::Handle handle_;
- bool running_ = false;
- raw_ptr<std::string> log_;
- };
- protected:
- void Prepare(const PrioritizedDispatcher::Limits& limits) {
- dispatcher_ = std::make_unique<PrioritizedDispatcher>(limits);
- }
- std::unique_ptr<TestJob> AddJob(char data, Priority priority) {
- auto job =
- std::make_unique<TestJob>(dispatcher_.get(), data, priority, &log_);
- job->Add(false);
- return job;
- }
- std::unique_ptr<TestJob> AddJobAtHead(char data, Priority priority) {
- auto job =
- std::make_unique<TestJob>(dispatcher_.get(), data, priority, &log_);
- job->Add(true);
- return job;
- }
- void Expect(const std::string& log) {
- EXPECT_EQ(0u, dispatcher_->num_queued_jobs());
- EXPECT_EQ(0u, dispatcher_->num_running_jobs());
- EXPECT_EQ(log, log_);
- log_.clear();
- }
- std::string log_;
- std::unique_ptr<PrioritizedDispatcher> dispatcher_;
- };
- TEST_F(PrioritizedDispatcherTest, GetLimits) {
- // Set non-trivial initial limits.
- PrioritizedDispatcher::Limits original_limits(NUM_PRIORITIES, 5);
- original_limits.reserved_slots[HIGHEST] = 1;
- original_limits.reserved_slots[LOW] = 2;
- Prepare(original_limits);
- // Get current limits, make sure the original limits are returned.
- PrioritizedDispatcher::Limits retrieved_limits = dispatcher_->GetLimits();
- ASSERT_EQ(original_limits.total_jobs, retrieved_limits.total_jobs);
- ASSERT_EQ(static_cast<size_t>(NUM_PRIORITIES),
- retrieved_limits.reserved_slots.size());
- for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
- ++priority) {
- EXPECT_EQ(original_limits.reserved_slots[priority],
- retrieved_limits.reserved_slots[priority]);
- }
- // Set new limits.
- PrioritizedDispatcher::Limits new_limits(NUM_PRIORITIES, 6);
- new_limits.reserved_slots[MEDIUM] = 3;
- new_limits.reserved_slots[LOWEST] = 1;
- Prepare(new_limits);
- // Get current limits, make sure the new limits are returned.
- retrieved_limits = dispatcher_->GetLimits();
- ASSERT_EQ(new_limits.total_jobs, retrieved_limits.total_jobs);
- ASSERT_EQ(static_cast<size_t>(NUM_PRIORITIES),
- retrieved_limits.reserved_slots.size());
- for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY;
- ++priority) {
- EXPECT_EQ(new_limits.reserved_slots[priority],
- retrieved_limits.reserved_slots[priority]);
- }
- }
- TEST_F(PrioritizedDispatcherTest, AddAFIFO) {
- // Allow only one running job.
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
- std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
- std::unique_ptr<TestJob> job_d = AddJob('d', IDLE);
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_d->running());
- job_d->Finish();
- Expect("a.b.c.d.");
- }
- TEST_F(PrioritizedDispatcherTest, AddPriority) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
- std::unique_ptr<TestJob> job_c = AddJob('c', HIGHEST);
- std::unique_ptr<TestJob> job_d = AddJob('d', HIGHEST);
- std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM);
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_d->running());
- job_d->Finish();
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- Expect("a.c.d.b.e.");
- }
- TEST_F(PrioritizedDispatcherTest, AddAtHead) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', MEDIUM);
- std::unique_ptr<TestJob> job_b = AddJobAtHead('b', MEDIUM);
- std::unique_ptr<TestJob> job_c = AddJobAtHead('c', HIGHEST);
- std::unique_ptr<TestJob> job_d = AddJobAtHead('d', HIGHEST);
- std::unique_ptr<TestJob> job_e = AddJobAtHead('e', MEDIUM);
- std::unique_ptr<TestJob> job_f = AddJob('f', MEDIUM);
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_d->running());
- job_d->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- ASSERT_TRUE(job_f->running());
- job_f->Finish();
- Expect("a.d.c.e.b.f.");
- }
- TEST_F(PrioritizedDispatcherTest, EnforceLimits) {
- // Reserve 2 for HIGHEST and 1 for LOW or higher.
- // This leaves 2 for LOWEST or lower.
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 5);
- limits.reserved_slots[HIGHEST] = 2;
- limits.reserved_slots[LOW] = 1;
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE); // Uses unreserved slot.
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE); // Uses unreserved slot.
- std::unique_ptr<TestJob> job_c = AddJob('c', LOWEST); // Must wait.
- std::unique_ptr<TestJob> job_d = AddJob('d', LOW); // Uses reserved slot.
- std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM); // Must wait.
- std::unique_ptr<TestJob> job_f = AddJob('f', HIGHEST); // Uses reserved slot.
- std::unique_ptr<TestJob> job_g = AddJob('g', HIGHEST); // Uses reserved slot.
- std::unique_ptr<TestJob> job_h = AddJob('h', HIGHEST); // Must wait.
- EXPECT_EQ(5u, dispatcher_->num_running_jobs());
- EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
- ASSERT_TRUE(job_a->running());
- ASSERT_TRUE(job_b->running());
- ASSERT_TRUE(job_d->running());
- ASSERT_TRUE(job_f->running());
- ASSERT_TRUE(job_g->running());
- // a, b, d, f, g are running. Finish them in any order.
- job_b->Finish(); // Releases h.
- job_f->Finish();
- job_a->Finish();
- job_g->Finish(); // Releases e.
- job_d->Finish();
- ASSERT_TRUE(job_e->running());
- ASSERT_TRUE(job_h->running());
- // h, e are running.
- job_e->Finish(); // Releases c.
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- job_h->Finish();
- Expect("abdfg.h...e..c..");
- }
- TEST_F(PrioritizedDispatcherTest, ChangePriority) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
- // Reserve one slot only for HIGHEST priority requests.
- limits.reserved_slots[HIGHEST] = 1;
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', LOW);
- std::unique_ptr<TestJob> job_c = AddJob('c', MEDIUM);
- std::unique_ptr<TestJob> job_d = AddJob('d', MEDIUM);
- std::unique_ptr<TestJob> job_e = AddJob('e', IDLE);
- ASSERT_FALSE(job_b->running());
- ASSERT_FALSE(job_c->running());
- job_b->ChangePriority(MEDIUM);
- job_c->ChangePriority(LOW);
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_d->running());
- job_d->Finish();
- EXPECT_FALSE(job_e->running());
- // Increasing |job_e|'s priority to HIGHEST should result in it being
- // started immediately.
- job_e->ChangePriority(HIGHEST);
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- Expect("a.d.be..c.");
- }
- TEST_F(PrioritizedDispatcherTest, Cancel) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
- std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
- std::unique_ptr<TestJob> job_d = AddJob('d', IDLE);
- std::unique_ptr<TestJob> job_e = AddJob('e', IDLE);
- ASSERT_FALSE(job_b->running());
- ASSERT_FALSE(job_d->running());
- job_b->Cancel();
- job_d->Cancel();
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- Expect("a.c.e.");
- }
- TEST_F(PrioritizedDispatcherTest, Evict) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', LOW);
- std::unique_ptr<TestJob> job_c = AddJob('c', HIGHEST);
- std::unique_ptr<TestJob> job_d = AddJob('d', LOW);
- std::unique_ptr<TestJob> job_e = AddJob('e', HIGHEST);
- EXPECT_EQ(job_b.get(), dispatcher_->EvictOldestLowest());
- EXPECT_EQ(job_d.get(), dispatcher_->EvictOldestLowest());
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- Expect("a.c.e.");
- }
- TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- EXPECT_TRUE(dispatcher_->EvictOldestLowest() == nullptr);
- }
- TEST_F(PrioritizedDispatcherTest, AddWhileZeroLimits) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
- Prepare(limits);
- dispatcher_->SetLimitsToZero();
- std::unique_ptr<TestJob> job_a = AddJob('a', LOW);
- std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
- std::unique_ptr<TestJob> job_c = AddJobAtHead('c', MEDIUM);
- EXPECT_EQ(0u, dispatcher_->num_running_jobs());
- EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
- dispatcher_->SetLimits(limits);
- EXPECT_EQ(2u, dispatcher_->num_running_jobs());
- EXPECT_EQ(1u, dispatcher_->num_queued_jobs());
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- Expect("cb.a..");
- }
- TEST_F(PrioritizedDispatcherTest, ReduceLimitsWhileJobQueued) {
- PrioritizedDispatcher::Limits initial_limits(NUM_PRIORITIES, 2);
- Prepare(initial_limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', MEDIUM);
- std::unique_ptr<TestJob> job_b = AddJob('b', MEDIUM);
- std::unique_ptr<TestJob> job_c = AddJob('c', MEDIUM);
- std::unique_ptr<TestJob> job_d = AddJob('d', MEDIUM);
- std::unique_ptr<TestJob> job_e = AddJob('e', MEDIUM);
- EXPECT_EQ(2u, dispatcher_->num_running_jobs());
- EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
- // Reduce limits to just allow one job at a time. Running jobs should not
- // be affected.
- dispatcher_->SetLimits(PrioritizedDispatcher::Limits(NUM_PRIORITIES, 1));
- EXPECT_EQ(2u, dispatcher_->num_running_jobs());
- EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
- // Finishing a job should not result in another job starting.
- ASSERT_TRUE(job_a->running());
- job_a->Finish();
- EXPECT_EQ(1u, dispatcher_->num_running_jobs());
- EXPECT_EQ(3u, dispatcher_->num_queued_jobs());
- ASSERT_TRUE(job_b->running());
- job_b->Finish();
- EXPECT_EQ(1u, dispatcher_->num_running_jobs());
- EXPECT_EQ(2u, dispatcher_->num_queued_jobs());
- // Increasing the limits again should let c start.
- dispatcher_->SetLimits(initial_limits);
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- ASSERT_TRUE(job_d->running());
- job_d->Finish();
- ASSERT_TRUE(job_e->running());
- job_e->Finish();
- Expect("ab..cd.e..");
- }
- TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenCancel) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
- std::unique_ptr<TestJob> job_c = AddJob('c', IDLE);
- dispatcher_->SetLimitsToZero();
- ASSERT_TRUE(job_a->running());
- EXPECT_FALSE(job_b->running());
- EXPECT_FALSE(job_c->running());
- job_a->Finish();
- EXPECT_FALSE(job_b->running());
- EXPECT_FALSE(job_c->running());
- // Cancelling b shouldn't start job c.
- job_b->Cancel();
- EXPECT_FALSE(job_c->running());
- // Restoring the limits should start c.
- dispatcher_->SetLimits(limits);
- ASSERT_TRUE(job_c->running());
- job_c->Finish();
- Expect("a.c.");
- }
- TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenIncreasePriority) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2);
- limits.reserved_slots[HIGHEST] = 1;
- Prepare(limits);
- std::unique_ptr<TestJob> job_a = AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
- EXPECT_TRUE(job_a->running());
- EXPECT_FALSE(job_b->running());
- dispatcher_->SetLimitsToZero();
- job_b->ChangePriority(HIGHEST);
- EXPECT_FALSE(job_b->running());
- job_a->Finish();
- EXPECT_FALSE(job_b->running());
- job_b->Cancel();
- Expect("a.");
- }
- #if GTEST_HAS_DEATH_TEST
- TEST_F(PrioritizedDispatcherTest, CancelNull) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- EXPECT_DCHECK_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()));
- }
- TEST_F(PrioritizedDispatcherTest, CancelMissing) {
- PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1);
- Prepare(limits);
- AddJob('a', IDLE);
- std::unique_ptr<TestJob> job_b = AddJob('b', IDLE);
- PrioritizedDispatcher::Handle handle = job_b->handle();
- ASSERT_FALSE(handle.is_null());
- dispatcher_->Cancel(handle);
- EXPECT_DCHECK_DEATH(dispatcher_->Cancel(handle));
- }
- #endif // GTEST_HAS_DEATH_TEST
- } // namespace
- } // namespace net
|