blob: 3bd0415a9828673c6bb28a6cd52d1fe6fac730d2 [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)
33#define list_entry_hash(ptr) list_entry((ptr), struct deadline_rq, hash)
34#define ON_HASH(drq) (drq)->on_hash
35
36struct deadline_data {
37 /*
38 * run time data
39 */
40
41 /*
42 * requests (deadline_rq s) are present on both sort_list and fifo_list
43 */
44 struct rb_root sort_list[2];
45 struct list_head fifo_list[2];
46
47 /*
48 * next in sort order. read, write or both are NULL
49 */
50 struct deadline_rq *next_drq[2];
Linus Torvalds1da177e2005-04-16 15:20:36 -070051 struct list_head *hash; /* request hash */
52 unsigned int batching; /* number of sequential requests made */
53 sector_t last_sector; /* head position */
54 unsigned int starved; /* times reads have starved writes */
55
56 /*
57 * settings that change how the i/o scheduler behaves
58 */
59 int fifo_expire[2];
60 int fifo_batch;
61 int writes_starved;
62 int front_merges;
63
64 mempool_t *drq_pool;
65};
66
67/*
68 * pre-request data.
69 */
70struct deadline_rq {
71 /*
72 * rbtree index, key is the starting offset
73 */
74 struct rb_node rb_node;
75 sector_t rb_key;
76
77 struct request *request;
78
79 /*
80 * request hash, key is the ending offset (for back merge lookup)
81 */
82 struct list_head hash;
83 char on_hash;
84
85 /*
86 * expire fifo
87 */
88 struct list_head fifo;
89 unsigned long expires;
90};
91
92static void deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq);
93
94static kmem_cache_t *drq_pool;
95
96#define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private)
97
98/*
99 * the back merge hash support functions
100 */
101static inline void __deadline_del_drq_hash(struct deadline_rq *drq)
102{
103 drq->on_hash = 0;
104 list_del_init(&drq->hash);
105}
106
107static inline void deadline_del_drq_hash(struct deadline_rq *drq)
108{
109 if (ON_HASH(drq))
110 __deadline_del_drq_hash(drq);
111}
112
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113static inline void
114deadline_add_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
115{
116 struct request *rq = drq->request;
117
118 BUG_ON(ON_HASH(drq));
119
120 drq->on_hash = 1;
121 list_add(&drq->hash, &dd->hash[DL_HASH_FN(rq_hash_key(rq))]);
122}
123
124/*
125 * move hot entry to front of chain
126 */
127static inline void
128deadline_hot_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
129{
130 struct request *rq = drq->request;
131 struct list_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))];
132
133 if (ON_HASH(drq) && drq->hash.prev != head) {
134 list_del(&drq->hash);
135 list_add(&drq->hash, head);
136 }
137}
138
139static struct request *
140deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
141{
142 struct list_head *hash_list = &dd->hash[DL_HASH_FN(offset)];
143 struct list_head *entry, *next = hash_list->next;
144
145 while ((entry = next) != hash_list) {
146 struct deadline_rq *drq = list_entry_hash(entry);
147 struct request *__rq = drq->request;
148
149 next = entry->next;
150
151 BUG_ON(!ON_HASH(drq));
152
153 if (!rq_mergeable(__rq)) {
154 __deadline_del_drq_hash(drq);
155 continue;
156 }
157
158 if (rq_hash_key(__rq) == offset)
159 return __rq;
160 }
161
162 return NULL;
163}
164
165/*
166 * rb tree support functions
167 */
168#define RB_NONE (2)
169#define RB_EMPTY(root) ((root)->rb_node == NULL)
170#define ON_RB(node) ((node)->rb_color != RB_NONE)
171#define RB_CLEAR(node) ((node)->rb_color = RB_NONE)
172#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node)
173#define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)])
174#define rq_rb_key(rq) (rq)->sector
175
176static struct deadline_rq *
177__deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
178{
179 struct rb_node **p = &DRQ_RB_ROOT(dd, drq)->rb_node;
180 struct rb_node *parent = NULL;
181 struct deadline_rq *__drq;
182
183 while (*p) {
184 parent = *p;
185 __drq = rb_entry_drq(parent);
186
187 if (drq->rb_key < __drq->rb_key)
188 p = &(*p)->rb_left;
189 else if (drq->rb_key > __drq->rb_key)
190 p = &(*p)->rb_right;
191 else
192 return __drq;
193 }
194
195 rb_link_node(&drq->rb_node, parent, p);
196 return NULL;
197}
198
199static void
200deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
201{
202 struct deadline_rq *__alias;
203
204 drq->rb_key = rq_rb_key(drq->request);
205
206retry:
207 __alias = __deadline_add_drq_rb(dd, drq);
208 if (!__alias) {
209 rb_insert_color(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
210 return;
211 }
212
213 deadline_move_request(dd, __alias);
214 goto retry;
215}
216
217static inline void
218deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
219{
220 const int data_dir = rq_data_dir(drq->request);
221
222 if (dd->next_drq[data_dir] == drq) {
223 struct rb_node *rbnext = rb_next(&drq->rb_node);
224
225 dd->next_drq[data_dir] = NULL;
226 if (rbnext)
227 dd->next_drq[data_dir] = rb_entry_drq(rbnext);
228 }
229
Jens Axboeb4878f22005-10-20 16:42:29 +0200230 BUG_ON(!ON_RB(&drq->rb_node));
231 rb_erase(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
232 RB_CLEAR(&drq->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233}
234
235static struct request *
236deadline_find_drq_rb(struct deadline_data *dd, sector_t sector, int data_dir)
237{
238 struct rb_node *n = dd->sort_list[data_dir].rb_node;
239 struct deadline_rq *drq;
240
241 while (n) {
242 drq = rb_entry_drq(n);
243
244 if (sector < drq->rb_key)
245 n = n->rb_left;
246 else if (sector > drq->rb_key)
247 n = n->rb_right;
248 else
249 return drq->request;
250 }
251
252 return NULL;
253}
254
255/*
256 * deadline_find_first_drq finds the first (lowest sector numbered) request
257 * for the specified data_dir. Used to sweep back to the start of the disk
258 * (1-way elevator) after we process the last (highest sector) request.
259 */
260static struct deadline_rq *
261deadline_find_first_drq(struct deadline_data *dd, int data_dir)
262{
263 struct rb_node *n = dd->sort_list[data_dir].rb_node;
264
265 for (;;) {
266 if (n->rb_left == NULL)
267 return rb_entry_drq(n);
268
269 n = n->rb_left;
270 }
271}
272
273/*
274 * add drq to rbtree and fifo
275 */
Jens Axboeb4878f22005-10-20 16:42:29 +0200276static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277deadline_add_request(struct request_queue *q, struct request *rq)
278{
279 struct deadline_data *dd = q->elevator->elevator_data;
280 struct deadline_rq *drq = RQ_DATA(rq);
281
282 const int data_dir = rq_data_dir(drq->request);
283
284 deadline_add_drq_rb(dd, drq);
285 /*
286 * set expire time (only used for reads) and add to fifo list
287 */
288 drq->expires = jiffies + dd->fifo_expire[data_dir];
289 list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);
290
Tejun Heo98b11472005-10-20 16:46:54 +0200291 if (rq_mergeable(rq))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 deadline_add_drq_hash(dd, drq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293}
294
295/*
296 * remove rq from rbtree, fifo, and hash
297 */
298static void deadline_remove_request(request_queue_t *q, struct request *rq)
299{
300 struct deadline_rq *drq = RQ_DATA(rq);
Jens Axboeb4878f22005-10-20 16:42:29 +0200301 struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302
Jens Axboeb4878f22005-10-20 16:42:29 +0200303 list_del_init(&drq->fifo);
Jens Axboeb4878f22005-10-20 16:42:29 +0200304 deadline_del_drq_rb(dd, drq);
Tejun Heo98b11472005-10-20 16:46:54 +0200305 deadline_del_drq_hash(drq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306}
307
308static int
309deadline_merge(request_queue_t *q, struct request **req, struct bio *bio)
310{
311 struct deadline_data *dd = q->elevator->elevator_data;
312 struct request *__rq;
313 int ret;
314
315 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316 * see if the merge hash can satisfy a back merge
317 */
318 __rq = deadline_find_drq_hash(dd, bio->bi_sector);
319 if (__rq) {
320 BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
321
322 if (elv_rq_merge_ok(__rq, bio)) {
323 ret = ELEVATOR_BACK_MERGE;
324 goto out;
325 }
326 }
327
328 /*
329 * check for front merge
330 */
331 if (dd->front_merges) {
332 sector_t rb_key = bio->bi_sector + bio_sectors(bio);
333
334 __rq = deadline_find_drq_rb(dd, rb_key, bio_data_dir(bio));
335 if (__rq) {
336 BUG_ON(rb_key != rq_rb_key(__rq));
337
338 if (elv_rq_merge_ok(__rq, bio)) {
339 ret = ELEVATOR_FRONT_MERGE;
340 goto out;
341 }
342 }
343 }
344
345 return ELEVATOR_NO_MERGE;
346out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347 if (ret)
348 deadline_hot_drq_hash(dd, RQ_DATA(__rq));
349 *req = __rq;
350 return ret;
351}
352
353static void deadline_merged_request(request_queue_t *q, struct request *req)
354{
355 struct deadline_data *dd = q->elevator->elevator_data;
356 struct deadline_rq *drq = RQ_DATA(req);
357
358 /*
359 * hash always needs to be repositioned, key is end sector
360 */
361 deadline_del_drq_hash(drq);
362 deadline_add_drq_hash(dd, drq);
363
364 /*
365 * if the merge was a front merge, we need to reposition request
366 */
367 if (rq_rb_key(req) != drq->rb_key) {
368 deadline_del_drq_rb(dd, drq);
369 deadline_add_drq_rb(dd, drq);
370 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371}
372
373static void
374deadline_merged_requests(request_queue_t *q, struct request *req,
375 struct request *next)
376{
377 struct deadline_data *dd = q->elevator->elevator_data;
378 struct deadline_rq *drq = RQ_DATA(req);
379 struct deadline_rq *dnext = RQ_DATA(next);
380
381 BUG_ON(!drq);
382 BUG_ON(!dnext);
383
384 /*
385 * reposition drq (this is the merged request) in hash, and in rbtree
386 * in case of a front merge
387 */
388 deadline_del_drq_hash(drq);
389 deadline_add_drq_hash(dd, drq);
390
391 if (rq_rb_key(req) != drq->rb_key) {
392 deadline_del_drq_rb(dd, drq);
393 deadline_add_drq_rb(dd, drq);
394 }
395
396 /*
397 * if dnext expires before drq, assign its expire time to drq
398 * and move into dnext position (dnext will be deleted) in fifo
399 */
400 if (!list_empty(&drq->fifo) && !list_empty(&dnext->fifo)) {
401 if (time_before(dnext->expires, drq->expires)) {
402 list_move(&drq->fifo, &dnext->fifo);
403 drq->expires = dnext->expires;
404 }
405 }
406
407 /*
408 * kill knowledge of next, this one is a goner
409 */
410 deadline_remove_request(q, next);
411}
412
413/*
414 * move request from sort list to dispatch queue.
415 */
416static inline void
417deadline_move_to_dispatch(struct deadline_data *dd, struct deadline_rq *drq)
418{
419 request_queue_t *q = drq->request->q;
420
421 deadline_remove_request(q, drq->request);
Jens Axboeb4878f22005-10-20 16:42:29 +0200422 elv_dispatch_add_tail(q, drq->request);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700423}
424
425/*
426 * move an entry to dispatch queue
427 */
428static void
429deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq)
430{
431 const int data_dir = rq_data_dir(drq->request);
432 struct rb_node *rbnext = rb_next(&drq->rb_node);
433
434 dd->next_drq[READ] = NULL;
435 dd->next_drq[WRITE] = NULL;
436
437 if (rbnext)
438 dd->next_drq[data_dir] = rb_entry_drq(rbnext);
439
440 dd->last_sector = drq->request->sector + drq->request->nr_sectors;
441
442 /*
443 * take it off the sort and fifo list, move
444 * to dispatch queue
445 */
446 deadline_move_to_dispatch(dd, drq);
447}
448
449#define list_entry_fifo(ptr) list_entry((ptr), struct deadline_rq, fifo)
450
451/*
452 * deadline_check_fifo returns 0 if there are no expired reads on the fifo,
453 * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
454 */
455static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
456{
457 struct deadline_rq *drq = list_entry_fifo(dd->fifo_list[ddir].next);
458
459 /*
460 * drq is expired!
461 */
462 if (time_after(jiffies, drq->expires))
463 return 1;
464
465 return 0;
466}
467
468/*
469 * deadline_dispatch_requests selects the best request according to
470 * read/write expire, fifo_batch, etc
471 */
Jens Axboeb4878f22005-10-20 16:42:29 +0200472static int deadline_dispatch_requests(request_queue_t *q, int force)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473{
Jens Axboeb4878f22005-10-20 16:42:29 +0200474 struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 const int reads = !list_empty(&dd->fifo_list[READ]);
476 const int writes = !list_empty(&dd->fifo_list[WRITE]);
477 struct deadline_rq *drq;
Nikita Danilov4b0dc072005-09-06 15:17:20 -0700478 int data_dir;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479
480 /*
481 * batches are currently reads XOR writes
482 */
Andrew Morton9d5c1e12005-09-09 13:02:12 -0700483 if (dd->next_drq[WRITE])
484 drq = dd->next_drq[WRITE];
485 else
486 drq = dd->next_drq[READ];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700487
488 if (drq) {
489 /* we have a "next request" */
490
491 if (dd->last_sector != drq->request->sector)
492 /* end the batch on a non sequential request */
493 dd->batching += dd->fifo_batch;
494
495 if (dd->batching < dd->fifo_batch)
496 /* we are still entitled to batch */
497 goto dispatch_request;
498 }
499
500 /*
501 * at this point we are not running a batch. select the appropriate
502 * data direction (read / write)
503 */
504
505 if (reads) {
506 BUG_ON(RB_EMPTY(&dd->sort_list[READ]));
507
508 if (writes && (dd->starved++ >= dd->writes_starved))
509 goto dispatch_writes;
510
511 data_dir = READ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512
513 goto dispatch_find_request;
514 }
515
516 /*
517 * there are either no reads or writes have been starved
518 */
519
520 if (writes) {
521dispatch_writes:
522 BUG_ON(RB_EMPTY(&dd->sort_list[WRITE]));
523
524 dd->starved = 0;
525
526 data_dir = WRITE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527
528 goto dispatch_find_request;
529 }
530
531 return 0;
532
533dispatch_find_request:
534 /*
535 * we are not running a batch, find best request for selected data_dir
536 */
537 if (deadline_check_fifo(dd, data_dir)) {
538 /* An expired request exists - satisfy it */
539 dd->batching = 0;
540 drq = list_entry_fifo(dd->fifo_list[data_dir].next);
541
542 } else if (dd->next_drq[data_dir]) {
543 /*
544 * The last req was the same dir and we have a next request in
545 * sort order. No expired requests so continue on from here.
546 */
547 drq = dd->next_drq[data_dir];
548 } else {
549 /*
550 * The last req was the other direction or we have run out of
551 * higher-sectored requests. Go back to the lowest sectored
552 * request (1 way elevator) and start a new batch.
553 */
554 dd->batching = 0;
555 drq = deadline_find_first_drq(dd, data_dir);
556 }
557
558dispatch_request:
559 /*
560 * drq is the selected appropriate request.
561 */
562 dd->batching++;
563 deadline_move_request(dd, drq);
564
565 return 1;
566}
567
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568static int deadline_queue_empty(request_queue_t *q)
569{
570 struct deadline_data *dd = q->elevator->elevator_data;
571
Jens Axboeb4878f22005-10-20 16:42:29 +0200572 return list_empty(&dd->fifo_list[WRITE])
573 && list_empty(&dd->fifo_list[READ]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574}
575
576static struct request *
577deadline_former_request(request_queue_t *q, struct request *rq)
578{
579 struct deadline_rq *drq = RQ_DATA(rq);
580 struct rb_node *rbprev = rb_prev(&drq->rb_node);
581
582 if (rbprev)
583 return rb_entry_drq(rbprev)->request;
584
585 return NULL;
586}
587
588static struct request *
589deadline_latter_request(request_queue_t *q, struct request *rq)
590{
591 struct deadline_rq *drq = RQ_DATA(rq);
592 struct rb_node *rbnext = rb_next(&drq->rb_node);
593
594 if (rbnext)
595 return rb_entry_drq(rbnext)->request;
596
597 return NULL;
598}
599
600static void deadline_exit_queue(elevator_t *e)
601{
602 struct deadline_data *dd = e->elevator_data;
603
604 BUG_ON(!list_empty(&dd->fifo_list[READ]));
605 BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
606
607 mempool_destroy(dd->drq_pool);
608 kfree(dd->hash);
609 kfree(dd);
610}
611
612/*
613 * initialize elevator private data (deadline_data), and alloc a drq for
614 * each request on the free lists
615 */
Jens Axboebc1c1162006-06-08 08:49:06 +0200616static void *deadline_init_queue(request_queue_t *q, elevator_t *e)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617{
618 struct deadline_data *dd;
619 int i;
620
621 if (!drq_pool)
Jens Axboebc1c1162006-06-08 08:49:06 +0200622 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623
Christoph Lameter19460892005-06-23 00:08:19 -0700624 dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625 if (!dd)
Jens Axboebc1c1162006-06-08 08:49:06 +0200626 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627 memset(dd, 0, sizeof(*dd));
628
Christoph Lameter19460892005-06-23 00:08:19 -0700629 dd->hash = kmalloc_node(sizeof(struct list_head)*DL_HASH_ENTRIES,
630 GFP_KERNEL, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700631 if (!dd->hash) {
632 kfree(dd);
Jens Axboebc1c1162006-06-08 08:49:06 +0200633 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634 }
635
Christoph Lameter19460892005-06-23 00:08:19 -0700636 dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
637 mempool_free_slab, drq_pool, q->node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700638 if (!dd->drq_pool) {
639 kfree(dd->hash);
640 kfree(dd);
Jens Axboebc1c1162006-06-08 08:49:06 +0200641 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642 }
643
644 for (i = 0; i < DL_HASH_ENTRIES; i++)
645 INIT_LIST_HEAD(&dd->hash[i]);
646
647 INIT_LIST_HEAD(&dd->fifo_list[READ]);
648 INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
649 dd->sort_list[READ] = RB_ROOT;
650 dd->sort_list[WRITE] = RB_ROOT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651 dd->fifo_expire[READ] = read_expire;
652 dd->fifo_expire[WRITE] = write_expire;
653 dd->writes_starved = writes_starved;
654 dd->front_merges = 1;
655 dd->fifo_batch = fifo_batch;
Jens Axboebc1c1162006-06-08 08:49:06 +0200656 return dd;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657}
658
659static void deadline_put_request(request_queue_t *q, struct request *rq)
660{
661 struct deadline_data *dd = q->elevator->elevator_data;
662 struct deadline_rq *drq = RQ_DATA(rq);
663
Jens Axboeb4878f22005-10-20 16:42:29 +0200664 mempool_free(drq, dd->drq_pool);
665 rq->elevator_private = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666}
667
668static int
Jens Axboe22e2c502005-06-27 10:55:12 +0200669deadline_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro8267e262005-10-21 03:20:53 -0400670 gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671{
672 struct deadline_data *dd = q->elevator->elevator_data;
673 struct deadline_rq *drq;
674
675 drq = mempool_alloc(dd->drq_pool, gfp_mask);
676 if (drq) {
677 memset(drq, 0, sizeof(*drq));
678 RB_CLEAR(&drq->rb_node);
679 drq->request = rq;
680
681 INIT_LIST_HEAD(&drq->hash);
682 drq->on_hash = 0;
683
684 INIT_LIST_HEAD(&drq->fifo);
685
686 rq->elevator_private = drq;
687 return 0;
688 }
689
690 return 1;
691}
692
693/*
694 * sysfs parts below
695 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700696
697static ssize_t
698deadline_var_show(int var, char *page)
699{
700 return sprintf(page, "%d\n", var);
701}
702
703static ssize_t
704deadline_var_store(int *var, const char *page, size_t count)
705{
706 char *p = (char *) page;
707
708 *var = simple_strtol(p, &p, 10);
709 return count;
710}
711
712#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -0500713static ssize_t __FUNC(elevator_t *e, char *page) \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714{ \
Al Viro3d1ab402006-03-18 18:35:43 -0500715 struct deadline_data *dd = e->elevator_data; \
716 int __data = __VAR; \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717 if (__CONV) \
718 __data = jiffies_to_msecs(__data); \
719 return deadline_var_show(__data, (page)); \
720}
Al Viroe572ec72006-03-18 22:27:18 -0500721SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
722SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
723SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
724SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
725SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726#undef SHOW_FUNCTION
727
728#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
Al Viro3d1ab402006-03-18 18:35:43 -0500729static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730{ \
Al Viro3d1ab402006-03-18 18:35:43 -0500731 struct deadline_data *dd = e->elevator_data; \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732 int __data; \
733 int ret = deadline_var_store(&__data, (page), count); \
734 if (__data < (MIN)) \
735 __data = (MIN); \
736 else if (__data > (MAX)) \
737 __data = (MAX); \
738 if (__CONV) \
739 *(__PTR) = msecs_to_jiffies(__data); \
740 else \
741 *(__PTR) = __data; \
742 return ret; \
743}
Al Viroe572ec72006-03-18 22:27:18 -0500744STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
745STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
746STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
747STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
748STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749#undef STORE_FUNCTION
750
Al Viroe572ec72006-03-18 22:27:18 -0500751#define DD_ATTR(name) \
752 __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
753 deadline_##name##_store)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700754
Al Viroe572ec72006-03-18 22:27:18 -0500755static struct elv_fs_entry deadline_attrs[] = {
756 DD_ATTR(read_expire),
757 DD_ATTR(write_expire),
758 DD_ATTR(writes_starved),
759 DD_ATTR(front_merges),
760 DD_ATTR(fifo_batch),
761 __ATTR_NULL
Linus Torvalds1da177e2005-04-16 15:20:36 -0700762};
763
Linus Torvalds1da177e2005-04-16 15:20:36 -0700764static struct elevator_type iosched_deadline = {
765 .ops = {
766 .elevator_merge_fn = deadline_merge,
767 .elevator_merged_fn = deadline_merged_request,
768 .elevator_merge_req_fn = deadline_merged_requests,
Jens Axboeb4878f22005-10-20 16:42:29 +0200769 .elevator_dispatch_fn = deadline_dispatch_requests,
770 .elevator_add_req_fn = deadline_add_request,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700771 .elevator_queue_empty_fn = deadline_queue_empty,
772 .elevator_former_req_fn = deadline_former_request,
773 .elevator_latter_req_fn = deadline_latter_request,
774 .elevator_set_req_fn = deadline_set_request,
775 .elevator_put_req_fn = deadline_put_request,
776 .elevator_init_fn = deadline_init_queue,
777 .elevator_exit_fn = deadline_exit_queue,
778 },
779
Al Viro3d1ab402006-03-18 18:35:43 -0500780 .elevator_attrs = deadline_attrs,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781 .elevator_name = "deadline",
782 .elevator_owner = THIS_MODULE,
783};
784
785static int __init deadline_init(void)
786{
787 int ret;
788
789 drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq),
790 0, 0, NULL, NULL);
791
792 if (!drq_pool)
793 return -ENOMEM;
794
795 ret = elv_register(&iosched_deadline);
796 if (ret)
797 kmem_cache_destroy(drq_pool);
798
799 return ret;
800}
801
802static void __exit deadline_exit(void)
803{
804 kmem_cache_destroy(drq_pool);
805 elv_unregister(&iosched_deadline);
806}
807
808module_init(deadline_init);
809module_exit(deadline_exit);
810
811MODULE_AUTHOR("Jens Axboe");
812MODULE_LICENSE("GPL");
813MODULE_DESCRIPTION("deadline IO scheduler");