2 * Anticipatory & deadline i/o scheduler.
4 * Copyright (C) 2002 Jens Axboe <axboe@suse.de>
5 * Nick Piggin <nickpiggin@yahoo.com.au>
8 #include <linux/kernel.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>
24 * See Documentation/block/as-iosched.txt
28 * max time before a read is submitted.
30 #define default_read_expire (HZ / 8)
33 * ditto for writes, these limits are not hard, even
34 * if the disk is capable of satisfying them.
36 #define default_write_expire (HZ / 4)
39 * read_batch_expire describes how long we will allow a stream of reads to
40 * persist before looking to see whether it is time to switch over to writes.
42 #define default_read_batch_expire (HZ / 2)
45 * write_batch_expire describes how long we want a stream of writes to run for.
46 * This is not a hard limit, but a target we set for the auto-tuning thingy.
47 * See, the problem is: we can send a lot of writes to disk cache / TCQ in
48 * a short amount of time...
50 #define default_write_batch_expire (HZ / 8)
53 * max time we may wait to anticipate a read (default around 6ms)
55 #define default_antic_expire ((HZ / 150) ? HZ / 150 : 1)
58 * Keep track of up to 20ms thinktimes. We can go as big as we like here,
59 * however huge values tend to interfere and not decay fast enough. A program
60 * might be in a non-io phase of operation. Waiting on user input for example,
61 * or doing a lengthy computation. A small penalty can be justified there, and
62 * will still catch out those processes that constantly have large thinktimes.
64 #define MAX_THINKTIME (HZ/50UL)
66 /* Bits in as_io_context.state */
68 AS_TASK_RUNNING=0, /* Process has not exited */
69 AS_TASK_IOSTARTED, /* Process has started some IO */
70 AS_TASK_IORUNNING, /* Process has completed some IO */
73 enum anticipation_status {
74 ANTIC_OFF=0, /* Not anticipating (normal operation) */
75 ANTIC_WAIT_REQ, /* The last read has not yet completed */
76 ANTIC_WAIT_NEXT, /* Currently anticipating a request vs
77 last read (which has completed) */
78 ANTIC_FINISHED, /* Anticipating but have found a candidate
87 struct request_queue *q; /* the "owner" queue */
90 * requests (as_rq s) are present on both sort_list and fifo_list
92 struct rb_root sort_list[2];
93 struct list_head fifo_list[2];
95 struct as_rq *next_arq[2]; /* next in sort order */
96 sector_t last_sector[2]; /* last REQ_SYNC & REQ_ASYNC sectors */
98 unsigned long exit_prob; /* probability a task will exit while
100 unsigned long exit_no_coop; /* probablility an exited task will
101 not be part of a later cooperating
103 unsigned long new_ttime_total; /* mean thinktime on new proc */
104 unsigned long new_ttime_mean;
105 u64 new_seek_total; /* mean seek on new proc */
106 sector_t new_seek_mean;
108 unsigned long current_batch_expires;
109 unsigned long last_check_fifo[2];
110 int changed_batch; /* 1: waiting for old batch to end */
111 int new_batch; /* 1: waiting on first read complete */
112 int batch_data_dir; /* current batch REQ_SYNC / REQ_ASYNC */
113 int write_batch_count; /* max # of reqs in a write batch */
114 int current_write_count; /* how many requests left this batch */
115 int write_batch_idled; /* has the write batch gone idle? */
118 enum anticipation_status antic_status;
119 unsigned long antic_start; /* jiffies: when it started */
120 struct timer_list antic_timer; /* anticipatory scheduling timer */
121 struct work_struct antic_work; /* Deferred unplugging */
122 struct io_context *io_context; /* Identify the expected process */
123 int ioc_finished; /* IO associated with io_context is finished */
127 * settings that change how the i/o scheduler behaves
129 unsigned long fifo_expire[2];
130 unsigned long batch_expire[2];
131 unsigned long antic_expire;
138 AS_RQ_NEW=0, /* New - not referenced and not on any lists */
139 AS_RQ_QUEUED, /* In the request queue. It belongs to the
141 AS_RQ_DISPATCHED, /* On the dispatch list. It belongs to the
143 AS_RQ_PRESCHED, /* Debug poisoning for requests being used */
146 AS_RQ_POSTSCHED, /* when they shouldn't be */
150 struct request *request;
152 struct io_context *io_context; /* The submitting task */
154 enum arq_state state;
157 #define RQ_DATA(rq) ((struct as_rq *) (rq)->elevator_private)
159 static kmem_cache_t *arq_pool;
161 static atomic_t ioc_count = ATOMIC_INIT(0);
162 static struct completion *ioc_gone;
164 static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq);
165 static void as_antic_stop(struct as_data *ad);
168 * IO Context helper functions
171 /* Called to deallocate the as_io_context */
172 static void free_as_io_context(struct as_io_context *aic)
175 if (atomic_dec_and_test(&ioc_count) && ioc_gone)
179 static void as_trim(struct io_context *ioc)
182 free_as_io_context(ioc->aic);
186 /* Called when the task exits */
187 static void exit_as_io_context(struct as_io_context *aic)
189 WARN_ON(!test_bit(AS_TASK_RUNNING, &aic->state));
190 clear_bit(AS_TASK_RUNNING, &aic->state);
193 static struct as_io_context *alloc_as_io_context(void)
195 struct as_io_context *ret;
197 ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
199 ret->dtor = free_as_io_context;
200 ret->exit = exit_as_io_context;
201 ret->state = 1 << AS_TASK_RUNNING;
202 atomic_set(&ret->nr_queued, 0);
203 atomic_set(&ret->nr_dispatched, 0);
204 spin_lock_init(&ret->lock);
205 ret->ttime_total = 0;
206 ret->ttime_samples = 0;
209 ret->seek_samples = 0;
211 atomic_inc(&ioc_count);
218 * If the current task has no AS IO context then create one and initialise it.
219 * Then take a ref on the task's io context and return it.
221 static struct io_context *as_get_io_context(void)
223 struct io_context *ioc = get_io_context(GFP_ATOMIC);
224 if (ioc && !ioc->aic) {
225 ioc->aic = alloc_as_io_context();
234 static void as_put_io_context(struct as_rq *arq)
236 struct as_io_context *aic;
238 if (unlikely(!arq->io_context))
241 aic = arq->io_context->aic;
243 if (rq_is_sync(arq->request) && aic) {
244 spin_lock(&aic->lock);
245 set_bit(AS_TASK_IORUNNING, &aic->state);
246 aic->last_end_request = jiffies;
247 spin_unlock(&aic->lock);
250 put_io_context(arq->io_context);
254 * rb tree support functions
256 #define RQ_RB_ROOT(ad, rq) (&(ad)->sort_list[rq_is_sync((rq))])
258 static void as_add_arq_rb(struct as_data *ad, struct request *rq)
260 struct request *alias;
262 while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(ad, rq), rq)))) {
263 as_move_to_dispatch(ad, RQ_DATA(alias));
268 static inline void as_del_arq_rb(struct as_data *ad, struct request *rq)
270 elv_rb_del(RQ_RB_ROOT(ad, rq), rq);
274 * IO Scheduler proper
277 #define MAXBACK (1024 * 1024) /*
278 * Maximum distance the disk will go backward
282 #define BACK_PENALTY 2
285 * as_choose_req selects the preferred one of two requests of the same data_dir
286 * ignoring time - eg. timeouts, which is the job of as_dispatch_request
288 static struct as_rq *
289 as_choose_req(struct as_data *ad, struct as_rq *arq1, struct as_rq *arq2)
292 sector_t last, s1, s2, d1, d2;
293 int r1_wrap=0, r2_wrap=0; /* requests are behind the disk head */
294 const sector_t maxback = MAXBACK;
296 if (arq1 == NULL || arq1 == arq2)
301 data_dir = rq_is_sync(arq1->request);
303 last = ad->last_sector[data_dir];
304 s1 = arq1->request->sector;
305 s2 = arq2->request->sector;
307 BUG_ON(data_dir != rq_is_sync(arq2->request));
310 * Strict one way elevator _except_ in the case where we allow
311 * short backward seeks which are biased as twice the cost of a
312 * similar forward seek.
316 else if (s1+maxback >= last)
317 d1 = (last - s1)*BACK_PENALTY;
320 d1 = 0; /* shut up, gcc */
325 else if (s2+maxback >= last)
326 d2 = (last - s2)*BACK_PENALTY;
332 /* Found required data */
333 if (!r1_wrap && r2_wrap)
335 else if (!r2_wrap && r1_wrap)
337 else if (r1_wrap && r2_wrap) {
338 /* both behind the head */
345 /* Both requests in front of the head */
359 * as_find_next_arq finds the next request after @prev in elevator order.
360 * this with as_choose_req form the basis for how the scheduler chooses
361 * what request to process next. Anticipation works on top of this.
363 static struct as_rq *as_find_next_arq(struct as_data *ad, struct as_rq *arq)
365 struct request *last = arq->request;
366 struct rb_node *rbnext = rb_next(&last->rb_node);
367 struct rb_node *rbprev = rb_prev(&last->rb_node);
368 struct as_rq *next = NULL, *prev = NULL;
370 BUG_ON(RB_EMPTY_NODE(&last->rb_node));
373 prev = RQ_DATA(rb_entry_rq(rbprev));
376 next = RQ_DATA(rb_entry_rq(rbnext));
378 const int data_dir = rq_is_sync(last);
380 rbnext = rb_first(&ad->sort_list[data_dir]);
381 if (rbnext && rbnext != &last->rb_node)
382 next = RQ_DATA(rb_entry_rq(rbnext));
385 return as_choose_req(ad, next, prev);
389 * anticipatory scheduling functions follow
393 * as_antic_expired tells us when we have anticipated too long.
394 * The funny "absolute difference" math on the elapsed time is to handle
395 * jiffy wraps, and disks which have been idle for 0x80000000 jiffies.
397 static int as_antic_expired(struct as_data *ad)
401 delta_jif = jiffies - ad->antic_start;
402 if (unlikely(delta_jif < 0))
403 delta_jif = -delta_jif;
404 if (delta_jif < ad->antic_expire)
411 * as_antic_waitnext starts anticipating that a nice request will soon be
412 * submitted. See also as_antic_waitreq
414 static void as_antic_waitnext(struct as_data *ad)
416 unsigned long timeout;
418 BUG_ON(ad->antic_status != ANTIC_OFF
419 && ad->antic_status != ANTIC_WAIT_REQ);
421 timeout = ad->antic_start + ad->antic_expire;
423 mod_timer(&ad->antic_timer, timeout);
425 ad->antic_status = ANTIC_WAIT_NEXT;
429 * as_antic_waitreq starts anticipating. We don't start timing the anticipation
430 * until the request that we're anticipating on has finished. This means we
431 * are timing from when the candidate process wakes up hopefully.
433 static void as_antic_waitreq(struct as_data *ad)
435 BUG_ON(ad->antic_status == ANTIC_FINISHED);
436 if (ad->antic_status == ANTIC_OFF) {
437 if (!ad->io_context || ad->ioc_finished)
438 as_antic_waitnext(ad);
440 ad->antic_status = ANTIC_WAIT_REQ;
445 * This is called directly by the functions in this file to stop anticipation.
446 * We kill the timer and schedule a call to the request_fn asap.
448 static void as_antic_stop(struct as_data *ad)
450 int status = ad->antic_status;
452 if (status == ANTIC_WAIT_REQ || status == ANTIC_WAIT_NEXT) {
453 if (status == ANTIC_WAIT_NEXT)
454 del_timer(&ad->antic_timer);
455 ad->antic_status = ANTIC_FINISHED;
456 /* see as_work_handler */
457 kblockd_schedule_work(&ad->antic_work);
462 * as_antic_timeout is the timer function set by as_antic_waitnext.
464 static void as_antic_timeout(unsigned long data)
466 struct request_queue *q = (struct request_queue *)data;
467 struct as_data *ad = q->elevator->elevator_data;
470 spin_lock_irqsave(q->queue_lock, flags);
471 if (ad->antic_status == ANTIC_WAIT_REQ
472 || ad->antic_status == ANTIC_WAIT_NEXT) {
473 struct as_io_context *aic = ad->io_context->aic;
475 ad->antic_status = ANTIC_FINISHED;
476 kblockd_schedule_work(&ad->antic_work);
478 if (aic->ttime_samples == 0) {
479 /* process anticipated on has exited or timed out*/
480 ad->exit_prob = (7*ad->exit_prob + 256)/8;
482 if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
483 /* process not "saved" by a cooperating request */
484 ad->exit_no_coop = (7*ad->exit_no_coop + 256)/8;
487 spin_unlock_irqrestore(q->queue_lock, flags);
490 static void as_update_thinktime(struct as_data *ad, struct as_io_context *aic,
493 /* fixed point: 1.0 == 1<<8 */
494 if (aic->ttime_samples == 0) {
495 ad->new_ttime_total = (7*ad->new_ttime_total + 256*ttime) / 8;
496 ad->new_ttime_mean = ad->new_ttime_total / 256;
498 ad->exit_prob = (7*ad->exit_prob)/8;
500 aic->ttime_samples = (7*aic->ttime_samples + 256) / 8;
501 aic->ttime_total = (7*aic->ttime_total + 256*ttime) / 8;
502 aic->ttime_mean = (aic->ttime_total + 128) / aic->ttime_samples;
505 static void as_update_seekdist(struct as_data *ad, struct as_io_context *aic,
510 if (aic->seek_samples == 0) {
511 ad->new_seek_total = (7*ad->new_seek_total + 256*(u64)sdist)/8;
512 ad->new_seek_mean = ad->new_seek_total / 256;
516 * Don't allow the seek distance to get too large from the
517 * odd fragment, pagein, etc
519 if (aic->seek_samples <= 60) /* second&third seek */
520 sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*1024);
522 sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*64);
524 aic->seek_samples = (7*aic->seek_samples + 256) / 8;
525 aic->seek_total = (7*aic->seek_total + (u64)256*sdist) / 8;
526 total = aic->seek_total + (aic->seek_samples/2);
527 do_div(total, aic->seek_samples);
528 aic->seek_mean = (sector_t)total;
532 * as_update_iohist keeps a decaying histogram of IO thinktimes, and
533 * updates @aic->ttime_mean based on that. It is called when a new
536 static void as_update_iohist(struct as_data *ad, struct as_io_context *aic,
539 int data_dir = rq_is_sync(rq);
540 unsigned long thinktime = 0;
546 if (data_dir == REQ_SYNC) {
547 unsigned long in_flight = atomic_read(&aic->nr_queued)
548 + atomic_read(&aic->nr_dispatched);
549 spin_lock(&aic->lock);
550 if (test_bit(AS_TASK_IORUNNING, &aic->state) ||
551 test_bit(AS_TASK_IOSTARTED, &aic->state)) {
552 /* Calculate read -> read thinktime */
553 if (test_bit(AS_TASK_IORUNNING, &aic->state)
555 thinktime = jiffies - aic->last_end_request;
556 thinktime = min(thinktime, MAX_THINKTIME-1);
558 as_update_thinktime(ad, aic, thinktime);
560 /* Calculate read -> read seek distance */
561 if (aic->last_request_pos < rq->sector)
562 seek_dist = rq->sector - aic->last_request_pos;
564 seek_dist = aic->last_request_pos - rq->sector;
565 as_update_seekdist(ad, aic, seek_dist);
567 aic->last_request_pos = rq->sector + rq->nr_sectors;
568 set_bit(AS_TASK_IOSTARTED, &aic->state);
569 spin_unlock(&aic->lock);
574 * as_close_req decides if one request is considered "close" to the
575 * previous one issued.
577 static int as_close_req(struct as_data *ad, struct as_io_context *aic,
580 unsigned long delay; /* milliseconds */
581 sector_t last = ad->last_sector[ad->batch_data_dir];
582 sector_t next = arq->request->sector;
583 sector_t delta; /* acceptable close offset (in sectors) */
586 if (ad->antic_status == ANTIC_OFF || !ad->ioc_finished)
589 delay = ((jiffies - ad->antic_start) * 1000) / HZ;
593 else if (delay <= 20 && delay <= ad->antic_expire)
594 delta = 8192 << delay;
598 if ((last <= next + (delta>>1)) && (next <= last + delta))
606 if (aic->seek_samples == 0) {
608 * Process has just started IO. Use past statistics to
609 * gauge success possibility
611 if (ad->new_seek_mean > s) {
612 /* this request is better than what we're expecting */
617 if (aic->seek_mean > s) {
618 /* this request is better than what we're expecting */
627 * as_can_break_anticipation returns true if we have been anticipating this
630 * It also returns true if the process against which we are anticipating
631 * submits a write - that's presumably an fsync, O_SYNC write, etc. We want to
632 * dispatch it ASAP, because we know that application will not be submitting
635 * If the task which has submitted the request has exited, break anticipation.
637 * If this task has queued some other IO, do not enter enticipation.
639 static int as_can_break_anticipation(struct as_data *ad, struct as_rq *arq)
641 struct io_context *ioc;
642 struct as_io_context *aic;
644 ioc = ad->io_context;
647 if (arq && ioc == arq->io_context) {
648 /* request from same process */
652 if (ad->ioc_finished && as_antic_expired(ad)) {
654 * In this situation status should really be FINISHED,
655 * however the timer hasn't had the chance to run yet.
664 if (atomic_read(&aic->nr_queued) > 0) {
665 /* process has more requests queued */
669 if (atomic_read(&aic->nr_dispatched) > 0) {
670 /* process has more requests dispatched */
674 if (arq && rq_is_sync(arq->request) && as_close_req(ad, aic, arq)) {
676 * Found a close request that is not one of ours.
678 * This makes close requests from another process update
679 * our IO history. Is generally useful when there are
680 * two or more cooperating processes working in the same
683 if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
684 if (aic->ttime_samples == 0)
685 ad->exit_prob = (7*ad->exit_prob + 256)/8;
687 ad->exit_no_coop = (7*ad->exit_no_coop)/8;
690 as_update_iohist(ad, aic, arq->request);
694 if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
695 /* process anticipated on has exited */
696 if (aic->ttime_samples == 0)
697 ad->exit_prob = (7*ad->exit_prob + 256)/8;
699 if (ad->exit_no_coop > 128)
703 if (aic->ttime_samples == 0) {
704 if (ad->new_ttime_mean > ad->antic_expire)
706 if (ad->exit_prob * ad->exit_no_coop > 128*256)
708 } else if (aic->ttime_mean > ad->antic_expire) {
709 /* the process thinks too much between requests */
717 * as_can_anticipate indicates whether we should either run arq
718 * or keep anticipating a better request.
720 static int as_can_anticipate(struct as_data *ad, struct as_rq *arq)
724 * Last request submitted was a write
728 if (ad->antic_status == ANTIC_FINISHED)
730 * Don't restart if we have just finished. Run the next request
734 if (as_can_break_anticipation(ad, arq))
736 * This request is a good candidate. Don't keep anticipating,
742 * OK from here, we haven't finished, and don't have a decent request!
743 * Status is either ANTIC_OFF so start waiting,
744 * ANTIC_WAIT_REQ so continue waiting for request to finish
745 * or ANTIC_WAIT_NEXT so continue waiting for an acceptable request.
752 * as_update_arq must be called whenever a request (arq) is added to
753 * the sort_list. This function keeps caches up to date, and checks if the
754 * request might be one we are "anticipating"
756 static void as_update_arq(struct as_data *ad, struct as_rq *arq)
758 const int data_dir = rq_is_sync(arq->request);
760 /* keep the next_arq cache up to date */
761 ad->next_arq[data_dir] = as_choose_req(ad, arq, ad->next_arq[data_dir]);
764 * have we been anticipating this request?
765 * or does it come from the same process as the one we are anticipating
768 if (ad->antic_status == ANTIC_WAIT_REQ
769 || ad->antic_status == ANTIC_WAIT_NEXT) {
770 if (as_can_break_anticipation(ad, arq))
776 * Gathers timings and resizes the write batch automatically
778 static void update_write_batch(struct as_data *ad)
780 unsigned long batch = ad->batch_expire[REQ_ASYNC];
783 write_time = (jiffies - ad->current_batch_expires) + batch;
787 if (write_time > batch && !ad->write_batch_idled) {
788 if (write_time > batch * 3)
789 ad->write_batch_count /= 2;
791 ad->write_batch_count--;
792 } else if (write_time < batch && ad->current_write_count == 0) {
793 if (batch > write_time * 3)
794 ad->write_batch_count *= 2;
796 ad->write_batch_count++;
799 if (ad->write_batch_count < 1)
800 ad->write_batch_count = 1;
804 * as_completed_request is to be called when a request has completed and
805 * returned something to the requesting process, be it an error or data.
807 static void as_completed_request(request_queue_t *q, struct request *rq)
809 struct as_data *ad = q->elevator->elevator_data;
810 struct as_rq *arq = RQ_DATA(rq);
812 WARN_ON(!list_empty(&rq->queuelist));
814 if (arq->state != AS_RQ_REMOVED) {
815 printk("arq->state %d\n", arq->state);
820 if (ad->changed_batch && ad->nr_dispatched == 1) {
821 kblockd_schedule_work(&ad->antic_work);
822 ad->changed_batch = 0;
824 if (ad->batch_data_dir == REQ_SYNC)
827 WARN_ON(ad->nr_dispatched == 0);
831 * Start counting the batch from when a request of that direction is
832 * actually serviced. This should help devices with big TCQ windows
833 * and writeback caches
835 if (ad->new_batch && ad->batch_data_dir == rq_is_sync(rq)) {
836 update_write_batch(ad);
837 ad->current_batch_expires = jiffies +
838 ad->batch_expire[REQ_SYNC];
842 if (ad->io_context == arq->io_context && ad->io_context) {
843 ad->antic_start = jiffies;
844 ad->ioc_finished = 1;
845 if (ad->antic_status == ANTIC_WAIT_REQ) {
847 * We were waiting on this request, now anticipate
850 as_antic_waitnext(ad);
854 as_put_io_context(arq);
856 arq->state = AS_RQ_POSTSCHED;
860 * as_remove_queued_request removes a request from the pre dispatch queue
861 * without updating refcounts. It is expected the caller will drop the
862 * reference unless it replaces the request at somepart of the elevator
863 * (ie. the dispatch queue)
865 static void as_remove_queued_request(request_queue_t *q, struct request *rq)
867 struct as_rq *arq = RQ_DATA(rq);
868 const int data_dir = rq_is_sync(rq);
869 struct as_data *ad = q->elevator->elevator_data;
871 WARN_ON(arq->state != AS_RQ_QUEUED);
873 if (arq->io_context && arq->io_context->aic) {
874 BUG_ON(!atomic_read(&arq->io_context->aic->nr_queued));
875 atomic_dec(&arq->io_context->aic->nr_queued);
879 * Update the "next_arq" cache if we are about to remove its
882 if (ad->next_arq[data_dir] == arq)
883 ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
886 as_del_arq_rb(ad, rq);
890 * as_fifo_expired returns 0 if there are no expired reads on the fifo,
891 * 1 otherwise. It is ratelimited so that we only perform the check once per
892 * `fifo_expire' interval. Otherwise a large number of expired requests
893 * would create a hopeless seekstorm.
895 * See as_antic_expired comment.
897 static int as_fifo_expired(struct as_data *ad, int adir)
902 delta_jif = jiffies - ad->last_check_fifo[adir];
903 if (unlikely(delta_jif < 0))
904 delta_jif = -delta_jif;
905 if (delta_jif < ad->fifo_expire[adir])
908 ad->last_check_fifo[adir] = jiffies;
910 if (list_empty(&ad->fifo_list[adir]))
913 rq = rq_entry_fifo(ad->fifo_list[adir].next);
915 return time_after(jiffies, rq_fifo_time(rq));
919 * as_batch_expired returns true if the current batch has expired. A batch
920 * is a set of reads or a set of writes.
922 static inline int as_batch_expired(struct as_data *ad)
924 if (ad->changed_batch || ad->new_batch)
927 if (ad->batch_data_dir == REQ_SYNC)
928 /* TODO! add a check so a complete fifo gets written? */
929 return time_after(jiffies, ad->current_batch_expires);
931 return time_after(jiffies, ad->current_batch_expires)
932 || ad->current_write_count == 0;
936 * move an entry to dispatch queue
938 static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq)
940 struct request *rq = arq->request;
941 const int data_dir = rq_is_sync(rq);
943 BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
946 ad->antic_status = ANTIC_OFF;
949 * This has to be set in order to be correctly updated by
952 ad->last_sector[data_dir] = rq->sector + rq->nr_sectors;
954 if (data_dir == REQ_SYNC) {
955 /* In case we have to anticipate after this */
956 copy_io_context(&ad->io_context, &arq->io_context);
958 if (ad->io_context) {
959 put_io_context(ad->io_context);
960 ad->io_context = NULL;
963 if (ad->current_write_count != 0)
964 ad->current_write_count--;
966 ad->ioc_finished = 0;
968 ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
971 * take it off the sort and fifo list, add to dispatch queue
973 as_remove_queued_request(ad->q, rq);
974 WARN_ON(arq->state != AS_RQ_QUEUED);
976 elv_dispatch_sort(ad->q, rq);
978 arq->state = AS_RQ_DISPATCHED;
979 if (arq->io_context && arq->io_context->aic)
980 atomic_inc(&arq->io_context->aic->nr_dispatched);
985 * as_dispatch_request selects the best request according to
986 * read/write expire, batch expire, etc, and moves it to the dispatch
987 * queue. Returns 1 if a request was found, 0 otherwise.
989 static int as_dispatch_request(request_queue_t *q, int force)
991 struct as_data *ad = q->elevator->elevator_data;
993 const int reads = !list_empty(&ad->fifo_list[REQ_SYNC]);
994 const int writes = !list_empty(&ad->fifo_list[REQ_ASYNC]);
996 if (unlikely(force)) {
998 * Forced dispatch, accounting is useless. Reset
999 * accounting states and dump fifo_lists. Note that
1000 * batch_data_dir is reset to REQ_SYNC to avoid
1001 * screwing write batch accounting as write batch
1002 * accounting occurs on W->R transition.
1006 ad->batch_data_dir = REQ_SYNC;
1007 ad->changed_batch = 0;
1010 while (ad->next_arq[REQ_SYNC]) {
1011 as_move_to_dispatch(ad, ad->next_arq[REQ_SYNC]);
1014 ad->last_check_fifo[REQ_SYNC] = jiffies;
1016 while (ad->next_arq[REQ_ASYNC]) {
1017 as_move_to_dispatch(ad, ad->next_arq[REQ_ASYNC]);
1020 ad->last_check_fifo[REQ_ASYNC] = jiffies;
1025 /* Signal that the write batch was uncontended, so we can't time it */
1026 if (ad->batch_data_dir == REQ_ASYNC && !reads) {
1027 if (ad->current_write_count == 0 || !writes)
1028 ad->write_batch_idled = 1;
1031 if (!(reads || writes)
1032 || ad->antic_status == ANTIC_WAIT_REQ
1033 || ad->antic_status == ANTIC_WAIT_NEXT
1034 || ad->changed_batch)
1037 if (!(reads && writes && as_batch_expired(ad))) {
1039 * batch is still running or no reads or no writes
1041 arq = ad->next_arq[ad->batch_data_dir];
1043 if (ad->batch_data_dir == REQ_SYNC && ad->antic_expire) {
1044 if (as_fifo_expired(ad, REQ_SYNC))
1047 if (as_can_anticipate(ad, arq)) {
1048 as_antic_waitreq(ad);
1054 /* we have a "next request" */
1055 if (reads && !writes)
1056 ad->current_batch_expires =
1057 jiffies + ad->batch_expire[REQ_SYNC];
1058 goto dispatch_request;
1063 * at this point we are not running a batch. select the appropriate
1064 * data direction (read / write)
1068 BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[REQ_SYNC]));
1070 if (writes && ad->batch_data_dir == REQ_SYNC)
1072 * Last batch was a read, switch to writes
1074 goto dispatch_writes;
1076 if (ad->batch_data_dir == REQ_ASYNC) {
1077 WARN_ON(ad->new_batch);
1078 ad->changed_batch = 1;
1080 ad->batch_data_dir = REQ_SYNC;
1081 arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[REQ_SYNC].next));
1082 ad->last_check_fifo[ad->batch_data_dir] = jiffies;
1083 goto dispatch_request;
1087 * the last batch was a read
1092 BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[REQ_ASYNC]));
1094 if (ad->batch_data_dir == REQ_SYNC) {
1095 ad->changed_batch = 1;
1098 * new_batch might be 1 when the queue runs out of
1099 * reads. A subsequent submission of a write might
1100 * cause a change of batch before the read is finished.
1104 ad->batch_data_dir = REQ_ASYNC;
1105 ad->current_write_count = ad->write_batch_count;
1106 ad->write_batch_idled = 0;
1107 arq = ad->next_arq[ad->batch_data_dir];
1108 goto dispatch_request;
1116 * If a request has expired, service it.
1119 if (as_fifo_expired(ad, ad->batch_data_dir)) {
1121 arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next));
1124 if (ad->changed_batch) {
1125 WARN_ON(ad->new_batch);
1127 if (ad->nr_dispatched)
1130 if (ad->batch_data_dir == REQ_ASYNC)
1131 ad->current_batch_expires = jiffies +
1132 ad->batch_expire[REQ_ASYNC];
1136 ad->changed_batch = 0;
1140 * arq is the selected appropriate request.
1142 as_move_to_dispatch(ad, arq);
1148 * add arq to rbtree and fifo
1150 static void as_add_request(request_queue_t *q, struct request *rq)
1152 struct as_data *ad = q->elevator->elevator_data;
1153 struct as_rq *arq = RQ_DATA(rq);
1156 arq->state = AS_RQ_NEW;
1158 data_dir = rq_is_sync(rq);
1160 arq->io_context = as_get_io_context();
1162 if (arq->io_context) {
1163 as_update_iohist(ad, arq->io_context->aic, arq->request);
1164 atomic_inc(&arq->io_context->aic->nr_queued);
1167 as_add_arq_rb(ad, rq);
1170 * set expire time (only used for reads) and add to fifo list
1172 rq_set_fifo_time(rq, jiffies + ad->fifo_expire[data_dir]);
1173 list_add_tail(&rq->queuelist, &ad->fifo_list[data_dir]);
1175 as_update_arq(ad, arq); /* keep state machine up to date */
1176 arq->state = AS_RQ_QUEUED;
1179 static void as_activate_request(request_queue_t *q, struct request *rq)
1181 struct as_rq *arq = RQ_DATA(rq);
1183 WARN_ON(arq->state != AS_RQ_DISPATCHED);
1184 arq->state = AS_RQ_REMOVED;
1185 if (arq->io_context && arq->io_context->aic)
1186 atomic_dec(&arq->io_context->aic->nr_dispatched);
1189 static void as_deactivate_request(request_queue_t *q, struct request *rq)
1191 struct as_rq *arq = RQ_DATA(rq);
1193 WARN_ON(arq->state != AS_RQ_REMOVED);
1194 arq->state = AS_RQ_DISPATCHED;
1195 if (arq->io_context && arq->io_context->aic)
1196 atomic_inc(&arq->io_context->aic->nr_dispatched);
1200 * as_queue_empty tells us if there are requests left in the device. It may
1201 * not be the case that a driver can get the next request even if the queue
1202 * is not empty - it is used in the block layer to check for plugging and
1203 * merging opportunities
1205 static int as_queue_empty(request_queue_t *q)
1207 struct as_data *ad = q->elevator->elevator_data;
1209 return list_empty(&ad->fifo_list[REQ_ASYNC])
1210 && list_empty(&ad->fifo_list[REQ_SYNC]);
1214 as_merge(request_queue_t *q, struct request **req, struct bio *bio)
1216 struct as_data *ad = q->elevator->elevator_data;
1217 sector_t rb_key = bio->bi_sector + bio_sectors(bio);
1218 struct request *__rq;
1221 * check for front merge
1223 __rq = elv_rb_find(&ad->sort_list[bio_data_dir(bio)], rb_key);
1224 if (__rq && elv_rq_merge_ok(__rq, bio)) {
1226 return ELEVATOR_FRONT_MERGE;
1229 return ELEVATOR_NO_MERGE;
1232 static void as_merged_request(request_queue_t *q, struct request *req, int type)
1234 struct as_data *ad = q->elevator->elevator_data;
1237 * if the merge was a front merge, we need to reposition request
1239 if (type == ELEVATOR_FRONT_MERGE) {
1240 as_del_arq_rb(ad, req);
1241 as_add_arq_rb(ad, req);
1243 * Note! At this stage of this and the next function, our next
1244 * request may not be optimal - eg the request may have "grown"
1245 * behind the disk head. We currently don't bother adjusting.
1250 static void as_merged_requests(request_queue_t *q, struct request *req,
1251 struct request *next)
1253 struct as_rq *arq = RQ_DATA(req);
1254 struct as_rq *anext = RQ_DATA(next);
1260 * if anext expires before arq, assign its expire time to arq
1261 * and move into anext position (anext will be deleted) in fifo
1263 if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
1264 if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
1265 list_move(&req->queuelist, &next->queuelist);
1266 rq_set_fifo_time(req, rq_fifo_time(next));
1268 * Don't copy here but swap, because when anext is
1269 * removed below, it must contain the unused context
1271 swap_io_context(&arq->io_context, &anext->io_context);
1276 * kill knowledge of next, this one is a goner
1278 as_remove_queued_request(q, next);
1279 as_put_io_context(anext);
1281 anext->state = AS_RQ_MERGED;
1285 * This is executed in a "deferred" process context, by kblockd. It calls the
1286 * driver's request_fn so the driver can submit that request.
1288 * IMPORTANT! This guy will reenter the elevator, so set up all queue global
1289 * state before calling, and don't rely on any state over calls.
1291 * FIXME! dispatch queue is not a queue at all!
1293 static void as_work_handler(void *data)
1295 struct request_queue *q = data;
1296 unsigned long flags;
1298 spin_lock_irqsave(q->queue_lock, flags);
1299 if (!as_queue_empty(q))
1301 spin_unlock_irqrestore(q->queue_lock, flags);
1304 static void as_put_request(request_queue_t *q, struct request *rq)
1306 struct as_data *ad = q->elevator->elevator_data;
1307 struct as_rq *arq = RQ_DATA(rq);
1314 if (unlikely(arq->state != AS_RQ_POSTSCHED &&
1315 arq->state != AS_RQ_PRESCHED &&
1316 arq->state != AS_RQ_MERGED)) {
1317 printk("arq->state %d\n", arq->state);
1321 mempool_free(arq, ad->arq_pool);
1322 rq->elevator_private = NULL;
1325 static int as_set_request(request_queue_t *q, struct request *rq,
1326 struct bio *bio, gfp_t gfp_mask)
1328 struct as_data *ad = q->elevator->elevator_data;
1329 struct as_rq *arq = mempool_alloc(ad->arq_pool, gfp_mask);
1332 memset(arq, 0, sizeof(*arq));
1334 arq->state = AS_RQ_PRESCHED;
1335 arq->io_context = NULL;
1336 rq->elevator_private = arq;
1343 static int as_may_queue(request_queue_t *q, int rw, struct bio *bio)
1345 int ret = ELV_MQUEUE_MAY;
1346 struct as_data *ad = q->elevator->elevator_data;
1347 struct io_context *ioc;
1348 if (ad->antic_status == ANTIC_WAIT_REQ ||
1349 ad->antic_status == ANTIC_WAIT_NEXT) {
1350 ioc = as_get_io_context();
1351 if (ad->io_context == ioc)
1352 ret = ELV_MQUEUE_MUST;
1353 put_io_context(ioc);
1359 static void as_exit_queue(elevator_t *e)
1361 struct as_data *ad = e->elevator_data;
1363 del_timer_sync(&ad->antic_timer);
1366 BUG_ON(!list_empty(&ad->fifo_list[REQ_SYNC]));
1367 BUG_ON(!list_empty(&ad->fifo_list[REQ_ASYNC]));
1369 mempool_destroy(ad->arq_pool);
1370 put_io_context(ad->io_context);
1375 * initialize elevator private data (as_data), and alloc a arq for
1376 * each request on the free lists
1378 static void *as_init_queue(request_queue_t *q, elevator_t *e)
1385 ad = kmalloc_node(sizeof(*ad), GFP_KERNEL, q->node);
1388 memset(ad, 0, sizeof(*ad));
1390 ad->q = q; /* Identify what queue the data belongs to */
1392 ad->arq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
1393 mempool_free_slab, arq_pool, q->node);
1394 if (!ad->arq_pool) {
1399 /* anticipatory scheduling helpers */
1400 ad->antic_timer.function = as_antic_timeout;
1401 ad->antic_timer.data = (unsigned long)q;
1402 init_timer(&ad->antic_timer);
1403 INIT_WORK(&ad->antic_work, as_work_handler, q);
1405 INIT_LIST_HEAD(&ad->fifo_list[REQ_SYNC]);
1406 INIT_LIST_HEAD(&ad->fifo_list[REQ_ASYNC]);
1407 ad->sort_list[REQ_SYNC] = RB_ROOT;
1408 ad->sort_list[REQ_ASYNC] = RB_ROOT;
1409 ad->fifo_expire[REQ_SYNC] = default_read_expire;
1410 ad->fifo_expire[REQ_ASYNC] = default_write_expire;
1411 ad->antic_expire = default_antic_expire;
1412 ad->batch_expire[REQ_SYNC] = default_read_batch_expire;
1413 ad->batch_expire[REQ_ASYNC] = default_write_batch_expire;
1415 ad->current_batch_expires = jiffies + ad->batch_expire[REQ_SYNC];
1416 ad->write_batch_count = ad->batch_expire[REQ_ASYNC] / 10;
1417 if (ad->write_batch_count < 2)
1418 ad->write_batch_count = 2;
1428 as_var_show(unsigned int var, char *page)
1430 return sprintf(page, "%d\n", var);
1434 as_var_store(unsigned long *var, const char *page, size_t count)
1436 char *p = (char *) page;
1438 *var = simple_strtoul(p, &p, 10);
1442 static ssize_t est_time_show(elevator_t *e, char *page)
1444 struct as_data *ad = e->elevator_data;
1447 pos += sprintf(page+pos, "%lu %% exit probability\n",
1448 100*ad->exit_prob/256);
1449 pos += sprintf(page+pos, "%lu %% probability of exiting without a "
1450 "cooperating process submitting IO\n",
1451 100*ad->exit_no_coop/256);
1452 pos += sprintf(page+pos, "%lu ms new thinktime\n", ad->new_ttime_mean);
1453 pos += sprintf(page+pos, "%llu sectors new seek distance\n",
1454 (unsigned long long)ad->new_seek_mean);
1459 #define SHOW_FUNCTION(__FUNC, __VAR) \
1460 static ssize_t __FUNC(elevator_t *e, char *page) \
1462 struct as_data *ad = e->elevator_data; \
1463 return as_var_show(jiffies_to_msecs((__VAR)), (page)); \
1465 SHOW_FUNCTION(as_read_expire_show, ad->fifo_expire[REQ_SYNC]);
1466 SHOW_FUNCTION(as_write_expire_show, ad->fifo_expire[REQ_ASYNC]);
1467 SHOW_FUNCTION(as_antic_expire_show, ad->antic_expire);
1468 SHOW_FUNCTION(as_read_batch_expire_show, ad->batch_expire[REQ_SYNC]);
1469 SHOW_FUNCTION(as_write_batch_expire_show, ad->batch_expire[REQ_ASYNC]);
1470 #undef SHOW_FUNCTION
1472 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX) \
1473 static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
1475 struct as_data *ad = e->elevator_data; \
1476 int ret = as_var_store(__PTR, (page), count); \
1477 if (*(__PTR) < (MIN)) \
1479 else if (*(__PTR) > (MAX)) \
1481 *(__PTR) = msecs_to_jiffies(*(__PTR)); \
1484 STORE_FUNCTION(as_read_expire_store, &ad->fifo_expire[REQ_SYNC], 0, INT_MAX);
1485 STORE_FUNCTION(as_write_expire_store, &ad->fifo_expire[REQ_ASYNC], 0, INT_MAX);
1486 STORE_FUNCTION(as_antic_expire_store, &ad->antic_expire, 0, INT_MAX);
1487 STORE_FUNCTION(as_read_batch_expire_store,
1488 &ad->batch_expire[REQ_SYNC], 0, INT_MAX);
1489 STORE_FUNCTION(as_write_batch_expire_store,
1490 &ad->batch_expire[REQ_ASYNC], 0, INT_MAX);
1491 #undef STORE_FUNCTION
1493 #define AS_ATTR(name) \
1494 __ATTR(name, S_IRUGO|S_IWUSR, as_##name##_show, as_##name##_store)
1496 static struct elv_fs_entry as_attrs[] = {
1497 __ATTR_RO(est_time),
1498 AS_ATTR(read_expire),
1499 AS_ATTR(write_expire),
1500 AS_ATTR(antic_expire),
1501 AS_ATTR(read_batch_expire),
1502 AS_ATTR(write_batch_expire),
1506 static struct elevator_type iosched_as = {
1508 .elevator_merge_fn = as_merge,
1509 .elevator_merged_fn = as_merged_request,
1510 .elevator_merge_req_fn = as_merged_requests,
1511 .elevator_dispatch_fn = as_dispatch_request,
1512 .elevator_add_req_fn = as_add_request,
1513 .elevator_activate_req_fn = as_activate_request,
1514 .elevator_deactivate_req_fn = as_deactivate_request,
1515 .elevator_queue_empty_fn = as_queue_empty,
1516 .elevator_completed_req_fn = as_completed_request,
1517 .elevator_former_req_fn = elv_rb_former_request,
1518 .elevator_latter_req_fn = elv_rb_latter_request,
1519 .elevator_set_req_fn = as_set_request,
1520 .elevator_put_req_fn = as_put_request,
1521 .elevator_may_queue_fn = as_may_queue,
1522 .elevator_init_fn = as_init_queue,
1523 .elevator_exit_fn = as_exit_queue,
1527 .elevator_attrs = as_attrs,
1528 .elevator_name = "anticipatory",
1529 .elevator_owner = THIS_MODULE,
1532 static int __init as_init(void)
1536 arq_pool = kmem_cache_create("as_arq", sizeof(struct as_rq),
1541 ret = elv_register(&iosched_as);
1544 * don't allow AS to get unregistered, since we would have
1545 * to browse all tasks in the system and release their
1546 * as_io_context first
1548 __module_get(THIS_MODULE);
1552 kmem_cache_destroy(arq_pool);
1556 static void __exit as_exit(void)
1558 DECLARE_COMPLETION(all_gone);
1559 elv_unregister(&iosched_as);
1560 ioc_gone = &all_gone;
1561 /* ioc_gone's update must be visible before reading ioc_count */
1563 if (atomic_read(&ioc_count))
1564 wait_for_completion(ioc_gone);
1566 kmem_cache_destroy(arq_pool);
1569 module_init(as_init);
1570 module_exit(as_exit);
1572 MODULE_AUTHOR("Nick Piggin");
1573 MODULE_LICENSE("GPL");
1574 MODULE_DESCRIPTION("anticipatory IO scheduler");