ceph/src/test/common/test_weighted_priority_queue.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include "gtest/gtest.h"
   5 #include "common/Formatter.h"
   6 #include "common/WeightedPriorityQueue.h"
   7
   8 #include <numeric>
   9 #include <vector>
  10 #include <map>
  11 #include <list>
  12 #include <tuple>
  13
  14 #define CEPH_OP_CLASS_STRICT    0
  15 #define CEPH_OP_CLASS_NORMAL    0
  16 #define CEPH_OP_QUEUE_BACK      0
  17 #define CEPH_OP_QUEUE_FRONT     0
  18
  19 class WeightedPriorityQueueTest : public testing::Test
  20 {
  21 protected:
  22   typedef unsigned Klass;
  23   // tuple<Prio, Klass, OpID> so that we can verfiy the op
  24   typedef std::tuple<unsigned, unsigned, unsigned> Item;
  25   typedef unsigned Prio;
  26   typedef unsigned Kost;
  27   typedef WeightedPriorityQueue<Item, Klass> WQ;
  28   // Simulate queue structure
  29   typedef std::list<std::pair<Kost, Item> > ItemList;
  30   typedef std::map<Klass, ItemList> KlassItem;
  31   typedef std::map<Prio, KlassItem> LQ;
  32   typedef std::list<Item> Removed;
  33   const unsigned max_prios = 5; // (0-4) * 64
  34   const unsigned klasses = 37;  // Make prime to help get good coverage
  35
  36   void fill_queue(WQ &wq, LQ &strictq, LQ &normq,
  37       unsigned item_size, bool randomize = false) {
  38     unsigned p, k, c, o, op_queue, fob;
  39     for (unsigned i = 1; i <= item_size; ++i) {
  40       // Choose priority, class, cost and 'op' for this op.
  41       if (randomize) {
  42         p = (rand() % max_prios) * 64;
  43         k = rand() % klasses;
  44         c = rand() % (1<<22);  // 4M cost
  45         // Make some of the costs 0, but make sure small costs
  46         // still work ok.
  47         if (c > (1<<19) && c < (1<<20)) {
  48           c = 0;
  49         }
  50         op_queue = rand() % 10;
  51         fob = rand() % 10;
  52       } else {
  53         p = (i % max_prios) * 64;
  54         k = i % klasses;
  55         c = (i % 8 == 0 || i % 16 == 0) ? 0 : 1 << (i % 23);
  56         op_queue = i % 7; // Use prime numbers to
  57         fob = i % 11;     // get better coverage
  58       }
  59       o = rand() % (1<<16);
  60       // Choose how to enqueue this op.
  61       switch (op_queue) {
  62       case 6 :
  63         // Strict Queue
  64         if (fob == 4) {
  65           // Queue to the front.
  66           strictq[p][k].push_front(std::make_pair(
  67             c, std::make_tuple(p, k, o)));
  68           wq.enqueue_strict_front(Klass(k), p, std::make_tuple(p, k, o));
  69         } else {
  70           //Queue to the back.
  71           strictq[p][k].push_back(std::make_pair(
  72             c, std::make_tuple(p, k, o)));
  73           wq.enqueue_strict(Klass(k), p, std::make_tuple(p, k, o));
  74         }
  75         break;
  76       default:
  77         // Normal queue
  78         if (fob == 4) {
  79           // Queue to the front.
  80           normq[p][k].push_front(std::make_pair(
  81             c, std::make_tuple(p, k, o)));
  82           wq.enqueue_front(Klass(k), p, c, std::make_tuple(p, k, o));
  83         } else {
  84           //Queue to the back.
  85           normq[p][k].push_back(std::make_pair(
  86             c, std::make_tuple(p, k, o)));
  87           wq.enqueue(Klass(k), p, c, std::make_tuple(p, k, o));
  88         }
  89         break;
  90       }
  91     }
  92   }
  93   void test_queue(unsigned item_size, bool randomize = false) {
  94     // Due to the WRR queue having a lot of probabilistic logic
  95     // we can't determine the exact order OPs will be dequeued.
  96     // However, the queue should not dequeue a priority out of
  97     // order. It should also dequeue the strict priority queue
  98     // first and in order. In both the strict and normal queues
  99     // push front and back should be respected. Here we keep
 100     // track of the ops queued and make sure they dequeue
 101     // correctly.
 102
 103     // Set up local tracking queues
 104     WQ wq(0, 0);
 105     LQ strictq, normq;
 106     fill_queue(wq, strictq, normq, item_size, randomize);
 107     // Test that the queue is dequeuing properly.
 108     typedef std::map<unsigned, unsigned> LastKlass;
 109     LastKlass last_strict, last_norm;
 110     while (!(wq.empty())) {
 111       Item r = wq.dequeue();
 112       if (!(strictq.empty())) {
 113         // Check that there are no higher priorities
 114         // in the strict queue.
 115         LQ::reverse_iterator ri = strictq.rbegin();
 116         EXPECT_EQ(std::get<0>(r), ri->first);
 117         // Check that if there are multiple classes in a priority
 118         // that it is not dequeueing the same class each time.
 119         LastKlass::iterator si = last_strict.find(std::get<0>(r));
 120         if (strictq[std::get<0>(r)].size() > 1 && si != last_strict.end()) {
 121           EXPECT_NE(std::get<1>(r), si->second);
 122         }
 123         last_strict[std::get<0>(r)] = std::get<1>(r);
 124
 125         Item t = strictq[std::get<0>(r)][std::get<1>(r)].front().second;
 126         EXPECT_EQ(std::get<2>(r), std::get<2>(t));
 127         strictq[std::get<0>(r)][std::get<1>(r)].pop_front();
 128         if (strictq[std::get<0>(r)][std::get<1>(r)].empty()) {
 129           strictq[std::get<0>(r)].erase(std::get<1>(r));
 130         }
 131         if (strictq[std::get<0>(r)].empty()) {
 132           strictq.erase(std::get<0>(r));
 133         }
 134       } else {
 135         // Check that if there are multiple classes in a priority
 136         // that it is not dequeueing the same class each time.
 137         LastKlass::iterator si = last_norm.find(std::get<0>(r));
 138         if (normq[std::get<0>(r)].size() > 1 && si != last_norm.end()) {
 139           EXPECT_NE(std::get<1>(r), si->second);
 140         }
 141         last_norm[std::get<0>(r)] = std::get<1>(r);
 142
 143         Item t = normq[std::get<0>(r)][std::get<1>(r)].front().second;
 144         EXPECT_EQ(std::get<2>(r), std::get<2>(t));
 145         normq[std::get<0>(r)][std::get<1>(r)].pop_front();
 146         if (normq[std::get<0>(r)][std::get<1>(r)].empty()) {
 147           normq[std::get<0>(r)].erase(std::get<1>(r));
 148         }
 149         if (normq[std::get<0>(r)].empty()) {
 150           normq.erase(std::get<0>(r));
 151         }
 152       }
 153     }
 154   }
 155
 156   void SetUp() override {
 157     srand(time(0));
 158   }
 159   void TearDown() override {
 160   }
 161 };
 162
 163 TEST_F(WeightedPriorityQueueTest, wpq_size){
 164   WQ wq(0, 0);
 165   EXPECT_TRUE(wq.empty());
 166   EXPECT_EQ(0u, wq.length());
 167
 168   // Test the strict queue size.
 169   for (unsigned i = 1; i < 5; ++i) {
 170     wq.enqueue_strict(Klass(i),i, std::make_tuple(i, i, i));
 171     EXPECT_FALSE(wq.empty());
 172     EXPECT_EQ(i, wq.length());
 173   }
 174   // Test the normal queue size.
 175   for (unsigned i = 5; i < 10; ++i) {
 176     wq.enqueue(Klass(i), i, i, std::make_tuple(i, i, i));
 177     EXPECT_FALSE(wq.empty());
 178     EXPECT_EQ(i, wq.length());
 179   }
 180   // Test that as both queues are emptied
 181   // the size is correct.
 182   for (unsigned i = 8; i >0; --i) {
 183     wq.dequeue();
 184     EXPECT_FALSE(wq.empty());
 185     EXPECT_EQ(i, wq.length());
 186   }
 187   wq.dequeue();
 188   EXPECT_TRUE(wq.empty());
 189   EXPECT_EQ(0u, wq.length());
 190 }
 191
 192 TEST_F(WeightedPriorityQueueTest, wpq_test_static) {
 193   test_queue(1000);
 194 }
 195
 196 TEST_F(WeightedPriorityQueueTest, wpq_test_random) {
 197   test_queue(rand() % 500 + 500, true);
 198 }
 199
 200 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class_null) {
 201   WQ wq(0, 0);
 202   LQ strictq, normq;
 203   unsigned num_items = 10;
 204   fill_queue(wq, strictq, normq, num_items);
 205   Removed wq_removed;
 206   // Pick a klass that was not enqueued
 207   wq.remove_by_class(klasses + 1, &wq_removed);
 208   EXPECT_EQ(0u, wq_removed.size());
 209 }
 210
 211 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class) {
 212   WQ wq(0, 0);
 213   LQ strictq, normq;
 214   unsigned num_items = 1000;
 215   fill_queue(wq, strictq, normq, num_items);
 216   unsigned num_to_remove = 0;
 217   const Klass k = 5;
 218   // Find how many ops are in the class
 219   for (LQ::iterator it = strictq.begin();
 220        it != strictq.end(); ++it) {
 221     num_to_remove += it->second[k].size();
 222   }
 223   for (LQ::iterator it = normq.begin();
 224        it != normq.end(); ++it) {
 225     num_to_remove += it->second[k].size();
 226   }
 227   Removed wq_removed;
 228   wq.remove_by_class(k, &wq_removed);
 229   // Check that the right ops were removed.
 230   EXPECT_EQ(num_to_remove, wq_removed.size());
 231   EXPECT_EQ(num_items - num_to_remove, wq.length());
 232   for (Removed::iterator it = wq_removed.begin();
 233        it != wq_removed.end(); ++it) {
 234     EXPECT_EQ(k, std::get<1>(*it));
 235   }
 236   // Check that none were missed
 237   while (!(wq.empty())) {
 238     EXPECT_NE(k, std::get<1>(wq.dequeue()));
 239   }
 240 }