Skip to contentSkip to conversation

Historical Service Time Path Selector

PATCH Superseded Gabriel Krisman Bertazi 3 participants 9 messages Apr 28, 2020 – May 1, 2020

Subsystems (2)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v2 cover Historical Service Time Path Selector

Hi Mike,

Please find an updated version of HST integrating the change you requested to also support BIO based multipath. I hope you don't mind me folding the function you implemented into patch 2. If you prefer, I can integrate a patch you provide into the series.

One interesting data point is that the selection performance on BIO-based is worse when compared to request-based. I tested a bit and I believe the reason is that the paths are more sticky because the bucket is too large, and it takes longer for HST to detect differences. By changing the bucket_size indirectly through the bucket_shift, the bio-based multipath performance improved, but I'm not sure this is a knob we want to expose to users. For now, please consider the patches below, for review.

By the way, the exercise to support bio-based mpath uncovered the mpath initialization bug that I fixed in the previous patch I sent today, so it was worth it.

Gabriel Krisman Bertazi (2):
md: multipath: Encapsulate parameters passed to selectors
md: multipath: Pass io_start_time to the path selector

Khazhismel Kumykov (1):
md: Add Historical Service Time Path Selector

 drivers/md/Kconfig                      |  11 +
 drivers/md/Makefile                     |   1 +
 drivers/md/dm-historical-service-time.c | 561 ++++++++++++++++++++++++
 drivers/md/dm-mpath.c                   |  30 +-
 drivers/md/dm-path-selector.h           |   9 +-
 drivers/md/dm-queue-length.c            |   4 +-
 drivers/md/dm-service-time.c            |   8 +-
 drivers/md/dm.c                         |  10 +
 include/linux/device-mapper.h           |   2 +
 9 files changed, 623 insertions(+), 13 deletions(-)
 create mode 100644 drivers/md/dm-historical-service-time.c
Signature · 1 line
2.26.2
#1 lore raw

PATCH v2 1/3 md: multipath: Encapsulate parameters passed to selectors

Different selector will use different parameters, which means .io_start and .io_end will get their signatures modified to include more and more parameters. This encapsulates the data in a structure so we can simplify the interface for future users. For now it only passes nr_bytes, but HST will require start_time already.

---
 drivers/md/dm-mpath.c         | 25 ++++++++++++++++++++-----
 drivers/md/dm-path-selector.h |  8 ++++++--
 drivers/md/dm-queue-length.c  |  4 ++--
 drivers/md/dm-service-time.c  |  8 ++++----
 4 files changed, 32 insertions(+), 13 deletions(-)
drivers/md/dm-mpath.c +20 -5
index f5e7f8e88767..1ef4fc2e745b 100644
@@ -500,6 +500,9 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	struct dm_mpath_io *mpio = get_mpio(map_context);
 	struct request_queue *q;
 	struct request *clone;
+	struct path_selector_io_data io_data = {
+		.nr_bytes = nr_bytes,
+	};
 
 	/* Do we need to select a new pgpath? */
 	pgpath = READ_ONCE(m->current_pgpath);
@@ -549,7 +552,7 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      nr_bytes);
+					      &io_data);
 	return DM_MAPIO_REMAPPED;
 }
 
@@ -563,11 +566,14 @@ static void multipath_release_clone(struct request *clone,
 		 */
 		struct dm_mpath_io *mpio = get_mpio(map_context);
 		struct pgpath *pgpath = mpio->pgpath;
+		struct path_selector_io_data ps_io_data = {
+			.nr_bytes = mpio->nr_bytes,
+		};
 
 		if (pgpath && pgpath->pg->ps.type->end_io)
 			pgpath->pg->ps.type->end_io(&pgpath->pg->ps,
 						    &pgpath->path,
-						    mpio->nr_bytes);
+						    &ps_io_data);
 	}
 
 	blk_put_request(clone);
@@ -617,6 +623,9 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 			       struct dm_mpath_io *mpio)
 {
 	struct pgpath *pgpath = __map_bio(m, bio);
+	struct path_selector_io_data io_data = {
+		.nr_bytes = mpio->nr_bytes,
+	};
 
 	if (IS_ERR(pgpath))
 		return DM_MAPIO_SUBMITTED;
@@ -637,7 +646,7 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      mpio->nr_bytes);
+					      &io_data);
 	return DM_MAPIO_REMAPPED;
 }
 
