// SPDX-License-Identifier: GPL-2.0-only /* * Historical Service Time * * Keeps a time-weighted exponential moving average of the historical * service time. Estimates future service time based on the historical * service time and the number of outstanding requests. * * Marks paths stale if they have not finished within hst * * num_paths. If a path is stale and unused, we will send a single * request to probe in case the path has improved. This situation * generally arises if the path is so much worse than others that it * will never have the best estimated service time, or if the entire * multipath device is unused. If a path is stale and in use, limit the * number of requests it can receive with the assumption that the path * has become degraded. * * To avoid repeatedly calculating exponents for time weighting, times * are split into HST_WEIGHT_COUNT buckets each (1 >> HST_BUCKET_SHIFT) * ns, and the weighting is pre-calculated. * */ #include "dm.h" #include "dm-path-selector.h" #include <linux/blkdev.h> #include <linux/slab.h> #include <linux/module.h> #define DM_MSG_PREFIX … #define HST_MIN_IO … #define HST_VERSION … #define HST_FIXED_SHIFT … #define HST_FIXED_MAX … #define HST_FIXED_1 … #define HST_FIXED_95 … #define HST_MAX_INFLIGHT … #define HST_BUCKET_SHIFT … #define HST_WEIGHT_COUNT … struct selector { … }; struct path_info { … }; /** * fixed_power - compute: x^n, in O(log n) time * * @x: base of the power * @frac_bits: fractional bits of @x * @n: power to raise @x to. * * By exploiting the relation between the definition of the natural power * function: x^n := x*x*...*x (x multiplied by itself for n times), and * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i, * (where: n_i \elem {0, 1}, the binary vector representing n), * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is * of course trivially computable in O(log_2 n), the length of our binary * vector. * * (see: kernel/sched/loadavg.c) */ static u64 fixed_power(u64 x, unsigned int frac_bits, unsigned int n) { … } /* * Calculate the next value of an exponential moving average * a_1 = a_0 * e + a * (1 - e) * * @last: [0, ULLONG_MAX >> HST_FIXED_SHIFT] * @next: [0, ULLONG_MAX >> HST_FIXED_SHIFT] * @weight: [0, HST_FIXED_1] * * Note: * To account for multiple periods in the same calculation, * a_n = a_0 * e^n + a * (1 - e^n), * so call fixed_ema(last, next, pow(weight, N)) */ static u64 fixed_ema(u64 last, u64 next, u64 weight) { … } static struct selector *alloc_selector(void) { … } /* * Get the weight for a given time span. */ static u64 hst_weight(struct path_selector *ps, u64 delta) { … } /* * Set up the weights array. * * weights[len-1] = 0 * weights[n] = base ^ (n + 1) */ static void hst_set_weights(struct path_selector *ps, unsigned int base) { … } static int hst_create(struct path_selector *ps, unsigned int argc, char **argv) { … } static void free_paths(struct list_head *paths) { … } static void hst_destroy(struct path_selector *ps) { … } static int hst_status(struct path_selector *ps, struct dm_path *path, status_type_t type, char *result, unsigned int maxlen) { … } static int hst_add_path(struct path_selector *ps, struct dm_path *path, int argc, char **argv, char **error) { … } static void hst_fail_path(struct path_selector *ps, struct dm_path *path) { … } static int hst_reinstate_path(struct path_selector *ps, struct dm_path *path) { … } static void hst_fill_compare(struct path_info *pi, u64 *hst, u64 *out, u64 *stale) { … } /* * Compare the estimated service time of 2 paths, pi1 and pi2, * for the incoming I/O. * * Returns: * < 0 : pi1 is better * 0 : no difference between pi1 and pi2 * > 0 : pi2 is better * */ static long long hst_compare(struct path_info *pi1, struct path_info *pi2, u64 time_now, struct path_selector *ps) { … } static struct dm_path *hst_select_path(struct path_selector *ps, size_t nr_bytes) { … } static int hst_start_io(struct path_selector *ps, struct dm_path *path, size_t nr_bytes) { … } static u64 path_service_time(struct path_info *pi, u64 start_time) { … } static int hst_end_io(struct path_selector *ps, struct dm_path *path, size_t nr_bytes, u64 start_time) { … } static struct path_selector_type hst_ps = …; static int __init dm_hst_init(void) { … } static void __exit dm_hst_exit(void) { … } module_init(…) …; module_exit(dm_hst_exit); MODULE_DESCRIPTION(…) …; MODULE_AUTHOR(…) …; MODULE_LICENSE(…) …;
Codebase Browser
linux