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 */ 20static const int read_expire = HZ / 2; /* max time before a read is submitted. */ 21static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */ 22static const int writes_starved = 2; /* max times reads can starve a write */ 23static const int fifo_batch = 16; /* # of sequential requests treated as one 24 by the above parameters. For throughput. */ 25 26struct 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 54static void deadline_move_request(struct deadline_data *, struct request *); 55 56static inline struct rb_root * 57deadline_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 */ 65static inline struct request * 66deadline_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 76static void 77deadline_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 84static inline void 85deadline_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 */ 98static void 99deadline_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 */ 116static 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 124static int 125deadline_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; 149out: 150 *req = __rq; 151 return ret; 152} 153 154static 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 168static void 169deadline_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 */ 192static inline void 193deadline_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 */ 204static void 205deadline_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 */ 226static 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 */ 243static 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) { 284dispatch_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 296dispatch_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 317dispatch_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 327static 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 */ 340static 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 376static ssize_t 377deadline_var_show(int var, char *page) 378{ 379 return sprintf(page, "%d\n", var); 380} 381 382static ssize_t 383deadline_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) \ 392static 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} 400SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1); 401SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1); 402SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0); 403SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0); 404SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0); 405#undef SHOW_FUNCTION 406 407#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ 408static 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} 423STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1); 424STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1); 425STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0); 426STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0); 427STORE_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 434static 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 443static 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 461static int __init deadline_init(void) 462{ 463 return elv_register(&iosched_deadline); 464} 465 466static void __exit deadline_exit(void) 467{ 468 elv_unregister(&iosched_deadline); 469} 470 471module_init(deadline_init); 472module_exit(deadline_exit); 473 474MODULE_AUTHOR("Jens Axboe"); 475MODULE_LICENSE("GPL"); 476MODULE_DESCRIPTION("deadline IO scheduler"); 477