1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * MQ Deadline i/o scheduler - adaptation of the legacy deadline scheduler,
4 * for the blk-mq scheduling framework
5 *
6 * Copyright (C) 2016 Jens Axboe <axboe@kernel.dk>
7 */
8 #include <linux/kernel.h>
9 #include <linux/fs.h>
10 #include <linux/blkdev.h>
11 #include <linux/bio.h>
12 #include <linux/module.h>
13 #include <linux/slab.h>
14 #include <linux/init.h>
15 #include <linux/compiler.h>
16 #include <linux/rbtree.h>
17 #include <linux/sbitmap.h>
18
19 #include <trace/events/block.h>
20
21 #include "elevator.h"
22 #include "blk.h"
23 #include "blk-mq.h"
24 #include "blk-mq-debugfs.h"
25 #include "blk-mq-sched.h"
26
27 /*
28 * See Documentation/block/deadline-iosched.rst
29 */
30 static const int read_expire = HZ / 2; /* max time before a read is submitted. */
31 static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
32 /*
33 * Time after which to dispatch lower priority requests even if higher
34 * priority requests are pending.
35 */
36 static const int prio_aging_expire = 10 * HZ;
37 static const int writes_starved = 2; /* max times reads can starve a write */
38 static const int fifo_batch = 16; /* # of sequential requests treated as one
39 by the above parameters. For throughput. */
40
41 enum dd_data_dir {
42 DD_READ = READ,
43 DD_WRITE = WRITE,
44 };
45
46 enum { DD_DIR_COUNT = 2 };
47
48 enum dd_prio {
49 DD_RT_PRIO = 0,
50 DD_BE_PRIO = 1,
51 DD_IDLE_PRIO = 2,
52 DD_PRIO_MAX = 2,
53 };
54
55 enum { DD_PRIO_COUNT = 3 };
56
57 /*
58 * I/O statistics per I/O priority. It is fine if these counters overflow.
59 * What matters is that these counters are at least as wide as
60 * log2(max_outstanding_requests).
61 */
62 struct io_stats_per_prio {
63 uint32_t inserted;
64 uint32_t merged;
65 uint32_t dispatched;
66 atomic_t completed;
67 };
68
69 /*
70 * Deadline scheduler data per I/O priority (enum dd_prio). Requests are
71 * present on both sort_list[] and fifo_list[].
72 */
73 struct dd_per_prio {
74 struct list_head dispatch;
75 struct rb_root sort_list[DD_DIR_COUNT];
76 struct list_head fifo_list[DD_DIR_COUNT];
77 /* Position of the most recently dispatched request. */
78 sector_t latest_pos[DD_DIR_COUNT];
79 struct io_stats_per_prio stats;
80 };
81
82 struct deadline_data {
83 /*
84 * run time data
85 */
86
87 struct dd_per_prio per_prio[DD_PRIO_COUNT];
88
89 /* Data direction of latest dispatched request. */
90 enum dd_data_dir last_dir;
91 unsigned int batching; /* number of sequential requests made */
92 unsigned int starved; /* times reads have starved writes */
93
94 /*
95 * settings that change how the i/o scheduler behaves
96 */
97 int fifo_expire[DD_DIR_COUNT];
98 int fifo_batch;
99 int writes_starved;
100 int front_merges;
101 u32 async_depth;
102 int prio_aging_expire;
103
104 spinlock_t lock;
105 };
106
107 /* Maps an I/O priority class to a deadline scheduler priority. */
108 static const enum dd_prio ioprio_class_to_prio[] = {
109 [IOPRIO_CLASS_NONE] = DD_BE_PRIO,
110 [IOPRIO_CLASS_RT] = DD_RT_PRIO,
111 [IOPRIO_CLASS_BE] = DD_BE_PRIO,
112 [IOPRIO_CLASS_IDLE] = DD_IDLE_PRIO,
113 };
114
115 static inline struct rb_root *
deadline_rb_root(struct dd_per_prio * per_prio,struct request * rq)116 deadline_rb_root(struct dd_per_prio *per_prio, struct request *rq)
117 {
118 return &per_prio->sort_list[rq_data_dir(rq)];
119 }
120
121 /*
122 * Returns the I/O priority class (IOPRIO_CLASS_*) that has been assigned to a
123 * request.
124 */
dd_rq_ioclass(struct request * rq)125 static u8 dd_rq_ioclass(struct request *rq)
126 {
127 return IOPRIO_PRIO_CLASS(req_get_ioprio(rq));
128 }
129
130 /*
131 * Return the first request for which blk_rq_pos() >= @pos.
132 */
deadline_from_pos(struct dd_per_prio * per_prio,enum dd_data_dir data_dir,sector_t pos)133 static inline struct request *deadline_from_pos(struct dd_per_prio *per_prio,
134 enum dd_data_dir data_dir, sector_t pos)
135 {
136 struct rb_node *node = per_prio->sort_list[data_dir].rb_node;
137 struct request *rq, *res = NULL;
138
139 if (!node)
140 return NULL;
141
142 rq = rb_entry_rq(node);
143 while (node) {
144 rq = rb_entry_rq(node);
145 if (blk_rq_pos(rq) >= pos) {
146 res = rq;
147 node = node->rb_left;
148 } else {
149 node = node->rb_right;
150 }
151 }
152 return res;
153 }
154
155 static void
deadline_add_rq_rb(struct dd_per_prio * per_prio,struct request * rq)156 deadline_add_rq_rb(struct dd_per_prio *per_prio, struct request *rq)
157 {
158 struct rb_root *root = deadline_rb_root(per_prio, rq);
159
160 elv_rb_add(root, rq);
161 }
162
163 static inline void
deadline_del_rq_rb(struct dd_per_prio * per_prio,struct request * rq)164 deadline_del_rq_rb(struct dd_per_prio *per_prio, struct request *rq)
165 {
166 elv_rb_del(deadline_rb_root(per_prio, rq), rq);
167 }
168
169 /*
170 * remove rq from rbtree and fifo.
171 */
deadline_remove_request(struct request_queue * q,struct dd_per_prio * per_prio,struct request * rq)172 static void deadline_remove_request(struct request_queue *q,
173 struct dd_per_prio *per_prio,
174 struct request *rq)
175 {
176 list_del_init(&rq->queuelist);
177
178 /*
179 * We might not be on the rbtree, if we are doing an insert merge
180 */
181 if (!RB_EMPTY_NODE(&rq->rb_node))
182 deadline_del_rq_rb(per_prio, rq);
183
184 elv_rqhash_del(q, rq);
185 if (q->last_merge == rq)
186 q->last_merge = NULL;
187 }
188
dd_request_merged(struct request_queue * q,struct request * req,enum elv_merge type)189 static void dd_request_merged(struct request_queue *q, struct request *req,
190 enum elv_merge type)
191 {
192 struct deadline_data *dd = q->elevator->elevator_data;
193 const u8 ioprio_class = dd_rq_ioclass(req);
194 const enum dd_prio prio = ioprio_class_to_prio[ioprio_class];
195 struct dd_per_prio *per_prio = &dd->per_prio[prio];
196
197 /*
198 * if the merge was a front merge, we need to reposition request
199 */
200 if (type == ELEVATOR_FRONT_MERGE) {
201 elv_rb_del(deadline_rb_root(per_prio, req), req);
202 deadline_add_rq_rb(per_prio, req);
203 }
204 }
205
206 /*
207 * Callback function that is invoked after @next has been merged into @req.
208 */
dd_merged_requests(struct request_queue * q,struct request * req,struct request * next)209 static void dd_merged_requests(struct request_queue *q, struct request *req,
210 struct request *next)
211 {
212 struct deadline_data *dd = q->elevator->elevator_data;
213 const u8 ioprio_class = dd_rq_ioclass(next);
214 const enum dd_prio prio = ioprio_class_to_prio[ioprio_class];
215
216 lockdep_assert_held(&dd->lock);
217
218 dd->per_prio[prio].stats.merged++;
219
220 /*
221 * if next expires before rq, assign its expire time to rq
222 * and move into next position (next will be deleted) in fifo
223 */
224 if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
225 if (time_before((unsigned long)next->fifo_time,
226 (unsigned long)req->fifo_time)) {
227 list_move(&req->queuelist, &next->queuelist);
228 req->fifo_time = next->fifo_time;
229 }
230 }
231
232 /*
233 * kill knowledge of next, this one is a goner
234 */
235 deadline_remove_request(q, &dd->per_prio[prio], next);
236 }
237
238 /*
239 * move an entry to dispatch queue
240 */
241 static void
deadline_move_request(struct deadline_data * dd,struct dd_per_prio * per_prio,struct request * rq)242 deadline_move_request(struct deadline_data *dd, struct dd_per_prio *per_prio,
243 struct request *rq)
244 {
245 /*
246 * take it off the sort and fifo list
247 */
248 deadline_remove_request(rq->q, per_prio, rq);
249 }
250
251 /* Number of requests queued for a given priority level. */
dd_queued(struct deadline_data * dd,enum dd_prio prio)252 static u32 dd_queued(struct deadline_data *dd, enum dd_prio prio)
253 {
254 const struct io_stats_per_prio *stats = &dd->per_prio[prio].stats;
255
256 lockdep_assert_held(&dd->lock);
257
258 return stats->inserted - atomic_read(&stats->completed);
259 }
260
261 /*
262 * deadline_check_fifo returns true if and only if there are expired requests
263 * in the FIFO list. Requires !list_empty(&dd->fifo_list[data_dir]).
264 */
deadline_check_fifo(struct dd_per_prio * per_prio,enum dd_data_dir data_dir)265 static inline bool deadline_check_fifo(struct dd_per_prio *per_prio,
266 enum dd_data_dir data_dir)
267 {
268 struct request *rq = rq_entry_fifo(per_prio->fifo_list[data_dir].next);
269
270 return time_is_before_eq_jiffies((unsigned long)rq->fifo_time);
271 }
272
273 /*
274 * For the specified data direction, return the next request to
275 * dispatch using arrival ordered lists.
276 */
277 static struct request *
deadline_fifo_request(struct deadline_data * dd,struct dd_per_prio * per_prio,enum dd_data_dir data_dir)278 deadline_fifo_request(struct deadline_data *dd, struct dd_per_prio *per_prio,
279 enum dd_data_dir data_dir)
280 {
281 if (list_empty(&per_prio->fifo_list[data_dir]))
282 return NULL;
283
284 return rq_entry_fifo(per_prio->fifo_list[data_dir].next);
285 }
286
287 /*
288 * For the specified data direction, return the next request to
289 * dispatch using sector position sorted lists.
290 */
291 static struct request *
deadline_next_request(struct deadline_data * dd,struct dd_per_prio * per_prio,enum dd_data_dir data_dir)292 deadline_next_request(struct deadline_data *dd, struct dd_per_prio *per_prio,
293 enum dd_data_dir data_dir)
294 {
295 return deadline_from_pos(per_prio, data_dir,
296 per_prio->latest_pos[data_dir]);
297 }
298
299 /*
300 * Returns true if and only if @rq started after @latest_start where
301 * @latest_start is in jiffies.
302 */
started_after(struct deadline_data * dd,struct request * rq,unsigned long latest_start)303 static bool started_after(struct deadline_data *dd, struct request *rq,
304 unsigned long latest_start)
305 {
306 unsigned long start_time = (unsigned long)rq->fifo_time;
307
308 start_time -= dd->fifo_expire[rq_data_dir(rq)];
309
310 return time_after(start_time, latest_start);
311 }
312
313 /*
314 * deadline_dispatch_requests selects the best request according to
315 * read/write expire, fifo_batch, etc and with a start time <= @latest_start.
316 */
__dd_dispatch_request(struct deadline_data * dd,struct dd_per_prio * per_prio,unsigned long latest_start)317 static struct request *__dd_dispatch_request(struct deadline_data *dd,
318 struct dd_per_prio *per_prio,
319 unsigned long latest_start)
320 {
321 struct request *rq, *next_rq;
322 enum dd_data_dir data_dir;
323 enum dd_prio prio;
324 u8 ioprio_class;
325
326 lockdep_assert_held(&dd->lock);
327
328 if (!list_empty(&per_prio->dispatch)) {
329 rq = list_first_entry(&per_prio->dispatch, struct request,
330 queuelist);
331 if (started_after(dd, rq, latest_start))
332 return NULL;
333 list_del_init(&rq->queuelist);
334 data_dir = rq_data_dir(rq);
335 goto done;
336 }
337
338 /*
339 * batches are currently reads XOR writes
340 */
341 rq = deadline_next_request(dd, per_prio, dd->last_dir);
342 if (rq && dd->batching < dd->fifo_batch) {
343 /* we have a next request and are still entitled to batch */
344 data_dir = rq_data_dir(rq);
345 goto dispatch_request;
346 }
347
348 /*
349 * at this point we are not running a batch. select the appropriate
350 * data direction (read / write)
351 */
352
353 if (!list_empty(&per_prio->fifo_list[DD_READ])) {
354 BUG_ON(RB_EMPTY_ROOT(&per_prio->sort_list[DD_READ]));
355
356 if (deadline_fifo_request(dd, per_prio, DD_WRITE) &&
357 (dd->starved++ >= dd->writes_starved))
358 goto dispatch_writes;
359
360 data_dir = DD_READ;
361
362 goto dispatch_find_request;
363 }
364
365 /*
366 * there are either no reads or writes have been starved
367 */
368
369 if (!list_empty(&per_prio->fifo_list[DD_WRITE])) {
370 dispatch_writes:
371 BUG_ON(RB_EMPTY_ROOT(&per_prio->sort_list[DD_WRITE]));
372
373 dd->starved = 0;
374
375 data_dir = DD_WRITE;
376
377 goto dispatch_find_request;
378 }
379
380 return NULL;
381
382 dispatch_find_request:
383 /*
384 * we are not running a batch, find best request for selected data_dir
385 */
386 next_rq = deadline_next_request(dd, per_prio, data_dir);
387 if (deadline_check_fifo(per_prio, data_dir) || !next_rq) {
388 /*
389 * A deadline has expired, the last request was in the other
390 * direction, or we have run out of higher-sectored requests.
391 * Start again from the request with the earliest expiry time.
392 */
393 rq = deadline_fifo_request(dd, per_prio, data_dir);
394 } else {
395 /*
396 * The last req was the same dir and we have a next request in
397 * sort order. No expired requests so continue on from here.
398 */
399 rq = next_rq;
400 }
401
402 if (!rq)
403 return NULL;
404
405 dd->last_dir = data_dir;
406 dd->batching = 0;
407
408 dispatch_request:
409 if (started_after(dd, rq, latest_start))
410 return NULL;
411
412 /*
413 * rq is the selected appropriate request.
414 */
415 dd->batching++;
416 deadline_move_request(dd, per_prio, rq);
417 done:
418 ioprio_class = dd_rq_ioclass(rq);
419 prio = ioprio_class_to_prio[ioprio_class];
420 dd->per_prio[prio].latest_pos[data_dir] = blk_rq_pos(rq);
421 dd->per_prio[prio].stats.dispatched++;
422 rq->rq_flags |= RQF_STARTED;
423 return rq;
424 }
425
426 /*
427 * Check whether there are any requests with priority other than DD_RT_PRIO
428 * that were inserted more than prio_aging_expire jiffies ago.
429 */
dd_dispatch_prio_aged_requests(struct deadline_data * dd,unsigned long now)430 static struct request *dd_dispatch_prio_aged_requests(struct deadline_data *dd,
431 unsigned long now)
432 {
433 struct request *rq;
434 enum dd_prio prio;
435 int prio_cnt;
436
437 lockdep_assert_held(&dd->lock);
438
439 prio_cnt = !!dd_queued(dd, DD_RT_PRIO) + !!dd_queued(dd, DD_BE_PRIO) +
440 !!dd_queued(dd, DD_IDLE_PRIO);
441 if (prio_cnt < 2)
442 return NULL;
443
444 for (prio = DD_BE_PRIO; prio <= DD_PRIO_MAX; prio++) {
445 rq = __dd_dispatch_request(dd, &dd->per_prio[prio],
446 now - dd->prio_aging_expire);
447 if (rq)
448 return rq;
449 }
450
451 return NULL;
452 }
453
454 /*
455 * Called from blk_mq_run_hw_queue() -> __blk_mq_sched_dispatch_requests().
456 *
457 * One confusing aspect here is that we get called for a specific
458 * hardware queue, but we may return a request that is for a
459 * different hardware queue. This is because mq-deadline has shared
460 * state for all hardware queues, in terms of sorting, FIFOs, etc.
461 */
dd_dispatch_request(struct blk_mq_hw_ctx * hctx)462 static struct request *dd_dispatch_request(struct blk_mq_hw_ctx *hctx)
463 {
464 struct deadline_data *dd = hctx->queue->elevator->elevator_data;
465 const unsigned long now = jiffies;
466 struct request *rq;
467 enum dd_prio prio;
468
469 spin_lock(&dd->lock);
470 rq = dd_dispatch_prio_aged_requests(dd, now);
471 if (rq)
472 goto unlock;
473
474 /*
475 * Next, dispatch requests in priority order. Ignore lower priority
476 * requests if any higher priority requests are pending.
477 */
478 for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
479 rq = __dd_dispatch_request(dd, &dd->per_prio[prio], now);
480 if (rq || dd_queued(dd, prio))
481 break;
482 }
483
484 unlock:
485 spin_unlock(&dd->lock);
486
487 return rq;
488 }
489
490 /*
491 * 'depth' is a number in the range 1..INT_MAX representing a number of
492 * requests. Scale it with a factor (1 << bt->sb.shift) / q->nr_requests since
493 * 1..(1 << bt->sb.shift) is the range expected by sbitmap_get_shallow().
494 * Values larger than q->nr_requests have the same effect as q->nr_requests.
495 */
dd_to_word_depth(struct blk_mq_hw_ctx * hctx,unsigned int qdepth)496 static int dd_to_word_depth(struct blk_mq_hw_ctx *hctx, unsigned int qdepth)
497 {
498 struct sbitmap_queue *bt = &hctx->sched_tags->bitmap_tags;
499 const unsigned int nrr = hctx->queue->nr_requests;
500
501 return ((qdepth << bt->sb.shift) + nrr - 1) / nrr;
502 }
503
504 /*
505 * Called by __blk_mq_alloc_request(). The shallow_depth value set by this
506 * function is used by __blk_mq_get_tag().
507 */
dd_limit_depth(blk_opf_t opf,struct blk_mq_alloc_data * data)508 static void dd_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
509 {
510 struct deadline_data *dd = data->q->elevator->elevator_data;
511
512 /* Do not throttle synchronous reads. */
513 if (op_is_sync(opf) && !op_is_write(opf))
514 return;
515
516 /*
517 * Throttle asynchronous requests and writes such that these requests
518 * do not block the allocation of synchronous requests.
519 */
520 data->shallow_depth = dd_to_word_depth(data->hctx, dd->async_depth);
521 }
522
523 /* Called by blk_mq_update_nr_requests(). */
dd_depth_updated(struct blk_mq_hw_ctx * hctx)524 static void dd_depth_updated(struct blk_mq_hw_ctx *hctx)
525 {
526 struct request_queue *q = hctx->queue;
527 struct deadline_data *dd = q->elevator->elevator_data;
528 struct blk_mq_tags *tags = hctx->sched_tags;
529
530 dd->async_depth = q->nr_requests;
531
532 sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, 1);
533 }
534
535 /* Called by blk_mq_init_hctx() and blk_mq_init_sched(). */
dd_init_hctx(struct blk_mq_hw_ctx * hctx,unsigned int hctx_idx)536 static int dd_init_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
537 {
538 dd_depth_updated(hctx);
539 return 0;
540 }
541
dd_exit_sched(struct elevator_queue * e)542 static void dd_exit_sched(struct elevator_queue *e)
543 {
544 struct deadline_data *dd = e->elevator_data;
545 enum dd_prio prio;
546
547 for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
548 struct dd_per_prio *per_prio = &dd->per_prio[prio];
549 const struct io_stats_per_prio *stats = &per_prio->stats;
550 uint32_t queued;
551
552 WARN_ON_ONCE(!list_empty(&per_prio->fifo_list[DD_READ]));
553 WARN_ON_ONCE(!list_empty(&per_prio->fifo_list[DD_WRITE]));
554
555 spin_lock(&dd->lock);
556 queued = dd_queued(dd, prio);
557 spin_unlock(&dd->lock);
558
559 WARN_ONCE(queued != 0,
560 "statistics for priority %d: i %u m %u d %u c %u\n",
561 prio, stats->inserted, stats->merged,
562 stats->dispatched, atomic_read(&stats->completed));
563 }
564
565 kfree(dd);
566 }
567
568 /*
569 * initialize elevator private data (deadline_data).
570 */
dd_init_sched(struct request_queue * q,struct elevator_type * e)571 static int dd_init_sched(struct request_queue *q, struct elevator_type *e)
572 {
573 struct deadline_data *dd;
574 struct elevator_queue *eq;
575 enum dd_prio prio;
576 int ret = -ENOMEM;
577
578 eq = elevator_alloc(q, e);
579 if (!eq)
580 return ret;
581
582 dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
583 if (!dd)
584 goto put_eq;
585
586 eq->elevator_data = dd;
587
588 for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
589 struct dd_per_prio *per_prio = &dd->per_prio[prio];
590
591 INIT_LIST_HEAD(&per_prio->dispatch);
592 INIT_LIST_HEAD(&per_prio->fifo_list[DD_READ]);
593 INIT_LIST_HEAD(&per_prio->fifo_list[DD_WRITE]);
594 per_prio->sort_list[DD_READ] = RB_ROOT;
595 per_prio->sort_list[DD_WRITE] = RB_ROOT;
596 }
597 dd->fifo_expire[DD_READ] = read_expire;
598 dd->fifo_expire[DD_WRITE] = write_expire;
599 dd->writes_starved = writes_starved;
600 dd->front_merges = 1;
601 dd->last_dir = DD_WRITE;
602 dd->fifo_batch = fifo_batch;
603 dd->prio_aging_expire = prio_aging_expire;
604 spin_lock_init(&dd->lock);
605
606 /* We dispatch from request queue wide instead of hw queue */
607 blk_queue_flag_set(QUEUE_FLAG_SQ_SCHED, q);
608
609 q->elevator = eq;
610 return 0;
611
612 put_eq:
613 kobject_put(&eq->kobj);
614 return ret;
615 }
616
617 /*
618 * Try to merge @bio into an existing request. If @bio has been merged into
619 * an existing request, store the pointer to that request into *@rq.
620 */
dd_request_merge(struct request_queue * q,struct request ** rq,struct bio * bio)621 static int dd_request_merge(struct request_queue *q, struct request **rq,
622 struct bio *bio)
623 {
624 struct deadline_data *dd = q->elevator->elevator_data;
625 const u8 ioprio_class = IOPRIO_PRIO_CLASS(bio->bi_ioprio);
626 const enum dd_prio prio = ioprio_class_to_prio[ioprio_class];
627 struct dd_per_prio *per_prio = &dd->per_prio[prio];
628 sector_t sector = bio_end_sector(bio);
629 struct request *__rq;
630
631 if (!dd->front_merges)
632 return ELEVATOR_NO_MERGE;
633
634 __rq = elv_rb_find(&per_prio->sort_list[bio_data_dir(bio)], sector);
635 if (__rq) {
636 BUG_ON(sector != blk_rq_pos(__rq));
637
638 if (elv_bio_merge_ok(__rq, bio)) {
639 *rq = __rq;
640 if (blk_discard_mergable(__rq))
641 return ELEVATOR_DISCARD_MERGE;
642 return ELEVATOR_FRONT_MERGE;
643 }
644 }
645
646 return ELEVATOR_NO_MERGE;
647 }
648
649 /*
650 * Attempt to merge a bio into an existing request. This function is called
651 * before @bio is associated with a request.
652 */
dd_bio_merge(struct request_queue * q,struct bio * bio,unsigned int nr_segs)653 static bool dd_bio_merge(struct request_queue *q, struct bio *bio,
654 unsigned int nr_segs)
655 {
656 struct deadline_data *dd = q->elevator->elevator_data;
657 struct request *free = NULL;
658 bool ret;
659
660 spin_lock(&dd->lock);
661 ret = blk_mq_sched_try_merge(q, bio, nr_segs, &free);
662 spin_unlock(&dd->lock);
663
664 if (free)
665 blk_mq_free_request(free);
666
667 return ret;
668 }
669
670 /*
671 * add rq to rbtree and fifo
672 */
dd_insert_request(struct blk_mq_hw_ctx * hctx,struct request * rq,blk_insert_t flags,struct list_head * free)673 static void dd_insert_request(struct blk_mq_hw_ctx *hctx, struct request *rq,
674 blk_insert_t flags, struct list_head *free)
675 {
676 struct request_queue *q = hctx->queue;
677 struct deadline_data *dd = q->elevator->elevator_data;
678 const enum dd_data_dir data_dir = rq_data_dir(rq);
679 u16 ioprio = req_get_ioprio(rq);
680 u8 ioprio_class = IOPRIO_PRIO_CLASS(ioprio);
681 struct dd_per_prio *per_prio;
682 enum dd_prio prio;
683
684 lockdep_assert_held(&dd->lock);
685
686 prio = ioprio_class_to_prio[ioprio_class];
687 per_prio = &dd->per_prio[prio];
688 if (!rq->elv.priv[0]) {
689 per_prio->stats.inserted++;
690 rq->elv.priv[0] = (void *)(uintptr_t)1;
691 }
692
693 if (blk_mq_sched_try_insert_merge(q, rq, free))
694 return;
695
696 trace_block_rq_insert(rq);
697
698 if (flags & BLK_MQ_INSERT_AT_HEAD) {
699 list_add(&rq->queuelist, &per_prio->dispatch);
700 rq->fifo_time = jiffies;
701 } else {
702 struct list_head *insert_before;
703
704 deadline_add_rq_rb(per_prio, rq);
705
706 if (rq_mergeable(rq)) {
707 elv_rqhash_add(q, rq);
708 if (!q->last_merge)
709 q->last_merge = rq;
710 }
711
712 /*
713 * set expire time and add to fifo list
714 */
715 rq->fifo_time = jiffies + dd->fifo_expire[data_dir];
716 insert_before = &per_prio->fifo_list[data_dir];
717 list_add_tail(&rq->queuelist, insert_before);
718 }
719 }
720
721 /*
722 * Called from blk_mq_insert_request() or blk_mq_dispatch_plug_list().
723 */
dd_insert_requests(struct blk_mq_hw_ctx * hctx,struct list_head * list,blk_insert_t flags)724 static void dd_insert_requests(struct blk_mq_hw_ctx *hctx,
725 struct list_head *list,
726 blk_insert_t flags)
727 {
728 struct request_queue *q = hctx->queue;
729 struct deadline_data *dd = q->elevator->elevator_data;
730 LIST_HEAD(free);
731
732 spin_lock(&dd->lock);
733 while (!list_empty(list)) {
734 struct request *rq;
735
736 rq = list_first_entry(list, struct request, queuelist);
737 list_del_init(&rq->queuelist);
738 dd_insert_request(hctx, rq, flags, &free);
739 }
740 spin_unlock(&dd->lock);
741
742 blk_mq_free_requests(&free);
743 }
744
745 /* Callback from inside blk_mq_rq_ctx_init(). */
dd_prepare_request(struct request * rq)746 static void dd_prepare_request(struct request *rq)
747 {
748 rq->elv.priv[0] = NULL;
749 }
750
751 /*
752 * Callback from inside blk_mq_free_request().
753 */
dd_finish_request(struct request * rq)754 static void dd_finish_request(struct request *rq)
755 {
756 struct request_queue *q = rq->q;
757 struct deadline_data *dd = q->elevator->elevator_data;
758 const u8 ioprio_class = dd_rq_ioclass(rq);
759 const enum dd_prio prio = ioprio_class_to_prio[ioprio_class];
760 struct dd_per_prio *per_prio = &dd->per_prio[prio];
761
762 /*
763 * The block layer core may call dd_finish_request() without having
764 * called dd_insert_requests(). Skip requests that bypassed I/O
765 * scheduling. See also blk_mq_request_bypass_insert().
766 */
767 if (rq->elv.priv[0])
768 atomic_inc(&per_prio->stats.completed);
769 }
770
dd_has_work_for_prio(struct dd_per_prio * per_prio)771 static bool dd_has_work_for_prio(struct dd_per_prio *per_prio)
772 {
773 return !list_empty_careful(&per_prio->dispatch) ||
774 !list_empty_careful(&per_prio->fifo_list[DD_READ]) ||
775 !list_empty_careful(&per_prio->fifo_list[DD_WRITE]);
776 }
777
dd_has_work(struct blk_mq_hw_ctx * hctx)778 static bool dd_has_work(struct blk_mq_hw_ctx *hctx)
779 {
780 struct deadline_data *dd = hctx->queue->elevator->elevator_data;
781 enum dd_prio prio;
782
783 for (prio = 0; prio <= DD_PRIO_MAX; prio++)
784 if (dd_has_work_for_prio(&dd->per_prio[prio]))
785 return true;
786
787 return false;
788 }
789
790 /*
791 * sysfs parts below
792 */
793 #define SHOW_INT(__FUNC, __VAR) \
794 static ssize_t __FUNC(struct elevator_queue *e, char *page) \
795 { \
796 struct deadline_data *dd = e->elevator_data; \
797 \
798 return sysfs_emit(page, "%d\n", __VAR); \
799 }
800 #define SHOW_JIFFIES(__FUNC, __VAR) SHOW_INT(__FUNC, jiffies_to_msecs(__VAR))
801 SHOW_JIFFIES(deadline_read_expire_show, dd->fifo_expire[DD_READ]);
802 SHOW_JIFFIES(deadline_write_expire_show, dd->fifo_expire[DD_WRITE]);
803 SHOW_JIFFIES(deadline_prio_aging_expire_show, dd->prio_aging_expire);
804 SHOW_INT(deadline_writes_starved_show, dd->writes_starved);
805 SHOW_INT(deadline_front_merges_show, dd->front_merges);
806 SHOW_INT(deadline_async_depth_show, dd->async_depth);
807 SHOW_INT(deadline_fifo_batch_show, dd->fifo_batch);
808 #undef SHOW_INT
809 #undef SHOW_JIFFIES
810
811 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
812 static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
813 { \
814 struct deadline_data *dd = e->elevator_data; \
815 int __data, __ret; \
816 \
817 __ret = kstrtoint(page, 0, &__data); \
818 if (__ret < 0) \
819 return __ret; \
820 if (__data < (MIN)) \
821 __data = (MIN); \
822 else if (__data > (MAX)) \
823 __data = (MAX); \
824 *(__PTR) = __CONV(__data); \
825 return count; \
826 }
827 #define STORE_INT(__FUNC, __PTR, MIN, MAX) \
828 STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, )
829 #define STORE_JIFFIES(__FUNC, __PTR, MIN, MAX) \
830 STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, msecs_to_jiffies)
831 STORE_JIFFIES(deadline_read_expire_store, &dd->fifo_expire[DD_READ], 0, INT_MAX);
832 STORE_JIFFIES(deadline_write_expire_store, &dd->fifo_expire[DD_WRITE], 0, INT_MAX);
833 STORE_JIFFIES(deadline_prio_aging_expire_store, &dd->prio_aging_expire, 0, INT_MAX);
834 STORE_INT(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX);
835 STORE_INT(deadline_front_merges_store, &dd->front_merges, 0, 1);
836 STORE_INT(deadline_async_depth_store, &dd->async_depth, 1, INT_MAX);
837 STORE_INT(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX);
838 #undef STORE_FUNCTION
839 #undef STORE_INT
840 #undef STORE_JIFFIES
841
842 #define DD_ATTR(name) \
843 __ATTR(name, 0644, deadline_##name##_show, deadline_##name##_store)
844
845 static struct elv_fs_entry deadline_attrs[] = {
846 DD_ATTR(read_expire),
847 DD_ATTR(write_expire),
848 DD_ATTR(writes_starved),
849 DD_ATTR(front_merges),
850 DD_ATTR(async_depth),
851 DD_ATTR(fifo_batch),
852 DD_ATTR(prio_aging_expire),
853 __ATTR_NULL
854 };
855
856 #ifdef CONFIG_BLK_DEBUG_FS
857 #define DEADLINE_DEBUGFS_DDIR_ATTRS(prio, data_dir, name) \
858 static void *deadline_##name##_fifo_start(struct seq_file *m, \
859 loff_t *pos) \
860 __acquires(&dd->lock) \
861 { \
862 struct request_queue *q = m->private; \
863 struct deadline_data *dd = q->elevator->elevator_data; \
864 struct dd_per_prio *per_prio = &dd->per_prio[prio]; \
865 \
866 spin_lock(&dd->lock); \
867 return seq_list_start(&per_prio->fifo_list[data_dir], *pos); \
868 } \
869 \
870 static void *deadline_##name##_fifo_next(struct seq_file *m, void *v, \
871 loff_t *pos) \
872 { \
873 struct request_queue *q = m->private; \
874 struct deadline_data *dd = q->elevator->elevator_data; \
875 struct dd_per_prio *per_prio = &dd->per_prio[prio]; \
876 \
877 return seq_list_next(v, &per_prio->fifo_list[data_dir], pos); \
878 } \
879 \
880 static void deadline_##name##_fifo_stop(struct seq_file *m, void *v) \
881 __releases(&dd->lock) \
882 { \
883 struct request_queue *q = m->private; \
884 struct deadline_data *dd = q->elevator->elevator_data; \
885 \
886 spin_unlock(&dd->lock); \
887 } \
888 \
889 static const struct seq_operations deadline_##name##_fifo_seq_ops = { \
890 .start = deadline_##name##_fifo_start, \
891 .next = deadline_##name##_fifo_next, \
892 .stop = deadline_##name##_fifo_stop, \
893 .show = blk_mq_debugfs_rq_show, \
894 }; \
895 \
896 static int deadline_##name##_next_rq_show(void *data, \
897 struct seq_file *m) \
898 { \
899 struct request_queue *q = data; \
900 struct deadline_data *dd = q->elevator->elevator_data; \
901 struct dd_per_prio *per_prio = &dd->per_prio[prio]; \
902 struct request *rq; \
903 \
904 rq = deadline_from_pos(per_prio, data_dir, \
905 per_prio->latest_pos[data_dir]); \
906 if (rq) \
907 __blk_mq_debugfs_rq_show(m, rq); \
908 return 0; \
909 }
910
911 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_RT_PRIO, DD_READ, read0);
912 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_RT_PRIO, DD_WRITE, write0);
913 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_BE_PRIO, DD_READ, read1);
914 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_BE_PRIO, DD_WRITE, write1);
915 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_IDLE_PRIO, DD_READ, read2);
916 DEADLINE_DEBUGFS_DDIR_ATTRS(DD_IDLE_PRIO, DD_WRITE, write2);
917 #undef DEADLINE_DEBUGFS_DDIR_ATTRS
918
deadline_batching_show(void * data,struct seq_file * m)919 static int deadline_batching_show(void *data, struct seq_file *m)
920 {
921 struct request_queue *q = data;
922 struct deadline_data *dd = q->elevator->elevator_data;
923
924 seq_printf(m, "%u\n", dd->batching);
925 return 0;
926 }
927
deadline_starved_show(void * data,struct seq_file * m)928 static int deadline_starved_show(void *data, struct seq_file *m)
929 {
930 struct request_queue *q = data;
931 struct deadline_data *dd = q->elevator->elevator_data;
932
933 seq_printf(m, "%u\n", dd->starved);
934 return 0;
935 }
936
dd_async_depth_show(void * data,struct seq_file * m)937 static int dd_async_depth_show(void *data, struct seq_file *m)
938 {
939 struct request_queue *q = data;
940 struct deadline_data *dd = q->elevator->elevator_data;
941
942 seq_printf(m, "%u\n", dd->async_depth);
943 return 0;
944 }
945
dd_queued_show(void * data,struct seq_file * m)946 static int dd_queued_show(void *data, struct seq_file *m)
947 {
948 struct request_queue *q = data;
949 struct deadline_data *dd = q->elevator->elevator_data;
950 u32 rt, be, idle;
951
952 spin_lock(&dd->lock);
953 rt = dd_queued(dd, DD_RT_PRIO);
954 be = dd_queued(dd, DD_BE_PRIO);
955 idle = dd_queued(dd, DD_IDLE_PRIO);
956 spin_unlock(&dd->lock);
957
958 seq_printf(m, "%u %u %u\n", rt, be, idle);
959
960 return 0;
961 }
962
963 /* Number of requests owned by the block driver for a given priority. */
dd_owned_by_driver(struct deadline_data * dd,enum dd_prio prio)964 static u32 dd_owned_by_driver(struct deadline_data *dd, enum dd_prio prio)
965 {
966 const struct io_stats_per_prio *stats = &dd->per_prio[prio].stats;
967
968 lockdep_assert_held(&dd->lock);
969
970 return stats->dispatched + stats->merged -
971 atomic_read(&stats->completed);
972 }
973
dd_owned_by_driver_show(void * data,struct seq_file * m)974 static int dd_owned_by_driver_show(void *data, struct seq_file *m)
975 {
976 struct request_queue *q = data;
977 struct deadline_data *dd = q->elevator->elevator_data;
978 u32 rt, be, idle;
979
980 spin_lock(&dd->lock);
981 rt = dd_owned_by_driver(dd, DD_RT_PRIO);
982 be = dd_owned_by_driver(dd, DD_BE_PRIO);
983 idle = dd_owned_by_driver(dd, DD_IDLE_PRIO);
984 spin_unlock(&dd->lock);
985
986 seq_printf(m, "%u %u %u\n", rt, be, idle);
987
988 return 0;
989 }
990
991 #define DEADLINE_DISPATCH_ATTR(prio) \
992 static void *deadline_dispatch##prio##_start(struct seq_file *m, \
993 loff_t *pos) \
994 __acquires(&dd->lock) \
995 { \
996 struct request_queue *q = m->private; \
997 struct deadline_data *dd = q->elevator->elevator_data; \
998 struct dd_per_prio *per_prio = &dd->per_prio[prio]; \
999 \
1000 spin_lock(&dd->lock); \
1001 return seq_list_start(&per_prio->dispatch, *pos); \
1002 } \
1003 \
1004 static void *deadline_dispatch##prio##_next(struct seq_file *m, \
1005 void *v, loff_t *pos) \
1006 { \
1007 struct request_queue *q = m->private; \
1008 struct deadline_data *dd = q->elevator->elevator_data; \
1009 struct dd_per_prio *per_prio = &dd->per_prio[prio]; \
1010 \
1011 return seq_list_next(v, &per_prio->dispatch, pos); \
1012 } \
1013 \
1014 static void deadline_dispatch##prio##_stop(struct seq_file *m, void *v) \
1015 __releases(&dd->lock) \
1016 { \
1017 struct request_queue *q = m->private; \
1018 struct deadline_data *dd = q->elevator->elevator_data; \
1019 \
1020 spin_unlock(&dd->lock); \
1021 } \
1022 \
1023 static const struct seq_operations deadline_dispatch##prio##_seq_ops = { \
1024 .start = deadline_dispatch##prio##_start, \
1025 .next = deadline_dispatch##prio##_next, \
1026 .stop = deadline_dispatch##prio##_stop, \
1027 .show = blk_mq_debugfs_rq_show, \
1028 }
1029
1030 DEADLINE_DISPATCH_ATTR(0);
1031 DEADLINE_DISPATCH_ATTR(1);
1032 DEADLINE_DISPATCH_ATTR(2);
1033 #undef DEADLINE_DISPATCH_ATTR
1034
1035 #define DEADLINE_QUEUE_DDIR_ATTRS(name) \
1036 {#name "_fifo_list", 0400, \
1037 .seq_ops = &deadline_##name##_fifo_seq_ops}
1038 #define DEADLINE_NEXT_RQ_ATTR(name) \
1039 {#name "_next_rq", 0400, deadline_##name##_next_rq_show}
1040 static const struct blk_mq_debugfs_attr deadline_queue_debugfs_attrs[] = {
1041 DEADLINE_QUEUE_DDIR_ATTRS(read0),
1042 DEADLINE_QUEUE_DDIR_ATTRS(write0),
1043 DEADLINE_QUEUE_DDIR_ATTRS(read1),
1044 DEADLINE_QUEUE_DDIR_ATTRS(write1),
1045 DEADLINE_QUEUE_DDIR_ATTRS(read2),
1046 DEADLINE_QUEUE_DDIR_ATTRS(write2),
1047 DEADLINE_NEXT_RQ_ATTR(read0),
1048 DEADLINE_NEXT_RQ_ATTR(write0),
1049 DEADLINE_NEXT_RQ_ATTR(read1),
1050 DEADLINE_NEXT_RQ_ATTR(write1),
1051 DEADLINE_NEXT_RQ_ATTR(read2),
1052 DEADLINE_NEXT_RQ_ATTR(write2),
1053 {"batching", 0400, deadline_batching_show},
1054 {"starved", 0400, deadline_starved_show},
1055 {"async_depth", 0400, dd_async_depth_show},
1056 {"dispatch0", 0400, .seq_ops = &deadline_dispatch0_seq_ops},
1057 {"dispatch1", 0400, .seq_ops = &deadline_dispatch1_seq_ops},
1058 {"dispatch2", 0400, .seq_ops = &deadline_dispatch2_seq_ops},
1059 {"owned_by_driver", 0400, dd_owned_by_driver_show},
1060 {"queued", 0400, dd_queued_show},
1061 {},
1062 };
1063 #undef DEADLINE_QUEUE_DDIR_ATTRS
1064 #endif
1065
1066 static struct elevator_type mq_deadline = {
1067 .ops = {
1068 .depth_updated = dd_depth_updated,
1069 .limit_depth = dd_limit_depth,
1070 .insert_requests = dd_insert_requests,
1071 .dispatch_request = dd_dispatch_request,
1072 .prepare_request = dd_prepare_request,
1073 .finish_request = dd_finish_request,
1074 .next_request = elv_rb_latter_request,
1075 .former_request = elv_rb_former_request,
1076 .bio_merge = dd_bio_merge,
1077 .request_merge = dd_request_merge,
1078 .requests_merged = dd_merged_requests,
1079 .request_merged = dd_request_merged,
1080 .has_work = dd_has_work,
1081 .init_sched = dd_init_sched,
1082 .exit_sched = dd_exit_sched,
1083 .init_hctx = dd_init_hctx,
1084 },
1085
1086 #ifdef CONFIG_BLK_DEBUG_FS
1087 .queue_debugfs_attrs = deadline_queue_debugfs_attrs,
1088 #endif
1089 .elevator_attrs = deadline_attrs,
1090 .elevator_name = "mq-deadline",
1091 .elevator_alias = "deadline",
1092 .elevator_owner = THIS_MODULE,
1093 };
1094 MODULE_ALIAS("mq-deadline-iosched");
1095
deadline_init(void)1096 static int __init deadline_init(void)
1097 {
1098 return elv_register(&mq_deadline);
1099 }
1100
deadline_exit(void)1101 static void __exit deadline_exit(void)
1102 {
1103 elv_unregister(&mq_deadline);
1104 }
1105
1106 module_init(deadline_init);
1107 module_exit(deadline_exit);
1108
1109 MODULE_AUTHOR("Jens Axboe, Damien Le Moal and Bart Van Assche");
1110 MODULE_LICENSE("GPL");
1111 MODULE_DESCRIPTION("MQ deadline IO scheduler");
1112