1 // SPDX-License-Identifier: GPL-2.0
3  *  Block device elevator/IO-scheduler.
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
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
43 #include "blk-mq-sched.h"
44 #include "blk-pm.h"
45 #include "blk-wbt.h"
46 #include "blk-cgroup.h"
62 	struct request_queue *q = rq->q;  in elv_iosched_allow_bio_merge()
63 	struct elevator_queue *e = q->elevator;  in elv_iosched_allow_bio_merge()  local
65 	if (e->type->ops.allow_merge)  in elv_iosched_allow_bio_merge()
66 		return e->type->ops.allow_merge(q, rq, bio);  in elv_iosched_allow_bio_merge()
87 		const struct elevator_type *e)  in elv_support_features()  argument
89 	return (q->required_elevator_features & e->elevator_features) ==  in elv_support_features()
90 		q->required_elevator_features;  in elv_support_features()
94  * elevator_match - Check whether @e's name or alias matches @name
95  * @e: Scheduler to test
98  * Return true if the elevator @e's name or alias matches @name.
100 static bool elevator_match(const struct elevator_type *e, const char *name)  in elevator_match()  argument
102 	return !strcmp(e->elevator_name, name) ||  in elevator_match()
103 		(e->elevator_alias && !strcmp(e->elevator_alias, name));  in elevator_match()
108 	struct elevator_type *e;  in __elevator_find()  local
110 	list_for_each_entry(e, &elv_list, list)  in __elevator_find()
111 		if (elevator_match(e, name))  in __elevator_find()
112 			return e;  in __elevator_find()
119 	struct elevator_type *e;  in elevator_find_get()  local
122 	e = __elevator_find(name);  in elevator_find_get()
123 	if (e && (!elv_support_features(q, e) || !elevator_tryget(e)))  in elevator_find_get()
124 		e = NULL;  in elevator_find_get()
126 	return e;  in elevator_find_get()
132 				  struct elevator_type *e)  in elevator_alloc()  argument
136 	eq = kzalloc_node(sizeof(*eq), GFP_KERNEL, q->node);  in elevator_alloc()
140 	__elevator_get(e);  in elevator_alloc()
141 	eq->type = e;  in elevator_alloc()
142 	kobject_init(&eq->kobj, &elv_ktype);  in elevator_alloc()
143 	mutex_init(&eq->sysfs_lock);  in elevator_alloc()
144 	hash_init(eq->hash);  in elevator_alloc()
152 	struct elevator_queue *e;  in elevator_release()  local
154 	e = container_of(kobj, struct elevator_queue, kobj);  in elevator_release()
155 	elevator_put(e->type);  in elevator_release()
156 	kfree(e);  in elevator_release()
161 	struct elevator_queue *e = q->elevator;  in elevator_exit()  local
166 	mutex_lock(&e->sysfs_lock);  in elevator_exit()
167 	blk_mq_exit_sched(q, e);  in elevator_exit()
168 	mutex_unlock(&e->sysfs_lock);  in elevator_exit()
170 	kobject_put(&e->kobj);  in elevator_exit()
175 	hash_del(&rq->hash);  in __elv_rqhash_del()
176 	rq->rq_flags &= ~RQF_HASHED;  in __elv_rqhash_del()
188 	struct elevator_queue *e = q->elevator;  in elv_rqhash_add()  local
191 	hash_add(e->hash, &rq->hash, rq_hash_key(rq));  in elv_rqhash_add()
192 	rq->rq_flags |= RQF_HASHED;  in elv_rqhash_add()
204 	struct elevator_queue *e = q->elevator;  in elv_rqhash_find()  local
208 	hash_for_each_possible_safe(e->hash, rq, next, hash, offset) {  in elv_rqhash_find()
224  * RB-tree support functions for inserting/lookup/removal of requests
229 	struct rb_node **p = &root->rb_node;  in elv_rb_add()
238 			p = &(*p)->rb_left;  in elv_rb_add()
240 			p = &(*p)->rb_right;  in elv_rb_add()
243 	rb_link_node(&rq->rb_node, parent, p);  in elv_rb_add()
244 	rb_insert_color(&rq->rb_node, root);  in elv_rb_add()
250 	BUG_ON(RB_EMPTY_NODE(&rq->rb_node));  in elv_rb_del()
251 	rb_erase(&rq->rb_node, root);  in elv_rb_del()
252 	RB_CLEAR_NODE(&rq->rb_node);  in elv_rb_del()
258 	struct rb_node *n = root->rb_node;  in elv_rb_find()
265 			n = n->rb_left;  in elv_rb_find()
267 			n = n->rb_right;  in elv_rb_find()
279 	struct elevator_queue *e = q->elevator;  in elv_merge()  local
285 	 * 	noxmerges: Only simple one-hit cache try  in elv_merge()
292 	 * First try one-hit cache.  in elv_merge()
294 	if (q->last_merge && elv_bio_merge_ok(q->last_merge, bio)) {  in elv_merge()
295 		enum elv_merge ret = blk_try_merge(q->last_merge, bio);  in elv_merge()
298 			*req = q->last_merge;  in elv_merge()
309 	__rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);  in elv_merge()
318 	if (e->type->ops.request_merge)  in elv_merge()
319 		return e->type->ops.request_merge(q, req, bio);  in elv_merge()
342 	 * First try one-hit cache.  in elv_attempt_insert_merge()
344 	if (q->last_merge && blk_attempt_req_merge(q, q->last_merge, rq)) {  in elv_attempt_insert_merge()
345 		list_add(&rq->queuelist, free);  in elv_attempt_insert_merge()
361 		list_add(&rq->queuelist, free);  in elv_attempt_insert_merge()
373 	struct elevator_queue *e = q->elevator;  in elv_merged_request()  local
375 	if (e->type->ops.request_merged)  in elv_merged_request()
376 		e->type->ops.request_merged(q, rq, type);  in elv_merged_request()
381 	q->last_merge = rq;  in elv_merged_request()
387 	struct elevator_queue *e = q->elevator;  in elv_merge_requests()  local
389 	if (e->type->ops.requests_merged)  in elv_merge_requests()
390 		e->type->ops.requests_merged(q, rq, next);  in elv_merge_requests()
393 	q->last_merge = rq;  in elv_merge_requests()
398 	struct elevator_queue *e = q->elevator;  in elv_latter_request()  local
400 	if (e->type->ops.next_request)  in elv_latter_request()
401 		return e->type->ops.next_request(q, rq);  in elv_latter_request()
408 	struct elevator_queue *e = q->elevator;  in elv_former_request()  local
410 	if (e->type->ops.former_request)  in elv_former_request()
411 		return e->type->ops.former_request(q, rq);  in elv_former_request()
422 	struct elevator_queue *e;  in elv_attr_show()  local
425 	if (!entry->show)  in elv_attr_show()
426 		return -EIO;  in elv_attr_show()
428 	e = container_of(kobj, struct elevator_queue, kobj);  in elv_attr_show()
429 	mutex_lock(&e->sysfs_lock);  in elv_attr_show()
430 	error = e->type ? entry->show(e, page) : -ENOENT;  in elv_attr_show()
431 	mutex_unlock(&e->sysfs_lock);  in elv_attr_show()
440 	struct elevator_queue *e;  in elv_attr_store()  local
443 	if (!entry->store)  in elv_attr_store()
444 		return -EIO;  in elv_attr_store()
446 	e = container_of(kobj, struct elevator_queue, kobj);  in elv_attr_store()
447 	mutex_lock(&e->sysfs_lock);  in elv_attr_store()
448 	error = e->type ? entry->store(e, page, length) : -ENOENT;  in elv_attr_store()
449 	mutex_unlock(&e->sysfs_lock);  in elv_attr_store()
465 	struct elevator_queue *e = q->elevator;  in elv_register_queue()  local
468 	lockdep_assert_held(&q->sysfs_lock);  in elv_register_queue()
470 	error = kobject_add(&e->kobj, &q->disk->queue_kobj, "iosched");  in elv_register_queue()
472 		struct elv_fs_entry *attr = e->type->elevator_attrs;  in elv_register_queue()
474 			while (attr->attr.name) {  in elv_register_queue()
475 				if (sysfs_create_file(&e->kobj, &attr->attr))  in elv_register_queue()
481 			kobject_uevent(&e->kobj, KOBJ_ADD);  in elv_register_queue()
483 		set_bit(ELEVATOR_FLAG_REGISTERED, &e->flags);  in elv_register_queue()
490 	struct elevator_queue *e = q->elevator;  in elv_unregister_queue()  local
492 	lockdep_assert_held(&q->sysfs_lock);  in elv_unregister_queue()
494 	if (e && test_and_clear_bit(ELEVATOR_FLAG_REGISTERED, &e->flags)) {  in elv_unregister_queue()
495 		kobject_uevent(&e->kobj, KOBJ_REMOVE);  in elv_unregister_queue()
496 		kobject_del(&e->kobj);  in elv_unregister_queue()
500 int elv_register(struct elevator_type *e)  in elv_register()  argument
503 	if (WARN_ON_ONCE(!e->ops.finish_request))  in elv_register()
504 		return -EINVAL;  in elv_register()
506 	if (WARN_ON_ONCE(!e->ops.insert_requests || !e->ops.dispatch_request))  in elv_register()
507 		return -EINVAL;  in elv_register()
510 	if (e->icq_size) {  in elv_register()
511 		if (WARN_ON(e->icq_size < sizeof(struct io_cq)) ||  in elv_register()
512 		    WARN_ON(e->icq_align < __alignof__(struct io_cq)))  in elv_register()
513 			return -EINVAL;  in elv_register()
515 		snprintf(e->icq_cache_name, sizeof(e->icq_cache_name),  in elv_register()
516 			 "%s_io_cq", e->elevator_name);  in elv_register()
517 		e->icq_cache = kmem_cache_create(e->icq_cache_name, e->icq_size,  in elv_register()
518 						 e->icq_align, 0, NULL);  in elv_register()
519 		if (!e->icq_cache)  in elv_register()
520 			return -ENOMEM;  in elv_register()
525 	if (__elevator_find(e->elevator_name)) {  in elv_register()
527 		kmem_cache_destroy(e->icq_cache);  in elv_register()
528 		return -EBUSY;  in elv_register()
530 	list_add_tail(&e->list, &elv_list);  in elv_register()
533 	printk(KERN_INFO "io scheduler %s registered\n", e->elevator_name);  in elv_register()
539 void elv_unregister(struct elevator_type *e)  in elv_unregister()  argument
543 	list_del_init(&e->list);  in elv_unregister()
550 	if (e->icq_cache) {  in elv_unregister()
552 		kmem_cache_destroy(e->icq_cache);  in elv_unregister()
553 		e->icq_cache = NULL;  in elv_unregister()
561 	    (q->tag_set->flags & BLK_MQ_F_NO_SCHED))  in elv_support_iosched()
567  * For single queue devices, default to using mq-deadline. If we have multiple
568  * queues or mq-deadline is not available, default to "none".
572 	if (q->tag_set->flags & BLK_MQ_F_NO_SCHED_BY_DEFAULT)  in elevator_get_default()
575 	if (q->nr_hw_queues != 1 &&  in elevator_get_default()
576 	    !blk_mq_is_shared_tags(q->tag_set->flags))  in elevator_get_default()
579 	return elevator_find_get(q, "mq-deadline");  in elevator_get_default()
588 	struct elevator_type *e, *found = NULL;  in elevator_get_by_features()  local
592 	list_for_each_entry(e, &elv_list, list) {  in elevator_get_by_features()
593 		if (elv_support_features(q, e)) {  in elevator_get_by_features()
594 			found = e;  in elevator_get_by_features()
614 	struct elevator_type *e;  in elevator_init_mq()  local
622 	if (unlikely(q->elevator))  in elevator_init_mq()
625 	if (!q->required_elevator_features)  in elevator_init_mq()
626 		e = elevator_get_default(q);  in elevator_init_mq()
628 		e = elevator_get_by_features(q);  in elevator_init_mq()
629 	if (!e)  in elevator_init_mq()
642 	err = blk_mq_init_sched(q, e);  in elevator_init_mq()
648 			"falling back to \"none\"\n", e->elevator_name);  in elevator_init_mq()
651 	elevator_put(e);  in elevator_init_mq()
664 	lockdep_assert_held(&q->sysfs_lock);  in elevator_switch()
669 	if (q->elevator) {  in elevator_switch()
683 	blk_add_trace_msg(q, "elv switch: %s", new_e->elevator_name);  in elevator_switch()
691 			new_e->elevator_name);  in elevator_switch()
699 	lockdep_assert_held(&q->sysfs_lock);  in elevator_disable()
707 	q->elevator = NULL;  in elevator_disable()
708 	q->nr_requests = q->tag_set->queue_depth;  in elevator_disable()
720 	struct elevator_type *e;  in elevator_change()  local
725 		return -ENOENT;  in elevator_change()
728 		if (q->elevator)  in elevator_change()
733 	if (q->elevator && elevator_match(q->elevator->type, elevator_name))  in elevator_change()
736 	e = elevator_find_get(q, elevator_name);  in elevator_change()
737 	if (!e) {  in elevator_change()
738 		request_module("%s-iosched", elevator_name);  in elevator_change()
739 		e = elevator_find_get(q, elevator_name);  in elevator_change()
740 		if (!e)  in elevator_change()
741 			return -EINVAL;  in elevator_change()
743 	ret = elevator_switch(q, e);  in elevator_change()
744 	elevator_put(e);  in elevator_change()
766 	struct elevator_queue *eq = q->elevator;  in elv_iosched_show()
767 	struct elevator_type *cur = NULL, *e;  in elv_iosched_show()  local
773 	if (!q->elevator) {  in elv_iosched_show()
777 		cur = eq->type;  in elv_iosched_show()
781 	list_for_each_entry(e, &elv_list, list) {  in elv_iosched_show()
782 		if (e == cur)  in elv_iosched_show()
783 			len += sprintf(name+len, "[%s] ", e->elevator_name);  in elv_iosched_show()
784 		else if (elv_support_features(q, e))  in elv_iosched_show()
785 			len += sprintf(name+len, "%s ", e->elevator_name);  in elv_iosched_show()
796 	struct rb_node *rbprev = rb_prev(&rq->rb_node);  in elv_rb_former_request()
808 	struct rb_node *rbnext = rb_next(&rq->rb_node);  in elv_rb_latter_request()