blob: 4469dd84623cc645b641dce21caaa3fddd270227 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * Deadline i/o scheduler.
3 *
4 * Copyright (C) 2002 Jens Axboe <axboe@suse.de>
5 */
6#include <linux/kernel.h>
7#include <linux/fs.h>
8#include <linux/blkdev.h>
9#include <linux/elevator.h>
10#include <linux/bio.h>
11#include <linux/config.h>
12#include <linux/module.h>
13#include <linux/slab.h>
14#include <linux/init.h>
15#include <linux/compiler.h>
16#include <linux/hash.h>
17#include <linux/rbtree.h>
18
19/*
20 * See Documentation/block/deadline-iosched.txt
21 */
Arjan van de Ven64100092006-01-06 09:46:02 +010022static const int read_expire = HZ / 2; /* max time before a read is submitted. */
23static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
24static const int writes_starved = 2; /* max times reads can starve a write */
25static const int fifo_batch = 16; /* # of sequential requests treated as one
Linus Torvalds1da177e2005-04-16 15:20:36 -070026 by the above parameters. For throughput. */
27
28static const int deadline_hash_shift = 5;
29#define DL_HASH_BLOCK(sec) ((sec) >> 3)
30#define DL_HASH_FN(sec) (hash_long(DL_HASH_BLOCK((sec)), deadline_hash_shift))
31#define DL_HASH_ENTRIES (1 << deadline_hash_shift)
32#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
Akinobu Mitabae386f2006-04-24 21:12:59 +020033#define ON_HASH(drq) (!hlist_unhashed(&(drq)->hash))
Linus Torvalds1da177e2005-04-16 15:20:36 -070034
35struct deadline_data {
36 /*
37 * run time data
38 */
39
40 /*
41 * requests (deadline_rq s) are present on both sort_list and fifo_list
42 */
43 struct rb_root sort_list[2];
44 struct list_head fifo_list[2];
45
46 /*
47 * next in sort order. read, write or both are NULL
48 */
49 struct deadline_rq *next_drq[2];
Akinobu Mitabae386f2006-04-24 21:12:59 +020050 struct hlist_head *hash; /* request hash */
Linus Torvalds1da177e2005-04-16 15:20:36 -070051 unsigned int batching; /* number of sequential requests made */
52 sector_t last_sector; /* head position */
53 unsigned int starved; /* times reads have starved writes */
54
55 /*
56 * settings that change how the i/o scheduler behaves
57 */
58 int fifo_expire[2];
59 int fifo_batch;
60 int writes_starved;
61 int front_merges;
62
63 mempool_t *drq_pool;
64};
65
66/*
67 * pre-request data.
68 */
69struct deadline_rq {
70 /*
71 * rbtree index, key is the starting offset
72 */
73 struct rb_node rb_node;
74 sector_t rb_key;
75
76 struct request *request;
77
78 /*
79 * request hash, key is the ending offset (for back merge lookup)
80 */
Akinobu Mitabae386f2006-04-24 21:12:59 +020081 struct hlist_node hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -070082
83 /*
84 * expire fifo
85 */
86 struct list_head fifo;
87 unsigned long expires;
88};
89
90static void deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq);
91
92static kmem_cache_t *drq_pool;
93
94#define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private)
95
96/*
97 * the back merge hash support functions
98 */
99static inline void __deadline_del_drq_hash(struct deadline_rq *drq)
100{
Akinobu Mitabae386f2006-04-24 21:12:59 +0200101 hlist_del_init(&drq->hash);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102}
103
104static inline void deadline_del_drq_hash(struct deadline_rq *drq)
105{
106 if (ON_HASH(drq))
107 __deadline_del_drq_hash(drq);
108}
109
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110static inline void
111deadline_add_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
112{
113 struct request *rq = drq->request;
114
115 BUG_ON(ON_HASH(drq));
116
Akinobu Mitabae386f2006-04-24 21:12:59 +0200117 hlist_add_head(&drq->hash, &dd->hash[DL_HASH_FN(rq_hash_key(rq))]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118}
119
120/*
121 * move hot entry to front of chain
122 */
123static inline void
124deadline_hot_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
125{
126 struct request *rq = drq->request;
Akinobu Mitabae386f2006-04-24 21:12:59 +0200127 struct hlist_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128
Akinobu Mitabae386f2006-04-24 21:12:59 +0200129 if (ON_HASH(drq) && &drq->hash != head->first) {
130 hlist_del(&drq->hash);
131 hlist_add_head(&drq->hash, head);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700132 }
133}
134
135static struct request *
136deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
137{
Akinobu Mitabae386f2006-04-24 21:12:59 +0200138 struct hlist_head *hash_list = &dd->hash[DL_HASH_FN(offset)];
139 struct hlist_node *entry, *next;
140 struct deadline_rq *drq;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
Akinobu Mitabae386f2006-04-24 21:12:59 +0200142 hlist_for_each_entry_safe(drq, entry, next, hash_list, hash) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143 struct request *__rq = drq->request;
144
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145 BUG_ON(!ON_HASH(drq));
146
147 if (!rq_mergeable(__rq)) {
148 __deadline_del_drq_hash(drq);
149 continue;
150 }
151
152 if (rq_hash_key(__rq) == offset)
153 return __rq;
154 }
155
156 return NULL;
157}
158
159/*
160 * rb tree support functions
161 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node)
163#define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)])
164#define rq_rb_key(rq) (rq)->sector
165
166static struct deadline_rq *
167__deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
168{
169 struct rb_node **p = &DRQ_RB_ROOT(dd, drq)->rb_node;
170 struct rb_node *parent = NULL;
171 struct deadline_rq *__drq;
172
173 while (*p) {
174 parent = *p;
175 __drq = rb_entry_drq(parent);
176
177 if (drq->rb_key < __drq->rb_key)
178 p = &(*p)->rb_left;
179 else if (drq->rb_key > __drq->rb_key)
180 p = &(*p)->rb_right;
181 else
182 return __drq;
183 }
184
185 rb_link_node(&drq->rb_node, parent, p);
186 return NULL;
187}
188
189static void
190deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
191{
192 struct deadline_rq *__alias;
193
194 drq->rb_key = rq_rb_key(drq->request);
195
196retry:
197 __alias = __deadline_add_drq_rb(dd, drq);
198 if (!__alias) {
199 rb_insert_color(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
200 return;
201 }
202
203 deadline_move_request(dd, __alias);
204 goto retry;
205}
206
207static inline void
208deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
209{
210 const int data_dir = rq_data_dir(drq->request);
211
212 if (dd->next_drq[data_dir] == drq) {
213 struct rb_node *rbnext = rb_next(&drq->rb_node);
214
215 dd->next_drq[data_dir] = NULL;
216 if (rbnext)
217 dd->next_drq[data_dir] = rb_entry_drq(rbnext);
218 }
219
Jens Axboedd67d052006-06-21 09:36:18 +0200220 BUG_ON(!RB_EMPTY_NODE(&drq->rb_node));
Jens Axboeb4878f22005-10-20 16:42:29 +0200221 rb_erase(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
Jens Axboedd67d052006-06-21 09:36:18 +0200222 RB_CLEAR_NODE(&drq->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223}
224
225static struct request *
226deadline_find_drq_rb(struct deadline_data *dd, sector_t sector, int data_dir)
227{
228 struct rb_node *n = dd->sort_list[data_dir].rb_node;
229 struct deadline_rq *drq;
230
231 while (n) {
232 drq = rb_entry_drq(n);
233
234 if (sector < drq->rb_key)
235 n = n->rb_left;
236 else if (sector > drq->rb_key)
237 n = n->rb_right;
238 else
239 return drq->request;
240 }
241
242 return NULL;
243}
244
245/*
246 * deadline_find_first_drq finds the first (lowest sector numbered) request
247 * for the specified data_dir. Used to sweep back to the start of the disk
248 * (1-way elevator) after we process the last (highest sector) request.
249 */
250static struct deadline_rq *
251deadline_find_first_drq(struct deadline_data *dd, int data_dir)
252{
253 struct rb_node *n = dd->sort_list[data_dir].rb_node;
254
255 for (;;) {
256 if (n->rb_left == NULL)
257 return rb_entry_drq(n);
258
259 n = n->rb_left;
260 }
261}
262
263/*
264 * add drq to rbtree and fifo
265 */
Jens Axboeb4878f22005-10-20 16:42:29 +0200266static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267deadline_add_request(struct request_queue *q, struct request *rq)
268{
269 struct deadline_data *dd = q->elevator->elevator_data;
270 struct deadline_rq *drq = RQ_DATA(rq);
271
272 const int data_dir = rq_data_dir(drq->request);
273
274 deadline_add_drq_rb(dd, drq);
275 /*
276 * set expire time (only used for reads) and add to fifo list
277 */
278 drq->expires = jiffies + dd->fifo_expire[data_dir];
279 list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);
280
Tejun Heo98b11472005-10-20 16:46:54 +0200281 if (rq_mergeable(rq))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282 deadline_add_drq_hash(dd, drq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283}
284
285/*
286 * remove rq from rbtree, fifo, and hash
287 */
288static void deadline_remove_request(request_queue_t *q, struct request *rq)
289{
290 struct deadline_rq *drq = RQ_DATA(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +0200291 struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292
Jens Axboeb4878f22005-10-20 16:42:29 +0200293 list_del_init(&drq->fifo);
Jens Axboeb4878f22005-10-20 16:42:29 +0200294 deadline_del_drq_rb(dd, drq);
Tejun Heo98b11472005-10-20 16:46:54 +0200295 deadline_del_drq_hash(drq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296}
297
298static int
299deadline_merge(request_queue_t *q, struct request **req, struct bio *bio)
300{
301 struct deadline_data *dd = q->elevator->elevator_data;
302 struct request *__rq;
303 int ret;
304
305 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306 * see if the merge hash can satisfy a back merge
307 */
308 __rq = deadline_find_drq_hash(dd, bio->bi_sector);
309 if (__rq) {
310 BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
311
312 if (elv_rq_merge_ok(__rq, bio)) {
313 ret = ELEVATOR_BACK_MERGE;
314 goto out;
315 }
316 }
317
318 /*
319 * check for front merge
320 */
321 if (dd->front_merges) {
322 sector_t rb_key = bio->bi_sector + bio_sectors(bio);
323
324 __rq = deadline_find_drq_rb(dd, rb_key, bio_data_dir(bio));
325 if (__rq) {
326 BUG_ON(rb_key != rq_rb_key(__rq));
327
328 if (elv_rq_merge_ok(__rq, bio)) {
329 ret = ELEVATOR_FRONT_MERGE;
330 goto out;
331 }
332 }
333 }
334
335 return ELEVATOR_NO_MERGE;
336out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700337 if (ret)
338 deadline_hot_drq_hash(dd, RQ_DATA(__rq));
339 *req = __rq;
340 return ret;
341}
342
343static void deadline_merged_request(request_queue_t *q, struct request *req)
344{
345 struct deadline_data *dd = q->elevator->elevator_data;
346 struct deadline_rq *drq = RQ_DATA(req);
347
348 /*
349 * hash always needs to be repositioned, key is end sector
350 */
351 deadline_del_drq_hash(drq);
352 deadline_add_drq_hash(dd, drq);
353
354 /*
355 * if the merge was a front merge, we need to reposition request
356 */
357 if (rq_rb_key(req) != drq->rb_key) {
358 deadline_del_drq_rb(dd, drq);
359 deadline_add_drq_rb(dd, drq);
360 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361}
362
363static void
364deadline_merged_requests(request_queue_t *q, struct request *req,
365 struct request *next)
366{
367 struct deadline_data *dd = q->elevator->elevator_data;
368 struct deadline_rq *drq = RQ_DATA(req);
369 struct deadline_rq *dnext = RQ_DATA(next);
370
371 BUG_ON(!drq);
372 BUG_ON(!dnext);
373
374 /*
375 * reposition drq (this is the merged request) in hash, and in rbtree
376 * in case of a front merge
377 */
378 deadline_del_drq_hash(drq);
379 deadline_add_drq_hash(dd, drq);
380
381 if (rq_rb_key(req) != drq->rb_key) {
382 deadline_del_drq_rb(dd, drq);
383 deadline_add_drq_rb(dd, drq);
384 }
385
386 /*
387 * if dnext expires before drq, assign its expire time to drq
388 * and move into dnext position (dnext will be deleted) in fifo
389 */
390 if (!list_empty(&drq->fifo) && !list_empty(&dnext->fifo)) {
391 if (time_before(dnext->expires, drq->expires)) {
392 list_move(&drq->fifo, &dnext->fifo);
393 drq->expires = dnext->expires;
394 }
395 }
396
397 /*
398 * kill knowledge of next, this one is a goner
399 */
400 deadline_remove_request(q, next);
401}
402
403/*
404 * move request from sort list to dispatch queue.
405 */
406static inline void
407deadline_move_to_dispatch(struct deadline_data *dd, struct deadline_rq *drq)
408{
409 request_queue_t *q = drq->request->q;
410
411 deadline_remove_request(q, drq->request);
Jens Axboeb4878f22005-10-20 16:42:29 +0200412 elv_dispatch_add_tail(q, drq->request);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413}
414
415/*
416 * move an entry to dispatch queue
417 */
418static void
419deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq)
420{
421 const int data_dir = rq_data_dir(drq->request);
422 struct rb_node *rbnext = rb_next(&drq->rb_node);
423
424 dd->next_drq[READ] = NULL;
425 dd->next_drq[WRITE] = NULL;
426
427 if (rbnext)
428 dd->next_drq[data_dir] = rb_entry_drq(rbnext);
429
430 dd->last_sector = drq->request->sector + drq->request->nr_sectors;
431
432 /*
433 * take it off the sort and fifo list, move
434 * to dispatch queue
435 */
436 deadline_move_to_dispatch(dd, drq);
437}
438
439#define list_entry_fifo(ptr) list_entry((ptr), struct deadline_rq, fifo)
440
441/*
442 * deadline_check_fifo returns 0 if there are no expired reads on the fifo,
443 * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
444 */
445static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
446{
447 struct deadline_rq *drq = list_entry_fifo(dd->fifo_list[ddir].next);
448
449 /*
450 * drq is expired!
451 */
452 if (time_after(jiffies, drq->expires))
453 return 1;
454
455 return 0;
456}
457
458/*
459 * deadline_dispatch_requests selects the best request according to
460 * read/write expire, fifo_batch, etc
461 */
Jens Axboeb4878f22005-10-20 16:42:29 +0200462static int deadline_dispatch_requests(request_queue_t *q, int force)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700463{
Jens Axboeb4878f22005-10-20 16:42:29 +0200464 struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 const int reads = !list_empty(&dd->fifo_list[READ]);
466 const int writes = !list_empty(&dd->fifo_list[WRITE]);
467 struct deadline_rq *drq;
Nikita Danilov4b0dc072005-09-06 15:17:20 -0700468 int data_dir;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469
470 /*
471 * batches are currently reads XOR writes
472 */
Andrew Morton9d5c1e12005-09-09 13:02:12 -0700473 if (dd->next_drq[WRITE])
474 drq = dd->next_drq[WRITE];
475 else
476 drq = dd->next_drq[READ];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477
478 if (drq) {
479 /* we have a "next request" */
480
481 if (dd->last_sector != drq->request->sector)
482 /* end the batch on a non sequential request */
483 dd->batching += dd->fifo_batch;
484
485 if (dd->batching < dd->fifo_batch)
486 /* we are still entitled to batch */
487 goto dispatch_request;
488 }
489
490 /*
491 * at this point we are not running a batch. select the appropriate
492 * data direction (read / write)
493 */
494
495 if (reads) {
Jens Axboedd67d052006-06-21 09:36:18 +0200496 BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497
498 if (writes && (dd->starved++ >= dd->writes_starved))
499 goto dispatch_writes;
500
501 data_dir = READ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502
503 goto dispatch_find_request;
504 }
505
506 /*
507 * there are either no reads or writes have been starved
508 */
509
510 if (writes) {
511dispatch_writes:
Jens Axboedd67d052006-06-21 09:36:18 +0200512 BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513
514 dd->starved = 0;
515
516 data_dir = WRITE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700517
518 goto dispatch_find_request;
519 }
520
521 return 0;
522
523dispatch_find_request:
524 /*
525 * we are not running a batch, find best request for selected data_dir
526 */
527 if (deadline_check_fifo(dd, data_dir)) {
528 /* An expired request exists - satisfy it */
529 dd->batching = 0;
530 drq = list_entry_fifo(dd->fifo_list[data_dir].next);
531
532 } else if (dd->next_drq[data_dir]) {
533 /*
534 * The last req was the same dir and we have a next request in
535 * sort order. No expired requests so continue on from here.
536 */
537 drq = dd->next_drq[data_dir];
538 } else {
539 /*
540 * The last req was the other direction or we have run out of
541 * higher-sectored requests. Go back to the lowest sectored
542 * request (1 way elevator) and start a new batch.
543 */
544 dd->batching = 0;
545 drq = deadline_find_first_drq(dd, data_dir);
546 }
547
548dispatch_request:
549 /*
550 * drq is the selected appropriate request.
551 */
552 dd->batching++;
553 deadline_move_request(dd, drq);
554
555 return 1;
556}
557
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558static int deadline_queue_empty(request_queue_t *q)
559{
560 struct deadline_data *dd = q->elevator->elevator_data;
561
Jens Axboeb4878f22005-10-20 16:42:29 +0200562 return list_empty(&dd->fifo_list[WRITE])
563 && list_empty(&dd->fifo_list[READ]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564}
565
566static struct request *
567deadline_former_request(request_queue_t *q, struct request *rq)
568{
569 struct deadline_rq *drq = RQ_DATA(rq);
570 struct rb_node *rbprev = rb_prev(&drq->rb_node);
571
572 if (rbprev)
573 return rb_entry_drq(rbprev)->request;
574
575 return NULL;
576}
577
578static struct request *
579deadline_latter_request(request_queue_t *q, struct request *rq)
580{
581 struct deadline_rq *drq = RQ_DATA(rq);
582 struct rb_node *rbnext = rb_next(&drq->rb_node);
583
584 if (rbnext)
585 return rb_entry_drq(rbnext)->request;
586
587 return NULL;
588}
589
590static void deadline_exit_queue(elevator_t *e)
591{
592 struct deadline_data *dd = e->elevator_data;
593
594 BUG_ON(!list_empty(&dd->fifo_list[READ]));
595 BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
596
597 mempool_destroy(dd->drq_pool);
598 kfree(dd->hash);
599 kfree(dd);
600}
601
602/*
603 * initialize elevator private data (deadline_data), and alloc a drq for
604 * each request on the free lists
605 */
Jens Axboebc1c1162006-06-08 08:49:06 +0200606static void *deadline_init_queue(request_queue_t *q, elevator_t *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607{
608 struct deadline_data *dd;
609 int i;
610
611 if (!drq_pool)
Jens Axboebc1c1162006-06-08 08:49:06 +0200612 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700613
Christoph Lameter19460892005-06-23 00:08:19 -0700614 dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615 if (!dd)
Jens Axboebc1c1162006-06-08 08:49:06 +0200616 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617 memset(dd, 0, sizeof(*dd));
618
Akinobu Mitabae386f2006-04-24 21:12:59 +0200619 dd->hash = kmalloc_node(sizeof(struct hlist_head)*DL_HASH_ENTRIES,
Christoph Lameter19460892005-06-23 00:08:19 -0700620 GFP_KERNEL, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621 if (!dd->hash) {
622 kfree(dd);
Jens Axboebc1c1162006-06-08 08:49:06 +0200623 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700624 }
625
Christoph Lameter19460892005-06-23 00:08:19 -0700626 dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
627 mempool_free_slab, drq_pool, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700628 if (!dd->drq_pool) {
629 kfree(dd->hash);
630 kfree(dd);
Jens Axboebc1c1162006-06-08 08:49:06 +0200631 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700632 }
633
634 for (i = 0; i < DL_HASH_ENTRIES; i++)
Akinobu Mitabae386f2006-04-24 21:12:59 +0200635 INIT_HLIST_HEAD(&dd->hash[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636
637 INIT_LIST_HEAD(&dd->fifo_list[READ]);
638 INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
639 dd->sort_list[READ] = RB_ROOT;
640 dd->sort_list[WRITE] = RB_ROOT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700641 dd->fifo_expire[READ] = read_expire;
642 dd->fifo_expire[WRITE] = write_expire;
643 dd->writes_starved = writes_starved;
644 dd->front_merges = 1;
645 dd->fifo_batch = fifo_batch;
Jens Axboebc1c1162006-06-08 08:49:06 +0200646 return dd;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647}
648
649static void deadline_put_request(request_queue_t *q, struct request *rq)
650{
651 struct deadline_data *dd = q->elevator->elevator_data;
652 struct deadline_rq *drq = RQ_DATA(rq);
653
Jens Axboeb4878f22005-10-20 16:42:29 +0200654 mempool_free(drq, dd->drq_pool);
655 rq->elevator_private = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656}
657
658static int
Jens Axboe22e2c502005-06-27 10:55:12 +0200659deadline_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro8267e262005-10-21 03:20:53 -0400660 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661{
662 struct deadline_data *dd = q->elevator->elevator_data;
663 struct deadline_rq *drq;
664
665 drq = mempool_alloc(dd->drq_pool, gfp_mask);
666 if (drq) {
667 memset(drq, 0, sizeof(*drq));
Jens Axboedd67d052006-06-21 09:36:18 +0200668 RB_CLEAR_NODE(&drq->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700669 drq->request = rq;
670
Akinobu Mitabae386f2006-04-24 21:12:59 +0200671 INIT_HLIST_NODE(&drq->hash);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672
673 INIT_LIST_HEAD(&drq->fifo);
674
675 rq->elevator_private = drq;
676 return 0;
677 }
678
679 return 1;
680}
681
682/*
683 * sysfs parts below
684 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685
686static ssize_t
687deadline_var_show(int var, char *page)
688{
689 return sprintf(page, "%d\n", var);
690}
691
692static ssize_t
693deadline_var_store(int *var, const char *page, size_t count)
694{
695 char *p = (char *) page;
696
697 *var = simple_strtol(p, &p, 10);
698 return count;
699}
700
701#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -0500702static ssize_t __FUNC(elevator_t *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700703{ \
Al Viro3d1ab402006-03-18 18:35:43 -0500704 struct deadline_data *dd = e->elevator_data; \
705 int __data = __VAR; \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706 if (__CONV) \
707 __data = jiffies_to_msecs(__data); \
708 return deadline_var_show(__data, (page)); \
709}
Al Viroe572ec72006-03-18 22:27:18 -0500710SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
711SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
712SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
713SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
714SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715#undef SHOW_FUNCTION
716
717#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -0500718static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700719{ \
Al Viro3d1ab402006-03-18 18:35:43 -0500720 struct deadline_data *dd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721 int __data; \
722 int ret = deadline_var_store(&__data, (page), count); \
723 if (__data < (MIN)) \
724 __data = (MIN); \
725 else if (__data > (MAX)) \
726 __data = (MAX); \
727 if (__CONV) \
728 *(__PTR) = msecs_to_jiffies(__data); \
729 else \
730 *(__PTR) = __data; \
731 return ret; \
732}
Al Viroe572ec72006-03-18 22:27:18 -0500733STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
734STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
735STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
736STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
737STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700738#undef STORE_FUNCTION
739
Al Viroe572ec72006-03-18 22:27:18 -0500740#define DD_ATTR(name) \
741 __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
742 deadline_##name##_store)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700743
Al Viroe572ec72006-03-18 22:27:18 -0500744static struct elv_fs_entry deadline_attrs[] = {
745 DD_ATTR(read_expire),
746 DD_ATTR(write_expire),
747 DD_ATTR(writes_starved),
748 DD_ATTR(front_merges),
749 DD_ATTR(fifo_batch),
750 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751};
752
Linus Torvalds1da177e2005-04-16 15:20:36 -0700753static struct elevator_type iosched_deadline = {
754 .ops = {
755 .elevator_merge_fn = deadline_merge,
756 .elevator_merged_fn = deadline_merged_request,
757 .elevator_merge_req_fn = deadline_merged_requests,
Jens Axboeb4878f22005-10-20 16:42:29 +0200758 .elevator_dispatch_fn = deadline_dispatch_requests,
759 .elevator_add_req_fn = deadline_add_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700760 .elevator_queue_empty_fn = deadline_queue_empty,
761 .elevator_former_req_fn = deadline_former_request,
762 .elevator_latter_req_fn = deadline_latter_request,
763 .elevator_set_req_fn = deadline_set_request,
764 .elevator_put_req_fn = deadline_put_request,
765 .elevator_init_fn = deadline_init_queue,
766 .elevator_exit_fn = deadline_exit_queue,
767 },
768
Al Viro3d1ab402006-03-18 18:35:43 -0500769 .elevator_attrs = deadline_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700770 .elevator_name = "deadline",
771 .elevator_owner = THIS_MODULE,
772};
773
774static int __init deadline_init(void)
775{
776 int ret;
777
778 drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq),
779 0, 0, NULL, NULL);
780
781 if (!drq_pool)
782 return -ENOMEM;
783
784 ret = elv_register(&iosched_deadline);
785 if (ret)
786 kmem_cache_destroy(drq_pool);
787
788 return ret;
789}
790
791static void __exit deadline_exit(void)
792{
793 kmem_cache_destroy(drq_pool);
794 elv_unregister(&iosched_deadline);
795}
796
797module_init(deadline_init);
798module_exit(deadline_exit);
799
800MODULE_AUTHOR("Jens Axboe");
801MODULE_LICENSE("GPL");
802MODULE_DESCRIPTION("deadline IO scheduler");