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