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