/* * Copyright (C) 2007-2009 NEC Corporation. All Rights Reserved. * * Module Author: Kiyoshi Ueda * * This file is released under the GPL. * * Throughput oriented path selector. */ #include "dm.h" #include "dm-path-selector.h" #include #define DM_MSG_PREFIX "multipath service-time" #define ST_MIN_IO 1 #define ST_MAX_RELATIVE_THROUGHPUT 100 #define ST_MAX_RELATIVE_THROUGHPUT_SHIFT 7 #define ST_MAX_INFLIGHT_SIZE ((size_t)-1 >> ST_MAX_RELATIVE_THROUGHPUT_SHIFT) #define ST_VERSION "0.2.0" struct selector { struct list_head valid_paths; struct list_head failed_paths; }; struct path_info { struct list_head list; struct dm_path *path; unsigned repeat_count; unsigned relative_throughput; atomic_t in_flight_size; /* Total size of in-flight I/Os */ }; static struct selector *alloc_selector(void) { struct selector *s = kmalloc(sizeof(*s), GFP_KERNEL); if (s) { INIT_LIST_HEAD(&s->valid_paths); INIT_LIST_HEAD(&s->failed_paths); } return s; } static int st_create(struct path_selector *ps, unsigned argc, char **argv) { struct selector *s = alloc_selector(); if (!s) return -ENOMEM; ps->context = s; return 0; } static void free_paths(struct list_head *paths) { struct path_info *pi, *next; list_for_each_entry_safe(pi, next, paths, list) { list_del(&pi->list); kfree(pi); } } static void st_destroy(struct path_selector *ps) { struct selector *s = ps->context; free_paths(&s->valid_paths); free_paths(&s->failed_paths); kfree(s); ps->context = NULL; } static int st_status(struct path_selector *ps, struct dm_path *path, status_type_t type, char *result, unsigned maxlen) { unsigned sz = 0; struct path_info *pi; if (!path) DMEMIT("0 "); else { pi = path->pscontext; switch (type) { case STATUSTYPE_INFO: DMEMIT("%d %u ", atomic_read(&pi->in_flight_size), pi->relative_throughput); break; case STATUSTYPE_TABLE: DMEMIT("%u %u ", pi->repeat_count, pi->relative_throughput); break; } } return sz; } static int st_add_path(struct path_selector *ps, struct dm_path *path, int argc, char **argv, char **error) { struct selector *s = ps->context; struct path_info *pi; unsigned repeat_count = ST_MIN_IO; unsigned relative_throughput = 1; /* * Arguments: [ []] * : The number of I/Os before switching path. * If not given, default (ST_MIN_IO) is used. * : The relative throughput value of * the path among all paths in the path-group. * The valid range: 0- * If not given, minimum value '1' is used. * If '0' is given, the path isn't selected while * other paths having a positive value are * available. */ if (argc > 2) { *error = "service-time ps: incorrect number of arguments"; return -EINVAL; } if (argc && (sscanf(argv[0], "%u", &repeat_count) != 1)) { *error = "service-time ps: invalid repeat count"; return -EINVAL; } if ((argc == 2) && (sscanf(argv[1], "%u", &relative_throughput) != 1 || relative_throughput > ST_MAX_RELATIVE_THROUGHPUT)) { *error = "service-time ps: invalid relative_throughput value"; return -EINVAL; } /* allocate the path */ pi = kmalloc(sizeof(*pi), GFP_KERNEL); if (!pi) { *error = "service-time ps: Error allocating path context"; return -ENOMEM; } pi->path = path; pi->repeat_count = repeat_count; pi->relative_throughput = relative_throughput; atomic_set(&pi->in_flight_size, 0); path->pscontext = pi; list_add_tail(&pi->list, &s->valid_paths); return 0; } static void st_fail_path(struct path_selector *ps, struct dm_path *path) { struct selector *s = ps->context; struct path_info *pi = path->pscontext; list_move(&pi->list, &s->failed_paths); } static int st_reinstate_path(struct path_selector *ps, struct dm_path *path) { struct selector *s = ps->context; struct path_info *pi = path->pscontext; list_move_tail(&pi->list, &s->valid_paths); return 0; } /* * 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 * * Description: * Basically, the service time is estimated by: * ('pi->in-flight-size' + 'incoming') / 'pi->relative_throughput' * To reduce the calculation, some optimizations are made. * (See comments inline) */ static int st_compare_load(struct path_info *pi1, struct path_info *pi2, size_t incoming) { size_t sz1, sz2, st1, st2; sz1 = atomic_read(&pi1->in_flight_size); sz2 = atomic_read(&pi2->in_flight_size); /* * Case 1: Both have same throughput value. Choose less loaded path. */ if (pi1->relative_throughput == pi2->relative_throughput) return sz1 - sz2; /* * Case 2a: Both have same load. Choose higher throughput path. * Case 2b: One path has no throughput value. Choose the other one. */ if (sz1 == sz2 || !pi1->relative_throughput || !pi2->relative_throughput) return pi2->relative_throughput - pi1->relative_throughput; /* * Case 3: Calculate service time. Choose faster path. * Service time using pi1: * st1 = (sz1 + incoming) / pi1->relative_throughput * Service time using pi2: * st2 = (sz2 + incoming) / pi2->relative_throughput * * To avoid the division, transform the expression to use * multiplication. * Because ->relative_throughput > 0 here, if st1 < st2, * the expressions below are the same meaning: * (sz1 + incoming) / pi1->relative_throughput < * (sz2 + incoming) / pi2->relative_throughput * (sz1 + incoming) * pi2->relative_throughput < * (sz2 + incoming) * pi1->relative_throughput * So use the later one. */ sz1 += incoming; sz2 += incoming; if (unlikely(sz1 >= ST_MAX_INFLIGHT_SIZE || sz2 >= ST_MAX_INFLIGHT_SIZE)) { /* * Size may be too big for multiplying pi->relative_throughput * and overflow. * To avoid the overflow and mis-selection, shift down both. */ sz1 >>= ST_MAX_RELATIVE_THROUGHPUT_SHIFT; sz2 >>= ST_MAX_RELATIVE_THROUGHPUT_SHIFT; } st1 = sz1 * pi2->relative_throughput; st2 = sz2 * pi1->relative_throughput; if (st1 != st2) return st1 - st2; /* * Case 4: Service time is equal. Choose higher throughput path. */ return pi2->relative_throughput - pi1->relative_throughput; } static struct dm_path *st_select_path(struct path_selector *ps, unsigned *repeat_count, size_t nr_bytes) { struct selector *s = ps->context; struct path_info *pi = NULL, *best = NULL; if (list_empty(&s->valid_paths)) return NULL; /* Change preferred (first in list) path to evenly balance. */ list_move_tail(s->valid_paths.next, &s->valid_paths); list_for_each_entry(pi, &s->valid_paths, list) if (!best || (st_compare_load(pi, best, nr_bytes) < 0)) best = pi; if (!best) return NULL; *repeat_count = best->repeat_count; return best->path; } static int st_start_io(struct path_selector *ps, struct dm_path *path, size_t nr_bytes) { struct path_info *pi = path->pscontext; atomic_add(nr_bytes, &pi->in_flight_size); return 0; } static int st_end_io(struct path_selector *ps, struct dm_path *path, size_t nr_bytes) { struct path_info *pi = path->pscontext; atomic_sub(nr_bytes, &pi->in_flight_size); return 0; } static struct path_selector_type st_ps = { .name = "service-time", .module = THIS_MODULE, .table_args = 2, .info_args = 2, .create = st_create, .destroy = st_destroy, .status = st_status, .add_path = st_add_path, .fail_path = st_fail_path, .reinstate_path = st_reinstate_path, .select_path = st_select_path, .start_io = st_start_io, .end_io = st_end_io, }; static int __init dm_st_init(void) { int r = dm_register_path_selector(&st_ps); if (r < 0) DMERR("register failed %d", r); DMINFO("version " ST_VERSION " loaded"); return r; } static void __exit dm_st_exit(void) { int r = dm_unregister_path_selector(&st_ps); if (r < 0) DMERR("unregister failed %d", r); } module_init(dm_st_init); module_exit(dm_st_exit); MODULE_DESCRIPTION(DM_NAME " throughput oriented path selector"); MODULE_AUTHOR("Kiyoshi Ueda "); MODULE_LICENSE("GPL");