From 3ba54cc483b70a62ffae3c72b2de6d75fa97bc42 Mon Sep 17 00:00:00 2001 From: Robert LeBlanc Date: Fri, 18 Dec 2015 21:06:43 +0000 Subject: [PATCH] test/commom/test_weighted_priority_queue.cc: Add unit tests for the new Weighted Priority Queue. Signed-Off-By: Robert LeBlanc --- src/test/CMakeLists.txt | 12 + src/test/Makefile.am | 4 + .../common/test_weighted_priority_queue.cc | 287 ++++++++++++++++++ 3 files changed, 303 insertions(+) create mode 100644 src/test/common/test_weighted_priority_queue.cc diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 82377732e4a..3bfa3116303 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -488,6 +488,18 @@ target_link_libraries(unittest_prioritized_queue global set_target_properties(unittest_prioritized_queue PROPERTIES COMPILE_FLAGS ${UNITTEST_CXX_FLAGS}) +# unittest_weighted_priority_queue +add_executable(unittest_weighted_priority_queue EXCLUDE_FROM_ALL + common/test_weighted_priority_queue.cc + $ + ) +add_test(unittest_weighted_priority_queue unittest_weighted_priority_queue) +add_dependencies(check unittest_weighted_priority_queue) +target_link_libraries(unittest_weighted_priority_queue global + ${BLKID_LIBRARIES} ${CMAKE_DL_LIBS} ${TCMALLOC_LIBS} ${UNITTEST_LIBS}) +set_target_properties(unittest_weighted_priority_queue + PROPERTIES COMPILE_FLAGS ${UNITTEST_CXX_FLAGS}) + # unittest_str_map add_executable(unittest_str_map EXCLUDE_FROM_ALL common/test_str_map.cc diff --git a/src/test/Makefile.am b/src/test/Makefile.am index ab665040060..af52a93ba37 100644 --- a/src/test/Makefile.am +++ b/src/test/Makefile.am @@ -168,6 +168,10 @@ unittest_prioritized_queue_CXXFLAGS = $(UNITTEST_CXXFLAGS) unittest_prioritized_queue_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) check_TESTPROGRAMS += unittest_prioritized_queue +unittest_weighted_priority_queue_SOURCES = test/common/test_weighted_priority_queue.cc +unittest_weighted_priority_queue_CXXFLAGS = $(UNITTEST_CXXFLAGS) +unittest_weighted_priority_queue_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL) +check_TESTPROGRAMS += unittest_weighted_priority_queue unittest_str_map_SOURCES = test/common/test_str_map.cc unittest_str_map_CXXFLAGS = $(UNITTEST_CXXFLAGS) diff --git a/src/test/common/test_weighted_priority_queue.cc b/src/test/common/test_weighted_priority_queue.cc new file mode 100644 index 00000000000..d3ebc4199cf --- /dev/null +++ b/src/test/common/test_weighted_priority_queue.cc @@ -0,0 +1,287 @@ +// -*- 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)); + } + } + } + } + + virtual void SetUp() { + srand(time(0)); + } + virtual void TearDown() { + } +}; + +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); +} + +template +struct Greater { + const T rhs; + Greater(const T &v) : rhs(v) {} + bool operator()(const T &lhs) const { + return std::get<2>(lhs) > std::get<2>(rhs); + } +}; + +TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_filter) { + WQ wq(0, 0); + LQ strictq, normq; + unsigned num_items = 1000; + fill_queue(wq, strictq, normq, num_items); + const Greater pred(std::make_tuple(0, 0, (1 << 16) - (1 << 16)/10)); + Removed r_strictq, r_normq; + unsigned num_to_remove = 0; + // Figure out from what has been queued what we + // expect to be removed + for (LQ::iterator pi = strictq.begin(); + pi != strictq.end(); ++pi) { + for (KlassItem::iterator ki = pi->second.begin(); + ki != pi->second.end(); ++ki) { + for (ItemList::iterator li = ki->second.begin(); + li != ki->second.end(); ++li) { + if (pred(li->second)) { + ++num_to_remove; + } + } + } + } + for (LQ::iterator pi = normq.begin(); + pi != normq.end(); ++pi) { + for (KlassItem::iterator ki = pi->second.begin(); + ki != pi->second.end(); ++ki) { + for (ItemList::iterator li = ki->second.begin(); + li != ki->second.end(); ++li) { + if (pred(li->second)) { + ++num_to_remove; + } + } + } + } + Removed wq_removed; + wq.remove_by_filter(pred, &wq_removed); + // Check that what was removed was correct + for (Removed::iterator it = wq_removed.begin(); + it != wq_removed.end(); ++it) { + EXPECT_TRUE(pred(*it)); + } + EXPECT_EQ(num_to_remove, wq_removed.size()); + EXPECT_EQ(num_items - num_to_remove, wq.length()); + // Make sure that none were missed + while (!(wq.empty())) { + EXPECT_FALSE(pred(wq.dequeue())); + } +} + +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())); + } +} -- 2.47.3