projects/linux·blob master · refs

1036 lines · 27.5 KiB

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