block/kyber-iosched.c

   1 /*
   2  * The Kyber I/O scheduler. Controls latency by throttling queue depths using
   3  * scalable techniques.
   4  *
   5  * Copyright (C) 2017 Facebook
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public
   9  * License v2 as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <linux/kernel.h>
  21 #include <linux/blkdev.h>
  22 #include <linux/blk-mq.h>
  23 #include <linux/elevator.h>
  24 #include <linux/module.h>
  25 #include <linux/sbitmap.h>
  26
  27 #include "blk.h"
  28 #include "blk-mq.h"
  29 #include "blk-mq-debugfs.h"
  30 #include "blk-mq-sched.h"
  31 #include "blk-mq-tag.h"
  32
  33 #define CREATE_TRACE_POINTS
  34 #include <trace/events/kyber.h>
  35
  36 /*
  37  * Scheduling domains: the device is divided into multiple domains based on the
  38  * request type.
  39  */
  40 enum {
  41         KYBER_READ,
  42         KYBER_WRITE,
  43         KYBER_DISCARD,
  44         KYBER_OTHER,
  45         KYBER_NUM_DOMAINS,
  46 };
  47
  48 static const char *kyber_domain_names[] = {
  49         [KYBER_READ] = "READ",
  50         [KYBER_WRITE] = "WRITE",
  51         [KYBER_DISCARD] = "DISCARD",
  52         [KYBER_OTHER] = "OTHER",
  53 };
  54
  55 enum {
  56         /*
  57          * In order to prevent starvation of synchronous requests by a flood of
  58          * asynchronous requests, we reserve 25% of requests for synchronous
  59          * operations.
  60          */
  61         KYBER_ASYNC_PERCENT = 75,
  62 };
  63
  64 /*
  65  * Maximum device-wide depth for each scheduling domain.
  66  *
  67  * Even for fast devices with lots of tags like NVMe, you can saturate the
  68  * device with only a fraction of the maximum possible queue depth. So, we cap
  69  * these to a reasonable value.
  70  */
  71 static const unsigned int kyber_depth[] = {
  72         [KYBER_READ] = 256,
  73         [KYBER_WRITE] = 128,
  74         [KYBER_DISCARD] = 64,
  75         [KYBER_OTHER] = 16,
  76 };
  77
  78 /*
  79  * Default latency targets for each scheduling domain.
  80  */
  81 static const u64 kyber_latency_targets[] = {
  82         [KYBER_READ] = 2ULL * NSEC_PER_MSEC,
  83         [KYBER_WRITE] = 10ULL * NSEC_PER_MSEC,
  84         [KYBER_DISCARD] = 5ULL * NSEC_PER_SEC,
  85 };
  86
  87 /*
  88  * Batch size (number of requests we'll dispatch in a row) for each scheduling
  89  * domain.
  90  */
  91 static const unsigned int kyber_batch_size[] = {
  92         [KYBER_READ] = 16,
  93         [KYBER_WRITE] = 8,
  94         [KYBER_DISCARD] = 1,
  95         [KYBER_OTHER] = 1,
  96 };
  97
  98 /*
  99  * Requests latencies are recorded in a histogram with buckets defined relative
 100  * to the target latency:
 101  *
 102  * <= 1/4 * target latency
 103  * <= 1/2 * target latency
 104  * <= 3/4 * target latency
 105  * <= target latency
 106  * <= 1 1/4 * target latency
 107  * <= 1 1/2 * target latency
 108  * <= 1 3/4 * target latency
 109  * > 1 3/4 * target latency
 110  */
 111 enum {
 112         /*
 113          * The width of the latency histogram buckets is
 114          * 1 / (1 << KYBER_LATENCY_SHIFT) * target latency.
 115          */
 116         KYBER_LATENCY_SHIFT = 2,
 117         /*
 118          * The first (1 << KYBER_LATENCY_SHIFT) buckets are <= target latency,
 119          * thus, "good".
 120          */
 121         KYBER_GOOD_BUCKETS = 1 << KYBER_LATENCY_SHIFT,
 122         /* There are also (1 << KYBER_LATENCY_SHIFT) "bad" buckets. */
 123         KYBER_LATENCY_BUCKETS = 2 << KYBER_LATENCY_SHIFT,
 124 };
 125
 126 /*
 127  * We measure both the total latency and the I/O latency (i.e., latency after
 128  * submitting to the device).
 129  */
 130 enum {
 131         KYBER_TOTAL_LATENCY,
 132         KYBER_IO_LATENCY,
 133 };
 134
 135 static const char *kyber_latency_type_names[] = {
 136         [KYBER_TOTAL_LATENCY] = "total",
 137         [KYBER_IO_LATENCY] = "I/O",
 138 };
 139
 140 /*
 141  * Per-cpu latency histograms: total latency and I/O latency for each scheduling
 142  * domain except for KYBER_OTHER.
 143  */
 144 struct kyber_cpu_latency {
 145         atomic_t buckets[KYBER_OTHER][2][KYBER_LATENCY_BUCKETS];
 146 };
 147
 148 /*
 149  * There is a same mapping between ctx & hctx and kcq & khd,
 150  * we use request->mq_ctx->index_hw to index the kcq in khd.
 151  */
 152 struct kyber_ctx_queue {
 153         /*
 154          * Used to ensure operations on rq_list and kcq_map to be an atmoic one.
 155          * Also protect the rqs on rq_list when merge.
 156          */
 157         spinlock_t lock;
 158         struct list_head rq_list[KYBER_NUM_DOMAINS];
 159 } ____cacheline_aligned_in_smp;
 160
 161 struct kyber_queue_data {
 162         struct request_queue *q;
 163
 164         /*
 165          * Each scheduling domain has a limited number of in-flight requests
 166          * device-wide, limited by these tokens.
 167          */
 168         struct sbitmap_queue domain_tokens[KYBER_NUM_DOMAINS];
 169
 170         /*
 171          * Async request percentage, converted to per-word depth for
 172          * sbitmap_get_shallow().
 173          */
 174         unsigned int async_depth;
 175
 176         struct kyber_cpu_latency __percpu *cpu_latency;
 177
 178         /* Timer for stats aggregation and adjusting domain tokens. */
 179         struct timer_list timer;
 180
 181         unsigned int latency_buckets[KYBER_OTHER][2][KYBER_LATENCY_BUCKETS];
 182
 183         unsigned long latency_timeout[KYBER_OTHER];
 184
 185         int domain_p99[KYBER_OTHER];
 186
 187         /* Target latencies in nanoseconds. */
 188         u64 latency_targets[KYBER_OTHER];
 189 };
 190
 191 struct kyber_hctx_data {
 192         spinlock_t lock;
 193         struct list_head rqs[KYBER_NUM_DOMAINS];
 194         unsigned int cur_domain;
 195         unsigned int batching;
 196         struct kyber_ctx_queue *kcqs;
 197         struct sbitmap kcq_map[KYBER_NUM_DOMAINS];
 198         wait_queue_entry_t domain_wait[KYBER_NUM_DOMAINS];
 199         struct sbq_wait_state *domain_ws[KYBER_NUM_DOMAINS];
 200         atomic_t wait_index[KYBER_NUM_DOMAINS];
 201 };
 202
 203 static int kyber_domain_wake(wait_queue_entry_t *wait, unsigned mode, int flags,
 204                              void *key);
 205
 206 static unsigned int kyber_sched_domain(unsigned int op)
 207 {
 208         switch (op & REQ_OP_MASK) {
 209         case REQ_OP_READ:
 210                 return KYBER_READ;
 211         case REQ_OP_WRITE:
 212                 return KYBER_WRITE;
 213         case REQ_OP_DISCARD:
 214                 return KYBER_DISCARD;
 215         default:
 216                 return KYBER_OTHER;
 217         }
 218 }
 219
 220 static void flush_latency_buckets(struct kyber_queue_data *kqd,
 221                                   struct kyber_cpu_latency *cpu_latency,
 222                                   unsigned int sched_domain, unsigned int type)
 223 {
 224         unsigned int *buckets = kqd->latency_buckets[sched_domain][type];
 225         atomic_t *cpu_buckets = cpu_latency->buckets[sched_domain][type];
 226         unsigned int bucket;
 227
 228         for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS; bucket++)
 229                 buckets[bucket] += atomic_xchg(&cpu_buckets[bucket], 0);
 230 }
 231
 232 /*
 233  * Calculate the histogram bucket with the given percentile rank, or -1 if there
 234  * aren't enough samples yet.
 235  */
 236 static int calculate_percentile(struct kyber_queue_data *kqd,
 237                                 unsigned int sched_domain, unsigned int type,
 238                                 unsigned int percentile)
 239 {
 240         unsigned int *buckets = kqd->latency_buckets[sched_domain][type];
 241         unsigned int bucket, samples = 0, percentile_samples;
 242
 243         for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS; bucket++)
 244                 samples += buckets[bucket];
 245
 246         if (!samples)
 247                 return -1;
 248
 249         /*
 250          * We do the calculation once we have 500 samples or one second passes
 251          * since the first sample was recorded, whichever comes first.
 252          */
 253         if (!kqd->latency_timeout[sched_domain])
 254                 kqd->latency_timeout[sched_domain] = max(jiffies + HZ, 1UL);
 255         if (samples < 500 &&
 256             time_is_after_jiffies(kqd->latency_timeout[sched_domain])) {
 257                 return -1;
 258         }
 259         kqd->latency_timeout[sched_domain] = 0;
 260
 261         percentile_samples = DIV_ROUND_UP(samples * percentile, 100);
 262         for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS - 1; bucket++) {
 263                 if (buckets[bucket] >= percentile_samples)
 264                         break;
 265                 percentile_samples -= buckets[bucket];
 266         }
 267         memset(buckets, 0, sizeof(kqd->latency_buckets[sched_domain][type]));
 268
 269         trace_kyber_latency(kqd->q, kyber_domain_names[sched_domain],
 270                             kyber_latency_type_names[type], percentile,
 271                             bucket + 1, 1 << KYBER_LATENCY_SHIFT, samples);
 272
 273         return bucket;
 274 }
 275
 276 static void kyber_resize_domain(struct kyber_queue_data *kqd,
 277                                 unsigned int sched_domain, unsigned int depth)
 278 {
 279         depth = clamp(depth, 1U, kyber_depth[sched_domain]);
 280         if (depth != kqd->domain_tokens[sched_domain].sb.depth) {
 281                 sbitmap_queue_resize(&kqd->domain_tokens[sched_domain], depth);
 282                 trace_kyber_adjust(kqd->q, kyber_domain_names[sched_domain],
 283                                    depth);
 284         }
 285 }
 286
 287 static void kyber_timer_fn(struct timer_list *t)
 288 {
 289         struct kyber_queue_data *kqd = from_timer(kqd, t, timer);
 290         unsigned int sched_domain;
 291         int cpu;
 292         bool bad = false;
 293
 294         /* Sum all of the per-cpu latency histograms. */
 295         for_each_online_cpu(cpu) {
 296                 struct kyber_cpu_latency *cpu_latency;
 297
 298                 cpu_latency = per_cpu_ptr(kqd->cpu_latency, cpu);
 299                 for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 300                         flush_latency_buckets(kqd, cpu_latency, sched_domain,
 301                                               KYBER_TOTAL_LATENCY);
 302                         flush_latency_buckets(kqd, cpu_latency, sched_domain,
 303                                               KYBER_IO_LATENCY);
 304                 }
 305         }
 306
 307         /*
 308          * Check if any domains have a high I/O latency, which might indicate
 309          * congestion in the device. Note that we use the p90; we don't want to
 310          * be too sensitive to outliers here.
 311          */
 312         for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 313                 int p90;
 314
 315                 p90 = calculate_percentile(kqd, sched_domain, KYBER_IO_LATENCY,
 316                                            90);
 317                 if (p90 >= KYBER_GOOD_BUCKETS)
 318                         bad = true;
 319         }
 320
 321         /*
 322          * Adjust the scheduling domain depths. If we determined that there was
 323          * congestion, we throttle all domains with good latencies. Either way,
 324          * we ease up on throttling domains with bad latencies.
 325          */
 326         for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 327                 unsigned int orig_depth, depth;
 328                 int p99;
 329
 330                 p99 = calculate_percentile(kqd, sched_domain,
 331                                            KYBER_TOTAL_LATENCY, 99);
 332                 /*
 333                  * This is kind of subtle: different domains will not
 334                  * necessarily have enough samples to calculate the latency
 335                  * percentiles during the same window, so we have to remember
 336                  * the p99 for the next time we observe congestion; once we do,
 337                  * we don't want to throttle again until we get more data, so we
 338                  * reset it to -1.
 339                  */
 340                 if (bad) {
 341                         if (p99 < 0)
 342                                 p99 = kqd->domain_p99[sched_domain];
 343                         kqd->domain_p99[sched_domain] = -1;
 344                 } else if (p99 >= 0) {
 345                         kqd->domain_p99[sched_domain] = p99;
 346                 }
 347                 if (p99 < 0)
 348                         continue;
 349
 350                 /*
 351                  * If this domain has bad latency, throttle less. Otherwise,
 352                  * throttle more iff we determined that there is congestion.
 353                  *
 354                  * The new depth is scaled linearly with the p99 latency vs the
 355                  * latency target. E.g., if the p99 is 3/4 of the target, then
 356                  * we throttle down to 3/4 of the current depth, and if the p99
 357                  * is 2x the target, then we double the depth.
 358                  */
 359                 if (bad || p99 >= KYBER_GOOD_BUCKETS) {
 360                         orig_depth = kqd->domain_tokens[sched_domain].sb.depth;
 361                         depth = (orig_depth * (p99 + 1)) >> KYBER_LATENCY_SHIFT;
 362                         kyber_resize_domain(kqd, sched_domain, depth);
 363                 }
 364         }
 365 }
 366
 367 static unsigned int kyber_sched_tags_shift(struct request_queue *q)
 368 {
 369         /*
 370          * All of the hardware queues have the same depth, so we can just grab
 371          * the shift of the first one.
 372          */
 373         return q->queue_hw_ctx[0]->sched_tags->bitmap_tags.sb.shift;
 374 }
 375
 376 static struct kyber_queue_data *kyber_queue_data_alloc(struct request_queue *q)
 377 {
 378         struct kyber_queue_data *kqd;
 379         unsigned int shift;
 380         int ret = -ENOMEM;
 381         int i;
 382
 383         kqd = kzalloc_node(sizeof(*kqd), GFP_KERNEL, q->node);
 384         if (!kqd)
 385                 goto err;
 386
 387         kqd->q = q;
 388
 389         kqd->cpu_latency = alloc_percpu_gfp(struct kyber_cpu_latency,
 390                                             GFP_KERNEL | __GFP_ZERO);
 391         if (!kqd->cpu_latency)
 392                 goto err_kqd;
 393
 394         timer_setup(&kqd->timer, kyber_timer_fn, 0);
 395
 396         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 397                 WARN_ON(!kyber_depth[i]);
 398                 WARN_ON(!kyber_batch_size[i]);
 399                 ret = sbitmap_queue_init_node(&kqd->domain_tokens[i],
 400                                               kyber_depth[i], -1, false,
 401                                               GFP_KERNEL, q->node);
 402                 if (ret) {
 403                         while (--i >= 0)
 404                                 sbitmap_queue_free(&kqd->domain_tokens[i]);
 405                         goto err_buckets;
 406                 }
 407         }
 408
 409         for (i = 0; i < KYBER_OTHER; i++) {
 410                 kqd->domain_p99[i] = -1;
 411                 kqd->latency_targets[i] = kyber_latency_targets[i];
 412         }
 413
 414         shift = kyber_sched_tags_shift(q);
 415         kqd->async_depth = (1U << shift) * KYBER_ASYNC_PERCENT / 100U;
 416
 417         return kqd;
 418
 419 err_buckets:
 420         free_percpu(kqd->cpu_latency);
 421 err_kqd:
 422         kfree(kqd);
 423 err:
 424         return ERR_PTR(ret);
 425 }
 426
 427 static int kyber_init_sched(struct request_queue *q, struct elevator_type *e)
 428 {
 429         struct kyber_queue_data *kqd;
 430         struct elevator_queue *eq;
 431
 432         eq = elevator_alloc(q, e);
 433         if (!eq)
 434                 return -ENOMEM;
 435
 436         kqd = kyber_queue_data_alloc(q);
 437         if (IS_ERR(kqd)) {
 438                 kobject_put(&eq->kobj);
 439                 return PTR_ERR(kqd);
 440         }
 441
 442         blk_stat_enable_accounting(q);
 443
 444         eq->elevator_data = kqd;
 445         q->elevator = eq;
 446
 447         return 0;
 448 }
 449
 450 static void kyber_exit_sched(struct elevator_queue *e)
 451 {
 452         struct kyber_queue_data *kqd = e->elevator_data;
 453         int i;
 454
 455         del_timer_sync(&kqd->timer);
 456
 457         for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 458                 sbitmap_queue_free(&kqd->domain_tokens[i]);
 459         free_percpu(kqd->cpu_latency);
 460         kfree(kqd);
 461 }
 462
 463 static void kyber_ctx_queue_init(struct kyber_ctx_queue *kcq)
 464 {
 465         unsigned int i;
 466
 467         spin_lock_init(&kcq->lock);
 468         for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 469                 INIT_LIST_HEAD(&kcq->rq_list[i]);
 470 }
 471
 472 static int kyber_init_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
 473 {
 474         struct kyber_queue_data *kqd = hctx->queue->elevator->elevator_data;
 475         struct kyber_hctx_data *khd;
 476         int i;
 477
 478         khd = kmalloc_node(sizeof(*khd), GFP_KERNEL, hctx->numa_node);
 479         if (!khd)
 480                 return -ENOMEM;
 481
 482         khd->kcqs = kmalloc_array_node(hctx->nr_ctx,
 483                                        sizeof(struct kyber_ctx_queue),
 484                                        GFP_KERNEL, hctx->numa_node);
 485         if (!khd->kcqs)
 486                 goto err_khd;
 487
 488         for (i = 0; i < hctx->nr_ctx; i++)
 489                 kyber_ctx_queue_init(&khd->kcqs[i]);
 490
 491         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 492                 if (sbitmap_init_node(&khd->kcq_map[i], hctx->nr_ctx,
 493                                       ilog2(8), GFP_KERNEL, hctx->numa_node)) {
 494                         while (--i >= 0)
 495                                 sbitmap_free(&khd->kcq_map[i]);
 496                         goto err_kcqs;
 497                 }
 498         }
 499
 500         spin_lock_init(&khd->lock);
 501
 502         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 503                 INIT_LIST_HEAD(&khd->rqs[i]);
 504                 init_waitqueue_func_entry(&khd->domain_wait[i],
 505                                           kyber_domain_wake);
 506                 khd->domain_wait[i].private = hctx;
 507                 INIT_LIST_HEAD(&khd->domain_wait[i].entry);
 508                 atomic_set(&khd->wait_index[i], 0);
 509         }
 510
 511         khd->cur_domain = 0;
 512         khd->batching = 0;
 513
 514         hctx->sched_data = khd;
 515         sbitmap_queue_min_shallow_depth(&hctx->sched_tags->bitmap_tags,
 516                                         kqd->async_depth);
 517
 518         return 0;
 519
 520 err_kcqs:
 521         kfree(khd->kcqs);
 522 err_khd:
 523         kfree(khd);
 524         return -ENOMEM;
 525 }
 526
 527 static void kyber_exit_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
 528 {
 529         struct kyber_hctx_data *khd = hctx->sched_data;
 530         int i;
 531
 532         for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 533                 sbitmap_free(&khd->kcq_map[i]);
 534         kfree(khd->kcqs);
 535         kfree(hctx->sched_data);
 536 }
 537
 538 static int rq_get_domain_token(struct request *rq)
 539 {
 540         return (long)rq->elv.priv[0];
 541 }
 542
 543 static void rq_set_domain_token(struct request *rq, int token)
 544 {
 545         rq->elv.priv[0] = (void *)(long)token;
 546 }
 547
 548 static void rq_clear_domain_token(struct kyber_queue_data *kqd,
 549                                   struct request *rq)
 550 {
 551         unsigned int sched_domain;
 552         int nr;
 553
 554         nr = rq_get_domain_token(rq);
 555         if (nr != -1) {
 556                 sched_domain = kyber_sched_domain(rq->cmd_flags);
 557                 sbitmap_queue_clear(&kqd->domain_tokens[sched_domain], nr,
 558                                     rq->mq_ctx->cpu);
 559         }
 560 }
 561
 562 static void kyber_limit_depth(unsigned int op, struct blk_mq_alloc_data *data)
 563 {
 564         /*
 565          * We use the scheduler tags as per-hardware queue queueing tokens.
 566          * Async requests can be limited at this stage.
 567          */
 568         if (!op_is_sync(op)) {
 569                 struct kyber_queue_data *kqd = data->q->elevator->elevator_data;
 570
 571                 data->shallow_depth = kqd->async_depth;
 572         }
 573 }
 574
 575 static bool kyber_bio_merge(struct blk_mq_hw_ctx *hctx, struct bio *bio)
 576 {
 577         struct kyber_hctx_data *khd = hctx->sched_data;
 578         struct blk_mq_ctx *ctx = blk_mq_get_ctx(hctx->queue);
 579         struct kyber_ctx_queue *kcq = &khd->kcqs[ctx->index_hw];
 580         unsigned int sched_domain = kyber_sched_domain(bio->bi_opf);
 581         struct list_head *rq_list = &kcq->rq_list[sched_domain];
 582         bool merged;
 583
 584         spin_lock(&kcq->lock);
 585         merged = blk_mq_bio_list_merge(hctx->queue, rq_list, bio);
 586         spin_unlock(&kcq->lock);
 587         blk_mq_put_ctx(ctx);
 588
 589         return merged;
 590 }
 591
 592 static void kyber_prepare_request(struct request *rq, struct bio *bio)
 593 {
 594         rq_set_domain_token(rq, -1);
 595 }
 596
 597 static void kyber_insert_requests(struct blk_mq_hw_ctx *hctx,
 598                                   struct list_head *rq_list, bool at_head)
 599 {
 600         struct kyber_hctx_data *khd = hctx->sched_data;
 601         struct request *rq, *next;
 602
 603         list_for_each_entry_safe(rq, next, rq_list, queuelist) {
 604                 unsigned int sched_domain = kyber_sched_domain(rq->cmd_flags);
 605                 struct kyber_ctx_queue *kcq = &khd->kcqs[rq->mq_ctx->index_hw];
 606                 struct list_head *head = &kcq->rq_list[sched_domain];
 607
 608                 spin_lock(&kcq->lock);
 609                 if (at_head)
 610                         list_move(&rq->queuelist, head);
 611                 else
 612                         list_move_tail(&rq->queuelist, head);
 613                 sbitmap_set_bit(&khd->kcq_map[sched_domain],
 614                                 rq->mq_ctx->index_hw);
 615                 blk_mq_sched_request_inserted(rq);
 616                 spin_unlock(&kcq->lock);
 617         }
 618 }
 619
 620 static void kyber_finish_request(struct request *rq)
 621 {
 622         struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 623
 624         rq_clear_domain_token(kqd, rq);
 625 }
 626
 627 static void add_latency_sample(struct kyber_cpu_latency *cpu_latency,
 628                                unsigned int sched_domain, unsigned int type,
 629                                u64 target, u64 latency)
 630 {
 631         unsigned int bucket;
 632         u64 divisor;
 633
 634         if (latency > 0) {
 635                 divisor = max_t(u64, target >> KYBER_LATENCY_SHIFT, 1);
 636                 bucket = min_t(unsigned int, div64_u64(latency - 1, divisor),
 637                                KYBER_LATENCY_BUCKETS - 1);
 638         } else {
 639                 bucket = 0;
 640         }
 641
 642         atomic_inc(&cpu_latency->buckets[sched_domain][type][bucket]);
 643 }
 644
 645 static void kyber_completed_request(struct request *rq, u64 now)
 646 {
 647         struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 648         struct kyber_cpu_latency *cpu_latency;
 649         unsigned int sched_domain;
 650         u64 target;
 651
 652         sched_domain = kyber_sched_domain(rq->cmd_flags);
 653         if (sched_domain == KYBER_OTHER)
 654                 return;
 655
 656         cpu_latency = get_cpu_ptr(kqd->cpu_latency);
 657         target = kqd->latency_targets[sched_domain];
 658         add_latency_sample(cpu_latency, sched_domain, KYBER_TOTAL_LATENCY,
 659                            target, now - rq->start_time_ns);
 660         add_latency_sample(cpu_latency, sched_domain, KYBER_IO_LATENCY, target,
 661                            now - rq->io_start_time_ns);
 662         put_cpu_ptr(kqd->cpu_latency);
 663
 664         timer_reduce(&kqd->timer, jiffies + HZ / 10);
 665 }
 666
 667 struct flush_kcq_data {
 668         struct kyber_hctx_data *khd;
 669         unsigned int sched_domain;
 670         struct list_head *list;
 671 };
 672
 673 static bool flush_busy_kcq(struct sbitmap *sb, unsigned int bitnr, void *data)
 674 {
 675         struct flush_kcq_data *flush_data = data;
 676         struct kyber_ctx_queue *kcq = &flush_data->khd->kcqs[bitnr];
 677
 678         spin_lock(&kcq->lock);
 679         list_splice_tail_init(&kcq->rq_list[flush_data->sched_domain],
 680                               flush_data->list);
 681         sbitmap_clear_bit(sb, bitnr);
 682         spin_unlock(&kcq->lock);
 683
 684         return true;
 685 }
 686
 687 static void kyber_flush_busy_kcqs(struct kyber_hctx_data *khd,
 688                                   unsigned int sched_domain,
 689                                   struct list_head *list)
 690 {
 691         struct flush_kcq_data data = {
 692                 .khd = khd,
 693                 .sched_domain = sched_domain,
 694                 .list = list,
 695         };
 696
 697         sbitmap_for_each_set(&khd->kcq_map[sched_domain],
 698                              flush_busy_kcq, &data);
 699 }
 700
 701 static int kyber_domain_wake(wait_queue_entry_t *wait, unsigned mode, int flags,
 702                              void *key)
 703 {
 704         struct blk_mq_hw_ctx *hctx = READ_ONCE(wait->private);
 705
 706         list_del_init(&wait->entry);
 707         blk_mq_run_hw_queue(hctx, true);
 708         return 1;
 709 }
 710
 711 static int kyber_get_domain_token(struct kyber_queue_data *kqd,
 712                                   struct kyber_hctx_data *khd,
 713                                   struct blk_mq_hw_ctx *hctx)
 714 {
 715         unsigned int sched_domain = khd->cur_domain;
 716         struct sbitmap_queue *domain_tokens = &kqd->domain_tokens[sched_domain];
 717         wait_queue_entry_t *wait = &khd->domain_wait[sched_domain];
 718         struct sbq_wait_state *ws;
 719         int nr;
 720
 721         nr = __sbitmap_queue_get(domain_tokens);
 722
 723         /*
 724          * If we failed to get a domain token, make sure the hardware queue is
 725          * run when one becomes available. Note that this is serialized on
 726          * khd->lock, but we still need to be careful about the waker.
 727          */
 728         if (nr < 0 && list_empty_careful(&wait->entry)) {
 729                 ws = sbq_wait_ptr(domain_tokens,
 730                                   &khd->wait_index[sched_domain]);
 731                 khd->domain_ws[sched_domain] = ws;
 732                 add_wait_queue(&ws->wait, wait);
 733
 734                 /*
 735                  * Try again in case a token was freed before we got on the wait
 736                  * queue.
 737                  */
 738                 nr = __sbitmap_queue_get(domain_tokens);
 739         }
 740
 741         /*
 742          * If we got a token while we were on the wait queue, remove ourselves
 743          * from the wait queue to ensure that all wake ups make forward
 744          * progress. It's possible that the waker already deleted the entry
 745          * between the !list_empty_careful() check and us grabbing the lock, but
 746          * list_del_init() is okay with that.
 747          */
 748         if (nr >= 0 && !list_empty_careful(&wait->entry)) {
 749                 ws = khd->domain_ws[sched_domain];
 750                 spin_lock_irq(&ws->wait.lock);
 751                 list_del_init(&wait->entry);
 752                 spin_unlock_irq(&ws->wait.lock);
 753         }
 754
 755         return nr;
 756 }
 757
 758 static struct request *
 759 kyber_dispatch_cur_domain(struct kyber_queue_data *kqd,
 760                           struct kyber_hctx_data *khd,
 761                           struct blk_mq_hw_ctx *hctx)
 762 {
 763         struct list_head *rqs;
 764         struct request *rq;
 765         int nr;
 766
 767         rqs = &khd->rqs[khd->cur_domain];
 768
 769         /*
 770          * If we already have a flushed request, then we just need to get a
 771          * token for it. Otherwise, if there are pending requests in the kcqs,
 772          * flush the kcqs, but only if we can get a token. If not, we should
 773          * leave the requests in the kcqs so that they can be merged. Note that
 774          * khd->lock serializes the flushes, so if we observed any bit set in
 775          * the kcq_map, we will always get a request.
 776          */
 777         rq = list_first_entry_or_null(rqs, struct request, queuelist);
 778         if (rq) {
 779                 nr = kyber_get_domain_token(kqd, khd, hctx);
 780                 if (nr >= 0) {
 781                         khd->batching++;
 782                         rq_set_domain_token(rq, nr);
 783                         list_del_init(&rq->queuelist);
 784                         return rq;
 785                 } else {
 786                         trace_kyber_throttled(kqd->q,
 787                                               kyber_domain_names[khd->cur_domain]);
 788                 }
 789         } else if (sbitmap_any_bit_set(&khd->kcq_map[khd->cur_domain])) {
 790                 nr = kyber_get_domain_token(kqd, khd, hctx);
 791                 if (nr >= 0) {
 792                         kyber_flush_busy_kcqs(khd, khd->cur_domain, rqs);
 793                         rq = list_first_entry(rqs, struct request, queuelist);
 794                         khd->batching++;
 795                         rq_set_domain_token(rq, nr);
 796                         list_del_init(&rq->queuelist);
 797                         return rq;
 798                 } else {
 799                         trace_kyber_throttled(kqd->q,
 800                                               kyber_domain_names[khd->cur_domain]);
 801                 }
 802         }
 803
 804         /* There were either no pending requests or no tokens. */
 805         return NULL;
 806 }
 807
 808 static struct request *kyber_dispatch_request(struct blk_mq_hw_ctx *hctx)
 809 {
 810         struct kyber_queue_data *kqd = hctx->queue->elevator->elevator_data;
 811         struct kyber_hctx_data *khd = hctx->sched_data;
 812         struct request *rq;
 813         int i;
 814
 815         spin_lock(&khd->lock);
 816
 817         /*
 818          * First, if we are still entitled to batch, try to dispatch a request
 819          * from the batch.
 820          */
 821         if (khd->batching < kyber_batch_size[khd->cur_domain]) {
 822                 rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 823                 if (rq)
 824                         goto out;
 825         }
 826
 827         /*
 828          * Either,
 829          * 1. We were no longer entitled to a batch.
 830          * 2. The domain we were batching didn't have any requests.
 831          * 3. The domain we were batching was out of tokens.
 832          *
 833          * Start another batch. Note that this wraps back around to the original
 834          * domain if no other domains have requests or tokens.
 835          */
 836         khd->batching = 0;
 837         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 838                 if (khd->cur_domain == KYBER_NUM_DOMAINS - 1)
 839                         khd->cur_domain = 0;
 840                 else
 841                         khd->cur_domain++;
 842
 843                 rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 844                 if (rq)
 845                         goto out;
 846         }
 847
 848         rq = NULL;
 849 out:
 850         spin_unlock(&khd->lock);
 851         return rq;
 852 }
 853
 854 static bool kyber_has_work(struct blk_mq_hw_ctx *hctx)
 855 {
 856         struct kyber_hctx_data *khd = hctx->sched_data;
 857         int i;
 858
 859         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 860                 if (!list_empty_careful(&khd->rqs[i]) ||
 861                     sbitmap_any_bit_set(&khd->kcq_map[i]))
 862                         return true;
 863         }
 864
 865         return false;
 866 }
 867
 868 #define KYBER_LAT_SHOW_STORE(domain, name)                              \
 869 static ssize_t kyber_##name##_lat_show(struct elevator_queue *e,        \
 870                                        char *page)                      \
 871 {                                                                       \
 872         struct kyber_queue_data *kqd = e->elevator_data;                \
 873                                                                         \
 874         return sprintf(page, "%llu\n", kqd->latency_targets[domain]);   \
 875 }                                                                       \
 876                                                                         \
 877 static ssize_t kyber_##name##_lat_store(struct elevator_queue *e,       \
 878                                         const char *page, size_t count) \
 879 {                                                                       \
 880         struct kyber_queue_data *kqd = e->elevator_data;                \
 881         unsigned long long nsec;                                        \
 882         int ret;                                                        \
 883                                                                         \
 884         ret = kstrtoull(page, 10, &nsec);                               \
 885         if (ret)                                                        \
 886                 return ret;                                             \
 887                                                                         \
 888         kqd->latency_targets[domain] = nsec;                            \
 889                                                                         \
 890         return count;                                                   \
 891 }
 892 KYBER_LAT_SHOW_STORE(KYBER_READ, read);
 893 KYBER_LAT_SHOW_STORE(KYBER_WRITE, write);
 894 #undef KYBER_LAT_SHOW_STORE
 895
 896 #define KYBER_LAT_ATTR(op) __ATTR(op##_lat_nsec, 0644, kyber_##op##_lat_show, kyber_##op##_lat_store)
 897 static struct elv_fs_entry kyber_sched_attrs[] = {
 898         KYBER_LAT_ATTR(read),
 899         KYBER_LAT_ATTR(write),
 900         __ATTR_NULL
 901 };
 902 #undef KYBER_LAT_ATTR
 903
 904 #ifdef CONFIG_BLK_DEBUG_FS
 905 #define KYBER_DEBUGFS_DOMAIN_ATTRS(domain, name)                        \
 906 static int kyber_##name##_tokens_show(void *data, struct seq_file *m)   \
 907 {                                                                       \
 908         struct request_queue *q = data;                                 \
 909         struct kyber_queue_data *kqd = q->elevator->elevator_data;      \
 910                                                                         \
 911         sbitmap_queue_show(&kqd->domain_tokens[domain], m);             \
 912         return 0;                                                       \
 913 }                                                                       \
 914                                                                         \
 915 static void *kyber_##name##_rqs_start(struct seq_file *m, loff_t *pos)  \
 916         __acquires(&khd->lock)                                          \
 917 {                                                                       \
 918         struct blk_mq_hw_ctx *hctx = m->private;                        \
 919         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 920                                                                         \
 921         spin_lock(&khd->lock);                                          \
 922         return seq_list_start(&khd->rqs[domain], *pos);                 \
 923 }                                                                       \
 924                                                                         \
 925 static void *kyber_##name##_rqs_next(struct seq_file *m, void *v,       \
 926                                      loff_t *pos)                       \
 927 {                                                                       \
 928         struct blk_mq_hw_ctx *hctx = m->private;                        \
 929         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 930                                                                         \
 931         return seq_list_next(v, &khd->rqs[domain], pos);                \
 932 }                                                                       \
 933                                                                         \
 934 static void kyber_##name##_rqs_stop(struct seq_file *m, void *v)        \
 935         __releases(&khd->lock)                                          \
 936 {                                                                       \
 937         struct blk_mq_hw_ctx *hctx = m->private;                        \
 938         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 939                                                                         \
 940         spin_unlock(&khd->lock);                                        \
 941 }                                                                       \
 942                                                                         \
 943 static const struct seq_operations kyber_##name##_rqs_seq_ops = {       \
 944         .start  = kyber_##name##_rqs_start,                             \
 945         .next   = kyber_##name##_rqs_next,                              \
 946         .stop   = kyber_##name##_rqs_stop,                              \
 947         .show   = blk_mq_debugfs_rq_show,                               \
 948 };                                                                      \
 949                                                                         \
 950 static int kyber_##name##_waiting_show(void *data, struct seq_file *m)  \
 951 {                                                                       \
 952         struct blk_mq_hw_ctx *hctx = data;                              \
 953         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 954         wait_queue_entry_t *wait = &khd->domain_wait[domain];           \
 955                                                                         \
 956         seq_printf(m, "%d\n", !list_empty_careful(&wait->entry));       \
 957         return 0;                                                       \
 958 }
 959 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_READ, read)
 960 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_WRITE, write)
 961 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_DISCARD, discard)
 962 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_OTHER, other)
 963 #undef KYBER_DEBUGFS_DOMAIN_ATTRS
 964
 965 static int kyber_async_depth_show(void *data, struct seq_file *m)
 966 {
 967         struct request_queue *q = data;
 968         struct kyber_queue_data *kqd = q->elevator->elevator_data;
 969
 970         seq_printf(m, "%u\n", kqd->async_depth);
 971         return 0;
 972 }
 973
 974 static int kyber_cur_domain_show(void *data, struct seq_file *m)
 975 {
 976         struct blk_mq_hw_ctx *hctx = data;
 977         struct kyber_hctx_data *khd = hctx->sched_data;
 978
 979         seq_printf(m, "%s\n", kyber_domain_names[khd->cur_domain]);
 980         return 0;
 981 }
 982
 983 static int kyber_batching_show(void *data, struct seq_file *m)
 984 {
 985         struct blk_mq_hw_ctx *hctx = data;
 986         struct kyber_hctx_data *khd = hctx->sched_data;
 987
 988         seq_printf(m, "%u\n", khd->batching);
 989         return 0;
 990 }
 991
 992 #define KYBER_QUEUE_DOMAIN_ATTRS(name)  \
 993         {#name "_tokens", 0400, kyber_##name##_tokens_show}
 994 static const struct blk_mq_debugfs_attr kyber_queue_debugfs_attrs[] = {
 995         KYBER_QUEUE_DOMAIN_ATTRS(read),
 996         KYBER_QUEUE_DOMAIN_ATTRS(write),
 997         KYBER_QUEUE_DOMAIN_ATTRS(discard),
 998         KYBER_QUEUE_DOMAIN_ATTRS(other),
 999         {"async_depth", 0400, kyber_async_depth_show},
1000         {},
1001 };
1002 #undef KYBER_QUEUE_DOMAIN_ATTRS
1003
1004 #define KYBER_HCTX_DOMAIN_ATTRS(name)                                   \
1005         {#name "_rqs", 0400, .seq_ops = &kyber_##name##_rqs_seq_ops},   \
1006         {#name "_waiting", 0400, kyber_##name##_waiting_show}
1007 static const struct blk_mq_debugfs_attr kyber_hctx_debugfs_attrs[] = {
1008         KYBER_HCTX_DOMAIN_ATTRS(read),
1009         KYBER_HCTX_DOMAIN_ATTRS(write),
1010         KYBER_HCTX_DOMAIN_ATTRS(discard),
1011         KYBER_HCTX_DOMAIN_ATTRS(other),
1012         {"cur_domain", 0400, kyber_cur_domain_show},
1013         {"batching", 0400, kyber_batching_show},
1014         {},
1015 };
1016 #undef KYBER_HCTX_DOMAIN_ATTRS
1017 #endif
1018
1019 static struct elevator_type kyber_sched = {
1020         .ops.mq = {
1021                 .init_sched = kyber_init_sched,
1022                 .exit_sched = kyber_exit_sched,
1023                 .init_hctx = kyber_init_hctx,
1024                 .exit_hctx = kyber_exit_hctx,
1025                 .limit_depth = kyber_limit_depth,
1026                 .bio_merge = kyber_bio_merge,
1027                 .prepare_request = kyber_prepare_request,
1028                 .insert_requests = kyber_insert_requests,
1029                 .finish_request = kyber_finish_request,
1030                 .requeue_request = kyber_finish_request,
1031                 .completed_request = kyber_completed_request,
1032                 .dispatch_request = kyber_dispatch_request,
1033                 .has_work = kyber_has_work,
1034         },
1035         .uses_mq = true,
1036 #ifdef CONFIG_BLK_DEBUG_FS
1037         .queue_debugfs_attrs = kyber_queue_debugfs_attrs,
1038         .hctx_debugfs_attrs = kyber_hctx_debugfs_attrs,
1039 #endif
1040         .elevator_attrs = kyber_sched_attrs,
1041         .elevator_name = "kyber",
1042         .elevator_owner = THIS_MODULE,
1043 };
1044
1045 static int __init kyber_init(void)
1046 {
1047         return elv_register(&kyber_sched);
1048 }
1049
1050 static void __exit kyber_exit(void)
1051 {
1052         elv_unregister(&kyber_sched);
1053 }
1054
1055 module_init(kyber_init);
1056 module_exit(kyber_exit);
1057
1058 MODULE_AUTHOR("Omar Sandoval");
1059 MODULE_LICENSE("GPL");
1060 MODULE_DESCRIPTION("Kyber I/O scheduler");