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/delay.h> 35#include <linux/blktrace_api.h> 36#include <linux/hash.h> 37#include <linux/uaccess.h> 38 39#include <trace/events/block.h> 40 41#include "blk.h" 42 43static DEFINE_SPINLOCK(elv_list_lock); 44static LIST_HEAD(elv_list); 45 46/* 47 * Merge hash stuff. 48 */ 49static const int elv_hash_shift = 6; 50#define ELV_HASH_BLOCK(sec) ((sec) >> 3) 51#define ELV_HASH_FN(sec) \ 52 (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift)) 53#define ELV_HASH_ENTRIES (1 << elv_hash_shift) 54#define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq)) 55 56/* 57 * Query io scheduler to see if the current process issuing bio may be 58 * merged with rq. 59 */ 60static int elv_iosched_allow_merge(struct request *rq, struct bio *bio) 61{ 62 struct request_queue *q = rq->q; 63 struct elevator_queue *e = q->elevator; 64 65 if (e->ops->elevator_allow_merge_fn) 66 return e->ops->elevator_allow_merge_fn(q, rq, bio); 67 68 return 1; 69} 70 71/* 72 * can we safely merge with this request? 73 */ 74int elv_rq_merge_ok(struct request *rq, struct bio *bio) 75{ 76 if (!rq_mergeable(rq)) 77 return 0; 78 79 /* 80 * Don't merge file system requests and discard requests 81 */ 82 if ((bio->bi_rw & REQ_DISCARD) != (rq->bio->bi_rw & REQ_DISCARD)) 83 return 0; 84 85 /* 86 * Don't merge discard requests and secure discard requests 87 */ 88 if ((bio->bi_rw & REQ_SECURE) != (rq->bio->bi_rw & REQ_SECURE)) 89 return 0; 90 91 /* 92 * different data direction or already started, don't merge 93 */ 94 if (bio_data_dir(bio) != rq_data_dir(rq)) 95 return 0; 96 97 /* 98 * must be same device and not a special request 99 */ 100 if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special) 101 return 0; 102 103 /* 104 * only merge integrity protected bio into ditto rq 105 */ 106 if (bio_integrity(bio) != blk_integrity_rq(rq)) 107 return 0; 108 109 if (!elv_iosched_allow_merge(rq, bio)) 110 return 0; 111 112 return 1; 113} 114EXPORT_SYMBOL(elv_rq_merge_ok); 115 116static inline int elv_try_merge(struct request *__rq, struct bio *bio) 117{ 118 int ret = ELEVATOR_NO_MERGE; 119 120 /* 121 * we can merge and sequence is ok, check if it's possible 122 */ 123 if (elv_rq_merge_ok(__rq, bio)) { 124 if (blk_rq_pos(__rq) + blk_rq_sectors(__rq) == bio->bi_sector) 125 ret = ELEVATOR_BACK_MERGE; 126 else if (blk_rq_pos(__rq) - bio_sectors(bio) == bio->bi_sector) 127 ret = ELEVATOR_FRONT_MERGE; 128 } 129 130 return ret; 131} 132 133static struct elevator_type *elevator_find(const char *name) 134{ 135 struct elevator_type *e; 136 137 list_for_each_entry(e, &elv_list, list) { 138 if (!strcmp(e->elevator_name, name)) 139 return e; 140 } 141 142 return NULL; 143} 144 145static void elevator_put(struct elevator_type *e) 146{ 147 module_put(e->elevator_owner); 148} 149 150static struct elevator_type *elevator_get(const char *name) 151{ 152 struct elevator_type *e; 153 154 spin_lock(&elv_list_lock); 155 156 e = elevator_find(name); 157 if (!e) { 158 char elv[ELV_NAME_MAX + strlen("-iosched")]; 159 160 spin_unlock(&elv_list_lock); 161 162 snprintf(elv, sizeof(elv), "%s-iosched", name); 163 164 request_module("%s", elv); 165 spin_lock(&elv_list_lock); 166 e = elevator_find(name); 167 } 168 169 if (e && !try_module_get(e->elevator_owner)) 170 e = NULL; 171 172 spin_unlock(&elv_list_lock); 173 174 return e; 175} 176 177static void *elevator_init_queue(struct request_queue *q, 178 struct elevator_queue *eq) 179{ 180 return eq->ops->elevator_init_fn(q); 181} 182 183static void elevator_attach(struct request_queue *q, struct elevator_queue *eq, 184 void *data) 185{ 186 q->elevator = eq; 187 eq->elevator_data = data; 188} 189 190static char chosen_elevator[16]; 191 192static int __init elevator_setup(char *str) 193{ 194 /* 195 * Be backwards-compatible with previous kernels, so users 196 * won't get the wrong elevator. 197 */ 198 strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1); 199 return 1; 200} 201 202__setup("elevator=", elevator_setup); 203 204static struct kobj_type elv_ktype; 205 206static struct elevator_queue *elevator_alloc(struct request_queue *q, 207 struct elevator_type *e) 208{ 209 struct elevator_queue *eq; 210 int i; 211 212 eq = kmalloc_node(sizeof(*eq), GFP_KERNEL | __GFP_ZERO, q->node); 213 if (unlikely(!eq)) 214 goto err; 215 216 eq->ops = &e->ops; 217 eq->elevator_type = e; 218 kobject_init(&eq->kobj, &elv_ktype); 219 mutex_init(&eq->sysfs_lock); 220 221 eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES, 222 GFP_KERNEL, q->node); 223 if (!eq->hash) 224 goto err; 225 226 for (i = 0; i < ELV_HASH_ENTRIES; i++) 227 INIT_HLIST_HEAD(&eq->hash[i]); 228 229 return eq; 230err: 231 kfree(eq); 232 elevator_put(e); 233 return NULL; 234} 235 236static void elevator_release(struct kobject *kobj) 237{ 238 struct elevator_queue *e; 239 240 e = container_of(kobj, struct elevator_queue, kobj); 241 elevator_put(e->elevator_type); 242 kfree(e->hash); 243 kfree(e); 244} 245 246int elevator_init(struct request_queue *q, char *name) 247{ 248 struct elevator_type *e = NULL; 249 struct elevator_queue *eq; 250 void *data; 251 252 if (unlikely(q->elevator)) 253 return 0; 254 255 INIT_LIST_HEAD(&q->queue_head); 256 q->last_merge = NULL; 257 q->end_sector = 0; 258 q->boundary_rq = NULL; 259 260 if (name) { 261 e = elevator_get(name); 262 if (!e) 263 return -EINVAL; 264 } 265 266 if (!e && *chosen_elevator) { 267 e = elevator_get(chosen_elevator); 268 if (!e) 269 printk(KERN_ERR "I/O scheduler %s not found\n", 270 chosen_elevator); 271 } 272 273 if (!e) { 274 e = elevator_get(CONFIG_DEFAULT_IOSCHED); 275 if (!e) { 276 printk(KERN_ERR 277 "Default I/O scheduler not found. " \ 278 "Using noop.\n"); 279 e = elevator_get("noop"); 280 } 281 } 282 283 eq = elevator_alloc(q, e); 284 if (!eq) 285 return -ENOMEM; 286 287 data = elevator_init_queue(q, eq); 288 if (!data) { 289 kobject_put(&eq->kobj); 290 return -ENOMEM; 291 } 292 293 elevator_attach(q, eq, data); 294 return 0; 295} 296EXPORT_SYMBOL(elevator_init); 297 298void elevator_exit(struct elevator_queue *e) 299{ 300 mutex_lock(&e->sysfs_lock); 301 if (e->ops->elevator_exit_fn) 302 e->ops->elevator_exit_fn(e); 303 e->ops = NULL; 304 mutex_unlock(&e->sysfs_lock); 305 306 kobject_put(&e->kobj); 307} 308EXPORT_SYMBOL(elevator_exit); 309 310static inline void __elv_rqhash_del(struct request *rq) 311{ 312 hlist_del_init(&rq->hash); 313} 314 315static void elv_rqhash_del(struct request_queue *q, struct request *rq) 316{ 317 if (ELV_ON_HASH(rq)) 318 __elv_rqhash_del(rq); 319} 320 321static void elv_rqhash_add(struct request_queue *q, struct request *rq) 322{ 323 struct elevator_queue *e = q->elevator; 324 325 BUG_ON(ELV_ON_HASH(rq)); 326 hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]); 327} 328 329static void elv_rqhash_reposition(struct request_queue *q, struct request *rq) 330{ 331 __elv_rqhash_del(rq); 332 elv_rqhash_add(q, rq); 333} 334 335static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset) 336{ 337 struct elevator_queue *e = q->elevator; 338 struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)]; 339 struct hlist_node *entry, *next; 340 struct request *rq; 341 342 hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) { 343 BUG_ON(!ELV_ON_HASH(rq)); 344 345 if (unlikely(!rq_mergeable(rq))) { 346 __elv_rqhash_del(rq); 347 continue; 348 } 349 350 if (rq_hash_key(rq) == offset) 351 return rq; 352 } 353 354 return NULL; 355} 356 357/* 358 * RB-tree support functions for inserting/lookup/removal of requests 359 * in a sorted RB tree. 360 */ 361struct request *elv_rb_add(struct rb_root *root, struct request *rq) 362{ 363 struct rb_node **p = &root->rb_node; 364 struct rb_node *parent = NULL; 365 struct request *__rq; 366 367 while (*p) { 368 parent = *p; 369 __rq = rb_entry(parent, struct request, rb_node); 370 371 if (blk_rq_pos(rq) < blk_rq_pos(__rq)) 372 p = &(*p)->rb_left; 373 else if (blk_rq_pos(rq) > blk_rq_pos(__rq)) 374 p = &(*p)->rb_right; 375 else 376 return __rq; 377 } 378 379 rb_link_node(&rq->rb_node, parent, p); 380 rb_insert_color(&rq->rb_node, root); 381 return NULL; 382} 383EXPORT_SYMBOL(elv_rb_add); 384 385void elv_rb_del(struct rb_root *root, struct request *rq) 386{ 387 BUG_ON(RB_EMPTY_NODE(&rq->rb_node)); 388 rb_erase(&rq->rb_node, root); 389 RB_CLEAR_NODE(&rq->rb_node); 390} 391EXPORT_SYMBOL(elv_rb_del); 392 393struct request *elv_rb_find(struct rb_root *root, sector_t sector) 394{ 395 struct rb_node *n = root->rb_node; 396 struct request *rq; 397 398 while (n) { 399 rq = rb_entry(n, struct request, rb_node); 400 401 if (sector < blk_rq_pos(rq)) 402 n = n->rb_left; 403 else if (sector > blk_rq_pos(rq)) 404 n = n->rb_right; 405 else 406 return rq; 407 } 408 409 return NULL; 410} 411EXPORT_SYMBOL(elv_rb_find); 412 413/* 414 * Insert rq into dispatch queue of q. Queue lock must be held on 415 * entry. rq is sort instead into the dispatch queue. To be used by 416 * specific elevators. 417 */ 418void elv_dispatch_sort(struct request_queue *q, struct request *rq) 419{ 420 sector_t boundary; 421 struct list_head *entry; 422 int stop_flags; 423 424 if (q->last_merge == rq) 425 q->last_merge = NULL; 426 427 elv_rqhash_del(q, rq); 428 429 q->nr_sorted--; 430 431 boundary = q->end_sector; 432 stop_flags = REQ_SOFTBARRIER | REQ_HARDBARRIER | REQ_STARTED; 433 list_for_each_prev(entry, &q->queue_head) { 434 struct request *pos = list_entry_rq(entry); 435 436 if ((rq->cmd_flags & REQ_DISCARD) != 437 (pos->cmd_flags & REQ_DISCARD)) 438 break; 439 if (rq_data_dir(rq) != rq_data_dir(pos)) 440 break; 441 if (pos->cmd_flags & stop_flags) 442 break; 443 if (blk_rq_pos(rq) >= boundary) { 444 if (blk_rq_pos(pos) < boundary) 445 continue; 446 } else { 447 if (blk_rq_pos(pos) >= boundary) 448 break; 449 } 450 if (blk_rq_pos(rq) >= blk_rq_pos(pos)) 451 break; 452 } 453 454 list_add(&rq->queuelist, entry); 455} 456EXPORT_SYMBOL(elv_dispatch_sort); 457 458/* 459 * Insert rq into dispatch queue of q. Queue lock must be held on 460 * entry. rq is added to the back of the dispatch queue. To be used by 461 * specific elevators. 462 */ 463void elv_dispatch_add_tail(struct request_queue *q, struct request *rq) 464{ 465 if (q->last_merge == rq) 466 q->last_merge = NULL; 467 468 elv_rqhash_del(q, rq); 469 470 q->nr_sorted--; 471 472 q->end_sector = rq_end_sector(rq); 473 q->boundary_rq = rq; 474 list_add_tail(&rq->queuelist, &q->queue_head); 475} 476EXPORT_SYMBOL(elv_dispatch_add_tail); 477 478int elv_merge(struct request_queue *q, struct request **req, struct bio *bio) 479{ 480 struct elevator_queue *e = q->elevator; 481 struct request *__rq; 482 int ret; 483 484 /* 485 * Levels of merges: 486 * nomerges: No merges at all attempted 487 * noxmerges: Only simple one-hit cache try 488 * merges: All merge tries attempted 489 */ 490 if (blk_queue_nomerges(q)) 491 return ELEVATOR_NO_MERGE; 492 493 /* 494 * First try one-hit cache. 495 */ 496 if (q->last_merge) { 497 ret = elv_try_merge(q->last_merge, bio); 498 if (ret != ELEVATOR_NO_MERGE) { 499 *req = q->last_merge; 500 return ret; 501 } 502 } 503 504 if (blk_queue_noxmerges(q)) 505 return ELEVATOR_NO_MERGE; 506 507 /* 508 * See if our hash lookup can find a potential backmerge. 509 */ 510 __rq = elv_rqhash_find(q, bio->bi_sector); 511 if (__rq && elv_rq_merge_ok(__rq, bio)) { 512 *req = __rq; 513 return ELEVATOR_BACK_MERGE; 514 } 515 516 if (e->ops->elevator_merge_fn) 517 return e->ops->elevator_merge_fn(q, req, bio); 518 519 return ELEVATOR_NO_MERGE; 520} 521 522void elv_merged_request(struct request_queue *q, struct request *rq, int type) 523{ 524 struct elevator_queue *e = q->elevator; 525 526 if (e->ops->elevator_merged_fn) 527 e->ops->elevator_merged_fn(q, rq, type); 528 529 if (type == ELEVATOR_BACK_MERGE) 530 elv_rqhash_reposition(q, rq); 531 532 q->last_merge = rq; 533} 534 535void elv_merge_requests(struct request_queue *q, struct request *rq, 536 struct request *next) 537{ 538 struct elevator_queue *e = q->elevator; 539 540 if (e->ops->elevator_merge_req_fn) 541 e->ops->elevator_merge_req_fn(q, rq, next); 542 543 elv_rqhash_reposition(q, rq); 544 elv_rqhash_del(q, next); 545 546 q->nr_sorted--; 547 q->last_merge = rq; 548} 549 550void elv_bio_merged(struct request_queue *q, struct request *rq, 551 struct bio *bio) 552{ 553 struct elevator_queue *e = q->elevator; 554 555 if (e->ops->elevator_bio_merged_fn) 556 e->ops->elevator_bio_merged_fn(q, rq, bio); 557} 558 559void elv_requeue_request(struct request_queue *q, struct request *rq) 560{ 561 /* 562 * it already went through dequeue, we need to decrement the 563 * in_flight count again 564 */ 565 if (blk_account_rq(rq)) { 566 q->in_flight[rq_is_sync(rq)]--; 567 if (rq->cmd_flags & REQ_SORTED) 568 elv_deactivate_rq(q, rq); 569 } 570 571 rq->cmd_flags &= ~REQ_STARTED; 572 573 elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE); 574} 575 576void elv_drain_elevator(struct request_queue *q) 577{ 578 static int printed; 579 while (q->elevator->ops->elevator_dispatch_fn(q, 1)) 580 ; 581 if (q->nr_sorted == 0) 582 return; 583 if (printed++ < 10) { 584 printk(KERN_ERR "%s: forced dispatching is broken " 585 "(nr_sorted=%u), please report this\n", 586 q->elevator->elevator_type->elevator_name, q->nr_sorted); 587 } 588} 589 590/* 591 * Call with queue lock held, interrupts disabled 592 */ 593void elv_quiesce_start(struct request_queue *q) 594{ 595 if (!q->elevator) 596 return; 597 598 queue_flag_set(QUEUE_FLAG_ELVSWITCH, q); 599 600 /* 601 * make sure we don't have any requests in flight 602 */ 603 elv_drain_elevator(q); 604 while (q->rq.elvpriv) { 605 __blk_run_queue(q); 606 spin_unlock_irq(q->queue_lock); 607 msleep(10); 608 spin_lock_irq(q->queue_lock); 609 elv_drain_elevator(q); 610 } 611} 612 613void elv_quiesce_end(struct request_queue *q) 614{ 615 queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q); 616} 617 618void elv_insert(struct request_queue *q, struct request *rq, int where) 619{ 620 struct list_head *pos; 621 unsigned ordseq; 622 int unplug_it = 1; 623 624 trace_block_rq_insert(q, rq); 625 626 rq->q = q; 627 628 switch (where) { 629 case ELEVATOR_INSERT_FRONT: 630 rq->cmd_flags |= REQ_SOFTBARRIER; 631 632 list_add(&rq->queuelist, &q->queue_head); 633 break; 634 635 case ELEVATOR_INSERT_BACK: 636 rq->cmd_flags |= REQ_SOFTBARRIER; 637 elv_drain_elevator(q); 638 list_add_tail(&rq->queuelist, &q->queue_head); 639 /* 640 * We kick the queue here for the following reasons. 641 * - The elevator might have returned NULL previously 642 * to delay requests and returned them now. As the 643 * queue wasn't empty before this request, ll_rw_blk 644 * won't run the queue on return, resulting in hang. 645 * - Usually, back inserted requests won't be merged 646 * with anything. There's no point in delaying queue 647 * processing. 648 */ 649 __blk_run_queue(q); 650 break; 651 652 case ELEVATOR_INSERT_SORT: 653 BUG_ON(rq->cmd_type != REQ_TYPE_FS && 654 !(rq->cmd_flags & REQ_DISCARD)); 655 rq->cmd_flags |= REQ_SORTED; 656 q->nr_sorted++; 657 if (rq_mergeable(rq)) { 658 elv_rqhash_add(q, rq); 659 if (!q->last_merge) 660 q->last_merge = rq; 661 } 662 663 /* 664 * Some ioscheds (cfq) run q->request_fn directly, so 665 * rq cannot be accessed after calling 666 * elevator_add_req_fn. 667 */ 668 q->elevator->ops->elevator_add_req_fn(q, rq); 669 break; 670 671 case ELEVATOR_INSERT_REQUEUE: 672 /* 673 * If ordered flush isn't in progress, we do front 674 * insertion; otherwise, requests should be requeued 675 * in ordseq order. 676 */ 677 rq->cmd_flags |= REQ_SOFTBARRIER; 678 679 /* 680 * Most requeues happen because of a busy condition, 681 * don't force unplug of the queue for that case. 682 */ 683 unplug_it = 0; 684 685 if (q->ordseq == 0) { 686 list_add(&rq->queuelist, &q->queue_head); 687 break; 688 } 689 690 ordseq = blk_ordered_req_seq(rq); 691 692 list_for_each(pos, &q->queue_head) { 693 struct request *pos_rq = list_entry_rq(pos); 694 if (ordseq <= blk_ordered_req_seq(pos_rq)) 695 break; 696 } 697 698 list_add_tail(&rq->queuelist, pos); 699 break; 700 701 default: 702 printk(KERN_ERR "%s: bad insertion point %d\n", 703 __func__, where); 704 BUG(); 705 } 706 707 if (unplug_it && blk_queue_plugged(q)) { 708 int nrq = q->rq.count[BLK_RW_SYNC] + q->rq.count[BLK_RW_ASYNC] 709 - queue_in_flight(q); 710 711 if (nrq >= q->unplug_thresh) 712 __generic_unplug_device(q); 713 } 714} 715 716void __elv_add_request(struct request_queue *q, struct request *rq, int where, 717 int plug) 718{ 719 if (q->ordcolor) 720 rq->cmd_flags |= REQ_ORDERED_COLOR; 721 722 if (rq->cmd_flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) { 723 /* 724 * toggle ordered color 725 */ 726 if (rq->cmd_flags & REQ_HARDBARRIER) 727 q->ordcolor ^= 1; 728 729 /* 730 * barriers implicitly indicate back insertion 731 */ 732 if (where == ELEVATOR_INSERT_SORT) 733 where = ELEVATOR_INSERT_BACK; 734 735 /* 736 * this request is scheduling boundary, update 737 * end_sector 738 */ 739 if (rq->cmd_type == REQ_TYPE_FS || 740 (rq->cmd_flags & REQ_DISCARD)) { 741 q->end_sector = rq_end_sector(rq); 742 q->boundary_rq = rq; 743 } 744 } else if (!(rq->cmd_flags & REQ_ELVPRIV) && 745 where == ELEVATOR_INSERT_SORT) 746 where = ELEVATOR_INSERT_BACK; 747 748 if (plug) 749 blk_plug_device(q); 750 751 elv_insert(q, rq, where); 752} 753EXPORT_SYMBOL(__elv_add_request); 754 755void elv_add_request(struct request_queue *q, struct request *rq, int where, 756 int plug) 757{ 758 unsigned long flags; 759 760 spin_lock_irqsave(q->queue_lock, flags); 761 __elv_add_request(q, rq, where, plug); 762 spin_unlock_irqrestore(q->queue_lock, flags); 763} 764EXPORT_SYMBOL(elv_add_request); 765 766int elv_queue_empty(struct request_queue *q) 767{ 768 struct elevator_queue *e = q->elevator; 769 770 if (!list_empty(&q->queue_head)) 771 return 0; 772 773 if (e->ops->elevator_queue_empty_fn) 774 return e->ops->elevator_queue_empty_fn(q); 775 776 return 1; 777} 778EXPORT_SYMBOL(elv_queue_empty); 779 780struct request *elv_latter_request(struct request_queue *q, struct request *rq) 781{ 782 struct elevator_queue *e = q->elevator; 783 784 if (e->ops->elevator_latter_req_fn) 785 return e->ops->elevator_latter_req_fn(q, rq); 786 return NULL; 787} 788 789struct request *elv_former_request(struct request_queue *q, struct request *rq) 790{ 791 struct elevator_queue *e = q->elevator; 792 793 if (e->ops->elevator_former_req_fn) 794 return e->ops->elevator_former_req_fn(q, rq); 795 return NULL; 796} 797 798int elv_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask) 799{ 800 struct elevator_queue *e = q->elevator; 801 802 if (e->ops->elevator_set_req_fn) 803 return e->ops->elevator_set_req_fn(q, rq, gfp_mask); 804 805 rq->elevator_private = NULL; 806 return 0; 807} 808 809void elv_put_request(struct request_queue *q, struct request *rq) 810{ 811 struct elevator_queue *e = q->elevator; 812 813 if (e->ops->elevator_put_req_fn) 814 e->ops->elevator_put_req_fn(rq); 815} 816 817int elv_may_queue(struct request_queue *q, int rw) 818{ 819 struct elevator_queue *e = q->elevator; 820 821 if (e->ops->elevator_may_queue_fn) 822 return e->ops->elevator_may_queue_fn(q, rw); 823 824 return ELV_MQUEUE_MAY; 825} 826 827void elv_abort_queue(struct request_queue *q) 828{ 829 struct request *rq; 830 831 while (!list_empty(&q->queue_head)) { 832 rq = list_entry_rq(q->queue_head.next); 833 rq->cmd_flags |= REQ_QUIET; 834 trace_block_rq_abort(q, rq); 835 /* 836 * Mark this request as started so we don't trigger 837 * any debug logic in the end I/O path. 838 */ 839 blk_start_request(rq); 840 __blk_end_request_all(rq, -EIO); 841 } 842} 843EXPORT_SYMBOL(elv_abort_queue); 844 845void elv_completed_request(struct request_queue *q, struct request *rq) 846{ 847 struct elevator_queue *e = q->elevator; 848 849 /* 850 * request is released from the driver, io must be done 851 */ 852 if (blk_account_rq(rq)) { 853 q->in_flight[rq_is_sync(rq)]--; 854 if ((rq->cmd_flags & REQ_SORTED) && 855 e->ops->elevator_completed_req_fn) 856 e->ops->elevator_completed_req_fn(q, rq); 857 } 858 859 /* 860 * Check if the queue is waiting for fs requests to be 861 * drained for flush sequence. 862 */ 863 if (unlikely(q->ordseq)) { 864 struct request *next = NULL; 865 866 if (!list_empty(&q->queue_head)) 867 next = list_entry_rq(q->queue_head.next); 868 869 if (!queue_in_flight(q) && 870 blk_ordered_cur_seq(q) == QUEUE_ORDSEQ_DRAIN && 871 (!next || blk_ordered_req_seq(next) > QUEUE_ORDSEQ_DRAIN)) { 872 blk_ordered_complete_seq(q, QUEUE_ORDSEQ_DRAIN, 0); 873 __blk_run_queue(q); 874 } 875 } 876} 877 878#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr) 879 880static ssize_t 881elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page) 882{ 883 struct elv_fs_entry *entry = to_elv(attr); 884 struct elevator_queue *e; 885 ssize_t error; 886 887 if (!entry->show) 888 return -EIO; 889 890 e = container_of(kobj, struct elevator_queue, kobj); 891 mutex_lock(&e->sysfs_lock); 892 error = e->ops ? entry->show(e, page) : -ENOENT; 893 mutex_unlock(&e->sysfs_lock); 894 return error; 895} 896 897static ssize_t 898elv_attr_store(struct kobject *kobj, struct attribute *attr, 899 const char *page, size_t length) 900{ 901 struct elv_fs_entry *entry = to_elv(attr); 902 struct elevator_queue *e; 903 ssize_t error; 904 905 if (!entry->store) 906 return -EIO; 907 908 e = container_of(kobj, struct elevator_queue, kobj); 909 mutex_lock(&e->sysfs_lock); 910 error = e->ops ? entry->store(e, page, length) : -ENOENT; 911 mutex_unlock(&e->sysfs_lock); 912 return error; 913} 914 915static const struct sysfs_ops elv_sysfs_ops = { 916 .show = elv_attr_show, 917 .store = elv_attr_store, 918}; 919 920static struct kobj_type elv_ktype = { 921 .sysfs_ops = &elv_sysfs_ops, 922 .release = elevator_release, 923}; 924 925int elv_register_queue(struct request_queue *q) 926{ 927 struct elevator_queue *e = q->elevator; 928 int error; 929 930 error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched"); 931 if (!error) { 932 struct elv_fs_entry *attr = e->elevator_type->elevator_attrs; 933 if (attr) { 934 while (attr->attr.name) { 935 if (sysfs_create_file(&e->kobj, &attr->attr)) 936 break; 937 attr++; 938 } 939 } 940 kobject_uevent(&e->kobj, KOBJ_ADD); 941 e->registered = 1; 942 } 943 return error; 944} 945EXPORT_SYMBOL(elv_register_queue); 946 947static void __elv_unregister_queue(struct elevator_queue *e) 948{ 949 kobject_uevent(&e->kobj, KOBJ_REMOVE); 950 kobject_del(&e->kobj); 951 e->registered = 0; 952} 953 954void elv_unregister_queue(struct request_queue *q) 955{ 956 if (q) 957 __elv_unregister_queue(q->elevator); 958} 959EXPORT_SYMBOL(elv_unregister_queue); 960 961void elv_register(struct elevator_type *e) 962{ 963 char *def = ""; 964 965 spin_lock(&elv_list_lock); 966 BUG_ON(elevator_find(e->elevator_name)); 967 list_add_tail(&e->list, &elv_list); 968 spin_unlock(&elv_list_lock); 969 970 if (!strcmp(e->elevator_name, chosen_elevator) || 971 (!*chosen_elevator && 972 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED))) 973 def = " (default)"; 974 975 printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name, 976 def); 977} 978EXPORT_SYMBOL_GPL(elv_register); 979 980void elv_unregister(struct elevator_type *e) 981{ 982 struct task_struct *g, *p; 983 984 /* 985 * Iterate every thread in the process to remove the io contexts. 986 */ 987 if (e->ops.trim) { 988 read_lock(&tasklist_lock); 989 do_each_thread(g, p) { 990 task_lock(p); 991 if (p->io_context) 992 e->ops.trim(p->io_context); 993 task_unlock(p); 994 } while_each_thread(g, p); 995 read_unlock(&tasklist_lock); 996 } 997 998 spin_lock(&elv_list_lock); 999 list_del_init(&e->list); 1000 spin_unlock(&elv_list_lock); 1001} 1002EXPORT_SYMBOL_GPL(elv_unregister); 1003 1004/* 1005 * switch to new_e io scheduler. be careful not to introduce deadlocks - 1006 * we don't free the old io scheduler, before we have allocated what we 1007 * need for the new one. this way we have a chance of going back to the old 1008 * one, if the new one fails init for some reason. 1009 */ 1010static int elevator_switch(struct request_queue *q, struct elevator_type *new_e) 1011{ 1012 struct elevator_queue *old_elevator, *e; 1013 void *data; 1014 int err; 1015 1016 /* 1017 * Allocate new elevator 1018 */ 1019 e = elevator_alloc(q, new_e); 1020 if (!e) 1021 return -ENOMEM; 1022 1023 data = elevator_init_queue(q, e); 1024 if (!data) { 1025 kobject_put(&e->kobj); 1026 return -ENOMEM; 1027 } 1028 1029 /* 1030 * Turn on BYPASS and drain all requests w/ elevator private data 1031 */ 1032 spin_lock_irq(q->queue_lock); 1033 elv_quiesce_start(q); 1034 1035 /* 1036 * Remember old elevator. 1037 */ 1038 old_elevator = q->elevator; 1039 1040 /* 1041 * attach and start new elevator 1042 */ 1043 elevator_attach(q, e, data); 1044 1045 spin_unlock_irq(q->queue_lock); 1046 1047 if (old_elevator->registered) { 1048 __elv_unregister_queue(old_elevator); 1049 1050 err = elv_register_queue(q); 1051 if (err) 1052 goto fail_register; 1053 } 1054 1055 /* 1056 * finally exit old elevator and turn off BYPASS. 1057 */ 1058 elevator_exit(old_elevator); 1059 spin_lock_irq(q->queue_lock); 1060 elv_quiesce_end(q); 1061 spin_unlock_irq(q->queue_lock); 1062 1063 blk_add_trace_msg(q, "elv switch: %s", e->elevator_type->elevator_name); 1064 1065 return 0; 1066 1067fail_register: 1068 /* 1069 * switch failed, exit the new io scheduler and reattach the old 1070 * one again (along with re-adding the sysfs dir) 1071 */ 1072 elevator_exit(e); 1073 q->elevator = old_elevator; 1074 elv_register_queue(q); 1075 1076 spin_lock_irq(q->queue_lock); 1077 queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q); 1078 spin_unlock_irq(q->queue_lock); 1079 1080 return err; 1081} 1082 1083/* 1084 * Switch this queue to the given IO scheduler. 1085 */ 1086int elevator_change(struct request_queue *q, const char *name) 1087{ 1088 char elevator_name[ELV_NAME_MAX]; 1089 struct elevator_type *e; 1090 1091 if (!q->elevator) 1092 return -ENXIO; 1093 1094 strlcpy(elevator_name, name, sizeof(elevator_name)); 1095 e = elevator_get(strstrip(elevator_name)); 1096 if (!e) { 1097 printk(KERN_ERR "elevator: type %s not found\n", elevator_name); 1098 return -EINVAL; 1099 } 1100 1101 if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) { 1102 elevator_put(e); 1103 return 0; 1104 } 1105 1106 return elevator_switch(q, e); 1107} 1108EXPORT_SYMBOL(elevator_change); 1109 1110ssize_t elv_iosched_store(struct request_queue *q, const char *name, 1111 size_t count) 1112{ 1113 int ret; 1114 1115 if (!q->elevator) 1116 return count; 1117 1118 ret = elevator_change(q, name); 1119 if (!ret) 1120 return count; 1121 1122 printk(KERN_ERR "elevator: switch to %s failed\n", name); 1123 return ret; 1124} 1125 1126ssize_t elv_iosched_show(struct request_queue *q, char *name) 1127{ 1128 struct elevator_queue *e = q->elevator; 1129 struct elevator_type *elv; 1130 struct elevator_type *__e; 1131 int len = 0; 1132 1133 if (!q->elevator || !blk_queue_stackable(q)) 1134 return sprintf(name, "none\n"); 1135 1136 elv = e->elevator_type; 1137 1138 spin_lock(&elv_list_lock); 1139 list_for_each_entry(__e, &elv_list, list) { 1140 if (!strcmp(elv->elevator_name, __e->elevator_name)) 1141 len += sprintf(name+len, "[%s] ", elv->elevator_name); 1142 else 1143 len += sprintf(name+len, "%s ", __e->elevator_name); 1144 } 1145 spin_unlock(&elv_list_lock); 1146 1147 len += sprintf(len+name, "\n"); 1148 return len; 1149} 1150 1151struct request *elv_rb_former_request(struct request_queue *q, 1152 struct request *rq) 1153{ 1154 struct rb_node *rbprev = rb_prev(&rq->rb_node); 1155 1156 if (rbprev) 1157 return rb_entry_rq(rbprev); 1158 1159 return NULL; 1160} 1161EXPORT_SYMBOL(elv_rb_former_request); 1162 1163struct request *elv_rb_latter_request(struct request_queue *q, 1164 struct request *rq) 1165{ 1166 struct rb_node *rbnext = rb_next(&rq->rb_node); 1167 1168 if (rbnext) 1169 return rb_entry_rq(rbnext); 1170 1171 return NULL; 1172} 1173EXPORT_SYMBOL(elv_rb_latter_request); 1174