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