linux/block/as-iosched.c
<<
>>
Prefs
   1/*
   2 *  Anticipatory & deadline i/o scheduler.
   3 *
   4 *  Copyright (C) 2002 Jens Axboe <axboe@kernel.dk>
   5 *                     Nick Piggin <nickpiggin@yahoo.com.au>
   6 *
   7 */
   8#include <linux/kernel.h>
   9#include <linux/fs.h>
  10#include <linux/blkdev.h>
  11#include <linux/elevator.h>
  12#include <linux/bio.h>
  13#include <linux/module.h>
  14#include <linux/slab.h>
  15#include <linux/init.h>
  16#include <linux/compiler.h>
  17#include <linux/rbtree.h>
  18#include <linux/interrupt.h>
  19
  20/*
  21 * See Documentation/block/as-iosched.txt
  22 */
  23
  24/*
  25 * max time before a read is submitted.
  26 */
  27#define default_read_expire (HZ / 8)
  28
  29/*
  30 * ditto for writes, these limits are not hard, even
  31 * if the disk is capable of satisfying them.
  32 */
  33#define default_write_expire (HZ / 4)
  34
  35/*
  36 * read_batch_expire describes how long we will allow a stream of reads to
  37 * persist before looking to see whether it is time to switch over to writes.
  38 */
  39#define default_read_batch_expire (HZ / 2)
  40
  41/*
  42 * write_batch_expire describes how long we want a stream of writes to run for.
  43 * This is not a hard limit, but a target we set for the auto-tuning thingy.
  44 * See, the problem is: we can send a lot of writes to disk cache / TCQ in
  45 * a short amount of time...
  46 */
  47#define default_write_batch_expire (HZ / 8)
  48
  49/*
  50 * max time we may wait to anticipate a read (default around 6ms)
  51 */
  52#define default_antic_expire ((HZ / 150) ? HZ / 150 : 1)
  53
  54/*
  55 * Keep track of up to 20ms thinktimes. We can go as big as we like here,
  56 * however huge values tend to interfere and not decay fast enough. A program
  57 * might be in a non-io phase of operation. Waiting on user input for example,
  58 * or doing a lengthy computation. A small penalty can be justified there, and
  59 * will still catch out those processes that constantly have large thinktimes.
  60 */
  61#define MAX_THINKTIME (HZ/50UL)
  62
  63/* Bits in as_io_context.state */
  64enum as_io_states {
  65        AS_TASK_RUNNING=0,      /* Process has not exited */
  66        AS_TASK_IOSTARTED,      /* Process has started some IO */
  67        AS_TASK_IORUNNING,      /* Process has completed some IO */
  68};
  69
  70enum anticipation_status {
  71        ANTIC_OFF=0,            /* Not anticipating (normal operation)  */
  72        ANTIC_WAIT_REQ,         /* The last read has not yet completed  */
  73        ANTIC_WAIT_NEXT,        /* Currently anticipating a request vs
  74                                   last read (which has completed) */
  75        ANTIC_FINISHED,         /* Anticipating but have found a candidate
  76                                 * or timed out */
  77};
  78
  79struct as_data {
  80        /*
  81         * run time data
  82         */
  83
  84        struct request_queue *q;        /* the "owner" queue */
  85
  86        /*
  87         * requests (as_rq s) are present on both sort_list and fifo_list
  88         */
  89        struct rb_root sort_list[2];
  90        struct list_head fifo_list[2];
  91
  92        struct request *next_rq[2];     /* next in sort order */
  93        sector_t last_sector[2];        /* last SYNC & ASYNC sectors */
  94
  95        unsigned long exit_prob;        /* probability a task will exit while
  96                                           being waited on */
  97        unsigned long exit_no_coop;     /* probablility an exited task will
  98                                           not be part of a later cooperating
  99                                           request */
 100        unsigned long new_ttime_total;  /* mean thinktime on new proc */
 101        unsigned long new_ttime_mean;
 102        u64 new_seek_total;             /* mean seek on new proc */
 103        sector_t new_seek_mean;
 104
 105        unsigned long current_batch_expires;
 106        unsigned long last_check_fifo[2];
 107        int changed_batch;              /* 1: waiting for old batch to end */
 108        int new_batch;                  /* 1: waiting on first read complete */
 109        int batch_data_dir;             /* current batch SYNC / ASYNC */
 110        int write_batch_count;          /* max # of reqs in a write batch */
 111        int current_write_count;        /* how many requests left this batch */
 112        int write_batch_idled;          /* has the write batch gone idle? */
 113
 114        enum anticipation_status antic_status;
 115        unsigned long antic_start;      /* jiffies: when it started */
 116        struct timer_list antic_timer;  /* anticipatory scheduling timer */
 117        struct work_struct antic_work;  /* Deferred unplugging */
 118        struct io_context *io_context;  /* Identify the expected process */
 119        int ioc_finished; /* IO associated with io_context is finished */
 120        int nr_dispatched;
 121
 122        /*
 123         * settings that change how the i/o scheduler behaves
 124         */
 125        unsigned long fifo_expire[2];
 126        unsigned long batch_expire[2];
 127        unsigned long antic_expire;
 128};
 129
 130/*
 131 * per-request data.
 132 */
 133enum arq_state {
 134        AS_RQ_NEW=0,            /* New - not referenced and not on any lists */
 135        AS_RQ_QUEUED,           /* In the request queue. It belongs to the
 136                                   scheduler */
 137        AS_RQ_DISPATCHED,       /* On the dispatch list. It belongs to the
 138                                   driver now */
 139        AS_RQ_PRESCHED,         /* Debug poisoning for requests being used */
 140        AS_RQ_REMOVED,
 141        AS_RQ_MERGED,
 142        AS_RQ_POSTSCHED,        /* when they shouldn't be */
 143};
 144
 145#define RQ_IOC(rq)      ((struct io_context *) (rq)->elevator_private)
 146#define RQ_STATE(rq)    ((enum arq_state)(rq)->elevator_private2)
 147#define RQ_SET_STATE(rq, state) ((rq)->elevator_private2 = (void *) state)
 148
 149static DEFINE_PER_CPU(unsigned long, ioc_count);
 150static struct completion *ioc_gone;
 151static DEFINE_SPINLOCK(ioc_gone_lock);
 152
 153static void as_move_to_dispatch(struct as_data *ad, struct request *rq);
 154static void as_antic_stop(struct as_data *ad);
 155
 156/*
 157 * IO Context helper functions
 158 */
 159
 160/* Called to deallocate the as_io_context */
 161static void free_as_io_context(struct as_io_context *aic)
 162{
 163        kfree(aic);
 164        elv_ioc_count_dec(ioc_count);
 165        if (ioc_gone) {
 166                /*
 167                 * AS scheduler is exiting, grab exit lock and check
 168                 * the pending io context count. If it hits zero,
 169                 * complete ioc_gone and set it back to NULL.
 170                 */
 171                spin_lock(&ioc_gone_lock);
 172                if (ioc_gone && !elv_ioc_count_read(ioc_count)) {
 173                        complete(ioc_gone);
 174                        ioc_gone = NULL;
 175                }
 176                spin_unlock(&ioc_gone_lock);
 177        }
 178}
 179
 180static void as_trim(struct io_context *ioc)
 181{
 182        spin_lock_irq(&ioc->lock);
 183        if (ioc->aic)
 184                free_as_io_context(ioc->aic);
 185        ioc->aic = NULL;
 186        spin_unlock_irq(&ioc->lock);
 187}
 188
 189/* Called when the task exits */
 190static void exit_as_io_context(struct as_io_context *aic)
 191{
 192        WARN_ON(!test_bit(AS_TASK_RUNNING, &aic->state));
 193        clear_bit(AS_TASK_RUNNING, &aic->state);
 194}
 195
 196static struct as_io_context *alloc_as_io_context(void)
 197{
 198        struct as_io_context *ret;
 199
 200        ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
 201        if (ret) {
 202                ret->dtor = free_as_io_context;
 203                ret->exit = exit_as_io_context;
 204                ret->state = 1 << AS_TASK_RUNNING;
 205                atomic_set(&ret->nr_queued, 0);
 206                atomic_set(&ret->nr_dispatched, 0);
 207                spin_lock_init(&ret->lock);
 208                ret->ttime_total = 0;
 209                ret->ttime_samples = 0;
 210                ret->ttime_mean = 0;
 211                ret->seek_total = 0;
 212                ret->seek_samples = 0;
 213                ret->seek_mean = 0;
 214                elv_ioc_count_inc(ioc_count);
 215        }
 216
 217        return ret;
 218}
 219
 220/*
 221 * If the current task has no AS IO context then create one and initialise it.
 222 * Then take a ref on the task's io context and return it.
 223 */
 224static struct io_context *as_get_io_context(int node)
 225{
 226        struct io_context *ioc = get_io_context(GFP_ATOMIC, node);
 227        if (ioc && !ioc->aic) {
 228                ioc->aic = alloc_as_io_context();
 229                if (!ioc->aic) {
 230                        put_io_context(ioc);
 231                        ioc = NULL;
 232                }
 233        }
 234        return ioc;
 235}
 236
 237static void as_put_io_context(struct request *rq)
 238{
 239        struct as_io_context *aic;
 240
 241        if (unlikely(!RQ_IOC(rq)))
 242                return;
 243
 244        aic = RQ_IOC(rq)->aic;
 245
 246        if (rq_is_sync(rq) && aic) {
 247                unsigned long flags;
 248
 249                spin_lock_irqsave(&aic->lock, flags);
 250                set_bit(AS_TASK_IORUNNING, &aic->state);
 251                aic->last_end_request = jiffies;
 252                spin_unlock_irqrestore(&aic->lock, flags);
 253        }
 254
 255        put_io_context(RQ_IOC(rq));
 256}
 257
 258/*
 259 * rb tree support functions
 260 */
 261#define RQ_RB_ROOT(ad, rq)      (&(ad)->sort_list[rq_is_sync((rq))])
 262
 263static void as_add_rq_rb(struct as_data *ad, struct request *rq)
 264{
 265        struct request *alias;
 266
 267        while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(ad, rq), rq)))) {
 268                as_move_to_dispatch(ad, alias);
 269                as_antic_stop(ad);
 270        }
 271}
 272
 273static inline void as_del_rq_rb(struct as_data *ad, struct request *rq)
 274{
 275        elv_rb_del(RQ_RB_ROOT(ad, rq), rq);
 276}
 277
 278/*
 279 * IO Scheduler proper
 280 */
 281
 282#define MAXBACK (1024 * 1024)   /*
 283                                 * Maximum distance the disk will go backward
 284                                 * for a request.
 285                                 */
 286
 287#define BACK_PENALTY    2
 288
 289/*
 290 * as_choose_req selects the preferred one of two requests of the same data_dir
 291 * ignoring time - eg. timeouts, which is the job of as_dispatch_request
 292 */
 293static struct request *
 294as_choose_req(struct as_data *ad, struct request *rq1, struct request *rq2)
 295{
 296        int data_dir;
 297        sector_t last, s1, s2, d1, d2;
 298        int r1_wrap=0, r2_wrap=0;       /* requests are behind the disk head */
 299        const sector_t maxback = MAXBACK;
 300
 301        if (rq1 == NULL || rq1 == rq2)
 302                return rq2;
 303        if (rq2 == NULL)
 304                return rq1;
 305
 306        data_dir = rq_is_sync(rq1);
 307
 308        last = ad->last_sector[data_dir];
 309        s1 = rq1->sector;
 310        s2 = rq2->sector;
 311
 312        BUG_ON(data_dir != rq_is_sync(rq2));
 313
 314        /*
 315         * Strict one way elevator _except_ in the case where we allow
 316         * short backward seeks which are biased as twice the cost of a
 317         * similar forward seek.
 318         */
 319        if (s1 >= last)
 320                d1 = s1 - last;
 321        else if (s1+maxback >= last)
 322                d1 = (last - s1)*BACK_PENALTY;
 323        else {
 324                r1_wrap = 1;
 325                d1 = 0; /* shut up, gcc */
 326        }
 327
 328        if (s2 >= last)
 329                d2 = s2 - last;
 330        else if (s2+maxback >= last)
 331                d2 = (last - s2)*BACK_PENALTY;
 332        else {
 333                r2_wrap = 1;
 334                d2 = 0;
 335        }
 336
 337        /* Found required data */
 338        if (!r1_wrap && r2_wrap)
 339                return rq1;
 340        else if (!r2_wrap && r1_wrap)
 341                return rq2;
 342        else if (r1_wrap && r2_wrap) {
 343                /* both behind the head */
 344                if (s1 <= s2)
 345                        return rq1;
 346                else
 347                        return rq2;
 348        }
 349
 350        /* Both requests in front of the head */
 351        if (d1 < d2)
 352                return rq1;
 353        else if (d2 < d1)
 354                return rq2;
 355        else {
 356                if (s1 >= s2)
 357                        return rq1;
 358                else
 359                        return rq2;
 360        }
 361}
 362
 363/*
 364 * as_find_next_rq finds the next request after @prev in elevator order.
 365 * this with as_choose_req form the basis for how the scheduler chooses
 366 * what request to process next. Anticipation works on top of this.
 367 */
 368static struct request *
 369as_find_next_rq(struct as_data *ad, struct request *last)
 370{
 371        struct rb_node *rbnext = rb_next(&last->rb_node);
 372        struct rb_node *rbprev = rb_prev(&last->rb_node);
 373        struct request *next = NULL, *prev = NULL;
 374
 375        BUG_ON(RB_EMPTY_NODE(&last->rb_node));
 376
 377        if (rbprev)
 378                prev = rb_entry_rq(rbprev);
 379
 380        if (rbnext)
 381                next = rb_entry_rq(rbnext);
 382        else {
 383                const int data_dir = rq_is_sync(last);
 384
 385                rbnext = rb_first(&ad->sort_list[data_dir]);
 386                if (rbnext && rbnext != &last->rb_node)
 387                        next = rb_entry_rq(rbnext);
 388        }
 389
 390        return as_choose_req(ad, next, prev);
 391}
 392
 393/*
 394 * anticipatory scheduling functions follow
 395 */
 396
 397/*
 398 * as_antic_expired tells us when we have anticipated too long.
 399 * The funny "absolute difference" math on the elapsed time is to handle
 400 * jiffy wraps, and disks which have been idle for 0x80000000 jiffies.
 401 */
 402static int as_antic_expired(struct as_data *ad)
 403{
 404        long delta_jif;
 405
 406        delta_jif = jiffies - ad->antic_start;
 407        if (unlikely(delta_jif < 0))
 408                delta_jif = -delta_jif;
 409        if (delta_jif < ad->antic_expire)
 410                return 0;
 411
 412        return 1;
 413}
 414
 415/*
 416 * as_antic_waitnext starts anticipating that a nice request will soon be
 417 * submitted. See also as_antic_waitreq
 418 */
 419static void as_antic_waitnext(struct as_data *ad)
 420{
 421        unsigned long timeout;
 422
 423        BUG_ON(ad->antic_status != ANTIC_OFF
 424                        && ad->antic_status != ANTIC_WAIT_REQ);
 425
 426        timeout = ad->antic_start + ad->antic_expire;
 427
 428        mod_timer(&ad->antic_timer, timeout);
 429
 430        ad->antic_status = ANTIC_WAIT_NEXT;
 431}
 432
 433/*
 434 * as_antic_waitreq starts anticipating. We don't start timing the anticipation
 435 * until the request that we're anticipating on has finished. This means we
 436 * are timing from when the candidate process wakes up hopefully.
 437 */
 438static void as_antic_waitreq(struct as_data *ad)
 439{
 440        BUG_ON(ad->antic_status == ANTIC_FINISHED);
 441        if (ad->antic_status == ANTIC_OFF) {
 442                if (!ad->io_context || ad->ioc_finished)
 443                        as_antic_waitnext(ad);
 444                else
 445                        ad->antic_status = ANTIC_WAIT_REQ;
 446        }
 447}
 448
 449/*
 450 * This is called directly by the functions in this file to stop anticipation.
 451 * We kill the timer and schedule a call to the request_fn asap.
 452 */
 453static void as_antic_stop(struct as_data *ad)
 454{
 455        int status = ad->antic_status;
 456
 457        if (status == ANTIC_WAIT_REQ || status == ANTIC_WAIT_NEXT) {
 458                if (status == ANTIC_WAIT_NEXT)
 459                        del_timer(&ad->antic_timer);
 460                ad->antic_status = ANTIC_FINISHED;
 461                /* see as_work_handler */
 462                kblockd_schedule_work(ad->q, &ad->antic_work);
 463        }
 464}
 465
 466/*
 467 * as_antic_timeout is the timer function set by as_antic_waitnext.
 468 */
 469static void as_antic_timeout(unsigned long data)
 470{
 471        struct request_queue *q = (struct request_queue *)data;
 472        struct as_data *ad = q->elevator->elevator_data;
 473        unsigned long flags;
 474
 475        spin_lock_irqsave(q->queue_lock, flags);
 476        if (ad->antic_status == ANTIC_WAIT_REQ
 477                        || ad->antic_status == ANTIC_WAIT_NEXT) {
 478                struct as_io_context *aic;
 479                spin_lock(&ad->io_context->lock);
 480                aic = ad->io_context->aic;
 481
 482                ad->antic_status = ANTIC_FINISHED;
 483                kblockd_schedule_work(q, &ad->antic_work);
 484
 485                if (aic->ttime_samples == 0) {
 486                        /* process anticipated on has exited or timed out*/
 487                        ad->exit_prob = (7*ad->exit_prob + 256)/8;
 488                }
 489                if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
 490                        /* process not "saved" by a cooperating request */
 491                        ad->exit_no_coop = (7*ad->exit_no_coop + 256)/8;
 492                }
 493                spin_unlock(&ad->io_context->lock);
 494        }
 495        spin_unlock_irqrestore(q->queue_lock, flags);
 496}
 497
 498static void as_update_thinktime(struct as_data *ad, struct as_io_context *aic,
 499                                unsigned long ttime)
 500{
 501        /* fixed point: 1.0 == 1<<8 */
 502        if (aic->ttime_samples == 0) {
 503                ad->new_ttime_total = (7*ad->new_ttime_total + 256*ttime) / 8;
 504                ad->new_ttime_mean = ad->new_ttime_total / 256;
 505
 506                ad->exit_prob = (7*ad->exit_prob)/8;
 507        }
 508        aic->ttime_samples = (7*aic->ttime_samples + 256) / 8;
 509        aic->ttime_total = (7*aic->ttime_total + 256*ttime) / 8;
 510        aic->ttime_mean = (aic->ttime_total + 128) / aic->ttime_samples;
 511}
 512
 513static void as_update_seekdist(struct as_data *ad, struct as_io_context *aic,
 514                                sector_t sdist)
 515{
 516        u64 total;
 517
 518        if (aic->seek_samples == 0) {
 519                ad->new_seek_total = (7*ad->new_seek_total + 256*(u64)sdist)/8;
 520                ad->new_seek_mean = ad->new_seek_total / 256;
 521        }
 522
 523        /*
 524         * Don't allow the seek distance to get too large from the
 525         * odd fragment, pagein, etc
 526         */
 527        if (aic->seek_samples <= 60) /* second&third seek */
 528                sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*1024);
 529        else
 530                sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*64);
 531
 532        aic->seek_samples = (7*aic->seek_samples + 256) / 8;
 533        aic->seek_total = (7*aic->seek_total + (u64)256*sdist) / 8;
 534        total = aic->seek_total + (aic->seek_samples/2);
 535        do_div(total, aic->seek_samples);
 536        aic->seek_mean = (sector_t)total;
 537}
 538
 539/*
 540 * as_update_iohist keeps a decaying histogram of IO thinktimes, and
 541 * updates @aic->ttime_mean based on that. It is called when a new
 542 * request is queued.
 543 */
 544static void as_update_iohist(struct as_data *ad, struct as_io_context *aic,
 545                                struct request *rq)
 546{
 547        int data_dir = rq_is_sync(rq);
 548        unsigned long thinktime = 0;
 549        sector_t seek_dist;
 550
 551        if (aic == NULL)
 552                return;
 553
 554        if (data_dir == BLK_RW_SYNC) {
 555                unsigned long in_flight = atomic_read(&aic->nr_queued)
 556                                        + atomic_read(&aic->nr_dispatched);
 557                spin_lock(&aic->lock);
 558                if (test_bit(AS_TASK_IORUNNING, &aic->state) ||
 559                        test_bit(AS_TASK_IOSTARTED, &aic->state)) {
 560                        /* Calculate read -> read thinktime */
 561                        if (test_bit(AS_TASK_IORUNNING, &aic->state)
 562                                                        && in_flight == 0) {
 563                                thinktime = jiffies - aic->last_end_request;
 564                                thinktime = min(thinktime, MAX_THINKTIME-1);
 565                        }
 566                        as_update_thinktime(ad, aic, thinktime);
 567
 568                        /* Calculate read -> read seek distance */
 569                        if (aic->last_request_pos < rq->sector)
 570                                seek_dist = rq->sector - aic->last_request_pos;
 571                        else
 572                                seek_dist = aic->last_request_pos - rq->sector;
 573                        as_update_seekdist(ad, aic, seek_dist);
 574                }
 575                aic->last_request_pos = rq->sector + rq->nr_sectors;
 576                set_bit(AS_TASK_IOSTARTED, &aic->state);
 577                spin_unlock(&aic->lock);
 578        }
 579}
 580
 581/*
 582 * as_close_req decides if one request is considered "close" to the
 583 * previous one issued.
 584 */
 585static int as_close_req(struct as_data *ad, struct as_io_context *aic,
 586                        struct request *rq)
 587{
 588        unsigned long delay;    /* jiffies */
 589        sector_t last = ad->last_sector[ad->batch_data_dir];
 590        sector_t next = rq->sector;
 591        sector_t delta; /* acceptable close offset (in sectors) */
 592        sector_t s;
 593
 594        if (ad->antic_status == ANTIC_OFF || !ad->ioc_finished)
 595                delay = 0;
 596        else
 597                delay = jiffies - ad->antic_start;
 598
 599        if (delay == 0)
 600                delta = 8192;
 601        else if (delay <= (20 * HZ / 1000) && delay <= ad->antic_expire)
 602                delta = 8192 << delay;
 603        else
 604                return 1;
 605
 606        if ((last <= next + (delta>>1)) && (next <= last + delta))
 607                return 1;
 608
 609        if (last < next)
 610                s = next - last;
 611        else
 612                s = last - next;
 613
 614        if (aic->seek_samples == 0) {
 615                /*
 616                 * Process has just started IO. Use past statistics to
 617                 * gauge success possibility
 618                 */
 619                if (ad->new_seek_mean > s) {
 620                        /* this request is better than what we're expecting */
 621                        return 1;
 622                }
 623
 624        } else {
 625                if (aic->seek_mean > s) {
 626                        /* this request is better than what we're expecting */
 627                        return 1;
 628                }
 629        }
 630
 631        return 0;
 632}
 633
 634/*
 635 * as_can_break_anticipation returns true if we have been anticipating this
 636 * request.
 637 *
 638 * It also returns true if the process against which we are anticipating
 639 * submits a write - that's presumably an fsync, O_SYNC write, etc. We want to
 640 * dispatch it ASAP, because we know that application will not be submitting
 641 * any new reads.
 642 *
 643 * If the task which has submitted the request has exited, break anticipation.
 644 *
 645 * If this task has queued some other IO, do not enter enticipation.
 646 */
 647static int as_can_break_anticipation(struct as_data *ad, struct request *rq)
 648{
 649        struct io_context *ioc;
 650        struct as_io_context *aic;
 651
 652        ioc = ad->io_context;
 653        BUG_ON(!ioc);
 654        spin_lock(&ioc->lock);
 655
 656        if (rq && ioc == RQ_IOC(rq)) {
 657                /* request from same process */
 658                spin_unlock(&ioc->lock);
 659                return 1;
 660        }
 661
 662        if (ad->ioc_finished && as_antic_expired(ad)) {
 663                /*
 664                 * In this situation status should really be FINISHED,
 665                 * however the timer hasn't had the chance to run yet.
 666                 */
 667                spin_unlock(&ioc->lock);
 668                return 1;
 669        }
 670
 671        aic = ioc->aic;
 672        if (!aic) {
 673                spin_unlock(&ioc->lock);
 674                return 0;
 675        }
 676
 677        if (atomic_read(&aic->nr_queued) > 0) {
 678                /* process has more requests queued */
 679                spin_unlock(&ioc->lock);
 680                return 1;
 681        }
 682
 683        if (atomic_read(&aic->nr_dispatched) > 0) {
 684                /* process has more requests dispatched */
 685                spin_unlock(&ioc->lock);
 686                return 1;
 687        }
 688
 689        if (rq && rq_is_sync(rq) && as_close_req(ad, aic, rq)) {
 690                /*
 691                 * Found a close request that is not one of ours.
 692                 *
 693                 * This makes close requests from another process update
 694                 * our IO history. Is generally useful when there are
 695                 * two or more cooperating processes working in the same
 696                 * area.
 697                 */
 698                if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
 699                        if (aic->ttime_samples == 0)
 700                                ad->exit_prob = (7*ad->exit_prob + 256)/8;
 701
 702                        ad->exit_no_coop = (7*ad->exit_no_coop)/8;
 703                }
 704
 705                as_update_iohist(ad, aic, rq);
 706                spin_unlock(&ioc->lock);
 707                return 1;
 708        }
 709
 710        if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
 711                /* process anticipated on has exited */
 712                if (aic->ttime_samples == 0)
 713                        ad->exit_prob = (7*ad->exit_prob + 256)/8;
 714
 715                if (ad->exit_no_coop > 128) {
 716                        spin_unlock(&ioc->lock);
 717                        return 1;
 718                }
 719        }
 720
 721        if (aic->ttime_samples == 0) {
 722                if (ad->new_ttime_mean > ad->antic_expire) {
 723                        spin_unlock(&ioc->lock);
 724                        return 1;
 725                }
 726                if (ad->exit_prob * ad->exit_no_coop > 128*256) {
 727                        spin_unlock(&ioc->lock);
 728                        return 1;
 729                }
 730        } else if (aic->ttime_mean > ad->antic_expire) {
 731                /* the process thinks too much between requests */
 732                spin_unlock(&ioc->lock);
 733                return 1;
 734        }
 735        spin_unlock(&ioc->lock);
 736        return 0;
 737}
 738
 739/*
 740 * as_can_anticipate indicates whether we should either run rq
 741 * or keep anticipating a better request.
 742 */
 743static int as_can_anticipate(struct as_data *ad, struct request *rq)
 744{
 745#if 0 /* disable for now, we need to check tag level as well */
 746        /*
 747         * SSD device without seek penalty, disable idling
 748         */
 749        if (blk_queue_nonrot(ad->q)) axman
 750                return 0;
 751#endif
 752
 753        if (!ad->io_context)
 754                /*
 755                 * Last request submitted was a write
 756                 */
 757                return 0;
 758
 759        if (ad->antic_status == ANTIC_FINISHED)
 760                /*
 761                 * Don't restart if we have just finished. Run the next request
 762                 */
 763                return 0;
 764
 765        if (as_can_break_anticipation(ad, rq))
 766                /*
 767                 * This request is a good candidate. Don't keep anticipating,
 768                 * run it.
 769                 */
 770                return 0;
 771
 772        /*
 773         * OK from here, we haven't finished, and don't have a decent request!
 774         * Status is either ANTIC_OFF so start waiting,
 775         * ANTIC_WAIT_REQ so continue waiting for request to finish
 776         * or ANTIC_WAIT_NEXT so continue waiting for an acceptable request.
 777         */
 778
 779        return 1;
 780}
 781
 782/*
 783 * as_update_rq must be called whenever a request (rq) is added to
 784 * the sort_list. This function keeps caches up to date, and checks if the
 785 * request might be one we are "anticipating"
 786 */
 787static void as_update_rq(struct as_data *ad, struct request *rq)
 788{
 789        const int data_dir = rq_is_sync(rq);
 790
 791        /* keep the next_rq cache up to date */
 792        ad->next_rq[data_dir] = as_choose_req(ad, rq, ad->next_rq[data_dir]);
 793
 794        /*
 795         * have we been anticipating this request?
 796         * or does it come from the same process as the one we are anticipating
 797         * for?
 798         */
 799        if (ad->antic_status == ANTIC_WAIT_REQ
 800                        || ad->antic_status == ANTIC_WAIT_NEXT) {
 801                if (as_can_break_anticipation(ad, rq))
 802                        as_antic_stop(ad);
 803        }
 804}
 805
 806/*
 807 * Gathers timings and resizes the write batch automatically
 808 */
 809static void update_write_batch(struct as_data *ad)
 810{
 811        unsigned long batch = ad->batch_expire[BLK_RW_ASYNC];
 812        long write_time;
 813
 814        write_time = (jiffies - ad->current_batch_expires) + batch;
 815        if (write_time < 0)
 816                write_time = 0;
 817
 818        if (write_time > batch && !ad->write_batch_idled) {
 819                if (write_time > batch * 3)
 820                        ad->write_batch_count /= 2;
 821                else
 822                        ad->write_batch_count--;
 823        } else if (write_time < batch && ad->current_write_count == 0) {
 824                if (batch > write_time * 3)
 825                        ad->write_batch_count *= 2;
 826                else
 827                        ad->write_batch_count++;
 828        }
 829
 830        if (ad->write_batch_count < 1)
 831                ad->write_batch_count = 1;
 832}
 833
 834/*
 835 * as_completed_request is to be called when a request has completed and
 836 * returned something to the requesting process, be it an error or data.
 837 */
 838static void as_completed_request(struct request_queue *q, struct request *rq)
 839{
 840        struct as_data *ad = q->elevator->elevator_data;
 841
 842        WARN_ON(!list_empty(&rq->queuelist));
 843
 844        if (RQ_STATE(rq) != AS_RQ_REMOVED) {
 845                WARN(1, "rq->state %d\n", RQ_STATE(rq));
 846                goto out;
 847        }
 848
 849        if (ad->changed_batch && ad->nr_dispatched == 1) {
 850                ad->current_batch_expires = jiffies +
 851                                        ad->batch_expire[ad->batch_data_dir];
 852                kblockd_schedule_work(q, &ad->antic_work);
 853                ad->changed_batch = 0;
 854
 855                if (ad->batch_data_dir == BLK_RW_SYNC)
 856                        ad->new_batch = 1;
 857        }
 858        WARN_ON(ad->nr_dispatched == 0);
 859        ad->nr_dispatched--;
 860
 861        /*
 862         * Start counting the batch from when a request of that direction is
 863         * actually serviced. This should help devices with big TCQ windows
 864         * and writeback caches
 865         */
 866        if (ad->new_batch && ad->batch_data_dir == rq_is_sync(rq)) {
 867                update_write_batch(ad);
 868                ad->current_batch_expires = jiffies +
 869                                ad->batch_expire[BLK_RW_SYNC];
 870                ad->new_batch = 0;
 871        }
 872
 873        if (ad->io_context == RQ_IOC(rq) && ad->io_context) {
 874                ad->antic_start = jiffies;
 875                ad->ioc_finished = 1;
 876                if (ad->antic_status == ANTIC_WAIT_REQ) {
 877                        /*
 878                         * We were waiting on this request, now anticipate
 879                         * the next one
 880                         */
 881                        as_antic_waitnext(ad);
 882                }
 883        }
 884
 885        as_put_io_context(rq);
 886out:
 887        RQ_SET_STATE(rq, AS_RQ_POSTSCHED);
 888}
 889
 890/*
 891 * as_remove_queued_request removes a request from the pre dispatch queue
 892 * without updating refcounts. It is expected the caller will drop the
 893 * reference unless it replaces the request at somepart of the elevator
 894 * (ie. the dispatch queue)
 895 */
 896static void as_remove_queued_request(struct request_queue *q,
 897                                     struct request *rq)
 898{
 899        const int data_dir = rq_is_sync(rq);
 900        struct as_data *ad = q->elevator->elevator_data;
 901        struct io_context *ioc;
 902
 903        WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);
 904
 905        ioc = RQ_IOC(rq);
 906        if (ioc && ioc->aic) {
 907                BUG_ON(!atomic_read(&ioc->aic->nr_queued));
 908                atomic_dec(&ioc->aic->nr_queued);
 909        }
 910
 911        /*
 912         * Update the "next_rq" cache if we are about to remove its
 913         * entry
 914         */
 915        if (ad->next_rq[data_dir] == rq)
 916                ad->next_rq[data_dir] = as_find_next_rq(ad, rq);
 917
 918        rq_fifo_clear(rq);
 919        as_del_rq_rb(ad, rq);
 920}
 921
 922/*
 923 * as_fifo_expired returns 0 if there are no expired requests on the fifo,
 924 * 1 otherwise.  It is ratelimited so that we only perform the check once per
 925 * `fifo_expire' interval.  Otherwise a large number of expired requests
 926 * would create a hopeless seekstorm.
 927 *
 928 * See as_antic_expired comment.
 929 */
 930static int as_fifo_expired(struct as_data *ad, int adir)
 931{
 932        struct request *rq;
 933        long delta_jif;
 934
 935        delta_jif = jiffies - ad->last_check_fifo[adir];
 936        if (unlikely(delta_jif < 0))
 937                delta_jif = -delta_jif;
 938        if (delta_jif < ad->fifo_expire[adir])
 939                return 0;
 940
 941        ad->last_check_fifo[adir] = jiffies;
 942
 943        if (list_empty(&ad->fifo_list[adir]))
 944                return 0;
 945
 946        rq = rq_entry_fifo(ad->fifo_list[adir].next);
 947
 948        return time_after(jiffies, rq_fifo_time(rq));
 949}
 950
 951/*
 952 * as_batch_expired returns true if the current batch has expired. A batch
 953 * is a set of reads or a set of writes.
 954 */
 955static inline int as_batch_expired(struct as_data *ad)
 956{
 957        if (ad->changed_batch || ad->new_batch)
 958                return 0;
 959
 960        if (ad->batch_data_dir == BLK_RW_SYNC)
 961                /* TODO! add a check so a complete fifo gets written? */
 962                return time_after(jiffies, ad->current_batch_expires);
 963
 964        return time_after(jiffies, ad->current_batch_expires)
 965                || ad->current_write_count == 0;
 966}
 967
 968/*
 969 * move an entry to dispatch queue
 970 */
 971static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
 972{
 973        const int data_dir = rq_is_sync(rq);
 974
 975        BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
 976
 977        as_antic_stop(ad);
 978        ad->antic_status = ANTIC_OFF;
 979
 980        /*
 981         * This has to be set in order to be correctly updated by
 982         * as_find_next_rq
 983         */
 984        ad->last_sector[data_dir] = rq->sector + rq->nr_sectors;
 985
 986        if (data_dir == BLK_RW_SYNC) {
 987                struct io_context *ioc = RQ_IOC(rq);
 988                /* In case we have to anticipate after this */
 989                copy_io_context(&ad->io_context, &ioc);
 990        } else {
 991                if (ad->io_context) {
 992                        put_io_context(ad->io_context);
 993                        ad->io_context = NULL;
 994                }
 995
 996                if (ad->current_write_count != 0)
 997                        ad->current_write_count--;
 998        }
 999        ad->ioc_finished = 0;
1000
1001        ad->next_rq[data_dir] = as_find_next_rq(ad, rq);
1002
1003        /*
1004         * take it off the sort and fifo list, add to dispatch queue
1005         */
1006        as_remove_queued_request(ad->q, rq);
1007        WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);
1008
1009        elv_dispatch_sort(ad->q, rq);
1010
1011        RQ_SET_STATE(rq, AS_RQ_DISPATCHED);
1012        if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
1013                atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
1014        ad->nr_dispatched++;
1015}
1016
1017/*
1018 * as_dispatch_request selects the best request according to
1019 * read/write expire, batch expire, etc, and moves it to the dispatch
1020 * queue. Returns 1 if a request was found, 0 otherwise.
1021 */
1022static int as_dispatch_request(struct request_queue *q, int force)
1023{
1024        struct as_data *ad = q->elevator->elevator_data;
1025        const int reads = !list_empty(&ad->fifo_list[BLK_RW_SYNC]);
1026        const int writes = !list_empty(&ad->fifo_list[BLK_RW_ASYNC]);
1027        struct request *rq;
1028
1029        if (unlikely(force)) {
1030                /*
1031                 * Forced dispatch, accounting is useless.  Reset
1032                 * accounting states and dump fifo_lists.  Note that
1033                 * batch_data_dir is reset to BLK_RW_SYNC to avoid
1034                 * screwing write batch accounting as write batch
1035                 * accounting occurs on W->R transition.
1036                 */
1037                int dispatched = 0;
1038
1039                ad->batch_data_dir = BLK_RW_SYNC;
1040                ad->changed_batch = 0;
1041                ad->new_batch = 0;
1042
1043                while (ad->next_rq[BLK_RW_SYNC]) {
1044                        as_move_to_dispatch(ad, ad->next_rq[BLK_RW_SYNC]);
1045                        dispatched++;
1046                }
1047                ad->last_check_fifo[BLK_RW_SYNC] = jiffies;
1048
1049                while (ad->next_rq[BLK_RW_ASYNC]) {
1050                        as_move_to_dispatch(ad, ad->next_rq[BLK_RW_ASYNC]);
1051                        dispatched++;
1052                }
1053                ad->last_check_fifo[BLK_RW_ASYNC] = jiffies;
1054
1055                return dispatched;
1056        }
1057
1058        /* Signal that the write batch was uncontended, so we can't time it */
1059        if (ad->batch_data_dir == BLK_RW_ASYNC && !reads) {
1060                if (ad->current_write_count == 0 || !writes)
1061                        ad->write_batch_idled = 1;
1062        }
1063
1064        if (!(reads || writes)
1065                || ad->antic_status == ANTIC_WAIT_REQ
1066                || ad->antic_status == ANTIC_WAIT_NEXT
1067                || ad->changed_batch)
1068                return 0;
1069
1070        if (!(reads && writes && as_batch_expired(ad))) {
1071                /*
1072                 * batch is still running or no reads or no writes
1073                 */
1074                rq = ad->next_rq[ad->batch_data_dir];
1075
1076                if (ad->batch_data_dir == BLK_RW_SYNC && ad->antic_expire) {
1077                        if (as_fifo_expired(ad, BLK_RW_SYNC))
1078                                goto fifo_expired;
1079
1080                        if (as_can_anticipate(ad, rq)) {
1081                                as_antic_waitreq(ad);
1082                                return 0;
1083                        }
1084                }
1085
1086                if (rq) {
1087                        /* we have a "next request" */
1088                        if (reads && !writes)
1089                                ad->current_batch_expires =
1090                                        jiffies + ad->batch_expire[BLK_RW_SYNC];
1091                        goto dispatch_request;
1092                }
1093        }
1094
1095        /*
1096         * at this point we are not running a batch. select the appropriate
1097         * data direction (read / write)
1098         */
1099
1100        if (reads) {
1101                BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[BLK_RW_SYNC]));
1102
1103                if (writes && ad->batch_data_dir == BLK_RW_SYNC)
1104                        /*
1105                         * Last batch was a read, switch to writes
1106                         */
1107                        goto dispatch_writes;
1108
1109                if (ad->batch_data_dir == BLK_RW_ASYNC) {
1110                        WARN_ON(ad->new_batch);
1111                        ad->changed_batch = 1;
1112                }
1113                ad->batch_data_dir = BLK_RW_SYNC;
1114                rq = rq_entry_fifo(ad->fifo_list[BLK_RW_SYNC].next);
1115                ad->last_check_fifo[ad->batch_data_dir] = jiffies;
1116                goto dispatch_request;
1117        }
1118
1119        /*
1120         * the last batch was a read
1121         */
1122
1123        if (writes) {
1124dispatch_writes:
1125                BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[BLK_RW_ASYNC]));
1126
1127                if (ad->batch_data_dir == BLK_RW_SYNC) {
1128                        ad->changed_batch = 1;
1129
1130                        /*
1131                         * new_batch might be 1 when the queue runs out of
1132                         * reads. A subsequent submission of a write might
1133                         * cause a change of batch before the read is finished.
1134                         */
1135                        ad->new_batch = 0;
1136                }
1137                ad->batch_data_dir = BLK_RW_ASYNC;
1138                ad->current_write_count = ad->write_batch_count;
1139                ad->write_batch_idled = 0;
1140                rq = rq_entry_fifo(ad->fifo_list[BLK_RW_ASYNC].next);
1141                ad->last_check_fifo[BLK_RW_ASYNC] = jiffies;
1142                goto dispatch_request;
1143        }
1144
1145        BUG();
1146        return 0;
1147
1148dispatch_request:
1149        /*
1150         * If a request has expired, service it.
1151         */
1152
1153        if (as_fifo_expired(ad, ad->batch_data_dir)) {
1154fifo_expired:
1155                rq = rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
1156        }
1157
1158        if (ad->changed_batch) {
1159                WARN_ON(ad->new_batch);
1160
1161                if (ad->nr_dispatched)
1162                        return 0;
1163
1164                if (ad->batch_data_dir == BLK_RW_ASYNC)
1165                        ad->current_batch_expires = jiffies +
1166                                        ad->batch_expire[BLK_RW_ASYNC];
1167                else
1168                        ad->new_batch = 1;
1169
1170                ad->changed_batch = 0;
1171        }
1172
1173        /*
1174         * rq is the selected appropriate request.
1175         */
1176        as_move_to_dispatch(ad, rq);
1177
1178        return 1;
1179}
1180
1181/*
1182 * add rq to rbtree and fifo
1183 */
1184static void as_add_request(struct request_queue *q, struct request *rq)
1185{
1186        struct as_data *ad = q->elevator->elevator_data;
1187        int data_dir;
1188
1189        RQ_SET_STATE(rq, AS_RQ_NEW);
1190
1191        data_dir = rq_is_sync(rq);
1192
1193        rq->elevator_private = as_get_io_context(q->node);
1194
1195        if (RQ_IOC(rq)) {
1196                as_update_iohist(ad, RQ_IOC(rq)->aic, rq);
1197                atomic_inc(&RQ_IOC(rq)->aic->nr_queued);
1198        }
1199
1200        as_add_rq_rb(ad, rq);
1201
1202        /*
1203         * set expire time and add to fifo list
1204         */
1205        rq_set_fifo_time(rq, jiffies + ad->fifo_expire[data_dir]);
1206        list_add_tail(&rq->queuelist, &ad->fifo_list[data_dir]);
1207
1208        as_update_rq(ad, rq); /* keep state machine up to date */
1209        RQ_SET_STATE(rq, AS_RQ_QUEUED);
1210}
1211
1212static void as_activate_request(struct request_queue *q, struct request *rq)
1213{
1214        WARN_ON(RQ_STATE(rq) != AS_RQ_DISPATCHED);
1215        RQ_SET_STATE(rq, AS_RQ_REMOVED);
1216        if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
1217                atomic_dec(&RQ_IOC(rq)->aic->nr_dispatched);
1218}
1219
1220static void as_deactivate_request(struct request_queue *q, struct request *rq)
1221{
1222        WARN_ON(RQ_STATE(rq) != AS_RQ_REMOVED);
1223        RQ_SET_STATE(rq, AS_RQ_DISPATCHED);
1224        if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
1225                atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
1226}
1227
1228/*
1229 * as_queue_empty tells us if there are requests left in the device. It may
1230 * not be the case that a driver can get the next request even if the queue
1231 * is not empty - it is used in the block layer to check for plugging and
1232 * merging opportunities
1233 */
1234static int as_queue_empty(struct request_queue *q)
1235{
1236        struct as_data *ad = q->elevator->elevator_data;
1237
1238        return list_empty(&ad->fifo_list[BLK_RW_ASYNC])
1239                && list_empty(&ad->fifo_list[BLK_RW_SYNC]);
1240}
1241
1242static int
1243as_merge(struct request_queue *q, struct request **req, struct bio *bio)
1244{
1245        struct as_data *ad = q->elevator->elevator_data;
1246        sector_t rb_key = bio->bi_sector + bio_sectors(bio);
1247        struct request *__rq;
1248
1249        /*
1250         * check for front merge
1251         */
1252        __rq = elv_rb_find(&ad->sort_list[bio_data_dir(bio)], rb_key);
1253        if (__rq && elv_rq_merge_ok(__rq, bio)) {
1254                *req = __rq;
1255                return ELEVATOR_FRONT_MERGE;
1256        }
1257
1258        return ELEVATOR_NO_MERGE;
1259}
1260
1261static void as_merged_request(struct request_queue *q, struct request *req,
1262                              int type)
1263{
1264        struct as_data *ad = q->elevator->elevator_data;
1265
1266        /*
1267         * if the merge was a front merge, we need to reposition request
1268         */
1269        if (type == ELEVATOR_FRONT_MERGE) {
1270                as_del_rq_rb(ad, req);
1271                as_add_rq_rb(ad, req);
1272                /*
1273                 * Note! At this stage of this and the next function, our next
1274                 * request may not be optimal - eg the request may have "grown"
1275                 * behind the disk head. We currently don't bother adjusting.
1276                 */
1277        }
1278}
1279
1280static void as_merged_requests(struct request_queue *q, struct request *req,
1281                                struct request *next)
1282{
1283        /*
1284         * if next expires before rq, assign its expire time to arq
1285         * and move into next position (next will be deleted) in fifo
1286         */
1287        if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
1288                if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
1289                        list_move(&req->queuelist, &next->queuelist);
1290                        rq_set_fifo_time(req, rq_fifo_time(next));
1291                }
1292        }
1293
1294        /*
1295         * kill knowledge of next, this one is a goner
1296         */
1297        as_remove_queued_request(q, next);
1298        as_put_io_context(next);
1299
1300        RQ_SET_STATE(next, AS_RQ_MERGED);
1301}
1302
1303/*
1304 * This is executed in a "deferred" process context, by kblockd. It calls the
1305 * driver's request_fn so the driver can submit that request.
1306 *
1307 * IMPORTANT! This guy will reenter the elevator, so set up all queue global
1308 * state before calling, and don't rely on any state over calls.
1309 *
1310 * FIXME! dispatch queue is not a queue at all!
1311 */
1312static void as_work_handler(struct work_struct *work)
1313{
1314        struct as_data *ad = container_of(work, struct as_data, antic_work);
1315        struct request_queue *q = ad->q;
1316        unsigned long flags;
1317
1318        spin_lock_irqsave(q->queue_lock, flags);
1319        blk_start_queueing(q);
1320        spin_unlock_irqrestore(q->queue_lock, flags);
1321}
1322
1323static int as_may_queue(struct request_queue *q, int rw)
1324{
1325        int ret = ELV_MQUEUE_MAY;
1326        struct as_data *ad = q->elevator->elevator_data;
1327        struct io_context *ioc;
1328        if (ad->antic_status == ANTIC_WAIT_REQ ||
1329                        ad->antic_status == ANTIC_WAIT_NEXT) {
1330                ioc = as_get_io_context(q->node);
1331                if (ad->io_context == ioc)
1332                        ret = ELV_MQUEUE_MUST;
1333                put_io_context(ioc);
1334        }
1335
1336        return ret;
1337}
1338
1339static void as_exit_queue(struct elevator_queue *e)
1340{
1341        struct as_data *ad = e->elevator_data;
1342
1343        del_timer_sync(&ad->antic_timer);
1344        cancel_work_sync(&ad->antic_work);
1345
1346        BUG_ON(!list_empty(&ad->fifo_list[BLK_RW_SYNC]));
1347        BUG_ON(!list_empty(&ad->fifo_list[BLK_RW_ASYNC]));
1348
1349        put_io_context(ad->io_context);
1350        kfree(ad);
1351}
1352
1353/*
1354 * initialize elevator private data (as_data).
1355 */
1356static void *as_init_queue(struct request_queue *q)
1357{
1358        struct as_data *ad;
1359
1360        ad = kmalloc_node(sizeof(*ad), GFP_KERNEL | __GFP_ZERO, q->node);
1361        if (!ad)
1362                return NULL;
1363
1364        ad->q = q; /* Identify what queue the data belongs to */
1365
1366        /* anticipatory scheduling helpers */
1367        ad->antic_timer.function = as_antic_timeout;
1368        ad->antic_timer.data = (unsigned long)q;
1369        init_timer(&ad->antic_timer);
1370        INIT_WORK(&ad->antic_work, as_work_handler);
1371
1372        INIT_LIST_HEAD(&ad->fifo_list[BLK_RW_SYNC]);
1373        INIT_LIST_HEAD(&ad->fifo_list[BLK_RW_ASYNC]);
1374        ad->sort_list[BLK_RW_SYNC] = RB_ROOT;
1375        ad->sort_list[BLK_RW_ASYNC] = RB_ROOT;
1376        ad->fifo_expire[BLK_RW_SYNC] = default_read_expire;
1377        ad->fifo_expire[BLK_RW_ASYNC] = default_write_expire;
1378        ad->antic_expire = default_antic_expire;
1379        ad->batch_expire[BLK_RW_SYNC] = default_read_batch_expire;
1380        ad->batch_expire[BLK_RW_ASYNC] = default_write_batch_expire;
1381
1382        ad->current_batch_expires = jiffies + ad->batch_expire[BLK_RW_SYNC];
1383        ad->write_batch_count = ad->batch_expire[BLK_RW_ASYNC] / 10;
1384        if (ad->write_batch_count < 2)
1385                ad->write_batch_count = 2;
1386
1387        return ad;
1388}
1389
1390/*
1391 * sysfs parts below
1392 */
1393
1394static ssize_t
1395as_var_show(unsigned int var, char *page)
1396{
1397        return sprintf(page, "%d\n", var);
1398}
1399
1400static ssize_t
1401as_var_store(unsigned long *var, const char *page, size_t count)
1402{
1403        char *p = (char *) page;
1404
1405        *var = simple_strtoul(p, &p, 10);
1406        return count;
1407}
1408
1409static ssize_t est_time_show(struct elevator_queue *e, char *page)
1410{
1411        struct as_data *ad = e->elevator_data;
1412        int pos = 0;
1413
1414        pos += sprintf(page+pos, "%lu %% exit probability\n",
1415                                100*ad->exit_prob/256);
1416        pos += sprintf(page+pos, "%lu %% probability of exiting without a "
1417                                "cooperating process submitting IO\n",
1418                                100*ad->exit_no_coop/256);
1419        pos += sprintf(page+pos, "%lu ms new thinktime\n", ad->new_ttime_mean);
1420        pos += sprintf(page+pos, "%llu sectors new seek distance\n",
1421                                (unsigned long long)ad->new_seek_mean);
1422
1423        return pos;
1424}
1425
1426#define SHOW_FUNCTION(__FUNC, __VAR)                            \
1427static ssize_t __FUNC(struct elevator_queue *e, char *page)     \
1428{                                                               \
1429        struct as_data *ad = e->elevator_data;                  \
1430        return as_var_show(jiffies_to_msecs((__VAR)), (page));  \
1431}
1432SHOW_FUNCTION(as_read_expire_show, ad->fifo_expire[BLK_RW_SYNC]);
1433SHOW_FUNCTION(as_write_expire_show, ad->fifo_expire[BLK_RW_ASYNC]);
1434SHOW_FUNCTION(as_antic_expire_show, ad->antic_expire);
1435SHOW_FUNCTION(as_read_batch_expire_show, ad->batch_expire[BLK_RW_SYNC]);
1436SHOW_FUNCTION(as_write_batch_expire_show, ad->batch_expire[BLK_RW_ASYNC]);
1437#undef SHOW_FUNCTION
1438
1439#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX)                         \
1440static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
1441{                                                                       \
1442        struct as_data *ad = e->elevator_data;                          \
1443        int ret = as_var_store(__PTR, (page), count);                   \
1444        if (*(__PTR) < (MIN))                                           \
1445                *(__PTR) = (MIN);                                       \
1446        else if (*(__PTR) > (MAX))                                      \
1447                *(__PTR) = (MAX);                                       \
1448        *(__PTR) = msecs_to_jiffies(*(__PTR));                          \
1449        return ret;                                                     \
1450}
1451STORE_FUNCTION(as_read_expire_store, &ad->fifo_expire[BLK_RW_SYNC], 0, INT_MAX);
1452STORE_FUNCTION(as_write_expire_store,
1453                        &ad->fifo_expire[BLK_RW_ASYNC], 0, INT_MAX);
1454STORE_FUNCTION(as_antic_expire_store, &ad->antic_expire, 0, INT_MAX);
1455STORE_FUNCTION(as_read_batch_expire_store,
1456                        &ad->batch_expire[BLK_RW_SYNC], 0, INT_MAX);
1457STORE_FUNCTION(as_write_batch_expire_store,
1458                        &ad->batch_expire[BLK_RW_ASYNC], 0, INT_MAX);
1459#undef STORE_FUNCTION
1460
1461#define AS_ATTR(name) \
1462        __ATTR(name, S_IRUGO|S_IWUSR, as_##name##_show, as_##name##_store)
1463
1464static struct elv_fs_entry as_attrs[] = {
1465        __ATTR_RO(est_time),
1466        AS_ATTR(read_expire),
1467        AS_ATTR(write_expire),
1468        AS_ATTR(antic_expire),
1469        AS_ATTR(read_batch_expire),
1470        AS_ATTR(write_batch_expire),
1471        __ATTR_NULL
1472};
1473
1474static struct elevator_type iosched_as = {
1475        .ops = {
1476                .elevator_merge_fn =            as_merge,
1477                .elevator_merged_fn =           as_merged_request,
1478                .elevator_merge_req_fn =        as_merged_requests,
1479                .elevator_dispatch_fn =         as_dispatch_request,
1480                .elevator_add_req_fn =          as_add_request,
1481                .elevator_activate_req_fn =     as_activate_request,
1482                .elevator_deactivate_req_fn =   as_deactivate_request,
1483                .elevator_queue_empty_fn =      as_queue_empty,
1484                .elevator_completed_req_fn =    as_completed_request,
1485                .elevator_former_req_fn =       elv_rb_former_request,
1486                .elevator_latter_req_fn =       elv_rb_latter_request,
1487                .elevator_may_queue_fn =        as_may_queue,
1488                .elevator_init_fn =             as_init_queue,
1489                .elevator_exit_fn =             as_exit_queue,
1490                .trim =                         as_trim,
1491        },
1492
1493        .elevator_attrs = as_attrs,
1494        .elevator_name = "anticipatory",
1495        .elevator_owner = THIS_MODULE,
1496};
1497
1498static int __init as_init(void)
1499{
1500        elv_register(&iosched_as);
1501
1502        return 0;
1503}
1504
1505static void __exit as_exit(void)
1506{
1507        DECLARE_COMPLETION_ONSTACK(all_gone);
1508        elv_unregister(&iosched_as);
1509        ioc_gone = &all_gone;
1510        /* ioc_gone's update must be visible before reading ioc_count */
1511        smp_wmb();
1512        if (elv_ioc_count_read(ioc_count))
1513                wait_for_completion(&all_gone);
1514        synchronize_rcu();
1515}
1516
1517module_init(as_init);
1518module_exit(as_exit);
1519
1520MODULE_AUTHOR("Nick Piggin");
1521MODULE_LICENSE("GPL");
1522MODULE_DESCRIPTION("anticipatory IO scheduler");
1523