dm-mpath: dynamic load balancers (v2)
Subsystems (3)
cover dm-mpath: dynamic load balancers (v2)
Hi,
The patch-set adds the following 2 dynamic load balancers:
o dm-queue-length: queue-length oriented dynamic load balancer
o dm-service-time: service-time oriented dynamic load balancer
This patch-set can be applied on top of 2.6.30-rc3. No dependencies on Alasdair's linux-next patches.
NOTE:
While the patches compile and work with the current bio-based dm, for them to *properly* work, the request-based dm patches should be applied, too.
See <http://marc.info/?l=dm-devel&m=123736590931733&w=2> for why request-based dm improves multipath load balancing.
Summary of the patch-set
========================
1/3: dm-mpath: interface change for dynamic load balancers 2/3: dm-mpath: add queue-length oriented dynamic load balancer 3/3: dm-mpath: add service-time oriented dynamic load balancer
drivers/md/Kconfig | 18 ++ drivers/md/Makefile | 2 drivers/md/dm-mpath.c | 28 ++- drivers/md/dm-path-selector.h | 8 - drivers/md/dm-queue-length.c | 257 +++++++++++++++++++++++++++++++++++ drivers/md/dm-round-robin.c | 2 drivers/md/dm-service-time.c | 301 ++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 603 insertions(+), 13 deletions(-)
CHANGES
=======
v2:
- Rebased to 2.6.30-rc3
v1: (http://marc.info/?l=dm-devel&m=123736539330980&w=2)
- Rebased to 2.6.29-rc8
Thanks,
Kiyoshi Ueda
PATCH 1/3 dm-mpath: interface change for dynamic load balancers
This patch changes the dm path selector interface for dynamic load balancers:
o adding a new hook, start_io()
o adding 'nr_bytes' parameter to select_path()/start_io()/end_io() to pass the size of the I/O
start_io() is called when a target driver actually submits I/O to the selected path.
Path selectors can use it to start accounting of the I/O. (e.g. counting the number of in-flight I/Os.)
The start_io hook is based on the patch posted by Stefan Bader:
https://www.redhat.com/archives/dm-devel/2005-October/msg00050.html
nr_bytes, the size of the I/O, is used by path selectors for size-based decision.
dm-service-time uses it to estimate service time, for example. (Added the nr_bytes member to dm_mpath_io instead of using existing
details.bi_size, since request-based dm patch deletes it.)
--- drivers/md/dm-mpath.c | 28 ++++++++++++++++++---------- drivers/md/dm-path-selector.h | 8 ++++++-- drivers/md/dm-round-robin.c | 2 +- 3 files changed, 25 insertions(+), 13 deletions(-)
drivers/md/dm-mpath.c +18 -10
@@ -102,6 +102,7 @@ struct multipath {struct dm_mpath_io {struct pgpath *pgpath;struct dm_bio_details details; +size_t nr_bytes; };typedef int (*action_fn ) (struct pgpath *pgpath);
@@ -250,11 +251,12 @@ static void __switch_pg(struct multipath m->pg_init_count =0 ; } -static int __choose_path_in_pg (struct multipath *m,struct priority_group *pg) +static int __choose_path_in_pg (struct multipath *m,struct priority_group *pg, +size_t nr_bytes) {struct dm_path *path; - path = pg->ps.type->select_path (&pg->ps, &m->repeat_count); + path = pg->ps.type->select_path (&pg->ps, &m->repeat_count, nr_bytes);if (!path)return -ENXIO ;
@@ -266,7 +268,7 @@ static int __choose_path_in_pg(struct mureturn 0 ; } -static void __choose_pgpath (struct multipath *m) +static void __choose_pgpath (struct multipath *m,size_t nr_bytes) {struct priority_group *pg;unsigned bypassed =1 ;
@@ -278,12 +280,12 @@ static void __choose_pgpath(struct multiif (m->next_pg) { pg = m->next_pg; m->next_pg =NULL ; -if (!__choose_path_in_pg (m, pg)) +if (!__choose_path_in_pg (m, pg, nr_bytes))return ; }/* Don't change PG until it has no remaining paths */ -if (m->current_pg && !__choose_path_in_pg (m, m->current_pg)) +if (m->current_pg && !__choose_path_in_pg (m, m->current_pg, nr_bytes))return ;/*
@@ -295,7 +297,7 @@ static void __choose_pgpath(struct multilist_for_each_entry (pg, &m->priority_groups, list) {if (pg->bypassed == bypassed)continue ; -if (!__choose_path_in_pg (m, pg)) +if (!__choose_path_in_pg (m, pg, nr_bytes))return ; } }while (bypassed--);
@@ -326,6 +328,7 @@ static int map_io(struct multipath *m, s struct dm_mpath_io *mpio, unsigned was_queued) { int r = DM_MAPIO_REMAPPED; +size_t nr_bytes = bio->bi_size;unsigned long flags;struct pgpath *pgpath;
@@ -334,7 +337,7 @@ static int map_io(struct multipath *m, s/* Do we need to select a new pgpath? */ if (!m->current_pgpath || (!m->queue_io && (m->repeat_count && --m->repeat_count ==0 ))) -__choose_pgpath (m); +__choose_pgpath (m, nr_bytes); pgpath = m->current_pgpath;
@@ -359,6 +362,11 @@ static int map_io(struct multipath *m, s r = -EIO ;/* Failed */ mpio->pgpath = pgpath; + mpio->nr_bytes = nr_bytes; + +if (r ==DM_MAPIO_REMAPPED && pgpath->pg->ps.type->start_io) + pgpath->pg->ps.type->start_io (&pgpath->pg->ps, &pgpath->path, + nr_bytes);spin_unlock_irqrestore (&m->lock, flags);
@@ -437,7 +445,7 @@ static void process_queued_ios(struct wo goto out;if (!m->current_pgpath) -__choose_pgpath (m); +__choose_pgpath (m,0 ); pgpath = m->current_pgpath;
@@ -1195,7 +1203,7 @@ static int multipath_end_io(struct dm_taif (pgpath) { ps = &pgpath->pg->ps;if (ps->type->end_io) - ps->type->end_io (ps, &pgpath->path); + ps->type->end_io (ps, &pgpath->path, mpio->nr_bytes); }if (r !=DM_ENDIO_INCOMPLETE )mempool_free (mpio, m->mpio_pool);
@@ -1411,7 +1419,7 @@ static int multipath_ioctl(struct dm_tarspin_lock_irqsave (&m->lock, flags);if (!m->current_pgpath) -__choose_pgpath (m); +__choose_pgpath (m,0 );if (m->current_pgpath) { bdev = m->current_pgpath->path.dev->bdev;
drivers/md/dm-path-selector.h +6 -2
@@ -56,7 +56,8 @@ struct path_selector_type {* the path fails. */ struct dm_path *(*select_path) (struct path_selector *ps, -unsigned *repeat_count); +unsigned *repeat_count, +size_t nr_bytes);/* * Notify the selector that a path has failed.
@@ -75,7 +76,10 @@ struct path_selector_type {int (*status) (struct path_selector *ps,struct dm_path *path,status_type_t type,char *result,unsigned int maxlen); -int (*end_io) (struct path_selector *ps,struct dm_path *path); +int (*start_io) (struct path_selector *ps,struct dm_path *path, +size_t nr_bytes); +int (*end_io) (struct path_selector *ps,struct dm_path *path, +size_t nr_bytes); };/* Register a path selector */
drivers/md/dm-round-robin.c +1 -1
@@ -161,7 +161,7 @@ static int rr_reinstate_path(struct path }static struct dm_path *rr_select_path (struct path_selector *ps, -unsigned *repeat_count) +unsigned *repeat_count,size_t nr_bytes) {struct selector *s = (struct selector *) ps->context;struct path_info *pi =NULL ;
PATCH 2/3 dm-mpath: add queue-length oriented dynamic load balancer
In reply to Kiyoshi UedaThis patch adds a dynamic load balancer, dm-queue-length, which balances the number of in-flight I/Os.
The code is based on the patch posted by Stefan Bader:
https://www.redhat.com/archives/dm-devel/2005-October/msg00050.html
--- drivers/md/Kconfig | 9 + drivers/md/Makefile | 1 drivers/md/dm-queue-length.c | 257 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 267 insertions(+)
drivers/md/dm-queue-length.c new file +257 -0
@@ -0,0 +1,257 @@ +/* +* Copyright (C) 2004-2005 IBM Corp. All Rights Reserved. +* Copyright (C) 2006-2009 NEC Corporation. +* +* dm-queue-length.c +* +* Module Author: Stefan Bader, IBM +* Modified by: Kiyoshi Ueda, NEC +* +* This file is released under the GPL. +* +* queue-length path selector, which chooses a path with the least number of +* in-flight I/Os. +*/ + +#include "dm.h" +#include "dm-path-selector.h" + +#include <linux/slab.h> +#include <linux/ctype.h> +#include <linux/errno.h> +#include <linux/module.h> +#include <asm/atomic.h> + +#define DM_MSG_PREFIX "multipath queue-length" +#define QL_MIN_IO 128 +#define QL_VERSION "0.1.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 int repeat_count; +atomic_t qlen; +}; + +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 ql_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 ql_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 ql_destroy (struct path_selector *ps) +{ +struct selector *s = (struct selector *) ps->context; + +ql_free_paths (&s->valid_paths); +ql_free_paths (&s->failed_paths); +kfree (s); + ps->context =NULL ; +} + +static int ql_status (struct path_selector *ps,struct dm_path *path, +status_type_t type,char *result,unsigned int maxlen) +{ +int sz =0 ; +struct path_info *pi; + +/* When called with (path == NULL), return selector status/args. */ +if (!path) +DMEMIT ("0 " ); +else { + pi = path->pscontext; + +switch (type) { +case STATUSTYPE_INFO : +DMEMIT ("%u " ,atomic_read (&pi->qlen)); +break ; +case STATUSTYPE_TABLE : +DMEMIT ("%u " , pi->repeat_count); +break ; + } + } + +return sz; +} + +static int ql_add_path (struct path_selector *ps,struct dm_path *path, +int argc,char **argv,char **error) +{ +struct selector *s = (struct selector *) ps->context; +struct path_info *pi; +unsigned int repeat_count =QL_MIN_IO ; + +/* Parse the arguments */ +if (argc >1 ) { + *error ="queue-length ps: incorrect number of arguments" ; +return -EINVAL ; + } + +/* First path argument is number of I/Os before switching path. */ +if ((argc ==1 ) && (sscanf (argv[0 ],"%u" , &repeat_count) !=1 )) { + *error ="queue-length ps: invalid repeat count" ; +return -EINVAL ; + } + +/* Allocate the path information structure */ + pi =kmalloc (sizeof (*pi),GFP_KERNEL ); +if (!pi) { + *error ="queue-length ps: Error allocating path information" ; +return -ENOMEM ; + } + + pi->path = path; + pi->repeat_count = repeat_count; +atomic_set (&pi->qlen,0 ); + + path->pscontext = pi; + +list_add_tail (&pi->list, &s->valid_paths); + +return 0 ; +} + +static void ql_fail_path (struct path_selector *ps,struct dm_path *path) +{ +struct selector *s = (struct selector *) ps->context; +struct path_info *pi = path->pscontext; + +list_move (&pi->list, &s->failed_paths); +} + +static int ql_reinstate_path (struct path_selector *ps,struct dm_path *path) +{ +struct selector *s = (struct selector *) ps->context; +struct path_info *pi = path->pscontext; + +list_move_tail (&pi->list, &s->valid_paths); + +return 0 ; +} + +static struct dm_path *ql_select_path (struct path_selector *ps, +unsigned *repeat_count,size_t nr_bytes) +{ +struct selector *s = (struct selector *) 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 || + (atomic_read (&pi->qlen) <atomic_read (&best->qlen))) + best = pi; + +if (!atomic_read (&best->qlen)) +break ; + } + +if (!best) +return NULL ; + + *repeat_count = best->repeat_count; + +return best->path; +} + +static int ql_start_io (struct path_selector *ps,struct dm_path *path, +size_t nr_bytes) +{ +struct path_info *pi = path->pscontext; + +atomic_inc (&pi->qlen); + +return 0 ; +} + +static int ql_end_io (struct path_selector *ps,struct dm_path *path, +size_t nr_bytes) +{ +struct path_info *pi = path->pscontext; + +atomic_dec (&pi->qlen); + +return 0 ; +} + +static struct path_selector_type ql_ps = { + .name ="queue-length" , + .module =THIS_MODULE , + .table_args =1 , + .info_args =1 , + .create = ql_create, + .destroy = ql_destroy, + .status = ql_status, + .add_path = ql_add_path, + .fail_path = ql_fail_path, + .reinstate_path = ql_reinstate_path, + .select_path = ql_select_path, + .start_io = ql_start_io, + .end_io = ql_end_io, +}; + +static int __init dm_ql_init (void ) +{ +int r =dm_register_path_selector (&ql_ps); + +if (r <0 ) +DMERR ("register failed %d" , r); + +DMINFO ("version " QL_VERSION " loaded" ); + +return r; +} + +static void __exit dm_ql_exit(void) +{ +int r =dm_unregister_path_selector (&ql_ps); + +if (r <0 ) +DMERR ("unregister failed %d" , r); +} + +module_init (dm_ql_init); +module_exit (dm_ql_exit); + +MODULE_AUTHOR ("Stefan Bader <Stefan.Bader at de.ibm.com>" ); +MODULE_DESCRIPTION ( +"(C) Copyright IBM Corp. 2004,2005 All Rights Reserved.\n" +DM_NAME " path selector to balance the number of in-flight I/Os" +); +MODULE_LICENSE ("GPL" );
drivers/md/Makefile +1 -0
@@ -36,6 +36,7 @@ obj-$(CONFIG_BLK_DEV_DM) += dm-mod.o obj-$(CONFIG_DM_CRYPT) += dm-crypt.o obj-$(CONFIG_DM_DELAY) += dm-delay.o obj-$(CONFIG_DM_MULTIPATH) += dm-multipath.o dm-round-robin.o +obj-$(CONFIG_DM_MULTIPATH_QL) += dm-queue-length.o obj-$(CONFIG_DM_SNAPSHOT) += dm-snapshot.o obj-$(CONFIG_DM_MIRROR) += dm-mirror.o dm-log.o dm-region-hash.o obj-$(CONFIG_DM_ZERO) += dm-zero.o
drivers/md/Kconfig +9 -0
@@ -249,6 +249,15 @@ config DM_MULTIPATH ---help--- Allow volume managers to support multipath hardware. +config DM_MULTIPATH_QL + tristate "I/O Path Selector based on the number of in-flight I/Os" + depends on DM_MULTIPATH + ---help--- + This path selector is a dynamic load balancer which selects + a path having the least number of in-flight I/Os. + + If unsure, say N. + config DM_DELAY tristate "I/O delaying target (EXPERIMENTAL)" depends on BLK_DEV_DM && EXPERIMENTAL
PATCH 3/3 dm-mpath: add service-time oriented dynamic load balancer
In reply to Kiyoshi UedaThis patch adds a service time oriented dynamic load balancer, dm-service-time, which selects a path with the shortest estimated service time for the incoming I/O.
The service time is estimated by dividing the in-flight I/O size with performance value of each path.
The performance value can be given as a table argument at the table loading time. If no performance value is given, all paths are recognized as equal performance.
--- drivers/md/Kconfig | 9 + drivers/md/Makefile | 1 drivers/md/dm-service-time.c | 301 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 311 insertions(+)
drivers/md/dm-service-time.c new file +301 -0
@@ -0,0 +1,301 @@ +/* +* 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" + +#define DM_MSG_PREFIX "multipath service-time" +#define ST_MIN_IO 1 +#define ST_VERSION "0.1.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 int repeat_count; +size_t perf; +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 = (struct selector *) 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 int maxlen) +{ +int sz =0 ; +struct path_info *pi; + +if (!path) +DMEMIT ("0 " ); +else { + pi = path->pscontext; + +switch (type) { +case STATUSTYPE_INFO : +DMEMIT ("%u %lu " ,atomic_read (&pi->in_flight_size), + pi->perf); +break ; +case STATUSTYPE_TABLE : +DMEMIT ("%u %lu " , pi->repeat_count, pi->perf); +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 = (struct selector *) ps->context; +struct path_info *pi; +unsigned int repeat_count =ST_MIN_IO ; +size_t perf =1 ; + +if (argc >2 ) { + *error ="service-time ps: incorrect number of arguments" ; +return -EINVAL ; + } + +/* First path argument is number of I/Os before switching path. */ +if ((argc >0 ) && (sscanf (argv[0 ],"%u" , &repeat_count) !=1 )) { + *error ="service-time ps: invalid repeat count" ; +return -EINVAL ; + } + +/* +* Second path argument is a relative performance value. +* If 0 is given, the path isn't used while other paths having +* a positive value are available. +*/ +if ((argc ==2 ) && (sscanf (argv[1 ],"%lu" , &perf) !=1 )) { + *error ="service-time ps: invalid performance 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->perf = perf; +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 = (struct selector *) 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 = (struct selector *) ps->context; +struct path_info *pi = path->pscontext; + +list_move_tail (&pi->list, &s->valid_paths); + +return 0 ; +} + +/* +* Returns: +* < 0 : pi1 is better +* 0 : no difference between pi1 and pi2 +* > 0 : pi2 is better +*/ +static int st_compare_load (struct path_info *pi1,struct path_info *pi2, +size_t incoming) +{ +size_t sz1, sz2; + + sz1 =atomic_read (&pi1->in_flight_size); + sz2 =atomic_read (&pi2->in_flight_size); + +/* +* Case 1: Both have same performace value. Choose less loaded path. +*/ +if (pi1->perf == pi2->perf) +return sz1 - sz2; + +/* +* Case 2a: Both have same load. Choose higher performance path. +* Case 2b: One path has no performance value. Choose the other one. +*/ +if (sz1 == sz2 || !pi1->perf || !pi2->perf) +return pi2->perf - pi1->perf; + +/* +* Case 3: Calculate service time. Choose faster path. +* if ((sz1+incoming)/pi1->perf < (sz2+incoming)/pi2->perf) pi1 +* if ((sz1+incoming)/pi1->perf > (sz2+incoming)/pi2->perf) pi2 +*/ + sz1 += incoming; + sz2 += incoming; +while (sz1 && sz2 && (sz1 < pi1->perf) && (sz2 < pi2->perf)) { +/* Size is not big enough to compare by division. Shift up */ + sz1 <<=2 ; + sz2 <<=2 ; + } +do_div (sz1, pi1->perf); +do_div (sz2, pi2->perf); + +if (sz1 != sz2) +return sz1 - sz2; + +/* +* Case 4: Service time is equal. Choose higher performance path. +*/ +return pi2->perf - pi1->perf; +} + +static struct dm_path *st_select_path (struct path_selector *ps, +unsigned *repeat_count,size_t nr_bytes) +{ +struct selector *s = (struct selector *) 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 <[email protected]>" ); +MODULE_LICENSE ("GPL" );
drivers/md/Makefile +1 -0
@@ -37,6 +37,7 @@ obj-$(CONFIG_DM_CRYPT) += dm-crypt.o obj-$(CONFIG_DM_DELAY) += dm-delay.o obj-$(CONFIG_DM_MULTIPATH) += dm-multipath.o dm-round-robin.o obj-$(CONFIG_DM_MULTIPATH_QL) += dm-queue-length.o +obj-$(CONFIG_DM_MULTIPATH_ST) += dm-service-time.o obj-$(CONFIG_DM_SNAPSHOT) += dm-snapshot.o obj-$(CONFIG_DM_MIRROR) += dm-mirror.o dm-log.o dm-region-hash.o obj-$(CONFIG_DM_ZERO) += dm-zero.o
drivers/md/Kconfig +9 -0
@@ -258,6 +258,15 @@ config DM_MULTIPATH_QL If unsure, say N. +config DM_MULTIPATH_ST + tristate "I/O Path Selector based on the service time" + depends on DM_MULTIPATH + ---help--- + This path selector is a dynamic load balancer which selects + a path to complete the incoming I/O with the shortest time. + + If unsure, say N. + config DM_DELAY tristate "I/O delaying target (EXPERIMENTAL)" depends on BLK_DEV_DM && EXPERIMENTAL
Alasdair G Kergon
maintainerRe: [PATCH 2/3] dm-mpath: add queue-length oriented dynamic load balancer
In reply to Kiyoshi Uedadrivers/md/dm-queue-length.c line 37
Quoted 1 line · Kiyoshi Ueda
drivers/md/dm-queue-length.c new file +1
-0+unsigned int repeat_count;
Just 'unsigned repeat_count'
Review
Quoted 1 line
(quoted diff) +1
-0+ struct selector *s = (struct selector *) ps->context;
Drop the cast when it's from void.
struct selector *s = ps->context;
drivers/md/dm-queue-length.c line 85
Quoted 2 lines
drivers/md/dm-queue-length.c new file +2
-0+static int ql_status (struct path_selector *ps,struct dm_path *path, +status_type_t type,char *result,unsigned int maxlen)
unsigned maxlen
(We're doing things like this in all new patches, but only changing existing code when it's touched for some other reason.)
drivers/md/dm-queue-length.c line 87
Quoted 1 line
drivers/md/dm-queue-length.c new file +1
-0+int sz =0 ;
signed or unsigned sz?
(It's already used inconsistently, I know - but is unsigned better here?)
drivers/md/dm-queue-length.c line 98
Quoted 2 lines
drivers/md/dm-queue-length.c new file +2
-0+case STATUSTYPE_INFO : +DMEMIT ("%u " ,atomic_read (&pi->qlen));
Signed or unsigned?
drivers/md/dm-queue-length.c line 116
Quoted 1 line
drivers/md/dm-queue-length.c new file +1
-0+/* Parse the arguments */
Please document parameters and selection algorithm in Documentation dir and maybe in inline comments too - it's not immediately obvious exactly how it behaves.
drivers/md/dm-queue-length.c line 165
Quoted 2 lines
drivers/md/dm-queue-length.c new file +2
-0+static struct dm_path *ql_select_path (struct path_selector *ps, +unsigned *repeat_count,size_t nr_bytes)
Alasdair
Alasdair G Kergon
maintainerRe: [PATCH 3/3] dm-mpath: add service-time oriented dynamic load balancer
In reply to Kiyoshi Uedadrivers/md/dm-service-time.c line 87
Quoted 4 lines · Kiyoshi Ueda
drivers/md/dm-service-time.c new file +4
-0+struct selector *s = (struct selector *) ps->context; + status_type_t type, char *result, unsigned int maxlen) + int sz = 0; + DMEMIT("%u %lu ", atomic_read(&pi->in_flight_size),
(similar comments)
drivers/md/dm-service-time.c line 91
Quoted 1 line
drivers/md/dm-service-time.c new file +1
-0+DMEMIT ("%u %lu " , pi->repeat_count, pi->perf);
Need to handle both 32 and 64 bit archs: cast to llu.
drivers/md/dm-service-time.c line 123
Quoted 1 line
drivers/md/dm-service-time.c new file +1
-0+if ((argc ==2 ) && (sscanf (argv[1 ],"%lu" , &perf) !=1 )) {
Please do sscanf for size_t the same way as dm-crypt does.
(Or scan for lu, if the intent is to impose a size limit ahead of the later do_div() then cast explicitly.)
Quoted 6 lines
+/*
+ * Returns:
+ * < 0 : pi1 is better
+ * 0 : no difference between pi1 and pi2
+ * > 0 : pi2 is better
+ */
Please document the parameters and algorithm.
Nothing explains what the performance value is for and examples of anticipated values.
drivers/md/dm-service-time.c line 205
Quoted 2 lines
drivers/md/dm-service-time.c new file +2
-0+do_div (sz1, pi1->perf); +do_div (sz2, pi2->perf);
Or sector_div ?
But what's the performance of those divisions like? Is there a better way of getting the same answer? Is there validation limiting the size of 'perf'?
(Also, did you check there's adequate locking & memory barriers around all the atomics?)
Alasdair
Re: [PATCH 2/3] dm-mpath: add queue-length oriented dynamic load balancer
In reply to Alasdair G KergonHi Alasdair,
Thank you for the review and comments.
I'm totally agree with your comments.
I found that you have already updated the patch in your editing tree, thanks. I attached patches for remaining parts of your comments.
Please review and apply.
Quoted 4 lines · Alasdair G Kergon
Review
Quoted 1 line · Kiyoshi Ueda
(quoted diff) +1
-0+ unsigned int repeat_count;Just 'unsigned
repeat_count'
OK. (You have already fixed this.)
Quoted 5 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ struct selector *s = (struct selector *) ps->context;Drop the cast when it's from void.
struct selector *s = ps->context;
OK. (You have already fixed this.)
Quoted 4 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+static int ql_status(struct path_selector *ps, struct dm_path *path, + status_type_t type, char *result, unsigned int maxlen)unsigned maxlen
OK, fixed in rqdm-dlb-02-queue-length-dlb-type-fixes.patch
Quoted 2 lines
(We're doing things like this in all new patches, but only changing existing code when it's touched for some other reason.)
OK, I followed the style of dm-round-robin and I understand your preference now.
I'll also check the request-based dm patch-set, too, when I update and repost it.
Quoted 4 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ int sz = 0;signed or unsigned sz?
(It's already used inconsistently, I know - but is unsigned better here?)
Yes, I think unsigned is better. (You have already fixed this.)
Quoted 4 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ case STATUSTYPE_INFO: + DMEMIT("%u ", atomic_read(&pi->qlen));Signed or unsigned?
qlen should be always >= 0, but atomic_t is defined as signed. So I use signed here.
Fixed in rqdm-dlb-02-queue-length-dlb-type-fixes.patch
Quoted 8 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ /* Parse the arguments */Please document parameters and selection algorithm in Documentation dir and maybe in inline comments too - it's not immediately obvious exactly how it behaves.
Review
Quoted 2 lines
(quoted diff) +2
-0+static struct dm_path *ql_select_path(struct path_selector *ps, + unsigned *repeat_count, size_t nr_bytes)
OK, added comments/documentaion in
rqdm-dlb-02-queue-length-dlb-document.patch.
Thanks,
Kiyoshi Ueda
o Use 'unsigned' instead of 'unsigned int' for maxlen in dm-queue-length.
o Fix the print format to use %d for qlen in dm-queue-length, since atomic_t is defined as 'int', not 'unsigned int'.
--- drivers/md/dm-queue-length.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
drivers/md/dm-queue-length.c +2 -2
@@ -82,7 +82,7 @@ static void ql_destroy(struct path_selec }static int ql_status (struct path_selector *ps,struct dm_path *path, -status_type_t type,char *result,unsigned int maxlen) +status_type_t type,char *result,unsigned maxlen) {unsigned sz =0 ;struct path_info *pi;
@@ -95,7 +95,7 @@ static int ql_status(struct path_selectoswitch (type) {case STATUSTYPE_INFO : -DMEMIT ("%u " ,atomic_read (&pi->qlen)); +DMEMIT ("%d " ,atomic_read (&pi->qlen));break ;case STATUSTYPE_TABLE :DMEMIT ("%u " , pi->repeat_count);
Add documents/comments for dm-queue-length.
--- Documentation/device-mapper/dm-queue-length.txt | 39 ++++++++++++++++++++++++ drivers/md/dm-queue-length.c | 12 +++++-- 2 files changed, 48 insertions(+), 3 deletions(-)
Documentation/device-mapper/dm-queue-length.txt new file +39 -0
@@ -0,0 +1,39 @@ +dm-queue-length +=============== + +dm-queue-length is a path selector module for device-mapper targets, +which selects a path having the least number of in-flight I/Os. +The path selector name is 'queue-length'. + +Table parameters for each path: [<repeat_count>] + <repeat_count>: The number of I/Os to dispatch using the selected + path before switching to the next path. + If not given, internal default is used. To check + the default value, see the activated table. + +Status for each path: <status> <fail-count> <in-flight> + <status>: 'A' if the path is active, 'F' if the path is failed. + <fail-count>: The number of path failures. + <in-flight>: The number of in-flight I/Os on the path. + + +Algorithm +========= + +dm-queue-length increments/decrements 'in-flight' when an I/O is +dispatched/completed respectively. +dm-queue-length selects a path having minimum 'in-flight'. + + +Examples +======== +In case that 2 paths (sda and sdb) are used with repeat_count == 128. + +# echo "0 10 multipath 0 0 1 1 queue-length 0 2 1 8:0 128 8:16 128" \ + dmsetup create test +# +# dmsetup table +test: 0 10 multipath 0 0 1 1 queue-length 0 2 1 8:0 128 8:16 128 +# +# dmsetup status +test: 0 10 multipath 2 0 0 0 1 1 E 0 2 1 8:0 A 0 0 8:16 A 0 0
drivers/md/dm-queue-length.c +9 -3
@@ -35,7 +35,7 @@ struct path_info {struct list_head list;struct dm_path *path;unsigned repeat_count; -atomic_t qlen; +atomic_t qlen;/* the number of in-flight I/Os */ };static struct selector *alloc_selector (void )
@@ -113,13 +113,16 @@ static int ql_add_path(struct path_selecstruct path_info *pi;unsigned repeat_count =QL_MIN_IO ; -/* Parse the arguments */ +/* +* Arguments: [<repeat_count>] +* <repeat_count>: The number of I/Os before switching path. +* If not given, default (QL_MIN_IO) is used. +*/ if (argc >1 ) { *error ="queue-length ps: incorrect number of arguments" ;return -EINVAL ; } -/* First path argument is number of I/Os before switching path. */ if ((argc ==1 ) && (sscanf (argv[0 ],"%u" , &repeat_count) !=1 )) { *error ="queue-length ps: invalid repeat count" ;return -EINVAL ;
@@ -161,6 +164,9 @@ static int ql_reinstate_path(struct pathreturn 0 ; } +/* +* Select a path having the minimum number of in-flight I/Os +*/ static struct dm_path *ql_select_path (struct path_selector *ps,unsigned *repeat_count,size_t nr_bytes) {
Re: Re: [PATCH 2/3] dm-mpath: add queue-length oriented dynamic load balancer
Quoted 1 line · Kiyoshi Ueda
Please review and apply.
Pushed to linux-next.
Alasdair
Re: [PATCH 3/3] dm-mpath: add service-time oriented dynamic load balancer
In reply to Alasdair G KergonHi Alasdair,
Thank you for the review and comments.
I'm totally agree with your comments.
I found that you have already updated the patch in your editing tree, thanks. But I'm considering to update the patch to be simpler.
Please see below.
Quoted 7 lines · Alasdair G Kergon
Review
Quoted 4 lines · Kiyoshi Ueda
(quoted diff) +4
-0+ struct selector *s = (struct selector *) ps->context; + status_type_t type, char *result, unsigned int maxlen) + int sz = 0; + DMEMIT("%u %lu ", atomic_read(&pi->in_flight_size),(similar comments)
OK, you have already fixed the pointer cast, the sz type and the print format for in_flight_size.
I'll fix the type of maxlen.
Quoted 9 lines
Quoted 6 lines
+/*
+ * Returns:
+ * < 0 : pi1 is better
+ * 0 : no difference between pi1 and pi2
+ * > 0 : pi2 is better
+ */Please document the parameters and algorithm.
Nothing explains what the performance value is for and examples of anticipated values.
OK, I'll add comments and documentation like the attached patch.
Quoted 10 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ DMEMIT("%u %lu ", pi->repeat_count, pi->perf);Need to handle both 32 and 64 bit archs: cast to llu.
Review
Quoted 1 line
(quoted diff) +1
-0+ if ((argc == 2) && (sscanf(argv[1], "%lu", &perf) != 1)) {Please do sscanf for
size_tthe same way as dm-crypt does.
(Or scan for lu, if the intent is to impose a size limit ahead of the laterdo_div()then cast explicitly.)
Quoted 8 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ do_div(sz1, pi1->perf); + do_div(sz2, pi2->perf);Or
sector_div?But what's the performance of those divisions like? Is there a better way of getting the same answer? Is there validation limiting the size of 'perf'?
I tried to use multiplication before, but it didn't work well, because overflow happened when 'in_flight_size' and 'perf' had pretty big values, and then I got wrong comparison results. So I decided to use division.
However, if I limit the 'perf' value in smaller range (e.g. 0 to 100), such overflow shouldn't happen. So I should be able to use multiplication. Also, I don't need to use size_t for 'perf', because 'unsinged' should be enough for such small values.
Quoted 2 lines
(Also, did you check there's adequate locking & memory barriers around all the atomics?)
Yes, I did and I found no problem in both dm-queue-length and dm-service-time.
Thanks,
Kiyoshi Ueda
Add documents/comments for dm-service-time.
--- Documentation/device-mapper/dm-service-time.txt | 87 ++++++++++++++++++++++++ drivers/md/dm-service-time.c | 26 +++++-- 2 files changed, 107 insertions(+), 6 deletions(-)
Documentation/device-mapper/dm-service-time.txt new file +87 -0
@@ -0,0 +1,87 @@ +dm-service-time +=============== + +dm-service-time is a path selector module for device-mapper targets, +which selects a path with the shortest estimated service time for +the incoming I/O. + +The service time for each path is estimated by dividing the total size +of in-flight I/Os on a path with the performance value of the path. +The performance value is a relative throughput value among all paths +in a path-group, and it can be specified as a table argument. + +The path selector name is 'service-time'. + +Table parameters for each path: [<repeat_count> [<performance>]] + <repeat_count>: The number of I/Os to dispatch using the selected + path before switching to the next path. + If not given, internal default is used. To check + the default value, see the activated table. + <performance>: The relative throughput value of the path + among all paths in the path-group. + 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. + +Status for each path: <status> <fail-count> <in-flight-size> <performance> + <status>: 'A' if the path is active, 'F' if the path is failed. + <fail-count>: The number of path failures. + <in-flight-size>: The size of in-flight I/Os on the path. + <performance>: The relative throughput value of the path + among all paths in the path-group. + + +Algorithm +========= + +dm-service-time adds the I/O size to 'in-flight-size' when the I/O is +dispatched and substracts when completed. +Basically, dm-service-time selects a path having minimum service time +which is calculated by: + + ('in-flight-size' + 'size-of-incoming-io') / 'performance' + +However, some optimizations below are used to reduce the calculation +as much as possible. + + 1. If the paths have the same 'performance', skip the division + and just compare the 'in-flight-size'. + + 2. If the paths have the same 'in-flight-size', skip the division + and just compare the 'performance'. + + 3. If some paths have non-zero 'performance' and others have zero + 'performance', ignore those paths with zero 'performance'. + +If such optimizations can't be applied, calculate service time, and +compare service time. +If calculated service time is equal, the path having maximum 'performance' +may be better. So compare 'performance' then. + + +Examples +======== +In case that 2 paths (sda and sdb) are used with repeat_count == 128 +and sda has an average throughput 1GB/s and sdb has 4GB/s, 'performance' +value may be '1' for sda and '4' for sdb. + +# echo "0 10 multipath 0 0 1 1 service-time 0 2 2 8:0 128 1 8:16 128 4" \ + dmsetup create test +# +# dmsetup table +test: 0 10 multipath 0 0 1 1 service-time 0 2 2 8:0 128 1 8:16 128 4 +# +# dmsetup status +test: 0 10 multipath 2 0 0 0 1 1 E 0 2 2 8:0 A 0 0 1 8:16 A 0 0 4 + + +Or '2' for sda and '8' for sdb would be also true. + +# echo "0 10 multipath 0 0 1 1 service-time 0 2 2 8:0 128 2 8:16 128 8" \ + dmsetup create test +# +# dmsetup table +test: 0 10 multipath 0 0 1 1 service-time 0 2 2 8:0 128 2 8:16 128 8 +# +# dmsetup status +test: 0 10 multipath 2 0 0 0 1 1 E 0 2 2 8:0 A 0 0 2 8:16 A 0 0 8
drivers/md/dm-service-time.c +20 -6
@@ -105,22 +105,27 @@ static int st_add_path(struct path_selecunsigned repeat_count =ST_MIN_IO ;unsigned long long tmpll =1 ; +/* +* Arguments: [<repeat_count> [<performance>]] +* <repeat_count>: The number of I/Os before switching path. +* If not given, default (ST_MIN_IO) is used. +* <performance>: The relative throughput value of the path +* among all paths in the path-group. +* 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 ; } -/* First path argument is number of I/Os before switching path. */ if ((argc >0 ) && (sscanf (argv[0 ],"%u" , &repeat_count) !=1 )) { *error ="service-time ps: invalid repeat count" ;return -EINVAL ; } -/* -* Second path argument is a relative performance value. -* If 0 is given, the path isn't used while other paths having -* a positive value are available. -*/ if ((argc ==2 ) && (sscanf (argv[1 ],"%llu" , &tmpll) !=1 )) { *error ="service-time ps: invalid performance value" ;return -EINVAL ;
@@ -164,10 +169,19 @@ static int st_reinstate_path(struct path }/* +* 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->perf' +* 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)
Alasdair G Kergon
maintainerRe: Re: [PATCH 3/3] dm-mpath: add service-time oriented dynamic load balancer
Quoted 4 lines · Kiyoshi Ueda
However, if I limit the 'perf' value in smaller range (e.g. 0 to 100), such overflow shouldn't happen. So I should be able to use multiplication. Also, I don't need to use
size_tfor 'perf', because 'unsinged' should be enough for such small values.
I think a small range would be adequate - look at the number sizes and go 0-100 or 0-1000 as appropriate.
Thinking of naming, is it 'relative_throughput' ?
However, is it also going to be possible to extend this target to measure the the actual throughput? If we did that, would we use a special value to indicate it or add a new table parameter and keep the 'perf' ones as a manual adjustment factor applied on top of the calculated one?
Alasdair
Re: Re: [PATCH 3/3] dm-mpath: add service-time oriented dynamic load balancer
Hi Alasdair,
Quoted 10 lines · Alasdair G Kergon
Quoted 4 lines · Kiyoshi Ueda
However, if I limit the 'perf' value in smaller range (e.g. 0 to 100), such overflow shouldn't happen. So I should be able to use multiplication. Also, I don't need to use
size_tfor 'perf', because 'unsinged' should be enough for such small values.I think a small range would be adequate - look at the number sizes and go 0-100 or 0-1000 as appropriate.
Thinking of naming, is it '
relative_throughput' ?
Yes, 'relative_throughput' may be better naming. I'll take it.
Quoted 4 lines
However, is it also going to be possible to extend this target to measure the the actual throughput? If we did that, would we use a special value to indicate it or add a new table parameter and keep the 'perf' ones as a manual adjustment factor applied on top of the calculated one?
The older version of dm-service-time calculated the actual throughput dynamically using part_stat:
http://marc.info/?l=dm-devel&m=123321314426149&w=2
But the calculated values often had some noises and it didn't work well. (e.g. Once the throughput value of a path was calculated so small,
the path was never used, and the small throughput value was never updated, and the path was never used, and ...)
So I think doing such calculations in user-space and simplifying the kernel-code are better.
For dynamically changing path's bandwidth, user-space daemon can measure the throughput periodically and notify the dm device. I've been thinking of adding a new dm message handler to update 'relative_thoughput' in future.
What do you think?
Thanks,
Kiyoshi Ueda
Re: Re: [PATCH 3/3] dm-mpath: add service-time oriented dynamic load balancer
Hi Alasdair,
I attached 3 patches below.
- rqdm-dlb-04-service-time-dlb-maxlen-type-fix.patch:
Use 'unsigned' instead of 'unsigned int' for maxlen.
- rqdm-dlb-04-service-time-dlb-add-perf-limit.patch:
Limit the 'perf' value within the range of 0-100.
- rqdm-dlb-04-service-time-dlb-naming-change.patch:
Change the 'perf' naming to 'relative_throughput'.
Please review and apply if you have no problem.
Quoted 11 lines · Kiyoshi Ueda
Hi Alasdair,
Quoted 8 lines · Alasdair G Kergon
Quoted 4 lines · Kiyoshi Ueda
However, if I limit the 'perf' value in smaller range (e.g. 0 to 100), such overflow shouldn't happen. So I should be able to use multiplication. Also, I don't need to use
size_tfor 'perf', because 'unsinged' should be enough for such small values.I think a small range would be adequate - look at the number sizes and go 0-100 or 0-1000 as appropriate.
See rqdm-dlb-04-service-time-dlb-add-perf-limit.patch.
Quoted 3 lines
Quoted 1 line
Thinking of naming, is it '
relative_throughput' ?Yes, '
relative_throughput' may be better naming. I'll take it.
See rqdm-dlb-04-service-time-dlb-naming-change.patch. Maybe the string is too longt. If you feel so, too, 'throughput' may be another alternative?
Thanks,
Kiyoshi Ueda
Use 'unsigned' instead of 'unsigned int' for maxlen in dm-service-time.
--- drivers/md/dm-service-time.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/md/dm-service-time.c +1 -1
@@ -72,7 +72,7 @@ static void st_destroy(struct path_selec }static int st_status (struct path_selector *ps,struct dm_path *path, -status_type_t type,char *result,unsigned int maxlen) +status_type_t type,char *result,unsigned maxlen) {unsigned sz =0 ;struct path_info *pi;
o Limited the second table argument (relative throughput value) in 0-100.
As a result, no need to use 'size_t' for ->perf. Use 'unsigned'. Updated comments/documents.
o Converted the service time calculation method to multiplication from division.
--- Documentation/device-mapper/dm-service-time.txt | 1 drivers/md/dm-service-time.c | 57 +++++++++++++++--------- 2 files changed, 37 insertions(+), 21 deletions(-)
drivers/md/dm-service-time.c +36 -21
117 lines not on this page · raw message
Documentation/device-mapper/dm-service-time.txt +1 -0
@@ -19,6 +19,7 @@ Table parameters for each path: [<repeat the default value, see the activated table. <performance>: The relative throughput value of the path among all paths in the path-group. + The valid range is 0-100. 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.
Changed the name of the member 'perf' in the path_info structure to 'relative_throughput' for readability.
Also, updated the related parts of comments and documents.
--- Documentation/device-mapper/dm-service-time.txt | 43 ++++++------ drivers/md/dm-service-time.c | 84 +++++++++++++----------- 2 files changed, 69 insertions(+), 58 deletions(-)
Documentation/device-mapper/dm-service-time.txt +23 -20
78 lines not on this page · raw message
drivers/md/dm-service-time.c +46 -38
163 lines not on this page · raw message