cfq-iosched.c revision eb97b73d75d5c9af7c78c05106de9e3fdc4455ab
1/* 2 * CFQ, or complete fairness queueing, disk scheduler. 3 * 4 * Based on ideas from a previously unfinished io 5 * scheduler (round robin per-process disk scheduling) and Andrea Arcangeli. 6 * 7 * Copyright (C) 2003 Jens Axboe <axboe@suse.de> 8 */ 9#include <linux/kernel.h> 10#include <linux/fs.h> 11#include <linux/blkdev.h> 12#include <linux/elevator.h> 13#include <linux/bio.h> 14#include <linux/config.h> 15#include <linux/module.h> 16#include <linux/slab.h> 17#include <linux/init.h> 18#include <linux/compiler.h> 19#include <linux/hash.h> 20#include <linux/rbtree.h> 21#include <linux/mempool.h> 22#include <linux/ioprio.h> 23#include <linux/writeback.h> 24 25/* 26 * tunables 27 */ 28static int cfq_quantum = 4; /* max queue in one round of service */ 29static int cfq_queued = 8; /* minimum rq allocate limit per-queue*/ 30static int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 }; 31static int cfq_back_max = 16 * 1024; /* maximum backwards seek, in KiB */ 32static int cfq_back_penalty = 2; /* penalty of a backwards seek */ 33 34static int cfq_slice_sync = HZ / 10; 35static int cfq_slice_async = HZ / 25; 36static int cfq_slice_async_rq = 2; 37static int cfq_slice_idle = HZ / 100; 38 39#define CFQ_IDLE_GRACE (HZ / 10) 40#define CFQ_SLICE_SCALE (5) 41 42#define CFQ_KEY_ASYNC (0) 43#define CFQ_KEY_ANY (0xffff) 44 45/* 46 * disable queueing at the driver/hardware level 47 */ 48static int cfq_max_depth = 2; 49 50/* 51 * for the hash of cfqq inside the cfqd 52 */ 53#define CFQ_QHASH_SHIFT 6 54#define CFQ_QHASH_ENTRIES (1 << CFQ_QHASH_SHIFT) 55#define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash) 56 57/* 58 * for the hash of crq inside the cfqq 59 */ 60#define CFQ_MHASH_SHIFT 6 61#define CFQ_MHASH_BLOCK(sec) ((sec) >> 3) 62#define CFQ_MHASH_ENTRIES (1 << CFQ_MHASH_SHIFT) 63#define CFQ_MHASH_FN(sec) hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT) 64#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors) 65#define list_entry_hash(ptr) hlist_entry((ptr), struct cfq_rq, hash) 66 67#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list) 68#define list_entry_fifo(ptr) list_entry((ptr), struct request, queuelist) 69 70#define RQ_DATA(rq) (rq)->elevator_private 71 72/* 73 * rb-tree defines 74 */ 75#define RB_NONE (2) 76#define RB_EMPTY(node) ((node)->rb_node == NULL) 77#define RB_CLEAR_COLOR(node) (node)->rb_color = RB_NONE 78#define RB_CLEAR(node) do { \ 79 (node)->rb_parent = NULL; \ 80 RB_CLEAR_COLOR((node)); \ 81 (node)->rb_right = NULL; \ 82 (node)->rb_left = NULL; \ 83} while (0) 84#define RB_CLEAR_ROOT(root) ((root)->rb_node = NULL) 85#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node) 86#define rq_rb_key(rq) (rq)->sector 87 88static kmem_cache_t *crq_pool; 89static kmem_cache_t *cfq_pool; 90static kmem_cache_t *cfq_ioc_pool; 91 92#define CFQ_PRIO_LISTS IOPRIO_BE_NR 93#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE) 94#define cfq_class_be(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_BE) 95#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT) 96 97#define ASYNC (0) 98#define SYNC (1) 99 100#define cfq_cfqq_dispatched(cfqq) \ 101 ((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC]) 102 103#define cfq_cfqq_class_sync(cfqq) ((cfqq)->key != CFQ_KEY_ASYNC) 104 105#define cfq_cfqq_sync(cfqq) \ 106 (cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC]) 107 108/* 109 * Per block device queue structure 110 */ 111struct cfq_data { 112 atomic_t ref; 113 request_queue_t *queue; 114 115 /* 116 * rr list of queues with requests and the count of them 117 */ 118 struct list_head rr_list[CFQ_PRIO_LISTS]; 119 struct list_head busy_rr; 120 struct list_head cur_rr; 121 struct list_head idle_rr; 122 unsigned int busy_queues; 123 124 /* 125 * non-ordered list of empty cfqq's 126 */ 127 struct list_head empty_list; 128 129 /* 130 * cfqq lookup hash 131 */ 132 struct hlist_head *cfq_hash; 133 134 /* 135 * global crq hash for all queues 136 */ 137 struct hlist_head *crq_hash; 138 139 unsigned int max_queued; 140 141 mempool_t *crq_pool; 142 143 int rq_in_driver; 144 145 /* 146 * schedule slice state info 147 */ 148 /* 149 * idle window management 150 */ 151 struct timer_list idle_slice_timer; 152 struct work_struct unplug_work; 153 154 struct cfq_queue *active_queue; 155 struct cfq_io_context *active_cic; 156 int cur_prio, cur_end_prio; 157 unsigned int dispatch_slice; 158 159 struct timer_list idle_class_timer; 160 161 sector_t last_sector; 162 unsigned long last_end_request; 163 164 unsigned int rq_starved; 165 166 /* 167 * tunables, see top of file 168 */ 169 unsigned int cfq_quantum; 170 unsigned int cfq_queued; 171 unsigned int cfq_fifo_expire[2]; 172 unsigned int cfq_back_penalty; 173 unsigned int cfq_back_max; 174 unsigned int cfq_slice[2]; 175 unsigned int cfq_slice_async_rq; 176 unsigned int cfq_slice_idle; 177 unsigned int cfq_max_depth; 178}; 179 180/* 181 * Per process-grouping structure 182 */ 183struct cfq_queue { 184 /* reference count */ 185 atomic_t ref; 186 /* parent cfq_data */ 187 struct cfq_data *cfqd; 188 /* cfqq lookup hash */ 189 struct hlist_node cfq_hash; 190 /* hash key */ 191 unsigned int key; 192 /* on either rr or empty list of cfqd */ 193 struct list_head cfq_list; 194 /* sorted list of pending requests */ 195 struct rb_root sort_list; 196 /* if fifo isn't expired, next request to serve */ 197 struct cfq_rq *next_crq; 198 /* requests queued in sort_list */ 199 int queued[2]; 200 /* currently allocated requests */ 201 int allocated[2]; 202 /* fifo list of requests in sort_list */ 203 struct list_head fifo; 204 205 unsigned long slice_start; 206 unsigned long slice_end; 207 unsigned long slice_left; 208 unsigned long service_last; 209 210 /* number of requests that are on the dispatch list */ 211 int on_dispatch[2]; 212 213 /* io prio of this group */ 214 unsigned short ioprio, org_ioprio; 215 unsigned short ioprio_class, org_ioprio_class; 216 217 /* various state flags, see below */ 218 unsigned int flags; 219}; 220 221struct cfq_rq { 222 struct rb_node rb_node; 223 sector_t rb_key; 224 struct request *request; 225 struct hlist_node hash; 226 227 struct cfq_queue *cfq_queue; 228 struct cfq_io_context *io_context; 229 230 unsigned int crq_flags; 231}; 232 233enum cfqq_state_flags { 234 CFQ_CFQQ_FLAG_on_rr = 0, 235 CFQ_CFQQ_FLAG_wait_request, 236 CFQ_CFQQ_FLAG_must_alloc, 237 CFQ_CFQQ_FLAG_must_alloc_slice, 238 CFQ_CFQQ_FLAG_must_dispatch, 239 CFQ_CFQQ_FLAG_fifo_expire, 240 CFQ_CFQQ_FLAG_idle_window, 241 CFQ_CFQQ_FLAG_prio_changed, 242 CFQ_CFQQ_FLAG_expired, 243}; 244 245#define CFQ_CFQQ_FNS(name) \ 246static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \ 247{ \ 248 cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name); \ 249} \ 250static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \ 251{ \ 252 cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \ 253} \ 254static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \ 255{ \ 256 return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \ 257} 258 259CFQ_CFQQ_FNS(on_rr); 260CFQ_CFQQ_FNS(wait_request); 261CFQ_CFQQ_FNS(must_alloc); 262CFQ_CFQQ_FNS(must_alloc_slice); 263CFQ_CFQQ_FNS(must_dispatch); 264CFQ_CFQQ_FNS(fifo_expire); 265CFQ_CFQQ_FNS(idle_window); 266CFQ_CFQQ_FNS(prio_changed); 267CFQ_CFQQ_FNS(expired); 268#undef CFQ_CFQQ_FNS 269 270enum cfq_rq_state_flags { 271 CFQ_CRQ_FLAG_is_sync = 0, 272}; 273 274#define CFQ_CRQ_FNS(name) \ 275static inline void cfq_mark_crq_##name(struct cfq_rq *crq) \ 276{ \ 277 crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name); \ 278} \ 279static inline void cfq_clear_crq_##name(struct cfq_rq *crq) \ 280{ \ 281 crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name); \ 282} \ 283static inline int cfq_crq_##name(const struct cfq_rq *crq) \ 284{ \ 285 return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0; \ 286} 287 288CFQ_CRQ_FNS(is_sync); 289#undef CFQ_CRQ_FNS 290 291static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short); 292static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *); 293static void cfq_put_cfqd(struct cfq_data *cfqd); 294 295#define process_sync(tsk) ((tsk)->flags & PF_SYNCWRITE) 296 297/* 298 * lots of deadline iosched dupes, can be abstracted later... 299 */ 300static inline void cfq_del_crq_hash(struct cfq_rq *crq) 301{ 302 hlist_del_init(&crq->hash); 303} 304 305static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq) 306{ 307 const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request)); 308 309 hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]); 310} 311 312static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset) 313{ 314 struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)]; 315 struct hlist_node *entry, *next; 316 317 hlist_for_each_safe(entry, next, hash_list) { 318 struct cfq_rq *crq = list_entry_hash(entry); 319 struct request *__rq = crq->request; 320 321 if (!rq_mergeable(__rq)) { 322 cfq_del_crq_hash(crq); 323 continue; 324 } 325 326 if (rq_hash_key(__rq) == offset) 327 return __rq; 328 } 329 330 return NULL; 331} 332 333/* 334 * scheduler run of queue, if there are requests pending and no one in the 335 * driver that will restart queueing 336 */ 337static inline void cfq_schedule_dispatch(struct cfq_data *cfqd) 338{ 339 if (!cfqd->rq_in_driver && cfqd->busy_queues) 340 kblockd_schedule_work(&cfqd->unplug_work); 341} 342 343static int cfq_queue_empty(request_queue_t *q) 344{ 345 struct cfq_data *cfqd = q->elevator->elevator_data; 346 347 return !cfqd->busy_queues; 348} 349 350/* 351 * Lifted from AS - choose which of crq1 and crq2 that is best served now. 352 * We choose the request that is closest to the head right now. Distance 353 * behind the head are penalized and only allowed to a certain extent. 354 */ 355static struct cfq_rq * 356cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2) 357{ 358 sector_t last, s1, s2, d1 = 0, d2 = 0; 359 int r1_wrap = 0, r2_wrap = 0; /* requests are behind the disk head */ 360 unsigned long back_max; 361 362 if (crq1 == NULL || crq1 == crq2) 363 return crq2; 364 if (crq2 == NULL) 365 return crq1; 366 367 if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2)) 368 return crq1; 369 else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1)) 370 return crq2; 371 372 s1 = crq1->request->sector; 373 s2 = crq2->request->sector; 374 375 last = cfqd->last_sector; 376 377 /* 378 * by definition, 1KiB is 2 sectors 379 */ 380 back_max = cfqd->cfq_back_max * 2; 381 382 /* 383 * Strict one way elevator _except_ in the case where we allow 384 * short backward seeks which are biased as twice the cost of a 385 * similar forward seek. 386 */ 387 if (s1 >= last) 388 d1 = s1 - last; 389 else if (s1 + back_max >= last) 390 d1 = (last - s1) * cfqd->cfq_back_penalty; 391 else 392 r1_wrap = 1; 393 394 if (s2 >= last) 395 d2 = s2 - last; 396 else if (s2 + back_max >= last) 397 d2 = (last - s2) * cfqd->cfq_back_penalty; 398 else 399 r2_wrap = 1; 400 401 /* Found required data */ 402 if (!r1_wrap && r2_wrap) 403 return crq1; 404 else if (!r2_wrap && r1_wrap) 405 return crq2; 406 else if (r1_wrap && r2_wrap) { 407 /* both behind the head */ 408 if (s1 <= s2) 409 return crq1; 410 else 411 return crq2; 412 } 413 414 /* Both requests in front of the head */ 415 if (d1 < d2) 416 return crq1; 417 else if (d2 < d1) 418 return crq2; 419 else { 420 if (s1 >= s2) 421 return crq1; 422 else 423 return crq2; 424 } 425} 426 427/* 428 * would be nice to take fifo expire time into account as well 429 */ 430static struct cfq_rq * 431cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq, 432 struct cfq_rq *last) 433{ 434 struct cfq_rq *crq_next = NULL, *crq_prev = NULL; 435 struct rb_node *rbnext, *rbprev; 436 437 if (!(rbnext = rb_next(&last->rb_node))) { 438 rbnext = rb_first(&cfqq->sort_list); 439 if (rbnext == &last->rb_node) 440 rbnext = NULL; 441 } 442 443 rbprev = rb_prev(&last->rb_node); 444 445 if (rbprev) 446 crq_prev = rb_entry_crq(rbprev); 447 if (rbnext) 448 crq_next = rb_entry_crq(rbnext); 449 450 return cfq_choose_req(cfqd, crq_next, crq_prev); 451} 452 453static void cfq_update_next_crq(struct cfq_rq *crq) 454{ 455 struct cfq_queue *cfqq = crq->cfq_queue; 456 457 if (cfqq->next_crq == crq) 458 cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq); 459} 460 461static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted) 462{ 463 struct cfq_data *cfqd = cfqq->cfqd; 464 struct list_head *list, *entry; 465 466 BUG_ON(!cfq_cfqq_on_rr(cfqq)); 467 468 list_del(&cfqq->cfq_list); 469 470 if (cfq_class_rt(cfqq)) 471 list = &cfqd->cur_rr; 472 else if (cfq_class_idle(cfqq)) 473 list = &cfqd->idle_rr; 474 else { 475 /* 476 * if cfqq has requests in flight, don't allow it to be 477 * found in cfq_set_active_queue before it has finished them. 478 * this is done to increase fairness between a process that 479 * has lots of io pending vs one that only generates one 480 * sporadically or synchronously 481 */ 482 if (cfq_cfqq_dispatched(cfqq)) 483 list = &cfqd->busy_rr; 484 else 485 list = &cfqd->rr_list[cfqq->ioprio]; 486 } 487 488 /* 489 * if queue was preempted, just add to front to be fair. busy_rr 490 * isn't sorted. 491 */ 492 if (preempted || list == &cfqd->busy_rr) { 493 list_add(&cfqq->cfq_list, list); 494 return; 495 } 496 497 /* 498 * sort by when queue was last serviced 499 */ 500 entry = list; 501 while ((entry = entry->prev) != list) { 502 struct cfq_queue *__cfqq = list_entry_cfqq(entry); 503 504 if (!__cfqq->service_last) 505 break; 506 if (time_before(__cfqq->service_last, cfqq->service_last)) 507 break; 508 } 509 510 list_add(&cfqq->cfq_list, entry); 511} 512 513/* 514 * add to busy list of queues for service, trying to be fair in ordering 515 * the pending list according to last request service 516 */ 517static inline void 518cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq) 519{ 520 BUG_ON(cfq_cfqq_on_rr(cfqq)); 521 cfq_mark_cfqq_on_rr(cfqq); 522 cfqd->busy_queues++; 523 524 cfq_resort_rr_list(cfqq, 0); 525} 526 527static inline void 528cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq) 529{ 530 BUG_ON(!cfq_cfqq_on_rr(cfqq)); 531 cfq_clear_cfqq_on_rr(cfqq); 532 list_move(&cfqq->cfq_list, &cfqd->empty_list); 533 534 BUG_ON(!cfqd->busy_queues); 535 cfqd->busy_queues--; 536} 537 538/* 539 * rb tree support functions 540 */ 541static inline void cfq_del_crq_rb(struct cfq_rq *crq) 542{ 543 struct cfq_queue *cfqq = crq->cfq_queue; 544 struct cfq_data *cfqd = cfqq->cfqd; 545 const int sync = cfq_crq_is_sync(crq); 546 547 BUG_ON(!cfqq->queued[sync]); 548 cfqq->queued[sync]--; 549 550 cfq_update_next_crq(crq); 551 552 rb_erase(&crq->rb_node, &cfqq->sort_list); 553 RB_CLEAR_COLOR(&crq->rb_node); 554 555 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list)) 556 cfq_del_cfqq_rr(cfqd, cfqq); 557} 558 559static struct cfq_rq * 560__cfq_add_crq_rb(struct cfq_rq *crq) 561{ 562 struct rb_node **p = &crq->cfq_queue->sort_list.rb_node; 563 struct rb_node *parent = NULL; 564 struct cfq_rq *__crq; 565 566 while (*p) { 567 parent = *p; 568 __crq = rb_entry_crq(parent); 569 570 if (crq->rb_key < __crq->rb_key) 571 p = &(*p)->rb_left; 572 else if (crq->rb_key > __crq->rb_key) 573 p = &(*p)->rb_right; 574 else 575 return __crq; 576 } 577 578 rb_link_node(&crq->rb_node, parent, p); 579 return NULL; 580} 581 582static void cfq_add_crq_rb(struct cfq_rq *crq) 583{ 584 struct cfq_queue *cfqq = crq->cfq_queue; 585 struct cfq_data *cfqd = cfqq->cfqd; 586 struct request *rq = crq->request; 587 struct cfq_rq *__alias; 588 589 crq->rb_key = rq_rb_key(rq); 590 cfqq->queued[cfq_crq_is_sync(crq)]++; 591 592 /* 593 * looks a little odd, but the first insert might return an alias. 594 * if that happens, put the alias on the dispatch list 595 */ 596 while ((__alias = __cfq_add_crq_rb(crq)) != NULL) 597 cfq_dispatch_insert(cfqd->queue, __alias); 598 599 rb_insert_color(&crq->rb_node, &cfqq->sort_list); 600 601 if (!cfq_cfqq_on_rr(cfqq)) 602 cfq_add_cfqq_rr(cfqd, cfqq); 603 604 /* 605 * check if this request is a better next-serve candidate 606 */ 607 cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq); 608} 609 610static inline void 611cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq) 612{ 613 rb_erase(&crq->rb_node, &cfqq->sort_list); 614 cfqq->queued[cfq_crq_is_sync(crq)]--; 615 616 cfq_add_crq_rb(crq); 617} 618 619static struct request *cfq_find_rq_rb(struct cfq_data *cfqd, sector_t sector) 620 621{ 622 struct cfq_queue *cfqq = cfq_find_cfq_hash(cfqd, current->pid, CFQ_KEY_ANY); 623 struct rb_node *n; 624 625 if (!cfqq) 626 goto out; 627 628 n = cfqq->sort_list.rb_node; 629 while (n) { 630 struct cfq_rq *crq = rb_entry_crq(n); 631 632 if (sector < crq->rb_key) 633 n = n->rb_left; 634 else if (sector > crq->rb_key) 635 n = n->rb_right; 636 else 637 return crq->request; 638 } 639 640out: 641 return NULL; 642} 643 644static void cfq_activate_request(request_queue_t *q, struct request *rq) 645{ 646 struct cfq_data *cfqd = q->elevator->elevator_data; 647 648 cfqd->rq_in_driver++; 649} 650 651static void cfq_deactivate_request(request_queue_t *q, struct request *rq) 652{ 653 struct cfq_data *cfqd = q->elevator->elevator_data; 654 655 WARN_ON(!cfqd->rq_in_driver); 656 cfqd->rq_in_driver--; 657} 658 659static void cfq_remove_request(struct request *rq) 660{ 661 struct cfq_rq *crq = RQ_DATA(rq); 662 663 list_del_init(&rq->queuelist); 664 cfq_del_crq_rb(crq); 665 cfq_del_crq_hash(crq); 666} 667 668static int 669cfq_merge(request_queue_t *q, struct request **req, struct bio *bio) 670{ 671 struct cfq_data *cfqd = q->elevator->elevator_data; 672 struct request *__rq; 673 int ret; 674 675 __rq = cfq_find_rq_hash(cfqd, bio->bi_sector); 676 if (__rq && elv_rq_merge_ok(__rq, bio)) { 677 ret = ELEVATOR_BACK_MERGE; 678 goto out; 679 } 680 681 __rq = cfq_find_rq_rb(cfqd, bio->bi_sector + bio_sectors(bio)); 682 if (__rq && elv_rq_merge_ok(__rq, bio)) { 683 ret = ELEVATOR_FRONT_MERGE; 684 goto out; 685 } 686 687 return ELEVATOR_NO_MERGE; 688out: 689 *req = __rq; 690 return ret; 691} 692 693static void cfq_merged_request(request_queue_t *q, struct request *req) 694{ 695 struct cfq_data *cfqd = q->elevator->elevator_data; 696 struct cfq_rq *crq = RQ_DATA(req); 697 698 cfq_del_crq_hash(crq); 699 cfq_add_crq_hash(cfqd, crq); 700 701 if (rq_rb_key(req) != crq->rb_key) { 702 struct cfq_queue *cfqq = crq->cfq_queue; 703 704 cfq_update_next_crq(crq); 705 cfq_reposition_crq_rb(cfqq, crq); 706 } 707} 708 709static void 710cfq_merged_requests(request_queue_t *q, struct request *rq, 711 struct request *next) 712{ 713 cfq_merged_request(q, rq); 714 715 /* 716 * reposition in fifo if next is older than rq 717 */ 718 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) && 719 time_before(next->start_time, rq->start_time)) 720 list_move(&rq->queuelist, &next->queuelist); 721 722 cfq_remove_request(next); 723} 724 725static inline void 726__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq) 727{ 728 if (cfqq) { 729 /* 730 * stop potential idle class queues waiting service 731 */ 732 del_timer(&cfqd->idle_class_timer); 733 734 cfqq->slice_start = jiffies; 735 cfqq->slice_end = 0; 736 cfqq->slice_left = 0; 737 cfq_clear_cfqq_must_alloc_slice(cfqq); 738 cfq_clear_cfqq_fifo_expire(cfqq); 739 cfq_clear_cfqq_expired(cfqq); 740 } 741 742 cfqd->active_queue = cfqq; 743} 744 745/* 746 * 0 747 * 0,1 748 * 0,1,2 749 * 0,1,2,3 750 * 0,1,2,3,4 751 * 0,1,2,3,4,5 752 * 0,1,2,3,4,5,6 753 * 0,1,2,3,4,5,6,7 754 */ 755static int cfq_get_next_prio_level(struct cfq_data *cfqd) 756{ 757 int prio, wrap; 758 759 prio = -1; 760 wrap = 0; 761 do { 762 int p; 763 764 for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) { 765 if (!list_empty(&cfqd->rr_list[p])) { 766 prio = p; 767 break; 768 } 769 } 770 771 if (prio != -1) 772 break; 773 cfqd->cur_prio = 0; 774 if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) { 775 cfqd->cur_end_prio = 0; 776 if (wrap) 777 break; 778 wrap = 1; 779 } 780 } while (1); 781 782 if (unlikely(prio == -1)) 783 return -1; 784 785 BUG_ON(prio >= CFQ_PRIO_LISTS); 786 787 list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr); 788 789 cfqd->cur_prio = prio + 1; 790 if (cfqd->cur_prio > cfqd->cur_end_prio) { 791 cfqd->cur_end_prio = cfqd->cur_prio; 792 cfqd->cur_prio = 0; 793 } 794 if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) { 795 cfqd->cur_prio = 0; 796 cfqd->cur_end_prio = 0; 797 } 798 799 return prio; 800} 801 802static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd) 803{ 804 struct cfq_queue *cfqq; 805 806 /* 807 * if current queue is expired but not done with its requests yet, 808 * wait for that to happen 809 */ 810 if ((cfqq = cfqd->active_queue) != NULL) { 811 if (cfq_cfqq_expired(cfqq) && cfq_cfqq_dispatched(cfqq)) 812 return NULL; 813 } 814 815 /* 816 * if current list is non-empty, grab first entry. if it is empty, 817 * get next prio level and grab first entry then if any are spliced 818 */ 819 if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1) 820 cfqq = list_entry_cfqq(cfqd->cur_rr.next); 821 822 /* 823 * if we have idle queues and no rt or be queues had pending 824 * requests, either allow immediate service if the grace period 825 * has passed or arm the idle grace timer 826 */ 827 if (!cfqq && !list_empty(&cfqd->idle_rr)) { 828 unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE; 829 830 if (time_after_eq(jiffies, end)) 831 cfqq = list_entry_cfqq(cfqd->idle_rr.next); 832 else 833 mod_timer(&cfqd->idle_class_timer, end); 834 } 835 836 __cfq_set_active_queue(cfqd, cfqq); 837 return cfqq; 838} 839 840/* 841 * current cfqq expired its slice (or was too idle), select new one 842 */ 843static void 844__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq, 845 int preempted) 846{ 847 unsigned long now = jiffies; 848 849 if (cfq_cfqq_wait_request(cfqq)) 850 del_timer(&cfqd->idle_slice_timer); 851 852 if (!preempted && !cfq_cfqq_dispatched(cfqq)) 853 cfqq->service_last = now; 854 855 cfq_clear_cfqq_must_dispatch(cfqq); 856 cfq_clear_cfqq_wait_request(cfqq); 857 858 /* 859 * store what was left of this slice, if the queue idled out 860 * or was preempted 861 */ 862 if (time_after(cfqq->slice_end, now)) 863 cfqq->slice_left = cfqq->slice_end - now; 864 else 865 cfqq->slice_left = 0; 866 867 if (cfq_cfqq_on_rr(cfqq)) 868 cfq_resort_rr_list(cfqq, preempted); 869 870 if (cfqq == cfqd->active_queue) 871 cfqd->active_queue = NULL; 872 873 if (cfqd->active_cic) { 874 put_io_context(cfqd->active_cic->ioc); 875 cfqd->active_cic = NULL; 876 } 877 878 cfqd->dispatch_slice = 0; 879} 880 881static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted) 882{ 883 struct cfq_queue *cfqq = cfqd->active_queue; 884 885 if (cfqq) { 886 /* 887 * use deferred expiry, if there are requests in progress as 888 * not to disturb the slice of the next queue 889 */ 890 if (cfq_cfqq_dispatched(cfqq)) 891 cfq_mark_cfqq_expired(cfqq); 892 else 893 __cfq_slice_expired(cfqd, cfqq, preempted); 894 } 895} 896 897static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq) 898 899{ 900 WARN_ON(!RB_EMPTY(&cfqq->sort_list)); 901 WARN_ON(cfqq != cfqd->active_queue); 902 903 /* 904 * idle is disabled, either manually or by past process history 905 */ 906 if (!cfqd->cfq_slice_idle) 907 return 0; 908 if (!cfq_cfqq_idle_window(cfqq)) 909 return 0; 910 /* 911 * task has exited, don't wait 912 */ 913 if (cfqd->active_cic && !cfqd->active_cic->ioc->task) 914 return 0; 915 916 cfq_mark_cfqq_must_dispatch(cfqq); 917 cfq_mark_cfqq_wait_request(cfqq); 918 919 if (!timer_pending(&cfqd->idle_slice_timer)) { 920 unsigned long slice_left = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle); 921 922 cfqd->idle_slice_timer.expires = jiffies + slice_left; 923 add_timer(&cfqd->idle_slice_timer); 924 } 925 926 return 1; 927} 928 929static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq) 930{ 931 struct cfq_data *cfqd = q->elevator->elevator_data; 932 struct cfq_queue *cfqq = crq->cfq_queue; 933 934 cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq); 935 cfq_remove_request(crq->request); 936 cfqq->on_dispatch[cfq_crq_is_sync(crq)]++; 937 elv_dispatch_sort(q, crq->request); 938} 939 940/* 941 * return expired entry, or NULL to just start from scratch in rbtree 942 */ 943static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq) 944{ 945 struct cfq_data *cfqd = cfqq->cfqd; 946 struct request *rq; 947 struct cfq_rq *crq; 948 949 if (cfq_cfqq_fifo_expire(cfqq)) 950 return NULL; 951 952 if (!list_empty(&cfqq->fifo)) { 953 int fifo = cfq_cfqq_class_sync(cfqq); 954 955 crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next)); 956 rq = crq->request; 957 if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) { 958 cfq_mark_cfqq_fifo_expire(cfqq); 959 return crq; 960 } 961 } 962 963 return NULL; 964} 965 966/* 967 * Scale schedule slice based on io priority. Use the sync time slice only 968 * if a queue is marked sync and has sync io queued. A sync queue with async 969 * io only, should not get full sync slice length. 970 */ 971static inline int 972cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) 973{ 974 const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)]; 975 976 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR); 977 978 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - cfqq->ioprio)); 979} 980 981static inline void 982cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) 983{ 984 cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies; 985} 986 987static inline int 988cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq) 989{ 990 const int base_rq = cfqd->cfq_slice_async_rq; 991 992 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR); 993 994 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio)); 995} 996 997/* 998 * get next queue for service 999 */ 1000static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd) 1001{ 1002 unsigned long now = jiffies; 1003 struct cfq_queue *cfqq; 1004 1005 cfqq = cfqd->active_queue; 1006 if (!cfqq) 1007 goto new_queue; 1008 1009 if (cfq_cfqq_expired(cfqq)) 1010 goto new_queue; 1011 1012 /* 1013 * slice has expired 1014 */ 1015 if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end)) 1016 goto expire; 1017 1018 /* 1019 * if queue has requests, dispatch one. if not, check if 1020 * enough slice is left to wait for one 1021 */ 1022 if (!RB_EMPTY(&cfqq->sort_list)) 1023 goto keep_queue; 1024 else if (cfq_cfqq_class_sync(cfqq) && 1025 time_before(now, cfqq->slice_end)) { 1026 if (cfq_arm_slice_timer(cfqd, cfqq)) 1027 return NULL; 1028 } 1029 1030expire: 1031 cfq_slice_expired(cfqd, 0); 1032new_queue: 1033 cfqq = cfq_set_active_queue(cfqd); 1034keep_queue: 1035 return cfqq; 1036} 1037 1038static int 1039__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1040 int max_dispatch) 1041{ 1042 int dispatched = 0; 1043 1044 BUG_ON(RB_EMPTY(&cfqq->sort_list)); 1045 1046 do { 1047 struct cfq_rq *crq; 1048 1049 /* 1050 * follow expired path, else get first next available 1051 */ 1052 if ((crq = cfq_check_fifo(cfqq)) == NULL) 1053 crq = cfqq->next_crq; 1054 1055 /* 1056 * finally, insert request into driver dispatch list 1057 */ 1058 cfq_dispatch_insert(cfqd->queue, crq); 1059 1060 cfqd->dispatch_slice++; 1061 dispatched++; 1062 1063 if (!cfqd->active_cic) { 1064 atomic_inc(&crq->io_context->ioc->refcount); 1065 cfqd->active_cic = crq->io_context; 1066 } 1067 1068 if (RB_EMPTY(&cfqq->sort_list)) 1069 break; 1070 1071 } while (dispatched < max_dispatch); 1072 1073 /* 1074 * if slice end isn't set yet, set it. if at least one request was 1075 * sync, use the sync time slice value 1076 */ 1077 if (!cfqq->slice_end) 1078 cfq_set_prio_slice(cfqd, cfqq); 1079 1080 /* 1081 * expire an async queue immediately if it has used up its slice. idle 1082 * queue always expire after 1 dispatch round. 1083 */ 1084 if ((!cfq_cfqq_sync(cfqq) && 1085 cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) || 1086 cfq_class_idle(cfqq)) 1087 cfq_slice_expired(cfqd, 0); 1088 1089 return dispatched; 1090} 1091 1092static int 1093cfq_forced_dispatch_cfqqs(struct list_head *list) 1094{ 1095 int dispatched = 0; 1096 struct cfq_queue *cfqq, *next; 1097 struct cfq_rq *crq; 1098 1099 list_for_each_entry_safe(cfqq, next, list, cfq_list) { 1100 while ((crq = cfqq->next_crq)) { 1101 cfq_dispatch_insert(cfqq->cfqd->queue, crq); 1102 dispatched++; 1103 } 1104 BUG_ON(!list_empty(&cfqq->fifo)); 1105 } 1106 return dispatched; 1107} 1108 1109static int 1110cfq_forced_dispatch(struct cfq_data *cfqd) 1111{ 1112 int i, dispatched = 0; 1113 1114 for (i = 0; i < CFQ_PRIO_LISTS; i++) 1115 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->rr_list[i]); 1116 1117 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->busy_rr); 1118 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->cur_rr); 1119 dispatched += cfq_forced_dispatch_cfqqs(&cfqd->idle_rr); 1120 1121 cfq_slice_expired(cfqd, 0); 1122 1123 BUG_ON(cfqd->busy_queues); 1124 1125 return dispatched; 1126} 1127 1128static int 1129cfq_dispatch_requests(request_queue_t *q, int force) 1130{ 1131 struct cfq_data *cfqd = q->elevator->elevator_data; 1132 struct cfq_queue *cfqq; 1133 1134 if (!cfqd->busy_queues) 1135 return 0; 1136 1137 if (unlikely(force)) 1138 return cfq_forced_dispatch(cfqd); 1139 1140 cfqq = cfq_select_queue(cfqd); 1141 if (cfqq) { 1142 int max_dispatch; 1143 1144 /* 1145 * if idle window is disabled, allow queue buildup 1146 */ 1147 if (!cfq_cfqq_idle_window(cfqq) && 1148 cfqd->rq_in_driver >= cfqd->cfq_max_depth) 1149 return 0; 1150 1151 cfq_clear_cfqq_must_dispatch(cfqq); 1152 cfq_clear_cfqq_wait_request(cfqq); 1153 del_timer(&cfqd->idle_slice_timer); 1154 1155 max_dispatch = cfqd->cfq_quantum; 1156 if (cfq_class_idle(cfqq)) 1157 max_dispatch = 1; 1158 1159 return __cfq_dispatch_requests(cfqd, cfqq, max_dispatch); 1160 } 1161 1162 return 0; 1163} 1164 1165/* 1166 * task holds one reference to the queue, dropped when task exits. each crq 1167 * in-flight on this queue also holds a reference, dropped when crq is freed. 1168 * 1169 * queue lock must be held here. 1170 */ 1171static void cfq_put_queue(struct cfq_queue *cfqq) 1172{ 1173 struct cfq_data *cfqd = cfqq->cfqd; 1174 1175 BUG_ON(atomic_read(&cfqq->ref) <= 0); 1176 1177 if (!atomic_dec_and_test(&cfqq->ref)) 1178 return; 1179 1180 BUG_ON(rb_first(&cfqq->sort_list)); 1181 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]); 1182 BUG_ON(cfq_cfqq_on_rr(cfqq)); 1183 1184 if (unlikely(cfqd->active_queue == cfqq)) { 1185 __cfq_slice_expired(cfqd, cfqq, 0); 1186 cfq_schedule_dispatch(cfqd); 1187 } 1188 1189 cfq_put_cfqd(cfqq->cfqd); 1190 1191 /* 1192 * it's on the empty list and still hashed 1193 */ 1194 list_del(&cfqq->cfq_list); 1195 hlist_del(&cfqq->cfq_hash); 1196 kmem_cache_free(cfq_pool, cfqq); 1197} 1198 1199static inline struct cfq_queue * 1200__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio, 1201 const int hashval) 1202{ 1203 struct hlist_head *hash_list = &cfqd->cfq_hash[hashval]; 1204 struct hlist_node *entry, *next; 1205 1206 hlist_for_each_safe(entry, next, hash_list) { 1207 struct cfq_queue *__cfqq = list_entry_qhash(entry); 1208 const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->ioprio_class, __cfqq->ioprio); 1209 1210 if (__cfqq->key == key && (__p == prio || prio == CFQ_KEY_ANY)) 1211 return __cfqq; 1212 } 1213 1214 return NULL; 1215} 1216 1217static struct cfq_queue * 1218cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio) 1219{ 1220 return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT)); 1221} 1222 1223static void cfq_free_io_context(struct cfq_io_context *cic) 1224{ 1225 struct cfq_io_context *__cic; 1226 struct list_head *entry, *next; 1227 1228 list_for_each_safe(entry, next, &cic->list) { 1229 __cic = list_entry(entry, struct cfq_io_context, list); 1230 kmem_cache_free(cfq_ioc_pool, __cic); 1231 } 1232 1233 kmem_cache_free(cfq_ioc_pool, cic); 1234} 1235 1236/* 1237 * Called with interrupts disabled 1238 */ 1239static void cfq_exit_single_io_context(struct cfq_io_context *cic) 1240{ 1241 struct cfq_data *cfqd = cic->cfqq->cfqd; 1242 request_queue_t *q = cfqd->queue; 1243 1244 WARN_ON(!irqs_disabled()); 1245 1246 spin_lock(q->queue_lock); 1247 1248 if (unlikely(cic->cfqq == cfqd->active_queue)) { 1249 __cfq_slice_expired(cfqd, cic->cfqq, 0); 1250 cfq_schedule_dispatch(cfqd); 1251 } 1252 1253 cfq_put_queue(cic->cfqq); 1254 cic->cfqq = NULL; 1255 spin_unlock(q->queue_lock); 1256} 1257 1258/* 1259 * Another task may update the task cic list, if it is doing a queue lookup 1260 * on its behalf. cfq_cic_lock excludes such concurrent updates 1261 */ 1262static void cfq_exit_io_context(struct cfq_io_context *cic) 1263{ 1264 struct cfq_io_context *__cic; 1265 struct list_head *entry; 1266 unsigned long flags; 1267 1268 local_irq_save(flags); 1269 1270 /* 1271 * put the reference this task is holding to the various queues 1272 */ 1273 list_for_each(entry, &cic->list) { 1274 __cic = list_entry(entry, struct cfq_io_context, list); 1275 cfq_exit_single_io_context(__cic); 1276 } 1277 1278 cfq_exit_single_io_context(cic); 1279 local_irq_restore(flags); 1280} 1281 1282static struct cfq_io_context * 1283cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask) 1284{ 1285 struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask); 1286 1287 if (cic) { 1288 INIT_LIST_HEAD(&cic->list); 1289 cic->cfqq = NULL; 1290 cic->key = NULL; 1291 cic->last_end_request = jiffies; 1292 cic->ttime_total = 0; 1293 cic->ttime_samples = 0; 1294 cic->ttime_mean = 0; 1295 cic->dtor = cfq_free_io_context; 1296 cic->exit = cfq_exit_io_context; 1297 } 1298 1299 return cic; 1300} 1301 1302static void cfq_init_prio_data(struct cfq_queue *cfqq) 1303{ 1304 struct task_struct *tsk = current; 1305 int ioprio_class; 1306 1307 if (!cfq_cfqq_prio_changed(cfqq)) 1308 return; 1309 1310 ioprio_class = IOPRIO_PRIO_CLASS(tsk->ioprio); 1311 switch (ioprio_class) { 1312 default: 1313 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class); 1314 case IOPRIO_CLASS_NONE: 1315 /* 1316 * no prio set, place us in the middle of the BE classes 1317 */ 1318 cfqq->ioprio = task_nice_ioprio(tsk); 1319 cfqq->ioprio_class = IOPRIO_CLASS_BE; 1320 break; 1321 case IOPRIO_CLASS_RT: 1322 cfqq->ioprio = task_ioprio(tsk); 1323 cfqq->ioprio_class = IOPRIO_CLASS_RT; 1324 break; 1325 case IOPRIO_CLASS_BE: 1326 cfqq->ioprio = task_ioprio(tsk); 1327 cfqq->ioprio_class = IOPRIO_CLASS_BE; 1328 break; 1329 case IOPRIO_CLASS_IDLE: 1330 cfqq->ioprio_class = IOPRIO_CLASS_IDLE; 1331 cfqq->ioprio = 7; 1332 cfq_clear_cfqq_idle_window(cfqq); 1333 break; 1334 } 1335 1336 /* 1337 * keep track of original prio settings in case we have to temporarily 1338 * elevate the priority of this queue 1339 */ 1340 cfqq->org_ioprio = cfqq->ioprio; 1341 cfqq->org_ioprio_class = cfqq->ioprio_class; 1342 1343 if (cfq_cfqq_on_rr(cfqq)) 1344 cfq_resort_rr_list(cfqq, 0); 1345 1346 cfq_clear_cfqq_prio_changed(cfqq); 1347} 1348 1349static inline void changed_ioprio(struct cfq_queue *cfqq) 1350{ 1351 if (cfqq) { 1352 struct cfq_data *cfqd = cfqq->cfqd; 1353 1354 spin_lock(cfqd->queue->queue_lock); 1355 cfq_mark_cfqq_prio_changed(cfqq); 1356 cfq_init_prio_data(cfqq); 1357 spin_unlock(cfqd->queue->queue_lock); 1358 } 1359} 1360 1361/* 1362 * callback from sys_ioprio_set, irqs are disabled 1363 */ 1364static int cfq_ioc_set_ioprio(struct io_context *ioc, unsigned int ioprio) 1365{ 1366 struct cfq_io_context *cic = ioc->cic; 1367 1368 changed_ioprio(cic->cfqq); 1369 1370 list_for_each_entry(cic, &cic->list, list) 1371 changed_ioprio(cic->cfqq); 1372 1373 return 0; 1374} 1375 1376static struct cfq_queue * 1377cfq_get_queue(struct cfq_data *cfqd, unsigned int key, unsigned short ioprio, 1378 gfp_t gfp_mask) 1379{ 1380 const int hashval = hash_long(key, CFQ_QHASH_SHIFT); 1381 struct cfq_queue *cfqq, *new_cfqq = NULL; 1382 1383retry: 1384 cfqq = __cfq_find_cfq_hash(cfqd, key, ioprio, hashval); 1385 1386 if (!cfqq) { 1387 if (new_cfqq) { 1388 cfqq = new_cfqq; 1389 new_cfqq = NULL; 1390 } else if (gfp_mask & __GFP_WAIT) { 1391 spin_unlock_irq(cfqd->queue->queue_lock); 1392 new_cfqq = kmem_cache_alloc(cfq_pool, gfp_mask); 1393 spin_lock_irq(cfqd->queue->queue_lock); 1394 goto retry; 1395 } else { 1396 cfqq = kmem_cache_alloc(cfq_pool, gfp_mask); 1397 if (!cfqq) 1398 goto out; 1399 } 1400 1401 memset(cfqq, 0, sizeof(*cfqq)); 1402 1403 INIT_HLIST_NODE(&cfqq->cfq_hash); 1404 INIT_LIST_HEAD(&cfqq->cfq_list); 1405 RB_CLEAR_ROOT(&cfqq->sort_list); 1406 INIT_LIST_HEAD(&cfqq->fifo); 1407 1408 cfqq->key = key; 1409 hlist_add_head(&cfqq->cfq_hash, &cfqd->cfq_hash[hashval]); 1410 atomic_set(&cfqq->ref, 0); 1411 cfqq->cfqd = cfqd; 1412 atomic_inc(&cfqd->ref); 1413 cfqq->service_last = 0; 1414 /* 1415 * set ->slice_left to allow preemption for a new process 1416 */ 1417 cfqq->slice_left = 2 * cfqd->cfq_slice_idle; 1418 cfq_mark_cfqq_idle_window(cfqq); 1419 cfq_mark_cfqq_prio_changed(cfqq); 1420 cfq_init_prio_data(cfqq); 1421 } 1422 1423 if (new_cfqq) 1424 kmem_cache_free(cfq_pool, new_cfqq); 1425 1426 atomic_inc(&cfqq->ref); 1427out: 1428 WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq); 1429 return cfqq; 1430} 1431 1432/* 1433 * Setup general io context and cfq io context. There can be several cfq 1434 * io contexts per general io context, if this process is doing io to more 1435 * than one device managed by cfq. Note that caller is holding a reference to 1436 * cfqq, so we don't need to worry about it disappearing 1437 */ 1438static struct cfq_io_context * 1439cfq_get_io_context(struct cfq_data *cfqd, pid_t pid, gfp_t gfp_mask) 1440{ 1441 struct io_context *ioc = NULL; 1442 struct cfq_io_context *cic; 1443 1444 might_sleep_if(gfp_mask & __GFP_WAIT); 1445 1446 ioc = get_io_context(gfp_mask); 1447 if (!ioc) 1448 return NULL; 1449 1450 if ((cic = ioc->cic) == NULL) { 1451 cic = cfq_alloc_io_context(cfqd, gfp_mask); 1452 1453 if (cic == NULL) 1454 goto err; 1455 1456 /* 1457 * manually increment generic io_context usage count, it 1458 * cannot go away since we are already holding one ref to it 1459 */ 1460 ioc->cic = cic; 1461 ioc->set_ioprio = cfq_ioc_set_ioprio; 1462 cic->ioc = ioc; 1463 cic->key = cfqd; 1464 atomic_inc(&cfqd->ref); 1465 } else { 1466 struct cfq_io_context *__cic; 1467 1468 /* 1469 * the first cic on the list is actually the head itself 1470 */ 1471 if (cic->key == cfqd) 1472 goto out; 1473 1474 /* 1475 * cic exists, check if we already are there. linear search 1476 * should be ok here, the list will usually not be more than 1477 * 1 or a few entries long 1478 */ 1479 list_for_each_entry(__cic, &cic->list, list) { 1480 /* 1481 * this process is already holding a reference to 1482 * this queue, so no need to get one more 1483 */ 1484 if (__cic->key == cfqd) { 1485 cic = __cic; 1486 goto out; 1487 } 1488 } 1489 1490 /* 1491 * nope, process doesn't have a cic assoicated with this 1492 * cfqq yet. get a new one and add to list 1493 */ 1494 __cic = cfq_alloc_io_context(cfqd, gfp_mask); 1495 if (__cic == NULL) 1496 goto err; 1497 1498 __cic->ioc = ioc; 1499 __cic->key = cfqd; 1500 atomic_inc(&cfqd->ref); 1501 list_add(&__cic->list, &cic->list); 1502 cic = __cic; 1503 } 1504 1505out: 1506 return cic; 1507err: 1508 put_io_context(ioc); 1509 return NULL; 1510} 1511 1512static void 1513cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic) 1514{ 1515 unsigned long elapsed, ttime; 1516 1517 /* 1518 * if this context already has stuff queued, thinktime is from 1519 * last queue not last end 1520 */ 1521#if 0 1522 if (time_after(cic->last_end_request, cic->last_queue)) 1523 elapsed = jiffies - cic->last_end_request; 1524 else 1525 elapsed = jiffies - cic->last_queue; 1526#else 1527 elapsed = jiffies - cic->last_end_request; 1528#endif 1529 1530 ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle); 1531 1532 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8; 1533 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8; 1534 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples; 1535} 1536 1537#define sample_valid(samples) ((samples) > 80) 1538 1539/* 1540 * Disable idle window if the process thinks too long or seeks so much that 1541 * it doesn't matter 1542 */ 1543static void 1544cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1545 struct cfq_io_context *cic) 1546{ 1547 int enable_idle = cfq_cfqq_idle_window(cfqq); 1548 1549 if (!cic->ioc->task || !cfqd->cfq_slice_idle) 1550 enable_idle = 0; 1551 else if (sample_valid(cic->ttime_samples)) { 1552 if (cic->ttime_mean > cfqd->cfq_slice_idle) 1553 enable_idle = 0; 1554 else 1555 enable_idle = 1; 1556 } 1557 1558 if (enable_idle) 1559 cfq_mark_cfqq_idle_window(cfqq); 1560 else 1561 cfq_clear_cfqq_idle_window(cfqq); 1562} 1563 1564 1565/* 1566 * Check if new_cfqq should preempt the currently active queue. Return 0 for 1567 * no or if we aren't sure, a 1 will cause a preempt. 1568 */ 1569static int 1570cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq, 1571 struct cfq_rq *crq) 1572{ 1573 struct cfq_queue *cfqq = cfqd->active_queue; 1574 1575 if (cfq_class_idle(new_cfqq)) 1576 return 0; 1577 1578 if (!cfqq) 1579 return 1; 1580 1581 if (cfq_class_idle(cfqq)) 1582 return 1; 1583 if (!cfq_cfqq_wait_request(new_cfqq)) 1584 return 0; 1585 /* 1586 * if it doesn't have slice left, forget it 1587 */ 1588 if (new_cfqq->slice_left < cfqd->cfq_slice_idle) 1589 return 0; 1590 if (cfq_crq_is_sync(crq) && !cfq_cfqq_sync(cfqq)) 1591 return 1; 1592 1593 return 0; 1594} 1595 1596/* 1597 * cfqq preempts the active queue. if we allowed preempt with no slice left, 1598 * let it have half of its nominal slice. 1599 */ 1600static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1601{ 1602 struct cfq_queue *__cfqq, *next; 1603 1604 list_for_each_entry_safe(__cfqq, next, &cfqd->cur_rr, cfq_list) 1605 cfq_resort_rr_list(__cfqq, 1); 1606 1607 if (!cfqq->slice_left) 1608 cfqq->slice_left = cfq_prio_to_slice(cfqd, cfqq) / 2; 1609 1610 cfqq->slice_end = cfqq->slice_left + jiffies; 1611 __cfq_slice_expired(cfqd, cfqq, 1); 1612 __cfq_set_active_queue(cfqd, cfqq); 1613} 1614 1615/* 1616 * should really be a ll_rw_blk.c helper 1617 */ 1618static void cfq_start_queueing(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1619{ 1620 request_queue_t *q = cfqd->queue; 1621 1622 if (!blk_queue_plugged(q)) 1623 q->request_fn(q); 1624 else 1625 __generic_unplug_device(q); 1626} 1627 1628/* 1629 * Called when a new fs request (crq) is added (to cfqq). Check if there's 1630 * something we should do about it 1631 */ 1632static void 1633cfq_crq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1634 struct cfq_rq *crq) 1635{ 1636 struct cfq_io_context *cic; 1637 1638 cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq); 1639 1640 /* 1641 * we never wait for an async request and we don't allow preemption 1642 * of an async request. so just return early 1643 */ 1644 if (!cfq_crq_is_sync(crq)) 1645 return; 1646 1647 cic = crq->io_context; 1648 1649 cfq_update_io_thinktime(cfqd, cic); 1650 cfq_update_idle_window(cfqd, cfqq, cic); 1651 1652 cic->last_queue = jiffies; 1653 1654 if (cfqq == cfqd->active_queue) { 1655 /* 1656 * if we are waiting for a request for this queue, let it rip 1657 * immediately and flag that we must not expire this queue 1658 * just now 1659 */ 1660 if (cfq_cfqq_wait_request(cfqq)) { 1661 cfq_mark_cfqq_must_dispatch(cfqq); 1662 del_timer(&cfqd->idle_slice_timer); 1663 cfq_start_queueing(cfqd, cfqq); 1664 } 1665 } else if (cfq_should_preempt(cfqd, cfqq, crq)) { 1666 /* 1667 * not the active queue - expire current slice if it is 1668 * idle and has expired it's mean thinktime or this new queue 1669 * has some old slice time left and is of higher priority 1670 */ 1671 cfq_preempt_queue(cfqd, cfqq); 1672 cfq_mark_cfqq_must_dispatch(cfqq); 1673 cfq_start_queueing(cfqd, cfqq); 1674 } 1675} 1676 1677static void cfq_insert_request(request_queue_t *q, struct request *rq) 1678{ 1679 struct cfq_data *cfqd = q->elevator->elevator_data; 1680 struct cfq_rq *crq = RQ_DATA(rq); 1681 struct cfq_queue *cfqq = crq->cfq_queue; 1682 1683 cfq_init_prio_data(cfqq); 1684 1685 cfq_add_crq_rb(crq); 1686 1687 list_add_tail(&rq->queuelist, &cfqq->fifo); 1688 1689 if (rq_mergeable(rq)) 1690 cfq_add_crq_hash(cfqd, crq); 1691 1692 cfq_crq_enqueued(cfqd, cfqq, crq); 1693} 1694 1695static void cfq_completed_request(request_queue_t *q, struct request *rq) 1696{ 1697 struct cfq_rq *crq = RQ_DATA(rq); 1698 struct cfq_queue *cfqq = crq->cfq_queue; 1699 struct cfq_data *cfqd = cfqq->cfqd; 1700 const int sync = cfq_crq_is_sync(crq); 1701 unsigned long now; 1702 1703 now = jiffies; 1704 1705 WARN_ON(!cfqd->rq_in_driver); 1706 WARN_ON(!cfqq->on_dispatch[sync]); 1707 cfqd->rq_in_driver--; 1708 cfqq->on_dispatch[sync]--; 1709 1710 if (!cfq_class_idle(cfqq)) 1711 cfqd->last_end_request = now; 1712 1713 if (!cfq_cfqq_dispatched(cfqq)) { 1714 if (cfq_cfqq_on_rr(cfqq)) { 1715 cfqq->service_last = now; 1716 cfq_resort_rr_list(cfqq, 0); 1717 } 1718 if (cfq_cfqq_expired(cfqq)) { 1719 __cfq_slice_expired(cfqd, cfqq, 0); 1720 cfq_schedule_dispatch(cfqd); 1721 } 1722 } 1723 1724 if (cfq_crq_is_sync(crq)) 1725 crq->io_context->last_end_request = now; 1726} 1727 1728static struct request * 1729cfq_former_request(request_queue_t *q, struct request *rq) 1730{ 1731 struct cfq_rq *crq = RQ_DATA(rq); 1732 struct rb_node *rbprev = rb_prev(&crq->rb_node); 1733 1734 if (rbprev) 1735 return rb_entry_crq(rbprev)->request; 1736 1737 return NULL; 1738} 1739 1740static struct request * 1741cfq_latter_request(request_queue_t *q, struct request *rq) 1742{ 1743 struct cfq_rq *crq = RQ_DATA(rq); 1744 struct rb_node *rbnext = rb_next(&crq->rb_node); 1745 1746 if (rbnext) 1747 return rb_entry_crq(rbnext)->request; 1748 1749 return NULL; 1750} 1751 1752/* 1753 * we temporarily boost lower priority queues if they are holding fs exclusive 1754 * resources. they are boosted to normal prio (CLASS_BE/4) 1755 */ 1756static void cfq_prio_boost(struct cfq_queue *cfqq) 1757{ 1758 const int ioprio_class = cfqq->ioprio_class; 1759 const int ioprio = cfqq->ioprio; 1760 1761 if (has_fs_excl()) { 1762 /* 1763 * boost idle prio on transactions that would lock out other 1764 * users of the filesystem 1765 */ 1766 if (cfq_class_idle(cfqq)) 1767 cfqq->ioprio_class = IOPRIO_CLASS_BE; 1768 if (cfqq->ioprio > IOPRIO_NORM) 1769 cfqq->ioprio = IOPRIO_NORM; 1770 } else { 1771 /* 1772 * check if we need to unboost the queue 1773 */ 1774 if (cfqq->ioprio_class != cfqq->org_ioprio_class) 1775 cfqq->ioprio_class = cfqq->org_ioprio_class; 1776 if (cfqq->ioprio != cfqq->org_ioprio) 1777 cfqq->ioprio = cfqq->org_ioprio; 1778 } 1779 1780 /* 1781 * refile between round-robin lists if we moved the priority class 1782 */ 1783 if ((ioprio_class != cfqq->ioprio_class || ioprio != cfqq->ioprio) && 1784 cfq_cfqq_on_rr(cfqq)) 1785 cfq_resort_rr_list(cfqq, 0); 1786} 1787 1788static inline pid_t cfq_queue_pid(struct task_struct *task, int rw) 1789{ 1790 if (rw == READ || process_sync(task)) 1791 return task->pid; 1792 1793 return CFQ_KEY_ASYNC; 1794} 1795 1796static inline int 1797__cfq_may_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1798 struct task_struct *task, int rw) 1799{ 1800#if 1 1801 if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) && 1802 !cfq_cfqq_must_alloc_slice(cfqq)) { 1803 cfq_mark_cfqq_must_alloc_slice(cfqq); 1804 return ELV_MQUEUE_MUST; 1805 } 1806 1807 return ELV_MQUEUE_MAY; 1808#else 1809 if (!cfqq || task->flags & PF_MEMALLOC) 1810 return ELV_MQUEUE_MAY; 1811 if (!cfqq->allocated[rw] || cfq_cfqq_must_alloc(cfqq)) { 1812 if (cfq_cfqq_wait_request(cfqq)) 1813 return ELV_MQUEUE_MUST; 1814 1815 /* 1816 * only allow 1 ELV_MQUEUE_MUST per slice, otherwise we 1817 * can quickly flood the queue with writes from a single task 1818 */ 1819 if (rw == READ || !cfq_cfqq_must_alloc_slice(cfqq)) { 1820 cfq_mark_cfqq_must_alloc_slice(cfqq); 1821 return ELV_MQUEUE_MUST; 1822 } 1823 1824 return ELV_MQUEUE_MAY; 1825 } 1826 if (cfq_class_idle(cfqq)) 1827 return ELV_MQUEUE_NO; 1828 if (cfqq->allocated[rw] >= cfqd->max_queued) { 1829 struct io_context *ioc = get_io_context(GFP_ATOMIC); 1830 int ret = ELV_MQUEUE_NO; 1831 1832 if (ioc && ioc->nr_batch_requests) 1833 ret = ELV_MQUEUE_MAY; 1834 1835 put_io_context(ioc); 1836 return ret; 1837 } 1838 1839 return ELV_MQUEUE_MAY; 1840#endif 1841} 1842 1843static int cfq_may_queue(request_queue_t *q, int rw, struct bio *bio) 1844{ 1845 struct cfq_data *cfqd = q->elevator->elevator_data; 1846 struct task_struct *tsk = current; 1847 struct cfq_queue *cfqq; 1848 1849 /* 1850 * don't force setup of a queue from here, as a call to may_queue 1851 * does not necessarily imply that a request actually will be queued. 1852 * so just lookup a possibly existing queue, or return 'may queue' 1853 * if that fails 1854 */ 1855 cfqq = cfq_find_cfq_hash(cfqd, cfq_queue_pid(tsk, rw), tsk->ioprio); 1856 if (cfqq) { 1857 cfq_init_prio_data(cfqq); 1858 cfq_prio_boost(cfqq); 1859 1860 return __cfq_may_queue(cfqd, cfqq, tsk, rw); 1861 } 1862 1863 return ELV_MQUEUE_MAY; 1864} 1865 1866static void cfq_check_waiters(request_queue_t *q, struct cfq_queue *cfqq) 1867{ 1868 struct cfq_data *cfqd = q->elevator->elevator_data; 1869 struct request_list *rl = &q->rq; 1870 1871 if (cfqq->allocated[READ] <= cfqd->max_queued || cfqd->rq_starved) { 1872 smp_mb(); 1873 if (waitqueue_active(&rl->wait[READ])) 1874 wake_up(&rl->wait[READ]); 1875 } 1876 1877 if (cfqq->allocated[WRITE] <= cfqd->max_queued || cfqd->rq_starved) { 1878 smp_mb(); 1879 if (waitqueue_active(&rl->wait[WRITE])) 1880 wake_up(&rl->wait[WRITE]); 1881 } 1882} 1883 1884/* 1885 * queue lock held here 1886 */ 1887static void cfq_put_request(request_queue_t *q, struct request *rq) 1888{ 1889 struct cfq_data *cfqd = q->elevator->elevator_data; 1890 struct cfq_rq *crq = RQ_DATA(rq); 1891 1892 if (crq) { 1893 struct cfq_queue *cfqq = crq->cfq_queue; 1894 const int rw = rq_data_dir(rq); 1895 1896 BUG_ON(!cfqq->allocated[rw]); 1897 cfqq->allocated[rw]--; 1898 1899 put_io_context(crq->io_context->ioc); 1900 1901 mempool_free(crq, cfqd->crq_pool); 1902 rq->elevator_private = NULL; 1903 1904 cfq_check_waiters(q, cfqq); 1905 cfq_put_queue(cfqq); 1906 } 1907} 1908 1909/* 1910 * Allocate cfq data structures associated with this request. 1911 */ 1912static int 1913cfq_set_request(request_queue_t *q, struct request *rq, struct bio *bio, 1914 gfp_t gfp_mask) 1915{ 1916 struct cfq_data *cfqd = q->elevator->elevator_data; 1917 struct task_struct *tsk = current; 1918 struct cfq_io_context *cic; 1919 const int rw = rq_data_dir(rq); 1920 pid_t key = cfq_queue_pid(tsk, rw); 1921 struct cfq_queue *cfqq; 1922 struct cfq_rq *crq; 1923 unsigned long flags; 1924 1925 might_sleep_if(gfp_mask & __GFP_WAIT); 1926 1927 cic = cfq_get_io_context(cfqd, key, gfp_mask); 1928 1929 spin_lock_irqsave(q->queue_lock, flags); 1930 1931 if (!cic) 1932 goto queue_fail; 1933 1934 if (!cic->cfqq) { 1935 cfqq = cfq_get_queue(cfqd, key, tsk->ioprio, gfp_mask); 1936 if (!cfqq) 1937 goto queue_fail; 1938 1939 cic->cfqq = cfqq; 1940 } else 1941 cfqq = cic->cfqq; 1942 1943 cfqq->allocated[rw]++; 1944 cfq_clear_cfqq_must_alloc(cfqq); 1945 cfqd->rq_starved = 0; 1946 atomic_inc(&cfqq->ref); 1947 spin_unlock_irqrestore(q->queue_lock, flags); 1948 1949 crq = mempool_alloc(cfqd->crq_pool, gfp_mask); 1950 if (crq) { 1951 RB_CLEAR(&crq->rb_node); 1952 crq->rb_key = 0; 1953 crq->request = rq; 1954 INIT_HLIST_NODE(&crq->hash); 1955 crq->cfq_queue = cfqq; 1956 crq->io_context = cic; 1957 1958 if (rw == READ || process_sync(tsk)) 1959 cfq_mark_crq_is_sync(crq); 1960 else 1961 cfq_clear_crq_is_sync(crq); 1962 1963 rq->elevator_private = crq; 1964 return 0; 1965 } 1966 1967 spin_lock_irqsave(q->queue_lock, flags); 1968 cfqq->allocated[rw]--; 1969 if (!(cfqq->allocated[0] + cfqq->allocated[1])) 1970 cfq_mark_cfqq_must_alloc(cfqq); 1971 cfq_put_queue(cfqq); 1972queue_fail: 1973 if (cic) 1974 put_io_context(cic->ioc); 1975 /* 1976 * mark us rq allocation starved. we need to kickstart the process 1977 * ourselves if there are no pending requests that can do it for us. 1978 * that would be an extremely rare OOM situation 1979 */ 1980 cfqd->rq_starved = 1; 1981 cfq_schedule_dispatch(cfqd); 1982 spin_unlock_irqrestore(q->queue_lock, flags); 1983 return 1; 1984} 1985 1986static void cfq_kick_queue(void *data) 1987{ 1988 request_queue_t *q = data; 1989 struct cfq_data *cfqd = q->elevator->elevator_data; 1990 unsigned long flags; 1991 1992 spin_lock_irqsave(q->queue_lock, flags); 1993 1994 if (cfqd->rq_starved) { 1995 struct request_list *rl = &q->rq; 1996 1997 /* 1998 * we aren't guaranteed to get a request after this, but we 1999 * have to be opportunistic 2000 */ 2001 smp_mb(); 2002 if (waitqueue_active(&rl->wait[READ])) 2003 wake_up(&rl->wait[READ]); 2004 if (waitqueue_active(&rl->wait[WRITE])) 2005 wake_up(&rl->wait[WRITE]); 2006 } 2007 2008 blk_remove_plug(q); 2009 q->request_fn(q); 2010 spin_unlock_irqrestore(q->queue_lock, flags); 2011} 2012 2013/* 2014 * Timer running if the active_queue is currently idling inside its time slice 2015 */ 2016static void cfq_idle_slice_timer(unsigned long data) 2017{ 2018 struct cfq_data *cfqd = (struct cfq_data *) data; 2019 struct cfq_queue *cfqq; 2020 unsigned long flags; 2021 2022 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 2023 2024 if ((cfqq = cfqd->active_queue) != NULL) { 2025 unsigned long now = jiffies; 2026 2027 /* 2028 * expired 2029 */ 2030 if (time_after(now, cfqq->slice_end)) 2031 goto expire; 2032 2033 /* 2034 * only expire and reinvoke request handler, if there are 2035 * other queues with pending requests 2036 */ 2037 if (!cfqd->busy_queues) { 2038 cfqd->idle_slice_timer.expires = min(now + cfqd->cfq_slice_idle, cfqq->slice_end); 2039 add_timer(&cfqd->idle_slice_timer); 2040 goto out_cont; 2041 } 2042 2043 /* 2044 * not expired and it has a request pending, let it dispatch 2045 */ 2046 if (!RB_EMPTY(&cfqq->sort_list)) { 2047 cfq_mark_cfqq_must_dispatch(cfqq); 2048 goto out_kick; 2049 } 2050 } 2051expire: 2052 cfq_slice_expired(cfqd, 0); 2053out_kick: 2054 cfq_schedule_dispatch(cfqd); 2055out_cont: 2056 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 2057} 2058 2059/* 2060 * Timer running if an idle class queue is waiting for service 2061 */ 2062static void cfq_idle_class_timer(unsigned long data) 2063{ 2064 struct cfq_data *cfqd = (struct cfq_data *) data; 2065 unsigned long flags, end; 2066 2067 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 2068 2069 /* 2070 * race with a non-idle queue, reset timer 2071 */ 2072 end = cfqd->last_end_request + CFQ_IDLE_GRACE; 2073 if (!time_after_eq(jiffies, end)) { 2074 cfqd->idle_class_timer.expires = end; 2075 add_timer(&cfqd->idle_class_timer); 2076 } else 2077 cfq_schedule_dispatch(cfqd); 2078 2079 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 2080} 2081 2082static void cfq_shutdown_timer_wq(struct cfq_data *cfqd) 2083{ 2084 del_timer_sync(&cfqd->idle_slice_timer); 2085 del_timer_sync(&cfqd->idle_class_timer); 2086 blk_sync_queue(cfqd->queue); 2087} 2088 2089static void cfq_put_cfqd(struct cfq_data *cfqd) 2090{ 2091 request_queue_t *q = cfqd->queue; 2092 2093 if (!atomic_dec_and_test(&cfqd->ref)) 2094 return; 2095 2096 cfq_shutdown_timer_wq(cfqd); 2097 blk_put_queue(q); 2098 2099 mempool_destroy(cfqd->crq_pool); 2100 kfree(cfqd->crq_hash); 2101 kfree(cfqd->cfq_hash); 2102 kfree(cfqd); 2103} 2104 2105static void cfq_exit_queue(elevator_t *e) 2106{ 2107 struct cfq_data *cfqd = e->elevator_data; 2108 2109 cfq_shutdown_timer_wq(cfqd); 2110 cfq_put_cfqd(cfqd); 2111} 2112 2113static int cfq_init_queue(request_queue_t *q, elevator_t *e) 2114{ 2115 struct cfq_data *cfqd; 2116 int i; 2117 2118 cfqd = kmalloc(sizeof(*cfqd), GFP_KERNEL); 2119 if (!cfqd) 2120 return -ENOMEM; 2121 2122 memset(cfqd, 0, sizeof(*cfqd)); 2123 2124 for (i = 0; i < CFQ_PRIO_LISTS; i++) 2125 INIT_LIST_HEAD(&cfqd->rr_list[i]); 2126 2127 INIT_LIST_HEAD(&cfqd->busy_rr); 2128 INIT_LIST_HEAD(&cfqd->cur_rr); 2129 INIT_LIST_HEAD(&cfqd->idle_rr); 2130 INIT_LIST_HEAD(&cfqd->empty_list); 2131 2132 cfqd->crq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_MHASH_ENTRIES, GFP_KERNEL); 2133 if (!cfqd->crq_hash) 2134 goto out_crqhash; 2135 2136 cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL); 2137 if (!cfqd->cfq_hash) 2138 goto out_cfqhash; 2139 2140 cfqd->crq_pool = mempool_create(BLKDEV_MIN_RQ, mempool_alloc_slab, mempool_free_slab, crq_pool); 2141 if (!cfqd->crq_pool) 2142 goto out_crqpool; 2143 2144 for (i = 0; i < CFQ_MHASH_ENTRIES; i++) 2145 INIT_HLIST_HEAD(&cfqd->crq_hash[i]); 2146 for (i = 0; i < CFQ_QHASH_ENTRIES; i++) 2147 INIT_HLIST_HEAD(&cfqd->cfq_hash[i]); 2148 2149 e->elevator_data = cfqd; 2150 2151 cfqd->queue = q; 2152 atomic_inc(&q->refcnt); 2153 2154 cfqd->max_queued = q->nr_requests / 4; 2155 q->nr_batching = cfq_queued; 2156 2157 init_timer(&cfqd->idle_slice_timer); 2158 cfqd->idle_slice_timer.function = cfq_idle_slice_timer; 2159 cfqd->idle_slice_timer.data = (unsigned long) cfqd; 2160 2161 init_timer(&cfqd->idle_class_timer); 2162 cfqd->idle_class_timer.function = cfq_idle_class_timer; 2163 cfqd->idle_class_timer.data = (unsigned long) cfqd; 2164 2165 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue, q); 2166 2167 atomic_set(&cfqd->ref, 1); 2168 2169 cfqd->cfq_queued = cfq_queued; 2170 cfqd->cfq_quantum = cfq_quantum; 2171 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0]; 2172 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1]; 2173 cfqd->cfq_back_max = cfq_back_max; 2174 cfqd->cfq_back_penalty = cfq_back_penalty; 2175 cfqd->cfq_slice[0] = cfq_slice_async; 2176 cfqd->cfq_slice[1] = cfq_slice_sync; 2177 cfqd->cfq_slice_async_rq = cfq_slice_async_rq; 2178 cfqd->cfq_slice_idle = cfq_slice_idle; 2179 cfqd->cfq_max_depth = cfq_max_depth; 2180 2181 return 0; 2182out_crqpool: 2183 kfree(cfqd->cfq_hash); 2184out_cfqhash: 2185 kfree(cfqd->crq_hash); 2186out_crqhash: 2187 kfree(cfqd); 2188 return -ENOMEM; 2189} 2190 2191static void cfq_slab_kill(void) 2192{ 2193 if (crq_pool) 2194 kmem_cache_destroy(crq_pool); 2195 if (cfq_pool) 2196 kmem_cache_destroy(cfq_pool); 2197 if (cfq_ioc_pool) 2198 kmem_cache_destroy(cfq_ioc_pool); 2199} 2200 2201static int __init cfq_slab_setup(void) 2202{ 2203 crq_pool = kmem_cache_create("crq_pool", sizeof(struct cfq_rq), 0, 0, 2204 NULL, NULL); 2205 if (!crq_pool) 2206 goto fail; 2207 2208 cfq_pool = kmem_cache_create("cfq_pool", sizeof(struct cfq_queue), 0, 0, 2209 NULL, NULL); 2210 if (!cfq_pool) 2211 goto fail; 2212 2213 cfq_ioc_pool = kmem_cache_create("cfq_ioc_pool", 2214 sizeof(struct cfq_io_context), 0, 0, NULL, NULL); 2215 if (!cfq_ioc_pool) 2216 goto fail; 2217 2218 return 0; 2219fail: 2220 cfq_slab_kill(); 2221 return -ENOMEM; 2222} 2223 2224/* 2225 * sysfs parts below --> 2226 */ 2227struct cfq_fs_entry { 2228 struct attribute attr; 2229 ssize_t (*show)(struct cfq_data *, char *); 2230 ssize_t (*store)(struct cfq_data *, const char *, size_t); 2231}; 2232 2233static ssize_t 2234cfq_var_show(unsigned int var, char *page) 2235{ 2236 return sprintf(page, "%d\n", var); 2237} 2238 2239static ssize_t 2240cfq_var_store(unsigned int *var, const char *page, size_t count) 2241{ 2242 char *p = (char *) page; 2243 2244 *var = simple_strtoul(p, &p, 10); 2245 return count; 2246} 2247 2248#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ 2249static ssize_t __FUNC(struct cfq_data *cfqd, char *page) \ 2250{ \ 2251 unsigned int __data = __VAR; \ 2252 if (__CONV) \ 2253 __data = jiffies_to_msecs(__data); \ 2254 return cfq_var_show(__data, (page)); \ 2255} 2256SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0); 2257SHOW_FUNCTION(cfq_queued_show, cfqd->cfq_queued, 0); 2258SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1); 2259SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1); 2260SHOW_FUNCTION(cfq_back_max_show, cfqd->cfq_back_max, 0); 2261SHOW_FUNCTION(cfq_back_penalty_show, cfqd->cfq_back_penalty, 0); 2262SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1); 2263SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1); 2264SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1); 2265SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0); 2266SHOW_FUNCTION(cfq_max_depth_show, cfqd->cfq_max_depth, 0); 2267#undef SHOW_FUNCTION 2268 2269#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ 2270static ssize_t __FUNC(struct cfq_data *cfqd, const char *page, size_t count) \ 2271{ \ 2272 unsigned int __data; \ 2273 int ret = cfq_var_store(&__data, (page), count); \ 2274 if (__data < (MIN)) \ 2275 __data = (MIN); \ 2276 else if (__data > (MAX)) \ 2277 __data = (MAX); \ 2278 if (__CONV) \ 2279 *(__PTR) = msecs_to_jiffies(__data); \ 2280 else \ 2281 *(__PTR) = __data; \ 2282 return ret; \ 2283} 2284STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0); 2285STORE_FUNCTION(cfq_queued_store, &cfqd->cfq_queued, 1, UINT_MAX, 0); 2286STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, UINT_MAX, 1); 2287STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1, UINT_MAX, 1); 2288STORE_FUNCTION(cfq_back_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0); 2289STORE_FUNCTION(cfq_back_penalty_store, &cfqd->cfq_back_penalty, 1, UINT_MAX, 0); 2290STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1); 2291STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1); 2292STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1); 2293STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1, UINT_MAX, 0); 2294STORE_FUNCTION(cfq_max_depth_store, &cfqd->cfq_max_depth, 1, UINT_MAX, 0); 2295#undef STORE_FUNCTION 2296 2297static struct cfq_fs_entry cfq_quantum_entry = { 2298 .attr = {.name = "quantum", .mode = S_IRUGO | S_IWUSR }, 2299 .show = cfq_quantum_show, 2300 .store = cfq_quantum_store, 2301}; 2302static struct cfq_fs_entry cfq_queued_entry = { 2303 .attr = {.name = "queued", .mode = S_IRUGO | S_IWUSR }, 2304 .show = cfq_queued_show, 2305 .store = cfq_queued_store, 2306}; 2307static struct cfq_fs_entry cfq_fifo_expire_sync_entry = { 2308 .attr = {.name = "fifo_expire_sync", .mode = S_IRUGO | S_IWUSR }, 2309 .show = cfq_fifo_expire_sync_show, 2310 .store = cfq_fifo_expire_sync_store, 2311}; 2312static struct cfq_fs_entry cfq_fifo_expire_async_entry = { 2313 .attr = {.name = "fifo_expire_async", .mode = S_IRUGO | S_IWUSR }, 2314 .show = cfq_fifo_expire_async_show, 2315 .store = cfq_fifo_expire_async_store, 2316}; 2317static struct cfq_fs_entry cfq_back_max_entry = { 2318 .attr = {.name = "back_seek_max", .mode = S_IRUGO | S_IWUSR }, 2319 .show = cfq_back_max_show, 2320 .store = cfq_back_max_store, 2321}; 2322static struct cfq_fs_entry cfq_back_penalty_entry = { 2323 .attr = {.name = "back_seek_penalty", .mode = S_IRUGO | S_IWUSR }, 2324 .show = cfq_back_penalty_show, 2325 .store = cfq_back_penalty_store, 2326}; 2327static struct cfq_fs_entry cfq_slice_sync_entry = { 2328 .attr = {.name = "slice_sync", .mode = S_IRUGO | S_IWUSR }, 2329 .show = cfq_slice_sync_show, 2330 .store = cfq_slice_sync_store, 2331}; 2332static struct cfq_fs_entry cfq_slice_async_entry = { 2333 .attr = {.name = "slice_async", .mode = S_IRUGO | S_IWUSR }, 2334 .show = cfq_slice_async_show, 2335 .store = cfq_slice_async_store, 2336}; 2337static struct cfq_fs_entry cfq_slice_async_rq_entry = { 2338 .attr = {.name = "slice_async_rq", .mode = S_IRUGO | S_IWUSR }, 2339 .show = cfq_slice_async_rq_show, 2340 .store = cfq_slice_async_rq_store, 2341}; 2342static struct cfq_fs_entry cfq_slice_idle_entry = { 2343 .attr = {.name = "slice_idle", .mode = S_IRUGO | S_IWUSR }, 2344 .show = cfq_slice_idle_show, 2345 .store = cfq_slice_idle_store, 2346}; 2347static struct cfq_fs_entry cfq_max_depth_entry = { 2348 .attr = {.name = "max_depth", .mode = S_IRUGO | S_IWUSR }, 2349 .show = cfq_max_depth_show, 2350 .store = cfq_max_depth_store, 2351}; 2352 2353static struct attribute *default_attrs[] = { 2354 &cfq_quantum_entry.attr, 2355 &cfq_queued_entry.attr, 2356 &cfq_fifo_expire_sync_entry.attr, 2357 &cfq_fifo_expire_async_entry.attr, 2358 &cfq_back_max_entry.attr, 2359 &cfq_back_penalty_entry.attr, 2360 &cfq_slice_sync_entry.attr, 2361 &cfq_slice_async_entry.attr, 2362 &cfq_slice_async_rq_entry.attr, 2363 &cfq_slice_idle_entry.attr, 2364 &cfq_max_depth_entry.attr, 2365 NULL, 2366}; 2367 2368#define to_cfq(atr) container_of((atr), struct cfq_fs_entry, attr) 2369 2370static ssize_t 2371cfq_attr_show(struct kobject *kobj, struct attribute *attr, char *page) 2372{ 2373 elevator_t *e = container_of(kobj, elevator_t, kobj); 2374 struct cfq_fs_entry *entry = to_cfq(attr); 2375 2376 if (!entry->show) 2377 return -EIO; 2378 2379 return entry->show(e->elevator_data, page); 2380} 2381 2382static ssize_t 2383cfq_attr_store(struct kobject *kobj, struct attribute *attr, 2384 const char *page, size_t length) 2385{ 2386 elevator_t *e = container_of(kobj, elevator_t, kobj); 2387 struct cfq_fs_entry *entry = to_cfq(attr); 2388 2389 if (!entry->store) 2390 return -EIO; 2391 2392 return entry->store(e->elevator_data, page, length); 2393} 2394 2395static struct sysfs_ops cfq_sysfs_ops = { 2396 .show = cfq_attr_show, 2397 .store = cfq_attr_store, 2398}; 2399 2400static struct kobj_type cfq_ktype = { 2401 .sysfs_ops = &cfq_sysfs_ops, 2402 .default_attrs = default_attrs, 2403}; 2404 2405static struct elevator_type iosched_cfq = { 2406 .ops = { 2407 .elevator_merge_fn = cfq_merge, 2408 .elevator_merged_fn = cfq_merged_request, 2409 .elevator_merge_req_fn = cfq_merged_requests, 2410 .elevator_dispatch_fn = cfq_dispatch_requests, 2411 .elevator_add_req_fn = cfq_insert_request, 2412 .elevator_activate_req_fn = cfq_activate_request, 2413 .elevator_deactivate_req_fn = cfq_deactivate_request, 2414 .elevator_queue_empty_fn = cfq_queue_empty, 2415 .elevator_completed_req_fn = cfq_completed_request, 2416 .elevator_former_req_fn = cfq_former_request, 2417 .elevator_latter_req_fn = cfq_latter_request, 2418 .elevator_set_req_fn = cfq_set_request, 2419 .elevator_put_req_fn = cfq_put_request, 2420 .elevator_may_queue_fn = cfq_may_queue, 2421 .elevator_init_fn = cfq_init_queue, 2422 .elevator_exit_fn = cfq_exit_queue, 2423 }, 2424 .elevator_ktype = &cfq_ktype, 2425 .elevator_name = "cfq", 2426 .elevator_owner = THIS_MODULE, 2427}; 2428 2429static int __init cfq_init(void) 2430{ 2431 int ret; 2432 2433 /* 2434 * could be 0 on HZ < 1000 setups 2435 */ 2436 if (!cfq_slice_async) 2437 cfq_slice_async = 1; 2438 if (!cfq_slice_idle) 2439 cfq_slice_idle = 1; 2440 2441 if (cfq_slab_setup()) 2442 return -ENOMEM; 2443 2444 ret = elv_register(&iosched_cfq); 2445 if (ret) 2446 cfq_slab_kill(); 2447 2448 return ret; 2449} 2450 2451static void __exit cfq_exit(void) 2452{ 2453 elv_unregister(&iosched_cfq); 2454 cfq_slab_kill(); 2455} 2456 2457module_init(cfq_init); 2458module_exit(cfq_exit); 2459 2460MODULE_AUTHOR("Jens Axboe"); 2461MODULE_LICENSE("GPL"); 2462MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler"); 2463