]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
7c673cae FG |
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 | } |