LCOV - code coverage report
Current view: top level - block - kyber-iosched.c (source / functions) Hit Total Coverage
Test: Real Lines: 2 279 0.7 %
Date: 2020-10-17 15:46:16 Functions: 0 52 0.0 %
Legend: Neither, QEMU, Real, Both Branches: 0 0 -

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

Generated by: LCOV version 1.14