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