1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (C) 2007-2009 NEC Corporation.  All Rights Reserved.
4 *
5 * Module Author: Kiyoshi Ueda
6 *
7 * This file is released under the GPL.
8 *
9 * Throughput oriented path selector.
10 */
11
12#include "dm.h"
13#include "dm-path-selector.h"
14
15#include <linux/slab.h>
16#include <linux/module.h>
17
18#define DM_MSG_PREFIX	"multipath service-time"
19#define ST_MIN_IO	1
20#define ST_MAX_RELATIVE_THROUGHPUT	100
21#define ST_MAX_RELATIVE_THROUGHPUT_SHIFT	7
22#define ST_MAX_INFLIGHT_SIZE	((size_t)-1 >> ST_MAX_RELATIVE_THROUGHPUT_SHIFT)
23#define ST_VERSION	"0.3.0"
24
25struct selector {
26	struct list_head valid_paths;
27	struct list_head failed_paths;
28	spinlock_t lock;
29};
30
31struct path_info {
32	struct list_head list;
33	struct dm_path *path;
34	unsigned int repeat_count;
35	unsigned int relative_throughput;
36	atomic_t in_flight_size;	/* Total size of in-flight I/Os */
37};
38
39static struct selector *alloc_selector(void)
40{
41	struct selector *s = kmalloc(sizeof(*s), GFP_KERNEL);
42
43	if (s) {
44		INIT_LIST_HEAD(&s->valid_paths);
45		INIT_LIST_HEAD(&s->failed_paths);
46		spin_lock_init(&s->lock);
47	}
48
49	return s;
50}
51
52static int st_create(struct path_selector *ps, unsigned int argc, char **argv)
53{
54	struct selector *s = alloc_selector();
55
56	if (!s)
57		return -ENOMEM;
58
59	ps->context = s;
60	return 0;
61}
62
63static void free_paths(struct list_head *paths)
64{
65	struct path_info *pi, *next;
66
67	list_for_each_entry_safe(pi, next, paths, list) {
68		list_del(&pi->list);
69		kfree(pi);
70	}
71}
72
73static void st_destroy(struct path_selector *ps)
74{
75	struct selector *s = ps->context;
76
77	free_paths(&s->valid_paths);
78	free_paths(&s->failed_paths);
79	kfree(s);
80	ps->context = NULL;
81}
82
83static int st_status(struct path_selector *ps, struct dm_path *path,
84		     status_type_t type, char *result, unsigned int maxlen)
85{
86	unsigned int sz = 0;
87	struct path_info *pi;
88
89	if (!path)
90		DMEMIT("0 ");
91	else {
92		pi = path->pscontext;
93
94		switch (type) {
95		case STATUSTYPE_INFO:
96			DMEMIT("%d %u ", atomic_read(&pi->in_flight_size),
97			       pi->relative_throughput);
98			break;
99		case STATUSTYPE_TABLE:
100			DMEMIT("%u %u ", pi->repeat_count,
101			       pi->relative_throughput);
102			break;
103		case STATUSTYPE_IMA:
104			result[0] = '\0';
105			break;
106		}
107	}
108
109	return sz;
110}
111
112static int st_add_path(struct path_selector *ps, struct dm_path *path,
113		       int argc, char **argv, char **error)
114{
115	struct selector *s = ps->context;
116	struct path_info *pi;
117	unsigned int repeat_count = ST_MIN_IO;
118	unsigned int relative_throughput = 1;
119	char dummy;
120	unsigned long flags;
121
122	/*
123	 * Arguments: [<repeat_count> [<relative_throughput>]]
124	 *	<repeat_count>: The number of I/Os before switching path.
125	 *			If not given, default (ST_MIN_IO) is used.
126	 *	<relative_throughput>: The relative throughput value of
127	 *			the path among all paths in the path-group.
128	 *			The valid range: 0-<ST_MAX_RELATIVE_THROUGHPUT>
129	 *			If not given, minimum value '1' is used.
130	 *			If '0' is given, the path isn't selected while
131	 *			other paths having a positive value are	available.
132	 */
133	if (argc > 2) {
134		*error = "service-time ps: incorrect number of arguments";
135		return -EINVAL;
136	}
137
138	if (argc && (sscanf(argv[0], "%u%c", &repeat_count, &dummy) != 1)) {
139		*error = "service-time ps: invalid repeat count";
140		return -EINVAL;
141	}
142
143	if (repeat_count > 1) {
144		DMWARN_LIMIT("repeat_count > 1 is deprecated, using 1 instead");
145		repeat_count = 1;
146	}
147
148	if ((argc == 2) &&
149	    (sscanf(argv[1], "%u%c", &relative_throughput, &dummy) != 1 ||
150	     relative_throughput > ST_MAX_RELATIVE_THROUGHPUT)) {
151		*error = "service-time ps: invalid relative_throughput value";
152		return -EINVAL;
153	}
154
155	/* allocate the path */
156	pi = kmalloc(sizeof(*pi), GFP_KERNEL);
157	if (!pi) {
158		*error = "service-time ps: Error allocating path context";
159		return -ENOMEM;
160	}
161
162	pi->path = path;
163	pi->repeat_count = repeat_count;
164	pi->relative_throughput = relative_throughput;
165	atomic_set(&pi->in_flight_size, 0);
166
167	path->pscontext = pi;
168
169	spin_lock_irqsave(&s->lock, flags);
170	list_add_tail(&pi->list, &s->valid_paths);
171	spin_unlock_irqrestore(&s->lock, flags);
172
173	return 0;
174}
175
176static void st_fail_path(struct path_selector *ps, struct dm_path *path)
177{
178	struct selector *s = ps->context;
179	struct path_info *pi = path->pscontext;
180	unsigned long flags;
181
182	spin_lock_irqsave(&s->lock, flags);
183	list_move(&pi->list, &s->failed_paths);
184	spin_unlock_irqrestore(&s->lock, flags);
185}
186
187static int st_reinstate_path(struct path_selector *ps, struct dm_path *path)
188{
189	struct selector *s = ps->context;
190	struct path_info *pi = path->pscontext;
191	unsigned long flags;
192
193	spin_lock_irqsave(&s->lock, flags);
194	list_move_tail(&pi->list, &s->valid_paths);
195	spin_unlock_irqrestore(&s->lock, flags);
196
197	return 0;
198}
199
200/*
201 * Compare the estimated service time of 2 paths, pi1 and pi2,
202 * for the incoming I/O.
203 *
204 * Returns:
205 * < 0 : pi1 is better
206 * 0   : no difference between pi1 and pi2
207 * > 0 : pi2 is better
208 *
209 * Description:
210 * Basically, the service time is estimated by:
211 *     ('pi->in-flight-size' + 'incoming') / 'pi->relative_throughput'
212 * To reduce the calculation, some optimizations are made.
213 * (See comments inline)
214 */
215static int st_compare_load(struct path_info *pi1, struct path_info *pi2,
216			   size_t incoming)
217{
218	size_t sz1, sz2, st1, st2;
219
220	sz1 = atomic_read(&pi1->in_flight_size);
221	sz2 = atomic_read(&pi2->in_flight_size);
222
223	/*
224	 * Case 1: Both have same throughput value. Choose less loaded path.
225	 */
226	if (pi1->relative_throughput == pi2->relative_throughput)
227		return sz1 - sz2;
228
229	/*
230	 * Case 2a: Both have same load. Choose higher throughput path.
231	 * Case 2b: One path has no throughput value. Choose the other one.
232	 */
233	if (sz1 == sz2 ||
234	    !pi1->relative_throughput || !pi2->relative_throughput)
235		return pi2->relative_throughput - pi1->relative_throughput;
236
237	/*
238	 * Case 3: Calculate service time. Choose faster path.
239	 *         Service time using pi1:
240	 *             st1 = (sz1 + incoming) / pi1->relative_throughput
241	 *         Service time using pi2:
242	 *             st2 = (sz2 + incoming) / pi2->relative_throughput
243	 *
244	 *         To avoid the division, transform the expression to use
245	 *         multiplication.
246	 *         Because ->relative_throughput > 0 here, if st1 < st2,
247	 *         the expressions below are the same meaning:
248	 *             (sz1 + incoming) / pi1->relative_throughput <
249	 *                 (sz2 + incoming) / pi2->relative_throughput
250	 *             (sz1 + incoming) * pi2->relative_throughput <
251	 *                 (sz2 + incoming) * pi1->relative_throughput
252	 *         So use the later one.
253	 */
254	sz1 += incoming;
255	sz2 += incoming;
256	if (unlikely(sz1 >= ST_MAX_INFLIGHT_SIZE ||
257		     sz2 >= ST_MAX_INFLIGHT_SIZE)) {
258		/*
259		 * Size may be too big for multiplying pi->relative_throughput
260		 * and overflow.
261		 * To avoid the overflow and mis-selection, shift down both.
262		 */
263		sz1 >>= ST_MAX_RELATIVE_THROUGHPUT_SHIFT;
264		sz2 >>= ST_MAX_RELATIVE_THROUGHPUT_SHIFT;
265	}
266	st1 = sz1 * pi2->relative_throughput;
267	st2 = sz2 * pi1->relative_throughput;
268	if (st1 != st2)
269		return st1 - st2;
270
271	/*
272	 * Case 4: Service time is equal. Choose higher throughput path.
273	 */
274	return pi2->relative_throughput - pi1->relative_throughput;
275}
276
277static struct dm_path *st_select_path(struct path_selector *ps, size_t nr_bytes)
278{
279	struct selector *s = ps->context;
280	struct path_info *pi = NULL, *best = NULL;
281	struct dm_path *ret = NULL;
282	unsigned long flags;
283
284	spin_lock_irqsave(&s->lock, flags);
285	if (list_empty(&s->valid_paths))
286		goto out;
287
288	list_for_each_entry(pi, &s->valid_paths, list)
289		if (!best || (st_compare_load(pi, best, nr_bytes) < 0))
290			best = pi;
291
292	if (!best)
293		goto out;
294
295	/* Move most recently used to least preferred to evenly balance. */
296	list_move_tail(&best->list, &s->valid_paths);
297
298	ret = best->path;
299out:
300	spin_unlock_irqrestore(&s->lock, flags);
301	return ret;
302}
303
304static int st_start_io(struct path_selector *ps, struct dm_path *path,
305		       size_t nr_bytes)
306{
307	struct path_info *pi = path->pscontext;
308
309	atomic_add(nr_bytes, &pi->in_flight_size);
310
311	return 0;
312}
313
314static int st_end_io(struct path_selector *ps, struct dm_path *path,
315		     size_t nr_bytes, u64 start_time)
316{
317	struct path_info *pi = path->pscontext;
318
319	atomic_sub(nr_bytes, &pi->in_flight_size);
320
321	return 0;
322}
323
324static struct path_selector_type st_ps = {
325	.name		= "service-time",
326	.module		= THIS_MODULE,
327	.table_args	= 2,
328	.info_args	= 2,
329	.create		= st_create,
330	.destroy	= st_destroy,
331	.status		= st_status,
332	.add_path	= st_add_path,
333	.fail_path	= st_fail_path,
334	.reinstate_path	= st_reinstate_path,
335	.select_path	= st_select_path,
336	.start_io	= st_start_io,
337	.end_io		= st_end_io,
338};
339
340static int __init dm_st_init(void)
341{
342	int r = dm_register_path_selector(&st_ps);
343
344	if (r < 0)
345		DMERR("register failed %d", r);
346
347	DMINFO("version " ST_VERSION " loaded");
348
349	return r;
350}
351
352static void __exit dm_st_exit(void)
353{
354	int r = dm_unregister_path_selector(&st_ps);
355
356	if (r < 0)
357		DMERR("unregister failed %d", r);
358}
359
360module_init(dm_st_init);
361module_exit(dm_st_exit);
362
363MODULE_DESCRIPTION(DM_NAME " throughput oriented path selector");
364MODULE_AUTHOR("Kiyoshi Ueda <k-ueda@ct.jp.nec.com>");
365MODULE_LICENSE("GPL");
366