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 template <typename T>
 201 struct Greater {
 202   const T rhs;
 203   std::list<T> *removed;
 204   Greater(const T &v, std::list<T> *removed) : rhs(v), removed(removed) {}
 205   bool operator()(const T &lhs) {
 206     if (std::get<2>(lhs) > std::get<2>(rhs)) {
 207       if (removed)
 208         removed->push_back(lhs);
 209       return true;
 210     } else {
 211       return false;
 212     }
 213   }
 214 };
 215
 216 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_filter_null) {
 217   WQ wq(0, 0);
 218   LQ strictq, normq;
 219   unsigned num_items = 100;
 220   fill_queue(wq, strictq, normq, num_items);
 221   // Pick a value that we didn't enqueue
 222   Removed wq_removed;
 223   Greater<Item> pred(std::make_tuple(0, 0, 1 << 17), &wq_removed);
 224   wq.remove_by_filter(pred);
 225   EXPECT_EQ(0u, wq_removed.size());
 226 }
 227
 228 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_filter) {
 229   WQ wq(0, 0);
 230   LQ strictq, normq;
 231   unsigned num_items = 1000;
 232   fill_queue(wq, strictq, normq, num_items);
 233   Greater<Item> pred2(std::make_tuple(0, 0, (1 << 16) - (1 << 16)/10), nullptr);
 234   Removed r_strictq, r_normq;
 235   unsigned num_to_remove = 0;
 236   // Figure out from what has been queued what we
 237   // expect to be removed
 238   for (LQ::iterator pi = strictq.begin();
 239        pi != strictq.end(); ++pi) {
 240     for (KlassItem::iterator ki = pi->second.begin();
 241          ki != pi->second.end(); ++ki) {
 242       for (ItemList::iterator li = ki->second.begin();
 243            li != ki->second.end(); ++li) {
 244         if (pred2(li->second)) {
 245           ++num_to_remove;
 246         }
 247       }
 248     }
 249   }
 250   for (LQ::iterator pi = normq.begin();
 251        pi != normq.end(); ++pi) {
 252     for (KlassItem::iterator ki = pi->second.begin();
 253          ki != pi->second.end(); ++ki) {
 254       for (ItemList::iterator li = ki->second.begin();
 255            li != ki->second.end(); ++li) {
 256         if (pred2(li->second)) {
 257           ++num_to_remove;
 258         }
 259       }
 260     }
 261   }
 262   Removed wq_removed;
 263   Greater<Item> pred(
 264     std::make_tuple(0, 0, (1 << 16) - (1 << 16)/10),
 265     &wq_removed);
 266   wq.remove_by_filter(pred);
 267   // Check that what was removed was correct
 268   for (Removed::iterator it = wq_removed.begin();
 269        it != wq_removed.end(); ++it) {
 270     EXPECT_TRUE(pred2(*it));
 271   }
 272   EXPECT_EQ(num_to_remove, wq_removed.size());
 273   EXPECT_EQ(num_items - num_to_remove, wq.length());
 274   // Make sure that none were missed
 275   while (!(wq.empty())) {
 276     EXPECT_FALSE(pred(wq.dequeue()));
 277   }
 278 }
 279
 280 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class_null) {
 281   WQ wq(0, 0);
 282   LQ strictq, normq;
 283   unsigned num_items = 10;
 284   fill_queue(wq, strictq, normq, num_items);
 285   Removed wq_removed;
 286   // Pick a klass that was not enqueued
 287   wq.remove_by_class(klasses + 1, &wq_removed);
 288   EXPECT_EQ(0u, wq_removed.size());
 289 }
 290
 291 TEST_F(WeightedPriorityQueueTest, wpq_test_remove_by_class) {
 292   WQ wq(0, 0);
 293   LQ strictq, normq;
 294   unsigned num_items = 1000;
 295   fill_queue(wq, strictq, normq, num_items);
 296   unsigned num_to_remove = 0;
 297   const Klass k = 5;
 298   // Find how many ops are in the class
 299   for (LQ::iterator it = strictq.begin();
 300        it != strictq.end(); ++it) {
 301     num_to_remove += it->second[k].size();
 302   }
 303   for (LQ::iterator it = normq.begin();
 304        it != normq.end(); ++it) {
 305     num_to_remove += it->second[k].size();
 306   }
 307   Removed wq_removed;
 308   wq.remove_by_class(k, &wq_removed);
 309   // Check that the right ops were removed.
 310   EXPECT_EQ(num_to_remove, wq_removed.size());
 311   EXPECT_EQ(num_items - num_to_remove, wq.length());
 312   for (Removed::iterator it = wq_removed.begin();
 313        it != wq_removed.end(); ++it) {
 314     EXPECT_EQ(k, std::get<1>(*it));
 315   }
 316   // Check that none were missed
 317   while (!(wq.empty())) {
 318     EXPECT_NE(k, std::get<1>(wq.dequeue()));
 319   }
 320 }