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         struct sbq_wait 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                 khd->domain_wait[i].sbq = NULL;
 505                 init_waitqueue_func_entry(&khd->domain_wait[i].wait,
 506                                           kyber_domain_wake);
 507                 khd->domain_wait[i].wait.private = hctx;
 508                 INIT_LIST_HEAD(&khd->domain_wait[i].wait.entry);
 509                 atomic_set(&khd->wait_index[i], 0);
 510         }
 511
 512         khd->cur_domain = 0;
 513         khd->batching = 0;
 514
 515         hctx->sched_data = khd;
 516         sbitmap_queue_min_shallow_depth(&hctx->sched_tags->bitmap_tags,
 517                                         kqd->async_depth);
 518
 519         return 0;
 520
 521 err_kcqs:
 522         kfree(khd->kcqs);
 523 err_khd:
 524         kfree(khd);
 525         return -ENOMEM;
 526 }
 527
 528 static void kyber_exit_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
 529 {
 530         struct kyber_hctx_data *khd = hctx->sched_data;
 531         int i;
 532
 533         for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 534                 sbitmap_free(&khd->kcq_map[i]);
 535         kfree(khd->kcqs);
 536         kfree(hctx->sched_data);
 537 }
 538
 539 static int rq_get_domain_token(struct request *rq)
 540 {
 541         return (long)rq->elv.priv[0];
 542 }
 543
 544 static void rq_set_domain_token(struct request *rq, int token)
 545 {
 546         rq->elv.priv[0] = (void *)(long)token;
 547 }
 548
 549 static void rq_clear_domain_token(struct kyber_queue_data *kqd,
 550                                   struct request *rq)
 551 {
 552         unsigned int sched_domain;
 553         int nr;
 554
 555         nr = rq_get_domain_token(rq);
 556         if (nr != -1) {
 557                 sched_domain = kyber_sched_domain(rq->cmd_flags);
 558                 sbitmap_queue_clear(&kqd->domain_tokens[sched_domain], nr,
 559                                     rq->mq_ctx->cpu);
 560         }
 561 }
 562
 563 static void kyber_limit_depth(unsigned int op, struct blk_mq_alloc_data *data)
 564 {
 565         /*
 566          * We use the scheduler tags as per-hardware queue queueing tokens.
 567          * Async requests can be limited at this stage.
 568          */
 569         if (!op_is_sync(op)) {
 570                 struct kyber_queue_data *kqd = data->q->elevator->elevator_data;
 571
 572                 data->shallow_depth = kqd->async_depth;
 573         }
 574 }
 575
 576 static bool kyber_bio_merge(struct blk_mq_hw_ctx *hctx, struct bio *bio)
 577 {
 578         struct kyber_hctx_data *khd = hctx->sched_data;
 579         struct blk_mq_ctx *ctx = blk_mq_get_ctx(hctx->queue);
 580         struct kyber_ctx_queue *kcq = &khd->kcqs[ctx->index_hw[hctx->type]];
 581         unsigned int sched_domain = kyber_sched_domain(bio->bi_opf);
 582         struct list_head *rq_list = &kcq->rq_list[sched_domain];
 583         bool merged;
 584
 585         spin_lock(&kcq->lock);
 586         merged = blk_mq_bio_list_merge(hctx->queue, rq_list, bio);
 587         spin_unlock(&kcq->lock);
 588         blk_mq_put_ctx(ctx);
 589
 590         return merged;
 591 }
 592
 593 static void kyber_prepare_request(struct request *rq, struct bio *bio)
 594 {
 595         rq_set_domain_token(rq, -1);
 596 }
 597
 598 static void kyber_insert_requests(struct blk_mq_hw_ctx *hctx,
 599                                   struct list_head *rq_list, bool at_head)
 600 {
 601         struct kyber_hctx_data *khd = hctx->sched_data;
 602         struct request *rq, *next;
 603
 604         list_for_each_entry_safe(rq, next, rq_list, queuelist) {
 605                 unsigned int sched_domain = kyber_sched_domain(rq->cmd_flags);
 606                 struct kyber_ctx_queue *kcq = &khd->kcqs[rq->mq_ctx->index_hw[hctx->type]];
 607                 struct list_head *head = &kcq->rq_list[sched_domain];
 608
 609                 spin_lock(&kcq->lock);
 610                 if (at_head)
 611                         list_move(&rq->queuelist, head);
 612                 else
 613                         list_move_tail(&rq->queuelist, head);
 614                 sbitmap_set_bit(&khd->kcq_map[sched_domain],
 615                                 rq->mq_ctx->index_hw[hctx->type]);
 616                 blk_mq_sched_request_inserted(rq);
 617                 spin_unlock(&kcq->lock);
 618         }
 619 }
 620
 621 static void kyber_finish_request(struct request *rq)
 622 {
 623         struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 624
 625         rq_clear_domain_token(kqd, rq);
 626 }
 627
 628 static void add_latency_sample(struct kyber_cpu_latency *cpu_latency,
 629                                unsigned int sched_domain, unsigned int type,
 630                                u64 target, u64 latency)
 631 {
 632         unsigned int bucket;
 633         u64 divisor;
 634
 635         if (latency > 0) {
 636                 divisor = max_t(u64, target >> KYBER_LATENCY_SHIFT, 1);
 637                 bucket = min_t(unsigned int, div64_u64(latency - 1, divisor),
 638                                KYBER_LATENCY_BUCKETS - 1);
 639         } else {
 640                 bucket = 0;
 641         }
 642
 643         atomic_inc(&cpu_latency->buckets[sched_domain][type][bucket]);
 644 }
 645
 646 static void kyber_completed_request(struct request *rq, u64 now)
 647 {
 648         struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 649         struct kyber_cpu_latency *cpu_latency;
 650         unsigned int sched_domain;
 651         u64 target;
 652
 653         sched_domain = kyber_sched_domain(rq->cmd_flags);
 654         if (sched_domain == KYBER_OTHER)
 655                 return;
 656
 657         cpu_latency = get_cpu_ptr(kqd->cpu_latency);
 658         target = kqd->latency_targets[sched_domain];
 659         add_latency_sample(cpu_latency, sched_domain, KYBER_TOTAL_LATENCY,
 660                            target, now - rq->start_time_ns);
 661         add_latency_sample(cpu_latency, sched_domain, KYBER_IO_LATENCY, target,
 662                            now - rq->io_start_time_ns);
 663         put_cpu_ptr(kqd->cpu_latency);
 664
 665         timer_reduce(&kqd->timer, jiffies + HZ / 10);
 666 }
 667
 668 struct flush_kcq_data {
 669         struct kyber_hctx_data *khd;
 670         unsigned int sched_domain;
 671         struct list_head *list;
 672 };
 673
 674 static bool flush_busy_kcq(struct sbitmap *sb, unsigned int bitnr, void *data)
 675 {
 676         struct flush_kcq_data *flush_data = data;
 677         struct kyber_ctx_queue *kcq = &flush_data->khd->kcqs[bitnr];
 678
 679         spin_lock(&kcq->lock);
 680         list_splice_tail_init(&kcq->rq_list[flush_data->sched_domain],
 681                               flush_data->list);
 682         sbitmap_clear_bit(sb, bitnr);
 683         spin_unlock(&kcq->lock);
 684
 685         return true;
 686 }
 687
 688 static void kyber_flush_busy_kcqs(struct kyber_hctx_data *khd,
 689                                   unsigned int sched_domain,
 690                                   struct list_head *list)
 691 {
 692         struct flush_kcq_data data = {
 693                 .khd = khd,
 694                 .sched_domain = sched_domain,
 695                 .list = list,
 696         };
 697
 698         sbitmap_for_each_set(&khd->kcq_map[sched_domain],
 699                              flush_busy_kcq, &data);
 700 }
 701
 702 static int kyber_domain_wake(wait_queue_entry_t *wqe, unsigned mode, int flags,
 703                              void *key)
 704 {
 705         struct blk_mq_hw_ctx *hctx = READ_ONCE(wqe->private);
 706         struct sbq_wait *wait = container_of(wqe, struct sbq_wait, wait);
 707
 708         sbitmap_del_wait_queue(wait);
 709         blk_mq_run_hw_queue(hctx, true);
 710         return 1;
 711 }
 712
 713 static int kyber_get_domain_token(struct kyber_queue_data *kqd,
 714                                   struct kyber_hctx_data *khd,
 715                                   struct blk_mq_hw_ctx *hctx)
 716 {
 717         unsigned int sched_domain = khd->cur_domain;
 718         struct sbitmap_queue *domain_tokens = &kqd->domain_tokens[sched_domain];
 719         struct sbq_wait *wait = &khd->domain_wait[sched_domain];
 720         struct sbq_wait_state *ws;
 721         int nr;
 722
 723         nr = __sbitmap_queue_get(domain_tokens);
 724
 725         /*
 726          * If we failed to get a domain token, make sure the hardware queue is
 727          * run when one becomes available. Note that this is serialized on
 728          * khd->lock, but we still need to be careful about the waker.
 729          */
 730         if (nr < 0 && list_empty_careful(&wait->wait.entry)) {
 731                 ws = sbq_wait_ptr(domain_tokens,
 732                                   &khd->wait_index[sched_domain]);
 733                 khd->domain_ws[sched_domain] = ws;
 734                 sbitmap_add_wait_queue(domain_tokens, ws, wait);
 735
 736                 /*
 737                  * Try again in case a token was freed before we got on the wait
 738                  * queue.
 739                  */
 740                 nr = __sbitmap_queue_get(domain_tokens);
 741         }
 742
 743         /*
 744          * If we got a token while we were on the wait queue, remove ourselves
 745          * from the wait queue to ensure that all wake ups make forward
 746          * progress. It's possible that the waker already deleted the entry
 747          * between the !list_empty_careful() check and us grabbing the lock, but
 748          * list_del_init() is okay with that.
 749          */
 750         if (nr >= 0 && !list_empty_careful(&wait->wait.entry)) {
 751                 ws = khd->domain_ws[sched_domain];
 752                 spin_lock_irq(&ws->wait.lock);
 753                 sbitmap_del_wait_queue(wait);
 754                 spin_unlock_irq(&ws->wait.lock);
 755         }
 756
 757         return nr;
 758 }
 759
 760 static struct request *
 761 kyber_dispatch_cur_domain(struct kyber_queue_data *kqd,
 762                           struct kyber_hctx_data *khd,
 763                           struct blk_mq_hw_ctx *hctx)
 764 {
 765         struct list_head *rqs;
 766         struct request *rq;
 767         int nr;
 768
 769         rqs = &khd->rqs[khd->cur_domain];
 770
 771         /*
 772          * If we already have a flushed request, then we just need to get a
 773          * token for it. Otherwise, if there are pending requests in the kcqs,
 774          * flush the kcqs, but only if we can get a token. If not, we should
 775          * leave the requests in the kcqs so that they can be merged. Note that
 776          * khd->lock serializes the flushes, so if we observed any bit set in
 777          * the kcq_map, we will always get a request.
 778          */
 779         rq = list_first_entry_or_null(rqs, struct request, queuelist);
 780         if (rq) {
 781                 nr = kyber_get_domain_token(kqd, khd, hctx);
 782                 if (nr >= 0) {
 783                         khd->batching++;
 784                         rq_set_domain_token(rq, nr);
 785                         list_del_init(&rq->queuelist);
 786                         return rq;
 787                 } else {
 788                         trace_kyber_throttled(kqd->q,
 789                                               kyber_domain_names[khd->cur_domain]);
 790                 }
 791         } else if (sbitmap_any_bit_set(&khd->kcq_map[khd->cur_domain])) {
 792                 nr = kyber_get_domain_token(kqd, khd, hctx);
 793                 if (nr >= 0) {
 794                         kyber_flush_busy_kcqs(khd, khd->cur_domain, rqs);
 795                         rq = list_first_entry(rqs, struct request, queuelist);
 796                         khd->batching++;
 797                         rq_set_domain_token(rq, nr);
 798                         list_del_init(&rq->queuelist);
 799                         return rq;
 800                 } else {
 801                         trace_kyber_throttled(kqd->q,
 802                                               kyber_domain_names[khd->cur_domain]);
 803                 }
 804         }
 805
 806         /* There were either no pending requests or no tokens. */
 807         return NULL;
 808 }
 809
 810 static struct request *kyber_dispatch_request(struct blk_mq_hw_ctx *hctx)
 811 {
 812         struct kyber_queue_data *kqd = hctx->queue->elevator->elevator_data;
 813         struct kyber_hctx_data *khd = hctx->sched_data;
 814         struct request *rq;
 815         int i;
 816
 817         spin_lock(&khd->lock);
 818
 819         /*
 820          * First, if we are still entitled to batch, try to dispatch a request
 821          * from the batch.
 822          */
 823         if (khd->batching < kyber_batch_size[khd->cur_domain]) {
 824                 rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 825                 if (rq)
 826                         goto out;
 827         }
 828
 829         /*
 830          * Either,
 831          * 1. We were no longer entitled to a batch.
 832          * 2. The domain we were batching didn't have any requests.
 833          * 3. The domain we were batching was out of tokens.
 834          *
 835          * Start another batch. Note that this wraps back around to the original
 836          * domain if no other domains have requests or tokens.
 837          */
 838         khd->batching = 0;
 839         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 840                 if (khd->cur_domain == KYBER_NUM_DOMAINS - 1)
 841                         khd->cur_domain = 0;
 842                 else
 843                         khd->cur_domain++;
 844
 845                 rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 846                 if (rq)
 847                         goto out;
 848         }
 849
 850         rq = NULL;
 851 out:
 852         spin_unlock(&khd->lock);
 853         return rq;
 854 }
 855
 856 static bool kyber_has_work(struct blk_mq_hw_ctx *hctx)
 857 {
 858         struct kyber_hctx_data *khd = hctx->sched_data;
 859         int i;
 860
 861         for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 862                 if (!list_empty_careful(&khd->rqs[i]) ||
 863                     sbitmap_any_bit_set(&khd->kcq_map[i]))
 864                         return true;
 865         }
 866
 867         return false;
 868 }
 869
 870 #define KYBER_LAT_SHOW_STORE(domain, name)                              \
 871 static ssize_t kyber_##name##_lat_show(struct elevator_queue *e,        \
 872                                        char *page)                      \
 873 {                                                                       \
 874         struct kyber_queue_data *kqd = e->elevator_data;                \
 875                                                                         \
 876         return sprintf(page, "%llu\n", kqd->latency_targets[domain]);   \
 877 }                                                                       \
 878                                                                         \
 879 static ssize_t kyber_##name##_lat_store(struct elevator_queue *e,       \
 880                                         const char *page, size_t count) \
 881 {                                                                       \
 882         struct kyber_queue_data *kqd = e->elevator_data;                \
 883         unsigned long long nsec;                                        \
 884         int ret;                                                        \
 885                                                                         \
 886         ret = kstrtoull(page, 10, &nsec);                               \
 887         if (ret)                                                        \
 888                 return ret;                                             \
 889                                                                         \
 890         kqd->latency_targets[domain] = nsec;                            \
 891                                                                         \
 892         return count;                                                   \
 893 }
 894 KYBER_LAT_SHOW_STORE(KYBER_READ, read);
 895 KYBER_LAT_SHOW_STORE(KYBER_WRITE, write);
 896 #undef KYBER_LAT_SHOW_STORE
 897
 898 #define KYBER_LAT_ATTR(op) __ATTR(op##_lat_nsec, 0644, kyber_##op##_lat_show, kyber_##op##_lat_store)
 899 static struct elv_fs_entry kyber_sched_attrs[] = {
 900         KYBER_LAT_ATTR(read),
 901         KYBER_LAT_ATTR(write),
 902         __ATTR_NULL
 903 };
 904 #undef KYBER_LAT_ATTR
 905
 906 #ifdef CONFIG_BLK_DEBUG_FS
 907 #define KYBER_DEBUGFS_DOMAIN_ATTRS(domain, name)                        \
 908 static int kyber_##name##_tokens_show(void *data, struct seq_file *m)   \
 909 {                                                                       \
 910         struct request_queue *q = data;                                 \
 911         struct kyber_queue_data *kqd = q->elevator->elevator_data;      \
 912                                                                         \
 913         sbitmap_queue_show(&kqd->domain_tokens[domain], m);             \
 914         return 0;                                                       \
 915 }                                                                       \
 916                                                                         \
 917 static void *kyber_##name##_rqs_start(struct seq_file *m, loff_t *pos)  \
 918         __acquires(&khd->lock)                                          \
 919 {                                                                       \
 920         struct blk_mq_hw_ctx *hctx = m->private;                        \
 921         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 922                                                                         \
 923         spin_lock(&khd->lock);                                          \
 924         return seq_list_start(&khd->rqs[domain], *pos);                 \
 925 }                                                                       \
 926                                                                         \
 927 static void *kyber_##name##_rqs_next(struct seq_file *m, void *v,       \
 928                                      loff_t *pos)                       \
 929 {                                                                       \
 930         struct blk_mq_hw_ctx *hctx = m->private;                        \
 931         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 932                                                                         \
 933         return seq_list_next(v, &khd->rqs[domain], pos);                \
 934 }                                                                       \
 935                                                                         \
 936 static void kyber_##name##_rqs_stop(struct seq_file *m, void *v)        \
 937         __releases(&khd->lock)                                          \
 938 {                                                                       \
 939         struct blk_mq_hw_ctx *hctx = m->private;                        \
 940         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 941                                                                         \
 942         spin_unlock(&khd->lock);                                        \
 943 }                                                                       \
 944                                                                         \
 945 static const struct seq_operations kyber_##name##_rqs_seq_ops = {       \
 946         .start  = kyber_##name##_rqs_start,                             \
 947         .next   = kyber_##name##_rqs_next,                              \
 948         .stop   = kyber_##name##_rqs_stop,                              \
 949         .show   = blk_mq_debugfs_rq_show,                               \
 950 };                                                                      \
 951                                                                         \
 952 static int kyber_##name##_waiting_show(void *data, struct seq_file *m)  \
 953 {                                                                       \
 954         struct blk_mq_hw_ctx *hctx = data;                              \
 955         struct kyber_hctx_data *khd = hctx->sched_data;                 \
 956         wait_queue_entry_t *wait = &khd->domain_wait[domain].wait;      \
 957                                                                         \
 958         seq_printf(m, "%d\n", !list_empty_careful(&wait->entry));       \
 959         return 0;                                                       \
 960 }
 961 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_READ, read)
 962 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_WRITE, write)
 963 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_DISCARD, discard)
 964 KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_OTHER, other)
 965 #undef KYBER_DEBUGFS_DOMAIN_ATTRS
 966
 967 static int kyber_async_depth_show(void *data, struct seq_file *m)
 968 {
 969         struct request_queue *q = data;
 970         struct kyber_queue_data *kqd = q->elevator->elevator_data;
 971
 972         seq_printf(m, "%u\n", kqd->async_depth);
 973         return 0;
 974 }
 975
 976 static int kyber_cur_domain_show(void *data, struct seq_file *m)
 977 {
 978         struct blk_mq_hw_ctx *hctx = data;
 979         struct kyber_hctx_data *khd = hctx->sched_data;
 980
 981         seq_printf(m, "%s\n", kyber_domain_names[khd->cur_domain]);
 982         return 0;
 983 }
 984
 985 static int kyber_batching_show(void *data, struct seq_file *m)
 986 {
 987         struct blk_mq_hw_ctx *hctx = data;
 988         struct kyber_hctx_data *khd = hctx->sched_data;
 989
 990         seq_printf(m, "%u\n", khd->batching);
 991         return 0;
 992 }
 993
 994 #define KYBER_QUEUE_DOMAIN_ATTRS(name)  \
 995         {#name "_tokens", 0400, kyber_##name##_tokens_show}
 996 static const struct blk_mq_debugfs_attr kyber_queue_debugfs_attrs[] = {
 997         KYBER_QUEUE_DOMAIN_ATTRS(read),
 998         KYBER_QUEUE_DOMAIN_ATTRS(write),
 999         KYBER_QUEUE_DOMAIN_ATTRS(discard),
1000         KYBER_QUEUE_DOMAIN_ATTRS(other),
1001         {"async_depth", 0400, kyber_async_depth_show},
1002         {},
1003 };
1004 #undef KYBER_QUEUE_DOMAIN_ATTRS
1005
1006 #define KYBER_HCTX_DOMAIN_ATTRS(name)                                   \
1007         {#name "_rqs", 0400, .seq_ops = &kyber_##name##_rqs_seq_ops},   \
1008         {#name "_waiting", 0400, kyber_##name##_waiting_show}
1009 static const struct blk_mq_debugfs_attr kyber_hctx_debugfs_attrs[] = {
1010         KYBER_HCTX_DOMAIN_ATTRS(read),
1011         KYBER_HCTX_DOMAIN_ATTRS(write),
1012         KYBER_HCTX_DOMAIN_ATTRS(discard),
1013         KYBER_HCTX_DOMAIN_ATTRS(other),
1014         {"cur_domain", 0400, kyber_cur_domain_show},
1015         {"batching", 0400, kyber_batching_show},
1016         {},
1017 };
1018 #undef KYBER_HCTX_DOMAIN_ATTRS
1019 #endif
1020
1021 static struct elevator_type kyber_sched = {
1022         .ops = {
1023                 .init_sched = kyber_init_sched,
1024                 .exit_sched = kyber_exit_sched,
1025                 .init_hctx = kyber_init_hctx,
1026                 .exit_hctx = kyber_exit_hctx,
1027                 .limit_depth = kyber_limit_depth,
1028                 .bio_merge = kyber_bio_merge,
1029                 .prepare_request = kyber_prepare_request,
1030                 .insert_requests = kyber_insert_requests,
1031                 .finish_request = kyber_finish_request,
1032                 .requeue_request = kyber_finish_request,
1033                 .completed_request = kyber_completed_request,
1034                 .dispatch_request = kyber_dispatch_request,
1035                 .has_work = kyber_has_work,
1036         },
1037 #ifdef CONFIG_BLK_DEBUG_FS
1038         .queue_debugfs_attrs = kyber_queue_debugfs_attrs,
1039         .hctx_debugfs_attrs = kyber_hctx_debugfs_attrs,
1040 #endif
1041         .elevator_attrs = kyber_sched_attrs,
1042         .elevator_name = "kyber",
1043         .elevator_owner = THIS_MODULE,
1044 };
1045
1046 static int __init kyber_init(void)
1047 {
1048         return elv_register(&kyber_sched);
1049 }
1050
1051 static void __exit kyber_exit(void)
1052 {
1053         elv_unregister(&kyber_sched);
1054 }
1055
1056 module_init(kyber_init);
1057 module_exit(kyber_exit);
1058
1059 MODULE_AUTHOR("Omar Sandoval");
1060 MODULE_LICENSE("GPL");
1061 MODULE_DESCRIPTION("Kyber I/O scheduler");