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