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