drivers/block/cfq-iosched.c

   1 /*
   2  *  linux/drivers/block/cfq-iosched.c
   3  *
   4  *  CFQ, or complete fairness queueing, disk scheduler.
   5  *
   6  *  Based on ideas from a previously unfinished io
   7  *  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
   8  *
   9  *  Copyright (C) 2003 Jens Axboe <axboe@suse.de>
  10  */
  11 #include <linux/kernel.h>
  12 #include <linux/fs.h>
  13 #include <linux/blkdev.h>
  14 #include <linux/elevator.h>
  15 #include <linux/bio.h>
  16 #include <linux/config.h>
  17 #include <linux/module.h>
  18 #include <linux/slab.h>
  19 #include <linux/init.h>
  20 #include <linux/compiler.h>
  21 #include <linux/hash.h>
  22 #include <linux/rbtree.h>
  23 #include <linux/mempool.h>
  24
  25 static unsigned long max_elapsed_crq;
  26 static unsigned long max_elapsed_dispatch;
  27
  28 /*
  29  * tunables
  30  */
  31 static int cfq_quantum = 4;             /* max queue in one round of service */
  32 static int cfq_queued = 8;              /* minimum rq allocate limit per-queue*/
  33 static int cfq_service = HZ;            /* period over which service is avg */
  34 static int cfq_fifo_expire_r = HZ / 2;  /* fifo timeout for sync requests */
  35 static int cfq_fifo_expire_w = 5 * HZ;  /* fifo timeout for async requests */
  36 static int cfq_fifo_rate = HZ / 8;      /* fifo expiry rate */
  37 static int cfq_back_max = 16 * 1024;    /* maximum backwards seek, in KiB */
  38 static int cfq_back_penalty = 2;        /* penalty of a backwards seek */
  39
  40 /*
  41  * for the hash of cfqq inside the cfqd
  42  */
  43 #define CFQ_QHASH_SHIFT         6
  44 #define CFQ_QHASH_ENTRIES       (1 << CFQ_QHASH_SHIFT)
  45 #define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash)
  46
  47 /*
  48  * for the hash of crq inside the cfqq
  49  */
  50 #define CFQ_MHASH_SHIFT         6
  51 #define CFQ_MHASH_BLOCK(sec)    ((sec) >> 3)
  52 #define CFQ_MHASH_ENTRIES       (1 << CFQ_MHASH_SHIFT)
  53 #define CFQ_MHASH_FN(sec)       hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT)
  54 #define rq_hash_key(rq)         ((rq)->sector + (rq)->nr_sectors)
  55 #define list_entry_hash(ptr)    hlist_entry((ptr), struct cfq_rq, hash)
  56
  57 #define list_entry_cfqq(ptr)    list_entry((ptr), struct cfq_queue, cfq_list)
  58
  59 #define RQ_DATA(rq)             (rq)->elevator_private
  60
  61 /*
  62  * rb-tree defines
  63  */
  64 #define RB_NONE                 (2)
  65 #define RB_EMPTY(node)          ((node)->rb_node == NULL)
  66 #define RB_CLEAR_COLOR(node)    (node)->rb_color = RB_NONE
  67 #define RB_CLEAR(node)          do {    \
  68         (node)->rb_parent = NULL;       \
  69         RB_CLEAR_COLOR((node));         \
  70         (node)->rb_right = NULL;        \
  71         (node)->rb_left = NULL;         \
  72 } while (0)
  73 #define RB_CLEAR_ROOT(root)     ((root)->rb_node = NULL)
  74 #define ON_RB(node)             ((node)->rb_color != RB_NONE)
  75 #define rb_entry_crq(node)      rb_entry((node), struct cfq_rq, rb_node)
  76 #define rq_rb_key(rq)           (rq)->sector
  77
  78 /*
  79  * threshold for switching off non-tag accounting
  80  */
  81 #define CFQ_MAX_TAG             (4)
  82
  83 /*
  84  * sort key types and names
  85  */
  86 enum {
  87         CFQ_KEY_PGID,
  88         CFQ_KEY_TGID,
  89         CFQ_KEY_UID,
  90         CFQ_KEY_GID,
  91         CFQ_KEY_LAST,
  92 };
  93
  94 static char *cfq_key_types[] = { "pgid", "tgid", "uid", "gid", NULL };
  95
  96 static kmem_cache_t *crq_pool;
  97 static kmem_cache_t *cfq_pool;
  98 static kmem_cache_t *cfq_ioc_pool;
  99
 100 struct cfq_data {
 101         struct list_head rr_list;
 102         struct list_head empty_list;
 103
 104         struct hlist_head *cfq_hash;
 105         struct hlist_head *crq_hash;
 106
 107         /* queues on rr_list (ie they have pending requests */
 108         unsigned int busy_queues;
 109
 110         unsigned int max_queued;
 111
 112         atomic_t ref;
 113
 114         int key_type;
 115
 116         mempool_t *crq_pool;
 117
 118         request_queue_t *queue;
 119
 120         sector_t last_sector;
 121
 122         int rq_in_driver;
 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_r;
 130         unsigned int cfq_fifo_expire_w;
 131         unsigned int cfq_fifo_batch_expire;
 132         unsigned int cfq_back_penalty;
 133         unsigned int cfq_back_max;
 134         unsigned int find_best_crq;
 135
 136         unsigned int cfq_tagged;
 137 };
 138
 139 struct cfq_queue {
 140         /* reference count */
 141         atomic_t ref;
 142         /* parent cfq_data */
 143         struct cfq_data *cfqd;
 144         /* hash of mergeable requests */
 145         struct hlist_node cfq_hash;
 146         /* hash key */
 147         unsigned long key;
 148         /* whether queue is on rr (or empty) list */
 149         int on_rr;
 150         /* on either rr or empty list of cfqd */
 151         struct list_head cfq_list;
 152         /* sorted list of pending requests */
 153         struct rb_root sort_list;
 154         /* if fifo isn't expired, next request to serve */
 155         struct cfq_rq *next_crq;
 156         /* requests queued in sort_list */
 157         int queued[2];
 158         /* currently allocated requests */
 159         int allocated[2];
 160         /* fifo list of requests in sort_list */
 161         struct list_head fifo[2];
 162         /* last time fifo expired */
 163         unsigned long last_fifo_expire;
 164
 165         int key_type;
 166
 167         unsigned long service_start;
 168         unsigned long service_used;
 169
 170         unsigned int max_rate;
 171
 172         /* number of requests that have been handed to the driver */
 173         int in_flight;
 174         /* number of currently allocated requests */
 175         int alloc_limit[2];
 176 };
 177
 178 struct cfq_rq {
 179         struct rb_node rb_node;
 180         sector_t rb_key;
 181         struct request *request;
 182         struct hlist_node hash;
 183
 184         struct cfq_queue *cfq_queue;
 185         struct cfq_io_context *io_context;
 186
 187         unsigned long service_start;
 188         unsigned long queue_start;
 189
 190         unsigned int in_flight : 1;
 191         unsigned int accounted : 1;
 192         unsigned int is_sync   : 1;
 193         unsigned int is_write  : 1;
 194 };
 195
 196 static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned long);
 197 static void cfq_dispatch_sort(request_queue_t *, struct cfq_rq *);
 198 static void cfq_update_next_crq(struct cfq_rq *);
 199 static void cfq_put_cfqd(struct cfq_data *cfqd);
 200
 201 /*
 202  * what the fairness is based on (ie how processes are grouped and
 203  * differentiated)
 204  */
 205 static inline unsigned long
 206 cfq_hash_key(struct cfq_data *cfqd, struct task_struct *tsk)
 207 {
 208         /*
 209          * optimize this so that ->key_type is the offset into the struct
 210          */
 211         switch (cfqd->key_type) {
 212                 case CFQ_KEY_PGID:
 213                         return process_group(tsk);
 214                 default:
 215                 case CFQ_KEY_TGID:
 216                         return tsk->tgid;
 217                 case CFQ_KEY_UID:
 218                         return tsk->uid;
 219                 case CFQ_KEY_GID:
 220                         return tsk->gid;
 221         }
 222 }
 223
 224 /*
 225  * lots of deadline iosched dupes, can be abstracted later...
 226  */
 227 static inline void cfq_del_crq_hash(struct cfq_rq *crq)
 228 {
 229         hlist_del_init(&crq->hash);
 230 }
 231
 232 static void cfq_remove_merge_hints(request_queue_t *q, struct cfq_rq *crq)
 233 {
 234         cfq_del_crq_hash(crq);
 235
 236         if (q->last_merge == crq->request)
 237                 q->last_merge = NULL;
 238
 239         cfq_update_next_crq(crq);
 240 }
 241
 242 static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
 243 {
 244         const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));
 245
 246         BUG_ON(!hlist_unhashed(&crq->hash));
 247
 248         hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
 249 }
 250
 251 static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
 252 {
 253         struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
 254         struct hlist_node *entry, *next;
 255
 256         hlist_for_each_safe(entry, next, hash_list) {
 257                 struct cfq_rq *crq = list_entry_hash(entry);
 258                 struct request *__rq = crq->request;
 259
 260                 BUG_ON(hlist_unhashed(&crq->hash));
 261
 262                 if (!rq_mergeable(__rq)) {
 263                         cfq_del_crq_hash(crq);
 264                         continue;
 265                 }
 266
 267                 if (rq_hash_key(__rq) == offset)
 268                         return __rq;
 269         }
 270
 271         return NULL;
 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 are 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         int r1_wrap = 0, r2_wrap = 0;   /* requests are behind the disk head */
 284         unsigned long back_max;
 285
 286         if (crq1 == NULL || crq1 == crq2)
 287                 return crq2;
 288         if (crq2 == NULL)
 289                 return crq1;
 290
 291         s1 = crq1->request->sector;
 292         s2 = crq2->request->sector;
 293
 294         last = cfqd->last_sector;
 295
 296 #if 0
 297         if (!list_empty(&cfqd->queue->queue_head)) {
 298                 struct list_head *entry = &cfqd->queue->queue_head;
 299                 unsigned long distance = ~0UL;
 300                 struct request *rq;
 301
 302                 while ((entry = entry->prev) != &cfqd->queue->queue_head) {
 303                         rq = list_entry_rq(entry);
 304
 305                         if (blk_barrier_rq(rq))
 306                                 break;
 307
 308                         if (distance < abs(s1 - rq->sector + rq->nr_sectors)) {
 309                                 distance = abs(s1 - rq->sector +rq->nr_sectors);
 310                                 last = rq->sector + rq->nr_sectors;
 311                         }
 312                         if (distance < abs(s2 - rq->sector + rq->nr_sectors)) {
 313                                 distance = abs(s2 - rq->sector +rq->nr_sectors);
 314                                 last = rq->sector + rq->nr_sectors;
 315                         }
 316                 }
 317         }
 318 #endif
 319
 320         /*
 321          * by definition, 1KiB is 2 sectors
 322          */
 323         back_max = cfqd->cfq_back_max * 2;
 324
 325         /*
 326          * Strict one way elevator _except_ in the case where we allow
 327          * short backward seeks which are biased as twice the cost of a
 328          * similar forward seek.
 329          */
 330         if (s1 >= last)
 331                 d1 = s1 - last;
 332         else if (s1 + back_max >= last)
 333                 d1 = (last - s1) * cfqd->cfq_back_penalty;
 334         else
 335                 r1_wrap = 1;
 336
 337         if (s2 >= last)
 338                 d2 = s2 - last;
 339         else if (s2 + back_max >= last)
 340                 d2 = (last - s2) * cfqd->cfq_back_penalty;
 341         else
 342                 r2_wrap = 1;
 343
 344         /* Found required data */
 345         if (!r1_wrap && r2_wrap)
 346                 return crq1;
 347         else if (!r2_wrap && r1_wrap)
 348                 return crq2;
 349         else if (r1_wrap && r2_wrap) {
 350                 /* both behind the head */
 351                 if (s1 <= s2)
 352                         return crq1;
 353                 else
 354                         return crq2;
 355         }
 356
 357         /* Both requests in front of the head */
 358         if (d1 < d2)
 359                 return crq1;
 360         else if (d2 < d1)
 361                 return crq2;
 362         else {
 363                 if (s1 >= s2)
 364                         return crq1;
 365                 else
 366                         return crq2;
 367         }
 368 }
 369
 370 /*
 371  * would be nice to take fifo expire time into account as well
 372  */
 373 static struct cfq_rq *
 374 cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 375                   struct cfq_rq *last)
 376 {
 377         struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
 378         struct rb_node *rbnext, *rbprev;
 379
 380         if (!ON_RB(&last->rb_node))
 381                 return NULL;
 382
 383         if ((rbnext = rb_next(&last->rb_node)) == NULL)
 384                 rbnext = rb_first(&cfqq->sort_list);
 385
 386         rbprev = rb_prev(&last->rb_node);
 387
 388         if (rbprev)
 389                 crq_prev = rb_entry_crq(rbprev);
 390         if (rbnext)
 391                 crq_next = rb_entry_crq(rbnext);
 392
 393         return cfq_choose_req(cfqd, crq_next, crq_prev);
 394 }
 395
 396 static void cfq_update_next_crq(struct cfq_rq *crq)
 397 {
 398         struct cfq_queue *cfqq = crq->cfq_queue;
 399
 400         if (cfqq->next_crq == crq)
 401                 cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
 402 }
 403
 404 static int cfq_check_sort_rr_list(struct cfq_queue *cfqq)
 405 {
 406         struct list_head *head = &cfqq->cfqd->rr_list;
 407         struct list_head *next, *prev;
 408
 409         /*
 410          * list might still be ordered
 411          */
 412         next = cfqq->cfq_list.next;
 413         if (next != head) {
 414                 struct cfq_queue *cnext = list_entry_cfqq(next);
 415
 416                 if (cfqq->service_used > cnext->service_used)
 417                         return 1;
 418         }
 419
 420         prev = cfqq->cfq_list.prev;
 421         if (prev != head) {
 422                 struct cfq_queue *cprev = list_entry_cfqq(prev);
 423
 424                 if (cfqq->service_used < cprev->service_used)
 425                         return 1;
 426         }
 427
 428         return 0;
 429 }
 430
 431 static void cfq_sort_rr_list(struct cfq_queue *cfqq, int new_queue)
 432 {
 433         struct list_head *entry = &cfqq->cfqd->rr_list;
 434
 435         if (!cfqq->on_rr)
 436                 return;
 437         if (!new_queue && !cfq_check_sort_rr_list(cfqq))
 438                 return;
 439
 440         list_del(&cfqq->cfq_list);
 441
 442         /*
 443          * sort by our mean service_used, sub-sort by in-flight requests
 444          */
 445         while ((entry = entry->prev) != &cfqq->cfqd->rr_list) {
 446                 struct cfq_queue *__cfqq = list_entry_cfqq(entry);
 447
 448                 if (cfqq->service_used > __cfqq->service_used)
 449                         break;
 450                 else if (cfqq->service_used == __cfqq->service_used) {
 451                         struct list_head *prv;
 452
 453                         while ((prv = entry->prev) != &cfqq->cfqd->rr_list) {
 454                                 __cfqq = list_entry_cfqq(prv);
 455
 456                                 WARN_ON(__cfqq->service_used > cfqq->service_used);
 457                                 if (cfqq->service_used != __cfqq->service_used)
 458                                         break;
 459                                 if (cfqq->in_flight > __cfqq->in_flight)
 460                                         break;
 461
 462                                 entry = prv;
 463                         }
 464                 }
 465         }
 466
 467         list_add(&cfqq->cfq_list, entry);
 468 }
 469
 470 /*
 471  * add to busy list of queues for service, trying to be fair in ordering
 472  * the pending list according to requests serviced
 473  */
 474 static inline void
 475 cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 476 {
 477         /*
 478          * it's currently on the empty list
 479          */
 480         cfqq->on_rr = 1;
 481         cfqd->busy_queues++;
 482
 483         if (time_after(jiffies, cfqq->service_start + cfq_service))
 484                 cfqq->service_used >>= 3;
 485
 486         cfq_sort_rr_list(cfqq, 1);
 487 }
 488
 489 static inline void
 490 cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 491 {
 492         list_move(&cfqq->cfq_list, &cfqd->empty_list);
 493         cfqq->on_rr = 0;
 494
 495         BUG_ON(!cfqd->busy_queues);
 496         cfqd->busy_queues--;
 497 }
 498
 499 /*
 500  * rb tree support functions
 501  */
 502 static inline void cfq_del_crq_rb(struct cfq_rq *crq)
 503 {
 504         struct cfq_queue *cfqq = crq->cfq_queue;
 505
 506         if (ON_RB(&crq->rb_node)) {
 507                 struct cfq_data *cfqd = cfqq->cfqd;
 508
 509                 BUG_ON(!cfqq->queued[crq->is_sync]);
 510
 511                 cfq_update_next_crq(crq);
 512
 513                 cfqq->queued[crq->is_sync]--;
 514                 rb_erase(&crq->rb_node, &cfqq->sort_list);
 515                 RB_CLEAR_COLOR(&crq->rb_node);
 516
 517                 if (RB_EMPTY(&cfqq->sort_list) && cfqq->on_rr)
 518                         cfq_del_cfqq_rr(cfqd, cfqq);
 519         }
 520 }
 521
 522 static struct cfq_rq *
 523 __cfq_add_crq_rb(struct cfq_rq *crq)
 524 {
 525         struct rb_node **p = &crq->cfq_queue->sort_list.rb_node;
 526         struct rb_node *parent = NULL;
 527         struct cfq_rq *__crq;
 528
 529         while (*p) {
 530                 parent = *p;
 531                 __crq = rb_entry_crq(parent);
 532
 533                 if (crq->rb_key < __crq->rb_key)
 534                         p = &(*p)->rb_left;
 535                 else if (crq->rb_key > __crq->rb_key)
 536                         p = &(*p)->rb_right;
 537                 else
 538                         return __crq;
 539         }
 540
 541         rb_link_node(&crq->rb_node, parent, p);
 542         return NULL;
 543 }
 544
 545 static void cfq_add_crq_rb(struct cfq_rq *crq)
 546 {
 547         struct cfq_queue *cfqq = crq->cfq_queue;
 548         struct cfq_data *cfqd = cfqq->cfqd;
 549         struct request *rq = crq->request;
 550         struct cfq_rq *__alias;
 551
 552         crq->rb_key = rq_rb_key(rq);
 553         cfqq->queued[crq->is_sync]++;
 554
 555         /*
 556          * looks a little odd, but the first insert might return an alias.
 557          * if that happens, put the alias on the dispatch list
 558          */
 559         while ((__alias = __cfq_add_crq_rb(crq)) != NULL)
 560                 cfq_dispatch_sort(cfqd->queue, __alias);
 561
 562         rb_insert_color(&crq->rb_node, &cfqq->sort_list);
 563
 564         if (!cfqq->on_rr)
 565                 cfq_add_cfqq_rr(cfqd, cfqq);
 566
 567         /*
 568          * check if this request is a better next-serve candidate
 569          */
 570         cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
 571 }
 572
 573 static inline void
 574 cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
 575 {
 576         if (ON_RB(&crq->rb_node)) {
 577                 rb_erase(&crq->rb_node, &cfqq->sort_list);
 578                 cfqq->queued[crq->is_sync]--;
 579         }
 580
 581         cfq_add_crq_rb(crq);
 582 }
 583
 584 static struct request *
 585 cfq_find_rq_rb(struct cfq_data *cfqd, sector_t sector)
 586 {
 587         const unsigned long key = cfq_hash_key(cfqd, current);
 588         struct cfq_queue *cfqq = cfq_find_cfq_hash(cfqd, key);
 589         struct rb_node *n;
 590
 591         if (!cfqq)
 592                 goto out;
 593
 594         n = cfqq->sort_list.rb_node;
 595         while (n) {
 596                 struct cfq_rq *crq = rb_entry_crq(n);
 597
 598                 if (sector < crq->rb_key)
 599                         n = n->rb_left;
 600                 else if (sector > crq->rb_key)
 601                         n = n->rb_right;
 602                 else
 603                         return crq->request;
 604         }
 605
 606 out:
 607         return NULL;
 608 }
 609
 610 static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
 611 {
 612         struct cfq_rq *crq = RQ_DATA(rq);
 613
 614         if (crq) {
 615                 struct cfq_queue *cfqq = crq->cfq_queue;
 616
 617                 if (cfqq->cfqd->cfq_tagged) {
 618                         cfqq->service_used--;
 619                         cfq_sort_rr_list(cfqq, 0);
 620                 }
 621
 622                 if (crq->accounted) {
 623                         crq->accounted = 0;
 624                         cfqq->cfqd->rq_in_driver--;
 625                 }
 626         }
 627 }
 628
 629 /*
 630  * make sure the service time gets corrected on reissue of this request
 631  */
 632 static void cfq_requeue_request(request_queue_t *q, struct request *rq)
 633 {
 634         cfq_deactivate_request(q, rq);
 635         list_add(&rq->queuelist, &q->queue_head);
 636 }
 637
 638 static void cfq_remove_request(request_queue_t *q, struct request *rq)
 639 {
 640         struct cfq_rq *crq = RQ_DATA(rq);
 641
 642         if (crq) {
 643                 cfq_remove_merge_hints(q, crq);
 644                 list_del_init(&rq->queuelist);
 645
 646                 if (crq->cfq_queue)
 647                         cfq_del_crq_rb(crq);
 648         }
 649 }
 650
 651 static int
 652 cfq_merge(request_queue_t *q, struct request **req, struct bio *bio)
 653 {
 654         struct cfq_data *cfqd = q->elevator->elevator_data;
 655         struct request *__rq;
 656         int ret;
 657
 658         ret = elv_try_last_merge(q, bio);
 659         if (ret != ELEVATOR_NO_MERGE) {
 660                 __rq = q->last_merge;
 661                 goto out_insert;
 662         }
 663
 664         __rq = cfq_find_rq_hash(cfqd, bio->bi_sector);
 665         if (__rq) {
 666                 BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
 667
 668                 if (elv_rq_merge_ok(__rq, bio)) {
 669                         ret = ELEVATOR_BACK_MERGE;
 670                         goto out;
 671                 }
 672         }
 673
 674         __rq = cfq_find_rq_rb(cfqd, bio->bi_sector + bio_sectors(bio));
 675         if (__rq) {
 676                 if (elv_rq_merge_ok(__rq, bio)) {
 677                         ret = ELEVATOR_FRONT_MERGE;
 678                         goto out;
 679                 }
 680         }
 681
 682         return ELEVATOR_NO_MERGE;
 683 out:
 684         q->last_merge = __rq;
 685 out_insert:
 686         *req = __rq;
 687         return ret;
 688 }
 689
 690 static void cfq_merged_request(request_queue_t *q, struct request *req)
 691 {
 692         struct cfq_data *cfqd = q->elevator->elevator_data;
 693         struct cfq_rq *crq = RQ_DATA(req);
 694
 695         cfq_del_crq_hash(crq);
 696         cfq_add_crq_hash(cfqd, crq);
 697
 698         if (ON_RB(&crq->rb_node) && (rq_rb_key(req) != crq->rb_key)) {
 699                 struct cfq_queue *cfqq = crq->cfq_queue;
 700
 701                 cfq_update_next_crq(crq);
 702                 cfq_reposition_crq_rb(cfqq, crq);
 703         }
 704
 705         q->last_merge = req;
 706 }
 707
 708 static void
 709 cfq_merged_requests(request_queue_t *q, struct request *rq,
 710                     struct request *next)
 711 {
 712         struct cfq_rq *crq = RQ_DATA(rq);
 713         struct cfq_rq *cnext = RQ_DATA(next);
 714
 715         cfq_merged_request(q, rq);
 716
 717         if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist)) {
 718                 if (time_before(cnext->queue_start, crq->queue_start)) {
 719                         list_move(&rq->queuelist, &next->queuelist);
 720                         crq->queue_start = cnext->queue_start;
 721                 }
 722         }
 723
 724         cfq_update_next_crq(cnext);
 725         cfq_remove_request(q, next);
 726 }
 727
 728 /*
 729  * we dispatch cfqd->cfq_quantum requests in total from the rr_list queues,
 730  * this function sector sorts the selected request to minimize seeks. we start
 731  * at cfqd->last_sector, not 0.
 732  */
 733 static void cfq_dispatch_sort(request_queue_t *q, struct cfq_rq *crq)
 734 {
 735         struct cfq_data *cfqd = q->elevator->elevator_data;
 736         struct cfq_queue *cfqq = crq->cfq_queue;
 737         struct list_head *head = &q->queue_head, *entry = head;
 738         struct request *__rq;
 739         sector_t last;
 740
 741         cfq_del_crq_rb(crq);
 742         cfq_remove_merge_hints(q, crq);
 743         list_del(&crq->request->queuelist);
 744
 745         last = cfqd->last_sector;
 746         while ((entry = entry->prev) != head) {
 747                 __rq = list_entry_rq(entry);
 748
 749                 if (blk_barrier_rq(crq->request))
 750                         break;
 751                 if (!blk_fs_request(crq->request))
 752                         break;
 753
 754                 if (crq->request->sector > __rq->sector)
 755                         break;
 756                 if (__rq->sector > last && crq->request->sector < last) {
 757                         last = crq->request->sector;
 758                         break;
 759                 }
 760         }
 761
 762         cfqd->last_sector = last;
 763         crq->in_flight = 1;
 764         cfqq->in_flight++;
 765         list_add(&crq->request->queuelist, entry);
 766 }
 767
 768 /*
 769  * return expired entry, or NULL to just start from scratch in rbtree
 770  */
 771 static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq)
 772 {
 773         struct cfq_data *cfqd = cfqq->cfqd;
 774         const int reads = !list_empty(&cfqq->fifo[0]);
 775         const int writes = !list_empty(&cfqq->fifo[1]);
 776         unsigned long now = jiffies;
 777         struct cfq_rq *crq;
 778
 779         if (time_before(now, cfqq->last_fifo_expire + cfqd->cfq_fifo_batch_expire))
 780                 return NULL;
 781
 782         crq = RQ_DATA(list_entry(cfqq->fifo[0].next, struct request, queuelist));
 783         if (reads && time_after(now, crq->queue_start + cfqd->cfq_fifo_expire_r)) {
 784                 cfqq->last_fifo_expire = now;
 785                 return crq;
 786         }
 787
 788         crq = RQ_DATA(list_entry(cfqq->fifo[1].next, struct request, queuelist));
 789         if (writes && time_after(now, crq->queue_start + cfqd->cfq_fifo_expire_w)) {
 790                 cfqq->last_fifo_expire = now;
 791                 return crq;
 792         }
 793
 794         return NULL;
 795 }
 796
 797 /*
 798  * dispatch a single request from given queue
 799  */
 800 static inline void
 801 cfq_dispatch_request(request_queue_t *q, struct cfq_data *cfqd,
 802                      struct cfq_queue *cfqq)
 803 {
 804         struct cfq_rq *crq;
 805
 806         /*
 807          * follow expired path, else get first next available
 808          */
 809         if ((crq = cfq_check_fifo(cfqq)) == NULL) {
 810                 if (cfqd->find_best_crq)
 811                         crq = cfqq->next_crq;
 812                 else
 813                         crq = rb_entry_crq(rb_first(&cfqq->sort_list));
 814         }
 815
 816         cfqd->last_sector = crq->request->sector + crq->request->nr_sectors;
 817
 818         /*
 819          * finally, insert request into driver list
 820          */
 821         cfq_dispatch_sort(q, crq);
 822 }
 823
 824 static int cfq_dispatch_requests(request_queue_t *q, int max_dispatch)
 825 {
 826         struct cfq_data *cfqd = q->elevator->elevator_data;
 827         struct cfq_queue *cfqq;
 828         struct list_head *entry, *tmp;
 829         int queued, busy_queues, first_round;
 830
 831         if (list_empty(&cfqd->rr_list))
 832                 return 0;
 833
 834         queued = 0;
 835         first_round = 1;
 836 restart:
 837         busy_queues = 0;
 838         list_for_each_safe(entry, tmp, &cfqd->rr_list) {
 839                 cfqq = list_entry_cfqq(entry);
 840
 841                 BUG_ON(RB_EMPTY(&cfqq->sort_list));
 842
 843                 /*
 844                  * first round of queueing, only select from queues that
 845                  * don't already have io in-flight
 846                  */
 847                 if (first_round && cfqq->in_flight)
 848                         continue;
 849
 850                 cfq_dispatch_request(q, cfqd, cfqq);
 851
 852                 if (!RB_EMPTY(&cfqq->sort_list))
 853                         busy_queues++;
 854
 855                 queued++;
 856         }
 857
 858         if ((queued < max_dispatch) && (busy_queues || first_round)) {
 859                 first_round = 0;
 860                 goto restart;
 861         }
 862
 863         return queued;
 864 }
 865
 866 static inline void cfq_account_dispatch(struct cfq_rq *crq)
 867 {
 868         struct cfq_queue *cfqq = crq->cfq_queue;
 869         struct cfq_data *cfqd = cfqq->cfqd;
 870         unsigned long now, elapsed;
 871
 872         if (!blk_fs_request(crq->request))
 873                 return;
 874
 875         /*
 876          * accounted bit is necessary since some drivers will call
 877          * elv_next_request() many times for the same request (eg ide)
 878          */
 879         if (crq->accounted)
 880                 return;
 881
 882         now = jiffies;
 883         if (cfqq->service_start == ~0UL)
 884                 cfqq->service_start = now;
 885
 886         /*
 887          * on drives with tagged command queueing, command turn-around time
 888          * doesn't necessarily reflect the time spent processing this very
 889          * command inside the drive. so do the accounting differently there,
 890          * by just sorting on the number of requests
 891          */
 892         if (cfqd->cfq_tagged) {
 893                 if (time_after(now, cfqq->service_start + cfq_service)) {
 894                         cfqq->service_start = now;
 895                         cfqq->service_used /= 10;
 896                 }
 897
 898                 cfqq->service_used++;
 899                 cfq_sort_rr_list(cfqq, 0);
 900         }
 901
 902         elapsed = now - crq->queue_start;
 903         if (elapsed > max_elapsed_dispatch)
 904                 max_elapsed_dispatch = elapsed;
 905
 906         crq->accounted = 1;
 907         crq->service_start = now;
 908
 909         if (++cfqd->rq_in_driver >= CFQ_MAX_TAG && !cfqd->cfq_tagged) {
 910                 cfqq->cfqd->cfq_tagged = 1;
 911                 printk("cfq: depth %d reached, tagging now on\n", CFQ_MAX_TAG);
 912         }
 913 }
 914
 915 static inline void
 916 cfq_account_completion(struct cfq_queue *cfqq, struct cfq_rq *crq)
 917 {
 918         struct cfq_data *cfqd = cfqq->cfqd;
 919
 920         if (!crq->accounted)
 921                 return;
 922
 923         WARN_ON(!cfqd->rq_in_driver);
 924         cfqd->rq_in_driver--;
 925
 926         if (!cfqd->cfq_tagged) {
 927                 unsigned long now = jiffies;
 928                 unsigned long duration = now - crq->service_start;
 929
 930                 if (time_after(now, cfqq->service_start + cfq_service)) {
 931                         cfqq->service_start = now;
 932                         cfqq->service_used >>= 3;
 933                 }
 934
 935                 cfqq->service_used += duration;
 936                 cfq_sort_rr_list(cfqq, 0);
 937
 938                 if (duration > max_elapsed_crq)
 939                         max_elapsed_crq = duration;
 940         }
 941 }
 942
 943 static struct request *cfq_next_request(request_queue_t *q)
 944 {
 945         struct cfq_data *cfqd = q->elevator->elevator_data;
 946         struct request *rq;
 947
 948         if (!list_empty(&q->queue_head)) {
 949                 struct cfq_rq *crq;
 950 dispatch:
 951                 rq = list_entry_rq(q->queue_head.next);
 952
 953                 if ((crq = RQ_DATA(rq)) != NULL) {
 954                         cfq_remove_merge_hints(q, crq);
 955                         cfq_account_dispatch(crq);
 956                 }
 957
 958                 return rq;
 959         }
 960
 961         if (cfq_dispatch_requests(q, cfqd->cfq_quantum))
 962                 goto dispatch;
 963
 964         return NULL;
 965 }
 966
 967 /*
 968  * task holds one reference to the queue, dropped when task exits. each crq
 969  * in-flight on this queue also holds a reference, dropped when crq is freed.
 970  *
 971  * queue lock must be held here.
 972  */
 973 static void cfq_put_queue(struct cfq_queue *cfqq)
 974 {
 975         BUG_ON(!atomic_read(&cfqq->ref));
 976
 977         if (!atomic_dec_and_test(&cfqq->ref))
 978                 return;
 979
 980         BUG_ON(rb_first(&cfqq->sort_list));
 981         BUG_ON(cfqq->on_rr);
 982
 983         cfq_put_cfqd(cfqq->cfqd);
 984
 985         /*
 986          * it's on the empty list and still hashed
 987          */
 988         list_del(&cfqq->cfq_list);
 989         hlist_del(&cfqq->cfq_hash);
 990         kmem_cache_free(cfq_pool, cfqq);
 991 }
 992
 993 static inline struct cfq_queue *
 994 __cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned long key, const int hashval)
 995 {
 996         struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
 997         struct hlist_node *entry, *next;
 998
 999         hlist_for_each_safe(entry, next, hash_list) {
1000                 struct cfq_queue *__cfqq = list_entry_qhash(entry);
1001
1002                 if (__cfqq->key == key)
1003                         return __cfqq;
1004         }
1005
1006         return NULL;
1007 }
1008
1009 static struct cfq_queue *
1010 cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned long key)
1011 {
1012         return __cfq_find_cfq_hash(cfqd, key, hash_long(key, CFQ_QHASH_SHIFT));
1013 }
1014
1015 static inline void
1016 cfq_rehash_cfqq(struct cfq_data *cfqd, struct cfq_queue **cfqq,
1017                 struct cfq_io_context *cic)
1018 {
1019         unsigned long hashkey = cfq_hash_key(cfqd, current);
1020         unsigned long hashval = hash_long(hashkey, CFQ_QHASH_SHIFT);
1021         struct cfq_queue *__cfqq;
1022         unsigned long flags;
1023
1024         spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1025
1026         hlist_del(&(*cfqq)->cfq_hash);
1027
1028         __cfqq = __cfq_find_cfq_hash(cfqd, hashkey, hashval);
1029         if (!__cfqq || __cfqq == *cfqq) {
1030                 __cfqq = *cfqq;
1031                 hlist_add_head(&__cfqq->cfq_hash, &cfqd->cfq_hash[hashval]);
1032                 __cfqq->key_type = cfqd->key_type;
1033         } else {
1034                 atomic_inc(&__cfqq->ref);
1035                 cic->cfqq = __cfqq;
1036                 cfq_put_queue(*cfqq);
1037                 *cfqq = __cfqq;
1038         }
1039
1040         cic->cfqq = __cfqq;
1041         spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1042 }
1043
1044 static void cfq_free_io_context(struct cfq_io_context *cic)
1045 {
1046         kmem_cache_free(cfq_ioc_pool, cic);
1047 }
1048
1049 /*
1050  * locking hierarchy is: io_context lock -> queue locks
1051  */
1052 static void cfq_exit_io_context(struct cfq_io_context *cic)
1053 {
1054         struct cfq_queue *cfqq = cic->cfqq;
1055         struct list_head *entry = &cic->list;
1056         request_queue_t *q;
1057         unsigned long flags;
1058
1059         /*
1060          * put the reference this task is holding to the various queues
1061          */
1062         spin_lock_irqsave(&cic->ioc->lock, flags);
1063         while ((entry = cic->list.next) != &cic->list) {
1064                 struct cfq_io_context *__cic;
1065
1066                 __cic = list_entry(entry, struct cfq_io_context, list);
1067                 list_del(entry);
1068
1069                 q = __cic->cfqq->cfqd->queue;
1070                 spin_lock(q->queue_lock);
1071                 cfq_put_queue(__cic->cfqq);
1072                 spin_unlock(q->queue_lock);
1073         }
1074
1075         q = cfqq->cfqd->queue;
1076         spin_lock(q->queue_lock);
1077         cfq_put_queue(cfqq);
1078         spin_unlock(q->queue_lock);
1079
1080         cic->cfqq = NULL;
1081         spin_unlock_irqrestore(&cic->ioc->lock, flags);
1082 }
1083
1084 static struct cfq_io_context *cfq_alloc_io_context(int gfp_flags)
1085 {
1086         struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_flags);
1087
1088         if (cic) {
1089                 cic->dtor = cfq_free_io_context;
1090                 cic->exit = cfq_exit_io_context;
1091                 INIT_LIST_HEAD(&cic->list);
1092                 cic->cfqq = NULL;
1093         }
1094
1095         return cic;
1096 }
1097
1098 /*
1099  * Setup general io context and cfq io context. There can be several cfq
1100  * io contexts per general io context, if this process is doing io to more
1101  * than one device managed by cfq. Note that caller is holding a reference to
1102  * cfqq, so we don't need to worry about it disappearing
1103  */
1104 static struct cfq_io_context *
1105 cfq_get_io_context(struct cfq_queue **cfqq, int gfp_flags)
1106 {
1107         struct cfq_data *cfqd = (*cfqq)->cfqd;
1108         struct cfq_queue *__cfqq = *cfqq;
1109         struct cfq_io_context *cic;
1110         struct io_context *ioc;
1111
1112         might_sleep_if(gfp_flags & __GFP_WAIT);
1113
1114         ioc = get_io_context(gfp_flags);
1115         if (!ioc)
1116                 return NULL;
1117
1118         if ((cic = ioc->cic) == NULL) {
1119                 cic = cfq_alloc_io_context(gfp_flags);
1120
1121                 if (cic == NULL)
1122                         goto err;
1123
1124                 ioc->cic = cic;
1125                 cic->ioc = ioc;
1126                 cic->cfqq = __cfqq;
1127                 atomic_inc(&__cfqq->ref);
1128         } else {
1129                 struct cfq_io_context *__cic;
1130                 unsigned long flags;
1131
1132                 /*
1133                  * since the first cic on the list is actually the head
1134                  * itself, need to check this here or we'll duplicate an
1135                  * cic per ioc for no reason
1136                  */
1137                 if (cic->cfqq == __cfqq)
1138                         goto out;
1139
1140                 /*
1141                  * cic exists, check if we already are there. linear search
1142                  * should be ok here, the list will usually not be more than
1143                  * 1 or a few entries long
1144                  */
1145                 spin_lock_irqsave(&ioc->lock, flags);
1146                 list_for_each_entry(__cic, &cic->list, list) {
1147                         /*
1148                          * this process is already holding a reference to
1149                          * this queue, so no need to get one more
1150                          */
1151                         if (__cic->cfqq == __cfqq) {
1152                                 cic = __cic;
1153                                 spin_unlock_irqrestore(&ioc->lock, flags);
1154                                 goto out;
1155                         }
1156                 }
1157                 spin_unlock_irqrestore(&ioc->lock, flags);
1158
1159                 /*
1160                  * nope, process doesn't have a cic assoicated with this
1161                  * cfqq yet. get a new one and add to list
1162                  */
1163                 __cic = cfq_alloc_io_context(gfp_flags);
1164                 if (__cic == NULL)
1165                         goto err;
1166
1167                 __cic->ioc = ioc;
1168                 __cic->cfqq = __cfqq;
1169                 atomic_inc(&__cfqq->ref);
1170                 spin_lock_irqsave(&ioc->lock, flags);
1171                 list_add(&__cic->list, &cic->list);
1172                 spin_unlock_irqrestore(&ioc->lock, flags);
1173
1174                 cic = __cic;
1175                 *cfqq = __cfqq;
1176         }
1177
1178 out:
1179         /*
1180          * if key_type has been changed on the fly, we lazily rehash
1181          * each queue at lookup time
1182          */
1183         if ((*cfqq)->key_type != cfqd->key_type)
1184                 cfq_rehash_cfqq(cfqd, cfqq, cic);
1185
1186         return cic;
1187 err:
1188         put_io_context(ioc);
1189         return NULL;
1190 }
1191
1192 static struct cfq_queue *
1193 __cfq_get_queue(struct cfq_data *cfqd, unsigned long key, int gfp_mask)
1194 {
1195         const int hashval = hash_long(key, CFQ_QHASH_SHIFT);
1196         struct cfq_queue *cfqq, *new_cfqq = NULL;
1197
1198 retry:
1199         cfqq = __cfq_find_cfq_hash(cfqd, key, hashval);
1200
1201         if (!cfqq) {
1202                 if (new_cfqq) {
1203                         cfqq = new_cfqq;
1204                         new_cfqq = NULL;
1205                 } else if (gfp_mask & __GFP_WAIT) {
1206                         spin_unlock_irq(cfqd->queue->queue_lock);
1207                         new_cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
1208                         spin_lock_irq(cfqd->queue->queue_lock);
1209                         goto retry;
1210                 } else
1211                         goto out;
1212
1213                 memset(cfqq, 0, sizeof(*cfqq));
1214
1215                 INIT_HLIST_NODE(&cfqq->cfq_hash);
1216                 INIT_LIST_HEAD(&cfqq->cfq_list);
1217                 RB_CLEAR_ROOT(&cfqq->sort_list);
1218                 INIT_LIST_HEAD(&cfqq->fifo[0]);
1219                 INIT_LIST_HEAD(&cfqq->fifo[1]);
1220
1221                 cfqq->key = key;
1222                 hlist_add_head(&cfqq->cfq_hash, &cfqd->cfq_hash[hashval]);
1223                 atomic_set(&cfqq->ref, 0);
1224                 cfqq->cfqd = cfqd;
1225                 atomic_inc(&cfqd->ref);
1226                 cfqq->key_type = cfqd->key_type;
1227                 cfqq->service_start = ~0UL;
1228         }
1229
1230         if (new_cfqq)
1231                 kmem_cache_free(cfq_pool, new_cfqq);
1232
1233         atomic_inc(&cfqq->ref);
1234 out:
1235         WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
1236         return cfqq;
1237 }
1238
1239 static void cfq_enqueue(struct cfq_data *cfqd, struct cfq_rq *crq)
1240 {
1241         crq->is_sync = 0;
1242         if (rq_data_dir(crq->request) == READ || current->flags & PF_SYNCWRITE)
1243                 crq->is_sync = 1;
1244
1245         cfq_add_crq_rb(crq);
1246         crq->queue_start = jiffies;
1247
1248         list_add_tail(&crq->request->queuelist, &crq->cfq_queue->fifo[crq->is_sync]);
1249 }
1250
1251 static void
1252 cfq_insert_request(request_queue_t *q, struct request *rq, int where)
1253 {
1254         struct cfq_data *cfqd = q->elevator->elevator_data;
1255         struct cfq_rq *crq = RQ_DATA(rq);
1256
1257         switch (where) {
1258                 case ELEVATOR_INSERT_BACK:
1259                         while (cfq_dispatch_requests(q, cfqd->cfq_quantum))
1260                                 ;
1261                         list_add_tail(&rq->queuelist, &q->queue_head);
1262                         break;
1263                 case ELEVATOR_INSERT_FRONT:
1264                         list_add(&rq->queuelist, &q->queue_head);
1265                         break;
1266                 case ELEVATOR_INSERT_SORT:
1267                         BUG_ON(!blk_fs_request(rq));
1268                         cfq_enqueue(cfqd, crq);
1269                         break;
1270                 default:
1271                         printk("%s: bad insert point %d\n", __FUNCTION__,where);
1272                         return;
1273         }
1274
1275         if (rq_mergeable(rq)) {
1276                 cfq_add_crq_hash(cfqd, crq);
1277
1278                 if (!q->last_merge)
1279                         q->last_merge = rq;
1280         }
1281 }
1282
1283 static int cfq_queue_empty(request_queue_t *q)
1284 {
1285         struct cfq_data *cfqd = q->elevator->elevator_data;
1286
1287         return list_empty(&q->queue_head) && list_empty(&cfqd->rr_list);
1288 }
1289
1290 static void cfq_completed_request(request_queue_t *q, struct request *rq)
1291 {
1292         struct cfq_rq *crq = RQ_DATA(rq);
1293         struct cfq_queue *cfqq;
1294
1295         if (unlikely(!blk_fs_request(rq)))
1296                 return;
1297
1298         cfqq = crq->cfq_queue;
1299
1300         if (crq->in_flight) {
1301                 WARN_ON(!cfqq->in_flight);
1302                 cfqq->in_flight--;
1303         }
1304
1305         cfq_account_completion(cfqq, crq);
1306 }
1307
1308 static struct request *
1309 cfq_former_request(request_queue_t *q, struct request *rq)
1310 {
1311         struct cfq_rq *crq = RQ_DATA(rq);
1312         struct rb_node *rbprev = rb_prev(&crq->rb_node);
1313
1314         if (rbprev)
1315                 return rb_entry_crq(rbprev)->request;
1316
1317         return NULL;
1318 }
1319
1320 static struct request *
1321 cfq_latter_request(request_queue_t *q, struct request *rq)
1322 {
1323         struct cfq_rq *crq = RQ_DATA(rq);
1324         struct rb_node *rbnext = rb_next(&crq->rb_node);
1325
1326         if (rbnext)
1327                 return rb_entry_crq(rbnext)->request;
1328
1329         return NULL;
1330 }
1331
1332 static int cfq_may_queue(request_queue_t *q, int rw)
1333 {
1334         struct cfq_data *cfqd = q->elevator->elevator_data;
1335         struct cfq_queue *cfqq;
1336         int ret = ELV_MQUEUE_MAY;
1337
1338         if (current->flags & PF_MEMALLOC)
1339                 return ELV_MQUEUE_MAY;
1340
1341         cfqq = cfq_find_cfq_hash(cfqd, cfq_hash_key(cfqd, current));
1342         if (cfqq) {
1343                 int limit = cfqd->max_queued;
1344
1345                 if (cfqq->allocated[rw] < cfqd->cfq_queued)
1346                         return ELV_MQUEUE_MUST;
1347
1348                 if (cfqd->busy_queues)
1349                         limit = q->nr_requests / cfqd->busy_queues;
1350
1351                 if (limit < cfqd->cfq_queued)
1352                         limit = cfqd->cfq_queued;
1353                 else if (limit > cfqd->max_queued)
1354                         limit = cfqd->max_queued;
1355
1356                 if (cfqq->allocated[rw] >= limit) {
1357                         if (limit > cfqq->alloc_limit[rw])
1358                                 cfqq->alloc_limit[rw] = limit;
1359
1360                         ret = ELV_MQUEUE_NO;
1361                 }
1362         }
1363
1364         return ret;
1365 }
1366
1367 static void cfq_check_waiters(request_queue_t *q, struct cfq_queue *cfqq)
1368 {
1369         struct request_list *rl = &q->rq;
1370         const int write = waitqueue_active(&rl->wait[WRITE]);
1371         const int read = waitqueue_active(&rl->wait[READ]);
1372
1373         if (read && cfqq->allocated[READ] < cfqq->alloc_limit[READ])
1374                 wake_up(&rl->wait[READ]);
1375         if (write && cfqq->allocated[WRITE] < cfqq->alloc_limit[WRITE])
1376                 wake_up(&rl->wait[WRITE]);
1377 }
1378
1379 /*
1380  * queue lock held here
1381  */
1382 static void cfq_put_request(request_queue_t *q, struct request *rq)
1383 {
1384         struct cfq_data *cfqd = q->elevator->elevator_data;
1385         struct cfq_rq *crq = RQ_DATA(rq);
1386
1387         if (crq) {
1388                 struct cfq_queue *cfqq = crq->cfq_queue;
1389
1390                 BUG_ON(q->last_merge == rq);
1391                 BUG_ON(!hlist_unhashed(&crq->hash));
1392
1393                 if (crq->io_context)
1394                         put_io_context(crq->io_context->ioc);
1395
1396                 BUG_ON(!cfqq->allocated[crq->is_write]);
1397                 cfqq->allocated[crq->is_write]--;
1398
1399                 mempool_free(crq, cfqd->crq_pool);
1400                 rq->elevator_private = NULL;
1401
1402                 smp_mb();
1403                 cfq_check_waiters(q, cfqq);
1404                 cfq_put_queue(cfqq);
1405         }
1406 }
1407
1408 /*
1409  * Allocate cfq data structures associated with this request. A queue and
1410  */
1411 static int cfq_set_request(request_queue_t *q, struct request *rq, int gfp_mask)
1412 {
1413         struct cfq_data *cfqd = q->elevator->elevator_data;
1414         struct cfq_io_context *cic;
1415         const int rw = rq_data_dir(rq);
1416         struct cfq_queue *cfqq, *saved_cfqq;
1417         struct cfq_rq *crq;
1418         unsigned long flags;
1419
1420         might_sleep_if(gfp_mask & __GFP_WAIT);
1421
1422         spin_lock_irqsave(q->queue_lock, flags);
1423
1424         cfqq = __cfq_get_queue(cfqd, cfq_hash_key(cfqd, current), gfp_mask);
1425         if (!cfqq)
1426                 goto out_lock;
1427
1428 repeat:
1429         if (cfqq->allocated[rw] >= cfqd->max_queued)
1430                 goto out_lock;
1431
1432         cfqq->allocated[rw]++;
1433         spin_unlock_irqrestore(q->queue_lock, flags);
1434
1435         /*
1436          * if hashing type has changed, the cfq_queue might change here.
1437          */
1438         saved_cfqq = cfqq;
1439         cic = cfq_get_io_context(&cfqq, gfp_mask);
1440         if (!cic)
1441                 goto err;
1442
1443         /*
1444          * repeat allocation checks on queue change
1445          */
1446         if (unlikely(saved_cfqq != cfqq)) {
1447                 spin_lock_irqsave(q->queue_lock, flags);
1448                 saved_cfqq->allocated[rw]--;
1449                 goto repeat;
1450         }
1451
1452         crq = mempool_alloc(cfqd->crq_pool, gfp_mask);
1453         if (crq) {
1454                 RB_CLEAR(&crq->rb_node);
1455                 crq->rb_key = 0;
1456                 crq->request = rq;
1457                 INIT_HLIST_NODE(&crq->hash);
1458                 crq->cfq_queue = cfqq;
1459                 crq->io_context = cic;
1460                 crq->service_start = crq->queue_start = 0;
1461                 crq->in_flight = crq->accounted = crq->is_sync = 0;
1462                 crq->is_write = rw;
1463                 rq->elevator_private = crq;
1464                 cfqq->alloc_limit[rw] = 0;
1465                 return 0;
1466         }
1467
1468         put_io_context(cic->ioc);
1469 err:
1470         spin_lock_irqsave(q->queue_lock, flags);
1471         cfqq->allocated[rw]--;
1472         cfq_put_queue(cfqq);
1473 out_lock:
1474         spin_unlock_irqrestore(q->queue_lock, flags);
1475         return 1;
1476 }
1477
1478 static void cfq_put_cfqd(struct cfq_data *cfqd)
1479 {
1480         request_queue_t *q = cfqd->queue;
1481
1482         if (!atomic_dec_and_test(&cfqd->ref))
1483                 return;
1484
1485         blk_put_queue(q);
1486
1487         mempool_destroy(cfqd->crq_pool);
1488         kfree(cfqd->crq_hash);
1489         kfree(cfqd->cfq_hash);
1490         kfree(cfqd);
1491 }
1492
1493 static void cfq_exit_queue(elevator_t *e)
1494 {
1495         cfq_put_cfqd(e->elevator_data);
1496 }
1497
1498 static int cfq_init_queue(request_queue_t *q, elevator_t *e)
1499 {
1500         struct cfq_data *cfqd;
1501         int i;
1502
1503         cfqd = kmalloc(sizeof(*cfqd), GFP_KERNEL);
1504         if (!cfqd)
1505                 return -ENOMEM;
1506
1507         memset(cfqd, 0, sizeof(*cfqd));
1508         INIT_LIST_HEAD(&cfqd->rr_list);
1509         INIT_LIST_HEAD(&cfqd->empty_list);
1510
1511         cfqd->crq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_MHASH_ENTRIES, GFP_KERNEL);
1512         if (!cfqd->crq_hash)
1513                 goto out_crqhash;
1514
1515         cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL);
1516         if (!cfqd->cfq_hash)
1517                 goto out_cfqhash;
1518
1519         cfqd->crq_pool = mempool_create(BLKDEV_MIN_RQ, mempool_alloc_slab, mempool_free_slab, crq_pool);
1520         if (!cfqd->crq_pool)
1521                 goto out_crqpool;
1522
1523         for (i = 0; i < CFQ_MHASH_ENTRIES; i++)
1524                 INIT_HLIST_HEAD(&cfqd->crq_hash[i]);
1525         for (i = 0; i < CFQ_QHASH_ENTRIES; i++)
1526                 INIT_HLIST_HEAD(&cfqd->cfq_hash[i]);
1527
1528         e->elevator_data = cfqd;
1529
1530         cfqd->queue = q;
1531         atomic_inc(&q->refcnt);
1532
1533         /*
1534          * just set it to some high value, we want anyone to be able to queue
1535          * some requests. fairness is handled differently
1536          */
1537         q->nr_requests = 1024;
1538         cfqd->max_queued = q->nr_requests / 16;
1539         q->nr_batching = cfq_queued;
1540         cfqd->key_type = CFQ_KEY_TGID;
1541         cfqd->find_best_crq = 1;
1542         atomic_set(&cfqd->ref, 1);
1543
1544         cfqd->cfq_queued = cfq_queued;
1545         cfqd->cfq_quantum = cfq_quantum;
1546         cfqd->cfq_fifo_expire_r = cfq_fifo_expire_r;
1547         cfqd->cfq_fifo_expire_w = cfq_fifo_expire_w;
1548         cfqd->cfq_fifo_batch_expire = cfq_fifo_rate;
1549         cfqd->cfq_back_max = cfq_back_max;
1550         cfqd->cfq_back_penalty = cfq_back_penalty;
1551
1552         return 0;
1553 out_crqpool:
1554         kfree(cfqd->cfq_hash);
1555 out_cfqhash:
1556         kfree(cfqd->crq_hash);
1557 out_crqhash:
1558         kfree(cfqd);
1559         return -ENOMEM;
1560 }
1561
1562 static void cfq_slab_kill(void)
1563 {
1564         if (crq_pool)
1565                 kmem_cache_destroy(crq_pool);
1566         if (cfq_pool)
1567                 kmem_cache_destroy(cfq_pool);
1568         if (cfq_ioc_pool)
1569                 kmem_cache_destroy(cfq_ioc_pool);
1570 }
1571
1572 static int __init cfq_slab_setup(void)
1573 {
1574         crq_pool = kmem_cache_create("crq_pool", sizeof(struct cfq_rq), 0, 0,
1575                                         NULL, NULL);
1576         if (!crq_pool)
1577                 goto fail;
1578
1579         cfq_pool = kmem_cache_create("cfq_pool", sizeof(struct cfq_queue), 0, 0,
1580                                         NULL, NULL);
1581         if (!cfq_pool)
1582                 goto fail;
1583
1584         cfq_ioc_pool = kmem_cache_create("cfq_ioc_pool",
1585                         sizeof(struct cfq_io_context), 0, 0, NULL, NULL);
1586         if (!cfq_ioc_pool)
1587                 goto fail;
1588
1589         return 0;
1590 fail:
1591         cfq_slab_kill();
1592         return -ENOMEM;
1593 }
1594
1595
1596 /*
1597  * sysfs parts below -->
1598  */
1599 struct cfq_fs_entry {
1600         struct attribute attr;
1601         ssize_t (*show)(struct cfq_data *, char *);
1602         ssize_t (*store)(struct cfq_data *, const char *, size_t);
1603 };
1604
1605 static ssize_t
1606 cfq_var_show(unsigned int var, char *page)
1607 {
1608         return sprintf(page, "%d\n", var);
1609 }
1610
1611 static ssize_t
1612 cfq_var_store(unsigned int *var, const char *page, size_t count)
1613 {
1614         char *p = (char *) page;
1615
1616         *var = simple_strtoul(p, &p, 10);
1617         return count;
1618 }
1619
1620 static ssize_t
1621 cfq_clear_elapsed(struct cfq_data *cfqd, const char *page, size_t count)
1622 {
1623         max_elapsed_dispatch = max_elapsed_crq = 0;
1624         return count;
1625 }
1626
1627 static ssize_t
1628 cfq_set_key_type(struct cfq_data *cfqd, const char *page, size_t count)
1629 {
1630         spin_lock_irq(cfqd->queue->queue_lock);
1631         if (!strncmp(page, "pgid", 4))
1632                 cfqd->key_type = CFQ_KEY_PGID;
1633         else if (!strncmp(page, "tgid", 4))
1634                 cfqd->key_type = CFQ_KEY_TGID;
1635         else if (!strncmp(page, "uid", 3))
1636                 cfqd->key_type = CFQ_KEY_UID;
1637         else if (!strncmp(page, "gid", 3))
1638                 cfqd->key_type = CFQ_KEY_GID;
1639         spin_unlock_irq(cfqd->queue->queue_lock);
1640         return count;
1641 }
1642
1643 static ssize_t
1644 cfq_read_key_type(struct cfq_data *cfqd, char *page)
1645 {
1646         ssize_t len = 0;
1647         int i;
1648
1649         for (i = CFQ_KEY_PGID; i < CFQ_KEY_LAST; i++) {
1650                 if (cfqd->key_type == i)
1651                         len += sprintf(page+len, "[%s] ", cfq_key_types[i]);
1652                 else
1653                         len += sprintf(page+len, "%s ", cfq_key_types[i]);
1654         }
1655         len += sprintf(page+len, "\n");
1656         return len;
1657 }
1658
1659 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV)                            \
1660 static ssize_t __FUNC(struct cfq_data *cfqd, char *page)                \
1661 {                                                                       \
1662         unsigned int __data = __VAR;                                    \
1663         if (__CONV)                                                     \
1664                 __data = jiffies_to_msecs(__data);                      \
1665         return cfq_var_show(__data, (page));                            \
1666 }
1667 SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
1668 SHOW_FUNCTION(cfq_queued_show, cfqd->cfq_queued, 0);
1669 SHOW_FUNCTION(cfq_fifo_expire_r_show, cfqd->cfq_fifo_expire_r, 1);
1670 SHOW_FUNCTION(cfq_fifo_expire_w_show, cfqd->cfq_fifo_expire_w, 1);
1671 SHOW_FUNCTION(cfq_fifo_batch_expire_show, cfqd->cfq_fifo_batch_expire, 1);
1672 SHOW_FUNCTION(cfq_find_best_show, cfqd->find_best_crq, 0);
1673 SHOW_FUNCTION(cfq_back_max_show, cfqd->cfq_back_max, 0);
1674 SHOW_FUNCTION(cfq_back_penalty_show, cfqd->cfq_back_penalty, 0);
1675 #undef SHOW_FUNCTION
1676
1677 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)                 \
1678 static ssize_t __FUNC(struct cfq_data *cfqd, const char *page, size_t count)    \
1679 {                                                                       \
1680         unsigned int __data;                                            \
1681         int ret = cfq_var_store(&__data, (page), count);                \
1682         if (__data < (MIN))                                             \
1683                 __data = (MIN);                                         \
1684         else if (__data > (MAX))                                        \
1685                 __data = (MAX);                                         \
1686         if (__CONV)                                                     \
1687                 *(__PTR) = msecs_to_jiffies(__data);                    \
1688         else                                                            \
1689                 *(__PTR) = __data;                                      \
1690         return ret;                                                     \
1691 }
1692 STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
1693 STORE_FUNCTION(cfq_queued_store, &cfqd->cfq_queued, 1, UINT_MAX, 0);
1694 STORE_FUNCTION(cfq_fifo_expire_r_store, &cfqd->cfq_fifo_expire_r, 1, UINT_MAX, 1);
1695 STORE_FUNCTION(cfq_fifo_expire_w_store, &cfqd->cfq_fifo_expire_w, 1, UINT_MAX, 1);
1696 STORE_FUNCTION(cfq_fifo_batch_expire_store, &cfqd->cfq_fifo_batch_expire, 0, UINT_MAX, 1);
1697 STORE_FUNCTION(cfq_find_best_store, &cfqd->find_best_crq, 0, 1, 0);
1698 STORE_FUNCTION(cfq_back_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
1699 STORE_FUNCTION(cfq_back_penalty_store, &cfqd->cfq_back_penalty, 1, UINT_MAX, 0);
1700 #undef STORE_FUNCTION
1701
1702 static struct cfq_fs_entry cfq_quantum_entry = {
1703         .attr = {.name = "quantum", .mode = S_IRUGO | S_IWUSR },
1704         .show = cfq_quantum_show,
1705         .store = cfq_quantum_store,
1706 };
1707 static struct cfq_fs_entry cfq_queued_entry = {
1708         .attr = {.name = "queued", .mode = S_IRUGO | S_IWUSR },
1709         .show = cfq_queued_show,
1710         .store = cfq_queued_store,
1711 };
1712 static struct cfq_fs_entry cfq_fifo_expire_r_entry = {
1713         .attr = {.name = "fifo_expire_sync", .mode = S_IRUGO | S_IWUSR },
1714         .show = cfq_fifo_expire_r_show,
1715         .store = cfq_fifo_expire_r_store,
1716 };
1717 static struct cfq_fs_entry cfq_fifo_expire_w_entry = {
1718         .attr = {.name = "fifo_expire_async", .mode = S_IRUGO | S_IWUSR },
1719         .show = cfq_fifo_expire_w_show,
1720         .store = cfq_fifo_expire_w_store,
1721 };
1722 static struct cfq_fs_entry cfq_fifo_batch_expire_entry = {
1723         .attr = {.name = "fifo_batch_expire", .mode = S_IRUGO | S_IWUSR },
1724         .show = cfq_fifo_batch_expire_show,
1725         .store = cfq_fifo_batch_expire_store,
1726 };
1727 static struct cfq_fs_entry cfq_find_best_entry = {
1728         .attr = {.name = "find_best_crq", .mode = S_IRUGO | S_IWUSR },
1729         .show = cfq_find_best_show,
1730         .store = cfq_find_best_store,
1731 };
1732 static struct cfq_fs_entry cfq_back_max_entry = {
1733         .attr = {.name = "back_seek_max", .mode = S_IRUGO | S_IWUSR },
1734         .show = cfq_back_max_show,
1735         .store = cfq_back_max_store,
1736 };
1737 static struct cfq_fs_entry cfq_back_penalty_entry = {
1738         .attr = {.name = "back_seek_penalty", .mode = S_IRUGO | S_IWUSR },
1739         .show = cfq_back_penalty_show,
1740         .store = cfq_back_penalty_store,
1741 };
1742 static struct cfq_fs_entry cfq_clear_elapsed_entry = {
1743         .attr = {.name = "clear_elapsed", .mode = S_IWUSR },
1744         .store = cfq_clear_elapsed,
1745 };
1746 static struct cfq_fs_entry cfq_key_type_entry = {
1747         .attr = {.name = "key_type", .mode = S_IRUGO | S_IWUSR },
1748         .show = cfq_read_key_type,
1749         .store = cfq_set_key_type,
1750 };
1751
1752 static struct attribute *default_attrs[] = {
1753         &cfq_quantum_entry.attr,
1754         &cfq_queued_entry.attr,
1755         &cfq_fifo_expire_r_entry.attr,
1756         &cfq_fifo_expire_w_entry.attr,
1757         &cfq_fifo_batch_expire_entry.attr,
1758         &cfq_key_type_entry.attr,
1759         &cfq_find_best_entry.attr,
1760         &cfq_back_max_entry.attr,
1761         &cfq_back_penalty_entry.attr,
1762         &cfq_clear_elapsed_entry.attr,
1763         NULL,
1764 };
1765
1766 #define to_cfq(atr) container_of((atr), struct cfq_fs_entry, attr)
1767
1768 static ssize_t
1769 cfq_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
1770 {
1771         elevator_t *e = container_of(kobj, elevator_t, kobj);
1772         struct cfq_fs_entry *entry = to_cfq(attr);
1773
1774         if (!entry->show)
1775                 return 0;
1776
1777         return entry->show(e->elevator_data, page);
1778 }
1779
1780 static ssize_t
1781 cfq_attr_store(struct kobject *kobj, struct attribute *attr,
1782                const char *page, size_t length)
1783 {
1784         elevator_t *e = container_of(kobj, elevator_t, kobj);
1785         struct cfq_fs_entry *entry = to_cfq(attr);
1786
1787         if (!entry->store)
1788                 return -EINVAL;
1789
1790         return entry->store(e->elevator_data, page, length);
1791 }
1792
1793 static struct sysfs_ops cfq_sysfs_ops = {
1794         .show   = cfq_attr_show,
1795         .store  = cfq_attr_store,
1796 };
1797
1798 static struct kobj_type cfq_ktype = {
1799         .sysfs_ops      = &cfq_sysfs_ops,
1800         .default_attrs  = default_attrs,
1801 };
1802
1803 static struct elevator_type iosched_cfq = {
1804         .ops = {
1805                 .elevator_merge_fn =            cfq_merge,
1806                 .elevator_merged_fn =           cfq_merged_request,
1807                 .elevator_merge_req_fn =        cfq_merged_requests,
1808                 .elevator_next_req_fn =         cfq_next_request,
1809                 .elevator_add_req_fn =          cfq_insert_request,
1810                 .elevator_remove_req_fn =       cfq_remove_request,
1811                 .elevator_requeue_req_fn =      cfq_requeue_request,
1812                 .elevator_deactivate_req_fn =   cfq_deactivate_request,
1813                 .elevator_queue_empty_fn =      cfq_queue_empty,
1814                 .elevator_completed_req_fn =    cfq_completed_request,
1815                 .elevator_former_req_fn =       cfq_former_request,
1816                 .elevator_latter_req_fn =       cfq_latter_request,
1817                 .elevator_set_req_fn =          cfq_set_request,
1818                 .elevator_put_req_fn =          cfq_put_request,
1819                 .elevator_may_queue_fn =        cfq_may_queue,
1820                 .elevator_init_fn =             cfq_init_queue,
1821                 .elevator_exit_fn =             cfq_exit_queue,
1822         },
1823         .elevator_ktype =       &cfq_ktype,
1824         .elevator_name =        "cfq",
1825         .elevator_owner =       THIS_MODULE,
1826 };
1827
1828 static int __init cfq_init(void)
1829 {
1830         int ret;
1831
1832         if (cfq_slab_setup())
1833                 return -ENOMEM;
1834
1835         ret = elv_register(&iosched_cfq);
1836         if (!ret) {
1837                 __module_get(THIS_MODULE);
1838                 return 0;
1839         }
1840
1841         cfq_slab_kill();
1842         return ret;
1843 }
1844
1845 static void __exit cfq_exit(void)
1846 {
1847         cfq_slab_kill();
1848         elv_unregister(&iosched_cfq);
1849 }
1850
1851 module_init(cfq_init);
1852 module_exit(cfq_exit);
1853
1854 MODULE_AUTHOR("Jens Axboe");
1855 MODULE_LICENSE("GPL");
1856 MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");