X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Ftest%2Fcommon%2Ftest_weighted_priority_queue.cc;fp=src%2Fceph%2Fsrc%2Ftest%2Fcommon%2Ftest_weighted_priority_queue.cc;h=0000000000000000000000000000000000000000;hb=7da45d65be36d36b880cc55c5036e96c24b53f00;hp=9bb87177147c69b30b128b8339e3f6749311e940;hpb=691462d09d0987b47e112d6ee8740375df3c51b2;p=stor4nfv.git diff --git a/src/ceph/src/test/common/test_weighted_priority_queue.cc b/src/ceph/src/test/common/test_weighted_priority_queue.cc deleted file mode 100644 index 9bb8717..0000000 --- a/src/ceph/src/test/common/test_weighted_priority_queue.cc +++ /dev/null @@ -1,240 +0,0 @@ -// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- -// vim: ts=8 sw=2 smarttab - -#include "gtest/gtest.h" -#include "common/Formatter.h" -#include "common/WeightedPriorityQueue.h" - -#include -#include -#include -#include -#include - -#define CEPH_OP_CLASS_STRICT 0 -#define CEPH_OP_CLASS_NORMAL 0 -#define CEPH_OP_QUEUE_BACK 0 -#define CEPH_OP_QUEUE_FRONT 0 - -class WeightedPriorityQueueTest : public testing::Test -{ -protected: - typedef unsigned Klass; - // tuple so that we can verfiy the op - typedef std::tuple Item; - typedef unsigned Prio; - typedef unsigned Kost; - typedef WeightedPriorityQueue WQ; - // Simulate queue structure - typedef std::list > ItemList; - typedef std::map KlassItem; - typedef std::map LQ; - typedef std::list Removed; - const unsigned max_prios = 5; // (0-4) * 64 - const unsigned klasses = 37; // Make prime to help get good coverage - - void fill_queue(WQ &wq, LQ &strictq, LQ &normq, - unsigned item_size, bool randomize = false) { - unsigned p, k, c, o, op_queue, fob; - for (unsigned i = 1; i <= item_size; ++i) { - // Choose priority, class, cost and 'op' for this op. - if (randomize) { - p = (rand() % max_prios) * 64; - k = rand() % klasses; - c = rand() % (1<<22); // 4M cost - // Make some of the costs 0, but make sure small costs - // still work ok. - if (c > (1<<19) && c < (1<<20)) { - c = 0; - } - op_queue = rand() % 10; - fob = rand() % 10; - } else { - p = (i % max_prios) * 64; - k = i % klasses; - c = (i % 8 == 0 || i % 16 == 0) ? 0 : 1 << (i % 23); - op_queue = i % 7; // Use prime numbers to - fob = i % 11; // get better coverage - } - o = rand() % (1<<16); - // Choose how to enqueue this op. - switch (op_queue) { - case 6 : - // Strict Queue - if (fob == 4) { - // Queue to the front. - strictq[p][k].push_front(std::make_pair( - c, std::make_tuple(p, k, o))); - wq.enqueue_strict_front(Klass(k), p, std::make_tuple(p, k, o)); - } else { - //Queue to the back. - strictq[p][k].push_back(std::make_pair( - c, std::make_tuple(p, k, o))); - wq.enqueue_strict(Klass(k), p, std::make_tuple(p, k, o)); - } - break; - default: - // Normal queue - if (fob == 4) { - // Queue to the front. - normq[p][k].push_front(std::make_pair( - c, std::make_tuple(p, k, o))); - wq.enqueue_front(Klass(k), p, c, std::make_tuple(p, k, o)); - } else { - //Queue to the back. - normq[p][k].push_back(std::make_pair( - c, std::make_tuple(p, k, o))); - wq.enqueue(Klass(k), p, c, std::make_tuple(p, k, o)); - } - break; - } - } - } - void test_queue(unsigned item_size, bool randomize = false) { - // Due to the WRR queue having a lot of probabilistic logic - // we can't determine the exact order OPs will be dequeued. - // However, the queue should not dequeue a priority out of - // order. It should also dequeue the strict priority queue - // first and in order. In both the strict and normal queues - // push front and back should be respected. Here we keep - // track of the ops queued and make sure they dequeue - // correctly. - - // Set up local tracking queues - WQ wq(0, 0); - LQ strictq, normq; - fill_queue(wq, strictq, normq, item_size, randomize); - // Test that the queue is dequeuing properly. - typedef std::map LastKlass; - LastKlass last_strict, last_norm; - while (!(wq.empty())) { - Item r = wq.dequeue(); - if (!(strictq.empty())) { - // Check that there are no higher priorities - // in the strict queue. - LQ::reverse_iterator ri = strictq.rbegin(); - EXPECT_EQ(std::get<0>(r), ri->first); - // Check that if there are multiple classes in a priority - // that it is not dequeueing the same class each time. - LastKlass::iterator si = last_strict.find(std::get<0>(r)); - if (strictq[std::get<0>(r)].size() > 1 && si != last_strict.end()) { - EXPECT_NE(std::get<1>(r), si->second); - } - last_strict[std::get<0>(r)] = std::get<1>(r); - - Item t = strictq[std::get<0>(r)][std::get<1>(r)].front().second; - EXPECT_EQ(std::get<2>(r), std::get<2>(t)); - strictq[std::get<0>(r)][std::get<1>(r)].pop_front(); - if (strictq[std::get<0>(r)][std::get<1>(r)].empty()) { - strictq[std::get<0>(r)].erase(std::get<1>(r)); - } - if (strictq[std::get<0>(r)].empty()) { - strictq.erase(std::get<0>(r)); - } - } else { - // Check that if there are multiple classes in a priority - // that it is not dequeueing the same class each time. - LastKlass::iterator si = last_norm.find(std::get<0>(r)); - if (normq[std::get<0>(r)].size() > 1 && si != last_norm.end()) { - EXPECT_NE(std::get<1>(r), si->second); - } - last_norm[std::get<0>(r)] = std::get<1>(r); - - Item t = normq[std::get<0>(r)][std::get<1>(r)].front().second; - EXPECT_EQ(std::get<2>(r), std::get<2>(t)); - normq[std::get<0>(r)][std::get<1>(r)].pop_front(); - if (normq[std::get<0>(r)][std::get<1>(r)].empty()) { - normq[std::get<0>(r)].erase(std::get<1>(r)); - } - if (normq[std::get<0>(r)].empty()) { - normq.erase(std::get<0>(r)); - } - } - } - } - - void SetUp() override { - srand(time(0)); - } - void TearDown() override { - } -}; - -TEST_F(WeightedPriorityQueueTest, wpq_size){ - WQ wq(0, 0); - EXPECT_TRUE(wq.empty()); - EXPECT_EQ(0u, wq.length()); - - // Test the strict queue size. - for (unsigned i = 1; i < 5; ++i) { - wq.enqueue_strict(Klass(i),i, std::make_tuple(i, i, i)); - EXPECT_FALSE(wq.empty()); - EXPECT_EQ(i, wq.length()); - } - // Test the normal queue size. - for (unsigned i = 5; i < 10; ++i) { - wq.enqueue(Klass(i), i, i, std::make_tuple(i, i, i)); - EXPECT_FALSE(wq.empty()); - EXPECT_EQ(i, wq.length()); - } - // Test that as both queues are emptied - // the size is correct. - for (unsigned i = 8; i >0; --i) { - wq.dequeue(); - EXPECT_FALSE(wq.empty()); - EXPECT_EQ(i, wq.length()); - } - wq.dequeue(); - EXPECT_TRUE(wq.empty()); - EXPECT_EQ(0u, wq.length()); -} - -TEST_F(WeightedPriorityQueueTest, wpq_test_static) { - test_queue(1000); -} - -TEST_F(WeightedPriorityQueueTest, wpq_test_random) { - test_queue(rand() % 500 + 500, true); -} - -TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class_null) { - WQ wq(0, 0); - LQ strictq, normq; - unsigned num_items = 10; - fill_queue(wq, strictq, normq, num_items); - Removed wq_removed; - // Pick a klass that was not enqueued - wq.remove_by_class(klasses + 1, &wq_removed); - EXPECT_EQ(0u, wq_removed.size()); -} - -TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class) { - WQ wq(0, 0); - LQ strictq, normq; - unsigned num_items = 1000; - fill_queue(wq, strictq, normq, num_items); - unsigned num_to_remove = 0; - const Klass k = 5; - // Find how many ops are in the class - for (LQ::iterator it = strictq.begin(); - it != strictq.end(); ++it) { - num_to_remove += it->second[k].size(); - } - for (LQ::iterator it = normq.begin(); - it != normq.end(); ++it) { - num_to_remove += it->second[k].size(); - } - Removed wq_removed; - wq.remove_by_class(k, &wq_removed); - // Check that the right ops were removed. - EXPECT_EQ(num_to_remove, wq_removed.size()); - EXPECT_EQ(num_items - num_to_remove, wq.length()); - for (Removed::iterator it = wq_removed.begin(); - it != wq_removed.end(); ++it) { - EXPECT_EQ(k, std::get<1>(*it)); - } - // Check that none were missed - while (!(wq.empty())) { - EXPECT_NE(k, std::get<1>(wq.dequeue())); - } -}