cfq-iosched.c revision 73e9ffdd0cc8159f876d5e29ecf2d9c1bfca544f
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/jiffies.h> 13#include <linux/rbtree.h> 14#include <linux/ioprio.h> 15#include <linux/blktrace_api.h> 16#include "blk-cgroup.h" 17 18/* 19 * tunables 20 */ 21/* max queue in one round of service */ 22static const int cfq_quantum = 8; 23static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 }; 24/* maximum backwards seek, in KiB */ 25static const int cfq_back_max = 16 * 1024; 26/* penalty of a backwards seek */ 27static const int cfq_back_penalty = 2; 28static const int cfq_slice_sync = HZ / 10; 29static int cfq_slice_async = HZ / 25; 30static const int cfq_slice_async_rq = 2; 31static int cfq_slice_idle = HZ / 125; 32static const int cfq_target_latency = HZ * 3/10; /* 300 ms */ 33static const int cfq_hist_divisor = 4; 34 35/* 36 * offset from end of service tree 37 */ 38#define CFQ_IDLE_DELAY (HZ / 5) 39 40/* 41 * below this threshold, we consider thinktime immediate 42 */ 43#define CFQ_MIN_TT (2) 44 45#define CFQ_SLICE_SCALE (5) 46#define CFQ_HW_QUEUE_MIN (5) 47#define CFQ_SERVICE_SHIFT 12 48 49#define CFQQ_SEEK_THR (sector_t)(8 * 100) 50#define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32) 51#define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8) 52 53#define RQ_CIC(rq) \ 54 ((struct cfq_io_context *) (rq)->elevator_private) 55#define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elevator_private2) 56 57static struct kmem_cache *cfq_pool; 58static struct kmem_cache *cfq_ioc_pool; 59 60static DEFINE_PER_CPU(unsigned long, cfq_ioc_count); 61static struct completion *ioc_gone; 62static DEFINE_SPINLOCK(ioc_gone_lock); 63 64#define CFQ_PRIO_LISTS IOPRIO_BE_NR 65#define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE) 66#define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT) 67 68#define sample_valid(samples) ((samples) > 80) 69#define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node) 70 71/* 72 * Most of our rbtree usage is for sorting with min extraction, so 73 * if we cache the leftmost node we don't have to walk down the tree 74 * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should 75 * move this into the elevator for the rq sorting as well. 76 */ 77struct cfq_rb_root { 78 struct rb_root rb; 79 struct rb_node *left; 80 unsigned count; 81 unsigned total_weight; 82 u64 min_vdisktime; 83 struct rb_node *active; 84}; 85#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, .left = NULL, \ 86 .count = 0, .min_vdisktime = 0, } 87 88/* 89 * Per process-grouping structure 90 */ 91struct cfq_queue { 92 /* reference count */ 93 atomic_t ref; 94 /* various state flags, see below */ 95 unsigned int flags; 96 /* parent cfq_data */ 97 struct cfq_data *cfqd; 98 /* service_tree member */ 99 struct rb_node rb_node; 100 /* service_tree key */ 101 unsigned long rb_key; 102 /* prio tree member */ 103 struct rb_node p_node; 104 /* prio tree root we belong to, if any */ 105 struct rb_root *p_root; 106 /* sorted list of pending requests */ 107 struct rb_root sort_list; 108 /* if fifo isn't expired, next request to serve */ 109 struct request *next_rq; 110 /* requests queued in sort_list */ 111 int queued[2]; 112 /* currently allocated requests */ 113 int allocated[2]; 114 /* fifo list of requests in sort_list */ 115 struct list_head fifo; 116 117 /* time when queue got scheduled in to dispatch first request. */ 118 unsigned long dispatch_start; 119 unsigned int allocated_slice; 120 unsigned int slice_dispatch; 121 /* time when first request from queue completed and slice started. */ 122 unsigned long slice_start; 123 unsigned long slice_end; 124 long slice_resid; 125 126 /* pending metadata requests */ 127 int meta_pending; 128 /* number of requests that are on the dispatch list or inside driver */ 129 int dispatched; 130 131 /* io prio of this group */ 132 unsigned short ioprio, org_ioprio; 133 unsigned short ioprio_class, org_ioprio_class; 134 135 pid_t pid; 136 137 u32 seek_history; 138 sector_t last_request_pos; 139 140 struct cfq_rb_root *service_tree; 141 struct cfq_queue *new_cfqq; 142 struct cfq_group *cfqg; 143 struct cfq_group *orig_cfqg; 144 /* Sectors dispatched in current dispatch round */ 145 unsigned long nr_sectors; 146}; 147 148/* 149 * First index in the service_trees. 150 * IDLE is handled separately, so it has negative index 151 */ 152enum wl_prio_t { 153 BE_WORKLOAD = 0, 154 RT_WORKLOAD = 1, 155 IDLE_WORKLOAD = 2, 156}; 157 158/* 159 * Second index in the service_trees. 160 */ 161enum wl_type_t { 162 ASYNC_WORKLOAD = 0, 163 SYNC_NOIDLE_WORKLOAD = 1, 164 SYNC_WORKLOAD = 2 165}; 166 167/* This is per cgroup per device grouping structure */ 168struct cfq_group { 169 /* group service_tree member */ 170 struct rb_node rb_node; 171 172 /* group service_tree key */ 173 u64 vdisktime; 174 unsigned int weight; 175 bool on_st; 176 177 /* number of cfqq currently on this group */ 178 int nr_cfqq; 179 180 /* Per group busy queus average. Useful for workload slice calc. */ 181 unsigned int busy_queues_avg[2]; 182 /* 183 * rr lists of queues with requests, onle rr for each priority class. 184 * Counts are embedded in the cfq_rb_root 185 */ 186 struct cfq_rb_root service_trees[2][3]; 187 struct cfq_rb_root service_tree_idle; 188 189 unsigned long saved_workload_slice; 190 enum wl_type_t saved_workload; 191 enum wl_prio_t saved_serving_prio; 192 struct blkio_group blkg; 193#ifdef CONFIG_CFQ_GROUP_IOSCHED 194 struct hlist_node cfqd_node; 195 atomic_t ref; 196#endif 197}; 198 199/* 200 * Per block device queue structure 201 */ 202struct cfq_data { 203 struct request_queue *queue; 204 /* Root service tree for cfq_groups */ 205 struct cfq_rb_root grp_service_tree; 206 struct cfq_group root_group; 207 208 /* 209 * The priority currently being served 210 */ 211 enum wl_prio_t serving_prio; 212 enum wl_type_t serving_type; 213 unsigned long workload_expires; 214 struct cfq_group *serving_group; 215 bool noidle_tree_requires_idle; 216 217 /* 218 * Each priority tree is sorted by next_request position. These 219 * trees are used when determining if two or more queues are 220 * interleaving requests (see cfq_close_cooperator). 221 */ 222 struct rb_root prio_trees[CFQ_PRIO_LISTS]; 223 224 unsigned int busy_queues; 225 226 int rq_in_driver; 227 int rq_in_flight[2]; 228 229 /* 230 * queue-depth detection 231 */ 232 int rq_queued; 233 int hw_tag; 234 /* 235 * hw_tag can be 236 * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection) 237 * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth) 238 * 0 => no NCQ 239 */ 240 int hw_tag_est_depth; 241 unsigned int hw_tag_samples; 242 243 /* 244 * idle window management 245 */ 246 struct timer_list idle_slice_timer; 247 struct work_struct unplug_work; 248 249 struct cfq_queue *active_queue; 250 struct cfq_io_context *active_cic; 251 252 /* 253 * async queue for each priority case 254 */ 255 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR]; 256 struct cfq_queue *async_idle_cfqq; 257 258 sector_t last_position; 259 260 /* 261 * tunables, see top of file 262 */ 263 unsigned int cfq_quantum; 264 unsigned int cfq_fifo_expire[2]; 265 unsigned int cfq_back_penalty; 266 unsigned int cfq_back_max; 267 unsigned int cfq_slice[2]; 268 unsigned int cfq_slice_async_rq; 269 unsigned int cfq_slice_idle; 270 unsigned int cfq_latency; 271 unsigned int cfq_group_isolation; 272 273 struct list_head cic_list; 274 275 /* 276 * Fallback dummy cfqq for extreme OOM conditions 277 */ 278 struct cfq_queue oom_cfqq; 279 280 unsigned long last_delayed_sync; 281 282 /* List of cfq groups being managed on this device*/ 283 struct hlist_head cfqg_list; 284 struct rcu_head rcu; 285}; 286 287static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd); 288 289static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg, 290 enum wl_prio_t prio, 291 enum wl_type_t type) 292{ 293 if (!cfqg) 294 return NULL; 295 296 if (prio == IDLE_WORKLOAD) 297 return &cfqg->service_tree_idle; 298 299 return &cfqg->service_trees[prio][type]; 300} 301 302enum cfqq_state_flags { 303 CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */ 304 CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */ 305 CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */ 306 CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */ 307 CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */ 308 CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */ 309 CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */ 310 CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */ 311 CFQ_CFQQ_FLAG_sync, /* synchronous queue */ 312 CFQ_CFQQ_FLAG_coop, /* cfqq is shared */ 313 CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */ 314 CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */ 315 CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */ 316}; 317 318#define CFQ_CFQQ_FNS(name) \ 319static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \ 320{ \ 321 (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \ 322} \ 323static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \ 324{ \ 325 (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \ 326} \ 327static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \ 328{ \ 329 return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \ 330} 331 332CFQ_CFQQ_FNS(on_rr); 333CFQ_CFQQ_FNS(wait_request); 334CFQ_CFQQ_FNS(must_dispatch); 335CFQ_CFQQ_FNS(must_alloc_slice); 336CFQ_CFQQ_FNS(fifo_expire); 337CFQ_CFQQ_FNS(idle_window); 338CFQ_CFQQ_FNS(prio_changed); 339CFQ_CFQQ_FNS(slice_new); 340CFQ_CFQQ_FNS(sync); 341CFQ_CFQQ_FNS(coop); 342CFQ_CFQQ_FNS(split_coop); 343CFQ_CFQQ_FNS(deep); 344CFQ_CFQQ_FNS(wait_busy); 345#undef CFQ_CFQQ_FNS 346 347#ifdef CONFIG_DEBUG_CFQ_IOSCHED 348#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \ 349 blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \ 350 cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \ 351 blkg_path(&(cfqq)->cfqg->blkg), ##args); 352 353#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) \ 354 blk_add_trace_msg((cfqd)->queue, "%s " fmt, \ 355 blkg_path(&(cfqg)->blkg), ##args); \ 356 357#else 358#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \ 359 blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args) 360#define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0); 361#endif 362#define cfq_log(cfqd, fmt, args...) \ 363 blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args) 364 365/* Traverses through cfq group service trees */ 366#define for_each_cfqg_st(cfqg, i, j, st) \ 367 for (i = 0; i <= IDLE_WORKLOAD; i++) \ 368 for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\ 369 : &cfqg->service_tree_idle; \ 370 (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \ 371 (i == IDLE_WORKLOAD && j == 0); \ 372 j++, st = i < IDLE_WORKLOAD ? \ 373 &cfqg->service_trees[i][j]: NULL) \ 374 375 376static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq) 377{ 378 if (cfq_class_idle(cfqq)) 379 return IDLE_WORKLOAD; 380 if (cfq_class_rt(cfqq)) 381 return RT_WORKLOAD; 382 return BE_WORKLOAD; 383} 384 385 386static enum wl_type_t cfqq_type(struct cfq_queue *cfqq) 387{ 388 if (!cfq_cfqq_sync(cfqq)) 389 return ASYNC_WORKLOAD; 390 if (!cfq_cfqq_idle_window(cfqq)) 391 return SYNC_NOIDLE_WORKLOAD; 392 return SYNC_WORKLOAD; 393} 394 395static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl, 396 struct cfq_data *cfqd, 397 struct cfq_group *cfqg) 398{ 399 if (wl == IDLE_WORKLOAD) 400 return cfqg->service_tree_idle.count; 401 402 return cfqg->service_trees[wl][ASYNC_WORKLOAD].count 403 + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count 404 + cfqg->service_trees[wl][SYNC_WORKLOAD].count; 405} 406 407static inline int cfqg_busy_async_queues(struct cfq_data *cfqd, 408 struct cfq_group *cfqg) 409{ 410 return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count 411 + cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count; 412} 413 414static void cfq_dispatch_insert(struct request_queue *, struct request *); 415static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool, 416 struct io_context *, gfp_t); 417static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *, 418 struct io_context *); 419 420static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic, 421 bool is_sync) 422{ 423 return cic->cfqq[is_sync]; 424} 425 426static inline void cic_set_cfqq(struct cfq_io_context *cic, 427 struct cfq_queue *cfqq, bool is_sync) 428{ 429 cic->cfqq[is_sync] = cfqq; 430} 431 432/* 433 * We regard a request as SYNC, if it's either a read or has the SYNC bit 434 * set (in which case it could also be direct WRITE). 435 */ 436static inline bool cfq_bio_sync(struct bio *bio) 437{ 438 return bio_data_dir(bio) == READ || bio_rw_flagged(bio, BIO_RW_SYNCIO); 439} 440 441/* 442 * scheduler run of queue, if there are requests pending and no one in the 443 * driver that will restart queueing 444 */ 445static inline void cfq_schedule_dispatch(struct cfq_data *cfqd) 446{ 447 if (cfqd->busy_queues) { 448 cfq_log(cfqd, "schedule dispatch"); 449 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work); 450 } 451} 452 453static int cfq_queue_empty(struct request_queue *q) 454{ 455 struct cfq_data *cfqd = q->elevator->elevator_data; 456 457 return !cfqd->rq_queued; 458} 459 460/* 461 * Scale schedule slice based on io priority. Use the sync time slice only 462 * if a queue is marked sync and has sync io queued. A sync queue with async 463 * io only, should not get full sync slice length. 464 */ 465static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync, 466 unsigned short prio) 467{ 468 const int base_slice = cfqd->cfq_slice[sync]; 469 470 WARN_ON(prio >= IOPRIO_BE_NR); 471 472 return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio)); 473} 474 475static inline int 476cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) 477{ 478 return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio); 479} 480 481static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg) 482{ 483 u64 d = delta << CFQ_SERVICE_SHIFT; 484 485 d = d * BLKIO_WEIGHT_DEFAULT; 486 do_div(d, cfqg->weight); 487 return d; 488} 489 490static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime) 491{ 492 s64 delta = (s64)(vdisktime - min_vdisktime); 493 if (delta > 0) 494 min_vdisktime = vdisktime; 495 496 return min_vdisktime; 497} 498 499static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime) 500{ 501 s64 delta = (s64)(vdisktime - min_vdisktime); 502 if (delta < 0) 503 min_vdisktime = vdisktime; 504 505 return min_vdisktime; 506} 507 508static void update_min_vdisktime(struct cfq_rb_root *st) 509{ 510 u64 vdisktime = st->min_vdisktime; 511 struct cfq_group *cfqg; 512 513 if (st->active) { 514 cfqg = rb_entry_cfqg(st->active); 515 vdisktime = cfqg->vdisktime; 516 } 517 518 if (st->left) { 519 cfqg = rb_entry_cfqg(st->left); 520 vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime); 521 } 522 523 st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime); 524} 525 526/* 527 * get averaged number of queues of RT/BE priority. 528 * average is updated, with a formula that gives more weight to higher numbers, 529 * to quickly follows sudden increases and decrease slowly 530 */ 531 532static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd, 533 struct cfq_group *cfqg, bool rt) 534{ 535 unsigned min_q, max_q; 536 unsigned mult = cfq_hist_divisor - 1; 537 unsigned round = cfq_hist_divisor / 2; 538 unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg); 539 540 min_q = min(cfqg->busy_queues_avg[rt], busy); 541 max_q = max(cfqg->busy_queues_avg[rt], busy); 542 cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) / 543 cfq_hist_divisor; 544 return cfqg->busy_queues_avg[rt]; 545} 546 547static inline unsigned 548cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg) 549{ 550 struct cfq_rb_root *st = &cfqd->grp_service_tree; 551 552 return cfq_target_latency * cfqg->weight / st->total_weight; 553} 554 555static inline void 556cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) 557{ 558 unsigned slice = cfq_prio_to_slice(cfqd, cfqq); 559 if (cfqd->cfq_latency) { 560 /* 561 * interested queues (we consider only the ones with the same 562 * priority class in the cfq group) 563 */ 564 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg, 565 cfq_class_rt(cfqq)); 566 unsigned sync_slice = cfqd->cfq_slice[1]; 567 unsigned expect_latency = sync_slice * iq; 568 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg); 569 570 if (expect_latency > group_slice) { 571 unsigned base_low_slice = 2 * cfqd->cfq_slice_idle; 572 /* scale low_slice according to IO priority 573 * and sync vs async */ 574 unsigned low_slice = 575 min(slice, base_low_slice * slice / sync_slice); 576 /* the adapted slice value is scaled to fit all iqs 577 * into the target latency */ 578 slice = max(slice * group_slice / expect_latency, 579 low_slice); 580 } 581 } 582 cfqq->slice_start = jiffies; 583 cfqq->slice_end = jiffies + slice; 584 cfqq->allocated_slice = slice; 585 cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies); 586} 587 588/* 589 * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end 590 * isn't valid until the first request from the dispatch is activated 591 * and the slice time set. 592 */ 593static inline bool cfq_slice_used(struct cfq_queue *cfqq) 594{ 595 if (cfq_cfqq_slice_new(cfqq)) 596 return 0; 597 if (time_before(jiffies, cfqq->slice_end)) 598 return 0; 599 600 return 1; 601} 602 603/* 604 * Lifted from AS - choose which of rq1 and rq2 that is best served now. 605 * We choose the request that is closest to the head right now. Distance 606 * behind the head is penalized and only allowed to a certain extent. 607 */ 608static struct request * 609cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last) 610{ 611 sector_t s1, s2, d1 = 0, d2 = 0; 612 unsigned long back_max; 613#define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */ 614#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */ 615 unsigned wrap = 0; /* bit mask: requests behind the disk head? */ 616 617 if (rq1 == NULL || rq1 == rq2) 618 return rq2; 619 if (rq2 == NULL) 620 return rq1; 621 622 if (rq_is_sync(rq1) && !rq_is_sync(rq2)) 623 return rq1; 624 else if (rq_is_sync(rq2) && !rq_is_sync(rq1)) 625 return rq2; 626 if (rq_is_meta(rq1) && !rq_is_meta(rq2)) 627 return rq1; 628 else if (rq_is_meta(rq2) && !rq_is_meta(rq1)) 629 return rq2; 630 631 s1 = blk_rq_pos(rq1); 632 s2 = blk_rq_pos(rq2); 633 634 /* 635 * by definition, 1KiB is 2 sectors 636 */ 637 back_max = cfqd->cfq_back_max * 2; 638 639 /* 640 * Strict one way elevator _except_ in the case where we allow 641 * short backward seeks which are biased as twice the cost of a 642 * similar forward seek. 643 */ 644 if (s1 >= last) 645 d1 = s1 - last; 646 else if (s1 + back_max >= last) 647 d1 = (last - s1) * cfqd->cfq_back_penalty; 648 else 649 wrap |= CFQ_RQ1_WRAP; 650 651 if (s2 >= last) 652 d2 = s2 - last; 653 else if (s2 + back_max >= last) 654 d2 = (last - s2) * cfqd->cfq_back_penalty; 655 else 656 wrap |= CFQ_RQ2_WRAP; 657 658 /* Found required data */ 659 660 /* 661 * By doing switch() on the bit mask "wrap" we avoid having to 662 * check two variables for all permutations: --> faster! 663 */ 664 switch (wrap) { 665 case 0: /* common case for CFQ: rq1 and rq2 not wrapped */ 666 if (d1 < d2) 667 return rq1; 668 else if (d2 < d1) 669 return rq2; 670 else { 671 if (s1 >= s2) 672 return rq1; 673 else 674 return rq2; 675 } 676 677 case CFQ_RQ2_WRAP: 678 return rq1; 679 case CFQ_RQ1_WRAP: 680 return rq2; 681 case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */ 682 default: 683 /* 684 * Since both rqs are wrapped, 685 * start with the one that's further behind head 686 * (--> only *one* back seek required), 687 * since back seek takes more time than forward. 688 */ 689 if (s1 <= s2) 690 return rq1; 691 else 692 return rq2; 693 } 694} 695 696/* 697 * The below is leftmost cache rbtree addon 698 */ 699static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root) 700{ 701 /* Service tree is empty */ 702 if (!root->count) 703 return NULL; 704 705 if (!root->left) 706 root->left = rb_first(&root->rb); 707 708 if (root->left) 709 return rb_entry(root->left, struct cfq_queue, rb_node); 710 711 return NULL; 712} 713 714static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root) 715{ 716 if (!root->left) 717 root->left = rb_first(&root->rb); 718 719 if (root->left) 720 return rb_entry_cfqg(root->left); 721 722 return NULL; 723} 724 725static void rb_erase_init(struct rb_node *n, struct rb_root *root) 726{ 727 rb_erase(n, root); 728 RB_CLEAR_NODE(n); 729} 730 731static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root) 732{ 733 if (root->left == n) 734 root->left = NULL; 735 rb_erase_init(n, &root->rb); 736 --root->count; 737} 738 739/* 740 * would be nice to take fifo expire time into account as well 741 */ 742static struct request * 743cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq, 744 struct request *last) 745{ 746 struct rb_node *rbnext = rb_next(&last->rb_node); 747 struct rb_node *rbprev = rb_prev(&last->rb_node); 748 struct request *next = NULL, *prev = NULL; 749 750 BUG_ON(RB_EMPTY_NODE(&last->rb_node)); 751 752 if (rbprev) 753 prev = rb_entry_rq(rbprev); 754 755 if (rbnext) 756 next = rb_entry_rq(rbnext); 757 else { 758 rbnext = rb_first(&cfqq->sort_list); 759 if (rbnext && rbnext != &last->rb_node) 760 next = rb_entry_rq(rbnext); 761 } 762 763 return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last)); 764} 765 766static unsigned long cfq_slice_offset(struct cfq_data *cfqd, 767 struct cfq_queue *cfqq) 768{ 769 /* 770 * just an approximation, should be ok. 771 */ 772 return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) - 773 cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio)); 774} 775 776static inline s64 777cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg) 778{ 779 return cfqg->vdisktime - st->min_vdisktime; 780} 781 782static void 783__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg) 784{ 785 struct rb_node **node = &st->rb.rb_node; 786 struct rb_node *parent = NULL; 787 struct cfq_group *__cfqg; 788 s64 key = cfqg_key(st, cfqg); 789 int left = 1; 790 791 while (*node != NULL) { 792 parent = *node; 793 __cfqg = rb_entry_cfqg(parent); 794 795 if (key < cfqg_key(st, __cfqg)) 796 node = &parent->rb_left; 797 else { 798 node = &parent->rb_right; 799 left = 0; 800 } 801 } 802 803 if (left) 804 st->left = &cfqg->rb_node; 805 806 rb_link_node(&cfqg->rb_node, parent, node); 807 rb_insert_color(&cfqg->rb_node, &st->rb); 808} 809 810static void 811cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg) 812{ 813 struct cfq_rb_root *st = &cfqd->grp_service_tree; 814 struct cfq_group *__cfqg; 815 struct rb_node *n; 816 817 cfqg->nr_cfqq++; 818 if (cfqg->on_st) 819 return; 820 821 /* 822 * Currently put the group at the end. Later implement something 823 * so that groups get lesser vtime based on their weights, so that 824 * if group does not loose all if it was not continously backlogged. 825 */ 826 n = rb_last(&st->rb); 827 if (n) { 828 __cfqg = rb_entry_cfqg(n); 829 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY; 830 } else 831 cfqg->vdisktime = st->min_vdisktime; 832 833 __cfq_group_service_tree_add(st, cfqg); 834 cfqg->on_st = true; 835 st->total_weight += cfqg->weight; 836} 837 838static void 839cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg) 840{ 841 struct cfq_rb_root *st = &cfqd->grp_service_tree; 842 843 if (st->active == &cfqg->rb_node) 844 st->active = NULL; 845 846 BUG_ON(cfqg->nr_cfqq < 1); 847 cfqg->nr_cfqq--; 848 849 /* If there are other cfq queues under this group, don't delete it */ 850 if (cfqg->nr_cfqq) 851 return; 852 853 cfq_log_cfqg(cfqd, cfqg, "del_from_rr group"); 854 cfqg->on_st = false; 855 st->total_weight -= cfqg->weight; 856 if (!RB_EMPTY_NODE(&cfqg->rb_node)) 857 cfq_rb_erase(&cfqg->rb_node, st); 858 cfqg->saved_workload_slice = 0; 859 blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1); 860} 861 862static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq) 863{ 864 unsigned int slice_used; 865 866 /* 867 * Queue got expired before even a single request completed or 868 * got expired immediately after first request completion. 869 */ 870 if (!cfqq->slice_start || cfqq->slice_start == jiffies) { 871 /* 872 * Also charge the seek time incurred to the group, otherwise 873 * if there are mutiple queues in the group, each can dispatch 874 * a single request on seeky media and cause lots of seek time 875 * and group will never know it. 876 */ 877 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start), 878 1); 879 } else { 880 slice_used = jiffies - cfqq->slice_start; 881 if (slice_used > cfqq->allocated_slice) 882 slice_used = cfqq->allocated_slice; 883 } 884 885 cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used, 886 cfqq->nr_sectors); 887 return slice_used; 888} 889 890static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg, 891 struct cfq_queue *cfqq) 892{ 893 struct cfq_rb_root *st = &cfqd->grp_service_tree; 894 unsigned int used_sl, charge_sl; 895 int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg) 896 - cfqg->service_tree_idle.count; 897 898 BUG_ON(nr_sync < 0); 899 used_sl = charge_sl = cfq_cfqq_slice_usage(cfqq); 900 901 if (!cfq_cfqq_sync(cfqq) && !nr_sync) 902 charge_sl = cfqq->allocated_slice; 903 904 /* Can't update vdisktime while group is on service tree */ 905 cfq_rb_erase(&cfqg->rb_node, st); 906 cfqg->vdisktime += cfq_scale_slice(charge_sl, cfqg); 907 __cfq_group_service_tree_add(st, cfqg); 908 909 /* This group is being expired. Save the context */ 910 if (time_after(cfqd->workload_expires, jiffies)) { 911 cfqg->saved_workload_slice = cfqd->workload_expires 912 - jiffies; 913 cfqg->saved_workload = cfqd->serving_type; 914 cfqg->saved_serving_prio = cfqd->serving_prio; 915 } else 916 cfqg->saved_workload_slice = 0; 917 918 cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime, 919 st->min_vdisktime); 920 blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl, 921 cfqq->nr_sectors); 922} 923 924#ifdef CONFIG_CFQ_GROUP_IOSCHED 925static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg) 926{ 927 if (blkg) 928 return container_of(blkg, struct cfq_group, blkg); 929 return NULL; 930} 931 932void 933cfq_update_blkio_group_weight(struct blkio_group *blkg, unsigned int weight) 934{ 935 cfqg_of_blkg(blkg)->weight = weight; 936} 937 938static struct cfq_group * 939cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create) 940{ 941 struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup); 942 struct cfq_group *cfqg = NULL; 943 void *key = cfqd; 944 int i, j; 945 struct cfq_rb_root *st; 946 struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info; 947 unsigned int major, minor; 948 949 cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key)); 950 if (cfqg || !create) 951 goto done; 952 953 cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node); 954 if (!cfqg) 955 goto done; 956 957 cfqg->weight = blkcg->weight; 958 for_each_cfqg_st(cfqg, i, j, st) 959 *st = CFQ_RB_ROOT; 960 RB_CLEAR_NODE(&cfqg->rb_node); 961 962 /* 963 * Take the initial reference that will be released on destroy 964 * This can be thought of a joint reference by cgroup and 965 * elevator which will be dropped by either elevator exit 966 * or cgroup deletion path depending on who is exiting first. 967 */ 968 atomic_set(&cfqg->ref, 1); 969 970 /* Add group onto cgroup list */ 971 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor); 972 blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd, 973 MKDEV(major, minor)); 974 975 /* Add group on cfqd list */ 976 hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list); 977 978done: 979 return cfqg; 980} 981 982/* 983 * Search for the cfq group current task belongs to. If create = 1, then also 984 * create the cfq group if it does not exist. request_queue lock must be held. 985 */ 986static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create) 987{ 988 struct cgroup *cgroup; 989 struct cfq_group *cfqg = NULL; 990 991 rcu_read_lock(); 992 cgroup = task_cgroup(current, blkio_subsys_id); 993 cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create); 994 if (!cfqg && create) 995 cfqg = &cfqd->root_group; 996 rcu_read_unlock(); 997 return cfqg; 998} 999 1000static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) 1001{ 1002 /* Currently, all async queues are mapped to root group */ 1003 if (!cfq_cfqq_sync(cfqq)) 1004 cfqg = &cfqq->cfqd->root_group; 1005 1006 cfqq->cfqg = cfqg; 1007 /* cfqq reference on cfqg */ 1008 atomic_inc(&cfqq->cfqg->ref); 1009} 1010 1011static void cfq_put_cfqg(struct cfq_group *cfqg) 1012{ 1013 struct cfq_rb_root *st; 1014 int i, j; 1015 1016 BUG_ON(atomic_read(&cfqg->ref) <= 0); 1017 if (!atomic_dec_and_test(&cfqg->ref)) 1018 return; 1019 for_each_cfqg_st(cfqg, i, j, st) 1020 BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL); 1021 kfree(cfqg); 1022} 1023 1024static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg) 1025{ 1026 /* Something wrong if we are trying to remove same group twice */ 1027 BUG_ON(hlist_unhashed(&cfqg->cfqd_node)); 1028 1029 hlist_del_init(&cfqg->cfqd_node); 1030 1031 /* 1032 * Put the reference taken at the time of creation so that when all 1033 * queues are gone, group can be destroyed. 1034 */ 1035 cfq_put_cfqg(cfqg); 1036} 1037 1038static void cfq_release_cfq_groups(struct cfq_data *cfqd) 1039{ 1040 struct hlist_node *pos, *n; 1041 struct cfq_group *cfqg; 1042 1043 hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) { 1044 /* 1045 * If cgroup removal path got to blk_group first and removed 1046 * it from cgroup list, then it will take care of destroying 1047 * cfqg also. 1048 */ 1049 if (!blkiocg_del_blkio_group(&cfqg->blkg)) 1050 cfq_destroy_cfqg(cfqd, cfqg); 1051 } 1052} 1053 1054/* 1055 * Blk cgroup controller notification saying that blkio_group object is being 1056 * delinked as associated cgroup object is going away. That also means that 1057 * no new IO will come in this group. So get rid of this group as soon as 1058 * any pending IO in the group is finished. 1059 * 1060 * This function is called under rcu_read_lock(). key is the rcu protected 1061 * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu 1062 * read lock. 1063 * 1064 * "key" was fetched from blkio_group under blkio_cgroup->lock. That means 1065 * it should not be NULL as even if elevator was exiting, cgroup deltion 1066 * path got to it first. 1067 */ 1068void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg) 1069{ 1070 unsigned long flags; 1071 struct cfq_data *cfqd = key; 1072 1073 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 1074 cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg)); 1075 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 1076} 1077 1078#else /* GROUP_IOSCHED */ 1079static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create) 1080{ 1081 return &cfqd->root_group; 1082} 1083static inline void 1084cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) { 1085 cfqq->cfqg = cfqg; 1086} 1087 1088static void cfq_release_cfq_groups(struct cfq_data *cfqd) {} 1089static inline void cfq_put_cfqg(struct cfq_group *cfqg) {} 1090 1091#endif /* GROUP_IOSCHED */ 1092 1093/* 1094 * The cfqd->service_trees holds all pending cfq_queue's that have 1095 * requests waiting to be processed. It is sorted in the order that 1096 * we will service the queues. 1097 */ 1098static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1099 bool add_front) 1100{ 1101 struct rb_node **p, *parent; 1102 struct cfq_queue *__cfqq; 1103 unsigned long rb_key; 1104 struct cfq_rb_root *service_tree; 1105 int left; 1106 int new_cfqq = 1; 1107 int group_changed = 0; 1108 1109#ifdef CONFIG_CFQ_GROUP_IOSCHED 1110 if (!cfqd->cfq_group_isolation 1111 && cfqq_type(cfqq) == SYNC_NOIDLE_WORKLOAD 1112 && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) { 1113 /* Move this cfq to root group */ 1114 cfq_log_cfqq(cfqd, cfqq, "moving to root group"); 1115 if (!RB_EMPTY_NODE(&cfqq->rb_node)) 1116 cfq_group_service_tree_del(cfqd, cfqq->cfqg); 1117 cfqq->orig_cfqg = cfqq->cfqg; 1118 cfqq->cfqg = &cfqd->root_group; 1119 atomic_inc(&cfqd->root_group.ref); 1120 group_changed = 1; 1121 } else if (!cfqd->cfq_group_isolation 1122 && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) { 1123 /* cfqq is sequential now needs to go to its original group */ 1124 BUG_ON(cfqq->cfqg != &cfqd->root_group); 1125 if (!RB_EMPTY_NODE(&cfqq->rb_node)) 1126 cfq_group_service_tree_del(cfqd, cfqq->cfqg); 1127 cfq_put_cfqg(cfqq->cfqg); 1128 cfqq->cfqg = cfqq->orig_cfqg; 1129 cfqq->orig_cfqg = NULL; 1130 group_changed = 1; 1131 cfq_log_cfqq(cfqd, cfqq, "moved to origin group"); 1132 } 1133#endif 1134 1135 service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq), 1136 cfqq_type(cfqq)); 1137 if (cfq_class_idle(cfqq)) { 1138 rb_key = CFQ_IDLE_DELAY; 1139 parent = rb_last(&service_tree->rb); 1140 if (parent && parent != &cfqq->rb_node) { 1141 __cfqq = rb_entry(parent, struct cfq_queue, rb_node); 1142 rb_key += __cfqq->rb_key; 1143 } else 1144 rb_key += jiffies; 1145 } else if (!add_front) { 1146 /* 1147 * Get our rb key offset. Subtract any residual slice 1148 * value carried from last service. A negative resid 1149 * count indicates slice overrun, and this should position 1150 * the next service time further away in the tree. 1151 */ 1152 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies; 1153 rb_key -= cfqq->slice_resid; 1154 cfqq->slice_resid = 0; 1155 } else { 1156 rb_key = -HZ; 1157 __cfqq = cfq_rb_first(service_tree); 1158 rb_key += __cfqq ? __cfqq->rb_key : jiffies; 1159 } 1160 1161 if (!RB_EMPTY_NODE(&cfqq->rb_node)) { 1162 new_cfqq = 0; 1163 /* 1164 * same position, nothing more to do 1165 */ 1166 if (rb_key == cfqq->rb_key && 1167 cfqq->service_tree == service_tree) 1168 return; 1169 1170 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree); 1171 cfqq->service_tree = NULL; 1172 } 1173 1174 left = 1; 1175 parent = NULL; 1176 cfqq->service_tree = service_tree; 1177 p = &service_tree->rb.rb_node; 1178 while (*p) { 1179 struct rb_node **n; 1180 1181 parent = *p; 1182 __cfqq = rb_entry(parent, struct cfq_queue, rb_node); 1183 1184 /* 1185 * sort by key, that represents service time. 1186 */ 1187 if (time_before(rb_key, __cfqq->rb_key)) 1188 n = &(*p)->rb_left; 1189 else { 1190 n = &(*p)->rb_right; 1191 left = 0; 1192 } 1193 1194 p = n; 1195 } 1196 1197 if (left) 1198 service_tree->left = &cfqq->rb_node; 1199 1200 cfqq->rb_key = rb_key; 1201 rb_link_node(&cfqq->rb_node, parent, p); 1202 rb_insert_color(&cfqq->rb_node, &service_tree->rb); 1203 service_tree->count++; 1204 if ((add_front || !new_cfqq) && !group_changed) 1205 return; 1206 cfq_group_service_tree_add(cfqd, cfqq->cfqg); 1207} 1208 1209static struct cfq_queue * 1210cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root, 1211 sector_t sector, struct rb_node **ret_parent, 1212 struct rb_node ***rb_link) 1213{ 1214 struct rb_node **p, *parent; 1215 struct cfq_queue *cfqq = NULL; 1216 1217 parent = NULL; 1218 p = &root->rb_node; 1219 while (*p) { 1220 struct rb_node **n; 1221 1222 parent = *p; 1223 cfqq = rb_entry(parent, struct cfq_queue, p_node); 1224 1225 /* 1226 * Sort strictly based on sector. Smallest to the left, 1227 * largest to the right. 1228 */ 1229 if (sector > blk_rq_pos(cfqq->next_rq)) 1230 n = &(*p)->rb_right; 1231 else if (sector < blk_rq_pos(cfqq->next_rq)) 1232 n = &(*p)->rb_left; 1233 else 1234 break; 1235 p = n; 1236 cfqq = NULL; 1237 } 1238 1239 *ret_parent = parent; 1240 if (rb_link) 1241 *rb_link = p; 1242 return cfqq; 1243} 1244 1245static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1246{ 1247 struct rb_node **p, *parent; 1248 struct cfq_queue *__cfqq; 1249 1250 if (cfqq->p_root) { 1251 rb_erase(&cfqq->p_node, cfqq->p_root); 1252 cfqq->p_root = NULL; 1253 } 1254 1255 if (cfq_class_idle(cfqq)) 1256 return; 1257 if (!cfqq->next_rq) 1258 return; 1259 1260 cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio]; 1261 __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root, 1262 blk_rq_pos(cfqq->next_rq), &parent, &p); 1263 if (!__cfqq) { 1264 rb_link_node(&cfqq->p_node, parent, p); 1265 rb_insert_color(&cfqq->p_node, cfqq->p_root); 1266 } else 1267 cfqq->p_root = NULL; 1268} 1269 1270/* 1271 * Update cfqq's position in the service tree. 1272 */ 1273static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1274{ 1275 /* 1276 * Resorting requires the cfqq to be on the RR list already. 1277 */ 1278 if (cfq_cfqq_on_rr(cfqq)) { 1279 cfq_service_tree_add(cfqd, cfqq, 0); 1280 cfq_prio_tree_add(cfqd, cfqq); 1281 } 1282} 1283 1284/* 1285 * add to busy list of queues for service, trying to be fair in ordering 1286 * the pending list according to last request service 1287 */ 1288static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1289{ 1290 cfq_log_cfqq(cfqd, cfqq, "add_to_rr"); 1291 BUG_ON(cfq_cfqq_on_rr(cfqq)); 1292 cfq_mark_cfqq_on_rr(cfqq); 1293 cfqd->busy_queues++; 1294 1295 cfq_resort_rr_list(cfqd, cfqq); 1296} 1297 1298/* 1299 * Called when the cfqq no longer has requests pending, remove it from 1300 * the service tree. 1301 */ 1302static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1303{ 1304 cfq_log_cfqq(cfqd, cfqq, "del_from_rr"); 1305 BUG_ON(!cfq_cfqq_on_rr(cfqq)); 1306 cfq_clear_cfqq_on_rr(cfqq); 1307 1308 if (!RB_EMPTY_NODE(&cfqq->rb_node)) { 1309 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree); 1310 cfqq->service_tree = NULL; 1311 } 1312 if (cfqq->p_root) { 1313 rb_erase(&cfqq->p_node, cfqq->p_root); 1314 cfqq->p_root = NULL; 1315 } 1316 1317 cfq_group_service_tree_del(cfqd, cfqq->cfqg); 1318 BUG_ON(!cfqd->busy_queues); 1319 cfqd->busy_queues--; 1320} 1321 1322/* 1323 * rb tree support functions 1324 */ 1325static void cfq_del_rq_rb(struct request *rq) 1326{ 1327 struct cfq_queue *cfqq = RQ_CFQQ(rq); 1328 const int sync = rq_is_sync(rq); 1329 1330 BUG_ON(!cfqq->queued[sync]); 1331 cfqq->queued[sync]--; 1332 1333 elv_rb_del(&cfqq->sort_list, rq); 1334 1335 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) { 1336 /* 1337 * Queue will be deleted from service tree when we actually 1338 * expire it later. Right now just remove it from prio tree 1339 * as it is empty. 1340 */ 1341 if (cfqq->p_root) { 1342 rb_erase(&cfqq->p_node, cfqq->p_root); 1343 cfqq->p_root = NULL; 1344 } 1345 } 1346} 1347 1348static void cfq_add_rq_rb(struct request *rq) 1349{ 1350 struct cfq_queue *cfqq = RQ_CFQQ(rq); 1351 struct cfq_data *cfqd = cfqq->cfqd; 1352 struct request *__alias, *prev; 1353 1354 cfqq->queued[rq_is_sync(rq)]++; 1355 1356 /* 1357 * looks a little odd, but the first insert might return an alias. 1358 * if that happens, put the alias on the dispatch list 1359 */ 1360 while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL) 1361 cfq_dispatch_insert(cfqd->queue, __alias); 1362 1363 if (!cfq_cfqq_on_rr(cfqq)) 1364 cfq_add_cfqq_rr(cfqd, cfqq); 1365 1366 /* 1367 * check if this request is a better next-serve candidate 1368 */ 1369 prev = cfqq->next_rq; 1370 cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position); 1371 1372 /* 1373 * adjust priority tree position, if ->next_rq changes 1374 */ 1375 if (prev != cfqq->next_rq) 1376 cfq_prio_tree_add(cfqd, cfqq); 1377 1378 BUG_ON(!cfqq->next_rq); 1379} 1380 1381static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq) 1382{ 1383 elv_rb_del(&cfqq->sort_list, rq); 1384 cfqq->queued[rq_is_sync(rq)]--; 1385 cfq_add_rq_rb(rq); 1386} 1387 1388static struct request * 1389cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio) 1390{ 1391 struct task_struct *tsk = current; 1392 struct cfq_io_context *cic; 1393 struct cfq_queue *cfqq; 1394 1395 cic = cfq_cic_lookup(cfqd, tsk->io_context); 1396 if (!cic) 1397 return NULL; 1398 1399 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio)); 1400 if (cfqq) { 1401 sector_t sector = bio->bi_sector + bio_sectors(bio); 1402 1403 return elv_rb_find(&cfqq->sort_list, sector); 1404 } 1405 1406 return NULL; 1407} 1408 1409static void cfq_activate_request(struct request_queue *q, struct request *rq) 1410{ 1411 struct cfq_data *cfqd = q->elevator->elevator_data; 1412 1413 cfqd->rq_in_driver++; 1414 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d", 1415 cfqd->rq_in_driver); 1416 1417 cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq); 1418} 1419 1420static void cfq_deactivate_request(struct request_queue *q, struct request *rq) 1421{ 1422 struct cfq_data *cfqd = q->elevator->elevator_data; 1423 1424 WARN_ON(!cfqd->rq_in_driver); 1425 cfqd->rq_in_driver--; 1426 cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d", 1427 cfqd->rq_in_driver); 1428} 1429 1430static void cfq_remove_request(struct request *rq) 1431{ 1432 struct cfq_queue *cfqq = RQ_CFQQ(rq); 1433 1434 if (cfqq->next_rq == rq) 1435 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq); 1436 1437 list_del_init(&rq->queuelist); 1438 cfq_del_rq_rb(rq); 1439 1440 cfqq->cfqd->rq_queued--; 1441 if (rq_is_meta(rq)) { 1442 WARN_ON(!cfqq->meta_pending); 1443 cfqq->meta_pending--; 1444 } 1445} 1446 1447static int cfq_merge(struct request_queue *q, struct request **req, 1448 struct bio *bio) 1449{ 1450 struct cfq_data *cfqd = q->elevator->elevator_data; 1451 struct request *__rq; 1452 1453 __rq = cfq_find_rq_fmerge(cfqd, bio); 1454 if (__rq && elv_rq_merge_ok(__rq, bio)) { 1455 *req = __rq; 1456 return ELEVATOR_FRONT_MERGE; 1457 } 1458 1459 return ELEVATOR_NO_MERGE; 1460} 1461 1462static void cfq_merged_request(struct request_queue *q, struct request *req, 1463 int type) 1464{ 1465 if (type == ELEVATOR_FRONT_MERGE) { 1466 struct cfq_queue *cfqq = RQ_CFQQ(req); 1467 1468 cfq_reposition_rq_rb(cfqq, req); 1469 } 1470} 1471 1472static void 1473cfq_merged_requests(struct request_queue *q, struct request *rq, 1474 struct request *next) 1475{ 1476 struct cfq_queue *cfqq = RQ_CFQQ(rq); 1477 /* 1478 * reposition in fifo if next is older than rq 1479 */ 1480 if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) && 1481 time_before(rq_fifo_time(next), rq_fifo_time(rq))) { 1482 list_move(&rq->queuelist, &next->queuelist); 1483 rq_set_fifo_time(rq, rq_fifo_time(next)); 1484 } 1485 1486 if (cfqq->next_rq == next) 1487 cfqq->next_rq = rq; 1488 cfq_remove_request(next); 1489} 1490 1491static int cfq_allow_merge(struct request_queue *q, struct request *rq, 1492 struct bio *bio) 1493{ 1494 struct cfq_data *cfqd = q->elevator->elevator_data; 1495 struct cfq_io_context *cic; 1496 struct cfq_queue *cfqq; 1497 1498 /* 1499 * Disallow merge of a sync bio into an async request. 1500 */ 1501 if (cfq_bio_sync(bio) && !rq_is_sync(rq)) 1502 return false; 1503 1504 /* 1505 * Lookup the cfqq that this bio will be queued with. Allow 1506 * merge only if rq is queued there. 1507 */ 1508 cic = cfq_cic_lookup(cfqd, current->io_context); 1509 if (!cic) 1510 return false; 1511 1512 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio)); 1513 return cfqq == RQ_CFQQ(rq); 1514} 1515 1516static void __cfq_set_active_queue(struct cfq_data *cfqd, 1517 struct cfq_queue *cfqq) 1518{ 1519 if (cfqq) { 1520 cfq_log_cfqq(cfqd, cfqq, "set_active"); 1521 cfqq->slice_start = 0; 1522 cfqq->dispatch_start = jiffies; 1523 cfqq->allocated_slice = 0; 1524 cfqq->slice_end = 0; 1525 cfqq->slice_dispatch = 0; 1526 cfqq->nr_sectors = 0; 1527 1528 cfq_clear_cfqq_wait_request(cfqq); 1529 cfq_clear_cfqq_must_dispatch(cfqq); 1530 cfq_clear_cfqq_must_alloc_slice(cfqq); 1531 cfq_clear_cfqq_fifo_expire(cfqq); 1532 cfq_mark_cfqq_slice_new(cfqq); 1533 1534 del_timer(&cfqd->idle_slice_timer); 1535 } 1536 1537 cfqd->active_queue = cfqq; 1538} 1539 1540/* 1541 * current cfqq expired its slice (or was too idle), select new one 1542 */ 1543static void 1544__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1545 bool timed_out) 1546{ 1547 cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out); 1548 1549 if (cfq_cfqq_wait_request(cfqq)) 1550 del_timer(&cfqd->idle_slice_timer); 1551 1552 cfq_clear_cfqq_wait_request(cfqq); 1553 cfq_clear_cfqq_wait_busy(cfqq); 1554 1555 /* 1556 * If this cfqq is shared between multiple processes, check to 1557 * make sure that those processes are still issuing I/Os within 1558 * the mean seek distance. If not, it may be time to break the 1559 * queues apart again. 1560 */ 1561 if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq)) 1562 cfq_mark_cfqq_split_coop(cfqq); 1563 1564 /* 1565 * store what was left of this slice, if the queue idled/timed out 1566 */ 1567 if (timed_out && !cfq_cfqq_slice_new(cfqq)) { 1568 cfqq->slice_resid = cfqq->slice_end - jiffies; 1569 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid); 1570 } 1571 1572 cfq_group_served(cfqd, cfqq->cfqg, cfqq); 1573 1574 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) 1575 cfq_del_cfqq_rr(cfqd, cfqq); 1576 1577 cfq_resort_rr_list(cfqd, cfqq); 1578 1579 if (cfqq == cfqd->active_queue) 1580 cfqd->active_queue = NULL; 1581 1582 if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active) 1583 cfqd->grp_service_tree.active = NULL; 1584 1585 if (cfqd->active_cic) { 1586 put_io_context(cfqd->active_cic->ioc); 1587 cfqd->active_cic = NULL; 1588 } 1589} 1590 1591static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out) 1592{ 1593 struct cfq_queue *cfqq = cfqd->active_queue; 1594 1595 if (cfqq) 1596 __cfq_slice_expired(cfqd, cfqq, timed_out); 1597} 1598 1599/* 1600 * Get next queue for service. Unless we have a queue preemption, 1601 * we'll simply select the first cfqq in the service tree. 1602 */ 1603static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd) 1604{ 1605 struct cfq_rb_root *service_tree = 1606 service_tree_for(cfqd->serving_group, cfqd->serving_prio, 1607 cfqd->serving_type); 1608 1609 if (!cfqd->rq_queued) 1610 return NULL; 1611 1612 /* There is nothing to dispatch */ 1613 if (!service_tree) 1614 return NULL; 1615 if (RB_EMPTY_ROOT(&service_tree->rb)) 1616 return NULL; 1617 return cfq_rb_first(service_tree); 1618} 1619 1620static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd) 1621{ 1622 struct cfq_group *cfqg; 1623 struct cfq_queue *cfqq; 1624 int i, j; 1625 struct cfq_rb_root *st; 1626 1627 if (!cfqd->rq_queued) 1628 return NULL; 1629 1630 cfqg = cfq_get_next_cfqg(cfqd); 1631 if (!cfqg) 1632 return NULL; 1633 1634 for_each_cfqg_st(cfqg, i, j, st) 1635 if ((cfqq = cfq_rb_first(st)) != NULL) 1636 return cfqq; 1637 return NULL; 1638} 1639 1640/* 1641 * Get and set a new active queue for service. 1642 */ 1643static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd, 1644 struct cfq_queue *cfqq) 1645{ 1646 if (!cfqq) 1647 cfqq = cfq_get_next_queue(cfqd); 1648 1649 __cfq_set_active_queue(cfqd, cfqq); 1650 return cfqq; 1651} 1652 1653static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd, 1654 struct request *rq) 1655{ 1656 if (blk_rq_pos(rq) >= cfqd->last_position) 1657 return blk_rq_pos(rq) - cfqd->last_position; 1658 else 1659 return cfqd->last_position - blk_rq_pos(rq); 1660} 1661 1662static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq, 1663 struct request *rq, bool for_preempt) 1664{ 1665 return cfq_dist_from_last(cfqd, rq) <= CFQQ_SEEK_THR; 1666} 1667 1668static struct cfq_queue *cfqq_close(struct cfq_data *cfqd, 1669 struct cfq_queue *cur_cfqq) 1670{ 1671 struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio]; 1672 struct rb_node *parent, *node; 1673 struct cfq_queue *__cfqq; 1674 sector_t sector = cfqd->last_position; 1675 1676 if (RB_EMPTY_ROOT(root)) 1677 return NULL; 1678 1679 /* 1680 * First, if we find a request starting at the end of the last 1681 * request, choose it. 1682 */ 1683 __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL); 1684 if (__cfqq) 1685 return __cfqq; 1686 1687 /* 1688 * If the exact sector wasn't found, the parent of the NULL leaf 1689 * will contain the closest sector. 1690 */ 1691 __cfqq = rb_entry(parent, struct cfq_queue, p_node); 1692 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false)) 1693 return __cfqq; 1694 1695 if (blk_rq_pos(__cfqq->next_rq) < sector) 1696 node = rb_next(&__cfqq->p_node); 1697 else 1698 node = rb_prev(&__cfqq->p_node); 1699 if (!node) 1700 return NULL; 1701 1702 __cfqq = rb_entry(node, struct cfq_queue, p_node); 1703 if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq, false)) 1704 return __cfqq; 1705 1706 return NULL; 1707} 1708 1709/* 1710 * cfqd - obvious 1711 * cur_cfqq - passed in so that we don't decide that the current queue is 1712 * closely cooperating with itself. 1713 * 1714 * So, basically we're assuming that that cur_cfqq has dispatched at least 1715 * one request, and that cfqd->last_position reflects a position on the disk 1716 * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid 1717 * assumption. 1718 */ 1719static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd, 1720 struct cfq_queue *cur_cfqq) 1721{ 1722 struct cfq_queue *cfqq; 1723 1724 if (!cfq_cfqq_sync(cur_cfqq)) 1725 return NULL; 1726 if (CFQQ_SEEKY(cur_cfqq)) 1727 return NULL; 1728 1729 /* 1730 * Don't search priority tree if it's the only queue in the group. 1731 */ 1732 if (cur_cfqq->cfqg->nr_cfqq == 1) 1733 return NULL; 1734 1735 /* 1736 * We should notice if some of the queues are cooperating, eg 1737 * working closely on the same area of the disk. In that case, 1738 * we can group them together and don't waste time idling. 1739 */ 1740 cfqq = cfqq_close(cfqd, cur_cfqq); 1741 if (!cfqq) 1742 return NULL; 1743 1744 /* If new queue belongs to different cfq_group, don't choose it */ 1745 if (cur_cfqq->cfqg != cfqq->cfqg) 1746 return NULL; 1747 1748 /* 1749 * It only makes sense to merge sync queues. 1750 */ 1751 if (!cfq_cfqq_sync(cfqq)) 1752 return NULL; 1753 if (CFQQ_SEEKY(cfqq)) 1754 return NULL; 1755 1756 /* 1757 * Do not merge queues of different priority classes 1758 */ 1759 if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq)) 1760 return NULL; 1761 1762 return cfqq; 1763} 1764 1765/* 1766 * Determine whether we should enforce idle window for this queue. 1767 */ 1768 1769static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1770{ 1771 enum wl_prio_t prio = cfqq_prio(cfqq); 1772 struct cfq_rb_root *service_tree = cfqq->service_tree; 1773 1774 BUG_ON(!service_tree); 1775 BUG_ON(!service_tree->count); 1776 1777 /* We never do for idle class queues. */ 1778 if (prio == IDLE_WORKLOAD) 1779 return false; 1780 1781 /* We do for queues that were marked with idle window flag. */ 1782 if (cfq_cfqq_idle_window(cfqq) && 1783 !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)) 1784 return true; 1785 1786 /* 1787 * Otherwise, we do only if they are the last ones 1788 * in their service tree. 1789 */ 1790 return service_tree->count == 1 && cfq_cfqq_sync(cfqq); 1791} 1792 1793static void cfq_arm_slice_timer(struct cfq_data *cfqd) 1794{ 1795 struct cfq_queue *cfqq = cfqd->active_queue; 1796 struct cfq_io_context *cic; 1797 unsigned long sl; 1798 1799 /* 1800 * SSD device without seek penalty, disable idling. But only do so 1801 * for devices that support queuing, otherwise we still have a problem 1802 * with sync vs async workloads. 1803 */ 1804 if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag) 1805 return; 1806 1807 WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list)); 1808 WARN_ON(cfq_cfqq_slice_new(cfqq)); 1809 1810 /* 1811 * idle is disabled, either manually or by past process history 1812 */ 1813 if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq)) 1814 return; 1815 1816 /* 1817 * still active requests from this queue, don't idle 1818 */ 1819 if (cfqq->dispatched) 1820 return; 1821 1822 /* 1823 * task has exited, don't wait 1824 */ 1825 cic = cfqd->active_cic; 1826 if (!cic || !atomic_read(&cic->ioc->nr_tasks)) 1827 return; 1828 1829 /* 1830 * If our average think time is larger than the remaining time 1831 * slice, then don't idle. This avoids overrunning the allotted 1832 * time slice. 1833 */ 1834 if (sample_valid(cic->ttime_samples) && 1835 (cfqq->slice_end - jiffies < cic->ttime_mean)) 1836 return; 1837 1838 cfq_mark_cfqq_wait_request(cfqq); 1839 1840 sl = cfqd->cfq_slice_idle; 1841 1842 mod_timer(&cfqd->idle_slice_timer, jiffies + sl); 1843 cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl); 1844} 1845 1846/* 1847 * Move request from internal lists to the request queue dispatch list. 1848 */ 1849static void cfq_dispatch_insert(struct request_queue *q, struct request *rq) 1850{ 1851 struct cfq_data *cfqd = q->elevator->elevator_data; 1852 struct cfq_queue *cfqq = RQ_CFQQ(rq); 1853 1854 cfq_log_cfqq(cfqd, cfqq, "dispatch_insert"); 1855 1856 cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq); 1857 cfq_remove_request(rq); 1858 cfqq->dispatched++; 1859 elv_dispatch_sort(q, rq); 1860 1861 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++; 1862 cfqq->nr_sectors += blk_rq_sectors(rq); 1863} 1864 1865/* 1866 * return expired entry, or NULL to just start from scratch in rbtree 1867 */ 1868static struct request *cfq_check_fifo(struct cfq_queue *cfqq) 1869{ 1870 struct request *rq = NULL; 1871 1872 if (cfq_cfqq_fifo_expire(cfqq)) 1873 return NULL; 1874 1875 cfq_mark_cfqq_fifo_expire(cfqq); 1876 1877 if (list_empty(&cfqq->fifo)) 1878 return NULL; 1879 1880 rq = rq_entry_fifo(cfqq->fifo.next); 1881 if (time_before(jiffies, rq_fifo_time(rq))) 1882 rq = NULL; 1883 1884 cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq); 1885 return rq; 1886} 1887 1888static inline int 1889cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq) 1890{ 1891 const int base_rq = cfqd->cfq_slice_async_rq; 1892 1893 WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR); 1894 1895 return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio)); 1896} 1897 1898/* 1899 * Must be called with the queue_lock held. 1900 */ 1901static int cfqq_process_refs(struct cfq_queue *cfqq) 1902{ 1903 int process_refs, io_refs; 1904 1905 io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE]; 1906 process_refs = atomic_read(&cfqq->ref) - io_refs; 1907 BUG_ON(process_refs < 0); 1908 return process_refs; 1909} 1910 1911static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq) 1912{ 1913 int process_refs, new_process_refs; 1914 struct cfq_queue *__cfqq; 1915 1916 /* Avoid a circular list and skip interim queue merges */ 1917 while ((__cfqq = new_cfqq->new_cfqq)) { 1918 if (__cfqq == cfqq) 1919 return; 1920 new_cfqq = __cfqq; 1921 } 1922 1923 process_refs = cfqq_process_refs(cfqq); 1924 /* 1925 * If the process for the cfqq has gone away, there is no 1926 * sense in merging the queues. 1927 */ 1928 if (process_refs == 0) 1929 return; 1930 1931 /* 1932 * Merge in the direction of the lesser amount of work. 1933 */ 1934 new_process_refs = cfqq_process_refs(new_cfqq); 1935 if (new_process_refs >= process_refs) { 1936 cfqq->new_cfqq = new_cfqq; 1937 atomic_add(process_refs, &new_cfqq->ref); 1938 } else { 1939 new_cfqq->new_cfqq = cfqq; 1940 atomic_add(new_process_refs, &cfqq->ref); 1941 } 1942} 1943 1944static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd, 1945 struct cfq_group *cfqg, enum wl_prio_t prio) 1946{ 1947 struct cfq_queue *queue; 1948 int i; 1949 bool key_valid = false; 1950 unsigned long lowest_key = 0; 1951 enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD; 1952 1953 for (i = 0; i <= SYNC_WORKLOAD; ++i) { 1954 /* select the one with lowest rb_key */ 1955 queue = cfq_rb_first(service_tree_for(cfqg, prio, i)); 1956 if (queue && 1957 (!key_valid || time_before(queue->rb_key, lowest_key))) { 1958 lowest_key = queue->rb_key; 1959 cur_best = i; 1960 key_valid = true; 1961 } 1962 } 1963 1964 return cur_best; 1965} 1966 1967static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg) 1968{ 1969 unsigned slice; 1970 unsigned count; 1971 struct cfq_rb_root *st; 1972 unsigned group_slice; 1973 1974 if (!cfqg) { 1975 cfqd->serving_prio = IDLE_WORKLOAD; 1976 cfqd->workload_expires = jiffies + 1; 1977 return; 1978 } 1979 1980 /* Choose next priority. RT > BE > IDLE */ 1981 if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg)) 1982 cfqd->serving_prio = RT_WORKLOAD; 1983 else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg)) 1984 cfqd->serving_prio = BE_WORKLOAD; 1985 else { 1986 cfqd->serving_prio = IDLE_WORKLOAD; 1987 cfqd->workload_expires = jiffies + 1; 1988 return; 1989 } 1990 1991 /* 1992 * For RT and BE, we have to choose also the type 1993 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload 1994 * expiration time 1995 */ 1996 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type); 1997 count = st->count; 1998 1999 /* 2000 * check workload expiration, and that we still have other queues ready 2001 */ 2002 if (count && !time_after(jiffies, cfqd->workload_expires)) 2003 return; 2004 2005 /* otherwise select new workload type */ 2006 cfqd->serving_type = 2007 cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio); 2008 st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type); 2009 count = st->count; 2010 2011 /* 2012 * the workload slice is computed as a fraction of target latency 2013 * proportional to the number of queues in that workload, over 2014 * all the queues in the same priority class 2015 */ 2016 group_slice = cfq_group_slice(cfqd, cfqg); 2017 2018 slice = group_slice * count / 2019 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio], 2020 cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg)); 2021 2022 if (cfqd->serving_type == ASYNC_WORKLOAD) { 2023 unsigned int tmp; 2024 2025 /* 2026 * Async queues are currently system wide. Just taking 2027 * proportion of queues with-in same group will lead to higher 2028 * async ratio system wide as generally root group is going 2029 * to have higher weight. A more accurate thing would be to 2030 * calculate system wide asnc/sync ratio. 2031 */ 2032 tmp = cfq_target_latency * cfqg_busy_async_queues(cfqd, cfqg); 2033 tmp = tmp/cfqd->busy_queues; 2034 slice = min_t(unsigned, slice, tmp); 2035 2036 /* async workload slice is scaled down according to 2037 * the sync/async slice ratio. */ 2038 slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1]; 2039 } else 2040 /* sync workload slice is at least 2 * cfq_slice_idle */ 2041 slice = max(slice, 2 * cfqd->cfq_slice_idle); 2042 2043 slice = max_t(unsigned, slice, CFQ_MIN_TT); 2044 cfqd->workload_expires = jiffies + slice; 2045 cfqd->noidle_tree_requires_idle = false; 2046} 2047 2048static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd) 2049{ 2050 struct cfq_rb_root *st = &cfqd->grp_service_tree; 2051 struct cfq_group *cfqg; 2052 2053 if (RB_EMPTY_ROOT(&st->rb)) 2054 return NULL; 2055 cfqg = cfq_rb_first_group(st); 2056 st->active = &cfqg->rb_node; 2057 update_min_vdisktime(st); 2058 return cfqg; 2059} 2060 2061static void cfq_choose_cfqg(struct cfq_data *cfqd) 2062{ 2063 struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd); 2064 2065 cfqd->serving_group = cfqg; 2066 2067 /* Restore the workload type data */ 2068 if (cfqg->saved_workload_slice) { 2069 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice; 2070 cfqd->serving_type = cfqg->saved_workload; 2071 cfqd->serving_prio = cfqg->saved_serving_prio; 2072 } else 2073 cfqd->workload_expires = jiffies - 1; 2074 2075 choose_service_tree(cfqd, cfqg); 2076} 2077 2078/* 2079 * Select a queue for service. If we have a current active queue, 2080 * check whether to continue servicing it, or retrieve and set a new one. 2081 */ 2082static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd) 2083{ 2084 struct cfq_queue *cfqq, *new_cfqq = NULL; 2085 2086 cfqq = cfqd->active_queue; 2087 if (!cfqq) 2088 goto new_queue; 2089 2090 if (!cfqd->rq_queued) 2091 return NULL; 2092 2093 /* 2094 * We were waiting for group to get backlogged. Expire the queue 2095 */ 2096 if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list)) 2097 goto expire; 2098 2099 /* 2100 * The active queue has run out of time, expire it and select new. 2101 */ 2102 if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) { 2103 /* 2104 * If slice had not expired at the completion of last request 2105 * we might not have turned on wait_busy flag. Don't expire 2106 * the queue yet. Allow the group to get backlogged. 2107 * 2108 * The very fact that we have used the slice, that means we 2109 * have been idling all along on this queue and it should be 2110 * ok to wait for this request to complete. 2111 */ 2112 if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list) 2113 && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) { 2114 cfqq = NULL; 2115 goto keep_queue; 2116 } else 2117 goto expire; 2118 } 2119 2120 /* 2121 * The active queue has requests and isn't expired, allow it to 2122 * dispatch. 2123 */ 2124 if (!RB_EMPTY_ROOT(&cfqq->sort_list)) 2125 goto keep_queue; 2126 2127 /* 2128 * If another queue has a request waiting within our mean seek 2129 * distance, let it run. The expire code will check for close 2130 * cooperators and put the close queue at the front of the service 2131 * tree. If possible, merge the expiring queue with the new cfqq. 2132 */ 2133 new_cfqq = cfq_close_cooperator(cfqd, cfqq); 2134 if (new_cfqq) { 2135 if (!cfqq->new_cfqq) 2136 cfq_setup_merge(cfqq, new_cfqq); 2137 goto expire; 2138 } 2139 2140 /* 2141 * No requests pending. If the active queue still has requests in 2142 * flight or is idling for a new request, allow either of these 2143 * conditions to happen (or time out) before selecting a new queue. 2144 */ 2145 if (timer_pending(&cfqd->idle_slice_timer) || 2146 (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) { 2147 cfqq = NULL; 2148 goto keep_queue; 2149 } 2150 2151expire: 2152 cfq_slice_expired(cfqd, 0); 2153new_queue: 2154 /* 2155 * Current queue expired. Check if we have to switch to a new 2156 * service tree 2157 */ 2158 if (!new_cfqq) 2159 cfq_choose_cfqg(cfqd); 2160 2161 cfqq = cfq_set_active_queue(cfqd, new_cfqq); 2162keep_queue: 2163 return cfqq; 2164} 2165 2166static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq) 2167{ 2168 int dispatched = 0; 2169 2170 while (cfqq->next_rq) { 2171 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq); 2172 dispatched++; 2173 } 2174 2175 BUG_ON(!list_empty(&cfqq->fifo)); 2176 2177 /* By default cfqq is not expired if it is empty. Do it explicitly */ 2178 __cfq_slice_expired(cfqq->cfqd, cfqq, 0); 2179 return dispatched; 2180} 2181 2182/* 2183 * Drain our current requests. Used for barriers and when switching 2184 * io schedulers on-the-fly. 2185 */ 2186static int cfq_forced_dispatch(struct cfq_data *cfqd) 2187{ 2188 struct cfq_queue *cfqq; 2189 int dispatched = 0; 2190 2191 while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) 2192 dispatched += __cfq_forced_dispatch_cfqq(cfqq); 2193 2194 cfq_slice_expired(cfqd, 0); 2195 BUG_ON(cfqd->busy_queues); 2196 2197 cfq_log(cfqd, "forced_dispatch=%d", dispatched); 2198 return dispatched; 2199} 2200 2201static inline bool cfq_slice_used_soon(struct cfq_data *cfqd, 2202 struct cfq_queue *cfqq) 2203{ 2204 /* the queue hasn't finished any request, can't estimate */ 2205 if (cfq_cfqq_slice_new(cfqq)) 2206 return 1; 2207 if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched, 2208 cfqq->slice_end)) 2209 return 1; 2210 2211 return 0; 2212} 2213 2214static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq) 2215{ 2216 unsigned int max_dispatch; 2217 2218 /* 2219 * Drain async requests before we start sync IO 2220 */ 2221 if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC]) 2222 return false; 2223 2224 /* 2225 * If this is an async queue and we have sync IO in flight, let it wait 2226 */ 2227 if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq)) 2228 return false; 2229 2230 max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1); 2231 if (cfq_class_idle(cfqq)) 2232 max_dispatch = 1; 2233 2234 /* 2235 * Does this cfqq already have too much IO in flight? 2236 */ 2237 if (cfqq->dispatched >= max_dispatch) { 2238 /* 2239 * idle queue must always only have a single IO in flight 2240 */ 2241 if (cfq_class_idle(cfqq)) 2242 return false; 2243 2244 /* 2245 * We have other queues, don't allow more IO from this one 2246 */ 2247 if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq)) 2248 return false; 2249 2250 /* 2251 * Sole queue user, no limit 2252 */ 2253 if (cfqd->busy_queues == 1) 2254 max_dispatch = -1; 2255 else 2256 /* 2257 * Normally we start throttling cfqq when cfq_quantum/2 2258 * requests have been dispatched. But we can drive 2259 * deeper queue depths at the beginning of slice 2260 * subjected to upper limit of cfq_quantum. 2261 * */ 2262 max_dispatch = cfqd->cfq_quantum; 2263 } 2264 2265 /* 2266 * Async queues must wait a bit before being allowed dispatch. 2267 * We also ramp up the dispatch depth gradually for async IO, 2268 * based on the last sync IO we serviced 2269 */ 2270 if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) { 2271 unsigned long last_sync = jiffies - cfqd->last_delayed_sync; 2272 unsigned int depth; 2273 2274 depth = last_sync / cfqd->cfq_slice[1]; 2275 if (!depth && !cfqq->dispatched) 2276 depth = 1; 2277 if (depth < max_dispatch) 2278 max_dispatch = depth; 2279 } 2280 2281 /* 2282 * If we're below the current max, allow a dispatch 2283 */ 2284 return cfqq->dispatched < max_dispatch; 2285} 2286 2287/* 2288 * Dispatch a request from cfqq, moving them to the request queue 2289 * dispatch list. 2290 */ 2291static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq) 2292{ 2293 struct request *rq; 2294 2295 BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list)); 2296 2297 if (!cfq_may_dispatch(cfqd, cfqq)) 2298 return false; 2299 2300 /* 2301 * follow expired path, else get first next available 2302 */ 2303 rq = cfq_check_fifo(cfqq); 2304 if (!rq) 2305 rq = cfqq->next_rq; 2306 2307 /* 2308 * insert request into driver dispatch list 2309 */ 2310 cfq_dispatch_insert(cfqd->queue, rq); 2311 2312 if (!cfqd->active_cic) { 2313 struct cfq_io_context *cic = RQ_CIC(rq); 2314 2315 atomic_long_inc(&cic->ioc->refcount); 2316 cfqd->active_cic = cic; 2317 } 2318 2319 return true; 2320} 2321 2322/* 2323 * Find the cfqq that we need to service and move a request from that to the 2324 * dispatch list 2325 */ 2326static int cfq_dispatch_requests(struct request_queue *q, int force) 2327{ 2328 struct cfq_data *cfqd = q->elevator->elevator_data; 2329 struct cfq_queue *cfqq; 2330 2331 if (!cfqd->busy_queues) 2332 return 0; 2333 2334 if (unlikely(force)) 2335 return cfq_forced_dispatch(cfqd); 2336 2337 cfqq = cfq_select_queue(cfqd); 2338 if (!cfqq) 2339 return 0; 2340 2341 /* 2342 * Dispatch a request from this cfqq, if it is allowed 2343 */ 2344 if (!cfq_dispatch_request(cfqd, cfqq)) 2345 return 0; 2346 2347 cfqq->slice_dispatch++; 2348 cfq_clear_cfqq_must_dispatch(cfqq); 2349 2350 /* 2351 * expire an async queue immediately if it has used up its slice. idle 2352 * queue always expire after 1 dispatch round. 2353 */ 2354 if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) && 2355 cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) || 2356 cfq_class_idle(cfqq))) { 2357 cfqq->slice_end = jiffies + 1; 2358 cfq_slice_expired(cfqd, 0); 2359 } 2360 2361 cfq_log_cfqq(cfqd, cfqq, "dispatched a request"); 2362 return 1; 2363} 2364 2365/* 2366 * task holds one reference to the queue, dropped when task exits. each rq 2367 * in-flight on this queue also holds a reference, dropped when rq is freed. 2368 * 2369 * Each cfq queue took a reference on the parent group. Drop it now. 2370 * queue lock must be held here. 2371 */ 2372static void cfq_put_queue(struct cfq_queue *cfqq) 2373{ 2374 struct cfq_data *cfqd = cfqq->cfqd; 2375 struct cfq_group *cfqg, *orig_cfqg; 2376 2377 BUG_ON(atomic_read(&cfqq->ref) <= 0); 2378 2379 if (!atomic_dec_and_test(&cfqq->ref)) 2380 return; 2381 2382 cfq_log_cfqq(cfqd, cfqq, "put_queue"); 2383 BUG_ON(rb_first(&cfqq->sort_list)); 2384 BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]); 2385 cfqg = cfqq->cfqg; 2386 orig_cfqg = cfqq->orig_cfqg; 2387 2388 if (unlikely(cfqd->active_queue == cfqq)) { 2389 __cfq_slice_expired(cfqd, cfqq, 0); 2390 cfq_schedule_dispatch(cfqd); 2391 } 2392 2393 BUG_ON(cfq_cfqq_on_rr(cfqq)); 2394 kmem_cache_free(cfq_pool, cfqq); 2395 cfq_put_cfqg(cfqg); 2396 if (orig_cfqg) 2397 cfq_put_cfqg(orig_cfqg); 2398} 2399 2400/* 2401 * Must always be called with the rcu_read_lock() held 2402 */ 2403static void 2404__call_for_each_cic(struct io_context *ioc, 2405 void (*func)(struct io_context *, struct cfq_io_context *)) 2406{ 2407 struct cfq_io_context *cic; 2408 struct hlist_node *n; 2409 2410 hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list) 2411 func(ioc, cic); 2412} 2413 2414/* 2415 * Call func for each cic attached to this ioc. 2416 */ 2417static void 2418call_for_each_cic(struct io_context *ioc, 2419 void (*func)(struct io_context *, struct cfq_io_context *)) 2420{ 2421 rcu_read_lock(); 2422 __call_for_each_cic(ioc, func); 2423 rcu_read_unlock(); 2424} 2425 2426static void cfq_cic_free_rcu(struct rcu_head *head) 2427{ 2428 struct cfq_io_context *cic; 2429 2430 cic = container_of(head, struct cfq_io_context, rcu_head); 2431 2432 kmem_cache_free(cfq_ioc_pool, cic); 2433 elv_ioc_count_dec(cfq_ioc_count); 2434 2435 if (ioc_gone) { 2436 /* 2437 * CFQ scheduler is exiting, grab exit lock and check 2438 * the pending io context count. If it hits zero, 2439 * complete ioc_gone and set it back to NULL 2440 */ 2441 spin_lock(&ioc_gone_lock); 2442 if (ioc_gone && !elv_ioc_count_read(cfq_ioc_count)) { 2443 complete(ioc_gone); 2444 ioc_gone = NULL; 2445 } 2446 spin_unlock(&ioc_gone_lock); 2447 } 2448} 2449 2450static void cfq_cic_free(struct cfq_io_context *cic) 2451{ 2452 call_rcu(&cic->rcu_head, cfq_cic_free_rcu); 2453} 2454 2455static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic) 2456{ 2457 unsigned long flags; 2458 2459 BUG_ON(!cic->dead_key); 2460 2461 spin_lock_irqsave(&ioc->lock, flags); 2462 radix_tree_delete(&ioc->radix_root, cic->dead_key); 2463 hlist_del_rcu(&cic->cic_list); 2464 spin_unlock_irqrestore(&ioc->lock, flags); 2465 2466 cfq_cic_free(cic); 2467} 2468 2469/* 2470 * Must be called with rcu_read_lock() held or preemption otherwise disabled. 2471 * Only two callers of this - ->dtor() which is called with the rcu_read_lock(), 2472 * and ->trim() which is called with the task lock held 2473 */ 2474static void cfq_free_io_context(struct io_context *ioc) 2475{ 2476 /* 2477 * ioc->refcount is zero here, or we are called from elv_unregister(), 2478 * so no more cic's are allowed to be linked into this ioc. So it 2479 * should be ok to iterate over the known list, we will see all cic's 2480 * since no new ones are added. 2481 */ 2482 __call_for_each_cic(ioc, cic_free_func); 2483} 2484 2485static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq) 2486{ 2487 struct cfq_queue *__cfqq, *next; 2488 2489 if (unlikely(cfqq == cfqd->active_queue)) { 2490 __cfq_slice_expired(cfqd, cfqq, 0); 2491 cfq_schedule_dispatch(cfqd); 2492 } 2493 2494 /* 2495 * If this queue was scheduled to merge with another queue, be 2496 * sure to drop the reference taken on that queue (and others in 2497 * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs. 2498 */ 2499 __cfqq = cfqq->new_cfqq; 2500 while (__cfqq) { 2501 if (__cfqq == cfqq) { 2502 WARN(1, "cfqq->new_cfqq loop detected\n"); 2503 break; 2504 } 2505 next = __cfqq->new_cfqq; 2506 cfq_put_queue(__cfqq); 2507 __cfqq = next; 2508 } 2509 2510 cfq_put_queue(cfqq); 2511} 2512 2513static void __cfq_exit_single_io_context(struct cfq_data *cfqd, 2514 struct cfq_io_context *cic) 2515{ 2516 struct io_context *ioc = cic->ioc; 2517 2518 list_del_init(&cic->queue_list); 2519 2520 /* 2521 * Make sure key == NULL is seen for dead queues 2522 */ 2523 smp_wmb(); 2524 cic->dead_key = (unsigned long) cic->key; 2525 cic->key = NULL; 2526 2527 if (ioc->ioc_data == cic) 2528 rcu_assign_pointer(ioc->ioc_data, NULL); 2529 2530 if (cic->cfqq[BLK_RW_ASYNC]) { 2531 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]); 2532 cic->cfqq[BLK_RW_ASYNC] = NULL; 2533 } 2534 2535 if (cic->cfqq[BLK_RW_SYNC]) { 2536 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]); 2537 cic->cfqq[BLK_RW_SYNC] = NULL; 2538 } 2539} 2540 2541static void cfq_exit_single_io_context(struct io_context *ioc, 2542 struct cfq_io_context *cic) 2543{ 2544 struct cfq_data *cfqd = cic->key; 2545 2546 if (cfqd) { 2547 struct request_queue *q = cfqd->queue; 2548 unsigned long flags; 2549 2550 spin_lock_irqsave(q->queue_lock, flags); 2551 2552 /* 2553 * Ensure we get a fresh copy of the ->key to prevent 2554 * race between exiting task and queue 2555 */ 2556 smp_read_barrier_depends(); 2557 if (cic->key) 2558 __cfq_exit_single_io_context(cfqd, cic); 2559 2560 spin_unlock_irqrestore(q->queue_lock, flags); 2561 } 2562} 2563 2564/* 2565 * The process that ioc belongs to has exited, we need to clean up 2566 * and put the internal structures we have that belongs to that process. 2567 */ 2568static void cfq_exit_io_context(struct io_context *ioc) 2569{ 2570 call_for_each_cic(ioc, cfq_exit_single_io_context); 2571} 2572 2573static struct cfq_io_context * 2574cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask) 2575{ 2576 struct cfq_io_context *cic; 2577 2578 cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO, 2579 cfqd->queue->node); 2580 if (cic) { 2581 cic->last_end_request = jiffies; 2582 INIT_LIST_HEAD(&cic->queue_list); 2583 INIT_HLIST_NODE(&cic->cic_list); 2584 cic->dtor = cfq_free_io_context; 2585 cic->exit = cfq_exit_io_context; 2586 elv_ioc_count_inc(cfq_ioc_count); 2587 } 2588 2589 return cic; 2590} 2591 2592static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc) 2593{ 2594 struct task_struct *tsk = current; 2595 int ioprio_class; 2596 2597 if (!cfq_cfqq_prio_changed(cfqq)) 2598 return; 2599 2600 ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio); 2601 switch (ioprio_class) { 2602 default: 2603 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class); 2604 case IOPRIO_CLASS_NONE: 2605 /* 2606 * no prio set, inherit CPU scheduling settings 2607 */ 2608 cfqq->ioprio = task_nice_ioprio(tsk); 2609 cfqq->ioprio_class = task_nice_ioclass(tsk); 2610 break; 2611 case IOPRIO_CLASS_RT: 2612 cfqq->ioprio = task_ioprio(ioc); 2613 cfqq->ioprio_class = IOPRIO_CLASS_RT; 2614 break; 2615 case IOPRIO_CLASS_BE: 2616 cfqq->ioprio = task_ioprio(ioc); 2617 cfqq->ioprio_class = IOPRIO_CLASS_BE; 2618 break; 2619 case IOPRIO_CLASS_IDLE: 2620 cfqq->ioprio_class = IOPRIO_CLASS_IDLE; 2621 cfqq->ioprio = 7; 2622 cfq_clear_cfqq_idle_window(cfqq); 2623 break; 2624 } 2625 2626 /* 2627 * keep track of original prio settings in case we have to temporarily 2628 * elevate the priority of this queue 2629 */ 2630 cfqq->org_ioprio = cfqq->ioprio; 2631 cfqq->org_ioprio_class = cfqq->ioprio_class; 2632 cfq_clear_cfqq_prio_changed(cfqq); 2633} 2634 2635static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic) 2636{ 2637 struct cfq_data *cfqd = cic->key; 2638 struct cfq_queue *cfqq; 2639 unsigned long flags; 2640 2641 if (unlikely(!cfqd)) 2642 return; 2643 2644 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 2645 2646 cfqq = cic->cfqq[BLK_RW_ASYNC]; 2647 if (cfqq) { 2648 struct cfq_queue *new_cfqq; 2649 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc, 2650 GFP_ATOMIC); 2651 if (new_cfqq) { 2652 cic->cfqq[BLK_RW_ASYNC] = new_cfqq; 2653 cfq_put_queue(cfqq); 2654 } 2655 } 2656 2657 cfqq = cic->cfqq[BLK_RW_SYNC]; 2658 if (cfqq) 2659 cfq_mark_cfqq_prio_changed(cfqq); 2660 2661 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 2662} 2663 2664static void cfq_ioc_set_ioprio(struct io_context *ioc) 2665{ 2666 call_for_each_cic(ioc, changed_ioprio); 2667 ioc->ioprio_changed = 0; 2668} 2669 2670static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq, 2671 pid_t pid, bool is_sync) 2672{ 2673 RB_CLEAR_NODE(&cfqq->rb_node); 2674 RB_CLEAR_NODE(&cfqq->p_node); 2675 INIT_LIST_HEAD(&cfqq->fifo); 2676 2677 atomic_set(&cfqq->ref, 0); 2678 cfqq->cfqd = cfqd; 2679 2680 cfq_mark_cfqq_prio_changed(cfqq); 2681 2682 if (is_sync) { 2683 if (!cfq_class_idle(cfqq)) 2684 cfq_mark_cfqq_idle_window(cfqq); 2685 cfq_mark_cfqq_sync(cfqq); 2686 } 2687 cfqq->pid = pid; 2688} 2689 2690#ifdef CONFIG_CFQ_GROUP_IOSCHED 2691static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic) 2692{ 2693 struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1); 2694 struct cfq_data *cfqd = cic->key; 2695 unsigned long flags; 2696 struct request_queue *q; 2697 2698 if (unlikely(!cfqd)) 2699 return; 2700 2701 q = cfqd->queue; 2702 2703 spin_lock_irqsave(q->queue_lock, flags); 2704 2705 if (sync_cfqq) { 2706 /* 2707 * Drop reference to sync queue. A new sync queue will be 2708 * assigned in new group upon arrival of a fresh request. 2709 */ 2710 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup"); 2711 cic_set_cfqq(cic, NULL, 1); 2712 cfq_put_queue(sync_cfqq); 2713 } 2714 2715 spin_unlock_irqrestore(q->queue_lock, flags); 2716} 2717 2718static void cfq_ioc_set_cgroup(struct io_context *ioc) 2719{ 2720 call_for_each_cic(ioc, changed_cgroup); 2721 ioc->cgroup_changed = 0; 2722} 2723#endif /* CONFIG_CFQ_GROUP_IOSCHED */ 2724 2725static struct cfq_queue * 2726cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync, 2727 struct io_context *ioc, gfp_t gfp_mask) 2728{ 2729 struct cfq_queue *cfqq, *new_cfqq = NULL; 2730 struct cfq_io_context *cic; 2731 struct cfq_group *cfqg; 2732 2733retry: 2734 cfqg = cfq_get_cfqg(cfqd, 1); 2735 cic = cfq_cic_lookup(cfqd, ioc); 2736 /* cic always exists here */ 2737 cfqq = cic_to_cfqq(cic, is_sync); 2738 2739 /* 2740 * Always try a new alloc if we fell back to the OOM cfqq 2741 * originally, since it should just be a temporary situation. 2742 */ 2743 if (!cfqq || cfqq == &cfqd->oom_cfqq) { 2744 cfqq = NULL; 2745 if (new_cfqq) { 2746 cfqq = new_cfqq; 2747 new_cfqq = NULL; 2748 } else if (gfp_mask & __GFP_WAIT) { 2749 spin_unlock_irq(cfqd->queue->queue_lock); 2750 new_cfqq = kmem_cache_alloc_node(cfq_pool, 2751 gfp_mask | __GFP_ZERO, 2752 cfqd->queue->node); 2753 spin_lock_irq(cfqd->queue->queue_lock); 2754 if (new_cfqq) 2755 goto retry; 2756 } else { 2757 cfqq = kmem_cache_alloc_node(cfq_pool, 2758 gfp_mask | __GFP_ZERO, 2759 cfqd->queue->node); 2760 } 2761 2762 if (cfqq) { 2763 cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync); 2764 cfq_init_prio_data(cfqq, ioc); 2765 cfq_link_cfqq_cfqg(cfqq, cfqg); 2766 cfq_log_cfqq(cfqd, cfqq, "alloced"); 2767 } else 2768 cfqq = &cfqd->oom_cfqq; 2769 } 2770 2771 if (new_cfqq) 2772 kmem_cache_free(cfq_pool, new_cfqq); 2773 2774 return cfqq; 2775} 2776 2777static struct cfq_queue ** 2778cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio) 2779{ 2780 switch (ioprio_class) { 2781 case IOPRIO_CLASS_RT: 2782 return &cfqd->async_cfqq[0][ioprio]; 2783 case IOPRIO_CLASS_BE: 2784 return &cfqd->async_cfqq[1][ioprio]; 2785 case IOPRIO_CLASS_IDLE: 2786 return &cfqd->async_idle_cfqq; 2787 default: 2788 BUG(); 2789 } 2790} 2791 2792static struct cfq_queue * 2793cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc, 2794 gfp_t gfp_mask) 2795{ 2796 const int ioprio = task_ioprio(ioc); 2797 const int ioprio_class = task_ioprio_class(ioc); 2798 struct cfq_queue **async_cfqq = NULL; 2799 struct cfq_queue *cfqq = NULL; 2800 2801 if (!is_sync) { 2802 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio); 2803 cfqq = *async_cfqq; 2804 } 2805 2806 if (!cfqq) 2807 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask); 2808 2809 /* 2810 * pin the queue now that it's allocated, scheduler exit will prune it 2811 */ 2812 if (!is_sync && !(*async_cfqq)) { 2813 atomic_inc(&cfqq->ref); 2814 *async_cfqq = cfqq; 2815 } 2816 2817 atomic_inc(&cfqq->ref); 2818 return cfqq; 2819} 2820 2821/* 2822 * We drop cfq io contexts lazily, so we may find a dead one. 2823 */ 2824static void 2825cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc, 2826 struct cfq_io_context *cic) 2827{ 2828 unsigned long flags; 2829 2830 WARN_ON(!list_empty(&cic->queue_list)); 2831 2832 spin_lock_irqsave(&ioc->lock, flags); 2833 2834 BUG_ON(ioc->ioc_data == cic); 2835 2836 radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd); 2837 hlist_del_rcu(&cic->cic_list); 2838 spin_unlock_irqrestore(&ioc->lock, flags); 2839 2840 cfq_cic_free(cic); 2841} 2842 2843static struct cfq_io_context * 2844cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc) 2845{ 2846 struct cfq_io_context *cic; 2847 unsigned long flags; 2848 void *k; 2849 2850 if (unlikely(!ioc)) 2851 return NULL; 2852 2853 rcu_read_lock(); 2854 2855 /* 2856 * we maintain a last-hit cache, to avoid browsing over the tree 2857 */ 2858 cic = rcu_dereference(ioc->ioc_data); 2859 if (cic && cic->key == cfqd) { 2860 rcu_read_unlock(); 2861 return cic; 2862 } 2863 2864 do { 2865 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd); 2866 rcu_read_unlock(); 2867 if (!cic) 2868 break; 2869 /* ->key must be copied to avoid race with cfq_exit_queue() */ 2870 k = cic->key; 2871 if (unlikely(!k)) { 2872 cfq_drop_dead_cic(cfqd, ioc, cic); 2873 rcu_read_lock(); 2874 continue; 2875 } 2876 2877 spin_lock_irqsave(&ioc->lock, flags); 2878 rcu_assign_pointer(ioc->ioc_data, cic); 2879 spin_unlock_irqrestore(&ioc->lock, flags); 2880 break; 2881 } while (1); 2882 2883 return cic; 2884} 2885 2886/* 2887 * Add cic into ioc, using cfqd as the search key. This enables us to lookup 2888 * the process specific cfq io context when entered from the block layer. 2889 * Also adds the cic to a per-cfqd list, used when this queue is removed. 2890 */ 2891static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc, 2892 struct cfq_io_context *cic, gfp_t gfp_mask) 2893{ 2894 unsigned long flags; 2895 int ret; 2896 2897 ret = radix_tree_preload(gfp_mask); 2898 if (!ret) { 2899 cic->ioc = ioc; 2900 cic->key = cfqd; 2901 2902 spin_lock_irqsave(&ioc->lock, flags); 2903 ret = radix_tree_insert(&ioc->radix_root, 2904 (unsigned long) cfqd, cic); 2905 if (!ret) 2906 hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list); 2907 spin_unlock_irqrestore(&ioc->lock, flags); 2908 2909 radix_tree_preload_end(); 2910 2911 if (!ret) { 2912 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 2913 list_add(&cic->queue_list, &cfqd->cic_list); 2914 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 2915 } 2916 } 2917 2918 if (ret) 2919 printk(KERN_ERR "cfq: cic link failed!\n"); 2920 2921 return ret; 2922} 2923 2924/* 2925 * Setup general io context and cfq io context. There can be several cfq 2926 * io contexts per general io context, if this process is doing io to more 2927 * than one device managed by cfq. 2928 */ 2929static struct cfq_io_context * 2930cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask) 2931{ 2932 struct io_context *ioc = NULL; 2933 struct cfq_io_context *cic; 2934 2935 might_sleep_if(gfp_mask & __GFP_WAIT); 2936 2937 ioc = get_io_context(gfp_mask, cfqd->queue->node); 2938 if (!ioc) 2939 return NULL; 2940 2941 cic = cfq_cic_lookup(cfqd, ioc); 2942 if (cic) 2943 goto out; 2944 2945 cic = cfq_alloc_io_context(cfqd, gfp_mask); 2946 if (cic == NULL) 2947 goto err; 2948 2949 if (cfq_cic_link(cfqd, ioc, cic, gfp_mask)) 2950 goto err_free; 2951 2952out: 2953 smp_read_barrier_depends(); 2954 if (unlikely(ioc->ioprio_changed)) 2955 cfq_ioc_set_ioprio(ioc); 2956 2957#ifdef CONFIG_CFQ_GROUP_IOSCHED 2958 if (unlikely(ioc->cgroup_changed)) 2959 cfq_ioc_set_cgroup(ioc); 2960#endif 2961 return cic; 2962err_free: 2963 cfq_cic_free(cic); 2964err: 2965 put_io_context(ioc); 2966 return NULL; 2967} 2968 2969static void 2970cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic) 2971{ 2972 unsigned long elapsed = jiffies - cic->last_end_request; 2973 unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle); 2974 2975 cic->ttime_samples = (7*cic->ttime_samples + 256) / 8; 2976 cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8; 2977 cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples; 2978} 2979 2980static void 2981cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq, 2982 struct request *rq) 2983{ 2984 sector_t sdist = 0; 2985 sector_t n_sec = blk_rq_sectors(rq); 2986 if (cfqq->last_request_pos) { 2987 if (cfqq->last_request_pos < blk_rq_pos(rq)) 2988 sdist = blk_rq_pos(rq) - cfqq->last_request_pos; 2989 else 2990 sdist = cfqq->last_request_pos - blk_rq_pos(rq); 2991 } 2992 2993 cfqq->seek_history <<= 1; 2994 if (blk_queue_nonrot(cfqd->queue)) 2995 cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT); 2996 else 2997 cfqq->seek_history |= (sdist > CFQQ_SEEK_THR); 2998} 2999 3000/* 3001 * Disable idle window if the process thinks too long or seeks so much that 3002 * it doesn't matter 3003 */ 3004static void 3005cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq, 3006 struct cfq_io_context *cic) 3007{ 3008 int old_idle, enable_idle; 3009 3010 /* 3011 * Don't idle for async or idle io prio class 3012 */ 3013 if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq)) 3014 return; 3015 3016 enable_idle = old_idle = cfq_cfqq_idle_window(cfqq); 3017 3018 if (cfqq->queued[0] + cfqq->queued[1] >= 4) 3019 cfq_mark_cfqq_deep(cfqq); 3020 3021 if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle || 3022 (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq))) 3023 enable_idle = 0; 3024 else if (sample_valid(cic->ttime_samples)) { 3025 if (cic->ttime_mean > cfqd->cfq_slice_idle) 3026 enable_idle = 0; 3027 else 3028 enable_idle = 1; 3029 } 3030 3031 if (old_idle != enable_idle) { 3032 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle); 3033 if (enable_idle) 3034 cfq_mark_cfqq_idle_window(cfqq); 3035 else 3036 cfq_clear_cfqq_idle_window(cfqq); 3037 } 3038} 3039 3040/* 3041 * Check if new_cfqq should preempt the currently active queue. Return 0 for 3042 * no or if we aren't sure, a 1 will cause a preempt. 3043 */ 3044static bool 3045cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq, 3046 struct request *rq) 3047{ 3048 struct cfq_queue *cfqq; 3049 3050 cfqq = cfqd->active_queue; 3051 if (!cfqq) 3052 return false; 3053 3054 if (cfq_class_idle(new_cfqq)) 3055 return false; 3056 3057 if (cfq_class_idle(cfqq)) 3058 return true; 3059 3060 /* 3061 * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice. 3062 */ 3063 if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq)) 3064 return false; 3065 3066 /* 3067 * if the new request is sync, but the currently running queue is 3068 * not, let the sync request have priority. 3069 */ 3070 if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq)) 3071 return true; 3072 3073 if (new_cfqq->cfqg != cfqq->cfqg) 3074 return false; 3075 3076 if (cfq_slice_used(cfqq)) 3077 return true; 3078 3079 /* Allow preemption only if we are idling on sync-noidle tree */ 3080 if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD && 3081 cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD && 3082 new_cfqq->service_tree->count == 2 && 3083 RB_EMPTY_ROOT(&cfqq->sort_list)) 3084 return true; 3085 3086 /* 3087 * So both queues are sync. Let the new request get disk time if 3088 * it's a metadata request and the current queue is doing regular IO. 3089 */ 3090 if (rq_is_meta(rq) && !cfqq->meta_pending) 3091 return true; 3092 3093 /* 3094 * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice. 3095 */ 3096 if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq)) 3097 return true; 3098 3099 if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq)) 3100 return false; 3101 3102 /* 3103 * if this request is as-good as one we would expect from the 3104 * current cfqq, let it preempt 3105 */ 3106 if (cfq_rq_close(cfqd, cfqq, rq, true)) 3107 return true; 3108 3109 return false; 3110} 3111 3112/* 3113 * cfqq preempts the active queue. if we allowed preempt with no slice left, 3114 * let it have half of its nominal slice. 3115 */ 3116static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq) 3117{ 3118 cfq_log_cfqq(cfqd, cfqq, "preempt"); 3119 cfq_slice_expired(cfqd, 1); 3120 3121 /* 3122 * Put the new queue at the front of the of the current list, 3123 * so we know that it will be selected next. 3124 */ 3125 BUG_ON(!cfq_cfqq_on_rr(cfqq)); 3126 3127 cfq_service_tree_add(cfqd, cfqq, 1); 3128 3129 cfqq->slice_end = 0; 3130 cfq_mark_cfqq_slice_new(cfqq); 3131} 3132 3133/* 3134 * Called when a new fs request (rq) is added (to cfqq). Check if there's 3135 * something we should do about it 3136 */ 3137static void 3138cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq, 3139 struct request *rq) 3140{ 3141 struct cfq_io_context *cic = RQ_CIC(rq); 3142 3143 cfqd->rq_queued++; 3144 if (rq_is_meta(rq)) 3145 cfqq->meta_pending++; 3146 3147 cfq_update_io_thinktime(cfqd, cic); 3148 cfq_update_io_seektime(cfqd, cfqq, rq); 3149 cfq_update_idle_window(cfqd, cfqq, cic); 3150 3151 cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq); 3152 3153 if (cfqq == cfqd->active_queue) { 3154 /* 3155 * Remember that we saw a request from this process, but 3156 * don't start queuing just yet. Otherwise we risk seeing lots 3157 * of tiny requests, because we disrupt the normal plugging 3158 * and merging. If the request is already larger than a single 3159 * page, let it rip immediately. For that case we assume that 3160 * merging is already done. Ditto for a busy system that 3161 * has other work pending, don't risk delaying until the 3162 * idle timer unplug to continue working. 3163 */ 3164 if (cfq_cfqq_wait_request(cfqq)) { 3165 if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE || 3166 cfqd->busy_queues > 1) { 3167 del_timer(&cfqd->idle_slice_timer); 3168 cfq_clear_cfqq_wait_request(cfqq); 3169 __blk_run_queue(cfqd->queue); 3170 } else 3171 cfq_mark_cfqq_must_dispatch(cfqq); 3172 } 3173 } else if (cfq_should_preempt(cfqd, cfqq, rq)) { 3174 /* 3175 * not the active queue - expire current slice if it is 3176 * idle and has expired it's mean thinktime or this new queue 3177 * has some old slice time left and is of higher priority or 3178 * this new queue is RT and the current one is BE 3179 */ 3180 cfq_preempt_queue(cfqd, cfqq); 3181 __blk_run_queue(cfqd->queue); 3182 } 3183} 3184 3185static void cfq_insert_request(struct request_queue *q, struct request *rq) 3186{ 3187 struct cfq_data *cfqd = q->elevator->elevator_data; 3188 struct cfq_queue *cfqq = RQ_CFQQ(rq); 3189 3190 cfq_log_cfqq(cfqd, cfqq, "insert_request"); 3191 cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc); 3192 3193 rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]); 3194 list_add_tail(&rq->queuelist, &cfqq->fifo); 3195 cfq_add_rq_rb(rq); 3196 3197 cfq_rq_enqueued(cfqd, cfqq, rq); 3198} 3199 3200/* 3201 * Update hw_tag based on peak queue depth over 50 samples under 3202 * sufficient load. 3203 */ 3204static void cfq_update_hw_tag(struct cfq_data *cfqd) 3205{ 3206 struct cfq_queue *cfqq = cfqd->active_queue; 3207 3208 if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth) 3209 cfqd->hw_tag_est_depth = cfqd->rq_in_driver; 3210 3211 if (cfqd->hw_tag == 1) 3212 return; 3213 3214 if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN && 3215 cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN) 3216 return; 3217 3218 /* 3219 * If active queue hasn't enough requests and can idle, cfq might not 3220 * dispatch sufficient requests to hardware. Don't zero hw_tag in this 3221 * case 3222 */ 3223 if (cfqq && cfq_cfqq_idle_window(cfqq) && 3224 cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] < 3225 CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN) 3226 return; 3227 3228 if (cfqd->hw_tag_samples++ < 50) 3229 return; 3230 3231 if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN) 3232 cfqd->hw_tag = 1; 3233 else 3234 cfqd->hw_tag = 0; 3235} 3236 3237static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq) 3238{ 3239 struct cfq_io_context *cic = cfqd->active_cic; 3240 3241 /* If there are other queues in the group, don't wait */ 3242 if (cfqq->cfqg->nr_cfqq > 1) 3243 return false; 3244 3245 if (cfq_slice_used(cfqq)) 3246 return true; 3247 3248 /* if slice left is less than think time, wait busy */ 3249 if (cic && sample_valid(cic->ttime_samples) 3250 && (cfqq->slice_end - jiffies < cic->ttime_mean)) 3251 return true; 3252 3253 /* 3254 * If think times is less than a jiffy than ttime_mean=0 and above 3255 * will not be true. It might happen that slice has not expired yet 3256 * but will expire soon (4-5 ns) during select_queue(). To cover the 3257 * case where think time is less than a jiffy, mark the queue wait 3258 * busy if only 1 jiffy is left in the slice. 3259 */ 3260 if (cfqq->slice_end - jiffies == 1) 3261 return true; 3262 3263 return false; 3264} 3265 3266static void cfq_completed_request(struct request_queue *q, struct request *rq) 3267{ 3268 struct cfq_queue *cfqq = RQ_CFQQ(rq); 3269 struct cfq_data *cfqd = cfqq->cfqd; 3270 const int sync = rq_is_sync(rq); 3271 unsigned long now; 3272 3273 now = jiffies; 3274 cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq)); 3275 3276 cfq_update_hw_tag(cfqd); 3277 3278 WARN_ON(!cfqd->rq_in_driver); 3279 WARN_ON(!cfqq->dispatched); 3280 cfqd->rq_in_driver--; 3281 cfqq->dispatched--; 3282 3283 cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--; 3284 3285 if (sync) { 3286 RQ_CIC(rq)->last_end_request = now; 3287 if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now)) 3288 cfqd->last_delayed_sync = now; 3289 } 3290 3291 /* 3292 * If this is the active queue, check if it needs to be expired, 3293 * or if we want to idle in case it has no pending requests. 3294 */ 3295 if (cfqd->active_queue == cfqq) { 3296 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list); 3297 3298 if (cfq_cfqq_slice_new(cfqq)) { 3299 cfq_set_prio_slice(cfqd, cfqq); 3300 cfq_clear_cfqq_slice_new(cfqq); 3301 } 3302 3303 /* 3304 * Should we wait for next request to come in before we expire 3305 * the queue. 3306 */ 3307 if (cfq_should_wait_busy(cfqd, cfqq)) { 3308 cfqq->slice_end = jiffies + cfqd->cfq_slice_idle; 3309 cfq_mark_cfqq_wait_busy(cfqq); 3310 } 3311 3312 /* 3313 * Idling is not enabled on: 3314 * - expired queues 3315 * - idle-priority queues 3316 * - async queues 3317 * - queues with still some requests queued 3318 * - when there is a close cooperator 3319 */ 3320 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq)) 3321 cfq_slice_expired(cfqd, 1); 3322 else if (sync && cfqq_empty && 3323 !cfq_close_cooperator(cfqd, cfqq)) { 3324 cfqd->noidle_tree_requires_idle |= !rq_noidle(rq); 3325 /* 3326 * Idling is enabled for SYNC_WORKLOAD. 3327 * SYNC_NOIDLE_WORKLOAD idles at the end of the tree 3328 * only if we processed at least one !rq_noidle request 3329 */ 3330 if (cfqd->serving_type == SYNC_WORKLOAD 3331 || cfqd->noidle_tree_requires_idle 3332 || cfqq->cfqg->nr_cfqq == 1) 3333 cfq_arm_slice_timer(cfqd); 3334 } 3335 } 3336 3337 if (!cfqd->rq_in_driver) 3338 cfq_schedule_dispatch(cfqd); 3339} 3340 3341/* 3342 * we temporarily boost lower priority queues if they are holding fs exclusive 3343 * resources. they are boosted to normal prio (CLASS_BE/4) 3344 */ 3345static void cfq_prio_boost(struct cfq_queue *cfqq) 3346{ 3347 if (has_fs_excl()) { 3348 /* 3349 * boost idle prio on transactions that would lock out other 3350 * users of the filesystem 3351 */ 3352 if (cfq_class_idle(cfqq)) 3353 cfqq->ioprio_class = IOPRIO_CLASS_BE; 3354 if (cfqq->ioprio > IOPRIO_NORM) 3355 cfqq->ioprio = IOPRIO_NORM; 3356 } else { 3357 /* 3358 * unboost the queue (if needed) 3359 */ 3360 cfqq->ioprio_class = cfqq->org_ioprio_class; 3361 cfqq->ioprio = cfqq->org_ioprio; 3362 } 3363} 3364 3365static inline int __cfq_may_queue(struct cfq_queue *cfqq) 3366{ 3367 if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) { 3368 cfq_mark_cfqq_must_alloc_slice(cfqq); 3369 return ELV_MQUEUE_MUST; 3370 } 3371 3372 return ELV_MQUEUE_MAY; 3373} 3374 3375static int cfq_may_queue(struct request_queue *q, int rw) 3376{ 3377 struct cfq_data *cfqd = q->elevator->elevator_data; 3378 struct task_struct *tsk = current; 3379 struct cfq_io_context *cic; 3380 struct cfq_queue *cfqq; 3381 3382 /* 3383 * don't force setup of a queue from here, as a call to may_queue 3384 * does not necessarily imply that a request actually will be queued. 3385 * so just lookup a possibly existing queue, or return 'may queue' 3386 * if that fails 3387 */ 3388 cic = cfq_cic_lookup(cfqd, tsk->io_context); 3389 if (!cic) 3390 return ELV_MQUEUE_MAY; 3391 3392 cfqq = cic_to_cfqq(cic, rw_is_sync(rw)); 3393 if (cfqq) { 3394 cfq_init_prio_data(cfqq, cic->ioc); 3395 cfq_prio_boost(cfqq); 3396 3397 return __cfq_may_queue(cfqq); 3398 } 3399 3400 return ELV_MQUEUE_MAY; 3401} 3402 3403/* 3404 * queue lock held here 3405 */ 3406static void cfq_put_request(struct request *rq) 3407{ 3408 struct cfq_queue *cfqq = RQ_CFQQ(rq); 3409 3410 if (cfqq) { 3411 const int rw = rq_data_dir(rq); 3412 3413 BUG_ON(!cfqq->allocated[rw]); 3414 cfqq->allocated[rw]--; 3415 3416 put_io_context(RQ_CIC(rq)->ioc); 3417 3418 rq->elevator_private = NULL; 3419 rq->elevator_private2 = NULL; 3420 3421 cfq_put_queue(cfqq); 3422 } 3423} 3424 3425static struct cfq_queue * 3426cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic, 3427 struct cfq_queue *cfqq) 3428{ 3429 cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq); 3430 cic_set_cfqq(cic, cfqq->new_cfqq, 1); 3431 cfq_mark_cfqq_coop(cfqq->new_cfqq); 3432 cfq_put_queue(cfqq); 3433 return cic_to_cfqq(cic, 1); 3434} 3435 3436/* 3437 * Returns NULL if a new cfqq should be allocated, or the old cfqq if this 3438 * was the last process referring to said cfqq. 3439 */ 3440static struct cfq_queue * 3441split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq) 3442{ 3443 if (cfqq_process_refs(cfqq) == 1) { 3444 cfqq->pid = current->pid; 3445 cfq_clear_cfqq_coop(cfqq); 3446 cfq_clear_cfqq_split_coop(cfqq); 3447 return cfqq; 3448 } 3449 3450 cic_set_cfqq(cic, NULL, 1); 3451 cfq_put_queue(cfqq); 3452 return NULL; 3453} 3454/* 3455 * Allocate cfq data structures associated with this request. 3456 */ 3457static int 3458cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask) 3459{ 3460 struct cfq_data *cfqd = q->elevator->elevator_data; 3461 struct cfq_io_context *cic; 3462 const int rw = rq_data_dir(rq); 3463 const bool is_sync = rq_is_sync(rq); 3464 struct cfq_queue *cfqq; 3465 unsigned long flags; 3466 3467 might_sleep_if(gfp_mask & __GFP_WAIT); 3468 3469 cic = cfq_get_io_context(cfqd, gfp_mask); 3470 3471 spin_lock_irqsave(q->queue_lock, flags); 3472 3473 if (!cic) 3474 goto queue_fail; 3475 3476new_queue: 3477 cfqq = cic_to_cfqq(cic, is_sync); 3478 if (!cfqq || cfqq == &cfqd->oom_cfqq) { 3479 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask); 3480 cic_set_cfqq(cic, cfqq, is_sync); 3481 } else { 3482 /* 3483 * If the queue was seeky for too long, break it apart. 3484 */ 3485 if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) { 3486 cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq"); 3487 cfqq = split_cfqq(cic, cfqq); 3488 if (!cfqq) 3489 goto new_queue; 3490 } 3491 3492 /* 3493 * Check to see if this queue is scheduled to merge with 3494 * another, closely cooperating queue. The merging of 3495 * queues happens here as it must be done in process context. 3496 * The reference on new_cfqq was taken in merge_cfqqs. 3497 */ 3498 if (cfqq->new_cfqq) 3499 cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq); 3500 } 3501 3502 cfqq->allocated[rw]++; 3503 atomic_inc(&cfqq->ref); 3504 3505 spin_unlock_irqrestore(q->queue_lock, flags); 3506 3507 rq->elevator_private = cic; 3508 rq->elevator_private2 = cfqq; 3509 return 0; 3510 3511queue_fail: 3512 if (cic) 3513 put_io_context(cic->ioc); 3514 3515 cfq_schedule_dispatch(cfqd); 3516 spin_unlock_irqrestore(q->queue_lock, flags); 3517 cfq_log(cfqd, "set_request fail"); 3518 return 1; 3519} 3520 3521static void cfq_kick_queue(struct work_struct *work) 3522{ 3523 struct cfq_data *cfqd = 3524 container_of(work, struct cfq_data, unplug_work); 3525 struct request_queue *q = cfqd->queue; 3526 3527 spin_lock_irq(q->queue_lock); 3528 __blk_run_queue(cfqd->queue); 3529 spin_unlock_irq(q->queue_lock); 3530} 3531 3532/* 3533 * Timer running if the active_queue is currently idling inside its time slice 3534 */ 3535static void cfq_idle_slice_timer(unsigned long data) 3536{ 3537 struct cfq_data *cfqd = (struct cfq_data *) data; 3538 struct cfq_queue *cfqq; 3539 unsigned long flags; 3540 int timed_out = 1; 3541 3542 cfq_log(cfqd, "idle timer fired"); 3543 3544 spin_lock_irqsave(cfqd->queue->queue_lock, flags); 3545 3546 cfqq = cfqd->active_queue; 3547 if (cfqq) { 3548 timed_out = 0; 3549 3550 /* 3551 * We saw a request before the queue expired, let it through 3552 */ 3553 if (cfq_cfqq_must_dispatch(cfqq)) 3554 goto out_kick; 3555 3556 /* 3557 * expired 3558 */ 3559 if (cfq_slice_used(cfqq)) 3560 goto expire; 3561 3562 /* 3563 * only expire and reinvoke request handler, if there are 3564 * other queues with pending requests 3565 */ 3566 if (!cfqd->busy_queues) 3567 goto out_cont; 3568 3569 /* 3570 * not expired and it has a request pending, let it dispatch 3571 */ 3572 if (!RB_EMPTY_ROOT(&cfqq->sort_list)) 3573 goto out_kick; 3574 3575 /* 3576 * Queue depth flag is reset only when the idle didn't succeed 3577 */ 3578 cfq_clear_cfqq_deep(cfqq); 3579 } 3580expire: 3581 cfq_slice_expired(cfqd, timed_out); 3582out_kick: 3583 cfq_schedule_dispatch(cfqd); 3584out_cont: 3585 spin_unlock_irqrestore(cfqd->queue->queue_lock, flags); 3586} 3587 3588static void cfq_shutdown_timer_wq(struct cfq_data *cfqd) 3589{ 3590 del_timer_sync(&cfqd->idle_slice_timer); 3591 cancel_work_sync(&cfqd->unplug_work); 3592} 3593 3594static void cfq_put_async_queues(struct cfq_data *cfqd) 3595{ 3596 int i; 3597 3598 for (i = 0; i < IOPRIO_BE_NR; i++) { 3599 if (cfqd->async_cfqq[0][i]) 3600 cfq_put_queue(cfqd->async_cfqq[0][i]); 3601 if (cfqd->async_cfqq[1][i]) 3602 cfq_put_queue(cfqd->async_cfqq[1][i]); 3603 } 3604 3605 if (cfqd->async_idle_cfqq) 3606 cfq_put_queue(cfqd->async_idle_cfqq); 3607} 3608 3609static void cfq_cfqd_free(struct rcu_head *head) 3610{ 3611 kfree(container_of(head, struct cfq_data, rcu)); 3612} 3613 3614static void cfq_exit_queue(struct elevator_queue *e) 3615{ 3616 struct cfq_data *cfqd = e->elevator_data; 3617 struct request_queue *q = cfqd->queue; 3618 3619 cfq_shutdown_timer_wq(cfqd); 3620 3621 spin_lock_irq(q->queue_lock); 3622 3623 if (cfqd->active_queue) 3624 __cfq_slice_expired(cfqd, cfqd->active_queue, 0); 3625 3626 while (!list_empty(&cfqd->cic_list)) { 3627 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next, 3628 struct cfq_io_context, 3629 queue_list); 3630 3631 __cfq_exit_single_io_context(cfqd, cic); 3632 } 3633 3634 cfq_put_async_queues(cfqd); 3635 cfq_release_cfq_groups(cfqd); 3636 blkiocg_del_blkio_group(&cfqd->root_group.blkg); 3637 3638 spin_unlock_irq(q->queue_lock); 3639 3640 cfq_shutdown_timer_wq(cfqd); 3641 3642 /* Wait for cfqg->blkg->key accessors to exit their grace periods. */ 3643 call_rcu(&cfqd->rcu, cfq_cfqd_free); 3644} 3645 3646static void *cfq_init_queue(struct request_queue *q) 3647{ 3648 struct cfq_data *cfqd; 3649 int i, j; 3650 struct cfq_group *cfqg; 3651 struct cfq_rb_root *st; 3652 3653 cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node); 3654 if (!cfqd) 3655 return NULL; 3656 3657 /* Init root service tree */ 3658 cfqd->grp_service_tree = CFQ_RB_ROOT; 3659 3660 /* Init root group */ 3661 cfqg = &cfqd->root_group; 3662 for_each_cfqg_st(cfqg, i, j, st) 3663 *st = CFQ_RB_ROOT; 3664 RB_CLEAR_NODE(&cfqg->rb_node); 3665 3666 /* Give preference to root group over other groups */ 3667 cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT; 3668 3669#ifdef CONFIG_CFQ_GROUP_IOSCHED 3670 /* 3671 * Take a reference to root group which we never drop. This is just 3672 * to make sure that cfq_put_cfqg() does not try to kfree root group 3673 */ 3674 atomic_set(&cfqg->ref, 1); 3675 blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd, 3676 0); 3677#endif 3678 /* 3679 * Not strictly needed (since RB_ROOT just clears the node and we 3680 * zeroed cfqd on alloc), but better be safe in case someone decides 3681 * to add magic to the rb code 3682 */ 3683 for (i = 0; i < CFQ_PRIO_LISTS; i++) 3684 cfqd->prio_trees[i] = RB_ROOT; 3685 3686 /* 3687 * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues. 3688 * Grab a permanent reference to it, so that the normal code flow 3689 * will not attempt to free it. 3690 */ 3691 cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0); 3692 atomic_inc(&cfqd->oom_cfqq.ref); 3693 cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group); 3694 3695 INIT_LIST_HEAD(&cfqd->cic_list); 3696 3697 cfqd->queue = q; 3698 3699 init_timer(&cfqd->idle_slice_timer); 3700 cfqd->idle_slice_timer.function = cfq_idle_slice_timer; 3701 cfqd->idle_slice_timer.data = (unsigned long) cfqd; 3702 3703 INIT_WORK(&cfqd->unplug_work, cfq_kick_queue); 3704 3705 cfqd->cfq_quantum = cfq_quantum; 3706 cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0]; 3707 cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1]; 3708 cfqd->cfq_back_max = cfq_back_max; 3709 cfqd->cfq_back_penalty = cfq_back_penalty; 3710 cfqd->cfq_slice[0] = cfq_slice_async; 3711 cfqd->cfq_slice[1] = cfq_slice_sync; 3712 cfqd->cfq_slice_async_rq = cfq_slice_async_rq; 3713 cfqd->cfq_slice_idle = cfq_slice_idle; 3714 cfqd->cfq_latency = 1; 3715 cfqd->cfq_group_isolation = 0; 3716 cfqd->hw_tag = -1; 3717 /* 3718 * we optimistically start assuming sync ops weren't delayed in last 3719 * second, in order to have larger depth for async operations. 3720 */ 3721 cfqd->last_delayed_sync = jiffies - HZ; 3722 INIT_RCU_HEAD(&cfqd->rcu); 3723 return cfqd; 3724} 3725 3726static void cfq_slab_kill(void) 3727{ 3728 /* 3729 * Caller already ensured that pending RCU callbacks are completed, 3730 * so we should have no busy allocations at this point. 3731 */ 3732 if (cfq_pool) 3733 kmem_cache_destroy(cfq_pool); 3734 if (cfq_ioc_pool) 3735 kmem_cache_destroy(cfq_ioc_pool); 3736} 3737 3738static int __init cfq_slab_setup(void) 3739{ 3740 cfq_pool = KMEM_CACHE(cfq_queue, 0); 3741 if (!cfq_pool) 3742 goto fail; 3743 3744 cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0); 3745 if (!cfq_ioc_pool) 3746 goto fail; 3747 3748 return 0; 3749fail: 3750 cfq_slab_kill(); 3751 return -ENOMEM; 3752} 3753 3754/* 3755 * sysfs parts below --> 3756 */ 3757static ssize_t 3758cfq_var_show(unsigned int var, char *page) 3759{ 3760 return sprintf(page, "%d\n", var); 3761} 3762 3763static ssize_t 3764cfq_var_store(unsigned int *var, const char *page, size_t count) 3765{ 3766 char *p = (char *) page; 3767 3768 *var = simple_strtoul(p, &p, 10); 3769 return count; 3770} 3771 3772#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ 3773static ssize_t __FUNC(struct elevator_queue *e, char *page) \ 3774{ \ 3775 struct cfq_data *cfqd = e->elevator_data; \ 3776 unsigned int __data = __VAR; \ 3777 if (__CONV) \ 3778 __data = jiffies_to_msecs(__data); \ 3779 return cfq_var_show(__data, (page)); \ 3780} 3781SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0); 3782SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1); 3783SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1); 3784SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0); 3785SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0); 3786SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1); 3787SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1); 3788SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1); 3789SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0); 3790SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0); 3791SHOW_FUNCTION(cfq_group_isolation_show, cfqd->cfq_group_isolation, 0); 3792#undef SHOW_FUNCTION 3793 3794#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ 3795static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \ 3796{ \ 3797 struct cfq_data *cfqd = e->elevator_data; \ 3798 unsigned int __data; \ 3799 int ret = cfq_var_store(&__data, (page), count); \ 3800 if (__data < (MIN)) \ 3801 __data = (MIN); \ 3802 else if (__data > (MAX)) \ 3803 __data = (MAX); \ 3804 if (__CONV) \ 3805 *(__PTR) = msecs_to_jiffies(__data); \ 3806 else \ 3807 *(__PTR) = __data; \ 3808 return ret; \ 3809} 3810STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0); 3811STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, 3812 UINT_MAX, 1); 3813STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1, 3814 UINT_MAX, 1); 3815STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0); 3816STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1, 3817 UINT_MAX, 0); 3818STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1); 3819STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1); 3820STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1); 3821STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1, 3822 UINT_MAX, 0); 3823STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0); 3824STORE_FUNCTION(cfq_group_isolation_store, &cfqd->cfq_group_isolation, 0, 1, 0); 3825#undef STORE_FUNCTION 3826 3827#define CFQ_ATTR(name) \ 3828 __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store) 3829 3830static struct elv_fs_entry cfq_attrs[] = { 3831 CFQ_ATTR(quantum), 3832 CFQ_ATTR(fifo_expire_sync), 3833 CFQ_ATTR(fifo_expire_async), 3834 CFQ_ATTR(back_seek_max), 3835 CFQ_ATTR(back_seek_penalty), 3836 CFQ_ATTR(slice_sync), 3837 CFQ_ATTR(slice_async), 3838 CFQ_ATTR(slice_async_rq), 3839 CFQ_ATTR(slice_idle), 3840 CFQ_ATTR(low_latency), 3841 CFQ_ATTR(group_isolation), 3842 __ATTR_NULL 3843}; 3844 3845static struct elevator_type iosched_cfq = { 3846 .ops = { 3847 .elevator_merge_fn = cfq_merge, 3848 .elevator_merged_fn = cfq_merged_request, 3849 .elevator_merge_req_fn = cfq_merged_requests, 3850 .elevator_allow_merge_fn = cfq_allow_merge, 3851 .elevator_dispatch_fn = cfq_dispatch_requests, 3852 .elevator_add_req_fn = cfq_insert_request, 3853 .elevator_activate_req_fn = cfq_activate_request, 3854 .elevator_deactivate_req_fn = cfq_deactivate_request, 3855 .elevator_queue_empty_fn = cfq_queue_empty, 3856 .elevator_completed_req_fn = cfq_completed_request, 3857 .elevator_former_req_fn = elv_rb_former_request, 3858 .elevator_latter_req_fn = elv_rb_latter_request, 3859 .elevator_set_req_fn = cfq_set_request, 3860 .elevator_put_req_fn = cfq_put_request, 3861 .elevator_may_queue_fn = cfq_may_queue, 3862 .elevator_init_fn = cfq_init_queue, 3863 .elevator_exit_fn = cfq_exit_queue, 3864 .trim = cfq_free_io_context, 3865 }, 3866 .elevator_attrs = cfq_attrs, 3867 .elevator_name = "cfq", 3868 .elevator_owner = THIS_MODULE, 3869}; 3870 3871#ifdef CONFIG_CFQ_GROUP_IOSCHED 3872static struct blkio_policy_type blkio_policy_cfq = { 3873 .ops = { 3874 .blkio_unlink_group_fn = cfq_unlink_blkio_group, 3875 .blkio_update_group_weight_fn = cfq_update_blkio_group_weight, 3876 }, 3877}; 3878#else 3879static struct blkio_policy_type blkio_policy_cfq; 3880#endif 3881 3882static int __init cfq_init(void) 3883{ 3884 /* 3885 * could be 0 on HZ < 1000 setups 3886 */ 3887 if (!cfq_slice_async) 3888 cfq_slice_async = 1; 3889 if (!cfq_slice_idle) 3890 cfq_slice_idle = 1; 3891 3892 if (cfq_slab_setup()) 3893 return -ENOMEM; 3894 3895 elv_register(&iosched_cfq); 3896 blkio_policy_register(&blkio_policy_cfq); 3897 3898 return 0; 3899} 3900 3901static void __exit cfq_exit(void) 3902{ 3903 DECLARE_COMPLETION_ONSTACK(all_gone); 3904 blkio_policy_unregister(&blkio_policy_cfq); 3905 elv_unregister(&iosched_cfq); 3906 ioc_gone = &all_gone; 3907 /* ioc_gone's update must be visible before reading ioc_count */ 3908 smp_wmb(); 3909 3910 /* 3911 * this also protects us from entering cfq_slab_kill() with 3912 * pending RCU callbacks 3913 */ 3914 if (elv_ioc_count_read(cfq_ioc_count)) 3915 wait_for_completion(&all_gone); 3916 cfq_slab_kill(); 3917} 3918 3919module_init(cfq_init); 3920module_exit(cfq_exit); 3921 3922MODULE_AUTHOR("Jens Axboe"); 3923MODULE_LICENSE("GPL"); 3924MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler"); 3925