block/cfq-iosched.c

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