]>
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 | /* | |
5 | * Copyright (C) 2017 Red Hat Inc. | |
11fdf7f2 TL |
6 | * |
7 | * Author: J. Eric Ivancich <ivancich@redhat.com> | |
8 | * | |
9 | * This is free software; you can redistribute it and/or modify it | |
10 | * under the terms of the GNU Lesser General Public License version | |
11 | * 2.1, as published by the Free Software Foundation. See file | |
12 | * COPYING. | |
7c673cae FG |
13 | */ |
14 | ||
15 | ||
16 | #pragma once | |
17 | ||
18 | #include <map> | |
19 | #include <deque> | |
20 | #include <chrono> | |
21 | #include <thread> | |
22 | #include <mutex> | |
23 | #include <condition_variable> | |
24 | ||
9f95a23c | 25 | #include "../support/src/run_every.h" |
7c673cae FG |
26 | #include "dmclock_util.h" |
27 | #include "dmclock_recs.h" | |
28 | ||
7c673cae FG |
29 | |
30 | namespace crimson { | |
31 | namespace dmclock { | |
11fdf7f2 TL |
32 | |
33 | // OrigTracker is a best-effort implementation of the the original | |
34 | // dmClock calculations of delta and rho. It adheres to an | |
35 | // interface, implemented via a template type, that allows it to | |
36 | // be replaced with an alternative. The interface consists of the | |
37 | // static create, prepare_req, resp_update, and get_last_delta | |
38 | // functions. | |
39 | class OrigTracker { | |
7c673cae FG |
40 | Counter delta_prev_req; |
41 | Counter rho_prev_req; | |
42 | uint32_t my_delta; | |
43 | uint32_t my_rho; | |
44 | ||
11fdf7f2 TL |
45 | public: |
46 | ||
47 | OrigTracker(Counter global_delta, | |
48 | Counter global_rho) : | |
49 | delta_prev_req(global_delta), | |
50 | rho_prev_req(global_rho), | |
7c673cae FG |
51 | my_delta(0), |
52 | my_rho(0) | |
11fdf7f2 TL |
53 | { /* empty */ } |
54 | ||
55 | static inline OrigTracker create(Counter the_delta, Counter the_rho) { | |
56 | return OrigTracker(the_delta, the_rho); | |
7c673cae FG |
57 | } |
58 | ||
11fdf7f2 TL |
59 | inline ReqParams prepare_req(Counter& the_delta, Counter& the_rho) { |
60 | Counter delta_out = the_delta - delta_prev_req - my_delta; | |
61 | Counter rho_out = the_rho - rho_prev_req - my_rho; | |
62 | delta_prev_req = the_delta; | |
63 | rho_prev_req = the_rho; | |
7c673cae FG |
64 | my_delta = 0; |
65 | my_rho = 0; | |
11fdf7f2 TL |
66 | return ReqParams(uint32_t(delta_out), uint32_t(rho_out)); |
67 | } | |
68 | ||
69 | inline void resp_update(PhaseType phase, | |
70 | Counter& the_delta, | |
71 | Counter& the_rho, | |
72 | Cost cost) { | |
73 | the_delta += cost; | |
74 | my_delta += cost; | |
75 | if (phase == PhaseType::reservation) { | |
76 | the_rho += cost; | |
77 | my_rho += cost; | |
78 | } | |
7c673cae FG |
79 | } |
80 | ||
11fdf7f2 TL |
81 | inline Counter get_last_delta() const { |
82 | return delta_prev_req; | |
7c673cae | 83 | } |
11fdf7f2 | 84 | }; // struct OrigTracker |
7c673cae FG |
85 | |
86 | ||
11fdf7f2 TL |
87 | // BorrowingTracker always returns a positive delta and rho. If |
88 | // not enough responses have come in to allow that, we will borrow | |
89 | // a future response and repay it later. | |
90 | class BorrowingTracker { | |
91 | Counter delta_prev_req; | |
92 | Counter rho_prev_req; | |
93 | Counter delta_borrow; | |
94 | Counter rho_borrow; | |
95 | ||
96 | public: | |
97 | ||
98 | BorrowingTracker(Counter global_delta, Counter global_rho) : | |
99 | delta_prev_req(global_delta), | |
100 | rho_prev_req(global_rho), | |
101 | delta_borrow(0), | |
102 | rho_borrow(0) | |
103 | { /* empty */ } | |
104 | ||
105 | static inline BorrowingTracker create(Counter the_delta, | |
106 | Counter the_rho) { | |
107 | return BorrowingTracker(the_delta, the_rho); | |
108 | } | |
109 | ||
110 | inline Counter calc_with_borrow(const Counter& global, | |
111 | const Counter& previous, | |
112 | Counter& borrow) { | |
113 | Counter result = global - previous; | |
114 | if (0 == result) { | |
115 | // if no replies have come in, borrow one from the future | |
116 | ++borrow; | |
117 | return 1; | |
118 | } else if (result > borrow) { | |
119 | // if we can give back all of what we borrowed, do so | |
120 | result -= borrow; | |
121 | borrow = 0; | |
122 | return result; | |
123 | } else { | |
124 | // can only return part of what was borrowed in order to | |
125 | // return positive | |
126 | borrow = borrow - result + 1; | |
127 | return 1; | |
128 | } | |
129 | } | |
130 | ||
131 | inline ReqParams prepare_req(Counter& the_delta, Counter& the_rho) { | |
132 | Counter delta_out = | |
133 | calc_with_borrow(the_delta, delta_prev_req, delta_borrow); | |
134 | Counter rho_out = | |
135 | calc_with_borrow(the_rho, rho_prev_req, rho_borrow); | |
136 | delta_prev_req = the_delta; | |
137 | rho_prev_req = the_rho; | |
138 | return ReqParams(uint32_t(delta_out), uint32_t(rho_out)); | |
139 | } | |
140 | ||
141 | inline void resp_update(PhaseType phase, | |
142 | Counter& the_delta, | |
143 | Counter& the_rho, | |
144 | Counter cost) { | |
145 | the_delta += cost; | |
146 | if (phase == PhaseType::reservation) { | |
147 | the_rho += cost; | |
148 | } | |
149 | } | |
150 | ||
151 | inline Counter get_last_delta() const { | |
152 | return delta_prev_req; | |
153 | } | |
154 | }; // struct BorrowingTracker | |
155 | ||
156 | ||
157 | /* | |
158 | * S is server identifier type | |
159 | * | |
160 | * T is the server info class that adheres to ServerTrackerIfc | |
161 | * interface | |
162 | */ | |
163 | template<typename S, typename T = OrigTracker> | |
7c673cae | 164 | class ServiceTracker { |
d2e6a577 FG |
165 | // we don't want to include gtest.h just for FRIEND_TEST |
166 | friend class dmclock_client_server_erase_Test; | |
7c673cae FG |
167 | |
168 | using TimePoint = decltype(std::chrono::steady_clock::now()); | |
169 | using Duration = std::chrono::milliseconds; | |
170 | using MarkPoint = std::pair<TimePoint,Counter>; | |
171 | ||
172 | Counter delta_counter; // # reqs completed | |
173 | Counter rho_counter; // # reqs completed via reservation | |
11fdf7f2 | 174 | std::map<S,T> server_map; |
7c673cae FG |
175 | mutable std::mutex data_mtx; // protects Counters and map |
176 | ||
177 | using DataGuard = std::lock_guard<decltype(data_mtx)>; | |
178 | ||
179 | // clean config | |
180 | ||
181 | std::deque<MarkPoint> clean_mark_points; | |
11fdf7f2 | 182 | Duration clean_age; // age at which server tracker cleaned |
7c673cae FG |
183 | |
184 | // NB: All threads declared at end, so they're destructed firs! | |
185 | ||
186 | std::unique_ptr<RunEvery> cleaning_job; | |
187 | ||
188 | ||
189 | public: | |
190 | ||
191 | // we have to start the counters at 1, as 0 is used in the | |
192 | // cleaning process | |
193 | template<typename Rep, typename Per> | |
194 | ServiceTracker(std::chrono::duration<Rep,Per> _clean_every, | |
195 | std::chrono::duration<Rep,Per> _clean_age) : | |
196 | delta_counter(1), | |
197 | rho_counter(1), | |
198 | clean_age(std::chrono::duration_cast<Duration>(_clean_age)) | |
199 | { | |
200 | cleaning_job = | |
201 | std::unique_ptr<RunEvery>( | |
202 | new RunEvery(_clean_every, | |
203 | std::bind(&ServiceTracker::do_clean, this))); | |
204 | } | |
205 | ||
206 | ||
207 | // the reason we're overloading the constructor rather than | |
208 | // using default values for the arguments is so that callers | |
209 | // have to either use all defaults or specify all timings; with | |
210 | // default arguments they could specify some without others | |
211 | ServiceTracker() : | |
212 | ServiceTracker(std::chrono::minutes(5), std::chrono::minutes(10)) | |
213 | { | |
214 | // empty | |
215 | } | |
216 | ||
217 | ||
218 | /* | |
11fdf7f2 | 219 | * Incorporates the response data received into the counters. |
7c673cae | 220 | */ |
11fdf7f2 TL |
221 | void track_resp(const S& server_id, |
222 | const PhaseType& phase, | |
223 | Counter request_cost = 1u) { | |
7c673cae FG |
224 | DataGuard g(data_mtx); |
225 | ||
226 | auto it = server_map.find(server_id); | |
227 | if (server_map.end() == it) { | |
228 | // this code can only run if a request did not precede the | |
229 | // response or if the record was cleaned up b/w when | |
230 | // the request was made and now | |
11fdf7f2 TL |
231 | auto i = server_map.emplace(server_id, |
232 | T::create(delta_counter, rho_counter)); | |
233 | it = i.first; | |
7c673cae | 234 | } |
11fdf7f2 | 235 | it->second.resp_update(phase, delta_counter, rho_counter, request_cost); |
7c673cae FG |
236 | } |
237 | ||
7c673cae FG |
238 | /* |
239 | * Returns the ReqParams for the given server. | |
240 | */ | |
241 | ReqParams get_req_params(const S& server) { | |
242 | DataGuard g(data_mtx); | |
243 | auto it = server_map.find(server); | |
244 | if (server_map.end() == it) { | |
11fdf7f2 TL |
245 | server_map.emplace(server, |
246 | T::create(delta_counter, rho_counter)); | |
7c673cae FG |
247 | return ReqParams(1, 1); |
248 | } else { | |
11fdf7f2 | 249 | return it->second.prepare_req(delta_counter, rho_counter); |
7c673cae FG |
250 | } |
251 | } | |
252 | ||
253 | private: | |
254 | ||
255 | /* | |
256 | * This is being called regularly by RunEvery. Every time it's | |
257 | * called it notes the time and delta counter (mark point) in a | |
258 | * deque. It also looks at the deque to find the most recent | |
259 | * mark point that is older than clean_age. It then walks the | |
260 | * map and delete all server entries that were last used before | |
261 | * that mark point. | |
262 | */ | |
263 | void do_clean() { | |
264 | TimePoint now = std::chrono::steady_clock::now(); | |
265 | DataGuard g(data_mtx); | |
266 | clean_mark_points.emplace_back(MarkPoint(now, delta_counter)); | |
267 | ||
268 | Counter earliest = 0; | |
269 | auto point = clean_mark_points.front(); | |
270 | while (point.first <= now - clean_age) { | |
271 | earliest = point.second; | |
272 | clean_mark_points.pop_front(); | |
273 | point = clean_mark_points.front(); | |
274 | } | |
275 | ||
276 | if (earliest > 0) { | |
277 | for (auto i = server_map.begin(); | |
278 | i != server_map.end(); | |
279 | /* empty */) { | |
280 | auto i2 = i++; | |
11fdf7f2 | 281 | if (i2->second.get_last_delta() <= earliest) { |
7c673cae FG |
282 | server_map.erase(i2); |
283 | } | |
284 | } | |
285 | } | |
286 | } // do_clean | |
287 | }; // class ServiceTracker | |
288 | } | |
289 | } |