@@ -1618,9 +1627,12 @@ static int multipath_end_io(struct dm_target *ti, struct request *clone,
 
 	if (pgpath) {
 		struct path_selector *ps = &pgpath->pg->ps;
+		struct path_selector_io_data io_data = {
+			.nr_bytes = mpio->nr_bytes
+		};
 
 		if (ps->type->end_io)
-			ps->type->end_io(ps, &pgpath->path, mpio->nr_bytes);
+			ps->type->end_io(ps, &pgpath->path, &io_data);
 	}
 
 	return r;
@@ -1662,9 +1674,12 @@ static int multipath_end_io_bio(struct dm_target *ti, struct bio *clone,
 done:
 	if (pgpath) {
 		struct path_selector *ps = &pgpath->pg->ps;
+		struct path_selector_io_data io_data = {
+			.nr_bytes = mpio->nr_bytes
+		};
 
 		if (ps->type->end_io)
-			ps->type->end_io(ps, &pgpath->path, mpio->nr_bytes);
+			ps->type->end_io(ps, &pgpath->path, &io_data);
 	}
 
 	return r;
drivers/md/dm-path-selector.h +6 -2
index b6eb5365b1a4..fb582a943234 100644
@@ -26,6 +26,10 @@ struct path_selector {
 	void *context;
 };
 
+struct path_selector_io_data {
+	size_t nr_bytes;
+};
+
 /* Information about a path selector type */
 struct path_selector_type {
 	char *name;
@@ -72,9 +76,9 @@ struct path_selector_type {
 		       status_type_t type, char *result, unsigned int maxlen);
 
 	int (*start_io) (struct path_selector *ps, struct dm_path *path,
-			 size_t nr_bytes);
+			 const struct path_selector_io_data *io_data);
 	int (*end_io) (struct path_selector *ps, struct dm_path *path,
-		       size_t nr_bytes);
+		       const struct path_selector_io_data *io_data);
 };
 
 /* Register a path selector */
drivers/md/dm-queue-length.c +2 -2
index 969c4f1a3633..eeaa038a1dbb 100644
@@ -217,7 +217,7 @@ static struct dm_path *ql_select_path(struct path_selector *ps, size_t nr_bytes)
 }
 
 static int ql_start_io(struct path_selector *ps, struct dm_path *path,
-		       size_t nr_bytes)
+		       const struct path_selector_io_data *io_data)
 {
 	struct path_info *pi = path->pscontext;
 
@@ -227,7 +227,7 @@ static int ql_start_io(struct path_selector *ps, struct dm_path *path,
 }
 
 static int ql_end_io(struct path_selector *ps, struct dm_path *path,
-		     size_t nr_bytes)
+		     const struct path_selector_io_data *io_data)
 {
 	struct path_info *pi = path->pscontext;
 
drivers/md/dm-service-time.c +4 -4
index f006a9005593..d751f26b61af 100644
@@ -299,21 +299,21 @@ static struct dm_path *st_select_path(struct path_selector *ps, size_t nr_bytes)
 }
 
 static int st_start_io(struct path_selector *ps, struct dm_path *path,
-		       size_t nr_bytes)
+		       const struct path_selector_io_data *io_data)
 {
 	struct path_info *pi = path->pscontext;
 
-	atomic_add(nr_bytes, &pi->in_flight_size);
+	atomic_add(io_data->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)
+		     const struct path_selector_io_data *io_data)
 {
 	struct path_info *pi = path->pscontext;
 
-	atomic_sub(nr_bytes, &pi->in_flight_size);
+	atomic_sub(io_data->nr_bytes, &pi->in_flight_size);
 
 	return 0;
 }
Signature · 1 line
2.26.2
#2 lore raw

Re: [PATCH v2 1/3] md: multipath: Encapsulate parameters passed to selectors

Quoted 8 lines · Gabriel Krisman Bertazi

Different selector will use different parameters, which means .io_start and .io_end will get their signatures modified to include more and more parameters. This encapsulates the data in a structure so we can simplify the interface for future users. For now it only passes nr_bytes, but HST will require start_time already.

I really don't see HST's need for start_time_ns in the path selector's end_io hook as a solid justification for this encapsulation.

Especially in that the parameters needed for ps's start_io and end_io really aren't symmetric. Imposing that they are just causes needless code (an example of that is in patch 2/3).

So please drop this encapsulation.

