]>
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 | 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 enum elv_merge | |
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 | ||
129 | /* | |
130 | * check for front merge | |
131 | */ | |
132 | if (dd->front_merges) { | |
133 | sector_t sector = bio_end_sector(bio); | |
134 | ||
135 | __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector); | |
136 | if (__rq) { | |
137 | BUG_ON(sector != blk_rq_pos(__rq)); | |
138 | ||
139 | if (elv_bio_merge_ok(__rq, bio)) { | |
140 | *req = __rq; | |
141 | return ELEVATOR_FRONT_MERGE; | |
142 | } | |
143 | } | |
144 | } | |
145 | ||
146 | return ELEVATOR_NO_MERGE; | |
147 | } | |
148 | ||
149 | static void deadline_merged_request(struct request_queue *q, | |
150 | struct request *req, enum elv_merge type) | |
151 | { | |
152 | struct deadline_data *dd = q->elevator->elevator_data; | |
153 | ||
154 | /* | |
155 | * if the merge was a front merge, we need to reposition request | |
156 | */ | |
157 | if (type == ELEVATOR_FRONT_MERGE) { | |
158 | elv_rb_del(deadline_rb_root(dd, req), req); | |
159 | deadline_add_rq_rb(dd, req); | |
160 | } | |
161 | } | |
162 | ||
163 | static void | |
164 | deadline_merged_requests(struct request_queue *q, struct request *req, | |
165 | struct request *next) | |
166 | { | |
167 | /* | |
168 | * if next expires before rq, assign its expire time to rq | |
169 | * and move into next position (next will be deleted) in fifo | |
170 | */ | |
171 | if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) { | |
172 | if (time_before((unsigned long)next->fifo_time, | |
173 | (unsigned long)req->fifo_time)) { | |
174 | list_move(&req->queuelist, &next->queuelist); | |
175 | req->fifo_time = next->fifo_time; | |
176 | } | |
177 | } | |
178 | ||
179 | /* | |
180 | * kill knowledge of next, this one is a goner | |
181 | */ | |
182 | deadline_remove_request(q, next); | |
183 | } | |
184 | ||
185 | /* | |
186 | * move request from sort list to dispatch queue. | |
187 | */ | |
188 | static inline void | |
189 | deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq) | |
190 | { | |
191 | struct request_queue *q = rq->q; | |
192 | ||
193 | deadline_remove_request(q, rq); | |
194 | elv_dispatch_add_tail(q, rq); | |
195 | } | |
196 | ||
197 | /* | |
198 | * move an entry to dispatch queue | |
199 | */ | |
200 | static void | |
201 | deadline_move_request(struct deadline_data *dd, struct request *rq) | |
202 | { | |
203 | const int data_dir = rq_data_dir(rq); | |
204 | ||
205 | dd->next_rq[READ] = NULL; | |
206 | dd->next_rq[WRITE] = NULL; | |
207 | dd->next_rq[data_dir] = deadline_latter_request(rq); | |
208 | ||
209 | /* | |
210 | * take it off the sort and fifo list, move | |
211 | * to dispatch queue | |
212 | */ | |
213 | deadline_move_to_dispatch(dd, rq); | |
214 | } | |
215 | ||
216 | /* | |
217 | * deadline_check_fifo returns 0 if there are no expired requests on the fifo, | |
218 | * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir]) | |
219 | */ | |
220 | static inline int deadline_check_fifo(struct deadline_data *dd, int ddir) | |
221 | { | |
222 | struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next); | |
223 | ||
224 | /* | |
225 | * rq is expired! | |
226 | */ | |
227 | if (time_after_eq(jiffies, (unsigned long)rq->fifo_time)) | |
228 | return 1; | |
229 | ||
230 | return 0; | |
231 | } | |
232 | ||
233 | /* | |
234 | * deadline_dispatch_requests selects the best request according to | |
235 | * read/write expire, fifo_batch, etc | |
236 | */ | |
237 | static int deadline_dispatch_requests(struct request_queue *q, int force) | |
238 | { | |
239 | struct deadline_data *dd = q->elevator->elevator_data; | |
240 | const int reads = !list_empty(&dd->fifo_list[READ]); | |
241 | const int writes = !list_empty(&dd->fifo_list[WRITE]); | |
242 | struct request *rq; | |
243 | int data_dir; | |
244 | ||
245 | /* | |
246 | * batches are currently reads XOR writes | |
247 | */ | |
248 | if (dd->next_rq[WRITE]) | |
249 | rq = dd->next_rq[WRITE]; | |
250 | else | |
251 | rq = dd->next_rq[READ]; | |
252 | ||
253 | if (rq && dd->batching < dd->fifo_batch) | |
254 | /* we have a next request are still entitled to batch */ | |
255 | goto dispatch_request; | |
256 | ||
257 | /* | |
258 | * at this point we are not running a batch. select the appropriate | |
259 | * data direction (read / write) | |
260 | */ | |
261 | ||
262 | if (reads) { | |
263 | BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ])); | |
264 | ||
265 | if (writes && (dd->starved++ >= dd->writes_starved)) | |
266 | goto dispatch_writes; | |
267 | ||
268 | data_dir = READ; | |
269 | ||
270 | goto dispatch_find_request; | |
271 | } | |
272 | ||
273 | /* | |
274 | * there are either no reads or writes have been starved | |
275 | */ | |
276 | ||
277 | if (writes) { | |
278 | dispatch_writes: | |
279 | BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE])); | |
280 | ||
281 | dd->starved = 0; | |
282 | ||
283 | data_dir = WRITE; | |
284 | ||
285 | goto dispatch_find_request; | |
286 | } | |
287 | ||
288 | return 0; | |
289 | ||
290 | dispatch_find_request: | |
291 | /* | |
292 | * we are not running a batch, find best request for selected data_dir | |
293 | */ | |
294 | if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) { | |
295 | /* | |
296 | * A deadline has expired, the last request was in the other | |
297 | * direction, or we have run out of higher-sectored requests. | |
298 | * Start again from the request with the earliest expiry time. | |
299 | */ | |
300 | rq = rq_entry_fifo(dd->fifo_list[data_dir].next); | |
301 | } else { | |
302 | /* | |
303 | * The last req was the same dir and we have a next request in | |
304 | * sort order. No expired requests so continue on from here. | |
305 | */ | |
306 | rq = dd->next_rq[data_dir]; | |
307 | } | |
308 | ||
309 | dd->batching = 0; | |
310 | ||
311 | dispatch_request: | |
312 | /* | |
313 | * rq is the selected appropriate request. | |
314 | */ | |
315 | dd->batching++; | |
316 | deadline_move_request(dd, rq); | |
317 | ||
318 | return 1; | |
319 | } | |
320 | ||
321 | static void deadline_exit_queue(struct elevator_queue *e) | |
322 | { | |
323 | struct deadline_data *dd = e->elevator_data; | |
324 | ||
325 | BUG_ON(!list_empty(&dd->fifo_list[READ])); | |
326 | BUG_ON(!list_empty(&dd->fifo_list[WRITE])); | |
327 | ||
328 | kfree(dd); | |
329 | } | |
330 | ||
331 | /* | |
332 | * initialize elevator private data (deadline_data). | |
333 | */ | |
334 | static int deadline_init_queue(struct request_queue *q, struct elevator_type *e) | |
335 | { | |
336 | struct deadline_data *dd; | |
337 | struct elevator_queue *eq; | |
338 | ||
339 | eq = elevator_alloc(q, e); | |
340 | if (!eq) | |
341 | return -ENOMEM; | |
342 | ||
343 | dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node); | |
344 | if (!dd) { | |
345 | kobject_put(&eq->kobj); | |
346 | return -ENOMEM; | |
347 | } | |
348 | eq->elevator_data = dd; | |
349 | ||
350 | INIT_LIST_HEAD(&dd->fifo_list[READ]); | |
351 | INIT_LIST_HEAD(&dd->fifo_list[WRITE]); | |
352 | dd->sort_list[READ] = RB_ROOT; | |
353 | dd->sort_list[WRITE] = RB_ROOT; | |
354 | dd->fifo_expire[READ] = read_expire; | |
355 | dd->fifo_expire[WRITE] = write_expire; | |
356 | dd->writes_starved = writes_starved; | |
357 | dd->front_merges = 1; | |
358 | dd->fifo_batch = fifo_batch; | |
359 | ||
360 | spin_lock_irq(q->queue_lock); | |
361 | q->elevator = eq; | |
362 | spin_unlock_irq(q->queue_lock); | |
363 | return 0; | |
364 | } | |
365 | ||
366 | /* | |
367 | * sysfs parts below | |
368 | */ | |
369 | ||
370 | static ssize_t | |
371 | deadline_var_show(int var, char *page) | |
372 | { | |
373 | return sprintf(page, "%d\n", var); | |
374 | } | |
375 | ||
376 | static void | |
377 | deadline_var_store(int *var, const char *page) | |
378 | { | |
379 | char *p = (char *) page; | |
380 | ||
381 | *var = simple_strtol(p, &p, 10); | |
382 | } | |
383 | ||
384 | #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ | |
385 | static ssize_t __FUNC(struct elevator_queue *e, char *page) \ | |
386 | { \ | |
387 | struct deadline_data *dd = e->elevator_data; \ | |
388 | int __data = __VAR; \ | |
389 | if (__CONV) \ | |
390 | __data = jiffies_to_msecs(__data); \ | |
391 | return deadline_var_show(__data, (page)); \ | |
392 | } | |
393 | SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1); | |
394 | SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1); | |
395 | SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0); | |
396 | SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0); | |
397 | SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0); | |
398 | #undef SHOW_FUNCTION | |
399 | ||
400 | #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ | |
401 | static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \ | |
402 | { \ | |
403 | struct deadline_data *dd = e->elevator_data; \ | |
404 | int __data; \ | |
405 | deadline_var_store(&__data, (page)); \ | |
406 | if (__data < (MIN)) \ | |
407 | __data = (MIN); \ | |
408 | else if (__data > (MAX)) \ | |
409 | __data = (MAX); \ | |
410 | if (__CONV) \ | |
411 | *(__PTR) = msecs_to_jiffies(__data); \ | |
412 | else \ | |
413 | *(__PTR) = __data; \ | |
414 | return count; \ | |
415 | } | |
416 | STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1); | |
417 | STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1); | |
418 | STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0); | |
419 | STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0); | |
420 | STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0); | |
421 | #undef STORE_FUNCTION | |
422 | ||
423 | #define DD_ATTR(name) \ | |
424 | __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \ | |
425 | deadline_##name##_store) | |
426 | ||
427 | static struct elv_fs_entry deadline_attrs[] = { | |
428 | DD_ATTR(read_expire), | |
429 | DD_ATTR(write_expire), | |
430 | DD_ATTR(writes_starved), | |
431 | DD_ATTR(front_merges), | |
432 | DD_ATTR(fifo_batch), | |
433 | __ATTR_NULL | |
434 | }; | |
435 | ||
436 | static struct elevator_type iosched_deadline = { | |
437 | .ops.sq = { | |
438 | .elevator_merge_fn = deadline_merge, | |
439 | .elevator_merged_fn = deadline_merged_request, | |
440 | .elevator_merge_req_fn = deadline_merged_requests, | |
441 | .elevator_dispatch_fn = deadline_dispatch_requests, | |
442 | .elevator_add_req_fn = deadline_add_request, | |
443 | .elevator_former_req_fn = elv_rb_former_request, | |
444 | .elevator_latter_req_fn = elv_rb_latter_request, | |
445 | .elevator_init_fn = deadline_init_queue, | |
446 | .elevator_exit_fn = deadline_exit_queue, | |
447 | }, | |
448 | ||
449 | .elevator_attrs = deadline_attrs, | |
450 | .elevator_name = "deadline", | |
451 | .elevator_owner = THIS_MODULE, | |
452 | }; | |
453 | ||
454 | static int __init deadline_init(void) | |
455 | { | |
456 | return elv_register(&iosched_deadline); | |
457 | } | |
458 | ||
459 | static void __exit deadline_exit(void) | |
460 | { | |
461 | elv_unregister(&iosched_deadline); | |
462 | } | |
463 | ||
464 | module_init(deadline_init); | |
465 | module_exit(deadline_exit); | |
466 | ||
467 | MODULE_AUTHOR("Jens Axboe"); | |
468 | MODULE_LICENSE("GPL"); | |
469 | MODULE_DESCRIPTION("deadline IO scheduler"); |