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