aboutsummaryrefslogtreecommitdiffstats
path: root/drivers/block/as-iosched.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /drivers/block/as-iosched.c
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'drivers/block/as-iosched.c')
-rw-r--r--drivers/block/as-iosched.c2136
1 files changed, 2136 insertions, 0 deletions
diff --git a/drivers/block/as-iosched.c b/drivers/block/as-iosched.c
new file mode 100644
index 000000000000..a9575bb58a5e
--- /dev/null
+++ b/drivers/block/as-iosched.c
@@ -0,0 +1,2136 @@
1/*
2 * linux/drivers/block/as-iosched.c
3 *
4 * Anticipatory & deadline i/o scheduler.
5 *
6 * Copyright (C) 2002 Jens Axboe <axboe@suse.de>
7 * Nick Piggin <piggin@cyberone.com.au>
8 *
9 */
10#include <linux/kernel.h>
11#include <linux/fs.h>
12#include <linux/blkdev.h>
13#include <linux/elevator.h>
14#include <linux/bio.h>
15#include <linux/config.h>
16#include <linux/module.h>
17#include <linux/slab.h>
18#include <linux/init.h>
19#include <linux/compiler.h>
20#include <linux/hash.h>
21#include <linux/rbtree.h>
22#include <linux/interrupt.h>
23
24#define REQ_SYNC 1
25#define REQ_ASYNC 0
26
27/*
28 * See Documentation/block/as-iosched.txt
29 */
30
31/*
32 * max time before a read is submitted.
33 */
34#define default_read_expire (HZ / 8)
35
36/*
37 * ditto for writes, these limits are not hard, even
38 * if the disk is capable of satisfying them.
39 */
40#define default_write_expire (HZ / 4)
41
42/*
43 * read_batch_expire describes how long we will allow a stream of reads to
44 * persist before looking to see whether it is time to switch over to writes.
45 */
46#define default_read_batch_expire (HZ / 2)
47
48/*
49 * write_batch_expire describes how long we want a stream of writes to run for.
50 * This is not a hard limit, but a target we set for the auto-tuning thingy.
51 * See, the problem is: we can send a lot of writes to disk cache / TCQ in
52 * a short amount of time...
53 */
54#define default_write_batch_expire (HZ / 8)
55
56/*
57 * max time we may wait to anticipate a read (default around 6ms)
58 */
59#define default_antic_expire ((HZ / 150) ? HZ / 150 : 1)
60
61/*
62 * Keep track of up to 20ms thinktimes. We can go as big as we like here,
63 * however huge values tend to interfere and not decay fast enough. A program
64 * might be in a non-io phase of operation. Waiting on user input for example,
65 * or doing a lengthy computation. A small penalty can be justified there, and
66 * will still catch out those processes that constantly have large thinktimes.
67 */
68#define MAX_THINKTIME (HZ/50UL)
69
70/* Bits in as_io_context.state */
71enum as_io_states {
72 AS_TASK_RUNNING=0, /* Process has not exitted */
73 AS_TASK_IOSTARTED, /* Process has started some IO */
74 AS_TASK_IORUNNING, /* Process has completed some IO */
75};
76
77enum anticipation_status {
78 ANTIC_OFF=0, /* Not anticipating (normal operation) */
79 ANTIC_WAIT_REQ, /* The last read has not yet completed */
80 ANTIC_WAIT_NEXT, /* Currently anticipating a request vs
81 last read (which has completed) */
82 ANTIC_FINISHED, /* Anticipating but have found a candidate
83 * or timed out */
84};
85
86struct as_data {
87 /*
88 * run time data
89 */
90
91 struct request_queue *q; /* the "owner" queue */
92
93 /*
94 * requests (as_rq s) are present on both sort_list and fifo_list
95 */
96 struct rb_root sort_list[2];
97 struct list_head fifo_list[2];
98
99 struct as_rq *next_arq[2]; /* next in sort order */
100 sector_t last_sector[2]; /* last REQ_SYNC & REQ_ASYNC sectors */
101 struct list_head *dispatch; /* driver dispatch queue */
102 struct list_head *hash; /* request hash */
103
104 unsigned long exit_prob; /* probability a task will exit while
105 being waited on */
106 unsigned long new_ttime_total; /* mean thinktime on new proc */
107 unsigned long new_ttime_mean;
108 u64 new_seek_total; /* mean seek on new proc */
109 sector_t new_seek_mean;
110
111 unsigned long current_batch_expires;
112 unsigned long last_check_fifo[2];
113 int changed_batch; /* 1: waiting for old batch to end */
114 int new_batch; /* 1: waiting on first read complete */
115 int batch_data_dir; /* current batch REQ_SYNC / REQ_ASYNC */
116 int write_batch_count; /* max # of reqs in a write batch */
117 int current_write_count; /* how many requests left this batch */
118 int write_batch_idled; /* has the write batch gone idle? */
119 mempool_t *arq_pool;
120
121 enum anticipation_status antic_status;
122 unsigned long antic_start; /* jiffies: when it started */
123 struct timer_list antic_timer; /* anticipatory scheduling timer */
124 struct work_struct antic_work; /* Deferred unplugging */
125 struct io_context *io_context; /* Identify the expected process */
126 int ioc_finished; /* IO associated with io_context is finished */
127 int nr_dispatched;
128
129 /*
130 * settings that change how the i/o scheduler behaves
131 */
132 unsigned long fifo_expire[2];
133 unsigned long batch_expire[2];
134 unsigned long antic_expire;
135};
136
137#define list_entry_fifo(ptr) list_entry((ptr), struct as_rq, fifo)
138
139/*
140 * per-request data.
141 */
142enum arq_state {
143 AS_RQ_NEW=0, /* New - not referenced and not on any lists */
144 AS_RQ_QUEUED, /* In the request queue. It belongs to the
145 scheduler */
146 AS_RQ_DISPATCHED, /* On the dispatch list. It belongs to the
147 driver now */
148 AS_RQ_PRESCHED, /* Debug poisoning for requests being used */
149 AS_RQ_REMOVED,
150 AS_RQ_MERGED,
151 AS_RQ_POSTSCHED, /* when they shouldn't be */
152};
153
154struct as_rq {
155 /*
156 * rbtree index, key is the starting offset
157 */
158 struct rb_node rb_node;
159 sector_t rb_key;
160
161 struct request *request;
162
163 struct io_context *io_context; /* The submitting task */
164
165 /*
166 * request hash, key is the ending offset (for back merge lookup)
167 */
168 struct list_head hash;
169 unsigned int on_hash;
170
171 /*
172 * expire fifo
173 */
174 struct list_head fifo;
175 unsigned long expires;
176
177 unsigned int is_sync;
178 enum arq_state state;
179};
180
181#define RQ_DATA(rq) ((struct as_rq *) (rq)->elevator_private)
182
183static kmem_cache_t *arq_pool;
184
185/*
186 * IO Context helper functions
187 */
188
189/* Called to deallocate the as_io_context */
190static void free_as_io_context(struct as_io_context *aic)
191{
192 kfree(aic);
193}
194
195/* Called when the task exits */
196static void exit_as_io_context(struct as_io_context *aic)
197{
198 WARN_ON(!test_bit(AS_TASK_RUNNING, &aic->state));
199 clear_bit(AS_TASK_RUNNING, &aic->state);
200}
201
202static struct as_io_context *alloc_as_io_context(void)
203{
204 struct as_io_context *ret;
205
206 ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
207 if (ret) {
208 ret->dtor = free_as_io_context;
209 ret->exit = exit_as_io_context;
210 ret->state = 1 << AS_TASK_RUNNING;
211 atomic_set(&ret->nr_queued, 0);
212 atomic_set(&ret->nr_dispatched, 0);
213 spin_lock_init(&ret->lock);
214 ret->ttime_total = 0;
215 ret->ttime_samples = 0;
216 ret->ttime_mean = 0;
217 ret->seek_total = 0;
218 ret->seek_samples = 0;
219 ret->seek_mean = 0;
220 }
221
222 return ret;
223}
224
225/*
226 * If the current task has no AS IO context then create one and initialise it.
227 * Then take a ref on the task's io context and return it.
228 */
229static struct io_context *as_get_io_context(void)
230{
231 struct io_context *ioc = get_io_context(GFP_ATOMIC);
232 if (ioc && !ioc->aic) {
233 ioc->aic = alloc_as_io_context();
234 if (!ioc->aic) {
235 put_io_context(ioc);
236 ioc = NULL;
237 }
238 }
239 return ioc;
240}
241
242/*
243 * the back merge hash support functions
244 */
245static const int as_hash_shift = 6;
246#define AS_HASH_BLOCK(sec) ((sec) >> 3)
247#define AS_HASH_FN(sec) (hash_long(AS_HASH_BLOCK((sec)), as_hash_shift))
248#define AS_HASH_ENTRIES (1 << as_hash_shift)
249#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
250#define list_entry_hash(ptr) list_entry((ptr), struct as_rq, hash)
251
252static inline void __as_del_arq_hash(struct as_rq *arq)
253{
254 arq->on_hash = 0;
255 list_del_init(&arq->hash);
256}
257
258static inline void as_del_arq_hash(struct as_rq *arq)
259{
260 if (arq->on_hash)
261 __as_del_arq_hash(arq);
262}
263
264static void as_remove_merge_hints(request_queue_t *q, struct as_rq *arq)
265{
266 as_del_arq_hash(arq);
267
268 if (q->last_merge == arq->request)
269 q->last_merge = NULL;
270}
271
272static void as_add_arq_hash(struct as_data *ad, struct as_rq *arq)
273{
274 struct request *rq = arq->request;
275
276 BUG_ON(arq->on_hash);
277
278 arq->on_hash = 1;
279 list_add(&arq->hash, &ad->hash[AS_HASH_FN(rq_hash_key(rq))]);
280}
281
282/*
283 * move hot entry to front of chain
284 */
285static inline void as_hot_arq_hash(struct as_data *ad, struct as_rq *arq)
286{
287 struct request *rq = arq->request;
288 struct list_head *head = &ad->hash[AS_HASH_FN(rq_hash_key(rq))];
289
290 if (!arq->on_hash) {
291 WARN_ON(1);
292 return;
293 }
294
295 if (arq->hash.prev != head) {
296 list_del(&arq->hash);
297 list_add(&arq->hash, head);
298 }
299}
300
301static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
302{
303 struct list_head *hash_list = &ad->hash[AS_HASH_FN(offset)];
304 struct list_head *entry, *next = hash_list->next;
305
306 while ((entry = next) != hash_list) {
307 struct as_rq *arq = list_entry_hash(entry);
308 struct request *__rq = arq->request;
309
310 next = entry->next;
311
312 BUG_ON(!arq->on_hash);
313
314 if (!rq_mergeable(__rq)) {
315 as_remove_merge_hints(ad->q, arq);
316 continue;
317 }
318
319 if (rq_hash_key(__rq) == offset)
320 return __rq;
321 }
322
323 return NULL;
324}
325
326/*
327 * rb tree support functions
328 */
329#define RB_NONE (2)
330#define RB_EMPTY(root) ((root)->rb_node == NULL)
331#define ON_RB(node) ((node)->rb_color != RB_NONE)
332#define RB_CLEAR(node) ((node)->rb_color = RB_NONE)
333#define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node)
334#define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync])
335#define rq_rb_key(rq) (rq)->sector
336
337/*
338 * as_find_first_arq finds the first (lowest sector numbered) request
339 * for the specified data_dir. Used to sweep back to the start of the disk
340 * (1-way elevator) after we process the last (highest sector) request.
341 */
342static struct as_rq *as_find_first_arq(struct as_data *ad, int data_dir)
343{
344 struct rb_node *n = ad->sort_list[data_dir].rb_node;
345
346 if (n == NULL)
347 return NULL;
348
349 for (;;) {
350 if (n->rb_left == NULL)
351 return rb_entry_arq(n);
352
353 n = n->rb_left;
354 }
355}
356
357/*
358 * Add the request to the rb tree if it is unique. If there is an alias (an
359 * existing request against the same sector), which can happen when using
360 * direct IO, then return the alias.
361 */
362static struct as_rq *as_add_arq_rb(struct as_data *ad, struct as_rq *arq)
363{
364 struct rb_node **p = &ARQ_RB_ROOT(ad, arq)->rb_node;
365 struct rb_node *parent = NULL;
366 struct as_rq *__arq;
367 struct request *rq = arq->request;
368
369 arq->rb_key = rq_rb_key(rq);
370
371 while (*p) {
372 parent = *p;
373 __arq = rb_entry_arq(parent);
374
375 if (arq->rb_key < __arq->rb_key)
376 p = &(*p)->rb_left;
377 else if (arq->rb_key > __arq->rb_key)
378 p = &(*p)->rb_right;
379 else
380 return __arq;
381 }
382
383 rb_link_node(&arq->rb_node, parent, p);
384 rb_insert_color(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
385
386 return NULL;
387}
388
389static inline void as_del_arq_rb(struct as_data *ad, struct as_rq *arq)
390{
391 if (!ON_RB(&arq->rb_node)) {
392 WARN_ON(1);
393 return;
394 }
395
396 rb_erase(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
397 RB_CLEAR(&arq->rb_node);
398}
399
400static struct request *
401as_find_arq_rb(struct as_data *ad, sector_t sector, int data_dir)
402{
403 struct rb_node *n = ad->sort_list[data_dir].rb_node;
404 struct as_rq *arq;
405
406 while (n) {
407 arq = rb_entry_arq(n);
408
409 if (sector < arq->rb_key)
410 n = n->rb_left;
411 else if (sector > arq->rb_key)
412 n = n->rb_right;
413 else
414 return arq->request;
415 }
416
417 return NULL;
418}
419
420/*
421 * IO Scheduler proper
422 */
423
424#define MAXBACK (1024 * 1024) /*
425 * Maximum distance the disk will go backward
426 * for a request.
427 */
428
429#define BACK_PENALTY 2
430
431/*
432 * as_choose_req selects the preferred one of two requests of the same data_dir
433 * ignoring time - eg. timeouts, which is the job of as_dispatch_request
434 */
435static struct as_rq *
436as_choose_req(struct as_data *ad, struct as_rq *arq1, struct as_rq *arq2)
437{
438 int data_dir;
439 sector_t last, s1, s2, d1, d2;
440 int r1_wrap=0, r2_wrap=0; /* requests are behind the disk head */
441 const sector_t maxback = MAXBACK;
442
443 if (arq1 == NULL || arq1 == arq2)
444 return arq2;
445 if (arq2 == NULL)
446 return arq1;
447
448 data_dir = arq1->is_sync;
449
450 last = ad->last_sector[data_dir];
451 s1 = arq1->request->sector;
452 s2 = arq2->request->sector;
453
454 BUG_ON(data_dir != arq2->is_sync);
455
456 /*
457 * Strict one way elevator _except_ in the case where we allow
458 * short backward seeks which are biased as twice the cost of a
459 * similar forward seek.
460 */
461 if (s1 >= last)
462 d1 = s1 - last;
463 else if (s1+maxback >= last)
464 d1 = (last - s1)*BACK_PENALTY;
465 else {
466 r1_wrap = 1;
467 d1 = 0; /* shut up, gcc */
468 }
469
470 if (s2 >= last)
471 d2 = s2 - last;
472 else if (s2+maxback >= last)
473 d2 = (last - s2)*BACK_PENALTY;
474 else {
475 r2_wrap = 1;
476 d2 = 0;
477 }
478
479 /* Found required data */
480 if (!r1_wrap && r2_wrap)
481 return arq1;
482 else if (!r2_wrap && r1_wrap)
483 return arq2;
484 else if (r1_wrap && r2_wrap) {
485 /* both behind the head */
486 if (s1 <= s2)
487 return arq1;
488 else
489 return arq2;
490 }
491
492 /* Both requests in front of the head */
493 if (d1 < d2)
494 return arq1;
495 else if (d2 < d1)
496 return arq2;
497 else {
498 if (s1 >= s2)
499 return arq1;
500 else
501 return arq2;
502 }
503}
504
505/*
506 * as_find_next_arq finds the next request after @prev in elevator order.
507 * this with as_choose_req form the basis for how the scheduler chooses
508 * what request to process next. Anticipation works on top of this.
509 */
510static struct as_rq *as_find_next_arq(struct as_data *ad, struct as_rq *last)
511{
512 const int data_dir = last->is_sync;
513 struct as_rq *ret;
514 struct rb_node *rbnext = rb_next(&last->rb_node);
515 struct rb_node *rbprev = rb_prev(&last->rb_node);
516 struct as_rq *arq_next, *arq_prev;
517
518 BUG_ON(!ON_RB(&last->rb_node));
519
520 if (rbprev)
521 arq_prev = rb_entry_arq(rbprev);
522 else
523 arq_prev = NULL;
524
525 if (rbnext)
526 arq_next = rb_entry_arq(rbnext);
527 else {
528 arq_next = as_find_first_arq(ad, data_dir);
529 if (arq_next == last)
530 arq_next = NULL;
531 }
532
533 ret = as_choose_req(ad, arq_next, arq_prev);
534
535 return ret;
536}
537
538/*
539 * anticipatory scheduling functions follow
540 */
541
542/*
543 * as_antic_expired tells us when we have anticipated too long.
544 * The funny "absolute difference" math on the elapsed time is to handle
545 * jiffy wraps, and disks which have been idle for 0x80000000 jiffies.
546 */
547static int as_antic_expired(struct as_data *ad)
548{
549 long delta_jif;
550
551 delta_jif = jiffies - ad->antic_start;
552 if (unlikely(delta_jif < 0))
553 delta_jif = -delta_jif;
554 if (delta_jif < ad->antic_expire)
555 return 0;
556
557 return 1;
558}
559
560/*
561 * as_antic_waitnext starts anticipating that a nice request will soon be
562 * submitted. See also as_antic_waitreq
563 */
564static void as_antic_waitnext(struct as_data *ad)
565{
566 unsigned long timeout;
567
568 BUG_ON(ad->antic_status != ANTIC_OFF
569 && ad->antic_status != ANTIC_WAIT_REQ);
570
571 timeout = ad->antic_start + ad->antic_expire;
572
573 mod_timer(&ad->antic_timer, timeout);
574
575 ad->antic_status = ANTIC_WAIT_NEXT;
576}
577
578/*
579 * as_antic_waitreq starts anticipating. We don't start timing the anticipation
580 * until the request that we're anticipating on has finished. This means we
581 * are timing from when the candidate process wakes up hopefully.
582 */
583static void as_antic_waitreq(struct as_data *ad)
584{
585 BUG_ON(ad->antic_status == ANTIC_FINISHED);
586 if (ad->antic_status == ANTIC_OFF) {
587 if (!ad->io_context || ad->ioc_finished)
588 as_antic_waitnext(ad);
589 else
590 ad->antic_status = ANTIC_WAIT_REQ;
591 }
592}
593
594/*
595 * This is called directly by the functions in this file to stop anticipation.
596 * We kill the timer and schedule a call to the request_fn asap.
597 */
598static void as_antic_stop(struct as_data *ad)
599{
600 int status = ad->antic_status;
601
602 if (status == ANTIC_WAIT_REQ || status == ANTIC_WAIT_NEXT) {
603 if (status == ANTIC_WAIT_NEXT)
604 del_timer(&ad->antic_timer);
605 ad->antic_status = ANTIC_FINISHED;
606 /* see as_work_handler */
607 kblockd_schedule_work(&ad->antic_work);
608 }
609}
610
611/*
612 * as_antic_timeout is the timer function set by as_antic_waitnext.
613 */
614static void as_antic_timeout(unsigned long data)
615{
616 struct request_queue *q = (struct request_queue *)data;
617 struct as_data *ad = q->elevator->elevator_data;
618 unsigned long flags;
619
620 spin_lock_irqsave(q->queue_lock, flags);
621 if (ad->antic_status == ANTIC_WAIT_REQ
622 || ad->antic_status == ANTIC_WAIT_NEXT) {
623 struct as_io_context *aic = ad->io_context->aic;
624
625 ad->antic_status = ANTIC_FINISHED;
626 kblockd_schedule_work(&ad->antic_work);
627
628 if (aic->ttime_samples == 0) {
629 /* process anticipated on has exitted or timed out*/
630 ad->exit_prob = (7*ad->exit_prob + 256)/8;
631 }
632 }
633 spin_unlock_irqrestore(q->queue_lock, flags);
634}
635
636/*
637 * as_close_req decides if one request is considered "close" to the
638 * previous one issued.
639 */
640static int as_close_req(struct as_data *ad, struct as_rq *arq)
641{
642 unsigned long delay; /* milliseconds */
643 sector_t last = ad->last_sector[ad->batch_data_dir];
644 sector_t next = arq->request->sector;
645 sector_t delta; /* acceptable close offset (in sectors) */
646
647 if (ad->antic_status == ANTIC_OFF || !ad->ioc_finished)
648 delay = 0;
649 else
650 delay = ((jiffies - ad->antic_start) * 1000) / HZ;
651
652 if (delay <= 1)
653 delta = 64;
654 else if (delay <= 20 && delay <= ad->antic_expire)
655 delta = 64 << (delay-1);
656 else
657 return 1;
658
659 return (last - (delta>>1) <= next) && (next <= last + delta);
660}
661
662/*
663 * as_can_break_anticipation returns true if we have been anticipating this
664 * request.
665 *
666 * It also returns true if the process against which we are anticipating
667 * submits a write - that's presumably an fsync, O_SYNC write, etc. We want to
668 * dispatch it ASAP, because we know that application will not be submitting
669 * any new reads.
670 *
671 * If the task which has submitted the request has exitted, break anticipation.
672 *
673 * If this task has queued some other IO, do not enter enticipation.
674 */
675static int as_can_break_anticipation(struct as_data *ad, struct as_rq *arq)
676{
677 struct io_context *ioc;
678 struct as_io_context *aic;
679 sector_t s;
680
681 ioc = ad->io_context;
682 BUG_ON(!ioc);
683
684 if (arq && ioc == arq->io_context) {
685 /* request from same process */
686 return 1;
687 }
688
689 if (ad->ioc_finished && as_antic_expired(ad)) {
690 /*
691 * In this situation status should really be FINISHED,
692 * however the timer hasn't had the chance to run yet.
693 */
694 return 1;
695 }
696
697 aic = ioc->aic;
698 if (!aic)
699 return 0;
700
701 if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
702 /* process anticipated on has exitted */
703 if (aic->ttime_samples == 0)
704 ad->exit_prob = (7*ad->exit_prob + 256)/8;
705 return 1;
706 }
707
708 if (atomic_read(&aic->nr_queued) > 0) {
709 /* process has more requests queued */
710 return 1;
711 }
712
713 if (atomic_read(&aic->nr_dispatched) > 0) {
714 /* process has more requests dispatched */
715 return 1;
716 }
717
718 if (arq && arq->is_sync == REQ_SYNC && as_close_req(ad, arq)) {
719 /*
720 * Found a close request that is not one of ours.
721 *
722 * This makes close requests from another process reset
723 * our thinktime delay. Is generally useful when there are
724 * two or more cooperating processes working in the same
725 * area.
726 */
727 spin_lock(&aic->lock);
728 aic->last_end_request = jiffies;
729 spin_unlock(&aic->lock);
730 return 1;
731 }
732
733
734 if (aic->ttime_samples == 0) {
735 if (ad->new_ttime_mean > ad->antic_expire)
736 return 1;
737 if (ad->exit_prob > 128)
738 return 1;
739 } else if (aic->ttime_mean > ad->antic_expire) {
740 /* the process thinks too much between requests */
741 return 1;
742 }
743
744 if (!arq)
745 return 0;
746
747 if (ad->last_sector[REQ_SYNC] < arq->request->sector)
748 s = arq->request->sector - ad->last_sector[REQ_SYNC];
749 else
750 s = ad->last_sector[REQ_SYNC] - arq->request->sector;
751
752 if (aic->seek_samples == 0) {
753 /*
754 * Process has just started IO. Use past statistics to
755 * guage success possibility
756 */
757 if (ad->new_seek_mean > s) {
758 /* this request is better than what we're expecting */
759 return 1;
760 }
761
762 } else {
763 if (aic->seek_mean > s) {
764 /* this request is better than what we're expecting */
765 return 1;
766 }
767 }
768
769 return 0;
770}
771
772/*
773 * as_can_anticipate indicates weather we should either run arq
774 * or keep anticipating a better request.
775 */
776static int as_can_anticipate(struct as_data *ad, struct as_rq *arq)
777{
778 if (!ad->io_context)
779 /*
780 * Last request submitted was a write
781 */
782 return 0;
783
784 if (ad->antic_status == ANTIC_FINISHED)
785 /*
786 * Don't restart if we have just finished. Run the next request
787 */
788 return 0;
789
790 if (as_can_break_anticipation(ad, arq))
791 /*
792 * This request is a good candidate. Don't keep anticipating,
793 * run it.
794 */
795 return 0;
796
797 /*
798 * OK from here, we haven't finished, and don't have a decent request!
799 * Status is either ANTIC_OFF so start waiting,
800 * ANTIC_WAIT_REQ so continue waiting for request to finish
801 * or ANTIC_WAIT_NEXT so continue waiting for an acceptable request.
802 *
803 */
804
805 return 1;
806}
807
808static void as_update_thinktime(struct as_data *ad, struct as_io_context *aic, unsigned long ttime)
809{
810 /* fixed point: 1.0 == 1<<8 */
811 if (aic->ttime_samples == 0) {
812 ad->new_ttime_total = (7*ad->new_ttime_total + 256*ttime) / 8;
813 ad->new_ttime_mean = ad->new_ttime_total / 256;
814
815 ad->exit_prob = (7*ad->exit_prob)/8;
816 }
817 aic->ttime_samples = (7*aic->ttime_samples + 256) / 8;
818 aic->ttime_total = (7*aic->ttime_total + 256*ttime) / 8;
819 aic->ttime_mean = (aic->ttime_total + 128) / aic->ttime_samples;
820}
821
822static void as_update_seekdist(struct as_data *ad, struct as_io_context *aic, sector_t sdist)
823{
824 u64 total;
825
826 if (aic->seek_samples == 0) {
827 ad->new_seek_total = (7*ad->new_seek_total + 256*(u64)sdist)/8;
828 ad->new_seek_mean = ad->new_seek_total / 256;
829 }
830
831 /*
832 * Don't allow the seek distance to get too large from the
833 * odd fragment, pagein, etc
834 */
835 if (aic->seek_samples <= 60) /* second&third seek */
836 sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*1024);
837 else
838 sdist = min(sdist, (aic->seek_mean * 4) + 2*1024*64);
839
840 aic->seek_samples = (7*aic->seek_samples + 256) / 8;
841 aic->seek_total = (7*aic->seek_total + (u64)256*sdist) / 8;
842 total = aic->seek_total + (aic->seek_samples/2);
843 do_div(total, aic->seek_samples);
844 aic->seek_mean = (sector_t)total;
845}
846
847/*
848 * as_update_iohist keeps a decaying histogram of IO thinktimes, and
849 * updates @aic->ttime_mean based on that. It is called when a new
850 * request is queued.
851 */
852static void as_update_iohist(struct as_data *ad, struct as_io_context *aic, struct request *rq)
853{
854 struct as_rq *arq = RQ_DATA(rq);
855 int data_dir = arq->is_sync;
856 unsigned long thinktime;
857 sector_t seek_dist;
858
859 if (aic == NULL)
860 return;
861
862 if (data_dir == REQ_SYNC) {
863 unsigned long in_flight = atomic_read(&aic->nr_queued)
864 + atomic_read(&aic->nr_dispatched);
865 spin_lock(&aic->lock);
866 if (test_bit(AS_TASK_IORUNNING, &aic->state) ||
867 test_bit(AS_TASK_IOSTARTED, &aic->state)) {
868 /* Calculate read -> read thinktime */
869 if (test_bit(AS_TASK_IORUNNING, &aic->state)
870 && in_flight == 0) {
871 thinktime = jiffies - aic->last_end_request;
872 thinktime = min(thinktime, MAX_THINKTIME-1);
873 } else
874 thinktime = 0;
875 as_update_thinktime(ad, aic, thinktime);
876
877 /* Calculate read -> read seek distance */
878 if (aic->last_request_pos < rq->sector)
879 seek_dist = rq->sector - aic->last_request_pos;
880 else
881 seek_dist = aic->last_request_pos - rq->sector;
882 as_update_seekdist(ad, aic, seek_dist);
883 }
884 aic->last_request_pos = rq->sector + rq->nr_sectors;
885 set_bit(AS_TASK_IOSTARTED, &aic->state);
886 spin_unlock(&aic->lock);
887 }
888}
889
890/*
891 * as_update_arq must be called whenever a request (arq) is added to
892 * the sort_list. This function keeps caches up to date, and checks if the
893 * request might be one we are "anticipating"
894 */
895static void as_update_arq(struct as_data *ad, struct as_rq *arq)
896{
897 const int data_dir = arq->is_sync;
898
899 /* keep the next_arq cache up to date */
900 ad->next_arq[data_dir] = as_choose_req(ad, arq, ad->next_arq[data_dir]);
901
902 /*
903 * have we been anticipating this request?
904 * or does it come from the same process as the one we are anticipating
905 * for?
906 */
907 if (ad->antic_status == ANTIC_WAIT_REQ
908 || ad->antic_status == ANTIC_WAIT_NEXT) {
909 if (as_can_break_anticipation(ad, arq))
910 as_antic_stop(ad);
911 }
912}
913
914/*
915 * Gathers timings and resizes the write batch automatically
916 */
917static void update_write_batch(struct as_data *ad)
918{
919 unsigned long batch = ad->batch_expire[REQ_ASYNC];
920 long write_time;
921
922 write_time = (jiffies - ad->current_batch_expires) + batch;
923 if (write_time < 0)
924 write_time = 0;
925
926 if (write_time > batch && !ad->write_batch_idled) {
927 if (write_time > batch * 3)
928 ad->write_batch_count /= 2;
929 else
930 ad->write_batch_count--;
931 } else if (write_time < batch && ad->current_write_count == 0) {
932 if (batch > write_time * 3)
933 ad->write_batch_count *= 2;
934 else
935 ad->write_batch_count++;
936 }
937
938 if (ad->write_batch_count < 1)
939 ad->write_batch_count = 1;
940}
941
942/*
943 * as_completed_request is to be called when a request has completed and
944 * returned something to the requesting process, be it an error or data.
945 */
946static void as_completed_request(request_queue_t *q, struct request *rq)
947{
948 struct as_data *ad = q->elevator->elevator_data;
949 struct as_rq *arq = RQ_DATA(rq);
950
951 WARN_ON(!list_empty(&rq->queuelist));
952
953 if (arq->state == AS_RQ_PRESCHED) {
954 WARN_ON(arq->io_context);
955 goto out;
956 }
957
958 if (arq->state == AS_RQ_MERGED)
959 goto out_ioc;
960
961 if (arq->state != AS_RQ_REMOVED) {
962 printk("arq->state %d\n", arq->state);
963 WARN_ON(1);
964 goto out;
965 }
966
967 if (!blk_fs_request(rq))
968 goto out;
969
970 if (ad->changed_batch && ad->nr_dispatched == 1) {
971 kblockd_schedule_work(&ad->antic_work);
972 ad->changed_batch = 0;
973
974 if (ad->batch_data_dir == REQ_SYNC)
975 ad->new_batch = 1;
976 }
977 WARN_ON(ad->nr_dispatched == 0);
978 ad->nr_dispatched--;
979
980 /*
981 * Start counting the batch from when a request of that direction is
982 * actually serviced. This should help devices with big TCQ windows
983 * and writeback caches
984 */
985 if (ad->new_batch && ad->batch_data_dir == arq->is_sync) {
986 update_write_batch(ad);
987 ad->current_batch_expires = jiffies +
988 ad->batch_expire[REQ_SYNC];
989 ad->new_batch = 0;
990 }
991
992 if (ad->io_context == arq->io_context && ad->io_context) {
993 ad->antic_start = jiffies;
994 ad->ioc_finished = 1;
995 if (ad->antic_status == ANTIC_WAIT_REQ) {
996 /*
997 * We were waiting on this request, now anticipate
998 * the next one
999 */
1000 as_antic_waitnext(ad);
1001 }
1002 }
1003
1004out_ioc:
1005 if (!arq->io_context)
1006 goto out;
1007
1008 if (arq->is_sync == REQ_SYNC) {
1009 struct as_io_context *aic = arq->io_context->aic;
1010 if (aic) {
1011 spin_lock(&aic->lock);
1012 set_bit(AS_TASK_IORUNNING, &aic->state);
1013 aic->last_end_request = jiffies;
1014 spin_unlock(&aic->lock);
1015 }
1016 }
1017
1018 put_io_context(arq->io_context);
1019out:
1020 arq->state = AS_RQ_POSTSCHED;
1021}
1022
1023/*
1024 * as_remove_queued_request removes a request from the pre dispatch queue
1025 * without updating refcounts. It is expected the caller will drop the
1026 * reference unless it replaces the request at somepart of the elevator
1027 * (ie. the dispatch queue)
1028 */
1029static void as_remove_queued_request(request_queue_t *q, struct request *rq)
1030{
1031 struct as_rq *arq = RQ_DATA(rq);
1032 const int data_dir = arq->is_sync;
1033 struct as_data *ad = q->elevator->elevator_data;
1034
1035 WARN_ON(arq->state != AS_RQ_QUEUED);
1036
1037 if (arq->io_context && arq->io_context->aic) {
1038 BUG_ON(!atomic_read(&arq->io_context->aic->nr_queued));
1039 atomic_dec(&arq->io_context->aic->nr_queued);
1040 }
1041
1042 /*
1043 * Update the "next_arq" cache if we are about to remove its
1044 * entry
1045 */
1046 if (ad->next_arq[data_dir] == arq)
1047 ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
1048
1049 list_del_init(&arq->fifo);
1050 as_remove_merge_hints(q, arq);
1051 as_del_arq_rb(ad, arq);
1052}
1053
1054/*
1055 * as_remove_dispatched_request is called to remove a request which has gone
1056 * to the dispatch list.
1057 */
1058static void as_remove_dispatched_request(request_queue_t *q, struct request *rq)
1059{
1060 struct as_rq *arq = RQ_DATA(rq);
1061 struct as_io_context *aic;
1062
1063 if (!arq) {
1064 WARN_ON(1);
1065 return;
1066 }
1067
1068 WARN_ON(arq->state != AS_RQ_DISPATCHED);
1069 WARN_ON(ON_RB(&arq->rb_node));
1070 if (arq->io_context && arq->io_context->aic) {
1071 aic = arq->io_context->aic;
1072 if (aic) {
1073 WARN_ON(!atomic_read(&aic->nr_dispatched));
1074 atomic_dec(&aic->nr_dispatched);
1075 }
1076 }
1077}
1078
1079/*
1080 * as_remove_request is called when a driver has finished with a request.
1081 * This should be only called for dispatched requests, but for some reason
1082 * a POWER4 box running hwscan it does not.
1083 */
1084static void as_remove_request(request_queue_t *q, struct request *rq)
1085{
1086 struct as_rq *arq = RQ_DATA(rq);
1087
1088 if (unlikely(arq->state == AS_RQ_NEW))
1089 goto out;
1090
1091 if (ON_RB(&arq->rb_node)) {
1092 if (arq->state != AS_RQ_QUEUED) {
1093 printk("arq->state %d\n", arq->state);
1094 WARN_ON(1);
1095 goto out;
1096 }
1097 /*
1098 * We'll lose the aliased request(s) here. I don't think this
1099 * will ever happen, but if it does, hopefully someone will
1100 * report it.
1101 */
1102 WARN_ON(!list_empty(&rq->queuelist));
1103 as_remove_queued_request(q, rq);
1104 } else {
1105 if (arq->state != AS_RQ_DISPATCHED) {
1106 printk("arq->state %d\n", arq->state);
1107 WARN_ON(1);
1108 goto out;
1109 }
1110 as_remove_dispatched_request(q, rq);
1111 }
1112out:
1113 arq->state = AS_RQ_REMOVED;
1114}
1115
1116/*
1117 * as_fifo_expired returns 0 if there are no expired reads on the fifo,
1118 * 1 otherwise. It is ratelimited so that we only perform the check once per
1119 * `fifo_expire' interval. Otherwise a large number of expired requests
1120 * would create a hopeless seekstorm.
1121 *
1122 * See as_antic_expired comment.
1123 */
1124static int as_fifo_expired(struct as_data *ad, int adir)
1125{
1126 struct as_rq *arq;
1127 long delta_jif;
1128
1129 delta_jif = jiffies - ad->last_check_fifo[adir];
1130 if (unlikely(delta_jif < 0))
1131 delta_jif = -delta_jif;
1132 if (delta_jif < ad->fifo_expire[adir])
1133 return 0;
1134
1135 ad->last_check_fifo[adir] = jiffies;
1136
1137 if (list_empty(&ad->fifo_list[adir]))
1138 return 0;
1139
1140 arq = list_entry_fifo(ad->fifo_list[adir].next);
1141
1142 return time_after(jiffies, arq->expires);
1143}
1144
1145/*
1146 * as_batch_expired returns true if the current batch has expired. A batch
1147 * is a set of reads or a set of writes.
1148 */
1149static inline int as_batch_expired(struct as_data *ad)
1150{
1151 if (ad->changed_batch || ad->new_batch)
1152 return 0;
1153
1154 if (ad->batch_data_dir == REQ_SYNC)
1155 /* TODO! add a check so a complete fifo gets written? */
1156 return time_after(jiffies, ad->current_batch_expires);
1157
1158 return time_after(jiffies, ad->current_batch_expires)
1159 || ad->current_write_count == 0;
1160}
1161
1162/*
1163 * move an entry to dispatch queue
1164 */
1165static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq)
1166{
1167 struct request *rq = arq->request;
1168 struct list_head *insert;
1169 const int data_dir = arq->is_sync;
1170
1171 BUG_ON(!ON_RB(&arq->rb_node));
1172
1173 as_antic_stop(ad);
1174 ad->antic_status = ANTIC_OFF;
1175
1176 /*
1177 * This has to be set in order to be correctly updated by
1178 * as_find_next_arq
1179 */
1180 ad->last_sector[data_dir] = rq->sector + rq->nr_sectors;
1181
1182 if (data_dir == REQ_SYNC) {
1183 /* In case we have to anticipate after this */
1184 copy_io_context(&ad->io_context, &arq->io_context);
1185 } else {
1186 if (ad->io_context) {
1187 put_io_context(ad->io_context);
1188 ad->io_context = NULL;
1189 }
1190
1191 if (ad->current_write_count != 0)
1192 ad->current_write_count--;
1193 }
1194 ad->ioc_finished = 0;
1195
1196 ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
1197
1198 /*
1199 * take it off the sort and fifo list, add to dispatch queue
1200 */
1201 insert = ad->dispatch->prev;
1202
1203 while (!list_empty(&rq->queuelist)) {
1204 struct request *__rq = list_entry_rq(rq->queuelist.next);
1205 struct as_rq *__arq = RQ_DATA(__rq);
1206
1207 list_move_tail(&__rq->queuelist, ad->dispatch);
1208
1209 if (__arq->io_context && __arq->io_context->aic)
1210 atomic_inc(&__arq->io_context->aic->nr_dispatched);
1211
1212 WARN_ON(__arq->state != AS_RQ_QUEUED);
1213 __arq->state = AS_RQ_DISPATCHED;
1214
1215 ad->nr_dispatched++;
1216 }
1217
1218 as_remove_queued_request(ad->q, rq);
1219 WARN_ON(arq->state != AS_RQ_QUEUED);
1220
1221 list_add(&rq->queuelist, insert);
1222 arq->state = AS_RQ_DISPATCHED;
1223 if (arq->io_context && arq->io_context->aic)
1224 atomic_inc(&arq->io_context->aic->nr_dispatched);
1225 ad->nr_dispatched++;
1226}
1227
1228/*
1229 * as_dispatch_request selects the best request according to
1230 * read/write expire, batch expire, etc, and moves it to the dispatch
1231 * queue. Returns 1 if a request was found, 0 otherwise.
1232 */
1233static int as_dispatch_request(struct as_data *ad)
1234{
1235 struct as_rq *arq;
1236 const int reads = !list_empty(&ad->fifo_list[REQ_SYNC]);
1237 const int writes = !list_empty(&ad->fifo_list[REQ_ASYNC]);
1238
1239 /* Signal that the write batch was uncontended, so we can't time it */
1240 if (ad->batch_data_dir == REQ_ASYNC && !reads) {
1241 if (ad->current_write_count == 0 || !writes)
1242 ad->write_batch_idled = 1;
1243 }
1244
1245 if (!(reads || writes)
1246 || ad->antic_status == ANTIC_WAIT_REQ
1247 || ad->antic_status == ANTIC_WAIT_NEXT
1248 || ad->changed_batch)
1249 return 0;
1250
1251 if (!(reads && writes && as_batch_expired(ad)) ) {
1252 /*
1253 * batch is still running or no reads or no writes
1254 */
1255 arq = ad->next_arq[ad->batch_data_dir];
1256
1257 if (ad->batch_data_dir == REQ_SYNC && ad->antic_expire) {
1258 if (as_fifo_expired(ad, REQ_SYNC))
1259 goto fifo_expired;
1260
1261 if (as_can_anticipate(ad, arq)) {
1262 as_antic_waitreq(ad);
1263 return 0;
1264 }
1265 }
1266
1267 if (arq) {
1268 /* we have a "next request" */
1269 if (reads && !writes)
1270 ad->current_batch_expires =
1271 jiffies + ad->batch_expire[REQ_SYNC];
1272 goto dispatch_request;
1273 }
1274 }
1275
1276 /*
1277 * at this point we are not running a batch. select the appropriate
1278 * data direction (read / write)
1279 */
1280
1281 if (reads) {
1282 BUG_ON(RB_EMPTY(&ad->sort_list[REQ_SYNC]));
1283
1284 if (writes && ad->batch_data_dir == REQ_SYNC)
1285 /*
1286 * Last batch was a read, switch to writes
1287 */
1288 goto dispatch_writes;
1289
1290 if (ad->batch_data_dir == REQ_ASYNC) {
1291 WARN_ON(ad->new_batch);
1292 ad->changed_batch = 1;
1293 }
1294 ad->batch_data_dir = REQ_SYNC;
1295 arq = list_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
1296 ad->last_check_fifo[ad->batch_data_dir] = jiffies;
1297 goto dispatch_request;
1298 }
1299
1300 /*
1301 * the last batch was a read
1302 */
1303
1304 if (writes) {
1305dispatch_writes:
1306 BUG_ON(RB_EMPTY(&ad->sort_list[REQ_ASYNC]));
1307
1308 if (ad->batch_data_dir == REQ_SYNC) {
1309 ad->changed_batch = 1;
1310
1311 /*
1312 * new_batch might be 1 when the queue runs out of
1313 * reads. A subsequent submission of a write might
1314 * cause a change of batch before the read is finished.
1315 */
1316 ad->new_batch = 0;
1317 }
1318 ad->batch_data_dir = REQ_ASYNC;
1319 ad->current_write_count = ad->write_batch_count;
1320 ad->write_batch_idled = 0;
1321 arq = ad->next_arq[ad->batch_data_dir];
1322 goto dispatch_request;
1323 }
1324
1325 BUG();
1326 return 0;
1327
1328dispatch_request:
1329 /*
1330 * If a request has expired, service it.
1331 */
1332
1333 if (as_fifo_expired(ad, ad->batch_data_dir)) {
1334fifo_expired:
1335 arq = list_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
1336 BUG_ON(arq == NULL);
1337 }
1338
1339 if (ad->changed_batch) {
1340 WARN_ON(ad->new_batch);
1341
1342 if (ad->nr_dispatched)
1343 return 0;
1344
1345 if (ad->batch_data_dir == REQ_ASYNC)
1346 ad->current_batch_expires = jiffies +
1347 ad->batch_expire[REQ_ASYNC];
1348 else
1349 ad->new_batch = 1;
1350
1351 ad->changed_batch = 0;
1352 }
1353
1354 /*
1355 * arq is the selected appropriate request.
1356 */
1357 as_move_to_dispatch(ad, arq);
1358
1359 return 1;
1360}
1361
1362static struct request *as_next_request(request_queue_t *q)
1363{
1364 struct as_data *ad = q->elevator->elevator_data;
1365 struct request *rq = NULL;
1366
1367 /*
1368 * if there are still requests on the dispatch queue, grab the first
1369 */
1370 if (!list_empty(ad->dispatch) || as_dispatch_request(ad))
1371 rq = list_entry_rq(ad->dispatch->next);
1372
1373 return rq;
1374}
1375
1376/*
1377 * Add arq to a list behind alias
1378 */
1379static inline void
1380as_add_aliased_request(struct as_data *ad, struct as_rq *arq, struct as_rq *alias)
1381{
1382 struct request *req = arq->request;
1383 struct list_head *insert = alias->request->queuelist.prev;
1384
1385 /*
1386 * Transfer list of aliases
1387 */
1388 while (!list_empty(&req->queuelist)) {
1389 struct request *__rq = list_entry_rq(req->queuelist.next);
1390 struct as_rq *__arq = RQ_DATA(__rq);
1391
1392 list_move_tail(&__rq->queuelist, &alias->request->queuelist);
1393
1394 WARN_ON(__arq->state != AS_RQ_QUEUED);
1395 }
1396
1397 /*
1398 * Another request with the same start sector on the rbtree.
1399 * Link this request to that sector. They are untangled in
1400 * as_move_to_dispatch
1401 */
1402 list_add(&arq->request->queuelist, insert);
1403
1404 /*
1405 * Don't want to have to handle merges.
1406 */
1407 as_remove_merge_hints(ad->q, arq);
1408}
1409
1410/*
1411 * add arq to rbtree and fifo
1412 */
1413static void as_add_request(struct as_data *ad, struct as_rq *arq)
1414{
1415 struct as_rq *alias;
1416 int data_dir;
1417
1418 if (rq_data_dir(arq->request) == READ
1419 || current->flags&PF_SYNCWRITE)
1420 arq->is_sync = 1;
1421 else
1422 arq->is_sync = 0;
1423 data_dir = arq->is_sync;
1424
1425 arq->io_context = as_get_io_context();
1426
1427 if (arq->io_context) {
1428 as_update_iohist(ad, arq->io_context->aic, arq->request);
1429 atomic_inc(&arq->io_context->aic->nr_queued);
1430 }
1431
1432 alias = as_add_arq_rb(ad, arq);
1433 if (!alias) {
1434 /*
1435 * set expire time (only used for reads) and add to fifo list
1436 */
1437 arq->expires = jiffies + ad->fifo_expire[data_dir];
1438 list_add_tail(&arq->fifo, &ad->fifo_list[data_dir]);
1439
1440 if (rq_mergeable(arq->request)) {
1441 as_add_arq_hash(ad, arq);
1442
1443 if (!ad->q->last_merge)
1444 ad->q->last_merge = arq->request;
1445 }
1446 as_update_arq(ad, arq); /* keep state machine up to date */
1447
1448 } else {
1449 as_add_aliased_request(ad, arq, alias);
1450
1451 /*
1452 * have we been anticipating this request?
1453 * or does it come from the same process as the one we are
1454 * anticipating for?
1455 */
1456 if (ad->antic_status == ANTIC_WAIT_REQ
1457 || ad->antic_status == ANTIC_WAIT_NEXT) {
1458 if (as_can_break_anticipation(ad, arq))
1459 as_antic_stop(ad);
1460 }
1461 }
1462
1463 arq->state = AS_RQ_QUEUED;
1464}
1465
1466static void as_deactivate_request(request_queue_t *q, struct request *rq)
1467{
1468 struct as_data *ad = q->elevator->elevator_data;
1469 struct as_rq *arq = RQ_DATA(rq);
1470
1471 if (arq) {
1472 if (arq->state == AS_RQ_REMOVED) {
1473 arq->state = AS_RQ_DISPATCHED;
1474 if (arq->io_context && arq->io_context->aic)
1475 atomic_inc(&arq->io_context->aic->nr_dispatched);
1476 }
1477 } else
1478 WARN_ON(blk_fs_request(rq)
1479 && (!(rq->flags & (REQ_HARDBARRIER|REQ_SOFTBARRIER))) );
1480
1481 /* Stop anticipating - let this request get through */
1482 as_antic_stop(ad);
1483}
1484
1485/*
1486 * requeue the request. The request has not been completed, nor is it a
1487 * new request, so don't touch accounting.
1488 */
1489static void as_requeue_request(request_queue_t *q, struct request *rq)
1490{
1491 as_deactivate_request(q, rq);
1492 list_add(&rq->queuelist, &q->queue_head);
1493}
1494
1495/*
1496 * Account a request that is inserted directly onto the dispatch queue.
1497 * arq->io_context->aic->nr_dispatched should not need to be incremented
1498 * because only new requests should come through here: requeues go through
1499 * our explicit requeue handler.
1500 */
1501static void as_account_queued_request(struct as_data *ad, struct request *rq)
1502{
1503 if (blk_fs_request(rq)) {
1504 struct as_rq *arq = RQ_DATA(rq);
1505 arq->state = AS_RQ_DISPATCHED;
1506 ad->nr_dispatched++;
1507 }
1508}
1509
1510static void
1511as_insert_request(request_queue_t *q, struct request *rq, int where)
1512{
1513 struct as_data *ad = q->elevator->elevator_data;
1514 struct as_rq *arq = RQ_DATA(rq);
1515
1516 if (arq) {
1517 if (arq->state != AS_RQ_PRESCHED) {
1518 printk("arq->state: %d\n", arq->state);
1519 WARN_ON(1);
1520 }
1521 arq->state = AS_RQ_NEW;
1522 }
1523
1524 /* barriers must flush the reorder queue */
1525 if (unlikely(rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)
1526 && where == ELEVATOR_INSERT_SORT)) {
1527 WARN_ON(1);
1528 where = ELEVATOR_INSERT_BACK;
1529 }
1530
1531 switch (where) {
1532 case ELEVATOR_INSERT_BACK:
1533 while (ad->next_arq[REQ_SYNC])
1534 as_move_to_dispatch(ad, ad->next_arq[REQ_SYNC]);
1535
1536 while (ad->next_arq[REQ_ASYNC])
1537 as_move_to_dispatch(ad, ad->next_arq[REQ_ASYNC]);
1538
1539 list_add_tail(&rq->queuelist, ad->dispatch);
1540 as_account_queued_request(ad, rq);
1541 as_antic_stop(ad);
1542 break;
1543 case ELEVATOR_INSERT_FRONT:
1544 list_add(&rq->queuelist, ad->dispatch);
1545 as_account_queued_request(ad, rq);
1546 as_antic_stop(ad);
1547 break;
1548 case ELEVATOR_INSERT_SORT:
1549 BUG_ON(!blk_fs_request(rq));
1550 as_add_request(ad, arq);
1551 break;
1552 default:
1553 BUG();
1554 return;
1555 }
1556}
1557
1558/*
1559 * as_queue_empty tells us if there are requests left in the device. It may
1560 * not be the case that a driver can get the next request even if the queue
1561 * is not empty - it is used in the block layer to check for plugging and
1562 * merging opportunities
1563 */
1564static int as_queue_empty(request_queue_t *q)
1565{
1566 struct as_data *ad = q->elevator->elevator_data;
1567
1568 if (!list_empty(&ad->fifo_list[REQ_ASYNC])
1569 || !list_empty(&ad->fifo_list[REQ_SYNC])
1570 || !list_empty(ad->dispatch))
1571 return 0;
1572
1573 return 1;
1574}
1575
1576static struct request *
1577as_former_request(request_queue_t *q, struct request *rq)
1578{
1579 struct as_rq *arq = RQ_DATA(rq);
1580 struct rb_node *rbprev = rb_prev(&arq->rb_node);
1581 struct request *ret = NULL;
1582
1583 if (rbprev)
1584 ret = rb_entry_arq(rbprev)->request;
1585
1586 return ret;
1587}
1588
1589static struct request *
1590as_latter_request(request_queue_t *q, struct request *rq)
1591{
1592 struct as_rq *arq = RQ_DATA(rq);
1593 struct rb_node *rbnext = rb_next(&arq->rb_node);
1594 struct request *ret = NULL;
1595
1596 if (rbnext)
1597 ret = rb_entry_arq(rbnext)->request;
1598
1599 return ret;
1600}
1601
1602static int
1603as_merge(request_queue_t *q, struct request **req, struct bio *bio)
1604{
1605 struct as_data *ad = q->elevator->elevator_data;
1606 sector_t rb_key = bio->bi_sector + bio_sectors(bio);
1607 struct request *__rq;
1608 int ret;
1609
1610 /*
1611 * try last_merge to avoid going to hash
1612 */
1613 ret = elv_try_last_merge(q, bio);
1614 if (ret != ELEVATOR_NO_MERGE) {
1615 __rq = q->last_merge;
1616 goto out_insert;
1617 }
1618
1619 /*
1620 * see if the merge hash can satisfy a back merge
1621 */
1622 __rq = as_find_arq_hash(ad, bio->bi_sector);
1623 if (__rq) {
1624 BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
1625
1626 if (elv_rq_merge_ok(__rq, bio)) {
1627 ret = ELEVATOR_BACK_MERGE;
1628 goto out;
1629 }
1630 }
1631
1632 /*
1633 * check for front merge
1634 */
1635 __rq = as_find_arq_rb(ad, rb_key, bio_data_dir(bio));
1636 if (__rq) {
1637 BUG_ON(rb_key != rq_rb_key(__rq));
1638
1639 if (elv_rq_merge_ok(__rq, bio)) {
1640 ret = ELEVATOR_FRONT_MERGE;
1641 goto out;
1642 }
1643 }
1644
1645 return ELEVATOR_NO_MERGE;
1646out:
1647 if (rq_mergeable(__rq))
1648 q->last_merge = __rq;
1649out_insert:
1650 if (ret) {
1651 if (rq_mergeable(__rq))
1652 as_hot_arq_hash(ad, RQ_DATA(__rq));
1653 }
1654 *req = __rq;
1655 return ret;
1656}
1657
1658static void as_merged_request(request_queue_t *q, struct request *req)
1659{
1660 struct as_data *ad = q->elevator->elevator_data;
1661 struct as_rq *arq = RQ_DATA(req);
1662
1663 /*
1664 * hash always needs to be repositioned, key is end sector
1665 */
1666 as_del_arq_hash(arq);
1667 as_add_arq_hash(ad, arq);
1668
1669 /*
1670 * if the merge was a front merge, we need to reposition request
1671 */
1672 if (rq_rb_key(req) != arq->rb_key) {
1673 struct as_rq *alias, *next_arq = NULL;
1674
1675 if (ad->next_arq[arq->is_sync] == arq)
1676 next_arq = as_find_next_arq(ad, arq);
1677
1678 /*
1679 * Note! We should really be moving any old aliased requests
1680 * off this request and try to insert them into the rbtree. We
1681 * currently don't bother. Ditto the next function.
1682 */
1683 as_del_arq_rb(ad, arq);
1684 if ((alias = as_add_arq_rb(ad, arq)) ) {
1685 list_del_init(&arq->fifo);
1686 as_add_aliased_request(ad, arq, alias);
1687 if (next_arq)
1688 ad->next_arq[arq->is_sync] = next_arq;
1689 }
1690 /*
1691 * Note! At this stage of this and the next function, our next
1692 * request may not be optimal - eg the request may have "grown"
1693 * behind the disk head. We currently don't bother adjusting.
1694 */
1695 }
1696
1697 if (arq->on_hash)
1698 q->last_merge = req;
1699}
1700
1701static void
1702as_merged_requests(request_queue_t *q, struct request *req,
1703 struct request *next)
1704{
1705 struct as_data *ad = q->elevator->elevator_data;
1706 struct as_rq *arq = RQ_DATA(req);
1707 struct as_rq *anext = RQ_DATA(next);
1708
1709 BUG_ON(!arq);
1710 BUG_ON(!anext);
1711
1712 /*
1713 * reposition arq (this is the merged request) in hash, and in rbtree
1714 * in case of a front merge
1715 */
1716 as_del_arq_hash(arq);
1717 as_add_arq_hash(ad, arq);
1718
1719 if (rq_rb_key(req) != arq->rb_key) {
1720 struct as_rq *alias, *next_arq = NULL;
1721
1722 if (ad->next_arq[arq->is_sync] == arq)
1723 next_arq = as_find_next_arq(ad, arq);
1724
1725 as_del_arq_rb(ad, arq);
1726 if ((alias = as_add_arq_rb(ad, arq)) ) {
1727 list_del_init(&arq->fifo);
1728 as_add_aliased_request(ad, arq, alias);
1729 if (next_arq)
1730 ad->next_arq[arq->is_sync] = next_arq;
1731 }
1732 }
1733
1734 /*
1735 * if anext expires before arq, assign its expire time to arq
1736 * and move into anext position (anext will be deleted) in fifo
1737 */
1738 if (!list_empty(&arq->fifo) && !list_empty(&anext->fifo)) {
1739 if (time_before(anext->expires, arq->expires)) {
1740 list_move(&arq->fifo, &anext->fifo);
1741 arq->expires = anext->expires;
1742 /*
1743 * Don't copy here but swap, because when anext is
1744 * removed below, it must contain the unused context
1745 */
1746 swap_io_context(&arq->io_context, &anext->io_context);
1747 }
1748 }
1749
1750 /*
1751 * Transfer list of aliases
1752 */
1753 while (!list_empty(&next->queuelist)) {
1754 struct request *__rq = list_entry_rq(next->queuelist.next);
1755 struct as_rq *__arq = RQ_DATA(__rq);
1756
1757 list_move_tail(&__rq->queuelist, &req->queuelist);
1758
1759 WARN_ON(__arq->state != AS_RQ_QUEUED);
1760 }
1761
1762 /*
1763 * kill knowledge of next, this one is a goner
1764 */
1765 as_remove_queued_request(q, next);
1766
1767 anext->state = AS_RQ_MERGED;
1768}
1769
1770/*
1771 * This is executed in a "deferred" process context, by kblockd. It calls the
1772 * driver's request_fn so the driver can submit that request.
1773 *
1774 * IMPORTANT! This guy will reenter the elevator, so set up all queue global
1775 * state before calling, and don't rely on any state over calls.
1776 *
1777 * FIXME! dispatch queue is not a queue at all!
1778 */
1779static void as_work_handler(void *data)
1780{
1781 struct request_queue *q = data;
1782 unsigned long flags;
1783
1784 spin_lock_irqsave(q->queue_lock, flags);
1785 if (as_next_request(q))
1786 q->request_fn(q);
1787 spin_unlock_irqrestore(q->queue_lock, flags);
1788}
1789
1790static void as_put_request(request_queue_t *q, struct request *rq)
1791{
1792 struct as_data *ad = q->elevator->elevator_data;
1793 struct as_rq *arq = RQ_DATA(rq);
1794
1795 if (!arq) {
1796 WARN_ON(1);
1797 return;
1798 }
1799
1800 if (arq->state != AS_RQ_POSTSCHED && arq->state != AS_RQ_PRESCHED) {
1801 printk("arq->state %d\n", arq->state);
1802 WARN_ON(1);
1803 }
1804
1805 mempool_free(arq, ad->arq_pool);
1806 rq->elevator_private = NULL;
1807}
1808
1809static int as_set_request(request_queue_t *q, struct request *rq, int gfp_mask)
1810{
1811 struct as_data *ad = q->elevator->elevator_data;
1812 struct as_rq *arq = mempool_alloc(ad->arq_pool, gfp_mask);
1813
1814 if (arq) {
1815 memset(arq, 0, sizeof(*arq));
1816 RB_CLEAR(&arq->rb_node);
1817 arq->request = rq;
1818 arq->state = AS_RQ_PRESCHED;
1819 arq->io_context = NULL;
1820 INIT_LIST_HEAD(&arq->hash);
1821 arq->on_hash = 0;
1822 INIT_LIST_HEAD(&arq->fifo);
1823 rq->elevator_private = arq;
1824 return 0;
1825 }
1826
1827 return 1;
1828}
1829
1830static int as_may_queue(request_queue_t *q, int rw)
1831{
1832 int ret = ELV_MQUEUE_MAY;
1833 struct as_data *ad = q->elevator->elevator_data;
1834 struct io_context *ioc;
1835 if (ad->antic_status == ANTIC_WAIT_REQ ||
1836 ad->antic_status == ANTIC_WAIT_NEXT) {
1837 ioc = as_get_io_context();
1838 if (ad->io_context == ioc)
1839 ret = ELV_MQUEUE_MUST;
1840 put_io_context(ioc);
1841 }
1842
1843 return ret;
1844}
1845
1846static void as_exit_queue(elevator_t *e)
1847{
1848 struct as_data *ad = e->elevator_data;
1849
1850 del_timer_sync(&ad->antic_timer);
1851 kblockd_flush();
1852
1853 BUG_ON(!list_empty(&ad->fifo_list[REQ_SYNC]));
1854 BUG_ON(!list_empty(&ad->fifo_list[REQ_ASYNC]));
1855
1856 mempool_destroy(ad->arq_pool);
1857 put_io_context(ad->io_context);
1858 kfree(ad->hash);
1859 kfree(ad);
1860}
1861
1862/*
1863 * initialize elevator private data (as_data), and alloc a arq for
1864 * each request on the free lists
1865 */
1866static int as_init_queue(request_queue_t *q, elevator_t *e)
1867{
1868 struct as_data *ad;
1869 int i;
1870
1871 if (!arq_pool)
1872 return -ENOMEM;
1873
1874 ad = kmalloc(sizeof(*ad), GFP_KERNEL);
1875 if (!ad)
1876 return -ENOMEM;
1877 memset(ad, 0, sizeof(*ad));
1878
1879 ad->q = q; /* Identify what queue the data belongs to */
1880
1881 ad->hash = kmalloc(sizeof(struct list_head)*AS_HASH_ENTRIES,GFP_KERNEL);
1882 if (!ad->hash) {
1883 kfree(ad);
1884 return -ENOMEM;
1885 }
1886
1887 ad->arq_pool = mempool_create(BLKDEV_MIN_RQ, mempool_alloc_slab, mempool_free_slab, arq_pool);
1888 if (!ad->arq_pool) {
1889 kfree(ad->hash);
1890 kfree(ad);
1891 return -ENOMEM;
1892 }
1893
1894 /* anticipatory scheduling helpers */
1895 ad->antic_timer.function = as_antic_timeout;
1896 ad->antic_timer.data = (unsigned long)q;
1897 init_timer(&ad->antic_timer);
1898 INIT_WORK(&ad->antic_work, as_work_handler, q);
1899
1900 for (i = 0; i < AS_HASH_ENTRIES; i++)
1901 INIT_LIST_HEAD(&ad->hash[i]);
1902
1903 INIT_LIST_HEAD(&ad->fifo_list[REQ_SYNC]);
1904 INIT_LIST_HEAD(&ad->fifo_list[REQ_ASYNC]);
1905 ad->sort_list[REQ_SYNC] = RB_ROOT;
1906 ad->sort_list[REQ_ASYNC] = RB_ROOT;
1907 ad->dispatch = &q->queue_head;
1908 ad->fifo_expire[REQ_SYNC] = default_read_expire;
1909 ad->fifo_expire[REQ_ASYNC] = default_write_expire;
1910 ad->antic_expire = default_antic_expire;
1911 ad->batch_expire[REQ_SYNC] = default_read_batch_expire;
1912 ad->batch_expire[REQ_ASYNC] = default_write_batch_expire;
1913 e->elevator_data = ad;
1914
1915 ad->current_batch_expires = jiffies + ad->batch_expire[REQ_SYNC];
1916 ad->write_batch_count = ad->batch_expire[REQ_ASYNC] / 10;
1917 if (ad->write_batch_count < 2)
1918 ad->write_batch_count = 2;
1919
1920 return 0;
1921}
1922
1923/*
1924 * sysfs parts below
1925 */
1926struct as_fs_entry {
1927 struct attribute attr;
1928 ssize_t (*show)(struct as_data *, char *);
1929 ssize_t (*store)(struct as_data *, const char *, size_t);
1930};
1931
1932static ssize_t
1933as_var_show(unsigned int var, char *page)
1934{
1935 var = (var * 1000) / HZ;
1936 return sprintf(page, "%d\n", var);
1937}
1938
1939static ssize_t
1940as_var_store(unsigned long *var, const char *page, size_t count)
1941{
1942 unsigned long tmp;
1943 char *p = (char *) page;
1944
1945 tmp = simple_strtoul(p, &p, 10);
1946 if (tmp != 0) {
1947 tmp = (tmp * HZ) / 1000;
1948 if (tmp == 0)
1949 tmp = 1;
1950 }
1951 *var = tmp;
1952 return count;
1953}
1954
1955static ssize_t as_est_show(struct as_data *ad, char *page)
1956{
1957 int pos = 0;
1958
1959 pos += sprintf(page+pos, "%lu %% exit probability\n", 100*ad->exit_prob/256);
1960 pos += sprintf(page+pos, "%lu ms new thinktime\n", ad->new_ttime_mean);
1961 pos += sprintf(page+pos, "%llu sectors new seek distance\n", (unsigned long long)ad->new_seek_mean);
1962
1963 return pos;
1964}
1965
1966#define SHOW_FUNCTION(__FUNC, __VAR) \
1967static ssize_t __FUNC(struct as_data *ad, char *page) \
1968{ \
1969 return as_var_show(jiffies_to_msecs((__VAR)), (page)); \
1970}
1971SHOW_FUNCTION(as_readexpire_show, ad->fifo_expire[REQ_SYNC]);
1972SHOW_FUNCTION(as_writeexpire_show, ad->fifo_expire[REQ_ASYNC]);
1973SHOW_FUNCTION(as_anticexpire_show, ad->antic_expire);
1974SHOW_FUNCTION(as_read_batchexpire_show, ad->batch_expire[REQ_SYNC]);
1975SHOW_FUNCTION(as_write_batchexpire_show, ad->batch_expire[REQ_ASYNC]);
1976#undef SHOW_FUNCTION
1977
1978#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX) \
1979static ssize_t __FUNC(struct as_data *ad, const char *page, size_t count) \
1980{ \
1981 int ret = as_var_store(__PTR, (page), count); \
1982 if (*(__PTR) < (MIN)) \
1983 *(__PTR) = (MIN); \
1984 else if (*(__PTR) > (MAX)) \
1985 *(__PTR) = (MAX); \
1986 *(__PTR) = msecs_to_jiffies(*(__PTR)); \
1987 return ret; \
1988}
1989STORE_FUNCTION(as_readexpire_store, &ad->fifo_expire[REQ_SYNC], 0, INT_MAX);
1990STORE_FUNCTION(as_writeexpire_store, &ad->fifo_expire[REQ_ASYNC], 0, INT_MAX);
1991STORE_FUNCTION(as_anticexpire_store, &ad->antic_expire, 0, INT_MAX);
1992STORE_FUNCTION(as_read_batchexpire_store,
1993 &ad->batch_expire[REQ_SYNC], 0, INT_MAX);
1994STORE_FUNCTION(as_write_batchexpire_store,
1995 &ad->batch_expire[REQ_ASYNC], 0, INT_MAX);
1996#undef STORE_FUNCTION
1997
1998static struct as_fs_entry as_est_entry = {
1999 .attr = {.name = "est_time", .mode = S_IRUGO },
2000 .show = as_est_show,
2001};
2002static struct as_fs_entry as_readexpire_entry = {
2003 .attr = {.name = "read_expire", .mode = S_IRUGO | S_IWUSR },
2004 .show = as_readexpire_show,
2005 .store = as_readexpire_store,
2006};
2007static struct as_fs_entry as_writeexpire_entry = {
2008 .attr = {.name = "write_expire", .mode = S_IRUGO | S_IWUSR },
2009 .show = as_writeexpire_show,
2010 .store = as_writeexpire_store,
2011};
2012static struct as_fs_entry as_anticexpire_entry = {
2013 .attr = {.name = "antic_expire", .mode = S_IRUGO | S_IWUSR },
2014 .show = as_anticexpire_show,
2015 .store = as_anticexpire_store,
2016};
2017static struct as_fs_entry as_read_batchexpire_entry = {
2018 .attr = {.name = "read_batch_expire", .mode = S_IRUGO | S_IWUSR },
2019 .show = as_read_batchexpire_show,
2020 .store = as_read_batchexpire_store,
2021};
2022static struct as_fs_entry as_write_batchexpire_entry = {
2023 .attr = {.name = "write_batch_expire", .mode = S_IRUGO | S_IWUSR },
2024 .show = as_write_batchexpire_show,
2025 .store = as_write_batchexpire_store,
2026};
2027
2028static struct attribute *default_attrs[] = {
2029 &as_est_entry.attr,
2030 &as_readexpire_entry.attr,
2031 &as_writeexpire_entry.attr,
2032 &as_anticexpire_entry.attr,
2033 &as_read_batchexpire_entry.attr,
2034 &as_write_batchexpire_entry.attr,
2035 NULL,
2036};
2037
2038#define to_as(atr) container_of((atr), struct as_fs_entry, attr)
2039
2040static ssize_t
2041as_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
2042{
2043 elevator_t *e = container_of(kobj, elevator_t, kobj);
2044 struct as_fs_entry *entry = to_as(attr);
2045
2046 if (!entry->show)
2047 return 0;
2048
2049 return entry->show(e->elevator_data, page);
2050}
2051
2052static ssize_t
2053as_attr_store(struct kobject *kobj, struct attribute *attr,
2054 const char *page, size_t length)
2055{
2056 elevator_t *e = container_of(kobj, elevator_t, kobj);
2057 struct as_fs_entry *entry = to_as(attr);
2058
2059 if (!entry->store)
2060 return -EINVAL;
2061
2062 return entry->store(e->elevator_data, page, length);
2063}
2064
2065static struct sysfs_ops as_sysfs_ops = {
2066 .show = as_attr_show,
2067 .store = as_attr_store,
2068};
2069
2070static struct kobj_type as_ktype = {
2071 .sysfs_ops = &as_sysfs_ops,
2072 .default_attrs = default_attrs,
2073};
2074
2075static struct elevator_type iosched_as = {
2076 .ops = {
2077 .elevator_merge_fn = as_merge,
2078 .elevator_merged_fn = as_merged_request,
2079 .elevator_merge_req_fn = as_merged_requests,
2080 .elevator_next_req_fn = as_next_request,
2081 .elevator_add_req_fn = as_insert_request,
2082 .elevator_remove_req_fn = as_remove_request,
2083 .elevator_requeue_req_fn = as_requeue_request,
2084 .elevator_deactivate_req_fn = as_deactivate_request,
2085 .elevator_queue_empty_fn = as_queue_empty,
2086 .elevator_completed_req_fn = as_completed_request,
2087 .elevator_former_req_fn = as_former_request,
2088 .elevator_latter_req_fn = as_latter_request,
2089 .elevator_set_req_fn = as_set_request,
2090 .elevator_put_req_fn = as_put_request,
2091 .elevator_may_queue_fn = as_may_queue,
2092 .elevator_init_fn = as_init_queue,
2093 .elevator_exit_fn = as_exit_queue,
2094 },
2095
2096 .elevator_ktype = &as_ktype,
2097 .elevator_name = "anticipatory",
2098 .elevator_owner = THIS_MODULE,
2099};
2100
2101static int __init as_init(void)
2102{
2103 int ret;
2104
2105 arq_pool = kmem_cache_create("as_arq", sizeof(struct as_rq),
2106 0, 0, NULL, NULL);
2107 if (!arq_pool)
2108 return -ENOMEM;
2109
2110 ret = elv_register(&iosched_as);
2111 if (!ret) {
2112 /*
2113 * don't allow AS to get unregistered, since we would have
2114 * to browse all tasks in the system and release their
2115 * as_io_context first
2116 */
2117 __module_get(THIS_MODULE);
2118 return 0;
2119 }
2120
2121 kmem_cache_destroy(arq_pool);
2122 return ret;
2123}
2124
2125static void __exit as_exit(void)
2126{
2127 kmem_cache_destroy(arq_pool);
2128 elv_unregister(&iosched_as);
2129}
2130
2131module_init(as_init);
2132module_exit(as_exit);
2133
2134MODULE_AUTHOR("Nick Piggin");
2135MODULE_LICENSE("GPL");
2136MODULE_DESCRIPTION("anticipatory IO scheduler");
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-07 03:34:30 -0500