blob: 55e0bb6d7da796e3b526a16832914ca88fcb879f
1 | /* |
2 | * Deadline i/o scheduler. |
3 | * |
4 | * Copyright (C) 2002 Jens Axboe <axboe@kernel.dk> |
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/module.h> |
12 | #include <linux/slab.h> |
13 | #include <linux/init.h> |
14 | #include <linux/compiler.h> |
15 | #include <linux/rbtree.h> |
16 | |
17 | /* |
18 | * See Documentation/block/deadline-iosched.txt |
19 | */ |
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. */ |
25 | |
26 | struct deadline_data { |
27 | /* |
28 | * run time data |
29 | */ |
30 | |
31 | /* |
32 | * requests (deadline_rq s) are present on both sort_list and fifo_list |
33 | */ |
34 | struct rb_root sort_list[2]; |
35 | struct list_head fifo_list[2]; |
36 | |
37 | /* |
38 | * next in sort order. read, write or both are NULL |
39 | */ |
40 | struct request *next_rq[2]; |
41 | unsigned int batching; /* number of sequential requests made */ |
42 | unsigned int starved; /* times reads have starved writes */ |
43 | |
44 | /* |
45 | * settings that change how the i/o scheduler behaves |
46 | */ |
47 | int fifo_expire[2]; |
48 | int fifo_batch; |
49 | int writes_starved; |
50 | int front_merges; |
51 | }; |
52 | |
53 | static void deadline_move_request(struct deadline_data *, struct request *); |
54 | |
55 | static inline struct rb_root * |
56 | deadline_rb_root(struct deadline_data *dd, struct request *rq) |
57 | { |
58 | return &dd->sort_list[rq_data_dir(rq)]; |
59 | } |
60 | |
61 | /* |
62 | * get the request after `rq' in sector-sorted order |
63 | */ |
64 | static inline struct request * |
65 | deadline_latter_request(struct request *rq) |
66 | { |
67 | struct rb_node *node = rb_next(&rq->rb_node); |
68 | |
69 | if (node) |
70 | return rb_entry_rq(node); |
71 | |
72 | return NULL; |
73 | } |
74 | |
75 | static void |
76 | deadline_add_rq_rb(struct deadline_data *dd, struct request *rq) |
77 | { |
78 | struct rb_root *root = deadline_rb_root(dd, rq); |
79 | |
80 | elv_rb_add(root, rq); |
81 | } |
82 | |
83 | static inline void |
84 | deadline_del_rq_rb(struct deadline_data *dd, struct request *rq) |
85 | { |
86 | const int data_dir = rq_data_dir(rq); |
87 | |
88 | if (dd->next_rq[data_dir] == rq) |
89 | dd->next_rq[data_dir] = deadline_latter_request(rq); |
90 | |
91 | elv_rb_del(deadline_rb_root(dd, rq), rq); |
92 | } |
93 | |
94 | /* |
95 | * add rq to rbtree and fifo |
96 | */ |
97 | static void |
98 | deadline_add_request(struct request_queue *q, struct request *rq) |
99 | { |
100 | struct deadline_data *dd = q->elevator->elevator_data; |
101 | const int data_dir = rq_data_dir(rq); |
102 | |
103 | deadline_add_rq_rb(dd, rq); |
104 | |
105 | /* |
106 | * set expire time and add to fifo list |
107 | */ |
108 | rq->fifo_time = jiffies + dd->fifo_expire[data_dir]; |
109 | list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]); |
110 | } |
111 | |
112 | /* |
113 | * remove rq from rbtree and fifo. |
114 | */ |
115 | static void deadline_remove_request(struct request_queue *q, struct request *rq) |
116 | { |
117 | struct deadline_data *dd = q->elevator->elevator_data; |
118 | |
119 | rq_fifo_clear(rq); |
120 | deadline_del_rq_rb(dd, rq); |
121 | } |
122 | |
123 | static int |
124 | deadline_merge(struct request_queue *q, struct request **req, struct bio *bio) |
125 | { |
126 | struct deadline_data *dd = q->elevator->elevator_data; |
127 | struct request *__rq; |
128 | int ret; |
129 | |
130 | /* |
131 | * check for front merge |
132 | */ |
133 | if (dd->front_merges) { |
134 | sector_t sector = bio_end_sector(bio); |
135 | |
136 | __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector); |
137 | if (__rq) { |
138 | BUG_ON(sector != blk_rq_pos(__rq)); |
139 | |
140 | if (elv_bio_merge_ok(__rq, bio)) { |
141 | ret = ELEVATOR_FRONT_MERGE; |
142 | goto out; |
143 | } |
144 | } |
145 | } |
146 | |
147 | return ELEVATOR_NO_MERGE; |
148 | out: |
149 | *req = __rq; |
150 | return ret; |
151 | } |
152 | |
153 | static void deadline_merged_request(struct request_queue *q, |
154 | struct request *req, int type) |
155 | { |
156 | struct deadline_data *dd = q->elevator->elevator_data; |
157 | |
158 | /* |
159 | * if the merge was a front merge, we need to reposition request |
160 | */ |
161 | if (type == ELEVATOR_FRONT_MERGE) { |
162 | elv_rb_del(deadline_rb_root(dd, req), req); |
163 | deadline_add_rq_rb(dd, req); |
164 | } |
165 | } |
166 | |
167 | static void |
168 | deadline_merged_requests(struct request_queue *q, struct request *req, |
169 | struct request *next) |
170 | { |
171 | /* |
172 | * if next expires before rq, assign its expire time to rq |
173 | * and move into next position (next will be deleted) in fifo |
174 | */ |
175 | if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) { |
176 | if (time_before((unsigned long)next->fifo_time, |
177 | (unsigned long)req->fifo_time)) { |
178 | list_move(&req->queuelist, &next->queuelist); |
179 | req->fifo_time = next->fifo_time; |
180 | } |
181 | } |
182 | |
183 | /* |
184 | * kill knowledge of next, this one is a goner |
185 | */ |
186 | deadline_remove_request(q, next); |
187 | } |
188 | |
189 | /* |
190 | * move request from sort list to dispatch queue. |
191 | */ |
192 | static inline void |
193 | deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq) |
194 | { |
195 | struct request_queue *q = rq->q; |
196 | |
197 | deadline_remove_request(q, rq); |
198 | elv_dispatch_add_tail(q, rq); |
199 | } |
200 | |
201 | /* |
202 | * move an entry to dispatch queue |
203 | */ |
204 | static void |
205 | deadline_move_request(struct deadline_data *dd, struct request *rq) |
206 | { |
207 | const int data_dir = rq_data_dir(rq); |
208 | |
209 | dd->next_rq[READ] = NULL; |
210 | dd->next_rq[WRITE] = NULL; |
211 | dd->next_rq[data_dir] = deadline_latter_request(rq); |
212 | |
213 | /* |
214 | * take it off the sort and fifo list, move |
215 | * to dispatch queue |
216 | */ |
217 | deadline_move_to_dispatch(dd, rq); |
218 | } |
219 | |
220 | /* |
221 | * deadline_check_fifo returns 0 if there are no expired requests on the fifo, |
222 | * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir]) |
223 | */ |
224 | static inline int deadline_check_fifo(struct deadline_data *dd, int ddir) |
225 | { |
226 | struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next); |
227 | |
228 | /* |
229 | * rq is expired! |
230 | */ |
231 | if (time_after_eq(jiffies, (unsigned long)rq->fifo_time)) |
232 | return 1; |
233 | |
234 | return 0; |
235 | } |
236 | |
237 | /* |
238 | * deadline_dispatch_requests selects the best request according to |
239 | * read/write expire, fifo_batch, etc |
240 | */ |
241 | static int deadline_dispatch_requests(struct request_queue *q, int force) |
242 | { |
243 | struct deadline_data *dd = q->elevator->elevator_data; |
244 | const int reads = !list_empty(&dd->fifo_list[READ]); |
245 | const int writes = !list_empty(&dd->fifo_list[WRITE]); |
246 | struct request *rq; |
247 | int data_dir; |
248 | |
249 | /* |
250 | * batches are currently reads XOR writes |
251 | */ |
252 | if (dd->next_rq[WRITE]) |
253 | rq = dd->next_rq[WRITE]; |
254 | else |
255 | rq = dd->next_rq[READ]; |
256 | |
257 | if (rq && dd->batching < dd->fifo_batch) |
258 | /* we have a next request are still entitled to batch */ |
259 | goto dispatch_request; |
260 | |
261 | /* |
262 | * at this point we are not running a batch. select the appropriate |
263 | * data direction (read / write) |
264 | */ |
265 | |
266 | if (reads) { |
267 | BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ])); |
268 | |
269 | if (writes && (dd->starved++ >= dd->writes_starved)) |
270 | goto dispatch_writes; |
271 | |
272 | data_dir = READ; |
273 | |
274 | goto dispatch_find_request; |
275 | } |
276 | |
277 | /* |
278 | * there are either no reads or writes have been starved |
279 | */ |
280 | |
281 | if (writes) { |
282 | dispatch_writes: |
283 | BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE])); |
284 | |
285 | dd->starved = 0; |
286 | |
287 | data_dir = WRITE; |
288 | |
289 | goto dispatch_find_request; |
290 | } |
291 | |
292 | return 0; |
293 | |
294 | dispatch_find_request: |
295 | /* |
296 | * we are not running a batch, find best request for selected data_dir |
297 | */ |
298 | if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) { |
299 | /* |
300 | * A deadline has expired, the last request was in the other |
301 | * direction, or we have run out of higher-sectored requests. |
302 | * Start again from the request with the earliest expiry time. |
303 | */ |
304 | rq = rq_entry_fifo(dd->fifo_list[data_dir].next); |
305 | } else { |
306 | /* |
307 | * The last req was the same dir and we have a next request in |
308 | * sort order. No expired requests so continue on from here. |
309 | */ |
310 | rq = dd->next_rq[data_dir]; |
311 | } |
312 | |
313 | dd->batching = 0; |
314 | |
315 | dispatch_request: |
316 | /* |
317 | * rq is the selected appropriate request. |
318 | */ |
319 | dd->batching++; |
320 | deadline_move_request(dd, rq); |
321 | |
322 | return 1; |
323 | } |
324 | |
325 | static void deadline_exit_queue(struct elevator_queue *e) |
326 | { |
327 | struct deadline_data *dd = e->elevator_data; |
328 | |
329 | BUG_ON(!list_empty(&dd->fifo_list[READ])); |
330 | BUG_ON(!list_empty(&dd->fifo_list[WRITE])); |
331 | |
332 | kfree(dd); |
333 | } |
334 | |
335 | /* |
336 | * initialize elevator private data (deadline_data). |
337 | */ |
338 | static int deadline_init_queue(struct request_queue *q, struct elevator_type *e) |
339 | { |
340 | struct deadline_data *dd; |
341 | struct elevator_queue *eq; |
342 | |
343 | eq = elevator_alloc(q, e); |
344 | if (!eq) |
345 | return -ENOMEM; |
346 | |
347 | dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node); |
348 | if (!dd) { |
349 | kobject_put(&eq->kobj); |
350 | return -ENOMEM; |
351 | } |
352 | eq->elevator_data = dd; |
353 | |
354 | INIT_LIST_HEAD(&dd->fifo_list[READ]); |
355 | INIT_LIST_HEAD(&dd->fifo_list[WRITE]); |
356 | dd->sort_list[READ] = RB_ROOT; |
357 | dd->sort_list[WRITE] = RB_ROOT; |
358 | dd->fifo_expire[READ] = read_expire; |
359 | dd->fifo_expire[WRITE] = write_expire; |
360 | dd->writes_starved = writes_starved; |
361 | dd->front_merges = 1; |
362 | dd->fifo_batch = fifo_batch; |
363 | |
364 | spin_lock_irq(q->queue_lock); |
365 | q->elevator = eq; |
366 | spin_unlock_irq(q->queue_lock); |
367 | return 0; |
368 | } |
369 | |
370 | /* |
371 | * sysfs parts below |
372 | */ |
373 | |
374 | static ssize_t |
375 | deadline_var_show(int var, char *page) |
376 | { |
377 | return sprintf(page, "%d\n", var); |
378 | } |
379 | |
380 | static ssize_t |
381 | deadline_var_store(int *var, const char *page, size_t count) |
382 | { |
383 | char *p = (char *) page; |
384 | |
385 | *var = simple_strtol(p, &p, 10); |
386 | return count; |
387 | } |
388 | |
389 | #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ |
390 | static ssize_t __FUNC(struct elevator_queue *e, char *page) \ |
391 | { \ |
392 | struct deadline_data *dd = e->elevator_data; \ |
393 | int __data = __VAR; \ |
394 | if (__CONV) \ |
395 | __data = jiffies_to_msecs(__data); \ |
396 | return deadline_var_show(__data, (page)); \ |
397 | } |
398 | SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1); |
399 | SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1); |
400 | SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0); |
401 | SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0); |
402 | SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0); |
403 | #undef SHOW_FUNCTION |
404 | |
405 | #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ |
406 | static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \ |
407 | { \ |
408 | struct deadline_data *dd = e->elevator_data; \ |
409 | int __data; \ |
410 | int ret = deadline_var_store(&__data, (page), count); \ |
411 | if (__data < (MIN)) \ |
412 | __data = (MIN); \ |
413 | else if (__data > (MAX)) \ |
414 | __data = (MAX); \ |
415 | if (__CONV) \ |
416 | *(__PTR) = msecs_to_jiffies(__data); \ |
417 | else \ |
418 | *(__PTR) = __data; \ |
419 | return ret; \ |
420 | } |
421 | STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1); |
422 | STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1); |
423 | STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0); |
424 | STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0); |
425 | STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0); |
426 | #undef STORE_FUNCTION |
427 | |
428 | #define DD_ATTR(name) \ |
429 | __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \ |
430 | deadline_##name##_store) |
431 | |
432 | static struct elv_fs_entry deadline_attrs[] = { |
433 | DD_ATTR(read_expire), |
434 | DD_ATTR(write_expire), |
435 | DD_ATTR(writes_starved), |
436 | DD_ATTR(front_merges), |
437 | DD_ATTR(fifo_batch), |
438 | __ATTR_NULL |
439 | }; |
440 | |
441 | static struct elevator_type iosched_deadline = { |
442 | .ops = { |
443 | .elevator_merge_fn = deadline_merge, |
444 | .elevator_merged_fn = deadline_merged_request, |
445 | .elevator_merge_req_fn = deadline_merged_requests, |
446 | .elevator_dispatch_fn = deadline_dispatch_requests, |
447 | .elevator_add_req_fn = deadline_add_request, |
448 | .elevator_former_req_fn = elv_rb_former_request, |
449 | .elevator_latter_req_fn = elv_rb_latter_request, |
450 | .elevator_init_fn = deadline_init_queue, |
451 | .elevator_exit_fn = deadline_exit_queue, |
452 | }, |
453 | |
454 | .elevator_attrs = deadline_attrs, |
455 | .elevator_name = "deadline", |
456 | .elevator_owner = THIS_MODULE, |
457 | }; |
458 | |
459 | static int __init deadline_init(void) |
460 | { |
461 | return elv_register(&iosched_deadline); |
462 | } |
463 | |
464 | static void __exit deadline_exit(void) |
465 | { |
466 | elv_unregister(&iosched_deadline); |
467 | } |
468 | |
469 | module_init(deadline_init); |
470 | module_exit(deadline_exit); |
471 | |
472 | MODULE_AUTHOR("Jens Axboe"); |
473 | MODULE_LICENSE("GPL"); |
474 | MODULE_DESCRIPTION("deadline IO scheduler"); |
475 |