Thanks,
Mike

#3 lore raw

PATCH v2 2/3 md: multipath: Pass io_start_time to the path selector

In reply to Gabriel Krisman Bertazi

HST need to know the IO start time in order to predict path performance. For request-based multipath use the block layer io_start_time, while for BIO use the dm_io start_time.

The dm_start_time_ns_from_clone function was suggested and implemented by Mike Snitzer <[email protected]>.

Cc Mike Snitzer <[email protected]>
Cc Khazhismel Kumykov <[email protected]>
---
 drivers/md/dm-mpath.c         | 25 +++++++++++++++----------
 drivers/md/dm-path-selector.h |  1 +
 drivers/md/dm.c               | 10 ++++++++++
 include/linux/device-mapper.h |  2 ++
 4 files changed, 28 insertions(+), 10 deletions(-)
drivers/md/dm-mpath.c +15 -10
index 1ef4fc2e745b..7af3249948be 100644
@@ -500,8 +500,9 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	struct dm_mpath_io *mpio = get_mpio(map_context);
 	struct request_queue *q;
 	struct request *clone;
-	struct path_selector_io_data io_data = {
+	struct path_selector_io_data ps_io_data = {
 		.nr_bytes = nr_bytes,
+		.io_start_time = rq->io_start_time_ns
 	};
 
 	/* Do we need to select a new pgpath? */
@@ -552,7 +553,7 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      &io_data);
+					      &ps_io_data);
 	return DM_MAPIO_REMAPPED;
 }
 
@@ -568,6 +569,7 @@ static void multipath_release_clone(struct request *clone,
 		struct pgpath *pgpath = mpio->pgpath;
 		struct path_selector_io_data ps_io_data = {
 			.nr_bytes = mpio->nr_bytes,
+			.io_start_time = clone->io_start_time_ns,
 		};
 
 		if (pgpath && pgpath->pg->ps.type->end_io)
@@ -623,8 +625,9 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 			       struct dm_mpath_io *mpio)
 {
 	struct pgpath *pgpath = __map_bio(m, bio);
-	struct path_selector_io_data io_data = {
+	struct path_selector_io_data ps_io_data = {
 		.nr_bytes = mpio->nr_bytes,
+		.io_start_time = dm_start_time_ns_from_clone(bio)
 	};
 
 	if (IS_ERR(pgpath))
@@ -646,7 +649,7 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      &io_data);
+					      &ps_io_data);
 	return DM_MAPIO_REMAPPED;
 }
 
