src/ceph/src/test/common/test_prioritized_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/PrioritizedQueue.h"
   6
   7 #include <numeric>
   8 #include <vector>
   9 #include <algorithm>
  10
  11 using std::vector;
  12
  13 class PrioritizedQueueTest : public testing::Test
  14 {
  15 protected:
  16   typedef int Klass;
  17   typedef unsigned Item;
  18   typedef PrioritizedQueue<Item, Klass> PQ;
  19   enum { item_size  = 100, };
  20   vector<Item> items;
  21
  22   void SetUp() override {
  23     for (int i = 0; i < item_size; i++) {
  24       items.push_back(Item(i));
  25     }
  26     std::random_shuffle(items.begin(), items.end());
  27   }
  28   void TearDown() override {
  29     items.clear();
  30   }
  31 };
  32
  33 TEST_F(PrioritizedQueueTest, capacity) {
  34   const unsigned min_cost  = 10;
  35   const unsigned max_tokens_per_subqueue = 50;
  36   PQ pq(max_tokens_per_subqueue, min_cost);
  37   EXPECT_TRUE(pq.empty());
  38   EXPECT_EQ(0u, pq.length());
  39
  40   pq.enqueue_strict(Klass(1), 0, Item(0));
  41   EXPECT_FALSE(pq.empty());
  42   EXPECT_EQ(1u, pq.length());
  43
  44   for (int i = 0; i < 3; i++) {
  45     pq.enqueue(Klass(1), 0, 10, Item(0));
  46   }
  47   for (unsigned i = 4; i > 0; i--) {
  48     EXPECT_FALSE(pq.empty());
  49     EXPECT_EQ(i, pq.length());
  50     pq.dequeue();
  51   }
  52   EXPECT_TRUE(pq.empty());
  53   EXPECT_EQ(0u, pq.length());
  54 }
  55
  56 TEST_F(PrioritizedQueueTest, strict_pq) {
  57   const unsigned min_cost = 1;
  58   const unsigned max_tokens_per_subqueue = 50;
  59   PQ pq(max_tokens_per_subqueue, min_cost);
  60   // 0 .. item_size-1
  61   for (unsigned i = 0; i < item_size; i++) {
  62     unsigned priority = items[i];
  63     pq.enqueue_strict(Klass(0), priority, items[i]);
  64   }
  65   // item_size-1 .. 0
  66   for (unsigned i = item_size; i > 0; i--) {
  67     Item item = pq.dequeue();
  68     unsigned priority = item;
  69     EXPECT_EQ(i - 1, priority);
  70   }
  71 }
  72
  73 TEST_F(PrioritizedQueueTest, lowest_among_eligible_otherwise_highest) {
  74   // to minimize the effect of `distribute_tokens()`
  75   // all eligible items will be assigned with cost of min_cost
  76   const unsigned min_cost = 0;
  77   const unsigned max_tokens_per_subqueue = 100;
  78   PQ pq(max_tokens_per_subqueue, min_cost);
  79
  80 #define ITEM_TO_COST(item_) (item_ % 5 ? min_cost : max_tokens_per_subqueue)
  81   unsigned num_low_cost = 0, num_high_cost = 0;
  82   for (int i = 0; i < item_size; i++) {
  83     const Item& item = items[i];
  84     unsigned cost = ITEM_TO_COST(item);
  85     unsigned priority = item;
  86     if (cost == min_cost) {
  87       num_low_cost++;
  88     } else {
  89       num_high_cost++;
  90     }
  91     pq.enqueue(Klass(0), priority, cost, item);
  92   }
  93   // the token in all buckets is 0 at the beginning, so dequeue() should pick
  94   // the first one with the highest priority.
  95   unsigned highest_priority;
  96   {
  97     Item item = pq.dequeue();
  98     unsigned cost = ITEM_TO_COST(item);
  99     unsigned priority = item;
 100     if (cost == min_cost) {
 101       num_low_cost--;
 102     } else {
 103       num_high_cost--;
 104     }
 105     EXPECT_EQ(item_size - 1u, priority);
 106     highest_priority = priority;
 107   }
 108   unsigned lowest_priority = 0;
 109   for (unsigned i = 0; i < num_low_cost; i++) {
 110     Item item = pq.dequeue();
 111     unsigned cost = ITEM_TO_COST(item);
 112     unsigned priority = item;
 113     EXPECT_EQ(min_cost, cost);
 114     EXPECT_GT(priority, lowest_priority);
 115     lowest_priority = priority;
 116   }
 117   for (unsigned i = 0; i < num_high_cost; i++) {
 118     Item item = pq.dequeue();
 119     unsigned cost = ITEM_TO_COST(item);
 120     unsigned priority = item;
 121     EXPECT_EQ(max_tokens_per_subqueue, cost);
 122     EXPECT_LT(priority, highest_priority);
 123     highest_priority = priority;
 124   }
 125 #undef ITEM_TO_COST
 126 }
 127
 128 static const unsigned num_classes = 4;
 129 // just a determinitic number
 130 #define ITEM_TO_CLASS(item_) Klass((item_ + 43) % num_classes)
 131
 132 TEST_F(PrioritizedQueueTest, fairness_by_class) {
 133   // dequeue should be fair to all classes in a certain bucket
 134   const unsigned min_cost = 1;
 135   const unsigned max_tokens_per_subqueue = 50;
 136   PQ pq(max_tokens_per_subqueue, min_cost);
 137
 138   for (int i = 0; i < item_size; i++) {
 139     const Item& item = items[i];
 140     Klass k = ITEM_TO_CLASS(item);
 141     unsigned priority = 0;
 142     unsigned cost = 1;
 143     pq.enqueue(k, priority, cost, item);
 144   }
 145   // just sample first 1/2 of the items
 146   // if i pick too small a dataset, the result won't be statisitcally
 147   // significant. if the sample dataset is too large, it will converge to the
 148   // distribution of the full set.
 149   vector<unsigned> num_picked_in_class(num_classes, 0u);
 150   for (int i = 0; i < item_size / 2; i++) {
 151     Item item = pq.dequeue();
 152     Klass k = ITEM_TO_CLASS(item);
 153     num_picked_in_class[k]++;
 154   }
 155   unsigned total = std::accumulate(num_picked_in_class.begin(),
 156                                    num_picked_in_class.end(),
 157                                    0);
 158   float avg = float(total) / num_classes;
 159   for (unsigned i = 0; i < num_classes; i++) {
 160     EXPECT_NEAR(avg, num_picked_in_class[i], 0.5);
 161   }
 162 }
 163
 164
 165 TEST_F(PrioritizedQueueTest, remove_by_class) {
 166   const unsigned min_cost = 1;
 167   const unsigned max_tokens_per_subqueue = 50;
 168   PQ pq(max_tokens_per_subqueue, min_cost);
 169   const Klass class_to_remove(2);
 170   unsigned num_to_remove = 0;
 171   for (int i = 0; i < item_size; i++) {
 172     const Item& item = items[i];
 173     Klass k = ITEM_TO_CLASS(item);
 174     pq.enqueue(k, 0, 0, item);
 175     if (k == class_to_remove) {
 176       num_to_remove++;
 177     }
 178   }
 179   std::list<Item> removed;
 180   pq.remove_by_class(class_to_remove, &removed);
 181
 182   // see if the removed items are expected ones.
 183   for (std::list<Item>::iterator it = removed.begin();
 184        it != removed.end();
 185        ++it) {
 186     const Item& item = *it;
 187     Klass k = ITEM_TO_CLASS(item);
 188     EXPECT_EQ(class_to_remove, k);
 189     items.erase(remove(items.begin(), items.end(), item), items.end());
 190   }
 191   EXPECT_EQ(num_to_remove, removed.size());
 192   EXPECT_EQ(item_size - num_to_remove, pq.length());
 193   EXPECT_EQ(item_size - num_to_remove, items.size());
 194   // see if the remainder are expeceted also.
 195   while (!pq.empty()) {
 196     const Item item = pq.dequeue();
 197     Klass k = ITEM_TO_CLASS(item);
 198     EXPECT_NE(class_to_remove, k);
 199     items.erase(remove(items.begin(), items.end(), item), items.end());
 200   }
 201   EXPECT_TRUE(items.empty());
 202 }