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