@@ -1627,12 +1630,13 @@ static int multipath_end_io(struct dm_target *ti, struct request *clone,
 
 	if (pgpath) {
 		struct path_selector *ps = &pgpath->pg->ps;
-		struct path_selector_io_data io_data = {
-			.nr_bytes = mpio->nr_bytes
+		struct path_selector_io_data ps_io_data = {
+			.nr_bytes = mpio->nr_bytes,
+			.io_start_time = clone->io_start_time_ns
 		};
 
 		if (ps->type->end_io)
-			ps->type->end_io(ps, &pgpath->path, &io_data);
+			ps->type->end_io(ps, &pgpath->path, &ps_io_data);
 	}
 
 	return r;
@@ -1674,12 +1678,13 @@ static int multipath_end_io_bio(struct dm_target *ti, struct bio *clone,
 done:
 	if (pgpath) {
 		struct path_selector *ps = &pgpath->pg->ps;
-		struct path_selector_io_data io_data = {
-			.nr_bytes = mpio->nr_bytes
+		struct path_selector_io_data ps_io_data = {
+			.nr_bytes = mpio->nr_bytes,
+			.io_start_time = dm_start_time_ns_from_clone(clone)
 		};
 
 		if (ps->type->end_io)
-			ps->type->end_io(ps, &pgpath->path, &io_data);
+			ps->type->end_io(ps, &pgpath->path, &ps_io_data);
 	}
 
 	return r;
drivers/md/dm-path-selector.h +1 -0
index fb582a943234..4c5fa6a2efe3 100644
@@ -28,6 +28,7 @@ struct path_selector {
 
 struct path_selector_io_data {
 	size_t nr_bytes;
+	u64 io_start_time;
 };
 
 /* Information about a path selector type */
drivers/md/dm.c +10 -0
index df13fdebe21f..2e0637a6de9d 100644
@@ -674,6 +674,16 @@ static bool md_in_flight(struct mapped_device *md)
 		return md_in_flight_bios(md);
 }
 
+u64 dm_start_time_ns_from_clone(struct bio *bio)
+{
+	struct dm_target_io *tio = container_of(bio, struct dm_target_io, clone);
+	struct dm_io *io = tio->io;
+
+	/* FIXME: convert io->start_time from jiffies to nanoseconds */
+	return (u64)jiffies_to_msecs(io->start_time) * NSEC_PER_MSEC;
+}
+EXPORT_SYMBOL_GPL(dm_start_time_ns_from_clone);
+
 static void start_io_acct(struct dm_io *io)
 {
 	struct mapped_device *md = io->md;
include/linux/device-mapper.h +2 -0
index 475668c69dbc..e2d506dd805e 100644
@@ -329,6 +329,8 @@ void *dm_per_bio_data(struct bio *bio, size_t data_size);
 struct bio *dm_bio_from_per_bio_data(void *data, size_t data_size);
 unsigned dm_bio_get_target_bio_nr(const struct bio *bio);
 
+u64 dm_start_time_ns_from_clone(struct bio *bio);
+
 int dm_register_target(struct target_type *t);
 void dm_unregister_target(struct target_type *t);
 
Signature · 1 line
2.26.2
#4 lore raw

Re: [PATCH v2 2/3] md: multipath: Pass io_start_time to the path selector

Quoted 61 lines · Gabriel Krisman Bertazi

HST need to know the IO start time in order to predict path performance. For request-based multipath use the block layer io_start_time, while for BIO use the dm_io start_time.

The dm_start_time_ns_from_clone function was suggested and implemented by Mike Snitzer <[email protected]>.

Cc Mike Snitzer <[email protected]>
Cc Khazhismel Kumykov <[email protected]>
---
 drivers/md/dm-mpath.c         | 25 +++++++++++++++----------
 drivers/md/dm-path-selector.h |  1 +
 drivers/md/dm.c               | 10 ++++++++++
 include/linux/device-mapper.h |  2 ++
 4 files changed, 28 insertions(+), 10 deletions(-)
drivers/md/dm-mpath.c +6 -3
index 1ef4fc2e745b..7af3249948be 100644
@@ -500,8 +500,9 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	struct dm_mpath_io *mpio = get_mpio(map_context);
 	struct request_queue *q;
 	struct request *clone;
-	struct path_selector_io_data io_data = {
+	struct path_selector_io_data ps_io_data = {
 		.nr_bytes = nr_bytes,
+		.io_start_time = rq->io_start_time_ns
 	};
 
 	/* Do we need to select a new pgpath? */
@@ -552,7 +553,7 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      &io_data);
+					      &ps_io_data);
 	return DM_MAPIO_REMAPPED;
 }
 
@@ -568,6 +569,7 @@ static void multipath_release_clone(struct request *clone,
 		struct pgpath *pgpath = mpio->pgpath;
 		struct path_selector_io_data ps_io_data = {
 			.nr_bytes = mpio->nr_bytes,
+			.io_start_time = clone->io_start_time_ns,
 		};
 
 		if (pgpath && pgpath->pg->ps.type->end_io)
@@ -623,8 +625,9 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 			       struct dm_mpath_io *mpio)
 {
 	struct pgpath *pgpath = __map_bio(m, bio);
-	struct path_selector_io_data io_data = {
+	struct path_selector_io_data ps_io_data = {
 		.nr_bytes = mpio->nr_bytes,
+		.io_start_time = dm_start_time_ns_from_clone(bio)
 	};
 
 	if (IS_ERR(pgpath))

drivers/md/dm-mpath.c static int __multipath_map_bio(struct multipath *m, struct bio *bio, · line 655

Quoted 8 lines
drivers/md/dm-mpath.c +1 -1
@@ -646,7 +649,7 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio,
 	if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
-					      &io_data);
+					      &ps_io_data);
 	return DM_MAPIO_REMAPPED;
 }
 

io_start_time_ns isn't needed by any path selector's start_io method. Please drop that from start_io and only pass it to the end_io hook.

(the need for dm_start_time_ns_from_clone() to access the more nested nature of a bio clone's start_time showcases why we should avoid needless collection of parameters that aren't required).

Thanks,
Mike

#5 lore raw

PATCH v2 3/3 md: Add Historical Service Time Path Selector

In reply to Gabriel Krisman Bertazi

From: Khazhismel Kumykov <[email protected]>

This new selector keeps an exponential moving average of the service time for each path (losely defined as delta between start_io and end_io), and uses this along with the number of inflight requests to estimate future service time for a path. Since we don't have a prober to account for temporally slow paths, re-try "slow" paths every once in a while (num_paths * historical_service_time). To account for fast paths transitioning to slow, if a path has not completed any request within (num_paths * historical_service_time), limit the number of outstanding requests. To account for low volume situations where number of inflights would be zero, the last finish time of each path is factored in.

---
 drivers/md/Kconfig                      |  11 +
 drivers/md/Makefile                     |   1 +
 drivers/md/dm-historical-service-time.c | 561 ++++++++++++++++++++++++
 3 files changed, 573 insertions(+)
 create mode 100644 drivers/md/dm-historical-service-time.c
drivers/md/Kconfig +11 -0
index 37f05707c59d..5669eeb5cf6f 100644
@@ -452,6 +452,17 @@ config DM_MULTIPATH_ST
 
 	  If unsure, say N.
 
+config DM_MULTIPATH_HST
+	tristate "I/O Path Selector based on historical service time"
+	depends on DM_MULTIPATH
+	help
+	  This path selector is a dynamic load balancer which selects
+	  the path expected to complete the incoming I/O in the shortest
+	  time by comparing estimated service time (based on historical
+	  service time).
+
+	  If unsure, say N.
+
 config DM_DELAY
 	tristate "I/O delaying target"
 	depends on BLK_DEV_DM
drivers/md/Makefile +1 -0
index 9a2d673f94bc..31840f95cd40 100644
@@ -55,6 +55,7 @@ obj-$(CONFIG_DM_FLAKEY)		+= dm-flakey.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_MULTIPATH_HST)	+= dm-historical-service-time.o
 obj-$(CONFIG_DM_SWITCH)		+= dm-switch.o
 obj-$(CONFIG_DM_SNAPSHOT)	+= dm-snapshot.o
 obj-$(CONFIG_DM_PERSISTENT_DATA)	+= persistent-data/
drivers/md/dm-historical-service-time.c new file +561 -0

561 lines not on this page · raw message

Signature · 1 line
2.26.2
#6 lore raw
In reply to Gabriel Krisman Bertazi
Quoted 6 lines · Gabriel Krisman Bertazi

Hi Mike,

Please find an updated version of HST integrating the change you requested to also support BIO based multipath. I hope you don't mind me folding the function you implemented into patch 2. If you prefer, I can integrate a patch you provide into the series.

Hi Mike,

Sorry for the encapsulation patches, I'll pass the parameter directly on v3.

Quoted 9 lines

One interesting data point is that the selection performance on BIO-based is worse when compared to request-based. I tested a bit and I believe the reason is that the paths are more sticky because the bucket is too large, and it takes longer for HST to detect differences. By changing the bucket_size indirectly through the bucket_shift, the bio-based multipath performance improved, but I'm not sure this is a knob we want to expose to users. For now, please consider the patches below, for review.

The reason for the BIO-based being worse than request-based was that we are comparing the jiffies_to_nsecs(jiffies) with ktime_get_ns(), which is not accurate, given the different precision of the clocks. Problem is, request-based mpath uses ktime_get_ns in the block layer, while dm_io->start_time uses jiffies, and inside the path selector, we don't have a way to distinguish those paths. I see a few ways forward, but in the best interest of getting it right early, I'd like to hear what you think it is best:

1) My best suggestion would be converting dm_io->start_time to use ktime_get_ns. This has the advantage of simplifying dm_stats_account_io and wouldn't affect the ABI of the accounting histogram. The only downside, from what I can see is that ktime_get is slightly more expensive than reading jiffies, which might be a problem according to Documentation/admin-guide/device-mapper/statistics.rst. Is that really a problem? I see your FIXME note on the function you implemented, but are you suggesting exactly this or simply storing jiffies_to_nsecs(jiffies) in dm_io->start_time?

2) Alternatively, pass end_io_time to the path selector as well, and do the time collection outside the path selector. This makes the interface look ugly, adds the cost anyway of doing ktime operations.

