Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 2 | * linux/drivers/block/deadline-iosched.c |
| 3 | * |
| 4 | * Deadline i/o scheduler. |
| 5 | * |
| 6 | * Copyright (C) 2002 Jens Axboe <axboe@suse.de> |
| 7 | */ |
| 8 | #include <linux/kernel.h> |
| 9 | #include <linux/fs.h> |
| 10 | #include <linux/blkdev.h> |
| 11 | #include <linux/elevator.h> |
| 12 | #include <linux/bio.h> |
| 13 | #include <linux/config.h> |
| 14 | #include <linux/module.h> |
| 15 | #include <linux/slab.h> |
| 16 | #include <linux/init.h> |
| 17 | #include <linux/compiler.h> |
| 18 | #include <linux/hash.h> |
| 19 | #include <linux/rbtree.h> |
| 20 | |
| 21 | /* |
| 22 | * See Documentation/block/deadline-iosched.txt |
| 23 | */ |
| 24 | static int read_expire = HZ / 2; /* max time before a read is submitted. */ |
| 25 | static int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */ |
| 26 | static int writes_starved = 2; /* max times reads can starve a write */ |
| 27 | static int fifo_batch = 16; /* # of sequential requests treated as one |
| 28 | by the above parameters. For throughput. */ |
| 29 | |
| 30 | static const int deadline_hash_shift = 5; |
| 31 | #define DL_HASH_BLOCK(sec) ((sec) >> 3) |
| 32 | #define DL_HASH_FN(sec) (hash_long(DL_HASH_BLOCK((sec)), deadline_hash_shift)) |
| 33 | #define DL_HASH_ENTRIES (1 << deadline_hash_shift) |
| 34 | #define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors) |
| 35 | #define list_entry_hash(ptr) list_entry((ptr), struct deadline_rq, hash) |
| 36 | #define ON_HASH(drq) (drq)->on_hash |
| 37 | |
| 38 | struct deadline_data { |
| 39 | /* |
| 40 | * run time data |
| 41 | */ |
| 42 | |
| 43 | /* |
| 44 | * requests (deadline_rq s) are present on both sort_list and fifo_list |
| 45 | */ |
| 46 | struct rb_root sort_list[2]; |
| 47 | struct list_head fifo_list[2]; |
| 48 | |
| 49 | /* |
| 50 | * next in sort order. read, write or both are NULL |
| 51 | */ |
| 52 | struct deadline_rq *next_drq[2]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 53 | struct list_head *hash; /* request hash */ |
| 54 | unsigned int batching; /* number of sequential requests made */ |
| 55 | sector_t last_sector; /* head position */ |
| 56 | unsigned int starved; /* times reads have starved writes */ |
| 57 | |
| 58 | /* |
| 59 | * settings that change how the i/o scheduler behaves |
| 60 | */ |
| 61 | int fifo_expire[2]; |
| 62 | int fifo_batch; |
| 63 | int writes_starved; |
| 64 | int front_merges; |
| 65 | |
| 66 | mempool_t *drq_pool; |
| 67 | }; |
| 68 | |
| 69 | /* |
| 70 | * pre-request data. |
| 71 | */ |
| 72 | struct deadline_rq { |
| 73 | /* |
| 74 | * rbtree index, key is the starting offset |
| 75 | */ |
| 76 | struct rb_node rb_node; |
| 77 | sector_t rb_key; |
| 78 | |
| 79 | struct request *request; |
| 80 | |
| 81 | /* |
| 82 | * request hash, key is the ending offset (for back merge lookup) |
| 83 | */ |
| 84 | struct list_head hash; |
| 85 | char on_hash; |
| 86 | |
| 87 | /* |
| 88 | * expire fifo |
| 89 | */ |
| 90 | struct list_head fifo; |
| 91 | unsigned long expires; |
| 92 | }; |
| 93 | |
| 94 | static void deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq); |
| 95 | |
| 96 | static kmem_cache_t *drq_pool; |
| 97 | |
| 98 | #define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private) |
| 99 | |
| 100 | /* |
| 101 | * the back merge hash support functions |
| 102 | */ |
| 103 | static inline void __deadline_del_drq_hash(struct deadline_rq *drq) |
| 104 | { |
| 105 | drq->on_hash = 0; |
| 106 | list_del_init(&drq->hash); |
| 107 | } |
| 108 | |
| 109 | static inline void deadline_del_drq_hash(struct deadline_rq *drq) |
| 110 | { |
| 111 | if (ON_HASH(drq)) |
| 112 | __deadline_del_drq_hash(drq); |
| 113 | } |
| 114 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 115 | static inline void |
| 116 | deadline_add_drq_hash(struct deadline_data *dd, struct deadline_rq *drq) |
| 117 | { |
| 118 | struct request *rq = drq->request; |
| 119 | |
| 120 | BUG_ON(ON_HASH(drq)); |
| 121 | |
| 122 | drq->on_hash = 1; |
| 123 | list_add(&drq->hash, &dd->hash[DL_HASH_FN(rq_hash_key(rq))]); |
| 124 | } |
| 125 | |
| 126 | /* |
| 127 | * move hot entry to front of chain |
| 128 | */ |
| 129 | static inline void |
| 130 | deadline_hot_drq_hash(struct deadline_data *dd, struct deadline_rq *drq) |
| 131 | { |
| 132 | struct request *rq = drq->request; |
| 133 | struct list_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))]; |
| 134 | |
| 135 | if (ON_HASH(drq) && drq->hash.prev != head) { |
| 136 | list_del(&drq->hash); |
| 137 | list_add(&drq->hash, head); |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | static struct request * |
| 142 | deadline_find_drq_hash(struct deadline_data *dd, sector_t offset) |
| 143 | { |
| 144 | struct list_head *hash_list = &dd->hash[DL_HASH_FN(offset)]; |
| 145 | struct list_head *entry, *next = hash_list->next; |
| 146 | |
| 147 | while ((entry = next) != hash_list) { |
| 148 | struct deadline_rq *drq = list_entry_hash(entry); |
| 149 | struct request *__rq = drq->request; |
| 150 | |
| 151 | next = entry->next; |
| 152 | |
| 153 | BUG_ON(!ON_HASH(drq)); |
| 154 | |
| 155 | if (!rq_mergeable(__rq)) { |
| 156 | __deadline_del_drq_hash(drq); |
| 157 | continue; |
| 158 | } |
| 159 | |
| 160 | if (rq_hash_key(__rq) == offset) |
| 161 | return __rq; |
| 162 | } |
| 163 | |
| 164 | return NULL; |
| 165 | } |
| 166 | |
| 167 | /* |
| 168 | * rb tree support functions |
| 169 | */ |
| 170 | #define RB_NONE (2) |
| 171 | #define RB_EMPTY(root) ((root)->rb_node == NULL) |
| 172 | #define ON_RB(node) ((node)->rb_color != RB_NONE) |
| 173 | #define RB_CLEAR(node) ((node)->rb_color = RB_NONE) |
| 174 | #define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node) |
| 175 | #define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)]) |
| 176 | #define rq_rb_key(rq) (rq)->sector |
| 177 | |
| 178 | static struct deadline_rq * |
| 179 | __deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq) |
| 180 | { |
| 181 | struct rb_node **p = &DRQ_RB_ROOT(dd, drq)->rb_node; |
| 182 | struct rb_node *parent = NULL; |
| 183 | struct deadline_rq *__drq; |
| 184 | |
| 185 | while (*p) { |
| 186 | parent = *p; |
| 187 | __drq = rb_entry_drq(parent); |
| 188 | |
| 189 | if (drq->rb_key < __drq->rb_key) |
| 190 | p = &(*p)->rb_left; |
| 191 | else if (drq->rb_key > __drq->rb_key) |
| 192 | p = &(*p)->rb_right; |
| 193 | else |
| 194 | return __drq; |
| 195 | } |
| 196 | |
| 197 | rb_link_node(&drq->rb_node, parent, p); |
| 198 | return NULL; |
| 199 | } |
| 200 | |
| 201 | static void |
| 202 | deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq) |
| 203 | { |
| 204 | struct deadline_rq *__alias; |
| 205 | |
| 206 | drq->rb_key = rq_rb_key(drq->request); |
| 207 | |
| 208 | retry: |
| 209 | __alias = __deadline_add_drq_rb(dd, drq); |
| 210 | if (!__alias) { |
| 211 | rb_insert_color(&drq->rb_node, DRQ_RB_ROOT(dd, drq)); |
| 212 | return; |
| 213 | } |
| 214 | |
| 215 | deadline_move_request(dd, __alias); |
| 216 | goto retry; |
| 217 | } |
| 218 | |
| 219 | static inline void |
| 220 | deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq) |
| 221 | { |
| 222 | const int data_dir = rq_data_dir(drq->request); |
| 223 | |
| 224 | if (dd->next_drq[data_dir] == drq) { |
| 225 | struct rb_node *rbnext = rb_next(&drq->rb_node); |
| 226 | |
| 227 | dd->next_drq[data_dir] = NULL; |
| 228 | if (rbnext) |
| 229 | dd->next_drq[data_dir] = rb_entry_drq(rbnext); |
| 230 | } |
| 231 | |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 232 | BUG_ON(!ON_RB(&drq->rb_node)); |
| 233 | rb_erase(&drq->rb_node, DRQ_RB_ROOT(dd, drq)); |
| 234 | RB_CLEAR(&drq->rb_node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 235 | } |
| 236 | |
| 237 | static struct request * |
| 238 | deadline_find_drq_rb(struct deadline_data *dd, sector_t sector, int data_dir) |
| 239 | { |
| 240 | struct rb_node *n = dd->sort_list[data_dir].rb_node; |
| 241 | struct deadline_rq *drq; |
| 242 | |
| 243 | while (n) { |
| 244 | drq = rb_entry_drq(n); |
| 245 | |
| 246 | if (sector < drq->rb_key) |
| 247 | n = n->rb_left; |
| 248 | else if (sector > drq->rb_key) |
| 249 | n = n->rb_right; |
| 250 | else |
| 251 | return drq->request; |
| 252 | } |
| 253 | |
| 254 | return NULL; |
| 255 | } |
| 256 | |
| 257 | /* |
| 258 | * deadline_find_first_drq finds the first (lowest sector numbered) request |
| 259 | * for the specified data_dir. Used to sweep back to the start of the disk |
| 260 | * (1-way elevator) after we process the last (highest sector) request. |
| 261 | */ |
| 262 | static struct deadline_rq * |
| 263 | deadline_find_first_drq(struct deadline_data *dd, int data_dir) |
| 264 | { |
| 265 | struct rb_node *n = dd->sort_list[data_dir].rb_node; |
| 266 | |
| 267 | for (;;) { |
| 268 | if (n->rb_left == NULL) |
| 269 | return rb_entry_drq(n); |
| 270 | |
| 271 | n = n->rb_left; |
| 272 | } |
| 273 | } |
| 274 | |
| 275 | /* |
| 276 | * add drq to rbtree and fifo |
| 277 | */ |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 278 | static void |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 279 | deadline_add_request(struct request_queue *q, struct request *rq) |
| 280 | { |
| 281 | struct deadline_data *dd = q->elevator->elevator_data; |
| 282 | struct deadline_rq *drq = RQ_DATA(rq); |
| 283 | |
| 284 | const int data_dir = rq_data_dir(drq->request); |
| 285 | |
| 286 | deadline_add_drq_rb(dd, drq); |
| 287 | /* |
| 288 | * set expire time (only used for reads) and add to fifo list |
| 289 | */ |
| 290 | drq->expires = jiffies + dd->fifo_expire[data_dir]; |
| 291 | list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]); |
| 292 | |
Tejun Heo | 98b1147 | 2005-10-20 16:46:54 +0200 | [diff] [blame^] | 293 | if (rq_mergeable(rq)) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 294 | deadline_add_drq_hash(dd, drq); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 295 | } |
| 296 | |
| 297 | /* |
| 298 | * remove rq from rbtree, fifo, and hash |
| 299 | */ |
| 300 | static void deadline_remove_request(request_queue_t *q, struct request *rq) |
| 301 | { |
| 302 | struct deadline_rq *drq = RQ_DATA(rq); |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 303 | struct deadline_data *dd = q->elevator->elevator_data; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 304 | |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 305 | list_del_init(&drq->fifo); |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 306 | deadline_del_drq_rb(dd, drq); |
Tejun Heo | 98b1147 | 2005-10-20 16:46:54 +0200 | [diff] [blame^] | 307 | deadline_del_drq_hash(drq); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 308 | } |
| 309 | |
| 310 | static int |
| 311 | deadline_merge(request_queue_t *q, struct request **req, struct bio *bio) |
| 312 | { |
| 313 | struct deadline_data *dd = q->elevator->elevator_data; |
| 314 | struct request *__rq; |
| 315 | int ret; |
| 316 | |
| 317 | /* |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 318 | * see if the merge hash can satisfy a back merge |
| 319 | */ |
| 320 | __rq = deadline_find_drq_hash(dd, bio->bi_sector); |
| 321 | if (__rq) { |
| 322 | BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector); |
| 323 | |
| 324 | if (elv_rq_merge_ok(__rq, bio)) { |
| 325 | ret = ELEVATOR_BACK_MERGE; |
| 326 | goto out; |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | /* |
| 331 | * check for front merge |
| 332 | */ |
| 333 | if (dd->front_merges) { |
| 334 | sector_t rb_key = bio->bi_sector + bio_sectors(bio); |
| 335 | |
| 336 | __rq = deadline_find_drq_rb(dd, rb_key, bio_data_dir(bio)); |
| 337 | if (__rq) { |
| 338 | BUG_ON(rb_key != rq_rb_key(__rq)); |
| 339 | |
| 340 | if (elv_rq_merge_ok(__rq, bio)) { |
| 341 | ret = ELEVATOR_FRONT_MERGE; |
| 342 | goto out; |
| 343 | } |
| 344 | } |
| 345 | } |
| 346 | |
| 347 | return ELEVATOR_NO_MERGE; |
| 348 | out: |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 349 | if (ret) |
| 350 | deadline_hot_drq_hash(dd, RQ_DATA(__rq)); |
| 351 | *req = __rq; |
| 352 | return ret; |
| 353 | } |
| 354 | |
| 355 | static void deadline_merged_request(request_queue_t *q, struct request *req) |
| 356 | { |
| 357 | struct deadline_data *dd = q->elevator->elevator_data; |
| 358 | struct deadline_rq *drq = RQ_DATA(req); |
| 359 | |
| 360 | /* |
| 361 | * hash always needs to be repositioned, key is end sector |
| 362 | */ |
| 363 | deadline_del_drq_hash(drq); |
| 364 | deadline_add_drq_hash(dd, drq); |
| 365 | |
| 366 | /* |
| 367 | * if the merge was a front merge, we need to reposition request |
| 368 | */ |
| 369 | if (rq_rb_key(req) != drq->rb_key) { |
| 370 | deadline_del_drq_rb(dd, drq); |
| 371 | deadline_add_drq_rb(dd, drq); |
| 372 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 373 | } |
| 374 | |
| 375 | static void |
| 376 | deadline_merged_requests(request_queue_t *q, struct request *req, |
| 377 | struct request *next) |
| 378 | { |
| 379 | struct deadline_data *dd = q->elevator->elevator_data; |
| 380 | struct deadline_rq *drq = RQ_DATA(req); |
| 381 | struct deadline_rq *dnext = RQ_DATA(next); |
| 382 | |
| 383 | BUG_ON(!drq); |
| 384 | BUG_ON(!dnext); |
| 385 | |
| 386 | /* |
| 387 | * reposition drq (this is the merged request) in hash, and in rbtree |
| 388 | * in case of a front merge |
| 389 | */ |
| 390 | deadline_del_drq_hash(drq); |
| 391 | deadline_add_drq_hash(dd, drq); |
| 392 | |
| 393 | if (rq_rb_key(req) != drq->rb_key) { |
| 394 | deadline_del_drq_rb(dd, drq); |
| 395 | deadline_add_drq_rb(dd, drq); |
| 396 | } |
| 397 | |
| 398 | /* |
| 399 | * if dnext expires before drq, assign its expire time to drq |
| 400 | * and move into dnext position (dnext will be deleted) in fifo |
| 401 | */ |
| 402 | if (!list_empty(&drq->fifo) && !list_empty(&dnext->fifo)) { |
| 403 | if (time_before(dnext->expires, drq->expires)) { |
| 404 | list_move(&drq->fifo, &dnext->fifo); |
| 405 | drq->expires = dnext->expires; |
| 406 | } |
| 407 | } |
| 408 | |
| 409 | /* |
| 410 | * kill knowledge of next, this one is a goner |
| 411 | */ |
| 412 | deadline_remove_request(q, next); |
| 413 | } |
| 414 | |
| 415 | /* |
| 416 | * move request from sort list to dispatch queue. |
| 417 | */ |
| 418 | static inline void |
| 419 | deadline_move_to_dispatch(struct deadline_data *dd, struct deadline_rq *drq) |
| 420 | { |
| 421 | request_queue_t *q = drq->request->q; |
| 422 | |
| 423 | deadline_remove_request(q, drq->request); |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 424 | elv_dispatch_add_tail(q, drq->request); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 425 | } |
| 426 | |
| 427 | /* |
| 428 | * move an entry to dispatch queue |
| 429 | */ |
| 430 | static void |
| 431 | deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq) |
| 432 | { |
| 433 | const int data_dir = rq_data_dir(drq->request); |
| 434 | struct rb_node *rbnext = rb_next(&drq->rb_node); |
| 435 | |
| 436 | dd->next_drq[READ] = NULL; |
| 437 | dd->next_drq[WRITE] = NULL; |
| 438 | |
| 439 | if (rbnext) |
| 440 | dd->next_drq[data_dir] = rb_entry_drq(rbnext); |
| 441 | |
| 442 | dd->last_sector = drq->request->sector + drq->request->nr_sectors; |
| 443 | |
| 444 | /* |
| 445 | * take it off the sort and fifo list, move |
| 446 | * to dispatch queue |
| 447 | */ |
| 448 | deadline_move_to_dispatch(dd, drq); |
| 449 | } |
| 450 | |
| 451 | #define list_entry_fifo(ptr) list_entry((ptr), struct deadline_rq, fifo) |
| 452 | |
| 453 | /* |
| 454 | * deadline_check_fifo returns 0 if there are no expired reads on the fifo, |
| 455 | * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir]) |
| 456 | */ |
| 457 | static inline int deadline_check_fifo(struct deadline_data *dd, int ddir) |
| 458 | { |
| 459 | struct deadline_rq *drq = list_entry_fifo(dd->fifo_list[ddir].next); |
| 460 | |
| 461 | /* |
| 462 | * drq is expired! |
| 463 | */ |
| 464 | if (time_after(jiffies, drq->expires)) |
| 465 | return 1; |
| 466 | |
| 467 | return 0; |
| 468 | } |
| 469 | |
| 470 | /* |
| 471 | * deadline_dispatch_requests selects the best request according to |
| 472 | * read/write expire, fifo_batch, etc |
| 473 | */ |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 474 | static int deadline_dispatch_requests(request_queue_t *q, int force) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 475 | { |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 476 | struct deadline_data *dd = q->elevator->elevator_data; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 477 | const int reads = !list_empty(&dd->fifo_list[READ]); |
| 478 | const int writes = !list_empty(&dd->fifo_list[WRITE]); |
| 479 | struct deadline_rq *drq; |
Nikita Danilov | 4b0dc07 | 2005-09-06 15:17:20 -0700 | [diff] [blame] | 480 | int data_dir; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 481 | |
| 482 | /* |
| 483 | * batches are currently reads XOR writes |
| 484 | */ |
Andrew Morton | 9d5c1e1 | 2005-09-09 13:02:12 -0700 | [diff] [blame] | 485 | if (dd->next_drq[WRITE]) |
| 486 | drq = dd->next_drq[WRITE]; |
| 487 | else |
| 488 | drq = dd->next_drq[READ]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 489 | |
| 490 | if (drq) { |
| 491 | /* we have a "next request" */ |
| 492 | |
| 493 | if (dd->last_sector != drq->request->sector) |
| 494 | /* end the batch on a non sequential request */ |
| 495 | dd->batching += dd->fifo_batch; |
| 496 | |
| 497 | if (dd->batching < dd->fifo_batch) |
| 498 | /* we are still entitled to batch */ |
| 499 | goto dispatch_request; |
| 500 | } |
| 501 | |
| 502 | /* |
| 503 | * at this point we are not running a batch. select the appropriate |
| 504 | * data direction (read / write) |
| 505 | */ |
| 506 | |
| 507 | if (reads) { |
| 508 | BUG_ON(RB_EMPTY(&dd->sort_list[READ])); |
| 509 | |
| 510 | if (writes && (dd->starved++ >= dd->writes_starved)) |
| 511 | goto dispatch_writes; |
| 512 | |
| 513 | data_dir = READ; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 514 | |
| 515 | goto dispatch_find_request; |
| 516 | } |
| 517 | |
| 518 | /* |
| 519 | * there are either no reads or writes have been starved |
| 520 | */ |
| 521 | |
| 522 | if (writes) { |
| 523 | dispatch_writes: |
| 524 | BUG_ON(RB_EMPTY(&dd->sort_list[WRITE])); |
| 525 | |
| 526 | dd->starved = 0; |
| 527 | |
| 528 | data_dir = WRITE; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 529 | |
| 530 | goto dispatch_find_request; |
| 531 | } |
| 532 | |
| 533 | return 0; |
| 534 | |
| 535 | dispatch_find_request: |
| 536 | /* |
| 537 | * we are not running a batch, find best request for selected data_dir |
| 538 | */ |
| 539 | if (deadline_check_fifo(dd, data_dir)) { |
| 540 | /* An expired request exists - satisfy it */ |
| 541 | dd->batching = 0; |
| 542 | drq = list_entry_fifo(dd->fifo_list[data_dir].next); |
| 543 | |
| 544 | } else if (dd->next_drq[data_dir]) { |
| 545 | /* |
| 546 | * The last req was the same dir and we have a next request in |
| 547 | * sort order. No expired requests so continue on from here. |
| 548 | */ |
| 549 | drq = dd->next_drq[data_dir]; |
| 550 | } else { |
| 551 | /* |
| 552 | * The last req was the other direction or we have run out of |
| 553 | * higher-sectored requests. Go back to the lowest sectored |
| 554 | * request (1 way elevator) and start a new batch. |
| 555 | */ |
| 556 | dd->batching = 0; |
| 557 | drq = deadline_find_first_drq(dd, data_dir); |
| 558 | } |
| 559 | |
| 560 | dispatch_request: |
| 561 | /* |
| 562 | * drq is the selected appropriate request. |
| 563 | */ |
| 564 | dd->batching++; |
| 565 | deadline_move_request(dd, drq); |
| 566 | |
| 567 | return 1; |
| 568 | } |
| 569 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 570 | static int deadline_queue_empty(request_queue_t *q) |
| 571 | { |
| 572 | struct deadline_data *dd = q->elevator->elevator_data; |
| 573 | |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 574 | return list_empty(&dd->fifo_list[WRITE]) |
| 575 | && list_empty(&dd->fifo_list[READ]); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 576 | } |
| 577 | |
| 578 | static struct request * |
| 579 | deadline_former_request(request_queue_t *q, struct request *rq) |
| 580 | { |
| 581 | struct deadline_rq *drq = RQ_DATA(rq); |
| 582 | struct rb_node *rbprev = rb_prev(&drq->rb_node); |
| 583 | |
| 584 | if (rbprev) |
| 585 | return rb_entry_drq(rbprev)->request; |
| 586 | |
| 587 | return NULL; |
| 588 | } |
| 589 | |
| 590 | static struct request * |
| 591 | deadline_latter_request(request_queue_t *q, struct request *rq) |
| 592 | { |
| 593 | struct deadline_rq *drq = RQ_DATA(rq); |
| 594 | struct rb_node *rbnext = rb_next(&drq->rb_node); |
| 595 | |
| 596 | if (rbnext) |
| 597 | return rb_entry_drq(rbnext)->request; |
| 598 | |
| 599 | return NULL; |
| 600 | } |
| 601 | |
| 602 | static void deadline_exit_queue(elevator_t *e) |
| 603 | { |
| 604 | struct deadline_data *dd = e->elevator_data; |
| 605 | |
| 606 | BUG_ON(!list_empty(&dd->fifo_list[READ])); |
| 607 | BUG_ON(!list_empty(&dd->fifo_list[WRITE])); |
| 608 | |
| 609 | mempool_destroy(dd->drq_pool); |
| 610 | kfree(dd->hash); |
| 611 | kfree(dd); |
| 612 | } |
| 613 | |
| 614 | /* |
| 615 | * initialize elevator private data (deadline_data), and alloc a drq for |
| 616 | * each request on the free lists |
| 617 | */ |
| 618 | static int deadline_init_queue(request_queue_t *q, elevator_t *e) |
| 619 | { |
| 620 | struct deadline_data *dd; |
| 621 | int i; |
| 622 | |
| 623 | if (!drq_pool) |
| 624 | return -ENOMEM; |
| 625 | |
Christoph Lameter | 1946089 | 2005-06-23 00:08:19 -0700 | [diff] [blame] | 626 | dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 627 | if (!dd) |
| 628 | return -ENOMEM; |
| 629 | memset(dd, 0, sizeof(*dd)); |
| 630 | |
Christoph Lameter | 1946089 | 2005-06-23 00:08:19 -0700 | [diff] [blame] | 631 | dd->hash = kmalloc_node(sizeof(struct list_head)*DL_HASH_ENTRIES, |
| 632 | GFP_KERNEL, q->node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 633 | if (!dd->hash) { |
| 634 | kfree(dd); |
| 635 | return -ENOMEM; |
| 636 | } |
| 637 | |
Christoph Lameter | 1946089 | 2005-06-23 00:08:19 -0700 | [diff] [blame] | 638 | dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab, |
| 639 | mempool_free_slab, drq_pool, q->node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 640 | if (!dd->drq_pool) { |
| 641 | kfree(dd->hash); |
| 642 | kfree(dd); |
| 643 | return -ENOMEM; |
| 644 | } |
| 645 | |
| 646 | for (i = 0; i < DL_HASH_ENTRIES; i++) |
| 647 | INIT_LIST_HEAD(&dd->hash[i]); |
| 648 | |
| 649 | INIT_LIST_HEAD(&dd->fifo_list[READ]); |
| 650 | INIT_LIST_HEAD(&dd->fifo_list[WRITE]); |
| 651 | dd->sort_list[READ] = RB_ROOT; |
| 652 | dd->sort_list[WRITE] = RB_ROOT; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 653 | dd->fifo_expire[READ] = read_expire; |
| 654 | dd->fifo_expire[WRITE] = write_expire; |
| 655 | dd->writes_starved = writes_starved; |
| 656 | dd->front_merges = 1; |
| 657 | dd->fifo_batch = fifo_batch; |
| 658 | e->elevator_data = dd; |
| 659 | return 0; |
| 660 | } |
| 661 | |
| 662 | static void deadline_put_request(request_queue_t *q, struct request *rq) |
| 663 | { |
| 664 | struct deadline_data *dd = q->elevator->elevator_data; |
| 665 | struct deadline_rq *drq = RQ_DATA(rq); |
| 666 | |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 667 | mempool_free(drq, dd->drq_pool); |
| 668 | rq->elevator_private = NULL; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 669 | } |
| 670 | |
| 671 | static int |
Jens Axboe | 22e2c50 | 2005-06-27 10:55:12 +0200 | [diff] [blame] | 672 | deadline_set_request(request_queue_t *q, struct request *rq, struct bio *bio, |
| 673 | int gfp_mask) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 674 | { |
| 675 | struct deadline_data *dd = q->elevator->elevator_data; |
| 676 | struct deadline_rq *drq; |
| 677 | |
| 678 | drq = mempool_alloc(dd->drq_pool, gfp_mask); |
| 679 | if (drq) { |
| 680 | memset(drq, 0, sizeof(*drq)); |
| 681 | RB_CLEAR(&drq->rb_node); |
| 682 | drq->request = rq; |
| 683 | |
| 684 | INIT_LIST_HEAD(&drq->hash); |
| 685 | drq->on_hash = 0; |
| 686 | |
| 687 | INIT_LIST_HEAD(&drq->fifo); |
| 688 | |
| 689 | rq->elevator_private = drq; |
| 690 | return 0; |
| 691 | } |
| 692 | |
| 693 | return 1; |
| 694 | } |
| 695 | |
| 696 | /* |
| 697 | * sysfs parts below |
| 698 | */ |
| 699 | struct deadline_fs_entry { |
| 700 | struct attribute attr; |
| 701 | ssize_t (*show)(struct deadline_data *, char *); |
| 702 | ssize_t (*store)(struct deadline_data *, const char *, size_t); |
| 703 | }; |
| 704 | |
| 705 | static ssize_t |
| 706 | deadline_var_show(int var, char *page) |
| 707 | { |
| 708 | return sprintf(page, "%d\n", var); |
| 709 | } |
| 710 | |
| 711 | static ssize_t |
| 712 | deadline_var_store(int *var, const char *page, size_t count) |
| 713 | { |
| 714 | char *p = (char *) page; |
| 715 | |
| 716 | *var = simple_strtol(p, &p, 10); |
| 717 | return count; |
| 718 | } |
| 719 | |
| 720 | #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \ |
| 721 | static ssize_t __FUNC(struct deadline_data *dd, char *page) \ |
| 722 | { \ |
| 723 | int __data = __VAR; \ |
| 724 | if (__CONV) \ |
| 725 | __data = jiffies_to_msecs(__data); \ |
| 726 | return deadline_var_show(__data, (page)); \ |
| 727 | } |
| 728 | SHOW_FUNCTION(deadline_readexpire_show, dd->fifo_expire[READ], 1); |
| 729 | SHOW_FUNCTION(deadline_writeexpire_show, dd->fifo_expire[WRITE], 1); |
| 730 | SHOW_FUNCTION(deadline_writesstarved_show, dd->writes_starved, 0); |
| 731 | SHOW_FUNCTION(deadline_frontmerges_show, dd->front_merges, 0); |
| 732 | SHOW_FUNCTION(deadline_fifobatch_show, dd->fifo_batch, 0); |
| 733 | #undef SHOW_FUNCTION |
| 734 | |
| 735 | #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \ |
| 736 | static ssize_t __FUNC(struct deadline_data *dd, const char *page, size_t count) \ |
| 737 | { \ |
| 738 | int __data; \ |
| 739 | int ret = deadline_var_store(&__data, (page), count); \ |
| 740 | if (__data < (MIN)) \ |
| 741 | __data = (MIN); \ |
| 742 | else if (__data > (MAX)) \ |
| 743 | __data = (MAX); \ |
| 744 | if (__CONV) \ |
| 745 | *(__PTR) = msecs_to_jiffies(__data); \ |
| 746 | else \ |
| 747 | *(__PTR) = __data; \ |
| 748 | return ret; \ |
| 749 | } |
| 750 | STORE_FUNCTION(deadline_readexpire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1); |
| 751 | STORE_FUNCTION(deadline_writeexpire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1); |
| 752 | STORE_FUNCTION(deadline_writesstarved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0); |
| 753 | STORE_FUNCTION(deadline_frontmerges_store, &dd->front_merges, 0, 1, 0); |
| 754 | STORE_FUNCTION(deadline_fifobatch_store, &dd->fifo_batch, 0, INT_MAX, 0); |
| 755 | #undef STORE_FUNCTION |
| 756 | |
| 757 | static struct deadline_fs_entry deadline_readexpire_entry = { |
| 758 | .attr = {.name = "read_expire", .mode = S_IRUGO | S_IWUSR }, |
| 759 | .show = deadline_readexpire_show, |
| 760 | .store = deadline_readexpire_store, |
| 761 | }; |
| 762 | static struct deadline_fs_entry deadline_writeexpire_entry = { |
| 763 | .attr = {.name = "write_expire", .mode = S_IRUGO | S_IWUSR }, |
| 764 | .show = deadline_writeexpire_show, |
| 765 | .store = deadline_writeexpire_store, |
| 766 | }; |
| 767 | static struct deadline_fs_entry deadline_writesstarved_entry = { |
| 768 | .attr = {.name = "writes_starved", .mode = S_IRUGO | S_IWUSR }, |
| 769 | .show = deadline_writesstarved_show, |
| 770 | .store = deadline_writesstarved_store, |
| 771 | }; |
| 772 | static struct deadline_fs_entry deadline_frontmerges_entry = { |
| 773 | .attr = {.name = "front_merges", .mode = S_IRUGO | S_IWUSR }, |
| 774 | .show = deadline_frontmerges_show, |
| 775 | .store = deadline_frontmerges_store, |
| 776 | }; |
| 777 | static struct deadline_fs_entry deadline_fifobatch_entry = { |
| 778 | .attr = {.name = "fifo_batch", .mode = S_IRUGO | S_IWUSR }, |
| 779 | .show = deadline_fifobatch_show, |
| 780 | .store = deadline_fifobatch_store, |
| 781 | }; |
| 782 | |
| 783 | static struct attribute *default_attrs[] = { |
| 784 | &deadline_readexpire_entry.attr, |
| 785 | &deadline_writeexpire_entry.attr, |
| 786 | &deadline_writesstarved_entry.attr, |
| 787 | &deadline_frontmerges_entry.attr, |
| 788 | &deadline_fifobatch_entry.attr, |
| 789 | NULL, |
| 790 | }; |
| 791 | |
| 792 | #define to_deadline(atr) container_of((atr), struct deadline_fs_entry, attr) |
| 793 | |
| 794 | static ssize_t |
| 795 | deadline_attr_show(struct kobject *kobj, struct attribute *attr, char *page) |
| 796 | { |
| 797 | elevator_t *e = container_of(kobj, elevator_t, kobj); |
| 798 | struct deadline_fs_entry *entry = to_deadline(attr); |
| 799 | |
| 800 | if (!entry->show) |
Dmitry Torokhov | 6c1852a | 2005-04-29 01:26:06 -0500 | [diff] [blame] | 801 | return -EIO; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 802 | |
| 803 | return entry->show(e->elevator_data, page); |
| 804 | } |
| 805 | |
| 806 | static ssize_t |
| 807 | deadline_attr_store(struct kobject *kobj, struct attribute *attr, |
| 808 | const char *page, size_t length) |
| 809 | { |
| 810 | elevator_t *e = container_of(kobj, elevator_t, kobj); |
| 811 | struct deadline_fs_entry *entry = to_deadline(attr); |
| 812 | |
| 813 | if (!entry->store) |
Dmitry Torokhov | 6c1852a | 2005-04-29 01:26:06 -0500 | [diff] [blame] | 814 | return -EIO; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 815 | |
| 816 | return entry->store(e->elevator_data, page, length); |
| 817 | } |
| 818 | |
| 819 | static struct sysfs_ops deadline_sysfs_ops = { |
| 820 | .show = deadline_attr_show, |
| 821 | .store = deadline_attr_store, |
| 822 | }; |
| 823 | |
| 824 | static struct kobj_type deadline_ktype = { |
| 825 | .sysfs_ops = &deadline_sysfs_ops, |
| 826 | .default_attrs = default_attrs, |
| 827 | }; |
| 828 | |
| 829 | static struct elevator_type iosched_deadline = { |
| 830 | .ops = { |
| 831 | .elevator_merge_fn = deadline_merge, |
| 832 | .elevator_merged_fn = deadline_merged_request, |
| 833 | .elevator_merge_req_fn = deadline_merged_requests, |
Jens Axboe | b4878f2 | 2005-10-20 16:42:29 +0200 | [diff] [blame] | 834 | .elevator_dispatch_fn = deadline_dispatch_requests, |
| 835 | .elevator_add_req_fn = deadline_add_request, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 836 | .elevator_queue_empty_fn = deadline_queue_empty, |
| 837 | .elevator_former_req_fn = deadline_former_request, |
| 838 | .elevator_latter_req_fn = deadline_latter_request, |
| 839 | .elevator_set_req_fn = deadline_set_request, |
| 840 | .elevator_put_req_fn = deadline_put_request, |
| 841 | .elevator_init_fn = deadline_init_queue, |
| 842 | .elevator_exit_fn = deadline_exit_queue, |
| 843 | }, |
| 844 | |
| 845 | .elevator_ktype = &deadline_ktype, |
| 846 | .elevator_name = "deadline", |
| 847 | .elevator_owner = THIS_MODULE, |
| 848 | }; |
| 849 | |
| 850 | static int __init deadline_init(void) |
| 851 | { |
| 852 | int ret; |
| 853 | |
| 854 | drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq), |
| 855 | 0, 0, NULL, NULL); |
| 856 | |
| 857 | if (!drq_pool) |
| 858 | return -ENOMEM; |
| 859 | |
| 860 | ret = elv_register(&iosched_deadline); |
| 861 | if (ret) |
| 862 | kmem_cache_destroy(drq_pool); |
| 863 | |
| 864 | return ret; |
| 865 | } |
| 866 | |
| 867 | static void __exit deadline_exit(void) |
| 868 | { |
| 869 | kmem_cache_destroy(drq_pool); |
| 870 | elv_unregister(&iosched_deadline); |
| 871 | } |
| 872 | |
| 873 | module_init(deadline_init); |
| 874 | module_exit(deadline_exit); |
| 875 | |
| 876 | MODULE_AUTHOR("Jens Axboe"); |
| 877 | MODULE_LICENSE("GPL"); |
| 878 | MODULE_DESCRIPTION("deadline IO scheduler"); |