Branch data Line data Source code
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 : 0 : 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 : 0 : struct rb_node *node = rb_next(&rq->rb_node);
69 : :
70 [ # # # # ]: 0 : if (node)
71 : 0 : return rb_entry_rq(node);
72 : :
73 : : return NULL;
74 : : }
75 : :
76 : : static void
77 : 0 : deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
78 : : {
79 : 0 : struct rb_root *root = deadline_rb_root(dd, rq);
80 : :
81 : 0 : elv_rb_add(root, rq);
82 : : }
83 : :
84 : : static inline void
85 : 0 : deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
86 : : {
87 : 0 : const int data_dir = rq_data_dir(rq);
88 : :
89 [ # # ]: 0 : if (dd->next_rq[data_dir] == rq)
90 : 0 : dd->next_rq[data_dir] = deadline_latter_request(rq);
91 : :
92 : 0 : elv_rb_del(deadline_rb_root(dd, rq), rq);
93 : : }
94 : :
95 : : /*
96 : : * add rq to rbtree and fifo
97 : : */
98 : : static void
99 : 0 : deadline_add_request(struct request_queue *q, struct request *rq)
100 : : {
101 : 0 : struct deadline_data *dd = q->elevator->elevator_data;
102 : 0 : 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 : 0 : rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
110 : 0 : list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
111 : 0 : }
112 : :
113 : : /*
114 : : * remove rq from rbtree and fifo.
115 : : */
116 : 0 : static void deadline_remove_request(struct request_queue *q, struct request *rq)
117 : : {
118 : 0 : struct deadline_data *dd = q->elevator->elevator_data;
119 : :
120 : 0 : rq_fifo_clear(rq);
121 : : deadline_del_rq_rb(dd, rq);
122 : 0 : }
123 : :
124 : : static int
125 : 0 : deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
126 : : {
127 : 0 : struct deadline_data *dd = q->elevator->elevator_data;
128 : 0 : struct request *__rq;
129 : : int ret;
130 : :
131 : : /*
132 : : * check for front merge
133 : : */
134 [ # # ]: 0 : if (dd->front_merges) {
135 : 0 : sector_t sector = bio_end_sector(bio);
136 : :
137 : 0 : __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
138 [ # # ]: 0 : if (__rq) {
139 [ # # ]: 0 : BUG_ON(sector != blk_rq_pos(__rq));
140 : :
141 [ # # ]: 0 : 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 : 0 : *req = __rq;
151 : 0 : return ret;
152 : : }
153 : :
154 : 0 : static void deadline_merged_request(struct request_queue *q,
155 : 0 : struct request *req, int type)
156 : : {
157 : 0 : 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 [ # # ]: 0 : if (type == ELEVATOR_FRONT_MERGE) {
163 : 0 : elv_rb_del(deadline_rb_root(dd, req), req);
164 : : deadline_add_rq_rb(dd, req);
165 : : }
166 : 0 : }
167 : :
168 : : static void
169 : 0 : 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 [ # # ][ # # ]: 0 : if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
177 [ # # ]: 0 : if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
178 : : list_move(&req->queuelist, &next->queuelist);
179 : 0 : rq_set_fifo_time(req, rq_fifo_time(next));
180 : : }
181 : : }
182 : :
183 : : /*
184 : : * kill knowledge of next, this one is a goner
185 : : */
186 : 0 : deadline_remove_request(q, next);
187 : 0 : }
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 : 0 : struct request_queue *q = rq->q;
196 : :
197 : 0 : deadline_remove_request(q, rq);
198 : 0 : elv_dispatch_add_tail(q, rq);
199 : : }
200 : :
201 : : /*
202 : : * move an entry to dispatch queue
203 : : */
204 : : static void
205 : 0 : deadline_move_request(struct deadline_data *dd, struct request *rq)
206 : : {
207 : 0 : const int data_dir = rq_data_dir(rq);
208 : :
209 : 0 : dd->next_rq[READ] = NULL;
210 : 0 : dd->next_rq[WRITE] = NULL;
211 : 0 : dd->next_rq[data_dir] = deadline_latter_request(rq);
212 : :
213 : 0 : 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 : 0 : }
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 : 0 : struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
229 : :
230 : : /*
231 : : * rq is expired!
232 : : */
233 [ # # ]: 0 : if (time_after_eq(jiffies, rq_fifo_time(rq)))
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 : 0 : static int deadline_dispatch_requests(struct request_queue *q, int force)
244 : : {
245 : 0 : struct deadline_data *dd = q->elevator->elevator_data;
246 : 0 : const int reads = !list_empty(&dd->fifo_list[READ]);
247 : 0 : 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 [ # # ]: 0 : if (dd->next_rq[WRITE])
255 : : rq = dd->next_rq[WRITE];
256 : : else
257 : 0 : rq = dd->next_rq[READ];
258 : :
259 [ # # ][ # # ]: 0 : 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 [ # # ]: 0 : if (reads) {
269 [ # # ]: 0 : BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
270 : :
271 [ # # ][ # # ]: 0 : 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 [ # # ]: 0 : if (writes) {
284 : : dispatch_writes:
285 [ # # ]: 0 : BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
286 : :
287 : 0 : dd->starved = 0;
288 : :
289 : : data_dir = WRITE;
290 : :
291 : 0 : 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 [ # # ][ # # ]: 0 : 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 : 0 : dd->batching = 0;
316 : :
317 : : dispatch_request:
318 : : /*
319 : : * rq is the selected appropriate request.
320 : : */
321 : 0 : dd->batching++;
322 : 0 : deadline_move_request(dd, rq);
323 : :
324 : 0 : return 1;
325 : : }
326 : :
327 : 0 : static void deadline_exit_queue(struct elevator_queue *e)
328 : : {
329 : 0 : struct deadline_data *dd = e->elevator_data;
330 : :
331 [ # # ]: 0 : BUG_ON(!list_empty(&dd->fifo_list[READ]));
332 [ # # ]: 0 : BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
333 : :
334 : 0 : kfree(dd);
335 : 0 : }
336 : :
337 : : /*
338 : : * initialize elevator private data (deadline_data).
339 : : */
340 : 0 : 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 : 0 : eq = elevator_alloc(q, e);
346 [ # # ]: 0 : if (!eq)
347 : : return -ENOMEM;
348 : :
349 : : dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
350 [ # # ]: 0 : if (!dd) {
351 : 0 : kobject_put(&eq->kobj);
352 : 0 : return -ENOMEM;
353 : : }
354 : 0 : eq->elevator_data = dd;
355 : :
356 : 0 : INIT_LIST_HEAD(&dd->fifo_list[READ]);
357 : 0 : INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
358 : 0 : dd->sort_list[READ] = RB_ROOT;
359 : 0 : dd->sort_list[WRITE] = RB_ROOT;
360 : 0 : dd->fifo_expire[READ] = read_expire;
361 : 0 : dd->fifo_expire[WRITE] = write_expire;
362 : 0 : dd->writes_starved = writes_starved;
363 : 0 : dd->front_merges = 1;
364 : 0 : dd->fifo_batch = fifo_batch;
365 : :
366 : 0 : spin_lock_irq(q->queue_lock);
367 : 0 : q->elevator = eq;
368 : 0 : spin_unlock_irq(q->queue_lock);
369 : 0 : 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 : 0 : 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 : 0 : char *p = (char *) page;
386 : :
387 : 0 : *var = simple_strtol(p, &p, 10);
388 : 0 : 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 : 0 : SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
401 : 0 : SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
402 : 0 : SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
403 : 0 : SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
404 : 0 : 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 [ # # ]: 0 : STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
424 [ # # ]: 0 : STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
425 : 0 : STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
426 [ # # ][ # # ]: 0 : STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
427 [ # # ]: 0 : 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 : 0 : static int __init deadline_init(void)
462 : : {
463 : 0 : return elv_register(&iosched_deadline);
464 : : }
465 : :
466 : 0 : static void __exit deadline_exit(void)
467 : : {
468 : 0 : elv_unregister(&iosched_deadline);
469 : 0 : }
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");
|