3) Alternatively, collect ktime start/end costs inside HST. This means we need to match the IO on start_io and end_io from inside HST, which doesn't seem like a good design either.

4) ?

As you can see, I'm leaning towards option 1. Would you be open to a patch like the following? Completely untested, still need some work, just to show the idea.

Khazhy, any thoughts?

drivers/md/dm-rq.c +4 -4
index 3f8577e2c13b..eb7c7fae4bc6 100644
@@ -23,7 +23,7 @@ struct dm_rq_target_io {
 	blk_status_t error;
 	union map_info info;
 	struct dm_stats_aux stats_aux;
-	unsigned long duration_jiffies;
+	u64 duration_ns;
 	unsigned n_sectors;
 	unsigned completed;
 };
@@ -132,10 +132,10 @@ static void rq_end_stats(struct mapped_device *md, struct request *orig)
 {
 	if (unlikely(dm_stats_used(&md->stats))) {
 		struct dm_rq_target_io *tio = tio_from_request(orig);
-		tio->duration_jiffies = jiffies - tio->duration_jiffies;
+		tio->duration_ns = ktime_get_ns() - tio->duration_ns;
 		dm_stats_account_io(&md->stats, rq_data_dir(orig),
 				    blk_rq_pos(orig), tio->n_sectors, true,
-				    tio->duration_jiffies, &tio->stats_aux);
+				    tio->duration_ns, &tio->stats_aux);
 	}
 }
 
