1 /* 2 * Copyright (C) 2007-2009 NEC Corporation. All Rights Reserved. 3 * 4 * Module Author: Kiyoshi Ueda 5 * 6 * This file is released under the GPL. 7 * 8 * Throughput oriented path selector. 9 */ 10 11 #include "dm.h" 12 #include "dm-path-selector.h" 13 14 #include <linux/slab.h> 15 #include <linux/module.h> 16 17 #define DM_MSG_PREFIX "multipath service-time" 18 #define ST_MIN_IO 1 19 #define ST_MAX_RELATIVE_THROUGHPUT 100 20 #define ST_MAX_RELATIVE_THROUGHPUT_SHIFT 7 21 #define ST_MAX_INFLIGHT_SIZE ((size_t)-1 >> ST_MAX_RELATIVE_THROUGHPUT_SHIFT) 22 #define ST_VERSION "0.3.0" 23 24 struct selector { 25 struct list_head valid_paths; 26 struct list_head failed_paths; 27 spinlock_t lock; 28 }; 29 30 struct path_info { 31 struct list_head list; 32 struct dm_path *path; 33 unsigned repeat_count; 34 unsigned relative_throughput; 35 atomic_t in_flight_size; /* Total size of in-flight I/Os */ 36 }; 37 38 static struct selector *alloc_selector(void) 39 { 40 struct selector *s = kmalloc(sizeof(*s), GFP_KERNEL); 41 42 if (s) { 43 INIT_LIST_HEAD(&s->valid_paths); 44 INIT_LIST_HEAD(&s->failed_paths); 45 spin_lock_init(&s->lock); 46 } 47 48 return s; 49 } 50 51 static int st_create(struct path_selector *ps, unsigned argc, char **argv) 52 { 53 struct selector *s = alloc_selector(); 54 55 if (!s) 56 return -ENOMEM; 57 58 ps->context = s; 59 return 0; 60 } 61 62 static void free_paths(struct list_head *paths) 63 { 64 struct path_info *pi, *next; 65 66 list_for_each_entry_safe(pi, next, paths, list) { 67 list_del(&pi->list); 68 kfree(pi); 69 } 70 } 71 72 static void st_destroy(struct path_selector *ps) 73 { 74 struct selector *s = ps->context; 75 76 free_paths(&s->valid_paths); 77 free_paths(&s->failed_paths); 78 kfree(s); 79 ps->context = NULL; 80 } 81 82 static int st_status(struct path_selector *ps, struct dm_path *path, 83 status_type_t type, char *result, unsigned maxlen) 84 { 85 unsigned sz = 0; 86 struct path_info *pi; 87 88 if (!path) 89 DMEMIT("0 "); 90 else { 91 pi = path->pscontext; 92 93 switch (type) { 94 case STATUSTYPE_INFO: 95 DMEMIT("%d %u ", atomic_read(&pi->in_flight_size), 96 pi->relative_throughput); 97 break; 98 case STATUSTYPE_TABLE: 99 DMEMIT("%u %u ", pi->repeat_count, 100 pi->relative_throughput); 101 break; 102 case STATUSTYPE_IMA: 103 result[0] = '\0'; 104 break; 105 } 106 } 107 108 return sz; 109 } 110 111 static int st_add_path(struct path_selector *ps, struct dm_path *path, 112 int argc, char **argv, char **error) 113 { 114 struct selector *s = ps->context; 115 struct path_info *pi; 116 unsigned repeat_count = ST_MIN_IO; 117 unsigned relative_throughput = 1; 118 char dummy; 119 unsigned long flags; 120 121 /* 122 * Arguments: [<repeat_count> [<relative_throughput>]] 123 * <repeat_count>: The number of I/Os before switching path. 124 * If not given, default (ST_MIN_IO) is used. 125 * <relative_throughput>: The relative throughput value of 126 * the path among all paths in the path-group. 127 * The valid range: 0-<ST_MAX_RELATIVE_THROUGHPUT> 128 * If not given, minimum value '1' is used. 129 * If '0' is given, the path isn't selected while 130 * other paths having a positive value are 131 * 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 176 static 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 187 static 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 */ 215 static 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 277 static 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; 299 out: 300 spin_unlock_irqrestore(&s->lock, flags); 301 return ret; 302 } 303 304 static 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 314 static 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 324 static 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 340 static 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 352 static 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 360 module_init(dm_st_init); 361 module_exit(dm_st_exit); 362 363 MODULE_DESCRIPTION(DM_NAME " throughput oriented path selector"); 364 MODULE_AUTHOR("Kiyoshi Ueda <k-ueda@ct.jp.nec.com>"); 365 MODULE_LICENSE("GPL"); 366