1 // SPDX-License-Identifier: GPL-2.0
3 * Block device elevator/IO-scheduler.
5 * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
7 * 30042000 Jens Axboe <axboe@kernel.dk> :
9 * Split the elevator a bit so that it is possible to choose a different
10 * one or even write a new "plug in". There are three pieces:
11 * - elevator_fn, inserts a new request in the queue list
12 * - elevator_merge_fn, decides whether a new buffer can be merged with
14 * - elevator_dequeue_fn, called when a request is taken off the active list
16 * 20082000 Dave Jones <davej@suse.de> :
17 * Removed tests for max-bomb-segments, which was breaking elvtune
18 * when run without -bN
21 * - Rework again to work with bio instead of buffer_heads
22 * - loose bi_dev comparisons, partition handling is right now
23 * - completely modularize elevator setup and teardown
26 #include <linux/kernel.h>
28 #include <linux/blkdev.h>
29 #include <linux/elevator.h>
30 #include <linux/bio.h>
31 #include <linux/module.h>
32 #include <linux/slab.h>
33 #include <linux/init.h>
34 #include <linux/compiler.h>
35 #include <linux/blktrace_api.h>
36 #include <linux/hash.h>
37 #include <linux/uaccess.h>
38 #include <linux/pm_runtime.h>
39 #include <linux/blk-cgroup.h>
41 #include <trace/events/block.h>
44 #include "blk-mq-sched.h"
48 static DEFINE_SPINLOCK(elv_list_lock
);
49 static LIST_HEAD(elv_list
);
54 #define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq))
57 * Query io scheduler to see if the current process issuing bio may be
60 static int elv_iosched_allow_bio_merge(struct request
*rq
, struct bio
*bio
)
62 struct request_queue
*q
= rq
->q
;
63 struct elevator_queue
*e
= q
->elevator
;
65 if (e
->type
->ops
.allow_merge
)
66 return e
->type
->ops
.allow_merge(q
, rq
, bio
);
72 * can we safely merge with this request?
74 bool elv_bio_merge_ok(struct request
*rq
, struct bio
*bio
)
76 if (!blk_rq_merge_ok(rq
, bio
))
79 if (!elv_iosched_allow_bio_merge(rq
, bio
))
84 EXPORT_SYMBOL(elv_bio_merge_ok
);
86 static inline bool elv_support_features(unsigned int elv_features
,
87 unsigned int required_features
)
89 return (required_features
& elv_features
) == required_features
;
93 * elevator_match - Test an elevator name and features
94 * @e: Scheduler to test
95 * @name: Elevator name to test
96 * @required_features: Features that the elevator must provide
98 * Return true if the elevator @e name matches @name and if @e provides all
99 * the features specified by @required_features.
101 static bool elevator_match(const struct elevator_type
*e
, const char *name
,
102 unsigned int required_features
)
104 if (!elv_support_features(e
->elevator_features
, required_features
))
106 if (!strcmp(e
->elevator_name
, name
))
108 if (e
->elevator_alias
&& !strcmp(e
->elevator_alias
, name
))
115 * elevator_find - Find an elevator
116 * @name: Name of the elevator to find
117 * @required_features: Features that the elevator must provide
119 * Return the first registered scheduler with name @name and supporting the
120 * features @required_features and NULL otherwise.
122 static struct elevator_type
*elevator_find(const char *name
,
123 unsigned int required_features
)
125 struct elevator_type
*e
;
127 list_for_each_entry(e
, &elv_list
, list
) {
128 if (elevator_match(e
, name
, required_features
))
135 static void elevator_put(struct elevator_type
*e
)
137 module_put(e
->elevator_owner
);
140 static struct elevator_type
*elevator_get(struct request_queue
*q
,
141 const char *name
, bool try_loading
)
143 struct elevator_type
*e
;
145 spin_lock(&elv_list_lock
);
147 e
= elevator_find(name
, q
->required_elevator_features
);
148 if (!e
&& try_loading
) {
149 spin_unlock(&elv_list_lock
);
150 request_module("%s-iosched", name
);
151 spin_lock(&elv_list_lock
);
152 e
= elevator_find(name
, q
->required_elevator_features
);
155 if (e
&& !try_module_get(e
->elevator_owner
))
158 spin_unlock(&elv_list_lock
);
162 static struct kobj_type elv_ktype
;
164 struct elevator_queue
*elevator_alloc(struct request_queue
*q
,
165 struct elevator_type
*e
)
167 struct elevator_queue
*eq
;
169 eq
= kzalloc_node(sizeof(*eq
), GFP_KERNEL
, q
->node
);
174 kobject_init(&eq
->kobj
, &elv_ktype
);
175 mutex_init(&eq
->sysfs_lock
);
180 EXPORT_SYMBOL(elevator_alloc
);
182 static void elevator_release(struct kobject
*kobj
)
184 struct elevator_queue
*e
;
186 e
= container_of(kobj
, struct elevator_queue
, kobj
);
187 elevator_put(e
->type
);
191 void __elevator_exit(struct request_queue
*q
, struct elevator_queue
*e
)
193 mutex_lock(&e
->sysfs_lock
);
194 blk_mq_exit_sched(q
, e
);
195 mutex_unlock(&e
->sysfs_lock
);
197 kobject_put(&e
->kobj
);
200 static inline void __elv_rqhash_del(struct request
*rq
)
203 rq
->rq_flags
&= ~RQF_HASHED
;
206 void elv_rqhash_del(struct request_queue
*q
, struct request
*rq
)
209 __elv_rqhash_del(rq
);
211 EXPORT_SYMBOL_GPL(elv_rqhash_del
);
213 void elv_rqhash_add(struct request_queue
*q
, struct request
*rq
)
215 struct elevator_queue
*e
= q
->elevator
;
217 BUG_ON(ELV_ON_HASH(rq
));
218 hash_add(e
->hash
, &rq
->hash
, rq_hash_key(rq
));
219 rq
->rq_flags
|= RQF_HASHED
;
221 EXPORT_SYMBOL_GPL(elv_rqhash_add
);
223 void elv_rqhash_reposition(struct request_queue
*q
, struct request
*rq
)
225 __elv_rqhash_del(rq
);
226 elv_rqhash_add(q
, rq
);
229 struct request
*elv_rqhash_find(struct request_queue
*q
, sector_t offset
)
231 struct elevator_queue
*e
= q
->elevator
;
232 struct hlist_node
*next
;
235 hash_for_each_possible_safe(e
->hash
, rq
, next
, hash
, offset
) {
236 BUG_ON(!ELV_ON_HASH(rq
));
238 if (unlikely(!rq_mergeable(rq
))) {
239 __elv_rqhash_del(rq
);
243 if (rq_hash_key(rq
) == offset
)
251 * RB-tree support functions for inserting/lookup/removal of requests
252 * in a sorted RB tree.
254 void elv_rb_add(struct rb_root
*root
, struct request
*rq
)
256 struct rb_node
**p
= &root
->rb_node
;
257 struct rb_node
*parent
= NULL
;
258 struct request
*__rq
;
262 __rq
= rb_entry(parent
, struct request
, rb_node
);
264 if (blk_rq_pos(rq
) < blk_rq_pos(__rq
))
266 else if (blk_rq_pos(rq
) >= blk_rq_pos(__rq
))
270 rb_link_node(&rq
->rb_node
, parent
, p
);
271 rb_insert_color(&rq
->rb_node
, root
);
273 EXPORT_SYMBOL(elv_rb_add
);
275 void elv_rb_del(struct rb_root
*root
, struct request
*rq
)
277 BUG_ON(RB_EMPTY_NODE(&rq
->rb_node
));
278 rb_erase(&rq
->rb_node
, root
);
279 RB_CLEAR_NODE(&rq
->rb_node
);
281 EXPORT_SYMBOL(elv_rb_del
);
283 struct request
*elv_rb_find(struct rb_root
*root
, sector_t sector
)
285 struct rb_node
*n
= root
->rb_node
;
289 rq
= rb_entry(n
, struct request
, rb_node
);
291 if (sector
< blk_rq_pos(rq
))
293 else if (sector
> blk_rq_pos(rq
))
301 EXPORT_SYMBOL(elv_rb_find
);
303 enum elv_merge
elv_merge(struct request_queue
*q
, struct request
**req
,
306 struct elevator_queue
*e
= q
->elevator
;
307 struct request
*__rq
;
311 * nomerges: No merges at all attempted
312 * noxmerges: Only simple one-hit cache try
313 * merges: All merge tries attempted
315 if (blk_queue_nomerges(q
) || !bio_mergeable(bio
))
316 return ELEVATOR_NO_MERGE
;
319 * First try one-hit cache.
321 if (q
->last_merge
&& elv_bio_merge_ok(q
->last_merge
, bio
)) {
322 enum elv_merge ret
= blk_try_merge(q
->last_merge
, bio
);
324 if (ret
!= ELEVATOR_NO_MERGE
) {
325 *req
= q
->last_merge
;
330 if (blk_queue_noxmerges(q
))
331 return ELEVATOR_NO_MERGE
;
334 * See if our hash lookup can find a potential backmerge.
336 __rq
= elv_rqhash_find(q
, bio
->bi_iter
.bi_sector
);
337 if (__rq
&& elv_bio_merge_ok(__rq
, bio
)) {
340 if (blk_discard_mergable(__rq
))
341 return ELEVATOR_DISCARD_MERGE
;
342 return ELEVATOR_BACK_MERGE
;
345 if (e
->type
->ops
.request_merge
)
346 return e
->type
->ops
.request_merge(q
, req
, bio
);
348 return ELEVATOR_NO_MERGE
;
352 * Attempt to do an insertion back merge. Only check for the case where
353 * we can append 'rq' to an existing request, so we can throw 'rq' away
356 * Returns true if we merged, false otherwise
358 bool elv_attempt_insert_merge(struct request_queue
*q
, struct request
*rq
)
360 struct request
*__rq
;
363 if (blk_queue_nomerges(q
))
367 * First try one-hit cache.
369 if (q
->last_merge
&& blk_attempt_req_merge(q
, q
->last_merge
, rq
))
372 if (blk_queue_noxmerges(q
))
377 * See if our hash lookup can find a potential backmerge.
380 __rq
= elv_rqhash_find(q
, blk_rq_pos(rq
));
381 if (!__rq
|| !blk_attempt_req_merge(q
, __rq
, rq
))
384 /* The merged request could be merged with others, try again */
392 void elv_merged_request(struct request_queue
*q
, struct request
*rq
,
395 struct elevator_queue
*e
= q
->elevator
;
397 if (e
->type
->ops
.request_merged
)
398 e
->type
->ops
.request_merged(q
, rq
, type
);
400 if (type
== ELEVATOR_BACK_MERGE
)
401 elv_rqhash_reposition(q
, rq
);
406 void elv_merge_requests(struct request_queue
*q
, struct request
*rq
,
407 struct request
*next
)
409 struct elevator_queue
*e
= q
->elevator
;
411 if (e
->type
->ops
.requests_merged
)
412 e
->type
->ops
.requests_merged(q
, rq
, next
);
414 elv_rqhash_reposition(q
, rq
);
418 struct request
*elv_latter_request(struct request_queue
*q
, struct request
*rq
)
420 struct elevator_queue
*e
= q
->elevator
;
422 if (e
->type
->ops
.next_request
)
423 return e
->type
->ops
.next_request(q
, rq
);
428 struct request
*elv_former_request(struct request_queue
*q
, struct request
*rq
)
430 struct elevator_queue
*e
= q
->elevator
;
432 if (e
->type
->ops
.former_request
)
433 return e
->type
->ops
.former_request(q
, rq
);
438 #define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
441 elv_attr_show(struct kobject
*kobj
, struct attribute
*attr
, char *page
)
443 struct elv_fs_entry
*entry
= to_elv(attr
);
444 struct elevator_queue
*e
;
450 e
= container_of(kobj
, struct elevator_queue
, kobj
);
451 mutex_lock(&e
->sysfs_lock
);
452 error
= e
->type
? entry
->show(e
, page
) : -ENOENT
;
453 mutex_unlock(&e
->sysfs_lock
);
458 elv_attr_store(struct kobject
*kobj
, struct attribute
*attr
,
459 const char *page
, size_t length
)
461 struct elv_fs_entry
*entry
= to_elv(attr
);
462 struct elevator_queue
*e
;
468 e
= container_of(kobj
, struct elevator_queue
, kobj
);
469 mutex_lock(&e
->sysfs_lock
);
470 error
= e
->type
? entry
->store(e
, page
, length
) : -ENOENT
;
471 mutex_unlock(&e
->sysfs_lock
);
475 static const struct sysfs_ops elv_sysfs_ops
= {
476 .show
= elv_attr_show
,
477 .store
= elv_attr_store
,
480 static struct kobj_type elv_ktype
= {
481 .sysfs_ops
= &elv_sysfs_ops
,
482 .release
= elevator_release
,
485 int elv_register_queue(struct request_queue
*q
, bool uevent
)
487 struct elevator_queue
*e
= q
->elevator
;
490 lockdep_assert_held(&q
->sysfs_lock
);
492 error
= kobject_add(&e
->kobj
, &q
->kobj
, "%s", "iosched");
494 struct elv_fs_entry
*attr
= e
->type
->elevator_attrs
;
496 while (attr
->attr
.name
) {
497 if (sysfs_create_file(&e
->kobj
, &attr
->attr
))
503 kobject_uevent(&e
->kobj
, KOBJ_ADD
);
510 void elv_unregister_queue(struct request_queue
*q
)
512 lockdep_assert_held(&q
->sysfs_lock
);
515 struct elevator_queue
*e
= q
->elevator
;
517 kobject_uevent(&e
->kobj
, KOBJ_REMOVE
);
518 kobject_del(&e
->kobj
);
521 /* Re-enable throttling in case elevator disabled it */
522 wbt_enable_default(q
);
526 int elv_register(struct elevator_type
*e
)
528 /* create icq_cache if requested */
530 if (WARN_ON(e
->icq_size
< sizeof(struct io_cq
)) ||
531 WARN_ON(e
->icq_align
< __alignof__(struct io_cq
)))
534 snprintf(e
->icq_cache_name
, sizeof(e
->icq_cache_name
),
535 "%s_io_cq", e
->elevator_name
);
536 e
->icq_cache
= kmem_cache_create(e
->icq_cache_name
, e
->icq_size
,
537 e
->icq_align
, 0, NULL
);
542 /* register, don't allow duplicate names */
543 spin_lock(&elv_list_lock
);
544 if (elevator_find(e
->elevator_name
, 0)) {
545 spin_unlock(&elv_list_lock
);
546 kmem_cache_destroy(e
->icq_cache
);
549 list_add_tail(&e
->list
, &elv_list
);
550 spin_unlock(&elv_list_lock
);
552 printk(KERN_INFO
"io scheduler %s registered\n", e
->elevator_name
);
556 EXPORT_SYMBOL_GPL(elv_register
);
558 void elv_unregister(struct elevator_type
*e
)
561 spin_lock(&elv_list_lock
);
562 list_del_init(&e
->list
);
563 spin_unlock(&elv_list_lock
);
566 * Destroy icq_cache if it exists. icq's are RCU managed. Make
567 * sure all RCU operations are complete before proceeding.
571 kmem_cache_destroy(e
->icq_cache
);
575 EXPORT_SYMBOL_GPL(elv_unregister
);
577 int elevator_switch_mq(struct request_queue
*q
,
578 struct elevator_type
*new_e
)
582 lockdep_assert_held(&q
->sysfs_lock
);
585 if (q
->elevator
->registered
)
586 elv_unregister_queue(q
);
589 elevator_exit(q
, q
->elevator
);
592 ret
= blk_mq_init_sched(q
, new_e
);
597 ret
= elv_register_queue(q
, true);
599 elevator_exit(q
, q
->elevator
);
605 blk_add_trace_msg(q
, "elv switch: %s", new_e
->elevator_name
);
607 blk_add_trace_msg(q
, "elv switch: none");
613 static inline bool elv_support_iosched(struct request_queue
*q
)
615 if (!queue_is_mq(q
) ||
616 (q
->tag_set
&& (q
->tag_set
->flags
& BLK_MQ_F_NO_SCHED
)))
622 * For single queue devices, default to using mq-deadline. If we have multiple
623 * queues or mq-deadline is not available, default to "none".
625 static struct elevator_type
*elevator_get_default(struct request_queue
*q
)
627 if (q
->nr_hw_queues
!= 1)
630 return elevator_get(q
, "mq-deadline", false);
634 * Get the first elevator providing the features required by the request queue.
635 * Default to "none" if no matching elevator is found.
637 static struct elevator_type
*elevator_get_by_features(struct request_queue
*q
)
639 struct elevator_type
*e
, *found
= NULL
;
641 spin_lock(&elv_list_lock
);
643 list_for_each_entry(e
, &elv_list
, list
) {
644 if (elv_support_features(e
->elevator_features
,
645 q
->required_elevator_features
)) {
651 if (found
&& !try_module_get(found
->elevator_owner
))
654 spin_unlock(&elv_list_lock
);
659 * For a device queue that has no required features, use the default elevator
660 * settings. Otherwise, use the first elevator available matching the required
661 * features. If no suitable elevator is find or if the chosen elevator
662 * initialization fails, fall back to the "none" elevator (no elevator).
664 void elevator_init_mq(struct request_queue
*q
)
666 struct elevator_type
*e
;
669 if (!elv_support_iosched(q
))
672 WARN_ON_ONCE(blk_queue_registered(q
));
674 if (unlikely(q
->elevator
))
677 if (!q
->required_elevator_features
)
678 e
= elevator_get_default(q
);
680 e
= elevator_get_by_features(q
);
684 blk_mq_freeze_queue(q
);
685 blk_mq_quiesce_queue(q
);
687 err
= blk_mq_init_sched(q
, e
);
689 blk_mq_unquiesce_queue(q
);
690 blk_mq_unfreeze_queue(q
);
693 pr_warn("\"%s\" elevator initialization failed, "
694 "falling back to \"none\"\n", e
->elevator_name
);
701 * switch to new_e io scheduler. be careful not to introduce deadlocks -
702 * we don't free the old io scheduler, before we have allocated what we
703 * need for the new one. this way we have a chance of going back to the old
704 * one, if the new one fails init for some reason.
706 static int elevator_switch(struct request_queue
*q
, struct elevator_type
*new_e
)
710 lockdep_assert_held(&q
->sysfs_lock
);
712 blk_mq_freeze_queue(q
);
713 blk_mq_quiesce_queue(q
);
715 err
= elevator_switch_mq(q
, new_e
);
717 blk_mq_unquiesce_queue(q
);
718 blk_mq_unfreeze_queue(q
);
724 * Switch this queue to the given IO scheduler.
726 static int __elevator_change(struct request_queue
*q
, const char *name
)
728 char elevator_name
[ELV_NAME_MAX
];
729 struct elevator_type
*e
;
731 /* Make sure queue is not in the middle of being removed */
732 if (!blk_queue_registered(q
))
736 * Special case for mq, turn off scheduling
738 if (!strncmp(name
, "none", 4)) {
741 return elevator_switch(q
, NULL
);
744 strlcpy(elevator_name
, name
, sizeof(elevator_name
));
745 e
= elevator_get(q
, strstrip(elevator_name
), true);
750 elevator_match(q
->elevator
->type
, elevator_name
, 0)) {
755 return elevator_switch(q
, e
);
758 ssize_t
elv_iosched_store(struct request_queue
*q
, const char *name
,
763 if (!elv_support_iosched(q
))
766 ret
= __elevator_change(q
, name
);
773 ssize_t
elv_iosched_show(struct request_queue
*q
, char *name
)
775 struct elevator_queue
*e
= q
->elevator
;
776 struct elevator_type
*elv
= NULL
;
777 struct elevator_type
*__e
;
781 return sprintf(name
, "none\n");
784 len
+= sprintf(name
+len
, "[none] ");
788 spin_lock(&elv_list_lock
);
789 list_for_each_entry(__e
, &elv_list
, list
) {
790 if (elv
&& elevator_match(elv
, __e
->elevator_name
, 0)) {
791 len
+= sprintf(name
+len
, "[%s] ", elv
->elevator_name
);
794 if (elv_support_iosched(q
) &&
795 elevator_match(__e
, __e
->elevator_name
,
796 q
->required_elevator_features
))
797 len
+= sprintf(name
+len
, "%s ", __e
->elevator_name
);
799 spin_unlock(&elv_list_lock
);
802 len
+= sprintf(name
+len
, "none");
804 len
+= sprintf(len
+name
, "\n");
808 struct request
*elv_rb_former_request(struct request_queue
*q
,
811 struct rb_node
*rbprev
= rb_prev(&rq
->rb_node
);
814 return rb_entry_rq(rbprev
);
818 EXPORT_SYMBOL(elv_rb_former_request
);
820 struct request
*elv_rb_latter_request(struct request_queue
*q
,
823 struct rb_node
*rbnext
= rb_next(&rq
->rb_node
);
826 return rb_entry_rq(rbnext
);
830 EXPORT_SYMBOL(elv_rb_latter_request
);
832 static int __init
elevator_setup(char *str
)
834 pr_warn("Kernel parameter elevator= does not have any effect anymore.\n"
835 "Please use sysfs to set IO scheduler for individual devices.\n");
839 __setup("elevator=", elevator_setup
);