Lines Matching +full:delta +full:- +full:x +full:- +full:threshold
1 // SPDX-License-Identifier: GPL-2.0-only
5 * Keeps a time-weighted exponential moving average of the historical
20 * ns, and the weighting is pre-calculated.
25 #include "dm-path-selector.h"
32 #define DM_MSG_PREFIX "multipath historical-service-time"
70 * fixed_power - compute: x^n, in O(log n) time
72 * @x: base of the power
73 * @frac_bits: fractional bits of @x
74 * @n: power to raise @x to.
77 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
80 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
86 static u64 fixed_power(u64 x, unsigned int frac_bits, unsigned int n) in fixed_power() argument
93 result *= x; in fixed_power()
94 result += 1UL << (frac_bits - 1); in fixed_power()
100 x *= x; in fixed_power()
101 x += 1UL << (frac_bits - 1); in fixed_power()
102 x >>= frac_bits; in fixed_power()
111 * a_1 = a_0 * e + a * (1 - e)
119 * a_n = a_0 * e^n + a * (1 - e^n),
125 last += next * (HST_FIXED_1 - weight); in fixed_ema()
126 last += 1ULL << (HST_FIXED_SHIFT - 1); in fixed_ema()
135 INIT_LIST_HEAD(&s->valid_paths); in alloc_selector()
136 INIT_LIST_HEAD(&s->failed_paths); in alloc_selector()
137 spin_lock_init(&s->lock); in alloc_selector()
138 s->valid_count = 0; in alloc_selector()
147 static u64 hst_weight(struct path_selector *ps, u64 delta) in hst_weight() argument
149 struct selector *s = ps->context; in hst_weight()
150 int bucket = clamp(delta >> HST_BUCKET_SHIFT, 0ULL, in hst_weight()
151 HST_WEIGHT_COUNT - 1); in hst_weight()
153 return s->weights[bucket]; in hst_weight()
159 * weights[len-1] = 0
164 struct selector *s = ps->context; in hst_set_weights()
170 for (i = 0; i < HST_WEIGHT_COUNT - 1; i++) in hst_set_weights()
171 s->weights[i] = fixed_power(base, HST_FIXED_SHIFT, i + 1); in hst_set_weights()
172 s->weights[HST_WEIGHT_COUNT - 1] = 0; in hst_set_weights()
184 * <base_weight>: Base weight for ema [0, 1024) 10-bit fixed point. A in hst_create()
187 * <threshold_multiplier>: Minimum threshold multiplier for paths to in hst_create()
190 * is the path with higher service time. A threshold in hst_create()
194 return -EINVAL; in hst_create()
198 return -EINVAL; in hst_create()
203 return -EINVAL; in hst_create()
208 return -ENOMEM; in hst_create()
210 ps->context = s; in hst_create()
213 s->threshold_multiplier = threshold_multiplier; in hst_create()
222 list_del(&pi->list); in free_paths()
229 struct selector *s = ps->context; in hst_destroy()
231 free_paths(&s->valid_paths); in hst_destroy()
232 free_paths(&s->failed_paths); in hst_destroy()
234 ps->context = NULL; in hst_destroy()
244 struct selector *s = ps->context; in hst_status()
246 DMEMIT("2 %u %u ", s->weights[0], s->threshold_multiplier); in hst_status()
248 pi = path->pscontext; in hst_status()
252 DMEMIT("%llu %llu %llu ", pi->historical_service_time, in hst_status()
253 pi->outstanding, pi->stale_after); in hst_status()
270 struct selector *s = ps->context; in hst_add_path()
282 *error = "historical-service-time ps: incorrect number of arguments"; in hst_add_path()
283 return -EINVAL; in hst_add_path()
287 *error = "historical-service-time ps: invalid repeat count"; in hst_add_path()
288 return -EINVAL; in hst_add_path()
294 *error = "historical-service-time ps: Error allocating path context"; in hst_add_path()
295 return -ENOMEM; in hst_add_path()
298 pi->path = path; in hst_add_path()
299 pi->repeat_count = repeat_count; in hst_add_path()
301 pi->historical_service_time = HST_FIXED_1; in hst_add_path()
303 spin_lock_init(&pi->lock); in hst_add_path()
304 pi->outstanding = 0; in hst_add_path()
306 pi->stale_after = 0; in hst_add_path()
307 pi->last_finish = 0; in hst_add_path()
309 path->pscontext = pi; in hst_add_path()
311 spin_lock_irqsave(&s->lock, flags); in hst_add_path()
312 list_add_tail(&pi->list, &s->valid_paths); in hst_add_path()
313 s->valid_count++; in hst_add_path()
314 spin_unlock_irqrestore(&s->lock, flags); in hst_add_path()
321 struct selector *s = ps->context; in hst_fail_path()
322 struct path_info *pi = path->pscontext; in hst_fail_path()
325 spin_lock_irqsave(&s->lock, flags); in hst_fail_path()
326 list_move(&pi->list, &s->failed_paths); in hst_fail_path()
327 s->valid_count--; in hst_fail_path()
328 spin_unlock_irqrestore(&s->lock, flags); in hst_fail_path()
333 struct selector *s = ps->context; in hst_reinstate_path()
334 struct path_info *pi = path->pscontext; in hst_reinstate_path()
337 spin_lock_irqsave(&s->lock, flags); in hst_reinstate_path()
338 list_move_tail(&pi->list, &s->valid_paths); in hst_reinstate_path()
339 s->valid_count++; in hst_reinstate_path()
340 spin_unlock_irqrestore(&s->lock, flags); in hst_reinstate_path()
350 spin_lock_irqsave(&pi->lock, flags); in hst_fill_compare()
351 *hst = pi->historical_service_time; in hst_fill_compare()
352 *out = pi->outstanding; in hst_fill_compare()
353 *stale = pi->stale_after; in hst_fill_compare()
354 spin_unlock_irqrestore(&pi->lock, flags); in hst_fill_compare()
370 struct selector *s = ps->context; in hst_compare()
384 over_threshold = hst1 > (s->threshold_multiplier * hst2); in hst_compare()
386 over_threshold = hst2 > (s->threshold_multiplier * hst1); in hst_compare()
389 return out1 - out2; in hst_compare()
398 return (!out2 * stale1) - (!out1 * stale2); in hst_compare()
409 /* If over 1023 in-flights, we may overflow if hst in hst_compare()
411 * 1048576 in-flights, which is high enough). in hst_compare()
422 return out1 - out2; in hst_compare()
426 return out1 - out2; in hst_compare()
427 return -1; in hst_compare()
433 struct selector *s = ps->context; in hst_select_path()
439 spin_lock_irqsave(&s->lock, flags); in hst_select_path()
440 if (list_empty(&s->valid_paths)) in hst_select_path()
443 list_for_each_entry(pi, &s->valid_paths, list) { in hst_select_path()
452 list_move_tail(&best->list, &s->valid_paths); in hst_select_path()
454 ret = best->path; in hst_select_path()
457 spin_unlock_irqrestore(&s->lock, flags); in hst_select_path()
464 struct path_info *pi = path->pscontext; in hst_start_io()
467 spin_lock_irqsave(&pi->lock, flags); in hst_start_io()
468 pi->outstanding++; in hst_start_io()
469 spin_unlock_irqrestore(&pi->lock, flags); in hst_start_io()
482 if (time_after64(pi->last_finish, start_time)) in path_service_time()
483 start_time = pi->last_finish; in path_service_time()
485 pi->last_finish = now; in path_service_time()
489 return now - start_time; in path_service_time()
495 struct path_info *pi = path->pscontext; in hst_end_io()
496 struct selector *s = ps->context; in hst_end_io()
500 spin_lock_irqsave(&pi->lock, flags); in hst_end_io()
503 pi->outstanding--; in hst_end_io()
504 pi->historical_service_time = in hst_end_io()
505 fixed_ema(pi->historical_service_time, in hst_end_io()
515 pi->stale_after = pi->last_finish + in hst_end_io()
516 (s->valid_count * (pi->historical_service_time >> HST_FIXED_SHIFT)); in hst_end_io()
518 spin_unlock_irqrestore(&pi->lock, flags); in hst_end_io()
524 .name = "historical-service-time",