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