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
)) {
339 return ELEVATOR_BACK_MERGE
;
342 if (e
->type
->ops
.request_merge
)
343 return e
->type
->ops
.request_merge(q
, req
, bio
);
345 return ELEVATOR_NO_MERGE
;
349 * Attempt to do an insertion back merge. Only check for the case where
350 * we can append 'rq' to an existing request, so we can throw 'rq' away
353 * Returns true if we merged, false otherwise. 'free' will contain all
354 * requests that need to be freed.
356 bool elv_attempt_insert_merge(struct request_queue
*q
, struct request
*rq
,
357 struct list_head
*free
)
359 struct request
*__rq
;
362 if (blk_queue_nomerges(q
))
366 * First try one-hit cache.
368 if (q
->last_merge
&& blk_attempt_req_merge(q
, q
->last_merge
, rq
)) {
369 list_add(&rq
->queuelist
, free
);
373 if (blk_queue_noxmerges(q
))
378 * See if our hash lookup can find a potential backmerge.
381 __rq
= elv_rqhash_find(q
, blk_rq_pos(rq
));
382 if (!__rq
|| !blk_attempt_req_merge(q
, __rq
, rq
))
385 list_add(&rq
->queuelist
, free
);
386 /* The merged request could be merged with others, try again */
394 void elv_merged_request(struct request_queue
*q
, struct request
*rq
,
397 struct elevator_queue
*e
= q
->elevator
;
399 if (e
->type
->ops
.request_merged
)
400 e
->type
->ops
.request_merged(q
, rq
, type
);
402 if (type
== ELEVATOR_BACK_MERGE
)
403 elv_rqhash_reposition(q
, rq
);
408 void elv_merge_requests(struct request_queue
*q
, struct request
*rq
,
409 struct request
*next
)
411 struct elevator_queue
*e
= q
->elevator
;
413 if (e
->type
->ops
.requests_merged
)
414 e
->type
->ops
.requests_merged(q
, rq
, next
);
416 elv_rqhash_reposition(q
, rq
);
420 struct request
*elv_latter_request(struct request_queue
*q
, struct request
*rq
)
422 struct elevator_queue
*e
= q
->elevator
;
424 if (e
->type
->ops
.next_request
)
425 return e
->type
->ops
.next_request(q
, rq
);
430 struct request
*elv_former_request(struct request_queue
*q
, struct request
*rq
)
432 struct elevator_queue
*e
= q
->elevator
;
434 if (e
->type
->ops
.former_request
)
435 return e
->type
->ops
.former_request(q
, rq
);
440 #define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
443 elv_attr_show(struct kobject
*kobj
, struct attribute
*attr
, char *page
)
445 struct elv_fs_entry
*entry
= to_elv(attr
);
446 struct elevator_queue
*e
;
452 e
= container_of(kobj
, struct elevator_queue
, kobj
);
453 mutex_lock(&e
->sysfs_lock
);
454 error
= e
->type
? entry
->show(e
, page
) : -ENOENT
;
455 mutex_unlock(&e
->sysfs_lock
);
460 elv_attr_store(struct kobject
*kobj
, struct attribute
*attr
,
461 const char *page
, size_t length
)
463 struct elv_fs_entry
*entry
= to_elv(attr
);
464 struct elevator_queue
*e
;
470 e
= container_of(kobj
, struct elevator_queue
, kobj
);
471 mutex_lock(&e
->sysfs_lock
);
472 error
= e
->type
? entry
->store(e
, page
, length
) : -ENOENT
;
473 mutex_unlock(&e
->sysfs_lock
);
477 static const struct sysfs_ops elv_sysfs_ops
= {
478 .show
= elv_attr_show
,
479 .store
= elv_attr_store
,
482 static struct kobj_type elv_ktype
= {
483 .sysfs_ops
= &elv_sysfs_ops
,
484 .release
= elevator_release
,
487 int elv_register_queue(struct request_queue
*q
, bool uevent
)
489 struct elevator_queue
*e
= q
->elevator
;
492 lockdep_assert_held(&q
->sysfs_lock
);
494 error
= kobject_add(&e
->kobj
, &q
->kobj
, "%s", "iosched");
496 struct elv_fs_entry
*attr
= e
->type
->elevator_attrs
;
498 while (attr
->attr
.name
) {
499 if (sysfs_create_file(&e
->kobj
, &attr
->attr
))
505 kobject_uevent(&e
->kobj
, KOBJ_ADD
);
512 void elv_unregister_queue(struct request_queue
*q
)
514 lockdep_assert_held(&q
->sysfs_lock
);
517 struct elevator_queue
*e
= q
->elevator
;
519 kobject_uevent(&e
->kobj
, KOBJ_REMOVE
);
520 kobject_del(&e
->kobj
);
523 /* Re-enable throttling in case elevator disabled it */
524 wbt_enable_default(q
);
528 int elv_register(struct elevator_type
*e
)
530 /* insert_requests and dispatch_request are mandatory */
531 if (WARN_ON_ONCE(!e
->ops
.insert_requests
|| !e
->ops
.dispatch_request
))
534 /* create icq_cache if requested */
536 if (WARN_ON(e
->icq_size
< sizeof(struct io_cq
)) ||
537 WARN_ON(e
->icq_align
< __alignof__(struct io_cq
)))
540 snprintf(e
->icq_cache_name
, sizeof(e
->icq_cache_name
),
541 "%s_io_cq", e
->elevator_name
);
542 e
->icq_cache
= kmem_cache_create(e
->icq_cache_name
, e
->icq_size
,
543 e
->icq_align
, 0, NULL
);
548 /* register, don't allow duplicate names */
549 spin_lock(&elv_list_lock
);
550 if (elevator_find(e
->elevator_name
, 0)) {
551 spin_unlock(&elv_list_lock
);
552 kmem_cache_destroy(e
->icq_cache
);
555 list_add_tail(&e
->list
, &elv_list
);
556 spin_unlock(&elv_list_lock
);
558 printk(KERN_INFO
"io scheduler %s registered\n", e
->elevator_name
);
562 EXPORT_SYMBOL_GPL(elv_register
);
564 void elv_unregister(struct elevator_type
*e
)
567 spin_lock(&elv_list_lock
);
568 list_del_init(&e
->list
);
569 spin_unlock(&elv_list_lock
);
572 * Destroy icq_cache if it exists. icq's are RCU managed. Make
573 * sure all RCU operations are complete before proceeding.
577 kmem_cache_destroy(e
->icq_cache
);
581 EXPORT_SYMBOL_GPL(elv_unregister
);
583 int elevator_switch_mq(struct request_queue
*q
,
584 struct elevator_type
*new_e
)
588 lockdep_assert_held(&q
->sysfs_lock
);
591 if (q
->elevator
->registered
)
592 elv_unregister_queue(q
);
595 elevator_exit(q
, q
->elevator
);
598 ret
= blk_mq_init_sched(q
, new_e
);
603 ret
= elv_register_queue(q
, true);
605 elevator_exit(q
, q
->elevator
);
611 blk_add_trace_msg(q
, "elv switch: %s", new_e
->elevator_name
);
613 blk_add_trace_msg(q
, "elv switch: none");
619 static inline bool elv_support_iosched(struct request_queue
*q
)
621 if (!queue_is_mq(q
) ||
622 (q
->tag_set
&& (q
->tag_set
->flags
& BLK_MQ_F_NO_SCHED
)))
628 * For single queue devices, default to using mq-deadline. If we have multiple
629 * queues or mq-deadline is not available, default to "none".
631 static struct elevator_type
*elevator_get_default(struct request_queue
*q
)
633 if (q
->nr_hw_queues
!= 1 &&
634 !blk_mq_is_sbitmap_shared(q
->tag_set
->flags
))
637 return elevator_get(q
, "mq-deadline", false);
641 * Get the first elevator providing the features required by the request queue.
642 * Default to "none" if no matching elevator is found.
644 static struct elevator_type
*elevator_get_by_features(struct request_queue
*q
)
646 struct elevator_type
*e
, *found
= NULL
;
648 spin_lock(&elv_list_lock
);
650 list_for_each_entry(e
, &elv_list
, list
) {
651 if (elv_support_features(e
->elevator_features
,
652 q
->required_elevator_features
)) {
658 if (found
&& !try_module_get(found
->elevator_owner
))
661 spin_unlock(&elv_list_lock
);
666 * For a device queue that has no required features, use the default elevator
667 * settings. Otherwise, use the first elevator available matching the required
668 * features. If no suitable elevator is find or if the chosen elevator
669 * initialization fails, fall back to the "none" elevator (no elevator).
671 void elevator_init_mq(struct request_queue
*q
)
673 struct elevator_type
*e
;
676 if (!elv_support_iosched(q
))
679 WARN_ON_ONCE(blk_queue_registered(q
));
681 if (unlikely(q
->elevator
))
684 if (!q
->required_elevator_features
)
685 e
= elevator_get_default(q
);
687 e
= elevator_get_by_features(q
);
691 blk_mq_freeze_queue(q
);
692 blk_mq_quiesce_queue(q
);
694 err
= blk_mq_init_sched(q
, e
);
696 blk_mq_unquiesce_queue(q
);
697 blk_mq_unfreeze_queue(q
);
700 pr_warn("\"%s\" elevator initialization failed, "
701 "falling back to \"none\"\n", e
->elevator_name
);
705 EXPORT_SYMBOL_GPL(elevator_init_mq
); /* only for dm-rq */
708 * switch to new_e io scheduler. be careful not to introduce deadlocks -
709 * we don't free the old io scheduler, before we have allocated what we
710 * need for the new one. this way we have a chance of going back to the old
711 * one, if the new one fails init for some reason.
713 static int elevator_switch(struct request_queue
*q
, struct elevator_type
*new_e
)
717 lockdep_assert_held(&q
->sysfs_lock
);
719 blk_mq_freeze_queue(q
);
720 blk_mq_quiesce_queue(q
);
722 err
= elevator_switch_mq(q
, new_e
);
724 blk_mq_unquiesce_queue(q
);
725 blk_mq_unfreeze_queue(q
);
731 * Switch this queue to the given IO scheduler.
733 static int __elevator_change(struct request_queue
*q
, const char *name
)
735 char elevator_name
[ELV_NAME_MAX
];
736 struct elevator_type
*e
;
738 /* Make sure queue is not in the middle of being removed */
739 if (!blk_queue_registered(q
))
743 * Special case for mq, turn off scheduling
745 if (!strncmp(name
, "none", 4)) {
748 return elevator_switch(q
, NULL
);
751 strlcpy(elevator_name
, name
, sizeof(elevator_name
));
752 e
= elevator_get(q
, strstrip(elevator_name
), true);
757 elevator_match(q
->elevator
->type
, elevator_name
, 0)) {
762 return elevator_switch(q
, e
);
765 ssize_t
elv_iosched_store(struct request_queue
*q
, const char *name
,
770 if (!elv_support_iosched(q
))
773 ret
= __elevator_change(q
, name
);
780 ssize_t
elv_iosched_show(struct request_queue
*q
, char *name
)
782 struct elevator_queue
*e
= q
->elevator
;
783 struct elevator_type
*elv
= NULL
;
784 struct elevator_type
*__e
;
788 return sprintf(name
, "none\n");
791 len
+= sprintf(name
+len
, "[none] ");
795 spin_lock(&elv_list_lock
);
796 list_for_each_entry(__e
, &elv_list
, list
) {
797 if (elv
&& elevator_match(elv
, __e
->elevator_name
, 0)) {
798 len
+= sprintf(name
+len
, "[%s] ", elv
->elevator_name
);
801 if (elv_support_iosched(q
) &&
802 elevator_match(__e
, __e
->elevator_name
,
803 q
->required_elevator_features
))
804 len
+= sprintf(name
+len
, "%s ", __e
->elevator_name
);
806 spin_unlock(&elv_list_lock
);
809 len
+= sprintf(name
+len
, "none");
811 len
+= sprintf(len
+name
, "\n");
815 struct request
*elv_rb_former_request(struct request_queue
*q
,
818 struct rb_node
*rbprev
= rb_prev(&rq
->rb_node
);
821 return rb_entry_rq(rbprev
);
825 EXPORT_SYMBOL(elv_rb_former_request
);
827 struct request
*elv_rb_latter_request(struct request_queue
*q
,
830 struct rb_node
*rbnext
= rb_next(&rq
->rb_node
);
833 return rb_entry_rq(rbnext
);
837 EXPORT_SYMBOL(elv_rb_latter_request
);
839 static int __init
elevator_setup(char *str
)
841 pr_warn("Kernel parameter elevator= does not have any effect anymore.\n"
842 "Please use sysfs to set IO scheduler for individual devices.\n");
846 __setup("elevator=", elevator_setup
);