Re: [PATCH V5 16/17] blk-throttle: add a mechanism to estimate IO latency

[Tejun Heo]

Hello,

On Thu, Dec 15, 2016 at 12:33:07PM -0800, Shaohua Li wrote:
> User configures latency target, but the latency threshold for each
> request size isn't fixed. For a SSD, the IO latency highly depends on
> request size. To calculate latency threshold, we sample some data, eg,
> average latency for request size 4k, 8k, 16k, 32k .. 1M. The latency
> threshold of each request size will be the sample latency (I'll call it
> base latency) plus latency target. For example, the base latency for
> request size 4k is 80us and user configures latency target 60us. The 4k
> latency threshold will be 80 + 60 = 140us.

Ah okay, the user configures the extra latency.  Yeah, this is way
better than treating what the user configures as the target latency
for 4k IOs.

> @@ -25,6 +25,8 @@ static int throtl_quantum = 32;
>  #define DFL_IDLE_THRESHOLD_HD (1000 * 1000) /* 1 ms */
>  #define MAX_IDLE_TIME (500L * 1000 * 1000) /* 500 ms */
>  
> +#define SKIP_TRACK (((u64)1) << BLK_STAT_RES_SHIFT)

SKIP_LATENCY?

> +static void throtl_update_latency_buckets(struct throtl_data *td)
> +{
> + struct avg_latency_bucket avg_latency[LATENCY_BUCKET_SIZE];
> + int i, cpu;
> + u64 last_latency = 0;
> + u64 latency;
> +
> + if (!blk_queue_nonrot(td->queue))
> + return;
> + if (time_before(jiffies, td->last_calculate_time + HZ))
> + return;
> + td->last_calculate_time = jiffies;
> +
> + memset(avg_latency, 0, sizeof(avg_latency));
> + for (i = 0; i < LATENCY_BUCKET_SIZE; i++) {
> + struct latency_bucket *tmp = >tmp_buckets[i];
> +
> + for_each_possible_cpu(cpu) {
> + struct latency_bucket *bucket;
> +
> + /* this isn't race free, but ok in practice */
> + bucket = per_cpu_ptr(td->latency_buckets, cpu);
> + tmp->total_latency += bucket[i].total_latency;
> + tmp->samples += bucket[i].samples;

Heh, this *can* lead to surprising results (like reading zero for a
value larger than 2^32) on 32bit machines due to split updates, and if
we're using nanosecs, those surprises have a chance, albeit low, of
happening every four secs, which is a bit unsettling.  If we have to
use nanosecs, let's please use u64_stats_sync.  If we're okay with
microsecs, ulongs should be fine.

>  void blk_throtl_bio_endio(struct bio *bio)
>  {
>   struct throtl_grp *tg;
> + u64 finish_time;
> + u64 start_time;
> + u64 lat;
>  
>   tg = bio->bi_cg_private;
>   if (!tg)
>   return;
>   bio->bi_cg_private = NULL;
>  
> - tg->last_finish_time = ktime_get_ns();
> + finish_time = ktime_get_ns();
> + tg->last_finish_time = finish_time;
> +
> + start_time = blk_stat_time(>bi_issue_stat);
> + finish_time = __blk_stat_time(finish_time);
> + if (start_time && finish_time > start_time &&
> + tg->td->track_bio_latency == 1 &&
> + !(bio->bi_issue_stat.stat & SKIP_TRACK)) {

Heh, can't we collapse some of the conditions?  e.g. flip SKIP_TRACK
to TRACK_LATENCY and set it iff the td has track_bio_latency set and
also the bio has start time set?

> @@ -2106,6 +2251,12 @@ int blk_throtl_init(struct request_queue *q)
>   td = kzalloc_node(sizeof(*td), GFP_KERNEL, q->node);
>   if (!td)
>   return -ENOMEM;
> + td->latency_buckets = __alloc_percpu(sizeof(struct latency_bucket) *
> + LATENCY_BUCKET_SIZE, __alignof__(u64));
> + if (!td->latency_buckets) {
> + kfree(td);
> + return -ENOMEM;
> + }
>  
>   INIT_WORK(>dispatch_work, blk_throtl_dispatch_work_fn);
>   throtl_service_queue_init(>service_queue);
> @@ -2119,10 +2270,13 @@ int blk_throtl_init(struct request_queue *q)
>   td->low_upgrade_time = jiffies;
>   td->low_downgrade_time = jiffies;
>  
> + td->track_bio_latency = UINT_MAX;

I don't think using 0, 1, UINT_MAX as enums is good for readability.

Thanks.

-- 
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-block" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH V5 16/17] blk-throttle: add a mechanism to estimate IO latency

[Shaohua Li]

User configures latency target, but the latency threshold for each
request size isn't fixed. For a SSD, the IO latency highly depends on
request size. To calculate latency threshold, we sample some data, eg,
average latency for request size 4k, 8k, 16k, 32k .. 1M. The latency
threshold of each request size will be the sample latency (I'll call it
base latency) plus latency target. For example, the base latency for
request size 4k is 80us and user configures latency target 60us. The 4k
latency threshold will be 80 + 60 = 140us.

To sample data, we calculate the order base 2 of rounded up IO sectors.
If the IO size is bigger than 1M, it will be accounted as 1M. Since the
calculation does round up, the base latency will be slightly smaller
than actual value. Also if there isn't any IO dispatched for a specific
IO size, we will use the base latency of smaller IO size for this IO
size.

But we shouldn't sample data at any time. The base latency is supposed
to be latency where disk isn't congested, because we use latency
threshold to schedule IOs between cgroups. If disk is congested, the
latency is higher, using it for scheduling is meaningless. Hence we only
do the sampling when block throttling is in the LOW limit, with
assumption disk isn't congested in such state. If the assumption isn't
true, eg, low limit is too high, calculated latency threshold will be
higher.

Hard disk is completely different. Latency depends on spindle seek
instead of request size. Currently this feature is SSD only, we probably
can use a fixed threshold like 4ms for hard disk though.

Signed-off-by: Shaohua Li 
---
 block/blk-stat.c  |   4 ++
 block/blk-throttle.c  | 159 +-
 block/blk.h   |   2 +
 include/linux/blk_types.h |   9 +--
 4 files changed, 168 insertions(+), 6 deletions(-)

diff --git a/block/blk-stat.c b/block/blk-stat.c
index 0469855..15c1621 100644
--- a/block/blk-stat.c
+++ b/block/blk-stat.c
@@ -7,6 +7,7 @@
 #include 
 
 #include "blk-stat.h"
+#include "blk.h"
 #include "blk-mq.h"
 
 static void blk_stat_flush_batch(struct blk_rq_stat *stat)
@@ -204,6 +205,9 @@ void blk_stat_add(struct blk_rq_stat *stat, struct request 
*rq)
__blk_stat_init(stat, now);
 
value = now - blk_stat_time(>issue_stat);
+
+   blk_throtl_stat_add(rq, value);
+
if (value > stat->max)
stat->max = value;
if (value < stat->min)
diff --git a/block/blk-throttle.c b/block/blk-throttle.c
index 3431b1d..1dc707a 100644
--- a/block/blk-throttle.c
+++ b/block/blk-throttle.c
@@ -25,6 +25,8 @@ static int throtl_quantum = 32;
 #define DFL_IDLE_THRESHOLD_HD (1000 * 1000) /* 1 ms */
 #define MAX_IDLE_TIME (500L * 1000 * 1000) /* 500 ms */
 
+#define SKIP_TRACK (((u64)1) << BLK_STAT_RES_SHIFT)
+
 static struct blkcg_policy blkcg_policy_throtl;
 
 /* A workqueue to queue throttle related work */
@@ -162,6 +164,19 @@ struct throtl_grp {
u64 idle_ttime_threshold;
 };
 
+/* We measure latency for request size from <= 4k to >= 1M */
+#define LATENCY_BUCKET_SIZE 9
+
+struct latency_bucket {
+   u64 total_latency;
+   int samples;
+};
+
+struct avg_latency_bucket {
+   u64 latency;
+   bool valid;
+};
+
 struct throtl_data
 {
/* service tree for active throtl groups */
@@ -185,6 +200,13 @@ struct throtl_data
unsigned long low_downgrade_time;
 
unsigned int scale;
+
+   struct latency_bucket tmp_buckets[LATENCY_BUCKET_SIZE];
+   struct avg_latency_bucket avg_buckets[LATENCY_BUCKET_SIZE];
+   struct latency_bucket __percpu *latency_buckets;
+   unsigned long last_calculate_time;
+
+   unsigned int track_bio_latency;
 };
 
 static void throtl_pending_timer_fn(unsigned long arg);
@@ -293,6 +315,13 @@ static unsigned int tg_iops_limit(struct throtl_grp *tg, 
int rw)
return ret;
 }
 
+static int request_bucket_index(sector_t sectors)
+{
+   int order = order_base_2(sectors);
+
+   return clamp_t(int, order - 3, 0, LATENCY_BUCKET_SIZE - 1);
+}
+
 /**
  * throtl_log - log debug message via blktrace
  * @sq: the service_queue being reported
@@ -1896,12 +1925,74 @@ static void blk_throtl_update_ttime(struct throtl_grp 
*tg)
tg->checked_last_finish_time = last_finish_time;
 }
 
+static void throtl_update_latency_buckets(struct throtl_data *td)
+{
+   struct avg_latency_bucket avg_latency[LATENCY_BUCKET_SIZE];
+   int i, cpu;
+   u64 last_latency = 0;
+   u64 latency;
+
+   if (!blk_queue_nonrot(td->queue))
+   return;
+   if (time_before(jiffies, td->last_calculate_time + HZ))
+   return;
+   td->last_calculate_time = jiffies;
+
+   memset(avg_latency, 0, sizeof(avg_latency));
+   for (i = 0; i < LATENCY_BUCKET_SIZE; i++) {
+   struct latency_bucket *tmp = >tmp_buckets[i];
+
+   for_each_possible_cpu(cpu) {
+   struct latency_bucket *bucket;
+
+