1/*
2 * Block device elevator/IO-scheduler.
3 *
4 * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
5 *
6 * 30042000 Jens Axboe <axboe@kernel.dk> :
7 *
8 * Split the elevator a bit so that it is possible to choose a different
9 * one or even write a new "plug in". There are three pieces:
10 * - elevator_fn, inserts a new request in the queue list
11 * - elevator_merge_fn, decides whether a new buffer can be merged with
12 * an existing request
13 * - elevator_dequeue_fn, called when a request is taken off the active list
14 *
15 * 20082000 Dave Jones <davej@suse.de> :
16 * Removed tests for max-bomb-segments, which was breaking elvtune
17 * when run without -bN
18 *
19 * Jens:
20 * - Rework again to work with bio instead of buffer_heads
21 * - loose bi_dev comparisons, partition handling is right now
22 * - completely modularize elevator setup and teardown
23 *
24 */
25#include <linux/kernel.h>
26#include <linux/fs.h>
27#include <linux/blkdev.h>
28#include <linux/elevator.h>
29#include <linux/bio.h>
30#include <linux/module.h>
31#include <linux/slab.h>
32#include <linux/init.h>
33#include <linux/compiler.h>
34#include <linux/blktrace_api.h>
35#include <linux/hash.h>
36#include <linux/uaccess.h>
37#include <linux/pm_runtime.h>
38#include <linux/blk-cgroup.h>
39
40#include <trace/events/block.h>
41
42#include "blk.h"
43#include "blk-mq-sched.h"
44#include "blk-pm.h"
45#include "blk-wbt.h"
46
47static DEFINE_SPINLOCK(elv_list_lock);
48static LIST_HEAD(elv_list);
49
50/*
51 * Merge hash stuff.
52 */
53#define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq))
54
55/*
56 * Query io scheduler to see if the current process issuing bio may be
57 * merged with rq.
58 */
59static int elv_iosched_allow_bio_merge(struct request *rq, struct bio *bio)
60{
61 struct request_queue *q = rq->q;
62 struct elevator_queue *e = q->elevator;
63
64 if (e->type->ops.allow_merge)
65 return e->type->ops.allow_merge(q, rq, bio);
66
67 return 1;
68}
69
70/*
71 * can we safely merge with this request?
72 */
73bool elv_bio_merge_ok(struct request *rq, struct bio *bio)
74{
75 if (!blk_rq_merge_ok(rq, bio))
76 return false;
77
78 if (!elv_iosched_allow_bio_merge(rq, bio))
79 return false;
80
81 return true;
82}
83EXPORT_SYMBOL(elv_bio_merge_ok);
84
85static bool elevator_match(const struct elevator_type *e, const char *name)
86{
87 if (!strcmp(e->elevator_name, name))
88 return true;
89 if (e->elevator_alias && !strcmp(e->elevator_alias, name))
90 return true;
91
92 return false;
93}
94
95/*
96 * Return scheduler with name 'name'
97 */
98static struct elevator_type *elevator_find(const char *name)
99{
100 struct elevator_type *e;
101
102 list_for_each_entry(e, &elv_list, list) {
103 if (elevator_match(e, name))
104 return e;
105 }
106
107 return NULL;
108}
109
110static void elevator_put(struct elevator_type *e)
111{
112 module_put(e->elevator_owner);
113}
114
115static struct elevator_type *elevator_get(struct request_queue *q,
116 const char *name, bool try_loading)
117{
118 struct elevator_type *e;
119
120 spin_lock(&elv_list_lock);
121
122 e = elevator_find(name);
123 if (!e && try_loading) {
124 spin_unlock(&elv_list_lock);
125 request_module("%s-iosched", name);
126 spin_lock(&elv_list_lock);
127 e = elevator_find(name);
128 }
129
130 if (e && !try_module_get(e->elevator_owner))
131 e = NULL;
132
133 spin_unlock(&elv_list_lock);
134 return e;
135}
136
137static char chosen_elevator[ELV_NAME_MAX];
138
139static int __init elevator_setup(char *str)
140{
141 /*
142 * Be backwards-compatible with previous kernels, so users
143 * won't get the wrong elevator.
144 */
145 strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
146 return 1;
147}
148
149__setup("elevator=", elevator_setup);
150
151static struct kobj_type elv_ktype;
152
153struct elevator_queue *elevator_alloc(struct request_queue *q,
154 struct elevator_type *e)
155{
156 struct elevator_queue *eq;
157
158 eq = kzalloc_node(sizeof(*eq), GFP_KERNEL, q->node);
159 if (unlikely(!eq))
160 return NULL;
161
162 eq->type = e;
163 kobject_init(&eq->kobj, &elv_ktype);
164 mutex_init(&eq->sysfs_lock);
165 hash_init(eq->hash);
166
167 return eq;
168}
169EXPORT_SYMBOL(elevator_alloc);
170
171static void elevator_release(struct kobject *kobj)
172{
173 struct elevator_queue *e;
174
175 e = container_of(kobj, struct elevator_queue, kobj);
176 elevator_put(e->type);
177 kfree(e);
178}
179
180void elevator_exit(struct request_queue *q, struct elevator_queue *e)
181{
182 mutex_lock(&e->sysfs_lock);
183 if (e->type->ops.exit_sched)
184 blk_mq_exit_sched(q, e);
185 mutex_unlock(&e->sysfs_lock);
186
187 kobject_put(&e->kobj);
188}
189
190static inline void __elv_rqhash_del(struct request *rq)
191{
192 hash_del(&rq->hash);
193 rq->rq_flags &= ~RQF_HASHED;
194}
195
196void elv_rqhash_del(struct request_queue *q, struct request *rq)
197{
198 if (ELV_ON_HASH(rq))
199 __elv_rqhash_del(rq);
200}
201EXPORT_SYMBOL_GPL(elv_rqhash_del);
202
203void elv_rqhash_add(struct request_queue *q, struct request *rq)
204{
205 struct elevator_queue *e = q->elevator;
206
207 BUG_ON(ELV_ON_HASH(rq));
208 hash_add(e->hash, &rq->hash, rq_hash_key(rq));
209 rq->rq_flags |= RQF_HASHED;
210}
211EXPORT_SYMBOL_GPL(elv_rqhash_add);
212
213void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
214{
215 __elv_rqhash_del(rq);
216 elv_rqhash_add(q, rq);
217}
218
219struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
220{
221 struct elevator_queue *e = q->elevator;
222 struct hlist_node *next;
223 struct request *rq;
224
225 hash_for_each_possible_safe(e->hash, rq, next, hash, offset) {
226 BUG_ON(!ELV_ON_HASH(rq));
227
228 if (unlikely(!rq_mergeable(rq))) {
229 __elv_rqhash_del(rq);
230 continue;
231 }
232
233 if (rq_hash_key(rq) == offset)
234 return rq;
235 }
236
237 return NULL;
238}
239
240/*
241 * RB-tree support functions for inserting/lookup/removal of requests
242 * in a sorted RB tree.
243 */
244void elv_rb_add(struct rb_root *root, struct request *rq)
245{
246 struct rb_node **p = &root->rb_node;
247 struct rb_node *parent = NULL;
248 struct request *__rq;
249
250 while (*p) {
251 parent = *p;
252 __rq = rb_entry(parent, struct request, rb_node);
253
254 if (blk_rq_pos(rq) < blk_rq_pos(__rq))
255 p = &(*p)->rb_left;
256 else if (blk_rq_pos(rq) >= blk_rq_pos(__rq))
257 p = &(*p)->rb_right;
258 }
259
260 rb_link_node(&rq->rb_node, parent, p);
261 rb_insert_color(&rq->rb_node, root);
262}
263EXPORT_SYMBOL(elv_rb_add);
264
265void elv_rb_del(struct rb_root *root, struct request *rq)
266{
267 BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
268 rb_erase(&rq->rb_node, root);
269 RB_CLEAR_NODE(&rq->rb_node);
270}
271EXPORT_SYMBOL(elv_rb_del);
272
273struct request *elv_rb_find(struct rb_root *root, sector_t sector)
274{
275 struct rb_node *n = root->rb_node;
276 struct request *rq;
277
278 while (n) {
279 rq = rb_entry(n, struct request, rb_node);
280
281 if (sector < blk_rq_pos(rq))
282 n = n->rb_left;
283 else if (sector > blk_rq_pos(rq))
284 n = n->rb_right;
285 else
286 return rq;
287 }
288
289 return NULL;
290}
291EXPORT_SYMBOL(elv_rb_find);
292
293enum elv_merge elv_merge(struct request_queue *q, struct request **req,
294 struct bio *bio)
295{
296 struct elevator_queue *e = q->elevator;
297 struct request *__rq;
298
299 /*
300 * Levels of merges:
301 * nomerges: No merges at all attempted
302 * noxmerges: Only simple one-hit cache try
303 * merges: All merge tries attempted
304 */
305 if (blk_queue_nomerges(q) || !bio_mergeable(bio))
306 return ELEVATOR_NO_MERGE;
307
308 /*
309 * First try one-hit cache.
310 */
311 if (q->last_merge && elv_bio_merge_ok(q->last_merge, bio)) {
312 enum elv_merge ret = blk_try_merge(q->last_merge, bio);
313
314 if (ret != ELEVATOR_NO_MERGE) {
315 *req = q->last_merge;
316 return ret;
317 }
318 }
319
320 if (blk_queue_noxmerges(q))
321 return ELEVATOR_NO_MERGE;
322
323 /*
324 * See if our hash lookup can find a potential backmerge.
325 */
326 __rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);
327 if (__rq && elv_bio_merge_ok(__rq, bio)) {
328 *req = __rq;
329 return ELEVATOR_BACK_MERGE;
330 }
331
332 if (e->type->ops.request_merge)
333 return e->type->ops.request_merge(q, req, bio);
334
335 return ELEVATOR_NO_MERGE;
336}
337
338/*
339 * Attempt to do an insertion back merge. Only check for the case where
340 * we can append 'rq' to an existing request, so we can throw 'rq' away
341 * afterwards.
342 *
343 * Returns true if we merged, false otherwise
344 */
345bool elv_attempt_insert_merge(struct request_queue *q, struct request *rq)
346{
347 struct request *__rq;
348 bool ret;
349
350 if (blk_queue_nomerges(q))
351 return false;
352
353 /*
354 * First try one-hit cache.
355 */
356 if (q->last_merge && blk_attempt_req_merge(q, q->last_merge, rq))
357 return true;
358
359 if (blk_queue_noxmerges(q))
360 return false;
361
362 ret = false;
363 /*
364 * See if our hash lookup can find a potential backmerge.
365 */
366 while (1) {
367 __rq = elv_rqhash_find(q, blk_rq_pos(rq));
368 if (!__rq || !blk_attempt_req_merge(q, __rq, rq))
369 break;
370
371 /* The merged request could be merged with others, try again */
372 ret = true;
373 rq = __rq;
374 }
375
376 return ret;
377}
378
379void elv_merged_request(struct request_queue *q, struct request *rq,
380 enum elv_merge type)
381{
382 struct elevator_queue *e = q->elevator;
383
384 if (e->type->ops.request_merged)
385 e->type->ops.request_merged(q, rq, type);
386
387 if (type == ELEVATOR_BACK_MERGE)
388 elv_rqhash_reposition(q, rq);
389
390 q->last_merge = rq;
391}
392
393void elv_merge_requests(struct request_queue *q, struct request *rq,
394 struct request *next)
395{
396 struct elevator_queue *e = q->elevator;
397
398 if (e->type->ops.requests_merged)
399 e->type->ops.requests_merged(q, rq, next);
400
401 elv_rqhash_reposition(q, rq);
402 q->last_merge = rq;
403}
404
405struct request *elv_latter_request(struct request_queue *q, struct request *rq)
406{
407 struct elevator_queue *e = q->elevator;
408
409 if (e->type->ops.next_request)
410 return e->type->ops.next_request(q, rq);
411
412 return NULL;
413}
414
415struct request *elv_former_request(struct request_queue *q, struct request *rq)
416{
417 struct elevator_queue *e = q->elevator;
418
419 if (e->type->ops.former_request)
420 return e->type->ops.former_request(q, rq);
421
422 return NULL;
423}
424
425#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
426
427static ssize_t
428elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
429{
430 struct elv_fs_entry *entry = to_elv(attr);
431 struct elevator_queue *e;
432 ssize_t error;
433
434 if (!entry->show)
435 return -EIO;
436
437 e = container_of(kobj, struct elevator_queue, kobj);
438 mutex_lock(&e->sysfs_lock);
439 error = e->type ? entry->show(e, page) : -ENOENT;
440 mutex_unlock(&e->sysfs_lock);
441 return error;
442}
443
444static ssize_t
445elv_attr_store(struct kobject *kobj, struct attribute *attr,
446 const char *page, size_t length)
447{
448 struct elv_fs_entry *entry = to_elv(attr);
449 struct elevator_queue *e;
450 ssize_t error;
451
452 if (!entry->store)
453 return -EIO;
454
455 e = container_of(kobj, struct elevator_queue, kobj);
456 mutex_lock(&e->sysfs_lock);
457 error = e->type ? entry->store(e, page, length) : -ENOENT;
458 mutex_unlock(&e->sysfs_lock);
459 return error;
460}
461
462static const struct sysfs_ops elv_sysfs_ops = {
463 .show = elv_attr_show,
464 .store = elv_attr_store,
465};
466
467static struct kobj_type elv_ktype = {
468 .sysfs_ops = &elv_sysfs_ops,
469 .release = elevator_release,
470};
471
472int elv_register_queue(struct request_queue *q)
473{
474 struct elevator_queue *e = q->elevator;
475 int error;
476
477 lockdep_assert_held(&q->sysfs_lock);
478
479 error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
480 if (!error) {
481 struct elv_fs_entry *attr = e->type->elevator_attrs;
482 if (attr) {
483 while (attr->attr.name) {
484 if (sysfs_create_file(&e->kobj, &attr->attr))
485 break;
486 attr++;
487 }
488 }
489 kobject_uevent(&e->kobj, KOBJ_ADD);
490 e->registered = 1;
491 }
492 return error;
493}
494
495void elv_unregister_queue(struct request_queue *q)
496{
497 lockdep_assert_held(&q->sysfs_lock);
498
499 if (q) {
500 struct elevator_queue *e = q->elevator;
501
502 kobject_uevent(&e->kobj, KOBJ_REMOVE);
503 kobject_del(&e->kobj);
504 e->registered = 0;
505 /* Re-enable throttling in case elevator disabled it */
506 wbt_enable_default(q);
507 }
508}
509
510int elv_register(struct elevator_type *e)
511{
512 char *def = "";
513
514 /* create icq_cache if requested */
515 if (e->icq_size) {
516 if (WARN_ON(e->icq_size < sizeof(struct io_cq)) ||
517 WARN_ON(e->icq_align < __alignof__(struct io_cq)))
518 return -EINVAL;
519
520 snprintf(e->icq_cache_name, sizeof(e->icq_cache_name),
521 "%s_io_cq", e->elevator_name);
522 e->icq_cache = kmem_cache_create(e->icq_cache_name, e->icq_size,
523 e->icq_align, 0, NULL);
524 if (!e->icq_cache)
525 return -ENOMEM;
526 }
527
528 /* register, don't allow duplicate names */
529 spin_lock(&elv_list_lock);
530 if (elevator_find(e->elevator_name)) {
531 spin_unlock(&elv_list_lock);
532 kmem_cache_destroy(e->icq_cache);
533 return -EBUSY;
534 }
535 list_add_tail(&e->list, &elv_list);
536 spin_unlock(&elv_list_lock);
537
538 printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
539 def);
540 return 0;
541}
542EXPORT_SYMBOL_GPL(elv_register);
543
544void elv_unregister(struct elevator_type *e)
545{
546 /* unregister */
547 spin_lock(&elv_list_lock);
548 list_del_init(&e->list);
549 spin_unlock(&elv_list_lock);
550
551 /*
552 * Destroy icq_cache if it exists. icq's are RCU managed. Make
553 * sure all RCU operations are complete before proceeding.
554 */
555 if (e->icq_cache) {
556 rcu_barrier();
557 kmem_cache_destroy(e->icq_cache);
558 e->icq_cache = NULL;
559 }
560}
561EXPORT_SYMBOL_GPL(elv_unregister);
562
563int elevator_switch_mq(struct request_queue *q,
564 struct elevator_type *new_e)
565{
566 int ret;
567
568 lockdep_assert_held(&q->sysfs_lock);
569
570 if (q->elevator) {
571 if (q->elevator->registered)
572 elv_unregister_queue(q);
573 ioc_clear_queue(q);
574 elevator_exit(q, q->elevator);
575 }
576
577 ret = blk_mq_init_sched(q, new_e);
578 if (ret)
579 goto out;
580
581 if (new_e) {
582 ret = elv_register_queue(q);
583 if (ret) {
584 elevator_exit(q, q->elevator);
585 goto out;
586 }
587 }
588
589 if (new_e)
590 blk_add_trace_msg(q, "elv switch: %s", new_e->elevator_name);
591 else
592 blk_add_trace_msg(q, "elv switch: none");
593
594out:
595 return ret;
596}
597
598/*
599 * For blk-mq devices, we default to using mq-deadline, if available, for single
600 * queue devices. If deadline isn't available OR we have multiple queues,
601 * default to "none".
602 */
603int elevator_init_mq(struct request_queue *q)
604{
605 struct elevator_type *e;
606 int err = 0;
607
608 if (q->nr_hw_queues != 1)
609 return 0;
610
611 /*
612 * q->sysfs_lock must be held to provide mutual exclusion between
613 * elevator_switch() and here.
614 */
615 mutex_lock(&q->sysfs_lock);
616 if (unlikely(q->elevator))
617 goto out_unlock;
618
619 e = elevator_get(q, "mq-deadline", false);
620 if (!e)
621 goto out_unlock;
622
623 err = blk_mq_init_sched(q, e);
624 if (err)
625 elevator_put(e);
626out_unlock:
627 mutex_unlock(&q->sysfs_lock);
628 return err;
629}
630
631
632/*
633 * switch to new_e io scheduler. be careful not to introduce deadlocks -
634 * we don't free the old io scheduler, before we have allocated what we
635 * need for the new one. this way we have a chance of going back to the old
636 * one, if the new one fails init for some reason.
637 */
638static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
639{
640 int err;
641
642 lockdep_assert_held(&q->sysfs_lock);
643
644 blk_mq_freeze_queue(q);
645 blk_mq_quiesce_queue(q);
646
647 err = elevator_switch_mq(q, new_e);
648
649 blk_mq_unquiesce_queue(q);
650 blk_mq_unfreeze_queue(q);
651
652 return err;
653}
654
655/*
656 * Switch this queue to the given IO scheduler.
657 */
658static int __elevator_change(struct request_queue *q, const char *name)
659{
660 char elevator_name[ELV_NAME_MAX];
661 struct elevator_type *e;
662
663 /* Make sure queue is not in the middle of being removed */
664 if (!test_bit(QUEUE_FLAG_REGISTERED, &q->queue_flags))
665 return -ENOENT;
666
667 /*
668 * Special case for mq, turn off scheduling
669 */
670 if (!strncmp(name, "none", 4)) {
671 if (!q->elevator)
672 return 0;
673 return elevator_switch(q, NULL);
674 }
675
676 strlcpy(elevator_name, name, sizeof(elevator_name));
677 e = elevator_get(q, strstrip(elevator_name), true);
678 if (!e)
679 return -EINVAL;
680
681 if (q->elevator && elevator_match(q->elevator->type, elevator_name)) {
682 elevator_put(e);
683 return 0;
684 }
685
686 return elevator_switch(q, e);
687}
688
689static inline bool elv_support_iosched(struct request_queue *q)
690{
691 if (q->tag_set && (q->tag_set->flags & BLK_MQ_F_NO_SCHED))
692 return false;
693 return true;
694}
695
696ssize_t elv_iosched_store(struct request_queue *q, const char *name,
697 size_t count)
698{
699 int ret;
700
701 if (!queue_is_mq(q) || !elv_support_iosched(q))
702 return count;
703
704 ret = __elevator_change(q, name);
705 if (!ret)
706 return count;
707
708 return ret;
709}
710
711ssize_t elv_iosched_show(struct request_queue *q, char *name)
712{
713 struct elevator_queue *e = q->elevator;
714 struct elevator_type *elv = NULL;
715 struct elevator_type *__e;
716 int len = 0;
717
718 if (!queue_is_mq(q))
719 return sprintf(name, "none\n");
720
721 if (!q->elevator)
722 len += sprintf(name+len, "[none] ");
723 else
724 elv = e->type;
725
726 spin_lock(&elv_list_lock);
727 list_for_each_entry(__e, &elv_list, list) {
728 if (elv && elevator_match(elv, __e->elevator_name)) {
729 len += sprintf(name+len, "[%s] ", elv->elevator_name);
730 continue;
731 }
732 if (elv_support_iosched(q))
733 len += sprintf(name+len, "%s ", __e->elevator_name);
734 }
735 spin_unlock(&elv_list_lock);
736
737 if (q->elevator)
738 len += sprintf(name+len, "none");
739
740 len += sprintf(len+name, "\n");
741 return len;
742}
743
744struct request *elv_rb_former_request(struct request_queue *q,
745 struct request *rq)
746{
747 struct rb_node *rbprev = rb_prev(&rq->rb_node);
748
749 if (rbprev)
750 return rb_entry_rq(rbprev);
751
752 return NULL;
753}
754EXPORT_SYMBOL(elv_rb_former_request);
755
756struct request *elv_rb_latter_request(struct request_queue *q,
757 struct request *rq)
758{
759 struct rb_node *rbnext = rb_next(&rq->rb_node);
760
761 if (rbnext)
762 return rb_entry_rq(rbnext);
763
764 return NULL;
765}
766EXPORT_SYMBOL(elv_rb_latter_request);
767