2 * Deadline i/o scheduler.
4 * Copyright (C) 2002 Jens Axboe <axboe@kernel.dk>
6 #include <linux/kernel.h>
8 #include <linux/blkdev.h>
9 #include <linux/elevator.h>
10 #include <linux/bio.h>
11 #include <linux/module.h>
12 #include <linux/slab.h>
13 #include <linux/init.h>
14 #include <linux/compiler.h>
15 #include <linux/rbtree.h>
18 * See Documentation/block/deadline-iosched.txt
20 static const int read_expire
= HZ
/ 2; /* max time before a read is submitted. */
21 static const int write_expire
= 5 * HZ
; /* ditto for writes, these limits are SOFT! */
22 static const int writes_starved
= 2; /* max times reads can starve a write */
23 static const int fifo_batch
= 16; /* # of sequential requests treated as one
24 by the above parameters. For throughput. */
26 struct deadline_data
{
32 * requests (deadline_rq s) are present on both sort_list and fifo_list
34 struct rb_root sort_list
[2];
35 struct list_head fifo_list
[2];
38 * next in sort order. read, write or both are NULL
40 struct request
*next_rq
[2];
41 unsigned int batching
; /* number of sequential requests made */
42 sector_t last_sector
; /* head position */
43 unsigned int starved
; /* times reads have starved writes */
46 * settings that change how the i/o scheduler behaves
54 static void deadline_move_request(struct deadline_data
*, struct request
*);
56 static inline struct rb_root
*
57 deadline_rb_root(struct deadline_data
*dd
, struct request
*rq
)
59 return &dd
->sort_list
[rq_data_dir(rq
)];
63 * get the request after `rq' in sector-sorted order
65 static inline struct request
*
66 deadline_latter_request(struct request
*rq
)
68 struct rb_node
*node
= rb_next(&rq
->rb_node
);
71 return rb_entry_rq(node
);
77 deadline_add_rq_rb(struct deadline_data
*dd
, struct request
*rq
)
79 struct rb_root
*root
= deadline_rb_root(dd
, rq
);
85 deadline_del_rq_rb(struct deadline_data
*dd
, struct request
*rq
)
87 const int data_dir
= rq_data_dir(rq
);
89 if (dd
->next_rq
[data_dir
] == rq
)
90 dd
->next_rq
[data_dir
] = deadline_latter_request(rq
);
92 elv_rb_del(deadline_rb_root(dd
, rq
), rq
);
96 * add rq to rbtree and fifo
99 deadline_add_request(struct request_queue
*q
, struct request
*rq
)
101 struct deadline_data
*dd
= q
->elevator
->elevator_data
;
102 const int data_dir
= rq_data_dir(rq
);
104 deadline_add_rq_rb(dd
, rq
);
107 * set expire time and add to fifo list
109 rq_set_fifo_time(rq
, jiffies
+ dd
->fifo_expire
[data_dir
]);
110 list_add_tail(&rq
->queuelist
, &dd
->fifo_list
[data_dir
]);
114 * remove rq from rbtree and fifo.
116 static void deadline_remove_request(struct request_queue
*q
, struct request
*rq
)
118 struct deadline_data
*dd
= q
->elevator
->elevator_data
;
121 deadline_del_rq_rb(dd
, rq
);
125 deadline_merge(struct request_queue
*q
, struct request
**req
, struct bio
*bio
)
127 struct deadline_data
*dd
= q
->elevator
->elevator_data
;
128 struct request
*__rq
;
132 * check for front merge
134 if (dd
->front_merges
) {
135 sector_t sector
= bio
->bi_sector
+ bio_sectors(bio
);
137 __rq
= elv_rb_find(&dd
->sort_list
[bio_data_dir(bio
)], sector
);
139 BUG_ON(sector
!= blk_rq_pos(__rq
));
141 if (elv_rq_merge_ok(__rq
, bio
)) {
142 ret
= ELEVATOR_FRONT_MERGE
;
148 return ELEVATOR_NO_MERGE
;
154 static void deadline_merged_request(struct request_queue
*q
,
155 struct request
*req
, int type
)
157 struct deadline_data
*dd
= q
->elevator
->elevator_data
;
160 * if the merge was a front merge, we need to reposition request
162 if (type
== ELEVATOR_FRONT_MERGE
) {
163 elv_rb_del(deadline_rb_root(dd
, req
), req
);
164 deadline_add_rq_rb(dd
, req
);
169 deadline_merged_requests(struct request_queue
*q
, struct request
*req
,
170 struct request
*next
)
173 * if next expires before rq, assign its expire time to rq
174 * and move into next position (next will be deleted) in fifo
176 if (!list_empty(&req
->queuelist
) && !list_empty(&next
->queuelist
)) {
177 if (time_before(rq_fifo_time(next
), rq_fifo_time(req
))) {
178 list_move(&req
->queuelist
, &next
->queuelist
);
179 rq_set_fifo_time(req
, rq_fifo_time(next
));
184 * kill knowledge of next, this one is a goner
186 deadline_remove_request(q
, next
);
190 * move request from sort list to dispatch queue.
193 deadline_move_to_dispatch(struct deadline_data
*dd
, struct request
*rq
)
195 struct request_queue
*q
= rq
->q
;
197 deadline_remove_request(q
, rq
);
198 elv_dispatch_add_tail(q
, rq
);
202 * move an entry to dispatch queue
205 deadline_move_request(struct deadline_data
*dd
, struct request
*rq
)
207 const int data_dir
= rq_data_dir(rq
);
209 dd
->next_rq
[READ
] = NULL
;
210 dd
->next_rq
[WRITE
] = NULL
;
211 dd
->next_rq
[data_dir
] = deadline_latter_request(rq
);
213 dd
->last_sector
= rq_end_sector(rq
);
216 * take it off the sort and fifo list, move
219 deadline_move_to_dispatch(dd
, rq
);
223 * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
224 * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
226 static inline int deadline_check_fifo(struct deadline_data
*dd
, int ddir
)
228 struct request
*rq
= rq_entry_fifo(dd
->fifo_list
[ddir
].next
);
233 if (time_after(jiffies
, rq_fifo_time(rq
)))
240 * deadline_dispatch_requests selects the best request according to
241 * read/write expire, fifo_batch, etc
243 static int deadline_dispatch_requests(struct request_queue
*q
, int force
)
245 struct deadline_data
*dd
= q
->elevator
->elevator_data
;
246 const int reads
= !list_empty(&dd
->fifo_list
[READ
]);
247 const int writes
= !list_empty(&dd
->fifo_list
[WRITE
]);
252 * batches are currently reads XOR writes
254 if (dd
->next_rq
[WRITE
])
255 rq
= dd
->next_rq
[WRITE
];
257 rq
= dd
->next_rq
[READ
];
259 if (rq
&& dd
->batching
< dd
->fifo_batch
)
260 /* we have a next request are still entitled to batch */
261 goto dispatch_request
;
264 * at this point we are not running a batch. select the appropriate
265 * data direction (read / write)
269 BUG_ON(RB_EMPTY_ROOT(&dd
->sort_list
[READ
]));
271 if (writes
&& (dd
->starved
++ >= dd
->writes_starved
))
272 goto dispatch_writes
;
276 goto dispatch_find_request
;
280 * there are either no reads or writes have been starved
285 BUG_ON(RB_EMPTY_ROOT(&dd
->sort_list
[WRITE
]));
291 goto dispatch_find_request
;
296 dispatch_find_request
:
298 * we are not running a batch, find best request for selected data_dir
300 if (deadline_check_fifo(dd
, data_dir
) || !dd
->next_rq
[data_dir
]) {
302 * A deadline has expired, the last request was in the other
303 * direction, or we have run out of higher-sectored requests.
304 * Start again from the request with the earliest expiry time.
306 rq
= rq_entry_fifo(dd
->fifo_list
[data_dir
].next
);
309 * The last req was the same dir and we have a next request in
310 * sort order. No expired requests so continue on from here.
312 rq
= dd
->next_rq
[data_dir
];
319 * rq is the selected appropriate request.
322 deadline_move_request(dd
, rq
);
327 static void deadline_exit_queue(struct elevator_queue
*e
)
329 struct deadline_data
*dd
= e
->elevator_data
;
331 BUG_ON(!list_empty(&dd
->fifo_list
[READ
]));
332 BUG_ON(!list_empty(&dd
->fifo_list
[WRITE
]));
338 * initialize elevator private data (deadline_data).
340 static void *deadline_init_queue(struct request_queue
*q
)
342 struct deadline_data
*dd
;
344 dd
= kmalloc_node(sizeof(*dd
), GFP_KERNEL
| __GFP_ZERO
, q
->node
);
348 INIT_LIST_HEAD(&dd
->fifo_list
[READ
]);
349 INIT_LIST_HEAD(&dd
->fifo_list
[WRITE
]);
350 dd
->sort_list
[READ
] = RB_ROOT
;
351 dd
->sort_list
[WRITE
] = RB_ROOT
;
352 dd
->fifo_expire
[READ
] = read_expire
;
353 dd
->fifo_expire
[WRITE
] = write_expire
;
354 dd
->writes_starved
= writes_starved
;
355 dd
->front_merges
= 1;
356 dd
->fifo_batch
= fifo_batch
;
365 deadline_var_show(int var
, char *page
)
367 return sprintf(page
, "%d\n", var
);
371 deadline_var_store(int *var
, const char *page
, size_t count
)
373 char *p
= (char *) page
;
375 *var
= simple_strtol(p
, &p
, 10);
379 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
380 static ssize_t __FUNC(struct elevator_queue *e, char *page) \
382 struct deadline_data *dd = e->elevator_data; \
383 int __data = __VAR; \
385 __data = jiffies_to_msecs(__data); \
386 return deadline_var_show(__data, (page)); \
388 SHOW_FUNCTION(deadline_read_expire_show
, dd
->fifo_expire
[READ
], 1);
389 SHOW_FUNCTION(deadline_write_expire_show
, dd
->fifo_expire
[WRITE
], 1);
390 SHOW_FUNCTION(deadline_writes_starved_show
, dd
->writes_starved
, 0);
391 SHOW_FUNCTION(deadline_front_merges_show
, dd
->front_merges
, 0);
392 SHOW_FUNCTION(deadline_fifo_batch_show
, dd
->fifo_batch
, 0);
395 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
396 static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
398 struct deadline_data *dd = e->elevator_data; \
400 int ret = deadline_var_store(&__data, (page), count); \
401 if (__data < (MIN)) \
403 else if (__data > (MAX)) \
406 *(__PTR) = msecs_to_jiffies(__data); \
411 STORE_FUNCTION(deadline_read_expire_store
, &dd
->fifo_expire
[READ
], 0, INT_MAX
, 1);
412 STORE_FUNCTION(deadline_write_expire_store
, &dd
->fifo_expire
[WRITE
], 0, INT_MAX
, 1);
413 STORE_FUNCTION(deadline_writes_starved_store
, &dd
->writes_starved
, INT_MIN
, INT_MAX
, 0);
414 STORE_FUNCTION(deadline_front_merges_store
, &dd
->front_merges
, 0, 1, 0);
415 STORE_FUNCTION(deadline_fifo_batch_store
, &dd
->fifo_batch
, 0, INT_MAX
, 0);
416 #undef STORE_FUNCTION
418 #define DD_ATTR(name) \
419 __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
420 deadline_##name##_store)
422 static struct elv_fs_entry deadline_attrs
[] = {
423 DD_ATTR(read_expire
),
424 DD_ATTR(write_expire
),
425 DD_ATTR(writes_starved
),
426 DD_ATTR(front_merges
),
431 static struct elevator_type iosched_deadline
= {
433 .elevator_merge_fn
= deadline_merge
,
434 .elevator_merged_fn
= deadline_merged_request
,
435 .elevator_merge_req_fn
= deadline_merged_requests
,
436 .elevator_dispatch_fn
= deadline_dispatch_requests
,
437 .elevator_add_req_fn
= deadline_add_request
,
438 .elevator_former_req_fn
= elv_rb_former_request
,
439 .elevator_latter_req_fn
= elv_rb_latter_request
,
440 .elevator_init_fn
= deadline_init_queue
,
441 .elevator_exit_fn
= deadline_exit_queue
,
444 .elevator_attrs
= deadline_attrs
,
445 .elevator_name
= "deadline",
446 .elevator_owner
= THIS_MODULE
,
449 static int __init
deadline_init(void)
451 elv_register(&iosched_deadline
);
456 static void __exit
deadline_exit(void)
458 elv_unregister(&iosched_deadline
);
461 module_init(deadline_init
);
462 module_exit(deadline_exit
);
464 MODULE_AUTHOR("Jens Axboe");
465 MODULE_LICENSE("GPL");
466 MODULE_DESCRIPTION("deadline IO scheduler");