@@ -451,7 +451,7 @@ static void dm_start_request(struct mapped_device *md, struct request *orig)
 
 	if (unlikely(dm_stats_used(&md->stats))) {
 		struct dm_rq_target_io *tio = tio_from_request(orig);
-		tio->duration_jiffies = jiffies;
+		tio->duration_ns = ktime_get_ns();
 		tio->n_sectors = blk_rq_sectors(orig);
 		dm_stats_account_io(&md->stats, rq_data_dir(orig),
 				    blk_rq_pos(orig), tio->n_sectors, false, 0,
drivers/md/dm-stats.c +11 -21
index 71417048256a..4353dd04ec42 100644
@@ -514,7 +514,7 @@ static void dm_stat_round(struct dm_stat *s, struct dm_stat_shared *shared,
 static void dm_stat_for_entry(struct dm_stat *s, size_t entry,
 			      int idx, sector_t len,
 			      struct dm_stats_aux *stats_aux, bool end,
-			      unsigned long duration_jiffies)
+			      u64 duration_ns)
 {
 	struct dm_stat_shared *shared = &s->stat_shared[entry];
 	struct dm_stat_percpu *p;
@@ -553,11 +553,11 @@ static void dm_stat_for_entry(struct dm_stat *s, size_t entry,
 		p->ios[idx] += 1;
 		p->merges[idx] += stats_aux->merged;
 		if (!(s->stat_flags & STAT_PRECISE_TIMESTAMPS)) {
-			p->ticks[idx] += duration_jiffies;
-			duration = jiffies_to_msecs(duration_jiffies);
+			p->ticks[idx] += nsecs_to_jiffies(duration_ns);
+			duration = div64_u64(duration_ns, 1000000);
 		} else {
-			p->ticks[idx] += stats_aux->duration_ns;
-			duration = stats_aux->duration_ns;
+			p->ticks[idx] += duration_ns;
+			duration = duration_ns;
 		}
 		if (s->n_histogram_entries) {
 			unsigned lo = 0, hi = s->n_histogram_entries + 1;
@@ -583,7 +583,7 @@ static void dm_stat_for_entry(struct dm_stat *s, size_t entry,
 
 static void __dm_stat_bio(struct dm_stat *s, int bi_rw,
 			  sector_t bi_sector, sector_t end_sector,
-			  bool end, unsigned long duration_jiffies,
+			  bool end, u64 duration_ns,
 			  struct dm_stats_aux *stats_aux)
 {
 	sector_t rel_sector, offset, todo, fragment_len;
@@ -612,7 +612,7 @@ static void __dm_stat_bio(struct dm_stat *s, int bi_rw,
 		if (fragment_len > s->step - offset)
 			fragment_len = s->step - offset;
 		dm_stat_for_entry(s, entry, bi_rw, fragment_len,
-				  stats_aux, end, duration_jiffies);
+				  stats_aux, end, duration_ns);
 		todo -= fragment_len;
 		entry++;
 		offset = 0;
@@ -621,13 +621,11 @@ static void __dm_stat_bio(struct dm_stat *s, int bi_rw,
 
 void dm_stats_account_io(struct dm_stats *stats, unsigned long bi_rw,
 			 sector_t bi_sector, unsigned bi_sectors, bool end,
-			 unsigned long duration_jiffies,
-			 struct dm_stats_aux *stats_aux)
+			 u64 duration_ns, struct dm_stats_aux *stats_aux)
 {
 	struct dm_stat *s;
 	sector_t end_sector;
 	struct dm_stats_last_position *last;
-	bool got_precise_time;
 
 	if (unlikely(!bi_sectors))
 		return;
@@ -651,17 +649,9 @@ void dm_stats_account_io(struct dm_stats *stats, unsigned long bi_rw,
 
 	rcu_read_lock();
 
-	got_precise_time = false;
-	list_for_each_entry_rcu(s, &stats->list, list_entry) {
-		if (s->stat_flags & STAT_PRECISE_TIMESTAMPS && !got_precise_time) {
-			if (!end)
-				stats_aux->duration_ns = ktime_to_ns(ktime_get());
-			else
-				stats_aux->duration_ns = ktime_to_ns(ktime_get()) - stats_aux->duration_ns;
-			got_precise_time = true;
-		}
-		__dm_stat_bio(s, bi_rw, bi_sector, end_sector, end, duration_jiffies, stats_aux);
-	}
+	list_for_each_entry_rcu(s, &stats->list, list_entry)
+		__dm_stat_bio(s, bi_rw, bi_sector, end_sector, end,
+			      duration_ns, stats_aux);
 
 	rcu_read_unlock();
 }
drivers/md/dm-stats.h +1 -3
index 2ddfae678f32..e9755f14ce68 100644
@@ -19,7 +19,6 @@ struct dm_stats {
 
 struct dm_stats_aux {
 	bool merged;
-	unsigned long long duration_ns;
 };
 
 void dm_stats_init(struct dm_stats *st);
@@ -32,8 +31,7 @@ int dm_stats_message(struct mapped_device *md, unsigned argc, char **argv,
 
 void dm_stats_account_io(struct dm_stats *stats, unsigned long bi_rw,
 			 sector_t bi_sector, unsigned bi_sectors, bool end,
-			 unsigned long duration_jiffies,
-			 struct dm_stats_aux *aux);
+			 u64 duration_ns, struct dm_stats_aux *aux);
 
 static inline bool dm_stats_used(struct dm_stats *st)
 {
drivers/md/dm.c +3 -3
index c5deee1bea67..10ca0d0c3c46 100644
@@ -689,7 +689,7 @@ static void start_io_acct(struct dm_io *io)
 	struct mapped_device *md = io->md;
 	struct bio *bio = io->orig_bio;
 
-	io->start_time = jiffies;
+	io->start_time = ktime_get_ns();
 
 	generic_start_io_acct(md->queue, bio_op(bio), bio_sectors(bio),
 			      &dm_disk(md)->part0);
@@ -704,10 +704,10 @@ static void end_io_acct(struct dm_io *io)
 {
 	struct mapped_device *md = io->md;
 	struct bio *bio = io->orig_bio;
-	unsigned long duration = jiffies - io->start_time;
+	u64 duration = ktime_get_ns() - io->start_time;
 
 	generic_end_io_acct(md->queue, bio_op(bio), &dm_disk(md)->part0,
-			    io->start_time);
+			    nsecs_to_jiffies(io->start_time));
 
 	if (unlikely(dm_stats_used(&md->stats)))
 		dm_stats_account_io(&md->stats, bio_data_dir(bio),
Signature · 1 line
Gabriel Krisman Bertazi
#7 lore raw
Quoted 9 lines · Gabriel Krisman Bertazi
Quoted 6 lines · Gabriel Krisman Bertazi

Hi Mike,

Please find an updated version of HST integrating the change you requested to also support BIO based multipath. I hope you don't mind me folding the function you implemented into patch 2. If you prefer, I can integrate a patch you provide into the series.

Quoted 4 lines

Hi Mike,

Sorry for the encapsulation patches, I'll pass the parameter directly on v3.

Great, thanks.

Quoted 19 lines
Quoted 9 lines

One interesting data point is that the selection performance on BIO-based is worse when compared to request-based. I tested a bit and I believe the reason is that the paths are more sticky because the bucket is too large, and it takes longer for HST to detect differences. By changing the bucket_size indirectly through the bucket_shift, the bio-based multipath performance improved, but I'm not sure this is a knob we want to expose to users. For now, please consider the patches below, for review.

The reason for the BIO-based being worse than request-based was that we are comparing the jiffies_to_nsecs(jiffies) with ktime_get_ns(), which is not accurate, given the different precision of the clocks. Problem is, request-based mpath uses ktime_get_ns in the block layer, while dm_io->start_time uses jiffies, and inside the path selector, we don't have a way to distinguish those paths. I see a few ways forward, but in the best interest of getting it right early, I'd like to hear what you think it is best:

Quoted 7 lines

1) My best suggestion would be converting dm_io->start_time to use ktime_get_ns. This has the advantage of simplifying dm_stats_account_io and wouldn't affect the ABI of the accounting histogram. The only downside, from what I can see is that ktime_get is slightly more expensive than reading jiffies, which might be a problem according to Documentation/admin-guide/device-mapper/statistics.rst. Is that really a problem?

We should check with Mikulas (now cc'd) but given the speed improvements of storage we'll likely need to use "precise_timestamps" going forward anyway.

So I'm inclined to just take the hit of ktime_get_ns(). Mikulas would you be OK with this?

Quoted 3 lines

I see your FIXME note on the function you implemented, but are you suggesting exactly this or simply storing jiffies_to_nsecs(jiffies) in dm_io->start_time?

Yes, I am suggesting exactly this (1) in that FIXME.

Quoted 3 lines

As you can see, I'm leaning towards option 1. Would you be open to a patch like the following? Completely untested, still need some work, just to show the idea.

Yes, follow-on work would be something like the patch you provided. Only nit I see is we should rename io->start_time to io->start_time_ns

But please keep this patch (that does the work to address the "FIXME" I added) separate from your HST patchset. The need to improve bio-based HST is a secondary concern given bio-based multipath isn't widely deployed AFAICT. So we can address the conversion to nanoseconds with later followon work that builds on your initial HST patchset.

Thanks,
Mike

maintainer
#8 lore raw
Quoted 46 lines · Mike Snitzer
Quoted 9 lines · Gabriel Krisman Bertazi
Quoted 6 lines · Gabriel Krisman Bertazi

Hi Mike,

Please find an updated version of HST integrating the change you requested to also support BIO based multipath. I hope you don't mind me folding the function you implemented into patch 2. If you prefer, I can integrate a patch you provide into the series.

Quoted 4 lines

Hi Mike,

Sorry for the encapsulation patches, I'll pass the parameter directly on v3.

Great, thanks.

Quoted 19 lines
Quoted 9 lines

One interesting data point is that the selection performance on BIO-based is worse when compared to request-based. I tested a bit and I believe the reason is that the paths are more sticky because the bucket is too large, and it takes longer for HST to detect differences. By changing the bucket_size indirectly through the bucket_shift, the bio-based multipath performance improved, but I'm not sure this is a knob we want to expose to users. For now, please consider the patches below, for review.

The reason for the BIO-based being worse than request-based was that we are comparing the jiffies_to_nsecs(jiffies) with ktime_get_ns(), which is not accurate, given the different precision of the clocks. Problem is, request-based mpath uses ktime_get_ns in the block layer, while dm_io->start_time uses jiffies, and inside the path selector, we don't have a way to distinguish those paths. I see a few ways forward, but in the best interest of getting it right early, I'd like to hear what you think it is best:

Quoted 7 lines

1) My best suggestion would be converting dm_io->start_time to use ktime_get_ns. This has the advantage of simplifying dm_stats_account_io and wouldn't affect the ABI of the accounting histogram. The only downside, from what I can see is that ktime_get is slightly more expensive than reading jiffies, which might be a problem according to Documentation/admin-guide/device-mapper/statistics.rst. Is that really a problem?

Quoted 6 lines

We should check with Mikulas (now cc'd) but given the speed improvements of storage we'll likely need to use "precise_timestamps" going forward anyway.

So I'm inclined to just take the hit of ktime_get_ns(). Mikulas would you be OK with this?

You can use ktime_get_ns() inside the multipath target. But I wouldn't use it in the general device mapper code because it would slow down everything.

I suggest to use ktime_get_ns() in the multipath map routine and in the the end_io routine and subract these two values to get precise time. I think that we don't need to hack generic dm code with that.

Mikulas