]>
Commit | Line | Data |
---|---|---|
224ce89b WB |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2017 Red Hat Inc. | |
7 | * | |
8 | * This is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License version 2.1, as published by the Free Software | |
11 | * Foundation. See file COPYING. | |
12 | * | |
13 | */ | |
14 | ||
15 | #include <thread> | |
16 | #include <chrono> | |
17 | #include <iostream> | |
18 | #include "gtest/gtest.h" | |
19 | #include "common/mClockPriorityQueue.h" | |
20 | ||
21 | ||
22 | struct Request { | |
23 | int value; | |
24 | Request() = default; | |
25 | Request(const Request& o) = default; | |
26 | Request(int value) : | |
27 | value(value) | |
28 | {} | |
29 | }; | |
30 | ||
31 | ||
32 | struct Client { | |
33 | int client_num; | |
34 | Client() : | |
35 | Client(-1) | |
36 | {} | |
37 | Client(int client_num) : | |
38 | client_num(client_num) | |
39 | {} | |
40 | friend bool operator<(const Client& r1, const Client& r2) { | |
41 | return r1.client_num < r2.client_num; | |
42 | } | |
43 | friend bool operator==(const Client& r1, const Client& r2) { | |
44 | return r1.client_num == r2.client_num; | |
45 | } | |
46 | }; | |
47 | ||
48 | ||
49 | crimson::dmclock::ClientInfo client_info_func(const Client& c) { | |
50 | static const crimson::dmclock::ClientInfo | |
51 | the_info(10.0, 10.0, 10.0); | |
52 | return the_info; | |
53 | } | |
54 | ||
55 | ||
56 | TEST(mClockPriorityQueue, Create) | |
57 | { | |
58 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
59 | } | |
60 | ||
61 | ||
62 | TEST(mClockPriorityQueue, Sizes) | |
63 | { | |
64 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
65 | ||
66 | ASSERT_TRUE(q.empty()); | |
67 | ASSERT_EQ(0u, q.length()); | |
68 | ||
69 | Client c1(1); | |
70 | Client c2(2); | |
71 | ||
72 | q.enqueue_strict(c1, 1, Request(1)); | |
73 | q.enqueue_strict(c2, 2, Request(2)); | |
74 | q.enqueue_strict(c1, 2, Request(3)); | |
75 | q.enqueue(c2, 1, 0, Request(4)); | |
76 | q.enqueue(c1, 2, 0, Request(5)); | |
77 | q.enqueue_strict(c2, 1, Request(6)); | |
78 | ||
79 | ASSERT_FALSE(q.empty()); | |
80 | ASSERT_EQ(6u, q.length()); | |
81 | ||
82 | ||
83 | for (int i = 0; i < 6; ++i) { | |
84 | (void) q.dequeue(); | |
85 | } | |
86 | ||
87 | ASSERT_TRUE(q.empty()); | |
88 | ASSERT_EQ(0u, q.length()); | |
89 | } | |
90 | ||
91 | ||
92 | TEST(mClockPriorityQueue, JustStrict) | |
93 | { | |
94 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
95 | ||
96 | Client c1(1); | |
97 | Client c2(2); | |
98 | ||
99 | q.enqueue_strict(c1, 1, Request(1)); | |
100 | q.enqueue_strict(c2, 2, Request(2)); | |
101 | q.enqueue_strict(c1, 2, Request(3)); | |
102 | q.enqueue_strict(c2, 1, Request(4)); | |
103 | ||
104 | Request r; | |
105 | ||
106 | r = q.dequeue(); | |
107 | ASSERT_EQ(2, r.value); | |
108 | r = q.dequeue(); | |
109 | ASSERT_EQ(3, r.value); | |
110 | r = q.dequeue(); | |
111 | ASSERT_EQ(1, r.value); | |
112 | r = q.dequeue(); | |
113 | ASSERT_EQ(4, r.value); | |
114 | } | |
115 | ||
116 | ||
117 | TEST(mClockPriorityQueue, StrictPriorities) | |
118 | { | |
119 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
120 | ||
121 | Client c1(1); | |
122 | Client c2(2); | |
123 | ||
124 | q.enqueue_strict(c1, 1, Request(1)); | |
125 | q.enqueue_strict(c2, 2, Request(2)); | |
126 | q.enqueue_strict(c1, 3, Request(3)); | |
127 | q.enqueue_strict(c2, 4, Request(4)); | |
128 | ||
129 | Request r; | |
130 | ||
131 | r = q.dequeue(); | |
132 | ASSERT_EQ(4, r.value); | |
133 | r = q.dequeue(); | |
134 | ASSERT_EQ(3, r.value); | |
135 | r = q.dequeue(); | |
136 | ASSERT_EQ(2, r.value); | |
137 | r = q.dequeue(); | |
138 | ASSERT_EQ(1, r.value); | |
139 | } | |
140 | ||
141 | ||
142 | TEST(mClockPriorityQueue, JustNotStrict) | |
143 | { | |
144 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
145 | ||
146 | Client c1(1); | |
147 | Client c2(2); | |
148 | ||
149 | // non-strict queue ignores priorites, but will divide between | |
150 | // clients evenly and maintain orders between clients | |
151 | q.enqueue(c1, 1, 0, Request(1)); | |
152 | q.enqueue(c1, 2, 0, Request(2)); | |
153 | q.enqueue(c2, 3, 0, Request(3)); | |
154 | q.enqueue(c2, 4, 0, Request(4)); | |
155 | ||
156 | Request r1, r2; | |
157 | ||
158 | r1 = q.dequeue(); | |
159 | ASSERT_TRUE(1 == r1.value || 3 == r1.value); | |
160 | ||
161 | r2 = q.dequeue(); | |
162 | ASSERT_TRUE(1 == r2.value || 3 == r2.value); | |
163 | ||
164 | ASSERT_NE(r1.value, r2.value); | |
165 | ||
166 | r1 = q.dequeue(); | |
167 | ASSERT_TRUE(2 == r1.value || 4 == r1.value); | |
168 | ||
169 | r2 = q.dequeue(); | |
170 | ASSERT_TRUE(2 == r2.value || 4 == r2.value); | |
171 | ||
172 | ASSERT_NE(r1.value, r2.value); | |
173 | } | |
174 | ||
175 | ||
176 | TEST(mClockPriorityQueue, EnqueuFront) | |
177 | { | |
178 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
179 | ||
180 | Client c1(1); | |
181 | Client c2(2); | |
182 | ||
183 | // non-strict queue ignores priorites, but will divide between | |
184 | // clients evenly and maintain orders between clients | |
185 | q.enqueue(c1, 1, 0, Request(1)); | |
186 | q.enqueue(c1, 2, 0, Request(2)); | |
187 | q.enqueue(c2, 3, 0, Request(3)); | |
188 | q.enqueue(c2, 4, 0, Request(4)); | |
189 | q.enqueue_strict(c2, 6, Request(6)); | |
190 | q.enqueue_strict(c1, 7, Request(7)); | |
191 | ||
192 | std::list<Request> reqs; | |
193 | ||
194 | for (uint i = 0; i < 4; ++i) { | |
195 | reqs.emplace_back(q.dequeue()); | |
196 | } | |
197 | ||
198 | for (uint i = 0; i < 4; ++i) { | |
199 | Request& r = reqs.front(); | |
200 | if (r.value > 5) { | |
201 | q.enqueue_strict_front(r.value == 6 ? c2 : 1, r.value, r); | |
202 | } else { | |
203 | q.enqueue_front(r.value <= 2 ? c1 : c2, r.value, 0, r); | |
204 | } | |
205 | reqs.pop_front(); | |
206 | } | |
207 | ||
208 | Request r; | |
209 | ||
210 | r = q.dequeue(); | |
211 | ASSERT_EQ(7, r.value); | |
212 | ||
213 | r = q.dequeue(); | |
214 | ASSERT_EQ(6, r.value); | |
215 | ||
216 | r = q.dequeue(); | |
217 | ASSERT_TRUE(1 == r.value || 3 == r.value); | |
218 | ||
219 | r = q.dequeue(); | |
220 | ASSERT_TRUE(1 == r.value || 3 == r.value); | |
221 | ||
222 | r = q.dequeue(); | |
223 | ASSERT_TRUE(2 == r.value || 4 == r.value); | |
224 | ||
225 | r = q.dequeue(); | |
226 | ASSERT_TRUE(2 == r.value || 4 == r.value); | |
227 | } | |
228 | ||
229 | ||
230 | TEST(mClockPriorityQueue, RemoveByClass) | |
231 | { | |
232 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
233 | ||
234 | Client c1(1); | |
235 | Client c2(2); | |
236 | Client c3(3); | |
237 | ||
238 | q.enqueue(c1, 1, 0, Request(1)); | |
239 | q.enqueue(c2, 1, 0, Request(2)); | |
240 | q.enqueue(c3, 1, 0, Request(4)); | |
241 | q.enqueue_strict(c1, 2, Request(8)); | |
242 | q.enqueue_strict(c2, 1, Request(16)); | |
243 | q.enqueue_strict(c3, 3, Request(32)); | |
244 | q.enqueue(c3, 1, 0, Request(64)); | |
245 | q.enqueue(c2, 1, 0, Request(128)); | |
246 | q.enqueue(c1, 1, 0, Request(256)); | |
247 | ||
248 | int out_mask = 2 | 16 | 128; | |
249 | int in_mask = 1 | 8 | 256; | |
250 | ||
251 | std::list<Request> out; | |
252 | q.remove_by_class(c2, &out); | |
253 | ||
254 | ASSERT_EQ(3u, out.size()); | |
255 | while (!out.empty()) { | |
256 | ASSERT_TRUE((out.front().value & out_mask) > 0) << | |
257 | "had value that was not expected after first removal"; | |
258 | out.pop_front(); | |
259 | } | |
260 | ||
261 | ASSERT_EQ(6u, q.length()) << "after removal of three from client c2"; | |
262 | ||
263 | q.remove_by_class(c3); | |
264 | ||
265 | ASSERT_EQ(3u, q.length()) << "after removal of three from client c3"; | |
266 | while (!q.empty()) { | |
267 | Request r = q.dequeue(); | |
268 | ASSERT_TRUE((r.value & in_mask) > 0) << | |
269 | "had value that was not expected after two removals"; | |
270 | } | |
271 | } | |
272 | ||
273 | ||
274 | TEST(mClockPriorityQueue, RemoveByFilter) | |
275 | { | |
276 | ceph::mClockQueue<Request,Client> q(&client_info_func); | |
277 | ||
278 | Client c1(1); | |
279 | Client c2(2); | |
280 | Client c3(3); | |
281 | ||
282 | q.enqueue(c1, 1, 0, Request(1)); | |
283 | q.enqueue(c2, 1, 0, Request(2)); | |
284 | q.enqueue(c3, 1, 0, Request(3)); | |
285 | q.enqueue_strict(c1, 2, Request(4)); | |
286 | q.enqueue_strict(c2, 1, Request(5)); | |
287 | q.enqueue_strict(c3, 3, Request(6)); | |
288 | q.enqueue(c3, 1, 0, Request(7)); | |
289 | q.enqueue(c2, 1, 0, Request(8)); | |
290 | q.enqueue(c1, 1, 0, Request(9)); | |
291 | ||
292 | std::list<Request> filtered; | |
293 | ||
294 | q.remove_by_filter([&](const Request& r) -> bool { | |
295 | if (r.value & 2) { | |
296 | filtered.push_back(r); | |
297 | return true; | |
298 | } else { | |
299 | return false; | |
300 | } | |
301 | }); | |
302 | ||
303 | ASSERT_EQ(4u, filtered.size()) << | |
304 | "filter should have removed four elements"; | |
305 | while (!filtered.empty()) { | |
306 | ASSERT_TRUE((filtered.front().value & 2) > 0) << | |
307 | "expect this value to have been filtered out"; | |
308 | filtered.pop_front(); | |
309 | } | |
310 | ||
311 | ASSERT_EQ(5u, q.length()) << | |
312 | "filter should have left five remaining elements"; | |
313 | while (!q.empty()) { | |
314 | Request r = q.dequeue(); | |
315 | ASSERT_TRUE((r.value & 2) == 0) << | |
316 | "expect this value to have been left in"; | |
317 | } | |
318 | } |