block/deadline-iosched.c

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