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